u2 Flashcards Preview

m269 > u2 > Flashcards

Flashcards in u2 Deck (5)
Loading flashcards...
1

precondition

a proposition concerning the inputs of an algorithm, such that if every precondition holds, then the algorithm will terminate with the correct output.

2

postcondition

a proposition relating the outputs to the inputsof an algorithm, such that if every precondition holds, then when the algorithm terminates, each postcondition holds

3

Inertial convention

Aspects of an ADT’s state not referred to in the postcondition for an operation are unaffected by the operation

4

invariant

a proposition concerning ADTs state that is always TRUE

5

Binary search

•Set the partition to be the input sequence.
•Find the index of the midpoint of the partition. If the target is at the midpoint then the item is found. Otherwise divide the partition into two halves, Left and Right, at the midpoint. If the targetis less than the item at the midpoint then make Left the new partition. Otherwise make Right the new partition. Repeat the process with the new partition.
O(log n)