CSE 5311: Design and Analysis of Algorithms

Section 002, Fall 2014

TuTh 2:00PM - 3:20PM, SH 125

As the instructor for this course, I reserve the right to adjust this schedule in any way that serves the educational needs of the students enrolled in this course.
--Saravanan Thirumuruganathan

Date Day Topic Slides
21-AugThu Introduction, Logistics, Brief tutorial of Piazza, Socrative and Anki N/A
26-AugTue Rate of growth of functions, Introduction to complexity analysis, Recurrence basics, Elementary sorting algorithms [PDF]
28-AugThu Divide and Conquer Paradigm - Merge sort and Quicksort [PDF]
2-SepTue No class due to Instructor's Conference travel
4-SepThu No class due to Instructor's Conference travel
9-SepTue Lower bounds for Sorting, Linear time sorting algorithms [PDF]
11-SepThu Order statistics - min, max, median, mode and k-th smallest/largest [PDF]
12-SepFri Makeup Class: Binary search, Introduction to Data Structures [PDF]
16-SepTue Quiz 1, Discussion of Quiz 1
18-SepThu Binary Search Trees, Red-Black Trees [PDF]
23-SepTue Heap, HeapSort, Union-Find [PDF]
25-SepThu Hash tables, Peek into DHTs and Bloom Filters [PDF]
30-SepTue Data Structures: Selection and Augmentation [PDF]
2-OctThu Graphs - representation and modelling, Sparse graphs, Quiz 2
7-OctTue Graph traversal and applications
9-OctThu Topological sorting
10-OctFri Makeup Class (2 hours): Catchup
14-OctTue Intro to Greedy Algorithms, MST: Kruskal, Prim
16-OctThu Shortest Path: Dijkstra, Mid-Term Review
21-OctTue Mid-Term
23-OctThu Basics of Bellman-Ford, Floyd-Warshall
28-OctTue Network flow: Ford-Fulkerson, Edmonds-Karp
30-OctThu Bipartite Matching, Stable Marriage
4-NovTue NP-Completeness, Popular NP-Complete problems, Quiz 3
6-NovThu Reductions, Techniques to tackle NP-Completeness
11-NovTue Divide and Conquer - I
13-NovThu Dynamic Programming - I
18-NovTue Dynamic Programming - II
20-NovThu Greedy Algorithms - I, Quiz 4
25-NovTue Greedy Algorithms - II
27-NovThu Thanksgiving holidays
2-DecTue 5311 and beyond, Final Exam Review
9-DecTue Final Exam, 2-4:30 PM