## Homework 1 (due 9/18) CSC 491

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

If you like mazes and puzzles, try out Sokoban (or, even better, Sourceforge's Sokoban, but this version needs installation).

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 log n √n n n2 2n

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

Marcus Schaefer
Last updated: September 11th, 2006.