CS447 Computer Algorithms (Fall 2024: 8/27 - 12/5)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344 Algorithms and Data Structures

Instructor: Christino Tamon
Lectures: TR 09:30-10:45, SN 213
Office hours: Science Center 373, TR 11:00-13:00, W 12:00-14:00. Please email to arrange for a zoom meeting if you are in the distance section.
Optional Texts:

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. 4ed, MIT Press. (CLRS)

Jeff Erickson, "Algorithms", 1st edition, 2019. link. (JeffE)

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.

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)

The chapter numbers refer to the third edition of the optional textbook (CLRS). Most of the class lectures will be self-contained.

Aug 27
Divide-conquer:
The power of recursive thinking.
Warmup example: MINMAX.

Reading: Chapter 1-2.

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

Reading: Chapter 6-7,9.

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

Reading: Chapter 6-7,9

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

Reading: Section 9.3. Original paper.

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

Sep 12
Asymptotics: how to compare algorithms
Recurrences. Summation

Reading: Chapter 3. See extra notes on moodle.

Sep 17
Asymptotics and Recurrences (Chapter 3) 		Sep 19
Asymptotics: recursive (recurrence) vs iterative (summation).

Reading: Chapter 3. Appendix A.

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

Reading: Section 4.5.

Sep 26
Lightbulb problem (HW1):
Boolean constraint satisfaction.

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

Reading: Chapter 5.

Oct 3
Dynamic programming:
Longest common subsequence. Edit distance.

Reading: Chapter 15. (4ed: Chapter 14, Section 4 and Exercise 14-5)

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

Reading: Chapter 15. (Viterbi)

Oct 10
Greedy algorithms: activity scheduling.

Reading: Chapter 16, class notes. (4ed: Chapter 15, 15.1 (activity selection))

Oct 15
Short break (no class). 		Oct 17
Compression: Huffman coding.
Enter the Jabber Wocky.

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

Oct 22
Compression.
More on the Jabber Wocky.

Reading: Shor's notes.

Oct 24
Amortized analysis.
Accounting method. Potential function.
Sleator-Tarjan's Splay trees.

Reading: Chapter 17. (4ed: Chapter 16) notes. Chapter 21. See also: CMU, Erickson, Stanford, Goemans, Mount.

Oct 29
Amortization.
The union-find data structure.

Oct 31
Midterm.
Nov 5
Graph algorithms.
Breadth and Depth First Searches (BFS and DFS).

Reading: Chapter 22-25. (4ed: Chapter 20, Figure 20.3 (BFS), Figure 20.4 (DFS).

Nov 7
Graph algorithms.
Topological sort. Strongly connected components.

Reading: Chapter 22-25. Figure 20.7 (topological sorting), Figure 20.9 (strongly connected component))

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

Reading: Chapter 24-25.

Nov 14
More graph algorithms.
Nov 19
Maximum Flow.
Ford-Fulkerson: augmenting paths. Edmonds-Karp.

Reading: Chapter 26. (4ed: Chapter 24, Figures 24.6 and 24.7)

Nov 21
Maximum Flow and Minimum Cut (continued).
Nov 26
Nov 28
Thanksgiving break.

Dec 3
NP-completeness.
How to cope with hard problems.

Reading: Chapter 34.

Dec 5
More NP-completeness.

Reading: Chapter 34.

Assignments

Miscellany