CSci 433: Algorithm & Data Structure Analysis
Spring Semester 1999

Assignment #7
Due Friday, 30 April, Noon

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

Note: This is an optional assignment. If higher, the grade on this assignment will replace the lowest previous assignment grade. Of course, it is a good idea for everyone to know how to work these problems for the final exam.

• Do exercises R-12.2 and R-12.4, on page 515 of the Goodrich and Tamassia textbook.

• Modify the binary search algorithm so that it splits the input not into two sets of almost-equal sizes, but into two sets of approximately one-third and two-thirds. Show either the pseudo-code or a Java implementation. Give a running time recurrence relation T(n) (where n is the length of the sequence) and solve it.

• Use the binary search technique to devise an algorithm for the problem of finding the square-roots of natural numbers. Given an n-bit natural number N, compute ceiling(sqrt(N)) using O(n) additions and shifts. (Remember that a shift will allow us to do multiplication by 2 or division by two efficiently.)

UP to CSCI 433 assignments document?