CSC 222 Lectures: Fall 2006
- Lecture 1 - Input Size, Basic Operations - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 2 - Overview of Functions; Best, Worst, and Average Case- [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 3 - Average, Amortized; Start of Formal Analysis - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 4 - Formal Analyses; Limit Based Approach - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Useful Logarithms - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 5 - Logarithms; Limit Based Approach; Analyzing Non-Recursive Functions - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 6 - Analyzing Non-Recursive Functions; Review of Mergesort - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 7 - Analyzing Recursive Functions; Backwards Substitution - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 8 - Recursive Functions - Backwards Substitution; Master Theorem - [Powerpoint (with instructor notes)][PDF (without instructor notes)]
- Lecture 9 - Decision Trees and Lower Bounds - [Microsoft Word][PDF]
- Lecture 10 - Trivial Lower Bounds and Reductions - [Microsoft Word][PDF]
- Lecture 11 - Adversary Arguments Lecture - [Microsoft Word][PDF]
- Lecture 12 - General Adversary Argument for Sorting; Decision vs Optimization Problems; Halting Problem - [Microsoft Word][PDF]
- Lecture 13 - P, NP, and NPC Classes - [Microsoft Word][PDF]
- Lecture 14 - Homework Review, Graph Datastructures - [Microsoft Word][PDF]
- Lecture 15 - Graph Datastructures, Intro to Greedy Algorithms - [Microsoft Word][PDF]
- Lecture 16 - Greedy Algorithms, Minimum Spanning Tree - [Microsoft Word][PDF]
- Lecture 17 - Greedy Algorithms, Shortest Path, BFS for Uniform Weight Edges - [Microsoft Word][PDF]
- Lecture 18 - Dynamic Programming Introduction, Edit Distance - [Microsoft Word][PDF]
- Lecture 19 - Dynamic Programming Bellman Ford Algorithm, Knapsack Solution - [Microsoft Word][PDF]
- Lecture 20 - Dynamic Programming For Knapsack, Pseudo-polynomial Algorithms, Introduction to Branch and Bound - [Microsoft Word][PDF]
- Lecture 21 - Branch and Bound, Application to Knapsack Problem - [Microsoft Word][PDF]
- Lecture 22 - Branch and Bound, Application to Assignment Problem - [Microsoft Word][PDF]