CS447 Computer Algorithms (Fall 2020)
Alternate listing: MA447, CS547, EE667
Prerequisites: CS344
Instructor: Christino Tamon
Lectures: TR 8am (online, synchronous)
Office hours: TBA
Text:
Jeff Erickson, "Algorithms", self-published, 1st edition, 2019.
link.
Additional reference:
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. 3e, MIT Press, 2009.
Syllabus
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.
Course Objectives and Outcomes
The objective of this course is to learn how to:
- design efficient algorithms for computational problems
- analyze the correctness of these algorithms
- prove the running times of these algorithms
Upon completion of this course, students should be able to:
- Deploy algorithmic design tools such as divide-conquer, dynamic programming, greedy methods, and randomization.
- Use analytical tools such as summations, recurrences, probabilistic analysis, and amortization.
- Detect incorrect analyses and construct counterexamples to faulty claims.
- Explain the concept of intractability and NP-completeness.
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)
- Basic algorithmic techniques: background.
- Advanced algorithmic techniques
- probabilistic analysis
- dynamic programming
- greedy methods
- amortization
- Graph algorithms.
- Intractability: NP-completeness.
Schedule (in progress)
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 (updated regularly)
- Satisfiability:
Schoning's algorithm,
unique SAT.
SAT competition.
- Compression algorithms:
anomaly detector,
dynamic Huffman,
Huffman encryption,
Lempel-Ziv (notes by Shor),
anomaly detector,
arithmetic coding,
Burrows-Wheeler.
- Advanced graph algorithms:
maximum matching, k-connectivity, PageRank: net.
- Linear programming:
Ellipsoid method, Karmarkar algorithm.
Support: cvxopt.
- Dynamic algorithms and data structures:
notes,
survey,
A*.
- Streaming algorithms:
resources.
- Partially observable Markov decision processes:
slides,
tutorial,
algorithms.