CS447/CS547/EE667 Computer Algorithms (Fall 2017)
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:
C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2011.
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%
Outline (tentative)
- Introduction: Chapter 1.
- Introduction: Chapter 2.
Formalizing "problem" and "solution". Resources: time, space, etc. Worst-case cost. Asymptotics.
Problems: Fibonacci recurrence. Divide-conquer. Algebraic problems (multiplication).
- Techniques: Chapter 3.
Recursion and divide-conquer. Sorting. Dynamic programming. Greedy methods. Reductions.
Problems: Mergesort. Quicksort. Median.
- (In)tractability: Chapter 4,5,6.
- Coping with hardness: Chapter 9,10.
- Other topics (time permitting): random walks (Chapter 12), satisfiability (Chapter 14), quantum (Chapter 15).
More pointers to the text.
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
- Dynamic Programming: Markov Decision Processes.
- Compression Algorithms: Lempel-Ziv, Burrows-Wheeler.
- Amortized Analysis: Dynamic Data Structures, Splay Trees.
- Algorithms for Graphs: Minimum Spanning Trees (greedy).
- Probabilistic Algorithms: k-Satisfiability.
- (Parallel) Searching and Sorting (under Incomplete Information).
- Rank Aggregation Algorithms: PageRank.
- Hard problems: Travelling Salesperson Problem (TSP), Subset Sum, Shortest Common Supersequence.
Groups
Tuesday talks:
- 8:00: Ryan, Mike: MapReduce.
- 8:10: Wen: sorting algorithms (PageRank).
- 8:20: Zander: learning algorithms (GANs).
- 8:30: Guchuan: network algorithms.
- 8:40: Dohan, Ashwaq, Aratrika: constraint satisfaction algorithms (Schoning's algorithm).
- 8:50: Abby, Ben, Eric: data (pancake) containers.
Thursday talks:
- 8:00: Dennis, Saleh: A* search.
- 8:10: Scott, Matthew: compression.
- 8:20: Abd: compression.
- 8:30: Jacob, Tanner, Brendan: distributed algorithms (Paxos).
- 8:40: Daniel, Joy, Grayson, Andrei: learning Markov models.
- 8:50: Zhiliu: learning algorithms (Capsule Net).
- 9:00: Houchao: NNs.
- 9:10: Phillip: HMMs.