Lectures

This page contains the order of topics contained in lectures, listed as a sequence of modules. Please note that modules may vary considerably in length and difficulty; please see the schedule for details on timing.

Lecture materials are posted on LEARN in various formats, for your convenience. The slides and audio have been joined together into videos; there are also written transcripts of the audio.

Please see the resources page for additional relevant material, including a document outlining coverage of the material by the (optional) textbook.

Module 1: Introduction

Topics: Introduction, course goals, types of problems, exhaustive search

Module 2: Comparing problems and solutions

Topics: Comparing problems, models of computation, pseudocode, asymptotic notation, analyzing algorithms, analyzing exhaustive search

Module 3: Greedy approach

Topics: Scheduling activities, making change, fractional knapsack, single-source cheapest paths, spanning tree

Module 4: Divide-and-conquer

Topics: Binary search, sorting, solving recurrence relations, maximum subtotal, matrix multiplication

Module 5: Dynamic programming

Topics: Matrix-chain multiplication, longest common subsequence, all-pairs cheapest paths

Module 6: Hardness of problems

Topics: Complexity, polynomial time, lower bounds, decision trees, adversary lower bounds, reductions, NP-completeness

Module 7: Compromising on speed

Topics: Search trees, backtracking, branch and bound, fixed-parameter algorithms, Las Vegas algorithms

Module 8: Compromising on correctness

Topics: Approximation algorithms, Monte Carlo algorithms, heuristics

CS 231: Algorithmic Problem Solving