CR: COMP 3804 Learning Objectives - Revision history

Maheshwa: /* Topics */

2011-03-22T17:43:42Z

Topics

← Older revision		Revision as of 17:43, 22 March 2011
Line 22:		Line 22:
	* Disjoint Sets Data Structure?		* Disjoint Sets Data Structure?
	* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).		* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
	* Greedy Algorithms: Minimum ~~SPanning~~ Trees, Huffman Encodings, ...		* 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), ~~ideas~~ of simplex algorithm ~~(or the randomized algorithm)~~. [This was never covered before]		* 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.		* Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.

Maheshwa: /* Topics */

2011-03-22T17:42:41Z

Topics

← Older revision		Revision as of 17:42, 22 March 2011
Line 18:		Line 18:

	=Topics=		=Topics=
	~~COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel~~
	* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.		* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
	* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..		* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..

Maheshwa: /* Calendar Description */

2011-03-22T17:42:04Z

Calendar Description

← Older revision		Revision as of 17:42, 22 March 2011
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=

Maheshwa: /* Topics */

2011-03-10T17:52:40Z

Topics

← Older revision		Revision as of 17:52, 10 March 2011
Line 16:		Line 16:
	=Topics=		=Topics=
	COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel		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.		* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
	* Divide and Conquer: ~~Some are already stated above~~, ~~Median~~		* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
	* Disjoint Sets Data Structure		* Disjoint Sets Data Structure?
	* ~~Graph Algorithms~~: Representation, DFS, BFS, Shortest Paths (including A* heuristic).		* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
	* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...		* 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), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]		* 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~~, and brief~~ idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).		* 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.

Maheshwa: /* Topics */

2011-03-10T16:42:42Z

Topics

← Older revision		Revision as of 16:42, 10 March 2011
Line 18:		Line 18:
	* 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.		* 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		* Divide and Conquer: Some are already stated above, Median
			* Disjoint Sets Data Structure
	* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).		* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).
	* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...		* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...

Maheshwa: /* Topics */

2011-03-10T16:20:38Z

Topics

← Older revision		Revision as of 16:20, 10 March 2011
Line 21:		Line 21:
	* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...		* 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), ideas of simplex algorithm (or the randomized algorithm).		* 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, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).		* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).

Maheshwa: /* Topics */

2011-03-10T16:19:38Z

Topics

← Older revision		Revision as of 16:19, 10 March 2011
Line 18:		Line 18:
	* 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.		* 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		* Divide and Conquer: Some are already stated above, Median
	* Graph Algorithms: Representation, DFS, BFS, Shortest Paths.		* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).
	* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...		* 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), ideas of simplex algorithm (or the randomized algorithm).		* 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.		* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).

Maheshwa: /* Topics */

2011-03-10T16:15:55Z

Topics

← Older revision		Revision as of 16:15, 10 March 2011
Line 16:		Line 16:
	=Topics=		=Topics=
	COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel		COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
	* Introduction:		* 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.

Maheshwa: /* Topics */

2011-03-10T16:08:13Z

Topics

← Older revision		Revision as of 16:08, 10 March 2011
Line 15:		Line 15:

	=Topics=		=Topics=
			COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
	~~==Topic 1==~~		* Introduction:

	~~Learning objectives for topic 1~~

	~~==Topic 2==~~

	~~Learning objectives for topic 2~~

Maheshwa: /* Learning Objectives */

2011-03-10T16:06:34Z

Learning Objectives

← Older revision		Revision as of 16:06, 10 March 2011
Line 8:		Line 8:

	Objectives for the whole course		Objectives for the whole course
	* Designing algorithms, their correctness and efficiency		* 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=		=Topics=