- 9/2 - 9/9
- Week 1 / Intro
Lecture 1 Notes
- Administrative, Intro (CLRS ch1, ch2)
- Introduction, Example Problems
- Fibonacci numbers
- Orders of Growth (CLRS ch3)
Slides:
Fibonacci, Strassen, 2 Lists
Recap. These math topics are prerequisites:
Discrete Math (Undergrad Honors)
- Background/prerequisites:
- * math
- * datastructures : arrays, trees, lists
- * pseudocode/ imperative programming
- * sorting : mergesort, insertionsort
Podcast: Fibonacci Matrix Exponentiation(adobe pdf)
- HW 1_ORDER
REC
- Due: Mon 9/15 HW1_Latex_template
math problems(optional, no credit)
- 9/9 - 9/16
- Week 2 / Recurrences Lecture 2 Notes
Notes: Recurrences
Example: Iteration Method
Notes: Master Theorem
Examples: Master Theorem
Slides : Recurrences
- Podcast:
Iteration Method (mp4)
- Podcast: Iteration -Derivation (mp4)
- Podcast: master Theorem (adobe pdf)
- 9/16 - 9/23
- Week 3 / Sorting
Lecture 3 Notes
- InsertionSort
- MergeSort
- HeapSort (CLRS ch6)
- QuickSort (CLRS ch7)
Algorithms Thinking Session Notes (optional)
- HW 2_SORT 1
- Due: 9/22 HW2_Latex_template
- 9/23 - 9/30
- Week 4 / Sorting, Order Statistics
Lecture 4 Notes
- QuickSort, Partition (CLRS ch7)
- Counting Sort, Radix Sort (CLRS ch8)
- Sorting bounds
- Median, order statistics (CLRS ch9)
- HW 3_SORT 2
- Due: 9/29 HW3_Latex_template
- 9/30 - 10/7
- Week 5 / Greedy
Lecture 5 Notes
Sub-problem Structure for Greedy
Lecture Notes: Greedy
Notes: Greedy Techniques
Wikipedia: Greedy
Slides : Greedy
podcast: Fractional Knapsack
podcast: Activity Selection Problem
- HW 4 GREEDY
- Due: 10/6 HW4_Latex_template
- 10/7 - 10/14
- Week 6 / Dynamic Programming Lecture 6 Notes
Sub-problem Structure for DynProg
Notes: Coin change
Notes: CheckBoard
Notes: Discrete Knapsack
Slides : DP1
podcast: coin change
podcast: check board
- HW 5 DYN PROG
- Due: 10/13 HW5_Latex_template
- 10/14 - 10/21
- Week 7 / Dynamic Programming Lecture 7 Notes
Notes: LCS
Notes: Matrix Chain Multiplication
Slides: DP2
SlidesDP2 + Optimal BST
- HW 6 DYN PROG
- Due: 10/20 HW6_Latex_template
- 10/21 - 10/28
- Week 8 / Dynamic Programming Lecture 8 Notes
SAT 10/25 MIDTERM 10AM-6PM
- room
- open notes/book/HWs first 90 minutes
- cheatsheet 4 pages (2 sheets) allowed whole exam
DP problems as DAG Shortest Paths (Notes)
- 10/28 - 11/4
- HW 7 SIMPLE STRUCTURES
- Due: 11/3 HW7_Latex_template
- 11/4 - 11/11
Trees and Hashes
Skiplists
Lecture 9 notes
- Hash Tables (ch 11)
- RB trees (ch13)
Hash, RB Tree Slides
Skiplists
Note ;
Slides ;
Visualizer
- podcast: RB tree rotation
- podcast: RB tree insertion
- podcast:
RB tree deletion
Other interesting tree structures:
B-trees (book)
van Emde Boas Trees (book)
AVL trees (balancing)
Splay trees (caching)
Y-fast tries
- HW 8+9 HASH & TREE, HEAPS
- Due: 11/10 HW89_Latex_template
- 11 /11 - 11/18
- Week 11 / Amortized Analysis
Lecture 10 notes (A)
Lecture 10 notes (B)
- 11/18 - 11/25
-
- Week 12 / Graphs I
- Graps Intro, BFS, DFS
- DAGs
- Strongly Connected Components
Lecture 11 notes
- Graphs Intro (ch 22)
- Minimum Spanning Trees (ch 23)
Podcast: SCC
Podcast: MST
- HW 10 GRAPHS 1
- Due: 11/17
HW10_Latex_template
- 11/25 - 12/2
- Week 13 / Graphs II
- MST
- Shortest Paths
Lecture 12 notes
- SSSP: Bellman Ford
- SSSP: Dijkstra
ASSP: DP by edges
ASSP: DP by vertices (Floyd Warshall)
- HW11 GRAPHS 2
due 11/25
HW11_Latex_template
- 12/2 - 12/9
- Week 14 / Graphs III,
- Network Flows
- SP
- Network Flow
- MaxFlow-MinCut Theorem
- Ford-Fulkerson
max Flow Slides
Push-relabel slides
Push Relabel text : Use CLRS 3rd edition
- HW 12_GRAPHS 3 NET due 12/3
HW12_Latex_template
-
FINAL EXAM
Sat 12/6-9 (TBD)
10AM-4PM
cheatsheet 4 pages allowed whole exam
- Optional / Linear Programming
RSA Math Notes: Number Theory
Slides: RSA
- HW 13 LIN
PROG, RSA
- Optional, no credit
- Optional / Advanced Topics (optional)
- NP-complete Problems, Approx Algorithms, RSA