CS447/CS547/EE667 Computer Algorithms

CS447 Computer Algorithms (Fall 2021)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344
Instructor: Christino Tamon
Lectures: TR 08:00-09:15, 2001 Price Hall
Office hours: TR 9:30-11:00. W 15:00-17:00.

Text: Jeff Erickson, "Algorithms", self-published, 1st edition, 2019. link.

Additional reference (optional): 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

This course is about how to design efficient algorithms for computational problems, how to analyze the correctness of these algorithms, and how to prove the running times of these algorithms.

(Course outcomes) Upon the completion of this course, students will be able to:

employ design tools such as divide-conquer, dynamic programming, greedy and randomized methods for solving problems involving graphs and other combinatorial structures.
use techniques such as summations, recurrences, probabilistic analysis and amortization to analyze the complexity of algorithms.
recognize incorrect analyses and construct counterexamples to false claims about algorithms.
explain the concept of NP-hardness to show the limits of designing efficient algorithms.

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

Basic algorithmic techniques:
- divide-conquer (recursion): Chapter 1
- backtracking: Chapter 2
- randomization
Advanced algorithmic techniques:
- dynamic programming: Chapter 3
- greedy methods: Chapter 4
- amortization
Graph algorithms:
- BFS and DFS: Chapter 5,6
- Minimum spanning trees: Chapter 7
- Shortest paths: Chapter 8,9
- MaxFlow MinCut: Chapter 10,11
NP-hardness: Chapter 12

Schedule (in-progress)

Aug 31 MinMax searching. The power of divide-conquer. Reading: notes-0, Chapter 0-1.	Sep 2 MinMax searching: Recurrence analysis.
Sep 7 Sorting: the good, the bad and the ugly (HW0). Reading: notes-1, Chapter 1.	Sep 9 Selection: linear-time (Blum-Floyd-Pratt-Rivest-Tarjan). Reading: Paper by Blum et al: [pdf].
Sep 14 Recurrences. Summation. Asymptotics. Sorting lower bound. Reading: supplementary notes, Chapter 1.	Sep 16 More asymptotics. Reading: more notes, Chapter 1.
Sep 21 Constraint Satisfaction Problem (CSP): backtracking, random walk methods. Reading: Chapter 2.	Sep 23 Constraint Satisfaction Problem (CSP): Graph-theoretic methods (HW1). Reading: Chapter 2.
Sep 28 Dynamic programming: Longest common subsequence. Reading: Chapter 3.	Sep 30 Dynamic programming: Edit Distance. Reading: Chapter 3.
Oct 5 Dynamic programming: Viterbi (HW2). Reading: see class notes.	Oct 7 Hidden Markov Model: Viterbi (HW2). Reading: see class notes.
Oct 12 Greedy algorithms: activity scheduling. Optimality (exchange property). Reading: Chapter 4.	Oct 14 Greedy algorithms: optimality (exchange property). Reading: Chapter 4.
Oct 19 Compression: Huffman coding. Reading: Chapter 4.	Oct 21 Compression: Huffman coding. Lempel-Ziv. Reading: Chapter 4, class notes; also notes (P. Shor).
Oct 26 Lempel-Ziv (continued). Amortization: stack and vector example. Reading: see class notes.	Oct 28 Amortized analysis. Potential function. Splay trees. Reading: notes.
Nov 2 Graph theory. Adjacency list vs matrix. Breadth vs Depth First Search. Reading: Chapter 5,6.	Nov 4 Graph theory. Topological sorting (DFS). Strongly connected components (DFS). Shortest Paths (Dijkstra: greedy method). Reading: Chapter 5,6,8.
Nov 9 Maximum-Flow Minimum-Cut. Ford-Fulkerson: st-flow, st-cut, augmenting path. Reading: Chapter 10.	Nov 11 Maximum-Flow Minimum-Cut. Edmonds-Karp: shortest augmenting path. Applications: maximum bipartite-matching. Reading: Chapter 10,11.
Nov 16 Graph Algorithms. Reading: Chapter 5-8.	Nov 18 Graph Algorithms. Reading: Chapter 5-8.
Nov 23 Graph Algorithms. Reading: Chapter 5-8.	Nov 25 Thanksgiving break.
Nov 30 Graph Algorithms. Reading: Chapter 5-8.	Dec 2 Test 2.
Dec 2 NP-completeness: Cook-Levin theorem. Karp's list. CLIQUE, VERTEX COVER, MAXCUT. Reading: Chapter 12.	Dec 9 Approximation: MAXCUT. Reading: see class notes.

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 the last 3-4 weeks of the semester).
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 (as a live talk during the last week of class or submitted as a video link).
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. DPLL algorithm.
LLL: Moser-Tardos (Tao's blog).
Graph isomorphism: article (CACM), nauty (McKay), Skiena.
Compression algorithms: dynamic Huffman, Huffman encryption, anomaly detector, arithmetic coding, Burrows-Wheeler transform.
Advanced graph algorithms: maximum matching, k-connectivity, PageRank: net.
Linear programming: notes (Goemans). Simplex method, Ellipsoid method. python.
Semidefinite programming: cvxopt: Goemans-Williamson (maxcut).
Dynamic algorithms and data structures: notes, A*. Transitive closure: Hesse, Hanauer et al.
Streaming algorithms: resources, AMS (classic paper), notes (Trevisan), graph streaming (Charikar).
Markov models.
POMDP: slides, tutorial, algorithms.
Computational geometry: tutorial, Skiena, CGAL.
Papers by Kleinberg.

Groups

Alex: compression for detection.
Saied: streaming algorithms.
Fanghao: transitive closure.
Kristen, Andrew: graph algorithms.
Bobby: beyond SAT.
Remy, Jennifer, Will: PageRank.
Lynden, Matt: computational geometry.
Brian, Nathan: POMDP.
Owen, Joe: compression algorithms.
Gurpreet, Richard: graph algorithms.
James: MDP.