College of Computer & Information Science Fall 2006 Northeastern University Handout 6 CSU690: Algorithms and Data 22 September 2006

Review 2 (Tuesday, September 26)

1. We will discuss parts of Problem Set 1 about which students had most concerns.

2. Chapter 5, Exercise 1, page 246.

3. Suppose you would like to merge k sorted lists, each of length n, into one sorted list of length nk.

• One strategy is to use the merge operation we studied in class to merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of n and k?

• Give a more efficient solution to this problem, using divide and conquer.