Algorithms and Complexity

[ Assignments | CIS | UO | News ]

CIS 621

Winter 2009

Time: Mondays and Wednesdays 12:00 - 1:30
Place: 200 Deschutes
Text:
Kleinberg, Tardos
Algorithm Design
Pearson/Addison-Wesley 2005
Supplemental Reading:
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein
  Introduction to Algorithms,
  McGraw-Hill 2001, 2nd Ed.
- Aho, Hopcroft and Ullman,
  The Design and Analysis of Computer Algorithms,
  Addison-Wesley 1987.
- Garey and Johnson,
  Computers and Intractability,
  W.H.Freeman 1979.
- Knuth,
  The Art of Computer Programming, vols.I, III,
  Addisson-Wesley, 1976.
Instructor: Andrzej Proskurowski
- email: andrzej@cs
- office: 256 Deschutes
- phone: 346-4428
Office half hours: TBA
Objectives: Study of analysis and design of efficient algorithms with examples from several application areas. Introduction into structure of complexity: inherently difficult problems.
Description: We will briefly review the analysis tools: proofs of correctness using the concept of loop invariant ("mathematical induction made simple"), complexity measures ("asymptotic growth of functions"), amortized complexity criterion. The remainder of the course consists of two components treating, respectively, the concrete and the abstract complexity of problems. The former gives standard examples of design strategies: greedy, divide-and-conquer, dynamic programming, followed by examples of algorithms in two main areas of models: graphs and matrices. Discussion of abstract complexity leads into the definition of the class of problems with efficiently verifiable solutions (NP) and the reducibility among problems (NPC).
Evaluation: Weekly homework assignments (discussion encouraged, individually authored submission, contribution acknowledgments required). Take-home midterm and final exams (no collaboration whatsoever). Class participation based on reading assignments and alertness will influence the final grade.

Weekly Homework Assignments 35%

Midterm and Final Examinations 60%

Class Participation 5%
An older edition of this course

Tentative Syllabus

Week of Chptr. Description Comments

Jan. 5 1-3 Introduction: algorithms and data structures, complexity analysis, loop invariants.

Jan. 12 X Amortized complexity, Disjoint sets: union/find, applications.

Jan. 19 4-6 Algorithm design strategies class on Jan. 23

Jan. 26 3 Elementary graph algorithms: traversals

Feb. 2 4 Greedy algorithms

Feb. 9 5 Divide-and-Conquer
Dynamic Programming

Feb. 16 6 Take home Midterm exam due Feb. 22

Feb. 23 8 P vs. NP

Mar. 1 8 NP-completeness proofs

Mar. 9 11 Approximation algorithms

Mar. 18 all the above Take home Final Exam due at 10:15

Weekly Homework Assignments	35%
Midterm and Final Examinations	60%
Class Participation	5%

Week of	Chptr.	Description	Comments

Jan. 5	1-3	Introduction: algorithms and data structures, complexity analysis, loop invariants.
Jan. 12	X	Amortized complexity, Disjoint sets: union/find, applications.
Jan. 19	4-6	Algorithm design strategies	class on Jan. 23
Jan. 26	3	Elementary graph algorithms: traversals
Feb. 2	4	Greedy algorithms
Feb. 9	5	Divide-and-Conquer Dynamic Programming
Feb. 16	6	Take home Midterm exam due Feb. 22
Feb. 23	8	P vs. NP
Mar. 1	8	NP-completeness proofs
Mar. 9	11	Approximation algorithms
Mar. 18	all the above	Take home Final Exam due at 10:15