Homework 1 Solution

Homework submission A pdf copy of your own solutions to Problems 1–3 should be submitted at SUCourse.




Grading Full credit will be given to correct solutions that are described clearly.




Problem 1 (Asymptotic Growth) Rank the following functions by nondecreas-ing order of growth; that is, find an arrangement g1; :::; g10 of the functions satis-fying g1 = O(g2), g2 = O(g3), ..., g9 = O(g10). All the logs are in base 2.




n2n; n log(n); n!; n; n100; 2n; log(n); log(n!); (log(n))!; 22n :




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.




T (n) = 2T (n=2) + n3



T (n) = 7T (n=2) + n2
p




(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.1 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 Fig-ure 2 is recursive.














































These algorithms are taken from the book “Problem Solving with Algorithms and Data Structures using Python” by Miller and Ranum: http://interactivepython.org/ runestone/static/pythonds/index.html .






1



CS301, Homework 1



















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













2



CS301, Homework 1










In the following, n is len(alist).




According to the cost model of Python, the cost of computing the length of a list 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:



What is the asymptotic running time of the iterative binary search al-gorithm shown in Figure 1? (State the running time and give an upper bound for it.)



What is the asymptotic running time of the recursive binary search algo-rithm shown in Figure 2? (State a recurrence and solve it.)



Implement these two algorithms using Python. For each algorithm, determine its 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.



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.




Plot these experimental results in a graph.



Discuss the scalability of the algorithms with respect to these experimen-tal results.



Determine whether the experimental results confirm the theoretical re-sults you found in (a).



For each algorithm, determine its average running time experimentally by run-ning it with randomly generated sorted lists of n numbers, and randomly gen-erated keys. For instance, for each randomly generated list of size n, you can generate 50 different keys.



Fill in following table with the average running times in seconds ( ), and the standard deviation ( ).






3



CS301, Homework 1













Algorithm


n = 104
n = 105
n = 106


n = 107












































Iterative




















Recursive























Plot these experimental results in a graph.



Discuss how the average running times observed in your experiments grow, compared to the worst case running times observed in (b).



How can we improve the recursive binary search algorithm so that it has the same asymptotic running time as the iterative one? (Make sure that the algo-rithm is still recursive after the improvements.)



Do we observe this improvement experimentally? (Redo the experiments in




for the worst-case analysis, with the improved binary search algorithm. Plot the running times of the given iterative algorithm, the given recursive al-gorithm, and the improved recursive algorithm as a graph.)
































































































4