optional · CSS study notes
P-I.IV. Algorithms & Data Structures
CSS Computer Science (Optional) — Paper-I, Section-B, Topic IV. Index for Algorithms & Data Structures — matches the textbook's chapter structure exactly, one page per heading.
https://www.tpointtech.com/daa-tutorial https://www.tutorialspoint.com/design_and_analysis_of_algorithms/index.htm
Fundamentals of Algorithms
Lists, Searching & Sorting
Stacks, Queues & Hashing
Recursion, Trees & Graphs
Advanced / Supplementary (beyond this textbook's TOC, kept for extra coverage)
✅ Self-Test Questions (with Answers)
Q1. State the average and worst-case time complexity of Quick Sort, and explain why the worst case occurs.
Ans: Average O(n log n), worst O(n²). The worst case occurs when the pivot is always the smallest or largest element, so each partition splits the array into sizes 0 and n−1 instead of halves — typically when the data is already sorted (or reverse sorted) and the first or last element is chosen as pivot. Recursion depth becomes n, giving n + (n−1) + … = O(n²). Fixes: randomised pivot or median-of-three, which make the worst case very unlikely.
Q2. Differentiate linear probing, bucketing, and chaining as hash-collision resolution strategies.
Ans:
- Linear probing (open addressing): on collision, check the next slot sequentially (h+1, h+2, … mod m). All data lives in the table; simple and cache-friendly, but suffers primary clustering and degrades as the load factor approaches 1.
- Bucketing: each table slot is a fixed-size bucket holding several records; collisions go into the same bucket, with overflow handled separately once the bucket is full.
- Chaining (open hashing): each slot points to a linked list of all keys hashing there. No clustering, load factor may exceed 1, deletion is easy, but it needs extra pointer memory and list traversal.
Q3. Why must Binary Search operate on sorted data, and what is its time complexity?
Ans: At each step it compares the key with the middle element and discards half the remaining range. That decision is only valid if the data is ordered; on unsorted data the discarded half could contain the key. Complexity: O(log₂ n) time, O(1) space iteratively (O(log n) recursively); it needs random access, so it suits arrays rather than linked lists.
Q4. What guarantee does an AVL tree provide over a plain Binary Search Tree?
Ans: An AVL tree is height-balanced: for every node the balance factor (height of left subtree − height of right subtree) is −1, 0 or +1, so its height stays O(log n) and search, insert and delete are guaranteed O(log n). A plain BST has no such guarantee — inserting sorted data degenerates it into a linked list with O(n) operations. The cost is rotations (and balance-factor bookkeeping) on insert and delete.
Q5. Distinguish DES and RSA by key type and typical use case.
Ans: DES is a symmetric block cipher: one shared secret key (56 effective bits, 64-bit blocks, 16 Feistel rounds) for both encryption and decryption. It is fast, so it suits bulk data encryption, but the key must be distributed securely and 56 bits is now breakable (replaced by 3DES/AES). RSA is asymmetric: a public key encrypts and a private key decrypts, with security resting on the difficulty of factoring the product of two large primes. It is far slower, so it is used for key exchange, digital signatures and authentication — typically to exchange a symmetric session key.
Q6. Trace the LL, RR, LR, and RL rotation cases for AVL tree rebalancing.
Ans: Let Z be the lowest unbalanced node (|BF| = 2).
- LL (left-left): insertion in the left subtree of Z's left child → one right rotation about Z.
- RR (right-right): insertion in the right subtree of Z's right child → one left rotation about Z.
- LR (left-right): insertion in the right subtree of Z's left child → left rotation about the left child, then right rotation about Z.
- RL (right-left): insertion in the left subtree of Z's right child → right rotation about the right child, then left rotation about Z.
Single rotations handle the "outside" cases, double rotations the "inside" cases; each restores height O(log n).
Q7. Compare Merge Sort, Quick Sort, and Heap Sort by worst-case time, space, and stability.
Ans:
| Algorithm | Best / Average | Worst | Extra space | Stable? |
|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) stack | No |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
In practice Quick Sort is usually fastest because of small constants and cache behaviour; Merge Sort is preferred when stability or external/linked-list sorting is needed; Heap Sort when guaranteed O(n log n) with no extra memory matters.
Q8. Trace the recoloring/rotation fix for a Red-Black tree insertion when the uncle is red vs. when it's black.
Ans: The new node is inserted red. A violation arises only if its parent is also red.
- Uncle is RED (recolouring case): colour the parent black, the uncle black and the grandparent red; then treat the grandparent as the new problem node and repeat upward. No rotation is needed. If the root becomes red, colour it black (this is the only step that increases black height).
- Uncle is BLACK (rotation case): first, if the new node is an "inside" child (LR or RL), rotate about the parent to convert it to an "outside" case. Then rotate about the grandparent (right rotation for LL, left for RR), colour the node that moves up black and the old grandparent red. After a rotation case the fix terminates — at most two rotations are ever needed for an insertion.
Q9. What two properties must a problem have for a Greedy algorithm to guarantee a globally optimal solution?
Ans: (1) Greedy-choice property — a globally optimal solution can be reached by making a locally optimal choice at each step, without reconsidering it; (2) Optimal substructure — an optimal solution to the problem contains optimal solutions to its subproblems. Both hold for the fractional knapsack, Huffman coding, Kruskal's and Prim's MST and Dijkstra's algorithm (non-negative weights); the 0/1 knapsack lacks the greedy-choice property and needs dynamic programming.
Q10. Is P = NP resolved? What's the practical implication of NP-hardness for an optimization problem?
Ans: No — it remains unresolved, and is one of the Clay Institute's Millennium Prize Problems; most computer scientists believe P ≠ NP. Practically, if an optimisation problem is NP-hard, no polynomial-time exact algorithm is known (and probably none exists), so for large inputs you stop looking for one and instead use approximation algorithms with provable bounds, heuristics and metaheuristics (greedy, genetic algorithms, simulated annealing), exact methods that prune (branch and bound, dynamic programming), or exact solutions only on small or special-case inputs.