Hand in on paper by 8:30 AM Monday, 26 Oct 2015. Please also submit the PDF
version of your LaTeX write-up via Moodle. (I'll discuss in class why I'm asking
occasionally for both PDF and paper.)
- Consider the worst-case linear time selection algorithm SELECT in section 9.3 of CLRS, which begins
by dividing our N items into 5-element groups. Why do we use 5-element groups instead of 3-element
groups, which would seem to work similarly but more simply? To answer this question, construct
the recurrence that would result from a 3-element-group version of SELECT, and show what happens in
the resulting analysis.
- Do the problem entitled "DLN's Starbucks Problem," posted on Moodle.
- Provide an analysis of the algorithm for identifying the optimal seam in an image, where
the notion of an optimal seam is described in Avidan and Shamir's "Seam Carving for Content-Aware
Image Resizing." Refer explicitly to sections and pages in the paper where appropriate.