COT 5405 Analysis of Algorithms Fall 2004

On-Campus Exam #1

Name: ______

UFID: ______- ______

E-mail: ______

Instructions:

1. Write neatly and legibly

2. While grading, not only your final answer but also your approach to the problem will be evaluated

3. You have to attempt only TWO problems. If you attempt more than two problems, we will grade the First two of them. If you forget to mark it and tell us right after the exam, even then we would correct the first two only.

4. Each problem carries 10 points

5. Total time for the exam is 50 minutes

6. You are not allowed to use a calculator for this exam

I have read carefully, and have understood the above instructions. On my honor, I have neither given nor received unauthorized aid on this examination.

Signature: ______

Date: ____ (MM) / ____ (DD) / ______(YYYY)
Question 1:

Solve the recurrence relation without using Master’s theorem:

T(N) = 3T(N/2) + cN (c is a constant)

Derive a Theta expression for T(N).


Question 2:

A and B are playing a guessing game where B first thinks up an integer X (positive, negative or zero, and could be of arbitrarily large magnitude) and A tries to guess it. In response to A’s guess, B gives exactly one of the following three replies:

a)  Try a bigger number

b)  Try a smaller number or

c)  You got it!!

Design an efficient algorithm to minimize the number of guesses A has to make. An example (not necessarily an efficient one) below:

B thinks up the number 35

A’s guess / B’s response
10 / Try a bigger number
20 / Try a bigger number
30 / Try a bigger number
40 / Try a smaller number
35 / You got it


Question 3:

There are n students in a class. The test results are out and assume, for your convenience, that all the students had distinct grades (numbers). You can think of the test result as an unsorted integer array. A student X has been told that his rank in the class is R (R is an integer and obviously, 1 <= R <= n). He wants to find out the k boys who are ranked closest to him (k/2 students below him, and k/2 students above). Devise an efficient algorithm to identify the scores of these k boys.

Analysis of Algorithms Fall 2004 On-Campus Exam #1 Page 7 of 7