# Cryptography (Svenska) — Medelnivå (B1/B2) 2: Algorithms, Sorting, Graph Traversal, Dynamic Programming & SQL/Databases

> [Svenska] Cryptography (Svenska): Sorting algorithms, BFS/DFS, shortest path, dynamic programming memoization, relational modeling, indexes, and ACID transactions

- **Canonical URL:** https://flashcards.world/flashcards/sets/69806c1d-52fe-4a91-b760-319a487ec30e/
- **Markdown URL:** https://flashcards.world/flashcards/sets/69806c1d-52fe-4a91-b760-319a487ec30e.md
- **Level:** intermediate
- **Languages:** sv → sv
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | What is a 'Phantom Read' anomaly, and which ANSI SQL isolation level prevents it? | When a transaction repeats a range query and discovers new rows inserted by another committed transaction; prevented by Serializable isolation level. |  |  |
| 2 | What algorithmic traversal does Breadth-First Search (BFS) perform, and why is it guaranteed to find the shortest path on unweighted graphs? | BFS uses a Queue to explore vertices in increasing order of distance (layer by layer); the first time an unweighted target is reached, it is via the minimum number of edges. |  |  |
| 3 | How do Kruskal's algorithm and Prim's algorithm differ in their greedy strategies for finding a Minimum Spanning Tree (MST)? | Kruskal's sorts all edges globally and adds the lightest edge that does not form a cycle (using Union-Find); Prim's grows a single connected tree outward by greedily adding the cheapest edge to an unvisited vertex. |  |  |
| 4 | What is the difference between an INNER JOIN and a LEFT OUTER JOIN in SQL? | INNER JOIN returns only rows with matching keys in both tables; LEFT OUTER JOIN returns all rows from the left table, with NULLs for unmatched columns from the right table. |  |  |
| 5 | Why is Heap Sort an attractive in-place sorting algorithm compared to standard Quick Sort and Merge Sort? | Heap Sort guarantees O(n log n) time in all cases (worst, average, and best) while using only O(1) auxiliary space (in-place). |  |  |
| 6 | What data structure or mechanism powers Depth-First Search (DFS), and how can DFS detect cycles in a directed graph? | DFS uses a Stack (or function call recursion); a cycle is detected if DFS encounters an ancestor vertex currently marked as active on the recursion call stack (a back-edge). |  |  |
| 7 | What is Dijkstra's algorithm, and why does it fail on graphs with negative edge weights? | A greedy algorithm finding shortest paths from a single source on non-negative weighted graphs using a min-priority queue (O((V+E)log V)); fails with negative weights because once a vertex is marked visited, it assumes its distance cannot decrease. |  |  |
| 8 | How does top-down Dynamic Programming (memoization) differ from bottom-up Dynamic Programming (tabulation)? | Top-down uses recursion and stores results in a memo lookup table on demand; bottom-up solves smallest subproblems iteratively in topological order, filling a DP table without call stack overhead. |  |  |
| 9 | Why are B+ trees preferred over standard binary search trees or hash tables for relational database indexes? | High fan-out yields shallow height minimizing disk I/O; leaf nodes are linked sequentially in a linked list, enabling highly efficient range scans (e.g., BETWEEN x AND y). |  |  |
| 10 | In relational database design, what is the purpose of a primary key and a foreign key? | A primary key uniquely identifies each row in a table (non-null and unique); a foreign key references a primary key in another table to enforce referential integrity. |  |  |
| 11 | What is the recurrence relation and time complexity for the 0/1 Knapsack problem with N items and capacity W? | DP[i][w] = max(DP[i-1][w], DP[i-1][w - wt[i]] + val[i]); time complexity is O(N * W), which is pseudo-polynomial. |  |  |
| 12 | What is a 'Non-Repeatable Read' anomaly, and which ANSI SQL isolation level prevents it? | When a transaction re-reads a row and finds modified or deleted values because another transaction committed changes in between; prevented by Repeatable Read. |  |  |
| 13 | What causes Quick Sort to degrade to its worst-case O(n^2) performance, and how can this be mitigated? | Degrades when the chosen pivot is consistently the minimum or maximum element (e.g., sorted array with first/last element pivot); mitigated by randomized pivot selection or median-of-three. |  |  |
| 14 | What is Two-Phase Locking (2PL), and what concurrency property does it guarantee? | A concurrency control protocol where transactions acquire all locks during an expanding growing phase and release locks during a shrinking phase; guarantees serializability. |  |  |
| 15 | What two fundamental characteristics must an optimization problem possess to be solvable via Dynamic Programming? | 1. Optimal Substructure (an optimal global solution contains optimal solutions to subproblems). 2. Overlapping Subproblems (the same subproblems are solved repeatedly). |  |  |
| 16 | How does Insertion Sort work, and under what specific data condition does it achieve O(n) linear performance? | It iteratively places each unsorted element into its proper position within a sorted sub-array; it achieves O(n) time on nearly sorted or small datasets. |  |  |
| 17 | What algorithmic paradigm does Merge Sort use, and what are its time and auxiliary space complexities? | Divide and conquer (recursive halving followed by sorted merging); time complexity is O(n log n) in all cases; auxiliary space complexity is O(n). |  |  |
| 18 | What is a Topological Sort of a Directed Acyclic Graph (DAG), and what is Kahn's algorithm for finding it? | A linear ordering of vertices such that for every directed edge u -> v, u comes before v; Kahn's algorithm repeatedly removes vertices with in-degree 0 using a queue. |  |  |
| 19 | How does a greedy algorithm differ fundamentally from dynamic programming? | Greedy algorithms make the locally optimal choice at each step without ever reconsidering past choices; DP solves all subproblems and compares combinations to guarantee global optimality. |  |  |
| 20 | What is a 'Dirty Read' anomaly, and which ANSI SQL isolation level prevents it? | When a transaction reads uncommitted data written by another concurrent transaction that is later rolled back; prevented by Read Committed isolation level. |  |  |
| 21 | How does the SQL WHERE clause differ from the HAVING clause? | WHERE filters individual table rows before grouping occurs; HAVING filters aggregated groups after GROUP BY evaluation. |  |  |
| 22 | What is the recurrence relation for finding the Longest Common Subsequence (LCS) of two strings S1 of length m and S2 of length n? | If S1[i] == S2[j]: DP[i][j] = 1 + DP[i-1][j-1]; else: DP[i][j] = max(DP[i-1][j], DP[i][j-1]); runs in O(m * n) time and space. |  |  |
| 23 | What is the difference between a clustered index and a non-clustered index in a relational database? | A clustered index defines the physical on-disk storage order of the actual table rows (only one per table); a non-clustered index is a separate index structure storing row pointers. |  |  |
| 24 | What mechanism ensures transaction Durability in database engines such as PostgreSQL or SQLite? | Write-Ahead Logging (WAL): data changes are synchronously written to an append-only log file on persistent storage before being written to actual database pages. |  |  |
| 25 | What are the requirements for First, Second, and Third Normal Forms (1NF, 2NF, 3NF)? | 1NF: Atomic column values and unique rows; 2NF: 1NF + no partial functional dependencies on composite primary keys; 3NF: 2NF + no transitive dependencies (non-key attributes dependent only on primary key). |  |  |
| 26 | What does it mean for a sorting algorithm to be 'stable', and which of Merge Sort and Quick Sort is stable? | A sorting algorithm is stable if it preserves the relative original order of elements with equal keys; standard Merge Sort is stable, whereas standard Quick Sort is unstable. |  |  |
| 27 | How do Counting Sort and Radix Sort achieve O(n) linear time complexity without violating the O(n log n) comparison sorting lower bound? | They are non-comparison sorting algorithms that exploit integer key properties and digit positions rather than pairwise comparisons. |  |  |
| 28 | What is the logical order of operations in SQL query execution? | 1. FROM (and JOINs) -> 2. WHERE -> 3. GROUP BY -> 4. HAVING -> 5. SELECT -> 6. DISTINCT -> 7. ORDER BY -> 8. LIMIT / OFFSET. |  |  |
| 29 | What precondition must be met to apply Binary Search, and what is its time complexity? | The input collection must be sorted in monotonic order with O(1) random indexing; time complexity is O(log n). |  |  |
| 30 | Which shortest path algorithm correctly handles negative edge weights and detects negative weight cycles? | The Bellman-Ford algorithm, which relaxes all \|E\| edges (\|V\| - 1) times in O(V * E) time. |  |  |
| 31 | Compare Adjacency Matrices and Adjacency Lists in terms of memory consumption and edge existence lookup for a graph G = (V, E). | Adjacency Matrix uses O(V^2) memory and O(1) edge lookup; Adjacency List uses O(V + E) memory and O(degree(u)) edge lookup. |  |  |
| 32 | Define each component of the ACID transaction properties in database management systems. | Atomicity (all operations succeed or all roll back); Consistency (transitions preserve all schema constraints); Isolation (concurrent transactions execute independently without interference); Durability (committed changes survive system crashes). |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/69806c1d-52fe-4a91-b760-319a487ec30e/).