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.

The Guide

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

## 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.

## Divide and conquer & recurrence relations

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

## 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:

## NP-completeness and reductions

Credits

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