- 9/3 - 9/10
- 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/16 HW1_Latex_template
- 9/10 - 9/17
- 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/17 - 9/24
- 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/23 HW2_Latex_template
- 9/24 - 10/1
- 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/30 HW3_Latex_template
- 10/1 - 10/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: 10/7 HW4_Latex_template
- 10/8 - 10/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: 10/14 HW5_Latex_template
- 10/15 - 10/22
- Week 7 / Dynamic Programming Lecture 7 Notes
Notes: LCS
Notes: Matrix Chain Multiplication
Slides: DP2
SlidesDP2 + Optimal BST
- HW 6 DYN PROG
- Due: 10/21 HW6_Latex_template
- 10/22 - 10/29
- Week 8 / Dynamic Programming Lecture 8 Notes
SAT 10/26 MIDTERM 10AM-6PM
- room Shillman (SH) 105
- open notes/book/HWs first 90 minutes
- cheatsheet 4 pages (2 sheets) allowed whole exam
DP problems as DAG Shortest Paths (Notes)
- 10/29 - 11/5
- HW 7 SIMPLE STRUCTURES
- Due: 11/4 HW7_Latex_template
- 11 / 5 - 11/12
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/11 HW89_Latex_template
- 11 /12 - 11/19
- Week 11 / Amortized Analysis
Lecture 10 notes (A)
Lecture 10 notes (B)
- 11/19 - 11/26
-
- 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/18
HW10_Latex_template
- 11/26 - 12/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
- 12 / 3- 12/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 12/4
HW12_Latex_template
-
FINAL EXAM
Sat 12/7
10AM-4PM
SH room 335
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