# 600.363 Introduction to Algorithms 600.463 Algorithms I

Please note that this schedule is subject to change.

## Exams

Quiz 1, on Mon 10/5
Quiz 2, on Mon 11/2
Quiz 3, on Mon 12/7

## Homeworks

H1 LaTeX, out 09/09, due 09/16
H2 LaTeX, out 09/16, due 09/23
H3 LaTeX, out 09/23, due 09/30
H4 LaTeX, out 10/12, due 10/21
H5 LaTeX, out 10/21, due 10/28
H6 LaTeX, out 11/09, due 11/16
H7 LaTeX, out 11/16, due 11/23

### Part 1: Foundations

Lecture 1 (Wed Sep 02): Introduction. Insertion sort and analysis.
-- CLRS: 1, 2.1, 2.2

Lecture 2 (Mon Sep 07): Labor Day.
-- No class today, enjoy the holiday.
Lecture 3 (Wed Sep 09): A better way to sort: Merge sort and analysis. Asymptotic notation.
-- CLRS: 2.3, 3

Lecture 4 (Mon Sep 14): Recurrences I.
-- CLRS: 4

Lecture 5 (Wed Sep 16): Recurrences II. Intro to probabilistic analysis.
-- CLRS: 4

Lecture 6 (Mon Sep 21): Probabilistic Analysis. Randomized algorithms.
-- CLRS: 5

### Part 2: Sorting and Order Statistics

Lecture 7 (Wed Sep 23): Quicksort. Randomized Quicksort.
-- CLRS: 7

Lecture 8 (Mon Sep 28): Medians and order statistics.
-- CLRS: 9.

Lecture 9 (Wed Sep 30): Lower bounds for comparison-based sorting. Beating the lower bound: counting sort.
-- CLRS: 8.1, 8.2, 8.3, 8.4.

Lecture 10 (Mon Oct 05): Quiz #1
-- CLRS: everything covered so far.

### Part 3: Advanced Design and Analysis Techniques

Lecture 11 (Wed Oct 07): Dynamic Programming I. Rod Cutting.
-- CLRS: 15.1, 15.2.

Lecture 12 (Mon Oct 12): Dynamic Programming II. Longest Common Subsequence.
-- CLRS: 15.3, 15.4.

Lecture 13 (Wed Oct 14): Greedy Algorithms. Activity selection. Huffman Codes.
-- CLRS: 16.1, 16.2, 16.3.

Lecture 14 (Mon Oct 19): Algorithms Fall Break Day.
-- No class today, enjoy the fall weather.

Lecture 15 (Wed Oct 21): Amortized Analysis.
-- CLRS: 17.1.

### Part 4: Graph Algorithms

Lecture 16 (Mon Oct 26): Graphs and their representations. BFS.
-- CLRS: 22.1, 22.2.

Lecture 17 (Wed Oct 28): DFS.
-- CLRS: 22.3.

Lecture 18 (Mon Nov 02): Quiz #2.
-- CLRS: everything so far, emphasis on material since Quiz #1.

Lecture 19 (Wed Nov 04): Topological sort. Minimum spanning trees. Kruskal and Prim's algorithms.
-- CLRS: 22.4, 23.

Lecture 20 (Mon Nov 09): Single-source shortest paths. The Bellman-Ford algorithm.
-- CLRS: 24 (before 24.1), 24.1.

Lecture 21 (Wed Nov 11): Dijkstra's algorithm.
-- CLRS: 24.3.

Lecture 22 (Mon Nov 16): All-pairs shortest paths.
-- CLRS: 25.2, 25.3.

Lecture 23 (Wed Nov 18): Maximum Flow. The Ford-Fulkerson algorithm.
-- CLRS: 26.1, 26.2.

### Part 5: Selected Topics

Lecture 24 (Mon Nov 23): Introduction to the P vs. NP problem. NP-Completeness.
-- CLRS: 34 (selections)
-- slides: PDF

Lecture 25 (Wed Nov 25): Thanksgiving Break.
-- No class today, enjoy the holiday

Lecture 26 (Mon Nov 30): Introduction to number theory and cryptography.
-- CLRS: 31 (selections)
-- slides: PDF

Lecture 27 (Wed Dec 02): Interactive Proofs and Zero-Knowledge.

Lecture 28 (Mon Dec 07): Quiz #3.
-- CRLS: all material so far, emphasis on material since Quiz #2.
-- This is the last day of classes.