GATE CS & IT Engineering Programming and Data Structures Syllabus

What are the time complexities of insert, extract-max (delete-max), and build-heap operations on a binary heap?

Insert: $O(\log n)$. Extract-max: $O(\log n)$. Build-heap from an array: $O(n)$ (not $O(n \log n)$, due to the tighter bound on heapify).

In a singly linked list, what is the time complexity to insert a node at the head versus at the tail (no tail pointer)?

Insert at head: $O(1)$. Insert at tail without a tail pointer: $O(n)$, since you must traverse to the last node.

What advantage does a doubly linked list have over a singly linked list?

It allows traversal in both directions and $O(1)$ deletion of a node given only a pointer to it, since each node stores both 'next' and 'prev' pointers.

How does Floyd's cycle detection (tortoise and hare) algorithm detect a loop in a linked list, and what is its complexity?

Two pointers advance, one by 1 step and one by 2 steps; if they ever meet, a cycle exists. It runs in $O(n)$ time and $O(1)$ space.

What is a hash table and what is the average-case time complexity of search/insert/delete?

A hash table maps keys to array indices via a hash function for near-constant access. Average case $O(1)$; worst case $O(n)$ when all keys collide into one bucket.

Distinguish separate chaining from open addressing as collision resolution strategies.

Separate chaining stores colliding keys in a linked list at each bucket. Open addressing stores all keys in the table itself and probes for the next free slot (linear, quadratic, or double hashing).

In open addressing, write the linear probing sequence for a key with hash $h(k)$ in a table of size $m$.

$h(k, i) = (h(k) + i) \bmod m$ for $i = 0, 1, 2, \dots$ The main drawback is primary clustering.

Define the load factor $\alpha$ of a hash table and its significance.

$\alpha = \frac{n}{m}$, where $n$ is the number of stored keys and $m$ the number of slots. It measures fullness; expected probe count grows as $\alpha \to 1$, so resizing (rehashing) is triggered at a threshold.

What is double hashing and why does it reduce clustering compared to linear probing?

It uses a second hash function for the step size: $h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod m$. Different keys get different probe sequences, eliminating primary clustering.

What is the worst-case and average-case time complexity of Quicksort, and when does the worst case occur?

Average $O(n \log n)$; worst case $O(n^{2})$ when the pivot is always the smallest or largest element (e.g., already-sorted input with naive pivot choice).

State the time complexity of Merge Sort in all cases and its space complexity.

Merge Sort is $O(n \log n)$ in best, average, and worst cases. It requires $O(n)$ auxiliary space, making it not in-place.

Which common sorting algorithms are stable, and what does stability mean?

Stability means equal keys retain their original relative order. Stable: Merge Sort, Insertion Sort, Bubble Sort, Counting Sort. Unstable: Quicksort, Heapsort, Selection Sort (in typical implementations).

What recurrence describes Merge Sort, and what is its solution by the Master Theorem?

$T(n) = 2T(n/2) + O(n)$. With $a=2$, $b=2$, $f(n)=n$, this is Case 2 of the Master Theorem, giving $T(n) = O(n \log n)$.

State the Master Theorem cases for $T(n) = aT(n/b) + f(n)$ with $c = \log_b a$.

Compare $f(n)$ with $n^{c}$: if $f(n)=O(n^{c-\epsilon})$ then $T(n)=\Theta(n^{c})$; if $f(n)=\Theta(n^{c})$ then $T(n)=\Theta(n^{c}\log n)$; if $f(n)=\Omega(n^{c+\epsilon})$ (and regularity holds) then $T(n)=\Theta(f(n))$.

What is the time complexity of binary search, and what precondition must the input satisfy?

$O(\log n)$. The input array must be sorted. The recurrence is $T(n) = T(n/2) + O(1)$.

Differentiate Big-O, Big-Omega ($\Omega$), and Big-Theta ($\Theta$) asymptotic notations.

$O$ is an asymptotic upper bound, $\Omega$ is an asymptotic lower bound, and $\Theta$ is a tight bound (both upper and lower, i.e., $f = O(g)$ and $f = \Omega(g)$).

In C, what is the difference between 'char *s = "hello";' and 'char s[] = "hello";'?

The pointer form points to a read-only string literal (modifying it is undefined behavior). The array form creates a modifiable local copy of the characters on the stack.

What does the C expression '*p++' do, given operator precedence?

Postfix ++ binds tighter than dereference, so it parses as $*(p\text{++})$: dereference the current $p$, then increment the pointer $p$ (not the value).

What is dynamic memory allocation in C and which functions perform allocation and deallocation?

Allocating memory on the heap at runtime. malloc/calloc/realloc allocate; free deallocates. malloc leaves memory uninitialized; calloc zero-initializes.

What is a dangling pointer and a memory leak in C?

A dangling pointer references memory that has been freed or gone out of scope. A memory leak is heap memory allocated but never freed, lost when its last pointer is overwritten.

For an array stored in row-major order with base address $B$, element size $w$, dimensions $m \times n$, give the address of $A[i][j]$.

$\text{Address} = B + (i \times n + j) \times w$, assuming 0-based indexing.

What is the time complexity to push and pop in a stack implemented using a linked list?

Both push and pop are $O(1)$, performed at the head of the list, requiring no traversal.

How can a queue be implemented using two stacks, and what is the amortized dequeue cost?

Use an 'in' stack for enqueue and an 'out' stack for dequeue; when 'out' is empty, transfer all elements from 'in' to 'out' (reversing order). Amortized cost per operation is $O(1)$.

What is the maximum number of leaf nodes in a binary tree of height $h$?

$2^{h}$ leaf nodes (the entire last level), occurring in a perfect binary tree with root at height 0.

In a binary tree with $n$ internal nodes (each having exactly 2 children), how many leaf nodes are there?

$n + 1$ leaf nodes. In any full binary tree, the number of leaves equals the number of internal nodes plus one.

What is an AVL tree and what is its balance condition?

An AVL tree is a self-balancing BST where, for every node, the heights of the two child subtrees differ by at most 1 (balance factor $\in \{-1, 0, +1\}$). It guarantees $O(\log n)$ operations.

What graph traversal uses a queue and what does it compute in an unweighted graph?

Breadth-First Search (BFS) uses a queue. It computes the shortest path (fewest edges) from the source to all reachable vertices in an unweighted graph, in $O(V+E)$ time.

What data structure underlies Depth-First Search (DFS), and what is its time complexity using adjacency lists?

A stack (explicit, or the call stack via recursion). DFS runs in $O(V + E)$ time using adjacency lists.

Compare adjacency matrix vs adjacency list representations of a graph in space and edge-lookup time.

Adjacency matrix: $O(V^{2})$ space, $O(1)$ edge lookup. Adjacency list: $O(V + E)$ space, $O(\deg(v))$ edge lookup. Lists are better for sparse graphs, matrices for dense graphs.

What is tail recursion and why is it significant for optimization?

Tail recursion is when the recursive call is the last operation in the function. Compilers can optimize it into a loop (tail-call optimization), reusing the same stack frame and reducing space from $O(n)$ to $O(1)$.