In class we covered the following algorithms: addition, Euclid's algorithm (31.2), Linear Search, Binary Search, Insertion Sort (2.1) and Mergesort (2.3). We also talked about the Big-Oh notation (1.2, only very superficially: 3.2), pseudocode (in 2.1) and some basic mathematics (3.2). Next time we will talk more about sorting and general divide & conquer algorithms, how they work and how to analyze them.
I've decided not to include the coin-weighing problem on the homework, but check out the 12-coin problem to do the problem (think about it before you look at the solution).
I've included two rather challenging and one extremely difficult extra credit problem below. Enjoy.
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
1. [Growth Rates, 20pt] One way to understand growth rates is in reverse. For the running times f(n) = log n, f(n) = √n, f(n) = n, f(n) = n2 and f(n) = 2n, compute what the largest instance of the problem is you can solve in a) 1 second, b) 1 hour, c) 1 day, d) 1 year, assuming the computer takes f(n) milliseconds to solve a problem of size n.
|1 second||1 hour||1 day||1 year|
2. [Running times, 9pt] What are the running times of the following functions, using our classification of constant, O(1), linear, O(n), quadratic, O( n2), and simply exponential, O(2n).
a) f(n) = 2n + 3n2,
b) f(n) = n - 20.
c) f(n) = 100 * 2n + 7n2
3. [Binary Search] You are given an ordered array A[1..n] of numbers and a number x. Your goal is to determine whether x occurs in the array, that is, whether there is i such that A[i]=x. You can only access the array by making queries of the form "A[j] <= x?" and "A[j] = x?". Recall that binary search will take log n + O(1) queries. This exercise is about dealing with wrong answers to queries.
a) [20pt] Suppose you know that there will be at most one incorrect answer to your queries. Show that you can still determine whether x occurs in the array making at most 2 log n + O(1) queries. Write pseudocode for this problem.
b) [10pt] Suppose you know that the number of incorrect answers is bounded by k. Show that you can determine whether x occurs in the array making at most (k+1) log n + O(1) queries.
c) [Extra Credit Challenge] For the case of at most one wrong answer can you do better than 2 log n + O(1)?
4. [Splitting a number, 25pt] Find an algorithm that, given an n-element array A and a number x determines whether there are two elements y = A[i] and z = A]j] in the array such that x = y + z. Your algorithm should run in time O(n log n). You don't need to give a formal proof that it does run in that time, but you should argue why it does. You can write pseudocode, or give a high-level description (as long as it is convincing and correct). Hint: what does the running time of O(n log n) suggest?
5. [Inversion Sort] Do Exercise 2-4, a,b,c of the book (page 39/40), part d is extra credit: Given an array A[1..n], an inversion is a pair i<j such that A[i] > A[j] (that is A[i] and A[j] are in the wrong order).
a) [5pt] How many inversions does [2,3,8,6,1] have?
b) [5pt] Which permutation of [1,2,3,...,n] has the most inversions? And how many?
c) [15pt] What is the relationship between the running time of insertion sort and the number of inversions of the array? (Hint: think about a single inversion first; then consider what a single swap does to the number of inversions.)
d) [Extra Credit Challenge] Find an algorithm that computes the number of inversions in time O(n log n).
6. [Extra credit, coin weighing, very hard] You are given n coins some of which are counterfeit, that is lighter than the others. You have a scale on which you can compare any two sets of coins by weight. Determine how many of the coins are counterfeit in at most O(log2 n) weighings. Hint: this is really hard (it took me a couple of days to solve when I was a graduate student).