CS4102 Algorithms - Spring 2020

Course Description: Introduces the analysis of algorithms and the effects of data structures on them. Algorithms selected from areas such as sorting, searching, shortest paths, greedy algorithms, backtracking, divide-and-conquer, and dynamic programming. Data structures include heaps and search, splay, and spanning trees. Analysis techniques include asymptotic worst-case, expected time, amortized analysis, and reductions between problems

Availability: It is important to us to be available to our students, and to address their concerns. If you cannot meet with either of us during our office hours, e-mail us and we will find the time to meet. That being said, like everybody else we are quite busy, so it may take a day or more to find a time to meet. And if you have any comments on the course—what is working, what is not working, what can be done better, etc.—we are very interested in hearing about them. Please send Prof. Hott, Prof. Horton, or one of the TAs an e-mail or post privately on Piazza to the instructors. We tend to get bogged down by e-mail as the semester progresses, so seeing us in person (right after lecture, during office hours, etc.) is often a good way to get a more immediate response.

Syllabus: Download

Resources

The topics we will cover are difficult to master. Below are resources to help with foundational concepts, including proof techniques and additional practice problems.

Useful Resources for CS 4102

Schedule

This is a tentative full-semester schedule of topics addressed. As we go through the semester, we will add homework dates and adjust topics slightly as needed.

Date Topic Slides/Notes Readings Homework
Jan 13 Introduction Horton, Hott - HW0 out
Jan 15 Divide and Conquer Horton, Hott Ch 3, 4  
Jan 20 MLK Day - No class      
Jan 22 Karatsuba, Tree Method Horton, Hott, math Ch 4  
Jan 27 Guess and Check Horton, Hott, math Ch 4  
Jan 29 Master Theorem Horton, Hott, math    
Feb 3 Master Theorem, Substitution Horton, Brunelle/Hott Ch 4  
Feb 5 Closest Pair of Points, Strassen’s Algorithm Horton, Hott Ch 4, 33  
Feb 10 Quicksort, Quickselect, Median of Medians Horton, Brunelle/Hott Ch 7, 9  
Feb 12 Median of Medians, Randomized Quicksort, Sorting Horton, Hott Ch 7, 8  
Feb 17 Average-case Quicksort, Lower Bounds Sorting Horton, Hott Intro II, Ch 4, 6, 8  
Feb 19 Linear Time Sorting, MSCS Horton, Hott 6, 8  
Feb 24 Dynamic Programming   Ch 15  
Feb 26 Matrix Chain Multiplication   Ch 15  
Mar 2 Seam Carving, Longest Common Subsequence   Ch 15  
Mar 4 Midterm Exam      
Mar 9 Spring Break      
Mar 11 Spring Break      
Mar 16 Exam Review, Longest Common Subsequence   -  
Mar 18 Gerrymandering   Ch 16  
Mar 23 Greedy Algorithms, Interval Scheduling   Ch 16  
Mar 25 Greedy Algorithms, Huffman Coding   -  
Mar 30 Belady Cache Replacement      
Apr 1 Graphs, Minimum Spanning Trees   Ch 23  
Apr 6 Dijkstra’s Algorithm   Ch 24  
Apr 8 Bellman-Ford, Floyd-Warshall      
Apr 13 Max Flow, Min Cut   Ch 26  
Apr 15 Bipartite Matching, Reductions      
Apr 20 Reductions   Ch 34  
Apr 22 NP-Completeness      
Apr 27 NP-Completeness, Finale      
May 2 Final Exam, 7-10pm