- 5/4 - 5/11
- 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
- HW1 LLM 3Jars
- Due: Mon 5/18 HW1_Latex_template
math problems(optional, no credit)
- 5/11 - 5/18
- 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)
- 5/18 - 5/25
- Week 3 / Sorting
Lecture 3 Notes
- InsertionSort
- MergeSort
- HeapSort (CLRS ch6)
- QuickSort (CLRS ch7)
Algorithms Thinking Session Notes (optional)
- HW 2_SORT 1
- Due: 5/25 HW2_Latex_template
- 5/25 - 6/1
- Week 4 / Sorting, Order Statistics
Lecture 4 Notes
Mon 5/25 Memorial Day, NO CLASS
- QuickSort, Partition (CLRS ch7)
- Counting Sort, Radix Sort (CLRS ch8)
- Sorting bounds
- Median, order statistics (CLRS ch9)
- HW 3_SORT 2
- Due: 6/1 HW3_Latex_template
- 6/1 - 6/8
- 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: 6/8 HW4_Latex_template
- 6/8 - 6/15
- 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: 6/15 HW5_Latex_template
- 6/15 - 6/22
- Week 7 / Dynamic Programming Lecture 7 Notes
Notes: LCS
Notes: Matrix Chain Multiplication
Slides: DP2
SlidesDP2 + Optimal BST
- HW 6 DYN PROG
- Due: 6/22 HW6_Latex_template
- 6/22 - 6/29
- Week 8 / Dynamic Programming Lecture 8 Notes
FRI or SAT 6/26-27 MIDTERM 10AM-6PM
- room TBD
- open notes/book/HWs first 90 minutes
- cheatsheet 4 pages (2 sheets) allowed whole exam
DP problems as DAG Shortest Paths (Notes)
- 6/29 - 7/6
- HW 7 SIMPLE STRUCTURES
- Due: 7/6 HW7_Latex_template
- 7/6 - 7/13
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: 7/13 HW89_Latex_template
- 7 /13 - 7/20
- Week 11 / Amortized Analysis
Lecture 10 notes (A)
Lecture 10 notes (B)
- HW 9 AA
- Due 7/20
HW9_Latex_template
- 7/20 - 7/27
-
- 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: 7/27
HW10_Latex_template
- 7/27 - 8/3
- 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
- 8/3 - 8/10
- 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 8/10
HW12_Latex_template
- 12/2 - 12/9
- Optional / Linear Programming
RSA Math Notes: Number Theory
Slides: RSA
- HW 13 LIN
PROG, RSA
- Optional, no credit
-
FINAL EXAM
Thu/Fri August 13-14 , 6 hours
cheatsheet 4 pages allowed whole exam
- Optional / Advanced Topics (optional)
- NP-complete Problems, Approx Algorithms, RSA