Theoretical Computer Science (M21276)
Part B/7: Analysis of algorithms
(January 10-14, 2022)
Question 1. Consider two algorithms below to compute xn. Algorithm A:
Copyright By PowCoder代写 加微信 powcoder
power := 1
for i:= 1 to n do
power := power ∗ x
Algorithm B: power := 1 while n>0 do
if n is odd then power:=power∗x x := x ∗ x
n := n ÷ 2
In each case compute the number of loop iterations required in the worst case. Assuming the primitive operations are multiplication (∗) and integer part after division (÷) deduce the time complexity functions in each case and compare values when n = 1000.
Question 2. We discussed two search algorithms: the sequential search which had a time complexity function TS (n) = An, and the binary search which had time complexity function TB (n) = B log2 n. Suppose for n = 128 the sequential search takes 3.2 × 10−4 seconds, while the binary search requires 7 × 10−5 seconds.
(a) Determine the constants A and B.
(b) For what n does it become advantageous to use the binary search?
(c) While the sequential search works on any list, the binary search requires the list to be sorted using the mergesort routine. Assume this has time complexity function TM (n) = Bn log2 n, where the constant B is the same as above. What is the total time complexity of the sort and binary search procedure?
(d) Assuming we begin with an unsorted list, when is the sequential search preferred over the combination of sort and binary search?
(e) Suppose that we wish to repeatedly search a given list many times (unsorted list). What is the time taken for m sequential searches of a length n list? What is the time taken for a sort and m binary searches of the same list?
(f) If n = 106 ≈ 220, for what values of m (approximately) is it better to do the sort and binary search?
Question 3. Consider the problem of given a list of numbers determining if any number appears three or more times. Design an algorithm for triplicate detection and discuss its complexity.
Question 4. Suppose algorithms A and B require respectively n2 and 2n operations for an input of size n. For a machine that can perform 109 operations per second, calculate the largest input which A and B can compute within 1 second, 1 hour, 1 year, 1century, the lifetime so far of the universe. (210 ≈ 103; 1 day ≈ 8 × 104 seconds; 1 year ≈ 3 × 107 seconds; the age of the universe is about 15 billion years.) How the results will be changed when we buy a new machine which runs 1000 times faster?
Question 5. Suppose that, in a divide-and-coquer algorithm, we always divide an in- stance of size n of a problem into n subinstances of size n/3, and the dividing and com- bining steps take linear time. Write a recurrence equation for the running time T (n).
Question 6. Suppose that there are n = 2k teams in an elimination tournament, in which there are n/2 games in the first round, with the n/2 = 2k−1 winners playing in the second round, and so on.
Develop a recurrence equation for the number of rounds in the tournament. How many rounds are there in the tournament when there are 64 teams?
Solve the recurrence equation of part (a).
Question 7. Discuss the complexity of Selection sort:
procedure selection-sort (n: integer; var S : array [1 . . . n] of integers) var i, j : integer;
for i:= 1 to n − 1 do
for j := i + 1 to n do
if S[j]