Skip to content

Introduction

  • Advanced Algorithms (CMPUT 501, Fall 2025) course website.
  • Instructor: Mohammad R. Salavatipour

Course Description

This is a new course that will cover topics in Advanced Algorithms in Theoretical Computer Science (TCS), targeted for senior undergraduate and graduate students interested in TCS. The tentative list of topics to be covered in this course are listed below. We cover some classic topics and more recent advances with applications in other areas: streaming and sketching algorithms for big data, online and randomized algorithms, and approximation algorithms.

Tentative topics (could change later):

  • Module 1: Classics (Greedy and Dynamic Programming) Stable matching, Interval scheduling, Weighted Interval Scheduling, Segmented least Squares, Advanced DP Minimum Spanning Trees and Arborescences

  • Module 2: Randomized Algorithms Simple deviation bounds, Randomized Min-Cut Chernoff bound, Hypercube routing, Randomized load balancing, Hashing Balls and bins, power of two choices, Random Walks in Graphs

  • Module 3: Linear Programming and Combinatorial Optimization Integer/Linear Programming, Duality, Integrality gap Matchings, matching polytope

  • Module 4: Approximation Algorithms Vertex/Set cover, LP rounding Knapsack, Bin Packing Max-Sat Max-Cut

  • Module 5: Streaming and Sketching Probabilistic Counting Frequency moments, Distinct elements estimation Sketching

  • Module 6: Online Algorithms, Learning from experts Online algorithms, Ski rental, paging Secretary problem, Learning from experts, Multiplicative Weight Update

By the end of this course you should have a basic knowledge of some of the basic techniques used in TCS in design and analysis of algorithms. You should also learn some tools and tricks to tackle problems that might arise in different settings (such as online setting, streaming setting, or interactable/hard to solve optimization problems).

Concepts

Greedy, Dynamic Programming

  • Lecture 1: Stable Matching, Interval Scheduling, Minimizing lateness, Weighted Interval Scheduling

    Also see sections 1.1, 4.1, 4.2, 6.1 (KT)

  • Lecture 2: Segmented Least Square, Sequence Alignments, BST

    Also see sections 6.3, 6.6, 6.6 in (KT), extra notes for Advanced algorithms by (JE), and this survey paper.

  • Lecture 3: Advanced DP: Saving time using monotonicity, SMWAK

    Extra notes for Advanced algorithms by (JE), and this survey paper.

Minimum Spanning Tree, Minimum Arborescence:

  • Lecture 4: Minimum Spanning Tree (MST), Fredman-Tarjan Algorithm

  • Lecture 5: MST in linear time, Minimum Arborescence

    Also 4.9 from (KT).

Randomized Algrithms:

  • Lecture 6: Introduction, simple deviation bounds, randomized min-cut

  • Lecture 7: Chernoff bound, Hypercube routing

    Also 4.1-4.2 from (MR)

  • Lecture 8: Balls and Bins, power of two choices

  • Lecture 9: Randomized load balancing, Hashing

    Also notes 5 from (JE), and these notes.

  • Lecture 10: Random Walks, resistence graph

    Also Chapter 6 from (MR)

  • Lecture 11: Finger printing, Polynomial identity testing

    Also Chapter 7 from (MR)

Integer/Linear Programming and Combinatorial Optimization:

  • Lecture 12: Integer/Linear Programming, Duality

  • Lecture 13: Bipartite Matching, Matching Polytope

  • Lecture 14: Weighted Biparite Matching

  • Lecture 15: Bipartite matching (vardinality and weighted) via priam dual methods

Approximation Algorithms

  • Lecture 16: Introduction, Set cover/Max coverage, Set cover rounding

    Also see 1.2, 1.6, 1.7 from (WS)

  • Lecture 17: Approximation Schemes: knapsack, Bin Packing

    Also see 3.1-3.3 from (WS)

  • Lecture 18: Max-SAT

    Also see 5.1-5.6 from (WS)

  • Lecture 19: Semidefinite Programming, Max-Cut

    Also see 6.1-6.2 from (WS)

  • Lecture 20: Approximating metrics by tree metrics

    Also see 8.5 from (WS)

Online Algorithms, Learning From Experts

  • Lecture 23: Online algorithms, Paging, Secretary problem

    Also see (MR) Chapter 13.

  • Lecture 24: Prophet inequality

    Also see these notes by Gupta, these by Singla

  • Lecture 25: Learning from experts, Multiplicative weight update

Reference

The following is a list of most commonly referred to references: