Homework 3: Due Feb 6

This assignment is be to be worked on individually-remember that it is important that you be able to solve these problems on your own in order to prepare you for the exams.

1. A sorting algorithm is described as stable if equal elements are in the same relative order in the sorted sequence as in the original sequence. Which of insertion sort, quicksort, and mergesort are stable, and which are unstable? Give a simple fix to make the unstable sorts stable.
   5 points.

2. Prob. 4-1, parts b, c, f, g, and h.
   5 points.

3. Solve (find the asymptotic upper bound for) the recurrence:
   T(n) = T(n - a) + T(a) + n
   where a is a positive constant, and T(a) is a constant.
   5 points.

4. Prob. 8-2, parts b, c, and d.
   5 points.