CSCE 411/629  Design and Analysis of Algorithms

Instructor: Prof. Anxiao (Andrew) Jiang. Email: ajiang@cse.tamu.edu  

Time and Location:  7/3/2024 to 8/7/2024, Monday through Friday (summer 2024), online

TA: Shivam Sharma, email: shivam@tamu.edu 

Office Hours:

Dr. Jiang's office hour: 11:00--11:30am on Tuesdays and Fridays, via zoom https://us04web.zoom.us/j/77071104472?pwd=haVa6MqqVQFYRgD9mXxQZAUGcJTTBq.1  (Meeting ID: 770 7110 4472, Passcode: 2VwU5M)   

TA's office hours: 4-5pm on Mondays, Wednesdays and Thursdays, via zoom https://tamu.zoom.us/my/shivamtamu (Annoucement: the office hour on Wednesday 7/17 will be 7-8pm instead of 4-5pm)

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 min-projects. Homework: 60%. Mini-projects: 40%.

Submission Policy: An electronic copy of each homework or mini-project (which should be typed, not hand-written and then scanned) should be submitted in https://canvas.tamu.edu. No late homework/project submission will be accepted.

By default, all work is solo; no collaboration allowed unless stated otherwise. Searching for solutions to homework/project problems from external resources (e.g., search online) is strictly forbidden. 

Lecture Videos

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. (Slides)


Lecture 2 Video (Dynamic Programming, Matrix Chain Multiplication)

This lecture is on Dynamic Programming, where we study the Matrix Chain Multiplication Problem. (Slides)

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 (Dynamic Programming, Longest Common Subsequence)  

This lecture is on Dynamic Programming, where we study the Longest Common Subsequence Problem. (Slides)


Lecture 4 Video (Greedy Algorithm, Activity Selection)

This lecture introduces Greedy Algorithms, and uses the Activity Selection Problem as an example. (Slides)


Lecture 5 Video (Greedy Algorithm, Huffman Codes)

This lecture studies Greedy Algorithms, with the design of Huffman Codes as an example. (Slides)


Lecture 6 Video (Amortized Analysis, Aggregate Analysis, Accounting Method)

This lecture introduces techniques of amortized analysis, including aggregate analysis and the accounting method, for analyzing time complexity. (Slides)


Lecture 7 Video (Amortized Analysis, Potential Method) 

This lecture introduces the "Potential Method" for amortized analysis. (Slides) 


Lecture 8 Video (Online Algorithms, Elevator or Stairs)

This lecture introduces online algorithms, where we study the "Elevator or Stairs" problem. (Slides)  


Lecture 9 Video (Online Algorithms, Maintaining a Search List)

This lecture introduces online algorithms, where we study the "Maintaining a Search List" problem. (Slides)  


Lecture 10 Video (Representation of Graphs, BFS)

This lecture studies how to represent a graph, and the BFS (Breadth First Search) Algorithm. (Slides)


Lecture 11 Video (DFS)

This lecture introduces DFS (Depth First Search). (Slides) 


Lecture 12 Video (Topological Sort)

This lecture introduces the "Topological Sort Problem" for directed acyclic graphs. The problem is solved using DFS. (Slides)


Lecture 13 (Strongly Connected Components)

This lecture introduces the "Strongly Connected Components" problem. It is solved using DFS. (Slides)  


Lecture 14 Video (MST)

This lecture studies the Minimum Spanning Tree (MST) problem. (Slides) 


Lecture 15 Video (Single Source Shortest Paths) 

This lecture introduces the single source shortest path problem for directed graphs. (Slides)


Lecture 16 Video (NP Completeness: Part 1)

This lecture introduces basic concepts for the study of NP-completeness. (Slides)   


Lecture 17 Video (NP Completeness: Part 2)

This lecture defines NP-completeness and introduces related concepts. (Slides)


Lecture 18 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. (Slides)  

  

Lecture 19 Video (NP Completeness: Part 4)

This lecture shows how to prove the Hamiltonian Cycle Problem is NP-complete. (Slides) 


Lecture 20 Video (NP Completeness: Part 5)

This lecture studies how to prove the NP-completeness of two problems: the traveling salesman problem and the subset sum problem. (Slides)  


Lecture 21 Video (Approximation Algorithms: Part 1)

This lecture introduces approximation algorithms for the Vertex Cover Problem and the Traveling Salesman Problem (TSP). (Slides)  


Lecture 22 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. (Slides)  

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 23 Video (Approximation Algorithms: Part 3)

This lecture studies an approxmation algorithm for the Set Covering Problem. (Slides)  


Lecture 24 Video (Approximation Algorithms: Part 4)

This lecture studies an approximation algorithm for the Subset Sum Problem, which is an FPTAS. (Slides)  


Lecture 25 Video (Maximum Flow: Part 1)

This lecture studies the maximum flow problem, and presents the Ford-Fulkerson method. (Slides)  


Lecture 26 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. (Slides)   


Lecture 27 Video (Maximum Bipartite Matching)

This lecture studies the Maximum Bipartite Matching Problem, which is solved using the Hopcroft-Karp Algorithm. (Slides)   


Lecture 28 Video (Hungarian Algorithm for Assignment Problem)

This lecture studies a bipartite matching problem called the "Assignment Problem", which is solved using the Hungarian Algorithm. (Slides)  


Lecture 29 Video (Linear Programming: Part 1)

This lecture introduces linear programming and its basic concepts. (Slides) 


Lecture 30 Video (Linear Programming: Part 2)

This lecture introduces the SIMPLEX algorithm. (Slides)


Lecture 31 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. (Slides)


Lecture 32 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. (Slides)

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.


Homework and Projects:

Submission Item One (Algorithm Report) and Submission Item Two (Program): due 11:59pm (Central Time) on Monday 7/22/2024 in Canvas.

Submission Item Three (Output of Your Program on Test Instances): due 11:59pm (Central Time) on Wednesday 7/24/2024 to the Project Email Address: csce411629@gmail.com. Remember that you need to submit three files in Python: small_solutions, medium_solutions, large_solutions, which are solutions to "test_set_small_instances", "test_set_medium_instances" and "test_set_large_instances" posted below. (Please use pickle.dump(yourSolutions, open(filePath, "wb")) to save your three files, and email the three files to the above email address.)  

Note: all three items should be submitted on time. If ANY of the three items is not submitted on time, the whole project will receive 0 point. And since enough time (multiple weeks) are given to work on the project, no excuse for late submission will be accepted. (Students should try to submit the project well ahead of the deadline in case anything happens that may prevent them from catching the deadline.)

Files to download: (1) examples_of_instances, examples_of_solutions;    (2) examples_of_small_instances, examples_of_medium_instances, examples_of_large_instances;    (3) test_set_small_instances, test_set_medium_instances, test_set_large_instances (to be posted on Tuesday 7/23/2024).

Submission Item One (Algorithm Report) and Submission Item Two (Program): due 11:59pm (Central Time) on Wednesday 7/31/2024 in Canvas.

Submission Item Three (Output of Your Program on Test Instances): due 11:59pm (Central Time) on Friday 8/2/2024 to the Project Email Address: csce411629@gmail.com. Remember that you need to submit three files in Python: small_solutions, medium_solutions, large_solutions, which are solutions to the small test set, medium test set and large test set posted below. (Please use pickle.dump(yourSolutions, open(filePath, "wb")) to save your three files, and email the three files to the above email address.)  

Note: all three items should be submitted on time. If ANY of the three items is not submitted on time, the whole project will receive 0 point.

Files to download: (1) Examples_of_AdjLists_of_Trees, Examples_of_k_values, Examples_of_labelling, (2) Small_Examples_of_AdjLists_of_Trees and Small_Examples_of_k_values (as small example set), Medium_Examples_of_AdjLists_of_Trees and Medium_Examples_of_k_values (as medium example set), Large_Examples_of_AdjLists_of_Trees and Large_Examples_of_k_values (as large example set), (3) Test_Set_Small_AdjLists_of_Trees and Test_Set_Small_of_k_values (as small test set), Test_Set_Medium_AdjLists_of_Trees and Test_Set_Medium_of_k_values (as medium test set), Test_Set_Large_AdjLists_of_Trees and Test_Set_Large_of_k_values (as large test set), to be posted on Thursday 8/1/2024.

Lecture schedule: 

7/3/2024 (Wednesday): Dynamic programming. (Watch video of Lecture 1, with slides. Read Chapter 14 of textbook.)    

7/4/2024 (Thursday): Holiday, no class.   

7/5/2024 (Friday):  Dynamic programming. (Watch video of Lecture 2, with slides. Read Chapter 14 of textbook.)   

7/8/2024 (Monday):  Greedy algorithms. (Watch video of Lecture 4 , with slides.  Read Chapter 15 of textbook.)   

7/9/2024 (Tuesday): Greedy algorithms. (Watch video of Lecture 5, with slides.  Read Chapter 15 of textbook.)   

7/10/2024 (Wednesday):  Amortized analysis. (Watch video of Lecture 6, with slides. Read Chapter 16 of textbook.)  

7/11/2024 (Thursday): Elementary graph algorithms. (Watch video of Lecture 10, with slides. Read Chapter 20 of textbook.)   

7/12/2024 (Friday):  Elementary graph algorithms. (Watch video of Lecture 11, with slides. Read Chapter 20 of textbook.)  

7/15/2024 (Monday):  Elementary graph algorithms. (Watch video of Lecture 12, with slides. Read Chapter 20 of textbook.)  

7/16/2024 (Tuesday): Minimum Spanning Tree. (Watch video of Lecture 14, with slides. Read Chapters 21 of textbook.)   

7/17/2024 (Wednesday):  Single-Source Shortest Paths. (Watch video of Lecture 15, with slides.  Read Chapter 22 of textbook.)    

7/18/2024 (Thursday): Single-Source Shortest Paths. (Watch video of Lecture 15, with slides.  Read Chapter 22 of textbook.)    

7/19/2024 (Friday): NP-completeness. (Watch video of Lecture 16, with slides. Read Chapter 34 of textbook.)    

7/22/2024 (Monday): NP-completeness. (Watch video of Lecture 17, with slides. Read Chapter 34 of textbook.)   

7/23/2024 (Tuesday): NP-completeness. (Watch video of Lecture 18, with slides. Read Chapter 34 of textbook.) 

7/24/2024 (Wednesday): NP-completeness. (Watch video of Lecture 20, with slides. Read Chapter 34 of textbook.)  

7/25/2024 (Thursday): Approximation Algorithms. (Watch video of Lecture 21, with slides. Read Chapter 35 of textbook.)    

7/26/2024 (Friday): Approximation Algorithms. (Watch video of Lecture 22, with slides. Read Chapter 35 of textbook.)   

7/29/2024 (Monday):  Approximation Algorithms. (Watch video of Lecture 22, with slides. Read Chapter 35 of textbook.)   

7/30/2024 (Tuesday):  Maximum Flow. (Watch video of Lecture 25, with slides. Read Chapter 24 of textbook.)    

7/31/2024 (Wednesday): Maximum Flow. (Watch video of Lecture 26, with slides. Read Chapter 24 of textbook.)      

8/1/2024 (Thursday):  Linear Programming. (Watch video of Lecture 29, with slides. Read Chapter 29 of textbook.)   

8/2/2024 (Friday): Linear Programming. (Watch video of Lecture 30, with slides. Read Chapter 29 of textbook.)       

8/5/2024 (Monday): Linear Programming. (Watch video of Lecture 31, with slides. Read Chapter 29 of textbook.)    

8/6/2024 (Tuesday):  Linear Programming. (Watch video  of Lecture 32, with slides.  Read Chapter 29 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