Programming and Data Structures

Data types, operators and expressions

What a C value really is (a fixed number of bits), how operands are converted before every operation, and the precedence and overflow rules that GATE expression questions are built on.

Control flow and loops

How a C program chooses and repeats: if and else (and the dangling else), while, do-while and for, break and continue, switch with its fall-through, short-circuit evaluation of && and ||, the pitfalls (assignment in a condition, a stray semicolon, off-by-one), tracing a loop by hand, and counting how many times a body runs.

C memory layout: text, data, heap, stack

The six regions of a running C program's address space, which kind of variable lives in which region, and why that decides lifetime, initial value and whether you may write to it.

Functions and parameter passing

How a C call really works. Arguments are copies, so a function can only change the caller's data if you hand it an address, and arrays are passed as exactly that.

Scope, lifetime and storage classes

Three related but distinct ideas that GATE mixes together. Where a name is visible (scope), how long the object exists (lifetime) and who else can link to it (linkage), plus what auto, static, extern and register change.

Evaluation order, sequence points and undefined behaviour

The four kinds of behaviour the C standard distinguishes, the sequence-point rule that makes expressions like i = i++ + ++i meaningless, and how to tell a question that has an answer from one that has none.

Arrays and indexing

An array is one unbroken block of equal-sized cells, and a[i] is just arithmetic on the address of the first cell. Everything GATE asks about arrays (address of an element, partial initialisation, sizeof, shifting, off-by-one) follows from that one fact.

Pointers and pointer arithmetic

A pointer is a variable that holds an address. Learn what &, * and p + 1 really do (p + 1 moves a whole element, not a byte), how *p++ and (*p)++ differ, and which pointer mistakes are undefined behaviour.

Arrays, strings and pointers together

Arrays and pointers look interchangeable in C but are different things. Learn exactly where they differ (sizeof, assignment, &a), how a string is just a char array ending in a zero byte, why modifying a literal is undefined, and the idioms such as while (*d++ = *s++) that exam questions are built from.

Multidimensional arrays and address calculation

Memory is one long line, so a 2-D or 3-D array has to be flattened. Learn row-major and column-major address formulas (with arbitrary bounds), how C declares and passes 2-D arrays, and the index formulas for triangular and tridiagonal matrices that GATE keeps asking for.

Dynamic memory: malloc, free and leaks

How a C program asks for memory while it runs, what malloc, calloc, realloc and free promise, and the catalogue of bugs that follow when the rules are broken (leak, use after free, double free, overflow). Includes how to count leaked blocks in an exam question.

Stack (abstract data type)

A stack lets you add and remove only at one end, so the last item in is the first out. Learn push, pop and peek, the array implementation with a top index (and how the top = -1 versus top = 0 convention changes every answer), overflow and underflow, and the classic GATE question of which output orders a stack can produce.

Queue (abstract data type)

A queue serves items in the order they arrived (first in, first out). Learn the circular array implementation with its two conventions for telling a full queue from an empty one, the formula for the number of items, linked and two-stack queues, and the deque.

Singly linked lists

A linked list is a chain of separately allocated nodes, each holding a value and the address of the next node. Learn the struct, traversal, insertion at the front, end and after a node, why a function that changes the head needs a pointer to the head pointer, and what each operation costs compared with an array.

Linked list operations

The standard things GATE does with singly linked lists: delete by value (head, middle, last), delete a node you only hold a pointer to, reverse (iteratively and recursively), find the middle and the k-th from the end with two pointers, detect and locate a cycle, and merge two sorted lists. Each is traced pointer by pointer and run for real.

Recursion and the call stack

How a function that calls itself actually runs. Frames pile up on the stack while the calls go down, and unwind in reverse as the answers come back.

Recursion patterns

The handful of shapes that nearly every recursive function in an exam has (linear, tail, binary, halving, nested, mutual, backtracking), how to read the output from the order of print and call, how many calls each shape makes, and which recurrence and running time it gives. All examples run for real.

Trees and binary trees

The vocabulary (root, leaf, depth, height, level, degree) and the counting facts GATE keeps using (n nodes have n - 1 edges, leaves = two-child nodes + 1, at most 2^h nodes on level h), the kinds of binary tree (full, complete, perfect, skewed), and how a tree is stored with pointers or in an array. The conventions that differ between books are marked.

Binary tree traversals

The four ways to visit every node of a binary tree (preorder, inorder, postorder, level order), how to read each off a drawing by hand, how the recursion and the explicit stack or queue really work, how many calls they make, and the facts about the three depth-first orders that exam questions use.

Constructing a tree from its traversals

Which pairs of traversals determine a binary tree (inorder with preorder, postorder or level order do; preorder with postorder does not, unless the tree is full), the recursive algorithm that rebuilds the tree, and the counting questions that follow (how many trees share a preorder, how many share a preorder and a postorder).

Counting binary trees

How many binary trees have n nodes (the Catalan number), how many with labels, how many binary search trees, how many full trees, how many trees of a given height, how many heaps and how many insertion orders build one search tree. The recurrence, the closed form, and the tables GATE asks for are all run and checked by programs.

Binary search trees

A binary tree kept in order so that search, insert and delete follow one path from the root. Learn the ordering rule, the three cases of deletion, why the shape (and so the running time) depends on the insertion order, the successor, the k-th smallest, how to rebuild a tree from its preorder, and the common wrong test for whether a tree is a BST.

Binary heaps and heap operations

A complete binary tree stored in an array so that every parent is at least as large as its children (max-heap) or at most as large (min-heap). Learn the index arithmetic, insertion by sifting up, deleting the root by sifting down, deleting any position, the height and leaf facts, where the minimum of a max-heap can hide, and how many different heaps exist.

Priority queues and building a heap

The priority queue as an abstract data type and why a heap implements it best; building a heap from an arbitrary array in linear time (and why repeated insertion costs n log n and gives a different array); heapsort with its cost and its instability; and the standard uses (the k largest keys, merging k sorted lists).

Stack applications: expression evaluation and matching

What a stack is used for. Convert infix to postfix with an operator stack (precedence, associativity, parentheses), evaluate postfix and prefix, build an expression tree, check brackets, find the next greater element and the stock span with a monotonic stack, and keep a running minimum. Includes the counting facts (balanced strings and valid postfix strings are Catalan) and the traps with operand order and stack depth.

Graph representations

How a graph is stored in memory. The adjacency matrix, the adjacency list, the edge list and the incidence matrix, with the space and the time of every common operation (is there an edge, list the neighbours, in-degree, visit all edges, transpose), the degree and edge-count facts GATE uses (handshake, maximum edges, ones in the matrix, nodes in the lists), walks counted by powers of the matrix, and the number of graphs on n labelled vertices.

AVL trees and rotations

A binary search tree that repairs itself: the balance factor and the AVL condition, the four cases LL, RR, LR and RL and their single and double rotations, insertion (at most one repair) and deletion (repairs up to the root), the fewest nodes of an AVL tree of a given height (a Fibonacci recurrence) and the resulting bound of about 1.44 log n on the height, and the cost of building and using AVL trees.