CR: COMP 3804 Learning Objectives

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

COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel

• Introduction: Whats an Algorithm, Simple Divide and Conquer Algorithms (e.g. Multiplying two n-bit integers), merge-sort, bib-O notation, recurrence relation, masters theorem.
• Divide and Conquer: Some are already stated above, Median
• Graph Algorithms: Representation, DFS, BFS, Shortest Paths.
• 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).
• NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems.