01:198:111 Lecture Notes - Lecture 2: Vending Machine, Infinite Loop
9 Oct 2018
School
Department
Course
Professor
01:198:111 verified notes
2/28View all
Document Summary
Sequential programs - algorithms are done in order one at a time. Parallel programs - algorithms are done in tandem with another program. Algorithm for finding a number in a sorted list, e. g. 10, 20, 25, 30, 35, 40, 45, 50, target. Takes the number and compares to each term sequentially until the number matches. Can write an if statement, where the program stops searching once the number on the list is >38. Worst case: target is the last term. Takes a middle term, e. g. 40, and compares 38 with it. Then it determines if 38 is below or above 40, and takes another middle term in the lower half and compares 38 to it. Rinse and repeat until target is found or is shown not to exist. Efficient, since even in a list with 10^6 terms, it only takes at most 20 searches to find the correct answer. Assume the machine takes only 25 cent coins.
