Strategy
guides.

Dynamic Programming — Lecture Notes

1. What Is Dynamic Programming?

• Dynamic programming (DP) is an algorithmic paradigm for solving problems that have overlapping subproblems and optimal substructure.
• Overlapping subproblems: the subproblems are smaller versions of the original problem.
• Optimal substructure: the optimal solution to a larger problem contains the optimal solutions to its smaller problems, so the larger problem can be derived from the smaller ones.

2. Example: Climbing Stairs

A staircase has $n$ steps. Each move, you can climb 1 or 2 steps. How many distinct ways are there to reach the top?

• Original problem: the number of ways to climb $n$ steps.
• Subproblems: the number of ways to climb $n-1$ steps, $n-2$ steps, $n-3$ steps, …
• Optimal substructure: can the optimal solutions of the subproblems yield the optimal solution of the original problem?
  • To reach step $n$, you must arrive either from step $n-1$ (one step) or from step $n-2$ (one move of two steps). Therefore:

• No aftereffect (Markov property): “the future is independent of the past.” We only need to consider how to get to step $n$ now; we don’t care how we previously reached step $n-1$ or $n-2$ — we just use their computed results. The optimal substructure satisfies the no-aftereffect property.

Variations (exercises)

1. A staircase has $n$ steps; each move you can climb 1, 2, or 4 steps. How many distinct ways are there?
2. A staircase has $n$ steps; each move you can climb 1 or $k$ steps. How many distinct ways are there?
3. A staircase has $n$ steps; each move you can climb 1, 2, …, $k$ steps. How many distinct ways are there?

3. Steps for DP Analysis

1. Decompose into subproblems: break the original problem into subproblems and find the relationships between them.
2. Define the state: a “state” refers to a distinct subproblem. E.g., earlier, $dp[x]$ denoted the number of ways to climb $x$ steps, so $x$ is the state. Defining the state means determining how many dimensions of known variables the problem needs. Typically it takes a form like “the max value / min value / number of ways for the first $n$ items when xxx equals $m$.”
3. State transition equation: how states (subproblems) transition between each other — i.e., which states a given state is derived from, or which states it can transition to.
4. Implementation: compute the final state (the answer) using iteration (bottom-up loops), memoized search (top-down recursion), etc.

4. Longest Increasing Subsequence (LIS)

Problem

• Given a list of length $n$, find its longest increasing subsequence.
• Subsequence: a new sequence formed by deleting some elements of the original sequence without changing the relative order of the remaining elements.
• Example: in [1, 3, 4, 2, 5, 3, 7, 2], [1, 4, 2, 7] is a subsequence; the longest increasing subsequence is [1, 3, 4, 5, 7].

What should the state be?

1. Option 1: the LIS of the first $i$ numbers?
   • This state does not support a state transition, because we don’t know what the actual subsequence is (in particular, what its last element is).
2. Option 2: the LIS ending at the $i$-th number. ✅

Transition

(with $dp[i] = 1$ if no such $j$ exists). The final answer is $\max_i dp[i]$.

Worked example

Maximum $dp$ value is 5 → LIS length 5 ([1, 3, 4, 5, 7]).

5. Longest Common Subsequence (LCS)

Problem

• Given an array $a$ of length $N$ and an array $b$ of length $M$, find their longest common subsequence.
• Common subsequence: a subsequence contained in both $a$ and $b$.

Formulation

• State: $dp[i][j]$ = length of the LCS of the first $i$ elements of $a$ and the first $j$ elements of $b$.
• Boundary: $dp[0][0] = dp[\cdot][0] = dp[0][\cdot] = 0$
• State transition equation:

Worked example

• a = [1, 3, 4, 2, 5]
• b = [1, 4, 3, 5, 2]

DP table (rows = prefix length $i$ of $a$, columns = prefix length $j$ of $b$):

(Bold cells mark the backtracking path.)

Recovering the actual subsequence

Start from $(n, m)$ and walk backward:

• If moving up or left keeps the $dp$ value unchanged, move in that direction.
• Otherwise, move diagonally up-left and record that element as part of the subsequence.

For the example above, backtracking yields the LCS [1, 3, 2] (length 3).

1. What Is Breadth-First Search?

Core idea: expand level by level

• Breadth-first search (BFS) is the other classic graph traversal algorithm.
• Starting from a source vertex, it first visits all of its immediate neighbors — these form the first level.
• Then it visits, in order, all not-yet-visited neighbors of the first-level nodes — these form the second level.
• The process resembles the ripples spreading out when a stone is dropped into water: it expands outward one level at a time until every reachable node has been visited.

Key data structure: the queue

BFS makes perfect use of a queue’s first-in, first-out (FIFO) property to guarantee level-by-level traversal order.

DFS vs. BFS

2. Implementing BFS on a Graph

Core logic: queue and marking.

1. Create a queue and enqueue the starting node start_node.
2. Create a visited array and mark start_node as visited.
3. While the queue is not empty, repeat:
   • Pop a node u from the front of the queue.
   • Visit u (e.g. print it).
   • Iterate over all neighbors v of u:
     • If v has not been visited, mark it as visited and enqueue it.

from collections import deque

def bfs(start_node, adj, visited):
    q = deque([start_node])
    visited[start_node] = True

    while q:
        u = q.popleft()
        print(u, end=" ")

        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

# --- build the graph and start BFS ---
N = 6
adj = [[] for _ in range(N)]
edges = [(0,1), (0,2), (1,3), (1,4),
         (2,5), (3,4)]
for u, v in edges:
    adj[u].append(v); adj[v].append(u)

visited = [False] * N
# start from an arbitrary vertex, 0
bfs(0, adj, visited)

Output

0 1 2 3 4 5

Note: a node is marked visited at enqueue time, not at dequeue time. This prevents the same node from being pushed into the queue more than once.

3. Walkthrough of the BFS Process

Graph: 6 vertices with edges 0-1, 0-2, 1-3, 1-4, 2-5, 3-4.

Visit order: 0 1 2 3 4 5

4. Application: Shortest Paths in an Unweighted Graph

Core property

One of the most important applications of BFS is solving the shortest-path problem in unweighted graphs.

• A BFS from source s visits nodes exactly in order of increasing distance (number of edges) from s.
• The path taken when a node v is reached for the first time is necessarily a shortest path from s to v.
• This holds because BFS’s level-by-level expansion guarantees that every node at distance less than d has already been visited before any node at level d is explored.

Implementation: computing distances

from collections import deque

def bfs_shortest_path(start_node, N, adj):
    dist = [-1] * N          # -1 means unreachable
    dist[start_node] = 0
    q = deque([start_node])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:        # if v has not been visited
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

# graph definition is the same as on the previous page
# start from node 0
distances = bfs_shortest_path(0, N, adj)
print(distances)

Output

[0, 1, 1, 2, 2, 2]

Explanation

The returned list gives the shortest distance (in edges) from the source 0 to each vertex:

• dist[0] = 0 (itself)
• dist[1] = 1 (0→1)
• dist[2] = 1 (0→2)
• dist[3] = 2 (0→1→3)
• dist[4] = 2 (0→1→4)
• dist[5] = 2 (0→2→5)

Here the dist array doubles as the visited marker: a value of -1 means “not yet reached.”

5. Programming Exercise: 01 Matrix

Problem

Implement a function update_matrix(mat) that takes a matrix mat of 0s and 1s and returns a new matrix of the same size in which each cell holds the distance from the corresponding element of mat to the nearest 0. The distance between two adjacent elements is 1.

Input

mat = [
  [0,0,0],
  [0,1,0],
  [1,1,1]
]

Output

[
  [0,0,0],
  [0,1,0],
  [1,2,1]
]

Idea: multi-source BFS

This can be seen as a shortest-path problem. Think of it in reverse: instead of having each 1 search for its nearest 0, treat all the 0s as sources, run a single BFS starting from all of them simultaneously, and compute the shortest distance over which they spread to each 1.

Reference solution

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                q.append((r, c))
                dist[r][c] = 0
    dirs = [(0,1), (0,-1), (1,0), (-1,0)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
                    and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

1. What Is a Graph?

Concept: From Trees to Graphs

• A graph can be understood as an extension and generalization of the tree structure. In fact, a tree is just a special kind of graph.
• A graph consists of a set of vertices and a set of edges. Each edge connects a pair of vertices in the graph.
• Graphs can model more complex real-world relationships, and are no longer restricted to the hierarchical relationships of a tree.

Applications of Graphs

• Social networks: individuals or organizations are vertices; the social connections between them are edges.
• Maps and navigation: key locations (intersections, landmarks) are vertices; roads are edges.
• Computer networks: computers or routers are vertices; network connections are edges.

2. Key Terminology

Undirected Graph

Edges have no direction. If there is an edge between vertices A and B, we can travel from A to B and also from B to A.

Directed Graph

Edges have a direction and are called arcs. If there is an arc pointing from A to B, we can only travel from A to B, not from B to A.

Other Important Terms

• Weighted graph: edges or vertices carry an associated numeric value called a weight. Common cases are edge weights (e.g. road length on a map) and vertex weights (e.g. a city’s population).
• Degree: in an undirected graph, the number of edges connected to a vertex. In a directed graph, it splits into in-degree and out-degree.
• Path: the sequence of vertices traversed in going from one vertex to another.
• Cycle: a path whose start and end vertex are the same.

3. Key Terminology (continued)

Connected Graph

In an undirected graph, if a path exists between every pair of vertices, the graph is connected.

Example: a graph with components A–B–C (a triangle) and D–E is not connected — it has two connected components.

Strongly Connected Graph

In a directed graph, if for every pair of vertices u and v there is a path from u to v and a path from v to u, the graph is strongly connected.

Example: A → B → C → A is strongly connected.

Complete Graph

In an undirected graph, every pair of distinct vertices is joined by exactly one edge.

Self-Loops and Simple Graphs

• Self-loop: an edge connecting a vertex to itself.
• Multiple edges: more than one edge between the same pair of vertices.
• Simple graph: a graph with no self-loops and no multiple edges. The vast majority of graphs discussed in competitive programming are simple graphs.

4. Representation (1): Adjacency Matrix

Idea

Use a two-dimensional array (matrix) matrix to represent the graph. If there is an edge between vertices i and j, then matrix[i][j] is 1 (or the weight value); otherwise it is 0.

Code

N = 5
matrix = [[0] * N for _ in range(N)]
edges = [(0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1  # undirected graph

Matrix Representation

Pros and Cons

• Pros: simple to implement; checking whether an edge exists between two vertices takes $O(1)$ time; convenient for using matrix operations to analyze graph properties (e.g. counting the number of paths).
• Cons: space complexity is $O(N^2)$, which is very wasteful when there are many vertices but few edges (a sparse graph); iterating over all neighbors of one vertex takes $O(N)$ time.

5. Representation (2): Adjacency List

Idea

This is the most commonly used method in competitive programming. Use an array of lists adj, where adj[i] is a list storing all vertices adjacent to vertex i.

Code

N = 5
adj = [[] for _ in range(N)]
edges = [(0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

List Representation

Pros and Cons

• Pros: space complexity is $O(N + M)$ (where $M$ is the number of edges), which is very space-efficient for sparse graphs; all neighbors of a vertex can be iterated over efficiently.
• Cons: checking whether an edge exists between two vertices takes $O(\deg(u))$ time.

6. Adjacency List: List vs. Set

Something to Think About

The inner structure of an adjacency list can be implemented with a set instead of a list — each has its own strengths and weaknesses.

Implementation 1: Using a List

# initialization
adj = [[] for _ in range(N)]
# add an edge
adj[u].append(v)
# check whether an edge exists (less efficient)
if v in adj[u]:
    ...

Implementation 2: Using a Set

# initialization
adj = [set() for _ in range(N)]
# add an edge (duplicates removed automatically)
adj[u].add(v)
# check whether an edge exists (efficient)
if v in adj[u]:
    ...

How to Choose?

• Advantages of the set: checking whether an edge exists is $O(1)$; duplicate edges are handled automatically.
• Advantages of the list: preserves the insertion order of neighbors; iteration may be marginally faster.
• Conclusion: if you need frequent edge queries, or the input may contain duplicates, the set is better. Otherwise the list is simpler.

7. Summary: Adjacency Matrix vs. Adjacency List

How to Choose?

• For dense graphs ($M \approx N^2$), the space complexity of the adjacency matrix and adjacency list is comparable. In this case the adjacency matrix is usually simpler to implement.
• For sparse graphs ($M \ll N^2$), always prefer the adjacency list — its $O(N + M)$ space efficiency is a huge advantage.
• Special requirements: if the problem needs to exploit properties of matrix operations (such as counting paths), the adjacency matrix is essential.
• First choice in contests: the overwhelming majority of graphs in algorithm competitions are sparse, so the adjacency list is the default choice. When edge-existence checks are frequent, implement it with a set.

1. DFS: From Trees to Graphs

Core idea recap: follow one path to the end

The core idea of depth-first search (DFS) — explore a branch as deeply as possible, then backtrack when you hit a dead end — carries over to graphs unchanged.

The new challenge: cycles

• Trees are acyclic. We move from a parent node to its children and never “walk back” to the parent. (For unrooted trees, this is avoided by passing the parent node as a parameter.)
• General graphs contain cycles. If we travel from u to v, v may well reach back to u along some other path.
• If this is not handled, DFS will fall into an infinite loop when it hits a cycle, causing a stack overflow.

The solution: mark visited nodes

We need an auxiliary data structure — typically a boolean array visited — to record which nodes have already been visited. Before visiting a new node, check whether it has been visited already.

2. Implementation (1): Connected Graphs

Core logic: mark, then recurse. When visiting a node, first mark it as visited, then recursively visit all of its unvisited neighbors.

# adj:     adjacency list
# visited: array recording whether a node has been visited
def dfs(u, adj, visited):
    visited[u] = True
    print(u, end=" ")   # visit the current node

    for v in adj[u]:
        if not visited[v]:
            dfs(v, adj, visited)

# --- build the graph and start DFS ---
N = 6
adj = [[] for _ in range(N)]
edges = [(0,1), (0,2), (1,3), (1,4),
         (2,4), (3,5), (4,5)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

visited = [False] * N
# start from an arbitrary vertex, 0
dfs(0, adj, visited)

Output

0 1 3 5 4 2

Problem: what if the graph is disconnected?

The code above starts at vertex 0 and therefore only visits vertices connected to 0. Any vertex not connected to 0 will never be reached.

3. Implementation (2): The General Case

Solution: try every vertex as a starting point. Unlike a tree, a graph may not be connected. A DFS from a single vertex may fail to reach every vertex, so we need an outer loop to guarantee that every connected component is visited.

# the dfs function is the same as on the previous page...
def dfs(u, adj, visited):
    # ... (implementation omitted)
    pass

# --- build a disconnected graph and start DFS ---
N = 6                                   # 6 vertices
adj = [[] for _ in range(N)]
edges = [(0,1), (1,2)]                  # component 1: 0-1-2
edges.extend([(3,4), (4,5)])            # component 2: 3-4-5
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

visited = [False] * N
# there may be several connected components, so iterate over all vertices
for i in range(N):
    if not visited[i]:
        # a new connected component has been found
        dfs(i, adj, visited)
        print()                         # newline per component

Output

0 1 2
3 4 5

Key code

for i in range(N):
    if not visited[i]:
        dfs(i, ...)

This loop guarantees that even if the graph consists of several disconnected parts, each part is traversed exactly once and completely.

4. Walkthrough of the DFS Process

The traced graph has 6 vertices with edges 0-1, 0-2, 1-3, 1-4, 3-4, 2-5.

Visit order: 0 → 1 → 3 → 4 → 2 → 5

Note: this walkthrough uses a slightly different edge set than the code in section 2, which is why the printed order there (0 1 3 5 4 2) differs.

5. Application (1): Counting Connected Components

Concept

In an undirected graph, if vertex v is reachable from vertex u, then u and v are said to be connected. A connected component is a maximal connected subgraph.

Example. With edges 0-1, 0-2, 1-2, 3-4, and an isolated vertex 5, the graph has 3 connected components: {0,1,2}, {3,4}, {5}.

Idea and implementation

Use DFS to find all connected components. Iterate over every vertex; if the current vertex has not been visited, a new connected component has been discovered — increment the counter, then run one complete DFS from that vertex to mark every vertex in its component as visited.

def count_components(N, adj):
    visited = [False] * N
    count = 0
    for i in range(N):
        if not visited[i]:
            count += 1
            dfs(i, adj, visited)
    return count

6. Application (2): Detecting a Cycle

Idea (undirected graphs)

During a DFS on an undirected graph, if we move from the current vertex u to a neighbor v that has already been visited and v is not u’s parent (the node that brought us to u), then we have found a cycle.

# u: current node, p: u's parent
def dfs(u, p, adj, visited):
    visited[u] = True
    for v in adj[u]:
        if v == p:          # neighbor is the parent — skip
            continue
        if visited[v]:      # reached a visited, non-parent node
            return True
        if dfs(v, u, adj, visited):   # recurse into unvisited neighbors
            return True
    return False

def check_cycle(N, adj):
    visited = [False] * N
    for i in range(N):
        if not visited[i]:
            # -1 means the starting node has no parent
            if dfs(i, -1, adj, visited):
                return True
    return False

Execution trace

Graph: triangle 0-1, 1-2, 0-2. DFS from 0:

1. dfs(0, -1): visit 1
2. dfs(1, 0): visit 2
3. Among 2’s neighbors, find 0; 0 is already visited and 0 is not 2’s parent (2’s parent is 1)
4. Cycle found!

Difference on Trees

1. Concept

Tree difference means applying the difference-array technique to a tree structure instead of a linear array. It is almost always used together with LCA (lowest common ancestor).

On an array, prefix sum and difference are inverse operations:

prefix sum  <----- inverse ----->  difference

On a tree, the analogue of “prefix sum” is the subtree sum: after all marks have been placed, the true value at node u equals the sum of the difference values over the whole subtree rooted at u. That aggregation is done with a single post-order DFS.

Example tree used throughout

                1
              /   \
             2     3
           / | \   / \
         11  4  5 6   7
                      |
                      8
                     / \
                    9   10

2. Problem 1 — Add 1 to every node on a path

Given a tree, each query adds 1 to all nodes on some path. After all queries, report the final value of every node.

Example: add 1 to every node on the path 6 → 10, i.e. nodes 6, 3, 7, 8, 10.

Doing this by walking the path costs O(path length) per query. With difference + LCA it costs O(1) marks per query (plus the LCA lookup).

Marking rule

For a query on path (x, y) with l = LCA(x, y):

1. Mark +1 at the start x and at the end y.
2. Mark -1 at l.
3. Mark -1 at parent(l).

c[x]           += 1
c[y]           += 1
c[l]           -= 1
c[parent(l)]   -= 1

For the example (x = 6, y = 10, LCA = 3, parent = 1):

node 1 : -1
node 3 : -1
node 6 : +1
node 10: +1

Then the answer at each node is the sum of the difference values in its subtree.

Why it works

+1 at x propagates up to every ancestor of x when subtree sums are taken, and likewise for y. Everything strictly above l would be counted twice (once from each branch), so -1 at l and -1 at parent(l) cancel it: the -1 at l removes one of the two counts at l itself and above, and the -1 at parent(l) removes the remaining count for all strict ancestors of l, leaving l correctly counted once.

3. Problem 2 — Add 1 to every edge on a path

Given a tree, each query adds 1 to all edges on some path. After all queries, report the final weight of every edge.

Example: add 1 to every edge on the path 6 → 10, i.e. edges (3,6), (3,7), (7,8), (8,10).

Marking rule

1. Push each edge’s weight down onto its lower endpoint — an edge (parent, child) is represented by the node child. Every node except the root then corresponds to exactly one edge.
2. Mark +1 at the start x and at the end y.
3. Mark -2 at l = LCA(x, y).

c[x] += 1
c[y] += 1
c[l] -= 2

For the example (x = 6, y = 10, LCA = 3):

node 3 : -2
node 6 : +1
node 10: +1

No parent(LCA) term this time: the edge above the LCA is not on the path, so both upward contributions must be killed at l itself, hence -2 instead of two separate -1s.

Node vs. edge difference at a glance

4. Reference implementation

Binary-lifting LCA template plus node-version tree difference. The final line prints the maximum node value over all k path-increment operations.

import sys
sys.setrecursionlimit(100000)

input = sys.stdin.readline
n, k = map(int, input().split())
G = [[] for i in range(n + 1)]
# deep[u] is the depth of node u
deep = [0] * (n + 1)
# p[u][i] is the node reached by moving 2^i steps up from u
p = [[0] * 21 for i in range(n + 1)]

for _ in range(n - 1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)


def dfs(u, fa):
    # preprocessing
    deep[u] = deep[fa] + 1
    p[u][0] = fa
    for i in range(1, 21):
        p[u][i] = p[p[u][i - 1]][i - 1]
    for v in G[u]:
        if v == fa:
            continue
        dfs(v, u)


def lca(x, y):
    # make sure x is the deeper node
    if deep[x] < deep[y]:
        x, y = y, x

    # lift x with binary lifting until deep[x] == deep[y];
    # enumerate step sizes 2^i from large to small.
    # A step is allowed if the node reached, p[x][i],
    # is still at depth >= deep[y].
    for i in range(20, -1, -1):
        if deep[p[x][i]] >= deep[y]:
            x = p[x][i]

    # now deep[x] == deep[y]
    if x == y:
        return x

    # lift both together: if a 2^i step lands them on the same
    # ancestor, the step is too big; otherwise take it
    for i in range(20, -1, -1):
        if p[x][i] != p[y][i]:
            x, y = p[x][i], p[y][i]
    return p[x][0]


dfs(1, 0)

# ---- tree difference ----
c = [0] * (n + 10)
for i in range(k):
    x, y = map(int, input().split())
    c[x] += 1
    c[y] += 1
    c[lca(x, y)] -= 1
    c[p[lca(x, y)][0]] -= 1


def dfs2(u, fa):
    for v in G[u]:
        if v == fa:
            continue
        dfs2(v, u)
        c[u] += c[v]


dfs2(1, 0)
print(max(c))

For the edge version, replace the marking block with:

for i in range(k):
    x, y = map(int, input().split())
    l = lca(x, y)
    c[x] += 1
    c[y] += 1
    c[l] -= 2

and remember that after dfs2, c[u] is the weight of the edge between u and its parent (c[root] is meaningless).

5. Complexity

Compare with the naive approach of walking every path, which is O(nk) in the worst case.

Lowest Common Ancestor (LCA)

1. Definition

LCA (Lowest Common Ancestor) refers to finding, in a rooted tree, the nearest (deepest) common ancestor of two given nodes x and y.

Using the reference tree below as an example:

• LCA(5, 8) = 1
• LCA(6, 10) = 3

Reference Tree

                1
              /   \
             2     3
           / | \   | \
         11  4  5  6  7
                       |
                       8
                      / \
                     9  10

2. Naive Solution

Steps:

1. Preprocess the depth dep of every node.
2. To find the LCA of x and y:
   • If dep[x] > dep[y]: climb x upward until dep[x] == dep[y].
   • If dep[x] < dep[y]: climb y upward until dep[x] == dep[y].
   • If dep[x] == dep[y]: climb x and y upward together until x == y. At this point we have found the LCA.

Drawback: This is essentially a brute-force approach. When the tree degenerates into a chain (linked-list shape), the time cost becomes too large.

3. Speeding Up With Binary Lifting

The naive approach moves up only 1 step at a time. Can we move up faster?

Idea — Binary Lifting: move up by 1, 2, 4, 8, … steps at once.

Similar to a Sparse Table (ST table), we preprocess, for each node, its 1-step ancestor, 2-step ancestor, 4-step ancestor, and so on. Based on this table, the binary-lifting method finds the LCA in O(log n) time.

Algorithm steps:

1. Preprocess the array p[u][i], defined as the node reached by moving u upward by 2^i steps.
2. Use the p array to optimize the naive algorithm.

4. Preprocessing the p Array

• Moving from node fa to node u: p[u][0] = fa
• Recurrence: p[u][i] = p[p[u][i-1]][i-1]
• Intuition: moving u up 2^i steps = moving u up 2^(i-1) steps to reach some node, then moving that node up another 2^(i-1) steps.

def dfs(u, fa):
    # Preprocessing
    deep[u] = deep[fa] + 1
    p[u][0] = fa
    for i in range(1, 21):
        p[u][i] = p[p[u][i - 1]][i - 1]
    for v in G[u]:
        if v == fa:
            continue
        dfs(v, u)

5. Solving LCA(x, y)

Assume deep[x] > deep[y]:

Step 1 — Bring x up so that deep[x] == deep[y]

Use binary lifting: enumerate i from large to small. Try moving x up 2^i steps to a node p. If deep[p] < deep[y] (the move would overshoot above y’s level), do not move; otherwise, move.

Step 2 — Now deep[x] == deep[y]

• If x == y, then the answer is x.
• Otherwise, climb both up together. Enumerate i from large to small. Move x up 2^i steps to px, and y up 2^i steps to py:
  • If px == py, they share a common ancestor, but we cannot guarantee it is the lowest common ancestor, so do not move.
  • If px != py, then move.

This eventually lands x and y on the first pair of nodes that are not the common ancestor (i.e., just below the LCA). The LCA is then p[x][0].

6. Implementation

def lca(x, y):
    # Ensure x is the deeper node
    if deep[x] < deep[y]:
        x, y = y, x

    # Use binary lifting to climb up so that deep[x] == deep[y].
    # Enumerate the step size 2^i from large to small.
    # If the node reached after this move, p[x][i], still has
    # depth >= deep[y], then the move is allowed.
    for i in range(20, -1, -1):
        if deep[p[x][i]] >= deep[y]:
            x = p[x][i]

    # At this point deep[x] == deep[y]
    if x == y:
        return x

    # Climb up together: if moving 2^i steps makes both nodes share
    # the same ancestor, the move is not allowed; otherwise it is.
    for i in range(20, -1, -1):
        if p[x][i] != p[y][i]:
            x, y = p[x][i], p[y][i]

    return p[x][0]

Memoization

1. What Is Memoization?

Memoization: a way of implementing a search that records information about states it has already visited, so that the same state is never traversed (recomputed) more than once.

Memoization = DFS + an extra dictionary (cache)

• If the state has been searched before: look it up in the dictionary and return the stored result directly.
• If the state has not been searched before: keep searching, and finally record that state’s result into the dictionary.

2. Worked Example — Fibonacci Sequence

Problem

Define the Fibonacci sequence as:

Compute $F[n]$, giving the result modulo $10^9 + 7$.

Constraints: 0 <= n <= 10000

2.1 Direct Recursion — Lots of Repeated Work

Solving by plain recursion produces a large number of repeated computations. Expanding F(5):

                       F(5)
              ┌──────────┴──────────┐
            F(3)                    F(4)
         ┌───┴───┐            ┌──────┴──────┐
       F(1)     F(2)        F(2)           F(3)
              ┌──┴──┐     ┌──┴──┐       ┌───┴───┐
            F(0)  F(1)   F(0)  F(1)    F(1)    F(2)
                                              ┌──┴──┐
                                            F(0)  F(1)

The dashed regions in the original slide highlight identical subtrees that get evaluated again and again — e.g. F(3) is computed twice and F(2) three times. The number of redundant calls grows exponentially.

2.2 Memoization — Store Once, Reuse Later

Each time a state is solved, record its answer in the dictionary; any later request for the same state returns the stored result immediately instead of recursing.

Annotating the same tree (store = save a newly computed value, retrieve = read a cached value):

                       F(5)          store: F[5] = 8
              ┌──────────┴──────────┐
            F(3)                    F(4)         store: F[4] = 5
   store: F[3] = 3              ┌────┴────┐
         ┌───┴───┐            F(2)        F(3)
       F(1)     F(2)        retrieve     retrieve
   retrieve  store: F[2]=2    F[2]         F[3]
     F[1]      ┌──┴──┐
              F(0)  F(1)
           retrieve retrieve
             F[0]    F[1]

Once F[2], F[3], and F[4] are cached on the left branch, the right branch’s F(2), F(3) resolve in O(1) by lookup — turning the exponential tree into a linear pass.

3. Three Implementations in Python

Original (plain recursion)

# Original
def f(x):
    if x == 0 or x == 1:
        return 1
    return f(x - 1) + f(x - 2)

Memoization 1 — explicit dictionary

# Memoization 1
dic = {0: 1, 1: 1}

def f(x):
    if x in dic.keys():
        return dic[x]
    dic[x] = f(x - 1) + f(x - 2)
    return dic[x]

Memoization 2 — functools.lru_cache

# Memoization 2
from functools import lru_cache

@lru_cache(maxsize=None)
def f(x):
    if x == 0 or x == 1:
        return 1
    return f(x - 1) + f(x - 2)

Note: To satisfy the mod 1e9 + 7 requirement and the recursion depth at n = 10000, you’d typically apply the modulus inside the addition and raise Python’s recursion limit (sys.setrecursionlimit) — or convert the memoized recursion into a bottom-up loop.

Introduction to DFS (Depth-First Search)

What is a Search Algorithm?

A search algorithm exhaustively explores part or all of the solution space of a problem to find its solution.

Depth-First Search (DFS)

• Essence: DFS is essentially brute-force enumeration.
• “Depth-first” principle: Go as far down one path as possible; only backtrack when no further progress can be made.

Example: Finding a Path from Node 1 to Node 8

Starting from node 1, always move to an unvisited node if one exists; otherwise, backtrack.

Following this rule, a valid path can always be found from 1 to 8, for example:

1 → 3 → 7 → A → 7 → 9 → 3 → 5 → 6 → 8

The portions shown in red (e.g., the second 7 and second 3) represent backtracking steps.

By modeling problems as graphs, DFS can be used to brute-force solve a wide variety of problems.

Backtracking

Definition

Backtracking is a form of DFS used to search for solutions. When the current state is found to no longer satisfy the solution conditions, we “backtrack” and try a different path.

Key Characteristics

• Backtracking emphasizes: When one path fails, try another; visited paths must be marked.
• Backtracking generally builds on DFS by adding pruning strategies.

Backtracking Trees

Subset Tree

For a subset problem, each element has two choices: include (1) or exclude (0). This produces a binary tree structure where each level corresponds to a decision about one element.

Permutation Tree

For a permutation problem with elements {1, 2, 3}, the root branches into each possible first choice (1, 2, or 3). At each subsequent level, the remaining unused numbers branch out, forming a tree of all possible orderings.

Pruning

Why Prune?

During the search process, exhaustively traversing all possibilities can be very time-consuming. If at some state we can determine that no valid solution lies further down that branch, we don’t need to continue searching that subtree.

Example: Given N positive integers, count how many subsets have a sum ≤ K. During the search, if the current sum already exceeds K, we can stop exploring that branch.

Types of Pruning

1. Feasibility Pruning: If the current state already violates the problem constraints and all subsequent states will also violate them, prune this branch.

2. Optimality Pruning: If the current state can no longer improve upon the best solution found so far, prune this branch.

DFS and N-Nested Loops

Motivating Problem

Given a number x, split it into 3 positive integers where each subsequent integer is greater than or equal to the previous one. Output all valid partitions.

• Simplest approach: Triple nested loop, brute-force search.
• What if we need to split into 4 positive integers?
• What about n positive integers?
  • We would need to implement an n-nested loop.
  • An n-nested loop is equivalent to a specific tree structure, which can be implemented via DFS.

Visualization (x = 6, split into 3 integers)

• Level 1: Choose first integer from {1, 2, 3, 4, 5, 6}
• Level 2: Choose second integer (≥ first)
• Level 3: Choose third integer (≥ second), with total sum = 6

This forms a tree where DFS traces a valid path from top to bottom — the path must be non-decreasing, length n, and sum to x.

Generic DFS Template for N-Nested Loops

def dfs(depth):
    """
    :param depth: current loop level
    :return:
    """
    if depth == N:
        # Code executed at the innermost loop
        return
    # Enumeration/selection at each loop level

Implementation (Without Pruning)

x, n = map(int, input().split())

# Record the number chosen at each level
a = [0] * n
# Counter for number of computations
cnt = 0

def dfs(depth):
    """
    :param depth: current loop level
    """
    global cnt
    cnt = cnt + 1
    # Levels 0 through n-1 have all been chosen; now check the answer
    if depth == n:
        # Condition 1: numbers must be non-decreasing
        for i in range(1, n):
            if a[i] >= a[i - 1]:
                continue
            else:
                return
        # Condition 2: sum must equal x
        if sum(a) != x:
            return
        # This is a valid answer
        print(a)
        return
    # Enumerate the number at level `depth` from [1, x]
    for i in range(1, x + 1):
        # Choose the number at level `depth`
        a[depth] = i
        # Recurse into the next level
        dfs(depth + 1)

dfs(0)
print("Total computations = {}".format(cnt))

Implementation (With Pruning)

By checking conditions during enumeration rather than only at the leaves, we can dramatically reduce computation:

def dfs(depth, last_val):
    """
    :param depth: current loop level
    """
    global cnt
    cnt = cnt + 1
    # All n levels have chosen numbers; check answer
    if depth == n:
        # Condition 2: sum must equal x
        if sum(a) != x:
            return
        # This is a valid answer
        print(a)
        return
    # At level `depth`, enumerate numbers in [last_val, x]
    # Condition 1: numbers must be non-decreasing (enforced via loop range)
    for i in range(last_val, x + 1):
        # Choose the number at level `depth`
        a[depth] = i
        # Recurse into the next level
        dfs(depth + 1, i)

dfs(0, 1)

Key insight: Placing conditions inside the enumeration loop (rather than only checking at the leaves) reduces computation — this is pruning.

Backtracking Template — Permutations

Problem

Generate all permutations of N distinct numbers.

Key Requirements

• No repeated numbers in a permutation → mark each chosen number using a vis (visited) array.
• Output the current permutation → record the current path using a path array.
• Backtracking pattern: mark → record path → recurse to next level → return to previous level → clear mark.

Implementation

def dfs(depth):
    # Currently at the depth-th position; positions 0 to depth-1 are set
    if depth == n:
        print(path)
        return

    # Enumerate the number at position `depth`
    for i in range(1, n + 1):
        # Number i must not have been chosen before
        if vis[i] is False:
            # Mark current state
            vis[i] = True
            # Record current path
            path.append(i)
            # Recurse into the next level
            dfs(depth + 1)
            # Clear mark (backtrack)
            vis[i] = False
            path.pop(-1)

n = int(input())
path = []
vis = [False] * (n + 1)
dfs(0)

Backtracking Template — Subsets

Problem

Given N numbers, generate all possible subsets.

Approach

At each level, we have a binary choice for each number: include (Y) or exclude (N). This creates a binary tree of depth N.

Implementation

n = int(input())
a = list(map(int, input().split()))

path = []

def dfs(depth):
    if depth == n:
        print(path)
        return

    # Include a[depth]
    path.append(a[depth])
    dfs(depth + 1)
    path.pop(-1)

    # Exclude a[depth]
    dfs(depth + 1)

dfs(0)

Summary

The general backtracking pattern is:

1. Mark the current choice
2. Record the path
3. Recurse to the next level
4. Return to the previous level
5. Clear the mark

Two pointers are useful when performing operations on a range: two indices traverse the data simultaneously and exploit the range’s structure. The technique can often reduce $\mathcal{O}(n^2)$ time complexity to $\mathcal{O}(n)$.

Opposite-Direction Scan

The left pointer starts at the beginning and continuously moves to the right, while the right pointer starts at the end and continuously moves to the left, until they meet and stop. This is generally used for problems involving sorted arrays or strings.

Same-Direction Scan

Also known as the sliding-window technique, this approach maintains an interval $[\mathrm{left}, \mathrm{right}]$. It tracks information about that interval, such as its sum or the count of each element.

• Moving the left endpoint to the right represents removing an element.
• Moving the right endpoint to the right represents adding an element.

It stops when it reaches the end, or when a specific condition is met.

Stack

• A Stack is a special linear data structure that only allows insertion and deletion operations at one end of the structure.
• This end is called the Top, and the other end is called the Bottom.
• Stack operations follow the Last-In, First-Out (LIFO) principle.

Push

Add a new element at the top of the stack.

Pop

Remove and return the element at the top of the stack.

Top (Peek)

Return the element at the top of the stack without removing it.

Using a List to Simulate a Stack

Python’s list provides all the necessary operations to easily simulate a stack.

• Push: Use the list’s append() method
• Pop: Use the list’s pop() method (without arguments)
• Top: Access the last element of the list with stack[-1]
• Check if the stack is empty: Check the length of the list with len(stack) == 0, or simply use if not stack

Queue

• A Queue is a special linear data structure that only allows insertion at one end of the structure and deletion at the other end.
• The end where insertion occurs is called the Rear, and the end where deletion occurs is called the Front.
• Queue operations follow the First-In, First-Out (FIFO) principle.

Enqueue

Add a new element at the rear of the queue.

Dequeue

Remove and return the element at the front of the queue.

Using a List to Simulate a Queue (Not Recommended)

• Enqueue: Use the list’s append() method
• Dequeue: Use the list’s pop(0) method
• Peek at the front: Access the first element of the list with queue[0]

Performance Issues

While simulating a queue with a list is functionally feasible, it is inefficient. Removing an element from the head of a list is an inefficient operation. The pop(0) operation on a list has a time complexity of $\mathcal{O}(n)$, where $n$ is the length of the list. This is because after removing the first element, all subsequent elements need to be shifted forward by one position to fill the gap.

Double-Ended Queue (Deque)

Python’s collections module provides a specifically optimized data structure called deque. It is the preferred way to implement a queue.

• A deque is a double-ended queue, meaning that adding and removing elements at both ends is highly efficient, with a time complexity of $\mathcal{O}(1)$.
• Its internal implementation is based on a doubly linked list, which avoids the performance issues that lists have with head operations.
• Enqueue: Use the append() method
• Dequeue: Use the popleft() method
• Peek at the front: Use queue[0] to access the first element

deque vs. list

deque and list each have their own strengths and weaknesses for different operations. Understanding the performance differences between them is key to efficient programming.

Trade-off

• deque: Optimized for fast $\mathcal{O}(1)$ insertions and deletions at both ends. However, the performance of indexed access depends on the position being accessed: accessing elements at either end is $\mathcal{O}(1)$, while accessing elements in the middle is more costly, with a worst-case time complexity of $\mathcal{O}(n)$.
• list: Optimized for fast $\mathcal{O}(1)$ random access and $\mathcal{O}(1)$ insertions and deletions at the tail, but insertions and deletions at the head are slow $\mathcal{O}(n)$ operations.
• Conclusion: In scenarios that require frequent operations at both ends of the data (such as queues, stacks, and sliding windows), deque is the ideal choice.

Initializing a deque and Bounded Deques

• Create an empty deque: d = deque()
• Create from an iterable: d = deque([1, 2, 3])

Bounded Deque

When creating a deque, you can provide an optional parameter maxlen to limit its maximum length. When a bounded deque is full and a new element is added at one end, the element at the other end is automatically pushed out. This is very useful in many algorithmic scenarios, such as solving “sliding window” problems.

What is a Tree?

Concept: A Non-Linear Hierarchical Structure

• Tree is an abstract data type used to simulate data with hierarchical relationships. It consists of n (n ≥ 0) finite nodes.
• It is a non-linear data structure, in contrast to the linear structures we studied earlier such as lists, stacks, and queues.
• In a tree structure, there is a special node called the Root. The remaining nodes can be divided into m (m ≥ 0) disjoint sets T₁, T₂, …, Tₘ, each of which is itself a tree, referred to as a Subtree of the root.

Real-Life Examples

• Book table of contents: The book is the root node, chapters are intermediate nodes, and sections are leaf nodes.
• File system: The root directory is the root node, subdirectories at each level are intermediate nodes, and files are leaf nodes.

Key Terminology

(Based on the tree diagram with nodes A, B, C, D, E, F, G, H, I, K)

• Root: The topmost node of the tree (A).
• Child: The direct successor of a node (B, C, D are children of A).
• Parent: The direct predecessor of a node (A is the parent of B, C, D).
• Sibling: Nodes that share the same parent (B, C, D are siblings of each other).
• Leaf: A node with no children (E, K, C, G, H, I).
• Internal Node: A non-leaf node (A, B, F, D).
• Degree: The number of subtrees a node has (A has degree 3).
• Depth: The path length from the root to a given node (depth of F is 2).
• Height: The maximum depth among all nodes in the tree.

Rooted Tree vs. Unrooted Tree

Rooted Tree

• All concepts discussed previously — parent, child, depth, etc. — are based on rooted trees.
• A rooted tree has an explicitly designated root node, which establishes the hierarchical structure and direction of the entire tree.
• In a problem, if the input directly provides directed “parent–child” relationships, then it describes a rooted tree.

Unrooted Tree

• In algorithm competitions, problems often provide only a set of “edges” connecting nodes without specifying a root. This describes an unrooted tree.
• An unrooted tree is a connected acyclic graph. It has no inherent hierarchical direction.
• We can choose any node as the root to convert an unrooted tree into a rooted tree for processing. Different choices of root produce structurally different rooted trees.

Properties of Trees

A Tree with N Nodes Has the Following Properties

• Edges: A tree has exactly N − 1 edges. This is a key characteristic that distinguishes trees from general graphs.
• Connectivity: There is exactly one unique simple path between any two nodes in a tree.
• Acyclicity: A tree contains no cycles.
• Corollaries:
  • Adding any one edge to a tree will necessarily create a cycle.
  • Removing any one edge from a tree will necessarily split it into two disconnected trees.
• In graph theory, a graph with N nodes is a tree if and only if any two of the following three conditions hold:
  • The graph is connected.
  • The graph is acyclic.
  • The graph has N − 1 edges.

Special Trees — Binary Tree

Definition

A Binary Tree is a special type of tree where each node has at most two children, referred to as the Left Child and the Right Child.

• The positions of the two children are ordered and cannot be swapped arbitrarily.
• A node may have only a left child, or only a right child.

Full Binary Tree

Every non-leaf node has exactly degree 2 (i.e., exactly two children).

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Complete Binary Tree

Every level, except possibly the last, is completely filled. All nodes in the last level are as far left as possible.

        1
       / \
      2   3
     /\ /
    4 5 6

Note: The heap data structure we studied previously is a type of complete binary tree.

Representation (1) — Node Class (Object-Oriented)

Concept

The most intuitive approach is to define a TreeNode class. Each object represents a node, containing the node’s value and a list of references to all its child nodes.

Code Implementation

# Define tree node
class TreeNode:
    def __init__(self, val, children=None):
        self.val = val
        if children is None:
            self.children = []
        else:
            self.children = children

root = TreeNode('A', [        # Manually construct a tree:
    TreeNode('B', [           #         A
        TreeNode('E'),        #       / | \
        TreeNode('F')         #      B  C  D
    ]),                       #     / \
    TreeNode('C'),            #    E   F
    TreeNode('D')
])

print(f"Root's value: {root.val}")
print(f"Number of children: {len(root.children)}")
print(f"First child's value: {root.children[0].val}")

Output

Root's value: A
Number of children: 3
First child's value: B

Pros and Cons

• Pros: Clear structure; very well-suited to object-oriented thinking.
• Cons: Not flexible enough for scenarios requiring frequent structural modifications or graph-based applications; not commonly used in the standard input format of algorithm competitions.

Representation (2) — Adjacency List

Concept

This is the most commonly used representation in graph theory and algorithm competitions. We use a dictionary or an array of lists to store the tree’s structure. This method can flexibly represent both rooted and unrooted trees.

Rooted Tree

# Input as (parent, child) pairs
N = 6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]
tree = [[] for _ in range(N)]
for parent, child in edges:
    tree[parent].append(child)

# Print results
for i in range(N):
    print(f"Node {i} children: {tree[i]}")

Output:

Node 0 children: [1, 2]
Node 1 children: [3, 4]
Node 2 children: [5]
Node 3 children: []
Node 4 children: []
Node 5 children: []

Unrooted Tree

# Input as undirected edges
N = 6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]
adj = [[] for _ in range(N)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

# Print results
for i in range(N):
    print(f"Node {i} neighbors: {adj[i]}")

Output:

Node 0 neighbors: [1, 2]
Node 1 neighbors: [0, 3, 4]
Node 2 neighbors: [0, 5]
Node 3 neighbors: [1]
Node 4 neighbors: [1]
Node 5 neighbors: [2]

Representation (3) — Parent Pointer

Concept

This method is specifically used for rooted trees. It uses an array parent to store the parent of each node. Specifically, parent[i] holds the index of node i’s parent node. For the root node, a special value (e.g., -1) is used to indicate it has no parent.

Code Implementation

# Assume N nodes, numbered 0 to N-1
N = 6
# parent[i] stores the parent of node i
# Assume root is 0, its parent is -1
parent = [-1] * N
# edges describe parent-child relationships
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]

for p, c in edges:
    parent[c] = p

# Print each node's parent
for i in range(N):
    print(f"Node {i}'s parent: {parent[i]}")

Output

Node 0's parent: -1
Node 1's parent: 0
Node 2's parent: 0
Node 3's parent: 1
Node 4's parent: 1
Node 5's parent: 2

Pros and Cons

• Pros: Quickly find the parent of any node; well-suited for algorithms that need to trace upward (e.g., Union-Find / Disjoint Set Union).
• Cons: Cannot directly find all children of a node; requires traversing the entire array.

What is Depth-First Search?

Concept: Go All the Way Down One Path

• Depth-First Search (DFS) is an algorithm for traversing or searching trees or graphs.
• Its core idea is: starting from the root node, explore each branch as deeply as possible.
• When exploring along a path and all children of a node have been visited, the algorithm backtracks to that node’s parent and continues exploring any unvisited children.
• This process is typically implemented using recursion, which naturally uses the function call stack to handle the “going deeper” and “backtracking” phases.

Traversal Order

The order in which DFS visits nodes is closely tied to the order of recursive calls. It always completes the full exploration of one subtree before moving on to the next sibling subtree.

DFS Implementation: Rooted Tree vs. Unrooted Tree

Rooted Tree

For a rooted tree, edge directions are fixed (from parent to child), so starting from the root we simply recurse into each node’s children.

Code Implementation:

# tree[i] stores the children of node i
def dfs_rooted(u, tree):
    print(u, end=" ")  # Visit and print current node
    for v in tree[u]:
        dfs_rooted(v, tree)

# --- Build directed adjacency list ---
N = 6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]
tree = [[] for _ in range(N)]
for p, c in edges:
    tree[p].append(c)
# Start DFS from root node 0
dfs_rooted(0, tree)

Output:

0 1 3 4 2 5

Unrooted Tree

For an unrooted tree (treated as an undirected graph), we need an extra mechanism to prevent “going back the way we came” during traversal. The common approach is to track each node’s visited status, or to pass the parent node into the recursive call.

Code Implementation (tracking parent):

# adj[i] stores all neighbors of node i
def dfs_unrooted(u, p, adj):
    print(u, end=" ")  # Visit and print current node
    for v in adj[u]:
        if v != p:  # If neighbor v is not where we came from
            dfs_unrooted(v, u, adj)

# --- Build undirected adjacency list ---
N = 6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]
adj = [[] for _ in range(N)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
# Start DFS from node 0, initially no parent (-1)
dfs_unrooted(0, -1, adj)

Output:

0 1 3 4 2 5

DFS Process Illustrated

The following steps trace the DFS execution on this tree:

        0
       / \
      1   2
     / \   \
    3   4   5

Final traversal order: 0 → 1 → 3 → 4 → 2 → 5

Binary Tree Traversal: Pre-order, In-order, and Post-order

Based on When the Root Node is Visited

For binary trees, DFS can be classified into three classic traversal orders based on the visit sequence of the root, left subtree, and right subtree. Assume the DFS function signature is dfs(node):

Pre-order Traversal (Root → Left → Right)

def preorder(node):
    if node is None: return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

In-order Traversal (Left → Root → Right)

def inorder(node):
    if node is None: return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

Post-order Traversal (Left → Right → Root)

def postorder(node):
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

Example

For the following binary tree:

        A
       / \
      B   C
     / \   \
    D   E   F

The three traversal sequences are:

DFS Application: Using Return Values for Aggregation

Core Idea: Passing Information Bottom-Up

DFS is not just for “walking through” all nodes. Its greater power lies in the recursive function’s ability to return information bottom-up, allowing us to compute and aggregate various properties of the entire tree.

Application: Finding the Maximum Height of a Tree

The function dfs_height(u) returns the height of the subtree rooted at node u.

Its recurrence relation is defined as: the maximum height of a node equals the maximum height among all its children’s subtrees, plus one.

Recurrence Relation:

For leaf nodes, the height is 0.

Code Implementation:

def get_max_height(u, tree):
    # Base case: leaf node has height 0
    if not tree[u]:
        return 0

    max_child_height = -1
    # Recursively compute height of all child subtrees
    for v in tree[u]:
        max_child_height = max(max_child_height,
                               get_max_height(v, tree))

    # Return the tallest child subtree height + 1
    return 1 + max_child_height

Union-Find (Disjoint Set Union)

Problem Definition

Given N mutually disjoint sets, we need to support two operations:

• Merge: Union two sets together
• Query: Determine whether two elements belong to the same set

Example Operation Sequence

Elements: a, b, c, d, e, f

Operations: Merge(a,b), Merge(b,e), Merge(c,f), Merge(b,f)

Approach 1: Naive Label-Based

Assign each element a set ID. To merge, update all elements of one set to the other’s ID.

Complexity: Query: O(1)  |  Merge: O(n)

Approach 2: Tree-Based Representation

Represent each set as a tree, where each node points to its parent. The root node serves as the set’s identifier.

Step-by-step Tree Evolution

Merges are always performed between root nodes to maintain valid tree structure.

Core Operations

Merge(x, y)

Find the root of each element, then attach one root as a child of the other:

p[rootx] = rooty

Query(x, y)

Check if both elements share the same root:

rootx == rooty  →  same set

Implementation Details

• For each node x, maintain p[x] = parent of x
• Initialize p[x] = x for all nodes (each node is its own root)

Python Implementation

def Findroot(x):
    while x != p[x]:
        x = p[x]
    return x

def Merge(x, y):
    # Merge the sets containing x and y
    rootx, rooty = Findroot(x), Findroot(y)
    p[rootx] = rooty

def Query(x, y):
    # Check if x and y belong to the same set
    rootx, rooty = Findroot(x), Findroot(y)
    return rootx == rooty

n, m = map(int, input().split())
p = list(range(n + 1))

for _ in range(m):
    op, x, y = map(int, input().split())
    if op == 1:
        Merge(x, y)
    else:
        print("YES" if Query(x, y) else "NO")

Drawback & Optimization

Problem: Findroot is O(n) in the worst case. Repeated merges can produce a degenerate chain structure, making traversal to the root expensive.

Solution: Path Compression

During Findroot, flatten the tree so every node on the path points directly to the root. This amortizes the per-operation cost to nearly O(1).

def Findroot(x):
    if x != p[x]:
        p[x] = Findroot(p[x])  # Recursively compress path
    return p[x]

With path compression (and optionally union by rank), the amortized complexity per operation is O(α(n)), where α is the inverse Ackermann function — effectively constant for all practical input sizes.

What is a Linked List?

Concept: A Dynamic Data Structure

• A Linked List is a linear data structure, but its elements are not stored contiguously in memory.
• It is composed of a series of Nodes, where each node contains two parts:
  • Data field: stores the element’s data.
  • Pointer field: stores the memory address of the next node.
• This structure — discrete memory blocks chained together via pointers — makes linked lists very efficient for insertion and deletion operations.

Comparison with Arrays

Structure: Nodes and Pointers

Singly Linked List

The simplest type of linked list. Each node has exactly one pointer pointing to its successor node.

[ 12 | • ] ──→ [ 99 | • ] ──→ [ 37 | Null ]
  Node 1          Node 2          Node 3

Key Terminology

• Head: The first node of the linked list.
• Tail: The last node of the linked list; its pointer field points to Null.

Implementing a Linked List in Python

Defining the ListNode Class

In Python, we typically define a node using a class that holds data and a reference to the next node.

# Define the linked list node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val    # node's data value
        self.next = next  # reference to the next node

# Create a simple linked list: 1 -> 2 -> 3
node3 = ListNode(3)
node2 = ListNode(2, node3)
head  = ListNode(1, node2)

# Traverse the list
current = head
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")

Output: 1 -> 2 -> 3 -> None

Dummy Head Node

When solving linked list problems, we often create a dummy head node whose next pointer points to the true head node.

The advantage is that it unifies operations on all nodes, avoiding special-casing the head node (e.g., inserting or deleting at the front). This makes the code cleaner and less error-prone.

Core Operation (1): Insert

Process: Insert New Node X After Node A

1. Find node A.
2. Set new node X’s next pointer to A’s current successor node.
3. Set node A’s next pointer to the new node X.

Step 1:  X.next = A.next   (X now points to B)
Step 2:  A.next = X        (A now points to X)

Before: A ──→ B
After:  A ──→ X ──→ B

Code Implementation

# Insert new_val after the node with value target_val
def insert_after(head, target_val, new_val):
    curr = head
    # 1. Find the target node
    while curr and curr.val != target_val:
        curr = curr.next
    # 2. If found, perform insertion
    if curr:
        new_node = ListNode(new_val)
        new_node.next = curr.next
        curr.next = new_node
    return head

# Example: list is 1 -> 2 -> 3
# insert_after(head, 2, 99)
# Result: 1 -> 2 -> 99 -> 3

Core Operation (2): Delete

Process: Delete the Node with Value target_val

1. Use a dummy head node to simplify edge cases.
2. Find the predecessor node prev of the node to be deleted.
3. Set prev.next to point directly to the node after the deleted node.

Before: A ──→ [B] ──→ C
                       ↑
        A.next = B.next (skip over B)
After:  A ──────────→ C

Code Implementation

# Delete the first node with value target_val
def delete_node(head, target_val):
    dummy = ListNode(next=head)
    prev, curr = dummy, head
    while curr:
        if curr.val == target_val:
            # Found it — bypass the current node
            prev.next = curr.next
            break  # delete the first one, then exit
        prev = curr
        curr = curr.next
    return dummy.next

# Example: list is 1 -> 2 -> 99 -> 3
# delete_node(head, 99)
# Result: 1 -> 2 -> 3

How is Memory Freed?

In Python, we don’t need to manually free memory like in C++. When an object (such as the removed node) has no variables or pointers referencing it, Python’s Garbage Collector automatically reclaims its memory. So the prev.next = curr.next operation simultaneously breaks the link and ensures the discarded node will eventually be reclaimed by the system.

Classic Problem: Josephus Problem

Problem Description

n people (numbered 1, 2, …, n) stand in a circle. Starting from person 1, every m-th person is eliminated. The next round restarts from the person after the one just eliminated, counting up to m again. This continues until everyone has been eliminated.

Find the original number of the last person to be eliminated.

Approach: Simulate with a Circular Linked List

1. This problem has an inherently circular structure — a circular linked list is a natural fit.
2. Create a circular linked list of n nodes representing the people.
3. Starting from the head, advance m − 1 steps each round to find the person to eliminate.
4. “Delete” that node (modify its predecessor’s pointer) and record its value.
5. Repeat until only one node remains.

Example Walkthrough (n = 5, m = 3)

1. Initial: 1 → 2 → 3 → 4 → 5 → (1)
2. Round 1: Count 3 from 1 — 3 is eliminated. Remaining: 1 → 2 → 4 → 5 → (1)
3. Round 2: Count 3 from 4 — 1 is eliminated. Remaining: 2 → 4 → 5 → (2)
4. Round 3: Count 3 from 2 — 5 is eliminated. Remaining: 2 → 4 → (2)
5. Round 4: Count 3 from 2 — 2 is eliminated. Remaining: 4
6. Final: The last person is 4.

Code Implementation (Circular Linked List)

# (ListNode class defined previously)
def josephus_linked_list(n, m):
    if n <= 0:
        return -1

    # 1. Build the circular linked list
    head = ListNode(1)
    curr = head
    for i in range(2, n + 1):
        curr.next = ListNode(i)
        curr = curr.next
    curr.next = head  # close the circle

    # 2. Find and delete nodes
    prev = head       # prev points to the node just before head
    curr = head
    count = n
    while count > 1:
        # Advance m-1 steps to reach the node to eliminate
        for _ in range(m - 1):
            prev = curr
            curr = curr.next
        # Delete the current node
        prev.next = curr.next
        curr = prev.next
        count -= 1

    return curr.val

print(f"n=5,  m=3 -> Winner: {josephus_linked_list(5, 3)}")
print(f"n=10, m=4 -> Winner: {josephus_linked_list(10, 4)}")

Output:

n=5,  m=3 -> Winner: 4
n=10, m=4 -> Winner: 5

Complexity Analysis

Time Complexity: O(n·m)

• In the naive simulation, there are n − 1 elimination rounds.
• Each round requires walking m − 1 steps from the current position.
• Using a true circular linked list, finding the node to delete is O(m) and deletion is O(1), giving O(n·m) overall.
• This complexity is acceptable when m ≪ n.

Space Complexity: O(n)

• We need a data structure (the linked list) of size n to hold all people.

Better Solution

The Josephus problem has a well-known mathematical recurrence that reduces time complexity to O(n) and space complexity to O(1):

where f(n, m) denotes the survivor’s index among n people counting every m-th (0-indexed).

Programming Exercise: Reverse a Linked List

Problem

Write a function reverse_list(head) that takes the head node head of a singly linked list and returns the head node of the reversed list.

Example:

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
• Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

Solution

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_temp = curr.next  # temporarily save the next node
        curr.next = prev       # point current node's next to the previous node
        prev = curr            # advance prev and curr pointers
        curr = next_temp

    return prev

Concept: A Special Kind of Queue

A priority queue is an abstract data type that allows us to store elements and retrieve (usually remove) the minimum or maximum element at any time.

• Unlike a regular queue’s “first-in, first-out” principle, a priority queue outputs the highest-priority element first.
• An element’s “priority” is typically determined by its value.

Comparison with Stack and Queue

1. What Is a Heap?

A heap is a special data structure based on a complete binary tree, commonly used to implement priority queues.

Complete Binary Tree: Every level is fully filled except possibly the last, and the last level’s nodes are as far left as possible.

Heap Properties:

• Min-Heap: Every node’s value is ≤ its children’s values. The root is always the minimum element in the heap.
• Max-Heap: Every node’s value is ≥ its children’s values. The root is always the maximum element in the heap.

2. Array Representation of a Heap

Since a heap is a complete binary tree, we can conveniently store it in an array (or list) from top to bottom, left to right — no pointers needed.

For a node at index i:

• Parent index: (i - 1) // 2
• Left child index: 2 * i + 1
• Right child index: 2 * i + 2

3. Core Operations

Push (Insert)

1. Append the new element to the end of the array (the next available position in the complete binary tree).
2. Compare the new element with its parent.
3. If the new element is smaller than its parent (for a min-heap), swap them.
4. Repeat until the new element is no longer smaller than its parent, or it has reached the root. This process is called sift-up (bubbling up).

Pop (Remove)

1. Extract the root’s value (this is the minimum value we want).
2. Move the last element in the array to the root position.
3. Compare the new root with its smaller child.
4. If the new root is larger than its smaller child, swap them.
5. Repeat until the node is no longer larger than either child, or it has become a leaf node. This process is called sift-down (sinking down).

4. The heapq Module

Module Basics: Operates In-Place on Lists

Python’s standard library heapq provides efficient algorithms to implement a min-heap on a regular list.

• Important: It is a functional module, not a data type like deque. You provide a list; it modifies that list in-place to satisfy the heap property.
• After operations, heap[0] is always the smallest element.
• Since it operates directly on a list, you can mix in regular list operations — but this may corrupt the heap structure, so use with care.

heapify: Efficient Heap Construction

heapq.heapify(x) is a very important function. It converts an arbitrary list x into a valid min-heap in-place in O(N) linear time.

import heapq
# Starting from an arbitrary list
data = [40, 20, 80, 10, 50]
print(f"Original list: {data}")
heapq.heapify(data)
print(f"Heapified list: {data}")
# The top is the minimum
print(f"Heap top: {data[0]}")

Output:

Original list: [40, 20, 80, 10, 50]
Heapified list: [10, 20, 80, 40, 50]
Heap top: 10

5. Core Operations: heappush & heappop

These are the two most commonly used methods for operating on a heap, corresponding to “push” and “pop”. Both have O(log N) time complexity.

• heapq.heappush(heap, item): Pushes item onto the heap while maintaining the heap property.
• heapq.heappop(heap): Pops and returns the smallest element from the heap while maintaining the heap property. Raises IndexError if the heap is empty.

import heapq
# Start with an empty list
heap = []
# Push elements in
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(f"Heap after pushes: {heap}")
# Pop the minimum
min_val = heapq.heappop(heap)
print(f"Popped: {min_val}, Heap is now: {heap}")
min_val = heapq.heappop(heap)
print(f"Popped: {min_val}, Heap is now: {heap}")

Output:

Heap after pushes: [10, 30, 20]
Popped: 10, Heap is now: [20, 30]
Popped: 20, Heap is now: [30]

6. Advanced Operations (1): Combined Methods

Efficient “Push and Pop”

heapq provides two highly optimized combined operations that are faster than calling heappush and heappop separately:

• heapq.heappushpop(heap, item): Pushes item onto the heap, then pops and returns the smallest element. The heap’s maximum size stays the same.
• heapq.heapreplace(heap, item): Pops and returns the smallest element, then pushes the new item. The heap’s maximum size stays the same.

Key Difference — when the pushed item is smaller than the current heap top, the two behave differently:

• heappushpop: first pushes the item, so it may return the item itself.
• heapreplace: pops the original top first, then pushes the item.

import heapq
heap = [10, 20, 30]
# heappushpop: 5 < 10, so push first, then pop 5 itself
ret1 = heapq.heappushpop(heap, 5)
print(f"heappushpop(5): returns {ret1}, heap is {heap}")
# 25 > 10, so 10 is popped
ret2 = heapq.heappushpop(heap, 25)
print(f"heappushpop(25): returns {ret2}, heap is {heap}")
# heapreplace: pops top (20) first, then pushes 15
heap = [20, 25, 30]
ret3 = heapq.heapreplace(heap, 15)
print(f"heapreplace(15): returns {ret3}, heap is {heap}")

Output:

heappushpop(5): returns 5, heap is [10, 20, 30]
heappushpop(25): returns 10, heap is [20, 25, 30]
heapreplace(15): returns 20, heap is [15, 25, 30]

7. Advanced Operations (2): Convenience Functions

Handy Top-K Tools

heapq also provides two very convenient functions to find the N largest or smallest elements from any iterable:

• heapq.nlargest(n, iterable, key=None): Returns a list of the n largest elements from the iterable.
• heapq.nsmallest(n, iterable, key=None): Returns a list of the n smallest elements from the iterable.

Performance Notes:

• Very efficient when n is relatively small.
• When n is close to the total length of the iterable, using sorted() may be more efficient.
• These are the cleanest way to solve “Top K” problems.

import heapq
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
# Find the 3 largest elements
top3 = heapq.nlargest(3, data)
print(f"Top 3 largest: {top3}")
# Find the 4 smallest elements
bottom4 = heapq.nsmallest(4, data)
print(f"Top 4 smallest: {bottom4}")
# Solve a Top K problem — find the 2nd largest element
k = 2
kth_largest = heapq.nlargest(k, data)[-1]
print(f"The 2th largest is: {kth_largest}")

Output:

Top 3 largest: [9, 8, 7]
Top 4 smallest: [0, 1, 2, 3]
The 2th largest is: 8

8. Trick: Simulating a Max-Heap

Problem

The heapq module only provides a min-heap. What if we want to pop the maximum element first?

Trick: Store Negated Values

We can use a simple math trick — the larger a number, the smaller its negation.

• Push: When pushing an element onto the “max-heap”, we actually push its negation.
• Pop: When popping from this heap, it pops the smallest negated value. We negate it once more to get the original maximum.

import heapq
# Simulate a max-heap
max_heap = []
# Push negated values
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
print(f"Internal min-heap: {max_heap}")
# Pop and negate to get original max
max_val = -heapq.heappop(max_heap)
print(f"Popped max value: {max_val}")
print(f"Internal min-heap after pop: {max_heap}")

Output:

Internal min-heap: [-30, -10, -20]
Popped max value: 30
Internal min-heap after pop: [-20, -10]

9. Comparison: heapq vs. queue.PriorityQueue

Another Option: queue.PriorityQueue

Python’s queue module also provides a PriorityQueue class. It is essentially a thread-safe priority queue implemented using heapq.

Why Not Recommended for Algorithm Competitions?

PriorityQueue is designed for multithreaded programming. Its internal thread-safety lock brings extra performance overhead. In single-threaded algorithm competitions, this makes it significantly slower than using heapq directly.

Therefore, in algorithm competitions, always prefer heapq.

Greedy Algorithms

Definition: The greedy method decomposes an overall problem into multiple steps. In each step, it selects the optimal solution for the current state until all steps are completed. The choice made in one step does not depend on or affect subsequent steps.

Core Property: By consistently making locally optimal choices, the final result is the globally optimal solution.

If a problem satisfies the core property above, it can be solved using a greedy approach.

Example: The Coin Change Problem (Minimum Coins)

Scenario: Assume there are three types of coins: $1$ yuan, $2$ yuan, and $5$ yuan (unlimited quantity). You need to pay a total of $M$ yuan. How should you pay to use the fewest number of coins?

• Local Optimal Strategy: To ensure the coin count is minimized, always prioritize choosing the largest denomination available for the remaining amount.
• Result: For this specific set of coins, adopting the local optimal strategy leads to the global optimal solution.

Counter-Example (When Greedy Fails)

If the coin denominations are changed to $1, 2, 4, 5, 6$ yuan, and you need to pay $9$ yuan:

• Greedy Approach: Selects $6$ first, leaving $3$. Then selects $2$, leaving $1$. Finally selects $1$.
  • Result: $6 + 2 + 1$ (3 coins)
• Actual Optimal Result:
  • Result: $5 + 4$ (2 coins)

Conclusion: Not all locally optimal choices result in a globally optimal solution.

How to Determine if Greedy is Applicable?

To use a greedy algorithm, the problem must satisfy two properties:

1. Optimal Substructure: A problem has optimal substructure if an optimal solution to the problem contains within it optimal solutions to sub-problems.
2. Greedy Choice Property: A global optimal solution can be arrived at by making a locally optimal (greedy) choice.

Practical Approach

1. Experience: Accumulate experience by solving various types of greedy problems to recognize patterns.
2. Counter-examples: Try to construct counter-examples to prove that a greedy strategy does not work. If you cannot find a counter-example, the greedy approach might be valid.

1. Core Concepts

Binary search is the standard algorithm for locating a specific element in a sorted sequence. It operates on the divide-and-conquer principle.

• Mechanism: Repeatedly halves the search space. By comparing the target with the middle element, we eliminate half of the candidates instantly.
• Prerequisite: The sequence must be sorted (monotonic).
• Complexity:
  • Time: $O(\log n)$ (Dramatically faster than the $O(n)$ of linear search).
  • Space: $O(1)$ (Iterative implementation).

2. Python’s bisect Module

implementing binary search manually is error-prone (off-by-one errors are common). Python’s bisect module provides a standardized, robust C-optimized implementation.

Key Functions

Note: bisect.bisect is an alias for bisect_right.

Example Usage:

import bisect
a = [10, 20, 30, 30, 40, 50]

# bisect_left: First index >= 30
idx1 = bisect.bisect_left(a, 30)   # Returns 2

# bisect_right: First index > 30
idx2 = bisect.bisect_right(a, 30)  # Returns 4

Inserting Elements (insort)

insort_left and insort_right insert element $x$ into the list while maintaining sorted order.

• Complexity: $O(n)$.
  • Why? Finding the index is $O(\log n)$, but shifting elements in the list to make room is linear $O(n)$.
• Return: None (modifies list in-place).

Practical Recipes

1. Check Existence

Check if x is present without a linear scan.

def check_existence(a, x):
    i = bisect.bisect_left(a, x)
    # Check if index is within bounds AND the value matches
    return i != len(a) and a[i] == x

2. Count Elements in Range $[L, R]$

Find how many numbers fit between left and right inclusive.

def count_in_range(a, left, right):
    start = bisect.bisect_left(a, left)   # First number >= left
    end = bisect.bisect_right(a, right)   # First number > right
    return end - start

3. General Binary Search Template

For problems beyond simple array lookups, we conceptualize Binary Search as a Decision Problem.

The Boolean Boundary

Any monotonic problem can be mapped to a boolean array where we seek the boundary between True and False.

• Pattern A: [T, T, T, F, F, F] (Find the last True)
• Pattern B: [F, F, F, T, T, T] (Find the first True)

The Invariant Template (l + 1 < r)

This approach minimizes off-by-one errors by maintaining an invariant where l and r always point to opposite boolean values.

• Invariant: check(l) is True, check(r) is False (or vice versa).
• Initialization: Set l and r to bounds outside the actual range (e.g., -1 and n) to handle edge cases gracefully.
• Termination: Loop ends when l + 1 == r. The boundary is exactly between l and r.

Code Template:

def check(mid):
    # Returns True if condition is met, False otherwise
    return nums[mid] <= target

def solve(nums, target):
    # Initialize pointers outside the array bounds
    l, r = -1, len(nums)

    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid  # l preserves the 'True' property
        else:
            r = mid  # r preserves the 'False' property

    return l # Returns the index of the last element satisfying check()

4. Binary Search on the Answer

This technique transforms an Optimization Problem (find the best X) into a Feasibility Problem (can X work?).

The Logic:

1. Guess a candidate answer ans.
2. Run check(ans) to see if it is valid.
3. If check(ans) implies that all values to one side are also valid/invalid (monotonicity), use Binary Search.

Type 1: Maximize the Minimum

• Goal: Make the smallest value in a set as large as possible (e.g., “Aggressive Cows”, “H-Index”).
• Pattern: [T, T, T, F, F] (Small values are possible, huge values are impossible).
• Strategy: Find the Last True.
• Check: Can we satisfy the condition if the minimum value is at least ans?

Type 2: Minimize the Maximum

• Goal: Make the largest value in a set as small as possible (e.g., “Split Array Largest Sum”, “Koko Eating Bananas”).
• Pattern: [F, F, F, T, T] (Small capacities fail, large capacities succeed).
• Strategy: Find the First True.
• Check: Is it possible to complete the task if the maximum load is limited to ans?

Prefix Sum

A prefix sum array p is a data structure that helps answer range sum queries efficiently. Given an input array a of length $n$, its prefix sum array p (also of length $n$) is defined as:

This means $p[i]$ stores the cumulative sum of all elements from the start of the array up to and including index $i$. For example, if:

Then the corresponding prefix sum array p is:

Properties

The prefix sum array has two key properties that make it useful:

1. Efficient Calculation: The array p can be computed in $O(n)$ time using a single pass:
   • Base Case: $p[0] = a[0]$
   • Recursive Relation: $p[i] = p[i - 1] + a[i]$ for $i > 0$
2. Constant-Time Range Sums: You can find the sum of any subarray $a[l \dots r]$ (the sum $a[l] + \dots + a[r]$) in $O(1)$ time: $$ \text{sum}(l, r) = p[r] - p[l - 1] $$

• Edge Case: If the range starts from the beginning ($l = 0$), the sum is just $p[r]$.

Code

from itertools import accumulate
from typing import List

def get_prefix_sum_v1(arr: List[int]) -> List[int]:
    """
    Computes the prefix sum array using the optimized
    itertools.accumulate function.

    Args:
        arr: The input list of numbers.

    Returns:
        The prefix sum list.
    """
    # Use list() to convert the 'accumulate' iterator to a list
    return list(accumulate(arr))

def get_prefix_sum_v2(arr: List[int]) -> List[int]:
    """
    Computes the prefix sum array using a manual loop.

    Args:
        arr: The input list of numbers.

    Returns:
        The prefix sum list.
    """
    # CRITICAL FIX: Handle the edge case of an empty list
    if not arr:
        return []

    n = len(arr)
    p = [0] * n  # Pre-allocate the list

    # Set the base case
    p[0] = arr[0]

    # Build the rest of the prefix sum array
    for i in range(1, n):
        p[i] = p[i - 1] + arr[i]

    return p

def query_range_sum(p: List[int], l: int, r: int) -> int:
    """
    Finds the sum of a subarray from index l to r (inclusive)
    using the precomputed prefix sum array 'p' in O(1) time.

    Args:
        p: The prefix sum array.
        l: The left-bound index of the query (inclusive).
        r: The right-bound index of the query (inclusive).

    Returns:
        The sum of the subarray arr[l...r].
    """
    # Assumes 0 <= l <= r < len(p)
    if l == 0:
        return p[r]
    else:
        return p[r] - p[l - 1]

# --- Example Usage ---

a = [1, 3, 4, 2, 5]

# v1 is the preferred, more Pythonic way
p = get_prefix_sum_v1(a)
print(f"Input array: {a}")
print(f"Prefix sum:    {p}")

# Query the sum from index 1 to 3 (i.e., 3 + 4 + 2)
# p[3] - p[1-1] = p[3] - p[0] = 10 - 1 = 9
sum_1_to_3 = query_range_sum(p, 1, 3)
print(f"Sum of range [1...3]: {sum_1_to_3}") # Output: 9

# Query the sum from index 0 to 2 (i.e., 1 + 3 + 4)
# p[2] = 8
sum_0_to_2 = query_range_sum(p, 0, 2)
print(f"Sum of range [0...2]: {sum_0_to_2}") # Output: 8

Two-dimensional Prefix Sum

Difference Arrays

1. For an array $a$, the difference array $\mathrm{diff}$ is defined as: $$ \mathrm{diff}[i] = a[i] - a[i - 1], \quad \text{where } a[0] = 0. $$
2. Computing the prefix sums of the difference array restores the original array: $$ \mathrm{diff}[1] + \mathrm{diff}[2] + \dots + \mathrm{diff}[i] = a[1] + (a[2] - a[1]) + \dots + (a[i] - a[i - 1]) = a[i]. $$
3. To perform range addition on the original array (adding $x$ to all elements in the interval $[l, r]$), the operations on the difference array are: $$ \mathrm{diff}[l] \mathrel{+}= x, \quad \mathrm{diff}[r + 1] \mathrel{-}= x. $$

Two-dimensional Difference Arrays

To perform range addition between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, do

Quicksort is a Divide and Conquer algorithm.

1. Divide (Pick Pivot): Choose one element from the array to be the pivot.
2. Conquer (Partition): Rearrange the array so that the pivot is in its final sorted position. All elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. (Elements equal to the pivot can go on either side, depending on the scheme).
3. Combine (Recurse): Recursively apply the same strategy to the two smaller subarrays—the one to the left of the pivot’s new position and the one to the right. The “combine” step is trivial as the sorting happens in place.

def partition(a, left, right):
    """
    Partitions the subarray a[left...right] using the Lomuto scheme
    with a[left] as the pivot.

    Returns the final index of the pivot.
    """
    # The pivot is the first element
    pivot_value = a[left]

    # 'idx' will track the boundary of the 'less-than-or-equal-to' partition.
    # All elements at indices [left+1 ... idx-1] will be <= pivot.
    idx = left + 1

    # Iterate through the array to partition it
    for i in range(left + 1, right + 1):
        # If current element is smaller or equal to the pivot
        if a[i] <= pivot_value:
            # Move it to the 'less-than' partition
            a[idx], a[i] = a[i], a[idx]
            # Expand the 'less-than' partition
            idx += 1

    # At the end, swap the pivot (originally at a[left]) with
    # the last element of the 'less-than' partition (at a[idx - 1])
    # to put the pivot in its final sorted position.
    pivot_final_index = idx - 1
    a[left], a[pivot_final_index] = a[pivot_final_index], a[left]

    return pivot_final_index


def quicksort(a, left, right):
    """
    Sorts the array 'a' in-place from index 'left' to 'right'
    using the quicksort algorithm.
    """
    if left < right:
        # Partition the array and get the pivot's final index
        pivot_index = partition(a, left, right)

        # Recursively sort the two subarrays
        quicksort(a, left, pivot_index - 1)  # Subarray to the left of pivot
        quicksort(a, pivot_index + 1, right) # Subarray to the right of pivot

The algorithm breaks the problem down into smaller, manageable pieces and then reassembles them in a sorted order. This happens in three main phases:

1. Divide: The list is repeatedly divided in half until you are left with many small lists, each containing only one element. A list with one element is considered, by definition, to be sorted (this is the base case for the recursion).
2. Conquer: This phase is trivial. Since the base-case lists (of one element) are already sorted, there’s no work to do. The real work happens in the “Combine” step.
3. Combine (The “Merge”): This is the core of the algorithm. Merge sort begins to combine (or “merge”) the small, one-element lists back together, two at a time. Crucially, it merges them in sorted order. It then takes those newly sorted lists (now of 2 elements) and merges them together, and so on, until the entire list is reassembled into one final, sorted list.

def merge_sort(arr):
    """
    Sorts a list in ascending order using the merge sort algorithm.
    """

    # Base case: A list with 0 or 1 elements is already sorted
    if len(arr) <= 1:
        return arr

    # 1. Divide: Split the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 2. Conquer: Recursively sort each half
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    # 3. Combine: Merge the two sorted halves
    merged = []
    i = 0  # Pointer for sorted_left
    j = 0  # Pointer for sorted_right

    # Loop while both halves have elements to compare
    while i < len(sorted_left) and j < len(sorted_right):
        if sorted_left[i] < sorted_right[j]:
            merged.append(sorted_left[i])
            i += 1
        else:
            merged.append(sorted_right[j])
            j += 1

    # At this point, one of the halves is empty.
    # Add all remaining elements from the non-empty half.
    merged.extend(sorted_left[i:])
    merged.extend(sorted_right[j:])

    return merged

# --- Example Usage ---
my_list = [38, 27, 43, 3, 9, 82, 10]

print(f"Original list: {my_list}")
sorted_list = merge_sort(my_list)
print(f"Sorted list:   {sorted_list}")

Bucket sort is a non-comparison sorting algorithm that works by distributing the elements of an array into a number of “buckets.” It is highly efficient when the input data is uniformly distributed (i.e., spread out evenly) across its range.

The algorithm follows these four main steps:

1. Initialize Buckets: First, create a fixed number of empty buckets (in your case, bucket_count).
2. Scatter: Iterate through the input array. For each element, calculate its proper bucket index (based on its value relative to the min/max values) and place the element into that bucket.
3. Sort Buckets: Go through each bucket, one by one, and sort the elements within it. This is typically done using another algorithm like insertion sort (or, in this case, Python’s built-in sort()).
4. Gather: Finally, concatenate the sorted buckets in order (from bucket 0 to the last bucket) to reassemble the full, sorted array.

from itertools import chain

def bucket_sort(arr, bucket_count):
    """
    Sorts a list in ascending order using the bucket sort algorithm.
    """

    # 1. Edge case: Handle empty or single-element lists
    if len(arr) <= 1:
        return arr

    # 2. Initialize Buckets & Find Range
    min_val, max_val = min(arr), max(arr)

    # Edge case: If all elements are the same, no sorting needed
    if min_val == max_val:
        return arr

    # Calculate the size of each bucket.
    # The '+1' ensures the range [min_val, max_val] is covered.
    bucket_size = (max_val - min_val + 1) // bucket_count
    # Fix for bucket_size becoming 0 if bucket_count > (max_val - min_val)
    if bucket_size == 0:
        bucket_size = 1

    buckets = [[] for _ in range(bucket_count)]

    # 3. Scatter: Distribute elements into buckets
    for x in arr:
        # Calculate the bucket index for the element
        idx = (x - min_val) // bucket_size
        # CRITICAL FIX: Ensure max_val lands in the last bucket
        idx = min(idx, bucket_count - 1)
        buckets[idx].append(x)

    # 4. Sort Buckets: Sort each individual bucket
    for bucket in buckets:
        bucket.sort() # Using built-in sort (Timsort)

    # 5. Gather: Concatenate the sorted buckets
    return list(chain(*buckets))

# --- Example Usage ---
my_list = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
# Using bucket_count = 5
sorted_list = bucket_sort(my_list, 5)
print(f"Original list: {my_list}")
print(f"Sorted list:   {sorted_list}")

my_list_2 = [29, 25, 3, 49, 9, 37, 21, 43]
# Using bucket_count = 4
sorted_list_2 = bucket_sort(my_list_2, 4)
print(f"\nOriginal list: {my_list_2}")
print(f"Sorted list:   {sorted_list_2}")

Selection sort works by conceptually dividing the list into two parts:

1. A sorted subarray, which is built up from left to right at the beginning.
2. An unsorted subarray, which makes up the rest of the list. The algorithm iterates through the list, and at each step $i$ (from $i = 0$ to $n-1$):
3. Find: It finds the smallest element in the unsorted subarray (i.e., from index $i$ to the end).
4. Swap: It swaps that smallest element with the element at the first position of the unsorted subarray (which is index $i$).

def selection_sort(arr):
    """
    Sorts a list in ascending order using the selection sort algorithm.
    """
    n = len(arr)

    # Outer loop: Move the boundary of the sorted subarray
    # This corresponds to your "i-th position"
    for i in range(n):

        # Step 1: Find the index of the smallest element in the
        # remaining unsorted part (from index i to n-1)
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Step 2: Swap the found smallest element with the
        # element at the i-th position
        # This "puts the smallest element" into its final sorted place
        arr[i], arr[min_index] = arr[min_index], arr[i]

# --- Example Usage ---
my_list = [64, 25, 12, 22, 11]

print(f"Original list: {my_list}")
selection_sort(my_list)
print(f"Sorted list:   {my_list}")

1. Start with the second element (at index 1), assuming the first element (at index 0) is already a sorted list of one.
2. Store this current element in a temporary variable (let’s call it the key).
3. Compare the key with the elements in the sorted subarray, moving from right to left (i.e., from index $i-1$ down to 0).
4. Shift any element in the sorted subarray that is greater than the key one position to the right. This opens up a “gap” for the key.
5. Insert the key into the gap once you find an element smaller than it, or when you reach the beginning of the list.
6. Repeat this process, expanding the sorted subarray by one element each time, until the entire list is sorted.

def insertion_sort(arr):
    """
    Sorts a list in ascending order using the insertion sort algorithm.
    """

    # Start from the second element (index 1)
    # The first element (index 0) is treated as the initial sorted part
    for i in range(1, len(arr)):

        # Step 2: Store the current element to be inserted
        key = arr[i]

        # Step 3 & 4: Move elements of the sorted part (arr[0..i-1])
        # that are greater than key, one position to the right
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # Shift element to the right
            j -= 1

        # Step 5: Insert the key into its correct position
        arr[j + 1] = key

# --- Example Usage ---
my_list = [12, 11, 13, 5, 6]

print(f"Original list: {my_list}")
insertion_sort(my_list)
print(f"Sorted list:   {my_list}")

1. Make a “pass” through the unsorted part of the list, comparing every pair of adjacent items (from the beginning to the end of the unsorted section).
2. For each pair, if the item on the left is greater than the item on the right, swap them. This moves the larger element one position to the right.
3. After the first full pass, the largest element in the list will have “bubbled up” to the very last position.
4. Repeat the process for the remaining unsorted portion of the list (i.e., from the beginning up to the now-sorted end), making one less comparison each time. Continue until no more swaps are needed.

def bubble_sort(arr):
    """
    Sorts a list in ascending order using the bubble sort algorithm.
    """
    n = len(arr)

    # Outer loop for the number of passes
    for i in range(n):
        # A flag to optimize if the list becomes sorted early
        swapped = False

        # Inner loop for comparing adjacent elements
        # The range is (n-i-1) because the last 'i' elements are already in place
        for j in range(0, n - i - 1):

            # Compare adjacent elements
            if arr[j] > arr[j + 1]:
                # Swap them if the first is greater than the second
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no swaps occurred in a full pass, the list is sorted
        if not swapped:
            break

# --- Example Usage ---
my_list = [64, 34, 25, 12, 22, 11, 90]

print(f"Original list: {my_list}")
bubble_sort(my_list)
print(f"Sorted list:   {my_list}")

Matrix norms

Given a matrix $X \in \mathbb{R}^{m \times n}$, $\sigma_{i}(X)$ denotes the $i$-th largest singular value of $X$ and is equal to the square root of the $i$-th largest eigenvalue of $XX'$. The rank of $X$, denoted as $\mathrm{rank}(X) = r$ is the number of non-zero singular values.

Inner Product

Given $X, Y \in \mathbb{R}^{m \times n}$, the inner product between $X$ and $Y$, denoted by $\langle X, Y\rangle$, is defined as

Frobenius Norm

The norm associated with the inner product is called Frobenius norm:

The Frobenius norm of a matrix $X$ is also equal to the square root of the sum of the squares of the singular values of $X$:

Operator Norm, Induced 2-norm, Spectral Norm

The operator norm of a matrix is the largest singular value

Nuclear Norm

The nuclear norm of a matrix is the sum of its singular values:

Dual Norms

For any given norm $\norm{}_{?}$ in an inner product space, there exists a dual norm $\norm{}_{d}$ defined as

Moreover, the dual norm of the operator norm/induced 2-norm/spectral norm is the nuclear norm. That is,

Proof

We first use the fact that given a matrix $X \in \mathbb{R}^{m \times n}$ and $t > 0$,

This is because

Using Schur’s complement,

This means that we can find the value of $\norm{X}$ via optimization (SDP):

We can rewrite the definition of dual norm

as

Now, let $X = UDV'$ be the singular value decomposition of $X$ whose rank is $r$. By definition

Let $Y := UV'$. Then,

and

This means that $Y := UV'$ is feasible for the optimization model above. If $Y := UV'$ is the optimal solution, then $\norm{X}_{d} = \norm{X}_{*}$. If $Y := UV'$ is not the optimal solution, then there exist other $Y$ such that $\mathrm{Tr}(X'Y) > \norm{X}_{*}$. Hence,

We now need to show that

We first re-write the definition of dual form into a semi-definite program:

The following program is the dual of the semi-definite program above:

If $W_{1} := UDU'$ and $W_{2} := VDV'$. Then, $(W_{1}, W_{2})$ is feasible for the dual, since

Moreover,

Thus, the objective is

Whether or not $(W_{1}, W_{2})$ is the optimal solution, we showed that

Hence,

This result shows that we can compute the nuclear norm via SDP.

References

Recht, Benjamin, Maryam Fazel, and Pablo A. Parrilo. "Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization." _SIAM review_ 52.3 (2010): 471-501.

Estimating LP bounds

Given an optimization problem

Suppose the maximum profit is $p^\star$. How can we bound $p^\star$? The lower bound of $p^\star$ can be found by picking any feasible point (since maximization). For example, $\{f=0, s=0\}$ is feasible. Therefore, $p^\star \geq 12f + 9s = 0$. Since any feasible point yields a lower bound of $p^\star$ and $p^\star$ itself is yielded by an feasible point, then finding the largest lower bound of $p^\star$ is equivalent to solving the LP.

The upper bound of $p^\star$ can be found using the constraints. For example, since $f$ and $s$ need to be less than $1000$ and $1500$ respectively, $p^\star \leq 12 \cdot 1000 + 9 \cdot 1500 = 25500$. We can include more constraints and have $p^\star \leq f + (4f + 2s) + 7(f + s) \leq 1000 + 4800 + 7 \cdot 1750 = 18050$. There are many different ways to combine these constraints to yield an upper bound of $p^\star$. We need to find the best way of combining these constraints so that it yields the best upper bound. To achieve this goal, we can choose 4 multipliers $\lambda_{1}, \lambda_{2}, \lambda_{3}, \lambda_{4} \geq 0$ to be the multipliers of our 4 constraints. We want the 4 multipliers to satisfy the following inequality, for any feasible $f$ and $s$,

Note that we can rearrange this inequality and obtain

Since the original problem is an LP, $f$ and $s$ have to be non-negative. Hence, to satisfy the inequality above, all we need to have is to satisfy

and

The $\lambda$’s that satisfy the constraints above yield an upper bound of $p^\star$

Finding the smallest upper bound would be yet another LP, i.e.

Primal and Dual

The first maximization problem is called the primal problem. The second minimization problem is called the dual problem. The $\lambda$’s in the dual problem are called the dual variable, and there is a dual variable corresponding to each constraint in the primal problem. Similarly, each constraint in the dual problem corresponds to a primal variable as well. Let $p^\star$ and $d^\star$ denote the optimal for the primal and the dual respectively. Then, they should satisfy the following inequality

In general, a primal problem $(P)$ is stated as

and a dual problem $(D)$ is stated as

If $x$ and $\lambda$ are feasible points of $(P)$ and $(D)$, then

If $p^\star$ and $d^\star$ exist and are finite, then $p^\star = d^\star$. This property is known as strong duality.

Properties of LP Duality

1. $(P)$ and $(D)$ are both feasible and bounded, and $p^\star = d^\star$
2. $(P)$ is unbounded and $(D)$ is infeasible, $p^\star = \infty$ and $d^\star = \infty$
3. $(P)$ is infeasible and $(D)$ is unbounded, $p^\star = -\infty$ and $d^\star = -\infty$
4. $(P)$ is infeasible and $(D)$ is infeasible, $p^\star = -\infty$ and $d^\star = \infty$
5. The dual of the dual is the primal

Duality and Sensitivity

Duality is related to the idea of sensitivity: how much each of your constraints affect the optimal cost.

Complementary Slackness

At the optimal point, some inequality constraints become tight. Some inequality constraints may remain loose, even at optimality. These constraints have slack. Either a primal constraint is tight or its dual variable is zero. Either a dual constraint is tight or its primal variable is zero. These properties are called complementary slackness. We can use complementary slackness to check if a proposed point is optimal or not.

Networks

Network Interface Controllers (NICs) can connect a computer to different physical mediums, such as Ethernet and Wi-Fi. Every NIC in the world has a unique MAC (media access control) address. It consists of 48 bits. Therefore, there are 28 trillion possible MAC addresses. Some devices randomly change their MAC address for privacy.

You can use command ifconfig to check you network interface controller and its corresponding MAC address. There exists virtual interfaces as well. For example, lo, the loopback device, is a virtual interface. It connects your computer to a mini network containing just your computer.

A network has nodes that send bytes to other nodes by MAC address. Nodes can be computers, switches, etc. The bytes are directed, or forwarded by switches. The whole network uses the same physical tech (Wi-Fi, Ethernet, etc.)

Internets and the Internet

Routers connect networks together to form internets. The global internet we all use is the Internet. Packets, which are some bytes with an address and other info, can be forwarded along a path from point A to point B. Routers contain forwarding tables that help them decide which direction to send along a packet. Those tables would be too big if a router had to know where every MAC address existed in the internet.

IP addresses are used to send packets across an internet. There are about 4 billion possible IP address (IPv4). Forwarding tables only need to know which way to send for a given network number, which is encoded in the IP address.

The challenge is that we don’t have enough IPv4 addresses. We don’t want every machine to be able to receive packets from anywhere. Private networks have private ranges. Different private networks can have the same IP address.

Network address translation (NAT) converts a public IP into a private IP. Only NAT knows the public address of a computer. The network interface of the computer does not know that.

Computers might be running multiple processes using the network. The IP address corresponds to a NIC, and the port number corresponds to a process.

Transport Protocols

User Datagram Protocol (UDP) Transmission Control Protocol (TCP) These two protocols both build on IP networking and both provide port numbers.

sudo lsof -i tcp -P

The difference between UDP and TCP is reliability. Packets may be dropped, reordered, and split. TCP saves and reassembles packets in order to provide the original message when possible. It retransmits dropped packets; UDP does not do this extra work.

Application Protocols

HTTP

Hypertext Transfer Protocol (HTTP): URL (domain/IP + port + resource)

HTTP messages between clients and servers: A client sends a request to a server. And the server sends a response back to the client. There are 4 common types of request: POST, PUT, GET, and DELETE.

RPC

Remote Procedure Calls (RPCs), helps us to call a function on the other computer. For example, a client can call a function on the server. (client application and server application do not need to write in the same programming language).

There are many tools for RPCs (Thrift, gRPC). gRPC builds on HTTP. Whenever we make a call, we make an HTTP POST request. The return value is returned through an HTTP response.

Serialization/Deserialization (Protobufs)

How do we represent arguments and return values as bytes in a request/response body? Serialization is converting various types into bytes. Deserialization converts bytes to various types. The challenge is that every language has different types and we want cross-languages calls. gRPC uses Google’s Protocol Buffers provide a uniform type system. The other challenge is that different CPUs order bytes differently. Some CPUs have big-endian, and some have little-endian. Protobufs help us to deal with this.

For computational efficiency, int32 uses 4 bytes during computation. For space efficiency, smaller numbers in int32 uses fewer bytes (4 bytes is max). This reduces network traffic. This is called variable-length encoding.

gRPC

Proto file:

syntax = "proto3";

service Calc {
  rpc Mult(MultReq) returns (MultResp);
}

message MultReq {
  int32 x = 1;
  int32 y = 2;
}

message MultResp {
  int32 result = 1;
}

Generate code

python3 -m grpc_tools.protoc -I=. --python_out=. --grpc_python_out=. XXXX.proto

Server file

import grpc
from concurrent import futures
import math_pb2_grpc
import math_pb2

class Calc(math_pb2_grpc.CalcServicer):
    def Mult(self, request, context):
        print(request)
        result = request.x * request.y
        return math_pb2.MultResp(result=result)

server = grpc.server(futures.ThreadPoolExecutor(max_workers=10), options=[("grpc.so_reuseport", 0)])

math_pb2_grpc.add_CalcServicer_to_server(Calc(), server)

server.add_insecure_port('localhost:5444')
server.start()
print("Listening to port 5444...")
server.wait_for_termination()

Client file

import grpc
import math_pb2
import math_pb2_grpc

channel = grpc.insecure_channel("localhost:5444")
stub = math_pb2_grpc.CalcStub(channel)

response = stub.Mult(math_pb2.MultReq(x=3, y=4))
print(response)

Virtualization

Virtualization is the illusion of private resources, provided by the software. We have virtual memory, virtual machine (hardware), virtual machine (languages), virtual operating system (container).

• Each process using a virtual address space is not aware of other processes using memory (illusion of private memory).
• Virtualized resources include CPU, RAM, disks, network devices, etc. VMs rarely use all their allocated resources, so overbooking is possible. If each program is deployed to a different VM, operating system overheads dominate.
• JVM or PVM runs Java Bytecode and Python Bytecode. Programs written in Java and Python are compiled to their corresponding byte code instead of a specific machine code.
• Virtual operating systems, or a containers, are run on a some flavor of Linux. You can have a container of Ubuntu and a container on Debian (but not Windows, since they are running on top of Linux). Containers are more efficient than virtual machines, but less flexible.

Containers and Virtual Machines are Sandboxes.

Docker Containers

Containers are lightweight alternative to virtual machines. Virtual machines form a cluster. Resources of the cluster are limited to those of a single VM that runs there containers.

Registries, Images, Containers, and Dockerfiles

The Images and the Containers are going to be on your VM. The images are pulled from the Registries (dockerhub, for example). Images are snapshots of installed software. From these images, we can run them to start a container. We can also build our own images and run them later.

Docker Commands

1. docker images: to list all the images I currently have.
2. docker pull IMAGENAME: to pull an image. If the image is not installed, it will try to pull it first.
3. docker tag IMAGE:TAG NEW_TAG: to create a new tag for an existing image.
4. docker run TAG COMMAND: to run a container and let the container runs the command.
5. docker run -it TAG COMMAND: to run a container with the command interactively.
6. docker ps: to show all running containers
7. docker ps -a: to show all containers
8. docker ps -a -q: to show containers with ID only
9. docker rm $(docker ps -a -q): to delete all containers
10. docker rmi IMAGE: to remove an image
11. docker run -d IMAGE COMMAND: run a Docker container in daemon mode.
12. docker logs CONTAINER_ID: to show the output of a container
13. docker exec [-it] CONTAINER_ID: to jump into an existing running container
14. docker build DIRECTORY -t TAG: make a container from the dockerfile (in the current directory) and save it into DIRECTORY with a TAG.
15. docker run -d -p 127.0.0.1:300:80 IMAGE: redirect incoming data from port 300 to port 80

Dockerfile instructions

1. FROM: run which image
2. RUN: run which command
3. COPY: copy a program on my computer into the image
4. CMD: default command you want to run

 FROM ubuntu:22.10
 RUN apt-get update
 RUN apt-get install -y python3 python3-pip curl lsof
 RUN pip3 install jupyterlab==3.4.5 MarkupSafe==2.0.1
 CMD ["python3", "-m", "jupyterlab", "--no-browser", "--ip=0.0.0.0", "--port=80", "--allow-root", "--NotebookApp.token="]

SSH port forwarding

ssh USER@VM -L localhost:5000:localhost:300 client side listens to port 5000 sshd redirects data to port 300 on the server side.

Container Orchestration

Orchestration lets you deploy many cooperating containers across a cluster of Docker workers. Kubernetes is the most well known. Docker compose is a simpler too that lets you deploy cooperating containers to a single worker.

services:
  jupyter:
    image: myimg
    deploy:
      replicas: 3

1. docker compose up: compose containers using the yaml file in the current directory.
2. docker compose ps: show the containers created withe the yaml config file in the current directory.
3. docker compose logs: show the outputs of these containers.
4. docker compose down: remove composed containers.

Given a dataset \(\mathcal{D} = \{(\vec{x}_1, y_1), \cdots, (\vec{x}_N, y_N)\}\) and a hypothesis set \(\mathcal{H}\), our learning algorithm \(\mathcal{A}\) tries to learn a function \(g \in \mathcal{H}\) that approximates the underlying, true function \(f: \mathcal{X} \to \mathcal{Y}\), which generates the points in \(\mathcal{D}\).

In unsupervised learning, there are no labels associated with features. Generally speaking, the ultimate goal of unsupervised learning is to find patterns and structures that help us to better understand data. Sometimes, we also use unsupervised learning to model a distribution. But we generally will not make predictions.

There are 3 types of clustering 1. Partitional (centroid, graph-theoretic, spectral) 1. Hierarchical (agglomerative, divisive) 2. Bayesian (decision-based, non-parametric)

There are two major steps in the K-means algorithm. The first one is to calculate the representatives (centroids) of a given partition. The second one is to find the partition based on the representatives.

dataset = np.array([[5, 6],
                    [6, 5],
                    [0, 1],
                    [1, 0],
                    [3, 3]])

partition = [[0, 3, 4], [1, 2]]

def find_centroids(dataset: np.ndarray, partition: list) -> np.ndarray:
    """
    find the centroids of the given partition
    """
    u = []
    for indices in partition:
        if len(indices) == 0:
            u.append(np.zeros((dataset.shape[1], )))
        else:
            u.append(np.mean(dataset[indices], axis=0))
    return np.array(u)

def new_partition(dataset: np.ndarray, u: np.ndarray) -> list:
    """
    find the new partition based on u
    """
    partition = [[] for _ in range(u.shape[0])]
    for i, point in enumerate(dataset):
        argmin = np.argmin(np.linalg.norm(point - u, axis=1))
        partition[argmin].append(i)
    return partition

def kmeans(dataset: np.ndarray, partition: list):
    """
    K-means algorithm, k can be inferred from the shape of partition
    """
    epoch = 0
    losses = {"epoch": [], "loss": []}

    while epoch < 3:
        epoch += 1

        u = find_centroids(dataset, partition)
        partition = new_partition(dataset, u)

    print("\n\nFinal Centroids:")
    print(u)
    print("Final Partition:")
    for i, indices in enumerate(partition):
        print("\tcluster #{}:".format(i + 1), {tuple(dataset[index])
                                               for index in indices})