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-case O(n) on pathological hash collisions.

2. Linear Data Structures: Stacks, Queues & Linked Lists

  • Stack (LIFO): Supports push and pop in O(1). Evaluates postfix expressions, handles function call call-stacks, and powers Depth First Search (DFS).
  • Queue (FIFO): Supports enqueue at rear and dequeue at front in O(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 is O(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), where h is 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 / m determines 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 yields O(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 (space O(V + E)). Dense graphs (E \approx V^2) benefit from an Adjacency Matrix (space O(V^2) with O(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.