CS447 Computer Algorithms (Fall 2025: 8/25 - 12/5)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344 Algorithms and Data Structures

Instructor: Christino Tamon
Lectures: TR 09:30-10:45, B10L Snell
Office hours: SC373, TR 11-1, W 12-2. (Distance section: email to arrange a zoom meeting.)
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 (tentative)

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

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

Reading: Chapter 1-2.

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

Reading: Chapter 6-7,9.

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

Reading: Chapter 6-7,9

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

Reading: Section 9.3. Original paper.

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

Sep 11
Asymptotics: how to compare algorithms
Recurrences. Summation

Reading: Chapter 3. See extra notes on moodle.

Sep 16
Asymptotics and Recurrences (Chapter 3) 		Sep 18
Asymptotics: recursive (recurrence) vs iterative (summation).

Reading: Chapter 3. Appendix A.

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

Reading: Section 4.5.

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

Sep 30
Probabilistic algorithms.
Random walk on a line (HW1).

Reading: Chapter 5.

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

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

Oct 7
Greedy algorithms: interval packing (activity scheduling)

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

Oct 9
Greedy Set Cover: (ln n)-approximation algorithm
Harmonic numbers. Integral approximation of divergent sum.

Reading: Chapter 35.

Oct 14
Short break (no class). 		Oct 16
Guest lecture: Kun Han.
Huffman coding.

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

Oct 21
JabberWocky

Reading: Shor's notes.

Oct 23
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 28
Amortization.
The union-find data structure.

Oct 30
Midterm.
Nov 4
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 6
Graph algorithms.
Topological sort. Strongly connected components.

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

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

Reading: Chapter 24-25.

Nov 13
More graph algorithms.
Nov 18
Maximum Flow.
Ford-Fulkerson: augmenting paths. Edmonds-Karp.

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

Nov 20
Maximum Flow and Minimum Cut (continued).
Nov 25
Nov 27
Thanksgiving break.

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

Reading: Chapter 34.

Dec 4
More NP-completeness.

Reading: Chapter 34.

Assignments

Miscellany