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.
08/30 | Introduction | Maximum Contiguous Subarray (MCS) sum |
MCS Contd. Dynamic Programming Approach / Bubble Sort |
09/06 | No class - labor day | Modified Bubble Sort / Selection Sort |
Insertion Sort Intro / Insertion Sort (w/ sentinel) |
09/13 | Insertion Sort ( Average Case w/ sentinel ) / Insertion sort w/o sentinel |
Insertion Sort ( Average case w/o sentinel) / Divide and Conquer |
Mergesort |
09/20 | Heapsort (Build Max-heap) |
Heapsort (Sorting max-heap) Build max-heap analysis |
Heap sort Analysis / Integer Addition |
09/27 | Integer Multiplication (Elementary school algorithm) |
Divide & Conquer Multiplication algorithm analysis |
Karatsuba Multiplication algorithm ("clever" method) |
10/04 | Midterm Review | Lower & Upper bounds of functions (summations) / Upper bound of Harmonic series |
Integral approximations (Summations , harmonic series) (see A.2 in CLRS) / Constructive Induction |
10/11 |
Intro to Quicksort /
Example / Quicksort Analysis (best cases) |
Quicksort Analysis (Best case, 25-75% split) |
Quick sort Analysis (random partition sizes, Random Pivot) |
10/18 | Quicksort Analysis (Random Pairwise Comparisons) |
Lower bound on comparison based sorting algorithms (Decision Tree) |
Counting Sort |
10/25 | Radix Sort | Bucket Sort Algorithm | Bucket Sort runtime analysis (Average case) |
11/01 | k-th order statistic (Selection Algorithm)
(worst-case, best-case) |
k-th order statistic(randomized,average case) | Select Algorithm (Blum,Floyd,Rivest,Tarjan,Pratt) |
11/08 | Intro to Graphs / Graph Representations | Midterm II Review | Bread First Search |
11/15 | Depth First Search | Eulerian Paths and Circuits | Minimum spanning tree (Generic Algorithm) Kruskal's MST |
11/22 | Prim's MST/ Dijkstra's Shortest Path Algorithm |
Thanksgiving break | |
11/29 | Prims / Dijkstra's algorithm Contd. | NP-Completeness Intro | NP-Completeness Contd. / Circuit-SAT to Formula-SAT Reduction |
12/06 | NP Verification | NPC Decision / Optimization Problems | NP-Completeness wrap-up / Floyd-Warshall Algorithm |
12/13 | Review |
Monday | Jeovane: 11:00 AM - 1:00 PM |
Tuesday | Gihan: 11:00 AM - 1:00 PM, Jon: 2:00 - 4:00 PM |
Wednesday | Jon: 1:00 PM - 3:00 PM, Ashwin: 2:00 PM - 4:00 PM |
Thursday | Alperen: 9:00 AM - 11:00 AM, Gihan: 11:00 AM - 1:00 PM , Ashwin: 12:30 - 1:30 PM |
Friday | Alperen: 11:00 AM - 1:00 PM, Jeovane: 1:00 PM - 3:00 PM |
Click the name of an assignment below to see its specifications.
Homework 0 | Fri. Sep. 03, 2021 |
Homework 1 | Fri. Sep. 10, 2021 |
Homework 2 | Sat. Sep. 18, 2021 |
Homework 3 | Sat. Sep. 25, 2021 |
Homework 4 | Sat. Oct. 02, 2021 |
Homework 5 | Sat. Oct. 16, 2021 |
Homework 6 | Sat. Oct. 23, 2021 |
Homework 7 | Sat. Oct. 30, 2021 |
Homework 8 | Sat Nov. 06, 2021 |
Homework 9 | Sat Nov. 20, 2021 |
Homework 10 | Sat Dec. 04, 2021 |
Homework 11 | Sat Dec. 11, 2021 |