[ Assignments | CIS | UO | News ]

CIS 621 Winter 1997

Algorithms and Complexity

CRN 22094

Time: Mondays, Wednesdays and Fridays at 13:00.
Place: 137 Gilbert Hall.
Texts:
- M.R. Garey and D.S. Johnson,
  Computers and Intractability,
  W.H.Freeman 1979.
- A.V. Aho, J.E. Hopcroft and J.D. Ullman,
  The Design and Analysis of Computer Algorithms,
  Addison-Wesley 1987.
Supplemental Reading:
- T.H. Cormen et al.,
  Introduction to Algorithms,
  McGraw Hill 1990.
Bulletin Board: uo.classes.cis.621
Instructor: Andrzej Proskurowski
- email: andrzej@cs.uoregon.edu
- office: 256 Deschutes,
- phone: x6-4428.
- office (half) hours: Mon., Wed., Fri. 2 pm.
  and by appointment
Assistent: Amithaba Roy
- email: aroy@cs.uoregon.edu
- office: 233 Deschutes,
- phone: x6-1384.
- Office hours: Mon., Tue, Wed., Thurs. 9-10 am.
Evaluation:

Weekly Homework Assignments 35%

Take home Midterm and Final Examinations 60%

Class Participation 5%
Description: This is a course in complexity of discrete optimization problems. We will assume a working knowledge with different models of computation (finite state machines, formal languages, Turing machines, algorithmic programming languages). In the first part of the course, we will discuss design and analysis of computer algorithms as pertaining to their complexity and correctness (``Big-Oh'' notation, loop invariant, structural induction). The second part of the course will be devoted to the abstract complexity of optimization problems.

Tentative Syllabus

Week of Text chptr. Description

Jan. 6 AHU 1, GJ 1 Introduction: complexity measures, discrete optimization
problems, correctness proofs.

Jan. 13 AHU 2, 3 Algorithm design methods: divide-and-conquer
(order statistics),

Jan. 20 AHU 2, 4 dynamic programming (matrix chain product).

Jan. 27 AHU 5 Graph algorithms: depth-first search, tree isomorphism.

Feb. 3 AHU 10, GJ 2 Classes P, NP and NPC, Cook's Theorem.

Feb. 10 AHU 1-5 Take home Midterm exam due

Feb. 17 AHU 10, GJ 3 Six basic NP-complete problems.

Feb. 24 GJ 4, 5 Strong NP-completeness, NP-hardness.

March 3 GJ 6 Approximation problems.

Mar. 10 AHU 11, GJ 7 Beyond NP-completeness.

Mar. 17 comprehensive Final Exam due

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

Week of	Text chptr.	Description

Jan. 6	AHU 1, GJ 1	Introduction: complexity measures, discrete optimization problems, correctness proofs.
Jan. 13	AHU 2, 3	Algorithm design methods: divide-and-conquer (order statistics),
Jan. 20	AHU 2, 4	dynamic programming (matrix chain product).
Jan. 27	AHU 5	Graph algorithms: depth-first search, tree isomorphism.
Feb. 3	AHU 10, GJ 2	Classes P, NP and NPC, Cook's Theorem.
Feb. 10	AHU 1-5	Take home Midterm exam due
Feb. 17	AHU 10, GJ 3	Six basic NP-complete problems.
Feb. 24	GJ 4, 5	Strong NP-completeness, NP-hardness.
March 3	GJ 6	Approximation problems.
Mar. 10	AHU 11, GJ 7	Beyond NP-completeness.
Mar. 17	comprehensive	Final Exam due