Assignment #6 CMPUT 204

Assignment #6
(Total 40 marks)
CMPUT 204
Most questions here are based on Problem Set #4. Possible solutions to some other problems may
also be found online. You may consult, adopt, or revise any of these solutions to compose your answers.
But recall that you must understand what you submitted and be able to explain your answers. If your
algorithm is the same as the one given in the Problem Set, just indicate so; otherwise please specify.
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