- 9/6 - 9/13
- 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 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: Wed 9/20 HW1_Latex_template
- 9/13 - 9/20
- 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/20 - 9/27
- Week 3 / Sorting
Lecture 3 Notes
- InsertionSort
- MergeSort
- HeapSort (CLRS ch6)
- QuickSort (CLRS ch7)
Algorithms Thinking Seesion Notes (optional)
- HW 2_SORT 1
- Due: 9/27 HW2_Latex_template
- 9/27 - 10/4
- 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: 10/4 HW3_Latex_template
- 10/4 - 10/11
- Week 5 / Greedy
Lecture 5 Notes
Mon 10/9 Indigenous Peoples Day, NO CLASS
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/11 HW4_Latex_template
- 10/11 - 10/18
- 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/18 HW5_Latex_template
- 10/18 - 10/25
- Week 7 / Dynamic Programming Lecture 7 Notes
Notes: LCS
Notes: Matrix Chain Multiplication
Slides: DP2
SlidesDP2 + Oprimal BST
- HW 6 DYN PROG
- Due: 10/25 HW6_Latex_template
- 10/25 - 11/1
- Week 8 / Dynamic Programming Lecture 8 Notes
SAT 10/28 MIDTERM 10AM-6PM
- Shillman(SH) room 335
- open notes/book/HWs first 90 minutes
- cheatsheet 4 pages/2 sheets allowed whole exam
DP problems as DAG Shortest Paths (Notes)
- 10/30 - 11/6
No class Thu 11/2
BREAK : Wed 11/1 - Sun 11/5
No Class, OH, HW
- HW 7 SIMPLE STRUCTURES
- Due: 11/9 HW7_Latex_template
- 11 /6 - 11/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)
- HW 8+9 HASH & TREE, HEAPS
- Due: 11/16 HW8_Latex_template
- 11/13 - 11/20
- Week 11 / Amortized Analysis
Lecture 10 notes (A)
Lecture 10 notes (B)
- 11/20 - 11/27
-
- Week 12 / Graphs I
- Graps Intro, BFS, DFS
- DAGs
- Strongly Connected Components
Lecture 11 notesThanksGiving : No class Thu 11/23
- Graphs Intro (ch 22)
- Minimum Spanning Trees (ch 23)
Podcast: SCC
Podcast: MST
- HW 10 GRAPHS 1
- Due: 11/26
HW10_Latex_template
- 11/27 - 12/4
- 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 12/3
HW11_Latex_template
- 12/4 - 12/11
- 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/12
HW12_Latex_template
-
FINAL EXAM, SAT DEC 9, 12PM-6PM
SH 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