Search for tag: "cs598jge"

27 Media

∞. Chasing puppies duration 1 hour 16 minutes ∞. Chasing puppies ∞. Chasing puppies	∞. Chasing puppies a. The puppy problem b. Special cases: blind vs. stubborn, puppies vs. guppies c. Configurations and the puppy diagram (Look, actual code!) d. Counting essential critical cycles e. Rubber bands on a… cs598jge From Jeff Erickson 24 plays 0 Date of creation 12/8/2020 12:00 AM
26. Planarizing and separating surface maps duration 1 hour 4 minutes 26. Planarizing and separating surface maps 26. Planarizing and separating surface maps	26. Planarizing and separating surface maps a. Shortest non-separating cycles b. Menger's theorem c. Planarizing with at most g cycles via cycles: O(sqrt{gn} log g) d. Greedy tree-cotree again again e. Planarixing via level slicing and… cs598jge From Jeff Erickson 10 plays 0 Date of creation 12/3/2020 12:00 AM
25. Approximation schemes via slicing duration 1 hour 14 minutes 25. Approximation schemes via slicing 25. Approximation schemes via slicing	25. Approximation schemes via slicing a. Carvings b. Branch decompositions c. Dynamic programming c. Radial and medial maps d. Radial greedy tree-cotree decomposition e. Branchwidth ≤ diameter ≠ 1 f. Low-diameter slicing cs598jge From Jeff Erickson 18 plays 0 Date of creation 12/1/2020 12:00 AM
24. Maximum flows in surface maps duration 1 hour 18 minutes 24. Maximum flows in surface maps 24. Maximum flows in surface maps	24. Maximum flows in surface maps a. 1-chains = pseudoflows, circulations b. 2-chains = face potentials = Alexander numberings, boundary circulations c. Real-homology d. cycles, cocycles, and homology annotations e. Duality between… cs598jge From Jeff Erickson 25 plays 0 Date of creation 11/19/2020 12:00 AM
23. Minimum cuts in surface maps duration 1 hour 17 minutes 23. Minimum cuts in surface maps 23. Minimum cuts in surface maps	23. Minimum cuts in surface maps a. Even subgraphs, cycle space, edge cuts, and cut spaceb. Planar duality c. Boundary subgraphs d. Z2-homology e. Systems of cycles and cocycles f. Homology anotations g. Dual of minimum cut is… cs598jge From Jeff Erickson 25 plays 0 Date of creation 11/17/2020 12:00 AM
22. Shortest nontrivial cycles in surfaces duration 1 hour 14 minutes 22. Shortest nontrivial cycles in surfaces 22. Shortest nontrivial cycles in surfaces	22. Shortest nontrivial cycles in surfaces a. Planarization b. Contractible versus separating c. Thomassen's 3-path condition ⇒ O(n³) time d. Greedy tree-cotree decompositions e. Greedy (reduced) cut graph ⇒ O(n² log… cs598jge From Jeff Erickson 43 plays 0 Date of creation 11/12/2020 12:00 AM
21. Homotopy testing on surfaces duration 1 hour 16 minutes 21. Homotopy testing on surfaces 21. Homotopy testing on surfaces	21. Homotopy testing on surfaces a. Modeling curves on surfaces as walks in maps b. Spur and face moves c. System of loops d. Contractible in surface = closed in universal cover e. Dehn's lemma f. Dehn's algorithm g.… cs598jge From Jeff Erickson 50 plays 0 Date of creation 11/10/2020 12:00 AM
20. Surface Classification duration 1 hour 14 minutes 20. Surface Classification 20. Surface Classification	20. Surface Classification a. Kerékjártó-Rado theorem (Every surface supports a map.) b. Tree-cotree decompositions and systems of loops c. Detaching handles by contracting two-sided loops d.… cs598jge From Jeff Erickson 29 plays 0 Date of creation 10/29/2020 12:00 AM
19. Surface Maps duration 1 hour 16 minutes 19. Surface Maps 19. Surface Maps	19. Surface Maps a. 2-manifolds b. Polygonal schemata c. Cellular embeddings and rotation systems d. Orientation and genus e. Band decompositions f. Reflection systems g. Deletion and contraction in reflection systems cs598jge From Jeff Erickson 30 plays 0 Date of creation 10/27/2020 12:00 AM
18. Faster minimum cuts and maximum flows duration 1 hour 17 minutes 18. Faster minimum cuts and maximum flows 18. Faster minimum cuts and maximum flows	18. Faster minimum cuts and maximum flows a. FR-Dijkstra summary b. O(n log log n) minimum cut overview c. Technical details d. Planar maximum flow history e. Venkatesan's duality between flows and shortest paths f. Parametric shortest… cs598jge From Jeff Erickson 22 plays 0 Date of creation 10/23/2020 12:00 AM
17. FR-Dijkstra and faster minimum cuts duration 1 hour 14 minutes 17. FR-Dijkstra and faster minimum cuts 17. FR-Dijkstra and faster minimum cuts	17. FR-Dijkstra and faster minimum cuts a. Monge heap operations: Revealing columns and hiding rows b. Range minimum queries c. Monge heap implementation d. High-level overview of FR-Dijkstra e. Monge structure of nice r-divisions f.… cs598jge From Jeff Erickson 27 plays 0 Date of creation 10/20/2020 12:00 AM
16. Planar minimum cuts duration 1 hour 16 minutes 16. Planar minimum cuts 16. Planar minimum cuts	16. Planar minimum cuts a. Duality: Shortest essential cycle b. Crosses shortest path at most once c. Slicing into a shortest-path problem d. Easy algorithms: Brute force and MSSP e. Divide-and-conquer: O(n log k) time f.… cs598jge From Jeff Erickson 23 plays 0 Date of creation 10/15/2020 12:00 AM
15. Planar shortest paths duration 1 hour 17 minutes 15. Planar shortest paths 15. Planar shortest paths	15. Planar shortest paths a. Dense distance graphs b. Improving Dijkstra to O(n log log n) time c. Repricing d. Nested dissection e. Monge arrays and SMAWK f. Planar distances are (almost) Monge) g. Shortest paths with… cs598jge From Jeff Erickson 25 plays 0 Date of creation 10/13/2020 12:00 AM
14. Planar separators duration 1 hour 15 minutes 14. Planar separators 14. Planar separators	14. Planar separators a. Tree separators b. Fundamental cycle separators c. BFS level separators d. Face-level cycles e. Short cycle separators f. Good r-divisions cs598jge From Jeff Erickson 33 plays 0 Date of creation 10/9/2020 12:00 AM
13. Multiple-source shortest paths duration 1 hour 15 minutes 13. Multiple-source shortest paths 13. Multiple-source shortest paths	13. Multiple-source shortest paths a. Problem statement b. Shortest paths and slacks c. Disk-tree lemma and compact output d. Red and blue vertices, active darts e. Dynamic forest data structures f. Summary: O(n) pivots, each in O(log… cs598jge From Jeff Erickson 60 plays 0 Date of creation 10/6/2020 12:00 AM
12. Tutte's spring embedding duration 1 hour 15 minutes 12. Tutte's spring embedding 12. Tutte's spring embedding	12. Tutte's spring embedding a. Tutte drawings b. Physical intuition: energy minimization c. Halfplane lemma d. No degenerate vertex neighborhoods e. No degenerate faces cs598jge From Jeff Erickson 46 plays 0 Date of creation 10/1/2020 12:00 AM
11. Straight-line planar maps duration 1 hour 16 minutes 11. Straight-line planar maps 11. Straight-line planar maps	11. Straight-line planar maps a. Simple triangulation lemma b. Hole filling (Every pentagon is star-shaped) c. Vertex deletion d. Schnyder woods e. Grid embedding cs598jge From Jeff Erickson 38 plays 0 Date of creation 9/29/2020 12:00 AM
10. Deletion and contraction duration 1 hour 12 minutes 10. Deletion and contraction 10. Deletion and contraction	10. Deletion and contraction a. Deletion and contraction in abstract graphs b. Spanning trees c. Planar duality: (Σ\e)* = Σ/e d. Implementing deletion and contraction in maps e. Cycle-cut duality f. Tree-cotree… cs598jge From Jeff Erickson 48 plays 0 Date of creation 9/24/2020 12:00 AM
9. Planar graphs and maps duration 1 hour 11 minutes 9. Planar graphs and maps 9. Planar graphs and maps	9. Planar graphs and maps a. What is a graph? (vertices and darts) b. Incidence list and incidence array data structures c. Planar maps: faces, shores, face degree d. Rotation systems e. Stereographic projection f. Planar map… cs598jge From Jeff Erickson 55 plays 0 Date of creation 9/22/2020 12:00 AM
8. Curve homotopy and curve invariants duration 1 hour 11 minutes 8. Curve homotopy and curve invariants 8. Curve homotopy and curve invariants	8. Curve homotopy and curve invariants a. Steinitz's contraction algorithm (spindle removal) b. Rotation number: Smiles minus frowns c. Rotation number: Initial winding and writhe d. Defect cs598jge From Jeff Erickson 26 plays 0 Date of creation 9/18/2020 12:00 AM
7. Unsigned Gauss codes duration 1 hour 7 minutes 7. Unsigned Gauss codes 7. Unsigned Gauss codes	7. Unsigned Gauss codes a. Winding numbers and Alexander numbering b. Gauss smoothing and Seifert decompositions c. Gauss' parity condition and the Nagy graph d. Dehn smoothing and Euler tours e. Tree-onion… cs598jge From Jeff Erickson 43 plays 0 Date of creation 9/15/2020 12:00 AM
6. Generic curves in the plane duration 1 hour 14 minutes 6. Generic curves in the plane 6. Generic curves in the plane	6. Generic curves in the plane a. Definitions: transverse intersection, generic curve (immersion) b. Isotopy c. Image graphs and their faces d. Homotopy moves e. Planarity: F = V+2 f. Gauss codes and Gauss diagrams g. Tracing… cs598jge From Jeff Erickson 44 plays 0 Date of creation 9/10/2020 12:00 AM
5. Shortest homotopic paths duration 1 hour 13 minutes 5. Shortest homotopic paths 5. Shortest homotopic paths	5. Shortest homotopic paths a. Shortest paths in simple polygons b. Crossing sequences via triangulation c. Dual tree of a polygon triangulation d. The funnel algorithm e. Adding holes: Nothing changes! f. Universal cover:… cs598jge From Jeff Erickson 42 plays 0 Date of creation 9/8/2020 12:00 AM
4. Faster homotopy testing duration 1 hour 16 minutes 4. Faster homotopy testing 4. Faster homotopy testing	4. Faster homotopy testing a. Quadratic lower bound? b. Trapezoidal decomposition c. Bentley-Ottmann sweep-line algorithm d. Horizontal and vertical ranks e. Rectification f. Sliding brackets g. Overall time analysis cs598jge From Jeff Erickson 51 plays 0 Date of creation 9/3/2020 12:00 AM

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois