GUJARAT TECHNOLOGICAL UNIVERSITY

Bachelor of Engineering
Subject Code: 3150703
ANALYSIS AND DESIGN OF ALGORITHMS
Semester V
Type of course: NA

Prerequisite: Programming (C or C++), Data and file structure

Rationale: Obtaining efficient algorithms is very important in modern computer engineering as the world
wants applications to be time and space and energy efficient. This course enables to understand and
analyze efficient algorithms for various applications.

Teaching and Examination Scheme:

Teaching Scheme Credits Examination Marks Total
L T P C Theory Marks Practical Marks Marks
ESE(E) PA ESE (V) PA(I)
4 0 2 5 70 30 30 20 150

Content:

Sr Course content Total Hrs %Wei

No ghtage
1 Basics of Algorithms and Mathematics: 02 2
What is an algorithm?, Mathematics for Algorithmic Sets, Functions and
Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.
2 Analysis of Algorithm: 08 20
The efficient algorithm, Average, Best and worst case analysis, Amortized
analysis , Asymptotic Notations, Analyzing control statement, Loop
invariant and the correctness of the algorithm, Sorting Algorithms and
analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort,
Sorting in linear time : Bucket sort, Radix sort and Counting sort
3 Divide and Conquer Algorithm: 06 15
Introduction, Recurrence and different methods to solve recurrence,
Multiplying large Integers Problem, Problem Solving using divide and
conquer algorithm - Binary Search, Max-Min problem, Sorting (Merge
Sort, Quick Sort), Matrix Multiplication, Exponential.
4 Dynamic Programming: 05 15
Introduction, The Principle of Optimality, Problem Solving using
Dynamic Programming – Calculating the Binomial Coefficient, Making
Change Problem, Assembly Line-Scheduling, Knapsack problem, All
Points Shortest path, Matrix chain multiplication, Longest Common
Subsequence.
5 Greedy Algorithm 05 15
General Characteristics of greedy algorithms, Problem solving using
Greedy Algorithm
- Activity selection problem, Elements of Greedy Strategy, Minimum
Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest
paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.
6 Exploring Graphs: 04 10

Page 1 of 3
w.e.f. AY 2018-19
 GUJARAT TECHNOLOGICAL UNIVERSITY
Bachelor of Engineering
Subject Code: 3150703
An introduction using graphs and games, Undirected Graph, Directed
Graph, Traversing Graphs, Depth First Search, Breath First Search,
Topological sort, Connected components,
7 Backtracking and Branch and Bound: 03 6
Introduction, The Eight queens problem , Knapsack problem, Travelling
Salesman problem, Minimax principle
8 String Matching: 03 6
Introduction, The naive string matching algorithm, The Rabin-Karp
algorithm, String Matching with finite automata, The Knuth-Morris-Pratt
algorithm.
9 Introduction to NP-Completeness: 05 11
The class P and NP, Polynomial reduction, NP- Completeness Problem,
NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem,
Approximation algorithms, Randomized algorithms, Class of
problems beyond NP – P SPACE

Suggested Specification table with Marks (Theory):70

Distribution of Theory Marks

R Level U Level A Level N Level E Level C Level

10 30 10 10 5 5

Legends: R: Remembrance; U: Understanding; A: Application, N: Analyze and E: Evaluate C:

Create and above Levels (Revised Bloom’s Taxonomy)

Note: This specification table shall be treated as a general guideline for students and teachers. The actual
distribution of marks in the question paper may vary slightly from above table.

Reference Books:

1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

and Clifford Stein, PHI.
2. Fundamentals of Algorithms – E. Horowitz et al.
3. Fundamental of Algorithms by Gills Brassard, Paul Bratley, PHI.
4. Introduction to Design and Analysis of Algorithms, Anany Levitin, Pearson.
5. Foundations of Algorithms, Shailesh R Sathe, Penram
6. Design and Analysis of Algorithms, Dave and Dave, Pearson.

Course Outcome:
After learning the course the students should be able to:

1. Analyze the asymptotic performance of algorithms.

2. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
3. Find optimal solution by applying various methods.
4. Apply pattern matching algorithms to find particular pattern.
5. Differentiate polynomial and nonpolynomial problems.
6. Explain the major graph algorithms and their analyses. Employ graphs to model engineering
problems, when appropriate.

Page 2 of 3
w.e.f. AY 2018-19
 GUJARAT TECHNOLOGICAL UNIVERSITY
Bachelor of Engineering
Subject Code: 3150703

List of Experiments:

1. Implementation and Time analysis of sorting algorithms.

Bubble sort, Selection sort, Insertion sort, Merge sort and Quicksort
2. Implementation and Time analysis of linear and binary search algorithm.
3. Implementation of max-heap sort algorithm
4. Implementation and Time analysis of factorial program using iterative and recursive method
5. Implementation of a knapsack problem using dynamic programming.
6. Implementation of chain matrix multiplication using dynamic programming.
7. Implementation of making a change problem using dynamic programming
8. Implementation of a knapsack problem using greedy algorithm
9. Implementation of Graph and Searching (DFS and BFS).
10. Implement prim’s algorithm
11. Implement kruskal’s algorithm.
12. Implement LCS problem.

Design based Problems (DP)/Open Ended Problem:

1. From the given string find maximum size possible palindrome sequence
2. Explore the application of Knapsack in human resource selection and courier loading system
using dynamic programming and greedy algorithm
3. BRTS route design, considering traffic, traffic on road, and benefits

ACTIVE LEARNING ASSIGNMENTS: Preparation of power-point slides, which include videos,

animations, pictures, graphics for better understanding theory and practical work – The faculty will
allocate chapters/ parts of chapters to groups of students so that the entire syllabus to be covered. The
power-point slides should be put up on the web-site of the College/ Institute, along with the names of the
students of the group, the name of the faculty, Department and College on the first slide. The best three
works should submit to GTU.

Page 3 of 3
w.e.f. AY 2018-19
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 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.

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 – 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 – 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

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

2
http://www.gujaratstudy.com
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2019
Subject Code: 2150703 Date: 06/06/2019
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.
MARKS
Q.1 (a) What is an algorithm? How it differ from flowchart? 03
(b) Give difference of dynamic programming and divide-and- 04
conquer method.
(c) Explain Asymptotic notation. Arrange the growth rate of 2n, n2, 07
1, log n, n logn, 3n and n in increasing order of growth.
Q.2 (a) Differentiate greedy and dynamic programming. 03
(b) Find out the Ө-notation for the function: f(n)=27n2+16n. 04
(c) What is recurrence? Explain recursion-tree method with suitable 07
example.
OR
(c) Write the Master theorem. Solve following recurrence using it. 07
(i) T(n)=9T(n/3) + n (ii) T(n)=3T(n/4) + nlgn
Q.3 (a) Use Iteration method to solve recurrence T(n) = T(n-1) + 1 , here 03
T(1)= Ө(1).
(b) Explain general characteristics of greedy algorithms. 04
(c) Using dynamic programming find out the optimal sequence for 07
the matrix chain multiplication of A4x10, B10x3, C3x12, D12x20 and
E20x7 matrices.
OR
Q.3 (a) Write the best and worst running time of Insertion sort 03
algorithm. Why it differ?
(b) What are the steps for dynamic programming? Explain principal 04
of optimality.
(c) Determine LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0} 07
Q.4 (a) What is string-matching problem? Define valid shift and invalid 03
shift.
(b) Define P, NP, NP-complete and NP-hard problems. 04
(c) Explain 0/1 knapsack using suitable example. 07
OR
Q.4 (a) Write pseudo-code for Naïve-String-Matching algorithm. 03
(b) Define spanning tree and MST. How Krushkal’s algorithm is 04
different from Prim’s algorithm.
(c) Explain fractional knapsack problem with example. 07
Q.5 (a) Define graph, complete graph and connected graph. 03
(b) Differentiate BFS and DFS. 04
(c) Write and explain Dijkastra algorithm with example. 07
OR
Q.5 (a) Explain “P = NP ?” problem. 03
(b) Write just steps for Backtracking and Branch-and-Bound 04
algorithms.
(c) Explain travelling salesman problem. Prove that it is NP 07
complete problem.
*******
1
http://www.gujaratstudy.com