数据结构DataStructurech1_intro.pptxVIP

1 Chapter 1Introduction Readings: Sections 1.1, 1.2, 1.3 2 Outline Why program execution time for large inputs matters? Statement proving techniques Review of recursion You should review Section 1.2 on mathematics 3 Selection Problem Find the kth largest number from a group of N numbers How would you solve this? Algorithm 1: Sort the N numbers and pick the kth one. Easy to implement, but Sorting requires many comparisons Much work comparing elements having no chance to be at position K To sort N elements, need N log2(N) comparisons/swaps in general Unsorted data set with 10,000,000 elements and 1,000 swaps/sec will result in 2.8 hours to finish task 4 Selection Problem (Cont’d) Algorithm 2: (Better) Sort first K elements in the array. Then insert elements (K+1) to N, discarding the smallest element each time. Then pick the kth element. What if N=10 million and K=5,000,000 ? How long do you think this would take? Both algorithms are impractical. A better algorithm can solve this in a second! 5 Word Puzzle Find the words in the puzzle, given a 2-D array and a word-list. Algorithm 1: For each word in the word list, compare each combination of letters in the puzzle Algorithm 2: For each combination of letters Check if the word is in the word list What if the word-list is the entire dictionary? 6 Proving techniques Two common proof techniques in data structure and algorithm analysis Proof by induction Proof by contradiction Another common technique Proof by counterexample These are also actually common in general CS 7 Proof by Induction Given a theorem First prove a base case Show the theorem is true for some small degenerate values Next assume an inductive hypothesis Assume the theorem is true for all cases up to some limit k Then prove that the theorem holds for the next value (k+1) 8 Proof by Induction - example Fibonacci Series F0 = 1, F1 = 1, Fi = F(i-1) + F(i-2), for i1 Show that Fi (5/3)i,for i0 Base case: F1 = 1 5/3 F2 = 2 (5/3)2=25/9 Inductive Hypothes