CSCE 629-700 Analysis of Algorithms (Online Course)
CSCE 629-700 Analysis of Algorithms (Online Course)
Instructor: Prof. Anxiao (Andrew) Jiang. Email: ajiang@cse.tamu.edu
Time and Location: Since 629-700 is an online course, it does not have a specific class meeting time. However, for the convenience of course organization, we will assume that the class has two lectures every week: one on Tuesday and the other on Thursday, throughout the Spring 2025 Semester.
TA: 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.
1/14/2025 (Tuesday): Dynamic Programming. (Lecture videos: Part 1 of 4) (Read Chapter 14 of Textbook.)
1/16/2025 (Thursday): Dynamic Programming. (Lecture videos: Part 2 of 4) (Read Chapter 14 of Textbook.)
1/21/2025 (Tuesday): Dynamic Programming. (Lecture videos: Part 2 of 4) (Read Chapter 14 of Textbook.)
1/23/2025 (Thursday): Dynamic Programming. (Lecture videos: Part 3 of 4) (Read Chapter 14 of Textbook.) Dynamic Programming. (Lecture videos: Part 4 of 4) (Read Chapter 14 of Textbook.)
1/28/2025 (Tuesday): Greedy Algorithm. (Lecture videos: Part 1 of 2) (Read Chapter 15 of Textbook.)
1/30/2025 (Thursday): Greedy Algorithm. (Lecture videos: Part 2 of 2) (Read Chapter 15 of Textbook.)
2/4/2025 (Tuesday): Amortized Analysis. (Lecture video: Part 1 of 1) (Read Chapter 16 of Textbook.)
2/6/2025 (Thursday): Linear Programming. (Lecture videos: Part 1 of 4) (Read Chapter 29 of Textbook.)
2/11/2025 (Tuesday): Linear Programming. (Lecture videos: Part 2 of 4) (Read Chapter 29 of Textbook.)
2/13/2025 (Thursday): Linear Programming. (Lecture videos: Part 2 of 4) (Read Chapter 29 of Textbook.)
2/18/2025 (Tuesday): Linear Programming. (Lecture videos: Part 3 of 4) (Read Chapter 29 of Textbook.) Linear Programming. (Lecture videos: Part 4 of 4) (Read Chapter 29 of Textbook.)
2/20/2025 (Thursday): Elementary Graph Algorithms. (Lecture videos: Part 1 of 5, Part 2 of 5) (Read Chapter 20 of Textbook.)
2/25/2025 (Tuesday): Elementary Graph Algorithms. (Lecture videos: Part 3 of 5, Part 4 of 5) (Read Chapter 20 of Textbook.)
2/27/2025 (Thursday): Elementary Graph Algorithms. (Lecture videos: Part 5 of 5) (Read Chapter 20 of Textbook.) Minimum Spanning Tree. (Lecture video: Part 1 of 1) (Read Chapter 21 of Textbook.)
3/4/2025 (Tuesday): Minimum Spanning Tree. (Lecture video: Part 1 of 1) (Read Chapter 21 of Textbook.) Single Source Shortest Paths. (Lecture video: Part 1 of 1) (Read Chapter 22 of Textbook.)
3/6/2025 (Thursday): Single Source Shortest Paths. (Lecture video: Part 1 of 1) (Read Chapter 22 of Textbook.) NP Completeness slides 1 of 2, slides 2 of 2. (Lecture videos: Part 1 of 6) (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 slides 1 of 2, slides 2 of 2. (Lecture videos: Part 1 of 6) (Read Chapter 34 of Textbook.)
3/20/2025 (Thursday): NP Completeness slides 1 of 2, slides 2 of 2. (Lecture videos: Part 2 of 6) (Read Chapter 34 of Textbook.)
3/25/2025 (Tuesday): NP Completeness slides 1 of 2, slides 2 of 2. (Lecture videos: Part 3 of 6, Part 4 of 6) (Read Chapter 34 of Textbook.)
3/27/2025 (Thursday): NP Completeness slides 1 of 2, slides 2 of 2. (Lecture videos: Part 5 of 6) (Read Chapter 34 of Textbook.)
4/1/2025 (Tuesday): (Lecture videos: Part 6 of 6) (Read Chapter 34 of Textbook.)
4/3/2025 (Thursday): Approximation Algorithms. (Lecture videos: Part 1 of 6, Part 2 of 6) (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. (Lecture videos: Part 3 of 6) (Read Chapter 35 of Textbook.)
4/15/2025 (Tuesday): Approximation Algorithms. (Lecture videos: Part 4 of 6, Part 5 of 6) (Read Chapter 35 of Textbook.)
4/17/2025 (Thursday): Approximation Algorithms. (Lecture videos: Part 6 of 6) (Read Chapter 35 of Textbook.) Maximum Flow. (Lecture videos: Part 1 of 2) (Read Chapter 24 of Textbook.)
4/22/2025 (Tuesday): Maximum Flow. (Lecture videos: Part 2 of 2) (Read Chapter 24 of Textbook.)
4/24/2025 (Thursday): Online Algorithms. (Lecture videos: Part 1 of 2) Online Algorithms. (Lecture videos: Part 2 of 2) (Read Chapter 27 of Textbook.)
4/29/2025 (Tuesday): Redefined day (as Friday). No class.
All related lectures:
1) Lecture 1: Dynamic Programming. (Lecture videos: Part 1 of 4, Part 2 of 4, Part 3 of 4, Part 4 of 4) (Read Chapter 14 of Textbook.)
2) Lecture 2: Greedy Algorithm. (Lecture videos: Part 1 of 2, Part 2 of 2)
3) Lecture 3: Amortized Analysis. (Lecture video: Part 1 of 1)
4) Lecture 4: Online Algorithms. (Lecture videos: Part 1 of 2, Part 2 of 2)
5) Lecture 5: Elementary Graph Algorithms. (Lecture videos: Part 1 of 5, Part 2 of 5, Part 3 of 5, Part 4 of 5, Part 5 of 5)
6) Lecture 6: Minimum Spanning Tree. (Lecture video: Part 1 of 1)
7) Lecture 7: Single Source Shortest Paths. (Lecture video: Part 1 of 1)
8) Lecture 8: NP Completeness slides 1 of 2, slides 2 of 2. (Lecture videos: Part 1 of 6, Part 2 of 6, Part 3 of 6, Part 4 of 6, Part 5 of 6, Part 6 of 6)
9) Lecture 9: Approximation Algorithms. (Lecture videos: Part 1 of 6, Part 2 of 6, Part 3 of 6, Part 4 of 6, Part 5 of 6, Part 6 of 6)
10) Lecture 10: Maximum Flow. (Lecture videos: Part 1 of 2, Part 2 of 2)
11) Lecture 11: Matchings in Bipartite Graphs. (Lecture videos: Part 1 of 5, Part 2 of 5, Part 3 of 5, Part 4 of 5, Part 5 of 5)
12) Lecture 12: Linear Programming. (Lecture videos: Part 1 of 4, Part 2 of 4, Part 3 of 4, Part 4 of 4)
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-700 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-700 Spring 2025 Project 2 + {YOUR NAME} + {YOUR UIN}".)
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