2. (25 points) Consider a sequence of n integers such that the difference between the consecutive...

Transcribed Image Text:

2. (25 points) Consider a sequence of n integers such that the difference between the consecutive terms is some constant d. Suppose that you are given only n-1 of these numbers and one of them is missing. Design an algorithm that finds the missing term in O(logn) time. You may assume that the first and last integers of the original sequence are still there to avoid ambiguity. Hint: When you see O(log n) time you should first try binary-search style algorithms, which are a special kind of divide and conquer algorithms. 3. (25 points) In this question, we consider the expected running time of the QuickSort algorithm when the pivot is chosen randomly. (If you do not know what QuickSort is, part of your job is to look it up from the internet and self-learn the algorithm.) (a) (20 points) Show that it runs in O(n) time on average for some constant e < 2. Hint: Try to mimic our analysis for the randomized selection algorithm in the slides. You need to choose the range of "reasonably" good pivot wisely here. (b) (5 points) Show that it runs in O(nlogn) time on average. 4. (25 points) Let there be an array A[1,2,...,n] of numbers and we wish to find the longest increasing consecutive sub sequence. Specifically we wish to find indices i, j such that ij and A[i] 2. (25 points) Consider a sequence of n integers such that the difference between the consecutive terms is some constant d. Suppose that you are given only n-1 of these numbers and one of them is missing. Design an algorithm that finds the missing term in O(logn) time. You may assume that the first and last integers of the original sequence are still there to avoid ambiguity. Hint: When you see O(log n) time you should first try binary-search style algorithms, which are a special kind of divide and conquer algorithms. 3. (25 points) In this question, we consider the expected running time of the QuickSort algorithm when the pivot is chosen randomly. (If you do not know what QuickSort is, part of your job is to look it up from the internet and self-learn the algorithm.) (a) (20 points) Show that it runs in O(n) time on average for some constant e < 2. Hint: Try to mimic our analysis for the randomized selection algorithm in the slides. You need to choose the range of "reasonably" good pivot wisely here. (b) (5 points) Show that it runs in O(nlogn) time on average. 4. (25 points) Let there be an array A[1,2,...,n] of numbers and we wish to find the longest increasing consecutive sub sequence. Specifically we wish to find indices i, j such that ij and A[i]