MTH 150 Chapter Notes - Chapter 3.1-3.3: Binary Search Algorithm, Insertion Sort, Bubble Sort

• School: University of Rochester
• Department: Mathematics
• Course: MTH 150
• Professor: Zeng

Document Summary

Algorithm - finite sequence of precise instructions for performing a computation for solving a problem. Ex. find max value of a set of numbers - set max temporarily to first int of sequence, compare next value, if it is larger, set that as the new max. Pseudocode - intermediate step between human language and programming language. For i :=2 to n, if max< ai, the max := ai. Has input values from a specified set and produces output values from a specified set. Definiteness - steps of algorithm must be defined precisely. Correctness - should produce correct output values for each set of input values. Finiteness - should produce desired output after a finite number of steps. Effectiveness - must be possible to perform each step of algorithm exactly and in a finite amount of time. Generality - should be applicable for all problems of desired form. Linear search/sequential search - compare x to a, if x = ai,