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 |
Textbook
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 |