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

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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₀.

सूत्रे

• 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²)

५ महत्त्वाचे प्रश्न

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²).

परीक्षेसाठी टीप

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

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

• 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

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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.

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

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)

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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().

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

Node structure and insertion at beginning:

Traversal:

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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.

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

• 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

५ महत्त्वाचे प्रश्न

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).

परीक्षेसाठी टीप

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

थोडक्यात सारांश

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).

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

• 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)

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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.

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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).

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

• 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.

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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.

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

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

५ महत्त्वाचे प्रश्न

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.

परीक्षेसाठी टीप

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

थोडक्यात सारांश

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.

महत्त्वाचे मुद्दे

• 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.

महत्त्वाच्या संज्ञा

• 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.

सूत्रे

• 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)

५ महत्त्वाचे प्रश्न

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).

परीक्षेसाठी टीप

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.