|
|
|
|
Week 1.
20 Mehr - 26 Mehr (Oct 12 - Oct 18)
|
|
Lecture 1 |
Introduction
Analyses of algorithms, Average and worst-case analysis
|
|
Lecture 2 |
Growth of Functions
Asymptotic notation, Sorting algorithms
|
|
Recitation 1 |
Summations and common functions
|
|
Reading |
CLRS: Chapters 1-3
Notes: Sections 1.1-1.4
|
|
Assignment |
Problem Set 1. Due: 27 Mehr (Oct 19)
|
|
Week 2.
27 Mehr - 3 Aban (Oct 19 - Oct 25)
|
|
Lecture 3 |
Recursive Algorithms
Divide and conquer, Mergesort, Quicksort
|
|
Lecture 4 |
Recurrences
The substitution and recursion-tree method, The master method
|
|
Recitation 2 |
Solving recurrences using the characteristic equation
|
|
Reading |
CLRS: Chapter 2, Sections 7.1-7.2
Notes: Sections 1.5-1.7
|
|
Assignment |
Problem Set 2. Due: 4 Aban (Oct 26)
|
|
Week 3.
4 Aban - 10 Aban (Oct 26 - Nov 1)
|
|
Lecture 5 |
Randomized Algorithms
Randomized versions of quicksort, Analysis of quicksort
|
|
Lecture 6 |
Heaps
Building a heap, The heapsort algorithm
|
|
Recitation 3 |
External Sorting
|
|
Reading |
CLRS: Chapters 6-7
Notes: Sections 2.3, 2.4 and 2.7
|
|
Assignment |
Problem Set 3. Due: 11 Aban (Nov 2)
|
|
Week 4.
11 Aban - 17 Aban (Nov 2 - Nov 8)
|
|
Lecture 7 |
Sorting in Linear Time
Lower bounds, Counting sort, Radix sort, Bucket sort
|
|
Lecture 8 |
Medians and Order Statistics
Selection in expected and worst-case linear time
|
|
QUIZ 1 |
In recitation class, closed book
|
|
Reading |
CLRS: Chapters 8-9
Notes: Sections 2.1, 2.2 and 2.6
|
|
Assignment |
Programming Project 1. Due: 21 Aban (Nov 12)
|
|
Week 5.
18 Aban - 24 Aban (Nov 9 - Nov 15)
|
|
Lecture 9 |
Elementary Data Structures
Hash tables, Binary search tree
|
|
Lecture 10 |
Disjoint Sets
Disjoint-set forests, Path compression
|
|
Recitation 4 |
Expected height of a binary search tree
|
|
Reading |
CLRS: Chapters 11, 12 and 21
Notes: Sections 3.2 and 3.9
|
|
Assignment |
Problem Set 4. Due: 25 Aban (Nov 16)
|
|
Week 6.
25 Aban - 1 Azar (Nov 16 - Nov 22)
|
|
Lecture 11 |
Red-Black Trees
Properties of red-black trees, Rotations, Insertion and deletion
|
|
Lecture 12 |
Augmenting Data Structures
Optimal polygon triangulation
|
|
Recitation 5 |
B-Trees
|
|
Reading |
CLRS: Chapters 13, 14 and 18
Notes: Sections 3.5-3.8
|
|
Assignment |
Programming Project 2. Due: 12 Azar (Dec 3)
|
|
Week 7.
2 Azar - 8 Azar (Nov 23 - Nov 29)
|
|
Lecture 13 |
Design of Algorithms by Induction
Largest consequent subsequence, Celebrity problem
|
|
Lecture 14 |
Divide and Conquer
Skyline problem, Fibonacci numbers
|
|
Recitation 6 |
Strassen's algorithm, Sorting Networks
|
|
Reading |
CLRS: Sections 2.3 and 28.2, Chapter 27
Notes: Sections 4.1-4.3
|
|
Assignment |
Problem Set 5. Due: 9 Azar (Nov 30)
|
|
Week 8.
9 Azar - 15 Azar (Nov 30 - Dec 6)
|
|
Lecture 15 |
Dynamic Programming
Matrix-chain multiplication, Longest common subsequence
|
|
Lecture 16 |
Dynamic Programming
Knapsack problem, Optimal binary search trees
|
|
Recitation 7 |
External Sorting
|
|
Reading |
CLRS: Chapter 15
Notes: Section 4.4
|
|
Assignment |
Programming Project 3. Due: 26 Azar (Dec 17)
|
|
Week 9.
16 Azar - 22 Azar (Dec 7 - Dec 13)
|
|
QUIZ 2 |
In class, closed book
|
|
Recitation 8 |
Quiz 2 solution
|
|
Week 10.
23 Azar - 29 Azar (Dec 14 - Dec 20)
|
|
Lecture 17 |
Greedy Algorithms
An activity-selection problem, Task-scheduling
|
|
Lecture 18 |
Minimum Spanning Trees
The algorithms of Kruskal and Prim
|
|
Recitation 9 |
Huffman codes
|
|
Reading |
CLRS: Chapters 16 and 23
Notes: Section 4.5
|
|
Assignment |
Problem Set 6. Due: 30 Azar (Dec 21)
|
|
Week 11.
30 Azar - 6 Dey (Dec 21 - Dec 27)
|
|
Lecture 19 |
Graph Algorithms
Breadth-first search, Depth-first search, Topological sort
|
|
Lecture 20 |
Backtracking
n-queen problem, Branch and bound
|
|
Recitation 10 |
Traveling-salesman problem
|
|
Reading |
CLRS: Chapter 22
Notes: Section 4.6
|
|
Assignment |
Problem Set 7. Due: 7 Dey (Dec 28)
|
|
Week 12.
7 Dey - 13 Dey (Dec 28 - Jan 3)
|
|
Lecture 21 |
Single-Source Shortest Paths
The Bellman-Ford algorithm, Dijkstra's algorithm
|
|
Lecture 22 |
All-Pairs Shortest Paths
The Floyd-Warshall algorithm, Johnson's algorithm
|
|
Recitation 11 |
Difference constraints and shortest paths
|
|
Reading |
CLRS: Chapters 24-25
|
|
Assignment |
Final Programming Project. Due: 7 Bahman (Jan 27)
|
|
|
|