CMPSC 40 Chapter Notes - Chapter 3.1-3.3: Insertion Sort, Linear Search, Halting Problem
Document Summary
Algorithm = a finite sequence of precise instructions for performing a computation or for solving a problem. Pseudocode provides an intermediate step between an english language description of an algorithm and an implementation of this algorithm in a programming language. For each input, the algorithm produces an output. The steps of an algorithm must be defined precisely. The algorithm should produce the correct output values for each set of input values. The algorithm should produce the output after a finite number of steps for any input. The algorithm must perform each step in a finite amount of time. The procedure should be applicable for all problems of the desired form. Searching problems = problems involving locating an element in an ordered list. Compares successively with each term of the list until a match is found. Compares the element to be located to the middle term of the list. List is split into two smaller sublists of approximately the same size.
