CSE 417 Homework 3, Winter 2011

1. (10 points). In Kleinberg and Tardos, Chapter 3, Exercise 11 (p.111) (The virus spread of infection problem).
2. (10 points). In Kleinberg and Tardos, Chapter 4, Exercise 2 (p.189) (Minimum spanning trees before and after squaring the costs.)
3. (20 points). Chapter 4, Exercise 4 (Subsequence matching algorithm)
4. (20 points). Chapter 4, Exercise 6 (Triathlon scheduling)
5. (20 points). Solve the Video Event Archiving Problem, described as follows.

   The video content analysis department at local startup ThereTube.com has identified certain frames f1, f2,...,fn of a long video sequence V as significant. These frames are to be archived within 5-second video clips, extracted from V at the original resolution. Once the extraction is done, V will be converted to a low-resolution, compressed format and the original discarded, making it impossible to obtain arbitrary frames at the original resolution unless they are parts of the special 5-second clips. Note: there are 24 frames per second in both the original and the clips.

   The archiver's job is to determine a set {C1, C2,...,Cm} of 5-second clips (i.e., their starting frames) such that each fi is contained in at least one of the clips, and such that as few clips as possible are used. The archiver's plan is to look first for a maximal group of frames that can all be covered by one clip, capture that clip, check off the frames that have been handled, and then recursively process the rest until all the fi are covered.

   (a) You've been hired as an outside consultant to evaluate the archiver's method, in part because the company is interested in automating this phase of the process. Is the archiver's method optimal? If so, give an argument for it. If not, give an example set of frames where it fails, and offer a method that is optimal and explain why it is.

   Here is a diagram showing one instance of the problem, with time going left to right. The archiver has used three clips here to cover the 6 special frames.

   V-------------------------------------------
     f1         f2 f3 f4         f5 f6
     C3------   C1------         C2------
   

(b) (optional and ungraded) The company now asks you to bid on the job of implementing the algorithm that automates the archiver's job. What would be your bid and why?
6. (20 points). (a) Use the algorithm on p.172 to construct a Huffman code for the following alphabet and probabilities, showing your final Huffman tree, as well as the intermediate trees involved in its construction.

   u: 0.04
   v: 0.03
   w: 0.03
   x: 0.2
   y: 0.3
   z: 0.4
   

   (b) Give the encoding for the following 15-byte string: "xyzzyxyzzyvuxwy"

   (c) How many bytes does the encoding require, including a starting byte that gives the length of the string?