Design by Induction

This set of exercises accompanies Lecture of Week 6 of the course Algorithm Design and Analysis.

Implementation problems

Implement the solution for one of folowing algorithms (discussed in lecture from week 6).

The successful party problem [Manber, chapter 5.3]
The celebrity problem [Manber, chapter 5.5]
The skyline problem [Manber, chapter 5.6]

Creative exercises

Solve following problems (Solve = Explain the designed algorithm, prove its correctnes (or design by induction) and analyse its time complexity. And then, finally, implement)

Skyline intersection. [Manber, Exercise 5.11] Suppose that there are two different skylines. One is projected on a screen, filled with blue color, and the other is superimposed on the first one, filled with red color. Design an efficient algorithm to compute the shape that will result purple by superimposing the red surface over the blue surface (the intersection of the two skylines)

Checking Intervals for Containment. The input is a set of n intervals on a line: I1, I2, ..., In. Each interval is given by the x-coordinates of its two endpoints. Identify and mark all intervals that are contained in some other interval. An interval Ij should be marked if there exists another interval Ik such that Left(Ik) <= Left(Ij) and Right(Ik) >= RightIj)

Example:

The list of intervals is:
[6, 9]; [5, 7]; [0, 3]; [4, 8]; [6, 10]; [7, 8]; [0, 5]; [1, 3]; [6, 8]

The intervals which are contained in others are:
[5, 7] [0, 3] [7, 8] [1, 3] [6, 8] [6, 9]