Welcome to introductory algorithms. We have four main sections.
We will follow the book Algorithms by Dasgupta, Papadimitriou, and Vazirani but there are other excellent books. These include the CLRS book, the Klienberg Tardos book, and Algorithms by Erickson. I will mostly post reading from DPV and occasionally from CLRS. It is expected you read these sections along with the posted notes.
This is subject to change as I realize what takes more or less time.
No. | Date | Subject | Notes | DPV book | DPV PDF | CLRS | other |
---|---|---|---|---|---|---|---|
01 | Aug 22 | Introduction | notes pre notes | pg 1-10 | pg 11-20 | ||
02 | Aug 24 | The Master Theorem and MergeSort | notes pre_notes | pg 49-53 | pg 53-59 | pg 29-39, 93-106 | |
03 | Aug 29 | Arithmetic | notes pre notes | pg 11-15,18-19,45-47,56-57 | pg 21-24, 28, 51-53,62-63 | ||
04 | Aug 31 | Cryptography | notes pre notes | pg 16-34 | pg 25-34 | ||
Sep 05 | Review | ||||||
Sep 07 | Exam 1 | ||||||
05 | Sep 12 | DFS, Topsort, SCC | notes pre notes | pg 80-95 | pg 87-100 | ||
06 | Sep 14 | BFS, Dijkstra | notes pre notes | pg 104-117 | pg 109-122 | ||
07 | Sep 19 | Kruskals | notes pre notes | pg 127-138 | pg 133-145 | ||
08 | Sep 21 | Max Flow Min Cut | notes pre notes | all of ch26 | Erickson ch10 | ||
Sep 26 | Review | ||||||
Sep 28 | Exam 2 | ||||||
09 | Oct 03 | Dynamic Programming | notes pre notes | Competitive Programmer's Handbook | |||
10 | Oct 05 | Longest Subsequences | notes pre notes | 157-166 | 162-170 | 390-396 | |
11 | Oct 12 | Chain Matrix Multiplication | notes pre notes | 370-378 | |||
12 | Oct 17 | Knapsack | notes pre notes | ||||
Oct 19 | Review | ||||||
Oct 24 | Exam 3 | ||||||
13 | Oct 26 | NP-completeness | notes | all ch8 | all ch 34 | Erickson | |
14 | Oct 31 | Satisfiability | notes | ||||
15 | Nov 02 | Independent Set, Vertex Cover | notes | ||||
16 | Nov 07 | Subset Sum and Knapsack | notes | ||||
17 | Nov 09 | 3-coloring, Mario, Puzzles | notes | Mario,Many more | |||
Nov 14 | Review | ||||||
Nov 16 | Exam 4 | ||||||
18 | Nov 21 | Linear Programming | notes pre notes | ||||
19 | Nov 28 | LP Duality | pre notes | ||||
20 | Nov 30 | Randomization | pre notes | ||||
21 | Dec 04 | Approximation | pre notes | ||||
Dec 12 | Final Exam |
As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.