Unit 6: Data Structures and Algorithms

DATA STRUCTURES & ALGORITHMS

UGC NET / JRF — Computer Science & Applications

High-Yield Study Notes & PYQ-Pattern Workbook (Unit 6)

Contents

Ch.1 — Intro & Linear Data Structures

Ch.2 — Non-linear Data Structures

Ch.3 — Performance Analysis & Recurrence Relations

Ch.4 — Algorithm Design Techniques

Ch.5 — Searching and Sorting Algorithms

Ch.6 — Hashing

One-Shot Revision

Mini Mock Test (Answer Key)

Beginner → Concept → NET-level → JRF-level. Compact by design — exam value over page count.

Chapter 1 — Introduction & Linear Data Structures

1.1 Arrays

SimpleAn array is a fixed-size, contiguous block of same-type elements accessed by index — O(1) random access, but insertion/deletion in the middle requires shifting elements.

JRF-level numerical — 2D array address2D array A[1..10][1..15] stored in row-major order, base address 1000, element size 4 bytes. Find address of A[4][6]. Address = base + ((row−lowRow)×numCols + (col−lowCol)) × size = 1000 + ((4−1)×15 + (6−1))×4 = 1000 + (45+5)×4 = 1000+200 = 1200. This exact row-major/column-major address-formula numerical is a very frequently tested DS question.

1.2 Stack (LIFO)

IdeaLast-In-First-Out. Operations: PUSH (insert at top), POP (remove from top), PEEK/TOP (view top without removing). All O(1).

Application	Why a Stack
Function call management	Call stack tracks return addresses (LIFO order of returns)
Expression evaluation	Infix→Postfix conversion, postfix evaluation
Balanced parentheses check	Push opening brackets, pop & match on closing
Undo functionality	Most recent action undone first

JRF-level numerical — infix to postfixConvert infix A+B*C−D to postfix using the stack-based algorithm (operators pushed/popped by precedence): Result = ABC*+D−. Trace: A→output. +→push. B→output. *→push(higher prec than +, stays). C→output. Now − arrives: pop *,+ (both ≥ prec of −) to output, push −. D→output. End: pop remaining − . Final: A B C * + D −. This trace-through technique is THE classic stack numerical for NET/JRF.

1.3 Queue (FIFO)

IdeaFirst-In-First-Out. ENQUEUE (insert at rear), DEQUEUE (remove from front). All O(1) with proper implementation (e.g., circular array or linked list).

Queue Type	Idea
Simple Queue	Basic FIFO, rear-insert/front-remove
Circular Queue	Rear wraps around to the beginning when array end is reached — avoids wasted space of a simple array queue
Priority Queue	Elements served by PRIORITY, not strictly arrival order (often implemented using a Heap)
Deque (Double-ended)	Insertion/deletion allowed at BOTH front and rear

JRF trapA simple array-based queue (without circularity) suffers from wasted space after several dequeues — front keeps advancing but the freed slots at the beginning can't be reused unless the queue is CIRCULAR. This "why use a circular queue" reasoning is commonly tested.

1.4 Linked Lists

Type	Idea
Singly Linked List	Each node points to the NEXT node only; traversal is one-directional
Doubly Linked List	Each node has pointers to BOTH next and previous nodes — bidirectional traversal, easier deletion
Circular Linked List	Last node points back to the FIRST node (no NULL end) — useful for round-robin style access

JRF trap — array vs linked list tradeoffsArrays: O(1) random access, O(n) insertion/deletion (shifting needed), fixed size, no extra memory overhead. Linked Lists: O(n) access (must traverse), O(1) insertion/deletion ONCE YOU HAVE THE POINTER (no shifting), dynamic size, extra memory for pointers. This complete access-vs-insertion tradeoff table is exactly what NET/JRF compares.

MUST REMEMBER — Chapter 1

• 2D array address (row-major): base + ((row−lowRow)×cols + (col−lowCol))×size.
• Stack = LIFO (push/pop/peek, all O(1)); used for function calls, expression conversion, undo.
• Queue = FIFO (enqueue/dequeue, all O(1)); Circular Queue avoids wasted space vs simple array queue.
• Singly linked = one direction; Doubly = both directions; Circular = last points back to first.
• Arrays: O(1) access, O(n) insert/delete. Linked lists: O(n) access, O(1) insert/delete (with pointer in hand).

DON'T CONFUSE

• Stack (LIFO) vs Queue (FIFO) — opposite removal order.
• Array's O(1) access vs Linked list's O(1) insertion — each structure is fast at a DIFFERENT operation.

JRF CHALLENGE ZONE — Chapter 1

1. 2D array A[1..20][1..10], base=500, element size=2, row-major. Find address of A[5][3].
Answer: 500+((5−1)×10+(3−1))×2 = 500+(40+2)×2 = 500+84 = 584

2. Convert infix (A+B)*C to postfix.
Answer: AB+C*

3. Which data structure provides O(1) insertion/deletion ANYWHERE once you have a pointer to the location, without shifting? (a) Array (b) Linked List (c) Both equally (d) Neither
Answer: (b)

Practice Questions — Chapter 1 (8)

1. 2D array A[1..10][1..10], base=1000, element size=4, row-major. Find address of A[3][3].
   Ans: 1000+((3−1)×10+(3−1))×4 = 1000+(20+2)×4 = 1000+88 = 1088
2. What are the three main stack operations?
   Ans: Push, Pop, Peek/Top
3. Convert infix A*B+C to postfix.
   Ans: AB*C+
4. Why is a circular queue preferred over a simple array-based queue?
   Ans: It reuses freed slots at the front by wrapping the rear around, avoiding wasted space
5. Differentiate a singly and a doubly linked list.
   Ans: Singly has next-pointers only (one direction); doubly has next AND previous pointers (bidirectional)
6. What is the time complexity of random access in an array vs a linked list?
   Ans: Array: O(1); Linked list: O(n) (must traverse from the head)
7. Name two real-world applications of a stack.
   Ans: Any two of: function call management, expression evaluation/conversion, balanced parentheses checking, undo functionality
8. What is a Deque?
   Ans: A double-ended queue allowing insertion and deletion at both the front and the rear

---

Chapter 2 — Non-linear Data Structures

2.1 Binary Trees — Basics

IdeaEach node has AT MOST 2 children (left, right). Terminology: Root (topmost node), Leaf (no children), Height (longest path from root to a leaf), Depth (distance from root to a specific node).

Max nodes at level L (root=level 0) = 2^L Max nodes in a tree of height h = 2^(h+1) − 1 Min height for n nodes = ⌈log2(n+1)⌉ − 1

JRF-level numericalA complete binary tree has 100 nodes. Find its height. Using min height formula: h = ⌈log2(101)⌉−1 ≈ ⌈6.66⌉−1 = 7−1 = 6. Verify: a tree of height 6 can hold up to 2^7−1=127 nodes (enough for 100); height 5 could hold only 2^6−1=63 (not enough). So height = 6.

2.2 Tree Traversals

Traversal	Order
Inorder	Left → Root → Right
Preorder	Root → Left → Right
Postorder	Left → Right → Root
Level order	Level by level, left to right (uses a Queue, BFS-style)

JRF-level numerical — reconstruct tree from traversalsGiven Inorder: D,B,E,A,F,C,G and Preorder: A,B,D,E,C,F,G — reconstruct and find Postorder. Preorder's first element A = root. In Inorder, everything left of A (D,B,E) is the LEFT subtree; everything right (F,C,G) is the RIGHT subtree. Recursively repeat: left subtree root (next in Preorder among D,B,E) = B, with D left of B and E right of B in Inorder. Right subtree root = C, with F left and G right. Final tree: A(root), B(left of A, children D,E), C(right of A, children F,G). Postorder = D,E,B,F,G,C,A. "Given any two traversals, reconstruct the tree / find the third traversal" is THE classic tree JRF numerical — Inorder+Preorder or Inorder+Postorder can always uniquely reconstruct a tree, but Preorder+Postorder ALONE cannot (ambiguous without Inorder).

2.3 Binary Search Tree (BST)

IdeaFor every node: all values in the LEFT subtree < node's value < all values in the RIGHT subtree. This property makes Inorder traversal of a BST always produce a SORTED sequence.

JRF trapBST search/insert/delete are O(log n) ONLY if the tree is balanced. In the WORST CASE (e.g., inserting already-sorted data 1,2,3,4,5... in order), a BST degenerates into a linked list, making operations O(n). This "BST is not automatically O(log n)" caveat is a very common JRF trap.

2.4 AVL Trees (Self-Balancing BST)

IdeaAn AVL tree maintains: |height(left subtree) − height(right subtree)| ≤ 1 for EVERY node (the "balance factor" is always −1, 0, or +1). If an insertion/deletion violates this, ROTATIONS (LL, RR, LR, RL) restore balance.

NET pointAVL trees guarantee O(log n) for search/insert/delete in the WORST CASE (unlike plain BST) — this guaranteed worst-case balance is the entire point of using AVL over a plain BST.

2.5 B-Trees (Overview)

IdeaA B-Tree of order m: each node can have UP TO m children and m−1 keys, keeps keys SORTED, and is used heavily in DATABASE INDEXING and file systems (since it minimizes disk I/O by keeping the tree very SHALLOW/wide, unlike a tall binary tree).

2.6 Graphs — Representation

Representation	Space	Edge check (u,v)
Adjacency Matrix	O(V²)	O(1)
Adjacency List	O(V+E)	O(degree of u)

JRF trapFor a SPARSE graph (E much less than V²), Adjacency List is far more space-efficient (O(V+E) vs O(V²)). For a DENSE graph (E close to V²), the space difference shrinks, and Adjacency Matrix's O(1) edge lookup becomes more attractive. "Which representation for which graph density" is a common JRF conceptual question.

2.7 Graph Traversals — BFS & DFS

IdeaBFS (Breadth-First Search): explores level-by-level, uses a QUEUE. DFS (Depth-First Search): explores as deep as possible before backtracking, uses a STACK (or recursion).

JRF insightBFS from a source finds the SHORTEST PATH (in terms of number of edges) in an UNWEIGHTED graph — this specific property (shortest path only for BFS, not DFS, and only for unweighted graphs) is frequently tested. DFS is commonly used for detecting cycles, topological sorting, and finding connected components.

MUST REMEMBER — Chapter 2

• Max nodes at level L = 2^L; max nodes in height-h tree = 2^(h+1)−1.
• Inorder(BST) always gives sorted order. BST worst case (sorted insertion) degenerates to O(n), not O(log n).
• AVL tree: balance factor ∈{−1,0,+1} for every node; guarantees O(log n) worst case via rotations.
• Inorder+Preorder OR Inorder+Postorder can uniquely reconstruct a tree; Preorder+Postorder alone CANNOT.
• B-Tree: wide/shallow, used for DB indexing to minimize disk I/O.
• Adjacency Matrix: O(V²) space, O(1) edge check. Adjacency List: O(V+E) space, better for sparse graphs.
• BFS uses a Queue, finds shortest path (unweighted graph only). DFS uses a Stack/recursion, used for cycle detection/topological sort.

DON'T CONFUSE

• BST (not always balanced, worst case O(n)) vs AVL (always balanced, guaranteed O(log n)).
• BFS (queue, shortest path in unweighted graphs) vs DFS (stack/recursion, cycle detection/topological sort).

JRF CHALLENGE ZONE — Chapter 2

1. Inserting values 1,2,3,4,5 in order into an empty BST results in: (a) A balanced tree, height 2 (b) A degenerate tree (linked list), height 4 (c) An AVL tree automatically (d) An error
Answer: (b)

2. Given ONLY Preorder and Postorder traversals (no Inorder), can you always uniquely reconstruct the binary tree? (a) Yes, always (b) No, it can be ambiguous (c) Only for BSTs (d) Only for AVL trees
Answer: (b)

3. Which traversal finds the shortest path (edge count) from a source in an unweighted graph? (a) DFS (b) BFS (c) Inorder (d) Postorder
Answer: (b)

Practice Questions — Chapter 2 (8)

1. What is the maximum number of nodes in a binary tree of height 4?
   Ans: 2^5−1 = 31
2. What does an Inorder traversal of a BST always produce?
   Ans: A sorted sequence of the values
3. Why can a BST degrade to O(n) operations in the worst case?
   Ans: If elements are inserted in already-sorted order, the tree degenerates into a linked-list shape
4. What is the balance factor range allowed at every node of an AVL tree?
   Ans: −1, 0, or +1
5. Which pair of traversals can always uniquely reconstruct a binary tree?
   Ans: Inorder + Preorder, or Inorder + Postorder
6. Why are B-Trees preferred for database indexing over plain binary trees?
   Ans: They are wide/shallow, minimizing disk I/O (fewer levels to traverse) for large datasets
7. Differentiate the space complexity of adjacency matrix and adjacency list graph representations.
   Ans: Adjacency matrix: O(V²); Adjacency list: O(V+E)
8. Which graph traversal uses a Queue, and which uses a Stack (or recursion)?
   Ans: BFS uses a Queue; DFS uses a Stack (or recursion)

---

Chapter 3 — Performance Analysis & Recurrence Relations

3.1 Asymptotic Notations

Notation	Meaning
Big-O (O)	UPPER bound — worst-case growth rate (algorithm runs "no slower than" this)
Big-Omega (Ω)	LOWER bound — best-case growth rate (algorithm runs "no faster than" this)
Big-Theta (Θ)	TIGHT bound — when upper and lower bounds MATCH (exact growth rate)

JRF trapBig-O describes an UPPER bound, which is often (loosely) associated with "worst case" — but technically O, Ω, and Θ can each be applied to best-case, average-case, OR worst-case analysis; they are mathematical bound concepts, not synonyms for "worst case" itself. E.g., you can say an algorithm's BEST case is O(n) too. Conflating "Big-O" with "worst case" as if they were the same concept is a common conceptual trap tested at JRF level.

3.2 Common Growth Rates (Fastest to Slowest)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

3.3 Solving Recurrences — Substitution & Recursion Tree

Worked example — recursion treeT(n) = 2T(n/2) + n. Draw the recursion tree: at depth 0, cost=n (1 problem of size n). Depth 1: cost=n (2 problems of size n/2, each contributing n/2, total n). Depth 2: cost=n (4 problems of size n/4, each n/4, total n). Pattern: EVERY level costs n. Number of levels = log2(n) (until problem size reaches 1). Total = n × log2(n) = O(n log n) — this is exactly Merge Sort's recurrence, and the recursion-tree method (cost-per-level × number-of-levels) is the standard technique tested.

3.4 Master Theorem

For T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a): Case 1: If f(n) = O(n^(log_b a − ε)) for some ε>0, then T(n) = Θ(n^(log_b a)) Case 2: If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) · log n) Case 3: If f(n) = Ω(n^(log_b a + ε)), AND regularity holds, then T(n) = Θ(f(n))

JRF-level numerical — applying Master TheoremT(n) = 2T(n/2) + n. Here a=2, b=2, f(n)=n. Compute n^(log_b a) = n^(log2 2) = n^1 = n. Compare f(n)=n with n^1=n → they are EQUAL (f(n) = Θ(n^(log_b a))) → this is Case 2 → T(n) = Θ(n log n). Another: T(n) = 8T(n/2) + n². a=8,b=2, n^(log2 8)=n^3. f(n)=n² grows SLOWER than n³ → Case 1 → T(n) = Θ(n³). Another: T(n) = 2T(n/2) + n². n^(log2 2)=n^1. f(n)=n² grows FASTER than n → Case 3 → T(n) = Θ(n²). "Compute n^(log_b a), compare with f(n), pick the matching case" is EXACTLY how Master Theorem numericals are tested — this is one of the highest-yield numerical types in the entire DAA syllabus.

TrapMaster Theorem does NOT apply to every recurrence — e.g., T(n)=2T(n/2)+n/log n has NO valid case (f(n)=n/log n doesn't fit polynomially into any of the 3 cases). Also, subtractive recurrences like T(n)=T(n−1)+n are NOT in Master Theorem form at all (must be T(n/b), not T(n−c)) — these need substitution/recursion-tree methods instead.

MUST REMEMBER — Chapter 3

• Big-O=upper bound; Big-Ω=lower bound; Big-Θ=tight bound (when O and Ω match). None of these means "worst case" specifically — they're bound types applicable to any case.
• Growth order: O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2ⁿ)<O(n!).
• Master Theorem (T(n)=aT(n/b)+f(n)): compare f(n) to n^(log_b a) — smaller→Case1(Θ(n^log_b a)); equal→Case2(Θ(n^log_b a · log n)); larger→Case3(Θ(f(n))).
• Master theorem doesn't apply to subtractive recurrences (T(n−c)) or non-polynomially-comparable f(n).

DON'T CONFUSE

• Big-O (upper bound concept) vs "worst case" (a scenario) — not strictly synonyms.
• Master Theorem Case 1 (f(n) smaller) vs Case 3 (f(n) larger) — easy to mix up direction.

JRF CHALLENGE ZONE — Chapter 3

1. T(n) = 4T(n/2) + n. Using Master Theorem, find T(n).
Answer: a=4,b=2,n^(log2 4)=n². f(n)=n is smaller (Case 1) → T(n) = Θ(n²)

2. T(n) = 3T(n/3) + n log n. Which Master Theorem case applies?
Answer: n^(log3 3)=n. f(n)=n log n grows faster than n (Case 3, with regularity check) → T(n) = Θ(n log n)

3. Which of these is NOT directly solvable by the Master Theorem? (a) T(n)=2T(n/2)+n (b) T(n)=T(n−1)+n (c) T(n)=8T(n/2)+n² (d) T(n)=3T(n/3)+n
Answer: (b) — subtractive recurrence, not of the form T(n/b).

Practice Questions — Chapter 3 (8)

1. What does Big-O notation represent?
   Ans: An upper bound on the growth rate of an algorithm's running time
2. What does Big-Theta represent?
   Ans: A tight bound — when the upper (O) and lower (Ω) bounds match
3. Order these by growth rate (fastest to slowest): O(n²), O(log n), O(n), O(n log n).
   Ans: O(log n) < O(n) < O(n log n) < O(n²)
4. T(n) = 2T(n/2) + n. Solve using the recursion tree method.
   Ans: Every level costs n, with log2(n) levels → T(n) = Θ(n log n)
5. T(n) = T(n/2) + 1. Apply Master Theorem to find T(n).
   Ans: a=1,b=2,n^(log2 1)=n^0=1. f(n)=1 matches (Case 2) → T(n) = Θ(log n)
6. T(n) = 2T(n/4) + n. Apply Master Theorem.
   Ans: n^(log4 2)=n^0.5. f(n)=n grows faster (Case 3) → T(n) = Θ(n)
7. Why doesn't Master Theorem apply to T(n) = T(n−1) + n?
   Ans: It's a subtractive recurrence (T(n−c) form), not the required T(n/b) divide-form
8. Is Big-O the same thing as "worst-case analysis"?
   Ans: No — Big-O is a bound type that can describe best, average, or worst case; they are not strictly synonymous

---

Chapter 4 — Algorithm Design Techniques

4.1 Divide and Conquer

IdeaBreak the problem into INDEPENDENT sub-problems (Divide), solve each recursively (Conquer), then COMBINE their solutions. Sub-problems don't overlap/share work. Examples: Merge Sort, Quick Sort, Binary Search.

4.2 Greedy Algorithms

IdeaMakes the LOCALLY optimal choice at each step, hoping it leads to a globally optimal solution — never reconsiders past choices. Works ONLY when the problem has the "Greedy Choice Property" (a locally optimal choice leads to a globally optimal solution) AND "Optimal Substructure".

Problem	Greedy Strategy
Activity Selection	Pick the activity that finishes EARLIEST first
Fractional Knapsack	Pick items by HIGHEST value/weight ratio first
Huffman Coding	Repeatedly merge the two LOWEST-frequency nodes
Dijkstra's Algorithm	Always expand the CLOSEST unvisited vertex next
Prim's/Kruskal's MST	Always add the CHEAPEST edge that doesn't violate the constraint (no cycle for Kruskal's)

JRF trap — greedy doesn't always workGreedy gives the OPTIMAL solution for Fractional Knapsack, but NOT for 0/1 Knapsack (where items can't be split) — 0/1 Knapsack needs Dynamic Programming instead, since a greedy local choice can lead to a suboptimal overall result. "Which problems does greedy actually solve optimally" is a very frequently tested JRF distinction.

4.3 Dynamic Programming (DP)

IdeaBreaks a problem into OVERLAPPING sub-problems (unlike divide-and-conquer's independent ones) and stores/reuses their solutions ("memoization" top-down, or "tabulation" bottom-up) to avoid recomputation. Requires "Optimal Substructure" (optimal solution built from optimal sub-solutions).

JRF-level numerical — 0/1 Knapsack DP traceItems: (weight,value) = (1,1),(3,4),(4,5),(5,7); capacity=7. Building the DP table (rows=items, columns=capacity 0-7), the final answer dp[4][7] is computed by, for each item, choosing max(exclude item: dp[i-1][w], include item: value+dp[i-1][w-weight]). Final optimal value = 9 (items with weight 3+4=7, value 4+5=9). This "build the DP table, trace which items are included" technique is the standard 0/1 Knapsack JRF numerical.

NET pointFibonacci computed via naive recursion is O(2ⁿ) (massive REPEATED sub-problem recomputation); using DP (memoization/tabulation) reduces it to O(n) — a classic example of DP's benefit from overlapping sub-problems, frequently used to illustrate WHY DP matters.

4.4 Backtracking

IdeaBuilds a solution incrementally, and ABANDONS ("backtracks" from) a partial solution as soon as it's determined that it CANNOT lead to a valid/optimal complete solution — avoids exploring the entire search space blindly. Examples: N-Queens, Sudoku solver, Hamiltonian cycle.

4.5 Branch and Bound

IdeaSimilar to backtracking (explores a search tree, prunes branches) but specifically used for OPTIMIZATION problems — maintains a "bound" (best solution found so far) and prunes any branch whose best-possible outcome CANNOT beat that bound. Example: 0/1 Knapsack (branch and bound variant), Travelling Salesman Problem.

JRF trap — backtracking vs branch and boundBacktracking abandons a path when it's INVALID (violates a constraint). Branch and Bound abandons a path when it CANNOT possibly be BETTER than the current best solution (even if technically still valid) — this is specifically for optimization problems, not just constraint satisfaction. Confusing these two pruning criteria is a common JRF trap.

MUST REMEMBER — Chapter 4

• Divide and Conquer: independent sub-problems, no overlap (Merge Sort, Quick Sort, Binary Search).
• Greedy: locally optimal choice each step; works only if Greedy Choice Property + Optimal Substructure hold.
• Greedy is optimal for Fractional Knapsack, MST (Prim's/Kruskal's), Dijkstra's, Activity Selection, Huffman — but NOT for 0/1 Knapsack (needs DP).
• DP: overlapping sub-problems + optimal substructure; memoization (top-down) or tabulation (bottom-up).
• Backtracking: abandons INVALID partial solutions. Branch and Bound: abandons partial solutions that CAN'T beat the current best (for optimization).

DON'T CONFUSE

• Divide and Conquer (independent sub-problems) vs DP (overlapping sub-problems, reuses solutions).
• Greedy (never reconsiders, no guarantee of optimality in general) vs DP (explores/combines optimal sub-solutions, guarantees optimality when applicable).
• Backtracking (prunes invalid paths) vs Branch and Bound (prunes paths that can't beat the current best).

JRF CHALLENGE ZONE — Chapter 4

1. Which problem does the GREEDY approach solve OPTIMALLY? (a) 0/1 Knapsack (b) Fractional Knapsack (c) Both equally (d) Neither
Answer: (b)

2. What key property must a problem have for Dynamic Programming to help (beyond optimal substructure)? (a) Independent sub-problems (b) Overlapping sub-problems (c) No sub-problems at all (d) Randomized input
Answer: (b)

3. A search algorithm abandons a partial solution because it violates a constraint (not because of any "best value" comparison). This is: (a) Branch and Bound (b) Backtracking (c) Dynamic Programming (d) Greedy
Answer: (b)

Practice Questions — Chapter 4 (8)

1. What is the key difference between the sub-problems in Divide-and-Conquer vs DP?
   Ans: Divide-and-Conquer sub-problems are independent; DP sub-problems overlap
2. What two properties must a problem have for Dynamic Programming to apply?
   Ans: Optimal substructure and overlapping sub-problems
3. Does the Greedy approach give an optimal solution for 0/1 Knapsack?
   Ans: No — 0/1 Knapsack requires Dynamic Programming for an optimal solution
4. What greedy strategy does Kruskal's algorithm use for MST?
   Ans: Always add the cheapest edge that does not form a cycle
5. Differentiate memoization and tabulation in DP.
   Ans: Memoization is top-down (recursive, caches results on demand); tabulation is bottom-up (iteratively fills a table)
6. What is the time complexity of naive recursive Fibonacci, and what does DP reduce it to?
   Ans: Naive: O(2ⁿ); DP reduces it to O(n)
7. Differentiate Backtracking and Branch and Bound.
   Ans: Backtracking prunes paths that violate a constraint; Branch and Bound prunes paths that cannot beat the current best solution (for optimization problems)
8. Name two classic examples of problems solved using Backtracking.
   Ans: Any two of: N-Queens, Sudoku solving, Hamiltonian cycle

---

Chapter 5 — Searching and Sorting Algorithms

5.1 Searching — Linear vs Binary

Algorithm	Requires Sorted?	Time Complexity
Linear Search	No	O(n)
Binary Search	Yes	O(log n)

Worked example — binary search traceSearch for 23 in sorted array [4,8,15,16,23,42,55,68,91], indices 0-8. mid=4(value 23) → FOUND immediately in this case, but generally: low=0,high=8,mid=(0+8)/2=4. arr[4]=23=target → found in just 1 comparison (lucky case). If searching for 42: mid=4(23)<42→low=5. mid=(5+8)/2=6(55)>42→high=5. mid=5(42)=target→found in 3 comparisons. This "trace mid calculations step by step" is the standard binary search JRF numerical.

5.2 Sorting Algorithms — Complexity Table (HIGH-YIELD)

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

JRF trap — this exact table is THE most-tested DAA factQuick Sort's WORST case is O(n²) (occurs with a consistently bad pivot choice, e.g., always picking the first/last element on already-sorted data) — despite Quick Sort usually being called "faster in practice" than Merge Sort. Merge Sort GUARANTEES O(n log n) in all cases but needs O(n) EXTRA space, while Quick Sort sorts IN-PLACE (O(log n) space for recursion). Heap Sort guarantees O(n log n) worst case AND O(1) space, but is NOT stable. "Which sort guarantees worst-case O(n log n) AND O(1) space" → answer is specifically Heap Sort — a frequently tested combination.

Trap — stabilityA STABLE sort preserves the relative order of EQUAL elements. Bubble, Insertion, and Merge Sort are stable; Selection, Quick, and Heap Sort are NOT stable (in their standard implementations). This exact stable/unstable classification is very frequently tested.

5.3 Sorting Trace — Selection Sort Example

Worked exampleArray: [29, 10, 14, 37, 13]. Selection sort (find min, swap to front, repeat): Pass1: min=10(idx1), swap with idx0 → [10,29,14,37,13] Pass2: min=13(idx4, among idx1-4), swap with idx1 → [10,13,14,37,29] Pass3: min=14(idx2, already in place, no swap needed) → [10,13,14,37,29] Pass4: min=29(idx4), swap with idx3 → [10,13,14,29,37] Sorted: [10,13,14,29,37]. Tracing sort passes step-by-step on a small array is a common JRF numerical style across all sorting algorithms.

5.4 Quick Sort — Partition Trace

JRF-level numerical — quicksort partition (pivot = last element)Array: [10,80,30,90,40,50,70], pivot=70(last element). Scan left to right, swap elements ≤70 to the front: 10(≤70,keep), 80(>70,skip), 30(≤70,swap into position after 10), 90(>70,skip), 40(≤70,swap in), 50(≤70,swap in). Final partition places pivot 70 at its correct sorted position, with [10,30,40,50] before it and [80,90] after. Result after ONE partition step: [10,30,40,50,70,80,90] — pivot 70 now sits exactly where it belongs in the final sorted array. This "trace one partition pass" numerical is THE standard Quick Sort JRF question.

MUST REMEMBER — Chapter 5

• Linear search O(n), no sort needed; Binary search O(log n), requires SORTED data.
• Stable sorts: Bubble, Insertion, Merge. Unstable: Selection, Quick, Heap.
• Merge Sort: always O(n log n), needs O(n) extra space. Quick Sort: average O(n log n) but WORST O(n²), in-place O(log n) space.
• Heap Sort: guaranteed O(n log n) worst case AND O(1) space — but unstable.
• Bubble/Insertion best case is O(n) (already-sorted/nearly-sorted input).

DON'T CONFUSE

• Quick Sort's average case O(n log n) vs its worst case O(n²) — don't quote average when worst is asked.
• Merge Sort (stable, O(n) space) vs Quick Sort (unstable, O(log n) space) vs Heap Sort (unstable, O(1) space).

JRF CHALLENGE ZONE — Chapter 5

1. Which sorting algorithm guarantees O(n log n) in the WORST case while using only O(1) extra space? (a) Merge Sort (b) Quick Sort (c) Heap Sort (d) Bubble Sort
Answer: (c)

2. Which of these sorts is NOT stable? (a) Bubble Sort (b) Insertion Sort (c) Merge Sort (d) Quick Sort
Answer: (d)

3. Binary search on a sorted array of 1000 elements takes at most how many comparisons (worst case)?
Answer: ⌈log2(1000)⌉ = 10

Practice Questions — Chapter 5 (8)

1. What is the prerequisite for using Binary Search?
   Ans: The array must be sorted
2. What is the worst-case time complexity of Quick Sort, and when does it occur?
   Ans: O(n²); occurs with consistently poor pivot choices, e.g., on already-sorted data with a naive pivot strategy
3. Which sorting algorithms are stable, among Bubble, Selection, Insertion, Merge, Quick, Heap?
   Ans: Bubble, Insertion, and Merge Sort
4. What is the space complexity of Merge Sort, and why?
   Ans: O(n) — it needs auxiliary arrays to merge sorted halves
5. Which sort guarantees O(n log n) worst case AND uses only O(1) extra space?
   Ans: Heap Sort
6. What is the best-case time complexity of Bubble Sort and Insertion Sort?
   Ans: O(n), when the input is already sorted
7. Array [5,2,9,1,5,6]. After one pass of Bubble Sort (adjacent swaps), what is the array?
   Ans: [2,5,1,5,6,9] — largest element (9) bubbles toward its correct position each pass, but here 9 moves past 1 and 5 until 6
8. What is the average and worst-case time complexity of Quick Sort?
   Ans: Average: O(n log n); Worst: O(n²)

---

Chapter 6 — Hashing

6.1 Hash Functions & Hash Tables

SimpleA hash function maps a (potentially large) key space to a small, fixed-size array of "buckets" (indices) — giving average O(1) insert/search/delete, MUCH faster than a linear search through a list.

Common hash function — Division Methodh(key) = key mod TableSize. Choosing TableSize as a PRIME number (not a power of 2) tends to distribute keys more evenly and reduce clustering — a frequently tested design consideration.

6.2 Collisions & Load Factor

IdeaA COLLISION occurs when two different keys hash to the SAME index. Load Factor (α) = n/m (n = number of stored elements, m = table size) — measures how "full" the table is; higher load factor means more collisions are likely.

6.3 Collision Resolution — Chaining

IdeaEach table slot holds a LINKED LIST (chain) of all keys that hashed to that index — collisions simply get appended to the chain. Simple, handles unlimited collisions (list can grow), but has pointer-storage overhead.

6.4 Collision Resolution — Open Addressing

Method	Probing formula (i = attempt number)
Linear Probing	h(key,i) = (h(key)+i) mod m — checks NEXT slot sequentially
Quadratic Probing	h(key,i) = (h(key)+i²) mod m — jumps by increasing SQUARES
Double Hashing	h(key,i) = (h1(key)+i·h2(key)) mod m — uses a SECOND hash function for the step size

JRF trap — primary vs secondary clusteringLinear Probing suffers from PRIMARY CLUSTERING (long runs of consecutive occupied slots form, making future collisions increasingly likely to collide again into the same growing cluster). Quadratic Probing reduces primary clustering but can still suffer from SECONDARY CLUSTERING (keys with the SAME initial hash value follow the exact same probe sequence). Double Hashing avoids BOTH types of clustering, since the step size itself depends on the key. This clustering-type hierarchy (Linear→primary, Quadratic→secondary, Double hashing→neither) is a very frequently tested JRF distinction.

Worked example — linear probing insertionTable size=7, hash h(key)=key mod 7. Insert keys 50,700,76,85 in order. 50 mod 7=1→slot1. 700 mod 7=0→slot0. 76 mod 7=6→slot6. 85 mod 7=1→COLLISION(slot1 taken)→try slot2(linear probe,+1)→empty→place at slot2. This "resolve the collision by probing forward" trace is the standard open-addressing JRF numerical.

6.5 Rehashing

IdeaWhen the load factor exceeds a threshold (commonly ~0.7), the table is RESIZED (typically doubled) and ALL existing elements are RE-INSERTED into the new, larger table using the hash function again — necessary because the modulus (table size) changed, so old indices are no longer valid.

MUST REMEMBER — Chapter 6

• Hash table gives average O(1) insert/search/delete. Load factor α = n/m.
• Division method h(key)=key mod TableSize; prime table size reduces clustering.
• Chaining: each slot holds a linked list of colliding keys.
• Linear probing → primary clustering; Quadratic probing → secondary clustering (less severe); Double hashing → avoids both.
• Rehashing: triggered when load factor exceeds a threshold; table resized (usually doubled) and all elements reinserted.

DON'T CONFUSE

• Primary clustering (Linear Probing — consecutive occupied runs) vs Secondary clustering (Quadratic Probing — same probe sequence for same initial hash).
• Chaining (separate linked lists per slot) vs Open Addressing (all keys stored directly within the table itself, no external structure).

JRF CHALLENGE ZONE — Chapter 6

1. Which collision resolution method suffers from PRIMARY clustering? (a) Chaining (b) Linear Probing (c) Double Hashing (d) None
Answer: (b)

2. Table size=5, h(key)=key mod 5. Insert 12, 17 in order using linear probing. Where does 17 end up? (12→slot2; 17→slot2 collision→probe forward)
Answer: slot3 — 17 mod 5=2(taken by 12), linear probe to slot3(empty).

3. Which collision resolution technique avoids BOTH primary and secondary clustering? (a) Linear Probing (b) Quadratic Probing (c) Double Hashing (d) Chaining causes clustering too
Answer: (c)

Practice Questions — Chapter 6 (7)

1. What is a collision in hashing?
   Ans: When two different keys hash to the same table index
2. Define load factor.
   Ans: α = n/m, the ratio of stored elements (n) to table size (m)
3. Why is a prime table size preferred in the division hash method?
   Ans: It distributes keys more evenly and reduces clustering compared to non-prime sizes like powers of 2
4. How does chaining resolve collisions?
   Ans: Each table slot holds a linked list of all keys that hash to that index
5. Which open-addressing method suffers from primary clustering, and why?
   Ans: Linear Probing — because consecutive occupied runs form, increasing the chance of further collisions in the same growing cluster
6. Table size=7, h(key)=key mod 7. Insert 21 then 14 using linear probing. Where does 14 end up?
   Ans: 21 mod 7=0→slot0. 14 mod 7=0→collision→probe to slot1
7. When is rehashing triggered, and what does it involve?
   Ans: When the load factor exceeds a threshold (commonly ~0.7); the table is resized (usually doubled) and all elements are reinserted

---

One-Shot Revision — Unit 6

Key facts across all chapters

• 2D array address (row-major): base+((row−lowRow)×cols+(col−lowCol))×size. Stack=LIFO; Queue=FIFO. Circular queue avoids wasted space.
• Array: O(1) access, O(n) insert/delete. Linked list: O(n) access, O(1) insert/delete (with pointer in hand).
• Max nodes height h = 2^(h+1)−1. Inorder(BST)=sorted. BST worst case degenerates to O(n); AVL guarantees O(log n) via rotations.
• Inorder+Preorder OR Inorder+Postorder → unique tree; Preorder+Postorder alone → ambiguous.
• Adjacency Matrix: O(V²) space, O(1) edge check. Adjacency List: O(V+E), better for sparse graphs. BFS=queue,shortest path(unweighted); DFS=stack/recursion,cycle detection.
• Big-O=upper bound; Ω=lower; Θ=tight. NOT synonyms for "worst case" specifically.
• Master Theorem: compare f(n) to n^(log_b a) — smaller→Case1; equal→Case2(+log n factor); larger→Case3. Doesn't apply to subtractive recurrences.
• Divide&Conquer=independent subproblems; DP=overlapping subproblems+optimal substructure (memoization/tabulation).
• Greedy optimal for: Fractional Knapsack, MST, Dijkstra's, Activity Selection, Huffman. NOT optimal for 0/1 Knapsack (needs DP).
• Backtracking=prunes invalid paths; Branch&Bound=prunes paths that can't beat current best (optimization).
• Sorting: Stable=Bubble,Insertion,Merge. Unstable=Selection,Quick,Heap. Quick Sort worst=O(n²); Merge Sort always O(n log n) but O(n) space; Heap Sort=O(n log n) worst AND O(1) space.
• Hashing: Load factor α=n/m. Linear probing→primary clustering; Quadratic→secondary; Double hashing→neither. Rehashing at ~0.7 load factor.

Potential future exam areasPotential high-value exam area based on syllabus importance and historical question patterns: Master Theorem case-identification numericals; tree-reconstruction-from-traversals numericals; sorting-algorithm complexity-table matching questions (especially the stable/unstable and space-complexity combinations); 0/1 Knapsack DP-table tracing; and hash-table collision-resolution insertion traces (linear vs quadratic vs double hashing).

---

Unit 6 — UGC NET/JRF Mini Mock Test

45 questions across all 6 chapters. NTA/UGC NET-style question patterns — mixed NET/JRF difficulty, numerical, statement-based, matching and scenario-based. Answer key with brief explanations follows each question.

Q1. 2D array A[1..5][1..5], base=200, element size=2, row-major. Find address of A[3][2].
Ans: 200+((3−1)×5+(2−1))×2 = 200+22 = 222 [Ch1 | NET numerical]

Q2. Convert infix A+B*C to postfix.
Ans: ABC*+ [Ch1 | NET]

Q3. Which data structure removes elements in FIFO order?
Ans: Queue [Ch1 | NET]

Q4. Why is a circular queue preferred over a simple linear array queue?
Ans: It reuses freed front slots by wrapping the rear around, avoiding wasted space [Ch1 | NET]

Q5. Which linked list allows bidirectional traversal? (a) Singly (b) Doubly (c) Circular singly (d) None
Ans: (b) [Ch1 | NET]

Q6. A complete binary tree has 50 nodes. Find its minimum possible height.
Ans: h=⌈log2(51)⌉−1=6−1=5 [Ch2 | JRF numerical]

Q7. Which traversal of a BST always produces sorted order?
Ans: Inorder [Ch2 | NET]

Q8. Inserting 1,2,3,4,5 in order into an empty BST results in: (a) A balanced tree (b) A degenerate (linked-list-like) tree (c) An AVL tree (d) An error
Ans: (b) [Ch2 | JRF]

Q9. What balance factor range does every AVL tree node maintain?
Ans: −1, 0, or +1 [Ch2 | NET]

Q10. Given ONLY Preorder and Postorder (no Inorder), can a binary tree always be uniquely reconstructed? (a) Yes (b) No, can be ambiguous (c) Only for BSTs (d) Only for AVL trees
Ans: (b) [Ch2 | JRF]

Q11. Which graph traversal finds the shortest path (by edge count) in an unweighted graph?
Ans: BFS [Ch2 | NET]

Q12. Adjacency list space complexity is: (a) O(V²) (b) O(V+E) (c) O(E²) (d) O(V)
Ans: (b) [Ch2 | NET]

Q13. Big-Theta notation represents: (a) Upper bound only (b) Lower bound only (c) A tight bound (both upper and lower match) (d) Worst case only
Ans: (c) [Ch3 | NET]

Q14. T(n) = 2T(n/2) + n. Solve using Master Theorem.
Ans: Case 2 → T(n) = Θ(n log n) [Ch3 | JRF numerical]

Q15. T(n) = 8T(n/2) + n². Solve using Master Theorem.
Ans: n^(log2 8)=n³; f(n)=n² smaller → Case 1 → T(n)=Θ(n³) [Ch3 | JRF numerical]

Q16. Which recurrence CANNOT be solved directly by the Master Theorem? (a) T(n)=2T(n/2)+n (b) T(n)=T(n−1)+n (c) T(n)=3T(n/3)+n (d) T(n)=4T(n/2)+n²
Ans: (b) [Ch3 | JRF]

Q17. Order these by growth (fastest to slowest): O(n²), O(n log n), O(log n), O(n).
Ans: O(log n) < O(n) < O(n log n) < O(n²) [Ch3 | NET]

Q18. Divide and Conquer sub-problems are: (a) Overlapping (b) Independent (c) Always recursive only (d) Always O(1)
Ans: (b) [Ch4 | NET]

Q19. Which technique is REQUIRED for optimal 0/1 Knapsack (not solvable optimally by simple greedy)? (a) Greedy (b) Dynamic Programming (c) Divide and Conquer only (d) Linear search
Ans: (b) [Ch4 | JRF]

Q20. What two properties must a problem exhibit for DP to be beneficial?
Ans: Optimal substructure and overlapping sub-problems [Ch4 | NET]

Q21. Kruskal's algorithm greedily selects: (a) The most expensive edge (b) The cheapest edge that doesn't form a cycle (c) A random edge (d) The edge closest to the source
Ans: (b) [Ch4 | NET]

Q22. Differentiate Backtracking and Branch and Bound in one line.
Ans: Backtracking prunes invalid paths; Branch and Bound prunes paths that can't beat the current best solution [Ch4 | JRF]

Q23. Naive recursive Fibonacci has time complexity: (a) O(n) (b) O(n log n) (c) O(2ⁿ) (d) O(n²)
Ans: (c) [Ch4 | NET]

Q24. Which sorting algorithm is NOT stable? (a) Bubble Sort (b) Merge Sort (c) Quick Sort (d) Insertion Sort
Ans: (c) [Ch5 | NET]

Q25. Which sort guarantees O(n log n) in the worst case AND uses O(1) extra space?
Ans: Heap Sort [Ch5 | JRF]

Q26. What is the worst-case time complexity of Quick Sort?
Ans: O(n²) [Ch5 | NET]

Q27. Binary search requires the array to be: (a) Unsorted (b) Sorted (c) Circular (d) A linked list
Ans: (b) [Ch5 | NET]

Q28. Binary search on a sorted array of 500 elements takes at most how many comparisons in the worst case?
Ans: ⌈log2(500)⌉ = 9 [Ch5 | NET numerical]

Q29. Merge Sort's space complexity is: (a) O(1) (b) O(log n) (c) O(n) (d) O(n²)
Ans: (c) [Ch5 | NET]

Q30. What is the best-case time complexity of Insertion Sort?
Ans: O(n), for already-sorted input [Ch5 | NET]

Q31. What does the load factor α represent in a hash table?
Ans: The ratio of stored elements to table size (n/m) [Ch6 | NET]

Q32. Which collision resolution method uses a linked list per slot?
Ans: Chaining [Ch6 | NET]

Q33. Which open-addressing method suffers from primary clustering? (a) Quadratic Probing (b) Linear Probing (c) Double Hashing (d) None
Ans: (b) [Ch6 | NET]

Q34. Which collision resolution method avoids both primary and secondary clustering?
Ans: Double Hashing [Ch6 | JRF]

Q35. Table size=7, h(key)=key mod 7. Insert 15 then 22 using linear probing. Where does 22 land?
Ans: 15 mod 7=1→slot1. 22 mod 7=1→collision→probe to slot2 [Ch6 | JRF numerical]

Q36. Why is a prime table size preferred in the division hashing method?
Ans: It distributes keys more evenly and reduces clustering [Ch6 | NET]

Q37. Rehashing typically occurs when the load factor exceeds approximately:
Ans: 0.7 [Ch6 | NET]

Q38. Which is TRUE about arrays vs linked lists? (a) Arrays have O(1) insertion in the middle (b) Linked lists have O(1) random access (c) Arrays have O(1) random access, linked lists have O(1) insertion given a pointer (d) Both are identical in performance
Ans: (c) [Ch1 | JRF]

Q39. A B-Tree is primarily used for: (a) In-memory sorting (b) Database indexing / minimizing disk I/O (c) Graph traversal (d) Hashing
Ans: (b) [Ch2 | NET]

Q40. Which notation gives a LOWER bound on an algorithm's growth rate?
Ans: Big-Omega (Ω) [Ch3 | NET]

Q41. T(n) = 3T(n/3) + n. Apply Master Theorem.
Ans: n^(log3 3)=n; f(n)=n matches → Case 2 → T(n)=Θ(n log n) [Ch3 | JRF numerical]

Q42. Which greedy algorithm builds a Minimum Spanning Tree by always adding the cheapest edge without forming a cycle?
Ans: Kruskal's algorithm [Ch4 | NET]

Q43. Which sorting algorithm has the same time complexity — O(n log n) — in best, average, AND worst case, guaranteed?
Ans: Merge Sort (also Heap Sort) [Ch5 | NET]

Q44. Array [8,3,5,1]. After Selection Sort's first pass (place minimum at front), the array is:
Ans: [1,3,5,8] — min=1 swapped to front; the rest happen to already be in order after that. [Ch5 | NET numerical]

Q45. Which is FALSE? (a) Chaining can handle unlimited collisions per slot (b) Open addressing stores all keys directly within the table array (c) Double hashing uses only one hash function (d) Linear probing checks the next sequential slot on collision
Ans: (c) — Double hashing uses TWO hash functions, not one. [Ch6 | JRF]

— End of Mock Test — Cross-check your score, revisit the "Don't Confuse" and "JRF Challenge Zone" boxes for any topic you missed, then re-attempt after 48 hours. —

Share: