CS 477/677 Study Problems

Due date: September 22, 2005, 11:30 AM.

This assignment should be worked, but not handed in, since an examination is scheduled for that day.
  1. Any algorithm which sorts n items requires Omega(n log n) time in the worst case, provided we make what assumption?
  2. Two sorted lists have lengths 5 and 8, respectively. How many comparisons are needed to merge the two lists? (Exact answer, please.)
  3. Design an algorithm that sorts four items using at most five comparisons.
  4. Design a sorting network that sorts four items using at most five comparisons, or prove that no such sorting network exists.
  5. In some situations, an unordered list is more efficient than an ordered list to store items. Describe some of those situations.
  6. Work Exercise 6 on page 73 of your textbook.
  7. Work Exercise 4 on page 99 of your textbook.
  8. Work Exercise 2 on page 130 of your textbook.
  9. Work Exercise 8 on page 153 of your textbook.

Back to Course Page