Shared by a Veda learner · Generated with Veda AI
This is the complete GTU Semester 5 exam paper for Analysis and Design of Algorithms (3150703). The paper is divided into five main questions (Q.1 to Q.5), each with three sub-parts (a, b, c). Sub-part (c) of Q.2, Q.3, Q…
Full explanation, worked examples & memory tricks in the app
Every question in the paper gets a full exam-length answer in the app — organised by marks, the way a topper writes it.
Derive the time complexity of Heap Sort step by step with suitable justification.
Heap Sort has O(n) for building the heap and O(n log n) for the extraction phase, resulting in a total time complexity of O(n log n).
The full exam-length answer is in the app.
Derive the recurrence relation and solve it for Merge Sort using the Master Theorem.
The recurrence is T(n) = 2T(n/2) + n, which solves to O(n log n) using the Master Theorem.
The full exam-length answer is in the app.
Solve the 0/1 Knapsack problem using dynamic programming for the given data: Weights = [2, 3, 4, 5], Values = [3, 4, 5, 6], Capacity = 5.
The maximum value is 7 (items 1 and 2).
The full exam-length answer is in the app.
For the two strings X = AGGTAB and Y = GXTXAYB, find the Longest Common Sub-sequence using Dynamic Programming.
The LCS length is 4 (e.g., 'GTAB').
The full exam-length answer is in the app.
Find the Minimum Spanning Tree using Kruskal’s algorithm for the following graph: Vertices = {A, B, C, D, E} Edges with weights: A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-E: 5, D-E: 2.
The MST includes edges B-C (1), A-B (2), D-E (2), A-C (3) with a total weight of 8.
The full exam-length answer is in the app.
Given items with weights (w) and profits (p): Item 1: (w=10, p=60), Item 2: (w=20, p=100), Item 3: (w=30, p=120), Capacity (W)=50. Solve using the Greedy method based on profit/weight ratio.
The maximum profit is 240 (items 1 and 2 fully, and 2/3 of item 3).
The full exam-length answer is in the app.
Describe the Travelling Salesman Problem (TSP). Why is it considered NP-hard? Discuss any one approximation algorithm for TSP.
TSP finds the shortest possible route visiting each city once and returning to the origin; it is NP-hard because no polynomial-time solution exists, and a 2-approximation algorithm uses MST.
The full exam-length answer is in the app.
Explain the class P SPACE and how it differs from P and NP. Provide suitable examples of P SPACE problems.
PSPACE is the class of problems solvable with polynomial space, regardless of time; it contains both P and NP, and examples include QBF (Quantified Boolean Formula) and generalized chess.
The full exam-length answer is in the app.
Describe the Multiplying Large Integers Problem using Divide and Conquer.
It splits large integers into halves and uses the formula (a*10^(n/2) + b)(c*10^(n/2) + d) to reduce the number of multiplications, achieving O(n^1.585) complexity.
The full exam-length answer is in the app.
Solve the recurrence relation T(n) = 2T(n/2) + n using the Master Theorem.
T(n) = O(n log n).
The full exam-length answer is in the app.
Perform Depth First Search (DFS) starting from vertex A for the graph: Vertices: A, B, C, D, E Edges: (A, B), (A, C), (B, D), (C, D), (D, E). Write the order of traversal.
A, B, D, E, C (or A, C, D, E, B).
The full exam-length answer is in the app.
Explain the amortized analysis technique with an example.
Amortized analysis averages the time cost of operations over a sequence, providing a worst-case bound on the average performance, e.g., dynamic array insertion.
The full exam-length answer is in the app.
Explain the Huffman Coding algorithm with a suitable example and construct the Huffman Tree.
Huffman Coding builds a binary tree by repeatedly merging the two least frequent nodes, assigning shorter codes to more frequent characters.
The full exam-length answer is in the app.
Describe the Knapsack Problem and mention why the Greedy approach works for the fractional version but not for the 0/1 version.
Greedy works for fractional because we can take parts of items, but for 0/1, taking a locally optimal item may prevent taking a better combination of other items.
The full exam-length answer is in the app.
Find one possible topological ordering for the directed graph with edges: (5→2), (5→0), (4→0), (4→1), (2→3), (3→1).
A valid topological order is 5, 4, 2, 3, 1, 0.
The full exam-length answer is in the app.
For the Rabin-Karp algorithm, given T = '31415926535', P = '26', base d = 10, and prime q = 13: Compute hash values of pattern and first few text substrings. Identify matching positions.
The pattern hash is 0, and it matches the substring at position 6 (0-indexed).
The full exam-length answer is in the app.
Given text T = 'AABAACAADAABAABA' and pattern P = 'AABA', trace the Knuth-Morris-Pratt algorithm execution step-by-step. Show all comparisons and matched positions.
The pattern 'AABA' is found at positions 0, 9, and 12.
The full exam-length answer is in the app.
Define domain, co-domain, and range of a function.
Domain is the set of all possible inputs, co-domain is the set of all possible outputs, and range is the set of actual outputs produced.
The full exam-length answer is in the app.
Perform Counting Sort on the input array A = [4, 2, 2, 8, 3, 3, 1]. Show all steps counting array, cumulative count, and the final sorted output.
The sorted output is [1, 2, 2, 3, 3, 4, 8].
The full exam-length answer is in the app.
Explain the Principle of Optimality in Dynamic Programming with a suitable example.
The Principle of Optimality states that an optimal solution to a problem contains optimal solutions to its subproblems, e.g., in the shortest path problem.
The full exam-length answer is in the app.
State and explain the basic characteristics of problems that can be solved using Dynamic Programming.
Problems must have overlapping subproblems and an optimal substructure property.
The full exam-length answer is in the app.
Explain the basic concepts of graphs with suitable examples. Differentiate between directed and undirected graphs.
A graph is a set of vertices and edges; in directed graphs edges have a direction, while in undirected graphs they do not.
The full exam-length answer is in the app.
Explain the Breadth First Search (BFS) algorithm. Illustrate the traversal process using an example graph.
BFS explores all neighbors at the present depth before moving to nodes at the next depth level, using a queue.
The full exam-length answer is in the app.
Discuss the Eight Queens Problem in detail. Write the backtracking algorithm and demonstrate the solution process.
The Eight Queens problem places 8 queens on an 8x8 board so no two attack each other, solved via backtracking by placing queens column by column and checking for conflicts.
The full exam-length answer is in the app.
Explain the Travelling Salesman Problem (TSP) using the Branch and Bound approach with a suitable example.
Branch and Bound for TSP explores the solution tree, using a lower bound (e.g., reduced cost matrix) to prune branches that cannot yield a better solution than the current best.
The full exam-length answer is in the app.
The full Veda Bites deck, complete notes, spaced-repetition flashcards, leveled MCQs, tests and games for this kit — plus Daily Facts and the Arena, every day.