Calendar Description

COMP 3804 Design and Analysis of Algorithms I

An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.

Assumed Background

COMP 2402 and COMP 2804.

Learning Objectives

Objectives for the whole course

Designing algorithms, their correctness and efficiency.
How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
How to compare one algorithmic solution versus another for a problem
How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

Topics

Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
Disjoint Sets Data Structure?
Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
Dynamic Programming: Edit Distance, Longest Common Sequence, ...
Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.