COMP 355
Advanced Algorithms
(CRN 20515, Fall 2019)


  • Office hours on Tuesday, Sept. 10th are cancelled. Please email me with questions, or to schedule a meeting later in the week.
  • The first lecture will be held on August 21, 2019.

    Course Description

    This course is an in-depth study of the design and analysis of advanced algorithms, including the performance tradeoffs and resources required by various algorithmic implementations. Major classes of computational problems will be identified and explored. Advanced data structures and approximation heuristics are introduced as required for solution design. Topics will include the Master Theorem, dynamic programming, divide-and-conquer and greedy algorithms.

    The syllabus for this course can be found at

    Book, Course Information, and Prerequisites

    Algorithms Book

    Textbook: Required: Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
    (Optional) Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2009.
    Location: Briggs 119
    Time: MWF 2-2:50PM
    Prerequisite: COMP 172 and COMP 241

    Course Instructor

    Instructor: Catie Welsh
    Office: Briggs 208
    Email: (please include “CS 355" somewhere in the subject)
    Office Hours: Tues/Thurs 10-11:30am, or by appointment - Briggs 208


    This is a tentative schedule and subject to change as needed.

    Date Lecture Topic(s) Recommended Reading Homework
    W-August 21 Introduction/Course Overview pdf Chapter 1 First-Day Survey due 8/23
    F-August 23 Stable Matching Algorithm Section 1.1 Homework 1
    M-August 26 Analyzing Algorithms pdf Sections 2.1, 2.3-2.4
    W-August 28 Asymptotic Forms pdf Section 2.2
    F-August 30 Master Theorem pdf CLRS Chapter 4 Homework 2
    M-September 2 Holiday- No Class
    W-September 4 Sorting and Selection pdf
    F-September 6 Greedy Algorithms for Scheduling pdf Ch. 4 Intro, Sections 4.1-4.2 (KT) Homework 3
    M-September 9 More on Greedy Algorithms
    Notes from Dr. Sanders
    Section 4.8
    W-September 11 Minimizing Lateness & Huffman Encoding pdf Section 4.8
    F-September 13 Graphs: Definitions, Representations, and Traversals Chapter 3 Homework 4
    M-September 16 Graphs: Topological Sort pdf Section 4.5
    W-September 18 Minimum Spanning Trees pdf Section 4.5
    F-September 20 Dijkstra's Algorithm for Shortest Paths pdf Section 4.4
    M-September 23 Midterm Review
    Practice Problems
    W-September 25 Midterm 1
    F-September 27 Divide-and-Conquer: Inversion Counting pdf Section 5.1-5.3 Homework 5
    M-September 30 Divide-and-Conquer: Closest Pairs pdf Section 5.4
    W-October 2 Divide-and-Conquer: Selection pdf
    F-October 4 Intro to Dynamic Programming Section 6 intro, 6.1-6.2 Homework 6
    M-October 7 Dynamic Programming: Knapsack & LCS pdf Section 6.4
    W-October 9 Dynamic Programming: Finish LCS & Edit Distance/Sequence Alignment pdf Section 6.6-6.7
    F-October 11 Space Efficient Sequence Alignment pdf
    Dynamic Programming Practice
    Homework 7
    M-October 14 Fall Break - No Class
    W- October 16 Bellman-Ford Algorithm for Shortest Paths pdf Section 6.8/CLRS Section 25.2
    F-October 18 All-Pairs Shortest Paths & Intro to Network Flows pdf Section 7.1-7.3
    M-October 21 More on Network Flows pdf Section 7.5-7.6 Homework 8
    W-October 23 Extensions to Network Flow pdf
    Network Flow Practice
    Section 7.7-7.12
    F-October 25 No Class Practice Problems
    M-October 28 Midterm Review
    W-October 30 Midterm 2
    F-November 1 NP-Completeness: Definitions pdf Chapter 8 intro Homework 9
    M-November 4 NP-Completeness: Reductions pdf Chapter 8 (KT)
    34.2-34.3 (CLRS)
    W-November 6 Cook's Theorem, 3SAT, Independent Set pdf Ch. 8 (KT)
    34.4-34.5 (CLRS)
    F-November 8 Clique, Vertex Cover, and Independent Set pdf Ch. 8 (KT)
    34.5 (CLRS)
    Homework 10
    M-November 11 Dominating Set pdf Ch. 8 (KT)
    34.5 (CLRS)
    W-November 13 NP-Complete Practice Problems
    F-November 15 Approximation Algorithms: VC & TSP pdf Chapter 11 (KT) Homework 11
    M-November 18 Approximation Algorithms: Set Cover and the Greedy Heuristic pdf Chapter 11 (KT)
    35.3 (CLRS)
    W-November 20 Subset Sum pdf Section 6.4 & 8.8 (KT)
    Section 35.5 (CLRS)
    F-November 22 Subset Sum Approximation pdf Section 6.4 & 8.8 (KT)
    Section 35.5 (CLRS)
    M-November 25 Practice Problems
    W-November 27 Holiday- No Class
    F-November 29 Holiday- No Class
    M-December 2 Practice Problems
    W-December 4 Wrap-Up/Evals
    Tues-December 10 Final Exam,Time: 5:30-8pm

    *Special thanks to Dave Mount for the use of his excellent notes and class materials.