CS447 Computer Algorithms (Fall 2018)
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 3rd letter in the alphabet 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:
- Design and analysis techniques for algorithms.
- Hard problems and methods to cope with them.
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.
- Tests (2): 50%
- Assignments and Quizzes: 40%
- Project: 10%
Topics (tentative)
- Recap: Chapters 1-4
- Algorithmic ideas and techniques
- Chapter 5: probabilistic analysis
- Chapter 15: dynamic programming
- Chapter 16: greedy methods
- Chapter 17: amortization
- Applications: Chapters 22-26 (graph theory)
- Algebraic problems (numbers, matrices, polynomials)
- Intractability (Chapter 34)
- Quantum algorithms
Schedule (in progress)
- Week 1-2: Reduction (Chapter 34)
- Week 3-4: Flows, Cuts, and Matchings (Chapter 26.1-3)
Hall's theorem. Ford-Fulkerson. Edmonds-Karp. Bipartite matching.
Guest lecture on MaxFlow: Chris Lynch (9/18 and 9/20).
- Week 5-6: Stable matching (Gale-Shapley). 3D-Matching. MinCut (Karger's algorithm).
- Week 7-8: Dynamic programming (Chapter 15). Viterbi algorithm (Problem 15-7).
- Week 9-10: Linear Programming (Chapter 29).
- Week 11-12:
Approximation algorithms (Chapter 35).
MaxCut: Goemans-Williamson.
Semidefinite programming (notes).
Multiplicative weights: Arora-Kale-Hazan.
- Time permitting:
Quantum algorithms.
Polynomials and Fast Fourier Transform (Chapter 30).
Coding and Compression (Chapter 16.3, Lempel-Ziv).
Assignments
Project
- 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.
- Submit a final report (hardcopy, at least 10 pages) that contains at minimum
the following separate sections:
- Abstract (What/Why/How).
Provide this on a separate page.
- Background information and literature: what has been done, what is the state-of-the-art
ideas or methods in the area.
Include proper and complete bibliography (at the end of the document) for your sources;
see examples of some journal papers listed below.
- Identify at least two possible ideas that can be done but has not been addressed in
the literature.
This can be either an improvement on implementation or on a mathematical idea.
- Prepare a 5-10 minute talk to be delivered during Dead Week (in class).
Submit by email your talk slides (PDF).
- Submit any other items, if any, related to your project (code, etc) by email.
Project Topics
- Markov decision processes.
- Compression Algorithms (Lempel-Ziv, Burrows-Wheeler).
- Advanced Graph Algorithms.
- Satisfiability.
- Dynamic Data Structures.
- Parallel Noisy Sorting. PageRank.
Groups
- Damon: A*.
- Jack, Ted: Burrows-Wheeler.
- Ben, Ben, Jacob: Lempel-Ziv.
- Chris, Jared, Lee, Nik: SAT.
- Alex: Vertex Cover.
- Iqra, Kristina: PageRank.
- Miao, Yijun: MDP.
- Abdullah, Murshed, Spencer: POMDP.
- Anthony, Anthony, Brian, Hunter: Markov models.
- Jeremy: search.