Class notes

Page 11

Sample answers to sample exam

1. Algorithm design
   • Greedy:

     Choose the next picture in sequence unless choosing the one after that would delay the start of a new page.

   • Local optimization:

     Put the pictures down in order. Then consider switching neighboring pictures if that saves a page.

   • Divide-and-conquer:

     Cut the sequence of pictures in half, optimize each half's layout, stop the recursion at some small size. (Note: This is not very promising, as it does not allow for deviating from the chronological order of the pictures except within certain arbitrary small subsequences where the recursion bottoms out.)

   • Dynamic programming:

     Solve all subproblems of the following type: Given a subsequence of the pictures, in the order they were taken but with some pictures missing from the sequence at the start and at the end, find an optimal layout for that sequence. (If no constraints are placed on the size of the missing set of pictures at either end, the algorithm is going to take exponential time. If the limit on the size is zero, it is like divide-and-conquer, which is not very good for this problem. If the size limit is a constant, the algorithm is not guaranteed to find the optimal solution but will run in polynomial time and will explore some deviations from the chronological order.)

2. Dynamic programming
   • A suitable parameter is a partially colored graph. (This leads to an exponential-time method and it no good because of that. But it is the natural attempt to apply dynamic programming to coloring.)

   • On the 'min' line change the sum of three terms to a maximum of three terms, and define the 'w' term to be the difference of the largest and smallest side of that triangle.

Previous page || Next page

Last edited (or copied to this place) at 10:35 PM, Tuesday, March 12, 1996.