Q1: Define Algorithm.
List Characteristics of an algorithm
A: An algorithm is a step-by-step procedure to solve a problem. Characteristics: finiteness, correctness,
input/output, feasibility, and effectiveness. Example: Binary Search algorithm.
Q2: Define the terms time & space complexity.
A: Time complexity is the time taken by an algorithm as a function of input size. Space complexity is the
memory used during execution. Example: Binary Search → Time: O(log n), Space: O(1).
Q3: List different types of asymptotic notations.
A: Asymptotic notations describe algorithm efficiency. Common types: Big-O (upper bound), Ω (lower bound),
and Θ (tight bound). Example: Linear Search → O(n).
Q4: Define Balanced Binary search tree.
A: A Balanced BST is a tree where the height difference between left and right subtrees is minimal. It ensures
efficient operations. Example: AVL Tree.
Q5: Define AVL Tree.
A: AVL Tree is a self-balancing BST where the height difference between left and right subtrees (balance factor)
is at most 1. Example: Insertions trigger rotations.
Q6: Explain the difference between binary search tree and AVL Tree.
A: BST allows unbalanced growth, leading to O(n). AVL Tree maintains balance, ensuring O(log n). Example:
AVL uses rotations during insert/delete.
Q7: Define B-Tree and List Properties of B-Tree.
A: B-Tree is a self-balancing search tree used in databases and file systems. Properties: multiple children,
sorted keys, all leaves at same level. Example: Order-3 B-Tree.
Q8: Discuss the procedure to perform delete operation from B-Tree.
A: Steps: (1) Find key, (2) Delete if in leaf, (3) If in internal node, replace with predecessor/successor, (4)
Rebalance. Example: Delete 30 in B-Tree.
Q9: List Applications of B-trees.
A: Used in databases, file systems, and indexing for efficient disk access. Example: NTFS uses B+ Trees.
Q10: Some sample problems related to asymptotic notations.
A: Example: T(n)=3n+2 → O(n). T(n)=2n²+5n+1 → O(n²). T(n)=log n+3 → O(log n).
Q11: Some sample problems related to step count calculation.
A: Single Loop: for(i=0;i<n;i++) → O(n). Nested Loop: → O(n²). Recursion: Fibonacci → O(2^n).
Q12: Justify the importance of rotations in AVL Tree. List various types of rotations.
A: Rotations restore balance in AVL Trees. Types: Left, Right, Left-Right, Right-Left. Example: LL rotation when
imbalance is on left-left side.
UNIT – 2: Short Answer Questions (2 Marks)
Q1: Define Heap and specify its properties.
A: Heap is a complete binary tree following heap property. Max-Heap: parent ≥ children; Min-Heap: parent ≤
children. Example: Priority Queue.
Q2: List the differences between Binary Tree and Binary Heap.
A: Binary Tree has no order, may be incomplete. Binary Heap is complete and satisfies heap order. Example:
Max-Heap for quick max retrieval.
Q3: List the differences between Max-Heap and Min-Heap.
A: Max-Heap root is maximum, Min-Heap root is minimum. Used in scheduling and shortest path. Example:
Dijkstra’s uses Min-Heap.
Q4: List applications of Heaps.
A: Used in Priority Queues, Heap Sort, Graph algorithms (Prim’s, Dijkstra’s). Example: CPU scheduling with
Priority Queue.
Q5: Define Graph. List various representations of graph.
A: Graph = set of vertices and edges. Representations: Adjacency Matrix, Adjacency List, Edge List. Example:
Social network graph.
Q6: Example Problem – Represent a Graph in adjacent matrix and list.
A: For V={A,B,C}, E={(A,B),(B,C)} → Matrix: [[0,1,0],[0,0,1],[0,0,0]], List: A->[B], B->[C], C->[].
Q7: Define the terms edge, path and cycle.
A: Edge connects two vertices, path is a sequence of edges, cycle is a closed path. Example: A→B→C→A is a
cycle.
Q8: Define the terms connected graph and bi-connected graph.
A: Connected: all vertices reachable. Bi-connected: remains connected even after removing a vertex. Example:
Triangle graph is bi-connected.
Q9: Define articulation point.
A: A vertex whose removal increases the number of connected components. Example: In A-B-C, B is
articulation point.
Q10: What is connected component and strongly connected component.
A: Connected component: reachable set in undirected graph. Strongly Connected Component: all vertices
reachable both ways in directed graph. Example: Directed cycle.
Q11: List various types of graph traversal techniques.
A: BFS (level-wise) and DFS (depth-wise). Example: BFS finds shortest path in unweighted graphs.
Q12: List the differences between BFS and DFS.
A: BFS uses Queue, level order. DFS uses Stack/Recursion, explores deep first. Both O(V+E). Example: BFS
shortest path.
Q13: Define Bi-connected Component.
A: Maximal subgraph where removing any vertex doesn’t disconnect it. Example: Cycle graph is bi-connected.
Q14: List applications of divide and conquer.
A: Used in Binary Search, Merge Sort, Quick Sort, Matrix Multiplication. Example: Merge Sort O(n log n).
Q15: Write control abstraction of divide and conquer.
A: Divide: split into subproblems, Conquer: solve recursively, Combine: merge solutions. Example: Binary
Search.
Q16: Simple example problem – solving recurrence relation.
A: T(n)=2T(n/2)+n → O(n log n) (Merge Sort). T(n)=T(n/2)+1 → O(log n) (Binary Search).
