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.

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.

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.

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.

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).

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).

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.

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.

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).

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.

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.

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.

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.

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.

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).

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.

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).

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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

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.

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).

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.

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.

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).

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

Level: intermediate
Languages: sv → sv
Cards: 32
Markdown: Cryptography (Svenska) — Medelnivå (B1/B2) 2: Algorithms, Sorting, Graph Traversal, Dynamic Programming & SQL/Databases (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
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).