Linear Algebra I401-0131-00L

Leetcode for A&D

Graph traversal and dynamic programming problems, in a sensible order

The dynamic programming problems will start making way more sense after the course actually gets there. I would still recommend looking into DP on your own time, because it’s just such as big part of the exams (20/80 points last year). You can get ahead early and chill during Lernphase.

Dynamic programming

The best problems from The Ultimate Dynamic Programming Roadmap on r/leetcode.

1. Warm-up

Enough to get a feel for what a DP state is.

2. One sequence, constant transition

Solve the sub-problem on every prefix of the array, that is every subarray from 0 to i. Each state looks back a fixed number of steps.

3. Grids

The table has the same shape as the grid, and the state at cell (i, j) relates to the grid at (i, j).

4. Two sequences

dp[i][j] is the answer for the first i entries of one sequence against the first j of the other.

5. Intervals

The problem is solved on every interval of the array, not just every prefix.

6. One sequence, transition from every earlier index

Prefixes again, but the state at i is built from every j < i. Longest increasing subsequence is the model.

7. Knapsack

The state is the classical knapsack state: how much of the input used, and the total so far.

8. Topological order on graphs

Optional. Solve the problem on every subgraph reachable from a node.

9. Trees

Optional. Solve the problem on every subtree.

Graph traversal: DFS and BFS

Graph traversal is the second most important thing you learn in this course. You have to know DFS/BFS by heart for the exam. This is also extremely common on Quant/SWE internship interviews so get ahead.

1. First traversals

The traversal on its own, with nothing else going on. Start on trees: a binary tree is the simplest graph there is, and the traversal is just recursion. Handle this node, then call yourself on the children. Do not skip these because they look trivial, this is where the pattern is learned.

2. Grids

A grid is a graph whose neighbours are the four adjacent cells. Seeing that is most of the work.

3. Multi-source BFS

Push every starting cell into the queue before the first step. The layers then give distances to the nearest source.

4. Graphs

Adjacency lists, connected components, cycles and topological order.

5. Shortest paths without weights

Exactly where BFS beats DFS. Knowing why is worth an exam question.

Always good to know.

1. The loop itself

Write it once from memory, then again tomorrow. Everything else here is this loop with a different condition.

2. Boundaries

Finding the first or last index that satisfies a condition. This is where the off-by-one errors live, so do all of them.

3. When the array is not plainly sorted

Sorted, but rotated or folded into two dimensions. The invariant is still there, you just have to find it.

4. Binary search on the answer

The one worth knowing. There is no array: you guess an answer, check whether it is achievable, and halve the range. Once you see it you will see it everywhere.