Computer Science 331 — Introduction to the Analysis of Algorithms
These initial lectures introduce techniques that can be used to prove the correctness of simple algorithms and bound their running times. Students will be required to use these techniques to solve problems on assignments and tests in this course.
Unfortunately there does not seem to a standard way to present some of this material. Descriptions of this from other places might describe things very differently and may use technial terms like “loop invariant” to mean different things. The lecture notes that are supplied here should, therefore, be used as the main reference for this material.
When techniques are introduced one of more examples are provided — but a general description of how to use the technique is generally also supplied. This general description should be consulted when you try to use these techniques yourself. It will often not be easy (or even possible) to modify one of the examples to solve a new problem, instead.
Implementations of the algorithms from lectures and tutorials are supplied as both Python and Java programs. Students are encouraged to compile the Java programs and execute both versions in order to verify claims about what happens when the algorithms from this course are implemented and used.