## Homework Assignments - Spring 2008

These homeworks are due in the homework box outside the TA office, 1044 TMCB by the time the building closes on the due date.

## CS235 - Homework 1

Textbook Exercises

5.6

5.8

5.12

5.16a

## CS 235 - Homework 2

Textbook Exercises

8.1a Give the content of the array after each iteration of the main loop.

8.1c Draw a tree-like diagram that shows the steps of mergesort on the array.

8.1e Show the steps of the median-of-three partitioning algorithm on the array.

(Don't show all the steps of quicksort. Only show the steps of one partitioning.)

8.4acd

8.5acd

8.6acd

## CS 235 - Homework 3

Textbook Exercises

18.1 a, b, d

18.2 d, e, f

18.3

18.7

18.9 a

## CS 235 - Homework 4

Textbook Exercises

19.1 (instead of showing the result of deleting the root, show the result of deleting 5, 4, and 3 from the BST)

19.5 (instead of doing the part that deals with red-black trees, show the result of deleting 4, 7, 9, and 6 from the AVL tree)

## CS 235 - Homework 5

Textbook Exercises

20.5 a,b,c

## CS 235 - Homework 6

Textbook Exercises

21.3 (Use MIN-heaps in this problem. First show the result of inserting the numbers one at a time into a MIN-heap. Then show the result of building a MIN-heap from the original list of numbers using the buildHeap algorithm.)

21.6 (Use MAX-heaps in this problem. Show the result of building a MAX-heap from the given list of numbers using the buildHeap algorithm. Then show the result of two deleteMax operations on the heap you built.)