|
Syllabus
|
|
Topic 0: Introduction, Simulation and Ad Hoc
|
Slides
|
Handout
|
Homework
|
Hints
|
Homework Deadline: 2023-08-31 23:59 EDT
- Logistics
- How to think about a problem:
- Observations (drawing connections from problem to some technique we know)
- Techniques (concrete technique for a fixed problem)
- How to code a problem:
- The concise code problem: how to write the most concise code?
- How to debug:
- Static: rubber-ducking
- Dynamic: log, breakpoints, fuzzing
|
|
Topic 1: Scan Line: Discretization, Monotonic Stack/Queue
|
Slides
|
Handout
|
Homework
|
Hints
|
Homework Deadline: 2023-09-07 23:59 EDT
- Prefix Sum / Differential
- Treating interval as +a at the start and -a at the end
- Data Structures with Scan Line
- Set, map, monotonic queue/stack
- 'Usefulness' and 'potential' of elements
- Classic problems
- Interval Cover: greedy, sort by left, then always take the most right interval
- Largest Rectangle in Histogram: monotonic queue, keep track of useful left bounds of
rectangle
|
|
Topic 2: Range Query: RMQ and Fenwick Tree
|
Slides
|
Handout
|
Homework
|
Hints
|
Homework Deadline: 2023-09-14 23:59 EDT
- Range Query: a combination of
- Find out what \( a[i] \) is (point query)
- Find out what \( \max(a[l..r]), \min(a[l..r]), \sum(a[l..r]), \ldots \) is (range query)
- Set \( a[i] \) to something (point modification)
- Set \( a[l..r] \) to \( x \) / Add \( x \) to \( a[l..r] \) / \( \ldots \) (range
modification)
- Analyze the problem, find out the operations necessary before deciding what technique to use!
- RMQ: capable of querying \( \max(a[l..r]) \) only.
- Array of size \( N \times \log N \), with each row denoting length \( 2^0, 2^1, \ldots,
2^{\log N} \)
- Populate the array with doubling technique, i.e. use data of length \( 2^i \) to compute \(
2^{i+1} \)
- Assemble a query of range \( a[l..l+len] \) with log many sub-ranges
- Assemble a query of range \( a[l..l+len] \) with two intersecting sub-ranges if range
intersection is permissible (the case of RMQ)
- Other Applications of Doubling
- Fast Power
- LCA
- Other ad hoc data (e.g. Surveillance from ICPC 2014)
- Fenwick Tree: capable of querying \( \sum(a[l..r]) \) and modifying a single element
|
|
Topic 3: Range Query: Segment Tree and Lazy Update
|
Slides
|
Handout
|
Homework
|
Hints
|
Homework Deadline: 2023-09-21 23:59 EDT
- Segment Tree
- Intuition: Square Root Decomposition
- Summary of Range Query Data Structure
- Array
- Prefix Sum
- RMQ & Sparse Table
- Fenwick Tree
- Segment Tree
- Pick the appropiate data structure for the problem!
|
|
Topic 4: Geometry: Basics, Convex Hull, Convex Optimization
|
Slides
|
Handout
|
Homework
|
Hints
|
Homework Deadline: 2023-09-28 23:59 EDT
-
Template: https://github.com/zhtluo/LMR
-
Computational Geometry Basics
-
Precision Problem and EPS
-
Everything is a vector!
-
Dot and Det product
-
Geometry and DP Optimization
-
Slope Trick / Convex Optimization / Decision Monotonicity
|