DESIGN AND ANALYSIS OF ALGORITHMS (NCS-501)
B.Tech | Semester V | Section-wise Important Questions & Notes
SECTION A – Very Short Answer (2 × 10 = 20 Marks)
This section focuses on definitions, comparisons, and basic complexity analysis.
Answers should be short, direct, and to the point.
Important Questions
Difference between Binary Tree and Complete Binary Tree
Difference between Greedy Technique and Dynamic Programming
Solve recurrence using Master Method
Most practically used sorting algorithm and its time complexity
Find time complexity of given recurrence relations
Explain Single Source Shortest Path
Define Graph Coloring
Compare Time Complexity and Space Complexity
Characteristics of a good algorithm
Difference between Backtracking and Branch & Bound
Key Notes
Greedy → locally optimal choice; DP → optimal substructure + overlapping subproblems
Master Method is very important (practice all cases)
Practical sorting: Quick Sort / Merge Sort
Single source shortest path → finds shortest paths from one vertex to all others
Backtracking explores all possibilities; Branch & Bound prunes search space
SECTION B – Medium Answer (Attempt Any 3, 10 × 3 = 30 Marks)
This section is very important and often includes step-wise explanations and examples.
Important Questions
Solve recurrence using Recursion Tree Method
B-Tree insertion (degree t = 3) with given keys
Explain Minimum Cost Spanning Tree (MST) and Kruskal’s Algorithm with time complexity
Explain Red-Black Tree and insertion algorithm
Explain Heap Sort and illustrate it on a given array
Key Notes
Recursion tree → expand recurrence step by step
B-Tree questions are diagram-based and scoring
Kruskal’s Algorithm uses greedy approach + union-find
Red-Black Tree maintains balance using coloring rules
Heap Sort → build heap + repeated deletion (O(n log n))
SECTION C – Shortest Path / Geometry (10 Marks)
Important Questions
Explain Convex Hull Problem
Find shortest path using Dijkstra’s Algorithm from a given source
Key Notes
Convex hull → smallest polygon enclosing all points
Dijkstra → single source shortest path (no negative edges)
Write step-wise table for Dijkstra (very important for marks)
