|
|
| 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 12]] |
| − | 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]]
| |
| − | | |
| − | :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. #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.11|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]]
| |
| − | | |
| − | :2.12
| |
| − | | |
| − | :2.13
| |
| − | | |
| − | :2.14
| |
| − | | |
| − | :2.15
| |
| − | | |
| − | :2.16
| |
| − | | |
| − | :2.17
| |
| − | | |
| − | :2.18
| |
| − | | |
| − | :2.19
| |
| − | | |
| − | :2.20
| |
| − | | |
| − | :2.21
| |
| − | | |
| − | :2.22
| |
| − | | |
| − | :2.23
| |
| − | | |
| − | :2.24
| |
| − | | |
| − | :2.25
| |
| − | | |
| − | :2.26
| |
| − | | |
| − | :2.27
| |
| − | | |
| − | :2.28
| |
| − | | |
| − | :2.29
| |
| − | | |
| − | :2.30
| |
| − | | |
| − | :2.31
| |
| − | | |
| − | :2.32
| |
| − | | |
| − | :2.33
| |
| − | | |
| − | :2.34
| |
| − | | |
| − | :2.35
| |
| − | | |
| − | :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]] | |
