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.
| 01/25 | Introduction | Maximum Contiguous Subarray (MCS) sum |
MCS Contd. Dynamic Programming Approach |
| 02/01 | Bubble Sort | Modified Bubble Sort / Selection Sort |
Insertion Sort Intro / Insertion Sort (w/ sentinel) |
| 02/08 | Insertion Sort ( Average Case w/ sentinel) / (best and worst case w/o sentinel) |
Insertion Sort ( Average case w/o sentinel) | Divide and Conquer |
| 02/15 | Merge Sort | Heapsort / heapsort animation |
Heapsort |
| 02/22 | Heap sort Analysis (Build max-heap) |
Heap sort Analysis (sort max-heap) / Integer Addition / Integer Multiplication (Elementary school algorithm) |
Recursive Multiplication |
| 03/01 | Midterm Review | Karatsuba "clever" method | Lower & Upper bounds of functions (summations) / Integral approximations (summations) (see A.2 in CLRS) |
| 03/08 |
Integral approximations (harmonic series)/ Constructive Induction / Intro to Quicksort / Example |
Quicksort Analysis (Worst, best cases) |
Quicksort Analysis (25-75% split, random partition sizes) |
| 03/15 | Spring break | ||
| 03/22 |
Quick sort Analysis (Random Pivot) |
Quicksort Analysis (Random Pairwise Comparisons) |
Lower bound on comparison based sorting algorithms (Decision Tree) |
| 03/29 | Lower bound on comparison based sorting algorithms (Decision Tree) | Counting Sort | Radix Sort |
| 04/05 | Bucket Sort Algorithm | k-th order statistic (Selection Algorithm)
(best-case, approx. average-case) |
k-th order statistic(randomized,average case) |
| 04/12 | Midterm II Review | k-th order statistic Average Case | Select Algorithm |
| 04/19 | Intro to Graphs / Graph Representations | Bread First Search / Depth First Search |
Depth First Search / Eulerian Paths and Cycles |
| 04/26 | Euler Cycles and Paths / Minimum spanning tree (Generic Algorithm) |
Kruskal and Prim's MST | Dijkstra's Shortest Path Algorithm |
| 05/03 | Prims / Dijkstra's algorithm | NP-Completeness | NP-Completeness Contd. |
| 05/10 | NP-Completeness / Wrap-up | ||
| Monday | Ashwin: 10:00 AM - 12:00 PM, Chen: 2:00 PM - 4:00 PM |
| Tuesday | Songwei: 9:00 AM - 11:00 AM, Yancy: 3:00 - 5:00 PM |
| Wednesday |
Chen: 10:00 AM - 12:00 PM, Kamala: 12:00 - 1:00 PM, Kamala: 2:00 - 3:00 PM, Ishat: 3:00 - 5:00 PM |
| Thursday |
Songwei: 9:00 AM - 11:00 AM, Ishat: 12:00 - 2:00 PM, Yancy: 2:00 - 4:00 PM, Anton: 5:00 - 6:00 PM |
| Friday |
Anton: 9:00 AM - 11:00 AM, Ashwin: 11:00 AM - 1:00 PM Kamala: 2:00 - 4:00 PM, Anton: 5:00 - 6:00 PM |
Click the name of an assignment below to see its specifications.
| Homework 0 | Fri. Jan. 29, 2021 |
| Homework 1 | Sat., Feb. 06, 2021 |
| Homework 2 | Sat., Feb. 13, 2021 |
| Homework 3 | Sat., Feb. 20, 2021 |
| Homework 4 | Sat., Feb. 27, 2021 |
| Homework 5 | Sat., March 13, 2021 |
| Homework 6 | Sat., Mar. 27, 2021 |
| Homework 7 | Sat., Apr. 03, 2021 |
| Homework 8 | Sat. Apr. 10, 2021 |
| Homework 9 | Sat Apr. 24, 2021 |
| Homework 10 | Sat May 01, 2021 |
| Homework 11 | Sat May 08, 2021 |