Chapter 2 Flashcards
How can we modify almost any algorithm to have a good best-case running time?
Modify the algorithm so it checks whether the input satisfies some _special case conditio_n. If it does, output a pre-computed answer.
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence
is T(n)=nlgn.
Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[i..j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(nlgn)?
Although we can reduce the number of comparisons by using binary search, we still need to shift all the elements greater than key towards the end of the array to insert key. And this shifting of elements runs at Θ(n) time, even in average case (as we need to shift half of the elements). So, the overall worst-case running time of insertion sort will still be Θ(n^2).
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
First sort with mergesort, then the two pointers are in the head and tail of the set, scan to the middle~ This topic can use the hash table (hash table) to achieve O (n)
Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n^2) worst- case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.
a. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk) worst-case time.
b. Show that the sublists can be merged in Θ(n lg (n/k) worst-case time.
c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what is the largest asymptotic (Θnotation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?
d. How should k be chosen in practice?
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ- notation.
Loop invariant: at the start of each iteration of the outer for loop, the subarray A[1..i-1] consists of the i-1 smallest elements in the array A[1..n] and this subarray is in sorted order.
Running time: Θ(n^2)
After the first n-1 elements, the subarray A[1..n-1] contains the smallest n-1 elements, sorted, and therefore element A[n] must be the largest element
We can express insertion sort as a recursive procedure as follows. In order to sort A[1 .. n], we recursively sort A[1 .. n-1] and then insert A[n] into the sorted array A[1 .. n-1]. Write a recursive pseudo code to implement the insertion sort. Write a recurrence for the worst-case running time of this recursive version of insertion sort and give the time complexity of the recursive algorithm.
Consider searching a target value within a sorted array. Since the array is sorted, we can check the midpoint of the array against the target value and eliminate half of the array from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the array each time. a. Write pseudocode, either iterative or recursive, for binary search. b. Argue that the worst-case running time of binary search is Θ(lg 𝑛).
Consider finding a peak element within a given array, in which all elements are unique. A Peak element is an element that is greater to its left and right neighbors. (If an element is at the border of the array, it only needs to be greater to its only neighbor to become a peak element.) For example, in {7, 8, 9, 5, 4, 3}, the peak element is 9 and in {1, 2, 4, 5, 6}, the peak element is 6. a. Find all the peak elements in {5, 4, 6, 8, 9, 2, 10} b. Give a worst-case Θ(lg 𝑛) algorithm that can find any peak element in an array of length n (hint: idea similar to binary search) (note: pseudo code is needed.)
