Unit 1: Machines & Models

This is an archived version of this module from Fall 2022.
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 machine 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

• slides

• lecture notes

• Video 1-1 (2022-10-03, 15:59): §1.1 Algorithm analysis
  
  Chapters

  0:15 Learning Outcomes
  1:08 What is an algorithm?
  4:54 What is a data structure?
  7:05 Good algorithms
  12:21 Data Models
  
• Video 1-2 (2022-10-03, 12:52): §1.2 The RAM model
  
  Chapters

  3:42 Machine Models
  5:22 Random Access Machine
  
• Video 1-3 (2022-10-05, 46:44): §1.3 Asymptotics and Big-Oh
  
  Chapters

  0:47 Clicker Question
  3:20 Why asymptotics?
  8:25 Asymptotic tools - Formal & definitive definition
  11:44 Asymptotic tools - Intuition
  27:41 Asymptotics - Example 1
  34:43 Asymptotics - Frequently used facts
  37:23 Asymptotics - Example 2
  

---

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

---

Unit 0  ⋅  Syllabus  ⋅  Unit 2