CS:4/56101 Design and Analysis of Algorithms - Summer 2020

Topics	Subtopics & Slides	Examples	Reading	Date
Introduction	Syllabus
	Intro			6/05
Ch 1: Algorithm Analysis	Analysis of Algorithms		1.1, 1.2, 1.3, 1.4	6/10
Ch 2: Basic Data Structures	Elementary Data Structures		1.5, 2.1, 2.2, 2.3	6/10
	Priority Queues and Heaps	heap insert, heap removeMin	2.4.1 - 2.4.4	6/12
	Dictionaries and Hash Tables	chaining, linear probing, double hashing	2.5.1 - 2.5.6	6/17
Ch 3: Search Trees and Skip Lists	Binary Search Trees	insert, find, remove	3.1.1 - 3.1.6	6/19
	Red-Black Trees	insert	3.3.3	6/19
Ch 4: Sorting, Sets, and Selection	Merge Sort	merge sort	4.1.1	6/24
	Quick Sort	quick sort	4.3.1, 4.6	6/24
	Sorting Lower Bound		4.4	6/24
	Radix Sort	bucket sort, radix sort	4.5.1, 4.5.2	6/26
	Sets		4.2.1	6/26
	Selection	quick select	4.7, 4.7.1 - 4.7.3	6/26
Ch 5: Fundamental Techniques	Greedy Method	fractional knapsack, task scheduling	5.1, 5.1.1, 5.1.2	7/03
	Divide and Conquer	master theorem	5.2, 5.2.1 - 5.2.3	7/03
	Dynamic Programming	matrix chain product, 0-1 knapsack	5.3, 5.3.1 - 5.3.3	7/08
Ch 6: Graphs	Graphs		6.1 - 6.2	7/10
	Depth-First Search	dfs	6.3.1	7/10
	Breadth-First Search	bfs	6.3.3	7/10
	Biconnectivity		6.3.2	7/15
	Directed Graphs		6.4.1, 6.4.2, 6.4.4	7/15
Ch 7: Weighted Graphs	Shortest Paths	dijkstra (on undirected graph), dijkstra (on digraph), dag-based, bellman-ford	7.1, 7.1.1 - 7.1.3, 7.2, 7.2.1	7/17
	Minimum Spanning Trees	prim-jarnik, kruskal	7.3, 7.3.1 - 7.3.3	7/22
Ch 8: Network Flow and Matching	Network Flow	ford-fulkerson, edmond-karp	8.1.1, 8.1.2, 8.2.1 - 8.2.3	7/24

Blackboard

Topics are broken up into modules.

• Module 1 Introduction: Ch. 1 and Ch. 2 Elementary Data Structures
• Module 2 Advanced Data Structures: Ch. 2 and Ch. 3
• Module 3 Sorting: Ch 4
• Module 4 Fundamental Design Technique: Ch. 5
• Module 5 Graphs: Ch. 6
• Module 6 More Graphs: Ch. 7 and Ch. 8 Network Flow

Each module has a set of corresponding videos, a few short quizzes to gauge your understanding of the material, and a homework assignment. Check Blackboard for this additional material.

Piazza

Sign up for Piazza, a Q&A web service where you can ask and answer questions related to the class.