 |
COMP 355 Advanced Algorithms (CRN 20515, Fall 2019) |
Announcements
Course Description
This course is an in-depth study of the design and analysis of advanced algorithms, including the performance tradeoffs and resources required by various algorithmic implementations. Major classes of computational problems will be identified and explored. Advanced data structures and approximation heuristics are introduced as required for solution design. Topics will include the Master Theorem, dynamic programming, divide-and-conquer and greedy algorithms.
The syllabus for this course can be found at http://cs.rhodes.edu/welshc/CS355/F19/syllabus.pdf.
Book, Course Information, and Prerequisites
| Textbook: | Required: Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
(Optional) Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2009. |
| Location: | Briggs 119 |
| Time: | MWF 2-2:50PM |
| URL: | http://cs.rhodes.edu/welshc/CS355/F19/ |
| Prerequisite: | COMP 172 and COMP 241 |
Course Instructor
| Instructor: | Catie Welsh |
| Office: | Briggs 208 |
| Email: | welshc@rhodes.edu (please include “CS 355" somewhere in the subject) |
| Office Hours: | Tues/Thurs 10-11:30am, or by appointment - Briggs 208 |
Schedule
This is a tentative schedule and subject to change as needed.
| Date | Lecture Topic(s) | Recommended Reading | Homework |
| W-August 21 | Introduction/Course Overview pdf | Chapter 1 | First-Day Survey due 8/23 |
| F-August 23 | Stable Matching Algorithm | Section 1.1 | Homework 1 |
| M-August 26 | Analyzing Algorithms pdf | Sections 2.1, 2.3-2.4 | |
| W-August 28 | Asymptotic Forms pdf | Section 2.2 | |
| F-August 30 | Master Theorem pdf | CLRS Chapter 4 | Homework 2 hw2input.txt |
| M-September 2 | Holiday- No Class | ||
| W-September 4 | Sorting and Selection pdf | ||
| F-September 6 | Greedy Algorithms for Scheduling pdf | Ch. 4 Intro, Sections 4.1-4.2 (KT) | Homework 3 PS3_input.txt |
| M-September 9 | More on Greedy Algorithms Notes from Dr. Sanders |
Section 4.8 | |
| W-September 11 | Minimizing Lateness & Huffman Encoding pdf | Section 4.8 | |
| F-September 13 | Graphs: Definitions, Representations, and Traversals | Chapter 3 | Homework 4 |
| M-September 16 | Graphs: Topological Sort pdf | Section 4.5 | |
| W-September 18 | Minimum Spanning Trees pdf | Section 4.5 | |
| F-September 20 | Dijkstra's Algorithm for Shortest Paths pdf | Section 4.4 | |
| M-September 23 | Midterm Review Practice Problems |
||
| W-September 25 | Midterm 1 | ||
| F-September 27 | Divide-and-Conquer: Inversion Counting pdf | Section 5.1-5.3 | Homework 5 |
| M-September 30 | Divide-and-Conquer: Closest Pairs pdf | Section 5.4 | |
| W-October 2 | Divide-and-Conquer: Selection pdf | ||
| F-October 4 | Intro to Dynamic Programming | Section 6 intro, 6.1-6.2 | Homework 6 |
| M-October 7 | Dynamic Programming: Knapsack & LCS pdf | Section 6.4 | |
| W-October 9 | Dynamic Programming: Finish LCS & Edit Distance/Sequence Alignment pdf | Section 6.6-6.7 | |
| F-October 11 | Space Efficient Sequence Alignment pdf Dynamic Programming Practice |
Homework 7 | |
| M-October 14 | Fall Break - No Class | ||
| W- October 16 | Bellman-Ford Algorithm for Shortest Paths pdf | Section 6.8/CLRS Section 25.2 | |
| F-October 18 | All-Pairs Shortest Paths & Intro to Network Flows pdf | Section 7.1-7.3 | |
| M-October 21 | More on Network Flows pdf | Section 7.5-7.6 | Homework 8 |
| W-October 23 | Extensions to Network Flow pdf Network Flow Practice |
Section 7.7-7.12 | |
| F-October 25 | No Class Practice Problems | ||
| M-October 28 | Midterm Review | ||
| W-October 30 | Midterm 2 | ||
| F-November 1 | NP-Completeness: Definitions pdf | Chapter 8 intro | Homework 9 |
| M-November 4 | NP-Completeness: Reductions pdf | Chapter 8 (KT) 34.2-34.3 (CLRS) |
|
| W-November 6 | Cook's Theorem, 3SAT, Independent Set pdf | Ch. 8 (KT) 34.4-34.5 (CLRS) |
|
| F-November 8 | Clique, Vertex Cover, and Independent Set pdf | Ch. 8 (KT) 34.5 (CLRS) |
Homework 10 |
| M-November 11 | Dominating Set pdf | Ch. 8 (KT) 34.5 (CLRS) |
|
| W-November 13 | NP-Complete Practice Problems | ||
| F-November 15 | Approximation Algorithms: VC & TSP pdf | Chapter 11 (KT) | Homework 11 |
| M-November 18 | Approximation Algorithms: Set Cover and the Greedy Heuristic pdf | Chapter 11 (KT) 35.3 (CLRS) |
|
| W-November 20 | Subset Sum pdf | Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) |
|
| F-November 22 | Subset Sum Approximation pdf | Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) |
|
| M-November 25 | Practice Problems | ||
| W-November 27 | Holiday- No Class | ||
| F-November 29 | Holiday- No Class | ||
| M-December 2 | Practice Problems | ||
| W-December 4 | Wrap-Up/Evals | ||
| Tues-December 10 | Final Exam,Time: 5:30-8pm | ||
*Special thanks to Dave Mount for the use of his excellent notes and class materials.