3. Data Structures & Algorithms — Computer Science | CSS Solved Past Papers

FPSC CSS Computer Science past papers (2016–2026) — 63 questions: 16 MCQs, 47 subjective parts. Newest first.

Part A — Subjective Questions

2026 · Paper-I · Q3(b) (6 marks)

Question

What are arrays? Describe one advantage and one limitation.

Solution

An array is a linear data structure that stores a fixed-size, ordered collection of elements of the same data type in contiguous memory locations, where each element can be accessed directly using an index (0-based in most languages such as C/C++/Java).

Advantage: constant-time O(1) random access — because elements are stored contiguously, the address of any element can be computed directly from its index (base_address + index x element_size), so accessing any element takes the same, very fast, constant time regardless of array size or which element is requested.

Limitation: fixed size — once created, an array's size cannot be changed at runtime (in languages with static arrays); if more elements need to be stored than initially allocated, an entirely new, larger array must be created and all elements copied over, which is an expensive O(n) operation. Insertion or deletion in the middle of an array is also costly (O(n)) since subsequent elements must be shifted to keep the array contiguous — unlike a linked list, which handles dynamic growth and mid-list insertion/deletion more efficiently.

2026 · Paper-I · Q5(a) (6 marks)

Question

Why is Binary Search not suitable for an unsorted list?

Solution

Binary search works by repeatedly comparing the target value with the middle element of the current search range and then discarding either the left or right half, based on the assumption that all elements to one side are guaranteed to be smaller (or larger) than the middle element. This decision — which half can safely be eliminated — is only valid if the list is sorted, because sortedness is exactly what guarantees that if the target is greater than the middle element, it cannot possibly exist in the left half (and vice versa).

In an unsorted list, this guarantee does not hold: the target value could be anywhere at all, since there is no ordering relationship between the middle element and the rest of the list. Discarding half the list based on a comparison with the middle element could wrongly eliminate the half that actually contains the target, producing an incorrect 'not found' result even when the value is present. Therefore, binary search requires a sorted list as a precondition; on unsorted data one must instead use linear search (O(n)), or first sort the list (O(n log n)) before applying binary search if repeated searches are needed.

2026 · Paper-I · Q5(b) (6 marks)

Question

What is the difference between Time Complexity and Space Complexity? Explain with examples.

Solution

Time complexity measures how the running time (number of basic operations) of an algorithm grows as a function of the input size n, expressed using asymptotic notation (commonly Big-O). It tells us how execution time scales as input grows larger, independent of the actual hardware speed.

Space complexity measures how much extra memory (working storage, beyond the input itself) an algorithm needs as a function of input size n, also expressed in Big-O notation.

Examples:

Linear search through an array of n elements: time complexity O(n) (in the worst case it checks every element once); space complexity O(1) (it only needs a couple of extra variables regardless of n).
Merge sort on an array of n elements: time complexity O(n log n); space complexity O(n) because it needs an auxiliary array of size n to merge sorted halves.
Recursive Fibonacci (naive): time complexity O(2^n) due to repeated recomputation of subproblems; space complexity O(n) due to the maximum depth of the recursion call stack.

In short: time complexity is about speed (how long it takes), space complexity is about memory usage (how much extra storage it needs) — an algorithm can be fast but memory-hungry (like merge sort) or slow but memory-light (like naive recursive Fibonacci in terms of stack-only usage vs its huge time cost), and algorithm designers often must trade one off against the other.

2026 · Paper-I · Q5(c) (8 marks)

Question

Write an algorithm with an example showing how a stack can be used to evaluate a postfix expression.

Solution

Algorithm (postfix/Reverse-Polish evaluation using a stack):

Function EvaluatePostfix(expression):
    create an empty stack S
    for each token in expression (left to right):
        if token is an operand (number):
            push(S, token)
        else if token is an operator (+, -, *, /):
            operand2 <- pop(S)
            operand1 <- pop(S)
            result <- apply operator to (operand1, operand2)
            push(S, result)
    return pop(S)   // final result remaining on the stack

Example: evaluate the postfix expression 5 3 4 * + (equivalent to infix 5 + 3*4):

Token '5' (operand) → push → Stack: [5]
Token '3' (operand) → push → Stack: [5, 3]
Token '4' (operand) → push → Stack: [5, 3, 4]
Token '' (operator) → pop 4 (operand2), pop 3 (operand1), compute 34=12, push 12 → Stack: [5, 12]
Token '+' (operator) → pop 12 (operand2), pop 5 (operand1), compute 5+12=17, push 17 → Stack: [17]
End of expression → pop and return 17.

Result: 5 3 4 * + evaluates to 17, matching 5 + (3*4) = 5 + 12 = 17. A stack works perfectly here because postfix notation already encodes operator precedence and associativity through ordering, so each operator simply needs its two most-recently-produced operands, which is exactly the Last-In-First-Out behaviour a stack provides — no parentheses or precedence rules need to be evaluated separately.

2026 · Paper-I · Q8(c) (8 marks)

Question

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

The most suitable data structure is a Hash Table.

Comparison of the options:

Array (unsorted): O(n) search, O(1) insertion at the end but O(n) if order/uniqueness must be maintained, O(n) deletion (shifting elements) — far too slow for millions of records with frequent operations.
Array (sorted): O(log n) search via binary search, but O(n) insertion/deletion because elements must be shifted to keep it sorted — insertion/deletion cost is unacceptable at large scale.
Plain Binary Search Tree (BST): average O(log n) search/insert/delete, but with no self-balancing, adversarial or sequential insertion patterns (e.g., product IDs inserted in increasing order) can degrade it to a linked list with O(n) worst-case performance — a serious risk given how product IDs are often generated in near-sorted batches.
AVL Tree: guarantees O(log n) worst-case search, insertion, and deletion by self-balancing via rotations, avoiding the BST's degeneration problem, and uses O(n) memory (one node per key plus a few balance-factor/pointer fields) — a solid choice, but it is still logarithmic, not constant, time.
Hash Table: with a good hash function and load factor maintained (e.g., via dynamic resizing), it achieves average-case O(1) time for search, insertion, and deletion — asymptotically faster than any tree-based structure — and product IDs (often unique identifiers) are naturally excellent hash keys since they map uniformly and don't need any inherent ordering to be searched by ID.

Justification: since the requirement explicitly emphasizes frequent search/insert/delete on an extremely large volume where performance is critical, and there is no stated need to retrieve product IDs in sorted order or do range queries (which would favor AVL/BST), the O(1) average-case operations of a Hash Table give the best practical performance at scale. Its memory overhead (extra space for the hash table array plus handling collisions via chaining/open addressing) is a reasonable, well-understood trade-off for the dramatic average-case speed advantage over the O(log n) alternatives, making Hash Table the most suitable choice here. (An AVL Tree would be the recommended fallback only if the company also needed guaranteed worst-case bounds or sorted/range-based access to product IDs.)

2025 · Paper-I · Q6(a) (6 marks)

Question

What are self-balancing Binary Search Trees? Under what circumstances, the self-balancing Binary Search Trees are preferred over Binary Search Tree?

Solution

A self-balancing Binary Search Tree (e.g., AVL tree, Red-Black tree) is a BST that automatically re-arranges (via rotations) after insertions/deletions to keep its height proportional to O(log n), rather than allowing it to degrade into a skewed, list-like shape. AVL trees enforce a strict balance factor (height difference of left/right subtree ≤ 1 at every node); Red-Black trees use colour properties to bound the height to at most 2·log2(n+1).

A plain (unbalanced) BST can degenerate to O(n) height — and hence O(n) search/insert/delete time — if elements are inserted in sorted or near-sorted order, effectively becoming a linked list.

Self-balancing trees are preferred when:

The data has frequent, unpredictable insertions and deletions and worst-case performance guarantees are required (e.g., real-time systems, databases, language runtime maps/sets).
Input order cannot be controlled and might be sorted/adversarial, which would make a plain BST degenerate.
Consistently fast O(log n) search, insert, and delete is needed regardless of insertion sequence.

A plain BST is acceptable only when data is inserted in a fairly random order or when the tree is built once and rarely modified, since balancing has extra bookkeeping (rotation) overhead.

2025 · Paper-I · Q6(b) (6 marks)

Question

Give pseudocode of implementing Fibonacci sequence recursively. Find the time complexity of this approach and explain how it is calculated.

Solution

Pseudocode:

Function Fibonacci(n):
    if n <= 1:
        return n
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

Time complexity: O(2^n) (exponential).

Explanation: each call to Fibonacci(n) (for n>1) makes two further recursive calls, Fibonacci(n-1) and Fibonacci(n-2), forming a binary recursion tree. Let T(n) be the number of calls; then the recurrence is T(n) = T(n-1) + T(n-2) + O(1), with T(0)=T(1)=O(1). This recurrence has the same structure as the Fibonacci recurrence itself, and its solution grows as O(φ^n) where φ ≈ 1.618 (the golden ratio) — commonly approximated/bounded as O(2^n). The exponential blow-up occurs because the same sub-problems (e.g., Fibonacci(n-3)) are recomputed many times across different branches of the recursion tree instead of being cached, unlike the O(n) achievable with memoization or an iterative/dynamic-programming approach.

2025 · Paper-I · Q6(c) (8 marks)

Question

Suppose you are the owner of a small manufacturing company that delivers goods to customers. During the sale season, you received a huge number of orders. To efficiently manage the orders, you need to sort the packages based on their weights. You are provided with the weights of 10 parcels (in kilograms) as shown below. Use the quick sort method to sort these parcels in ascending order. Weights: [30, 45, 10, 20, 75, 15, 85, 40, 05, 65] Clearly indicate the choice of pivot and reason for it. Provide a graphical representation with explanation at each step.

Solution

Pivot choice: the LAST element of each (sub)array is chosen as pivot (Lomuto partition scheme). Reason: it is simple to implement, needs no extra memory (sorts in place), and gives good average-case O(n log n) performance; it is one of the most common pivot strategies taught and used in practice (often combined with median-of-three in production libraries to avoid worst-case behaviour on already-sorted input).

Array: [30, 45, 10, 20, 75, 15, 85, 40, 5, 65] (indices 0-9)

Level 1 - QuickSort(0,9), pivot = A[9] = 65: Scan and swap all elements <= 65 to the front. Result after partition: [30, 45, 10, 20, 15, 40, 5 | 65 | 85, 75]. Pivot 65 lands at index 7 (its final sorted position). Left part = [30,45,10,20,15,40,5], Right part = [85,75].

Level 2a - QuickSort on right part [85,75], pivot = 75: 85 > 75 so no swap needed except placing pivot; result [75 | 85]. Combined so far: [... , 65, 75, 85] (indices 7,8,9 now sorted).

Level 2b - QuickSort on left part [30,45,10,20,15,40,5] (idx 0-6), pivot = A[6] = 5: every other element (30,45,10,20,15,40) is greater than 5, so pivot swaps straight to the front: [5 | 30,45,10,20,15,40]. Pivot 5 fixed at index 0. Right sub-part to recurse: [30,45,10,20,15,40] (idx 1-6).

Level 3 - QuickSort(1,6), pivot = A[6] = 40, wait — using last element = 40? (careful: after level2b the array is 5,30,45,10,20,15,40) pivot=40; elements <=40 among {30,45,10,20,15}: 30,10,20,15 (45 excluded). Partition gives [30,10,20,15 | 40 | 45], i.e. array indices1-6 become 30,10,20,15,40,45? Actually correctly following Lomuto on [30,45,10,20,15,40]: pivot=40 (last element); scanning: 30<=40 keep,45>40 skip,10<=40 keep,20<=40 keep,15<=40 keep -> after partition pivot 40 placed after all the <=40 elements: result [30,10,20,15,40,45]. Pivot 40 fixed at position (idx5). Left sub-part to recurse: [30,10,20,15] (idx1-4), Right: [45] (idx6, already sorted single element).

Level 4 - QuickSort on [30,10,20,15], pivot = 15 (last element): elements <=15 among {30,10,20}: only 10. Partition -> [10 | 15 | 30,20]. Pivot 15 fixed. Left: [10] (sorted). Right: [30,20] to recurse.

Level 5 - QuickSort on [30,20], pivot = 20: 30>20, so pivot swaps to front: [20 | 30]. Both now sorted singles.

Assembling all fixed pivot positions in order: 5, 10, 15, 20, 30, 40, 45, 65, 75, 85.

Final sorted array (ascending): [5, 10, 15, 20, 30, 40, 45, 65, 75, 85].

2024 · Paper-I · Q3(c) (8 marks)

Question

Write a version of Breadth First Search (BFS) that finds the distances from the start node to each of the others, rather than the actual paths.

Solution

Standard BFS explores a graph level by level from a start node; instead of recording parent pointers (to reconstruct paths), we record, for each node, the number of edges traversed to reach it from the start - since BFS visits nodes in increasing order of distance, this distance is simply one more than the distance of the node it was discovered from.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> bfsDistances(int start, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);   // -1 means unvisited / unreachable
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {          // not yet visited
                dist[v] = dist[u] + 1;    // one more edge than u
                q.push(v);
            }
        }
    }
    return dist;
}

After this runs, dist[v] holds the length of the shortest path (in number of edges, for an unweighted graph) from start to v, or -1 if v is unreachable - achieved in O(V+E) time, the same complexity as ordinary BFS, just tracking distance instead of the parent chain used to reconstruct actual paths.

2024 · Paper-I · Q6(a) (8 marks)

Question

For the following data sets, which sorting algorithms would work well, and which would not? a. 10 floating-point values b. 1,000 integers c. 1,000 names d. 100,000 integers with values between 0 and 1,000 e. 100,000 integers with values between 0 and 1 billion f. 100,000 names g. 1 million floating-point values h. 1 million names i. 1 million integers with uniform distribution j. 1 million integers with non-uniform distribution

Solution

a. 10 floating-point values - very small input: insertion sort works well (simple, low overhead, efficient for small n); complex O(n log n) algorithms add unnecessary overhead here.

b. 1,000 integers - quicksort or mergesort work well (O(n log n)); insertion sort (O(n^2)) is still tolerable at this size but not ideal.

c. 1,000 names (strings) - comparison-based mergesort/quicksort work well; string comparisons cost more per comparison but the total count is still manageable.

d. 100,000 integers, values in [0,1000] - counting sort works EXTREMELY well here (O(n+k) with small k=1000), beating any comparison sort.

e. 100,000 integers, values in [0, 1 billion] - counting sort is impractical (k too large, would need a huge array); use quicksort/mergesort (O(n log n)), or radix sort (works well on fixed-width integers regardless of value range).

f. 100,000 names - mergesort or quicksort (O(n log n)) works well; a good pivot/median strategy avoids quicksort's worst case.

g. 1 million floating-point values - mergesort or an optimized quicksort/introsort (like std::sort) works well at this scale.

h. 1 million names - mergesort (stable, guaranteed O(n log n) worst case) is preferable; MSD radix sort on string prefixes is also a strong option.

i. 1 million integers, uniform distribution - bucket sort works excellently here (uniform distribution is exactly bucket sort's ideal case, giving near O(n) average time); quicksort is also fine.

j. 1 million integers, non-uniform distribution - bucket sort performs POORLY here (buckets fill unevenly, some buckets get almost all elements, degrading toward O(n^2)); better choices are quicksort, mergesort, heapsort, or radix sort, which are not sensitive to the data's distribution.

2024 · Paper-I · Q6(b) (6 marks)

Question

Write an algorithm that implements binary search recursively. Does this version have any advantages or disadvantages compared to the non-recursive version?

Solution

int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high) return -1;               // not found
    int mid = low + (high - low) / 2;
    if (arr[mid] == target)
        return mid;
    else if (target < arr[mid])
        return binarySearchRecursive(arr, low, mid - 1, target);
    else
        return binarySearchRecursive(arr, mid + 1, high, target);
}

Advantages of the recursive version: the code is more concise and directly mirrors the divide-and-conquer logic (search the left half, or the right half), making it arguably easier to read/reason about.

Disadvantages: each recursive call adds a stack frame, so there is function-call overhead and O(log n) extra memory used for the call stack, making it slightly slower and more memory-hungry than the iterative version, which uses only O(1) extra space (just a few local variables) and has no function-call overhead. For very large n, the iterative version is generally preferred in performance-critical code, though O(log n) recursion depth is small enough in practice that stack overflow is not usually a concern.

2024 · Paper-I · Q6(c) (6 marks)

Question

Write an algorithm that deletes a specified cell from a doubly linked list. Draw a picture that shows the process graphically.

Solution

struct Node {
    int data;
    Node* prev;
    Node* next;
};

void deleteNode(Node*& head, Node* delNode) {
    if (head == nullptr || delNode == nullptr) return;

    if (head == delNode)
        head = delNode->next;              // update head if deleting the first node

    if (delNode->next != nullptr)
        delNode->next->prev = delNode->prev;  // bypass delNode from the right

    if (delNode->prev != nullptr)
        delNode->prev->next = delNode->next;  // bypass delNode from the left

    delete delNode;                        // free the memory
}

Graphical process - deleting node B from a list A <-> B <-> C:

Before: [A] <-> [B] <-> [C]

Step 1 (relink around B): A.next is set to C, and C.prev is set to A: [A] -------------> [C] [A] <------------- [C] (B still exists but is now bypassed)

Step 2 (free B): B's own prev/next links are discarded and its memory is released.

After: [A] <-> [C]

This takes O(1) time given a pointer directly to the node to delete, since only a constant number of pointers need updating.

2023 · Paper-I · Q5(a) (8 marks)

Question

For analyzing an Algorithm theoretically & asymptotically, give a detailed note on Input size, unit of time & order of growth. Support your answer with appropriate mathematical equations.

Solution

Input size (n): a measure of the magnitude of the problem instance given to an algorithm - e.g., the number of elements in an array to be sorted, the number of vertices/edges in a graph, or the number of bits in an integer. Running time is expressed as a function of n, T(n), so that algorithms can be compared independent of any specific input instance.

Unit of time: rather than measuring wall-clock seconds (which depend on hardware, compiler, and system load), theoretical analysis counts the number of "basic operations" (comparisons, assignments, arithmetic operations) executed as a function of n. This abstracts away machine-dependent constants and allows algorithms to be compared purely by their operation count, e.g., T(n) = 3n^2 + 5n + 2 basic operations.

Order of growth: describes how T(n) scales as n becomes very large, focusing on the dominant (highest-order) term and ignoring lower-order terms and constant factors, since these become insignificant for large n. This is captured formally using asymptotic notations:

Big-O: T(n) = O(g(n)) if there exist constants c>0, n0 such that T(n) <= c*g(n) for all n >= n0 (upper bound / worst case growth).
Big-Omega: T(n) = Omega(g(n)) for a lower bound.
Big-Theta: T(n) = Theta(g(n)) when both bounds match (tight bound). For example, T(n) = 3n^2 + 5n + 2 has order of growth Theta(n^2), since the n^2 term dominates as n -> infinity.

2023 · Paper-I · Q5(b) (6 marks)

Question

Briefly describe the four types of analysis we may perform to evaluate the asymptotic behavior of an algorithm.

Solution

Worst-case analysis: determines the maximum possible running time over all inputs of size n - guarantees an upper bound that will never be exceeded, most commonly used and reported.
Best-case analysis: determines the minimum possible running time over all inputs of size n - the most favorable input scenario (e.g., an already-sorted array for insertion sort).
Average-case analysis: determines the expected running time averaged over all possible inputs of size n, typically assuming some probability distribution over inputs (e.g., random permutations) - often harder to compute but more representative of typical behavior.
Amortized analysis: determines the average running time per operation over a worst-case sequence of operations on a data structure, rather than a single operation in isolation - useful when occasional expensive operations (e.g., dynamic array resizing) are balanced out by many cheap ones (e.g., total cost of n push_back operations on a dynamic array is O(n), i.e. O(1) amortized per operation, even though a single resizing push_back costs O(n)).

2023 · Paper-I · Q5(c) (6 marks)

Question

Evaluate order of growth of the functions given below. Compare & write down which one has higher, same or lower order of growth than the other one: I. n(n+1) and 2000n^2 II. 100n^2 and 0.01n^3 III. Log2 n and ln n IV. 2^(n-1) and 2^n V. (n-1)! and n!

Solution

I. n(n+1) = n^2 + n, which is Theta(n^2); 2000n^2 is also Theta(n^2). Differing only by constant factors -> SAME order of growth.

II. 100n^2 is Theta(n^2); 0.01n^3 is Theta(n^3). Since n^3 grows faster than n^2 for large n regardless of the constant multipliers, 0.01n^3 has a HIGHER order of growth than 100n^2.

III. log2(n) = ln(n) / ln(2) ~ 1.4427 * ln(n) - the two differ only by the constant factor 1/ln(2), so both are Theta(log n) -> SAME order of growth.

IV. 2^(n-1) = 2^n / 2 = 0.5 * 2^n - differs from 2^n only by the constant factor 0.5, so both are Theta(2^n) -> SAME order of growth.

V. n! = n * (n-1)!, and the ratio n!/(n-1)! = n grows without bound as n increases (not a constant), so n! has a HIGHER order of growth than (n-1)!.

2023 · Paper-I · Q8(c) (6 marks)

Question

What is an Optimization problem? What are its 02 general categories? Write down mathematical representation of a standard optimization problem.

Solution

An optimization problem is a computational problem of finding the best solution - i.e., a solution that maximizes or minimizes a given objective function - from among a (possibly very large) set of feasible solutions that satisfy a set of constraints.

Two general categories:

Continuous optimization: decision variables can take any real (continuous) value within their domain (e.g., linear programming, calculus-based optimization).
Combinatorial (discrete) optimization: decision variables are restricted to discrete values, often chosen from a finite set (e.g., the Knapsack problem, Traveling Salesman Problem, integer programming).

Standard mathematical representation: minimize (or maximize) f(x) subject to: g_i(x) <= 0, for i = 1, ..., m (inequality constraints) h_j(x) = 0, for j = 1, ..., p (equality constraints) x in S (feasible domain, e.g., x in R^n or a discrete set)

where f(x) is the objective function, x is the vector of decision variables, and the constraints g_i, h_j define the feasible region of valid solutions.

2022 · Paper-I · Q3(a) (8 marks)

Question

Complete the C++ code below to find the number of distinct elements in an array in O(n) time (linear time complexity) where "n" is the number of elements in the array. For example, if the array is {3,1,3,8,2,1,8,2}, the number of distinct elements is 4 (to be returned from the function below) as the distinct elements are {1,2,3,8}. All the elements of the array are in the range [1,100]. Also, n >> 100 (n is significantly greater than 100). int numDistinctElements(int[] array, int n) { int count = 0; // write your code here return count; }

Solution

Since all values lie in the fixed small range [1,100], we can use a boolean lookup ("seen") array of size 101 as a direct-address table. Marking an element seen and checking it is O(1), so a single pass over n elements gives O(n) overall time (independent of the constant-size range check), instead of an O(n log n) sort or O(n^2) nested comparison.

int numDistinctElements(int array[], int n)
{
    int count = 0;
    bool seen[101] = {false};   // values are in [1,100]
    for (int i = 0; i < n; i++) {
        if (!seen[array[i]]) {
            seen[array[i]] = true;
            count++;
        }
    }
    return count;
}

For {3,1,3,8,2,1,8,2}, the function marks 3,1,8,2 as seen once each and returns count = 4, as required.

2022 · Paper-I · Q6(c) (4 marks)

Question

Write the time complexity of the following C++ code in terms of Big-O notation. Assume that there is no error in the code. int isPrime (unsigned int n) // returns true if the argument value is prime and false otherwise { for (unsigned int i = 2; (i * i) < n; i++) { // if i is a factor, then not prime if (n % i == 0) return 0; } // if we end loop without finding factor then number must be Prime return 1; }

Solution

The loop increments i starting from 2 and continues while i*i < n, i.e., while i < sqrt(n). In the worst case (n is prime, so the loop never returns early), the loop runs approximately sqrt(n) times, each iteration doing O(1) work.

Time complexity: O(sqrt(n)).

2021 · Paper-I · Q5(a) (8 marks)

Question

What is a tree in data structure? Describe its types with the help of examples.

Solution

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges, with one designated root node and every other node having exactly one parent, forming no cycles. Each node may have zero or more child nodes. Types:

Binary Tree: each node has at most two children (left and right). Example: used as the base structure for many other trees.
Binary Search Tree (BST): a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger, enabling efficient O(log n) average search/insert/delete.
Balanced trees (AVL tree, Red-Black tree): self-balancing BSTs that guarantee O(log n) height even in the worst case by automatically rebalancing on insert/delete.
Heap (Binary Heap): a complete binary tree satisfying the heap-order property (parent ≥/≤ children); used to implement priority queues and heapsort.
B-Tree / B+ Tree: multi-way balanced trees where each node can have many children; used extensively in databases and file systems to minimise disk I/O.
Trie (prefix tree): a tree used for efficiently storing and searching strings by shared prefixes, used in autocomplete/dictionary lookups.

2021 · Paper-I · Q5(c) (6 marks)

Question

Convert following infix notation to prefix (i) (30+23)(43-21)/(84+7) (ii) 2(1+(4*(2+1)+3))

Solution

(i) (30+23)(43-21)/(84+7): Build up recursively: (30+23) → + 30 23 ; (43-21) → - 43 21 ; (84+7) → + 84 7. (30+23)(43-21) → * (+ 30 23) (- 43 21) = * + 30 23 - 43 21 [above] / (84+7) → / (* + 30 23 - 43 21) (+ 84 7) Prefix result: / * + 30 23 - 43 21 + 84 7 Check by evaluation: 30+23=53, 43-21=22, 53*22=1166, 84+7=91, 1166/91 ≈ 12.81 — matches evaluating the original infix expression, confirming correctness.

(ii) 2*(1+(4*(2+1)+3)): (2+1) → + 2 1 4*(2+1) → * 4 + 2 1 (4*(2+1)+3) → + * 4 + 2 1 3 1+(...) → + 1 + * 4 + 2 1 3 2*(...) → * 2 + 1 + * 4 + 2 1 3 Prefix result: * 2 + 1 + * 4 + 2 1 3 Check by evaluation: 2+1=3, 43=12, 12+3=15, 1+15=16, 216=32 — matches the infix expression's value of 32.

2021 · Paper-I · Q6(c) (6 marks)

Question

What is recursion in data structures? Explain three conditions of a recursive function with the help of an example.

Solution

Recursion is a technique where a function solves a problem by calling itself to solve smaller instance(s) of the same problem, until the problem becomes trivial to solve directly. Three essential conditions for a correct recursive function:

Base case — a condition under which the function returns a result directly, WITHOUT making any further recursive call; this stops the recursion.
Recursive case — the function calls itself with a modified (typically smaller/simpler) version of the input, working toward the base case.
Progress toward termination — every recursive call must move the input strictly closer to the base case (e.g. a decreasing parameter), guaranteeing the recursion eventually terminates rather than running forever (stack overflow). Example: factorial(n):

int factorial(int n) {
    if (n == 0) return 1;         // base case
    return n * factorial(n - 1); // recursive case, n decreases toward base case
}

Here n=0 is the base case, each call reduces n by 1 (progress), and the recursive call itself computes factorial(n-1), satisfying all three conditions.

2020 · Paper-I · Q6(a) (7 marks)

Question

John rides a Van service from new square (S) to the city harbor (T). The van service charges Rs 10 per Km. There are numerous routes between the two points. In order to rip off his customers, John always wanted to use the longest path. To find the longest path, John evaluates all the possible paths and selects the longest path. Write an algorithm to select the longest path using this approach.

Solution

Since the general 'longest simple path' problem has no known polynomial algorithm, John's brute-force approach is to enumerate every simple path (no repeated vertices, since a route with a repeated stop is not sensible) from S to T and keep the one with maximum total distance, via backtracking/DFS:

Algorithm LongestPath(Graph G, S, T):
    best <- -infinity
    bestPath <- empty
    visited <- {} 
    function DFS(node, path, distSoFar):
        if node == T:
            if distSoFar > best:
                best <- distSoFar
                bestPath <- path
            return
        mark node visited
        for each neighbor v of node with edge weight w:
            if v not visited:
                DFS(v, path + [v], distSoFar + w)
        unmark node visited   // backtrack
    DFS(S, [S], 0)
    return bestPath, best

This exhaustively tries every possible simple route from S to T, updating the best (longest) one found, backtracking after exploring each branch so every path is considered.

2020 · Paper-I · Q6(b) (3 marks)

Question

Compute the complexity of this algorithm and determine that whether it is in P, NP, or NP-complete.

Solution

This brute-force enumeration explores, in the worst case, all simple paths between two vertices in a graph with V vertices, which can be exponential — up to O(V!) in a dense/complete graph (since every permutation of intermediate vertices could form a distinct simple path), i.e. exponential time O(2^V) or worse, NOT polynomial. The Longest Path problem (decision version: 'is there a simple path of length ≥ k?') is known to be NP-complete in general graphs — it is in NP because a proposed path of length ≥ k can be verified in polynomial time, and it is NP-hard because the Hamiltonian Path problem (NP-complete) reduces to it. So the optimisation version John is solving is NP-hard, and this brute-force algorithm (which visits essentially all such candidate paths) is not a polynomial-time (P) algorithm.

2020 · Paper-I · Q6(c) (7 marks)

Question

Write an algorithm to find a minimum distance between 'S' and 'T'.

Solution

Since edge weights (distance in km) are non-negative, Dijkstra's algorithm efficiently finds the shortest path from S to T:

Algorithm Dijkstra(Graph G, S, T):
    dist[v] <- infinity for all v; dist[S] <- 0
    prev[v] <- undefined for all v
    PQ <- min-priority-queue containing all vertices, keyed by dist
    while PQ not empty:
        u <- vertex in PQ with smallest dist[u]; remove u from PQ
        if u == T: break
        for each neighbor v of u with edge weight w(u,v):
            if dist[u] + w(u,v) < dist[v]:
                dist[v] <- dist[u] + w(u,v)
                prev[v] <- u
                decrease-key of v in PQ to dist[v]
    reconstruct path from T back to S using prev[]
    return path, dist[T]

This greedily settles the vertex with smallest tentative distance at each step and relaxes its neighbours' distances, guaranteeing the shortest S-T path once T is popped/settled.

2020 · Paper-I · Q6(d) (3 marks)

Question

Derive the complexity of this algorithm.

Solution

Using a binary-heap-based priority queue, Dijkstra's algorithm performs V extract-min operations (O(log V) each) and up to E decrease-key operations (O(log V) each), giving a total time complexity of O((V + E) log V). (With a simple array instead of a heap it would be O(V²), which can be faster for very dense graphs but slower for sparse ones.) This is polynomial in the size of the graph, unlike the brute-force longest-path algorithm above.

2020 · Paper-I · Q8(a) (4 marks)

Question

Is P = NP? Comment

Solution

Whether P = NP is one of the most famous unsolved problems in computer science (a Clay Mathematics Institute Millennium Prize Problem). P is the class of decision problems solvable in polynomial time by a deterministic algorithm. NP is the class of decision problems for which a proposed solution ('certificate') can be VERIFIED in polynomial time. It is proven that P ⊆ NP (anything solvable quickly can also be verified quickly), but whether NP ⊆ P — i.e. whether P = NP — remains unproven either way. The overwhelming majority of computer scientists believe P ≠ NP, because thousands of NP-complete problems (SAT, Travelling Salesman, Subset Sum, etc.) have resisted all attempts at a polynomial-time algorithm despite decades of effort, but no one has proved this impossibility. Resolving it would have profound consequences: if P = NP were proven (with a constructive algorithm), it would break most modern public-key cryptography and solve enormous classes of optimisation problems efficiently.

2020 · Paper-I · Q8(b) (7 marks)

Question

Suppose you are representing a social network (such as facebook) as a graph. Devise an algorithm through which you can determine friends of friends.

Solution

Represent the social network as an undirected graph where vertices are users and edges are friendships (adjacency list). To find 'friends of friends' of a given user, perform a breadth-first search restricted to depth 2:

Algorithm FriendsOfFriends(Graph G, user):
    directFriends <- G.neighbors(user)
    result <- empty set
    for each f in directFriends:
        for each f2 in G.neighbors(f):
            if f2 != user and f2 not in directFriends:
                add f2 to result
    return result

This visits each direct friend of user, then each of THEIR friends, collecting anyone who is exactly two hops away and excluding the user itself and existing direct friends (people already friends with user shouldn't be listed as a 'friend of a friend' suggestion).

2020 · Paper-I · Q8(c) (5 marks)

Question

Explain the complexity of this algorithm

Solution

Let d be the average number of friends (degree) a user has. For the given user we examine each of its ~d direct friends, and for each of those we examine ~d of their friends, giving roughly d × d = O(d²) time using adjacency lists (checking membership in directFriends can be made O(1) using a hash set, so it does not add extra asymptotic cost). In the worst case where a user's friends are highly connected hubs with very large degree, this approaches O(V) per friend examined, but for a typical sparse social graph with bounded average degree d, O(d²) is the practical complexity.

2020 · Paper-I · Q8(d) (4 marks)

Question

Optimal problems are generally NP hard problems. Is it appropriate to use heuristics based approaches?

Solution

Yes, it is appropriate and, in practice, usually necessary. Since exact algorithms for NP-hard optimisation problems require (conjectured) exponential time in the worst case, they become infeasible for realistically large inputs. Heuristic and approximation approaches (greedy algorithms, local search, simulated annealing, genetic algorithms, branch-and-bound with pruning) trade the guarantee of finding the provably optimal solution for a solution that is 'good enough' and found in acceptable (typically polynomial) time. For most real applications — e.g. route planning, resource scheduling, network design — a near-optimal answer delivered quickly is far more valuable than a perfect answer that would take longer than the age of the universe to compute for large inputs, making heuristics the pragmatic and standard choice for NP-hard problems at scale.

2019 · Paper-I · Q6(b) (5 marks)

Question

What is AVL tree? Under what condition, a binary tree becomes AVL tree?

Solution

An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one. This difference (height of left subtree − height of right subtree) is called the balance factor, and it must be -1, 0, or +1 for every node. A binary search tree becomes an AVL tree precisely when this height-balance condition holds at every single node of the tree. Whenever an insertion or deletion causes a node's balance factor to fall outside {-1,0,1}, the tree is rebalanced using one of four rotations — Left-Left (single right rotation), Right-Right (single left rotation), Left-Right, or Right-Left (double rotations) — to restore the AVL property. Maintaining this balance guarantees O(log n) height and hence O(log n) search, insertion and deletion in the worst case, unlike an unbalanced BST which can degrade to O(n).

2019 · Paper-I · Q6(c) (5 marks)

Question

Consider the following graph. Find out the sequence of edges added to the minimum spanning tree using Kruskal's algorithm.

Solution

Reading the weighted graph on vertices {a,b,c,d,e,f,g} from the figure gives the edge list: a-b=5, a-c=3, b-d=6, b-e=2, c-d=5, c-f=6, d-e=6, d-f=6, d-g=6, e-g=5, f-g=4. Kruskal's algorithm sorts all edges by ascending weight and adds an edge only if it does not form a cycle with edges already chosen (using a union-find/disjoint-set structure), stopping once (n-1) = 6 edges have been added for the 7 vertices. Sorted edges: b-e(2), a-c(3), f-g(4), a-b(5), c-d(5), e-g(5), b-d(6), c-f(6), d-e(6), d-f(6), d-g(6). Step-by-step selection:

b-e (2) — no cycle, add. Components: {b,e}
a-c (3) — no cycle, add. Components: {a,c}, {b,e}
f-g (4) — no cycle, add. Components: {f,g}, {a,c}, {b,e}
a-b (5) — a in {a,c}, b in {b,e}, different components, add. Components: {a,b,c,e}
c-d (5) — c in {a,b,c,e}, d isolated, different, add. Components: {a,b,c,d,e}
e-g (5) — e in {a,b,c,d,e}, g in {f,g}, different, add. Components: {a,b,c,d,e,f,g} — all 7 vertices connected with 6 edges, MST complete. MST edge order: b-e, a-c, f-g, a-b, c-d, e-g, with total weight = 2+3+4+5+5+5 = 24. (The remaining weight-6 edges are never needed since a spanning tree is already achieved.)

2018 · Paper-I · Q5(b) (5 marks)

Question

What data structure would employ to build a text editor and why?

Solution

A common and effective choice is a Doubly Linked List (or a more advanced structure like a Gap Buffer or a Piece Table, used in real editors), representing each character or line as a node with pointers to the previous and next nodes, plus a 'cursor' pointer marking the current editing position.

Why: text-editing operations are dominated by insertions and deletions at (or near) the current cursor position, not random access by index. A doubly linked list allows insertion/deletion of a character/line at the cursor position in O(1) time (given a pointer to that position), unlike an array/string, which requires O(n) shifting of all subsequent elements for every insertion or deletion. The 'doubly' linked (both forward and backward pointers) aspect additionally allows efficient cursor movement in both directions (moving left/right, or undoing an edit) without needing to re-traverse from the start.

(In practice, production editors often use a Gap Buffer - an array with a movable 'gap' at the cursor position - or a Piece Table, since these give even better cache locality and performance than a plain linked list, but a linked list captures the fundamental reasoning: cheap localized insert/delete near a cursor is the dominant requirement.)

2018 · Paper-I · Q5(c) (7 marks)

Question

Random insertion of nodes into a binary search tree would result in what types of tree shape. Elaborate.

Solution

If keys are inserted into a Binary Search Tree in a RANDOM order (each of the n! possible insertion orderings equally likely), the resulting tree is, on average, reasonably well-balanced: the expected height of a randomly-built BST is O(log n) - specifically, it is known to be approximately 2 ln(n) = O(log n) in expectation, and the expected search/insert/delete cost is also O(log n).

This is because random insertion order tends to place roughly half the keys smaller and half larger than the root at each level, on average, similar to how randomized quicksort's average case behaves well despite no explicit balancing.

However, this is only an AVERAGE-case guarantee, not a worst-case guarantee: for any specific unlucky insertion order (particularly if keys are inserted in already-sorted, ascending or descending order), the tree degenerates into a completely skewed, linked-list-like shape with height O(n), giving O(n) worst-case search/insert/delete time.

This is precisely why, in practice, applications requiring guaranteed worst-case O(log n) performance regardless of insertion order use self-balancing trees (AVL trees, Red-Black trees) instead of relying on a plain BST and hoping for a favourable (random) insertion order.

2018 · Paper-I · Q5(d) (5 marks)

Question

How would you modify a link list based queue so that first and last node can be accessed in a constant time regardless of data nodes in the queue?

Solution

Maintain two separate pointers as part of the queue's structure at all times: a front pointer (always pointing to the first/head node, used for dequeue operations) and a rear/tail pointer (always pointing to the last node, used for enqueue operations) - instead of only keeping a single head pointer and traversing the whole list to find the last node whenever an insertion is needed.

Implementation details:

Enqueue (insert at rear): create the new node, set rear->next = newNode (if queue is non-empty), then update rear = newNode. If the queue was empty, also set front = newNode. This is O(1).
Dequeue (remove from front): save front, update front = front->next, delete the saved node. If the queue becomes empty, also reset rear = nullptr. This is O(1).

With both front and rear pointers explicitly maintained and updated on every insertion/deletion, both ends of the queue are always accessible directly in O(1) time, regardless of how many nodes are in the queue - avoiding the O(n) traversal that would otherwise be needed to locate the last node from a singly-tracked head pointer alone.

2018 · Paper-I · Q6(a) (4 marks)

Question

Define balanced tree both for AVL and Binary search tree.

Solution

Balanced AVL Tree: a self-balancing Binary Search Tree in which, for EVERY node, the balance factor - defined as (height of left subtree - height of right subtree) - is restricted to be exactly -1, 0, or +1. Whenever an insertion or deletion causes any node's balance factor to fall outside this range, the tree performs rotations (single or double: LL, RR, LR, RL) to restore balance. This guarantees the tree's height stays O(log n).

Balanced Binary Search Tree (general sense): more loosely, a BST is considered 'balanced' if its height is O(log n) relative to the number of nodes n - i.e., the left and right subtrees of every node have roughly comparable heights/sizes, so no single root-to-leaf path is disproportionately longer than others. A plain BST has no formal guarantee or enforcement mechanism for this (it depends entirely on the order keys were inserted), whereas AVL trees (and Red-Black trees) are specific, self-enforcing structures that formally guarantee balance via a precise, checkable invariant (the balance-factor rule, for AVL) after every operation.

2018 · Paper-I · Q6(c) (5 marks)

Question

Differentiate between graph and trees. Which is special case of the other?

Solution

Tree: a hierarchical, connected, acyclic data structure with exactly one node designated as the root, exactly one path between any two nodes, and n nodes always having exactly n-1 edges. Every node (except the root) has exactly one parent. Trees model strictly hierarchical relationships (e.g. file-system directories, org charts).

Graph: a more general structure consisting of a set of vertices (nodes) and a set of edges connecting pairs of vertices, with NO restriction on cycles, connectivity, or the number of paths between two nodes - a graph may be cyclic, disconnected (multiple components), directed or undirected, and a node can have any number of connections/relationships to other nodes (no single 'parent' concept).

Key differences:

Cycles: trees cannot contain cycles; graphs can.
Connectivity/paths: trees have exactly one unique path between any two nodes; graphs may have multiple paths, or none at all, between two nodes.
Edge count: a tree with n nodes always has exactly n-1 edges; a graph can have any number of edges (from 0 up to n(n-1)/2 for a simple undirected graph).
Hierarchy: trees have a defined root and parent-child structure; graphs have no inherent hierarchy.

Which is a special case of the other: A Tree is a special case of a Graph - specifically, a tree is a connected, acyclic (undirected) graph. Every tree is a graph, but not every graph is a tree (a graph becomes a tree only if it satisfies the additional constraints of being connected and having no cycles).

2017 · Paper-I · Q5(a) (8 marks)

Question

Draw and build a Red-black tree for the following keys (50, 60, 70, 80, 90) and (50, 40, 30, 20, 10). Would a binary tree be suitable for the insertion of these keys?

Solution

Sequence 1 (50,60,70,80,90) - ascending insert into an empty RB-tree: 50 -> root (Black). 60 -> right of 50 (Red); no violation (parent Black). 70 -> right of 60: red-red violation, uncle(50's other child)=NIL(Black), Right-Right case -> left-rotate at 50, recolor -> tree: 60(B), left=50(R), right=70(R). 80 -> right of 70(Red): parent 70 Red -> violation, uncle=50(Red) -> recolor: 70->Black, 50->Black, 60 stays root(Black). Tree: 60(B)[50(B), 70(B)[80(R)]]. 90 -> right of 80(Red): parent 80 Red -> violation, uncle=70's other child=NIL(Black), Right-Right case at grandparent 70 -> left-rotate at 70, recolor -> 80 becomes Black with children 70(R) and 90(R). Final tree 1: 60(B) /
50(B) 80(B) /
70(R) 90(R)

Sequence 2 (50,40,30,20,10) - descending insert into an empty RB-tree (mirror image of sequence 1): 50->root(B). 40->left(R). 30-> Left-Left case -> right-rotate at 50, recolor -> 40(B)[30(R),50(R)]. 20-> uncle(50) Red -> recolor: 30->B,50->B, root 40 stays B. 10-> Left-Left case at grandparent 30 -> right-rotate at 30, recolor -> 20 becomes Black with children 10(R) and 30(R). Final tree 2: 40(B) /
20(B) 50(B) /
10(R) 30(R)

Would a plain (unbalanced) Binary Search Tree be suitable? No. Inserting keys that are already in ascending or descending sorted order into an ordinary BST (without rebalancing) produces a completely skewed tree - effectively a linked list (each new key becomes the only child of the previous one), giving O(n) height instead of O(log n). Search/insert/delete then degrade to O(n) time. This is exactly why a self-balancing structure like a Red-Black tree (which uses rotations and recoloring to guarantee O(log n) height regardless of insertion order) is preferred for such sorted/adversarial input patterns.

2017 · Paper-I · Q5(b) (6 marks)

Question

Hash tables enable for fast insertion and searching within the database. Describe the process of hashing with a suitable example.

Solution

Hashing maps a key to an array index using a hash function h(key), allowing average-case O(1) insertion, deletion and search, since the location of a record can be computed directly instead of being searched for.

Process:

Choose a hash table of size m (an array of m buckets/slots).
Define a hash function h(key) that maps any key to an index in the range [0, m-1] - a common simple choice is h(key) = key mod m.
To insert a key: compute index = h(key), and place the record at table[index].
To search for a key: compute index = h(key) and look directly at table[index].
Collision handling: since different keys may map to the same index (a collision), a collision-resolution strategy is needed - e.g. Chaining (each slot holds a linked list of all keys hashing there) or Open Addressing (probe for the next free slot, e.g. linear probing: index, index+1, index+2, ...).

Example: table size m=7, keys to insert: 15, 22, 9. h(key)=key mod 7. h(15)=15 mod 7=1 -> slot1. h(22)=22 mod 7=1 -> collision with 15! Using chaining, 22 is appended to the list at slot1; using linear probing, 22 is placed at slot2 (next free slot). h(9)=9 mod 7=2 -> if using chaining, placed directly at slot2; if linear probing was used above (22 at slot2), 9 would probe to slot3. This illustrates both the O(1) average-time benefit and the need to handle collisions properly to keep performance good.

2017 · Paper-I · Q5(c) (6 marks)

Question

Describe the process of Bubble Sorting. Write down the output after each pass of the Bubble Sort algorithm for sorting the sequence (3, 8, 2, 6, 1, 10).

Solution

Bubble Sort repeatedly steps through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order; this process is repeated (each full pass 'bubbles' the largest remaining unsorted element to its correct position at the end) until a full pass makes no swaps, meaning the list is sorted. Worst/average-case time complexity O(n^2), best case (already sorted, with an early-exit flag) O(n).

Trace for (3, 8, 2, 6, 1, 10): Initial: 3, 8, 2, 6, 1, 10

Pass 1: compare & swap adjacent out-of-order pairs -> 3,2,6,1,8,10 (3,8)ok; (8,2)swap->3,2,8,6,1,10; (8,6)swap->3,2,6,8,1,10; (8,1)swap->3,2,6,1,8,10; (8,10)ok. After Pass 1: 3, 2, 6, 1, 8, 10

Pass 2: (3,2)swap->2,3,6,1,8,10; (3,6)ok; (6,1)swap->2,3,1,6,8,10; (6,8)ok; (8,10)ok. After Pass 2: 2, 3, 1, 6, 8, 10

Pass 3: (2,3)ok; (3,1)swap->2,1,3,6,8,10; (3,6)ok; (6,8)ok; (8,10)ok. After Pass 3: 2, 1, 3, 6, 8, 10

Pass 4: (2,1)swap->1,2,3,6,8,10; (2,3)ok; (3,6)ok; (6,8)ok; (8,10)ok. After Pass 4: 1, 2, 3, 6, 8, 10 - no swaps needed on a further pass, so the list is now fully sorted.

2017 · Paper-I · Q8(f) (5 marks)

Question

Write short notes on any FOUR of the following (5 each): (f) Searching Algorithms

Solution

Searching algorithms locate a target value (key) within a data structure. The two fundamental classic algorithms:

Linear (Sequential) Search: examines each element of the array/list one at a time, from the beginning, until the target is found or the list ends. Works on both sorted and unsorted data. Time complexity: O(n) worst/average case, O(1) best case (target is first element). Simple to implement, no pre-processing required.

Binary Search: requires the data to be sorted; repeatedly compares the target with the middle element of the current search range - if equal, found; if the target is smaller, search the left half; if larger, search the right half; the search range halves each step. Time complexity: O(log n), far more efficient than linear search for large sorted datasets, but requires the overhead of keeping data sorted.

Other important searching approaches: Hashing (average O(1) lookup via a hash function, discussed separately), Interpolation Search (an improvement on binary search for uniformly distributed sorted data, estimating the likely position rather than always picking the midpoint), and tree-based searches (e.g. searching a Binary Search Tree, O(log n) average, O(n) worst case if unbalanced), and graph-search algorithms (BFS/DFS) for searching within graph/tree structures rather than linear arrays.

2016 · Paper-I · Q5(a) (8 marks)

Question

Describe the followings (no description with more than three lines); i. Sibling Nodes ii. Degree of a tree iii. Leaf Node iv. Height/Depth of a tree v. Binary Tree vi. Full Binary Tree vii. Complete Binary Tree viii. Maximum number of nodes in a Binary Tree at level L.

Solution

i. Sibling Nodes: Nodes that share the same immediate parent node in a tree. ii. Degree of a tree: The maximum number of children possessed by any node in the tree. iii. Leaf Node: A node that has no children (also called a terminal node). iv. Height/Depth of a tree: Height is the number of edges on the longest path from the root to a leaf; depth of a node is the number of edges from the root to that node. v. Binary Tree: A tree in which every node has at most two children, conventionally called left and right. vi. Full Binary Tree: A binary tree in which every node has either exactly 0 or exactly 2 children (never just one). vii. Complete Binary Tree: A binary tree in which every level is completely filled except possibly the last, which is filled strictly from left to right. viii. Maximum nodes at level L: 2^L, where the root is at level 0 (so level 0 has at most 1 node, level 1 at most 2, level 2 at most 4, etc.).

2016 · Paper-I · Q5(b) (6 marks)

Question

Find the time complexity of Binary search by resolving the recurrence (given below) using iterative substitution method. T(1) = 2 if n =< 1 T(n) = 4 + T(n/2) if n>1

Solution

Expand T(n) repeatedly by substitution: T(n) = 4 + T(n/2) = 4 + [4 + T(n/4)] = 2(4) + T(n/4) = 2(4) + [4 + T(n/8)] = 3(4) + T(n/8) = ... = k(4) + T(n/2^k)

The recursion bottoms out when n/2^k = 1, i.e. k = log2(n).

Substituting k = log2(n): T(n) = 4log2(n) + T(1) = 4log2(n) + 2

Dropping constants and lower-order terms for asymptotic notation: T(n) = O(log n)

This confirms the well-known result that Binary Search runs in logarithmic time, since each comparison halves the remaining search space.

2016 · Paper-I · Q5(c) (6 marks)

Question

Draw the given array in the form of binary tree. Then apply 'Build-Heap' Algorithm to convert the given tree in the form of Max-Heap (i.e. draw final Max-heap in the form of tree and array). Finally show execution of 'Heap-sort' algorithm by rewriting the Heap array after each iteration of the algorithm. A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7}

Solution

Initial array (as a complete binary tree, index i's children are 2i+1, 2i+2): A = [8,14,2,26,10,12,16,28,20,7]

Build-Max-Heap (heapify from last internal node, index 4, down to 0):

i=4 (10): child(7). 10>7, no change.
i=3 (26): children(28,20). Largest child 28 > 26 -> swap: [8,14,2,28,10,12,16,26,20,7]
i=2 (2): children(12,16). Largest 16 > 2 -> swap: [8,14,16,28,10,12,2,26,20,7]
i=1 (14): children(28,10). 28>14 -> swap -> [8,28,16,14,10,12,2,26,20,7]; sift-down at new position(index3=14): children(26,20); 26>14 -> swap -> [8,28,16,26,10,12,2,14,20,7]
i=0 (8): children(28,16). 28>8 -> swap -> [28,8,16,26,10,12,2,14,20,7]; sift-down (index1=8): children(26,10); 26>8 -> swap -> [28,26,16,8,10,12,2,14,20,7]; sift-down (index3=8): children(14,20); 20>8 -> swap -> [28,26,16,20,10,12,2,14,8,7]

Final Max-Heap array: [28,26,16,20,10,12,2,14,8,7] Final Max-Heap tree: 28 /
26 16 / \ /
20 10 12 2 /
14 8 / 7

Heap-Sort (repeatedly swap root with last element of the current heap, shrink heap size by 1, then sift-down the new root): Heap: [28,26,16,20,10,12,2,14,8,7] (size 10)

swap(28,7): [7,26,16,20,10,12,2,14,8,28] -> heapify -> [26,20,16,14,10,12,2,7,8] + sorted[28]
swap(26,8): [8,20,16,14,10,12,2,7,26,28] -> heapify -> [20,14,16,8,10,12,2,7] + sorted[26,28]
swap(20,7): [7,14,16,8,10,12,2,20,26,28] -> heapify -> [16,14,12,8,10,7,2] + sorted[20,26,28]
swap(16,2): [2,14,12,8,10,7,16,20,26,28] -> heapify -> [14,10,12,8,2,7] + sorted[16,20,26,28]
swap(14,7): [7,10,12,8,2,14,...] -> heapify -> [12,10,7,8,2] + sorted[14,16,20,26,28]
swap(12,2): [2,10,7,8,...] -> heapify -> [10,8,7,2] + sorted[12,14,16,20,26,28]
swap(10,2): [2,8,7,...] -> heapify -> [8,2,7] + sorted[10,12,14,16,20,26,28]
swap(8,7): [7,2,...] -> heapify -> [7,2] + sorted[8,10,12,14,16,20,26,28]
swap(7,2): [2,7] -> heap size 1, done.

Final sorted array (ascending): [2, 7, 8, 10, 12, 14, 16, 20, 26, 28]

2016 · Paper-I · Q6(a) (8 marks)

Question

Write Abstract Data Types (ADT) of Stack and Queue. Include the specifications of Add, Delete, IsEmpty, IsFull functions along with their respective functions.

Solution

ADT Stack (LIFO - Last In First Out): Objects: a finite ordered list of elements of the same type, with one end designated as the 'top'. Operations:

Push(item): Add() - inserts item at the top of the stack; precondition: stack not full; postcondition: item becomes new top.
Pop(): Delete() - removes and returns the top item; precondition: stack not empty; postcondition: the element below becomes the new top.
IsEmpty(): returns true if the stack has zero elements (top == -1), else false.
IsFull(): returns true if the stack has reached its maximum capacity (top == MAXSIZE-1), else false.
Peek()/Top(): returns the top element without removing it.

ADT Queue (FIFO - First In First Out): Objects: a finite ordered list of elements with two ends - 'front' (for removal) and 'rear' (for insertion). Operations:

Enqueue(item): Add() - inserts item at the rear; precondition: queue not full.
Dequeue(): Delete() - removes and returns the item at the front; precondition: queue not empty.
IsEmpty(): returns true if front == rear (no elements), else false.
IsFull(): returns true if rear has reached MAXSIZE (or, in a circular queue, if the next rear position equals front), else false.
Peek(): returns the front element without removing it.

2016 · Paper-I · Q6(b) (6 marks)

Question

For step count expressions n2 + 10 and 2n / 4 find breakeven point i.e. for which value of n (starting from 1,2...) second expression will become greater than value of first expression.

Solution

We compare f(n) = n^2 + 10 with g(n) = 2^n / 4 for n = 1, 2, 3, ...

n=1: g=0.5, f=11 -> g<f n=2: g=1, f=14 -> g<f n=3: g=2, f=19 -> g<f n=4: g=4, f=26 -> g<f n=5: g=8, f=35 -> g<f n=6: g=16, f=46 -> g<f n=7: g=32, f=59 -> g<f n=8: g=64, f=74 -> g<f n=9: g=128, f=91 -> g>f (128 > 91)

The breakeven point is n = 9: this is the first value of n at which 2^n/4 exceeds n^2 + 10. This is expected asymptotically since exponential growth (2^n) eventually overtakes polynomial growth (n^2) for large enough n.

2016 · Paper-I · Q6(c) (6 marks)

Question

In AVL tree balance factor of every node is -1 or 0 or +1. We can calculate the balance factor as Height left-sub-tree - Height right-sub-tree. Construct AVL tree from the given data; A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7}

Solution

Inserting one key at a time (standard BST insertion) and rebalancing whenever a node's balance factor goes outside {-1,0,+1}:

8, 14, 2, 26, 10 insert without rotation (tree stays balanced). Insert 12: causes an imbalance at node 8 (BF=-2), with right child 14 being left-heavy (BF=+1) -> Right-Left (RL) case: rotate right at 14, then rotate left at 8. Insert 16, 28: no rotation needed (tree stays balanced). Insert 20: causes imbalance at node 14 (BF=-2), right child 26 left-heavy -> RL case again: rotate right at 26, then rotate left at 14. Insert 7: causes imbalance at node 8 (BF=+2), left child 2 right-heavy (BF=-1) -> Left-Right (LR) case: rotate left at 2, then rotate right at 8.

Final balanced AVL tree: 10 /
7 16 / \ /
2 8 14 26 /
20 28

Balance factors of every node are within {-1,0,+1}: node10 BF=-1(heights2,3), node7 BF=0, node16 BF=0, node2 BF=0, node8 BF=0, node14 BF=1, node26 BF=0, node20/28 BF=0 - confirming a valid AVL tree.

2016 · Paper-II · Q7(a) (6 marks)

Question

Write down a short note on Array versus Matrix Operations

Solution

An array is a linear, homogeneous collection of elements stored in contiguous memory, accessed via a single index (a[i]); a matrix is essentially a 2-dimensional array, accessed via two indices (a[i][j]), representing rows and columns, and is the natural structure for representing mathematical/tabular data.

Array operations: traversal, insertion/deletion (with shifting), searching (linear/binary), and sorting - all operate on a single dimension in O(n) or O(log n) time depending on the operation.

Matrix operations are richer because of the two-dimensional structure:

Addition/Subtraction: element-wise, requires matrices of the same dimensions, O(m*n).
Multiplication: requires columns of the first matrix to equal rows of the second; result element (i,j) is the dot product of row i and column j; standard algorithm is O(mnp) for an m x n by n x p multiplication.
Transpose: swap rows and columns, O(m*n).
Traversal: often needs nested loops (row-major or column-major order) instead of a single loop.

In memory, a matrix is usually stored as a 1-D array internally (row-major or column-major layout), with the address of a[i][j] computed via a formula, which is why matrix operations, though conceptually 2-D, ultimately reduce to array-style linear memory access with index arithmetic.

Part B — MCQs

2026 · Paper-I · Q11 (MCQ)

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

Answer: B

Explanation: Algorithm efficiency is formally measured by its time complexity (how running time grows with input size) and space complexity (how memory usage grows), independent of superficial factors like code length.

2026 · Paper-I · Q12 (MCQ)

In Hash Tables, what is a collision resolution technique?

A. Linear Search
B. Binary Search
C. Chaining
D. None of these

Answer: C

Explanation: Chaining resolves hash collisions by storing all keys that hash to the same slot in a linked list (or similar structure) at that slot, one of the two classic collision-resolution techniques (the other being open addressing).

2025 · Paper-I · Q1 (MCQ)

What is the degree of leaf node in a tree?

A. 0
B. 1
C. 2
D. None of these

Answer: A

Explanation: A leaf node has no children, and the degree of a node equals its number of children, so a leaf always has degree 0.

2025 · Paper-I · Q10 (MCQ)

What is the correct data structure for implementing Huffman algorithm?

A. Priority queue
B. Linked list
C. Binary Tree
D. None of these

Answer: A

Explanation: Huffman coding repeatedly extracts the two lowest-frequency nodes to merge them, an operation efficiently supported by a min-priority queue (typically implemented as a min-heap).

2025 · Paper-I · Q11 (MCQ)

Which asymptotic notation gives the strict upper bound for a function?

A. Omega notation
B. Big O notation
C. Theta notation
D. None of these

Answer: B

Explanation: Big-O notation describes the asymptotic upper bound of a function's growth rate, while Omega gives the lower bound and Theta gives a tight (both) bound.

2025 · Paper-I · Q12 (MCQ)

Which one of the following is the fastest way of searching for a given key?

A. Sorted array
B. Linked list
C. Binary search tree
D. None of these

Answer: D

Explanation: A hash table gives average O(1) search time, which beats binary search on a sorted array (O(log n)), a balanced BST (O(log n)) and a linked list (O(n)); since hashing is not listed, the correct choice is 'None of these'.

2025 · Paper-I · Q16 (MCQ)

The process of deleting an element from an empty stack is called:

A. Overflow
B. Deletion
C. Underflow
D. None of these

Answer: C

Explanation: Attempting to pop from an empty stack is called stack underflow, the counterpart to overflow (pushing onto a full stack).

2025 · Paper-I · Q17 (MCQ)

How is the head node deleted in a doubly circular linked list?

A. By adjusting the prev pointer of the new head node to null.
B. By setting the next pointer of prev node to point to new head.
C. By pointing the next pointer of last node to null.
D. None of these

Answer: B

Explanation: In a circular list the tail node's next pointer must keep pointing to the new head (never null, since the list stays circular); this is achieved by updating the tail's ('prev' node's) next pointer to the new head node.

2025 · Paper-I · Q18 (MCQ)

Which technique works by selecting the local optimal choice at each step?

A. Dynamic Programming
B. Divide and Conquer
C. Greedy Algorithm
D. None of these

Answer: C

Explanation: Greedy algorithms build a solution by always making the choice that looks best at the current step, hoping it leads to a globally optimal solution.

2025 · Paper-I · Q19 (MCQ)

What is the time complexity of searching for an element in a hash table?

A. O (1)
B. O (n)
C. O (nlogn)
D. None of these

Answer: A

Explanation: With a good hash function and load factor, a hash table gives constant average-case time O(1) for search, insert and delete.

2024 · Paper-I · Q17 (MCQ)

When we attempt to add the eleventh element to a stack with a size of 10, we encounter a circumstance known as:

A. Garbage collection
B. Underflow
C. Overflow
D. None of these

Answer: C

Explanation: Attempting to push onto a stack that is already at its maximum capacity causes a stack overflow condition; underflow is the opposite (popping from an empty stack).

2024 · Paper-I · Q18 (MCQ)

Regarding Binary Trees, which of the following is true?

A. Every binary tree has two states: full and complete.
B. Every binary tree that is full is also a complete binary tree.
C. All complete binary trees are likewise full binary trees.
D. None of these

Answer: D

Explanation: Neither statement (A), (B) nor (C) is generally true: a full binary tree (every node has 0 or 2 children) need not be complete (e.g., an unbalanced full tree), and a complete binary tree (levels filled left-to-right) need not be full (a node in the last level can have exactly one child), so the correct choice is None of these.

2024 · Paper-I · Q19 (MCQ)

What is the name of a linear collection of data components where the linear node is provided by a pointer?

A. Linked list
B. Primitive List
C. Node list
D. None of these

Answer: A

Explanation: A linked list is precisely a linear collection of nodes, where each node's linkage to the next is maintained via a pointer, rather than by contiguous memory as in an array.

2024 · Paper-I · Q20 (MCQ)

How much time would it take to add an element to the linked list asymptotically?

A. O (1)
B. O (n)
C. O (n2)
D. None of these

Answer: A

Explanation: Inserting an element at a known position (such as the head, or given a pointer to the node after which to insert) in a linked list only requires updating a constant number of pointers, making it an O(1) operation.

2024 · Paper-II · Q3 (MCQ)

Making a system store data in memory contiguously would:

A. Results in lesser computation while searching for data
B. Results in more computation while searching data
C. Makes storing data very easy as one doesn't have to search for available memory to store
D. None of these

Answer: A

Explanation: Contiguous storage (as in arrays) allows direct index-based addressing and better cache locality, reducing the computation needed to locate/access an element compared to scattered (non-contiguous) storage.

2024 · Paper-II · Q5 (MCQ)

The time complexity of finding a shortest path in a network is:

A. Fairly low with Dijkstra's algorithm
B. Very efficient with A* search given spatial heuristics
C. Better than the above two using some randomization mechanism in large networks
D. None of these

Answer: A

Explanation: Dijkstra's algorithm finds shortest paths in a graph with non-negative weights efficiently, in O((V+E) log V) with a priority queue, which is considered fairly low/efficient for this problem.