| Aug 27-31 |
(Aug 27) Intro to Algorithms and algorithm complexity. Intro slides, Intro slides (black & white)
(Aug 29) Comparison based algorithms slides, slides with lecture notes
(Aug 31) Analysis of insertion sort, asymptotic analysis
|
Asymptotic complexity proofs |
Ch 2.2, Ch 3 |
Initial Assessment Survey |
| Sep 3 |
NO CLASS: Labor day |
| Sep 5-7 |
(Sep 5) Comparison sort analysis
(Sep 7) Divide & conquer, recurrences
|
|
Ch 8.1
Ch 4.3 - 4.4
|
Homework 1 is posted |
| Sep 10-14 |
(Sep 10) Solving Recurrences with Substitution method practice
(Sep 12)Master Theorem for Recurrences
(Sep 14)Divide and Conquer: Merge Sort
|
|
Ch 4.5.
Ch 2.3
|
|
| Sep 17-21 |
(Sep 17) Dynamic Programming - Longest Common Subsequence
(Sep 19) Dynamic Programming - Subset Sum Problem
(Sep 21) Dynamic Programming - Rod Cutting Problem
|
|
Ch 15.4
Ch 15.1
Practice problems: 15.1-2, 15.1-3, 15.1-5
|
Homework 2 is posted |
| Sep 24-28 |
(Sep 24) Greedy Algorithms - Activity Selection Problem
(Sep 26) Weighted activity selection, activity partitioning
(Sep 28) Greedy Algorithms - Minimize schedule delay
|
|
Ch 16.1 - 16.2
Practice problems: 16.1-2, 16.1-3, 16.2-7
|
|
| Oct 1-5 |
Elementary Graph Algorithms
|
|
Ch 22.1-22.3
Practice problems: 22.1-1, 22.1-2, 22.1-3, 22.1-4, 22.1-5
|
Homework 3 is posted |
| Oct 8-12 |
Topological sort order, strongly connecteed components
Midterm review
|
|
Ch 22.4
|
|
| Oct 15 |
Midterm Exam |
| Oct 17-19 |
Sstrongly connecteed components (continued)
|
|
Ch 22.4
|
|
| Oct 22 |
Fall Break |
| Oct 24-26 |
Minimum spanning trees, Kruskal's algorithm
Prim's algorithm, Priority queue
|
|
Ch 23
|
Extra credit assigned |
| Oct 29-Nov 2 |
Priority queues continued, Prim's algorithm revisited
Prim's algorithm example, Cycle property, example problem
Clustering using MST, Shortest Path problems
|
|
Ch 23
Ch 24.1, 24.2
|
|
| Nov 5-9 |
Bellman-Ford Algorithm for shortest path, Shortest path in DAG
Application of Bellman-Ford Algorithm. Dijkstra's Algorithm.
All Pairs Shortest Paths.
|
|
Ch 24.1, 24.2
Ch 24.3
Ch 25.2
|
|
| Nov 12-16 |
Introduction to Maximum Flow problem
Residual networks, augmented flow
Max Flow Min Cut
|
|
Ch 26.1
Ch 26.2
|
Homework 5 is assigned |
| Nov 19 |
Basic Ford-Fulkerson algorithm, Edmonds-Karp algorithm for max flow
|
|
Ch 26.2 |
|
| Nov 21-23 |
Thanksgiving Break |
| Nov 26-30 |
NP Complete Problems - Introduction
NP Complete Problems - Reductions
Approximation Algorithms - Introduction
|
|
Ch 34-intro, 34.1
Ch 35
|
Homework 6 is posted |
| Dec 3-7 |
Evolutionary Algorithms - Introduction
Evolutionary Algorithms Examples
Final Review Day 1
|
|
|
Homework 7 is posted |
| Dec 10 |
Final Review Day 2
|
|
|
|
| Dec 17, 8am - 9:50am |
FINAL EXAM - RITTER HALL 314 |