CSE 101 Homework 1
Sorting, Selection, & Divide-and-Conquer
Due October 20, 1998 at the beginning of lecture
100 points total

Note that ``Exercises'' and ``Problems'' are numbered separately in this textbook.

1. (5 pts.) Exercise 1.3-1.

2. (10 pts.) Exercise 1.3-4. Also, solve the recurrence to show that the running time of this modified version of insertion sort is still in the worst case.

3. (5 pts.) Exercise 1.4-2.

4. (5 pts.) Exercise 8.1-1.

5. (15 pts.) Exercise 8.4-1. Note that the ``Best-case partitioning'' subsection of section 8.2 just gives an informal argument - for this exercise you need a complete proof. To get an idea of what such a proof might look like, look at section 8.4.1.

6. (25 pts.) Problem 8-3, parts (a) and (b). Give a proof of correctness, using induction, for part (a).

7. (5 pts.) Exercise 9.2-1.

8. (5 pts.) Exercise 10.3-3. Just give a brief explanation.

9. (25 pts.) Problem 10-2, part (c). Modify the SELECT algorithm to compute the weighted median, and give a running time analysis for your algorithm. You do not need to formally prove your algorithm's correctness.