CSC 344
Homework 3

Assigned March 7, due March 31

You have 13 problems, and 24 days to do them (including Spring Break, which I'm sure you plan to spend doing Algorithms homework!).

As you're doing these, think of which one you'd like to present in class, and let me know as soon as you've decided. Solutions will be presented in class March 31 and April 2.

Written problems from textbooks

• Shaffer problem 7.6 (which sorting algorithms are stable?)
• Shaffer problem 7.7 (making a non-stable sorting algorithm stable)
• Shaffer problem 7.15 (matching nuts and bolts).
  1. Give an obviously-correct brute-force algorithm and prove that it runs in O(n²) time.
  2. Prove an Ω(n log(n)) lower bound for the worst case of any algorithm that solves this problem.
  3. Give a randomized algorithm whose average-case complexity is O(n log(n));
     prove that it works, and that its average-case complexity really is O(n log(n)).
• CLRS problem 6-3 (Young tableaux)
• CLRS exercise 7.4-5 (also discussed on p. 242 of Shaffer)
• CLRS problem 7-4 (tail recursion and quicksort; see also Shaffer exercise 7.8)
• CLRS problem 7-6 (fuzzy sorting of intervals)
• CLRS exercise 8.2-4 (answering range queries)
• CLRS exercise 8.4-2 (analysis of bucket-sort)
• CLRS exercise 9.1-1 (find second-smallest)
• CLRS exercise 9.3-5 (given a linear-time median algorithm, write a linear-time k-selection algorithm)
• CLRS exercise 9.3-9 (find optimal location for oil pipeline)

Programming problems

• Shaffer project 7.2 (double insertion sort) OR 7.4 (merge-sort on different data structures)