Weekly Note 5, DM45, spring 2007

Lecture March 7

• Orthogonal Range Searching (chapter 5).

Discussion Section March 5

• Exercises 4.1, 4.2, 4.3, 4.15.
• Show that RandomPermutation generates all permutations with the same probability.
• Show that it must take at least the order of n log n to compute the intersection of n halfplanes (some model assumptions are required to make this formal, but you should ignore that). Hint: reduce from sorting.

Announcements

• The obligatory assignment has deadline Wednesday, May 16, 2007, 12:00.