u2

Question 1

precondition

Answer 1

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

Question 2

postcondition

Answer 2

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

Question 3

Inertial convention

Answer 3

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

Question 4

invariant

Answer 4

a proposition concerning ADTs state that is always TRUE

Question 5

Binary search

Answer 5

•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)