(SEM V) THEORY EXAMINATION 2017-18 DESIGN AND ANALYSIS OF ALGORITHMS

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)