CS447/CS547/EE667 Computer Algorithms

CS447 Computer Algorithms (Fall 2020)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344
Instructor: Christino Tamon
Lectures: TR 08:00-09:25 (hybrid/split mode, synchronous), CB 176
Office hours: virtual or outdoors (by appointment)

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

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 (tentative)

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 18	Aug 20 MinMax searching. The power of divide-conquer. Reading: notes, Chapter 0-1.
Aug 25 Sorting: the good, the bad and the ugly (HW0). Selection: median finding (Blum-Floyd-Pratt-Rivest-Tarjan). Reading: notes, Chapter 1.	Aug 27 Recurrences; Asymptotics. Lower bounds. Reading: supplementary notes, Chapter 1.
Sep 1 Backtracking: subset-sum, etc. Reading: Chapter 2 (optimal BST, LIS)	Sep 3 Constraint Satisfaction Problem (CSP): randomized and graph-theoretic methods (HW1). Reading: Chapter 2.
Sep 8 Dynamic programming. Reading: Chapter 3.	Sep 10 Dynamic programming: Edit Distance. Reading: Chapter 3.
Sep 15 Dynamic programming: Viterbi (HW2). Reading: see class notes.	Sept 17 Hidden Markov Model: Viterbi (continued). Reading: see class notes.
Sep 22 Greedy algorithms: activity scheduling. Reading: Chapter 4.	Sep 24 Greedy: optimality (exchange property). Reading: Chapter 4.
Sep 29 Huffman coding. Reading: Chapter 4.	Oct 1 Compression: Lempel-Ziv. Reading: see class notes; also notes (by Peter Shor).
Oct 6 Amortized analysis. Stack and Vector examples. Potential function. Reading: see class notes.	Oct 8 Test 1.
Oct 13 Graph theory. Adjacency list vs matrix. Breadth vs Depth First Search. Reading: Chapter 5,6.	Oct 15 Graph theory. Topological sorting (DFS). Strongly connected components (DFS). Shortest Paths (Dijkstra: greedy method). Reading: Chapter 5,6,8.
Oct 20 Maximum-Flow Minimum-Cut. Ford-Fulkerson: st-flow, st-cut, augmenting path. Reading: Chapter 10.	Oct 22 Maximum-Flow Minimum-Cut. Edmonds-Karp: shortest augmenting path. Applications: maximum bipartite-matching. Reading: Chapter 10,11.
Oct 27 NP-Hardness. Reading: Chapter 12.	Oct 29 NP-Hardness. Reading: Chapter 12.
Nov 3 Test 2.	Nov 5 Other graph problems: minimum spanning trees, bipartite perfect matching (via MaxFlow), maximum matching.
Nov 10 Data structures: heap (heapsort), splay trees, disjoint union.	Nov 12

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.
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*.
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

Josh, Marzieh, Irving: compression algorithms.
Esma, Tom: streaming algorithms.
Jeremy, Ken, Kristen, Joshua: Huffman encryption.
Mingjun, Sichao: POMDP algorithms.
Peter-John, Tyler, Wayne: image processing (anti aliasing) algorithms.
Ghada: all-pairs-shortest-paths.
Chris: graph algorithms (pagerank).
Ryan, Mike: algorithmic libraries.
Daniel, Tyler: satisfiability algorithms.
Anthony: A* search.
Justin, Joe, Hannah: reservoir sampling.
Henry, Andy: bi-directional search algorithms.
Cameron: distribution sorting algorithms.
Thomas, David: computational geometry algorithms.