Syllabus

Topic 0: Introduction, Simulation and Ad Hoc

Slides

Handout

Homework

Hints

Homework Deadline: 20230831 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: rubberducking
 Dynamic: log, breakpoints, fuzzing

Topic 1: Scan Line: Discretization, Monotonic Stack/Queue

Slides

Handout

Homework

Hints

Homework Deadline: 20230907 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: 20230914 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 subranges
 Assemble a query of range \( a[l..l+len] \) with two intersecting subranges 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: 20230921 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: 20230928 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
