# Algorithms, Graphs, Dynamic Programming & Relational Databases

> Algorithmic and database foundations for machine learning: 32 review cards on sorting, graph search (BFS/DFS, Dijkstra, A*), dynamic programming, relational data modeling, B-tree/hash indexes, and ACID transactions.

- **Canonical URL:** https://flashcards.world/flashcards/sets/c1222f27-fee2-480b-aee4-35ce002e6ad2/
- **Markdown URL:** https://flashcards.world/flashcards/sets/c1222f27-fee2-480b-aee4-35ce002e6ad2.md
- **Level:** intermediate
- **Languages:** en → en
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | What do the ACID transaction properties mean? | Atomicity: all-or-nothing effects. Consistency: correct transactions preserve constraints and application invariants. Isolation: concurrent behavior obeys the chosen isolation level. Durability: committed effects survive failures covered by the database’s configured guarantees. |  |  |
| 2 | Why is dynamic programming useful for many optimization problems? | Optimal substructure lets an optimum be expressed through subproblem optima. When subproblems overlap, storing their answers avoids repeated work. The state definitions and recurrence must correctly represent the original problem. |  |  |
| 3 | Why can quicksort take Θ(n²) time, and how does randomization help? | Repeated highly unbalanced partitions, such as choosing the smallest distinct key each time, cause quadratic work. With distinct keys or suitable duplicate handling, random pivots give expected O(n log n) time. Median-of-three is a useful heuristic, not a worst-case guarantee. |  |  |
| 4 | How does insertion sort work, and what determines its time on nearly sorted input? | It inserts each item into a sorted prefix. The usual adjacent-shift or adjacent-swap version takes Θ(n+I) time, where I is the number of inversions. It is linear when I=O(n); small input alone does not change the worst-case Θ(n²) bound. |  |  |
| 5 | How do Kruskal’s and Prim’s algorithms construct a minimum spanning tree? | For a connected undirected weighted graph, Kruskal considers edges in increasing weight and uses Union–Find to reject cycles. Prim grows one tree by repeatedly choosing a minimum-weight edge crossing from the tree to a vertex outside it. |  |  |
| 6 | What is the dynamic-programming recurrence for LCS length? | Let L[i,j] be the LCS length of prefixes of lengths i,j. Set L[0,j]=L[i,0]=0. If the last characters match, L[i,j]=1+L[i−1,j−1]; otherwise L[i,j]=max(L[i−1,j],L[i,j−1]). The full table uses O(mn) time and space. |  |  |
| 7 | What is the standard 0/1 knapsack recurrence for integer capacity W? | Let D[i,w] be the best value using the first i items with capacity w, with positive integer weights wᵢ. Set D[0,w]=0. If wᵢ>w, copy D[i−1,w]; otherwise take max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Time O(NW) is pseudo-polynomial. |  |  |
| 8 | How do WHERE and HAVING differ in a grouped query? | WHERE filters input rows before grouping. HAVING filters the resulting groups and can use aggregate conditions, such as COUNT(*)>1. |  |  |
| 9 | How do INNER JOIN and LEFT JOIN differ? | INNER JOIN returns row combinations satisfying the join condition. LEFT JOIN also retains each unmatched left row, supplying NULLs for right-side columns. Multiple matching right rows can produce multiple output rows for one left row. |  |  |
| 10 | What are the worst-case time and extra-space bounds of in-place heapsort? | Building a heap takes O(n), followed by O(n log n) total extraction work. With iterative sift-down in the input array, heapsort takes O(n log n) worst-case time and O(1) extra space. |  |  |
| 11 | How do clustered and nonclustered rowstore indexes differ in SQL Server? | A clustered index stores table rows in key order, so a table has at most one. A nonclustered index has its own keys and row locators, and may include other columns. These terms and storage details vary across database systems. |  |  |
| 12 | Why are B+ trees useful for database indexes and range queries? | Their high fan-out keeps trees shallow, reducing page accesses. Ordered keys and linked leaves support range scans. Hash indexes target equality lookups and do not inherently provide the same ordered range access. |  |  |
| 13 | How do memoization and bottom-up dynamic programming differ? | Memoization evaluates subproblems on demand, usually recursively, and caches results. Bottom-up DP evaluates states in an order where their dependencies are already available, usually filling a table. |  |  |
| 14 | How do an adjacency matrix and ordinary adjacency lists compare? | For V vertices and E edges, a matrix uses O(V²) space and tests an edge in O(1). Lists use O(V+E) space; searching an unsorted list for edge (u,v) takes O(deg(u)), where deg(u) is that list’s length. |  |  |
| 15 | How does standard array merge sort work, and what are its time and space bounds? | It recursively sorts two halves and merges them in linear time. The standard version takes Θ(n log n) time and O(n) auxiliary space, assuming constant-time comparisons. |  |  |
| 16 | What do first, second and third normal form require? | 1NF: atomic attribute values. 2NF: 1NF and no non-prime attribute depends on a proper part of any candidate key. 3NF: 1NF and every nontrivial dependency X→A has X a superkey or A prime. A prime attribute belongs to some candidate key. |  |  |
| 17 | When can counting sort or radix sort run in linear time? | Counting sort costs O(n+k) for n keys in a range of k values. Radix sort with d stable digit passes and radix b costs O(d(n+b)). They are linear only when these parameters permit it; they use key structure beyond comparisons. |  |  |
| 18 | How can depth-first search detect a cycle in a directed graph? | DFS explores deeply using recursion or an explicit stack. An edge to a vertex still active on the current DFS path is a back edge and proves a directed cycle; an edge to any previously visited vertex is not enough. |  |  |
| 19 | What is a dirty read, and which standard isolation level first prevents it? | Reading another transaction’s uncommitted data, whether or not that transaction later rolls back. READ COMMITTED and stronger standard isolation levels prohibit dirty reads. |  |  |
| 20 | How does Bellman–Ford handle negative edges and detect a reachable negative cycle? | Relax all edges up to V−1 times. A further improvement from a reachable vertex reveals a negative cycle reachable from the source. Worst-case time is O(VE); vertices reachable from such a cycle have no finite shortest-path cost. |  |  |
| 21 | How does PostgreSQL WAL support durability under normal synchronous commit? | Relevant log records reach durable storage before commit is acknowledged and before changed data pages are written. After a crash, WAL can replay changes missing from data pages. Asynchronous commit can lose recent acknowledged transactions. |  |  |
| 22 | How does a greedy algorithm differ from dynamic programming? | Greedy commits to a local choice and needs a proof that such choices preserve an optimum. DP compares alternatives through a recurrence and reuses subproblem results. A global optimum requires a correct model and recurrence, not merely the label “DP”. |  |  |
| 23 | How does breadth-first search find shortest paths in an unweighted graph? | BFS uses a FIFO queue and explores vertices by distance in edges. Marking a vertex when enqueued avoids repeated visits. Its first discovered path to a reachable vertex has the minimum number of edges. |  |  |
| 24 | What are the two phases of two-phase locking (2PL)? | Growing: acquire locks without releasing them. Shrinking: release locks without acquiring new ones. With appropriate conflicting read/write locks, 2PL guarantees conflict-serializable schedules, but deadlocks remain possible. |  |  |
| 25 | What is a phantom read, and how is it prevented? | Repeating a predicate query finds a different matching row set after another transaction commits changes. SERIALIZABLE prevents phantoms in the standard model; some implementations, including PostgreSQL REPEATABLE READ, also prevent them at a lower level. |  |  |
| 26 | What is a simplified logical processing order for a SQL SELECT query? | For a query without CTEs, window functions or set operations: FROM/JOIN → WHERE → GROUP BY and aggregates → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. This is a logical model, not necessarily the optimizer’s physical execution order. |  |  |
| 27 | What is a topological order, and how does Kahn’s algorithm find one? | In a DAG, every edge u→v places u before v. Repeatedly output a zero-indegree vertex and remove its outgoing edges, enqueueing new zero-indegree vertices. If fewer than V vertices are output, the directed graph has a cycle. |  |  |
| 28 | What is a nonrepeatable read, and which standard isolation level prevents it? | Rereading a row yields changed data, or the row disappears, after another transaction commits an update or deletion. REPEATABLE READ and SERIALIZABLE prohibit this anomaly. |  |  |
| 29 | What does binary search require, and when does it run in O(log n) time? | It repeatedly halves a search interval in data sorted under the comparison order. On an array with O(1) indexed access and constant-time comparisons, searching n elements takes O(log n) time. |  |  |
| 30 | What makes a sorting algorithm stable? | Equal-key items keep their original relative order. Merge sort can be stable by taking the left item first on ties; standard in-place quicksort is generally unstable. Stability depends on the implementation. |  |  |
| 31 | How do primary keys and foreign keys differ in PostgreSQL? | A primary key identifies rows with unique, non-NULL values. A foreign key requires matching referenced key values, subject to its NULL rules. It may reference an eligible UNIQUE key or primary key in the same or another table. |  |  |
| 32 | When is Dijkstra’s algorithm valid, and what is a usual heap-based bound? | With nonnegative edge weights, it repeatedly settles the vertex with least tentative distance. An adjacency-list implementation with a binary min-heap takes O((V+E) log V). Negative edges can invalidate the settled-distance argument. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/c1222f27-fee2-480b-aee4-35ce002e6ad2/).