Sebastian

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

  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 2-0 (2024-10-21): §2.0 Introduction

  • Video 2-1 (2024-10-21): §2.1 Algorithm analysis

  • Video 2-2 (2024-10-21): §2.2 The word-RAM model

  • Video 2-3 (2024-10-21): §2.3 Asymptotics and Big-Oh

  • Video 2-4 (2024-10-22): §2.3 Asymptotics and Big-Oh: Asymptotics with several variables

  • Video 2-5 (2024-10-22): §2.4 Teaser: Maximum subarray problem: brute force

  • Video 2-6 (2024-10-22): §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 maximum subarray problem is discussed in

Unit 1  ⋅  Syllabus  ⋅  Unit 3