Syllabus

Topic 0: Introduction, Simulation and Ad Hoc

Slides

Handout

Homework

Hints

Homework Deadline: 20230831 23:59 EDT
 Logistics
 Observations serve as a means to comprehend a problem and simplify it into a more manageable
form.
 Intuition: Are we able to visualize the problem? Could we develop a
straightforward bruteforce solution?
 Insight: Can we identify any unique or nonobvious properties within the
problem?
 Exploration: Is it possible to leverage these properties to reframe the problem into a
different context?
 Verification: Is the reframed problem recognizable? Can we solve it using
techniques we're familiar with?
 Enhanced observational skills facilitate more efficient connections between a problem and
known techniques.
 Techniques are specialized methods or codes used to solve welldefined problems.
 Familiarity with a broader array of techniques provides more reference points for
problemsolving.
 Both observational acumen and technical skill are essential for effective problemsolving.
 When it comes to coding, one oftenneglected focus should be on optimal conciseness, aiming to
write the most streamlined code possible for the problem at hand.
 For debugging, we have a couple of options.
 Static methods include techniques like rubberduck debugging to help us think through the
problem.
 Dynamic methods, on the other hand, involve using logs, setting breakpoints, and applying
fuzz testing to identify issues.

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

Slides

Handout

Homework

Hints

Homework Deadline: 20230907 23:59 EDT
 We can use the prefix sum/differential technique to solve easy range query problems.
 One common technique is converting an interval into two events: \( +a \) at the start and \( a
\) at the end.
 We can use various data structures together with the sweep line technique, such as set, map,
monotonic queue/stack, etc.
 It is helpful to consider the 'usefulness' and 'potential' of every element when constructing an
algorithm.
 Classic problems include interval cover and largest rectangle in histogram.

Topic 2: Range Query: RMQ and Fenwick Tree

Slides

Handout

Homework

Hints

Homework Deadline: 20230914 23:59 EDT
 Range query encompasses various operations on a list, such as:
 Point Query: Retrieve the value of \( a[i] \).
 Range Query: Calculate \( \max(a[l..r]), \min(a[l..r]), \sum(a[l..r]), \ldots \).
 Point Modification: Update \( a[i] \) to a specific value.
 Range Modification: Apply operations like setting \( a[l..r] \) to \( x \), adding \( x \)
to \( a[l..r] \), etc.
 We can use the sparse table to query \( \max(a[l..r]) \) in \( O(\log n) \).
 We can use the Fenwick tree to query \( \sum(a[l..r]) \) and update a single point in \( O(\log
n) \).

Topic 3: Range Query: Segment Tree and Lazy Update

Slides

Handout

Homework

Hints

Homework Deadline: 20230921 23:59 EDT
 Intuition of the segment tree comes from square root decomposition.
 Segment tree is the swiss knife that is effective at all range query problems. Nevertheless, it
suffers from implementation complexity and poor constant factor.
 We have learnt a variety of range query data structures:
 Array
 Prefix Sum
 Sparse Table
 Fenwick Tree
 Segment Tree
 We should pick the appropiate data structure based on the problem.

Topic 4: Geometry: Basics, Convex Hull, Convex Optimization

Slides

Handout

Homework

Hints

Homework Deadline: 20230928 23:59 EDT
 Reference and template is important to solve a geometry problem. My reference is available at https://github.com/zhtluo/LMR.
 We can handle the precision issues in geometry by setting an EPS.
 Dot and det products are building blocks in geometry problems.
 The slope trick, convex optimization and decision monotonicity are common techniques in
optimizing a DP problem.

Topic 5: Number Theory: Prime Numbers, GCD, exGCD

Slides

Handout

Homework

Hints

Homework Deadline: 20231006 23:59 EDT
 We can find all prime numbers within \( n \) with the linear sieve.
 We can compute \( x^a \) within \( O(\log a) \) with binary exponentiation.
 Fermat's Little Theorem allows us to compute a modular inverse with binary exponentiation,
assuming the modular is prime.
 Extended GCD allows us to compute a modular inverse with any modular.

Topic 6: Combinatorics: Counting, InclusionExclusion, Linear Recurrence

Slides

Handout

Homework

Hints

Homework Deadline: 20231012 23:59 EDT
 Basic building blocks for a counting problem include permutation \( P(n, m)=\frac{n!}{(nm)!} \)
and combination \( C(n, m)=\binom{n}{m}=\frac{n!}{(nm)!m!} \).
 The stars and bars trick is a common technique in building a solution.
 we can use the inclusionexclusion principle to transform a 'exactly \( k \) times' problem to a
set of 'at most \( i \) times \( (0 \le i \le k) \)' problems.
 We can find the \( n \)th termn of a linear recurrence by constructing a matrix and use binary
exponentiation to obtain a complexity of \( O(k^3\log n) \).

Topic 7: Tree: LCA, DP, DFS Order

Slides

Handout

Homework

Hints

Homework Deadline: 20231012 23:59 EDT
 We covered two types of problems: one that cares about subtrees and one that cares about paths
on trees.
 For the problems about subtrees, one approach is to consider the DFS order (inorder) of the
tree: every subtree is an interval on the DFS order.
 For the problems about paths, one approach is to take aprt the paths between \( (u, v) \) to \(
(u, w) \) and \( (w, v) \), where \( w \) is the LCA of \( (u, v) \).
 Two archetypes of dynamic programming on the tree are:
 Finding the size of all subtrees, in which for every node \( x \) we care about all its
subtrees.
 Finding the height of all nodes, in which for every node \( x \) we care about the value on
its parent.
 Real problems require a combination of the above techniques and is often done by traversing the
tree twice. During the first traversal we consider something about the subtree rooted at that
node. During the second traversal we consider the impact of the parent on that node.

Topic 8: Graph: Matching, Network Flow

Slides

Handout

Homework

Hints

Homework Deadline: 20231026 23:59 EDT
 There are different algorithms to solve the network flow problem: Dinic, ISAP, Pushrelabel,
Primal Dual, etc.
 It is less important to fully grasp the inner working of the algorithms of this topic (which
hopefully we already did in CS 381).
 Instead, try grabbing a template online or from my codebase (https://github.com/zhtluo/LMR/tree/master/src/graph/flow)
and use it to solve the problems.
 Network flow problems are hard to identify. Some signs are a relatively small \( n \) (100 to
1000) and being hard to solve otherwise.
 Network flow problems have three catagories: max flow, min cut and min cost.
 We can use a flow template to solve bipartite matching problems, but dedicated algorithms
(HopcroftKarp, Hungarian, etc.) are usually faster by a constant factor.

Topic 9: String: Hash, KMP, AC Automata

Slides

Handout

Homework

Hints

Homework Deadline: 20231102 23:59 EDT
 Two approaches are available to solve string matching: rolling hash and automata.
 Rolling hash is considered secure if implemented correctly.
 Automata approaches such as KMP and AC automata are useful in dynamic programming.
 Other approaches are also available: suffix array/automata, palindrome tree, etc. They are topics for CP3 and available to pursue at your own interest.

Topic 10: String: DP, Bitmasking, Plugging

Slides

Handout

Homework

Hints

Homework Deadline: 20231109 23:59 EDT
 Review: two common ways to construct a DP is to observe the transition and the substructure.
 In a digit DP, we treat the number as a string and do DP on its prefix.
 In a bitmask DP, we compress a state into a number.
