CS447 Computer Algorithms (Fall 2019)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344
Instructor: Christino Tamon
Lectures: TR 8am SC356
Office hours: TR 9:15-11am, 2:15-3:30 SC373
Contact: last name preceded by first initial at clarkson.edu
Text: Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. 3e, MIT Press, 2009.

Outline

This course covers algorithmic thinking relevant for solving problems efficiently. Standard techniques covered include: divide-conquer methods, recurrence analysis, dynamic programming, greedy methods, amortization, and others. This course also covers intractabilities and methods for coping with them.

Objectives and outcomes

The objective of this course is to learn fundamental algorithmic techniques, to gain the ability to evaluate the efficiency of algorithms, and to understand certain intractability issues concerning hard algorithmic questions.

The specific outcomes are basic knowledge of the following:

Requirements and Policies

Although attendance is not mandatory, students are responsible for all course materials covered in lectures and any quizzes given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

Grading Scheme

There is no final exam in this course.

Topics (tentative)

Schedule (in progress)

Sep 3
Reductions: Satisfiability.
Reading: Chapter 34. 		Sep 5
Reductions: k-SAT < 3-SAT.
3-SAT < Vertex-Cover < Stable-Set.
Reading: Chapter 34.
Sep 10
2-SAT: as a graph theory problem.
Reading: Chapter 22 (Section 5). 		Sep 12
2-SAT: random walk algorithm.
Reading: Chapter 5 for background on probabilistic analysis of algorithms.
Sep 17
Dynamic programming.
Reading: Chapter 15. 		Sep 19
Dynamic programming.
Reading: Chapter 15.
Sep 24
Guest lecture: Chris Lynch.
Topics: Longest Common Subsequence. Edit Distance.
Reading: Chapter 15, Exercise 15-5. 		Sep 26
No class.
Oct 1
Greedy methods: Activity selection, Huffman coding.
Reading: Chapter 16. 		Oct 3
Greedy methods: Huffman coding, Lempel-Ziv.
Reading: Chapter 16.
Oct 8
Amortization: Stack, Binary counter.
Reading: Chapter 17. 		Oct 10
Disjoint sets: Union-Find.
Reading: Chapter 21.
Oct 15
Short break. 		Oct 17
Disjoint sets: Union-Find.
Reading: Chapter 21.
Oct 22
Review. 		Oct 24
Disjoint sets: Union-Find.
Reading: Chapter 21.
Oct 29
Maximum flow: Bellman-Ford.
Reading: Chapter 26. 		Oct 31
Maximum flow: Edmonds-Karp.
Reading: Chapter 26.
Nov 5
MaxFlow and MinCut Theorem.
Reading: Chapter 26. 		Nov 7
Recap: Asymptotics.
Reading: Chapter 3.
Nov 12
Recap: summations.
Reading: Chapter 4. 		Nov 14
Recurrences: Master theorem.
Reading: Chapter 4.
Nov 19
Linear programming: simplex method.
Reading: Chapter 29. 		Nov 21
Linear programming: duality.
Reading: Chapter 29.
Nov 26
Randomized methods.
Reading: Chapter 5. 		Nov 28
Thanksgiving break.
Dec 3
Randomized methods: online hiring.
Reading: Chapter 5. 		Dec 5
Test 2 (in-class).
Dec 10
Cook-Levin theorem. 		Dec 12
Final project talks.

Assignments

Project

  1. Choose a project topic of interest; you may work in groups of up to three or four.
    Indicate your topic and group by early November.

  2. Submit a final report (hardcopy, at least 10 pages) that contains at minimum the following separate sections:

  3. Prepare a 5-10 minute talk to be delivered during Dead Week (in class).
    Submit by email your talk slides (PDF).

  4. Submit any other items, if any, related to your project (code, etc) by email.
Project Topics (TBA) Groups:
. . . .