CS 252: Algorithms

Problem Set #4

Interval scheduling, divide-and-conquer, and implementing graph algorithms

1. Do problem 3 on pages 189-190.
2. Do problem 6 on page 191.
3. Show that any function T(n) that satisfies T(n) ≤ T(n/2) + 1 is O(log n).
4. Show that any function T(n) that satisfies T(n) ≤ 3T(n/3) + n is O(n log n).

5. Suppose you have an array of integers, and you want to try a divide-and-conquer method for finding the sum of the integers: split the array in half, sum each half, and then add the two sums to get the final result.

   1. Give a recurrence relation for the running time T(n) of this algorithm.
   2. Solve the recurrence to get a tight bound on T(n).
   3. Compare your results for this problem to mergesort. In particular, what difference between the two algorithms accounts for the differences in their running time bounds?
   4. Would you use divide-and-conquer summation in practice? Why or why not?

6. The program graph.py has a Graph class, with a load method that loads graph descriptions from text files, and a breadthFirstSearch method that returns the results of a breadth-first search of a graph. It also includes stubs for a getShortestPaths method and a getTopologicalSort method. Here are a couple tiny sample graphs: directed.txt and undirected.txt.

   1. Pick either getShortestPaths or getTopologicalSort and implement it. Your implementation should adhere to the specification comment at the top of the method.
   2. Add testing code for your method to the main program at the bottom of the source file.
   3. Collect and present timing data for your implementation. Show that your timing data support the complexity claims developed in the textbook for the algorithm you chose.