| 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 |
Textbook
T. Cormen, C. Leiserson, R. Rivest, and C. Stein:
Introduction to Algorithms, 4th ed., The MIT Press, 2009.
Supplementary Materials
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 |
| April 4 | Finding an augmenting path | Lecture #30 | Section 25.1 | Homework #6 posted |
| April 7 | Maximum matching in bipartite graphs | Lecture #31 | Section 25.1 | |
| April 9 | Randomized algorithms | Lecture #32 | Section 5.3 | |
| April 11 | NP-completeness theory | Lecture #33 | Section 34.1 | |
| April 14 | P and NP | Lecture #34 | Section 34.1 | Solutions to Homework #6 posted |
| April 16 | Polynomial-time reduction and Cook Theorem | Lecture #35 | Section 34.2 | Homework #7 posted |
| April 21 | NP-hardness and NP-completeness | Lecture #36 | Section 34.3 | |
| April 23 | Proving NP-completeness | Lecture #37 | Section 34.4 | |
| April 25 | Subset-Sum and Partition | Lecture #38 | Section 34.4 | Homework #7 is due next Monday |
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 |
| Assignment #6 | April 11 | Solutions |
| Assignment #7 | April 28 |