cmps-2200-notes

CMPS2200: Introduction to Algorithms

CMPS 2200 Slides Repository

All lecture slides are listed below. These are organized by module, each of which may contain one more more lectures.

These lectures are prepared using Jupyter, an interactive environment for coding and presenting. You can access the github repository containing the lecture notes here: https://github.com/CMPS-2200/cmps-2200-notes

Linked below are are all produced slide decks. You may also clone the repository and view the jupyter notebooks using Visual Studio Code.

Slide Decks
Module 01: Formalizing the cost of an algorithm
Introduction
Asymptotic Analysis
Parallelism
Functional programming
SPARC
Cost models
Module 02: Recurrences
Recurrences
The Brick Method
Divide and Conquer Multiplication
Module 03: Sequences
Sequences Overview
Reduce
Scan
Problem solving with sequences
Module 04: Divide and Conquer
Reductions and Brute Force
Divide and Conquer Scan
MCSS and Euclidean TSP
Midterm Review
Module 05: Randomized Algorithms
Randomized Algorithms
The Selection Problem
Quicksort
Module 06: Greedy Algorithms
Greedy Algorithms
Meldable Priority Queues
Huffman Encoding
Module 07: Dynamic Programming
Dynamic Programming
Edit Distance, LIS
Optimal BSTs
Module 08: Graphs
Graphs
Breadth-First Search
Depth-First Search
Shortest Paths
Bellman-Ford
All Pairs Shortest Paths
Module 09: Spanning trees
Minimum Spanning Trees
Kruskal’s Algorithm, TSP (revisited)
Graph Contractions
Star Contractions
Boruvka’s Algorithm
Module 10: Computability
Computational Complexity
Final Review