Skip to content
academia.sh
tr
Log in

Course Advanced

Advanced Algorithms and Problem Solving

By the end of this course

Start course

01

Algorithm Design Approaches

Brute force's role as an oracle, the divide-and-conquer recurrence, the systems where greedy choice is wrong, memoization's overlap condition, the search space pruning cuts, and randomization's expected performance.

  1. 01 Brute Force and Its Limits Brute force's role in this course is not a slow option but an oracle: exhaustive counting spends 2640 steps on 40 inputs, early-exit pruning gives the same answer in 866 steps, and sampling that looks only at the first six positions diverges from the oracle on 14 inputs in 406 steps.
  2. 02 Divide and Conquer Splitting and combining are separate calculations: on the same split, linear combining spends 1.16 times fewer steps than the oracle and stays correct on all 40 inputs, while quadratic combining is 1.71 times slower than the oracle, and incomplete combining, which skips the boundary-crossing solution, gives a wrong answer on 40 of 40 inputs with 920 steps.
  3. 03 Greedy Algorithms Greedy choice is not a procedure until it is proven: on 827 of 969 four-value coin systems, greedy gives more coins than necessary, a ratio of 0.8535, with the largest excess being 16 coins; when the same error is tested only up to amount 10 instead of 50, it appears in just 85 of the systems.
  4. 04 Dynamic Programming Memoization's two conditions, both counted: in overlapping subproblems, calls drop from 21,891 to 39, while in non-overlapping ones both stay at 39 and the memo table holds 19 entries for nothing; when the memo's key does not carry the whole state, the approach diverges from the oracle on 39 of 40 inputs.
  5. 05 Backtracking Pruning is the one shortcut that preserves correctness, and what happens when its criterion breaks: on a seven-queens board, pruned search visits 552 nodes and unpruned search 960,800, but over-pruning, which also cuts the neighboring column, finishes in 82 nodes and loses every solution.
  6. 06 Randomized Algorithms Randomness can be used in two separate places, and the two are measured separately: unverified sampling returns a wrong value on all 40 of the 40 arrays with no majority, while verified sampling never errs on the same arrays, and on a sixteen-queens board, random column order brings a 10,053-node deterministic search down to an average of 360 nodes.

02

Problem-Solving Patterns

Measuring the two pointers, sliding window, fast and slow pointer, interval merging, cyclic sort, two heaps, selection, and grid traversal patterns by their preconditions and the wrong answers they give when those preconditions break.

  1. 01 Two Pointers Scanning from both ends of a sorted array; the 25 wrong answers that appear once the precondition breaks and the step cost of establishing that precondition.
  2. 02 Sliding Window Incremental computation over a contiguous subarray; the 10 inputs where a negative value breaks the shrink rule and why the precondition belongs to the window, not the rule.
  3. 03 Fast and Slow Pointer Cycle detection and the middle element using two pointers moving at different speeds; the 14 cycles a second edge makes invisible and the cost of never stopping.
  4. 04 Interval Merging Reducing overlapping intervals in a single pass; the 29 inputs a wrong sort key breaks the merge on, and the 8 inputs an event-ordering rule changes the answer for.
  5. 05 Cyclic Sort In-place placement without comparison over a bounded value range; the pattern that never stops on duplicate values, 40 wrong answers on out-of-range values, and what the guard does not fix.
  6. 06 Two Heaps Median tracking in a stream; how removing the rebalancing step corrupts 295 of 480 medians, and how the pattern's gain grows as the stream lengthens.
  7. 07 K-th Element Heap-based and partition-based solutions to selection problems; the 27 diverging inputs that appear once the question shifts, and the 15-fold step increase from pivot choice.
  8. 08 Grid Traversal Connected-component search on a matrix; how the connectivity definition changes the answer on 38 grids, and what marking and traversal choice do to held cell count.

03

Classical Problems

Comparing solutions to the knapsack, travelling salesman, longest path, n-queens, knight's tour, and Hamiltonian path problems against an oracle, and measuring the deviation of approximate solutions.

  1. 01 The Knapsack Problem The same greedy order giving two different results in two variants: in the fractional knapsack, the same answer as the oracle on 40 of 40 inputs, at 579.3 times fewer steps; in the 0/1 variant, the same order splits from the oracle on 5 of 40 inputs, with a worst loss of 7 value units. Dynamic programming matches the oracle on 40/40 in 4544 steps, against the oracle's 15,360. On the second input pool, the split count is 6, keeping the ratio at the same order of magnitude.
  2. 02 The Travelling Salesman Problem Making the best tour found by exhaustive enumeration on eight cities the oracle, and measuring how far two approximate solutions deviate from it in percent: nearest neighbor splits from the oracle on 17 of 20 samples, with an average deviation of 9.3 percent and a worst case of 33.33 percent; the two-opt improvement brings the split count down to 2 and the average deviation down to 0.49 percent, in 819 steps. The oracle spends 352,800 steps on the same 20 samples. The growth of the search space is shown by counting, not by running it: at eighteen cities the tour count is 177,843,714,048,000. The question of why it is hard is referred to the Theory of Computation course.
  3. 03 The Longest Path Problem Turning the shortest-path relaxation toward the longest path and measuring it on two graph families: the same answer as the oracle on 40 of 40 inputs on acyclic graphs, splitting on 38 of 40 on cyclic graphs with a worst overshoot of 228 weight units; 39 on the second pool. The reason for the split is not that the procedure slows down but that what it is looking for changes: the relaxation finds the heaviest walk, while the problem asks for the heaviest simple path. The oracle is cheaper than the pattern at eight nodes; at thirteen nodes it becomes 86.37 times more expensive.
  4. 04 The N-Queens Problem Taking the shared definition's backtracking counts as input and measuring symmetry breaking on top of them: restricting the first queen to half the board brings the node count at eight queens from 2057 down to 1029, a ratio of 2.00; 1.69 at five queens, 1.78 at nine. The mirrored solutions restore the oracle's solution set exactly, on all five board sizes. The fundamental-solution count at eight queens is 12 instead of 92, but the smallest equivalence class is 4, not 8. Pruning's gain grows with n; symmetry breaking's gain stays fixed at 2 and buys nothing when finding the first solution.
  5. 05 The Knight's Tour and Maze Problems Representing the same grid with two different models and watching the search space change with the model: on a five-by-five grid, when the candidate solution is counted as a path, 8512 simple paths and 90,111 steps; when counted as a cell, 25 steps — a ratio of 3604, and both models give the same shortest length. In the knight's tour, trying the least-option square first finds the tour in 25 nodes on all four starting squares of a five-by-five board; natural order visits between 182 and 101,718 nodes. On a four-by-four board there is no tour at all, and both orderings visit exactly 29,976 nodes: the move-ordering heuristic buys nothing on a no answer.
  6. 06 Hamiltonian Paths Framing an existence question as a decision problem and counting decision, search, counting, and verification separately: a path exists on 25 of 40 graphs, and deciding spends 1526 steps while counting spends 29,270, a ratio of 19.18. On all 15 graphs where no path exists, the decision step count is exactly equal to the counting step count, both 2538. The second pool gives the same structure, with 23 and 17 graphs. Verifying a found path takes 7 steps per graph, searching for one takes an average of 61. The names of complexity classes are left to the Theory of Computation course.

04

Practice Discipline

Deriving a step budget from input size, verifying a solution by comparing it against an oracle, and counting repeated practice's progress metric through pattern diversity.

  1. 01 Problem Reading and Constraint Analysis Deriving a step budget from input size, and measuring that the budget alone cannot select the pattern: at n=12 the sorting pattern is 1.61 times costlier than the oracle, and a wrong constraint reading gives a wrong answer on 18 of 40 inputs.
  2. 02 Solution Verification Turning comparison against an oracle into a procedure: 40 random inputs catch four of five defects, 12 edge cases catch all five, and a diverging input shrinks from 12 values to 1 in 23 attempts.
  3. 03 Using Practice Environments Counting repeated practice's progress metric over the shared reference's five patterns: an environment that solves 144 problems sees all five patterns too, but its balance ratio is 0.2431, against 0.6667 in an environment that solves 30.

Start typing to search.

↑↓ ↵ Esc navigate · open · close