| Office: | HRBB 338C | ||
| Phone: | (979) 845-4259 | ||
| Email: | chen@cse.tamu.edu | ||
| Web: | https://people.engr.tamu.edu/j-chen3/ | ||
| Office hours: | NWF 12:50 pm-1:50 pm or by appointment. |
Senior Grader: Aditya Biradavolu
| Phone: | (513) 488-4486 | ||
| Email: | aditya95913@tamu.edu | ||
| Office hours: | TR 3:30 pm -- 4:30 pm |
Course Syllabus (revised, March 1)
Textbook
T. Cormen, C. Leiserson, R. Rivest, and C. Stein:
Introduction to Algorithms, 3rd ed., The MIT Press, 2009.
Supplementary Materials
Schedule
(Lecture videos are available in Zoom cloud)
| Date | Topics | Slides | Book Sections | Quiz and Assignments |
|---|---|---|---|---|
| Jan. 20 | Introduction | | ||
| Jan. 22 | Introduction | Slides | Chapters 1-3 | |
| Jan. 25 | O-notation and recursion | Slides | Sections 4.3-4.4 | Course video |
| Jan. 27 | Divide and conquer | Slides | Chapter 4 | |
| Jan. 29 | HeapSort | Slides | Chapter 6 | Homework #1 handed out, quiz #1 given |
| Feb. 1 | HeapSort II | Slides | Chapter 6 | |
| Feb. 3 | Lower bound for sorting | Slides | Section 8.1 | |
| Feb. 5 | Lower bounds (continued) | Slides | Section 8.1 | |
| Feb. 8 | Sorting in linear time | Slides | Section 8.2 | |
| Feb. 10 | Counting sort | Slides | Section 8.3 | Homework #1 collected, quiz #2 given |
| Feb. 12 | RadixSort | Slides | Section 8.3 | Hoemwork #2 handed out |
| Feb. 15-19 | classes were cancelled. | |||
| Feb. 22 | Dynamic programming | Slides | Section 15.4 | |
| Feb. 24 | Graph algorithms | Slides | Section 22.1 | |
| Feb. 26 | Midterm exam #1 | Homework #2 collected | ||
| March 1 | Breadth-first search | Slides | Section 22.2 | Hoemwork #3 handed out, quiz #3 given |
| March 3 | Depth-first search | Slides | Section 22.3 | Quiz #4 given |
| March 5 | Applications of BFS and DFS | Slides | Sections 22.2-22.3 | |
| March 8 | DFS on directed graphs | Slides | Sections 22.4 | |
| March 10 | Strongly connected components | Slides | Sections 22.5 | Homework #3 collected |
| March 12 | Strongly connected components II | Slides | Sections 22.5 | Homework #4 handed out, quiz #5 given, |
| March 15 | The shortest path problem | Slides | Sections 24.3 | |
| March 17 | Dijkstra: implementation and correctness | Slides | Sections 24.3 | |
| March 18 | Shortest path: further discussions | Slides | Sections 24.2 | Quiz #6 given |
| March 22 | The Bellman-Ford algorithm | Slides | Sections 24.1 | Homework #4 collected |
| March 24 | All-pairs shortest paths | Slides | Section 25.2 | Homework #5 handed out |
| March 26 | Midterm exam #2 | |||
| March 29 | Mimimum spanning tree | Slides | Chapter 23 | |
| March 31 | Kruskal's algorithm | Slides | Chapter 23 | |
| April 5 | Analysis and correctness of Kruskal | Slides | Chapter 23 | Homework #5 collected |
| April 7 | Graph Matching | Slides | Section 26.3 | |
| April 9 | Algorithm for bipartite matching | Slides | Section 26.3 | Homework #6 handed out, Quiz #7 given |
| April 12 | Matching algorithm: summary | Slides | Section 26.3 | |
| April 14 | Problems in NP | Slides | Sections 34.1-34.2 | Quiz #8 given |
| April 16 | Poly-time reductions | Slides | Section 34.3 | Homework #6 collected |
| April 19 | NP-hardness and NP-completeness | Slides | Section 34.4 | Homework #7 handed out |
| April 21 | Independent-Set is NP-complete | Slides | Section 34.5 | |
| April 23 | Vertex-Cover and Partition | Slides | Section 34.5 | |
| April 26 | Dealing with NP-hardness | Slides | Section 35.1 | |
| April 28 | Computability theory | Slides | Homework #7 collected |
Assignments
(Assignments are due on the designated due dates at the beginning of the class)
| Assignment | Due Date | Solution |
|---|---|---|
| Assignment #1 | Feb. 10 | Solutions |
| Assignment #2 | Feb. 26 | Solutions |
| Midterm Exam #1 | Feb. 26 | |
| Assignment #3 | March 10 | Solutions |
| Assignment #4 | March 22 | Solutions |
| Assignment #5 | April 5 | Solutions |
| Midterm Exam #2 | March 26 | |
| Assignment #6 | April 16 | Solutions |
| Assignment #7 | April 28 | Solutions |
| Final Exam #1 | May 5 |