This course presents an introduction to the techniques for designing efficient computer algorithms and analyzing their running times. General topics include asymptotics, solving summations and recurrences, algorithm design techniques, analysis of data structures, and introduction to NP-completeness.
Week of | |||
---|---|---|---|
08/26 | Introduction | Maximum Contiguous subarray sum |
Maximum subarray sum / Bubble sort |
09/02 | Labor Day (No Class) | Bubble Sort Contd. / Intro to insertion sort |
Insertion Sort Analysis |
09/09 | Insertion sort without sentinel (Analysis)/ Selection sort |
Merge Sort / Analysis |
Heap sort / Heap sort animation |
09/16 | Heap build analysis | Heap sort analysis / Integer Addition, Integer Multiplication (Brute force) |
Integer Multiplication (Divide and Conquer) |
09/23 |
Integer Multiplication (Karatsuba Approach / Clever method) |
Lower and Upper bounds of functions (summations) |
Integral Approximations (Summations) / Constructive Induction / Intro to Quicksort algorithm |
09/30 | Quicksort Analysis (Worst Case) |
Midterm Review | Quick Sort Analysis best case (Median pivot)/ "approximate" average case (25%-75% split) |
10/07 | Quicksort Analysis (Randomized pivot) |
Randomized QS Analysis (Pairwise comparisons) |
Decision Trees (Lower bound on comparison based sorting ) Intro to Counting sort |
10/14 | Counting sort Intro to Radix sort |
Radix sort | Bucket sort |
10/21 | kth order statistic ( Selection algorithm) Best and worst case |
Selection - Avg. case | Worst-case Selection (deterministic) (kth order statistic) |
10/28 | Deterministic Select Analysis / Intro to Graphs |
Breadth First Search/ Depth First Search |
Eulerian Paths and Cycles |
11/04 | Minimum Spanning Trees (MST) | Midterm Review | Kruskal's and Prim's MST algorithms |
11/11 | Dijkstra's shortest path algorithm | Dijkstra's algorithm | Dijkstra's wrap-up / Intro to Random Number Generators |
11/18 | Random Number Generators / Intro to NP-Completeness |
NP-Completeness / Circuit-SAT to Formula-SAT reduction |
Optimization / decision problem (example: Independent set) |
11/25 | Polynomial runtime Random walk algorithm for 2-SAT |
Thanksgiving break | |
12/02 | All pairs shortest path Floyd-Warshall Algorithm |
Transitive Closure | Karger's min-cut algorithm |
12/09 | Final Review (last day of class) |
Instructor: Mohammad Nayeem Teli (nayeem at cs.umd.edu)
Office: 1128 IRB
Office Hours: MWF 2:00 - 3:00 PM
Administrators:
Anton Pozharsky | apozharski@gmail.com |
Deep Patel | dpatel17@umd.edu |
Eric Xiao | ericxiao2013@gmail.com |
Jie Li | jli2718@umd.edu |
Mara Levy | mlevy2525@gmail.com |
Matthew Walmer | mwalmer@cs.umd.edu |
Harihara Muralidharan | hsmurali@cs.umd.edu |
Peihong Yu | peihong@umd.edu |
Masataro Koizumi | masataro.koizumi@gmail.com |
Ruochen Wang | rwang113@terpmail.umd.edu |
Shubhankar Sachdev | ssachdev@terpmail.umd.edu |
Bryce Toole | bctoole@gmail.com |
All TA office hours take place in room IRB 1108. Please note that a TA may need to leave 5 minutes before the end of the hour in order to go to his/her class. Please be understanding of their schedules.
Time | MON | TUE | WED | THU | FRI |
---|---|---|---|---|---|
9:00 - 10:00 | Ruochen | Mara | Ruochen | ||
10:00 - 11:00 | class | Mara | class | Masa | class |
11:00 - 12:00 | Hari | Hari | Bryce | Anton | Anton |
12:00 - 1:00 | Hari | Hari | Shubhankar | Deep | Eric |
1:00 - 2:00 | Matt | Peihong | Matt | Peihong | Masa |
2:00 - 3:00 | Matt | Peihong | Anton / Matt | Peihong / Mara | Jie |
3:00 - 4:00 | Jie | Bryce / Deep | Eric | Mara | Jie |
4:00 - 5:00 | Jie | Bryce | Eric | ||
5:00 - 6:00 | Shubhankar | Shubhankar |
Click the name of an assignment below to see its specifications.
Homework 0 | Aug. 30, 2019 |
Homework 1 | Sep. 6, 2019 |
Homework 2 | Sep. 14, 2019 |
Homework 3 | Sep. 21, 2019 |
Homework 4 | Sep. 28, 2019 |
Homework 5 | Oct. 12, 2019 |
Homework 6 | Oct. 19, 2019 |
Homework 7 | Oct. 26, 2019 |
Homework 8 | Nov. 02, 2019 |
Homework 9 | Nov. 16, 2019 |
Homework 10 | Nov. 23, 2019 |
Homework 11 | Dec. 06, 2019 |