 |
COMP 355 Advanced Algorithms (CRN 18286, Fall 2017) |
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/COMP355_F17/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/COMP355_F17/ |
| 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: | MW 3-4pm, Thurs 10am-12pm, 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 23 | Introduction/Course Overview pdf | Chapter 1 | |
| F-August 25 | Stable Matching Algorithm | Section 1.1 | |
| M-August 28 | Analyzing Algorithms pdf | Sections 2.1, 2.3-2.4 | |
| W-August 30 | Asymptotic Forms pdf | Section 2.2 | |
| F-September 1 | Master Theorem pdf | CLRS Chapter 4 | Homework 1 PS1_input.txt |
| M-September 4 | Holiday- No Class | ||
| W-September 6 | Sorting and Selection pdf | ||
| F-September 8 | Greedy Algorithms for Scheduling pdf | Ch. 4 Intro, Sections 4.1-4.2 (KT) | |
| M-September 11 | More on Greedy Algorithms pdf | Section 4.8 | |
| W-September 13 | Huffman Encoding pdf | Section 4.8 | Homework 2 |
| F-September 15 | Graphs: Definitions, Representations, and Traversals | Chapter 3 | |
| M-September 18 | Graphs: Topological Sort pdf | Section 4.5 | |
| W-September 20 | Minimum Spanning Trees pdf | Section 4.5 | |
| F-September 22 | Dijkstra's Algorithm for Shortest Paths pdf Practice Problems |
Section 4.4 | |
| M-September 25 | Midterm Review | ||
| W-September 27 | Midterm 1 | ||
| F-September 29 | Divide-and-Conquer: Inversion Counting pdf | Section 5.1-5.3 | |
| M-October 2 | Divide-and-Conquer: Closest Pairs pdf | Section 5.4 | Homework 3 |
| W-October 4 | Divide-and-Conquer: Selection pdf | ||
| F-October 6 | Dynamic Programming: Weighted Interval Scheduling pdf | Section 6 intro, 6.1-6.2 | |
| M-October 9 | Dynamic Programming: Knapsack & LCS pdf | Section 6.4 | |
| W-October 11 | Dynamic Programming: Manhattan Tourist Problem & Sequence Alignment pdf | Section 6.6-6.7 | |
| F-October 13 | Bellman-Ford Algorithm for Shortest Paths pdf | Section 6.8 | |
| M-October 16 | Fall Break - No Class | ||
| W- October 18 | All-Pairs Shortest Paths, Floyd-Warshall Algorithm pdf | CLRS Section 25.2 | |
| F-October 20 | Network Flows pdf | Section 7.1-7.3 | Homework 4 |
| M-October 23 | More on Network Flows pdf | Section 7.5-7.6 | |
| W-October 25 | Extensions to Network Flow pdf | Section 7.7-7.12 | |
| F-October 27 | Practice Problems | ||
| M-October 30 | Midterm Review | ||
| W-November 1 | Midterm 2 | ||
| F-November 3 | NP-Completeness: Definitions pdf | Chapter 8 intro | |
| M-November 6 | NP-Completeness: Reductions pdf | Chapter 8 (KT) 34.2-34.3 (CLRS) |
|
| W-November 8 | Cook's Theorem, 3SAT, Independent Set pdf | Ch. 8 (KT) 34.4-34.5 (CLRS) |
Homework 5 |
| F-November 10 | Clique, Vertex Cover, and Independent Set pdf | Ch. 8 (KT) 34.5 (CLRS) |
|
| M-November 13 | Dominating Set pdf | Ch. 8 (KT) 34.5 (CLRS) |
|
| W-November 15 | NP-Complete Practice Problems | ||
| F-November 17 | Approximation Algorithms: VC & TSP pdf | Chapter 11 (KT) | |
| M-November 20 | Approximation Algorithms: Set Cover and the Greedy Heuristic pdf | Chapter 11 (KT) 35.3 (CLRS) |
Homework 6 |
| W-November 22 | Holiday- No Class | ||
| F-November 24 | Holiday- No Class | ||
| M-November 27 | Subset Sum pdf | Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) |
|
| W-November 29 | Subset Sum Approximation pdf | Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) |
|
| F-December 1 | Practice Problems | ||
| M-December 4 | Practice Problems | ||
| W-December 6 | Wrap-Up/Evals | ||
| Tues-December 12 | Final Exam,Time: 5:30-8pm | ||
*Special thanks to Dave Mount for the use of his excellent notes and class materials.