Google University - Problem Set Algorithm Analysis

Problem Set* This problem set will give you practice with big­oh analyses from a mathematical and an algorithmic point  of view.  At times, we will ask for exact instruction counts and other times, just a big­oh approximation.  Both are important skills for computer scientists.  You will also work on some recurrence relations, and the  analysis of recursive algorithms.  It is likely you will find the recurrence relations and recursion problems  the most challenging, so be sure to allow enough time. On this problem set, if we ask for a proof be precise and always reference proofs of theorems from other  sources (handouts, problem sets, etc.), but it’s okay to start leaving out some of the more obvious steps.  We’ll let you know if you go too far.  If we ask for an inductive proof, include the six steps.  On all  questions, always show your work so partial credit can be given. Big­Oh 1) We say that n0 and c are witnesses to the fact that f(n) is O(g(n)) if for all n >= n0, it is true that  f(n) <= c * g(n). If n0 = 1, what is the smallest value of c such that n0 and c are witnesses to the fact that (n + 2)2 is  O(n2)?  (3 pts) b) If c = 5, what is the smallest non­negative integer n0 such that n0 and c are witnesses to the fact  that (n + 2)2 is O(n2)? (3 pts) c) If n0 = 0, for what values of c are n0 and c witnesses to the fact that (n + 2)2 is O(n2)? (3 pts) a)

2) Prove or disprove: an is O(bn) if 1 < a <= b. (6 pts) 3) Prove or disprove: If f1(n) and f2(n) are both tight bounds on some function T(n), then f1(n) and f2(n)  are each big­oh of the other. Here is the definition of "tightness": f(n) is a tight big­oh bound on T(n) if:  1) T(n) is O(f(n)) 2) If T(n) is O(g(n)) then it is also true that f(n) is O(g(n)). Informally, this means that we cannot find a function g(n) that grows at least as fast as T(n) but grows  slower than f(n).  For example, T(n) = 2n2 + 3n and f(n) = n3.  This does not represent a tight bound since we could pick g(n) = n2.  T(n) is O(g(n)), but f(n) is not O(g(n)).  (6 pts)

Algorithm Analysis 4) Write the most efficient algorithm you can think of (in C, Java, pseudo-code) for the following: Given an array of n integers, find the smallest. What is the running time in terms of big-oh, big-theta, big-omega? Explain your answer. (6 pts)

5) Write the most efficient algorithm you can think of for the following: Given a set of p points, find the pair closest to each other. What is the running time in terms of big-theta? Explain your answer. (9 pts)

6) Write the most efficient algorithm you can think of for the following: Find the k-th item in an n-node doubly-linked list. What is the running time in terms of big-theta? Explain your answer. (12 pts)

Recurrence Relations 7) Solve the following recurrence relation using repeated substitution.  Do an inductive proof to show your  formula is correct (10 pts): T(1) = 0 T(n) = 1/2 T(n­1) + 1 for integers n > 1 8) A string that contains only 0's, 1's and 2's is called a ternary string.  Define a recurrence relation for the  number of ternary strings that contain two consecutive symbols that are the same.  For example, for n = 3,  here are the strings: 001, 000, 100, 002, 200, 110, 011, 111, 112, 211, 220, 022, 122, 221, 222. (15 pts)  9) Solve the following recurrence relation using any technique that works for you.  Then, prove your  solution is correct using induction. (15 pts) a0 = 1; a1 = 0 an = an­2 / 4  for n >= 2

10) Find the big-Oh running time of the following recurrences. Assume that T(1)=1. Use the Master Theorem. (4 points each) a) T (n) = 2 T ( n/2 ) + n3 b) T (n) = 9 T (n/3) + n c) T (n) = 25 T (n/5) + n2 The Format for Inductive Proofs 1) 2) 3) 4) 5)

state P(n) show that P(base case) is true state the inductive hypothesis (substitute k for n) state what must be proven (substitute k+1 for n) state that you are beginning your proof, and proceed to manipulate the inductive hypothesis (which  we assume is true) to find a link between the inductive hypothesis and the statement to be proven.  Always state explicitly where you are invoking the inductive hypothesis.  A proof that does not use  the inductive hypothesis is not induction!

6) Always finish your proof with something like: P(k+1) is true when P(k) is true, and therefore P(n)  is true for all natural numbers, or a simple QED will do.  We just want to know when you feel you  are done. NOTE: On problem sets and exams, it is important to present your proof in the proper form.  You  must always write out steps 1­6 as given above.  Form is important in inductive proofs. An Example:  P(n) denotes 1 + 3 + 5 + ... + (2n­1) = n2, i.e., the sum of the first n odd integers is n2 i) base case: prove that P(1) is true  1 = 12 = 1; the sum of the first 1 odd integers = 1  (include     both parts) ii)  induction hypothesis is to assume P(k):  1 + 3 + 5 + ... + (2k­1) = k2 and show: P(k+1):  1 + 3 + 5 + ... + (2k­1) + (2k+1) = (k+1)2 PROOF:  Simulate adding another term to both sides of the induction hypothesis: 1 + 3 + 5 + ... + (2k­1) + (2k+1) 

= k2 + (2k+1) = k2 + 2k + 1 = (k+1)2

P(k+1) is true when P(k) is true, and therefore P(n) is true for all natural numbers.

* Except as otherwise noted, the content of this presentation is licensed under the Creative Commons Attribution 2.5 License.