Data Structures and Algorithm Analysis

Data structures are evaluated not only by what they represent but also by the cost of their operations. Arrays, linked lists, stacks, queues, trees, hashing, and graphs are therefore presented together with algorithm analysis. Worst-case, average-case, and amortized costs are distinguished where that difference affects the engineering decision.

Unit 1: Introduction and Fundamental Concepts

1.1. Software, Programs and Hardware

A program is executable logic expressed in some representation; software is broader and includes code, configuration, data, documentation and supporting artifacts. Hardware provides the processor, memory and I/O resources on which software executes.

A data structure sits between the problem's information model and the machine's memory model. Choosing a structure determines not only how values are represented but also which operations are cheap or expensive.

1.2. Operating System

The operating system provides abstractions such as processes, virtual memory, files and sockets. Data-structure code ultimately uses resources managed through these abstractions, so memory allocation and I/O costs cannot be ignored when evaluating a real implementation.

1.3. Data Structure and Data Model

A data model describes conceptual relationships. A data structure is a concrete organization used to implement operations on data.

For example, a set can be modeled abstractly as an unordered collection of unique elements and implemented with a hash table, balanced tree, bitset or sorted array depending on constraints.

1.4. Algorithm

An algorithm is a finite, unambiguous sequence of operations that solves a stated problem. Correctness and complexity are separate questions: an algorithm can be correct but impractically slow or memory-hungry.

1.5. Execution Speed and Memory Requirement

Performance must be discussed against input size and workload. One isolated timing number is not an algorithmic complexity result.

Useful questions include:

• how many primitive operations grow with n,
• how much additional memory is required,
• which memory accesses are contiguous or random,
• whether allocation or I/O dominates,
• whether worst-case latency matters more than average throughput.

1.6. Processor, Machine Code and Assembly

High-level operations eventually become machine instructions, but source-level operation count does not map one-to-one to CPU cycles. Compilers, caches, branch prediction, vectorization and memory latency all affect actual runtime.

Assembly and machine-code awareness is useful when investigating low-level cost, but asymptotic analysis deliberately abstracts away a particular processor implementation.

1.7. Programming Languages

The same abstract data structure can have different concrete costs depending on the language/runtime. Manual allocation in C, RAII containers in C++, garbage-collected objects in Java and contiguous numerical arrays in other systems can represent the same logical structure with different memory layouts.

1.8. Database and SQL

Database systems implement their own indexing, hashing, trees, sorting and graph-like execution structures. SQL remains declarative, but query performance depends heavily on physical data structures and algorithms chosen by the optimizer.

1.9. Divide and Conquer

Divide-and-conquer algorithms:

1. divide a problem into smaller subproblems,
2. solve them recursively or iteratively,
3. combine the results.

Merge sort and binary search are classic examples. Recurrence relations describe the cost:

T(n) = a T(n/b) + f(n)

for many divide-and-conquer families.

1.10. Benchmarking

A benchmark measures one concrete implementation under one environment. It should include warm-up/runtime effects where relevant, representative data distributions and enough repetitions to distinguish signal from noise.

Benchmark results complement complexity analysis; they do not replace it.

Unit 2: Data Structures and Representation

Data structure selection begins by specifying the required operations: search, insertion, deletion, ordered traversal, and random access carry different costs. Evaluate worst-case time and auxiliary memory alongside expected complexity. A change in data distribution or access pattern may justify reconsidering the choice. When comparing functionally equivalent structures, consider the operations that dominate at scale rather than relying solely on timing small test inputs.

2.1. From Raw Data to Information

Raw values acquire meaning through type, structure and context. A byte sequence can represent text, integers, floating-point numbers, serialized records or instructions depending on interpretation.

2.2. Classification

Data structures can be classified in several overlapping ways:

• linear vs non-linear,
• contiguous vs linked,
• static-size vs dynamic,
• ordered vs unordered,
• hierarchical vs network/graph,
• mutable vs immutable.

No classification alone determines performance.

2.3. Computer Memory

Memory is byte-addressable on common systems, but language objects have alignment, size and lifetime rules. Contiguous structures benefit from spatial locality; pointer-rich structures may incur allocation overhead and cache misses.

2.4. Character Data

Character representation requires an encoding. ASCII historically maps basic characters to byte values; modern Unicode text may use variable-length encodings such as UTF-8. "One character equals one byte" is not a safe general assumption.

2.5. Unsigned and Signed Integers

An n-bit unsigned integer typically represents:

0 ... 2^n - 1

Two's-complement signed integers represent:

-2^(n-1) ... 2^(n-1)-1

The data structure storing an integer may be simple, but arithmetic overflow behavior depends on the programming language and type.

2.6. BCD

Binary-coded decimal stores each decimal digit separately. It uses more bits than pure binary for the same numerical range but preserves decimal digit representation, which can matter in display or decimal-centric systems.

2.7. Floating-point Values

IEEE 754 binary floating-point represents sign, exponent and significand. Many decimal values are not exactly representable, so comparisons and accumulated numerical error require explicit tolerance/error models where appropriate.

2.8. Strings

A string can be represented as:

• a null-terminated character array,
• a length plus contiguous storage,
• immutable shared storage,
• a rope/tree for very large editing workloads,
• language/runtime-specific objects.

Length, encoding and ownership semantics affect complexity.

2.9. Arrays

An array stores equal-type elements contiguously:

address(A[i]) = base + i * element_size

Random indexed access is O(1). Inserting/removing in the middle is generally O(n) because elements must move, unless order can be discarded or an indirection scheme is used.

2.10. Multidimensional Arrays

A multidimensional array maps several indices to one linear storage region according to a layout such as row-major or column-major. Traversal order affects cache locality.

2.11. Structures, Unions and bit-fields

A structure groups heterogeneous fields and can contain padding for alignment. A union overlays alternatives in one storage region. Bit-fields provide compact implementation-defined packing and are not automatically portable serialized formats.

Unit 3: Data Models

3.1. List

A list is an ordered sequence. It can be implemented with arrays, linked nodes, trees or chunked storage depending on operation requirements.

3.2. Linked List

A linked list stores links between nodes rather than requiring contiguous element storage. It supports cheap insertion/removal at a known node but has O(n) indexed access and weaker cache locality.

3.3. Tree

A tree represents hierarchical parent/child relationships. Many algorithms exploit recursive substructure and logarithmic height when the tree is balanced.

3.4. Graph

A graph models general relationships among vertices through edges. Trees are a restricted class of graphs; graph algorithms must account for cycles and multiple paths.

3.5. State Machine

A state machine is a graph whose nodes are states and edges are transitions conditioned on events/inputs. It is a data/control model used in protocols, parsers and embedded systems.

3.6. Relational Model

The relational model represents data as relations and uses set-oriented operators. Physical DBMS implementations still rely on arrays, B-trees, hash tables and other structures beneath the logical model.

3.7. Network Model

Historical network database models represent records and explicit link sets. The concept illustrates the difference between navigation through stored relationships and declarative relational querying.

Unit 4: Algorithmic Program Design

Algorithm correctness requires preconditions, postconditions, and invariants. In divide-and-conquer solutions, establish that subproblems become smaller and that combining their answers preserves correctness. For recursion, show that a base case is reachable; for iteration, identify a progress measure that ensures termination. Derive time complexity from dominant operations and report input-dependent memory growth separately.

4.1. Program Design

A reliable design begins from inputs, outputs, invariants and failure conditions. Data structures should be selected after identifying the operations the algorithm must support.

4.2. Pseudocode

Pseudocode documents logic without binding it to language syntax. It should be precise about loops, conditions and data updates but need not define machine-level details.

4.3. Real Code

The implementation adds type rules, memory ownership, error handling, library behavior and performance effects absent from pseudocode. Correct translation therefore requires preserving algorithm invariants, not merely copying control structure.

4.4. Flowcharts

Flowcharts can illustrate small decision/loop structures. For large algorithms, pseudocode and data-structure invariants are usually more compact.

4.5. Conditional Branching and Loops

Branching selects between paths. Loops repeat operations while maintaining an invariant. Nested loops do not automatically mean O(n^2); bounds and data dependence must be analyzed.

4.6. Quadratic Equation Roots

For:

a x^2 + b x + c = 0

the discriminant is:

D = b^2 - 4ac

A robust implementation must separately handle a = 0, negative discriminant for real-only output, and numerical precision. The textbook formula demonstrates branching but is also an example where numerical analysis matters.

4.7. Arithmetic Mean

For n > 0 values:

mean = sum / n

The algorithm is O(n) time and O(1) auxiliary space when streamed. Numeric type and overflow/precision can matter more than asymptotic complexity.

4.8. Finding the Minimum

A single-pass minimum scan performs n-1 comparisons for non-empty input:

min <- A[0]
for i = 1 .. n-1:
    if A[i] < min:
        min <- A[i]

Time is Theta(n) because every element may have to be inspected.

Unit 5: Time and Space Complexity

5.1. Algorithm Analysis

Complexity describes resource growth as a function of input size. It intentionally ignores constant machine-specific details when comparing scalability.

5.2. Big O

O(g(n)) is an asymptotic upper bound: beyond some point, f(n) is bounded above by a constant multiple of g(n).

5.3. Big Omega

Omega(g(n)) is an asymptotic lower bound.

5.4. Big Theta

Theta(g(n)) means both upper and lower bounds of the same order.

These notations describe mathematical growth, not automatically worst/best/average cases. One must state which cost function is being bounded.

5.5. Common Growth Classes

Typical orders are:

O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(n^3)
O(2^n)
O(n!)

For sufficiently large inputs, growth rate dominates constant-factor differences, although constants and locality remain important in real systems.

5.6. Best, Average and Worst Case

Linear search is:

• best case O(1),
• worst case O(n),
• average case O(n) under ordinary position assumptions.

Average-case analysis requires a probability/distribution model; it should not be asserted without one.

5.7. Amortized Analysis

Amortized analysis distributes occasional expensive operations over a sequence. Dynamic-array append is a classic example: some appends reallocate/copy O(n) elements, but geometric growth yields amortized O(1) append.

Amortized cost is not probabilistic average-case cost.

5.8. Space Complexity

Space analysis includes auxiliary structures, recursion depth, temporary arrays and metadata. In-place does not always mean O(1) total memory if recursion or runtime stacks grow with input.

5.9. Code Memory and Call Stack

Executable code consumes storage largely independently of input size for a fixed program, while recursive call stacks can grow with depth. Quicksort, tree traversal and DFS therefore have stack costs tied to recursion shape.

5.10. Benchmark versus Analysis

Complexity predicts growth; benchmarking measures one implementation. Cache locality can make an O(n) array scan much faster than an O(n) pointer chase despite the same asymptotic order.

Vectorization usually moves loop execution to another layer rather than eliminating the work. Summing a million contiguous numerical elements can benefit from much better cache locality than traversing a million separately referenced objects. Yet large temporary arrays may saturate memory bandwidth, and call overhead may dominate for small inputs. Slicing is not universally a constant-cost view: depending on the data structure and API it may allocate a copy. Asymptotic complexity, memory layout, allocation count and measured latency all need consideration when choosing an implementation.

Unit 6: Linked Lists

6.1. Singly Linked List

A node contains data and a next link:

[data | next] -> [data | next] -> ... -> null

Given a pointer to the insertion location/predecessor, insertion can be O(1). Searching for a value is O(n).

6.2. Array versus Linked List

Array:

• O(1) indexed access,
• contiguous memory/locality,
• middle insertion/removal usually O(n).

Linked list:

• indexed access O(n),
• insertion/removal at a known node can be O(1),
• per-node allocation and pointer overhead,
• weak spatial locality.

The theoretically cheaper insertion does not make linked lists universally faster.

6.3. Doubly Linked List

Each node stores previous and next links. Removal of a known node is direct because its predecessor is available, at the cost of another pointer and more link updates.

6.4. Circular List

A circular list links the final node back to the first or sentinel. It can simplify repeated round-robin traversal but requires careful termination conditions.

6.5. Dynamic Allocation and Ownership

Each allocated node must have one clear ownership strategy. Failure paths, deletion and list destruction must release every node exactly once.

6.6. Insert, Search and Delete

Head insertion is constant time. Tail insertion is constant time if a tail pointer is maintained, otherwise locating the end is linear.

Deleting by value requires search first (O(n)) unless an external index locates the node. Deleting a known singly linked node usually also needs access to its predecessor.

6.7. Sentinel Nodes

A sentinel is a non-data boundary node. It reduces special cases for empty/head/tail operations by ensuring links always have a structural endpoint.

Unit 7: Tree Data Model

7.1. Trees

A tree is a connected acyclic graph. Rooted trees define parent/child relations, depth and subtrees.

The degree of a node is its number of children in the rooted-tree sense used here; terminology can vary in general graph theory.

7.2. Memory Representations

Trees can be stored as node objects with child links, arrays for implicit complete trees, or first-child/next-sibling representation for arbitrary numbers of children.

First-child/next-sibling turns an n-ary tree into a binary-link representation:

node -> first child
node -> next sibling

7.3. Balanced Trees

A balanced search tree keeps height proportional to log n, preventing a sorted/adversarial insertion sequence from degrading ordinary binary search-tree operations to O(n).

7.4. AVL Tree

AVL trees maintain a strict balance-factor condition at each node. Rotations restore balance after insertions/deletions. Search, insertion and deletion are O(log n).

7.5. Heap

A binary heap is a complete binary tree usually stored in an array. For zero-based indexing:

left(i)  = 2i + 1
right(i) = 2i + 2
parent(i)= floor((i-1)/2)

A min-heap guarantees each parent is no greater than its children; it does not globally sort siblings/subtrees.

Peek is O(1), insert and remove-root are O(log n). Building a heap bottom-up is O(n).

7.6. Trie

A trie stores keys by prefixes. Lookup depends on key length rather than directly on number of stored keys:

O(L)

for key length L, subject to child-representation cost. It can consume substantial memory when branching is sparse.

7.7. Huffman Coding

Huffman coding builds a prefix code by repeatedly combining the two least-frequent symbols/subtrees. With an appropriate priority queue the construction is typically O(k log k) for k symbols.

The result is optimal among prefix codes for the supplied symbol-frequency model in expected code length. It is not a universal compression method by itself; model/header overhead and data distribution matter.

Huffman coding assigns unequal codeword lengths, usually giving frequent symbols shorter representations. The prefix property means that no complete codeword is the beginning of another, allowing unambiguous decoding without a separator. Expected code length is the sum of each leaf depth weighted by that symbol's probability. This figure alone is insufficient for short messages, because transmitting a code tree may cost more than the saved bits. When the symbol distribution shifts, the efficiency of a fixed code tree should be measured again.

7.8. Shannon-Fano

Shannon-Fano recursively partitions symbols into groups with approximately balanced total probability. It is historically important but does not guarantee the same optimal prefix-code result as Huffman's algorithm.

Unit 8: Binary Trees

8.1. Binary Tree

A binary tree has at most two children per node. A full binary tree commonly means every internal node has exactly two children. A complete binary tree fills all levels except possibly the last, which is filled from left to right. Terminology should be stated because some sources use "full"/"perfect" differently.

8.2. Traversals

Depth-first traversals are:

preorder:  node, left, right
inorder:   left, node, right
postorder: left, right, node

Breadth-first level-order traversal uses a queue.

For a binary search tree, inorder traversal returns keys in sorted order when the ordering invariant holds.

8.3. Expression Notations

Expression trees connect traversals to notation:

• inorder -> infix with appropriate parentheses,
• preorder -> prefix,
• postorder -> postfix.

8.4. Binary Search Tree

BST invariant:

keys(left subtree) < key(node) < keys(right subtree)

subject to the chosen duplicate-key policy.

Search, insertion and deletion cost O(h) where h is tree height. A balanced tree has h = O(log n); an unbalanced chain has h = O(n).

Deletion has three structural cases: leaf, one child, two children. For two children, replace using a predecessor/successor strategy and remove that node from its original location.

Unit 9: Stack and Queue

9.1. Stack

A stack is LIFO:

push
pop
top/peek

All are O(1) with ordinary array or linked implementations. Uses include call stacks, parsing, expression evaluation, undo and DFS.

An array stack maintains a top index and must handle capacity. A linked stack avoids contiguous resizing but allocates nodes.

9.2. Queue

A queue is FIFO:

enqueue -> rear
 dequeue <- front

A naive array queue that shifts elements on every dequeue makes dequeue O(n). A circular buffer uses head/tail indices and achieves O(1) enqueue/dequeue without shifting.

A linked queue maintains front and rear pointers for constant-time operations.

9.3. Deque

A double-ended queue permits insertion/removal at both front and rear. It supports algorithms such as sliding-window extrema and can implement both stack- and queue-like behavior.

9.4. Priority Queue

A priority queue removes the element with highest/lowest priority rather than oldest insertion time. A binary heap is a common implementation with O(log n) insertion/removal and O(1) access to the best element.

9.5. Comparing Sorting Algorithms by Contract

Sorting algorithms should be compared by more than asymptotic time.

• Worst-case time: Can an adversarial input force quadratic work?
• Extra space: Is the algorithm in-place?
• Stability: Do equal keys preserve their original order?
• Locality: Does the access pattern use cache efficiently?
• External suitability: Can the data exceed memory?

Merge sort provides predictable O(n log n) time and stability but normally needs additional storage. Heap sort gives O(n log n) worst-case time with small auxiliary space but poorer locality. Quicksort is often fast in memory, yet pivot strategy matters for worst-case behavior.

The implementation contract should follow the workload rather than a universal ranking.

9.6. Tree Traversals and Ordered Search

Binary-search-tree search is O(h), where h is tree height. It is logarithmic only when the tree remains sufficiently balanced. AVL and red-black trees control height; heaps optimize priority access rather than arbitrary ordered lookup.

Preorder, inorder, and postorder traversals answer different structural questions. Inorder traversal of a binary search tree produces sorted keys, while postorder is natural for deleting or aggregating a tree bottom-up.

9.7. Capacity, Ordering, and Progress Guarantees in Bounded Queues

FIFO behavior does not imply that a queueing system should admit an unbounded number of requests. A bounded ring queue of capacity C limits memory usage; when full, it must block, reject, discard according to policy, or apply backpressure. The choice is tied to loss semantics and application deadlines.

Concurrent SPSC, MPSC, and MPMC structures do not inherit the memory-visibility guarantees of a sequential array-based FIFO implementation. Linearizability requires concurrent operations to admit a consistent logical order and is distinct from lock-free progress. Amortized O(1) enqueue/dequeue complexity alone does not bound p99 latency or CPU efficiency under contention.

Unit 10: Sorting Algorithms

10.1. Sorting Properties

Sorting arranges records according to a key. Important properties include:

• stable: equal keys preserve relative order,
• in-place: uses only small auxiliary storage under a stated model,
• internal vs external sorting depending on whether data fit in memory.

10.2. Insertion Sort

Insertion sort maintains a sorted prefix and inserts the next element into it.

• best case O(n) for already sorted data with the usual implementation,
• average/worst O(n^2),
• stable and in-place.

It performs well for small or nearly sorted ranges and is often used inside hybrid sorts.

10.3. Selection Sort

Selection sort repeatedly selects the minimum remaining element.

• comparisons Theta(n^2) in all ordinary cases,
• few swaps,
• simple but generally not stable in its basic form.

10.4. Bubble Sort

Bubble sort repeatedly swaps adjacent inverted pairs. Basic complexity is O(n^2); an early-exit flag gives O(n) best case for an already sorted input. It is mostly pedagogical compared with stronger general-purpose algorithms.

10.5. Merge Sort

Merge sort divides, sorts halves and merges:

T(n) = 2T(n/2) + Theta(n)
     = Theta(n log n)

It is stable with the ordinary merge and works well for linked/external data, but array implementations usually require O(n) auxiliary storage.

10.6. Heap Sort

Heap sort builds a heap and repeatedly moves the extreme element into final position.

• build heap O(n),
• total O(n log n),
• in-place in an array,
• not stable in its usual form.

10.7. Quicksort

Quicksort partitions around a pivot and recursively sorts partitions.

• average/expected O(n log n) with appropriate pivot behavior,
• worst case O(n^2),
• excellent locality and low constants in many array workloads.

Randomized or median-like pivot strategies reduce the likelihood of repeatedly pathological partitions. Recursion depth should be controlled for robustness.

10.8. Comparison

No sorting algorithm is universally best. Data size, stability, memory, presortedness, key cost, cache behavior and external-storage constraints determine the choice.

Comparison sorting has a lower bound of Omega(n log n) in the general comparison model. Counting/radix approaches can beat it by exploiting stronger assumptions about keys.

Making stability an explicit sorting requirement. Suppose records are (id, score) tuples [(A,3), (B,1), (C,3)]. Sorting by ascending score must move B first. If business rules also require preserving the order of equal-score records, the output must specifically be [(B,1), (A,3), (C,3)]. This property is sort stability. Without a stable algorithm or an explicit secondary key recording original position, the visible order of equal keys may change. Verification must check more than monotonic scores: for every pair of equal-score records, it must also preserve their original relative order. Memory, runtime, and comparator semantics should be considered together when choosing the implementation.

Unit 11: Searching and Hash Tables

11.1. Linear Search

Linear search scans elements until a match is found. Worst-case time is O(n) and it works without sorted input.

11.2. Binary Search

Binary search requires ordered random-access data and repeatedly halves the search range:

O(log n)

Boundary arithmetic should avoid overflow, e.g.:

mid = low + (high - low) / 2

The insertion-position and duplicate-key policy must be defined separately from mere existence testing.

11.3. Search in BST

BST search follows left/right ordering and costs O(h), which is logarithmic only when height is controlled.

11.4. Hash Functions and Tables

A hash function maps a key to an integer/bucket space. A good non-cryptographic table hash should be fast and distribute expected keys well; it need not provide cryptographic security.

A hash table uses this mapping for average O(1) lookup/insertion under assumptions about load and distribution. Worst-case behavior can be O(n).

11.5. Collisions

Different keys can map to the same bucket. Collision handling is therefore required.

Separate chaining stores multiple entries per bucket, commonly in lists or small structures.

Open addressing stores entries in the table itself and probes alternative slots.

11.6. Linear, Quadratic and double-hash Probing

Linear probing has excellent locality but primary clustering. Quadratic probing changes probe spacing to reduce clustering. Double hashing derives a probe step from another hash function and can spread probes more broadly.

Probe sequences must be compatible with table size so an available slot can be reached.

11.7. Load Factor and Rehashing

Load factor:

alpha = number_of_entries / number_of_buckets

Strongly affects expected probe/chain cost. A table resizes and rehashes when its policy threshold is reached. Resize is expensive but amortized over many insertions.

11.8. Collision Costs and Adversarial Inputs in Hash Tables

The expected access cost of a hash table presumes that keys are distributed sufficiently evenly. Under separate chaining, the load factor \(\alpha=n/m\) denotes entries per bucket; expected search cost can remain close to constant for suitable distributions, whereas a single bucket containing all keys produces \(\Theta(n)\) work. Under open addressing, increasing occupancy reduces the probability of finding a free slot; deleted-slot markers can also lengthen probe sequences. Complexity therefore depends on key distribution, collision resolution, growth policy, and deletion semantics rather than on the hash-function name alone.

A reproducible collision experiment fixes \(n\) and compares random, ordered, and deliberately colliding key sets. Report comparisons per lookup, maximum chain length, 99th-percentile latency, and resize counts independently. An average can conceal a small group of exceptionally expensive lookups. When untrusted parties control keys, engineered collisions may constitute a denial-of-service mechanism. Keyed or randomized hashing and tree-backed buckets are possible mitigations, but their guarantees must be checked against the actual language-runtime contract; no generic technique should be presented as guaranteeing constant worst-case cost.

Growth policy introduces a second distinction. Doubling capacity may require \(\Theta(n)\) relocations in one insertion, yet the total number of relocated elements across a sequence of insertions is bounded by a geometric series. The amortized insertion bound and the latency of the individual resizing operation are different claims. Hard real-time workloads must evaluate the latter explicitly even when average insertion throughput is satisfactory.

Unit 12: Graphs

12.1. Graph Model

A graph is:

G = (V, E)

with vertices V and edges E.

Graphs may be undirected, directed, weighted or unweighted. Degree counts incident edges in undirected graphs; directed graphs distinguish in-degree and out-degree.

A path is a sequence of adjacent vertices/edges. A cycle returns to its starting vertex under the graph's direction rules.

12.2. Representations

Adjacency matrix uses O(V^2) memory and gives constant-time edge-existence checks.

Adjacency list uses roughly O(V + E) memory and is efficient for sparse graphs and neighbor traversal.

Edge list stores edge tuples and is convenient for algorithms such as Kruskal.

An incidence matrix represents vertex-edge incidence and is distinct from an adjacency matrix.

12.3. DFS

Depth-first search explores as far as possible before backtracking. With adjacency lists:

O(V + E)

It can be implemented recursively or with an explicit stack. Uses include cycle analysis, connected components and topological-order construction.

12.4. BFS

Breadth-first search explores vertices by increasing unweighted distance from a source using a queue. With adjacency lists it is also O(V + E) and finds shortest path lengths in unweighted graphs.

12.5. Greedy Approach

A greedy algorithm makes locally optimal choices without revisiting them. Greedy correctness depends on problem structure; the strategy is not valid merely because each step looks best locally.

12.6. Dijkstra

Dijkstra's algorithm computes shortest paths from one source when edge weights are non-negative. With a binary heap and adjacency lists, a common complexity is:

O((V + E) log V)

often simplified to O(E log V) for connected sparse graphs. Negative edge weights invalidate Dijkstra's correctness assumptions.

Algorithmic correctness cannot be inferred merely from the length of the path returned. Dijkstra's permanent-label argument depends on nonnegative edge weights. Consider A→B with cost 2, A→C with cost 5, and C→B with cost −6. The least-cost path from A to B has cost −1; finalizing B at cost 2 would be incorrect. When negative edge weights are permitted, a different relaxation scheme, such as Bellman–Ford, is required. Validating the weight contract of the source data is part of choosing a shortest-path algorithm.

12.7. Minimum Spanning Tree

For a connected undirected weighted graph, an MST connects all vertices with minimum total edge weight and no cycles.

Kruskal sorts edges by weight and adds an edge when it joins different components. Disjoint Set Union efficiently tracks components.

With sorting:

O(E log E)

is typical.

Prim grows one tree by repeatedly adding the cheapest edge crossing from the built set to an outside vertex. With a heap it has complexity similar to Dijkstra's form on sparse adjacency lists.

12.8. Disjoint Set Union

DSU supports:

find(x)
union(a, b)

With path compression and union by rank/size, amortized operation cost is nearly constant, formally involving the inverse Ackermann function.

12.9. Graph Coloring

Graph coloring assigns colors so adjacent vertices differ. General minimum vertex coloring is computationally hard; greedy coloring is fast but does not guarantee the minimum number of colors.

12.10. Topological Sorting

A topological order exists only for a directed acyclic graph. Kahn's algorithm repeatedly removes zero-in-degree vertices; DFS can also construct a reverse finishing order. Detecting that not all vertices can be processed reveals a cycle.

12.11. Greedy Correctness and dynamic-programming State

A greedy algorithm commits to a locally preferred choice and never revisits it. It is correct only when the problem has the required exchange or cut property; a plausible heuristic is not automatically a greedy proof.

Dynamic programming instead identifies overlapping subproblems and a state that contains enough information for future decisions. A useful derivation sequence is:

define state
-> write recurrence
-> define base cases
-> choose evaluation order
-> reconstruct solution if needed

The number of states multiplied by transition work gives the main complexity estimate.

12.12. Graph Search and shortest-path Assumptions

BFS gives shortest paths in unweighted graphs because it explores vertices by increasing edge count. Dijkstra's algorithm requires nonnegative edge weights. Bellman-Ford tolerates negative edges and can detect reachable negative cycles.

Minimum-spanning-tree algorithms solve a different problem. Prim and Kruskal minimize total tree weight; they do not compute shortest paths from a source.

Keeping these contracts explicit prevents algorithms with similar graph inputs from being treated as interchangeable.

12.13. Centrality on Sparse sentence-similarity Graphs

A graph in which sentences are vertices and sufficiently similar sentence pairs are connected can help select representative passages from a long document. Comparing every pair produces a dense graph; doubling the sentence count increases pairwise work by roughly a factor of four. Instead, a bounded neighborhood can be found for each sentence using a lexicon or inverted index, and similarity is computed only for these candidates.

Iterative centrality scores can be calculated from edge weights. At each iteration a vertex receives contributions from its neighbors' previous scores; a damping factor prevents short, high-degree cycles from absorbing all mass. Explicit convergence tolerance and iteration limits keep runtime bounded. If connected components vary greatly in size, global centrality alone may overlook a small but significant document section.

Centrality should not be the only criterion for summary selection. Query relevance, section location, and redundancy with already selected sentences contribute separate signals. Graph computation does not verify the meaning of a statement; it ranks vertices that may be worth presenting.

Unit 13: Algorithm-Design Paradigms and Complexity Boundaries

Choosing a data structure and choosing an algorithmic design paradigm are separate decisions. The same representation can be processed using different strategies depending on subproblem structure, optimal substructure, and input characteristics.

13.1. Divide and Conquer

A divide-and-conquer algorithm separates a problem into smaller independent subproblems, solves them, and combines their results.

problem
  ↓ divide
subproblems
  ↓ solve
partial results
  ↓ combine
result

Merge sort is the classical example. The cost of many such algorithms can be expressed by a recurrence:

T(n) = a T(n/b) + f(n)

The recurrence is useful not only for obtaining a Big-O bound but also for seeing where work is multiplied across levels.

13.2. Dynamic Programming

When the same subproblems are solved repeatedly, their results can be stored. Dynamic programming typically relies on overlapping subproblems and optimal substructure.

Top-down memoization and bottom-up tabulation can evaluate the same recurrence in different orders. Recursion alone does not make a problem suitable for dynamic programming; the dependency structure between subproblems must be established explicitly.

13.3. Greedy Algorithms

A greedy algorithm chooses the locally preferred option at each step. That choice must be proven to lead to a globally correct solution. "Take the largest available value" is not itself a correctness argument.

Exchange arguments, cut properties, and problem-specific invariants are common ways to establish greedy correctness.

13.4. Amortized Analysis

A single operation can occasionally be expensive while a long sequence of operations remains cheap overall. Geometric growth of a dynamic array is a standard example:

1, 2, 4, 8, 16, ...

Some appends may cost O(n) because storage must be reallocated, yet the total work of n appends remains O(n), giving O(1) amortized cost per append.

This is not the same as probabilistic average-case analysis. Amortized analysis bounds total cost over an operation sequence.

13.5. Randomized Algorithms

Randomized algorithms make random choice part of the algorithm. Randomizing pivot selection in quicksort can improve expected behavior against structured or adversarial input.

A Monte Carlo algorithm returns within a bounded execution model but may have a small error probability. A Las Vegas algorithm preserves correctness while allowing running time to vary randomly. The distinction matters in systems with explicit reliability contracts.

13.6. NP-hardness and Approximation

Being able to solve small instances exactly does not imply the existence of an efficient general algorithm for large instances. A practical strategy for NP-hard problems may combine:

exact solution for small n
   +
special-case algorithms
   +
approximation / heuristics
   +
measurable quality bounds

A heuristic may be fast without guaranteeing optimality. An approximation algorithm can instead provide a mathematical bound on solution quality. Metaheuristics such as genetic algorithms should be interpreted within this boundary rather than as replacements for complexity analysis.

Algorithm engineering therefore asks more than "what is the asymptotic complexity?" Correctness guarantees, input scale, memory locality, worst-case behavior, reproducibility, and acceptable approximation error belong to the same design decision.

13.7. Using Data Structures Together

Real systems rarely use one isolated structure. A graph algorithm may use adjacency lists, a hash map for identifiers, a heap for priorities, a queue for work and a DSU for connectivity. The design question is therefore not "which data structure is fastest" but which combination supports the required operations under the actual data scale and latency/memory constraints.

The core relationship is:

problem operations
      ↓
data model
      ↓
data structure
      ↓
algorithm
      ↓
time + memory + locality cost

Complexity analysis defines scalability. Concrete memory layout and implementation determine whether that theoretical advantage survives on real hardware.

13.8. Applied Examples from Early Optimization Projects

My Subset Sum Optimization project is an early experiment in exponential search versus dynamic programming, while the Dudley's Hat algorithm records a separate attempt to reduce search work by reusing state rather than only adding parallel execution.

13.9. Connecting Algorithm Choice to Data and System Constraints

Asymptotic complexity is important but is not the only selection criterion. Input size and distribution, memory-access patterns, auxiliary space, stability, online/offline processing, and whether data exceed memory can change the practical choice.

13.9.1. Comparing Sorting Algorithms

• Insertion sort can perform well on small or nearly sorted arrays with low constant overhead, but is O(n²) in the general/worst case.
• Selection sort also performs O(n²) comparisons and can be useful when minimizing swaps matters.
• Merge sort provides O(n log n) worst-case time and can be stable, typically using auxiliary memory for array implementations.
• Quicksort has excellent average O(n log n) behavior and locality in many implementations, while poor pivot behavior can produce O(n²) worst cases.
• Heapsort provides O(n log n) worst-case time with constant auxiliary array space, but locality and constants influence real performance.

There is no data-independent answer to “the fastest sorting algorithm.” Standard-library implementations often combine techniques.

13.9.2. Stability and in-place Behavior

A stable sort preserves the relative order of records with equal keys. This can matter when multiple ordering keys are applied successively. In-place behavior describes auxiliary-space requirements and is a separate property from stability.

13.9.3. Search Depends on Representation

Binary search provides O(log n) comparisons but requires ordered data and efficient indexed/random access. A hash table targets average constant-time lookup but introduces hash distribution, load-factor, collision, and resize behavior. Balanced search trees provide logarithmic bounds while preserving ordered traversal and range queries.

The search algorithm therefore cannot be selected independently of the data structure.

13.9.4. Graph Algorithms

BFS uses a queue and can find paths with the minimum number of edges in an unweighted graph. DFS explores depth-first through a stack/recursion and forms a basis for cycle, component, and topological algorithms. Dijkstra's algorithm solves single-source shortest paths for non-negative edge weights; negative weights violate its assumptions.

Algorithm preconditions must be checked rather than inferred from the algorithm's name.

13.9.5. Greedy and Dynamic Programming

A greedy algorithm makes a locally preferred choice at each step, but correctness requires a problem property that turns those local choices into a global optimum. Dynamic programming exploits overlapping subproblems and optimal substructure by retaining state results. Memoization is commonly top-down; tabulation is commonly bottom-up.

Not every recursive solution is dynamic programming, and a dynamic-programming implementation does not have to use recursion.

13.9.6. External Sorting

When data do not fit in RAM, storage I/O can dominate CPU complexity. External merge sort sorts memory-sized runs and merges them later. It demonstrates why real algorithm analysis must include the memory hierarchy and I/O model.

13.9.7. Euclidean Algorithm and GCD

The greatest common divisor (GCD) of two integers can be computed efficiently by the Euclidean algorithm through repeated remainders. Its core relation is gcd(a,b) = gcd(b, a mod b), terminating when the second value becomes zero. It is a classic example of reducing a problem to a smaller equivalent subproblem.

13.9.8. Measurement Principle

Asymptotic analysis describes scaling behavior; a benchmark measures one implementation, input distribution, runtime, and machine. Neither replaces the other. Sound engineering uses the complexity bound and measured bottleneck together.

13.10. Cache Locality and Adversarial Input

Asymptotic complexity is fundamental, but two structures with the same Big-O class can behave very differently on real hardware. Contiguous arrays often benefit from cache locality while pointer-heavy structures incur extra indirection.

Expected O(1) hash-table access depends on hash quality and load factor. If an attacker can force many collisions, average-case analysis is not enough.

Algorithm selection should therefore combine asymptotic bounds, expected input distribution, and hardware behavior. Benchmarks are meaningful only when data and execution conditions are representative.

13.11. Relating Complexity Claims to Experiments

Big-O is an asymptotic bound, not a direct prediction of elapsed time on one machine. Two structures in the same complexity class can behave differently because of cache locality, constants, and input distribution.

A benchmark should separate data generation from timing, state warm-up and repetition policy, and report at least a central tendency plus spread. Random, sorted, reverse-sorted, and duplicate-heavy inputs can stress the same algorithm differently.

Correctness also depends on invariants and boundary cases. Empty inputs, single elements, duplicate keys, extreme values, and adversarial cases provide evidence that normal examples cannot.

13.12. Data Structures, Search, and Artificial Intelligence

Many AI methods operate over a large state or candidate space and try to reach a useful result with bounded cost. The connection to data structures and algorithm analysis is therefore deeper than the observation that AI software also uses algorithms. Representation, candidate ordering, and intermediate-state storage directly determine whether a method is computationally practical.

State-space search is the clearest example. If a problem is modeled as a graph, nodes represent states and edges represent valid transitions. BFS finds paths with the fewest edges, Dijkstra finds minimum-cost paths for nonnegative edge weights, and A* combines known cost with a heuristic estimate:

f(n) = g(n) + h(n)

A priority queue is not incidental here; efficient extraction of the smallest f(n) candidate is part of the practical complexity of A*.

Game trees and planning reveal the tree-versus-graph distinction. The same state may be reached through several action sequences. Treating each occurrence as a new tree node repeats work, while a hash table or transposition table can detect previously evaluated states. Hash distribution, memory use, and collision behavior then become search-capacity concerns.

Nearest-neighbor methods create another link. k-NN is conceptually simple, but a full scan per query becomes expensive on large datasets. Depending on dimensionality and distance geometry, k-d trees, ball trees, or approximate nearest-neighbor indexes can reduce the candidate set. In high dimensions, classical spatial trees may lose effectiveness, so representation and index structure must be evaluated together.

Queues, heaps, and bounded candidate structures also appear in production inference and decoding: request scheduling, dynamic batching, beam search, and event pipelines all depend on them. The structure implements an algorithmic policy; it does not by itself define that policy.

Graphs can also be the learning data itself. Social networks, molecular structures, communication graphs, and knowledge graphs are naturally represented with nodes and edges. Graph neural networks learn over such structures, but adjacency lists, sparse matrices, and edge lists still determine memory footprint and execution pattern.

Complexity analysis provides the boundary. An O(n²) step may be acceptable for thousands of items and dominant for millions. Big-O alone is still insufficient: cache locality, allocation, branch behavior, parallelism, and the actual data distribution influence runtime.

Three layers should remain distinct:

problem representation → data structure
search / learning rule → algorithm
physical execution      → system and hardware

AI operates across all three. Data structures and algorithms do not define intelligence; they make search, planning, neighborhood queries, and large candidate spaces computationally manageable.

13.13. Before Choosing an Algorithm

Choosing the right representation is often more important than recalling the name of an algorithm. Start by identifying the dominant operations: search, insertion, deletion, minimum/maximum retrieval, ordered traversal, or neighbourhood queries. The same data can behave very differently when represented as an array, linked list, stack, queue, hash table, tree, or graph.

Asymptotic notation describes growth, not the exact running time for every input size. An O(n log n) method can lose to an O(n^2) method on small inputs because of constants, allocation, or memory-access patterns; the growth term becomes decisive as n increases. A sound analysis therefore counts how often the important operations execute before discarding lower-order terms.

Graph questions require the same discipline. BFS naturally gives shortest paths by edge count in an unweighted graph. Dijkstra is appropriate when edge weights are non-negative; negative weights invalidate its central assumption. A greedy method may make locally attractive choices without producing a global optimum unless the problem has the required greedy-choice structure. Dynamic programming is appropriate when overlapping subproblems and optimal substructure can be exploited.

A compact correctness check is to state an invariant. In binary search, if the target exists it must remain inside the current interval after each step. In Dijkstra's algorithm, a settled vertex must not later receive a shorter distance under the stated assumptions. In a stack-based parenthesis check, the stack represents unmatched opening symbols for the processed prefix. Complexity explains cost; an invariant explains correctness.

Unit 14: Verifying an Algorithm Before Running It: Tracing, Invariants, and Shell Sort

Interview and exam questions often present a short program and ask for its output. A reliable method is to trace state explicitly instead of guessing.

14.1. Dry-run Tables

Track the variables that actually change:

step | i | j | value | result

For Euclid's algorithm:

a = 48, b = 18
48 mod 18 = 12
18 mod 12 = 6
12 mod 6  = 0
=> gcd = 6

The trace exposes initialization, progress, and termination.

14.2. Loop Invariants

A loop invariant is a property that remains true at a defined point of every iteration.

A correctness argument asks:

1. Is it true before the first iteration?
2. Does one iteration preserve it?
3. When the loop terminates, does it imply the required result?

For insertion sort, a useful invariant is:

The range 0..i-1 is sorted at the start of each outer iteration.

This is useful for debugging as well as formal reasoning.

14.3. Input Classes and Boundaries

Algorithms should be tested against more than a typical input:

empty
one element
two elements
already sorted
reverse sorted
all equal
duplicates
minimum / maximum representable values

Different classes expose different defects.

14.4. Problem Families

Large exam collections become easier to reason about when grouped into reusable families:

number theory:
  primes, gcd/lcm, digits, Fibonacci

array scans:
  min/max, sum, frequency, duplicates

text:
  palindrome, character counting, tokenization

matrix:
  rows/columns, diagonal, transpose

search:
  linear, binary

sorting:
  bubble, selection, insertion, shell, merge, quick

A new exercise is often a variation of one of these patterns.

14.5. Shell Sort

Shell sort generalizes insertion sort by moving elements across larger gaps before the final adjacent insertion pass.

choose a large gap
insertion-sort the gap-separated subsequences
reduce the gap
finish with gap = 1

Performance depends strongly on the gap sequence, so there is no single universal complexity figure that describes every Shell-sort variant.

This is a useful lesson: algorithmic complexity can depend on configuration as well as source structure.

14.6. Linear versus Binary Search

Linear search requires no ordering and costs O(n).

Binary search costs O(log n) but requires data ordered by the search key.

Sorting solely to perform one search can cost more than a direct linear scan. Preconditions and preparation cost belong in the algorithm choice.

14.7. Flowchart versus Executable Correctness

A flowchart can express algorithmic intent but does not automatically settle integer overflow, array bounds, language-specific division/modulo semantics, Unicode behavior, aliasing, nullability, or floating-point rounding.

Correctness crosses several layers:

algorithmic model
-> pseudocode
-> programming language
-> test / measurement

14.8. Problem-solving Sequence

1. State input and expected output.
2. Identify the invariant or preserved condition.
3. Trace a small example.
4. Exercise boundary cases.
5. Analyze time and space.
6. Reconsider the data structure if needed.

This creates transferable algorithmic reasoning instead of memorizing isolated answers.

Unit 15: Selection, Order Statistics, and Linear-Time Sorting

Sorting is a powerful general solution when the full order is required. Many problems, however, ask only for a particular order statistic: the minimum, maximum, median, or the ith smallest element. Sorting the entire input can therefore perform work that the result does not require.

15.1. The order-statistic Problem

For n elements:

1st order statistic        -> minimum
nth order statistic        -> maximum
middle order statistic     -> median region
ith order statistic        -> ith smallest element

Minimum or maximum can be found in one pass in O(n) time. If both are needed, pairwise processing can reduce the number of comparisons relative to running two independent scans.

The broader design principle is:

If the required output is not the complete sorted sequence, first ask whether a full sort is necessary.

15.2. Quickselect

Quickselect reuses the partition idea from Quicksort but recursively continues only in the side that can contain the target rank.

partition(A, p)
        ↓
pivot rank r

i = r  -> pivot is the answer
i < r  -> continue only left
i > r  -> continue only right

With good pivots, the problem shrinks rapidly and randomized Quickselect runs in expected O(n) time.

Repeatedly poor pivots can instead produce subproblems of sizes:

n
n-1
n-2
...

and yield O(n^2) worst-case behavior.

The statement "Quickselect is linear" is therefore incomplete unless the pivot policy and analysis type are stated.

15.3. Randomized Selection

Randomized selection chooses the pivot randomly so that a fixed adversarial input order does not systematically trigger a deterministic bad-pivot policy.

The expectation is taken over:

fixed input
random algorithmic choices

rather than assuming a random input distribution.

15.4. Median of Medians and Deterministic worst-case Linear Selection

Selection can guarantee worst-case O(n) time.

The core idea is:

split elements into small groups
↓
find each group median
↓
find the median of those medians
↓
use it as pivot
↓
partition
↓
continue only on the target side

The pivot does not need to be the exact median. It only needs to guarantee that a constant fraction of elements is discarded from both extremes.

This leads to a recurrence that can be bounded in the form:

T(n)
<=
T(n/5)
+
T(7n/10 + constant)
+
O(n)

and therefore to worst-case linear time.

In practice, constants can be higher than randomized Quickselect. A theoretical worst-case guarantee and the best real workload choice are different engineering questions.

15.5. Lower Bound for Comparison Sorting

A comparison sort that learns order only from questions such as:

a < b ?

can be modeled as a binary decision tree.

There are n! possible permutations of n distinct elements, and different final orders must reach distinguishable leaves.

The decision-tree height is therefore at least:

log2(n!)

which grows as Omega(n log n).

Thus:

Within the general comparison-sorting model, worst-case comparison count cannot be reduced to o(n log n).

Merge sort and Heap sort match this asymptotic lower bound. Quicksort has expected O(n log n) cost but can have O(n^2) worst-case cost.

The lower bound does not apply to every sorting problem. Algorithms that use additional structure of the keys can do better.

15.6. Counting Sort

Counting sort assumes keys come from a bounded integer domain such as:

key ∈ {0, 1, ..., k}

It counts occurrences and reconstructs order in:

O(n + k)

time.

Its strength is also its limitation. If k is enormous relative to n, memory and time can become unattractive.

Counting sort does not violate the comparison lower bound because it uses key values directly rather than only pairwise comparisons.

15.7. Stability

A stable sort preserves the relative input order of records with equal keys.

This matters when sorting by multiple fields or when one stable pass must preserve information established by an earlier pass.

In radix sorting, for example, stability of the inner digit sort is often essential so that lower-order digit information survives later passes.

15.8. Radix Sort

Radix sort decomposes a key into digits.

In least-significant-digit order:

least significant digit
↓
...
↓
most significant digit

a stable sort is applied at each stage.

With d digits and a digit range 0..k, a common cost model is:

O(d * (n + k))

provided that the digit representation and inner stable sort satisfy the required assumptions.

15.9. Bucket Sort

Bucket sort distributes elements into value ranges and sorts or processes each bucket independently.

Under a suitable near-uniform distribution, expected cost can approach linear time.

A highly skewed distribution can instead send many elements into one bucket and eliminate the advantage.

The input distribution is therefore part of the algorithm's performance contract.

15.10. A Practical Decision Path

only min/max?
-> one scan

only the ith item?
-> selection

small integer key domain?
-> counting/radix candidate

known useful distribution?
-> bucket candidate

general comparable objects?
-> comparison sort

Algorithm choice is a function of required output, key contract, memory budget, and worst-case requirement, not merely a Big-O table.

Unit 16: Augmented Trees and Advanced Search Structures

A data structure does not always need a completely new tree design to support a new query. A balanced structure can often be extended with a small piece of summary metadata that enables efficient additional operations.

16.1. Red-Black Tree Invariants

A Red-Black Tree augments a binary search tree with one color bit per node.

A classical invariant set is:

1. Every node is red or black.
2. The root is black.
3. NIL leaves are black.
4. A red node cannot have a red child.
5. Every path from a node to descendant NIL leaves
   contains the same number of black nodes.

These rules do not create perfect balance, but they bound tree height logarithmically.

Search, insertion, and deletion can therefore remain O(log n) in height.

16.2. The Role of Rotation

Left and right rotations:

• preserve BST key order,
• modify only local links,
• allow local maintenance of height or summary metadata.

After insertion or deletion violates a Red-Black invariant, a combination of recoloring and rotations restores balance.

A rotation is best understood as:

A constant-cost local structural transformation that changes tree geometry without changing sorted key semantics.

16.3. The Augmentation Principle

Metadata is especially useful when it can be recomputed from a node and its children.

For example:

size[x] =
size[left[x]]
+
size[right[x]]
+
1

stores the number of nodes in a subtree.

Only a small number of size values need to change after a rotation.

The balanced BST then becomes an order-statistic tree.

16.4. Order-statistic Trees

Two core operations are:

Select(i):

find the ith smallest key

Rank(x):

find the position of x in sorted order

Because each node knows the size of its left subtree, comparisons with:

leftSize + 1

guide the traversal.

With a balanced tree, both operations can be O(log n).

Applications include dynamic percentiles, leaderboards, rank-based indexing, and dynamic order queries.

16.5. Interval Trees

An interval is represented as:

[low, high]

A BST ordered only by low cannot efficiently prune every overlap query.

If each node stores:

maxHigh =
largest high endpoint in its subtree

then subtrees that cannot overlap a query interval can be skipped.

Interval trees are useful for scheduling, reservations, temporal conflicts, and geometric intersection queries.

16.6. When Augmentation Remains Efficient

A useful augmentation should ideally:

1. be computable from local subtree information,
2. require updates in only a small region after rotation,
3. provide real pruning or decision information for the target query.

Metadata that requires a full O(n) recomputation after every update can destroy the operational benefit of the balanced tree.

16.7. B-trees: from the RAM Model to the I/O Model

A binary search tree is natural when pointer traversal in RAM is the primary cost.

For block storage, the expensive event may be:

one page / block access

rather than one comparison.

A B-tree uses high fanout so one node stores many keys and child pointers.

The result can be:

fewer tree levels
-> fewer block accesses

which is why B-tree families are natural in database and filesystem indexes.

16.8. Split and Merge

When a B-tree node exceeds its capacity it can be split. When occupancy becomes too low, keys can be redistributed from siblings or nodes can be merged.

These operations preserve:

• sorted-key semantics,
• balanced leaf depth,
• occupancy constraints.

The key design contrast is:

AVL / Red-Black:
low fanout, RAM-oriented

B-tree:
high fanout, block-I/O-oriented

16.9. B+ Tree as a storage-oriented Variation

In B+ tree families, record pointers or complete entries are typically kept in leaves while internal nodes guide traversal.

Linked leaves can make ordered range scans efficient.

Actual database implementations add page size, fill factor, concurrency, write-ahead logging, and split policies. The algorithmic lesson is the combination of high fanout and ordered leaf access, not a claim that every storage engine has identical behavior.

16.10. Derive the Structure from the Query Family

Instead of asking only:

how fast is insert?
how fast is search?

ask:

exact key?
range?
rank/select?
interval overlap?
ordered iteration?
block I/O?
update frequency?

Augmentation is a systematic way to shape a data structure around the queries it must support.

Unit 17: State Design in Dynamic Programming and Backtracking

Dynamic programming is not merely "filling a table." The difficult step is choosing a state that captures exactly the information needed by the recurrence.

A disciplined DP design states five elements explicitly:

state
transition / recurrence
base case
evaluation order
solution reconstruction

If these are unclear, code can look plausible while solving the wrong problem.

17.1. 0/1 Knapsack

Each item has:

weight[i]
value[i]

and can be selected at most once.

A state can be:

DP[i][w]
=
best value obtainable from the first i items
under capacity w

The transition compares not selecting the item with selecting it when capacity permits:

DP[i][w] =
max(
  DP[i-1][w],
  value[i] + DP[i-1][w-weight[i]]
)

The familiar cost is O(nW).

However, W is the numeric capacity itself while its encoding length is about log W bits, so this is a pseudo-polynomial algorithm.

That distinction matters in complexity analysis.

17.2. Longest Common Subsequence

For sequences:

X[1..m]
Y[1..n]

define:

L[i][j]
=
LCS length of
X's first i elements and
Y's first j elements

When final elements match:

L[i][j] = 1 + L[i-1][j-1]

otherwise:

L[i][j] = max(
  L[i-1][j],
  L[i][j-1]
)

The core idea is that an optimal solution over two prefixes can be expressed through smaller prefix problems.

If the actual subsequence is required, predecessor choices must be reconstructed rather than returning only the length.

17.3. Edit Distance

Edit distance minimizes the cost of converting one sequence to another through operations such as insert, delete, and replace.

A state can be:

D[i][j]
=
minimum cost to transform
X[1..i] into Y[1..j]

When final symbols differ, candidates include:

delete  -> D[i-1][j] + costDelete
insert  -> D[i][j-1] + costInsert
replace -> D[i-1][j-1] + costReplace

This pattern supports spell correction, sequence alignment, and fuzzy matching.

In real text systems, the unit called a "character" must still be defined: byte, Unicode code point, grapheme, or token.

17.4. Matrix-chain Multiplication

A chain of compatible matrices can be parenthesized in many ways.

The mathematical result is the same, but scalar multiplication cost can differ greatly.

Define:

M[i][j]
=
minimum cost of multiplying
A_i ... A_j

Try each split point k and combine:

i..k
k+1..j

The table is filled from shorter intervals toward longer ones.

This example shows why evaluation order is determined by dependency structure.

17.5. Memoization versus Tabulation

Top-down memoization uses recursive specification plus a cache and can compute only states actually reached.

Bottom-up tabulation evaluates states in dependency order and can provide better control over call overhead and memory layout.

Even with the same asymptotic state count, practical behavior depends on state sparsity, cache locality, recursion depth, and reconstruction requirements.

17.6. State Compression

If a recurrence depends only on the previous row, memory can sometimes be reduced from:

O(nW)

to:

O(W)

However, if the actual selected solution must be reconstructed, a value-only compressed table may not contain enough history.

Memory optimization therefore depends on the output contract.

17.7. Backtracking Is a Separate Design Paradigm

Backtracking explores a search tree while pruning partial assignments that cannot become valid solutions.

partial solution
    ↓
candidate choice
    ↓
feasible?
   / \
 no   yes
 |     |
prune recurse
       |
      undo

N-Queens, subset choices, constraint problems, and graph coloring can use this pattern.

17.8. Backtracking versus Dynamic Programming

Backtracking emphasizes:

search tree
+
constraint pruning

Dynamic programming emphasizes:

overlapping subproblems
+
optimal substructure
+
state reuse

Some problems admit both approaches, but repeated equivalent states are where memoization can transform the search dramatically.

17.9. Branch-and-bound

Branch-and-bound adds an objective bound rather than relying only on feasibility.

For minimization:

current partial cost
+
best possible remaining lower bound
>=
best known solution

allows a branch to be discarded.

Backtracking asks whether a partial assignment can remain feasible.

Branch-and-bound asks whether a feasible continuation can still beat the incumbent objective.

The two can be combined.

17.10. DP Design Checklist

1. What exactly does one state mean?
2. Can multiple paths reach the same state?
3. Does the transition cover every valid decision?
4. What are the base cases?
5. Does evaluation order respect dependencies?
6. Is the state space truly polynomial in input length?
7. Must the solution itself be reconstructed?
8. Does memory compression preserve the required semantics?

These questions turn dynamic programming from pattern memorization into a reusable design method.

17.11. State, Transition, and Reconstruction in Dynamic Programming

A dynamic-programming design becomes clearer when split into four parts:

state          -> what must be remembered from the past?
transition     -> which previous states define a new state?
base case      -> where does computation begin?
reconstruction -> how is the optimal decision sequence recovered?

Memoization caches a top-down recursion. Tabulation evaluates the same recurrence bottom-up in dependency order. They implement the same mathematical relation with different execution and memory models.

The full state table is not always necessary. If one row depends only on the preceding row, rolling arrays can reduce memory, although reconstruction may require additional predecessor information. Time and space complexity should therefore be designed together.

Unit 18: Advanced Graph Algorithms: Shortest Paths, SCCs, Flow, and Matching

In graph problems, a major source of error is choosing an algorithm by label alone: "this finds shortest paths" or "this analyzes connectivity." Edge-sign assumptions, graph direction, source scope, and whether the problem is about paths or flow all matter.

18.1. Relaxation as a Shared Abstraction

Many shortest-path algorithms use the same core operation.

For an edge:

u -> v
weight = w(u,v)

if:

dist[u] + w(u,v) < dist[v]

then:

dist[v] = dist[u] + w(u,v)
parent[v] = u

This relaxation step is not an algorithm by itself. Dijkstra, Bellman-Ford, and DAG shortest-path algorithms apply relaxation in different orders under different assumptions.

18.2. Bellman-Ford

Bellman-Ford:

• allows negative-weight edges,
• can detect a negative-weight cycle reachable from the source.

The core structure is:

repeat V-1 times:
    relax every edge

A simple shortest path without repeated vertices has at most V-1 edges.

If one more full edge scan can still improve a distance, a reachable negative-weight cycle exists.

The standard cost is:

O(VE)

Bellman-Ford is not automatically the best answer to every graph containing negative edges; a DAG or another structural restriction can provide a cheaper algorithm.

18.3. Shortest Paths in a DAG

If the graph is directed and acyclic, topological order provides a strong guarantee.

topological sort
+
one ordered relaxation pass

can solve single-source shortest paths in:

O(V + E)

time.

Negative edge weights are not a problem because there are no cycles.

This illustrates a broader rule:

Use graph structure, not only edge-weight properties, when choosing the algorithm.

18.4. All-pairs Shortest Paths

If every source-destination pair is required, repeatedly applying a single-source algorithm is not always the best formulation.

18.5. Floyd-Warshall

Floyd-Warshall is a dynamic-programming algorithm.

A conceptual state is:

D[k][i][j]
=
shortest i -> j path
when only the first k vertices
may be used as intermediate vertices

The transition chooses between:

do not use k
or
go i -> k -> j

With in-place space optimization, one two-dimensional matrix is sufficient.

The standard time cost is:

O(V^3)

It is especially attractive when the graph is dense and all-pairs distances are genuinely needed.

The Floyd–Warshall distance table can also be used to detect negative cycles. Once all permitted intermediate vertices have been considered, a negative diagonal entry indicates a walk that returns to a vertex at a lower total cost. Pairs of vertices connected through such a cycle have no finite shortest-path lower bound. A negative edge and a negative cycle are different conditions: the former does not by itself invalidate the algorithm, whereas the latter makes the optimum for affected paths undefined. Checking diagonal entries is therefore part of validating an all-pairs shortest-path result.

18.6. Johnson's Algorithm

For sparse graphs, Johnson's algorithm combines:

Bellman-Ford potentials
↓
edge reweighting
↓
nonnegative transformed edges
↓
Dijkstra from every source

The reweighting preserves shortest-path ordering while enabling a nonnegative-edge shortest-path routine.

This can be preferable to Floyd-Warshall when the graph is sparse.

A negative cycle invalidates the required reweighting, so it must be detected first.

18.7. Strongly Connected Components

In a directed graph, vertices belong to the same strongly connected component when each can reach the other.

SCC decomposition is useful in dependency graphs, call graphs, state machines, and module relations.

If each SCC is contracted to one node, the resulting condensation graph is always a DAG.

This decomposes a directed graph into:

local cyclic components
+
an acyclic global structure

18.8. Kosaraju's Approach

Conceptually:

DFS to obtain finishing order
↓
transpose the graph
↓
DFS in reverse finishing order
↓
each DFS tree identifies one SCC

Two DFS traversals plus graph transposition can achieve:

O(V + E)

time.

18.9. Tarjan SCC

Tarjan's method uses one DFS and tracks:

• discovery index,
• low-link value,
• membership in an active stack.

A condition of the form:

lowlink == discoveryIndex

identifies an SCC root.

The method also runs in linear time.

The general lesson is:

DFS is not only traversal; with carefully chosen state it becomes a framework for extracting graph invariants.

18.10. Flow Networks

Shortest path and maximum flow are different problems.

A flow network gives each directed edge a capacity:

0 <= flow(u,v) <= capacity(u,v)

and conserves flow at intermediate vertices:

incoming flow = outgoing flow

The objective is to maximize total flow from source s to sink t.

18.11. Residual Graphs

Sending flow on an edge changes not only remaining forward capacity but also the ability to undo or redirect previous decisions.

Conceptually:

forward residual
=
capacity - current flow

reverse residual
=
current flow

A residual graph therefore represents what modifications to the current flow remain feasible.

18.12. Ford-Fulkerson Method

The conceptual scheme is:

while there is an s -> t path in the residual graph:
    find the path bottleneck
    augment along the path

Ford-Fulkerson is a method rather than one single implementation with one universal complexity bound.

The choice of augmenting path and the capacity domain affect behavior.

Edmonds-Karp selects a shortest augmenting path in edge count using BFS and has a worst-case bound:

O(V E^2)

18.13. Max-flow min-cut

An s-t cut partitions vertices into:

S
T

with s in S and t in T.

The cut capacity is the total capacity of edges directed from S to T.

The max-flow min-cut theorem states:

The value of a maximum s-t flow equals the capacity of a minimum s-t cut.

This provides both an optimum flow and a structural certificate explaining why additional flow is impossible.

18.14. Bipartite Matching

A bipartite graph divides vertices into:

L ∪ R

with edges only between the two sides.

A matching is a set of edges in which no vertex is incident to more than one selected edge.

Maximum bipartite matching can be reduced to a unit-capacity flow network:

source -> L -> R -> sink

With integral unit capacities, an integral maximum flow corresponds to a matching.

This is a useful example of algorithmic reduction.

18.15. Hopcroft-Karp

A general max-flow solver can find a bipartite matching, but a specialized algorithm can do better.

Hopcroft-Karp uses BFS to find layers of shortest augmenting paths and DFS-like exploration to augment along many such paths in one phase.

Its standard complexity is:

O(E * sqrt(V))

It is a core tool for assignment and compatibility-matching problems.

18.16. Choosing a Graph Algorithm

Ask:

single source?
all pairs?
negative edge?
negative cycle possible?
DAG?
path or flow?
bipartite?
sparse or dense?

There is no meaningful "best graph algorithm" before these problem properties are specified.

18.17. Uniform-cost, a*, and Bidirectional Search

On a weighted graph, uniform-cost search expands the open node with the smallest accumulated path cost. With nonnegative edge costs, this idea is closely related to Dijkstra's algorithm.

A* combines known and estimated cost:

f(n) = g(n) + h(n),

where g(n) is the known cost from the start and h(n) estimates the remaining cost to the goal. A heuristic that never overestimates the true remaining cost is admissible; one satisfying a triangle-like consistency condition is consistent.

A more informative heuristic can reduce unnecessary expansion, but heuristic evaluation itself also has a cost. Setting h(n)=0 reduces A* to uniform-cost behavior.

When start and goal are both known, bidirectional search attempts to meet two search frontiers. Its branching-factor advantage must be balanced against reverse-edge access, stopping conditions, and memory management.

Unit 19: String Matching, Rolling Hashes, and Suffix Structures

Given:

text T of length n
pattern P of length m

the string-matching problem asks where P occurs in T.

The best method depends on preprocessing budget, alphabet structure, repetition, number of patterns, and how often the text will be queried.

19.1. Naive Matching

The direct method tests every possible starting position:

compare
T[s ... s+m-1]
with
P[0 ... m-1]

Its worst-case cost can be:

O((n-m+1) * m)

Highly repetitive inputs can cause the same known information to be compared repeatedly.

More advanced algorithms exploit structure discovered during earlier comparisons.

19.2. Rabin-Karp and Rolling Hash

Rabin-Karp compares a pattern hash with the hash of each length-m text window.

The key technique is rolling hashing:

current window hash
-> next window hash

without recomputing the entire hash from scratch.

A matching hash must still be verified against the actual characters because collisions are possible.

Therefore:

equal hash
!=
guaranteed equal text

Rabin-Karp is useful for multi-pattern candidates, rolling fingerprints, and workloads where hash-based filtering is natural.

Hash choice and collision policy remain part of the performance and robustness contract.

19.3. Finite-automaton Matching

A pattern can be represented as a state machine.

A state represents:

how many characters of the pattern prefix
have been matched so far

Each input character performs:

state = delta(state, character)

If the transition function is precomputed, scanning the text can take O(n) time, with preprocessing cost shifted to pattern and alphabet structure.

This connects automata theory directly to practical substring search.

19.4. KMP and Failure Information

Knuth-Morris-Pratt does not restart the pattern from position zero after every mismatch.

If a prefix of the pattern is also a suffix of the already matched region, those characters are already known and do not need to be compared again.

A prefix/failure function stores information of the form:

pi[q]
=
length of the longest proper prefix of P[0..q]
that is also a suffix

Pattern preprocessing takes:

O(m)

and text scanning takes:

O(n)

for total:

O(n + m)

The deeper lesson is that a failed comparison can still preserve useful state.

19.5. Boyer-Moore Intuition

Boyer-Moore often compares from the right side of the pattern and can skip multiple text positions after a mismatch.

Two classical ideas are:

• bad-character rule,
• good-suffix rule.

On many natural-text workloads it inspects far fewer characters than a left-to-right scan.

However, exact worst-case guarantees depend on the variant and preprocessing rules.

It should not be described as universally linear or universally faster than KMP.

19.6. One Pattern versus Repeated Queries

If one pattern is searched once, KMP or Rabin-Karp can be natural choices.

If the same large text will serve many substring queries, it can be better to preprocess the text itself.

This motivates suffix structures.

19.7. Suffix Arrays

Consider every suffix:

T[0..]
T[1..]
T[2..]
...
T[n-1..]

A suffix array stores the starting positions of those suffixes in lexicographic order rather than copying each suffix.

For a text such as:

banana

the array orders starting positions according to suffixes such as "a", "ana", "anana", "banana", and so on.

Suffix arrays support substring search, repeated-substring analysis, lexicographic rank, and text indexing.

19.8. Searching a Suffix Array

A pattern can be searched against lexicographically sorted suffixes using binary search.

A lower-bound and upper-bound search can identify the interval of suffixes that begin with the pattern.

A simple implementation may spend O(m) character comparisons at each binary-search step, so the cost is not just O(log n).

LCP-aware and specialized methods can avoid some repeated comparisons.

19.9. LCP Arrays

An LCP array stores:

Longest Common Prefix

lengths between neighboring suffixes in suffix-array order.

It supports tasks such as repeated-substring analysis and can be combined with range-minimum structures for richer text queries.

Suffix arrays and LCP arrays offer different space and locality trade-offs from tries and suffix trees.

19.10. Multiple Patterns

When many patterns are searched against the same stream of text, preprocessing the entire pattern set into a trie and failure-transition structure leads to multi-pattern automata such as Aho-Corasick.

The broader design principle is:

Decide whether preprocessing belongs to the pattern, the text, or the entire pattern set based on query distribution.

19.11. Unicode and Normalization

Many textbook algorithms assume a sequence of "characters."

Real text may distinguish:

• UTF-8 bytes,
• Unicode code points,
• grapheme clusters,
• normalized forms.

The same visible symbol can have more than one code-point representation.

Substring semantics must therefore specify whether matching is byte-level, code-point-level, or normalization-aware.

An algorithm can be internally correct and still produce the wrong user-visible result when it operates on the wrong representation layer.

19.12. Choosing a string-matching Strategy

small one-off query
-> naive can be enough

one pattern + large text
-> KMP / Rabin-Karp

hash-friendly candidate filtering
-> Rabin-Karp

many queries + fixed text
-> suffix array / text index

many patterns
-> trie / multi-pattern automaton

The decision includes preprocessing cost and query frequency, not only asymptotic scan time.

19.13. Edit Distance and Sequence Alignment Are Not the Same Problem

Levenshtein-style edit distance summarizes the minimum transformation cost between two strings as a scalar. Sequence alignment instead produces an explicit correspondence between symbols and gaps. The methods can share a dynamic-programming grid while optimizing different objectives with different score semantics.

Needleman-Wunsch performs global alignment: both sequences are aligned from beginning to end. A simple state is:

F[i][j] = best global-alignment score for X[1..i] and Y[1..j]

with candidates for a paired symbol and two gap directions:

F[i-1][j-1] + score(X[i], Y[j])
F[i-1][j]   + gap
F[i][j-1]   + gap

Smith-Waterman performs local alignment. Adding 0 as a candidate lets negative partial scores restart, so the best matching region can emerge independently of the rest of either sequence:

H[i][j] = max(0, diagonal, up, left)

The problem statement should therefore drive the choice:

global alignment -> compare the sequences end to end
local alignment  -> find the strongest matching subsequences
edit distance    -> minimize transformation cost
substring search -> locate exact or pattern occurrences

A constant gap penalty treats a long gap as many independent penalties. An affine model separates gap-open from gap-extend, which can represent long gaps more appropriately. In biological sequences a substitution matrix changes the score semantics; in natural-language data, tokenization and normalization choices play an analogous role.

The classical table uses O(nm) time and O(nm) space. If only the score is required, memory can be reduced by retaining only the necessary previous row or column; reconstructing the actual alignment requires additional traceback information or a reconstruction strategy.

19.14. Delete Keys and Candidate Complexity in Spelling Correction

Computing edit distance against every dictionary word for every noisy query is expensive. An alternative is to index keys obtained by deleting a bounded number of characters from each dictionary entry. Similar deletion keys derived from a misspelled query retrieve a much smaller candidate set; exact edit distance is evaluated only on these candidates. Expensive validation thus operates over a restricted set rather than the full vocabulary.

The maximum deletion distance controls the trade-off. Raising it may improve recall, but also increases index size and spurious matches. Short words and common syllabic patterns collide more often. Turkish inflection introduces an additional memory–coverage choice between indexing every surface form and separately modeling stems and affixes.

Candidate retrieval must not be confused with correction correctness. A deletion key only finds plausible words; their sentence roles, negation, and protected identifiers require separate checks. Split and merge candidates can be proposed when word boundaries are missing, but contextual evidence is needed before selecting a form.

Unit 20: Amortized Analysis: Aggregate, Accounting, and Potential Methods

Worst-case analysis asks how expensive one operation can become.

Amortized analysis asks:

Across a long valid sequence of operations, how is the cost of rare expensive operations distributed?

This is not average-case analysis.

Amortized guarantees do not require a probability distribution over inputs. They can hold over every valid operation sequence.

20.1. Dynamic-array Example

Suppose an array doubles its capacity when full.

Most appends perform:

one element write

A resize requires copying all existing elements and then writing the new item.

One append can therefore cost O(n).

With geometric capacities:

1, 2, 4, 8, 16, ...

the total copy work is bounded by:

1 + 2 + 4 + ... < 2n

Thus n appends cost O(n) in total and the amortized append cost is O(1).

20.2. Aggregate Analysis

Aggregate analysis first bounds:

total actual cost T(n)
for n operations

and then assigns:

T(n) / n

as the amortized per-operation cost.

Dynamic arrays and binary counters are natural examples.

20.3. Binary Counter

A binary increment such as:

...01111
->
...10000

can flip many bits.

One increment may cost O(log n) bit flips.

Across many increments, however:

• the least significant bit changes every time,
• the next bit every two increments,
• the next every four,
• and so on.

Over n increments, the total number of flips is O(n), so the amortized increment cost is O(1).

20.4. Accounting Method

The accounting method assigns an amortized charge that can differ from the actual cost.

Cheap operations can be overcharged and the excess viewed as stored credit for future expensive work.

For a growing array:

normal append actual cost: 1

amortized charge:
1 -> current write
1 -> future movement credit
1 -> additional reserve

is one possible interpretation.

A key invariant is:

stored credit never becomes negative

If this holds, total amortized charges upper-bound total actual cost.

20.5. Potential Method

The potential method represents stored future work as a global scalar associated with the data-structure state.

For state D_i, define:

Phi(D_i) >= 0

and:

amortized_i
=
actual_i
+
Phi(D_i)
-
Phi(D_(i-1))

Summing across operations causes intermediate potential terms to telescope:

sum(amortized)
=
sum(actual)
+
Phi(final)
-
Phi(initial)

With a suitable initial state and nonnegative potential, amortized total bounds actual total.

20.6. Choosing a Potential

A useful potential function should:

• represent deferred work,
• increase during cheap operations,
• decrease when expensive work is paid,
• be easy to compute from state.

Potential is not an arbitrary mathematical trick.

A poor choice can produce a uselessly weak bound or fail to represent future work.

20.7. Three Methods, One Underlying Idea

aggregate:
count the total cost directly

accounting:
store credit on operations or objects

potential:
encode stored work in a state function

The most convenient proof method depends on the structure.

20.8. Amortized versus Expected Cost

Randomized quicksort or randomized hashing is analyzed through expectation over random variables.

Amortized cost can be deterministic and sequence-based.

An algorithm may be randomized and amortized, deterministic and amortized, or expected-cost without an amortized guarantee.

They should not all be described as "average" complexity.

20.9. Worst-case Latency Still Matters

An O(1) amortized operation is not necessarily O(1) on every call.

A resize can still create an O(n) pause.

In latency-sensitive systems this can motivate:

• incremental resizing,
• reserved capacity,
• bounded maintenance per operation.

Amortized analysis can justify throughput while still failing a hard tail-latency requirement.

20.10. When to Look for Amortized Analysis

Useful warning signs include:

rare expensive rebuild
geometric growth
lazy cleanup
path compression
self-adjusting structure
deferred maintenance

In these settings, single-operation worst case can misrepresent the long-run cost.

Amortized analysis proves how often expensive work can occur under the data structure's invariants.

Unit 21: P, NP, Reductions, and Approximation Guarantees

An algorithm being slow is not the same claim as a problem being computationally hard.

A poor implementation can make an easy problem slow. Complexity theory studies structural difficulty at the problem level.

21.1. Decision versus Optimization

An optimization problem may ask:

find the minimum-cost tour

Its decision form asks:

does a tour with cost <= K exist?

NP-completeness is normally defined for decision problems.

The optimization version asks for more information, although decision procedures can sometimes be used repeatedly to recover an optimum value.

21.2. Class P

P is the class of decision problems solvable in polynomial time on a deterministic computational model.

Examples include connectivity and many shortest-path or spanning-tree decision formulations.

"Polynomial" does not mean practically fast in every case. A hypothetical n^100 algorithm is polynomial but usually useless.

The classification captures a fundamental scaling distinction.

21.3. Class NP

NP historically means nondeterministic polynomial time, but the verifier interpretation is often more useful.

For every YES instance, there must be a polynomial-size certificate that a deterministic verifier can check in polynomial time.

For a Hamiltonian-cycle decision problem, a certificate can be a proposed vertex order.

The verifier checks that vertices are used correctly and required edges exist.

This does not imply that finding the certificate is easy.

21.4. P versus NP

We know:

P ⊆ NP

because anything solvable quickly can also be verified quickly.

The central unresolved question is:

P = NP ?

It is widely believed that P != NP, but this has not been proved.

The statement:

NP = exponential-time problems

is incorrect.

NP is defined through nondeterministic polynomial time or polynomial verification, not by one known deterministic running time.

21.5. Polynomial-time Reduction

If problem A can be transformed into problem B in polynomial time:

A <=p B

then an efficient solver for B would provide an efficient solver for A after polynomial transformation overhead.

Reduction direction is frequently misunderstood.

If A is known hard and:

A <=p B

then this supports the conclusion that B is at least as hard as A.

The reverse direction does not prove the same fact.

21.6. NP-hard and NP-complete

An NP-hard problem is at least as hard as every problem in NP under the chosen reduction notion.

It does not have to be in NP and does not even have to be a decision problem.

An NP-complete problem is:

NP-hard
+
in NP

A standard proof pattern is:

1. show the new problem is in NP
2. reduce a known NP-complete problem to it

21.7. Reduction Chains

SAT is the historical foundational NP-complete problem.

Small pedagogical chains can look like:

SAT
-> 3-SAT
-> Vertex Cover
-> another combinatorial problem

The important proof invariant is:

source instance
-> polynomial transformation
-> target instance

YES iff YES

The goal is to understand preservation of answer structure, not memorize every gadget.

21.8. What to Do with an NP-hard Problem

"NP-hard" does not mean "give up."

Possible strategies include:

small n
-> exact exponential / branch-and-bound

small structural parameter
-> parameterized/FPT method

restricted special case
-> polynomial special-case algorithm

near-optimal acceptable
-> approximation

empirical quality acceptable
-> heuristic / metaheuristic

repeated workload
-> preprocessing / decomposition

Complexity classification constrains design; it does not choose one implementation automatically.

21.9. Approximation Algorithm versus Heuristic

An approximation algorithm runs in polynomial time and can provide a proven bound on solution quality.

A heuristic may work well empirically but provide no general worst-case quality guarantee.

The distinction is fundamental.

21.10. A 2-Approximation for Vertex Cover

For an undirected graph, a vertex cover includes at least one endpoint of every edge.

A simple algorithm is:

C = empty

while there is an uncovered edge (u,v):
    add u and v to C
    remove edges incident to u or v

The selected edges can be viewed as a matching.

Any optimal vertex cover must include at least one endpoint from every edge in that matching.

The algorithm includes two endpoints per selected edge, so:

|C| <= 2 * |OPT|

This is a formal approximation ratio rather than an empirical observation.

21.11. Metric TSP

General TSP is difficult to approximate strongly.

If distances satisfy the triangle inequality, the problem becomes metric TSP.

A classic construction uses:

minimum spanning tree
-> traverse tree edges twice
-> obtain an Eulerian walk
-> shortcut repeated vertices

Triangle inequality ensures that shortcutting does not increase the cost.

This yields a 2-approximation-style guarantee.

The lesson is:

Approximation guarantees depend on problem assumptions.

21.12. Report Exact, Approximate, and Heuristic Results Differently

A useful benchmark separates:

runtime
objective value
optimality gap
proof / guarantee
random seed
time limit

A heuristic finding the optimum on small tests does not create an approximation guarantee.

Likewise, a worst-case approximation ratio does not mean every instance reaches that worst case.

21.13. Why Complexity Theory Matters to Engineering

When a search problem fails to scale, the explanation may be:

the implementation is poor

or:

the problem family is structurally difficult

These require different remedies.

Complexity theory helps decide whether to optimize code, restrict the problem, use approximation, or accept heuristic search.

21.14. The Boundary Between Computability and Complexity

A problem being computable does not mean that it is efficiently solvable. Computability asks whether an algorithm can in principle terminate with the correct answer; complexity asks how required resources scale with input size.

Some decision problems have no general algorithm at all, with the halting problem as the classical boundary example. NP-complete problems are decidable, but known general exact algorithms may still have nonpolynomial worst-case cost.

For engineering, these are distinct statements: "no algorithm exists," "an algorithm exists but is expensive," and "we deliberately use an approximation or heuristic" should not be conflated.

21.15. From Exact Algorithms to Controlled Approximation

Exact answers are not always economical in large-scale data processing. From a data-structure perspective, MinHash/LSH builds signatures and buckets for approximate similarity search, reservoir sampling retains k items from an unknown-length stream in O(k) memory, and sketches estimate frequency or cardinality without materializing a complete table, subject to probabilistic error bounds. The engineering distinction is that an approximation with explicit error probability and memory cost is not an uncontrolled guess; it is an algorithm with a defined contract.

• Compare exhaustive similarity search with MinHash/LSH cost.
• Perform sampling and frequency estimation under bounded memory in streams.
• Report approximation error, memory complexity, and time complexity together.

Unit 22: Online Algorithms, Competitive Analysis, and Streaming Structures

Classical algorithm analysis often assumes the entire input is known before decisions are made.

Real systems frequently receive requests over time and must act without seeing the future.

This creates the online-algorithm model.

22.1. Online versus Offline

An offline algorithm can inspect the whole input.

An online algorithm proceeds as:

request_1 arrives
-> decide

request_2 arrives
-> decide

...

future requests are unknown

Decisions can be irreversible or expensive to revise.

Examples include cache eviction, scheduling, routing, resource allocation, and rent-versus-buy decisions.

22.2. Competitive Analysis

An online algorithm can be compared with an ideal offline optimum that knows the full future request sequence.

For a minimization problem, a conceptual guarantee is:

cost_online(sequence)
<=
c * cost_OPT(sequence)
+
constant

for every request sequence.

The offline OPT is a reference benchmark, not an implementable real-time system.

The competitive ratio measures part of the cost of making decisions without future knowledge.

22.3. Ski Rental

The classic model offers two choices:

rent for each use
or
buy once

while the total number of future uses is unknown.

If daily rent costs 1 and buying costs B, a deterministic strategy that rents for roughly B-1 uses and then buys can keep worst-case cost within about twice the offline optimum.

The point is the information constraint:

Buying too early and renting forever are both risky when the future horizon is unknown.

22.4. Online Caching

A bounded cache must evict an item when new data arrives and no free slot remains.

An offline optimum that knows the future can evict the item whose next use is farthest away.

A real policy does not know that future.

LRU instead uses past behavior:

evict the least recently used item

Caching is therefore a natural online problem:

• requests arrive continuously,
• memory is bounded,
• a wrong eviction creates future misses.

Actual CPU and database caches are more complex than this theoretical model, but the model isolates the future-information constraint.

22.5. Competitive Ratio Is Not the Only Metric

Worst-case competitive analysis may ignore workload distribution, locality, implementation constants, or real latency.

Production evaluation can combine:

competitive guarantee
+
trace replay
+
latency
+
hit rate
+
memory

Theory provides a worst-case perspective while trace-based benchmarking measures the actual workload.

22.6. Streaming Model

A streaming algorithm processes data in one or a small number of passes under:

input is very large
memory << input

constraints.

Instead of retaining every item, it stores a summary, sketch, sample, or probabilistic membership structure.

Controlled approximation may be necessary.

22.7. Bloom Filter

A Bloom filter supports probabilistic set-membership tests with little memory.

It uses:

m-bit array
k hash functions

Insertion sets the corresponding bits.

A query checks the same positions:

any bit is 0
-> definitely absent

all bits are 1
-> possibly present

Under the standard Bloom-filter contract:

false positives are possible
false negatives are not expected

provided the implementation and operations follow the model.

Deletion is not directly safe in a classic Bloom filter because one bit can be shared by several inserted elements. Variants such as counting Bloom filters change this trade-off.

22.8. False-positive Probability

After inserting n items, a common approximation is:

p ≈ (1 - exp(-k*n/m))^k

For fixed m and n, the useful number of hash functions lies near:

k ≈ (m/n) * ln(2)

The important lesson is the trade-off:

more bits
-> lower false-positive probability

too few or too many hashes
-> quality / CPU balance can worsen

22.9. Where Bloom Filters Fit

Suppose a disk lookup is expensive.

ask Bloom filter first
↓
"definitely absent"
-> skip disk lookup

"possibly present"
-> query the real index

A false positive causes extra work, not an incorrect final membership result.

Probabilistic structures are safest when their error mode maps to a controlled cost rather than a wrong authoritative answer.

22.10. Reservoir Sampling

Suppose stream length is unknown and only k uniformly sampled items should be retained.

A basic reservoir algorithm is:

store the first k items

for t = k+1, k+2, ...:
    choose random j in [1..t]
    if j <= k:
        reservoir[j] = current item

Memory usage is only O(k).

After processing t items, every item seen so far has probability:

k / t

of being in the reservoir.

22.11. Why Reservoir Sampling Remains Uniform

The new tth item enters with probability:

k/t

An old item was previously present with probability:

k/(t-1)

and survives replacement with probability:

1 - 1/t
=
(t-1)/t

so:

k/(t-1) * (t-1)/t
=
k/t

All seen items therefore retain equal inclusion probability.

22.12. Sampling and Estimation Are Separate Layers

A reservoir contains a sample, not the exact stream result.

An estimator computed from that sample has its own variance and confidence behavior.

Keep separate:

sampling algorithm
+
statistical estimator

22.13. Bound Streaming State Explicitly

Production streaming systems must also ask:

• Can hashes be adversarial?
• Can counters overflow?
• Must summaries be mergeable?
• Is the window bounded?
• Can data arrive late or out of order?
• How is state restored after restart?
• How is approximation error exposed?

These questions connect streaming theory to operational data engineering.

22.14. Online and Streaming Are Not Synonyms

Online algorithm:

make decisions without future knowledge

Streaming algorithm:

process an arriving data sequence under strict memory/pass limits

An algorithm can be online but memory-rich, streaming but not decision-oriented, or both.

22.15. Match the Cost Model to the Problem

The classical RAM model emphasizes CPU operations.

Online analysis adds the cost of missing future information.

Streaming analysis adds memory and pass limits.

External-memory analysis emphasizes block I/O.

Distributed analysis can add communication and synchronization costs.

Advanced algorithm engineering therefore begins with:

Which cost model represents the real bottleneck?

The same mathematical task can have a different best algorithm under a different cost model.

22.16. Mergeable Streaming Summaries

Keeping a summary state instead of every incoming record makes stream-processing memory use more predictable. Whether independently computed summaries can later be merged correctly across nodes is a separate property that must be established. Sums and counts are straightforward examples; merging means requires sample counts as well as local averages. The unweighted average of two local means is not the global mean when the partitions contain different numbers of observations.

Some probabilistic streaming algorithms provide explicit error-probability or approximation bounds. The false-positive probability of a Bloom filter, the relative error of a distinct-item estimate and the inclusion probability in reservoir sampling represent different types of guarantees. Combining several sketches in one pipeline does not imply that their individual error bounds transfer unchanged to the end-to-end result.

In distributed streaming, delayed or duplicated events make the update semantics as important as the data structure. A non-idempotent counter can be corrupted by replaying the same event twice. Remedies depend on key-based deduplication, event-time windows or an explicit replay contract. Memory consumption, window latency and result accuracy belong in the same cost model.

22.17. Stable Top-K Selection and Partitioned Merging Under Memory Bounds

A bounded min-heap can retain the largest k results without sorting all inputs. Processing n items takes O(n log k) time and O(k) auxiliary memory. If ties are unspecified, identical datasets may produce different visible orders. A total ordering such as (score, timestamp, stable_identifier) makes results reproducible, provided the identifier itself is stable for the relevant dataset.

In partitioned execution, retaining the local top k from each partition suffices for the global top k: an item excluded from its partition's local top k cannot enter the global top k. This property does not transfer automatically to all aggregates. A global sum per key, for example, may require combining contributions from several partitions before ranking. Deterministic order still does not imply that all eligible records were available; input coverage must be reported separately.

Correctness tests compare against full sorting on small synthetic datasets and expect an invariant result set under every input permutation. Tied scores, empty input, k=0, k>n and partition boundaries are important cases.

22.18. Invalidation Boundaries in Incremental Graph Computation

Adding one edge to a graph does not imply that every metric changes only locally. Vertex degree can be updated locally, while connected components, bridges, shortest paths or PageRank may change over a wider portion of the graph. An incremental strategy should be selected from the mathematical impact domain of the metric, not performance preference alone.

Record insertion or deletion, time-window changes and edge-weight updates are different event classes. Every result should be associated with its input graph version, filters and calculation parameters. An incorrectly invalidated cache provides fast but wrong answers. A full recomputation can serve as a differential-test oracle for incremental methods on small randomized graphs.

References

• Bloom, Burton H. “Space/Time Trade-offs in Hash Coding with Allowable Errors.” Communications of the ACM, 13(7), 422–426, 1970. DOI: https://doi.org/10.1145/362686.362692

• Borodin, Allan; El-Yaniv, Ran. Online Computation and Competitive Analysis. Cambridge University Press, 1998. ISBN 978-0-521-56392-5.

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. 4th ed., MIT Press, 2022. ISBN 9780262046305.

• Hopcroft, John E.; Karp, Richard M. “An n^(5/2) Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing, 2(4), 225–231, 1973. DOI: https://doi.org/10.1137/0202019

• Jure Leskovec; Anand Rajaraman; Jeffrey D. Ullman. Mining of Massive Datasets.

• Karp, Richard M. “Reducibility Among Combinatorial Problems.” In Complexity of Computer Computations, 85–103, Plenum Press, 1972.

• Knuth, Donald E.; Morris, James H., Jr.; Pratt, Vaughan R. “Fast Pattern Matching in Strings.” SIAM Journal on Computing, 6(2), 323–350, 1977. DOI: https://doi.org/10.1137/0206024

• Mark Allen Weiss. Data Structures and Algorithm Analysis in C++. Pearson, 2012.

• Robert Sedgewick; Kevin Wayne. Algorithms. Addison-Wesley, 2011.

• Saul B. Needleman; Christian D. Wunsch. “A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins.” Journal of Molecular Biology, 48(3), 443–453, 1970. DOI: https://doi.org/10.1016/0022-2836(70)90057-4

• Temple F. Smith; Michael S. Waterman. “Identification of Common Molecular Subsequences.” Journal of Molecular Biology, 147(1), 195–197, 1981. DOI: https://doi.org/10.1016/0022-2836(81)90087-5

• Stuart Russell, P. N. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2021.

• Tarjan, Robert E. “Amortized Computational Complexity.” SIAM Journal on Algebraic Discrete Methods, 6(2), 306–318, 1985. DOI: https://doi.org/10.1137/0606031

• Tarjan, Robert E. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing, 1(2), 146–160, 1972. DOI: https://doi.org/10.1137/0201010

• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms. MIT Press, 2009.

• Vitter, Jeffrey S. “Random Sampling with a Reservoir.” ACM Transactions on Mathematical Software, 11(1), 37–57, 1985. DOI: https://doi.org/10.1145/3147.3165

• Walter W. Piegorsch, Richard A. Levine, Hao Helen Zhang, Thomas C. M. Lee (eds.). Computational Statistics in Data Science. Wiley, 2022. ISBN 9781119561071.