This guide is intended for self-study of undergraduate algorithms as taught at Oregon State University.
Prerequisites
Data structures and introductory discrete mathematics: trees and graphs, data structures such as priority queues, basic proof technique including induction, and basic graph algorithms such as Dijkstra, Prim and Kruskal.
Please contact me if you find dead links or encounter errors.
Contents of the Guide (hide)
- Review: recursion
- Review: proof technique and induction
- Is it correct? (by induction)
- Is it correct? (by contradiction)
- Review: logarithms
- Run time analysis
- Divide and conquer & recurrence relations
- Dynamic Programming
- Test your knowledge: 4 ways to solve the max subarray problem (project)
- Linear Programming
- Test your knowledge: Linear programming (project)
- Computational complexity
- NP-completeness and reductions
The Guide
What is an algorithm? (esp. sections 0.1 to 0.4) (from Jeff Erickson)
Review: recursion
- Binary search: an example (video)
- Binary search (interactive questions)
- Review mergesort (from Algorithms by Sedgewick and Wayne).
- Doubling search (video)
- Pseudocode for doubling search (video)
- A visualization of mergesort (from Vamanos)
- Review the stack and recursion by playing Robozzle. Solve puzzles 330, 536, 656.
Review: proof technique and induction
- Video lectures from CS225:
- Propositions & Simple Formulas: lecture and example.
- Logical Equivalence: lecture and example.
- Predicates and Quantifiers: lecture and example.
- Direct Proof & Contrapositive: lecture and example.
- Contradiction & Other techniques: lecture and example.
- Weak Induction: lecture and example.
- Strong Induction: lecture and example.
- Recursive Definitions: lecture and example.
- Structural Induction: lecture and example.
- Review of induction (video by Khan Academy)
- Review notes for induction (sections 1-4) (from Jeff Erickson)
- An example inductive proof (video) and accompanying pdf
Is it correct? (by induction)
We often use induction to prove that recursive algorithms are correct. In fact, recursion and induction are pretty much the same thing.
- Making postage recursively (interactive questions)
- Correctness of mergeseort & merge (video)
- Using induction to design and debug
- Practice problems for induction.
Is it correct? (by contradiction)
- Lecture notes on MST algorithms and their correctness (esp. sections 20.1-20.3) (from Jeff Erickson)
- MST and the cut property (interactive questions)
- MST correctness (video)
- A visualization of Prim's MST algorithm (from Vamanos)
- A visualization of Kruskal's MST algorithm (from Vamanos)
- Boruvka's algorithm (video)
- A visualization of Boruvka's algorithm (from Vamanos)
- Practice problems for contradiction.
Review: logarithms
- Tutorial on logarithms (by Khan Academy)
- Log log plots tutorial (video) and accompanying file
Run time analysis
- An intro to big-Oh (from Richard Chang)
- Introduction to Asymptotic Analysis (from Cornell University)
- Asymptotic analysis & big-Oh (interactive questions)
- Asymptotic Notation Cheat Sheet
- Practice problems for asymptotic notation
Divide and conquer & recurrence relations
We use recurrence relations to describe and analyze the running time of recursive and divide & conquer algorithms.
- Notes on recurrence relations, read section 3 (from Jeff Erickson)
- A recurrence for make-postage (video)
- A recurrence for binary-search (video)
- Notes on divide and conquer algorithms, read sections 1.5-1.8 (from Jeff Erickson)
- Recursive multiplication (video)
- A visualization of recursive multiplication (from Vamanos)
- Computing a geometric series (video from Khan Academy)
- Geometric series (interactive questions)
- Finishing up recursive multiplication (video)
- Solving a general recurrence relation (interactive questions)
- Practice problems for Divide and Conquer
Dynamic Programming
- Intro to Dynamic Programming (video)
- Longest Common Substring Problem (Wikipedia)
- Fibonacci numbers (interactive questions)
- Dynamic Programming: sections 5.1 to 5.5 (from Jeff Erickson)
- Longest increasing subsequence (interactive questions)
- Longest increasing subsequence (video)
- Longest increasing subsequence (visualization)
- The Knapsack Problem (read intro, definition and DP solution to 0/1 problem (from Wikipedia)
- Sequence alignment
- Practice problems for DP
Test your knowledge: 4 ways to solve the max subarray problem (project)
Here is a project to test your knowledge of designing and analyzing divide and conquer and dynamic programming algorithms. Try to complete the project first and then check your ideas against the explanation of these algorithms here:
- A video explaining 4 ways to solve the max subarray problem and accompanying pdf (pages 8 to 13).
Linear Programming
- Intro to Linear Programming (sections 1.1 and 1.2) (from Steven Miller)
Note that on page 3, the first two inequalities should be:
30 x_1 + 15 x_2 >= 60
5 x_1 + 10 x_2 >= 70 - A simple LP (interactive questions)
- The bicycle problem (video) and accompanying file
- Solving the bicycle problem with Matlab (video)
- The Bicycle problem polyhedron (video)
- The shortest path LP and my pet graph (video)
- Practice Problems for LP
Test your knowledge: Linear programming (project)
- Versatility of Linear Programming (section2) (from Steven Miller)
- COMING SOON
Computational complexity
- A short introduction to complexity (video)
- A long introduction to complexity (video)
- To understand how we can talk about computation in a formal way, we must understand Turing machines (from MIT OCW)
- An undecidable problem, the halting problem (from Craig Kaplan)
- The importance of polynomial time (interactive questions)
- Sorting lower bound (video)
- Non-determinism (video)
NP-completeness and reductions
- A working definition of NP-hard (from Stephen Boyd)
- NP-hard problems, read sections 30.1 to 30.4 (30.4 is advanced, but good for you) (from Jeff Erickson)
- Reductions (video)
- Is this problem in NP? (interactive questions)
- NP-hard problems, read sections 30.5 and 30.6 (from Jeff Erickson)
- NP, NP-hard and NP-complete (interactive questions)
- TSP is NP-hard (video)
- How to show a problem is NP hard (video)
- NP-hard problems, read sections 30.7 to 30.12 (from Jeff Erickson)
- Practice problems for computational complexity
Credits
- Videos recorded by Glencora Borradaile and editted by eCampus as Oregon State University.
- Interactive questions designed by eCampus as Oregon State University.
- Visualizations of algorithms in Vamanos by Brent Carmer and Mike Rosulek.
- Review videos by Khan Academy.
- Course materials by Jeff Erickson.
- Wikipedia and other selected materials.
Many thanks go out to those who make knowledge freely available online.
resources
courses
- CS523, Spring 2020
- CS515, Fall 2018
- CS325, Fall 2018
- CS523, Winter 2017
- CS523, Spring 2016
- CS325H, Winter 2016
- CS325, Fall 2015
- CS507, ECE507, Fall 2015
- CS523, Spring 2015
- CS325, Winter 2015
- CS325, Fall 2014
- CS523, Spring 2014
- CS325, Fall 2013
- CS515, Fall 2013
- CS523, Spring 2013
- CS325, Fall 2012
- CS523, Spring 2012
- CS515, Fall 2011
- CS523, Spring 2011
- CS325, Winter 2011
- CS515, Fall 2010
- CS521, Spring 2010
- CS325, Winter 2010