CSCE-411 Design and Analysis of Algorithms (Spring 2025)

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:MW 1:30 pm--3:00 pm.

Senior Grader: William Kang
Phone:(979) 575-9987
Email:rkdvlfah1018@tamu.edu
Office hours:via phone and email, and by appointments

Course Syllabus

Textbook
T. Cormen, C. Leiserson, R. Rivest, and C. Stein: Introduction to Algorithms, 4th ed., The MIT Press, 2009.

Supplementary Materials
  • N. Malpani and J. Chen, A note on practical construction of maximum bandwidth paths, Information Processing Letters 83, pp. 175-180, (2002)
  • Course Progress
    Date Topics Lecture Notes Book Sections Announcement
    Jan. 13 Introduction Lecture #1
    Chapters 1-2
    Jan. 15 Correctness, feasibility, efficiency, improvements Lecture #2
    Chapters 1-2
    Jan. 17 Recursive algorithms Lecture #3
    Chapter 4
    Jan. 22 Review on sorting algorithms Lecture #4
    Jan. 24 Heap structures Lecture #5
    Sections 6.1-6.2 Homework #1 posted
    Jan. 27 Heapsort Lecture #6
    Sections 6.3-6.4
    Jan. 29 Lower bounds on sorting and searching Lecture #7
    Section 8.1
    Jan. 31 Linear-time sorting algorithms Lecture #8
    Section 8.2 Homework #1 is due today at 11:30 am
    Feb. 3 RadixSort Lecture #9
    Section 8.3
    Feb. 5 Dynamic programming Lecture #10
    Chapter 14 Homework #2 posted
    Feb. 7 Graph algorithms Lecture #11
    Section 20.1 Solutions to Homework #1 posted
    Feb. 10 Breadth First Search (BFS) Lecture #12
    Section 20.2 Midterm I on Friday, Feb. 14
    Feb. 12 Time complexity of BFS, Midterm I review Lecture #13
    Section 20.2
    Feb. 14 Midterm exam I Solutions to Homework #2 posted
    Feb. 17 Depth First Search (DFS) Lecture #14
    Section 20.3
    Feb. 19 Applications of DFS and BFS Lecture #15
    Sections 20.1-20.3 Homework #3 posted
    Feb. 21 Algorithms on directed graphs Lecture #16
    Section 20.4
    Feb. 24 Topological sorting Lecture #17
    Section 20.4
    Feb. 26 Strongly connected components Lecture #18
    Section 20.5
    Feb. 28 The shortest path problem Lecture #19
    Section 22.3 Homework #3 is due today at 11:30 am
    March 3 Dijkstra's algorithm Lecture #20
    Section 22.3
    March 5 Dijkstra's algorithm (further discussions) Lecture #21
    Section 22.3 Homework #4 posted
    March 7 The Bellman-Ford algorithm Lecture #22
    Section 22.1 Solutions to Homework #3 posted
    March 10-14 Spring Break
    March 17 All-pair shortest paths Lecture #23
    Sections 23.1-23.2
    March 19 Johnson's algorithm for APSP Lecture #24
    Section 23.3 Homework #5 posted
    March 21 Minimum spanning tree: Prim's algorithm Lecture #25
    Section 21.1
    March 24 Minimum spanning tree: Kruskal's algorithm Lecture #26
    Section 21.2 Solutions to Homework #4 posted
    March 26 Union, Find, and MakeSet Lecture #27
    Sections 19.1, 19.3 Midterm II on Friday, March 28
    March 28 Midterm exam II
    March 31 Further discussions on the SSSP and MST problems Lecture #28
    Section 21.2
    April 2 Graph matching Lecture #29
    Section 25.1 Solutions to Homework #5 posted

    Assignments
    (Assignments are due on the designated due dates at the beginning of the class)
    Assignment Due Date Solution
    Assignment #1 Jan. 31 Solutions
    Assignment #2 Feb. 12 Solutions
    Assignment #3 Feb. 28 Solutions
    Assignment #4 March 17 Solutions
    Assignment #5 March 28 Solutions