CSci 433: Algorithm & Data Structure Analysis
Spring Semester 1999

Assignment #4
Due Tuesday, 23 March, 11:00 a.m. (Revised Date)

Prepare this assignment paper by the above deadline in accordance with the instructions given in the Professional Conduct and Assignments sections of the Syllabus .

1. To sort or not to sort: Outline a reasonable method for solving each of the following problems. Give the order of the worst-case complexity of your methods.

   1. You are given a pile of thousands of telephone bills and another pile of thousands of checks. Assuming that the person's telephone number appear on the checks, find out who did not pay.

   2. You are given a list containing title, author, call number, and publisher of all books in the campus library and another list of 30 publishers. Find out how many of the books were published by each of the 30 publishing companies.

   3. You are given a list of all the checkout records for the books checked out from the campus library last year. The checkout record includes the call number of the the book checked out, the name and identifier of the person checking the book out, and the date and time the book was checked out. Determine how many distinct people checked out at least one book.

2. Do exercise R-8.4 on page 337 of the Goodrich and Tamassia textbook.

3. Do exercise R-8.9 on page 337 of the Goodrich and Tamassia textbook.

4. Do exercise C-8.5 on page 338 of the Goodrich and Tamassia textbook.

5. Do exercise C-8.13 on page 339 of the Goodrich and Tamassia textbook.

UP to CSCI 433 assignments document?