Traditionally programming is considered as something practically important but very boring, something like looking for errors in long unreadable non-working programs. However, it is quite possible to learn how to write short and elegant programs when they exist; the key idea is that you try to construct a program together with the proof of its correctness. We will try to show you this technique using many examples (from Dijkstra, Gries, and other books). At the same time we will learn some techniques for constructing effective (fast) algorithms.

Curriculum:

1. Basic constructions. Variables, assignments, loops, invariant relations.
2. Arrays. General scheme of one-pass algorithms.
3. Generation of combinatorial objects. Tree traversal, backtracking.
4. Finite automata.
5. Sorting and related problems.
6. Data structures: stacks, queues, etc.
7. Sets and their representations. Hashing, trees, balanced trees.
8. Algorithms on graphs.
9. Recursion: how to use it and how to replace it by iteration.
10. Context-free grammars, recursive parsing.
11. LL(1), LR(1) parsers.

Textbooks

• A. Shen, Algorithms and programming: theorems and problems, Birkhauser, 1997.