computer-science

Programming

Programming Books on algorithms, data structures, system design, and formal verification. Book About [Algorithm Cookbook]({{< relref "programming/algorithms/_index.md" >}}) Practical patterns, correctness arguments, and implementation techniques [System Design]({{< relref "programming/system-design/_index.md" >}}) Scalability, architecture, and interview-style problem solving [Lean]({{< relref "programming/lean/_index.md" >}}) Theorem proving, formalization, and proof engineering

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways. These failures are not random. They arise from mismatches between the specification, the model, and the code. Recognizing these patterns early reduces debugging time and prevents subtle errors. Problem You have an implementation that behaves incorrectly or inconsistently, and you need a systematic way to identify likely causes. Solution Check the implementation against a small set of known...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.24 Benchmarking

Benchmarking measures how an implementation behaves on real inputs and real hardware. Complexity analysis tells you how an algorithm should scale. Benchmarking tells you what the constants, memory effects, and implementation details actually do. A benchmark should answer a specific question. It should not merely produce a number. Useful questions include whether one implementation is faster than another, whether the running time grows as expected, whether memory usage fits the...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.22 Numerical Limits

Algorithms are usually described with mathematical integers and real numbers. Implementations run with finite machine values. This difference matters. An algorithm can be correct in theory and still fail in code because an integer overflows, a floating-point comparison is unstable, or a counter cannot represent the true answer. Numerical limits should be checked during design, not after debugging. The input constraints often tell you which numeric type is required. Problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.20 Implementation Discipline

Implementation discipline means translating an algorithm into code without changing its meaning accidentally. The pseudocode gives the structure. The implementation must preserve the same state, boundaries, invariants, and output contract. Many algorithmic bugs are not failures of the idea. They are failures of translation: an inclusive interval becomes half-open, an index update skips an element, a comparison uses < instead of <= , or an integer type overflows. Implementation discipline...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.23 Stability and Determinism

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers. These properties do not always change the mathematical objective, but they often change the required output, the implementation, and the tests. An algorithm is deterministic if the same input always produces the same output. An algorithm is stable, in the common sorting sense, if equal keys keep their original relative order....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.21 Data Representation

Data representation is the choice of concrete form used to store the objects in a problem. The same mathematical object can have many representations, and each representation makes some operations cheap while making others expensive. Choosing the representation is therefore part of algorithm design. A graph can be stored as an edge list, adjacency list, adjacency matrix, or compressed sparse structure. A set can be stored as a sorted array,...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.19 Pseudocode Style

Pseudocode is a bridge between the problem statement and an implementation. It should expose the algorithmic idea without committing too early to language-specific details. Good pseudocode is precise enough to analyze, but simple enough to read as a description of the method. The purpose of pseudocode is not to look like code. Its purpose is to make control flow, data flow, invariants, and cost visible. Problem You need to describe...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.15 Dynamic Programming

Dynamic programming solves problems by storing answers to subproblems and reusing them. It is useful when a naive recursive solution repeats the same work many times. Instead of recomputing a subproblem every time it appears, the algorithm computes it once and records the result. The method depends on two properties: Optimal substructure: The answer to a larger problem can be built from answers to smaller problems. Overlapping subproblems: The same...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.17 Amortized Analysis

Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive. It is used when a data structure has rare costly steps that are paid for by many cheap steps. The guarantee is different from average-case analysis. Amortized analysis does not require random input or a probability distribution. It gives a worst-case bound over any valid sequence of operations. Problem You have an...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.16 Randomization

Randomized algorithms use random choices during execution. The output or running time may depend on those choices. Randomization is useful when it simplifies design, avoids adversarial patterns, or gives good expected performance with a small amount of code. A randomized algorithm still needs a correctness contract. The contract must say whether the algorithm is always correct, probably correct, or correct in expectation. Problem You want to use randomness to make...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.18 Reductions

A reduction transforms one problem into another problem. It is a way to reuse algorithms and transfer difficulty. If problem A can be converted into problem B, and we already know how to solve B, then we can solve A by translating the input, running the solver for B, and translating the output back. Reductions are useful in two directions. For algorithm design, they let you solve a new problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers. It is useful when the original problem has repeated structure and when the cost of combining subanswers is controlled. The pattern has three parts: divide: split the input into smaller pieces conquer: solve each piece recursively combine: merge the subanswers into the answer for the full input The key question is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.11 Testing Algorithms

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details. A good test suite is built from the problem statement. It checks whether the implementation satisfies the input and output contract under ordinary, boundary, and adversarial conditions. Algorithm tests should not only ask, "Does this example pass?" They should ask, "What assumption would fail if this test failed?" Each test should...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.13 Greedy Choices

A greedy algorithm builds a solution by making one locally best choice at a time. It does not reconsider earlier choices. This makes greedy algorithms simple and fast, but also easy to get wrong. The main difficulty is proof: you must show that each local choice can be part of some globally optimal solution. Greedy algorithms work when the problem has structure that makes local progress safe. A choice is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.12 Brute Force Baselines

A brute force baseline is the simplest correct algorithm you can write from the problem statement. It may be too slow for the final constraints, but it is valuable because it gives you a reference answer, exposes edge cases, and clarifies what the optimized algorithm must preserve. A good baseline is intentionally direct. It should follow the definition of the problem more closely than the efficient solution does. This makes...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.9 Lower Bounds

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation. It tells you what cannot be improved. Upper bounds come from algorithms. Lower bounds come from arguments about necessity. For example, if an algorithm scans an unsorted array to find the maximum value, the linear-time algorithm gives an upper bound of $O(n)$. A lower bound proves...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.10 Edge Cases

Edge cases are valid inputs that sit at the boundary of the specification. They are often small, empty, repeated, extreme, or structurally degenerate. They matter because many algorithms are designed around the typical case, while many bugs occur at the boundary. An edge case should not be treated as an exception to the problem. It is part of the problem. If the input is allowed by the specification, the algorithm...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.8 Big O Notation

Big O notation provides a formal way to describe how a function grows. In algorithms, it is used to express upper bounds on time and space complexity. The notation suppresses constant factors and lower order terms so that the dominant growth rate is clear. Problem You have derived a function that counts operations, such as (3n^2 + 5n + 7), and you need a standard way to express its growth....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.7 Space Complexity

Space complexity measures how much memory an algorithm uses as a function of input size. It complements time complexity and often determines whether an algorithm is feasible in practice. Memory includes both the input representation and any additional storage used during execution. The focus in algorithm design is usually on auxiliary space , which is the extra memory beyond the input itself. Problem You have an algorithm and need to...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.6 Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows. It does not try to predict the exact number of seconds on a particular machine. Instead, it gives a portable way to compare algorithms by counting how many primitive operations they perform as a function of the input. The main size parameter is usually written as (n). For graphs, we often use two parameters:...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.5 Recursion Invariants

Recursive algorithms replace loop structure with self-reference. Instead of tracking progress through iteration, you track progress through problem size. A recursion invariant describes what each call is responsible for computing and how that responsibility relates to smaller subproblems. The core idea is simple: every recursive call must solve a strictly smaller instance of the same problem, and the combination of those solutions must produce a correct result for the original...

Programming › Algorithm Cookbook ›

Chapter 1. Foundations

This chapter defines how you think about algorithms before you write any code. It establishes a small set of rules for describing problems, reasoning about correctness, and estimating cost. Every later technique relies on these rules, so the focus here stays on precision and repeatability. An algorithm begins with a contract. You specify inputs, outputs, and constraints in a way that removes ambiguity. This includes data shape, value ranges, ordering...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.2 Input and Output Models

An algorithm does not operate on an abstract idea of data. It operates on a chosen model of data. The same problem can look easy or hard depending on how the input is represented and how the output must be produced. For this reason, every serious algorithm description should state not only what the input means, but also how the input is presented to the algorithm. The input model defines...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.3 Correctness Arguments

A correctness argument explains why an algorithm returns an acceptable output for every valid input. It should be written before, or at least alongside, the implementation. Code tells you what the algorithm does. A correctness argument tells you why those steps solve the stated problem. A good correctness argument is local. It does not rely on intuition about the whole program at once. Instead, it identifies a property that remains...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.1 Problem Statements

An algorithm begins with a precise statement of the problem. The goal is to define the task so clearly that both correctness and complexity follow from the definition. Ambiguity at this stage propagates into proofs, implementations, and tests. A problem statement consists of four parts: input, output, constraints, and guarantees. Input specifies the structure and domain of data. You describe types, sizes, ordering, and any preconditions. For example, an input...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.4 Loop Invariants

Loop invariants are the primary tool for reasoning about iterative algorithms. They formalize what remains true at each step of a loop and provide a bridge between local updates and global correctness. A loop invariant is not an observation after the fact. It is a design component that guides how the loop is written. Problem You need a reliable method to prove that a loop-based algorithm is correct, especially when...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.25 Case Studies

This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms. Each example highlights how invariants, pointer discipline, and structural operations interact. Case Study 1: Merge Sort on Linked Lists Problem Sort a singly linked list in O(n log n) time using O(1) extra space. Approach Use divide-and-conquer: Split the list into two halves Recursively sort each half Merge the sorted halves Implementation sort(head): if head ==...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.11 Insertion Patterns

Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes. In a singly linked list, insertion is defined relative to a known position, usually a predecessor node. In a doubly linked list, insertion can be defined relative to either neighbor. Problem Given a linked list and a rule for placement, insert a new node or a sequence of nodes while maintaining structural...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.12 Dummy Heads (Dummy Nodes)

A dummy head is a fixed node placed before the real head of a singly linked list. It does not carry user data. It provides a stable predecessor for every real node, including the original head. This removes most boundary cases from insertion and deletion. Problem Algorithms that modify the first node require special handling because the head has no predecessor. This leads to branching logic and error-prone code paths....

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.18 Iterators

An iterator is an object or procedure that visits the nodes of a linked list one at a time. It separates traversal from the operation applied to each node. This separation is useful because many list algorithms have the same walking pattern but different processing logic. Problem You need to scan a linked list without exposing every detail of pointer movement to the caller. Typical uses include: print every value...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.14 Persistent Lists

A persistent list is a list that preserves older versions after an update. Instead of modifying nodes in place, the algorithm creates new nodes for the changed prefix and shares the unchanged suffix. This style is common in functional programming, immutable data structures, undo systems, and versioned state. Problem You want to update a list while keeping the original list available. For example, given: old: 1 -> 2 -> 3...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.16 Intrusive Lists

An intrusive list stores the linkage fields inside the objects being linked. Instead of allocating a separate wrapper node that contains a value, each object contains its own next pointer, or both prev and next pointers for a doubly linked list. This design is common in kernels, memory allocators, schedulers, game engines, and low-level systems where allocation, ownership, and memory layout must be controlled carefully. Problem You want to maintain...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.21 LRU Cache Structure

An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded. It combines two data structures: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates. The hash map answers "where is the entry for this key?" The list answers "which entry was used least recently?" Problem Design a cache with these operations: get(key) ->...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.15 Skip Lists

A skip list augments a sorted linked list with multiple levels of forward pointers. Higher levels “skip” over many nodes, enabling fast search, insertion, and deletion. The structure is probabilistic: node heights are assigned randomly, which yields expected logarithmic performance without rotations or strict balancing. Structure Each node stores a value and an array of forward pointers. Node { value next[0..h] // level 0 is the base list } A...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.17 Memory Ownership

Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node. In linked list algorithms, pointer correctness is only one side of the problem. The other side is lifetime correctness: every node that remains linked must be alive, and every node that is removed must still be handled according to the memory model of the language. Problem You have a linked list whose...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.13 Pointer Aliasing

Pointer aliasing occurs when two or more references point to the same node. In linked list algorithms, aliasing is unavoidable. Multiple variables often refer to the same structure during traversal, insertion, deletion, or merging. Correct algorithms treat aliasing as a controlled property. Incorrect algorithms create unintended sharing, which leads to structural corruption. Problem You manipulate a linked list using multiple pointers. Some of these pointers may refer to the same...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.24 Complexity Analysis

Linked list algorithms are dominated by pointer traversal and constant-time link updates. The key to correct analysis is to count how many nodes are visited and how many pointers are changed. Unlike arrays, there is no random access, so position-based operations depend on traversal length. Cost Model Use these basic costs: read next pointer: O(1) write next pointer: O(1) allocate node: O(1) free node: O(1) compare values: O(1) A loop...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.20 Queue via List

A queue is a first-in, first-out structure. The first value inserted is the first value removed. A singly linked list implements a queue efficiently when the structure keeps both a head pointer and a tail pointer. The head points to the next node to remove. The tail points to the last node inserted. Queue { head : Node | null tail : Node | null } Structure Each node stores...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.19 Stack via List

A stack is a last-in, first-out (LIFO) structure. A singly linked list implements a stack naturally by treating the head as the top. All operations occur at the head, which gives constant-time push and pop. Structure Use a singly linked list: Node { value next : Node | null } Stack { head : Node | null } The invariant is: head points to the top of the stack Push...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.23 Testing Pointer Code

Pointer code should be tested by checking structure, not only values. A linked list can contain the right values while still having broken links, accidental cycles, stale tails, or shared nodes that should have been detached. Good tests therefore verify both the sequence and the shape of the list. Problem You want to test linked list algorithms such as insertion, deletion, reversal, splitting, merging, and LRU operations. A weak test...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.22 Edge Cases

Edge cases are inputs that sit near the boundary of an algorithm's assumptions. In linked list problems, these cases usually involve empty lists, one-node lists, changes at the head, changes at the tail, repeated values, cycles, shared nodes, or invalid positions. A linked list algorithm is often correct for the middle of the list before it is correct for the boundaries. This section gives a checklist for finding and handling...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.1 Singly Linked Lists

A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node. The structure is defined inductively: an empty list is nil , and a non-empty list is a node followed by another list. This definition forces all traversal to proceed in one direction, from head to tail. Structure A minimal node definition in pseudocode is: Node { value next...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.10 Deletion Patterns

Deletion removes one or more nodes from a linked list by changing links around them. The values stored in the nodes are usually irrelevant. What matters is the predecessor of the node being removed and the successor that must remain reachable afterward. In a singly linked list, deletion is harder than insertion because a node does not know its predecessor. For this reason, most deletion algorithms maintain a prev pointer,...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.6 Fast and Slow Pointers

Fast and slow pointers are two references that traverse the same linked structure at different speeds. Usually, the slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This simple difference creates information about the shape of the list: whether a cycle exists, where the middle lies, or how to split the list into two parts. Problem You need to locate structural...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.5 Cycle Detection

A cycle exists in a linked list when some node’s next pointer eventually leads back to a previously visited node. In such a structure, traversal never reaches null . Detecting this condition requires reasoning about the movement of pointers rather than counting nodes. Problem Given the head of a singly linked list, determine whether the list contains a cycle. If a cycle exists, optionally identify the node where the cycle...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.8 Split Patterns

Splitting a linked list means cutting one list into two or more lists while preserving the original nodes. The operation changes links, not values. It appears in merge sort, partitioning, alternating lists, palindrome checks, and algorithms that process the front and back halves separately. Problem Given the head of a singly linked list, divide it into parts according to a rule. Common rules include: split into first half and second...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.2 Doubly Linked Lists

A doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node. Compared with a singly linked list, it gives bidirectional movement, but every structural update must preserve two links instead of one. Structure A minimal node definition is: Node { value prev : Node | null next : Node | null } The...

Programming › Algorithm Cookbook ›

Chapter 3. Linked Lists and Pointers

Linked lists are the first data structure in this book where the shape of the data matters as much as the values stored inside it. An array gives direct access by index, but a linked list gives access through references from one node to the next. This changes the way algorithms are written. A solution must track not only what value is being inspected, but also which node owns the...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.4 Reversal

Reversal transforms a linked list so that the direction of all edges is flipped. For a list a -> b -> c -> d -> null the result is d -> c -> b -> a -> null The operation is structural. No values change. Only the next pointers are reassigned. Problem Given the head of a singly linked list, reverse the list in place and return the new head....

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.3 Sentinel Nodes

A sentinel node is an artificial node placed at the boundary of a linked list. It usually does not store a real user value. Its purpose is to simplify algorithms by ensuring that important positions, especially the head and tail boundaries, always have a node that can be referenced safely. In a singly linked list, the most common sentinel is a dummy head. dummy.next = head The real list begins...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.9 Merge Patterns

Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants. Unlike simple two-list merge, these patterns generalize to conditional routing, alternating consumption, or multi-way combination. Problem Given one or more input lists, construct an output list by selecting nodes according to a rule, without allocating new nodes. Typical rules include: merge two sorted lists merge k sorted lists alternate...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.7 Merge Two Sorted Lists

Merging combines two sorted singly linked lists into one sorted list by relinking nodes. The operation does not create new nodes. It reuses existing nodes and preserves their order. Problem Given two lists l1 and l2 , both sorted in non-decreasing order, produce a single sorted list. l1: a1 -> a2 -> ... l2: b1 -> b2 -> ... Return a list that contains all nodes from both inputs, ordered....

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.25 Boundary Conditions

Boundary conditions define the valid domain of indices, ranges, and states in an algorithm. Many bugs arise not from the main logic, but from incorrect handling of edges such as empty input, single-element cases, or off-by-one errors. This section provides a systematic approach to designing and verifying boundaries. Problem Given an algorithm over arrays or strings, ensure correctness for all valid inputs, including edge cases: empty input single element full...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.22 Spiral Traversal

Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column, then shrinking the boundaries and repeating. Problem Given a matrix: 1 2 3 4 5 6 7 8 9 Spiral order: 1, 2, 3, 6, 9, 8, 7, 4, 5 Boundaries Maintain four boundaries: top, bottom, left, right Initialize: top = 0...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.24 Common Patterns

Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns. The value of these patterns is that they provide a known invariant, a known complexity bound, and a known set of boundary cases. Once the pattern is recognized, the remaining work is mostly adapting the state and update rules. Pattern 1: Linear Scan Use a linear scan when every element...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.23 Flood Fill

Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region. Connectivity is defined by a neighborhood relation, typically 4-directional or 8-directional. Problem Given a grid a , a starting cell (sr, sc) , and a new value newVal , replace all cells connected to (sr, sc) that have the same original value with newVal...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.20 Tries

A trie is a tree structure for storing a set of strings so that common prefixes are shared. Each edge corresponds to a symbol, and each node represents a prefix. Tries support fast insertion, lookup, prefix queries, and lexicographic traversal. Problem Maintain a dynamic set of strings and support: Insert(s) Contains(s) HasPrefix(p) List all strings with prefix p A naive approach compares strings directly and costs O(length) per comparison. A...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.18 String Comparison

String comparison determines the ordering or equality of two strings. The simplest form compares byte sequences. More advanced forms compare Unicode code points, normalized text, or locale-specific collation units. Algorithmically, the important point is that comparison is usually linear in the length of the common prefix. Problem Given two strings a and b , decide whether: a == b a < b a > b For example: "apple" < "apply"...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.19 Parsing Expressions

Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity. The result is typically an abstract syntax tree (AST) or a computed value. This section presents a practical method, the shunting-yard algorithm, followed by a direct recursive descent approach. Problem Given an expression: 3 + 4 * (2 - 1) Produce either: a value: 7 or a structured representation such as an AST...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.17 Rolling Hashes

Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly. After preprocessing, the hash of any substring can be computed in constant time. This is useful in substring search, duplicate detection, palindrome checks, longest common substring, and approximate text indexing. The method is usually probabilistic. Equal hashes suggest equal strings, but collisions can occur unless the algorithm uses a collision-free representation or verifies matches...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.21 Matrix Traversal

Matrix traversal processes a two-dimensional array in a defined order. It is the two-dimensional form of array traversal, but the extra dimension adds boundary choices, coordinate conventions, and common patterns such as row-major order, column-major order, diagonal scans, and grid-neighbor exploration. Problem Given a matrix a with rows rows and cols columns, visit every cell exactly once. Example: 1 2 3 4 5 6 7 8 9 A row-major traversal...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.12 Substring Search

Substring search locates occurrences of a pattern p inside a text s . The objective is to find all indices i such that: s[i : i + m] == p where m = len(p) . The choice of algorithm depends on input size, number of queries, and tolerance for probabilistic error. Problem Given: s = "abracadabra" p = "abra" Return all starting indices: [0, 7] Baseline: Naive Search Check every...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.13 Palindromes

A palindrome is a sequence that reads the same forward and backward. In array and string algorithms, palindrome problems usually reduce to symmetric comparison, center expansion, dynamic programming, or hashing. For strings, first decide whether the unit of comparison is a byte, a Unicode code point, or a normalized user-visible character. The examples here use byte strings for clarity. Problem Given a string s , determine whether it is a...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.15 Frequency Tables

A frequency table records how many times each value appears in an array, string, or stream. It is one of the simplest and most useful summaries of linear data. Many problems about duplicates, anagrams, modes, majority elements, histograms, and sliding windows reduce to maintaining counts. Problem Given a sequence, count how often each element occurs. Example: [4, 1, 4, 2, 1, 4] Frequency table: 1 -> 2 2 -> 1...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.16 Run-Length Encoding

Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair (value, count) . It is effective when the input contains long runs of the same element and serves as a simple pre-processing step for more complex compression or for speeding up certain algorithms. Problem Given a sequence, produce its run-length encoding. Example: [1, 1, 1, 2, 2, 3, 1, 1] Encoding: [(1, 3), (2, 2), (3, 1),...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.14 Anagrams

Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order. For example, "listen" and "silent" are anagrams because each letter appears the same number of times in both strings. The usual algorithmic task is to compare frequency tables. Sorting also works, but counting is often faster when the alphabet is small or bounded. Problem Given two strings a and b , decide...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.11 Tokenization

Tokenization converts a string into a sequence of meaningful units called tokens. A token may be a word, number, identifier, operator, delimiter, quoted string, or whitespace block, depending on the grammar. Tokenization is the first stage of many parsers because it separates low level character scanning from higher level syntactic analysis. Problem Given an input string, split it into tokens while preserving enough information for later processing. For example: sum...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.8 In-Place Modification

In-place modification changes an array without allocating another array of the same size. The goal is to reuse the input storage while preserving the part of the data that has not yet been read. This pattern is common in filtering, deduplication, partitioning, reversing, rotation, merging, and compaction. Problem Given an array a , transform it using only O(1) extra space. For example, remove all zero values: [0, 3, 0, 4,...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.7 Rotation

Array rotation moves elements by a fixed offset while preserving their relative circular order. A left rotation by k moves each element at index i to index i - k modulo n . A right rotation by k moves each element at index i to index i + k modulo n . Rotation appears in cyclic buffers, scheduling, string matching, block rearrangement, and in-place array transformations. Problem Given an array:...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.9 Deduplication

Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order. The design depends on two decisions: whether the input is sorted whether the output must preserve original order These decisions determine both the algorithm and its complexity. Problem Given an array a , produce a sequence that contains each value at most once. Example: [3, 1, 3, 2, 1, 4] Possible outputs: preserve first occurrence order:...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.10 String Scanning

String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization. The algorithm reads a string from left to right, maintains a small state, and decides what to do with each character or byte. The main difference between string scanning and array traversal is representation. A string may be treated as bytes, Unicode code points, or higher level text units. The correct choice depends on the problem....

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.6 Partitioning

Partitioning rearranges an array so that elements are grouped by a predicate. The order inside each group may or may not be preserved, depending on the algorithm. This pattern appears in quicksort, selection, filtering, deduplication, stream compaction, and many in-place array transformations. The central idea is to maintain a boundary between elements that are already classified and elements that are still unknown. Problem Given an array a and a predicate...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.4 Two Pointers

The two pointers technique uses two indices that move through an array or string in a controlled way. The main idea is to avoid restarting a scan from the beginning when useful information has already been discovered. When the pointers move monotonically, the total number of pointer movements is linear. This pattern is useful when the problem has an ordered structure: sorted arrays, contiguous ranges, opposite-end searches, or windows whose...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.5 Sliding Windows

Sliding windows maintain a contiguous subarray [l, r) while both endpoints move forward. The window expands to include new elements and contracts to restore a constraint. When both pointers are monotone, each index is visited a constant number of times, giving linear time. This technique applies when a property over a range can be updated incrementally as elements enter or leave the window. Problem Given an array or string, find...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.2 Prefix Sums

Prefix sums are a preprocessing technique for answering repeated range sum queries on an array. Instead of summing a range from scratch each time, we build an auxiliary array that stores cumulative totals. After this preprocessing step, each range sum can be computed in constant time. Problem You have an array A of length n . You need to answer many queries of the form: sum of A[l] through A[r]...

Programming › Algorithm Cookbook ›

Chapter 2. Arrays and Strings

This chapter studies linear data as the primary substrate for algorithm design. Arrays and strings appear simple, but most high performance solutions reduce to controlled traversal, local state maintenance, and careful boundary handling on these structures. The objective here is to make these operations predictable and composable. An array is treated as a contiguous block of memory with constant time indexed access. A string is treated as a sequence with...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.3 Difference Arrays

A difference array is the inverse pattern of a prefix sum. Prefix sums make range queries fast. Difference arrays make range updates fast. The typical problem is this: you have an array A of length n , and you need to apply many updates of the form "add x to every element from index l through index r ." Updating each element directly costs O(r - l + 1) per...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.1 Array Traversal

Array traversal is the base operation for all algorithms over linear data. The task is to visit elements in a defined order, maintain a small amount of state, and ensure that every access is valid. Most higher level patterns reduce to controlled traversal with stronger invariants. Problem You have an array A of length n . You want to process each element, possibly combining information from earlier positions, while maintaining...

Maths ›

68. Computer Science

This volume studies theoretical and practical foundations of computation. It connects algorithms, systems, and formal models with mathematical rigor. Part I. Foundations of Computation Chapter 1. Models of Computation 1.1 Finite automata 1.2 Turing machines 1.3 Computability 1.4 Church–Turing thesis 1.5 Examples Chapter 2. Formal Languages 2.1 Alphabets and strings 2.2 Regular languages 2.3 Context-free languages 2.4 Grammars 2.5 Applications Chapter 3. Logic and Proof Systems 3.1 Propositional logic 3.2...

Programming ›

Algorithm Cookbook

Chapter 1. Foundations Problem statements Input and output models Correctness arguments Loop invariants Recursion invariants Time complexity Space complexity Big O notation Lower bounds Edge cases Testing algorithms Brute force baselines Greedy choices Divide and conquer Dynamic programming Randomization Amortized analysis Reductions Pseudocode style Implementation discipline Data representation Numerical limits Stability and determinism Benchmarking Common failure modes Chapter 2. Arrays and Strings Array traversal Prefix sums Difference arrays Two pointers...

#computer-science

Programming

1.25 Common Failure Modes

1.24 Benchmarking

1.22 Numerical Limits

1.20 Implementation Discipline

1.23 Stability and Determinism

1.21 Data Representation

1.19 Pseudocode Style

1.15 Dynamic Programming

1.17 Amortized Analysis

1.16 Randomization

1.18 Reductions

1.14 Divide and Conquer

1.11 Testing Algorithms

1.13 Greedy Choices

1.12 Brute Force Baselines

1.9 Lower Bounds

1.10 Edge Cases

1.8 Big O Notation

1.7 Space Complexity

1.6 Time Complexity

1.5 Recursion Invariants

Chapter 1. Foundations

1.2 Input and Output Models

1.3 Correctness Arguments

1.1 Problem Statements

1.4 Loop Invariants

3.25 Case Studies

3.11 Insertion Patterns

3.12 Dummy Heads (Dummy Nodes)

3.18 Iterators

3.14 Persistent Lists

3.16 Intrusive Lists

3.21 LRU Cache Structure

3.15 Skip Lists

3.17 Memory Ownership

3.13 Pointer Aliasing

3.24 Complexity Analysis

3.20 Queue via List

3.19 Stack via List

3.23 Testing Pointer Code

3.22 Edge Cases

3.1 Singly Linked Lists

3.10 Deletion Patterns

3.6 Fast and Slow Pointers

3.5 Cycle Detection

3.8 Split Patterns

3.2 Doubly Linked Lists

Chapter 3. Linked Lists and Pointers

3.4 Reversal

3.3 Sentinel Nodes

3.9 Merge Patterns

3.7 Merge Two Sorted Lists

2.25 Boundary Conditions

2.22 Spiral Traversal

2.24 Common Patterns

2.23 Flood Fill

2.20 Tries

2.18 String Comparison

2.19 Parsing Expressions

2.17 Rolling Hashes

2.21 Matrix Traversal

2.12 Substring Search

2.13 Palindromes

2.15 Frequency Tables

2.16 Run-Length Encoding

2.14 Anagrams

2.11 Tokenization

2.8 In-Place Modification

2.7 Rotation

2.9 Deduplication

2.10 String Scanning

2.6 Partitioning

2.4 Two Pointers

2.5 Sliding Windows

2.2 Prefix Sums

Chapter 2. Arrays and Strings

2.3 Difference Arrays

2.1 Array Traversal