CMPT405 Spring 2016

Instructor: Petra Berenbrink, petra@sfu.ca, TASC1 8227
TA: Chang Xu (Steve), xuchangx@sfu.ca,
TA office hour:
Monday 12:00 - 13:00 ASB 9814
Friday 15:00 - 16:00 ASB 9814

Textbook

Introduction to Algorithms

Hardcover – Jul 31 2009 by Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein

Outline

• Greedy Algorithms
• Dynamic Programming
• Graph Algorithms (shortest paths, spanning trees, flow)
• NP-Completeness
• Approximation Algorithms
• Amortized Analysis
• Local Search or Algorithmic Game Theory

Grading scheme

• 70% final
• 30% for 2 midterms

Please note that students have to pass the final to pass this course.

Slides

Greedy Algorithms
Shortest Path
Minimum Spanning Tree
Network Flow
Complexity
Approximation

Problems

Problem sheet 1
Problem sheet 2
Problem sheet 3
Problem sheet 4
Problem sheet 5
Problem sheet 6
Problem sheet 7
Problem sheet 8