Class Notes
### **Unit 1 – Hashing**
**Q1. What is hashing? Explain with an example.**
**A:** Hashing is a technique to map data (keys) to fixed-size indices in a hash table
using a hash function.
**Example:** Storing student records where `roll_no % 10` generates an index (e.g., roll
number `25` maps to index `5`).
**Q2. What is collision? How is it resolved?**
**A:** Collision occurs when two keys hash to the same index. Resolved via:
- **Chaining:** Store collided keys in a linked list at the index.
- **Open Addressing:** Probe for next empty slot (linear/quadratic probing).
**Q3. What is rehashing? Why is it needed?**
**A:** Rehashing resizes the hash table (e.g., doubling its size) to reduce collisions
when the load factor (α) exceeds 0.7.
2
**Q4. Compare static vs. dynamic hashing.**
**A:**
- **Static:** Fixed table size. Requires rehashing for expansion.
- **Dynamic:** Adjusts table size automatically (e.g., extendible hashing).
---
### **Unit 2 – Trees**
**Q1. Explain tree traversals with examples.**
**A:**
- **Inorder (LNR):** Left → Root → Right. Outputs sorted order in
BST.
- **Preorder (NLR):** Root → Left → Right. Used to copy trees.
- **Postorder (LRN):** Left → Right → Root. Used to delete trees.
**Q2. How do you delete a node with two children in a BST?**
**A:** Replace the node with its **inorder successor** (smallest node in the right
subtree) and delete the successor.
**Q3. What is a threaded BST?**
**A:** A BST where null pointers are replaced with threads (pointers to inorder
predecessor/successor) to allow traversal without recursion/stack.
---
3
### **Unit 3 – Graphs**
**Q1. Compare adjacency matrix and adjacency list.**
**A:**
| **Adjacency Matrix** | **Adjacency List** |
|-----------------------|---------------------|
| O(V²) space | O(V + E) space |
| Fast edge lookup (O(1)) | Slow edge lookup (O(V)) |
**Q2. Explain Prim’s algorithm for MST.**
**A:**
1. Start with a source node.
2. Use a priority queue to greedily select the minimum-weight edge connecting the MST
to a new vertex.
3. Repeat until all vertices are included.
**Q3. How does Dijkstra’s algorithm work?**
**A:**
1. Initialize distances to infinity except the source (0).
2. Extract the node with the smallest distance using a priority queue.
3. Relax all adjacent edges and update distances.
---
4
### **Unit 4 – Balanced Trees**
**Q1. What is an AVL tree? Explain rotations.**
**A:** A height-balanced BST where the balance factor (height difference of left/right
subtrees) is ±1.
- **LL Rotation:** Right rotation for left-heavy subtree.
- **RR Rotation:** Left rotation for right-heavy subtree.
**Q2. What are Red-Black Trees? State their properties.**
**A:** A self-balancing BST with:
1. Nodes colored red/black.
2. Root and leaves (NIL) are black.
3. No two consecutive red nodes.
4. Equal black height on all paths.
**Q3. What is dynamic programming? How is it used in Optimal BST?**
**A:** Dynamic programming solves problems by breaking them into overlapping
subproblems and storing solutions.
- **Optimal BST:** Minimizes expected search cost using probabilities of keys. Formula:
\[
\text{Cost}(i,j) = \min_{i \leq r \leq j} \left[ \text{Cost}(i, r-1) + \text{Cost}(r+1, j) \right] +
\sum_{k=i}^{j} p_k
\]
---
5
### **Unit 5 – Indexing and Multiway Trees**
**Q1. Compare B-tree and B+ tree.**
**A:**
| **B-tree** | **B+ tree** |
|------------|-------------|
| Data stored in all nodes | Data only in leaf nodes |
| Slower range queries | Faster range queries (linked leaves) |
**Q2. What is a B-tree? Explain its properties.**
**A:** A balanced multiway search tree where:
- Each node has between \( \lceil m/2 \rceil \) and \( m \) children.
- All leaves are at the same level.
---
### **Unit 6 – File Organization**
**Q1. Compare sequential vs. indexed file organization.**
**A:**
| **Sequential** | **Indexed** |
|----------------|-------------|
| Records stored in order | Uses a B+ tree index for fast access |
| Slow for random access | O(log n) search time |
**Q2. What is a clustered index?**
6
**A:** A reordering of records on disk to match the index order (e.g., PRIMARY KEY in
SQL).
**Q3. What is an inverted file?**
**A:** Maps keywords to their locations in documents (used in search engines).
---
### **Algorithms & Code Snippets**
**Q1. Write pseudocode for BST insertion.**
```python
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
```
**Q2. Write pseudocode for BFS traversal.**
```python
def BFS(root):
7
queue = [root]
while queue:
node = queue.pop(0)
print(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
