Due: Wednesday, March 13 at the beginning of class.
From the book: 16.1-3 [page 422]. Only show that the greedy algorithm that selects the activity of shortest duration does not work.
From the book: 16.2-1 [page 427]
From the book: 4.1-5 [page 75].
From the book: 16.2-4 [page 427].
From the book: 16.2-2 [page 427].
This is a dynamic programming problem. It is not enough just to produce an algorithm. If you provide only an algorithm, you will receive no credit. You must go through the steps of a dynamic programming algorithm. Define the subproblems that you will solve. Write recurrences that relate solutions to subproblems. Say how to compute all of the solutions to the subproblems.
From the book: 15-5(a) [406] Edit distance. Omit the kill operation. Note that the definition of edit distance in this problem is not the same as the definition used in class.
This is a dynamic programming problem. It is not enough just to produce an algorithm. If you provide only an algorithm, you will receive no credit. You must go through the steps of a dynamic programming algorithm. Define the subproblems that you will solve. Write recurrences that relate solutions to subproblems. Say how to compute all of the solutions to the subproblems. Say how to write out the sequence of operations to use. (Just show the operations, as shown in the left-hand column of the example that converts "algorithm" to "altruistic".)
From the book: 15-6 [page 408] Planning a company party. Do not worry about the details of how the tree is organized. Each person is either invited or not invited. Consider computing two scores for each persion (or, equivalently, for each node of the tree).
Define what the scores are.
Derive equations that can be used to compute each score for a given node. Shop around.
Explain how to compute all of the scores and write them in the nodes of the tree. Store the scores in an order so that, any time you need to get another score, you have already recorded that other score.
Explain how to decide whom to invite, using a tree with the scores recorded in its nodes.
How much time does it take, in terms of the number of employees, to plan the party?
From the book, 16.2(a,b) [page 447]. Scheduling to minimize average completion time