1. Write the method Take() from the Linq namespace.
2. Write the method Aggregate() from the Linq
namespace.
3. Write the method OrderBy() from the Linq namespace.
4. Write a method maxBy() that takes an IEnumerable<T> and a function f from T to int, and returns the element in the enumeration for which f returns the greatest value.
5. Write a method maxVal() that takes an integer start,
an integer end and a function f from int
to int. The method should determine the value i
in the range start <= i <= end
for which f has the greatest value. Your method should
return two values: the value i and the value f(i).
Do not evaluate f(i) twice.
6. Write a method that takes a filename and returns an enumeration of all words in the file, where a word is any sequence of non-space characters.
7. Write a method that takes two strings s and t and returns true if the characters in t are a subsequence of the characters in s, i.e. if s contains all the characters in t in the same order (not necessarily contiguously). Can you write this both iteratively and recursively?
8. Repeat the previous exercise, but for arbitrary enumerations e and f.
9. Modify the rod-cutting program from the lecture so that it prints out the rod sizes needed to attain the maximum possible price.
10. Write a recursive method to determine if a string is a palindrome.
11. Write a method to find the length of the longest palindrome contained in a given string. (Use dynamic programming.)
11. Modify your method from the previous exercise to return the palindrome itself.
12. Write a method to find the length of the longest ascending subsequence in an array of integers, where a subsequence is not necessarily contiguous. Use dynamic programming.
13. Modify your method from the previous exercise to print the longest subsequence.
14. Write a method that takes an array of coin denominations (e.g. 1, 5, 10, 20, 50 for the Czech Republic) and an integer k representing an amount of money. Your method should return the smallest number of coins that will add up to the value k, assuming that you can use as many coins as you like of each denomination. Use dynamic programming to achieve a sub-exponential solution.
15. Modify the previous method to print the values of the coins that are used in the solution.
15. Write a method that takes an array of 16-bit integers and a 16-bit integer t, and returns true if any subset of the integers in the array add up to t. Use dynamic programming to build a solution that runs in sub-exponential time.
16. Suppose that we multiply two matrices of dimensions (m x n) and (n x p) using the naive algorithm, i.e. a triple loop. (More asymptotically efficient algorithms exist, though we won't consider them here). How many scalar multiplications are required? Now consider the problem of computing the product of matrices M1 x M2 x … x Mn of various sizes. Suppose that matrix Mi has dimensions di-1 x di for some series of integers d0, d1, … dn. Matrix multiplication is associative, so we may parenthesize the multiplication in any way we like. The total number of multiplications will depend on the parenthesization we use. Write a method that determines the minimum number of scalar multiplications required over all possible parenthesizations. Use dynamic programming.
17. Modify the previous method to print out the optional parenthesization.
18. Consider the following game. You are given a row of squares, each of which contains a positive integer. You start on the leftmost square. At each step, if you are currently on a square with value N, then you may jump either N squares to the left or N squares to the right. (You may not jump off the left or right edges of the board.) You win if you reach the rightmost square.
Write a function canWin that takes an array of integers representing a board in this game and returns true if it is possible to win, i.e. if there is some sequence of moves from the leftmost to the rightmost square. If no win is possible, the function should return false.
19. Repeat the preceding exercise, but instead return an integer representing the minimum number of hops to reach the rightmost square, or -1 if it cannot be reached.