Review List for Midterm Contents and Requirements Midterm 1 09 30 2013 CLOSED BOOK What to bring ASU ID Calculator What NOT to bring Cell phone should be turned off during exam Laptop Notes Books Analysis of Algorithms What is an algorithm Computation model Time complexity space complexity Worse average best case analysis Concentrate on concept definition example operations count Asymptotic Notations O notations derivation and proof definitions properties proofs lectures Summations derivation and proof geometric sequence arithmetic sequence harmonic sequence and others used in class Asymptotic Notations continued Recurrences master method three cases Sorting Algorithms Insertion sort Quicksort Algorithms and complexities Sorting Lower Bound Computing model Decision trees Lower bound You need to know the results and be able to draw the decision trees for 3 or 4 elements or a root to leaf path for up to 7 elements Divide and Conquer Technique Divide Conquer Combine Examples Quicksort Searching a sorted array Block matrix multiplication Summations 1 2 3 n n n 1 2 1 1 2 1 3 1 4 1 n log en ln n 1 1 2 1 4 1 8 1 2 n Sum 0 n 1xi 1 xn 1 x 1 1 2 1 4 1 8 1 2 n 1 1 2 n 1 2 n infinity 2 12 22 32 n2 n n 1 2n 1 6 Growth of functions log n sqrt n n n log n n2 n3 2n n nn Big O If f n n2 g n n3 f n O g n g n f n If f n g n f n O g n f n g n Master Method Recurrence must be of the form T n aT n b f n Where a 1 and b 1 and f n is an asymptotically positive function Three Cases Master Method Case 1 T n 9T n 3 n a 9 b 3 log b a log 3 9 2 f n O n logba e for 0 e 1 T n n logba n2 Master Method Case 2 T n T 2n 3 1 a 1 b 3 2 logba log3 21 0 f n n logba T n n logba lg n lg n Master Method Case 3 T n 3T n 4 n lg n a 3 b 4 log b a log 4 3 0 793 f n n log b a e for 0 e 1 log43 0 217 Is af n b cf n for c 1 3 n 4 lg n 4 c n lg n c 3 4 will work T n f n n lg n Insertion Sort Insertion Sort A 1 for j 2 to length A do 2 key A j 3 insert A j into sorted A 1 j 1 4 i j 1 5 while i 0 and A i key do 6 A i 1 A i 7 i i 1 8 A i 1 key Insertion Sort Example Initial array 7 2 5 3 6 Key 2 2 7 5 3 6 Key 5 2 5 7 3 6 Key 3 2 3 5 7 6 Key 6 2 3 5 6 7 Insertion Sort Decision Tree 7 2 5 3 6 2 7 5 3 6 2 5 7 3 6 2 5 7 3 6 2 5 3 7 6 2 3 5 7 6 2 3 5 7 6 2 3 5 6 7 key 2 key 5 key 5 key 3 key 3 key 3 key 6 key 6 Quick sort Quicksort A p r if p r then k Partition A p r Quicksort A p k 1 Quicksort A k 1 r Quick Sort Partition Partition A p r 1 x A r 2 i p 1 3 for j p to r 1 do 4 If A j x then 5 i i 1 6 exchange A i and A j 7 exchange A i 1 and A r 8 return i 1 Quick Sort Example Initial array 7 2 5 3 6 Quicksort A 1 5 7 2 5 3 6 x 6 7 2 5 3 6 2 7 5 3 6 2 5 7 3 6 2 5 3 7 6 2 5 3 6 7 Quicksort A 1 3 2 5 3 x 3 2 5 3 2 5 3 2 3 5 Quicksort A 1 1 2 Quicksort A 3 3 5 Quicksort A 5 5 7 Quick Sort Decision Tree 7 2 5 3 6 7 2 5 3 6 2 7 5 3 6 2 5 7 3 6 2 5 3 7 6 2 5 3 6 7 2 5 3 6 7 2 5 3 6 7 2 5 3 6 7 2 3 5 6 7 x 6 i 0 x 6 i 0 x 6 i 1 x 6 i 2 x 6 i 3 x 3 i 0 x 3 i 1 Running time Best Case Average Case Worst Case Insertion Sort O n O n2 O n2 Quick Sort O n log n O n log n O n2 Merge Sort O n log n O n log n O n log n
View Full Document
Unlocking...