What two heuristic optimizations enable Union-Find to achieve near-constant amortized time complexity?

1. Path Compression during Find (flattening the tree by attaching visited nodes directly to the root). 2. Union by Rank/Size (attaching the shallower tree under the root of the deeper tree).

What balance condition defines an AVL tree?

For every node, the height difference between its left and right subtrees (the balance factor) is at most 1: Balance_Factor = Height(Left) - Height(Right) ∈ {-1, 0, 1}.

What advantage does a doubly linked list have over a singly linked list when deleting an arbitrary node given only a pointer to that node?

A doubly linked list allows O(1) deletion because node->prev and node->next are immediately accessible without traversing from the head.

What fundamental access discipline defines a Stack, and what are its primary operations and their time complexities?

Last-In, First-Out (LIFO); primary operations are push, pop, and peek, all executing in O(1) time.

What are the average-case and worst-case time complexities of searching, inserting, and deleting in a standard BST?

Average-case is O(log n) when the tree is reasonably balanced; worst-case is O(n) when elements are inserted in sorted order, forming a skewed degenerate tree (linked list).

How does level-order tree traversal work, and what auxiliary data structure does it use?

It visits nodes level by level from top to bottom and left to right (Breadth-First Search) using a Queue.

What is the load factor (α) of a hash table, and what action is triggered when it exceeds a threshold (typically 0.75)?

α = (number of stored keys) / (total number of buckets); exceeding the threshold triggers rehashing (allocating a larger array, typically 2x, and re-inserting all keys).

What is open addressing for hash collision resolution, and how do linear probing and quadratic probing differ?

All entries are stored directly in the array; linear probing searches the next adjacent slot (index + i), while quadratic probing uses quadratic offsets (index + c1*i + c2*i^2) to reduce primary clustering.

What access discipline defines a Queue, and what are its primary operations and their time complexities?

First-In, First-Out (FIFO); primary operations are enqueue and dequeue, both executing in O(1) time.

How do singly linked lists and dynamic arrays compare in terms of head insertion and random access time complexities?

Singly linked lists offer O(1) head insertion but O(n) random access; dynamic arrays offer O(1) random access but O(n) head insertion (due to shifting elements).

How does collision resolution by separate chaining work in a hash table?

Each hash bucket stores a pointer to a linked list (or balanced red-black tree) containing all key-value entries that hashed to the same bucket index.

What is the formal mathematical definition of Big-O notation, O(g(n))?

f(n) is O(g(n)) if there exist positive constants c and n0 such that 0 = n0 (asymptotic upper bound).

What is the time complexity of building a binary heap from an unsorted array of n elements using bottom-up heapify?

O(n) time (linear time, proven by the sum Σ [h / 2^h] which converges to a constant).

Define the Binary Search Tree (BST) invariant property.

For every node X, all values in X's left subtree are strictly less than X.val, and all values in X's right subtree are strictly greater than X.val.

Why is an in-order traversal of a Binary Search Tree particularly useful?

It visits and outputs all keys in strictly ascending sorted order in O(n) time.

In a 0-indexed array representation of a complete binary heap, what are the index formulas for a node's parent, left child, and right child?

Parent = ⌊(i - 1) / 2⌋; Left child = 2*i + 1; Right child = 2*i + 2.

What two operations define the Disjoint Set Union (Union-Find) data structure?

Find(x): determines the representative identifier of the set containing element x; Union(x, y): merges the two distinct sets containing x and y.

What is a Bloom filter, and what types of query outcomes can it produce?

A space-efficient probabilistic data structure using multiple hash functions over a bit array; it produces false positives (may say item is present when it isn't), but zero false negatives (never says item is absent if it was added).

What is a circular queue buffer, and what problem does it solve in array-based queue implementations?

A fixed-size array where the rear wraps around to the front using modulo arithmetic ((rear + 1) % capacity), preventing O(n) element shifting on dequeue.

What is the difference between Big-O, Big-Omega (Ω), and Big-Theta (Θ) notations?

Big-O denotes an asymptotic upper bound (worst-case ceiling); Big-Omega denotes an asymptotic lower bound (floor); Big-Theta denotes an asymptotically tight bound (both upper and lower).

What structural invariant defines a Min-Heap binary tree?

For every node X, the value of X is less than or equal to the values of its children (root holds the minimum element), and the tree is a complete binary tree.

What is the amortized time complexity of appending an element to a dynamic array that doubles its capacity upon filling?

Amortized O(1) time per append (doubling from capacity N requires O(N) copy, but occurs once every N appends).

What are the essential properties of an effective hash function in a hash table?

Deterministic (same key produces same hash), uniform distribution across buckets, fast computation (O(1)), and minimizing collisions.

What are the average-case and worst-case time complexities for lookup, insertion, and deletion in a hash table?

Average-case is O(1) time; worst-case is O(n) time when all keys collide into a single chain.

Rank the following standard time complexity classes from fastest to slowest growing: O(n!), O(n), O(1), O(n^2), O(log n), O(2^n), O(n log n).

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

What invariants guarantee that a Red-Black Tree maintains O(log n) search, insert, and delete operations?

1. Every node is red or black. 2. Root is black. 3. Red nodes cannot have red children (no two consecutive reds). 4. Every path from root to null leaves contains the exact same number of black nodes (black-height).

What tree rotation is performed to restore balance after an insertion causing a Left-Right (LR) imbalance in an AVL tree?

A double rotation: first a Left rotation on the left child, followed by a Right rotation on the unbalanced root.

What order of node processing characterizes pre-order, in-order, and post-order depth-first tree traversals?

Pre-order: Node -> Left -> Right; In-order: Left -> Node -> Right; Post-order: Left -> Right -> Node.

What is the amortized time complexity per operation in a Union-Find structure with path compression and union by rank?

O(α(n)), where α is the Inverse Ackermann function, which grows so slowly that α(n) < 5 for any practical n in the universe.

Why do static arrays support O(1) random access by index?

Elements are stored contiguously in memory, allowing direct memory address calculation via Address = Base_Address + Index * Element_Size.

What are the time complexities of pushing an element, popping the root, and peeking the root in a binary heap?

Push: O(log n) (heapify-up); Pop-min/max: O(log n) (heapify-down); Peek: O(1).

What is a Trie (prefix tree), and what is the time complexity of searching for a word of length L among N stored words?

A tree where each node represents a character along string paths; searching takes O(L) time, depending only on the word length L, independent of total words N.

Cryptography (Svenska) — Grundläggande (A1/A2) 2: Data Structures, Arrays, Hash Maps, Trees & Big-O Complexity

[Svenska] Cryptography (Svenska): Core data structures, time and space complexity, arrays, linked lists, hash tables, binary search trees, and heaps

Level: basic
Languages: sv → sv
Cards: 32
Markdown: Cryptography (Svenska) — Grundläggande (A1/A2) 2: Data Structures, Arrays, Hash Maps, Trees & Big-O Complexity (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	What two heuristic optimizations enable Union-Find to achieve near-constant amortized time complexity?	1. Path Compression during Find (flattening the tree by attaching visited nodes directly to the root). 2. Union by Rank/Size (attaching the shallower tree under the root of the deeper tree).
2	What balance condition defines an AVL tree?	For every node, the height difference between its left and right subtrees (the balance factor) is at most 1: Balance_Factor = Height(Left) - Height(Right) ∈ {-1, 0, 1}.
3	What advantage does a doubly linked list have over a singly linked list when deleting an arbitrary node given only a pointer to that node?	A doubly linked list allows O(1) deletion because node->prev and node->next are immediately accessible without traversing from the head.
4	What fundamental access discipline defines a Stack, and what are its primary operations and their time complexities?	Last-In, First-Out (LIFO); primary operations are push, pop, and peek, all executing in O(1) time.
5	What are the average-case and worst-case time complexities of searching, inserting, and deleting in a standard BST?	Average-case is O(log n) when the tree is reasonably balanced; worst-case is O(n) when elements are inserted in sorted order, forming a skewed degenerate tree (linked list).
6	How does level-order tree traversal work, and what auxiliary data structure does it use?	It visits nodes level by level from top to bottom and left to right (Breadth-First Search) using a Queue.
7	What is the load factor (α) of a hash table, and what action is triggered when it exceeds a threshold (typically 0.75)?	α = (number of stored keys) / (total number of buckets); exceeding the threshold triggers rehashing (allocating a larger array, typically 2x, and re-inserting all keys).
8	What is open addressing for hash collision resolution, and how do linear probing and quadratic probing differ?	All entries are stored directly in the array; linear probing searches the next adjacent slot (index + i), while quadratic probing uses quadratic offsets (index + c1i + c2i^2) to reduce primary clustering.
9	What access discipline defines a Queue, and what are its primary operations and their time complexities?	First-In, First-Out (FIFO); primary operations are enqueue and dequeue, both executing in O(1) time.
10	How do singly linked lists and dynamic arrays compare in terms of head insertion and random access time complexities?	Singly linked lists offer O(1) head insertion but O(n) random access; dynamic arrays offer O(1) random access but O(n) head insertion (due to shifting elements).
11	How does collision resolution by separate chaining work in a hash table?	Each hash bucket stores a pointer to a linked list (or balanced red-black tree) containing all key-value entries that hashed to the same bucket index.
12	What is the formal mathematical definition of Big-O notation, O(g(n))?	f(n) is O(g(n)) if there exist positive constants c and n0 such that 0 <= f(n) <= c * g(n) for all n >= n0 (asymptotic upper bound).
13	What is the time complexity of building a binary heap from an unsorted array of n elements using bottom-up heapify?	O(n) time (linear time, proven by the sum Σ [h / 2^h] which converges to a constant).
14	Define the Binary Search Tree (BST) invariant property.	For every node X, all values in X's left subtree are strictly less than X.val, and all values in X's right subtree are strictly greater than X.val.
15	Why is an in-order traversal of a Binary Search Tree particularly useful?	It visits and outputs all keys in strictly ascending sorted order in O(n) time.
16	In a 0-indexed array representation of a complete binary heap, what are the index formulas for a node's parent, left child, and right child?	Parent = ⌊(i - 1) / 2⌋; Left child = 2i + 1; Right child = 2i + 2.
17	What two operations define the Disjoint Set Union (Union-Find) data structure?	Find(x): determines the representative identifier of the set containing element x; Union(x, y): merges the two distinct sets containing x and y.
18	What is a Bloom filter, and what types of query outcomes can it produce?	A space-efficient probabilistic data structure using multiple hash functions over a bit array; it produces false positives (may say item is present when it isn't), but zero false negatives (never says item is absent if it was added).
19	What is a circular queue buffer, and what problem does it solve in array-based queue implementations?	A fixed-size array where the rear wraps around to the front using modulo arithmetic ((rear + 1) % capacity), preventing O(n) element shifting on dequeue.
20	What is the difference between Big-O, Big-Omega (Ω), and Big-Theta (Θ) notations?	Big-O denotes an asymptotic upper bound (worst-case ceiling); Big-Omega denotes an asymptotic lower bound (floor); Big-Theta denotes an asymptotically tight bound (both upper and lower).
21	What structural invariant defines a Min-Heap binary tree?	For every node X, the value of X is less than or equal to the values of its children (root holds the minimum element), and the tree is a complete binary tree.
22	What is the amortized time complexity of appending an element to a dynamic array that doubles its capacity upon filling?	Amortized O(1) time per append (doubling from capacity N requires O(N) copy, but occurs once every N appends).
23	What are the essential properties of an effective hash function in a hash table?	Deterministic (same key produces same hash), uniform distribution across buckets, fast computation (O(1)), and minimizing collisions.
24	What are the average-case and worst-case time complexities for lookup, insertion, and deletion in a hash table?	Average-case is O(1) time; worst-case is O(n) time when all keys collide into a single chain.
25	Rank the following standard time complexity classes from fastest to slowest growing: O(n!), O(n), O(1), O(n^2), O(log n), O(2^n), O(n log n).	O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).
26	What invariants guarantee that a Red-Black Tree maintains O(log n) search, insert, and delete operations?	1. Every node is red or black. 2. Root is black. 3. Red nodes cannot have red children (no two consecutive reds). 4. Every path from root to null leaves contains the exact same number of black nodes (black-height).
27	What tree rotation is performed to restore balance after an insertion causing a Left-Right (LR) imbalance in an AVL tree?	A double rotation: first a Left rotation on the left child, followed by a Right rotation on the unbalanced root.
28	What order of node processing characterizes pre-order, in-order, and post-order depth-first tree traversals?	Pre-order: Node -> Left -> Right; In-order: Left -> Node -> Right; Post-order: Left -> Right -> Node.
29	What is the amortized time complexity per operation in a Union-Find structure with path compression and union by rank?	O(α(n)), where α is the Inverse Ackermann function, which grows so slowly that α(n) < 5 for any practical n in the universe.
30	Why do static arrays support O(1) random access by index?	Elements are stored contiguously in memory, allowing direct memory address calculation via Address = Base_Address + Index * Element_Size.
31	What are the time complexities of pushing an element, popping the root, and peeking the root in a binary heap?	Push: O(log n) (heapify-up); Pop-min/max: O(log n) (heapify-down); Peek: O(1).
32	What is a Trie (prefix tree), and what is the time complexity of searching for a word of length L among N stored words?	A tree where each node represents a character along string paths; searching takes O(L) time, depending only on the word length L, independent of total words N.