GATE DA — Section 4
Programming, Data Structures & Algorithms
Complete preparation notes for Python programming, core data structures, sorting, search, divide & conquer, and graph traversal algorithms for GATE Data Science & AI.
Official GATE DA Syllabus: Programming in Python; stacks, queues, linked lists, trees, hash tables; linear search and binary search; selection sort, bubble sort, insertion sort; divide and conquer: mergesort, quicksort; introduction to graph theory; traversals and shortest path.
1. Python Programming Core Semantics
GATE tests Python fundamentals rigorously, focusing on variable scope, mutable vs. immutable objects, and slicing semantics:
- Mutability: Numbers, strings, and tuples are immutable. Lists, dictionaries, and sets are mutable. Passing mutable arguments to functions passes by object reference; modifications inside the function mutate the original caller object.
- Slicing:
a[start:stop:step]produces a new shallow copy. Negative steps reverse indices (e.g.,s[::-1]reverses a sequence). - Dictionary & Set Lookup: Hash-table based lookups have average-case
O(1)time complexity, but worst-caseO(n)on pathological hash collisions.
2. Linear Data Structures: Stacks, Queues & Linked Lists
- Stack (LIFO): Supports
pushandpopinO(1). Evaluates postfix expressions, handles function call call-stacks, and powers Depth First Search (DFS). - Queue (FIFO): Supports
enqueueat rear anddequeueat front inO(1). Powers Breadth First Search (BFS) and task scheduling. Circular queues avoid array drift by computing(rear + 1) % capacity. - Linked Lists: Singly and doubly linked lists provide dynamic allocation. Insertion/deletion at a known pointer is
O(1), but element search isO(n)because random access by index is unavailable.
3. Non-Linear Structures: Trees & Hash Tables
- Binary Search Trees (BST): For every node
u, keys in the left subtree are< key(u), and keys in the right subtree are> key(u).- In-order traversal (Left → Node → Right) of a BST outputs elements in strictly ascending sorted order.
- Search, Insert, and Delete take
O(h), wherehis tree height. For balanced BSTs (AVL, Red-Black),h = O(log n); for skewed degenerate trees,h = O(n).
- Hash Tables: Map keys to indices via hash function
h(k). Collisions are resolved via Separate Chaining (linked lists per bucket) or Open Addressing (Linear Probing, Quadratic Probing, Double Hashing). Load factorα = n / mdetermines expected probe cost.
4. Search & Sorting Algorithms Comparison
| Algorithm | Best Time | Average Time | Worst Time | Space | Stable? |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) | Yes |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Bubble Sort | O(n) [optimized] | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) [sorted] | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
5. Divide & Conquer Recurrences (Master Theorem)
For recurrences of the form T(n) = aT(n/b) + O(n^d) where a ≥ 1, b > 1, d ≥ 0:
- If
d < \log_b a→T(n) = \Theta(n^{\log_b a}). - If
d = \log_b a→T(n) = \Theta(n^d \log n)(MergeSort:a=2, b=2, d=1 ⇒ \log_2 2 = 1 = d). - If
d > \log_b a→T(n) = \Theta(n^d).
6. Graph Traversals & Shortest Paths
- Breadth First Search (BFS): Explores vertex-by-vertex level-wise using a FIFO queue. Time complexity:
O(V + E). Finds the shortest path in unweighted graphs. - Depth First Search (DFS): Explores paths deeply using a stack or recursion. Time complexity:
O(V + E). Used for topological sort and cycle detection. - Dijkstra's Algorithm: Computes single-source shortest paths on weighted graphs with non-negative edge weights. Using a min-heap priority queue, running time is
O((V + E) \log V). Fails if negative edge weights exist (use Bellman-Ford instead).
7. Worked Code Trace & Implementation
Worked Trace: Binary Search Iterative Implementation
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2 # prevents integer overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Trace with arr = [3, 8, 14, 21, 35, 42], target = 21:
# Iteration 1: low=0, high=5 -> mid=2 (arr[2]=14 < 21) -> low=3
# Iteration 2: low=3, high=5 -> mid=4 (arr[4]=35 > 21) -> high=3
# Iteration 3: low=3, high=3 -> mid=3 (arr[3]=21 == 21) -> return 3
8. GATE Exam Traps & Common Distractors
- QuickSort Degeneracy: When partitioning around the first or last element of an already sorted array, QuickSort performs
n + (n-1) + \dots + 1 = O(n^2)comparisons. Randomized pivot selection yieldsO(n \log n)expected time. - Stability: A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Selection sort is unstable because long-distance swaps bypass identical intermediate keys.
- Graph Representation: Sparse graphs (
E \ll V^2) require an Adjacency List (spaceO(V + E)). Dense graphs (E \approx V^2) benefit from an Adjacency Matrix (spaceO(V^2)withO(1)edge lookup).
9. Practice & Topic Tracking
Solidify your understanding by solving syllabus-aligned programming questions:
Practice Programming & DSA or review the GATE DA Syllabus Index.