Computer Science संगणकशास्त्र

Quick summary

A data structure is a way of organising and storing data in memory so that it can be used efficiently. Choosing the right data structure makes programs faster and simpler. This topic covers the classification of data structures, abstract data types, basic operations, and analysis of algorithms using time and space complexity and asymptotic notations.

Key points

• Data structure = organised data + allowed operations on it.
• Primitive data structures: int, float, char, pointer (directly supported by the machine).
• Non-primitive: built from primitive ones. Divided into linear (array, stack, queue, linked list – elements in a sequence) and non-linear (tree, graph – hierarchical or network form).
• Static structures have fixed size (array); dynamic structures can grow or shrink at run time (linked list).
• Basic operations: traversal, insertion, deletion, searching, sorting, merging.
• Abstract Data Type (ADT): a logical description of data and operations, without saying how they are implemented. Example: a Stack ADT has push, pop, peek, isEmpty.
• An algorithm is analysed for time complexity (number of steps as a function of input size n) and space complexity (memory needed).
• Cases: best case, average case and worst case. Worst case is used most often because it gives a guarantee.
• Asymptotic notations: Big-O (upper bound), Big-Omega Ω (lower bound), Big-Theta Θ (tight bound).
• Growth order (slow to fast): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
• Time–space trade-off: we can often save time by using more memory, or save memory at the cost of time.
• Applications: arrays for tables, stacks for function calls and undo, queues for printers and CPU scheduling, trees for file systems and databases, graphs for maps and networks.

Important terms

• Data structure (डेटा संरचना) – organised way of storing data.
• ADT – model of data and operations independent of implementation.
• Time complexity – how running time grows with input size.
• Space complexity – how memory use grows with input size.
• Big-O notation – upper bound on growth rate, f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀.

Formulas

• f(n) = O(g(n)) if there exist c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀
• f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for all n ≥ n₀
• f(n) = Θ(g(n)) if c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀
• Drop constants and lower terms: 3n² + 5n + 2 = O(n²)

5 important questions

Q1. Differentiate linear and non-linear data structures.

In linear structures elements form a sequence and each element has at most one predecessor and one successor (array, stack, queue, linked list). In non-linear structures an element can connect to many others in a hierarchy or network (tree, graph).

Q2. What is an Abstract Data Type? Give an example.

An ADT defines what data is stored and what operations are allowed, but not how they are coded. Example: Queue ADT with enqueue, dequeue, front and isEmpty; it can be implemented with an array or a linked list.

Q3. Find the time complexity of this code: for (i = 0; i < n; i++) for (j = 0; j < n; j++) sum++;

• Outer loop runs n times.
• For each outer iteration, inner loop runs n times.
• Total executions of sum++ = n × n = n².
• Time complexity = O(n²).

Q4. Find the time complexity of: for (i = 1; i < n; i = i * 2) count++;

• i takes values 1, 2, 4, 8, … 2ᵏ.
• Loop stops when 2ᵏ ≥ n, i.e. k ≥ log₂ n.
• So the loop runs about log₂ n times.
• Time complexity = O(log n).

Q5. Explain asymptotic notations with graphs in words.

• Big-O: f(n) stays below c·g(n) after n₀; gives the worst-case upper bound. Graph: f(n) curve lies under c·g(n) to the right of n₀.
• Omega: f(n) stays above c·g(n) after n₀; lower bound (best case).
• Theta: f(n) is sandwiched between c₁·g(n) and c₂·g(n); exact growth.
• Example: 3n² + 5n is O(n²), Ω(n²) and Θ(n²).

Exam tip

Practise finding the complexity of simple loops; it is a common 4-mark question. Learn the growth order list by heart.

Quick summary

An array is the simplest linear data structure: a fixed number of elements of the same type stored in continuous memory. This topic covers one- and two-dimensional arrays, how their addresses are calculated (row-major and column-major order), basic operations (traversal, insertion, deletion), sparse matrices and their triplet representation, and representing and adding polynomials with arrays.

Key points

• An array element is reached directly by its index, so access takes O(1) time.
• Insertion or deletion in the middle needs shifting of elements, so it takes O(n) time.
• In C, indexing starts at 0 (lower bound LB = 0).
• A 2-D array is stored in 1-D memory in one of two ways: row-major (row by row; used by C/C++) or column-major (column by column; used by FORTRAN).
• A sparse matrix has most elements equal to zero. Storing all zeros wastes memory.
• Triplet (3-tuple) representation: store only non-zero elements as (row, column, value). Row 0 of the triplet table holds (total rows, total columns, number of non-zeros).
• A sparse matrix can also be stored as a linked list of non-zero nodes.
• Special matrices: lower triangular, upper triangular, diagonal and tridiagonal can also be stored compactly.
• A polynomial can be stored as an array where index = exponent and value = coefficient, or as an array/list of (coefficient, exponent) pairs in decreasing order of exponent.
• Polynomial addition: compare exponents of the current terms; if equal, add coefficients; otherwise copy the term with the larger exponent; repeat until both are finished.

Important terms

• Base address – address of the first element of the array.
• Word size (w) – bytes taken by one element.
• Sparse matrix – matrix with very few non-zero elements.
• Density – non-zero elements ÷ total elements.
• Triplet – (row, column, value) record of a non-zero element.

Formulas

• 1-D: Address of A[i] = B + w × (i − LB)
• 2-D row-major (m rows, n columns): Address of A[i][j] = B + w × [n × (i − LR) + (j − LC)]
• 2-D column-major: Address of A[i][j] = B + w × [m × (j − LC) + (i − LR)]
• (B = base address, w = element size, LR/LC = lower bounds of row/column, 0 in C)
• Number of elements in A[LB..UB] = UB − LB + 1
• Triplet storage = 3 × (t + 1) values for t non-zero elements

5 important questions

Q1. What is a sparse matrix? Why is a special representation needed?

A sparse matrix is one in which most elements are zero, for example a 100 × 100 matrix with only 50 non-zero values. Storing all 10,000 values wastes memory and time, so only the non-zero values are stored as triplets (row, column, value) or in a linked list.

Q2. An array int A[5][6] starts at address 2000 and each int takes 4 bytes. Find the address of A[3][4] in row-major and column-major order (indices from 0).

• Row-major: 2000 + 4 × (6 × 3 + 4) = 2000 + 4 × 22 = 2000 + 88 = 2088
• Column-major: 2000 + 4 × (5 × 4 + 3) = 2000 + 4 × 23 = 2000 + 92 = 2092

Q3. Write the triplet representation of the matrix below.

• The first row says: 4 rows, 5 columns, 4 non-zeros. Full storage = 20 values; triplet = 15 values.

Q4. Add the polynomials P = 5x³ + 4x² + 2 and Q = 3x³ + 6x + 7 using arrays. Write the algorithm.

• Store as (coef, exp): P = (5,3), (4,2), (2,0); Q = (3,3), (6,1), (7,0)
• Exp 3 = 3 → 5 + 3 = 8 → (8,3)
• Exp 2 > 1 → copy (4,2)
• Exp 0 < 1 → copy (6,1)
• Exp 0 = 0 → 2 + 7 = 9 → (9,0)
• Result: 8x³ + 4x² + 6x + 9
• Algorithm: set i = j = k = 0; while both have terms, compare exponents (equal → add, else copy larger); then copy remaining terms of either polynomial.

Q5. Explain insertion and deletion in a linear array with algorithms.

Outline: Insertion at position pos — check overflow (n = MAX), move elements from n − 1 down to pos one place right, put the item at pos, n = n + 1. Deletion at pos — store A[pos], move elements from pos + 1 to n − 1 one place left, n = n − 1. Both take O(n) in the worst case. Example: inserting 25 at index 2 in 10, 20, 30, 40 gives 10, 20, 25, 30, 40.

Exam tip

In address questions, write the formula, then the values of B, w, n (or m), i and j before substituting. Check whether the question uses 0-based or 1-based indices.

Quick summary

A stack is a linear data structure that works on Last In First Out (LIFO). A queue works on First In First Out (FIFO). This topic covers stack operations, array implementation, overflow and underflow, applications like expression conversion and evaluation, recursion, and types of queues: simple, circular, double-ended and priority queue.

Key points

• Stack: insertion (push) and deletion (pop) happen at one end called the top. Example: a pile of plates.
• Stack operations: push, pop, peek (top element), isEmpty, isFull.
• Overflow: push on a full stack. Underflow: pop on an empty stack.
• In array implementation, top = −1 means the stack is empty; top = MAX − 1 means it is full.
• Applications of stack: function calls and recursion, undo in editors, browser back button, balancing of parentheses, conversion of infix to postfix, evaluation of postfix expressions.
• Notations: infix (A + B), prefix/Polish (+AB), postfix/reverse Polish (AB+). Postfix needs no brackets and is easy for computers to evaluate.
• Queue: insertion at the rear, deletion at the front. Example: a ticket line.
• Queue operations: enqueue (insert), dequeue (delete), front/peek, isEmpty, isFull.
• In a simple linear array queue, space at the front is wasted after deletions. A circular queue solves this by wrapping around: rear = (rear + 1) % MAX.
• Deque (double-ended queue): insertion and deletion at both ends. Input-restricted and output-restricted types.
• Priority queue: each element has a priority; the element with the highest priority is removed first.
• Applications of queue: CPU and printer scheduling, keyboard buffer, call centre systems, breadth-first search.

Important terms

• LIFO (शेवटी आत, प्रथम बाहेर) – last element inserted is the first removed.
• FIFO – first element inserted is the first removed.
• Top – pointer to the last inserted element of a stack.
• Front / Rear – deletion end / insertion end of a queue.
• Postfix expression – operator written after its operands.

Formulas

Push and pop (array):

• Circular queue: rear = (rear + 1) % MAX; front = (front + 1) % MAX
• Circular queue full when (rear + 1) % MAX == front (one-slot-empty method)
• Operator precedence for conversion: ^ (highest, right to left) > * / > + − (left to right)

5 important questions

Q1. Differentiate stack and queue.

A stack follows LIFO and uses one end (top) for both push and pop. A queue follows FIFO; insertion is at the rear and deletion at the front. Stack is used for recursion; queue for scheduling.

Q2. What is a circular queue? Why is it needed?

A circular queue treats the array as a circle, so after the last position, the next position is index 0. It reuses empty spaces freed at the front, which a simple linear queue cannot use.

Q3. Convert the infix expression A + B * C − D / E to postfix.

• B * C has higher precedence → BC*
• D / E → DE/
• A + (BC*) → ABC*+
• Then subtract (DE/): ABC*+DE/−
• Postfix: A B C * + D E / −

Q4. Evaluate the postfix expression 6 2 3 + − 3 8 2 / + * using a stack.

• Push 6, 2, 3. '+' → pop 3, 2 → 5; stack: 6, 5.
• '−' → 6 − 5 = 1; stack: 1.
• Push 3, 8, 2. '/' → 8/2 = 4; stack: 1, 3, 4.
• '+' → 3 + 4 = 7; stack: 1, 7.
• '*' → 1 × 7 = 7. Result = 7.

Q5. Write algorithms for insertion and deletion in a linear queue.

• Enqueue(x): if rear == MAX − 1, print "Overflow"; else if front == −1 set front = 0; rear = rear + 1; queue[rear] = x.
• Dequeue(): if front == −1 or front > rear, print "Underflow"; else x = queue[front]; front = front + 1; return x.
• Start with front = rear = −1.
• Mention the drawback (wasted space) and circular queue as solution.

Exam tip

Infix to postfix conversion and postfix evaluation come almost every year. Show the stack contents at each step in a table: symbol, stack, output.

Quick summary

A linked list is a linear data structure made of nodes, where each node stores data and a link (pointer) to the next node. Unlike an array, nodes need not be in continuous memory and the list can grow or shrink at run time. This topic covers singly, doubly and circular linked lists, their operations, and a comparison with arrays.

Key points

• Each node has two parts: data and next (address of the next node).
• The address of the first node is kept in a pointer called head (or start). The last node's next is NULL.
• Memory for nodes is taken dynamically using malloc() and released with free().
• Types: singly linked list (one link), doubly linked list (prev and next links), circular linked list (last node points back to the first), and circular doubly linked list.
• Operations: create, traverse (display), count nodes, search, insert (at beginning, end, or after a given node), delete (first, last, or a given node), reverse.
• Insert at beginning: new node's next = head; head = new node. This takes O(1) time.
• Searching or accessing the kth element takes O(n) because we must start from head (no random access).
• Doubly linked list allows traversal in both directions and easy deletion of a given node, but uses extra memory for the prev pointer.
• Circular list is useful for round-robin scheduling and repeating playlists.
• Applications: implementing stacks and queues, polynomial representation and addition, dynamic memory management, adjacency lists of graphs.
• Garbage collection refers to reclaiming memory of deleted nodes; in C it must be done with free().

Important terms

• Node (नोड) – unit of a linked list containing data and link.
• Head – pointer to the first node.
• NULL pointer – shows the end of the list.
• Self-referential structure – structure containing a pointer to its own type.
• Traversal – visiting each node once from head to end.

Formulas

Node structure and insertion at beginning:

Traversal:

5 important questions

Q1. What is a linked list? Draw the structure of a node.

A linked list is a collection of nodes linked by pointers in a sequence. Each node is a box divided in two parts: DATA and NEXT. The NEXT part holds the address of the next node; the last node holds NULL.

Q2. Give two advantages and two disadvantages of a linked list over an array.

Advantages: size can change at run time; insertion and deletion need no shifting. Disadvantages: no direct (random) access to an element; extra memory is needed for pointers.

Q3. Write an algorithm to insert a node at the end of a singly linked list.

1. Create new node t; set t->data = x and t->next = NULL.
2. If head == NULL, set head = t and stop.
3. Else set p = head.
4. While p->next != NULL, set p = p->next.
5. Set p->next = t. Stop.

• Time complexity O(n) (O(1) if a tail pointer is kept).

Q4. Write an algorithm to delete a node with a given value key.

1. If head == NULL, print "List empty" and stop.
2. If head->data == key: t = head; head = head->next; free(t); stop.
3. Set p = head. While p->next != NULL and p->next->data != key, p = p->next.
4. If p->next == NULL, print "Not found".
5. Else t = p->next; p->next = t->next; free(t).

Q5. Explain the doubly linked list and insertion at the beginning.

• Node has three parts: prev, data, next.
• First node's prev = NULL; last node's next = NULL.
• Insert at beginning: create t; t->prev = NULL; t->next = head.
• If head != NULL, head->prev = t. Then head = t.
• Advantages: two-way traversal, easy deletion when a node pointer is given; disadvantage: extra pointer per node.

Exam tip

Draw box-and-arrow diagrams before and after each insertion or deletion. Examiners give marks for clear diagrams even if the code has a small slip.

Quick summary

A tree is a non-linear, hierarchical data structure made of nodes connected by edges, with one special node called the root. This topic covers tree terminology, binary trees and their properties, representation, the three traversals (inorder, preorder, postorder), binary search trees (BST) with insertion, searching and deletion, and a brief look at AVL trees and heaps.

Key points

• Root: topmost node. Parent, child, siblings: family-like relations. Leaf: node with no children.
• Degree of a node = number of its children. Level of root = 0 (some books use 1). Height/depth = longest path from root to a leaf.
• Binary tree: each node has at most two children (left and right).
• Strictly (full) binary tree: every node has 0 or 2 children. Complete binary tree: all levels full except possibly the last, which is filled from left.
• Representation: array (for node at index i, children at 2i + 1 and 2i + 2 using 0-based indexing) or linked (node with left, data, right).
• Traversals: inorder (Left, Root, Right), preorder (Root, Left, Right), postorder (Left, Right, Root). Level-order uses a queue.
• Binary Search Tree (BST): for every node, values in the left subtree are smaller and values in the right subtree are larger.
• Inorder traversal of a BST gives sorted (ascending) order.
• BST search, insert and delete take O(h) time: O(log n) when balanced, O(n) when skewed.
• Deletion in BST: leaf – just remove; one child – link the child to the parent; two children – replace with the inorder successor (smallest in right subtree) or predecessor, then delete that.
• AVL tree: self-balancing BST where the balance factor (height of left − height of right) of every node is −1, 0 or +1. Rotations: LL, RR, LR, RL.
• Heap: complete binary tree; in a max-heap every parent ≥ its children. Used in heap sort and priority queues.
• Expression trees: leaves are operands, internal nodes are operators.

Important terms

• Tree (वृक्ष) – hierarchical structure of nodes with one root.
• Leaf node – node without children.
• Subtree – a node with all its descendants.
• Balance factor – height(left subtree) − height(right subtree).
• Skewed tree – every node has only one child, like a linked list.

Formulas

• Maximum nodes at level l (root at level 0) = 2ˡ
• Maximum nodes in a binary tree of height h (root level 0) = 2^(h+1) − 1
• Minimum height with n nodes = ⌈log₂(n + 1)⌉ − 1
• In any binary tree: number of leaves = number of nodes with two children + 1 (n₀ = n₂ + 1)
• Edges in a tree with n nodes = n − 1

5 important questions

Q1. Define: root, leaf, degree and height of a tree.

Root is the topmost node without a parent. A leaf has no children. Degree of a node is the number of its children. Height of a tree is the number of edges on the longest path from the root to a leaf.

Q2. Why does inorder traversal of a BST give sorted output?

Inorder visits the left subtree first, then the node, then the right subtree. In a BST all left values are smaller and all right values are larger than the node, so values come out in increasing order.

Q3. Construct a BST by inserting 50, 30, 70, 20, 40, 60, 80 and give all three traversals.

• 50 is root; 30 left, 70 right; 20 and 40 under 30; 60 and 80 under 70.
• Inorder: 20 30 40 50 60 70 80
• Preorder: 50 30 20 40 70 60 80
• Postorder: 20 40 30 60 80 70 50

Q4. In the BST above, delete 30 and then 50. Show the result.

• Delete 30 (two children): inorder successor = 40. Replace 30 with 40, remove old 40. Now 40 has left child 20.
• Delete 50 (root, two children): inorder successor = 60. Replace 50 with 60, remove old 60 (a leaf).
• New tree: root 60; left 40 (left child 20); right 70 (right child 80).
• Inorder check: 20 40 60 70 80 ✓ (still sorted)

Q5. Write recursive functions for inorder, preorder and postorder traversals.

• Base case: empty subtree (NULL) → do nothing.
• Each traversal visits every node once → O(n).

Exam tip

Practise building a BST from a list and writing all three traversals; then check that inorder is sorted. This one habit catches most mistakes.

Quick summary

A graph is a non-linear data structure made of a set of vertices (nodes) and a set of edges that connect pairs of vertices. Graphs model road maps, computer networks and social networks. This topic covers graph terminology, types of graphs, the adjacency matrix and adjacency list representations, and the two traversal methods: Breadth First Search (BFS) and Depth First Search (DFS).

Key points

• A graph G = (V, E), where V = set of vertices and E = set of edges.
• Undirected graph: edges have no direction, (u, v) = (v, u). Directed graph (digraph): edges have direction, u → v.
• Weighted graph: each edge carries a cost or distance.
• Degree of a vertex = number of edges at it. In a digraph: in-degree (edges coming in) and out-degree (edges going out).
• Path: sequence of vertices joined by edges. Cycle: path that starts and ends at the same vertex.
• Connected graph: a path exists between every pair of vertices. Complete graph: every pair is joined directly.
• A tree is a connected graph with no cycle; it has exactly n − 1 edges.
• Adjacency matrix: n × n matrix, A[i][j] = 1 (or the weight) if an edge exists, else 0. Symmetric for undirected graphs. Space O(n²).
• Adjacency list: for each vertex, a linked list of its neighbours. Space O(n + e); better for sparse graphs.
• BFS visits vertices level by level using a queue. It finds the shortest path (fewest edges) in an unweighted graph.
• DFS goes as deep as possible along one branch, then backtracks; it uses a stack (or recursion).
• Both BFS and DFS take O(n + e) time with adjacency lists and O(n²) with a matrix.
• Uses: BFS — shortest route, network broadcasting; DFS — cycle detection, topological sort, maze solving.

Important terms

• Vertex / node – a point of the graph.
• Edge / arc – a link between two vertices.
• Adjacent vertices – vertices joined by an edge.
• Isolated vertex – vertex with degree 0.
• Spanning tree – a tree that includes all vertices of a graph.

Formulas

• Sum of degrees of all vertices = 2 × number of edges (handshaking lemma)
• Maximum edges: undirected = n(n − 1)/2; directed = n(n − 1)
• Adjacency matrix space = n²; adjacency list space ≈ n + 2e (undirected)

5 important questions

Q1. Differentiate BFS and DFS.

BFS uses a queue and visits all neighbours of a vertex before going deeper; it gives the shortest path in edges. DFS uses a stack or recursion and goes deep along one path before backtracking; it is used for cycle detection and topological sorting. Both take O(n + e) time.

Q2. A graph has 6 vertices with degrees 3, 2, 2, 3, 2, 2. How many edges does it have? What is the maximum number of edges possible?

• Sum of degrees = 3 + 2 + 2 + 3 + 2 + 2 = 14 = 2 × e, so e = 7.
• Maximum for an undirected simple graph = 6 × 5 / 2 = 15.

Q3. For the undirected graph with edges A–B, A–C, B–D, C–D, C–E, D–E, draw the adjacency matrix and list.

• List: A → B, C; B → A, D; C → A, D, E; D → B, C, E; E → C, D
• Check: degrees 2 + 2 + 3 + 3 + 2 = 12 = 2 × 6 edges.

Q4. Find the BFS and DFS order of the same graph starting from A (take neighbours in alphabetical order).

BFS (queue):

• Visit A; queue = B, C
• Remove B, add D; queue = C, D
• Remove C, add E (D already added); queue = D, E
• Remove D, then E
• BFS: A, B, C, D, E

DFS (stack/recursion):

• A → B (first unvisited neighbour) → D → C (D's next unvisited) → E (C's unvisited); backtrack to end
• DFS: A, B, D, C, E

Q5. Write the BFS algorithm and explain it.

Outline: mark all vertices unvisited → mark start visited and insert into queue → while queue not empty: delete vertex v, print it, for every neighbour w of v that is unvisited, mark w visited and insert it → stop. Mention the queue, the visited array, O(n + e) time, and that marking at insertion time stops a vertex from being added twice.

Exam tip

Always state the neighbour order you assume (alphabetical) and show the queue or stack contents at every step — marks are given for the steps, not just the final order.

Quick summary

In a weighted graph we often need the cheapest way to connect all vertices, or the shortest route from one vertex to the others. A minimum spanning tree (MST) connects all vertices with the least total edge weight; Prim's and Kruskal's algorithms find it. Dijkstra's algorithm finds the shortest path from one source to every other vertex. This topic explains all three with one solved example.

Key points

• A spanning tree of a connected graph with n vertices contains all n vertices and exactly n − 1 edges, with no cycle.
• A graph can have many spanning trees; the one with the smallest total weight is the minimum spanning tree.
• Both Prim's and Kruskal's are greedy algorithms: they pick the best choice at each step.
• Kruskal's algorithm: sort all edges by weight; take the smallest edge that does not form a cycle; stop after n − 1 edges. Cycle check uses disjoint sets (union–find). Time O(e log e).
• Prim's algorithm: start from any vertex; repeatedly add the cheapest edge that joins a tree vertex to a non-tree vertex. Time O(n²) with a matrix, O(e log n) with a heap.
• If all edge weights are different, the MST is unique, so Prim and Kruskal give the same tree.
• Dijkstra's algorithm: single-source shortest paths for non-negative weights. Keep a distance for each vertex (source 0, others ∞); repeatedly choose the unvisited vertex with the smallest distance and relax its edges.
• Relaxation: if dist[u] + w(u, v) < dist[v], then dist[v] = dist[u] + w(u, v).
• Dijkstra fails with negative edge weights; Bellman–Ford handles them. Floyd–Warshall finds all-pairs shortest paths.
• Uses: MST — laying cables, roads, pipelines at minimum cost; shortest path — GPS routes, network routing (OSPF).

Important terms

• Greedy method – choosing the locally best option at every step.
• Weight / cost – number attached to an edge.
• Relaxation – improving a vertex's distance through another vertex.
• Union–find – structure that tells whether two vertices are already connected.

Formulas

• Edges in a spanning tree = n − 1
• Relax: dist[v] = min(dist[v], dist[u] + w(u, v))
• Kruskal time = O(e log e); Prim (matrix) = O(n²); Dijkstra (matrix) = O(n²)

Example graph used below (6 vertices, 9 edges): A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3.

5 important questions

Q1. Differentiate Prim's and Kruskal's algorithms.

Prim's grows one tree from a starting vertex, always adding the cheapest edge leaving the tree; it suits dense graphs. Kruskal's sorts all edges and adds the cheapest edge that makes no cycle, so it may build several pieces that join later; it suits sparse graphs. Both give an MST with n − 1 edges.

Q2. Why does Dijkstra's algorithm not work with negative edge weights?

Dijkstra fixes a vertex's distance as final once it is chosen. A negative edge found later could make that distance smaller, but the algorithm never revisits it, so the answer can be wrong. Bellman–Ford is used instead.

Q3. Find the MST of the example graph using Kruskal's algorithm.

• MST edges: B–C, A–C, D–E, E–F, B–D. Total cost = 1 + 2 + 2 + 3 + 5 = 13

Q4. Find the MST of the same graph using Prim's algorithm starting at A.

• Tree {A}: cheapest edge A–C (2) → add C
• Tree {A, C}: cheapest C–B (1) → add B
• Tree {A, B, C}: options B–D 5, C–D 8, C–E 10 → B–D (5) → add D
• Tree {A, B, C, D}: D–E (2) → add E
• Tree {A, B, C, D, E}: E–F (3) beats D–F (6) → add F
• Same total = 2 + 1 + 5 + 2 + 3 = 13

Q5. Apply Dijkstra's algorithm on the example graph with source A.

• Shortest path to F: A → C → B → D → E → F = 2 + 1 + 5 + 2 + 3 = 13.

Exam tip

Draw the graph neatly first, then show a table of steps. In Kruskal, write "skip – forms cycle" clearly; in Dijkstra, circle the chosen vertex in each row.

Quick summary

Searching means finding the position of a given element in a collection. Sorting means arranging elements in ascending or descending order. This topic covers linear and binary search, and the sorting methods bubble, selection, insertion, quick, merge and (briefly) heap sort, with their working and time complexities.

Key points

• Linear (sequential) search: check each element from the start until the key is found or the list ends. Works on unsorted data. Worst case O(n).
• Binary search: works only on sorted data. Compare the key with the middle element; if smaller, search the left half, else the right half. Worst case O(log n).
• Bubble sort: repeatedly compare adjacent elements and swap if out of order. After each pass the largest element 'bubbles' to the end. O(n²); best case O(n) with a swap flag.
• Selection sort: in each pass, find the smallest element in the unsorted part and swap it to its correct position. Always O(n²) comparisons, but at most n − 1 swaps.
• Insertion sort: take one element at a time and insert it into its correct place in the already-sorted left part (like arranging playing cards). O(n²) worst, O(n) best (already sorted).
• Quick sort: divide and conquer. Choose a pivot, partition so smaller elements go left and larger go right, then sort both parts recursively. Average O(n log n), worst O(n²) when the pivot is always the smallest or largest.
• Merge sort: divide the list into halves, sort each half, then merge the two sorted halves. Always O(n log n); needs O(n) extra memory.
• Heap sort: build a max-heap, repeatedly move the root (largest) to the end. O(n log n), in-place.
• A sort is stable if equal elements keep their original relative order. Bubble, insertion and merge sort are stable; selection, quick and heap sort are not (in their usual form).
• In-place sort uses only a small constant amount of extra memory.

Important terms

• Key – the value being searched for.
• Pass – one complete scan through the list in a sorting method.
• Pivot – element used to partition the list in quick sort.
• Divide and conquer (विभागा आणि जिंका) – break a problem into smaller parts, solve, then combine.
• Stable sort – keeps the order of equal keys.

Formulas

• Binary search: mid = (low + high)/2 (integer division)
• Maximum comparisons in binary search ≈ ⌊log₂ n⌋ + 1

5 important questions

Q1. Why can binary search not be used on unsorted data?

Binary search decides which half to discard by comparing the key with the middle element. This works only if all smaller values are on the left and larger on the right, which is true only for sorted data.

Q2. What is a stable sorting algorithm? Give one example.

A sort is stable when two equal elements appear in the output in the same order as in the input. Example: insertion sort, merge sort.

Q3. Search 23 in the sorted list 5, 8, 12, 16, 23, 38, 56, 72, 91 (indices 0–8) using binary search.

• low = 0, high = 8 → mid = 4, a[4] = 23.
• Key found at index 4 in 1 comparison.
• (Search 72: mid = 4 → 23 < 72, low = 5; mid = 6 → 56 < 72, low = 7; mid = 7 → 72 found at index 7 after 3 comparisons.)

Q4. Sort 64, 25, 12, 22, 11 using bubble sort, showing each pass.

• Pass 1: 25, 12, 22, 11, 64
• Pass 2: 12, 22, 11, 25, 64
• Pass 3: 12, 11, 22, 25, 64
• Pass 4: 11, 12, 22, 25, 64
• Sorted after n − 1 = 4 passes.

Q5. Explain merge sort with the example 38, 27, 43, 3, 9, 82, 10.

• Divide: (38, 27, 43, 3) and (9, 82, 10) → keep halving to single elements.
• Merge pairs: (27, 38), (3, 43), (9, 82), (10).
• Merge again: (3, 27, 38, 43) and (9, 10, 82).
• Final merge: 3, 9, 10, 27, 38, 43, 82.
• Recurrence T(n) = 2T(n/2) + n → O(n log n); extra array needed for merging.

Exam tip

For any sorting question, write the list after every pass. Learn the complexity table — it is often asked as a short note.

Quick summary

Hashing is a technique to store and find data in almost constant time. A hash function converts a key into an index (address) of a table called the hash table. When two keys get the same index, a collision occurs, which is handled by chaining or open addressing. This topic covers hash functions, collision resolution (linear probing, quadratic probing, double hashing, separate chaining), load factor and rehashing, with worked examples.

Key points

• Linear search takes O(n) and binary search O(log n); hashing aims for O(1) average search time.
• Hash table: an array of m slots (buckets). Hash function h(k) gives the slot for key k.
• A good hash function is fast to compute, spreads keys evenly, and uses all parts of the key.
• Division method: h(k) = k mod m (choose m as a prime not close to a power of 2).
• Mid-square method: square the key and take the middle digits.
• Folding method: split the key into parts and add them, e.g. 123456 → 12 + 34 + 56 = 102.
• Collision: two different keys map to the same slot.
• Separate chaining: each slot holds a linked list of all keys that hash there. Table never "fills up".
• Open addressing: all keys stay inside the table; on collision, probe other slots.
• Linear probing: try h, h + 1, h + 2 … (mod m). Suffers from primary clustering.
• Quadratic probing: try h, h + 1², h + 2², h + 3² … (mod m). Reduces primary clustering.
• Double hashing: try h₁(k) + i × h₂(k) (mod m); a second hash function gives the step size.
• Load factor α = n / m. As α rises, collisions rise. For open addressing α must stay below 1 (usually below 0.7).
• Rehashing: when α becomes too high, make a bigger table (about double, a prime size) and insert all keys again.
• Uses: symbol tables in compilers, database indexing, password storage, caches, dictionaries in Python.

Important terms

• Key – the value used to find a record.
• Bucket / slot – one position of the hash table.
• Probe – one attempt to find a free or matching slot.
• Clustering – keys bunching together in nearby slots.
• Perfect hash function – gives no collisions for a given set of keys.

Formulas

• Division: h(k) = k mod m
• Linear probing: hᵢ(k) = (h(k) + i) mod m, i = 0, 1, 2 …
• Quadratic probing: hᵢ(k) = (h(k) + i²) mod m
• Double hashing: hᵢ(k) = (h₁(k) + i × h₂(k)) mod m
• Load factor α = n / m (n = keys stored, m = table size)

5 important questions

Q1. What is a collision? Name the methods to resolve it.

A collision happens when the hash function gives the same slot for two different keys, e.g. with h(k) = k mod 10, both 23 and 43 go to slot 3. Methods: separate chaining (linked list at each slot) and open addressing (linear probing, quadratic probing, double hashing).

Q2. What is load factor? A table of size 13 holds 9 keys. Find α and say whether rehashing is needed (threshold 0.7).

α = n / m = 9 / 13 ≈ 0.69. It is just below 0.7, so rehashing is not yet needed; one more key makes α = 10/13 ≈ 0.77, so the table should then be rehashed to a larger prime size such as 29.

Q3. Insert 23, 43, 13, 27, 37, 18 into a table of size 10 using h(k) = k mod 10 with linear probing.

• Final table: slot 3 = 23, 4 = 43, 5 = 13, 7 = 27, 8 = 37, 9 = 18; slots 0, 1, 2, 6 empty.
• Note the cluster from 3 to 5 and from 7 to 9 (primary clustering).

Q4. Insert the same keys using quadratic probing.

• 23 → 3; 43 → 3 taken, 3 + 1 = 4 → 4
• 13 → 3, 4 taken; 3 + 4 = 7 → 7
• 27 → 7 taken; 7 + 1 = 8 → 8
• 37 → 7, 8 taken; 7 + 4 = 11 mod 10 = 1 → 1
• 18 → 8 taken; 8 + 1 = 9 → 9
• Final: 1 = 37, 3 = 23, 4 = 43, 7 = 13, 8 = 27, 9 = 18. Keys are spread more widely than with linear probing.

Q5. Explain separate chaining with an example and compare it with open addressing.

Example: m = 7, h(k) = k mod 7, keys 50, 700, 76, 85, 92, 73, 101. Slots: 0 → 700; 1 → 50 → 85 → 92; 3 → 73 → 101; 6 → 76. Comparison: chaining is simple, never overflows and allows α > 1, but needs extra memory for pointers; open addressing uses no pointers and is cache-friendly but suffers clustering, needs α < 1 and makes deletion tricky (deleted slots must be marked).

Exam tip

Always draw the final hash table with slot numbers 0 to m − 1. Write the probe sequence for every collided key — that is where the marks are.

Quick summary

Object-Oriented Programming (OOP) is a way of writing programs around objects, which combine data and the functions that work on that data. It models real-world things. This topic covers the difference between procedural and object-oriented programming, and the main OOP concepts: class, object, encapsulation, abstraction, inheritance, polymorphism, dynamic binding and message passing, plus the benefits of OOP and an introduction to C++.

Key points

• Procedure-oriented programming (POP) like C focuses on functions; data moves freely between functions and is less secure. It follows a top-down approach.
• OOP like C++, Java and Python focuses on data (objects); data is hidden and accessed only through member functions. It follows a bottom-up approach.
• Class: a user-defined blueprint that describes data members and member functions. Example: class Student.
• Object: an instance of a class; a real entity in memory. Example: Student s1;
• Encapsulation: wrapping data and functions into a single unit (class). It supports data hiding using private access.
• Abstraction: showing only essential features and hiding background details (we drive a car without knowing the engine design).
• Inheritance: a new class (derived) gets properties of an existing class (base). It gives reusability.
• Polymorphism ("many forms"): the same name behaves differently in different situations. Compile-time (function and operator overloading) and run-time (virtual functions).
• Dynamic binding: the code to run for a function call is decided at run time.
• Message passing: objects communicate by calling each other's functions.
• Benefits: reusability, data security, easier maintenance, modelling of real-world problems, scalability.
• C++ was developed by Bjarne Stroustrup at Bell Labs in the early 1980s, first called "C with Classes".
• C++ I/O uses cout with the insertion operator and cin with the extraction operator, from the iostream header.

Important terms

• Object (वस्तू) – instance of a class with its own state and behaviour.
• Data hiding – preventing direct access to data from outside the class.
• Reusability – using existing code again through inheritance.
• Overloading – same function name or operator with different meanings by argument type.
• Access specifiers – private, protected, public; control visibility of members.

Formulas

A first C++ program:

5 important questions

Q1. Differentiate between a class and an object.

A class is a blueprint or template that defines data and functions; it uses no memory for data until objects are made. An object is an instance of a class that occupies memory. Example: Car is a class; myCar is an object.

Q2. What is encapsulation? How does it give data hiding?

Encapsulation binds data and functions into a class. By declaring data members private, they can be reached only through public member functions, so outside code cannot change them directly. This is data hiding.

Q3. Explain the basic concepts of OOP.

• Class and object.
• Encapsulation and data hiding.
• Abstraction.
• Inheritance (reusability).
• Polymorphism (overloading, virtual functions).
• Dynamic binding and message passing.
• Give a one-line example for each (e.g. BankAccount class with deposit()).

Q4. Compare procedure-oriented and object-oriented programming.

• POP divides the program into functions; OOP into objects.
• POP uses top-down design; OOP bottom-up.
• In POP data is mostly global; OOP hides data inside classes.
• OOP supports inheritance, polymorphism and overloading; POP does not.
• Examples: C (POP); C++, Java (OOP).

Q5. What are the benefits and applications of OOP?

• Benefits: code reuse, data security, easy upgrades, modular design, fewer errors in big projects.
• Real-world modelling makes design natural.
• Applications: GUI applications, games, simulation, CAD/CAM, real-time systems, object databases.
• Many modern languages (C++, Java, Python, C#) are object-oriented.

Exam tip

The POP vs OOP table and "explain OOP concepts" are near-certain questions. Give a small real-life example for each concept to score full marks.

Quick summary

In C++, a class groups data members and member functions into one unit, and objects are variables of that class. This topic covers defining a class, access specifiers, defining member functions inside and outside the class, creating objects, constructors and destructors, static members, friend functions, and inline functions.

Key points

• Syntax: class Name { private: data; public: functions; }; — note the semicolon after the closing brace.
• Access specifiers: private (default in a class; accessible only inside the class), public (accessible everywhere), protected (accessible in the class and its derived classes).
• Members are accessed through an object with the dot operator: s1.getdata();
• Member functions can be defined inside the class (they become inline automatically) or outside using the scope resolution operator ::, e.g. void Student::show() { … }
• Constructor: a special member function with the same name as the class and no return type. It is called automatically when an object is created. Used to initialise data.
• Types of constructor: default (no arguments), parameterised, copy constructor (initialises an object from another object of the same class).
• Constructor overloading: a class can have several constructors with different parameter lists.
• Destructor: same name as the class with a tilde (~), no arguments and no return type; called automatically when the object goes out of scope. Only one destructor per class.
• Static data member: one copy shared by all objects (e.g. a counter of objects). It must also be defined outside the class.
• Static member function can access only static members and is called with the class name: Student::count();
• Friend function: not a member, but declared with the keyword friend inside the class, so it can access private data.
• Inline function: the compiler may replace the call with the function body, saving call overhead for small functions.
• The this pointer inside a member function points to the object that called it.

Important terms

• Data member – variable declared inside a class.
• Member function (सदस्य फलन) – function declared inside a class.
• Scope resolution operator (::) – links a function defined outside to its class.
• Constructor – auto-called initialiser with the class name.
• Destructor – auto-called clean-up function, ~ClassName().

Formulas

Example class:

5 important questions

Q1. What is a constructor? List its characteristics.

A constructor is a special member function that initialises an object automatically when it is created. It has the same name as the class, has no return type (not even void), is usually declared public, can be overloaded, and cannot be virtual.

Q2. Differentiate constructor and destructor.

A constructor initialises an object when it is created; it can take arguments and can be overloaded. A destructor releases resources when the object is destroyed; its name starts with ~, it takes no arguments and cannot be overloaded.

Q3. Find the output and explain:

• c is static, so all objects share one copy.
• Each object creation calls the constructor, which increments c.
• Three objects a, b, d → c = 3.
• Output: 3

Q4. Write a C++ class Student with roll number and marks, with functions to read and display data (one defined outside the class).

• Data members are private by default; functions are public.
• show() is defined outside using ::.

Q5. What is a friend function? Write its features with an example.

• A non-member function given access to private members by declaring it with friend inside the class.
• It is called like a normal function, not with an object and dot.
• It takes objects as arguments, e.g. friend float average(Student s);
• It can be a friend of more than one class (useful to work on two classes' data).
• Drawback: it weakens data hiding, so use it only when needed.

Exam tip

Learn the types of constructors with one small example each — "explain constructors with types" is one of the most frequent long questions.

Quick summary

Inheritance lets a new class (derived class) acquire the properties of an existing class (base class), giving code reuse. Polymorphism lets one name take many forms. This topic covers types of inheritance, visibility modes, constructors in derived classes, the diamond problem and virtual base classes, function and operator overloading, function overriding, virtual functions and abstract classes.

Key points

• Syntax: class Derived : public Base { … };
• Visibility modes: public, protected, private. Private members of the base are never directly accessible in the derived class.
• With public inheritance: public stays public, protected stays protected. With protected inheritance: public and protected become protected. With private inheritance: both become private.
• Types of inheritance: single (A → B), multiple (A, B → C), multilevel (A → B → C), hierarchical (A → B, A → C), hybrid (combination).
• Diamond problem: in hybrid inheritance, class D gets two copies of A's members through B and C. Solved by making A a virtual base class: class B : virtual public A.
• Constructors of the base class run first, then the derived class; destructors run in reverse order.
• Compile-time (static) polymorphism: function overloading (same name, different parameters) and operator overloading (giving a new meaning to +, ==, etc. for user types).
• Run-time (dynamic) polymorphism: achieved using virtual functions and a base class pointer or reference. The function that runs depends on the type of object pointed to, not the type of pointer.
• Function overriding: a derived class redefines a base class function with the same signature.
• Pure virtual function: virtual void draw() = 0; A class with at least one pure virtual function is an abstract class; it cannot be instantiated.
• Some operators cannot be overloaded: scope resolution (::), member access (.), pointer-to-member (.*), conditional (?:) and sizeof.

Important terms

• Base class (मूळ वर्ग) – class whose features are inherited.
• Derived class – class that inherits from a base class.
• Virtual function – member function declared virtual so that calls are resolved at run time.
• Abstract class – class with a pure virtual function; used only as a base.
• Early binding / late binding – function call fixed at compile time / at run time.

Formulas

Run-time polymorphism example:

5 important questions

Q1. What is a virtual base class?

When a class is inherited by two classes which are both inherited by a fourth class (diamond shape), the fourth gets two copies of the first class. Declaring the inheritance with the keyword virtual (class B : virtual public A) keeps only one shared copy.

Q2. Differentiate function overloading and function overriding.

Overloading: same function name with different parameter lists in the same scope; decided at compile time. Overriding: derived class redefines a base function with the same name and parameters; with virtual functions it is decided at run time.

Q3. Find the output (no virtual keyword):

• show() is not virtual, so binding is early (compile time).
• The call is decided by the pointer type A*.
• Output: A
• If show() in A were declared virtual, output would be B.

Q4. Explain the types of inheritance with diagrams in words.

• Single: one base, one derived (Person → Student).
• Multiple: two bases, one derived (Teacher, Researcher → Professor).
• Multilevel: chain (Person → Employee → Manager).
• Hierarchical: one base, many derived (Shape → Circle, Square).
• Hybrid: mix, e.g. multilevel + multiple, may need a virtual base class.

Q5. What is operator overloading? Overload + to add two complex numbers.

• c3 = c1 + c2; is read as c1.operator+(c2).
• Rules: at least one operand must be a user-defined type; precedence and arity cannot change; some operators cannot be overloaded.

Exam tip

Always show the effect of the virtual keyword with a base pointer example — it is the clearest way to explain run-time polymorphism.

Quick summary

Templates let one piece of C++ code work with many data types, which is called generic programming. Exception handling lets a program catch run-time errors and respond to them instead of crashing. This topic covers function templates, class templates, templates with more than one type, an introduction to the STL, and exception handling with try, throw and catch, including multiple catch blocks and the catch-all handler.

Key points

• A template is a blueprint; the compiler creates the real function or class for each type used. This is compile-time polymorphism.
• Function template: template <class T> T maxOf(T a, T b) { return (a > b) ? a : b; } works for int, double, char …
• Class template: template <class T> class Box { T v; … }; used as Box<int> b1(10); or Box<string> b2("Hi");.
• typename and class mean the same in a template parameter list.
• Multiple parameters: template <class T1, class T2>.
• A template function can be overloaded by a normal function; the exact normal match is preferred.
• STL (Standard Template Library) is built from templates: containers (vector, list, stack, queue, map), algorithms (sort, find) and iterators.
• An exception is an unusual run-time event such as division by zero, array index out of range or memory not available.
• try block holds code that may fail; throw raises the exception; catch handles it.
• When an exception is thrown, the rest of the try block is skipped and control jumps to the matching catch.
• Several catch blocks can follow one try; the first one whose type matches is run.
• catch(...) catches any exception; write it last.
• An exception can be rethrown with throw; inside a catch block.
• Standard exceptions come from std::exception, e.g. bad_alloc (new fails), out_of_range.

Important terms

• Generic programming – writing code independent of data type.
• Template instantiation – compiler creating a real version for a given type.
• Exception – run-time error condition.
• Handler – a catch block.
• Stack unwinding – destroying local objects while control moves to the handler.

Formulas

• Function template syntax: template <class T> return-type name(T arg, …) { … }
• Class template object: ClassName<type> object(args);
• Exception syntax: try { … throw value; … } catch (type var) { … }

5 important questions

Q1. What is a template? Why is it called generic programming?

A template is a model for a function or class in which the data type is a parameter. The same code serves int, float, char or user types, and the compiler generates the needed version. Because the code is written once without fixing the type, it is called generic programming.

Q2. What does catch(...) do? Where should it be placed?

catch(...) (three dots) is the catch-all handler; it catches an exception of any type. It must be the last catch block, otherwise the specific handlers after it would never run.

Q3. Find the output:

• maxOf(3, 7) uses T = int → 7
• maxOf(2.5, 1.5) uses T = double → 2.5
• maxOf('a', 'z') uses T = char; 'z' (122) > 'a' (97) → z
• Output: 7 2.5 z

Q4. Write a program to handle division by zero using exception handling. Show the output.

• Output: 5, then Error: Division by zero
• "after" is never printed, because after the throw the rest of the try block is skipped.

Q5. Explain class templates with an example, and list the advantages of templates.

Outline: syntax template <class T> class Box { T v; public: Box(T x) { v = x; } T get() { return v; } }; → objects Box<int> b1(10); Box<string> b2("Hi"); print 10 and Hi → a class template with two types (Pair<T1, T2>) → advantages: code reuse, type safety, less code, base of the STL → disadvantage: larger compiled code and harder error messages.

Exam tip

In output questions, write which type T becomes for every call. For exceptions, show clearly which statements are skipped after throw.

Quick summary

C++ handles files through stream classes declared in <fstream>. An ofstream writes to a file, an ifstream reads from it, and an fstream can do both. This topic covers the stream class hierarchy, opening and closing files, file modes, reading and writing text with <<, >> and getline(), binary files with write() and read(), file pointers and random access, and error checking.

Key points

• A stream is a flow of bytes. cin and cout are console streams; file streams connect to disk files.
• Classes: ifstream (input file), ofstream (output file), fstream (both). They come from istream, ostream and iostream, whose common base is ios.
• Open by constructor: ofstream out("marks.txt"); or by function: out.open("marks.txt");. Close with out.close();.
• File modes (combine with |): ios::in read, ios::out write, ios::app append at end, ios::ate go to end on opening, ios::trunc erase old contents, ios::binary binary mode, ios::nocreate/ios::noreplace in old compilers.
• Text I/O uses << and >> just like cout/cin; getline(in, line) reads a full line with spaces.
• Character I/O: get(ch) and put(ch).
• Binary I/O: out.write((char*) &obj, sizeof(obj)); and in.read((char*) &obj, sizeof(obj)); — used to store whole objects.
• Check success with if (!in) or in.is_open(). eof() is true at end of file; fail() when an operation fails.
• File pointers: get pointer (reading) and put pointer (writing). seekg()/seekp() move them; tellg()/tellp() give their position.
• Seek origin: ios::beg, ios::cur, ios::end.
• A file is closed automatically when the stream object goes out of scope (destructor), but closing explicitly is good practice.

Important terms

• ifstream / ofstream / fstream – stream classes for input, output and both.
• Get pointer – position of the next read.
• Put pointer – position of the next write.
• Binary file – stores the memory image of data.
• Persistent object – object saved in a file so it survives after the program ends.

Formulas

• Open with modes: fstream f("data.dat", ios::in | ios::out | ios::binary);
• Position of object k (k = 0, 1, …) = k × sizeof(object) → f.seekg(k * sizeof(obj), ios::beg);
• Number of objects in file = file size ÷ sizeof(object), file size from seekg(0, ios::end); tellg();

5 important questions

Q1. Differentiate ios::app and ios::ate.

ios::app opens the file so that every write is added at the end; existing data cannot be overwritten. ios::ate only moves the pointer to the end when the file is opened; after that the pointer can be moved with seekp and data can be written anywhere.

Q2. What are seekg() and tellg()?

seekg(offset, origin) moves the get (read) pointer, e.g. in.seekg(0, ios::end) jumps to the end. tellg() returns the current position of the get pointer in bytes. Together they give the file size: in.seekg(0, ios::end); long size = in.tellg();.

Q3. A file s.txt has the lines "Asha 85" and "Ravi 72". Write a program to read it and print the number of students, total and average marks.

• Output: 2 157 78.5 (85 + 72 = 157; 157 ÷ 2 = 78.5)

Q4. Write a program to store objects of class Student in a binary file and display them.

Outline: class Student with roll, name (char array), marks and functions getdata()/show() → ofstream out("stu.dat", ios::binary); → loop: getdata, out.write((char*) &s, sizeof(s)); → close → ifstream in("stu.dat", ios::binary); → while (in.read((char*) &s, sizeof(s))) s.show(); → close. Note: use char arrays, not string, inside objects written in binary.

Q5. Explain the file stream class hierarchy and the file opening modes.

Outline: draw ios at top → istream and ostream → iostream; file classes ifstream (from istream), ofstream (from ostream), fstream (from iostream), plus filebuf for buffering → list each mode with its meaning → show combining modes with | → explain default modes (ifstream = in, ofstream = out | trunc).

Exam tip

Always check whether the file opened (if (!in)) and close it at the end. In binary programs, write the (char*) &obj cast and sizeof(obj) exactly.

Quick summary

A Database Management System (DBMS) is software used to create, store, manage and retrieve data in a database. It removes many problems of the old file-processing system. This topic covers advantages of DBMS, three-level architecture and data independence, data models, the ER model, the relational model with keys, and normalisation (1NF, 2NF, 3NF).

Key points

• Database: an organised collection of related data. DBMS: software to manage it (MySQL, Oracle, PostgreSQL, MS Access).
• Problems of file systems: data redundancy, inconsistency, difficulty in access, poor security, no concurrent access control.
• Advantages of DBMS: less redundancy, consistency, data sharing, security, integrity constraints, backup and recovery, concurrency control.
• Three-level (ANSI/SPARC) architecture: external level (user views), conceptual level (whole logical structure), internal level (physical storage).
• Data independence: physical (change storage without changing the logical schema) and logical (change the conceptual schema without changing user views).
• Data models: hierarchical (tree), network (graph), relational (tables), object-oriented.
• ER model (Peter Chen, 1976): entity (rectangle), attribute (ellipse), relationship (diamond). Key attributes are underlined; multivalued attributes have double ellipses; weak entities have double rectangles.
• Cardinality: one-to-one, one-to-many, many-to-one, many-to-many.
• Relational model (E. F. Codd, 1970): data in tables called relations. Row = tuple, column = attribute, number of rows = cardinality, number of columns = degree.
• Keys: super key, candidate key, primary key (unique, not null), alternate key, foreign key (refers to a primary key of another table), composite key.
• Normalisation reduces redundancy and update anomalies:
• 1NF – every attribute has atomic (single) values.
• 2NF – in 1NF and no partial dependency (non-key attribute depending on part of a composite key).
• 3NF – in 2NF and no transitive dependency (non-key depending on another non-key).
• ACID properties of transactions: Atomicity, Consistency, Isolation, Durability.

Important terms

• Schema – logical design of the database. Instance – data at a given moment.
• Tuple (पंक्ती) – a row of a table.
• Primary key – attribute(s) that uniquely identify each row.
• Foreign key – attribute that links to the primary key of another table.
• Functional dependency – X → Y means the value of X decides the value of Y.
• DBA – database administrator who controls the database.

Formulas

• Degree = number of attributes (columns); Cardinality = number of tuples (rows)
• Functional dependency notation: RollNo → Name
• Partial dependency: (RollNo, CourseID) → StudentName depends only on RollNo
• Transitive dependency: RollNo → PinCode and PinCode → City, so RollNo → City through PinCode

5 important questions

Q1. Define primary key and foreign key with an example.

A primary key uniquely identifies each row and cannot be NULL, e.g. RollNo in Student. A foreign key is a column in one table that refers to the primary key of another, e.g. RollNo in the Marks table referring to Student(RollNo).

Q2. What is data independence? Name its types.

It is the ability to change the schema at one level without changing the schema at the next higher level. Physical data independence and logical data independence.

Q3. Draw an ER diagram (in words) for a college with Student and Course.

• Entity Student (rectangle): attributes RollNo (underlined key), Name, Phone (double ellipse if many).
• Entity Course (rectangle): CourseID (key), Title, Credits.
• Relationship "Enrolls" (diamond) between them.
• Cardinality many-to-many (M:N): a student takes many courses; a course has many students.
• Attribute of relationship: Grade (ellipse attached to the diamond).

Q4. Normalise up to 3NF: Result(RollNo, Name, CourseID, CourseName, Marks), key (RollNo, CourseID).

• 1NF: values are atomic → already 1NF.
• Partial dependencies: RollNo → Name; CourseID → CourseName.
• 2NF: Student(RollNo, Name), Course(CourseID, CourseName), Result(RollNo, CourseID, Marks).
• No transitive dependency remains → all three tables are in 3NF.

Q5. Explain the three-level architecture of DBMS.

• External level: individual user views; each user sees only needed data.
• Conceptual level: complete logical structure — entities, relationships, constraints.
• Internal level: how data is physically stored — files, indexes.
• Mappings between levels give data independence.
• Diagram: three stacked layers with users at top and the stored database at bottom.

Exam tip

Normalisation examples carry big marks. Always state the key first, list dependencies, then split tables step by step.

Quick summary

The relational model, proposed by E. F. Codd in 1970, stores data in tables called relations. This topic covers relational terms (relation, tuple, attribute, domain, degree, cardinality), the types of keys, integrity constraints, Codd's rules in brief, and relational algebra — the set of operations (select, project, union, set difference, Cartesian product, rename, join, intersection, division) used to query relations, with worked examples.

Key points

• A relation is a table; a tuple is a row; an attribute is a column; a domain is the set of allowed values of an attribute.
• Degree = number of attributes (columns); cardinality = number of tuples (rows).
• Rows have no fixed order, and no two rows are exactly the same.
• Keys: super key (any set of attributes that identifies a row uniquely), candidate key (minimal super key), primary key (the candidate key chosen), alternate key (other candidate keys), foreign key (attribute that refers to the primary key of another table), composite key (key with two or more attributes).
• Integrity constraints: domain constraint (value must be from its domain), entity integrity (primary key cannot be NULL), referential integrity (a foreign key value must exist in the referenced table or be NULL).
• Relational algebra is procedural: it says what operations to do and in which order. Each operation takes relations and returns a relation.
• Basic operations: select σ (picks rows), project π (picks columns, removes duplicates), union ∪, set difference −, Cartesian product ×, rename ρ.
• Derived operations: intersection ∩, join ⋈ (theta join, equi-join, natural join), division ÷.
• Union, difference and intersection need union-compatible relations: same number of attributes with matching domains.
• Relational calculus (tuple and domain) is non-procedural: it says only what is wanted. SQL is based on both.

Important terms

• Relation schema – name and list of attributes, e.g. Student(roll, name, city, dept_id).
• Relation instance – the data in the table at a given time.
• NULL – unknown or missing value.
• Natural join – join on common attributes, keeping one copy of them.
• Union compatible – having the same structure for set operations.

Formulas

Tables used: Student(roll, name, city, dept_id) = (1, Asha, Nagpur, 10), (2, Ravi, Pune, 20), (3, Neha, Nagpur, 10), (4, Amit, Bhandara, NULL); Dept(dept_id, dname) = (10, Computer), (20, Physics), (30, Maths).

• Degree of R × S = degree of R + degree of S; cardinality = |R| × |S|
• R ∩ S = R − (R − S)

5 important questions

Q1. Define degree and cardinality. Find them for the Student table above.

Degree is the number of attributes; cardinality is the number of tuples. Student has 4 attributes (roll, name, city, dept_id) and 4 rows, so degree = 4 and cardinality = 4.

Q2. Differentiate primary key and candidate key.

A candidate key is any minimal set of attributes that identifies each row uniquely; a table may have several (e.g. roll and Aadhaar number). The primary key is the one candidate key chosen by the designer; it cannot be NULL. The remaining candidate keys become alternate keys.

Q3. Write relational algebra and the result for: (a) names of students from Nagpur; (b) Student × Dept size; (c) names with their department names.

• (a) π name (σ city = 'Nagpur' (Student)) → Asha, Neha
• (b) Student × Dept has degree 4 + 2 = 6 and cardinality 4 × 3 = 12
• (c) π name, dname (Student ⋈ Dept) → (Asha, Computer), (Ravi, Physics), (Neha, Computer). Amit has NULL dept_id and Maths has no student, so neither appears.

Q4. Explain the set operations with an example.

Let A = π name (σ city = 'Nagpur' (Student)) = {Asha, Neha} and C = π name (σ roll ≤ 2 (Student)) = {Asha, Ravi}. Then A ∪ C = {Asha, Neha, Ravi}; A ∩ C = {Asha}; A − C = {Neha}; C − A = {Ravi}. State the union-compatibility condition and that duplicates are removed.

Q5. Explain the types of keys and integrity constraints with examples.

Outline: define each key using Student and Dept (roll = primary key, dept_id in Student = foreign key, {roll, name} = super key) → entity integrity (roll cannot be NULL) → referential integrity (Student cannot have dept_id 50 because Dept has no 50; deleting Dept 10 must be blocked or cascaded) → domain constraint (marks between 0 and 100) → why constraints keep data correct.

Exam tip

Write the relational algebra expression from inside out: first σ for rows, then ⋈ if two tables are needed, and π last for columns. Show the result table for full marks.

Quick summary

SQL (Structured Query Language) is the standard language for working with relational databases. It is used to create tables, insert and change data, and ask questions (queries). This topic covers SQL command categories, data types, constraints, CREATE, INSERT, UPDATE, DELETE, SELECT with WHERE, ORDER BY, GROUP BY, HAVING, aggregate functions, and simple joins.

Key points

• SQL is not case-sensitive for keywords; statements usually end with a semicolon.
• DDL (Data Definition Language): CREATE, ALTER, DROP, TRUNCATE, RENAME — change structure.
• DML (Data Manipulation Language): INSERT, UPDATE, DELETE (and SELECT, sometimes called DQL).
• DCL (Data Control Language): GRANT, REVOKE. TCL (Transaction Control): COMMIT, ROLLBACK, SAVEPOINT.
• Common data types: INT, DECIMAL(p, s), CHAR(n) (fixed length), VARCHAR(n) (variable length), DATE.
• Constraints: PRIMARY KEY, FOREIGN KEY, NOT NULL, UNIQUE, CHECK, DEFAULT.
• SELECT fetches data; WHERE filters rows; ORDER BY sorts (ASC default, DESC); DISTINCT removes duplicate rows.
• Operators in WHERE: =, <>, >, <, >=, <=, AND, OR, NOT, BETWEEN, IN, LIKE (with % for any characters and _ for one character), IS NULL.
• Aggregate functions: COUNT, SUM, AVG, MAX, MIN.
• GROUP BY groups rows with the same value; HAVING filters groups (WHERE cannot use aggregates).
• DELETE removes rows (can use WHERE, can be rolled back); TRUNCATE removes all rows quickly; DROP removes the whole table structure.
• JOIN combines rows of two tables using a common column. INNER JOIN returns only matching rows; LEFT JOIN returns all rows of the left table.

Important terms

• Query (प्रश्न / क्वेरी) – a request for data from a database.
• Constraint – rule applied to a column to keep data valid.
• Aggregate function – function that returns one value from many rows.
• View – virtual table based on a SELECT query.
• NULL – unknown or missing value (not zero, not blank).

Formulas

Sample statements for a table Student:

• Order of clauses: SELECT → FROM → WHERE → GROUP BY → HAVING → ORDER BY

5 important questions

Q1. Differentiate DELETE, TRUNCATE and DROP.

DELETE removes selected rows using WHERE and is DML. TRUNCATE removes all rows but keeps the table structure; it is DDL and faster. DROP removes the entire table, including its structure.

Q2. What is the difference between WHERE and HAVING?

WHERE filters individual rows before grouping and cannot use aggregate functions. HAVING filters groups after GROUP BY and can use aggregates like COUNT or AVG.

Q3. Write queries on Student(RollNo, Name, City, Marks): (a) names of students with marks between 60 and 80; (b) number of students in each city; (c) cities with average marks above 70.

• (a) SELECT Name FROM Student WHERE Marks BETWEEN 60 AND 80;
• (b) SELECT City, COUNT(*) FROM Student GROUP BY City;
• (c) SELECT City, AVG(Marks) FROM Student GROUP BY City HAVING AVG(Marks) > 70;
• BETWEEN includes both 60 and 80.

Q4. Write queries: (a) students whose names start with 'S'; (b) highest marks; (c) list students in alphabetical order.

• (a) SELECT * FROM Student WHERE Name LIKE 'S%';
• (b) SELECT MAX(Marks) FROM Student;
• (c) SELECT * FROM Student ORDER BY Name ASC;
• Names with 'a' as second letter: WHERE Name LIKE '_a%'

Q5. Explain INNER JOIN with an example using Student(RollNo, Name) and Result(RollNo, Subject, Marks).

• Matches rows where RollNo is equal in both tables.
• Students without any result row are not shown.
• LEFT JOIN would show all students, with NULL for missing results.
• RollNo in Result is a foreign key referring to Student.

Exam tip

Write SQL keywords in capitals and end every query with a semicolon. Practise GROUP BY with HAVING — it is the most common query question.

Quick summary

Real questions often need data from more than one table. SQL joins combine rows of two tables using a related column, subqueries put one query inside another, and views save a query as a virtual table. This topic covers inner, left, right, full outer, cross and self joins, aggregate functions with GROUP BY and HAVING, single-row and multi-row subqueries (IN, EXISTS, ANY, ALL), and creating, using and dropping views, with outputs.

Key points

• A join combines rows from two tables based on a condition, usually primary key = foreign key.
• INNER JOIN: only rows that match in both tables.
• LEFT (OUTER) JOIN: all rows of the left table; unmatched right-side columns become NULL. RIGHT JOIN is the mirror image.
• FULL OUTER JOIN: all rows of both tables, NULL where no match.
• CROSS JOIN: Cartesian product, every row with every row (m × n rows).
• SELF JOIN: a table joined with itself using aliases, e.g. employee and manager in one table.
• Aggregate functions: COUNT, SUM, AVG, MIN, MAX. GROUP BY forms groups; HAVING filters groups (WHERE filters rows before grouping).
• Subquery: a query inside another, written in brackets. The inner query usually runs first.
• Single-row subquery uses =, <, >; multi-row subquery uses IN, ANY, ALL; EXISTS checks whether the inner query returns any row.
• Correlated subquery: the inner query uses a column of the outer query and runs once for each outer row.
• View: a stored SELECT that behaves like a virtual table; it stores no data of its own. CREATE VIEW … AS SELECT …, DROP VIEW ….
• Views give security (show only some columns), simplicity (hide complex joins) and logical data independence.

Important terms

• Alias – short temporary name for a table or column (Student s).
• Outer join – join that also keeps unmatched rows.
• Nested query – another name for a subquery.
• Virtual table – a view; its rows come from base tables when queried.
• Base table – a table that actually stores data.

Formulas

Tables: Student(roll, name, city, dept_id) = (1, Asha, Nagpur, 10), (2, Ravi, Pune, 20), (3, Neha, Nagpur, 10), (4, Amit, Bhandara, NULL). Dept(dept_id, dname) = (10, Computer), (20, Physics), (30, Maths). Marks(roll, marks) = (1, 82), (2, 67), (3, 91), (4, 58).

• Order of clauses: SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY …

5 important questions

Q1. Differentiate WHERE and HAVING.

WHERE filters individual rows before grouping and cannot use aggregate functions. HAVING filters groups after GROUP BY and can use aggregates, e.g. HAVING COUNT(*) > 1.

Q2. What is a view? Give two advantages.

A view is a virtual table defined by a SELECT query; it stores no data and shows current data from the base tables each time it is used. Advantages: it hides sensitive columns (security) and saves a complex query so users can write a simple SELECT * FROM view.

Q3. Write queries and outputs: (a) each student's name with department name (inner join); (b) all students even without a department.

• Output: (Asha, Computer), (Ravi, Physics), (Neha, Computer)

• Output: the same three rows plus (Amit, NULL)

Q4. Find the names of students who scored above the class average, and the departments with more than one student.

• Average = (82 + 67 + 91 + 58) ÷ 4 = 298 ÷ 4 = 74.5. Rolls above it: 1 (82) and 3 (91). Output: Asha, Neha.

• Output: (Computer, 2)

Q5. Explain views with syntax and an example; can a view be updated?

• SELECT * FROM TopStudents; gives (Asha, 82), (Neha, 91).
• DROP VIEW TopStudents; removes the view, not the data.
• A simple view on one table without GROUP BY, DISTINCT or aggregates is usually updatable; views with joins or aggregates are generally read-only.

Exam tip

Use table aliases and always write the join condition with ON. For subqueries, solve the innermost query first and write its value beside it.

Quick summary

A transaction is a group of database operations that must be done completely or not at all, like transferring money between two accounts. This topic covers the ACID properties, transaction states, problems caused by running transactions at the same time (lost update, dirty read, unrepeatable read), schedules and serializability, lock-based concurrency control with two-phase locking, deadlocks, and basic recovery using logs, COMMIT and ROLLBACK.

Key points

• A transaction is a logical unit of work: it reads and/or writes data items, e.g. read(A), A = A − 500, write(A), read(B), B = B + 500, write(B).
• ACID properties:
• Atomicity – all or nothing; a half-done transfer is undone.
• Consistency – the database moves from one valid state to another (A + B stays the same in a transfer).
• Isolation – concurrent transactions do not see each other's half-done work.
• Durability – once committed, changes survive crashes.
• Transaction states: active → partially committed → committed; or active → failed → aborted (rolled back), then restart or kill.
• SQL commands: COMMIT saves changes, ROLLBACK undoes them, SAVEPOINT marks a point to roll back to.
• Concurrency problems: lost update (one write overwrites another), dirty read (reading uncommitted data), unrepeatable read (same item read twice gives different values), phantom rows.
• A schedule is the order in which operations of several transactions run. A serial schedule runs one transaction completely, then the next.
• A schedule is conflict serializable if it can be turned into a serial schedule by swapping non-conflicting operations. Test: draw a precedence graph; if it has no cycle, the schedule is serializable.
• Two operations conflict if they belong to different transactions, use the same item, and at least one is a write.
• Locks: shared lock (S) for reading — many can hold it; exclusive lock (X) for writing — only one can hold it.
• Two-Phase Locking (2PL): growing phase (only acquire locks) then shrinking phase (only release). It guarantees conflict serializability but can cause deadlock. Strict 2PL holds X locks until commit.
• Deadlock: T1 waits for T2's lock and T2 waits for T1's. Handled by wait-for graph detection and aborting a victim, or by timeouts / wait-die and wound-wait schemes.
• Recovery: the DBMS keeps a log of every change (old and new values). After a crash it redoes committed transactions and undoes uncommitted ones. A checkpoint limits how much log must be read.

Important terms

• Commit – making a transaction's changes permanent.
• Rollback / abort – undoing a transaction's changes.
• Schedule – sequence of operations from concurrent transactions.
• Precedence graph – graph with an edge Ti → Tj when an operation of Ti conflicts with and comes before one of Tj.
• Lock – permission to access a data item.

Formulas

• Conflicting pairs: R–W, W–R, W–W on the same item by different transactions (R–R never conflicts)
• Number of serial schedules of n transactions = n!

5 important questions

Q1. State the ACID properties with the example of a bank transfer.

Transfer ₹500 from A to B. Atomicity: if the system fails after debiting A, the debit is undone. Consistency: A + B is the same before and after. Isolation: another transaction cannot see A debited but B not yet credited. Durability: after "transfer successful", the change stays even if power fails.

Q2. Explain the lost update problem with an example.

Balance A = 100. T1 withdraws 50, T2 deposits 20. Interleaving: T1 reads 100, T2 reads 100, T1 writes 50, T2 writes 120. Final A = 120, but the correct result is 100 − 50 + 20 = 70. T1's update is lost because T2 overwrote it using an old value.

Q3. Check whether the schedule S: R1(A), R2(A), W1(A), W2(A) is conflict serializable.

• R1(A) before W2(A): conflict → edge T1 → T2
• R2(A) before W1(A): conflict → edge T2 → T1
• W1(A) before W2(A): conflict → edge T1 → T2
• The graph has a cycle T1 → T2 → T1, so S is not conflict serializable. (This is the lost update pattern.)

Q4. Is S′: R1(A), W1(A), R2(A), W2(A), R1(B), W1(B), R2(B), W2(B) conflict serializable?

• On A: every operation of T1 comes before T2's → T1 → T2
• On B: again T1's operations come first → T1 → T2
• Only edge T1 → T2, no cycle → serializable, equivalent to the serial schedule T1 then T2.

Q5. Explain two-phase locking and how it may lead to deadlock.

Outline: shared and exclusive locks with the compatibility table → growing and shrinking phases, lock point → 2PL ensures conflict serializability → strict and rigorous 2PL avoid cascading rollback → deadlock example: T1 holds X(A) and asks for X(B); T2 holds X(B) and asks for X(A); both wait forever → detection with a wait-for graph and aborting one transaction, or prevention by wait-die/wound-wait.

Exam tip

For serializability questions, list every conflicting pair, draw the precedence graph, then state clearly "cycle → not serializable" or "no cycle → equivalent to serial order …".