Homework 3

Download the corresponding ipynb file here: hw-3.ipynb.

Recursive Insertion Sort

You can also think of insertion sort as a recursive algorithm (recInsertionSort). In order to sort A[0:n-1]: - recursively sort the subarray A[0:n-2] and then - insert A[n-1] into the sorted subarray A[0:n-2].

Exercise 1 (5 Points) Write a Python code for this recursive version (recInsertionSort) of insertion sort.

Exercise 2 (3 Points) Give a recurrence equation for its worst-case running time T(n).

Exercise 3 (2 Points) Compare and contrast T(n) with the best and worst-case running times of incremental insertionSort.

Divide-and-Conquer

Exercise 4 (3 points) Let A[0:n-1] be an array of n numbers. If i<j and A[i]>A[j], then the pair (i,j) is called an inversion of A.

Design an \mathcal O(n\lg{n}) algorithm that determines the number of inversions in any permutation of n elements. Provide a Python implementation.

Hint: Modify MERGE-SORT.

Exercise 5 (2 points) Analyze the time complexity of your algorithm in Exercise 4.

Exercise 6 (3 points) Design an \mathcal{O}(n\lg{n}) algorithm that, given a set S of n integers and another integer x, determines whether S contains two elements that sum to exactly x. Provide a Python implementation.

Exercise 7 (2 points) Analyze the time complexity of your algorithm in Exercise 6.

Time-complexity of Recursive Algorithms

Exercise 8 (1 point) Use the Master Theorem to get an upper bound (in big-\mathcal O notation) for the following recursion: T(n)=T(n/2) + n^3.

Exercise 9 (1 point) Use the Master Theorem to get an upper bound (in big-\mathcal O notation) for the following recursion: T(n)=4T(n/2) + n.

Exercise 10 (3 points) Given the recurrence relation T(n)=2T(n/2)+\mathcal O(n), what is the time complexity of the corresponding recursive algorithm?

Exercise 11 (🏅 Bonus) How does recursion impact space complexity, and what factors should be considered when analyzing it?