1
Q
What is the instance of a problem?
A
- The input of an algorithm
2
Q
What is the difference between an abstract datatype and a data structure?
A
- An abstract datatype defines the behaivoud of a certain type
- Data structures implement abstract data types
3
Q
What is the Random Access Machine model?
A
- Models time complexity based on high-level primitive operations
- Running time = number of primitive operations executed
- Models computer as a CPU which can access any memory cell in 1 operation, and RAM
4
Q
What is amortised analysis and how is it different from average-case analysis?
A
- Averages time over a sequence of operations on a data structure
- Measures average cost per operation in the worst-case
- Doesn’t involve probability, unlike average-case analysis
5
Q
What are the 3 main methods of amortised analysis?
A
- Aggregate method: Average cost per operation
- Accounting method: Assign amortised cost to each operation
- Potential method: Overcharge some operations early to compensate later
6
Q
How can we do amortised analysis to a stack with push, pop and multipop?
A
- Each push/pop: O(1)
- Multi-pop worst case: Θ(n)
- Max number of pushes and pops = n -> total cost Θ(n)
- Amortised cost per operation = Θ(n)/n = Θ(1)
7
Q
How does amortised analysis apply to dynamic tables (resizing arrays)?
A
- Push/pop into table Θ(1)
- Table resizes when full: moving all items is worst case Θ(n)
- Resizing is rare-> total cost Θ(n) over n inserts
- Amortised cost per insert: Θ(n)/n = Θ(1)
8
Q
What are the key properties and time complexities of linked lists?
A
- Consist of nodes, each with a next pointer
- Insert: O(n)
- Remove from tail: O(n)
- Search: O(n)
- No indexing, so list bust be traversed sequentially
9
Q
What is a hash map?
A
- Maps a key to an integer index using a hash function
- This enables fast insert, search and delete
10
Q
How do we keep our hash table as efficient as possible?
A
- Try and achieve uniform hashing- make each key equally likely to map to any slot
- This reduces collisions
- Using prime table size reduces clustering
11
Q
Why are polynomial hash functions better than linear?
A
- Convert sequences into integers
- Takes order into account of hash value and avoids symmetry
12
Q
What is open addressing in hash maps and what are the 3 main strategies?
A
- A collision resolution method so each bucket holds only one item and collisions are resolved by probing for another slot
- Linear probing: hash(k)+i -> creates clusters
- Quadratic probing: hash(k)+i^2 -> reduces clustering
- Double hashing: hash(k)+i*hash2(k) -> best distribution
13
Q
What is load factor and what does it indicate?
A
- Load factor = no. of objects/ table capacity
- Measures how full the hash table is
14
Q
What is the average and worst-case time complexities of hash maps?
What are we assuming as well?
A
- Average: Insert/find/remove = O(1)
- Worst case: Insert/find/remove = O(n)
- Assuming uniform hashing and LF < 1
15
Q
What is rehashing and what is its amortised cost?
A
- When load factor of a hash table reaches a threshold, create a larger table and reinsert elements
- Rehashing is expensive Θ(n) but rare so the cost is amortised and becomes Θ(n)/n = Θ(1)
16
Q
What are the 5 types of tree and explain them all
A
- Binary tree: all nodes have at most 2 children
- General tree: at least 1 node has more than 2 children
- Proper binary tree: each node has 0 or 2 children
- Complete binary tree: all levels are full except last level where all nodes are to the left
- Perfect binary tree: tree is proper and all external nodes are same depth
17
Q
Compare and explain array and linked representations of binary trees
A
- Array representations flatten a tree but waste a lot of space in memory and are hard to traverse
- Linked representations are better: each node contains Element, Parent, Left child, Right child
18
Q
Name and explain each type of tree traversal
A
- Pre-order: current node, left subtree, right subtree
- In-order: left subtree, current node, right subtree
- Post-order: left subtree, right subtree, current node
19
Q
What are the 2 main types of tree search and how is each implemented?
A
- Depth first: Explores one branch as deep as possible then backtracks- implemented using stack
- Breadth first: Explores all nodes at one level before moving to the next level- implemented using queue
20
Q
What is a binary search tree?
A
- For every node, the left child is smaller and the right child is larger
- Only one of each element
- Allows efficient search
- Inorder traversal outputs elements in ascending order
21
Q
Explain the uniform and non-uniform time complexities of BST operations
A
- Uniform: Insert/delete/find = O(logn)
- Non-uniform/skewed: Insert/delete/find = O(n)
22
Q
What is an AVL tree and what are its properties?
A
- AVL trees are special types of binary search trees that balance themselves
- The difference between the heights of the left and right trees should be <=1
- Keeps height at O(logn)
- Keeps search at O(logn)
- Building is O(nlogn)
23
Q
What is a balance factor in an AVL tree?
A
- Balance factor = height(left) - height(right)
- Valid balance factors = -1, 0, 1
- If balance becomes +-2, rotation is required
24
Q
Explain left and right rotations of AVL trees
A
- Right rotation: Left heavy (2), left child->up, root->right
- Left rotation: Right heavy (-2), right child->up, root->left
25
Name and explain the 2 types of double rotation of AVL trees
- **Left-right rotation** (Balance=2, left child balance=-1): Left rotation on left child, then right rotation on node
- **Right-left rotation** (Balance=-2, right child balance=1): Right rotation of right child, then left rotation on node
26
What is a priority queue?
- An abstract data type that stores items with their **priorities**
- Item with highest priority is **removed first** regardless of insertion order
27
What are the basic operations and their complexities for a simple priority queue?
- **Peek max** or **remove max**: O(1) with correct implementation
- **Insert**: O(n)
28
What is the difference between ordered and unordered priority queues?
- Unordered: easy insertion and expensive removal
- Ordered: easy removal and expensive insertion
29
What is a binary heap?
- Data structure that implements **priority queues**
- Complete binary heap that satisfies max heap property: **node <= parent**
30
How is a binary heap stored in an array?
- Parent at index: i/2
- Left child at index: 2i
- Right child at index: 2i+1
31
How is the max-heap property of a Binary heap maintained after insertion?
- Bubble-up
1. Compare element with parent
2. If greater, swap with parent
3. Repeat until parent is larger or root is reached
| Complexity: O(logn)
32
How is the maximum element removed in a binary heap?
- Remove the root
- Move the last element to the root
- Use bubble down to restore heap property
| O(logn)
33
What is a skip list and how is it structured?
- Layered linked list designed to speed up insertion, deletion and search- upper levels can skip nodes
- Bottom level: normal ordered linked list
- Upper level: subsets of nodes from lower levels
- Sentiel nodes: +-infinity for boundary handling
34
How is a skip list searched?
- Move right while the next nodes key<=target
- If next node > target, drop down one level
- Repeat until bottom
35
What is a disjoint set data structure and what are its benefits?
- Partions elements into **non-overlapping sets**
- Supports **dynamic** grouping and regrouping
- Used to track **connectivity** between components
36
What operations are in a disjoint set?
- **Add(x)**: create a new set belonging to x
- **Find(x)**: identify which set x belongs to
- **Union(x,y)**: merge the sets containing x and y
37
How does the array-based disjoint set implementation work?
| And what are the runtimes of operations
- Index=element, value=set identifier
- **Add and find**: O(1) (direct indexing)
- **Union**: O(n) (must scan entire array)
## Footnote
- Only suitable when unions are rare as they are expensive
38
What are linked list disjoint sets and why are they better than arrays?
- Each set is a linked list with head node that represents the set
- **Add and find**: O(n) (due to head node)
- Union requires **repointing** of head node
39
Why is union amortised to O(logn) in linked-list disjoint sets?
- At most **n-1** union operators, and union **doubles size** of smaller set
- Pointer can only change logn times so amortised cost **O(nlogn)/O(n) = O(logn)**
40
Why is a BST-based disjoint set inefficient for unions?
- Elements stored in a **balanced** BST with set identifiers
- **Find and add**: O(logn)
- **Union**: O(n) (requires updating all elements of one set)
41
How does rooted tree implementation of disjoint sets work?
| Include runtimes
- Each disjoint set is a rooted tree so each node points to its parent and the node stores the size
- **Add**: O(1)
- **Find**: O(n) (requires checking whole chain)
- **Union**: O(n) (finds the root of both elements then does constant-time redirection)
42
How and why do we need to limit size when using rooted tree disjoint sets?
- Trees can become very tall during unions so O(n) becomes very slow
- **Path compression**: Every node redirected to point to root
- **Path splitting**: Each node redirected to point to its grandparent
- **Path halving**: Every second node redirected to its grandparent
43
What is union by size in path compression of rooted tree disjoint sets and how does it affect union time?
- Means always the smaller tree pointing to larger tree during union
- N add operations + M find and unions = **O(N + Mα(N))**
- α(N) is the **inverse Ackermann function**- grows quickly and always **less than 4** (find and union are essentially constant)
44
What are the main types of computational problems?
- **Decision problems**: yes/no feasability problems
- **Function problems**: compute a single specific output
- **Search problems**: find one or more valid solutions
- **Counting problems**: count how many solutions exist
- **Optimisation problems**: find the best solution under a criterion
45
What are the two main ways to approach computational problems?
- **Problem decomposition view**: break problem into smaller subproblems, solve recursively then combine results
- **Solution space view**: explore all possible solutions and is often represented as a search tree
46
What is brute-force (enumerative) search and what are its trade-offs?
- Systematically **generates all possible solutions** and checks each for validity
- **Guarantees correctness** if a solution exists
- Can be **extremely inefficient** due to large solution spaces
47
How are solution space problems represented and explored?
- **Nodes**: partial solutions
- **Edges**: choices extending the solution
- **Leaves**: complete solutions
48
Why and how is pruning used in search problems?
- Avoids exploring branches that cannot lead to useful solutions
- Reduces unecessary computation
- Does **not** affect correctness
49
How do backtracking and branch-and-bound differ?
- **Backtracking**: used for decision and search problems- prunes when a partial solution is guaranteed invalid
- **Branch-and-bound**: used for optimisation problems- keeps best solution and prunes branches that are worse
50
What is a greedy algorithm and when is it correct?
- Builds solution step-by-step using locally best choice
- Decisions are **never undone**
- Correct only if **local optimality implies global optimality**
51
What is the exchange argument in greedy algorithms?
- Assume a better solution exists than the greedy one
- **Swap** parts of the solution with greedy choices
- If the solution is **not worse after swapping**, greedy solution is optimal
52
Year 2
flashcards
Decks in class (7)
# Cards
