COMP317: Design and Analysis of Algorithms (the 2009 EDITION)

Assignment3 Mon 11 May, deadline Fri 22 May
Submit here or email me.

Assignment4 Mon 25 May, deadline Fri 5 June
Submit here or email me.

WARNING: this is *NOT* a complete set of everything I cover in class. The slides below are taken from the following book: Algorithm Design by M.T.Goodrich and R.Tamassia

Simple methods
- GreedyMethod
- DynamicProgramming
- Pseudo code for LCS (longest common subsequence)
- Java source for fast exponentiation and Fibonacci
- An interesting programming problem (for a more challenging version see below: APIO-2009)
- DivideAndConquer
- IntroSort
Graphs
- Graphs background
- Depth-first search
- Breadth-first search
- Minimum Spanning Tree
- Disjoint-set data structure (aka union-find)
- Java source for fast union-find and Kruskal based on it
- ShortestPath
- Directed graphs
- Pseudo code for topologicalSort (corrected book version)
- Biconnectivity
- Network Flow
NP-Completeness
- NP-Completeness definitions
- NP-Completeness reductions
- Approximation algorithms
- Smart Enumeration (added some slides June 2nd)