|
|
| Line 1: |
Line 1: |
| − | =Algorithm Analysis=
| |
| | | | |
| − | ===Program Analysis===
| + | For a known set of integer numbers ( assume Nr-1, Nr-2 ... Nr-k) the best is to use a non-comparison based sort algorithm like radix sort with O(n) |
| | | | |
| − | :[[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.
| + | You have an array that creates a histogram of all numbers ( histoThenStartIndexArray[Nr-i]++) |
| − | 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]]
| + | Step 2, in the same array calculate the index of that position |
| | + | For example if there are 3 numbers 99, and 5 numbers 105, the next index will be 8 for the next number |
| | | | |
| | + | Step 3, parse array and display values |
| | | | |
| − | :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)
| |
| | | | |
| − | | + | Back to [[Chapter 4]] |
| − | :[[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(<math>r</math>)
| |
| − | | |
| − | | |
| − | :[[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>
| |
| − | end
| |
| − | #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
| |
| − | | |
| − | :2.9
| |
| − | | |
| − | :2.10
| |
| − | | |
| − | :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]] | |
For a known set of integer numbers ( assume Nr-1, Nr-2 ... Nr-k) the best is to use a non-comparison based sort algorithm like radix sort with O(n)
You have an array that creates a histogram of all numbers ( histoThenStartIndexArray[Nr-i]++)
Step 2, in the same array calculate the index of that position
For example if there are 3 numbers 99, and 5 numbers 105, the next index will be 8 for the next number
Step 3, parse array and display values
Back to Chapter 4
