CSCE-629-601 Analysis of Algorithms (Fall 2022)

Instructor: Dr. Jianer Chen
Office:PETR 428
Phone:(979) 845-4259
Email:chen@cse.tamu.edu
Web: https://people.engr.tamu.edu/j-chen3/
Office hours:MWF 3:50pm - 5:00pm

Teaching Assistant: Vaibhav Bajaj
Office:EABC 107B
Phone:(979) 739-2707
Email:vaibhavbajaj@tamu.edu
Office hours:T: 2:00pm-3:00pm, TR: 4:00pm-5:00pm

Course Syllabus

Textbook

  • T. Cormen, C. Leiserson, R. Rivest, and C. Stein: Introduction to Algorithms, 3rd ed., The MIT Press, 2009.
  • M. Garey and D. Johnson: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
  • Supplementary materials to be handed out.

    Schedule
    Date Topics Lecture Notes Book Sections Announcements
    Aug. 24 Introduction Prerequisites Chapters 1-3 syllabus posted
    Aug. 26 Recursive algorithms and analysis Sections 4.3-4.5 class videos in Canvas
    Aug. 29 Sorting and searching Chapters 6-7
    Aug. 31 2-3 trees 2-3 trees Definitions Lecture notes on 2-3 trees posted
    Sept. 2 2-3 trees, and other balanced search trees Homework #1 assigned
    Sept. 5 Labor's day. No class.
    Sept. 7 Splice and split in 2-3 trees
    Sept. 9 B+ trees B+ trees
    Sept. 12 Hash functions Sections 11.1-11.2
    Sept. 14 Universal family of hash functions Hashing Section 11.3 Homework #1 is due on Friday at 3 PM
    Sept. 16 Perfect hashing, graphs Sections 11.5, 22.1 Homework #1 is due today
    Sept. 19 Depth First Search and applications Section 22.3
    Sept. 21 Breadth First Search and applications Section 22.2 Homework #2 assigned
    Sept. 23 Topological sorting BFS and DFS Section 22.4
    Sept. 26 Strongly connected components SCC Section 22.5 Midterm will be on Oct. 17.
    Sept. 28 The maximum bandwidth path problem
    Sept. 30 Dijkstra's algorithm Sections 24.2-24.3
    Oct. 3 Correctness of Dijkstra's algorithm Dijkstra's algorithm Section 24.5 Homework #3 assigned
    Oct. 5 Max-heap, Max-BW and Max spanning tree The Max-BW problem Notes on Max-BW posted
    Oct. 7 Kruskal's algorithm Chapter 23
    Oct. 10-11 Fall break. No class
    Oct. 12 Kruskal using Union and Find Kruskal's algorithm
    Oct. 14 Midterm review Midterm review
    Oct. 17 Midterm examination
    Oct. 19 Union and Find Union and Find Chapter 21
    Oct. 21 Course Project Project assignment handed out.
    Oct. 24 Union and Find, function log* n Union and Find II Homework #4 assigned
    Oct. 26 The Bellman-Ford algorithm Section 24.1
    Oct. 28 The Floyd-Warshall algorithm Chapter 25
    Oct. 31 Graph matching Graph matching
    Nov. 2 Matching in bipartite graph Section 26.3
    Nov. 4 Maximum flow, introduction Section 26.1
    Nov. 7 Maximum flow, finding all shortest paths Homework #5 assigned
    Nov. 9 Dinic algorithm Algorithms for max-flow Section 26.2 Notes on max-flow algorithms posted
    Nov. 11 Max-flow algorithms, summary Max-flow algorithms
    Nov. 14 NP-completeness theory Section 34.1 Homework #5 is due on Wednesday
    Nov. 16 Nondeterministic algorithms Lecture Notes: NPC(1) Section 34.2 Solutions to HW4 posted
    Nov. 18 The class NP, poly-time reduction Section 34.3 Homework #6 assigned
    Nov. 21 Polynomial-time reductions Sections 34.3-34.4
    Nov. 23-25 Thanksgiving holiday: no classes
    Nov. 28 Independent Set is NP-complete Lecture Notes: NPC(2) Sections 34.4
    Nov. 30 Vertex Cover, Partition, Subset-Sum Review on NPC Sections 34.5 Solutions to HW5 posted
    Dec. 2 Scheduling, Knapsack Course project is due at midnight today
    Dec. 5 Dynamic programming, branch-and-bound Sections 35.5 Homework #6 is due today
    Dec. 7 Approximation algorithms, Course review Course review Sections 35.1
    Dec. 13 Final examination (10:30 am--12:30 pm)

    Assignments
    (Assignments are due on the designated due dates at the beginning of the class)
    Assignment Due Date Solution
    Assignment #1 September 16 Solutions
    Assignment #2 September 30 Solutions
    Assignment #3 October 14 Solutions
    Course Project December 2
    Assignment #4 November 4 Solutions
    Assignment #5 November 16 Solutions
    Assignment #6 December 5 Solutions