[Solved] CS301 Homework 1-Asymptotic Growth and Recurrences

Problem 1 (Asymptotic Growth) Rank the following functions by nondecreasing order of growth; that is, find an arrangement g₁,,g₁₀ of the functions satisfying g₁ = O(g₂), g₂ = O(g₃), , g₉ = O(g₁₀). 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.

• T(n) = 2T(n/2) + n³
• T(n) = 7T(n/2) + n²

• T(n) = 2T(n/4) + n
• 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 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).

• 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:
  • 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.)
  • What is the asymptotic running time of the recursive binary search algorithm shown in Figure 2? (State a recurrence and solve it.)
• 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 10⁷ (using range function of Python) and search for 1.
  • Fill in following table with the running times in seconds.

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 experimental results.
• Determine whether the experimental results confirm the theoretical results you found in (a).

• 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.
  • Fill in following table with the average running times in seconds (), and the standard deviation ().

• Plot these experimental results in a graph.
• Discuss how the average running times observed in your experimentsgrow, compared to the worst case running times observed in (b).

• 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.)

[1] 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 .