Due: Friday December 7 by 2pm in E2-219 (my office)

Reading: Chapters 15, 16, 23 and Sections 25.1-2

From the text
1. (3 pts) Page 338 15.2-1
2. (3 pts) Page 338 15.2-4 (count the references in line 9)
3. (3 pts) Page 350 15.3-5
4. (3 pts) Determine an LCS of the sequences
      1 0 0 1 0 0 0 1 0 0 0
    and
      1 1 0 0 0 1 1 0 1 1 0
5. (4 pts) Page 356 15.4-5
6. (6 pts) Page 367 15-4
7. (4 pts) Page 379 16.1-4
8. (5 pts) Page 384 16.2-4
9. (5 pts) Page 384 16.2-5
10. (10 pts) Page 402 16-1
11. (5 pts) In the weighted-activity-selection problem you are given a set of n activities, S = {1, 2,..., n}. Each activity has a start time s_i , an end time e_i where s_i < e_i, and also a weight w_i. The problem is to select a set of mutually compatible activities. Activities i and j are compatible if e_i <= s_j or e_j <= s_i. In the text the goal was to select the largest number of mutually compatible activities. But here the goal is to maximize the weight of the selected activities. That is, we want to find a subset A of S which,

            maximizes SUM_{i in A} w_i
            subject to For all i,j in A, e_i <= s_j or e_j <= s_i.

Give a dynamic programming algorithm to solve this problem in O(n²) time. You may assume that the activities are ordered by increasing end times:
            e₁ <= e₂ <= ... <= e_n .

Solutions (pdf)

Sample Final (pdf)
Solutions to Final (pdf)

Access to Solutions