CSCE 629-601 Analysis of Algorithms
CSCE 629-601 Analysis of Algorithms
Instructor: Prof. Anxiao (Andrew) Jiang. Email: ajiang@cse.tamu.edu
Time and Location: 1/13/2025 to 5/6/2025, 2:20-3:35pm on Tuesdays and Thursdays, in 106 EABB
TAs: Pouyan Forghani (email: pouyan.forghani@tamu.edu) and Wenjing Chen (jj9754@tamu.edu)
Grader: Anant Mehta (email: anant_mehta@tamu.edu)
Office Hours:
Dr. Jiang's office hour: 11:30am--12:00pm on Mondays, via Zoom at https://us04web.zoom.us/j/76827536251?pwd=m1GTxGUA7JrTSVwfkLP9fLTelI9dEM.1
(Meeting ID: 768 2753 6251, Passcode: 4qjnyu)
Pouyan Forghani's office hours: 11am-12pm on Tuesdays and 11am-12pm on Thursdays, via zoom at https://tamu.zoom.us/j/98251566679 . (Meeting ID: 982 5156 6679)
Wenjing Chen's office hours: 3pm-4pm on Wednesdays and 2pm-3pm on Fridays, via zoom at https://tamu.zoom.us/j/93695955910?pwd=rnFNM50BzhPsawUSlkEMXqzoblDr2z.1 (Meeting ID: 936 9595 5910, Passcode: 517278)
Textbook: Introduction to Algorithms (4th Edition), by Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein.
Thanks to the support of Texas A&M University Libraries, you can access the textbook (as an e-book, both on and off campus) for free:
Introduction to Algorithms https://search.ebscohost.com/login.aspx?direct=true&db=nlebk&AN=2932690&site=eds-live&scope=site&authtype=shib&custid=s8516548&ebv=EK&ppid=Page-__-1
Grading and Requirements:
The final grade is based on homework and project. Homework: 34%. Two projects: 33% per project (66% total).
Submission Policy: An electronic copy of each homework should be submitted in https://canvas.tamu.edu. An electronic copy of files for each project should be emailed to moore.research.education@gmail.com. No late homework/project submission will be accepted. Students should double check each submission to make sure correct files are submitted. (If wrong files are submitted, correct files to replace them can only be submitted before the deadline, not after it.)
By default, all work is solo; no collaboration allowed unless stated otherwise. Searching for solutions to homework problems from external resources (e.g., search online) is strictly forbidden.
Homework and project reports should be submitted as PDF files. (LaTeX is a great tool for creating beautiful PDF files. If you edit them using other software such as Microsft Word, please convert them to PDF files before submitting them.) For homework, we strongly encourage students to prepare it with software; but if you really need to use handwriting and then scan it, please make sure it is very clear and easy to read, because any hard-to-read part will be treated as an incorrect answer, and points will be deducted. For project reports, they are required to be prepared using software, not by handwriting.
Lecture 1 Video (Dynamic Programming, Rod Cutting Problem, Time Complexity)
This is the video of Lecture 1. It covers the basics of Dynamic Programming, studies the Rod Cutting Problem in detail as an example of dynamic programming, and gives a brief overview of Time Complexity.
Lecture 2 Video (Dynamic Programming, Matrix Chain Multiplication)
This lecture is on Dynamic Programming, where we study the Matrix Chain Multiplication Problem.
Please note: at about 48 minutes 32 seconds of the video, on the whiteboard, "k* - 1" should have been written as "k* + 1." (It was a typo.)
Lecture 3 Video (Greedy Algorithm, Activity Selection)
This lecture introduces Greedy Algorithms, and uses the Activity Selection Problem as an example.
Lecture 4 Video (Greedy Algorithm, Huffman Codes)
This lecture studies Greedy Algorithms, with the design of Huffman Codes as an example.
Lecture 5 Video (Amortized Analysis)
This lecture introduces techniques of amortized analysis, including aggregate analysis and the accounting method, for analyzing time complexity.
Lecture 6 Video (Representation of Graphs, BFS)
This lecture studies how to represent a graph, and the BFS (Breadth First Search) Algorithm.
This lecture introduces DFS (Depth First Search).
Lecture 8 Video (Topological Sort)
This lecture introduces the "Topological Sort Problem" for directed acyclic graphs. The problem is solved using DFS.
This lecture studies the Minimum Spanning Tree (MST) problem.
Lecture 10 Video (Single Source Shortest Paths)
This lecture introduces the single source shortest path problem for directed graphs.
Lecture 11 Video (Linear Programming: Part 1)
This lecture introduces linear programming and its basic concepts.
Lecture 12 Video (Linear Programming: Part 2)
This lecture introduces the SIMPLEX algorithm.
Lecture 13 Video (Linear Programming: Part 3)
This lecture reviews the SIMPLEX algorithm, proves its correctness using the duality between primal LP and dual LP, and discusses the possibility that the initial basic solution to a slack-form LP is not feasible.
Lecture 14 Video (Linear Programming: Part 4)
This lecture studies how to determine if an LP is feasible, and how to find an initial feasible basic solution.
Please note: at around 58 minutes 28 seconds of the lecture, on the board, in the question "what if x0 is a basic solution in the final slack form?", "basic solution" should be "basic variable." It was a typo.
Lecture 15 Video (NP Completeness: Part 1)
This lecture introduces basic concepts for the study of NP-completeness.
Lecture 16 Video (NP Completeness: Part 2)
This lecture defines NP-completeness and introduces related concepts.
Lecture 17 Video (NP Completeness: Part 3)
This lecture shows hows to prove a problem is NP-complete, using the Clique Problem and the Vertex Cover Problem as examples.
Lecture 18 Video (NP Completeness: Part 4)
This lecture studies how to prove the NP-completeness of two problems: the traveling salesman problem and the subset sum problem.
Lecture 19 Video (Approximation Algorithms: Part 1)
This lecture introduces approximation algorithms for the Vertex Cover Problem and the Traveling Salesman Problem (TSP).
Lecture 20 Video (Approximation Algorithms: Part 2)
This lecture studies the hardness of approximating the general traveling salesman problem (general TSP), the technique of using linear programming for approximation, and randomized algorithms.
Note: at around 19 minutes 57 seconds of the video, what was written on the board should be "G has a Hamiltonian cycle of weight |V|", not G'. It was a small typo.
Lecture 21 Video (Maximum Flow: Part 1)
This lecture studies the maximum flow problem, and presents the Ford-Fulkerson method.
Lecture 22 Video (Maximum Flow: Part 2)
This lecture proves the max-flow min-cut theorem and the correctness of the Ford-Fulkerson method, introduces the Edmonds-Karp algorithm, solves the maximum bipartite matching problem as an application of the maximum flow problem, and introduces how to formulate the maximum flow problem as a linear program.
Homework one is here. Due: 11:59pm (Central Time) on Thursday 1/30/2025 in Canvas.
Homework two is here. Due: 11:59pm (Central Time) on Thursday 2/6/2025 in Canvas.
Homework three is here. Due: 11:59pm (Central Time) on Thursday 2/20/2025 in Canvas.
Homework four is here. Due: 11:59pm (Central Time) on Tuesday 3/18/2025 in Canvas.
Homework five is here. Due: 11:59pm (Central Time) on Thursday 3/27/2025 in Canvas.
Homework six has two problems: Problem 1 and Problem 2. Due: 11:59pm (Central Time) on Thursday 4/3/2025 in Canvas.
Homework seven is here. Due: 11:59pm (Central Time) on Thursday 4/17/2025 in Canvas.
Homework eight is here. Due: 11:59pm (Central Time) on Wednesday 4/30/2025 in Canvas.
Project 1. Due: 11:59pm (Central Time) on Tuesday 4/8/2025 by email. (Please email your files to our project email address moore.research.education@gmail.com. The title of the email should be "CSCE 629-601 Spring 2025 Project 1 + {YOUR NAME} + {YOUR UIN}".)
Project 2: Same as Project 1. Students are encouraged to explore new methods to further improve the results. Due: 11:59pm (Central Time) on Monday 4/28/2025 by email. (Please email your files to our project email address moore.research.education@gmail.com. The title of the email should be "CSCE 629-601 Spring 2025 Project 2 + {YOUR NAME} + {YOUR UIN}".)
1/14/2025 (Tuesday): Dynamic programming. (Watch video of Lecture 1, with slides. Read Chapter 14 of textbook.)
1/16/2025 (Thursday): Dynamic programming. (Watch video of Lecture 2, with slides. Read Chapter 14 of textbook.)
1/21/2025 (Tuesday): Class cancelled due to weather
1/23/2025 (Thursday): Dynamic Programming. (Watch video of Lecture 3, with slides. Read Chpater 14 of textbook.)
1/28/2025 (Tuesday): Greedy algorithms. (Watch video of Lecture 4 , with slides. Read Chapter 15 of textbook.)
1/30/2025 (Thursday): Greedy algorithms. (Watch video of Lecture 5, with slides. Read Chapter 15 of textbook.)
2/4/2025 (Tuesday): Amortized analysis. (Watch video of Lecture 6, with slides. Read Chapter 16 of textbook.) Amortized analysis. (Watch video of Lecture 7, with slides. Read Chapter 16 of textbook.)
2/6/2025 (Thursday): Linear Programming. (Watch video of Lecture 29, with slides. Read Chapter 29 of textbook.)
2/11/2025 (Tuesday): Self-study.
2/13/2025 (Thursday): Linear Programming. (Watch video of Lecture 30, with slides. Read Chapter 29 of textbook.)
2/18/2025 (Tuesday): Linear Programming. (Watch video of Lecture 31, with slides. Read Chapter 29 of textbook.) Linear Programming. (Watch video of Lecture 32, with slides. Read Chapter 29 of textbook.)
2/20/2025 (Thursday): Elementary graph algorithms. (Watch video of Lecture 10, with slides. Read Chapter 20 of textbook.) Elementary graph algorithms. (Watch video of Lecture 11, with slides. Read Chapter 20 of textbook.).
2/25/2025 (Tuesday): Elementary graph algorithms. (Watch video of Lecture 12, with slides. Read Chapter 20 of textbook.).
2/27/2025 (Thursday): ELementary graph algorithms. (Watch video of Lecture 13, with slides. Read Chapter 20 of textbook.). Minimum Spanning Tree. (Watch video of Lecture 14, with slides. Read Chapters 21 of textbook.)
3/4/2025 (Tuesday): Minimum Spanning Tree. (Watch video of Lecture 14, with slides. Read Chapters 21 of textbook.) Single-Source Shortest Paths. (Watch video of Lecture 15, with slides. Read Chapter 22 of textbook.).
3/6/2025 (Thursday): Single-Source Shortest Paths. (Watch video of Lecture 15, with slides. Read Chapter 22 of textbook.). NP-completeness. (Watch video of Lecture 16, with slides. Read Chapter 34 of textbook.)
3/11/2025 (Tuesday): Spring break, no class.
3/13/2025 (Thursday): Spring break, no class.
3/18/2025 (Tuesday): NP-completeness. (Watch video of Lecture 16, with slides. Read Chapter 34 of textbook.)
3/20/2025 (Thursday): NP-completeness. (Watch video of Lecture 17, with slides. Read Chapter 34 of textbook.).
3/25/2025 (Tuesday): NP-completeness. (Watch video of Lecture 18, with slides. Read Chapter 34 of textbook.).
3/27/2025 (Thursday): NP-completeness. (Watch video of Lecture 19, with slides. Read Chapter 34 of textbook.).
4/1/2025 (Tuesday): NP-completeness. (Watch video of Lecture 20, with slides. Read Chapter 34 of textbook.)
4/3/2025 (Thursday): Approximation Algorithms. (Watch video of Lecture 21, with slides. Read Chapter 35 of textbook.).
4/8/2025 (Tuesday): Q&A Session for Project 1, via zoom at 2:20--3:35pm. (The zoom link is the same as that for Prof. Jiang's office hour on Mondays, shown at the top of this webpage.) No in-class meeting.
4/10/2025 (Thursday): Approximation Algorithms. (Watch video of Lecture 22, with slides. Read Chapter 35 of textbook.).
4/15/2025 (Tuesday): Approximation Algorithms. (Watch video of Lecture 23, with slides. Read Chapter 35 of textbook.). Approximation Algorithms. (Watch video of Lecture 24, with slides. Read Chapter 35 of textbook.).
4/17/2025 (Thursday): Maximum Flow. (Watch video of Lecture 25, with slides. Read Chapter 24 of textbook.).
4/22/2025 (Tuesday): Maximum Flow. (Watch video of Lecture 26, with slides. Read Chapter 24 of textbook.)
4/24/2025 (Thursday): Online Algorithms. (Watch video of Lecture 8, with slides. Read Chapter 27 of textbook.). Online Algorithms. (Watch video of Lecture 9, with slides. Read Chapter 27 of textbook.)
4/29/2025 (Tuesday): Redefined day (as Friday). No class.
Related Lectures: Matchings in Bipartite Graphs. (Watch video of Lecture 27, with slides. Read Chapter 25 of textbook.). Matchings in Bipartite Graphs. (Watch video of Lecture 28, with slides. Read Chapter 25 of textbook.).
Statement: The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, currently located in the Disability Services building at the Student Services at White Creek complex on west campus or call 979-845-1637. For additional information, visit http://disability.tamu.edu.
“An Aggie does not lie, cheat or steal, or to tolerate those who do.” See http://aggiehonor.tamu.edu