(SEM V) THEORY EXAMINATION 2022-23 DESIGN & ANALYSIS OF ALGORITHM
Course: B.Tech (Semester V) Subject Code: KCS-503
Subject Name: Design & Analysis of Algorithm Time: 3 Hours
Total Marks: 100
Note: Attempt all sections. If data is missing, assume suitably.
Section A – Short Answer Questions (2 × 10 = 20 Marks)
Answer all briefly:
Basic steps in the development of an algorithm.
Compare best and worst time complexity of Quick Sort. Discuss Skip List and its operations.
Properties of Binomial Trees. Applications of the Graph Coloring Problem.
Define the Principle of Optimality. Differentiate between Backtracking and Branch and Bound.
Explain the backtracking problem-solving approach.
Define NP, NP-Hard, NP-Complete problems with examples.
Explain Randomized Algorithms.
Section B – Descriptive Questions (10 × 3 = 30 Marks)
Attempt any three:
Explain Merge Sort algorithm and sort the sequence {23, 11, 5, 15, 68, 31, 4, 17}.
Difference between Binomial Heap and Fibonacci Heap.
Prove that distinct edge weights in a connected graph yield a unique Minimum Spanning Tree (MST). Explain Kruskal’s Algorithm.
Discuss the Longest Common Subsequence (LCS) algorithm with time complexity.
Apply Naïve String Matching on pattern P = aab and text T = acaabc.
Section C – Long Answer Questions (10 × 5 = 50 Marks)
Q3
(a) Solve recurrence relations:
T(n)=T(n−1)+n4T(n) = T(n-1) + n^4T(n)=T(n−1)+n4
T(n)=T(n/4)+T(n/2)+n2T(n) = T(n/4) + T(n/2) + n^2T(n)=T(n/4)+T(n/2)+n2
or
(b) Explain Counting Sort Algorithm and apply it to array {0,1,3,0,3,2,4,5,2,4,6,2,2,3}.
Q4
(a) Insertion cases in a Red-Black Tree for {15,13,12,16,19,23,5,8} and show that height ≤ 2log(n+1).
or
(b) Write algorithm for Union of Two Binomial Heaps and its time complexity.
Q5
(a) Explain Greedy Algorithm. Write pseudocode to prove Fractional Knapsack problem satisfies the greedy-choice property.
or
(b) Define Single Source Shortest Path and write Dijkstra’s Algorithm.
Q6
(a) Solve Subset Sum Problem using recursive Backtracking for
w=5,7,10,12,15,18,20w = {5,7,10,12,15,18,20}w=5,7,10,12,15,18,20, m=35m = 35m=35. Draw the State Space Tree.
or
(b) Explain N-Queen Problem, and solve 4-Queen Problem using backtracking.
Q7
(a) Explain String Matching Algorithm and Rabin-Karp Method with examples.
or
(b) Define Approximation Algorithm. Discuss the Set Cover Problem using it.
Related Notes
BASIC ELECTRICAL ENGINEERING
ENGINEERING PHYSICS THEORY EXAMINATION 2024-25
(SEM I) ENGINEERING CHEMISTRY THEORY EXAMINATION...
THEORY EXAMINATION 2024-25 ENGINEERING MATHEMATICS...
(SEM I) THEORY EXAMINATION 2024-25 ENGINEERING CHE...
(SEM I) THEORY EXAMINATION 2024-25 ENVIRONMENT AND...
Need more notes?
Return to the notes store to keep exploring curated study material.
Back to Notes StoreLatest Blog Posts
Best Home Tutors for Class 12 Science in Dwarka, Delhi
Top Universities in Chennai for Postgraduate Courses with Complete Guide
Best Home Tuition for Competitive Exams in Dwarka, Delhi
Best Online Tutors for Maths in Noida 2026
Best Coaching Centers for UPSC in Rajender Place, Delhi 2026
How to Apply for NEET in Gurugram, Haryana for 2026
Admission Process for BTech at NIT Warangal 2026
Best Home Tutors for JEE in Maharashtra 2026
Meet Our Exceptional Teachers
Discover passionate educators who inspire, motivate, and transform learning experiences with their expertise and dedication
Explore Tutors In Your Location
Discover expert tutors in popular areas across India
Discover Elite Educational Institutes
Connect with top-tier educational institutions offering world-class learning experiences, expert faculty, and innovative teaching methodologies