Unit 2: Machines & Models

This unit covers

• algorithm analysis
• the random-access-machine model
• asymptotic approximations, Big-Oh notation
• maximum sum subarray problem

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 (preliminary)

---

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

For formulas to simplify sums, see:

• The Theoretical Computer Science Cheat Sheet by Steve Seiden for series and other formulas.
  Version with our Big-Oh definition
  Original version

The maximum subarray problem is discussed in

• Nebel, Wild: Entwurf und Analyse von Algorithmen (2018), Springer Vieweg
• Column 8: Algorithm design techniques from Jon Bentley’s Programming Pearls (2nd ed.) Addison-Wesley, 2000

---

Unit 1  ⋅  Syllabus  ⋅  Unit 3