Computer Science Learning Portal

Module 1: Graph Matching and Network Flow Algorithms

Topics Covered

Lecture 1: (11 slides) Teacher/course motivating problem with the bipartite diagram, matching definitions, Hall's theorem, augmenting paths (with the original matching/path figures embedded), the maximal-matching algorithm, the BFS-style level-graph method for finding augmenting paths, complexity analysis, applications, exercises (with the bipartite/K_{m,n} figures), and references.

Lecture 2: (14 slides) Transportation-network intro, flow network definition, flow constraints, a worked capacity/flow example, cuts, the max-flow min-cut theorem, residual-graph definitions, blocking flow & Dinitz's algorithm, the Ford–Fulkerson algorithm, the residual-capacity formula, a full flow → residual → augmented-flow worked example, exercises, and references.

Lecture 3: (15 slides) Introduction to computational geometry, the half-plane-intersection problem, the divide-and-conquer algorithm, its O(n log n) running-time analysis, convex set definitions (geometric and formal), examples, a worked convexity-verification example, convex functions, intersections/unions, the Jordan curve theorem, testing polygon convexity, and the point-in-polygon ray-casting algorithm.

• 1. Graph Algorithms (Matchings)
• 2. Graph Algorithms (Network Flows)
• 3. Geometric Algorithms (Convex Sets, Divide & Conquer Algorithms)

Module 2: Geometrical Algorithms

Topics Covered

Lecture 4: (15 slides): Introduction, convex hull definitions & d-faces, the rubber-band picture, Graham scan, gift wrapping, the closest-pair problem, divide-and-conquer closest pair, Voronoi diagram definitions, construction & a worked shop-siting illustration, Voronoi applications, line arrangements (vertex/edge/face counts), the three arrangement equivalence classes, exercises, and references.

Lecture 5: (10 slides): Sequential-vs-parallel intro (with the prefix-sum example), the RAM model, the three multiprocessor machine models, the PRAM model, its read/write mode variants (ER/EW/CR), bus/mesh/hypercube networks, multistage & fat-tree networks, binary-tree networks and the fat-tree fix, and references.

Learning Resources

• 4. Geometric Algorithms (Convex Hull, Voronoi Diagrams)
• 5. Parallel Algorithms

Module 3: Parallel Algorithms

Topics Covered

Lecture 6: (14 slides):Work/depth/parallelism intro, the circuit model (with your original diagram), the vector model, the language model & cost assignment, designing parallel algorithms (torus filtering example), global operations part 1 (broadcast/reduction/shift), part 2 (sort/merge/associative read-write), divide-and-conquer via parallel mergesort, sorted-array search, the parallel binary search algorithm -- complexity analysis, exercises (with your work-depth-models figure), and references.

Lecture 7: (14 slides): Deterministic-vs-randomized goals, Monte Carlo vs. Las Vegas, applications, randomized sequential search, why-randomize (simplicity via quicksort, speed via zero-polynomial testing with the polynomial-curve figure), the file-comparison XOR-check example, the hiring-problem algorithm, worst-case vs. probabilistic analysis, "Find the Lady," the RAM model and review questions, exercises, and references.

Learning Resources

• 6. Parallel Algorithms
• 7. Randomized Algorithms

Module 4: Randomized and Probabilistic Algorithms

Topics Covered

Lecture 8: (14 slides): Random variable definitions (dice example), formal modelling of a randomized algorithm, the coin-flip indicator-variable example, events & the probability mass function, expectation and linearity, the alphabet-cards worked example, why randomization works, the Max-Cut problem. The Max-Cut proof, randomized sorting (algorithm RQS), counting comparisons via linearity, exercises, and references.

Lecture 9: (13 slides) Why approximate, α-approximation definitions, the vertex cover problem, the integer program vs. LP relaxation, the fractional-vs-integral 3-cycle example, the LP rounding algorithm and rule, its factor-2 proof, the primal-dual method and dual LP, the primal-dual algorithm, its loop invariants, its factor-2 correctness proof, and references.

Learning Resources

• 8. Random Variables
• 9. Approximation Algorithms

Module 5: Approximation Algorithms and Advanced Data Structures

Topics Covered

Lecture 10: (14 slides): Splay tree introduction, advantages/disadvantages, splay-step anatomy, and the three splay-step diagrams (zig, zig-zig, zig-zag), correctly-connected rotation diagrams natively — join/split operations, insertion/deletion, persistent data structures (partial/full/confluent/ephemeral), a persistent-tree path-copying example, k-d trees, k-d tree construction and operations, and references.

Learning Resources

• 10. Self-Adjusting Data Structures