Skip to main content
@shmVirus

Algorithms

A proof-driven, implementation-focused study of algorithm design: correctness, complexity, searching, recursion, sorting, backtracking, dynamic programming, greedy methods, string matching, graph algorithms, network flow, and computational limits.

Algorithmic thinking turns a problem into a precise contract, derives a method that satisfies it, proves that the method works, and accounts for the resources it consumes. Correctness and complexity support searching, recursive decomposition, sorting, backtracking, dynamic programming, greedy design, string matching, graph optimization, network flow, and complexity classification.

Each chapter restates or identifies the small C or data-structure interface it needs, while the dedicated courses provide fuller implementation treatment. The focus remains the algorithmic model, invariant, design choice, proof, applicability condition, and cost.

Outline

Start →
  1. 01
    CorrectnessProblem and algorithm specifications, assertions, Hoare triples, sorting contracts, partial and total correctness, loop invariants, recursive proofs, proof obligations, termination, counterexamples, randomized algorithms, floating-point limits, testing, and a complete lower-bound proof.
  2. 02
    ComplexityInput size, cost models, timing limits, operation counts, asymptotic notation, growth rates, space complexity, summations, best/average/worst cases, break-even analysis, amortized accounting and potentials, adversarial lower bounds, and time-space trade-offs.
  3. 03
    SearchingLinear and sentinel search, binary invariants, lower and upper bounds, duplicate handling, rotated arrays, exponential search over unknown lengths, interpolation search, monotone answer search, sorted-matrix search, query workloads, adversarial lower bounds, and strategy selection.
  4. 04
    Recursive DesignRecursive decomposition, call stacks, Tower of Hanoi, Ackermann growth, branching recursion, divide and conquer, recurrences, substitution, recursion trees, the Master Theorem, Karatsuba multiplication, uneven splits, maximum subarray, interface design, iterative conversion, and stack-depth analysis.
  5. 05
    SortingSorting contracts, stability, adaptivity, in-place storage, selection, bubble and insertion sorts, merge sort, Lomuto and three-way quicksort, heapsort, comparison lower bounds, counting and radix sorts, external sorting, quickselect, adversarial inputs, and strategy selection.
  6. 06
    BacktrackingSearch trees, candidate states, reversible mutation, feasibility and bound pruning, duplicate-safe permutations, N-Queens, signed subset sum, Hamiltonian cycles, Sudoku with validated state, branch-and-bound, state reuse, memoization, candidate ordering, and search-tree cost.
  7. 07
    Dynamic ProgrammingOverlapping subproblems, optimal substructure, state design, memoization, tabulation, minimum coin change, zero-one knapsack, witness recovery, LCS with Hirschberg reconstruction, maximum subarray, quadratic and n-log-n LIS, matrix-chain interval DP, space optimization, and pseudo-polynomial time.
  8. 08
    Greedy AlgorithmsGreedy-choice properties, exchange and staying-ahead proofs, cut properties, activity selection, interval partitioning, deadline scheduling, fractional knapsack and numeric models, Huffman coding and prefix trees, matroid structure, counterexamples, and strategy selection.
  9. 09
    String MatchingExplicit-length matching models, naive matching, polynomial rolling hashes, Rabin–Karp verification, prefix and failure functions, KMP invariants, finite automata, shared algorithm traces, Aho–Corasick multi-pattern matching, byte and Unicode symbol streams, callback reporting, complexity, and strategy selection.
  10. 10
    Graph TraversalTraversal colors and parent forests, breadth-first search and shortest unweighted paths, path recovery, depth-first search, discovery times, edge classification, directed and undirected cycle detection, bridges and articulation points, components, bipartite testing with odd-cycle certificates, topological sorting, and strongly connected components.
  11. 11
    Spanning TreesSpanning trees and forests, minimum spanning trees, cut and cycle exchange properties, reverse delete, Kruskal with union-find, Prim with matrices and heaps, correctness, uniqueness, optimality verification, bottleneck paths, maximum-spacing clustering, complexity, and method selection.
  12. 12
    Shortest PathsWeighted path models, optimal subpaths, checked relaxation, path recovery, DAG paths, Dijkstra with settling and priority queues, Bellman–Ford rounds and negative-cycle certificates, Floyd–Warshall, Johnson reweighting, single-source and all-pairs query workloads, numeric safety, preconditions, and strategy selection.
  13. 13
    Network FlowFlow networks, capacities and conservation, residual rerouting, augmenting paths, flow decomposition, Ford–Fulkerson, Edmonds–Karp, minimum-cut certificates and duality, bipartite matching, capacity scaling with its cut bound, Dinic level graphs, lower bounds and circulation demands, complexity, reductions, and applications.
  14. 14
    NP-CompletenessLanguages, decision and optimization problems, self-reduction, P and NP, certificates and verifiers, polynomial reductions, NP-hardness, NP-completeness, Cook–Levin, classic problems, pseudo-polynomial time, backtracking, branch-and-bound, meet-in-the-middle, integer programming, SAT and SMT encodings, approximation, parameterization, local search, annealing, and heuristic evaluation.