Weekly Topic: Algorithmic Schemas

This year, we try to unite divide & conquer, greedy and searching over the state space under the topic of algorithmic schemas, as they refer to more of algorithmic thinkings than concrete algorithms.

Problem Set

• Practice problem 1 (yet to come)
• …

Divide & Conquer

• Closest Pair: Given $n$ ($n \leq 10^6$) points in a 2-D plane, find the pair of points that are closest to each other.

Binary Search

Suppose you have a sorted array, and you want to find whether a certain value $x$ is in the array. We can start at the middle location, and check whether the value is $x$. If the value $v$ is $x$, then we are done, else we can move to the left or right side.

Estimate the Time Complexity

It might be important to notice the time complexity of the divide and conquer algorithm.

Master Theorem

• $T(n) = k\cdot T(\frac{n}{k}) + t(n)$
• $⇒ T(n) = k^\alpha \cdot T(1) + \displaystyle\sum^{\alpha - 1}_{i=0}(k^i\cdot t(\frac{n}{k^i}))$
• $⇒T(n)=\log_k(n)=k^\alpha+ \begin{cases} \text{if } t(\frac{n}{k})=O(1), \displaystyle\sum^{\alpha - 1}_{i=0}(k^i) \approx n ⇒O(n)\\ \text{if }t(\frac{n}{k})=O(n), \displaystyle\sum^{\alpha - 1}_{i=0}(n) \approx \alpha n⇒O(n\log n) \end{cases}$

Greedy

• be careful

Searching

• Complete search (all permutations)/state space traversal (DFS, BFS) + other topics (DP, computational geometry, graph…)/data structure (priority queue, bitmask, segment tree, …)