Ch2: Getting Started Flashcards
Pseudocode for InsertionSort(A)
How do you prove pseudocode is correct? (in general)
Formulate a predicate that shows the algorithm is correct. The predicate must be related to the pseudocode and reflect the pseudocode’s inputs.
Predicate
The statement we wish to prove
Loop invariant
A condition that is true immediately before each iteration of a loop.
What 3 things must we show about a loop invariant in proving an algorithm?
Initialization, Maintenance, and Termination
Initialization (Loop invariant)
Loop Invariant is true prior to the first iteration of the loop
Maintenance (Loop Invariant)
If the Loop Invariant is true before an iteration of the loop, it remains true before the next iteration
Termination (Loop Invariant)
When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct
Input size of an algorithm
Usually the number of items in the input (sorting), or sometimes the number of bits needed to represent the input (integer multiplication)
Running time of an algorithm
The number of primitive operations or steps executed
Incremental design technique
Assuming a solution to the problem with a given input size exists (j-1), solve the problem for a slightly larger input (j). Thus you can start with an empty input and keep applying the solution until the problem is solved for the entire input of size n.
e.g. For insertion sort, we assume we have the sorted subarray A[1..j-1], and simply insert the single element A[j].
Recursive algorithms typically use this design approach
Divide-and-Conquer
3 steps of the divide-and-conquer design approach
Divide, Conquer, and Combine
Divide step
Divide the problem into a number of subproblems that are smaller instances of the same problem
Conquer step
Conquer the subproblems by solving them recursively. However if the subproblem sizes are small enough, just solve them in a straightforward manner.
