main page — CS 566 Efficient Algorithms
Unit 2: Machines & Models
This is an archived version of this module from Winter 2024-25.
This unit covers
- algorithm analysis
- the random-access-machine model
- asymptotic approximations, Big-Oh notation
- maximum sum subarray problem
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 2-0 (2024-10-21, 8:08):
§2.0 Introduction
- Video 2-1 (2024-10-21, 6:06):
§2.1 Algorithm analysis
- Video 2-2 (2024-10-21, 26:39):
§2.2 The word-RAM model
- Video 2-3 (2024-10-21, 30:26):
§2.3 Asymptotics and Big-Oh
- Video 2-4 (2024-10-22, 11:52):
§2.3 Asymptotics and Big-Oh: Asymptotics with several variables
- Video 2-5 (2024-10-22, 34:35):
§2.4 Teaser: Maximum subarray problem: brute force
- Video 2-6 (2024-10-22, 28:14):
§2.4 Teaser: Maximum subarray problem: efficient solutions
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