Computer Science

Data Structures

Arrays and Linked Lists

• Array — contiguous block of memory; random access O(1); insertion/deletion at arbitrary index O(n) due to shifting; fixed size in static variants, amortized O(1) append in dynamic arrays.
• Dynamic array (ArrayList / vector) — doubles capacity when full; amortized O(1) append; underlying copies are O(n) but infrequent.
• Linked list (singly) — each node stores a value and a pointer to the next node; O(1) head insertion/deletion; O(n) search and arbitrary access; no wasted capacity.
• Doubly linked list — each node stores prev and next pointers; O(1) deletion given the node; used in LRU cache implementations.

Stacks and Queues

• Stack — LIFO; push/pop/peek all O(1); implemented with array or linked list; used for function call frames, expression parsing, DFS.
• Queue — FIFO; enqueue/dequeue O(1) with circular array or linked list; used for BFS, scheduling.
• Deque (double-ended queue) — O(1) insertion and deletion at both ends; sliding-window problems.
• Priority queue — element with the highest (or lowest) priority is dequeued first; typically implemented as a heap; O(log n) push/pop.

Trees

• Binary tree — each node has at most two children; a complete binary tree fills levels left to right; a perfect binary tree has all leaves at the same level.
• Binary search tree (BST) — left child < parent < right child; search/insert/delete O(h) where h is height; degenerates to O(n) for sorted input.
• AVL tree — self-balancing BST; height difference between subtrees ≤ 1; rotations maintain O(log n) operations.
• Red-black tree — self-balancing BST with node coloring; guarantees O(log n); used in C++ std::map, Java TreeMap, Linux scheduler.
• B-tree — generalized balanced tree with branching factor > 2; nodes can hold many keys; minimizes disk I/O; standard in database index structures; B+ tree variant stores all data in leaves with leaf-to-leaf linked list.
• Trie (prefix tree) — tree where each path from root to node encodes a string prefix; O(m) search where m is string length; used in autocomplete, spell-check.
• Segment tree — binary tree over an array; supports range queries (sum, min, max) and point updates in O(log n); a Fenwick tree (binary indexed tree) is a simpler structure for prefix sums.

Heaps

• Min-heap / max-heap — complete binary tree where parent ≤ children (min) or parent ≥ children (max); stored compactly in an array: left child at 2i+1, right child at 2i+2; insert O(log n), extract-min/max O(log n), peek O(1), build from array O(n).
• Heap applications — priority queues, heap sort, Dijkstra’s algorithm, scheduling.

Hash Tables

• Hash table — key-value store; hash function maps keys to bucket indices; average O(1) insert, delete, search; worst case O(n) with collisions.
• Collision resolution — separate chaining (each bucket is a linked list); open addressing (linear probing, quadratic probing, double hashing); load factor λ = n/m; rehashing triggered at high load.
• Hash function properties — deterministic, uniform distribution, fast to compute; cryptographic hashes additionally require preimage resistance and collision resistance.

Graphs

• Representations — adjacency matrix: O(V²) space, O(1) edge lookup; adjacency list: O(V + E) space, standard for sparse graphs.
• Directed (digraph) vs undirected — edges have direction or not; in-degree / out-degree vs degree.
• Weighted vs unweighted — weighted edges carry a numeric cost; used in shortest-path and MST algorithms.
• DAG (directed acyclic graph) — no cycles; enables topological sort; used in dependency resolution, build systems.

Other Key Structures

• Disjoint-set / union-find — data structure tracking a partition of elements into disjoint sets; supports find (which set does x belong to?) and union (merge two sets); with path compression and union by rank, both operations are nearly O(1) amortized (inverse Ackermann time); critical for Kruskal’s MST algorithm.
• Skip list — probabilistic data structure; layered linked lists with “express lanes”; supports search, insert, delete in O(log n) expected time; used in Redis sorted sets; invented by William Pugh (1990).
• Bloom filter — probabilistic set-membership structure; uses k hash functions and a bit array; false positives possible, false negatives impossible; space-efficient; used in databases, caches, and CDNs to avoid expensive lookups.
• Fenwick tree (binary indexed tree) — compact array-based structure for prefix-sum queries and point updates, both O(log n); simpler implementation than a segment tree for sum queries.

Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked list	O(n)	O(n)	O(1)	O(1)*	O(n)
Hash table (avg)	—	O(1)	O(1)	O(1)	O(n)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Min/Max heap	O(n)	O(n)	O(log n)	O(log n)	O(n)

*O(1) deletion given a pointer to the node.

• Circular buffer (ring buffer) — fixed-size array treated as circular; head and tail pointers advance with wrap-around; O(1) enqueue and dequeue; used in I/O buffering, producer-consumer pipelines.
• Adjacency matrix — V×V matrix; entry [i][j] = 1 (or weight) if edge i→j exists; O(V²) space; O(1) edge lookup; preferred for dense graphs.
• Adjacency list — array of lists, one per vertex; O(V + E) space; the standard representation for sparse graphs; used by BFS, DFS, Dijkstra.
• Sparse matrix — matrix with mostly zero entries; compressed representations (CSR, COO) store only non-zero values; key in scientific computing, graph algorithms, and neural-network layers.
• LRU cache — Least Recently Used eviction policy; implemented with a doubly linked list + hash map achieving O(1) get and put; frequent interview problem; used in OS page replacement and CPU caches.

Sorting and Searching

Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable?
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Yes
Radix sort	O(nk)	O(nk)	O(nk)	O(n+k)	Yes

• Comparison-sort lower bound — any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case; information-theoretic argument: n! possible orderings require at least log₂(n!) ≈ n log n comparisons to distinguish; applies to mergesort, heapsort, quicksort; non-comparison sorts (radix, counting) bypass this by exploiting integer structure.
• Stable sort — equal elements maintain their original relative order; merge sort and insertion sort are stable; quicksort and heap sort typically are not.
• Quicksort pivot strategies — first element (bad on sorted input), random pivot, median-of-three; introsort (used in C++ STL) switches to heap sort to avoid worst case.
• Lower bound — comparison-based sorting cannot beat O(n log n) in the worst case (information-theoretic argument: ⌈log₂(n!)⌉ comparisons required to distinguish all n! orderings, by Stirling’s approximation Θ(n log n)); non-comparison sorts (counting, radix) bypass this with integer keys.
• Quicksort — divide-and-conquer; choose a pivot, partition into smaller/larger, recurse; average O(n log n), worst O(n²) on sorted input with bad pivot choice; in-place (O(log n) stack); Hoare’s original partition (1959); introsort (C++ STL) switches to heapsort after recursion depth exceeds 2 log n.
• Merge sort — guaranteed O(n log n) all cases; stable; O(n) auxiliary space; recursive split-and-merge; preferred for linked lists; John von Neumann credited (1945); basis of Timsort (Python/Java default), which exploits natural runs in data.
• Heapsort — in-place O(n log n) sort; build a max-heap in O(n), then repeatedly extract maximum; not stable; constant O(1) space advantage over merge sort; poor cache performance compared to quicksort.
• Counting sort — integer keys only; create a frequency array of size k; O(n + k) time and space; stable; efficient when k = O(n).
• Radix sort — sort by individual digits/characters from least significant to most significant (LSD) or reverse (MSD); O(nk) where k is number of digits; uses counting sort as subroutine; stable.

Searching

• Linear search — O(n); works on unsorted data.
• Binary search — O(log n); requires sorted array; halves the search space each step; classic source of off-by-one errors (use mid = lo + (hi - lo) / 2 to avoid overflow).
• Interpolation search — O(log log n) average for uniformly distributed sorted data; O(n) worst case.

String Algorithms

• Knuth-Morris-Pratt (KMP) — string search in O(n + m) time (n = text length, m = pattern length); precomputes a failure function (partial match table) encoding the longest proper prefix that is also a suffix; avoids re-examining text characters; Donald Knuth, James Morris, Vaughan Pratt (1977).
• Rabin-Karp algorithm — string search using rolling hashes; O(n + m) expected, O(nm) worst case (hash collisions); particularly useful for multi-pattern search (detecting plagiarism); Michael Rabin and Richard Karp (1987).
• Boyer-Moore algorithm — right-to-left pattern comparison with bad-character and good-suffix heuristics; O(n/m) best case (sublinear); common in practical text editors and grep.
• Z-algorithm — linear O(n + m) string matching; builds Z-array where Z[i] = length of longest substring starting at position i that is also a prefix of the string; alternative to KMP.

Algorithms

Recursion and Divide-and-Conquer

• Recursion — a function that calls itself on a smaller subproblem; requires a base case; each call uses stack frame space, so O(n) space for depth n.
• Tail recursion — recursive call is the last operation; some languages/compilers optimize to iteration (tail-call optimization); Python does NOT.
• Divide-and-conquer — split into subproblems, solve recursively, combine; merge sort, quicksort, binary search, Strassen’s matrix multiplication follow this pattern.
• Master theorem — gives O-notation for recurrences of the form T(n) = aT(n/b) + f(n).

Dynamic Programming

• Dynamic programming (DP) — solve overlapping subproblems once, store results; two approaches: top-down (memoization) with recursion + cache; bottom-up (tabulation) fills a table iteratively.
• Optimal substructure — optimal solution to the whole contains optimal solutions to subproblems; required for DP.
• Classic DP problems — Fibonacci, 0/1 knapsack, longest common subsequence (LCS), longest increasing subsequence (LIS), edit distance (Levenshtein), matrix chain multiplication, coin change.
• Memoization — top-down DP; cache results of recursive calls so each subproblem is solved at most once; straightforward to implement from a recursive solution; may have call-stack overhead vs tabulation.
• Edit distance (Levenshtein) — minimum number of single-character insertions, deletions, substitutions to transform one string to another; O(nm) DP; used in spell-check, bioinformatics sequence alignment.
• Longest common subsequence (LCS) — O(nm) DP classic; not the same as longest common substring (contiguous); DNA sequence comparison, diff utilities.
• Euclidean algorithm — finds GCD of two integers by repeated remainder; GCD(a, b) = GCD(b, a mod b); terminates in O(log min(a,b)) steps; one of the oldest known algorithms (Euclid’s Elements, ~300 BCE); extended Euclidean algorithm finds Bezout coefficients.

  Greedy Algorithms

• Greedy — make the locally optimal choice at each step; does not always yield global optimum but works for some problems; requires proof of greedy choice and optimal substructure.
• Greedy examples — activity selection, Huffman coding, Kruskal’s and Prim’s MST, Dijkstra’s shortest path (non-negative weights only).

Graph Algorithms

• Huffman coding — greedy algorithm for optimal prefix-free compression; builds a binary tree by repeatedly merging the two lowest-frequency symbols; produces variable-length codes where frequent symbols get shorter codes; O(n log n); used in JPEG, MP3, ZIP; David Huffman (1952).

• Activity selection / interval scheduling — greedy: always pick the activity that finishes earliest; proves that greedy is optimal for maximizing non-overlapping intervals; classic proof of greedy correctness.

• BFS (Breadth-First Search) — explores level by level using a queue; O(V + E); finds shortest paths in unweighted graphs; detects bipartiteness.
• DFS (Depth-First Search) — explores as deep as possible using a stack (or recursion); O(V + E); used for cycle detection, topological sort, strongly connected components.
• Dijkstra’s algorithm — single-source shortest paths in non-negative weighted graphs; uses a min-heap; O((V + E) log V) with binary heap; fails with negative edge weights.
• Kruskal’s algorithm — minimum spanning tree (MST); sort edges by weight; add edge if it doesn’t create a cycle (union-find); O(E log E).
• Prim’s algorithm — MST starting from a node; greedy; O((V + E) log V) with binary heap.
• Topological sort — linear ordering of vertices in a DAG such that all edges go forward; Kahn’s algorithm (BFS-based) or DFS-based (reverse finish order).
• Strongly Connected Components (SCC) — Tarjan’s algorithm (O(V + E)) and Kosaraju’s algorithm find SCCs in directed graphs.
• A* search — BFS/Dijkstra variant using a heuristic h(n) to guide search; optimal when h is admissible (never overestimates); used in pathfinding/game AI.
• Fast Fourier Transform (FFT) — computes the Discrete Fourier Transform in O(n log n) instead of O(n²); Cooley-Tukey algorithm (1965); key to polynomial multiplication, signal processing, image compression (JPEG); used to multiply large integers.
• Bellman-Ford — single-source shortest paths tolerating negative edge weights; relaxes all edges V-1 times; O(VE); can detect negative cycles (a V-th relaxation pass changes a distance); slower than Dijkstra but more general.
• Floyd-Warshall — all-pairs shortest paths via O(V³) DP; d[i][j][k] = shortest path from i to j using only vertices 1..k as intermediates; handles negative weights but not negative cycles; produces a distance matrix.
• Two-pointer / sliding window — linear-time techniques for array/string problems; two pointers move toward each other or both move right; avoids nested loops; examples: sorted pair sums, subarray problems.
• Bit manipulation — exploiting binary representations; XOR tricks (find single number, swap without temp), AND/OR masking, left/right shifts; bitmask DP for subset enumeration; O(1) operations.
• Network flow (max-flow / min-cut) — find maximum flow through a directed capacity graph; Ford-Fulkerson method (augmenting paths); Edmonds-Karp uses BFS for O(VE²); max-flow min-cut theorem: maximum flow equals minimum cut capacity.

Complexity Theory

Big-O Notation

• Big-O O(f) — upper bound on growth rate; O(g) means the function grows no faster than g asymptotically; constant factors dropped.
• Big-Omega Ω(f) — lower bound; Big-Theta Θ(f) — tight bound (both upper and lower).
• Common complexities — O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
• Amortized analysis — averages cost over a sequence of operations; dynamic array append is O(1) amortized despite occasional O(n) copies.
• Space complexity — memory used as a function of input size; important alongside time complexity; O(1) in-place (heapsort), O(log n) stack (quicksort), O(n) auxiliary (mergesort).
• NP-hardness reduction technique — to prove problem X is NP-hard, reduce a known NP-hard problem (often 3-SAT) to X in polynomial time; if you can solve X, you can solve 3-SAT; the direction of reduction matters.
• Approximation algorithms — polynomial-time algorithms for NP-hard optimization problems guaranteed to return a solution within a factor of optimal; e.g., 2-approximation for vertex cover; greedy (1 - 1/e)-approximation for set cover; PTAS = polynomial-time approximation scheme.
• Randomized algorithms — use random choices; Las Vegas algorithms always correct (expected fast, e.g., randomized quicksort); Monte Carlo algorithms always fast (may be wrong with small probability, e.g., Miller-Rabin primality test).

Complexity Classes

• P — decision problems solvable in polynomial time by a deterministic Turing machine; considered “tractable.”
• NP (Nondeterministic Polynomial time) — decision problems whose solutions can be verified in polynomial time; every problem in P is in NP.
• NP-complete — hardest problems in NP; a problem is NP-complete if (1) it is in NP and (2) every NP problem reduces to it in polynomial time; if any NP-complete problem is in P, then P = NP.
• NP-hard — at least as hard as the hardest NP problems; need not be in NP (may not be decidable); optimization versions of NP-complete problems are NP-hard.
• Classic NP-complete problems — Boolean satisfiability (SAT, Cook’s theorem 1971), 3-SAT, vertex cover, clique, independent set, subset sum, 0/1 knapsack, Hamiltonian cycle, graph coloring (k ≥ 3), traveling salesman (decision form).
• P vs NP — whether P = NP is the most famous open problem in computer science; a $1 million Millennium Prize Problem; most researchers believe P ≠ NP.
• PSPACE — problems solvable in polynomial space; PSPACE ⊇ NP; PSPACE-complete problems include TQBF.
• co-NP — complement class of NP; problems where “no” instances can be verified in polynomial time; graph non-isomorphism is in co-NP.
• EXP / EXPTIME — problems solvable in exponential time 2^{poly(n)}; strictly contains PSPACE by the time-hierarchy theorem; chess on an n×n board is EXPTIME-complete.
• #P (sharp-P) — counting complexity class; asks how many solutions exist (not just whether one exists); #P-hard problems include counting satisfying assignments to a 3-CNF formula; proved by Valiant (1979).
• Time-hierarchy theorem — more time strictly enlarges the class of solvable problems; proves P ≠ EXPTIME and similar separations; does NOT prove P ≠ NP.
• Oracle / relativization — a technique attaching a black-box oracle subroutine to a TM; Baker-Gill-Solovay (1975) showed there exist oracles A and B with P^A = NP^A and P^B ≠ NP^B; this means P vs NP cannot be resolved by relativizing proof techniques alone.
• Cook-Levin theorem — SAT (Boolean satisfiability) is NP-complete; proven independently by Stephen Cook (1971) and Leonid Levin; the first problem shown to be NP-complete; established the foundation for NP-completeness theory.
• SAT and 3-SAT — SAT asks whether a Boolean formula has a satisfying assignment; 3-SAT restricts to CNF clauses of exactly 3 literals; 3-SAT is NP-complete and serves as the standard starting point for NP-hardness reductions; 2-SAT is in P (solvable via SCCs).
• Polynomial-time reduction — transformation from problem A to problem B computable in polynomial time; if A reduces to B and B is in P, then A is in P; if A is NP-hard and reduces to B, then B is NP-hard; the mechanism of NP-completeness proofs.
• Space complexity classes — L (logspace, deterministic) and NL (nondeterministic logspace) sit below P; PSPACE contains NP and co-NP; EXPTIME contains PSPACE; hierarchy: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME.

Computability and Automata

• Turing machine — abstract model of computation: infinite tape, read/write head, state transitions; defines what is computable.
• Church-Turing thesis — any function computable by an algorithm can be computed by a Turing machine; a thesis, not a theorem.
• Halting problem — given a program and input, does it halt? Proven undecidable by Alan Turing (1936) via diagonalization; no algorithm can solve it for all inputs.
• Rice’s theorem — all non-trivial semantic properties of programs are undecidable; generalizes the halting problem.
• Decidable vs recognizable — a decidable language has a TM that always halts; a recognizable (recursively enumerable) language has a TM that halts on “yes” instances but may loop on “no.”
• Finite automaton (DFA/NFA) — models recognizing regular languages; DFA and NFA accept the same class (regular languages); both weaker than pushdown automata.
• Context-free grammar (CFG) — generates context-free languages (e.g., balanced parentheses); recognized by pushdown automata; relevant to parsing programming languages.
• Chomsky hierarchy — regular < context-free < context-sensitive < recursively enumerable; each class strictly contains the previous; Noam Chomsky formalized this (1956).
• Pushdown automaton (PDA) — finite automaton augmented with a stack; recognizes context-free languages; nondeterministic PDAs = deterministic PDAs in power (unlike finite automata).

• Regular expressions — formal notation for regular languages; operators: concatenation, union (

  ), Kleene star (*); every regex corresponds to an NFA by Thompson’s construction; used in text processing, compilers (lexical analysis).

• Pumping lemma — necessary condition for a language to be regular (or context-free); used to prove languages are NOT regular; for regular: if

  w

  ≥ pumping length p, then w can be split so that the middle part can be pumped (repeated) and stay in the language.

• Lambda calculus — formal system for expressing computation via function abstraction (λx.body) and application; Alonzo Church (1930s); equivalent in power to Turing machines (Church-Turing thesis); theoretical basis of functional programming; beta reduction is the computation rule.
• NFA (Nondeterministic Finite Automaton) — finite automaton that can be in multiple states simultaneously (or take epsilon transitions); accepts if any branch accepts; equivalent in expressive power to DFA; exponential blowup possible in determinization (subset construction).
• Undecidability examples — halting problem; Post correspondence problem; whether a CFG generates all strings; whether two CFGs are equivalent; whether a program has a bug (Rice’s theorem); all proven by reduction from the halting problem.
• Post correspondence problem (PCP) — undecidable problem: given tiles with two strings, does some sequence make both sides equal? Standard target for undecidability reductions; Emil Post (1946).
• Universal Turing machine — a TM that simulates any other TM given its description as input; the theoretical basis for stored-program computers; proves that a single machine can compute anything computable.
• Diagonalization — proof technique used by Turing (halting problem) and Cantor (uncountability of reals); construct an object that differs from every element of an enumerated list at the diagonal position; key tool in computability and complexity.
• Entscheidungsproblem — Hilbert’s “decision problem” asking for an algorithm to determine the truth of any mathematical statement; proven unsolvable by Church and Turing (1936), giving birth to computability theory.
• Context-sensitive language — Chomsky hierarchy level 2; recognized by linear bounded automata; more expressive than context-free; example: {aⁿbⁿcⁿ}.
• Kleene star — closure operation in formal language theory: L* = all finite concatenations of strings from L, including the empty string ε; fundamental in regular expressions and automata theory; Stephen Kleene (1956).

Programming Paradigms and Languages

• Imperative — step-by-step instructions changing program state; C, Pascal.
• Object-oriented (OOP) — organizes code around objects with encapsulation, inheritance, polymorphism; key languages: Java, C++, Python, C#.
• Functional — treats computation as evaluation of mathematical functions; avoids mutable state; first-class and higher-order functions; Haskell (purely functional), Lisp, Erlang, Clojure; functional features in Python, Scala, Kotlin.
• Declarative — describes what to compute, not how; SQL is the canonical example; Prolog (logic programming).
• Interpreted vs compiled — compiled languages (C, C++) translate to machine code ahead of time; interpreted languages (Python, Ruby) run via a runtime interpreter; JVM languages (Java, Kotlin) compile to bytecode, then JIT-compile.
• Static vs dynamic typing — static: types checked at compile time (Java, C, Rust); dynamic: types checked at runtime (Python, JavaScript, Ruby).
• Strong vs weak typing — strong typing prevents implicit type coercion (Python, Java); weak typing allows it (C, JavaScript).
• Garbage collection — automatic memory management; used in Java, Python, Go; GC algorithms: mark-and-sweep, reference counting, generational GC; contrasts with manual memory management (C/C++) and ownership systems (Rust).
• Pointer / reference — a variable holding a memory address; direct memory manipulation in C/C++; a source of bugs (null pointer, dangling pointer, buffer overflow).
• Pass by value vs pass by reference — pass by value copies the argument; pass by reference passes the memory address, allowing mutation.
• Lambda calculus in PL — anonymous functions (lambdas/closures) in modern languages derive from Church’s lambda calculus; closures capture their lexical environment; key to functional programming in Python, JavaScript, Haskell, Scala.
• Type systems — static typing: types checked at compile time, catches errors early (Java, C, Rust, Haskell); dynamic typing: types checked at runtime (Python, JavaScript, Ruby); gradual typing: optional type annotations (TypeScript, mypy for Python).
• Compiler pipeline — lexical analysis (tokenizing) → parsing (AST construction) → semantic analysis (type checking) → optimization → code generation; LLVM is a widely-used compiler infrastructure.
• Interpreter vs compiler — interpreters execute source directly (Python CPython, early BASIC); compilers translate to machine code or bytecode ahead of time; JIT (just-in-time) compilation compiles at runtime (JVM HotSpot, V8 JavaScript engine, PyPy).
• Garbage collection algorithms — mark-and-sweep: trace reachable objects, collect the rest; reference counting: count references, free at zero (problem: cycles; Python uses cycle detector); generational GC: most objects die young, promote long-lived objects to older generations (JVM, CPython).
• Call stack and stack frame — each function call pushes a frame containing local variables, parameters, and return address; stack grows downward on x86; stack overflow occurs when recursion is too deep; heap is used for dynamically allocated objects.
• Recursion vs iteration — recursion is cleaner for tree/graph traversal but uses O(depth) stack space; iterative solutions use explicit stacks; tail-call optimization (TCO) converts tail recursion to iteration; Scheme mandates TCO, Python explicitly does not.
• First-class functions and higher-order functions — in functional languages, functions are values that can be passed to/returned from other functions; map, filter, reduce (fold) are canonical higher-order functions.
• Logic programming — programs are logical clauses; computation is inference; Prolog is the canonical language; uses unification and backtracking search; applied in AI, natural language processing, constraint solving.
• Closure — a function that captures variables from its enclosing lexical scope; allows functions to be returned as values while retaining access to outer-scope bindings; central to functional programming and JavaScript.
• Currying — transforming a function of multiple arguments into a chain of single-argument functions; f(x, y) becomes f(x)(y); named after Haskell Curry; fundamental in Haskell and functional languages.
• Monad — design pattern in functional programming (especially Haskell) for chaining computations with context (e.g., handling failure, I/O, state) while maintaining purity; a monad must satisfy left-identity, right-identity, and associativity laws.
• Type inference — compiler/interpreter deduces types without explicit annotations; Hindley-Milner algorithm (ML, Haskell); distinct from dynamic typing, which checks types at runtime.
• Abstract syntax tree (AST) — tree representation of the syntactic structure of source code produced during parsing; nodes represent constructs (expressions, statements); used in compilers, linters, and code analysis tools.
• Memory management: stack vs heap — stack holds local variables and call frames (fast, automatic, fixed size per frame); heap holds dynamically allocated objects (flexible size, managed by GC or manual free); stack overflow from deep recursion; heap fragmentation from dynamic allocation.
• Ownership and borrowing (Rust) — Rust’s memory safety model: each value has exactly one owner; references (borrows) must not outlive the owner; prevents dangling pointers and data races without garbage collection; enforced at compile time by the borrow checker.
• Event loop — JavaScript’s concurrency model; single-threaded; I/O callbacks queued in the event loop while the call stack is empty; Node.js uses libuv for async I/O; microtask queue (Promises) drains before macrotasks (setTimeout).
• Concurrency vs parallelism — concurrency: multiple tasks make progress by interleaving (single core); parallelism: tasks execute simultaneously on multiple cores; Go’s goroutines are concurrent; SIMD/GPU kernels are parallel.
• Amdahl’s law — speedup from parallelizing a program is limited by the serial fraction s: Speedup ≤ 1/(s + (1-s)/p) where p is processor count; diminishing returns; Gene Amdahl (1967).

Key Languages (Brief)

• C — low-level, compiled, manual memory; basis for UNIX and most operating system kernels; Dennis Ritchie (Bell Labs, early 1970s).
• C++ — extends C with OOP and templates; Bjarne Stroustrup (1979).
• Java — “write once, run anywhere” via JVM bytecode; strong static typing, garbage collected; James Gosling (Sun, 1995).
• Python — dynamic, interpreted, emphasis on readability; Guido van Rossum (1991); dominant in data science, scripting, and ML.
• JavaScript — prototype-based, event-driven; the language of web browsers; Brendan Eich (Netscape, 10 days, 1995); Node.js brings it server-side.
• Rust — memory-safe without garbage collection via ownership/borrow checker; Mozilla Research (Graydon Hoare), 1.0 in 2015.
• Lisp — one of the oldest high-level languages (John McCarthy, 1958); homoiconicity (code is data); dialects include Common Lisp, Scheme, Clojure.

Operating Systems

• Process vs thread — a process is an independent execution environment with its own memory space; threads share memory within a process; lighter-weight context switching for threads.
• Scheduling — OS decides which process/thread runs on the CPU; algorithms: FCFS (first-come-first-served), SJF (shortest job first), round-robin (time slices), priority scheduling.
• Context switch — saving and restoring CPU state when switching between processes/threads; overhead degrades performance at high frequency.
• Virtual memory — abstraction giving each process its own address space; paging maps virtual to physical addresses via a page table; a TLB (translation lookaside buffer) caches recent translations.
• Page fault — a process accesses a page not in physical memory; OS loads it from disk; thrashing occurs when excessive page faults dominate CPU time.
• Deadlock — four necessary conditions (Coffman, 1971): mutual exclusion, hold-and-wait, no preemption, circular wait; prevention requires denying at least one condition; detection via resource-allocation graph; Dining Philosophers problem (Dijkstra) illustrates deadlock and starvation with five philosophers alternating eating/thinking.
• Dining Philosophers problem — five philosophers sit at a round table; each needs two forks to eat; naive solution deadlocks when all pick up left fork simultaneously; solutions include resource ordering, Chandy/Misra approach, or an arbitrator; classic concurrency textbook problem.
• Memory hierarchy and cache — registers → L1 cache → L2 cache → L3 cache → RAM → SSD/HDD; each level trades speed for size; cache hit serves data from fast cache; cache miss fetches from slower memory; cache coherence is the challenge in multi-core systems.
• Cache replacement policies — LRU (Least Recently Used): evict the item unused longest; LFU (Least Frequently Used); FIFO; LRU implemented efficiently with a doubly linked list + hash map.
• CPU scheduling — FCFS: simple, convoy effect; SJF (Shortest Job First): optimal average wait time, requires knowing burst times; Round Robin: time slices (quantum), good for interactive systems; Priority scheduling: can cause starvation (solved by aging).
• Thrashing — when a process spends more time swapping pages than executing; occurs when working set does not fit in RAM; addressed by working-set model or page-fault frequency control.
• Semaphore — synchronization primitive invented by Edsger Dijkstra; integer counter with atomic P (wait/down) and V (signal/up) operations; binary semaphore (0/1) = mutex; counting semaphore controls a pool of N resources; prevents race conditions and coordinates producer-consumer.
• Mutex (mutual exclusion lock) — only one thread holds the lock at a time; prevents race conditions on shared data; a thread that cannot acquire a mutex blocks (sleeps) until the holder releases it; distinct from a spinlock, which busy-waits.
• Race condition — output depends on the non-deterministic interleaving of concurrent operations; prevented by synchronization.
• Spinlock — busy-wait synchronization; thread loops checking a flag rather than sleeping; avoids context-switch overhead for very short critical sections; wastes CPU if the wait is long; common in OS kernel code.
• Condition variable — synchronization primitive used with a mutex; threads wait (sleep) until another thread signals a condition (e.g., pthread_cond_wait/signal); used in monitor-based concurrency; avoids busy-waiting.
• Monitor — high-level synchronization construct combining a mutex and one or more condition variables; ensures mutual exclusion automatically; Java’s synchronized keyword implements monitors; C. A. R. Hoare (1974).
• Livelock — two or more threads keep changing state in response to each other but make no progress; distinct from deadlock (where threads are blocked); example: two people in a hallway each stepping aside in the same direction.
• IPC (inter-process communication) — mechanisms for processes to exchange data: pipes, message queues, shared memory, sockets, semaphores, signals; shared memory is fastest (no kernel copy); pipes are simplest for parent-child processes.
• File system — organizes data on disk; UNIX uses an inode-based structure; ext4, NTFS, HFS+ are common; journaling file systems log changes before committing to prevent corruption.
• System call — interface between user programs and the OS kernel; transitions CPU from user mode to kernel mode; examples: read(), write(), fork(), exec().

Databases

• Relational database — data organized in tables (relations) with rows and columns; SQL is the query language; primary keys uniquely identify rows; foreign keys enforce referential integrity.
• ACID — properties of a reliable transaction: Atomicity (all-or-nothing), Consistency (data integrity invariants preserved), Isolation (concurrent transactions do not interfere), Durability (committed data persists).
• Normalization — process of eliminating redundancy; 1NF (atomic values), 2NF (no partial dependencies), 3NF (no transitive dependencies), BCNF (Boyce-Codd).
• Index — auxiliary data structure (typically B+ tree) speeding up lookups at the cost of write overhead and storage; a clustered index dictates physical row order.
• JOIN types — INNER JOIN (matching rows only), LEFT/RIGHT OUTER JOIN (all rows from one side), FULL OUTER JOIN, CROSS JOIN (Cartesian product).
• Transaction isolation levels — Read Uncommitted, Read Committed, Repeatable Read, Serializable; higher levels prevent more anomalies (dirty reads, non-repeatable reads, phantom reads) at the cost of concurrency.
• CAP theorem — a distributed data store can guarantee at most two of: Consistency, Availability, Partition tolerance; network partitions are unavoidable, so real systems choose between C and A.
• BASE — alternative to ACID for distributed/NoSQL: Basically Available, Soft state, Eventually consistent.
• NoSQL categories — key-value (Redis), document (MongoDB), column-family (Cassandra, HBase), graph (Neo4j); trade normalization and ACID for horizontal scalability.
• ORM (Object-Relational Mapper) — maps OOP objects to relational tables; examples: Hibernate (Java), SQLAlchemy (Python), ActiveRecord (Ruby).
• View (SQL) — virtual table defined by a SELECT query; stored query, not stored data; simplifies complex queries; materialized view physically stores the result for performance.
• Stored procedure — named, precompiled SQL routine stored in the database; reduces round trips; can accept parameters; common in enterprise databases; debated in modern architectures.
• Query optimization — RDBMS parses SQL into a query plan; the optimizer chooses join order, index use, and execution strategy using cost estimates; EXPLAIN shows the chosen plan.
• Sharding — horizontal partitioning of a database across multiple servers by a shard key (e.g., user ID); scales writes; complicates joins and transactions; used by large-scale web applications.
• Replication — copying data to multiple database replicas; primary-replica model: writes to primary, reads from replicas; improves read throughput and fault tolerance; introduces replication lag.
• Relational model and Codd — Edgar F. Codd (IBM) proposed the relational model in 1970 (“A Relational Model of Data for Large Shared Data Banks”); introduced relations (tables), keys, and relational algebra; Turing Award 1981; prior systems were hierarchical (IMS) or network-based.
• SQL — Structured Query Language; declarative language for relational databases; ANSI standard since 1986; DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE), DCL (GRANT, REVOKE); first implemented in IBM System R (1974).
• Two-phase commit (2PC) — distributed transaction protocol ensuring all-or-nothing commit across multiple nodes; Phase 1 (prepare): coordinator asks all participants to vote; Phase 2 (commit/abort): coordinator sends final decision; blocks on coordinator failure.
• Eventual consistency — distributed systems guarantee that if no new updates are made, all replicas will eventually converge; weaker than strong consistency but allows higher availability and partition tolerance; common in NoSQL (Cassandra, DynamoDB).
• CAP theorem proof / Brewer’s theorem — stated by Eric Brewer (2000), proved by Gilbert and Lynch (2002); in the presence of a network partition, a distributed system cannot be both consistent and available; modern systems acknowledge CP vs AP trade-offs.

Cryptography Fundamentals

• Symmetric encryption — the same key encrypts and decrypts; fast; key distribution is a challenge; AES (Advanced Encryption Standard) is the current standard (128/192/256-bit keys).
• Asymmetric (public-key) encryption — mathematically linked key pair: a public key encrypts, a private key decrypts; solves key distribution; examples: RSA (factoring hardness), Elliptic Curve Cryptography (ECC) (discrete log over elliptic curves).
• RSA — Rivest-Shamir-Adleman (1977); security rests on the difficulty of factoring the product of two large primes; key sizes typically 2048–4096 bits.
• Diffie-Hellman key exchange — allows two parties to establish a shared secret over a public channel without transmitting the secret; basis for TLS/SSL key agreement.
• Cryptographic hash function — maps arbitrary input to a fixed-length digest; properties: deterministic, fast to compute, preimage resistant, collision resistant; examples: SHA-256 (256-bit), SHA-3, MD5 (128-bit, broken).
• Digital signature — hash of a message encrypted with the sender’s private key; recipient verifies with public key; ensures authenticity and non-repudiation.
• TLS/SSL — Transport Layer Security; cryptographic protocol securing web (HTTPS) and other traffic; combines asymmetric exchange with symmetric session keys.
• Quantum threat — Shor’s algorithm (polynomial time on a quantum computer) would break RSA and ECC; post-quantum cryptography (lattice-based, etc.) is under active standardization (NIST).
• AES (Advanced Encryption Standard) — symmetric block cipher standardized by NIST (2001); replaced DES; key sizes 128, 192, or 256 bits; block size 128 bits; uses SubBytes, ShiftRows, MixColumns, AddRoundKey rounds; selected from the Rijndael cipher (Joan Daemen and Vincent Rijmen).
• Block cipher modes — AES alone encrypts a single 128-bit block; modes chain blocks: ECB (insecure, patterns visible), CBC (chained XOR), CTR (turns block cipher into stream cipher), GCM (authenticated encryption); CTR/GCM are preferred.
• Message authentication code (MAC) — keyed checksum ensuring integrity and authenticity; HMAC uses a cryptographic hash (e.g., HMAC-SHA256); distinct from a digital signature (which uses asymmetric keys).
• Elliptic curve cryptography (ECC) — public-key cryptography over elliptic curve groups; same security as RSA with much smaller keys (256-bit ECC ≈ 3072-bit RSA); used in TLS, Bitcoin (secp256k1); discrete logarithm problem over elliptic curves is the hard problem.
• Zero-knowledge proof — interactive protocol where a prover convinces a verifier they know a secret without revealing the secret; properties: completeness, soundness, zero-knowledge; modern SNARKs enable non-interactive variants; used in privacy-preserving cryptocurrencies (Zcash).
• verify: Diffie-Hellman security rests on the discrete logarithm problem, not integer factoring (which is RSA’s basis). Confirm the exact group (multiplicative group mod prime p) used in classical DH vs elliptic curve DH (ECDH).
• verify: AES-128 has not been practically broken; Biclique attacks reduce security to ~2^126 operations, which is still infeasible. Confirm whether AES-256 has any known-key distinguishing attacks.

Networking Basics

• OSI model — 7-layer reference model: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP model collapses to 4 layers.
• IP (Internet Protocol) — connectionless, best-effort delivery; IPv4 (32-bit addresses, ~4.3 billion), IPv6 (128-bit, effectively unlimited).
• TCP vs UDP — TCP provides reliable, ordered, connection-oriented delivery (three-way handshake: SYN, SYN-ACK, ACK); UDP is connectionless, unreliable, faster; used for DNS, streaming, gaming.
• DNS — Domain Name System; translates hostnames to IP addresses; hierarchical distributed database.
• HTTP/HTTPS — HyperText Transfer Protocol; stateless, application-layer; HTTPS adds TLS encryption.
• Router vs switch vs hub — hub broadcasts to all ports; switch learns MAC addresses and forwards frames to the correct port (Layer 2); router routes packets between networks using IP addresses (Layer 3).
• Subnet and CIDR — Classless Inter-Domain Routing partitions IP space with prefix notation (e.g., 192.168.1.0/24 = 256 addresses); subnetting divides a network into smaller blocks; NAT allows multiple hosts to share one public IP.
• Port and socket — IP address identifies a host; port (16-bit integer) identifies a process; a socket is a (IP, port) pair; well-known ports: HTTP 80, HTTPS 443, SSH 22, DNS 53, SMTP 25.
• Three-way TCP handshake — SYN (client → server), SYN-ACK (server → client), ACK (client → server); establishes sequence numbers and connection state; four-way FIN handshake tears down the connection.
• CDN (Content Delivery Network) — geographically distributed servers cache and serve static content close to users; reduces latency; examples: Cloudflare, Akamai, AWS CloudFront.
• Load balancer — distributes incoming requests across multiple backend servers; algorithms: round-robin, least connections, IP hash; Layer 4 (transport) vs Layer 7 (application/HTTP) balancers.

Key Figures and Turing Award Context

• Alan Turing — foundational theorist: Turing machine, computability, halting problem (1936); codebreaking at Bletchley Park; died 1954. The Turing Award is named for him but he never received it.
• John von Neumann — von Neumann architecture (CPU, memory, I/O bus, stored-program concept); also contributed to game theory and quantum mechanics.
• Edsger Dijkstra — shortest-path algorithm (1956), structured programming, semaphores, Dijkstra’s algorithm and the “GOTO statement considered harmful” letter; Turing Award 1972.
• Donald Knuth — The Art of Computer Programming series; developed TeX; Turing Award 1974; coined the term “literate programming.”
• John McCarthy — invented Lisp (1958); coined the term “artificial intelligence”; Turing Award 1971.
• Grace Hopper — pioneered compilers; developed COBOL; coined “debugging” after removing a literal moth from the Mark II computer (1947).
• Dennis Ritchie and Ken Thompson — created UNIX (1969) and the C programming language at Bell Labs; Turing Award 1983.
• Linus Torvalds — created the Linux kernel (1991) and Git (2005).
• Tim Berners-Lee — invented the World Wide Web (1989–1991) at CERN; proposed HTTP, HTML, and URLs.
• Claude Shannon — founder of information theory; A Mathematical Theory of Communication (1948); defined bit and entropy.
• Turing Award — highest honor in computer science, awarded annually by the ACM since 1966; first recipient was Alan Perlis.
• Niklaus Wirth — designed Pascal (1970), Modula-2, Oberon; Turing Award 1984; proposed “Wirth’s law” — software gets slower faster than hardware gets faster; championed structured programming.
• Tony Hoare — invented Quicksort (1959); designed Communicating Sequential Processes (CSP); Turing Award 1980; introduced the null reference and called it his “billion-dollar mistake.”
• Barbara Liskov — Liskov Substitution Principle (LSP): if S is a subtype of T, objects of type T may be replaced by objects of type S without altering program correctness; Turing Award 2008; designed CLU (first language with abstract data types as a linguistic construct).
• Leslie Lamport — distributed systems pioneer; Paxos consensus algorithm; logical clocks (“Time, Clocks, and the Ordering of Events in a Distributed System,” 1978); LaTeX document system; Turing Award 2013.
• John Backus — designed FORTRAN (1957), the first widely used high-level programming language; invented BNF (Backus-Naur Form) notation for grammars; Turing Award 1977; also proposed “function-level programming.”
• Peter Naur — formalized BNF with Backus; co-editor of the ALGOL 60 report; Turing Award 2005; his name appears in “Backus-Naur Form.”
• Marvin Minsky — co-founder of MIT AI Lab; Perceptrons book (with Papert) showed limits of single-layer networks; Turing Award 1969; built the first neural network simulator (SNARC, 1951).
• verify: Tony Hoare’s CSP (Communicating Sequential Processes) paper year — commonly cited as 1978. Confirm whether Hoare’s quicksort paper is correctly 1962 (Communications of the ACM) or 1959 (internal report).
• verify: Leslie Lamport’s Paxos algorithm was described in “The Part-Time Parliament” (1989/1998) — confirm the original submission year versus TOCS publication year, as the long delay is a well-known anecdote.