Initial assessment: Answer the questions below
Jamaal Gray
Fundamentals of Algorithms Fall 2010 HW 3 DUE: September 20, 2010, 10 am
1. Order the following functions from fastest growing to slowest growing:
|3n^2 |Fastest Growing |1 |n^n |
|100 |. |2 |2^(n+1) |
|2^n |. |3 |2^n |
|4n |. |4 |(4/3)^n |
|2n^3 |. |5 |n+ n^2+5n^4 |
|(4/3)^n |. |6 |2n^3 |
|2^(n+1) |. |7 |n^3+ log n |
|6sqrt(n) |. |8 |3n^2 |
|log log log n |. |9 |5n log n |
| n^3+ log n |. |10 |4n |
|(log n)^10 |. |11 |6sqrt(n) |
|5n log n |. |12 |(log n)^10 |
|n+ n^2+5n^4 |. |13 |7log n |
|7log n |. |14 |log log log n |
|n^n |Slowest Growing |15 |100 |
2. Please show which function is faster growing between the following two functions:
a. n + log(n) and n*sqrt(n)
b. n^11 and n^10 + 3n + 4
c. log n + 1 and 2loglog(n)^2
d. (n^3-n)/2 and 6n^4
e. 3nlog(n) + n^3 and (n^2-n)/2
f. sqrt(n) and nlog(n)
g. n^2 + n log(n) and n*sqrt(n)/2
h. n and n^5 + 2sqrt(n)
*Highlight indicates faster growing...
3. Prove by induction that
F(1)^2 + F(2)^2 + F(3)^2 +…+F(n)^2 = F(n)F(n+1)
for all n>=1 and where F(n) is the nth Fibonacci number.
F(0) = 0
F(1) = 1
F(2) = F(1)+F0) = 1
Base Case : F(1)2 = F(1)F(1+1) = F(1)F(2) = 1(1) = 1 ✓
Inductive Step: n = k
Inductive Hypothesis: F(1)2 + F(2)2 + F(3)2 +…+ F(k)2 = F(k)F(k+1) for all k>=1
To Show: F(1)2 + F(2)2 + F(3)2 +…+ F(k)2 + F(k+1)2 = F(k+1)F(k+2) for all k>=1
Method: Taking the Left side of the To Show...
F(1)2 +…+ F(k)2 + F(k+1)2= F(k)F(k+1) + F(k+1)2
= F(k+1)[F(k) + F(k+1)] Factoring out F(k+1)
= F(k+1)F(k+2) Plugging in F(k+2) = [F(k) + F(k+1)]
4. Master Theorem: Find a closed from expression for T(n)
a) T(n) = 3T(n/2) T(1)=1
T(2) = 3T(2/2) = 3
T(4) = 3T(4/2) = 3 x 3 = 9
T(8) = 3T(8/2) = 3 x 9 = 27
T(2k) = 3k
3k = (2lg 3)k = (2k)lg3
n = 2k
T(n) = nlg 3
b) T(n) = 5 T(n/2) T(1)=1
T(2) = 5T(2/2) = 5
T(4) = 5T(4/2) = 5 x 5 = 25
T(8) = 5T(8/2) = 25 x 5 = 125
T(2k) = 5k
5k = (2lg 5)k = (2k)lg5
n = 2k
T(n) = nlg 5
c) T(n) = 6 T(n/2) T(1)=1
T(2) = 6T(2/2) = 6
T(4) = 6T(4/2) = 6 x 6 = 36
T(8) = 6T(8/2) = 6 x 36 = 216
T(2k) = 6k
6k = (2lg 6)k = (2k)lg6
n = 2k
T(n) = nlg 6
d) T(n) = 7 T(n/2) T(1)=1
T(2) = 7T(2/2) = 7
T(4) = 7T(4/2) = 7 x 7 = 49
T(8) = 7T(8/2) = 7 x 49 = 343
T(2k) = 7k
7k = (2lg7)k = (2k)lg7 = nlg7
T(n) = nlg 7
e) T(n) = 3k T(n/2) T(1)=1
T(1) = 1
T(2) = 3k T(2/2) = 3k
T(4) = 3k T(4/2) = 3k x 3k = 32k = 9k
T(8) = 3k T(8/2) = 3k x 32k = 33k = 27k
T(2p) = 3kp
5. What is the running time of the best and worst cases of the following sorting algorithms?
| |Heap Sort |Selection Sort |Bubble Sort |Merge Sort |
|Best Case |O(N log N) |O(n2) |O(n) |O(N log N) |
|Worst Case |O(N log N) |O(n2) |O(n2) |O(N log N) |
Explain for each one.
Heap Sort
An almost complete binary tree with n vertices has a depth of at most log(n). Therefore, procedure downheap requires at most log(n) steps. Procedure buildheap calls downheap for each vertex, therefore it requires at most n·log(n) steps. Heapsort calls buildheap once; then it calls downheap for each vertex, together it requires at most 2·n·log(n) steps.
Best Case (Sorted Already): Visits the same amount of nodes regardless... O(N log N)
Worst Case (Reversed): At most ... O(N log N)
Selection Sort
Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on. It’ll do the same amount of checks regardless
Best Case (Already Sorted): (n -1) + (n -2) +..+ 2 + 1 = n(n -1) / 2= (n2 - n)/2=(1/2)n2 - (1/2)n ∈ O(n2)
Worst Case (Reversed): (n -1) + (n -2) +..+ 2 + 1 = n(n -1) / 2= (n2 - n)/2=(1/2)n2 - (1/2)n ∈ O(n2)
Bubble Sort
Compares two elements in some array and swaps them if one happens to be less than the other.
The worst case equation is as follows for this particular sort:
5 + 4 +..+ n = n(n+1)/2 =(n2 + n)/2=(1/2)n2 + (1/2)n ∈ O(n2)
Best Case (Already Sorted): No element needs to be swapped if they are all in order. O(n).
Worst Case (Reversed): 5 + 4 +..+ n = n(n+1)/2 =(n2 + n)/2=(1/2)n2 + (1/2)n ∈ O(n2)
Merge Sort
The merge function requires at most 2n steps (n steps for copying the sequence to the intermediate array b, and at most n steps for copying it back to array a). The time complexity of mergesort is therefore
T(n) ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- answer wh questions worksheet
- answer my questions with questions
- answer wh questions iep goal
- how to answer interview questions about weaknesses
- how to answer weakness questions in interview
- reconstruction assessment answer key
- answer my questions for test
- 15 1 biology assessment answer key
- initial assessment form for counseling
- how to answer interview questions effectively
- answer poll questions online
- how to answer interview questions about pay