CMPT-103 Lecture Notes - Lecture 1: The Algorithm, Pseudocode
Document Summary
Algorithm example: finding someone named "john doe" in a phone book. If the phone book is 1000 pages, the algorithm can go page by page until it reaches john doe. So as long as the concept of "john doe" is in this phone book, it will be found. Page by page in this example is very time consuming. Skipping by 2s and 4s makes this algorithm faster. It makes the algorithm incorrect because it could skip the s section or page of the s section that includes. Algorithm could be modified to go back to a few pages in the s section, but the algorithm still must go through 500 or more pages to get to john doe. Algorithm in the phone book could split the book in half. Algorithm goes down from 1000 to 500 pages. It could split again and again until it is just left with the s section.