GATE CS & IT Engineering Algorithms Syllabus

Algorithms syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Algorithms in GATE CS & IT Engineering, not a summary of it.

1. 1

   Searching

   2 topics

   • Linear Search
   • Binary Search
2. 2

   Sorting

   2 topics

   • Bubble Sort
   • Merge Sort
3. 3

   Hashing

   2 topics

   • Hash Functions
   • Collision Handling
4. 4

   Asymptotic worst case time and space complexity

   2 topics

   • Time Complexity
   • Space Complexity
5. 5

   Algorithm design techniques

   3 topics

   • Greedy
   • Dynamic Programming
   • Divide-and-Conquer
6. 6

   Graph Traversals

   2 topics

   • Breadth First Search (BFS)
   • Depth First Search (DFS)
7. 7

   Minimum Spanning Trees

   2 topics

   • Kruskal's Algorithm
   • Prim's Algorithm
8. 8

   Shortest Paths

   2 topics

   • Dijkstra's Algorithm
   • Bellman-Ford Algorithm

Algorithms flashcards for GATE CS & IT Engineering

23 of 51 cards from the Algorithms deck — real questions with worked answers.

1. What is Linear Search and what is its worst-case and average-case time complexity?

   Linear Search scans elements one by one from the start until the target is found or the list ends. It works on unsorted data. Worst-case and average-case time complexity are both $O(n)$; best case is $O(1)$.

2. State the precondition for Binary Search and its time complexity.

   The array must be sorted. Binary Search repeatedly halves the search interval, comparing the target to the middle element. Time complexity is $O(\log n)$ in the worst and average case, $O(1)$ best case.

3. Write the recurrence relation for Binary Search and its solution.

   $$T(n) = T\!\left(\frac{n}{2}\right) + O(1)$$ which solves to $T(n) = O(\log n)$.

4. In Binary Search, how is the middle index computed safely to avoid integer overflow?

   Use $mid = low + \frac{high - low}{2}$ instead of $mid = \frac{low + high}{2}$, since the latter can overflow for large $low + high$.

5. Describe how Bubble Sort works.

   Bubble Sort repeatedly steps through the list, comparing adjacent elements and swapping them if they are out of order. After each pass the largest unsorted element 'bubbles' to its correct position. It repeats until no swaps are needed.

6. State the worst-case, average-case, and best-case time complexity of Bubble Sort.

   Worst and average case: $O(n^{2})$. Best case (already sorted, with optimization): $O(n)$. Space complexity: $O(1)$.

7. Is Bubble Sort stable and in-place? Why does stability matter?

   Bubble Sort is both stable (equal elements keep their relative order, since it only swaps strictly out-of-order adjacent pairs) and in-place ($O(1)$ extra space). Stability matters when sorting records by a secondary key.

8. Describe the Merge Sort algorithm and its paradigm.

   Merge Sort is a divide-and-conquer algorithm: it splits the array into two halves, recursively sorts each half, then merges the two sorted halves into one sorted array.

9. Write the recurrence relation for Merge Sort and its solution.

   $$T(n) = 2T\!\left(\frac{n}{2}\right) + O(n)$$ which by the Master Theorem solves to $T(n) = O(n \log n)$.

10. State the time and space complexity of Merge Sort, and whether it is stable.

    Time complexity is $O(n \log n)$ in all cases (best, average, worst). Space complexity is $O(n)$ for the auxiliary array. Merge Sort is stable.

11. In Merge Sort, what is the time complexity of the merge step for two sorted lists of total size $n$?

    The merge step runs in $O(n)$ time, since each element is compared and placed exactly once using two pointers.

12. What is a hash function, and what are the two essential properties of a good one?

    A hash function maps a key to an index in a hash table. A good hash function should be (1) deterministic and fast to compute, and (2) distribute keys uniformly to minimize collisions.

13. What is the division method of hashing? Give its formula.

    The division method computes $h(k) = k \bmod m$, where $m$ is the table size. Choosing $m$ as a prime not close to a power of 2 helps spread keys uniformly.

14. State the multiplication method of hashing.

    $$h(k) = \lfloor m \,(k A \bmod 1) \rfloor$$ where $0 < A < 1$ is a constant (Knuth suggests $A \approx \frac{\sqrt{5}-1}{2} \approx 0.6180$) and $k A \bmod 1$ is the fractional part of $kA$.

15. What is a collision in hashing?

    A collision occurs when two distinct keys $k_1 \neq k_2$ hash to the same index, i.e. $h(k_1) = h(k_2)$.

16. Name the two broad strategies for collision handling.

    (1) Separate chaining (each slot holds a linked list/bucket of entries), and (2) open addressing (probing for another empty slot within the table).

17. Define the load factor of a hash table and give its formula.

    The load factor measures how full the table is: $$\alpha = \frac{n}{m}$$ where $n$ is the number of stored elements and $m$ is the number of slots.

18. What is linear probing, and what problem does it cause?

    Linear probing resolves collisions by checking the next slots sequentially: $h(k, i) = (h'(k) + i) \bmod m$. It causes primary clustering, where long runs of occupied slots form and degrade performance.

19. Write the probe sequence for quadratic probing and the problem it addresses.

    $$h(k, i) = \left(h'(k) + c_1 i + c_2 i^{2}\right) \bmod m$$ It reduces primary clustering but suffers from secondary clustering (keys with the same initial hash follow the same probe sequence).

20. Write the double hashing probe sequence.

    $$h(k, i) = \left(h_1(k) + i \cdot h_2(k)\right) \bmod m$$ where $h_2(k)$ must never be $0$ and should be relatively prime to $m$. Double hashing minimizes clustering.

21. In separate chaining, what is the expected search time under simple uniform hashing?

    Expected time is $O(1 + \alpha)$, where $\alpha$ is the load factor. With $\alpha = O(1)$ (table size proportional to $n$), search, insert, and delete are $O(1)$ on average.

22. Define time complexity (asymptotic) and what Big-O notation represents.

    Time complexity describes how an algorithm's running time grows with input size $n$. Big-O, $O(f(n))$, gives an asymptotic upper bound: $T(n) = O(f(n))$ if $T(n) \leq c \cdot f(n)$ for some constant $c > 0$ and all $n \geq n_0$.

23. Define Big-Omega $\Omega$ and Big-Theta $\Theta$ notation.

    $\Omega(f(n))$ is an asymptotic lower bound: $T(n) \geq c f(n)$ for large $n$. $\Theta(f(n))$ is a tight bound: $T(n) = \Theta(f(n))$ iff $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$ simultaneously.

See more Algorithms flashcards →

Planning Algorithms for GATE CS & IT Engineering

Algorithms (GATE CS & IT Engineering) FAQ