CR: COMP 3804 Learning Objectives: Difference between revisions
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Calendar Description= | =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= | =Assumed Background= | ||
| Line 15: | Line 18: | ||
=Topics= | =Topics= | ||
* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem. | |||
* Introduction: Whats an Algorithm, | * Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication .. | ||
* Divide and Conquer: | * Disjoint Sets Data Structure? | ||
* | * Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic). | ||
* Greedy Algorithms: Minimum | * Greedy Algorithms: Minimum Spanning Trees, Huffman Encodings, ... | ||
* Dynamic Programming: Edit Distance, Longest Common Sequence, ... | * Dynamic Programming: Edit Distance, Longest Common Sequence, ... | ||
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), | * Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), review of simplex algorithm. [This was never covered before] | ||
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem | * 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. | |||
Latest revision as of 17:43, 22 March 2011
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), review of simplex 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.