|
|
| Line 1: |
Line 1: |
| − | =Algorithm Analysis=
| |
| | | | |
| − | ===Program Analysis===
| |
| | | | |
| − | :[[2.1]]. What value is returned by the following function? Express your answer as a function of <math>n</math>. Give the worst-case running time using the Big Oh notation.
| + | Back to [[Chapter 5]] |
| − | mystery(''n'')
| |
| − | r:=0
| |
| − | ''for'' i:=1 ''to'' n-1 ''do''
| |
| − | ''for'' j:=i+1 ''to'' n ''do''
| |
| − | ''for'' k:=1 ''to'' j ''do''
| |
| − | r:=r+1
| |
| − | ''return''(r)
| |
| − | | |
| − | [[2.1|Solution]]
| |
| − | | |
| − | | |
| − | :2.2. What value is returned by the following function? Express your answer as a function of <math>n</math>. Give the worst-case running time using Big Oh notation.
| |
| − | pesky(n)
| |
| − | r:=0
| |
| − | ''for'' i:=1 ''to'' n ''do''
| |
| − | ''for'' j:=1 ''to'' i ''do''
| |
| − | ''for'' k:=j ''to'' i+j ''do''
| |
| − | r:=r+1
| |
| − | ''return''(r)
| |
| − | | |
| − | | |
| − | :[[2.3]]. What value is returned by the following function? Express your answer as a function of <math>n</math>. Give the worst-case running time using Big Oh notation.
| |
| − | prestiferous(n)
| |
| − | r:=0
| |
| − | ''for'' i:=1 ''to'' n ''do''
| |
| − | ''for'' j:=1 ''to'' i ''do''
| |
| − | ''for'' k:=j ''to'' i+j ''do''
| |
| − | ''for'' l:=1 ''to'' i+j-k ''do''
| |
| − | r:=r+1
| |
| − | ''return''(r)
| |
| − | | |
| − | [[2.3|Solution]]
| |
| − | | |
| − | | |
| − | :2.4. What value is returned by the following function? Express your answer as a function of <math>n</math>. Give the worst-case running time using Big Oh notation.
| |
| − | conundrum(<math>n</math>)
| |
| − | <math>r:=0</math>
| |
| − | ''for'' <math>i:=1</math> ''to'' <math>n</math> ''do''
| |
| − | ''for'' <math>j:=i+1</math> ''to'' <math>n</math> ''do''
| |
| − | ''for'' <math>k:=i+j-1</math> ''to'' <math>n</math> ''do''
| |
| − | <math>r:=r+1</math>
| |
| − | ''return''(r)
| |
| − | | |
| − | | |
| − | :[[2.5]]. Consider the following algorithm: (the print operation prints a single asterisk; the operation <math>x = 2x</math> doubles the value of the variable <math>x</math>).
| |
| − | ''for'' <math> k = 1</math> to <math>n</math>
| |
| − | <math>x = k</math>
| |
| − | ''while'' (<math>x < n</math>):
| |
| − | ''print'' '*'
| |
| − | <math>x = 2x</math>
| |
| − | :Let <math>f(n)</math> be the complexity of this algorithm (or equivalently the number of times * is printed). Proivde correct bounds for <math> O(f(n))</math>, and <math>/Theta(f(n))</math>, ideally converging on <math>\Theta(f(n))</math>.
| |
| − | | |
| − | [[2.5|Solution]]
| |
| − | | |
| − | | |
| − | :2.6. Suppose the following algorithm is used to evaluate the polynomial
| |
| − | ::::::<math> p(x)=a_n x^n +a_{n-1} x^{n-1}+ \ldots + a_1 x +a_0</math>
| |
| − | <math>p:=a_0;</math>
| |
| − | <math>xpower:=1;</math>
| |
| − | for <math>i:=1</math> to <math>n</math> do
| |
| − | <math>xpower:=x*xpower;</math>
| |
| − | <math>p:=p+a_i * xpower</math>
| |
| − | #How many multiplications are done in the worst-case? How many additions?
| |
| − | #How many multiplications are done on the average?
| |
| − | #Can you improve this algorithm?
| |
| − | | |
| − | | |
| − | :2.7. Prove that the following algorithm for computing the maximum value in an array <math>A[1..n]</math> is correct.
| |
| − | max(A)
| |
| − | <math>m:=A[1]</math>
| |
| − | ''for'' <math>i:=2</math> ''to'' n ''do''
| |
| − | ''if'' <math>A[i] > m</math> ''then'' <math>m:=A[i]</math>
| |
| − | ''return'' (m)
| |
| − | | |
| − | [[2.7|Solution]]
| |
| − | | |
| − | ===Big Oh===
| |
| − | | |
| − | | |
| − | :2.8. True or False?
| |
| − | #Is <math>2^{n+1} = O (2^n)</math>?
| |
| − | #Is <math>2^{2n} = O(2^n)</math>?
| |
| − | | |
| − | | |
| − | :[[2.9]]. For each of the following pairs of functions, either <math>f(n )</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why.
| |
| − | #<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>
| |
| − | #<math>f(n)=\sqrt n</math>; <math>g(n)=\log n^2</math>
| |
| − | #<math>f(n)=\log^2 n</math>; <math>g(n)=\log n</math>
| |
| − | #<math>f(n)=n</math>; <math>g(n)=\log^2 n</math>
| |
| − | #<math>f(n)=n \log n + n</math>; <math>g(n)=\log n</math>
| |
| − | #<math>f(n)=10</math>; <math>g(n)=\log 10</math>
| |
| − | #<math>f(n)=2^n</math>; <math>g(n)=10 n^2</math>
| |
| − | #<math>f(n)=2^n</math>; <math>g(n)=3^n</math>
| |
| − | | |
| − | [[2.9|Solution]]
| |
| − | | |
| − | | |
| − | :2.10. For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.
| |
| − | #<math>f(n) = (n^2 - n)/2</math>, <math>g(n) =6n</math>
| |
| − | #<math>f(n) = n +2 \sqrt n</math>, <math>g(n) = n^2</math>
| |
| − | #<math>f(n) = n \log n</math>, <math>g(n) = n \sqrt n /2</math>
| |
| − | #<math>f(n) = n + \log n</math>, <math>g(n) = \sqrt n</math>
| |
| − | #<math>f(n) = 2(\log n)^2</math>, <math>g(n) = \log n + 1</math>
| |
| − | #<math>f(n) = 4n\log n + n</math>, <math>g(n) = (n^2 - n)/2</math>
| |
| − | | |
| − | | |
| − | :[[2.11]]. For each of the following functions, which of the following asymptotic bounds hold for <math>f(n) = O(g(n)),\Theta(g(n)),\Omega(g(n))</math>?
| |
| − | | |
| − | [[2.11|Solution]]
| |
| − | | |
| − | | |
| − | :2.12. Prove that <math>n^3 - 3n^2-n+1 = \Theta(n^3)</math>.
| |
| − | | |
| − | | |
| − | :2.13. Prove that <math>n^2 = O(2^n)</math>.
| |
| − | | |
| − | [[2.13|Solution]]
| |
| − | | |
| − | | |
| − | :2.14. Prove or disprove: <math>\Theta(n^2) = \Theta(n^2+1)<\math>.
| |
| − | | |
| − | | |
| − | :[[2.15]]
| |
| − | [[2.15|Solution]]
| |
| − | | |
| − | | |
| − | :2.16
| |
| − | | |
| − | | |
| − | :[[2.17]]
| |
| − | | |
| − | [[2.17|Solution]]
| |
| − | | |
| − | | |
| − | :2.18
| |
| − | | |
| − | | |
| − | :[[2.19]]
| |
| − | | |
| − | [[2.19|Solution]]
| |
| − | | |
| − | | |
| − | :2.20
| |
| − | | |
| − | | |
| − | :[[2.21]]
| |
| − | | |
| − | [[2.21|Solution]]
| |
| − | | |
| − | | |
| − | :2.22
| |
| − | | |
| − | | |
| − | :[[2.23]]
| |
| − | | |
| − | [[2.23|Solution]]
| |
| − | | |
| − | | |
| − | :2.24
| |
| − | | |
| − | | |
| − | :[[2.25]]
| |
| − | | |
| − | [[2.25|Solution]]
| |
| − | | |
| − | | |
| − | :2.26
| |
| − | | |
| − | | |
| − | :[[2.27]]
| |
| − | | |
| − | [[2.27|Solution]]
| |
| − | | |
| − | | |
| − | :2.28
| |
| − | | |
| − | | |
| − | :[[2.29]]
| |
| − | | |
| − | [[2.29|Solution]]
| |
| − | | |
| − | | |
| − | :2.30
| |
| − | | |
| − | | |
| − | :[[2.31]]
| |
| − | | |
| − | [[2.31|Solution]]
| |
| − | | |
| − | | |
| − | :2.32
| |
| − | | |
| − | | |
| − | :[[2.33]]
| |
| − | | |
| − | [[2.33|Solution]]
| |
| − | | |
| − | | |
| − | :2.34
| |
| − | | |
| − | | |
| − | :[[2.35]]
| |
| − | | |
| − | [[2.35|Solution]]
| |
| − | | |
| − | | |
| − | :2.36
| |
| − | | |
| − | ===Summations===
| |
| − | | |
| − | | |
| − | :2.37
| |
| − | | |
| − | :2.38
| |
| − | | |
| − | :2.39
| |
| − | | |
| − | :2.40
| |
| − | | |
| − | :2.41
| |
| − | | |
| − | :2.42
| |
| − | | |
| − | :2.43
| |
| − | | |
| − | ===Logartihms===
| |
| − | | |
| − | | |
| − | :2.44
| |
| − | | |
| − | :2.45
| |
| − | | |
| − | :2.46
| |
| − | | |
| − | :2.47
| |
| − | | |
| − | ===Interview Problems===
| |
| − | | |
| − | | |
| − | :2.48
| |
| − | | |
| − | :2.49
| |
| − | | |
| − | :2.50
| |
| − | | |
| − | :2.51
| |
| − | | |
| − | :2.52
| |
| − | | |
| − | :2.53
| |
| − | | |
| − | :2.54
| |
| − | | |
| − | :2.55
| |
| − | | |
| − | | |
| − | Back to [[Chapter List]] | |
