CS/Math 473 (Fall 2022)

CS/Math 473 (Fall 2022)

Show Details

Fall 2022 lecture videos for CS/Math 473, taught by Jeff Erickson

…Read more Less…

∞. Final Exam Review

duration 1 hour 12 minutes

∞. Final Exam Review

∞. Final Exam Review

From Jeff Erickson

147 plays 0
Logistics Read the questions Pareto-optimal points Separating points with parallel lines Rooted subtree search Nesting boxes Escape wiring Elmo and Daisy play cards…
26. Splay trees and the dynamic optimality…

duration 1 hour 11 minutes

26. Splay trees and the dynamic optimality…

26. Splay trees and the dynamic optimality conjecture

From Jeff Erickson

56 plays 0
Splay trees Amortized time via potential function Access Lemma ⇒ O(log n) amortized time per splay Generalized Access Lemma ⇒ static optimality What is a…
25. Online algorithms

duration 1 hour 15 minutes

25. Online algorithms

25. Online algorithms

From Jeff Erickson

66 plays 0
What are online algorithms? Example: paging The lost cow problem Exponential search is 9-competitive Randomizing first step direction: expected competitive ratio 7 [Kao,…
24. LP duality and the simplex algorithm

duration 1 hour 17 minutes

24. LP duality and the simplex algorithm

24. LP duality and the simplex algorithm

From Jeff Erickson

102 plays 0
LP duality: swap roles of matrix constraints and variables Weak duality theorem: cx ≤ yAx ≤ yb Physical interpretation of optimal dual solution Vocabulary: basis,…
23. Linear programming

duration 1 hour 16 minutes

23. Linear programming

23. Linear programming

From Jeff Erickson

163 plays 0
Definition of linear programming Example: Maximum flows Geometry: Lowest point in a convex polyhedron Infeasible and unbounded LPs Canonical (standard inequality) form…
22. Minimum cost flows

duration 1 hour 15 minutes

22. Minimum cost flows

22. Minimum cost flows

From Jeff Erickson

126 plays 0
Minimum-cost circulations Cycle cancelling Minimum-cost flows Feasible then balanced then locally optimal Successive shortest paths: feasible and locally optimal then…
21. More applications and extensions

duration 1 hour 5 minutes

21. More applications and extensions

21. More applications and extensions

From Jeff Erickson

116 plays 0
Minimum vertex cover Project selection Non-zero balances Lower bounds on edges
20. More applications of maximum flow

duration 1 hour 15 minutes

20. More applications of maximum flow

20. More applications of maximum flow

From Jeff Erickson

153 plays 0
General strategy Scheduling final exams Tuple selection Disjoint path cover in dags Cycle cover in directed graphs
19. Midterm 2 review

duration 1 hour 17 minutes

19. Midterm 2 review

19. Midterm 2 review

From Jeff Erickson

140 plays 0
hashing collisions leaves in treaps Thomas the Tank Engine gets COVID cyclic shifts of strings
18. Applications/extensions of maximum flow

duration 1 hour 14 minutes

18. Applications/extensions of maximum flow

18. Applications/extensions of maximum flow

From Jeff Erickson

205 plays 0
Edge-disjoint paths Undirected graphs Vertex capacities and vertex-disjoint paths Maximum bipartite matching The Jacobi-Berge alternating path algorithm (aka…
17. Maximum flow structure and algorithms

duration 1 hour 15 minutes

17. Maximum flow structure and algorithms

17. Maximum flow structure and algorithms

From Jeff Erickson

160 plays 0
Definition review Ford-Fulkerson Bad example with integer capacities Really bad example with irrational capacities Decomposing flows into paths and cycles Good…
16. Maximum flows and minimum cuts

duration 1 hour 14 minutes

16. Maximum flows and minimum cuts

16. Maximum flows and minimum cuts

From Jeff Erickson

206 plays 0
Definition of maximum flows Definition of minimum cuts The maxflow-mincut theorem Easy direction: follow the inequalities Harder direction: Residual graphs…
15. String matching via careful failure

duration 1 hour 18 minutes

15. String matching via careful failure

15. String matching via careful failure

From Jeff Erickson

123 plays 0
Avoiding redundant comparisons The fail function and finite-state machine Knuth-Morris-Pratt: O(n) worst-case time Border of P = any proper prefix of P that is also a…
15. String matching via rolling hash

duration 1 hour 0 minutes

15. String matching via rolling hash

15. String matching via rolling hash

From Jeff Erickson

105 plays 0
The string matching problem Almost brute force -> O(mn) worst-case time but usually good in practice unless you are a potato Intuition: interpret strings as numbers…
14. More Hashing

duration 1 hour 15 minutes

14. More Hashing

14. More Hashing

From Jeff Erickson

113 plays 0
Open addressed hashing Fictional analysis: Strongly universal hashing Linear probing and binary probing Analysis of binary probing: full versus popular 2-uniformity and…
13. Hashing

duration 1 hour 13 minutes

13. Hashing

13. Hashing

From Jeff Erickson

180 plays 0
Hash table definitions and standard fiction Deterministic hash functions are stupid. Families of hash functions Uniform (yawn), universal, and strongly universal…
12. Tail inequalities

duration 1 hour 10 minutes

12. Tail inequalities

12. Tail inequalities

From Jeff Erickson

152 plays 0
What are tail inequalities? Markov's inequality: Pr[ X > x ] ≤ E[X} / x Independent random variables Chebyshev: If X is sum of pairwise-independent 0/1…
11. Treaps

duration 1 hour 9 minutes

11. Treaps

11. Treaps

From Jeff Erickson

104 plays 0
Binary search tree (ordered dictionary) operations Treaps: BST with respect to keys + min-heap with respect to priorities Insert, delete, split, and join algorithms;…
10. Midterm review session

duration 1 hour 14 minutes

10. Midterm review session

10. Midterm review session

From Jeff Erickson

126 plays 0
Review session for Midterm 1
9. Matching nuts and bolts

duration 1 hour 15 minutes

9. Matching nuts and bolts

9. Matching nuts and bolts

From Jeff Erickson

166 plays 0
Midterm 1 logistics Rawlins’ nuts and bolts problem Reductions to and from sorting nuts and/or bolts Randomized quicksort! Full-history recurrence Back of the…
8. Discrete probability review

duration 1 hour 16 minutes

8. Discrete probability review

8. Discrete probability review

From Jeff Erickson

163 plays 0
Reflections|Projections! Randomized algorithms: what and why? Discrete sample spaces, good old rock, events, probability, conditional probability Random variables:…
7. Speeding up dynamic programming

duration 1 hour 15 minutes

7. Speeding up dynamic programming

7. Speeding up dynamic programming

From Jeff Erickson

153 plays 0
Finding minimum elements in every row of an array No other information: Brute force O(mn) is optimal Monotone: Minima in higher rows are above/left of minima in later…
6. Revenge of the son of dynamic programming

duration 1 hour 16 minutes

6. Revenge of the son of dynamic programming

6. Revenge of the son of dynamic programming

From Jeff Erickson

172 plays 0
Dynamic programming over directed acyclic graphs: longest path Saving space: Sliding windows Reconstructing structure by walking through memorized data Choudhury and…
5. Even more dynamic programming

duration 1 hour 14 minutes

5. Even more dynamic programming

5. Even more dynamic programming

From Jeff Erickson

182 plays 0
Intuitive sketches of common recursion patterns Dynamic programming in trees: Maximum independent set Memoization is depth-first search; dynamic programming is postorder…
4. More dynamic programming

duration 1 hour 17 minutes

4. More dynamic programming

4. More dynamic programming

From Jeff Erickson

204 plays 0
Longest increasing subsequence, take 2 Tree-shaped DP: The woodcutter's problem
3. Backtracking and dynamic programming

duration 1 hour 16 minutes

3. Backtracking and dynamic programming

3. Backtracking and dynamic programming

From Jeff Erickson

341 plays 0
Example 1: Text segmentation (Interpunctio verborum) A sequence of X's is either nothing or an X followed by a sequence of X's Where does the first word end?…
2. Fast Fourier transforms

duration 1 hour 10 minutes

2. Fast Fourier transforms

2. Fast Fourier transforms

From Jeff Erickson

373 plays 0
Representing polynomials as coefficients, roots, or sample values Converting from coefficients to samples is a linear transformation Divide-and-conquer via collapsible…
1. Administrivia, recursion

duration 1 hour 10 minutes

1. Administrivia, recursion

1. Administrivia, recursion

From Jeff Erickson

647 plays 0
Technical difficulties Welcome, introduction, about this class, important course policies Recursion: Tower of Hanoi Recursion: Karatsuba multiplication

Search for ""

Public, Restricted

28 Media

1 Members

Managers:: Jeff Erickson