Lecture 1

Question 1

Name the most important problem types

Answer 1

Sorting, searching, string processing, graph, geometric, combinatorial and numerical problems

Question 2

What is a loop variant?

Answer 2

a logical predicate such that if it is satisfied before entering any single iteration of the loop then it is also satisfied after the iteration

Question 3

What are the three components of a loop variant

Answer 3

Initialization: It is true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.