main page — COMP 526 Efficient Algorithms
Unit 1: Machines & Models
This is an archived version of this module from Spring 2022.
Click here for the current iteration.
This unit covers
- algorithm analysis
- the random-access-machine model
- asymptotic approximations, Big-Oh notation
Learning outcomes
- Understand the difference between empirical running time and algorithm analysis.
- Understand worst/best/average case models for input data.
- Know the RAM machine model.
- Know the definitions of asymptotic notation (Big-Oh classes and relatives).
- Understand the reasons to make asymptotic approximations.
- Be able to analyze simple algorithms.
Material
- slides
- Video 1-1 (2022-02-07):
§1.1 Algorithm analysis
- Video 1-2 (2022-02-07):
§1.2 The RAM model
- Video 1-3 (2022-02-07):
§1.3 Asymptotics
Further reading and sources
The RAM model is explained in more detail here: