CS447 Computer Algorithms (Fall 2026: 8/25 - 12/3)

Alternate listing: MA447, CS547, EE667

Prerequisites: CS344 Algorithms and Data Structures

Instructor: Christino Tamon
Lectures: TR 09:30-10:45, CAMP 194
Office hours: SC373, TR 11-1, W 12-2. (Distance section: please 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. Some nonstandard techniques covered include basic quantum algorithms. This course also covers intractabilities and methods for coping with them.
To borrow the Preface from Knuth's monumental work The Art of Computer Programming (Volume 3, second edition), this course attemps to answer the following questions:

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 25
Divide-conquer:
The power of recursive thinking.
Warmup example: MINMAX.

Reading: Chapter 1-2.

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

Reading: Chapter 6-7,9.

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

Reading: Chapter 6-7,9

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

Reading: Section 9.3. Original paper.

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

Sep 10
Asymptotics: how to compare algorithms
Recurrences. Summation

Reading: Chapter 3. See extra notes on moodle.

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

Reading: Chapter 3. Appendix A.

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

Reading: Section 4.5.

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

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

Reading: Chapter 5.

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

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

Oct 6
Greedy algorithms: interval packing (activity scheduling)

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

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

Reading: Chapter 35.

Oct 13
Short break (no class). 		Oct 15
Huffman coding.

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

Oct 20
JabberWocky

Reading: Shor's notes.

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

Oct 29
Midterm.
Nov 3
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 5
Graph algorithms.
Topological sort. Strongly connected components.

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

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

Reading: Chapter 24-25.

Nov 12
Maximum Flow.
Ford-Fulkerson: augmenting paths. Edmonds-Karp.

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

Nov 17
NP-completeness.
How to cope with hard problems.

Reading: Chapter 34.

Nov 19
More NP-completeness.

Reading: Chapter 34.

Nov 24
Quantum algorithms. 		Nov 26
Thanksgiving break.

Dec 1
Quantum algorithms. 		Dec 3
Quantum algorithms.

Assignments

Project

  1. 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).

  2. Submit a final report (hardcopy, between 5-10 pages) that contains at minimum the following separate sections:

  3. 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).

  4. Submit any other items, if any, related to your project (code, etc) by email.

Miscellany