GUJARAT TECHNOLOGICAL UNIVERSITY

Program Name: Bachelor of Engineering

Level: UG
Subject Code: BE04000241
Subject Name: Analysis and Design of Algorithms

WEF Academic Year 2024-25

Semester 4
Category of the Course PCC

Prerequisite : Data Structure, Programming

Rationale : Developing efficient algorithms is crucial in modern computer engineering, as
today's applications demand optimized performance in terms of time, space, and
energy. This course provides the knowledge and skills to understand and analyze
efficient algorithms for a wide range of applications.

Course Outcome :
After Completion of the Course, Student will able to :
RBT
No Course Outcomes
Level*
01 Identify Time and Space complexities of various algorithms RM
02 Solve and analyze the problems divide and conquer methods UN
03 Solve and analyze the problems using greedy and dynamic programming AP
04 Understand and solve graph based problems CR
05 Apply backtracking and branch and bound methods to solve various problems EL

*RM: Remember, UN: Understand, AP: Apply, AN: Analyze, EL: Evaluate, CR: Create

Course Scheme :

Teaching - Learning Scheme Total Assessment Pattern and Marks Total

(in Hours per Semester) Credits Marks
L T P PBL* TH = Theory Tutorial / Practical
TH/30
ESE PA PA PBL ESE
(E) (M) (I) (I) (V)
45 0 30 45 120 04 70 30 20 30 50 200
* Problem Based Learning (PBL) aims to accommodate learning beyond syllabus as per clause
9.4 of NBA manual.

w.e.f. 2025-26 [Link] Page 1 of 5

 GUJARAT TECHNOLOGICAL UNIVERSITY
Program Name: Bachelor of Engineering
Level: UG
Subject Code: BE04000241
Subject Name: Analysis and Design of Algorithms
Course Content:
Sr. No. of % of
Course Content
No. Hours Weightage
Introduction and Analysis of Algorithm: Introduction to algorithm,
Properties of good algorithm, Average, Best and worst case analysis,
1 4 10
Asymptotic Notations (Big Oh, Big Theta, Big Omega), Disjoint set
operations, Union and find algorithms,
Analysis of Sorting Algorithms: Comparison based sorting: Bubble
2 sort, Selection sort, Insertion sort, Heap sort, Sorting in linear time : 6 15
Bucket sort, Radix sort and Counting sort
Divide and Conquer: Introduction, General method, Recurrence and
different methods to solve recurrence, Problem solving using Divide
3 and Conquer: Binomial Coefficient, Binary Search, Max-Min 6 15
problem, Merge Sort, Quick Sort, Quick sort using median of three,
Matrix Multiplication, Exponential.
Dynamic Programming: Introduction, General method, Elements of
Dynamic Programming, The Principle of Optimality
Problem Solving using Dynamic Programming: Binomial Coefficient,
4 6 15
Making Change Problem, Knapsack problem, Matrix chain
multiplication, Longest Common Subsequence, Shortest Common
Supersequence
Greedy Algorithm: Introduction, General method, Characteristics of
greedy algorithms, Elements of greedy strategy
5 Problem solving using Greedy method: Making change problem, 5 10
Activity selection problem, Knapsack problem (0/1 and Fractional),
Job Scheduling Problem,
Graph Algorithms: Introduction, Types of graph, Representation
6 Graph, Traversing Graphs: Depth First Search, and Breath First 6 15
Search, Topological sort, Strongly Connected components.

w.e.f. 2025-26 [Link] Page 2 of 5

 GUJARAT TECHNOLOGICAL UNIVERSITY
Program Name: Bachelor of Engineering
Level: UG
Subject Code: BE04000241
Subject Name: Analysis and Design of Algorithms

Problems solving: Finding articulation point, Minimum Spanning

trees (Kruskal’s algorithm, Prim’s algorithm) using greedy approach,
Single pair shortest path using greedy method, All Points Shortest
path using Dynamic Programming,
Backtracking: Introduction, General method, n-queen problem, Sum
of subset problem, Graph coloring problem, Hamiltonian cycle
7 problem, 6 15
Branch and Bound: General method, LC branch and bound, FIFO
branch and bound, Traveling salesman problem, Knapsack problem
Introduction to NP-Completeness: The class P and NP, Polynomial
8 3 05
reduction, NP- Complete Problems, NP-Hard Problems.
Total 42 100

Suggested Course Practical List:

1. Perform following sorting operation and measure the execution time for sufficient large input:
Selection Sort, Bubble Sort, Insertion Sort
2. Implement Linear search and Binary Search
3. Perform following sorting operation and measure the execution time for sufficient large input:
Merge Sort, Quick Sort
4. Solve Given Problems using Greedy Strategy: Make a change problem, Activity Selection
5. Solve Given Problems using Greedy Strategy: Problem, 0/1 Knapsack Problem, Job Scheduling
Problem
6. Solve Given Problems using Greedy Strategy: MST using Prim’s Algorithm, MST using
Krushkal’s Algorithm
7. Solve Given Problems Using Dynamic Programming: Make a change problem, 0/1 Knapsack
Problem
8. Solve Given Problems Using Dynamic Programming: Matrix Chain Multiplication

9. Solve Given Problems Using Dynamic Programming: Longest Common Subsequence (LCS),
Shortest Common Supper sequence (SCS)
10. Solve following problems using Backtracking 4-Queen Problem, 8-Queen Problem

w.e.f. 2025-26 [Link] Page 3 of 5

Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V EXAMINATION – WINTER 2025
Subject Code:3150703 Date:02-12-2025
Subject Name: Analysis and Design of Algorithms
Time:10:30 AM TO 01:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS
Q.1 (a) State the time complexity of following problems in descending order: 03
Matrix multiplication, inserting element in binary search tree, inert node
at beaning in linked list, linear search, selection sort, merge sort.
(b) Summarize and explain the properties of algorithm 04
(c) Apply bubble sort on the given data sequence: 77, 22, 55, 11, 33, 66, 44 07

Q.2 (a) Write the algorithm for binary search 03

(b) Identify the constant c, n0 and upper bound for given recurrences: 04
T(n) = 4n2 + 3n – 4
T(n) = 6n3 – 8n2 + 9n + 2
(c) Illustrate and solve recurrence for best and worst case of quick sort 07
OR
(c) Construct solution using Merge sort on the given data sequence: 88, 77, 07
22, 55, 11, 33, 66, 99, 44. Also state its recurrence and solve it.
Q.3 (a) Define principle of Optimality. Discuss with example. 03
(b) Differentiate: Dynamic programming vs divide and conquer 04
(c) Solve following instance of knapsack problem using dynamic 07
programming: W = [1, 2, 5, 6, 10], V = [1, 6, 18, 22, 30] and Knapsack
capacity M = 12
OR
Q.3 (a) Define the characteristics of greedy algorithms 03
(b) Explain activity selection problem. 04
(c) Infer the Longest Common Subsequence for following strings: X = 07
10010100 Y = 10011

Q.4 (a) State and explain methods to represent the graph 03

(b) Differentiate: BFS vs DFS 04

1
 (c) Outline algorithm for Prim’s method and find MST for given graph 07
using Prim’s method

Figure 1
OR
Q.4 (a) Define Articulation point, Acyclic Directed Graph, Back Edge 03
(b) Find prefix code for given data. A: 45, B: 30, C: 15, D: 12, E: 8 04
(c) Outline algorithm for Kruskal’s method and find MST for the graph 07
given in Figure 1, using Kruskal’s method
Q.5 (a) Show naïve string matching algorithm with example. 03
(b) Find topological sequence of vertices for the graph given in Figure 1. 04
Consider A is starting vertex.

A - D - C - F - B - E

(c)Explain backtracking method. What is 4 queen problem? Show its all 07

possible solutions.
OR
Q.5 (a) Explain polynomial time reduction 03
(b) Compare and contrast: Backtracking vs. Branch and Bound 04
(c) What do you mean by spurious hits? For modulo q=13, how many 07
spurious hits does the Rabin-Karp encounters for the text T =
4359023141526739921 when looking for the pattern P = 31415?

*************

2
Enrolment No./Seat No_______________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V EXAMINATION – SUMMER 2025
Subject Code:3150703 Date:28-05-2025
Subject Name:Analysis and Design of Algorithms
Time:02:30 PM TO 05:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS

Q.1 (a) Find Big-oh (O) notation of following functions 03

f(n)=3n6 + 2 n * lg n + 6n, h(n)= 3n2+ 6n*lgn+ 2n2.5
(b) Define Omega and Theta notations with graph. 04
(c) Write binary search algorithm and analyze it for worst case time 07
complexity. Represent its time complexity using Big-oh (O) notation.

Q.2 (a) Prove that (n + 6)3 = Ө( n3). 03

(b) If P(n) = a0+ a1 n + a2 n2 + . . . . . . + amnm then prove that P(n) = Ω(nm). 04
Here a0, a1, a2 …..am are constants and am>0.
(c) Solve following recurrence relation using suitable method and express 07
your answer using Big-oh (O) notation.
T(n) = T(n/6) + T(5n/6) + Ө(n)
OR
(c) Solve following recurrence relations using suitable method and express 07
your answer using Big-oh (O) notation.
1. T(n) = 2 T(n/2) + n log n 2. T(n) = 4 T(n/4) + n
Q.3 (a) Arrange the following growth rates from the lowest to highest asymptotic 03
order:
O(n log n), O(n2n), Ω(log n), O(n0.5), O(n!), Ω(2n), O(n0.5 log n)
(b) Write the recurrence relation for the quick sort on input instance: 15, 19, 04
20, 25, 32, 37, 50, 62, 70. Comment on the nature of input i.e. best case,
average case or worst case.
(c) Write greedy algorithm for activity selection problem. Give its time 07
complexity. For following intervals, select the activities according to your
algorithm. I1 (1-3), I2 (0-2), I3 (3-6), I4 (2-5), I5 (5-8), I6 (3-10), I7 (7-9).

OR
Q.3 (a) Prove that Log(√n ) = O(log n). 03
(b) Write any algorithm (need not to have meaningful) which has a time 04
complexity of O(1) and also includes a loop statement. Also, confirm its
time complexity of O(1) using tabular method.

1
 (c) Write DFS traversal and draw DFS tree corresponds to following graph. 07
Also, write time complexity of DFS algorithm.

G A B

D E

F
H

Q.4 (a) What is Principle of Optimality in dynamic programming? Explain it with 03

example.
(b) What is knapsack problem? Using greedy algorithm find an optimal 04
solution for fractional knapsack instance n=7, M =17, profits p[ ] =
{10,5,15,7,6,16,4} and weights w[ ] = {2,3,5,7,1,4,1}.
(c) Find the optimal way of multiplying following matrices using dynamic 07
programming. Also indicate optimal number of multiplications required.
A:2 x 3, B: 3 x 5, C:5 x 6, D: 6 x 2, E: 2 x 3
OR
Q.4 (a) What is the Travelling Salesman Problem (TSP)? Why TSP is considered 03
an NP-hard problem?
(b) Illustrate the working of Kruskal’s algorithm using greedy technique. 04
Take the suitable graph for illustration.
(c) Find the longest common subsequence for the following two sequences 07
using dynamic programming. Show the complete process and indicate the
time complexity.
X = 10101010011
Y = 101001
Q.5 (a) Define P and NP problems. Also give example of each type of problem. 03
(b) Explain the backtracking strategy to solve optimization problem. Explain 04
how it can be applied to find the solution for 4-queen problem.
(c) Given a text and a pattern, write the naive string matching algorithm to 07
find all occurrences of the pattern in the text. Use the text
"ABCABCABC" and the pattern "ABC". Also, give time complexity of
naive string matching algorithm.
OR
Q.5 (a) What is a polynomial reduction? Explain its role in proving NP- 03
completeness.
(b) Give example of any NP complete problem. Explain how to prove that 04
particular problem is NP complete.
(c) Show that Hamiltonian cycle is a NP problem. 07

*************

2
Enrolment No./Seat No_______________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2024
Subject Code:3150703 Date:17-12-2024
Subject Name:Analysis and Design of Algorithms
Time:10:30 AM TO 01:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

Marks
Q.1 (a) Define the following terms: 03
i) Function in mathematics ii) Linear inequalities
(b) Explain the need of amortized notation. Explain with suitable example. 04
(c) Write an algorithm for insertion sort. Calculate the best, average and worst 07
case complexity of it.

Q.2 (a) Sort the following elements using counting sort. 03

2, 5, 3, 0, 2, 3, 0, 3
(b) Sort the following elements using bucket sort. 04
10, 21, 29, 41, 52
(c) Write the Master theorem. Solve following recurrence using it. 07
(i)T(n)= 3T(n/2) + n2
(ii) T(n)=2T(n/2) + n log n
OR
(c) Write binary search algorithm using recursion. Derive its recurrence 07
relation. Calculate its complexity using master theorem.

Q.3 (a) Explain the steps of greedy strategy for solving a problem. 03
(b) Write an algorithm for Max-Min problem using divide and conquer 04
approach. Calculate its complexity.
(c) The matrices A(5X10), B(10X15), C(15X20), and D(20X25) are given. 07
Solve the matrix chain multiplication problem using dynamic programming.
OR
Q.3 (a) Enlist the general characteristics of greedy algorithms. 03
(b) Write an algorithm for matrix multiplication using divide and conquer 04
approach. Calculate its complexity.
(c) For the given set of items and knapsack capacity = 5 kg, find the optimal 07
solution for the 0/1 knapsack problem using dynamic programming.
Item Weight Value
I1 2 3
I2 3 4
I3 4 5
I4 5 6

Q.4 (a) Explain DFS with suitable example. 03

(b) Enlist the advantages and disadvantages of dynamic programming. 04

1
 (c) Define minimum spanning tree. Explain Prim’s algorithm with suitable 07
example.
OR
Q.4 (a) Explain BFS with suitable example. 03
(b) Define principal of optimality. Explain its use in Dynamic Programming 04
Method.
(c) "A greedy strategy will work for fractional Knapsack problem but not for 07
0/1", is this true or false? Explain with suitable example.

Q.5 (a) Define string matching problem. Define valid shift and invalid shift. 03
(b) Define the followings: 04
i) Articulation point ii) Acyclic Directed Graph iii) Back Edge iv) Tree
(c) Explain P, NP, NP complete and NP-Hard problems. Give examples of each. 07
OR
Q.5 (a) Explain Backtracking Method. Give solutions for 4-queens problem using 03
backtracking method.
(b) Explain in-order, pre-order and post-order traversals of the graph. 04
(c) Write short note on the followings: 07
i) Approximation algorithms
ii) Randomized algorithms

****************

2
Enrolment No./Seat No_____________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2024
Subject Code:3150703 Date:31-05-2024
Subject Name:Analysis and Design of Algorithms
Time:02:30 PM TO 05:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS
Q.1 (a) Find Omega (Ω) notation of function f(n)=2n2 + n * lg n + 6n 03
(b) Define Big-oh and Theta notations with graph 04
(c) Write and analyze an insertion sort algorithm to sort n items into ascending order. 07

Q.2 (a) Explain: Articulation Point, Graph, Tree 03

(b) Solve following recurrence using Master Theorem: 04
T(n) = 3T(n/3) + n^3.
(c) Illustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 50, 07
52, 60. Comment on the nature of input i.e. best case, average case or worst case.
OR
(c) What is recurrence? Explain recursion-tree method with suitable example. 07

Q.3 (a) What is Principle of Optimality? Explain its use in Dynamic Programming Method 03
(b) Explain Binomial Coefficient algorithm using dynamic programming. 04
(c) Obtain longest common subsequence using dynamic programming. Given A = 07
“acabaca” and B = “bacac”.
OR
Q.3 (a) Explain the steps of greedy strategy for solving a problem 03
(b) Demonstrate Binary Search method to search Key = 14, form the array 04
A=<2,4,7,8,9,10,12,14,18>
(c) What is a minimum spanning tree? Draw the minimum spanning tree correspond 07
to following graph using Prim’s algorithm.

Q.4 (a) Explain Tower of Hanoi Problem, Derive its recursion equation and computer it’s 03
time complexity.
(b) Using greedy algorithm find an optimal schedule for following jobs with n=7 04
profits: (P1, P2, P3, P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline (d1, d2,
d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)

1
 (c) Solve the following Knapsack Problem using greedy method. Number of items = 07
5, knapsack capacity W = 100, weight vector = {50, 40, 30, 20, 10} and profit
vector = {1, 2, 3, 4, 5}.
OR
Q.4 (a) What are the disadvantages of greedy method over dynamic programming method? 03
(b) Find an optimal Huffman code for the following set of frequency. A : 50, b: 20, c: 04
15, d: 30
(c) Consider a Knapsack with the maximum weight capacity M is 7, for the objects 07
with value [12,10,20,15] with weights [2,1,3,2] solve using dynamic programming
the maximum value the knapsack can have.
Q.5 (a) Define NP-Complete and NP-Hard problems. 03
(b) Draw the state space tree Diagram for 4 Queens problem. 04
(c) Find all pair of shortest path using Floyd’s Algorithm for following graph. 07

OR
Q.5 (a) Define BFS. How it is differ from DFS. 03
(b) Explain the naive string matching algorithm. 04
(c) Explain spurious hits in Rabin-Karp string matching algorithm with example. 07
Working modulo q=13, how many spurious hits does the Rabin Karp matcher
encounter in the text T = 2359023141526739921 when looking for the pattern P =
31415?

*************

2
 Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2023
Subject Code:3150703 Date:20-12-2023
Subject Name: Analysis and Design of Algorithms
Time:10:30 AM TO 01:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS
Q.1 (a) What is an algorithm? Explain various properties of an algorithm. 03
(b) Solve the following using Master’s theorem: 04
a. T(n) = 2T(n/4) + 1
b. T(n)=3T(n/4) + nlgn
(c) Write selection sort algorithm and compute running time of algorithm. 07

Q.2 (a) Explain general characteristics of greedy algorithms. 03

(b) What is asymptotic notation? Find out big-oh notation of the f(n) = 3n2+5n+10 04
(c) Illustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 07
50, 52, 60. Comment on the nature of input i.e. best case, average case or worst
case. Also discuss worst and best case of quick sort algorithm.
OR
(c) Give the properties of Heap Tree. Sort the following data using Heap Sort 07
Method: 20, 50, 30, 75, 90, 60, 80, 25, 10, 40.
Q.3 (a) Sort the List “G,U,J,A,R,A,T,S,A,R,K,A,R” in alphabetical order using merge 03
sort.
(b) Following are the details of various jobs to be scheduled on multiple processors 04
such that no two processes execute at the same on the same processor. Show
schedule of these jobs on minimum number of processors using greedy approach.
Jobs J1 J2 J3 J4 J5 J6 J7
Start time 0 3 4 9 7 1 6
Finish time 2 7 7 11 10 5 8
(c) Using algorithm find an optimal parenthesization of a matrix chain product 07
whose sequence of dimension is (5,10,3,12,5,50,6) (use dynamic programming).
OR
Q.3 (a) Apply counting sort for the following numbers to sort in ascending order. 03
3, 1, 2, 3, 3, 1
(b) Find the Optimal Huffman code for each symbol in following text 04
ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE
(c) Solve following knapsack problem using dynamic programming algorithm with 07
given capacity W=5, Weight and Value are as follows (2,12),(1,10),(3,20),(2,15)
Q.4 (a) Solve the following Task Assignment problem for minimization using following 03
cost matrix. (Cost matrix represents cost of Task T performed by Person P).
T1 T2 T3
P1 10 20 25
P2 20 23 26
P3 12 16 25

1
 (b) Given coins of denominations 2, 3 and 4 with amount to be pay is 5. Find optimal 04
no. of coins and sequence of coins used to pay given amount using dynamic
method.
(c) Write an algorithm to find out the articulation points of an undirected graph. Find 07
out articulation points for the following graph. Consider vertex 0 as the starting
point.

OR
Q.4 (a) Find out the NCR (5) Using Dynamic Method. 03
3
(b) Write the Kruskal’s Algorithm to find out Minimum Spanning Tree. Apply the 04
same and find MST for the graph given below.

(c) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- 07

Queens Problem using Backtracking Method.
Q.5 (a) Demonstrate Binary Search method to search Key = 14, form the array A 03
= <2,4,7,8,10,13,14,60>.
(b) Solve the following knapsack problem using greedy method. Number of items = 04
5, knapsack capacity W = 100, weight vector = {50,40,30,20,10} and profit
vector = {1,2,3,4,5}.
(c) Define P, NP, NP-complete, NP-Hard problems. Give examples of each 07
OR
Q.5 (a) Explain in Brief: Polynomial reduction. 03
(b) Traverse the following graph using Breadth First Search Technique. Also draw 04
BFS Tree for a given graph.

V R S W T X U Y

(c) Explain spurious hits in Rabin-Karp string matching algorithm with example. 07
Working modulo q=13, how many spurious hits does the Rabin-Karp matcher
encounter in the text T = 2359023141526739921 when looking for the pattern P
= 26739?

*************

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE – SEMESTER- V EXAMINATION-SUMMER 2023
Subject Code: 3150703 Date: 03/07/2023
Subject Name: Analysis and Design of Algorithms
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS
Q.1 (a) Define following terms: (i) Big O Notation, (ii) Big Theta Notation, 03
(iii) Big Omega Notation.
(b) Perform Bucket sort for following sequence: 30, 12, 22, 66, 48, 27, 35, 04
43, 47, 41.
(c) Explain the bubble sort algorithm and derive its best case, worst case, 07
and average case time complexity.
Q.2 (a) Define Algorithms and characteristics of algorithms. 03
(b) What is a recurrence? Solve recurrence equation for T (n) =T (n-1) + 1 04
using substitution method.
(c) Discuss Binary search algorithm, also write and solve its recurrence 07
relation.
OR
(c) Explain Merge Sort algorithm with suitable example. 07

Q.3 (a) Explain principle of optimality with suitable example. 03

(b) Explain advantages and disadvantages of dynamic programming. 04
(c) Given the denominations: d1=1, d2=4, d3=6. Calculate for making 07
change of Rs. 8 using dynamic programming.
OR
Q.3 (a) Explain Weighted Graph, Undirected Graph, Directed Graph. 03
(b) Discuss advantages and disadvantages of greedy algorithm. 04
(c) Consider weights w=(3,4,6,5) and profit v=(2,3,1,4) and Knapsack 07
capacity W=8. Find the maximum profit using dynamic approach.

Q.4 (a) Find an optimal Huffman code for the following set of frequency. a : 03
40, b: 20, c: 15, d: 30, e: 10.
(b) Explain depth first traversal using suitable example. 04
(c) Draw the minimum spanning tree correspond to following graph using 07
Prim’s algorithm and find the MST weight:

1
 OR
Q.4 (a) Differentiate between Kruskal’s algorithm and Prim’s algorithm for 03
finding MST.
(b) Explain the need of topological Sort with example. 04
(c) Draw the minimum spanning tree correspond to following graph using 07
Kruskal’s algorithm and find weight of MST:

Q.5 (a) Explain Spurious hits with an example. 03

(b) Write the pseudocode for Naïve String-Matching Algorithm. 04
(c) What is state space tree. How do you solve the Eight queens problem 07
using backtracking with the help of state space tree.
OR
Q.5 (a) Explain polynomial time reduction. 03
(b) Differentiate between Backtracking and Branch-and-Bound 04
algorithms.
(c) Define P, NP, NP complete and NP-Hard problems. Give examples of 07
each.

*************

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:3150703 Date:09-01-2023
Subject Name:Analysis and Design of Algorithms
Time:10:30 AM TO 01:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

Marks
Q.1 (a) Sort the best case running times of all these algorithms in a non-decreasing 03
order.
LCS, Quick-Sort, Merge-Sort, Counting-Sort, Heap-Sort, Selection-Sort,
Insertion-Sort, Bucket-Sort, Strassen’s Algorithm.
(b) State whether the statements are correct or incorrect with reasons. 04
1. O(f(n)) + O(f(n)) = O (2f(n))
2. If 3n + 5 = O(n2) , then 3n + 5 = o(n2)
(c) Explain asymptotic analysis with all the notations and its mathematical 07
inequalities.

Q.2 (a) What is the use of Loop Invariant? What should be shown to prove that an 03
algorithm is correct?
(b) Apply LCS on sequence <A,B,A,C,B,C> for pattern <A,B,C> 04
(c) Write and explain the recurrence relation of Merge Sort. 07
OR
(c) Perform the analysis of a recurrence relation T(n)= 2𝑇 (𝑛) + 𝜃(𝑛2 ) by 07
2
drawing its recurrence tree.

Q.3 (a) Consider the array 2,4,6,7,8,9,10,12,14,15,17,19,20. Show (without 03

actually sorting), how the quick sort performance will be affected with
such input.
(b) "A greedy strategy will work for fractional Knapsack problem but not for 04
0/1", is this true or false? Explain.
(c) Apply Kruskal’s algorithm on the given graph and step by step generate 07
the MST.

FIG:1
Graph G(V,E)

1
 OR
Q.3 (a) Consider an array of size 2048 elements sorted in non-decreasing order. 03
Show how the Binary Search will perform on this size by analysis of its
recurrence relation. Derive the running time.
(b) Explain the steps of greedy strategy for solving a problem. 04
(c) Apply Prim’s algorithm on the given graph in Q.3 (C) FIG:1 Graph 07
G(V,E) and step by step generate the MST.

Q.4 (a) Given is the S-table after running Chain Matrix Multiplication algorithm. 03
Calculate the parenthesized output based on
PRINT_OPTIMAL_PARENTHESIS algorithm. Assume the matrix are
names from A1, A2, ….,An
4 1
3 1 2
2 1 3 3
1 2 3

(b) Explain states, constraints types of nodes and bounding function used by 04
backtracking and branch and bound methods.
(c) Apply the algorithm to find strongly connected components from the 07
given graph.

OR
Q.4 (a) Consider a Knapsack with maximum weight capacity M is 7, for the three 03
objects with value <3, 4, 5> with weights <2, 3, 4> solve using dynamic
programming the maximum value the knapsack can have.

(b) Explain the Minimax principle and show its working for simple tic-tac-toe game 04
playing.
(c) 07
Given is the DAG, apply the algorithm to perform topological sort and
show the sorted graph.

C - G - A - B - F - E

2
Q.5 (a) When can we say that a problem exhibits the property of Optimal Sub- 03
structure?
(b) Create an example of string P of length 7 such that, the prefix function of KMP 04
string matcher returns π[5] = 3, π[3] = 1 and π[1] = 0
(c) Explain the 3SAT problem and show that it is NP Complete. 07
OR
Q.5 (a) Explain Over-lapping Sub-problem with respect to dynamic 03
programming.
(b) Show that if all the characters of pattern P of size m are different, the naïve string 04
matching algorithm can perform better with modification. Write the modified
algorithm that performs better than O(n.m).
(c) Explain with example, how the Hamiltonian Cycle problem can be used to solve 07
the Travelling Salesman problem.

************

3
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:3150703 Date:07/06/2022
Subject Name:Analysis and Design of Algorithms
Time:02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

Marks

Q.1 (a) Define Algorithm, Time Complexity and Space Complexity 03

(b) Explain: Worst Case, Best Case and Average Case Complexity 04
with suitable example.
(c) Sort the following list using quick sort algorithm:< 5, 07
3 ,8 ,1 ,4 ,6 ,2 ,7 > Also write Worst and Best case and Average
case of quick sort algorithm.

Q.2 (a) Write an algorithm of Selection Sort Method. 03

(b) Demonstrate Binary Search method to search Key = 14, form the 04
array
A=<2,4,7,8,10,13,14,60>
(c) Write the Master theorem. Solve following recurrence using it. 07
(i)T(n)= T(n/2) + 1
(ii) T(n)=2T(n/2) + n log n
OR
(c) Solve following recurrence relation using iterative method T(n) = 07
T(n - 1) + 1 with T(0) = 0 as initial condition. Also find big oh
notation

Q.3 (a) What is Principle of Optimality? Explain its use in Dynamic 03

Programming Method
(b) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} 04
(c) Discuss Assembly Line Scheduling problem using dynamic 07
programming with example.
OR
Q.3 (a) Give the characteristics of Greedy Algorithms 03
(b) Give difference between greedy approach and dynamic 04
programming.
(c) Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15, 07
12, 8) find the maximum profit using greedy method.

Q.4 (a) Explain: Articulation Point, Graph, Tree 03

(b) Find Minimum Spanning Tree for the given graph using Prim’s 04
Algorithm.

1
 (c) Explain Breath First Traversal Method for Graph with algorithm 07
with example.
OR

Q.4 (a) Explain Huffman code with Example. 03

(b) Write the Kruskal’s Algorithm to find out Minimum Spanning 04
Tree. Apply the same and find MST for the graph given below

(c) Explain fractional knapsack problem with example. 07

Q.5 (a) What is string-matching problem? Define valid shift and invalid 03
shift.
(b) Define P, NP, NP-Hard and NP-Complete Problem 04
(c) Explain Backtracking Method. What is N-Queens Problem? Give 07
solution of 4- Queens Problem using Backtracking Method.
OR
Q.5 (a) Explain “P = NP ?” problem. 03
(b) Explain Minimax principal. 04
(c) What is Finite Automata? Explain use of finite automata for string 07
matching with suitable example.

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:3150703 Date:17/12/2021
Subject Name:Analysis and Design of Algorithms
Time:02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.
MARKS
Q.1 (a) Define algorithm. Discuss key characteristics of algorithms. 03
(b) Explain why analysis of algorithms is important? Explain: Worst Case, Best 04
Case and Average Case Complexity with suitable example.
(c) Write and analyze an insertion sort algorithm to arrange n items into 07
ascending order.

Q.2 (a) Write an algorithm of Selection Sort Method. 03

(b) Sort the following numbers using heap sort. 04
20, 10, 50, 40, 30
(c) Sort the following list using quick sort algorithm: <50, 40, 20, 60, 80, 100, 07
45, 70, 105, 30, 90, 75> Also discuss worst and best case of quick sort
algorithm.
OR
(c) Apply merge sort algorithm on array A = {2,7,3,5,1,9,4,8}. What is time 07
complexity of merge sort in worst case?
Q.3 (a) What is Principle of Optimality? Explain its use in Dynamic Programming 03
Method
(b) Explain Binomial Coefficient algorithm using dynamic programming. 04
(c) Solve the following 0/1 Knapsack Problem using Dynamic Programming. 07
There are five items whose weights and values are given in following arrays.
Weight w [] = {1,2,5,6,7} Value v [] = {1, 6, 18, 22, 28} Show your
equation and find out the optimal knapsack items for weight capacity of 11
units.
OR
Q.3 (a) Compare Dynamic Programming Technique with Greedy Algorithms 03
(b) Give the characteristics of Greedy Algorithms. 04
(c) Obtain longest common subsequence using dynamic programming. Given A 07
= “acabaca” and B = “bacac”.
Q.4 (a) Using greedy algorithm find an optimal schedule for following jobs with n=7 03
profits: (P1, P2, P3, P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline
(d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)
(b) Find Minimum Spanning Tree for the given graph using Prim’s Algo. 04

1
 (c) Explain in brief Breadth First Search and Depth First Search Traversal 07
techniques of a Graph with Example.
OR
Q.4 (a) Find an optimal Huffman code for the following set of frequency. A : 50, b: 03
20, c: 15, d: 30
(b) Find Minimum Spanning Tree for the given graph using Kruskal Algo. 04

(c) Explain Backtracking Method. What is N-Queens Problem? Give solution 07

of 4- Queens Problem using Backtracking Method
Q.5 (a) Define Articulation point, Acyclic Directed Graph, Back Edge 03
(b) Show the comparisons that naïve string matcher makes for the pattern 04
p=0001 in the text T=000010001010001
(c) Explain spurious hits in Rabin-Karp string matching algorithm with 07
example. Working modulo q=13, how many spurious hits does the Rabin-
Karp matcher encounter in the text T = 2359023141526739921 when
looking for the pattern P = 31415?
OR
Q.5 (a) Explain polynomial reduction. 03
(b) Differentiate branch and bound and back tracking algorithm. 04
(c) Explain P, NP, NP complete and NP-Hard problems. Give examples of each 07

*************

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:3150703 Date:05/10/2021
Subject Name:Analysis & Design of Algorithms
Time:10:30 AM TO 01:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

MARKS
Q.1 (a) Explain Asymptotic notations. 03
(b) What is Principle of Optimality? Explain its use in Dynamic 04
Programming Method.
(c) Explain why algorithm analysis is important. Also explain Worst Case, 07
Best Case & Average Case Complexity of algorithm.

Q.2 (a) Explain Master method for solving Recurrence. 03

(b) Explain Counting Sort algorithm with example. 04
(c) Explain Quick Sort algorithm with suitable example. Also give its 07
complexity analysis.
OR
(c) Explain Binary search algorithm with divide and conquer strategy and 07
show that the solution to the binary search recurrence T(n)= T(n/2) +
Ѳ (1) is T(n) = Ѳ(lgn).

Q.3 (a) Explain general characteristics of Greedy algorithm. 03

(b) Write Kruskal’s algorithm to find Minimum Spanning Tree. 04
(c) Write Huffman code algorithm and Generate Huffman code for 07
following:
Symbol a b c d e
Frequency 35 25 20 12 8
OR
Q.3 (a) Define amortized analysis. Briefly explain any two techniques. 03
(b) Write algorithm to find Minimum Spanning Tree (MST) using Prim’s 04
method.
(c) Using Greedy method find an optimal solution for fractional knapsack 07
problem given below:
n=7, W=15.
Weight (w) 2 3 5 7 1 4 1
Profit (p) 10 5 15 7 6 18 3

Q.4 (a) Explain Optimal Substructure and Overlapping sub problems with 03
suitable example.
(b) Explain All Pair Shortest Path Algorithm. 04
(c) Given two sequences of characters, M=<A,B,C,D,B,A,C,D,F>, 07
N=<C,B,A,F> Obtain the Longest Common Subsequence. Write
equations and necessary steps.

1
 OR
Q.4 (a) Explain: Articulation Point, Graph, Minimum Spanning Tree. 03
(b) Explain Depth First Search algorithm. 04
(c) Solve the following Knapsack Problem using Dynamic Method. Write 07
the equation and steps for solving above problem. n = 5, W = 100
Object 1 2 3 4 5
Weight (w) 10 20 30 40 50
Value (v) 20 30 66 40 60

Q.5 (a) Explain Hamiltonian problem. 03

(b) Explain Knuth-Morris-Pratt string matching algorithm with example. 04
(c) Give state space tree after application of backtracking for Knapsack 07
problem given below and explain it briefly.
Number of objects=4, Capacity of knapsack= W= 8 units. Objects
weight are (2, 3, 4, 5) and values are (3, 5, 6, 10) respectively
OR
Q.5 (a) Explain Branch and Bound technique briefly. 03
(b) Define P, NP, NP-Hard and NP-Complete Problem 04
(c) Explain Rabin-Karp Algorithm for string matching with example and 07
show all necessary steps.

*************

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:3150703 Date:29/01/2021
Subject Name:Analysis & Design of Algorithms
Time:10:30 AM TO 12:30 PM Total Marks: 56
Instructions:
1. Attempt any FOUR questions out of EIGHT questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

MARKS
Q.1 (a) What is an algorithm? Why analysis of algorithm is required? 03
(b) What is asymptotic notation? Find out big-oh notation of the f(n)= 04
3n2+5n+10

(c) Write an algorithm for insertion sort. Analyze insertion sort algorithm 07
for best case and worst case.

Q.2 (a) What is the difference between selection sort and bubble sort? 03
(b) Write iterative and recursive algorithm for finding the factorial of N. 04
Derive the time complexity of both algorithms.
(c) Solve following recurrence relation using iterative method 07
T(n)=2T(n / 2) + n
Q.3 (a) How divide and conquer approach work? 03
(b) Trace the quick sort for data A = {6,5,3,11,10,4,7,9} 04
(c) Explain master theorem and solve the recurrence T(n)=9T(n/3)+n with 07
master method

Q.4 (a) Write the characteristics of greedy algorithm. 03

(b) Trace the merge sort for data A = {6,5,3,11,10,4,7,9} 04
(c) Find minimum spanning tree for the given graph in fig-1 using prim’s 07
algorithm

Fig-1
Q.5 (a) How huffman code is memory efficient compare to fixed length code? 03
(b) Give difference between greedy approach and dynamic programming. 04
(c) Find the Huffman code for each symbol in following text 07
ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE

Q.6 (a) What is principal of optimality? Explain its use in Dynamic 03

Programming Method.
(b) Find out minimum number of multiplications required for multiplying: 04
A[1 × 5], B[5 × 4], C[4 × 3], D[3 × 2], and E[2 × 1].
(c) Solve following knapsack problem using dynamic programming 07
algorithm with given capacity W=5, Weight and Value are as follows :
1
 (2,12),(1,10),(3,20),(2,15)

Q.7 (a) What is finite automata? How it can be used in string matching? 03
(b) Differentiate BFS and DFS 04
(c) Explain Backtracking Method. What is N-Queens Problem? Give 07
solution of 4-Queens Problem using Backtracking Method.

Q.8 (a) Explain Minimax principal. 03

(b) Define P, NP, NP-complete, NP-Hard problems. 04
(c) Explain rabin-karp string matching algorithm. 07

*************