1) Solve LCS problem using dynamic programming: algorithms agronomy 2) Design greedy procedure for the following problem -- interval coloring: you have a list of classes that specifies class start and end time $[s_i,e_i]$. You have to assign rooms to classes -- your goal is to minimize the total number of rooms used. Obviously you cannot skip a class and if two classes overlap they cannot be in the same room. The problem can be stated as color given intervals in fewest number of colors, so that no two intervals with the same color overlap. 3) Design recursive formula (first step in designing DP algorithm) for the problem: How many $n$-digit numbers have exactly k bits set? 4) You are given a collection if n bolts of different width and n corresponding nuts. You are allowed to try a nut and a bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two bolts together, or two nuts together. The problem is to match each bolt to its nut. Design an algorithm for this problem with average-case efficiency in Theta( n log n ). 5) You need to buy some filing cabinets. You know that Cabinet X costs $10 per unit, requires six square feet of floor space, and holds eight cubic feet of files. Cabinet Y costs $20 per unit, requires eight square feet of floor space, and holds twelve cubic feet of files. You have been given $140 for this purchase, though you don't have to spend that much. The office has room for no more than 72 square feet of cabinets. How many of which model should you buy, in order to maximize storage volume? Convert to a linear programming problem - DO NOT SOLVE THE LPP. 6) Given two strings a and b, the edit distance d(a, b) is the minimum-weight series of edit operations that transforms a into b. Allowed operations (all 3 have the same cost - say 1): Insertion of a single symbol at any position Deletion of a single symbol changes at any position Substitution of a single symbol at any position Design DP solution to find edit distance. 7) Surprise 8) Surprise