Initial assessment: Answer the questions below



Fundamentals of Algorithms Fall 2009 HW 2 Solutions

Based on responses of Keesha Joseph and Rotimi Iziduh

1. Expand log (x/y) in terms of log x and log y

log(x/y) = log x + log y

2. What is the running time of multiplying two n-digit numbers using the standard algorithm? Is it possible to solve this problem with fewer multiplications?

The running time of multiplying two n-digit # is O(n^2).

There is a way to solve this problem with fewer multiplications. A guy by the name of Karatsuba came up with a system to multiply these numbers faster. The running time for this is O(n^(lg 2)) = O(n^1.59).

3. What is the worst case running time of sequential search? What about binary search? What conditions need to hold before we can run binary search?

The worst case running time of sequential search is n.

The worst case running time of binary search is log n

Before we run a binary search the elements being searched must be in order from lowest to highest.

4. What is the running time of the best and worst cases of the following sorting algorithms?

| |Insertion Sort |Selection Sort |Bubble Sort |Merge Sort |

|Best Case |O(n) |O(n^2) |O(n) |O(nlogn) |

|Worst Case |O(n^2) |O(n^2) |O(n^2) |O(nlogn) |

5. What is the worst case input for

a) Insertion Sort – Reversed List

b) Bubble Sort – Reversed list

c) Selection Sort – Doesn’t matter, all lists take the same number of steps.

d) Merge Sort – Reversed list.

e) Sequential Search – item is at end of list or not in list.

6. What is the Best case input for

a) Insertion Sort – Sorted list

b) Bubble Sort – Sorted list

c) Selection Sort - Doesn’t matter, all lists take the same number of steps.

d) Merge Sort – Sorted List.

e) Sequential Search – item is at beginning of list.

7. Consider the sequence [4 3 2 1]. Show how to sort this sequence using (a) Bubble Sort (b) Selection Sort (c) Insertion Sort (d) Merge Sort

a) Bubble Sort

4321

3214

2134

1234

b) Selection Sort

4321 - > 1 is moved to the new array. -> 1

432 - > 2 is moved into the new array. ->12

43 - > 3 is moved into the new array. -> 123

4 -> 4 is moved to the new array -> 1234

c) Insertion Sort

4321

3421

2341

1234

d) Merge Sort

4321

43 21

34 12

1234

8. Implement Sequential Search and Binary Search in your favorite programming language. Run some test inputs on both algorithms and compare the running times.

NOT SHOWN

9. Implement Selection Sort, Insertion Sort, Bubble Sort and Merge Sort in your favorite programming language. Compare running time on an in order array and a reversed array. What does this show about the best and worst case inputs for these algorithms?

NOT SHOWN

10. Please solve exercises 1.4.2 #1 and 1.4.2 #2 in the textbook.

a) The following functions are ordered from fastest growing to slowest growing:

n!, 2^n, 2^(n-1), (3/2)^n, n- n^2+5n^3, n^3+ log n, n^3, n^2, n log n, n, sqrt(n), (log n)^2, log n, log log n, 6

b) Please show which function is faster growing between the following two functions:

a.(n^2-n)/2 and 6n

(n^2-n)/2

b. n+2sqrt(n) and n^2

n^2

c. n+nlog(n) and n*sqrt(n)

n*sqrt(n)

d. n^2 + 3n + 4 and n^3

n^3

e. n log(n) and n*sqrt(n)/2

n*sqrt(n)/2

f. n + log(n) and sqrt(n)

n + log(n)

g. 2log(n)^2 and log n +1

2log(n)^2

h. 4nlog(n) + n and (n^2-n)/2

(n^2-n)/2

11. Order the following function from slowest growing to fastest growing: n^3, lg n, 2^n, n, n^2, n lg n

lg n, n, n lg n, n^2, n^3, 2^n

12. Use the product rule for derivates [(fg)' = f'g + fg'] to prove by mathematical induction that for every integer n >= 1, the derivative of [pic]is[pic].

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic] (product rule)

[pic](IH)

[pic]

[pic]

13. Suppose that m is a fixed integer and[pic]. Then for every integer n >= 1, [pic]. Prove this by mathematical induction.

[pic]

[pic]

[pic]

[pic]

[pic]

x^(k+1) mod m= y^(k+1) mod m

[pic]

[pic]

[pic]

x^(k+1) mod m= y^(k+1) mod m QED

14. Suppose that f(n)=n*f(n-1) with f(1)=1. Prove by induction that f(n)=n*(n-1)…3*2*1.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

15. Suppose that f(n)=f(n-1) + 2*n-1 with f(1)=1. Prove by induction that f(n)=n^2.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

LHS F(k+1)[pic]

[pic]

[pic]

16. Suppose that f(n)=2*f(n-1) with f(1)=1. Prove by induction that f(n)=2^n.

[pic]

[pic]

[pic]

[pic]

[pic]

F(k+1)[pic]

17. Suppose that f(n)=2*f(n/2) with f(1)=1. Prove by induction that f(2^k)=2^k.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

18. Suppose that f(n)=2*f(n/2) + n with f(2)=2. Prove by induction that f(2^k)=k*2^k.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

19. Suppose that f(n)=3*f(n-1) - 15 with f(1)=8. Prove by induction that f(n)= (3^(n-1) + 15) /2.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic] multiplying by 3 and subtracting 15 from both sides

3(f(k)-15 = 3((3^(k-1) + 15)/2)-15 =

F(k+1) = (3^k +45)/2 -15 = (3^k + 15)/2

20. Suppose that f(n)=f(n-1) + n-1 with f(1)=3. Prove by induction that f(n)= 3 + ((n-1)*n)/2.

Base Case: f(1) = 3

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

=f(k) + k

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]QED

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download