Description

Grading Full credit will be given to correct solutions that are described clearly.
Problem 1 (Asymptotic Growth) Rank the following functions by nondecreasing order of growth; that is, find an arrangement g1,…,g10 of the functions satisfying g1 = O(g2), g2 = O(g3), …, g9 = O(g10). All the logs are in base 2.
.
Problem 2 (Recurrences) Give an asymptotic tight bound for T(n) in each of the following recurrences. Assume that T(n) is constant for n ≤ 2.
(a) T(n) = 2T(n/2) + n3
(b) T(n) = 7T(n/2) + n2
√
(c) T(n) = 2T(n/4) + n
(d) T(n) = T(n − 1) + n
Problem 3 (Binary Search – Python) Consider the two algorithms for binary search, shown in Figures 1 and 2. Each algorithm takes a sorted list of numbers, alist, and a number, item, and returns true if and only if item is an element of alist. The algorithm shown in Figure 1 is iterative whereas the algorithm shown in Figure 2 is recursive.
def binarySearch(alist,item): first = 0 last = len(alist)-1 found = False
while first<=last and not found: midpoint = (first + last)/2 if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
Figure 1: Iterative binary search
def binarySearch(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)/2 if alist[midpoint] == item:
return True
else:
if item<alist[midpoint]:
return binarySearch(alist[:midpoint],item)
else: return binarySearch(alist[midpoint+1:],item)
Figure 2: Recursive binary search
In the following, n is len(alist).
(a) According to the cost model of Python, the cost of computing the length of alist of size n using the function len is O(1), and the cost of extracting a slice of a list using : (e.g., alist[0:n/2]) is O(n). Based on this cost model:
(i) What is the asymptotic running time of the iterative binary search algorithm shown in Figure 1? (State the running time and give an upper bound for it.)
(ii) What is the asymptotic running time of the recursive binary search algorithm shown in Figure 2? (State a recurrence and solve it.)
(b) Implement these two algorithms using Python. For each algorithm, determineits scalability experimentally by running it with different sized sorted lists of numbers in the worst case. For instance, you can generate a sorted list of n numbers ranging between 1 and 107 (using range function of Python) and search for 1.
(i) Fill in following table with the running times in seconds.
Algorithm n = 104 n = 105 n = 106 n = 107
Iterative
Recursive
Specify the properties of your machine (e.g., CPU, RAM, OS) where you run your programs.
(ii) Plot these experimental results in a graph.
(iii) Discuss the scalability of the algorithms with respect to these experimental results.
(iv) Determine whether the experimental results confirm the theoretical results you found in (a).
(c) For each algorithm, determine its average running time experimentally by running it with randomly generated sorted lists of n numbers, and randomly generated keys. For instance, for each randomly generated list of size n, you can generate 50 different keys.
(i) Fill in following table with the average running times in seconds (µ), and the standard deviation (σ).
Algorithm n = 104 n = 105 n = 106 n = 107
µ σ µ σ µ σ µ σ
Iterative
Recursive
(ii) Plot these experimental results in a graph.
(iii) Discuss how the average running times observed in your experimentsgrow, compared to the worst case running times observed in (b).
(d) How can we improve the recursive binary search algorithm so that it has thesame asymptotic running time as the iterative one? (Make sure that the algorithm is still recursive after the improvements.)
Do we observe this improvement experimentally? (Redo the experiments in (b) for the worst-case analysis, with the improved binary search algorithm. Plot the running times of the given iterative algorithm, the given recursive algorithm, and the improved recursive algorithm as a graph.)