Due

Assignment

07/18/03

18.1-4, 18.1-5, 18.2-1, 18.2-2, 21.3-1, 22.3-2, 22.3-10, 22.4-3, 22.5-1, 22.5-2, 22.5-6, 23.1-1, 23.1-3, 23.1-9, 23.2-1, 23.2-2, 24.1-1, 24.1-4, 24.2-4, 24.3-1, 24.3-5, 26.1-1, 26.1-6, 26.2-2, 26.2-4.

This will be covered in the last week: 17.1-1, 17.1-3, 17.2-1, 17.2-2, 17.3-2, 17.3-3, 34.1-3.

Implement Bellman-Ford algorithm.

Solutions: ps, pdf.

07/04/03

15.2-1, 15.2-3, 15.2-5, 15.3-2, 15.4-1, 16.1-2, 16.2-4, 16.2-5, 16.3-2, 16.3-4.

15.7 - develop an algorithm, next time best description will be published and you'll be assigned to implement it (or your own solution).

Implement Huffman algorithm, pick a big text file (that contains a real English text), find frequencies of all characters in it, compress this file and report the compression rate received, compress it with zip or any other well-known compression program, report its compression rate also.

Solutions: ps, pdf.

06/27/03

(numbers are from the Second Edition) 7.2-1, 7.2-2, 7.2-3, 7.4-1, 8.1-1, 8.1-3, 8.2-1 (for reversed array), 8.2-2, 8.3-1, 8.3-2, 8.4-1, 11.2-2, 11.3-1, 12.1-1, 12.2-1, 13.1-1, 13.1-6, 13.2-4.

Implement Randomized Quick Sort.

Solutions: ps, pdf.

06/20/03

Same as below but in pdf, due Nathan Carter.

1.1-1(do this for Bubble, Insertion and Merge sorts but with inversed array), 1.2-3, 1.2-5, 1.3-3, 1.3-4, 2.1-1, 2-1, 3.2-1 .. 3.2-4, 4.1-1, 4.2-1, 4.2-3, 7.1-1, 7.2-5, 8.1-1(do this both for Heap and Quick sorts, you can skip some similar steps if you feel comfortable with procedure). Implement Merge, Heap and Quick sorts.

Solutions: ps, pdf.