CS447 Computer Algorithms (Fall 2023: 8/28 - 12/8)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344 Algorithms and Data Structures

Instructor: Christino Tamon
Lectures: TR 09:30-10:45, Science Center 360
Office hours: Science Center 373, TR 10:45-13:30. Also 15min before class.
Text: Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. 4ed, MIT Press.

Optional: Jeff Erickson, "Algorithms", 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:

  1. Use design tools such as divide-conquer, dynamic programming, greedy and randomized methods for solving problems involving graphs and other combinatorial structures.
  2. Apply techniques such as summations, recurrences, probabilistic analysis and amortization to analyze the complexity of algorithms.
  3. Recognize incorrect analyses and construct counterexamples to false claims about algorithms.
  4. 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

Topics

Schedule (in-progress)

Additional lecture notes are available on our Moodle course page. The chapter numbers refer to the third edition of the textbook.
Aug 29
Divide-conquer:
The power of recursive thinking.
Warmup example: MINMAX.

Reading: Chapter 1-2.

Aug 31
Sorting and selection:
the good, the bad and the ugly.

Reading: Chapter 6-7,9.

Sep 5
Sorting: the good, the bad and the ugly (HW0).

Reading: Chapter 6-7,9

Sep 7
Selection in linear-time!
Classic algorithm by Blum, Floyd, Pratt, Rivest and Tarjan.

Reading: Section 9.3. Original paper.

Sep 12
Lower bounds: why is this algorithm optimal?
MIN and SORTING: adversary and counting arguments.

Sep 14
Asymptotics: how to compare algorithms
Recurrences. Summation

Reading: Chapter 3. See extra notes on moodle.

Sep 19
No class.

Makeup class: Mon 9/25. Asymptotics and Recurrences (Chapter 3)

Sep 21
Asymptotics: recursive (recurrence) vs iterative (summation).

Reading: Chapter 3. Appendix A.

Sep 26
Master Theorem.
Integer multiplication: Karatsuba's algorithm (see also Section 4.2).

Reading: Section 4.5.

Sep 28
Lightbulb problem (HW1)

Quiz 1.

Oct 3
Probabilistic algorithms.
Random walk on a line (HW1).

Reading: Chapter 5.

Oct 5
Dynamic programming:
Longest common subsequence.

Reading: Chapter 15. (4ed: Chapter 14, Section 4 (LCS))

Oct 10
Short break (no class). 		Oct 14
Dynamic programming.
Edit distance.

Reading: Chapter 15. (4ed: Chapter 14, Exercise 14-5 (edit distance))

Oct 17
More Dynamic programming.

Reading: Chapter 15. (4ed: Chapter 14)

Oct 19
Greedy algorithms: activity scheduling.
Reading: Chapter 16, class notes. (4ed: Chapter 15, 15.1 (activity selection))

Quiz 2.

Oct 24
Compression: Huffman coding.

Reading: Chapter 16. (4ed: Chapter 15, 15.3 (Huffman codes))

Oct 26
Compression: JabberWocky (Lempel-Ziv).

Reading: class notes. Also see notes (P. Shor).

Oct 31
Back to Dynamic Programming:
Hidden Markov Model (HW2).

Reading: Chapter 15. (4ed: Chapter 14)

Nov 2
Midterm.
Nov 7
Amortized analysis.
Accounting method. Potential function.

Reading: Chapter 17. (4ed: Chapter 16)

Nov 9
Amortization.
Splay trees. (Omitted: Union Find).

Reading: notes. Chapter 21. See also notes from the following sources: CMU, Erickson, Stanford, Goemans, Mount.

Nov 14
Graph algorithms.
Breadth and Depth First Searches (BFS and DFS).
Topological sort. Strongly connected components.

Reading: Chapter 22-25. (4ed: Chapter 20, Figure 20.3 (BFS), Figure 20.4 (DFS), Figure 20.7 (topological sorting), Figure 20.9 (strongly connected component))

Nov 16
Maximum-Flow.
Ford-Fulkerson: augmenting paths.

Reading: Chapter 26. (4ed: Chapter 24, Figure 24.6)

Nov 21
Optional Test. 		Nov 23
Thanksgiving break.

Nov 28
Maximum Flow Minimum Cut (Edmonds-Karp)

Reading: Chapter 26. (4ed: Chapter 24, Figure 24.7)

Nov 30
Graph algorithms.
Shortest Paths (Bellman-Ford, Dijkstra, Floyd-Warshall).
Greedy and Dynamic Programming strikes again.

Reading: Chapter 24-25. (4ed: Chapter 22, Figure 22.4 (Bellman-Ford), Figure 22.6 (Dijkstra)) (4ed: Chapter 23, Figure 23.1 (matrix multiplication), Figure 23.4 (Floyd-Warshall))

Dec 5
NP-completeness.
SAT, MAXCUT.

Reading: Chapter 34.

Dec 7
More NP-completeness.

Reading: Chapter 34.

Assignments

Miscellany