Unit 1: Machines & Models

This is an archived version of this module from Spring 2020.
Click here for the current iteration.

This unit covers

• algorithm analysis
• the random-access-machine model
• asymptotic approximations, Big-Oh notation

Learning outcomes

1. Understand the difference between empirical running time and algorithm analysis.
2. Understand worst/best/average case models for input data.
3. Know the RAM model.
4. Know the definitions of asymptotic notation (Big-Oh classes and relatives).
5. Understand the reasons to make asymptotic approximations.
6. Be able to analyze simple algorithms.

Material

• lecture notes
• raw slides

• tutorial problems

• Lecture 2020-01-28 (stream)

• Lecture 2020-02-03 (stream)

• Lecture 2020-01-28 (youtube)

• Lecture 2020-02-03 (youtube)

Further reading and sources

The RAM model is explained in more detail here:

• Sanders, Mehlhorn, Dietzfelbinger, Dementiev: Sequential and Parallel Algorithms and Data Structures (2019), Springer