optional · CSS study notes
🔥 Most Repeated — Algorithms & Data Structures
CSS Computer Science (Optional) — Paper-I, Section-B, Topic IV. This is the first year this page has been compiled — all 4 question-patterns below are freshly extracted from the CSS Computer Science Paper-I 2026 exam (the earliest Section-B past paper reviewed for this project so far). More patterns will be added here as further years' Section-B papers are reviewed.
Q1. Why Binary Search Fails on an Unsorted List
Appeared: 2026, Q5(a)
Why is Binary Search not suitable for an unsorted list?
Solution:
Binary Search works by repeatedly comparing the target with the middle element and eliminating one half of the remaining search space — but that elimination step is only valid if the array is sorted, since it relies on the assumption that everything to one side of the midpoint is smaller (or larger) than the midpoint itself. On an unsorted list, the target could be anywhere regardless of how it compares to the midpoint, so discarding a half based on that comparison can wrongly throw away the region that actually contains the target — the algorithm can return "not found" even when the value is present.
- Correctness of Binary Search formally depends on the sorted-order precondition — it is not an optional optimization detail, it is required for the algorithm to work at all.
- Without a sorted list, the only reliable options are: Linear Search (O(n), works on any order), or sort first, then binary search (O(n log n) to sort + O(log n) per search — worthwhile only if many searches will follow).
Q2. Time Complexity vs Space Complexity (with Examples)
Appeared: 2026, Q5(b)
What is the difference between Time Complexity and Space Complexity? Explain with examples.
Solution:
| Aspect | Time Complexity | Space Complexity |
|---|---|---|
| Measures | How the running time grows as input size n grows | How much additional memory is needed as n grows |
| Expressed as | Big-O notation, e.g. O(n), O(log n), O(n²) | Big-O notation over memory units, e.g. O(1), O(n) |
| Includes | Comparisons, loop iterations, recursive calls | Auxiliary variables, extra data structures, recursion call-stack frames |
Example 1 — Linear Search: Time O(n) (may check every element in the worst case); Space O(1) (only a loop index/counter is needed, no extra structures).
Example 2 — Merge Sort: Time O(n log n); Space O(n) (needs an auxiliary array to merge the two halves back together — unlike in-place Quick Sort).
Example 3 — Recursive Factorial(n): Time O(n); Space O(n) — each recursive call pushes a new stack frame, so space grows with recursion depth even though the algorithm creates no explicit array.
Key reasoning point: a fast algorithm (low time complexity) can still be memory-hungry (high space complexity), and vice versa — the two must always be evaluated independently; a common examiner trap is testing whether a candidate conflates "efficient" with only one of the two.
Q3. Stack — Algorithm to Evaluate a Postfix Expression
Appeared: 2026, Q5(c)
Write an algorithm with an example showing how a stack can be used to evaluate a postfix expression.
Solution:
ALGORITHM EvaluatePostfix(expression)
CREATE an empty stack S
FOR each token in expression, left to right:
IF token is an operand (a number):
PUSH token onto S
ELSE IF token is an operator (+, -, *, /):
operand2 <- POP from S
operand1 <- POP from S
result <- operand1 OPERATOR operand2
PUSH result onto S
RETURN POP from S // the final answer
END ALGORITHM
Worked example — evaluate the postfix expression 5 3 4 * + (equivalent to infix 5 + (3 * 4)):
| Token | Action | Stack (bottom → top) |
|---|---|---|
| 5 | push | [5] |
| 3 | push | [5, 3] |
| 4 | push | [5, 3, 4] |
| * | pop 4, pop 3 → 3*4=12 → push | [5, 12] |
| + | pop 12, pop 5 → 5+12=17 → push | [17] |
Result: 17.
Key reasoning points: a stack is the natural fit here because postfix (Reverse Polish) notation needs no parentheses or precedence rules at all — an operator always applies to the two most-recently-seen operands, which is exactly a stack's LIFO (Last-In-First-Out) behavior. The whole evaluation is a single left-to-right pass: O(n) time, one stack as the only auxiliary structure.
Q4. Choosing a Data Structure for Millions of Product IDs (Search, Insert, Delete)
Appeared: 2026, Q8(c)
A company maintains millions of product IDs and frequently performs searching, insertion, and deletion. The data volume is extremely large, and performance is critical. Which data structure would be most suitable—Binary Search Tree, AVL Tree, Hash Table, or Array? Justify your answer logically using time complexity and memory considerations.
Solution:
| Structure | Search | Insert | Delete | Note |
|---|---|---|---|---|
| Array | O(n) unsorted / O(log n) sorted | O(n) (shifting) | O(n) (shifting) | Not suitable at "millions" scale — insert/delete cost dominates |
| Binary Search Tree (unbalanced) | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(log n) average, O(n) worst | Degenerates toward a linked list if IDs arrive in sorted/near-sorted order — unreliable at scale |
| AVL Tree | O(log n) guaranteed | O(log n) guaranteed | O(log n) guaranteed | Self-balancing via rotations; extra memory per node (balance factor) and rotation overhead on every insert/delete |
| Hash Table | O(1) average | O(1) average | O(1) average | Fastest when ordering is not required, given a good hash function and managed load factor |
Recommendation: Hash Table. For pure ID-based search/insert/delete on millions of records where the order of IDs doesn't matter, its O(1) average-case performance beats even an AVL Tree's guaranteed O(log n) — and it is the standard real-world choice for this exact use case (e.g., database index / key-value store lookups by ID).
Caveat — justify both sides: if the application also needs range queries or sorted traversal (e.g., "list all IDs between X and Y"), an AVL Tree would be preferable despite its higher per-operation cost, because a Hash Table cannot efficiently support ordered range queries at all — its buckets have no inherent order. A strong CSS answer states this trade-off explicitly, since "performance critical" alone doesn't specify whether ordering is ever needed.
Frequency Note
Papers reviewed for this topic so far: 2026 only (the first Section-B past paper reviewed for this project). Even from this single year, a clear pattern emerges: one algorithm-tracing/design question (stack/queue usage, or writing pseudocode) and one comparative data-structure justification question ("which structure and why, given these constraints") appear together — expect both formats again in future papers. See the full concept breakdown starting at P-I.IV. Algorithms & Data Structures for deeper coverage of any single topic (sorting, hashing, trees, graphs).
2026 Past Paper MCQs (Part-I)
-
You are analyzing an algorithm's efficiency. What do you consider?
A) Code length B) Time and space complexity C) Programmer's experience D) None of these
Why: these are the two standard, objective measures of algorithmic efficiency — see Q2 above for the full distinction.
-
In Hash Tables, what is a collision resolution technique?
A) Linear Search B) Binary Search C) Chaining D) None of these
Why: each hash-table bucket holds a linked structure of every entry that hashed to the same index; linear/binary search are search algorithms, not collision-resolution techniques (open addressing/linear probing is the other major technique, not listed here).
-
In Recursion, what is crucial to prevent infinite loops?
A) Base case B) Recursive call C) Loop usage D) None of these
Why: the base case is the terminating condition that stops further recursive calls — without one, recursion continues until the call stack overflows.