4005-800-70 Theory of Computer Algorithms
Module 5 Homework Assignment

Reading
Problems
Submission

• Cormen, Leiserson, Rivest, & Stein, Chapter 11.
• Cormen, Leiserson, Rivest, & Stein, Chapter 12.
• Jon Bentley. Programming pearls: Writing correct programs. Communications of the ACM, 26(12):1040-1045, December 1983.
  [PDF, 648,550 bytes]

1. Cormen, Leiserson, Rivest, & Stein, Exercise 11.2-1, page 228.
2. Cormen, Leiserson, Rivest, & Stein, Exercise 11.2-2, page 229.
3. Cormen, Leiserson, Rivest, & Stein, Exercise 11.3-1, page 236.
4. Cormen, Leiserson, Rivest, & Stein, Exercise 11.3-2, page 236.
5. Cormen, Leiserson, Rivest, & Stein, Exercise 11.4-1, page 244.
6. Cormen, Leiserson, Rivest, & Stein, Problem 11-3, page 250.
7. Cormen, Leiserson, Rivest, & Stein, Exercise 12.1-1, page 256.
8. Cormen, Leiserson, Rivest, & Stein, Exercise 12.1-4, page 256.
9. Cormen, Leiserson, Rivest, & Stein, Exercise 12.2-1, page 259.
10. Cormen, Leiserson, Rivest, & Stein, Exercise 12.2-5, page 259.
11. Cormen, Leiserson, Rivest, & Stein, Exercise 12.3-3, page 264.
     
12. The pseudocode for binary search in a sorted array appears at the bottom left of page 1041 of Bentley's article. What is the worst-case asymptotic upper bound for the running time of this algorithm? Prove your answer.
     
13. Here is a variation of the binary search algorithm. Given an array X[1..N] containing distinct integers in ascending sorted order, and given a search value T, return the index P defined as follows:
    • If T appears in X, then X[P] = T.
    • If T does not appear in X and T < X[1], then P = 0.
    • If T does not appear in X and X[1] < T < X[N], then X[P] < T < X[P+1].
    • If T does not appear in X and X[N] < T, then P = N.
    Informally, if T does not appear in X and T were to be inserted into X, then T would go between the elements at indexes P and P+1. Give the pseudocode for this binary search algorithm. Use a loop invariant to prove that your pseudocode is correct.
     
14. Bentley's article, Problem 5, page 1044.

Create a PDF file named "<username>.pdf", replacing <username> with your Computer Science account user name. The PDF file must begin with the following information:

The PDF file must contain your answer for each problem above. Make sure I can tell where each answer starts by marking them Problem 1, Problem 2, and so on.

Send me an email message at ark­@­cs.rit.edu. In the text of your email message, list the same information that appears at the top of the PDF file. Include the PDF file itself as an attachment to your email message.

The Module 5 homework assignment is due by 6:00pm on Tuesday, 13-Jan-2004. The date and time at which your PDF file arrives at my email inbox determines whether the assignment is on time. After I receive your email message, I will send you an email message confirming that I received your assignment. (The confirmation process is not automated, so you may not receive the confirmation message immediately.)

See the Course Policies for further information on grading the homework assignments, late homework assignments, and plagiarism.

Theory of Computer Algorithms 4005-800-70 Winter Quarter 2003

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2004 Alan Kaminsky. All rights reserved. Last updated 07-Jan-2004. Please send comments to ark­@­cs.rit.edu.