Algorithms and Data Structures
Problems and Solutions A problem is a description of the: assumptions on the inputs requirements on the outputs A solution is a description of an algorithm and associated data structures that solve that problem, independant of language. e.g., given a non-negative integer n , calculate output: . You could solve this: s ← 0 for i ← 1 to n do s ← s + i ; s ← n × ( n + 1)/2 if ∃ p . n = 2 p then s ← n /2 s ← s × ( n + 1) else s ← ( n + 1)/2 s ← x × n Are these correct? If we assume they are, how do we compare them to find the best one? Correctness You can be formal about correctness using predicates and set theory, but in ADS, we shall be semi-formal and informal. An invariant is a property of a data structure that is true at every stable point (e.g., immediately before and after the body of a loop (for...