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.

The Guide

What is an algorithm? (esp. sections 0.1 to 0.4) (from Jeff Erickson)

Review: recursion

Back to contents

Review: proof technique and induction

Back to contents

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.

Back to contents

Is it correct? (by contradiction)

Back to contents

Review: logarithms

Back to contents

Run time analysis

Back to contents

Divide and conquer & recurrence relations

We use recurrence relations to describe and analyze the running time of recursive and divide & conquer algorithms.

Back to contents

Dynamic Programming

Back to contents

Test your knowledge: 4 ways to solve the max subarray problem (project)

Here is a projectupload 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:

Back to contents

Linear Programming

Back to contents

Test your knowledge: Linear programming (project)

Back to contents

Computational complexity

Back to contents

NP-completeness and reductions

Back to contents

Credits

Many thanks go out to those who make knowledge freely available online.