## Description

Problem 1. (8 marks)

a. Consider the algorithm of the expoentiation problem discussed in class.

(i) Show the sequence of recursive calls to compute power(b, 79).

(ii) To compute power(b, n) for an arbitrary integer n > 0, at most how many recursive calls (in

terms of n) to the procedure power(.) are needed? Justify your answer briefly, and give an

instance of n > 50 for which the worst-case occurs.

b. Consider Exercise 4.2-3 (CLRS p.82, which is also given in Problem Set #4): How would you modify

Strassen’s algorithm to multiply n × n matrices in which n is not an exact power of 2? Explain how

your algorithm works for the case where n = 30.

Problem 2. (12 marks)

a. Consider the following problem from Problem Set #4: Given a set P of n teams in some sport, a

Round-Robin tournament is a collection. of games in which each team plays each other team exactly

once. Design an efficient algorithm for constructing a Round-Robin tournament assuming n is a

power of 2. Note that every team can play at most one game per day and the goal is to schedule all

the games in n − 1 days.

You are asked to answer the following questions:

(i) Suppose there are 8 teams, named {t1, t2, . . . , t8}. What will be the schedule produced by your

algorithm? Show a concrete schedule among the 8 teams.

(ii) What is the running time of your algorithm in terms of the number of games played (i.e., making

the arrangement for one game takes O(1) time)? Give a recurrence relation and briefly explain

what it solves to.

(iii) Let us assume n is an even number which may not be a power of 2. Can your algorithm be

generalized so that every team plays at most one game per day and all the games are to be

completed in n − 1 days? If yes, show how, and if no, argue by a counterexample.

b. Consider the following problem from Problem Set #4: You have a manufacturing company who

produces some form of glass that is more resistant than a typical glass. In your quality control

section you do testing of samples and the setup for a particular type of cup produced is as follows.

You have a ladder with n steps and you want to find the highest step from which you can drop a

sample cup and not have it break. We call this the highest safe step. A natural approach to find that

1

highest safe step is binary search: drop a cup from step n/2 and depending on whether it breaks or

not try step n/4 or 3n/4 (and of course if it broke you take another sample), and so on. Of course

you can find the answer quickly (in O(log n) drops) but the drawback is you may break many cups.

You are asked to answer the following questions.

(i) Suppose k = 3. Describe a strategy that uses at most 3 cups to find the highest safe step among

the n steps. If T3(n) is the function that upper bounds the number of experiments performed

by your algorithm (i.e. how many times you drop a cup) for k = 3, it must be the case that

T3(n) ∈ o(

√

n) since for k = 2 we can have T2(n) ∈ O(

√

n).

(ii) What if k = 4? Describe your solution. You can describe it on top of your solution for k = 3.

Note: The question here is a generalization of the “magic wand” question we studied earlier.

Problem 3. (8 marks)

Consider the Maximum Subarray Sum Problem given in Problem Set #4: You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of

numbers which has the largest sum.

You are asked to answer the following questions.

a. Consider the input array B = [2, −3, 2, −1, 3, −1, 2, −1], with the index to the first array element

being 1 and the index to the last array element being 8. What is the output of running your

algorithm?

b. Answer the same question as above for the input array C = [1, −3, 1, 3, −4, 5, −2, −2, 3].

c. If the given array consists of only positive numbers, then the solution is the sum of all numbers

in the array. Now consider the the maximum subarray problem where an input array has exactly

two negative numbers in consecutive positions. Describe an algorithm for this problem. Your

algorithm must be asymptotically faster than your algorithm for the original problem. You do not

need to write pseudocode but the description of your algorithm should be clear. What is the running

time of your algorithm? Justify your answer briefly.

Problem 4. (12 marks) Write an efficient algorithm (in pseudocode) that searches for a value in an

n × m table (two-dimensional array). The table is sorted along the rows and columns, i.e., for table T

(1 ≤ i ≤ n, 1 ≤ j ≤ m)

T[i, j] ≤ T[i, j + 1]

T[i, j] ≤ T[i + 1, j]

Analyze the running time of your algorithm in terms of n and m (i.e., your asymptotic bound should be

a function of n and m). Consider both the best-case and worst-case running times. The following is an

example of such a table.

1 4 7 11

2 5 8 12

3 6 9 16

10 13 14 17

18 21 23 26

2

Hint: Imagine a robot that starts from the top right position and walks, repeatedly if necessary, each time

either to the left or to the row below depending on the result of comparing the value of the box with the

target value; eventually the robot reaches the box that holds the target value, or report that the target

value is not in the table.

Before you give your algorithm in pseudocode, please first describe your algorithm in plain words.

3