Seat No.: ________ Enrolment No.

___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:3150713 Date:07/09/2021
Subject Name:Python for Data Science
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) Differentiate the list and dictionary data types of python by their 03
characteristics along with example in brief.
(b) What do you mean by slicing operation in string of python? Write an 04
example of slicing to fetch first name and last name from full name
of person and display it.
(c) Which are the basic activities we performed as a part of data science 07
pipeline? Summarize and explain in brief.

Q.2 (a) What is the core competencies needed to become a data scientist? 03
Explain in brief.
(b) Compare and summarize four different coding styles supported by 04
Python language.
(c) Summarize the characteristics of NumPy, Pandas, Scikit-Learn and 07
matplotlib libraries along with their usage in brief.
OR
(c) What do you mean by prototyping? List the phases of prototyping 07
and experimentation process and explain in brief.
Q.3 (a) Compare the numpy and pandas on the basis of their characteristics 03
and usage.
(b) For what purpose sampling is used. Demonstrate random sampling 04
with example.
(c) What is the need of streaming the data? Explain data uploading and 07
streaming data with example.
OR
Q.3 (a) How XPath is useful for analysis of html data? Explain in brief. 03
(b) Define term n-gram. Explain the TF-IDF techniques. 04
(c) List the techniques to handle missing data. Explain various 07
techniques with example.

Q.4 (a) List various types of graph/chart available in the pyplot of matplotlib 03
library for data visualization. Explain any two of them in brief.
(b) What kind data is analyzed with Bag of word model? Explain it with 04
example.
(c) What do you mean by time series data? How can we plot it? Explain 07
it with example to plot trend over time

OR

1
Q.4 (a) Compare bar graph, box-plot and histogram with respect to their 03
applicability in data visualization.
(b) Define stemming. Explain the concept of stemming with example. 04
(c) What is the use of scatter-plot in data visualization? Can we draw 07
trendline in scatter-plot? Explain it with example.

Q.5 (a) Define the term Data wrangling. Explain the steps needed to perform 03
data wrangling.
(b) Why we need to perform Z-score standardization in EDA? Justify it 04
with example.
(c) What is the use of hash function in EDA? Express various hashing 07
trick along with example.
OR
Q.5 (a) What do you mean by Exploratory Data Analysis (EDA)? How t-test 03
is useful for EDA?
(b) What do you mean by covariance? What is the importance of 04
covariance in data analysis? Explain it with example.
(c) List different way for defining descriptive statistics for 07
Numeric Data. Explain them in brief.

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:3150713 Date:15/12/2021
Subject Name:Python for Data Science
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) What is the role of Python in Data science? 03
(b) Differentiate List and Tuple in Python 04
(c) Explain data science pipeline in details. 07

Q.2 (a) What is HTML parsing? 03

(b) Write a python code to find factorial of number using function. 04
(c) Explain Dictionary in Python with example 07
OR
(c) Is String a mutable data type? Also explain the string operations 07
length, indexing and slicing in detail with an appropriate
example

Q.3 (a) List and explain any three Magic function. 03

(b) Explain Slicing rows and columns with example. 04
(c) What do you mean by missing values? Explain the different ways 07
to handle the missing value with example.
OR
Q.3 (a) What is Categorical Variables? Explain it with example. 03
(b) How to read data from relational database? Briefly explain it. 04
(c) What is the use of following operations on Panda’s Data Frames? 07
Explain with a small example of each.
1. shape 2. tail() 3. describe()

Q.4 (a) Explain hist() function with code. 03

(b) Write a program using Numpy to count number of “C” element 04
wise in a given array.
(c) What do you understand by Data visualization? Discuss some 07
Python’s data visualization techniques.
OR
Q.4 (a) Explain bar() function with code. 03
(b) What are the different ways to remove duplicate values from 04
dataset?
(c) Write a simple python program that draws a line graph where x 07
= [1,2,3,4] and y = [1,4,9,16] and gives both axis label as “X-
axis”and “Y-axis”.

Q.5 (a) What is Scikit-learn? 03

(b) Explain Box plot with example. 04
Page 1 of 2
 (c) Write a Python programming to create a pie chart with a title of 07
the popularity of programming Languages.
Sample data:
Programming languages: Java, Python, PHP, JavaScript, C#,
C++
Popularity: 22.2, 17.6, 8.8, 8, 7.7, 6.7
OR
Q.5 (a) Define covariance and correlation 03
(b) Explain scatterplots with example. 04
(c) What is Data Wrangling process? Define data exploratory data 07
analysis? Why EDA is required in data analysis?

******All THE BEST*******

Page 2 of 2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:3150713 Date:02/06/2022
Subject Name:Python for Data Science
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) List Advantages of Python. 03
(b) Differentiate Numpy and Pandas. 04
(c) Explain Exploratory Data Analysis (EDA). 07

Q.2 (a) Explain String Slicing in python with Example. 03

(b) List and Explain different programming styles in python. 04
(c) Write a program to check whether the given number is prime or not. 07
OR
(c) Write a program to print Fibonacci series up to number given by user. 07

Q.3 (a) Differentiate rand and randn function in Numpy. 03

(b) Explain DataFrame in Pandas with example. 04
(c) Write a program to print following patterns. 07
1)
*
**
***
****
2)
$$$$
$$$
$$
$
3)
#####
###
#
###
#####
OR
Q.3 (a) Explain Groupby function in pandas with example. 03
(b) Explain how to deal with missing data in Pandas. 04
(c) Explain Web Scrapping with Example using Beautiful Soup library. 07

Q.4 (a) Explain Bag of Word model. 03

(b) Differentiate join and merge functions in pandas. 04
(c) Write a program which takes 2 digits, X,Y as input and generates a 2- 07
dimensional array of size X * Y. The element value in the i-th row
and j-th column of the array should be i*j.
1
 OR
Q.4 (a) Explain Hashing Trick in python with example. 03
(b) Write a brief note on NetworkX library. 04
(c) List and Explain different graphs in MatPlotLib. 07

Q.5 (a) Explain Labels, Annotation and Legends in MatPlotLib. 03

(b) Differentiate Supervised and Unsupervised learning. 04
(c) Explain Regression with example. 07
OR
Q.5 (a) Write a program to print Current date and time. 03
(b) Write a program to interchange the List elements on two positions 04
entered by a user
(c) Explain Classification with example. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:3150713 Date:04-01-2023
Subject Name:Python for Data Science
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.

Q.1 (a) What is the role of python in data science? 03

(b) Explain the input function of python that demonstrates type casting. 04
(c) Explain following data structures of python with suitable example. 07
1. String
2. List
3. Tuple
4. Dictionary
Q.2 (a) Differentiate: C and Python. 03
(b) How to format Date and Time in python. Explain it with example. 04
(c) Give comparison between Numpy and Pandas. 07
OR
(c) Write a python code to read data from text file. 07
Q.3 (a) Explain %matplotlib magic function. 03
(b) Explain stemming and stop words removal operation in python. 04
(c) Write a python program to implement Fibonacci sequence for given input. 07
OR
Q.3 (a) What are the magic functions in Jupyter? Explain with example. 03
(b) With example explain the concept of bags of words model. 04
(c) Write a python program that finds the factorial of a natural number n. 07
Q.4 (a) Explain labels, annotations and legends. 03
(b) Explain with example how to parse XML and HTML. 04
(c) Write a python code that demonstrate hashing trick. 07
OR
Q.4 (a) Explain any three functions from Scikit learn. 03
(b) Explain how to create data science pipeline. 04
(c) Write a python program to demonstrate the concept of skewness and kurtosis. 07
Q.5 (a) Explain EDA in detail. 03
(b) Write a python code to access data from web. 04
(c) Write a small code to perform following operations on data: Slicing, Dicing, 07
Concatenation, Transformation.
OR
Q.5 (a) Explain Z-score standardization. 03
(b) How to Obtain online graphics and multimedia. Explain with example. 04
(c) Write a code to draw pie chart using python’s library. 07

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:3150713 Date:22/01/2021
Subject Name:Python for Data Science
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) Discuss the role of indentation in python. 03

(b) Explain range() function with suitable examples. 04
(c) Write a python program to find the factorial of a given number using 07
recursion.

Q.2 (a) Explain sampling in terms of data science? 03

(b) List and explain different coding styles supported by python. 04
(c) Discuss why python is a first choice for data scientists? 07

Q.3 (a) Explain TF-IDF transformations. 03

(b) Explain categorical variables in detail. 04
(c) Write a python program to read the data from XML file using pandas 07
library.

Q.4 (a) Describe date time transformation using datetime module. 03

(b) Explain a bag of words model in detail. 04
(c) Explain imputation in detail with example. 07

Q.5 (a) List the features of matplotlib. 03

(b) Write a python program to read data from a text file using pandas 04
library.
(c) Explain time series plot with appropriate examples. 07

Q.6 (a) List the type of plots that can be drawn using matplotlib. 03
(b) Write a python program to read data from CSV files using pandas. 04
(c) Explain pie chart plot with appropriate examples. 07

Q.7 (a) List and explain interfaces of SciKit-learn. 03

(b) List the multiprocessing tasksthat can be done using SciKit-learn? 04
(c) Define the classification problem. How can it be solved using 07
1
 SciKit-learn?

Q.8 (a) Define EDA. List the tasks need to be carried out in EDA? 03
(b) How hash functions can be useful to solve data science problems? 04
(c) Define the regression problem. How can it be solved using SciKit- 07
learn?

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:3150711 Date:09/09/2021
Subject Name:Software Engineering
Time:10:30 AM TO 01:00 PM Total Marks:
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.

Q.1 (a) Explain software engineering as a layered technology. 03

(b) What is process model? Compare incremental process model with prototyping 04
process model.
(c) What is SRS? What are the key elements of it? What are the qualities of a 07
good SRS?

Q.2 (a) What is Extreme Programming (XP)? What are the advantages of it? 03
(b) What is black box testing? What are the different black box testing techniques? 04
(c) What is DevOps? How it works? What are the DevOps principles & best 07
practices?
OR
(c) Discuss SCRUM as agile software development process model. 07
Q.3 (a) Discuss some of the problems that occur when requirements must be elicited 03
from three or four different customers.
(b) You have been appointed a project manager for a major software products 04
company.
Your job is to manage the development of the next-generation version of its
widely used word processing software. Because competition is intense, tight
deadlines have been established and announced. What team structure would
you choose and why? What software process model(s) would you choose and
why?
(c) What is the importance of user interface? Discuss user interface design rules. 07
OR
Q.3 (a) How do we assess the quality of a software design? 03
(b) You have been appointed a software project manager for a company that 04
services the genetic engineering world. Your job is to manage the development
of a new software product that will accelerate the pace of gene typing. The
work is R&D oriented, but the goal is to produce a product within the next
year. What team structure would you choose and why? What software process
model(s) would you choose and why?
(c) What is architectural design? Discuss different style and patterns of 07
architecture.
Q.4 (a) Considering the aspects of the cost of software quality, which do you think is 03
the most expensive and why?
(b) What is FTR? Enlist FTR guidelines. 04
(c) Explain the design concepts Modularity and Functional Independence in detail. 07
OR
Q.4 (a) What elements of the WebApp can be “unit tested”? What types of tests must 03
be conducted only after the WebApp elements are integrated?
(b) Quality and reliability are related concepts but are fundamentally different in a 04
1
 number of ways. Discuss the differences.
(c) What is the importance of SQA? Discuss SQA activities. 07

Q.5 (a) Using your own words, describe the difference between verification and 03
validation.
Do both make use of test-case design methods and testing strategies?
(b) What are the four elements that exist when an effective SCM system is 04
implemented? Discuss each briefly.
(c) What is the importance of class model? Prepare the class model for a web- 07
based order-processing system for a computer store.
OR
Q.5 (a) What is white box testing? What are the different coverage based testing 03
strategies.
(b) Briefly discuss the process of reverse software engineering. 04
(c) What are the elements of a behavioral model? Prepare use case diagram and 07
sequence diagrams for ATM system of a bank.

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:3150711 Date:04/06/2022
Subject Name:Software Engineering
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) What is Software Engineering? List down different myths for it. 03
(b) What are different layers of Software Engineering? Draw and 04
explain it in short.
(c) Draw and explain the different phases of Waterfall Model. 07

Q.2 (a) What is Agility? List down 12 principals of Agile Manifesto. 03

(b) Draw and explain different phases of Agile Process Model. 04
(c) Draw and explain Spiral Model with its advantages. 07
OR
(c) What is Coupling? What is Cohesion? Explain different types of 07
Cohesion and Coupling with proper example.

Q.3 (a) What is Requirement Engineering? How it is carried out in a 03

Software Organizations?
(b) Create a SRS document for College Management System. 04
(c) What is Software Testing? Explain Black-box and White-Box 07
Testing in details along with examples.
OR
Q.3 (a) What is Software Quality? List down different Software Quality 03
Metrics?
(b) List down various Software Design Principles applicable to College 04
Management System.
(c) Write a short note on: (1) Function-Oriented Design (2) User 07
Interface Design

Q.4 (a) What is Software Maintenance? Explain different types of it in short. 03

(b) Create a list of Software Reverse Engineering phases for College 04
Management System and explain in short.
(c) How version and change are controlled within and across 07
organizations? Explain it.
OR
Q.4 (a) Define: Risk Identification, Risk Refinement, and Risk Mitigation. 03
(b) How software organization go from different maturity level of SEI 04
CMM? Explain it.
(c) How organization can get ISO 9000 certification? Explain the 07
process.

Q.5 (a) What is DevOps? List down its toolchain for development process. 03
(b) How DevOps practice be adopted for software development process. 04
(c) Explain 7Cs of DevOps lifecycle. 07
1
 OR
Q.5 (a) What is Component Based Software Engineering? What are its 03
advantages?
(b) How a typical software is being Reengineered? Explain why is 04
required?
(c) Explain Computer-Aided Software Engineering in detail. 07

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:3150711 Date:01/01/2022
Subject Name:Software Engineering
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) Write a short note on Software Configuration Management. 03

(b) Compare Spiral Model with Prototype model. 04
(c) What is Software Testing? What is the role of a Software Tester? Compare 07
Black Box and White Box Testing.

Q.2 (a) Compare Waterfall model with RAD model. 03

(b) Explain merits and demerits of Scrum. 04
(c) Explain Agile Development in detail. 07
OR
(c) Explain DevOps life Cycle. 07

Q.3 (a) Explain Formal Technical Review. 03

(b) Define Coupling and Cohesion. What is the difference between cohesion and 04
coupling?
(c) What is Requirement Engineering? List the Functional and Non-Functional 07
requirements for Blood bank Management system.
OR
Q.3 (a) State the difference between procedural Design and Object Oriented Design. 03
(b) Explain Software metrics used for software cost estimation. 04
(c) Write SRS For Students Result Management System. 07

Q.4 (a) Write short note on Version Control. 03

(b) What are the fundamental differences between DevOps & Agile Development? 04
(c) Explain project scheduling process and Gantt Chart in detail. 07
OR
Q.4 (a) Write short note on Six Sigma standard. 03
(b) Explain RMMM plan. 04
(c) What is the importance of Software Quality Assurance? Explain different CMM 07
levels.

Q.5 (a) Write short note on Reverse-engineering. 03

(b) Which are the Software quality standards? Explain any one. 04
(c) What is an architectural design? Enlist different style and patterns of architecture. 07
OR
Q.5 (a) Write short note on Re-engineering. 03
(b) Explain the SQA activities. 04
(c) What is BVA? Explain merits and demerits of BVA. 07
*************

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:3150711 Date:06-01-2023
Subject Name:Software Engineering
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) List the goals of software engineering? 03
(b) Distinguish between process and methods. 04
(c) Explain the Evolutionary and Incremental Model. What are the Advantages 07
and Disadvantages?
Q.2 (a) Define the followings: 03
1) Agile methods 2) Agile process
(b) What is Extreme Programming? 04
(c) Explain how breakdown structure is used in software engineering. Discuss 07
how software project scheduling helps in timely release of a product.
OR
(c) Discuss the concept of risk assessment and risk control. 07

Q.3 (a) What are functional requirements? 03

(b) What are the elements of Analysis model? 04
(c) State and explain the requirements engineering tasks in detail. 07
OR
Q.3 (a) What are non-functional requirements? 03
(b) Define design process. List the principles of a software design. 04
(c) Explain the feasibility studies. What are the outcomes? Does it have either 07
implicit or explicit effects on software requirement collection?

Q.4 (a) How to measure quality and defect removal efficiency. 03

(b) Explain reverse engineering. 04
(c) What is coupling? Explain the various types of coupling? 07
OR
Q.4 (a) What is the importance of SQA? 03
(b) Explain the version control and change control. 04
(c) What is cohesion? Explain the various types of cohesion? 07

Q.5 (a) What are the levels at which testing done? 03

(b) Describe the different challenges with DevOps implementation. 04
(c) What do you mean by integration testing? Explain their outcomes. 07
OR
Q.5 (a) Define basic path testing. 03
(b) What is DevOps? Explain the importance and benefits of the DevOps. 04

1
(c) What is white box testing? Why it is required? Discuss different techniques 07
of it?
*************

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:3150711 Date:27/01/2021
Subject Name:Software Engineering
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.

Q.1 (a) Distinguish between a program and a software product. 03

(b) Which are the major phases in the waterfall model of software 04
development? Which phase consumes the maximum effort for developing
a typical software product?
(c) With suitable illustration explain SPIRAL model evolutionary software 07
development.

Q.2 (a) What is Agile Manifesto? 03

(b) Define the terms: 04
1) Agility 2) Agile team
(c) What are the different activities in project planning? What is error 07
tracking?
Q.3 (a) What are the relative advantages of using either the LOC or the function 03
point metric to measure the size of a software product?
(b) What are the types of metrics? 04
(c) What is requirement engineering? State its process and explain 07
requirements elicitation problem.

Q.4 (a) What is the purpose of timeline chart? 03

(b) Distinguish between verification & validation. 04
(c) Explain with example diagram the functional and behavioral modeling. 07
How do we model the software’s reaction to some external event?

Q.5 (a) What are the different levels of abstraction? 03

(b) What are the common activities in design process? 04
(c) Discuss the differences between black box and white box testing. 07

1
Q.6 (a) What are the different types of Cohesion? 03
(b) What are the various elements of data design? 04
(c) What do you mean by system testing? Explain in detail. 07

Q.7 (a) What is the Objective of Formal Technical Reviews? 03

(b) What is DevOps? 04
(c) Explain Component Based software engineering in detail. 07

Q.8 (a) State the need for software configuration review. 03

(b) What are the challenges with DevOps implementation? 04
(c) What is the use of CMM? Discuss different levels of SEI-CMM. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:3150710 Date:15/09/2021
Subject Name:Computer Networks
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) Discuss throughput in the network. 03
(b) Differentiate TCP/IP protocol stack and OSI Reference model of the 04
computer network.
(c) How does the reservation protocol work to control access of the 07
medium? Discuss the disadvantages of it.

Q.2 (a) Define Unicasting, Multicasting and Broadcasting. 03

(b) Discriminate fully qualified domain name from partially qualified 04
domain name.
(c) How the p-persistent is different from 1-persisent in CSMA/CD? 07
Explain how the Backoff time is set in the case of collision.
OR
(c) Explain the working mechanism of the binary countdown protocol. 07
Which limitation of bitmap protocol is overcome by it?
Q.3 (a) Bit steam 10011101 is to be transmitted using the standard CRC 03
method with divisor value x3+1. Generate the CRC code word.
(b) Why the virtual circuit is to be set up for transmission of message in 04
TCP protocol?
(c) Explain Distance Vector routing protocol. 07
OR
Q.3 (a) How the encapsulation is done in the transport layer? 03
(b) What is subnetting? Why is it required? 04
(c) Explain Link State routing protocol. 07
Q.4 (a) How does store-n-forward technique work at network layer? 03
(b) Discuss the various measures which are used to compute the cost 04
between two routers of the network.
(c) Explain TCP Congestion control in detail. 07
OR
Q.4 (a) How many subnets can be created for the subnet mask 03
255.255.255.224? Which IP address class these subnet does belong to?
(b) What is process-to-process delivery in transport layer? Why do we 04
require it though host-to-host delivery is provided by the network
layer?
(c) Explain User Datagram Protocol. 07

Q.5 (a) Why the data encryption is necessary at the presentation layer of OSI 03
reference model?
(b) How does chock packet technique work for congestion control? 04
(c) What is POP3 protocol? How the limitations of POP3 protocols are 07
overcome by IMAP?
1
 OR
Q.5 (a) Why data compression is necessary at the presentation layer of OSI 03
reference model?
(b) Differentiate Congestion control and flow control. 04
(c) Explain MIME structure for electronic mail. 07

***********

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:3150710 Date:09/06/2022
Subject Name:Computer Networks
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) What is the difference between a host and an end system? 03
List several different types of end systems.
(b) Explain IP Address, Physical Address and Port Number in 04
Brief.
(c) Draw the layered architecture of OSI reference model and 07
write at least two services provided by each layer of the
model.

Q.2 (a) Explain the role of Domain Name Server (DNS) in 03

Internet?
(b) Explain functionality of Repeater, HUB, Bridge, Switch, 04
Router and Gateway.
(c) How end-to-end congestion control is provided by TCP. 07
OR
(c) Consider the 7-bit generator, G=10011, and suppose that D 07
has the value1010101010. What is the value of R?

Q.3 (a) Discuss parity check for error detection in data transfer. 03
(b) List and briefly describe three types of switching fabrics 04
used in Routers. Which, if any, can send multiple packets
across the fabric in parallel?
(c) Describe Go Back N and Selective Repeat protocol. 07
OR
Q.3 (a) Give difference between connection oriented and 03
connection less services.
(b) Why do HTTP, FTP, SMTP, and POP3 run on top of TCP 04
rather than on UDP? Name one application that uses UDP
and why?
(c) Explain RDT 2.0. 07

Q.4 (a) Give difference between flow control verses Congestion 03

Control.
(b) What is HTTP? Differentiate its persistent and non- 04
persistent types with request-response behavior of HTTP.
(c) Explain distance vector routing algorithm. 07
OR
Q.4 (a) Explain CSMA/CD Protocol. 03
(b) Why are different inter-AS and intra-AS protocols used in 04
the Internet?
(c) Explain Link-State routing algorithm. 07

1
Q.5 (a) Explain in brief socket, multiplexing and demultiplexing. 03
(b) How DHCP protocol works? 04
(c) Explain TCP segment structure and justify the importance 07
of its field values.
OR
Q.5 (a) Describe how a botnet can be created, and how it can be 03
used for a DDoS attack.
(b) What do you mean by random access protocols? Explain 04
slotted ALOHA in brief.
(c) Explain IPv4 datagram format and importance of each 07
field

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:3150710 Date:27/12/2021
Subject Name:Computer Networks
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.

Q.1 (a) What is topology? Explain star topology in brief. 03

(b) Explain various delay which are occur in data packet transmission. 04
(c ) Explain functionality of Repeater, Hub, Bridge, Switch, Router and Gateway. 07
Q.2 (a) Write short note on Domain Name System (DNS). 03
(b) What is HTTP? Differentiate its persistent and non-persistent types with 04
request-response behavior of HTTP.
(c ) Draw the layered architecture of OSI reference model and write at least two 07
services provided by each layer of the model.
OR
(c ) Explain DHCP and Email in detail. 07
Q.3 (a) Explain Physical Address, IP address, Port Address in brief. 03
(b) Compare IPv4 and IPv6. 04
(c ) Explain Distance Vector Routing Algorithm. 07
OR
Q.3 (a) Discuss the principles of Reliable Data Transfer. 03
(b) Give difference between connection oriented and connectionless services. 04
(c ) What do you mean by congestion and overflow? Explain the slow-start 07
component of the TCP congestion-control algorithm.
Q.4 (a) Explain packet fragmentation with example. 03
(b) Write a short note on broadcast and multicast routing. 04
(c ) What is IP address? Explain sub netting with example. 07
OR
Q.4 (a) Give differences between TCP and UDP. 03
(b) What is socket? Explain its importance at transport layer protocols. 04
(c ) Discuss transport layer multiplexing and demultiplexing concepts. 07
Q.5 (a) Discuss CSMA/CD Protocol. 03
(b) Explain CRC code generation with example. 04
(c ) Describe Go Back N and Selective Repeat protocol. 07
OR
Q.5 (a) Discuss parity check for error detection in data transfer. 03
(b) What do you mean by random access protocols? Explain slotted ALOHA in 04
brief.
(c ) Draw and explain Ethernet Frame Structure. 07

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:3150710 Date:11-01-2023
Subject Name:Computer Networks
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) Which of the OSI layers handles each of the following: 03
i) Dividing the message into segments.
ii) Determining which route through the subnet to use.
iii) Dividing the transmitted bit stream into frames.
(b) Besides bandwidth and latency, what other parameter(s) is/are needed to 04
give a good characterization of the quality of service offered by network
used for
(i) Online financial transaction traffic?
(ii) Video streaming traffic?

(c) Discuss the circuit switching versus packet switching approaches for 07
moving data through a network of links and switches.

Q.2 (a) Justify the statement, “HTTP server is stateless”. 03

(b) State the port number for the following application layer protocols. 04
i) FTP ii) HTTP iii) SMTP iv) POP3
(c) Discuss the five layer internet protocol stack along with the functionalities 07
of each layer in detail.
OR
(c) Explain User Datagram Protocol (UDP) in detail and discuss how it differs 07
from Transmission Control Protocol (TCP).

Q.3 (a) For the below mentioned internet applications protocol, mention the 03
underlying transport protocol (TCP or UDP).
i) Telnet ii) FTP iii) HTTP
(b) Discuss the count-to-infinity problem in distance vector routing algorithm 04
with example.
(c) Explain the class-full sub-netting with example. 07
OR
Q.3 (a) Define the term unicasting, multicasting, and broadcasting. 03
(b) What is the significance of the following flags in TCP segment? 04
i) URG ii) SYN iii) FIN iv) PSH
(c) Explain TCP Congestion mechanism in detail. 07

Q.4 (a) Explain the UDP checksum mechanism for error detection with example. 03
(b) What is the relevance of Type of Service (ToS) and Time to Live (TTL) 04
field in IPV4 packet?
(c) Explain Link State Routing algorithm in detail. 07
OR
Q.4 (a) What are the three most important network-layer functions in a virtual- 03
circuit network?
(b) Explain Route Summarization or Route Aggregation in network layer. 04
1
 (c) Demonstrate the various error detection techniques at data link layer with 07
example.

Q.5 (a) What is the purpose of Address Resolution Protocol (ARP) and Network 03
Address Translation (NAT)?
(b) Explain the following static channel allocations mechanisms: 04
i) TDMA ii) FDMA
(c) Explain p-persistent CSMA protocol in detail. 07
OR
Q.5 (a) Data link protocols almost always put CRC in a trailer rather than in a 03
header. Why?
(b) State the difference between bit rate and baud rate. 04
(c) Discuss the working of slotted aloha along with its efficiency in terms of 07
channel utilization.

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

2
 Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:3150710 Date:01/02/2021
Subject Name:Computer Networks
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) Explain how bit rate and baud rate are related with respect to Ethernet. 03
(b) Differentiate between connection oriented versus connection less services in 04
networks.
(c) Explain the working of binary count down MAC layer protocol in detail. 07

Q.2 (a) Explain how multicasting differs from multiple unicasting in networks. 03
(b) Discriminate fully qualified domain name from partially qualified domain 04
name.
(c) Explain the working of CSMA/CD protocol in detail. 07
Q.3 (a) A Bit steam 100100 is to be transmitted using standard CRC method with 03
divisor value x3+x2+1. Generate the CRC code word.
(b) How switch device is different from the router? 04
(c) Explain the problem of Count-to-infinity with example in distance vector 07
routing algorithm.

Q.4 (a) What is meant by encapsulation at transport layer? 03

(b) Explain flow and error control in TCP. 04
(c) What do you mean by sub-netting and super-netting? Explain it with example 07
Q.5 (a) Explain NAT (Network Address Translation) as a solution to IP address 03
depletion problem.
(b) What is the minimum and maximum size of the TCP and UDP segment? 04
(c) Explain leaky bucket algorithm for the network traffic shaping. 07

Q.6 (a) Is deadlock possible in TCP? If yes, when? 03

(b) What is route aggregation? How it can be useful in Internet? 04
(c) Explain the significance of the following flags present in TCP segment header: 07
1) URG 2) ACK 3) PSH 4) RST 5) SYN 6) FIN
Q.7 (a) How the Jitter is different from the delay in streaming applications? 03
(b) Explain the following TCP socket system calls: 04
1) socket() 2) bind()
3) listen() 4) accept()
(c) Give the well defined port number for the following protocols: 07
1) SMTP 2) DNS 3) HTTP 4) POP3
5) TELNET 6) HTTPS 7) SSH

Q.8 (a) Is data compression is necessary at the presentation layer of OSI reference 03
model? Explain it with proper reason.
(b) What do you mean by stream and datagram sockets? 04
(c) Explain the hierarchical DNS system 07

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:3150709 Date:13/06/2022
Subject Name:Professional ethics
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. 03

1. Ethics.2. Personal Ethics.3. Business Ethics.
(b) Compare Morality and Law. 04
(c) What are the sources of ethical problems in business? How can these 07
be solved?
Q.2 (a) Elaborate ethics of Gandhiji. 03
(b) Explain
how canwhite-collar crime withbeansolved?
these be solved?these example. 04
(c) Explain Kohlberg’s model of cognitive moral development in your 07
own words with suitable examples.
OR
(c) How Human values are important for a manager? Explain in detail. 07
Q.3 (a) Explain Indian Ethical Traditions? 03
(b) How the law of Karma affects a human life? 04
(c) What are business ethics? Describe its nature. Is business ethics a 07
necessity?
OR
Q.3 (a) Explain Roots of unethical Behavior. 03
(b) What is the difference between honesty and integrity? 04
(c) Explain the principles of Personal ethics and Professional ethics? 07
Q.4 (a) Define professional ethics. 03
(b) What are professional etiquettes? 04
(c) Explain personal values and ethical decision making. 07
OR
Q.4 (a) Define deontology. 03
(b) Explain cross -holder conflict and competition. How one can make 04
ethical decision with it.
(c) Explain the model for ethical decision-making. 07
Q.5 (a) Explain the impact of personal values on Ethical decision making. 03
(b) How is ancient education different from modern education in India? 04
(c) What is an Ethical Dilemma? How to Resolve Ethical Dilemmas. 07
OR
Q.5 (a) What are the qualities of working life? 03
(b) Compare morality and religion. 04
(c) How to apply moral philosophy in Ethical Decision making? 07
************

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:3150709 Date:13-01-2023
Subject Name:Professional ethics
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 Ethics in short 03

(b) Differentiate between Personal ethics and Business Ethics. 04
(c) Explain five qualities of successful professional. 07

Q.2 (a) Explain Morality in short. 03

(b) Differentiate between Morality and Law. 04
(c) What is the role of Manager in business? List and explain values of 07
Indian Manager.
OR
(c) Swami Vivekananda’s thoughts on ethics are essentially practical and 07
based on normative ethics. Discuss.

Q.3 (a) Explain Moral Philosophies. 03

(b) What is Ethical Dilemmas? Explain with example. 04
(c) What do you mean by Quality of Working life? List and explain 07
affecting factors of on working life.
OR
Q.3 (a) What is unethical practice in Business? List and explain any 5 of them. 03
(b) Differentiate between Values and Ethics. 04
(c) What is Ethical Decision Making process? List and explain at least 3 07
scenarios when it is required in business.

Q.4 (a) How corporate culture will help to develop Ethical Environment in 03
company.
(b) What do you learn from Ethics of Gandhiji? How would you add that in 04
your life?
(c) Explain Honesty, Integrity and Transparency in Business. 07
OR
Q.4 (a) Define following terms: Utilitarianism, Virtue, Fairness and Justice. 03
(b) What do you learn from Ethics of Aurobindo? How would you add that 04
in your life?
(c) List and Explain sources of Ethical Behavior. 07

Q.5 (a) What do you mean by Karma? Explain Law of Karma. 03

1
 (b) What do you learn from Ethics of Tagore? How would you add that in 04
your life?
(c) Explain Ethical Decision Making. Explain Six-step decision making 07
model.
OR
Q.5 (a) Explain “White Collar Crime” in Business with example. 03
(b) Differentiate between Ethics and Philosophy. 04
(c) Explain Kohlberg’s Model of Cognitive. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:3150709 Date:17/09/2021
Subject Name:Professional ethics
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) Differentiate Personal Ethics vs. Business Ethics. 03

(b) What is an ethical dilemma? Give a suitable example. Suggest a viable 04
approach to resolve the same.
(c) List and explain the roots of unethical behavior. 07

Q.2 (a) A personal moral standard can impact an employee’s decision making. 03
Elaborate.
(b) What kind of conflicts can be created by the confrontation of the 04
individual’s and organization’s moral philosophies in the work place?
How can they be resolved?
(c) Why should businesses act ethically? Discuss one example where 07
acting unethically harmed the business and its stake holders.
OR
(c) What values company expect from their employees? 07
Q.3 (a) What factors influence the employee’s decision making in business? 03
(b) Why do businesses have a negative image? 04
(c) Compare and contrast the Utilitarianism and Deontology ethical 07
theories.
OR
Q.3 (a) Can an effective decision be unethical? Explain. 03
(b) Explain the following terms with respect to business: 04
i) Loyalty ii) Reliability
(c) Discuss Walton’s six models of business conduct. 07
Q.4 (a) ‘Caring is the heart of ethics and ethical decision making.’ Justify with 03
an example.
(b) Compare: Normative ethics and Applied ethics. 04
(c) What are the steps in making a good ethical decision? Explain with an 07
illustration.
OR
Q.4 (a) One of the Shlokas from Rigveda says: 03
“A businessman should benefit from the business like a honey-bee
which suckles honey from the flower without affecting its charm and
beauty”.
What ethical values do you infer from this Shloka?

(b) Give two examples of white collar crimes. 04

(c) Getting the facts right is very important in decision making. Provide 07
guidelines that help in getting reliable facts.
Q.5 (a) Elaborate the theory of rights. 03
1
 (b) Consider an organization where the employees have to maintain 8 04
hours/day. There are no rules regarding timings. Highlight the pros
and cons of such a system.
(c) Write a brief note on the ethics and moral values of Swami 07
Vivekananda.
OR
Q.5 (a) Suggest what companies should do or provide to maintain the quality 03
of life and work of employees.
(b) List the main pillars of Tagore’s concept of education. 04
(c) Explain Kohlberg’s Model of Cognitive Moral Development. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:3150709 Date:20/12/2021
Subject Name:Professional ethics
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) Enlist at least four characteristics of quality of working life. How 03
alternate work schedules helps to improvise and achieve standard
quality of working life?
(b) Define Engineering Ethics. Distinguish between ethics, laws and 04
morals.
(c) Mention the need for businesses to act ethically. 07

Q.2 (a) Justify: “Beauty lies in the eye of the beholder and thus one must 03
accept the way it is” correlates the law of humility of karma.
(b) Generalize your views over incorporation of Bhagwat Gita’s moral 04
values and ethics into one’s work life?
(c) Presume that pawan is a senior officer working for cyber security 07
agency. He comes to know that his junior officer has been a victim
of honey trapping through social media. In all of this, his phone
was hacked and confidential files were leaked. The entire
department has come together and wants pawan to take strict
actions against junior officer for his behavior. That junior officer is
highly skilled and is an asset to organization. He is also close to
pawan as he had mentored him throughout and respects him a lot.
Moreover, any action against him might attract media attention and
bring a bad repute to the entire organization at large.
i. What are the ethical issues involved and options available
to pawan in such a situation?
ii. Suggest a course of action that pawan would take to resolve
it.
OR
(c) Mention the business ethics in Islam keeping into context the 07
indian ethical traditions.
Q.3 (a) Mention principles of professional ethics. 03
(b) Provide some appropriate ways for creating an ethical working 04
environment.
(c) Discuss at least seven notable features of ancient Indian education 07
system.
OR
Q.3 (a) Mention principles of personal ethics. 03
(b) Describe how failure of personal character can be considered as 04
one of the sources of ethical problems stating one real life scenario.
(c) Briefly describe three two laws of karma by providing appropriate 07
examples.
Q.4 (a) Briefly describe the normative theory of business ethics. 03
1
 (b) Briefly elaborate below statements in context to why they cannot 04
be considered business ethics:
i. Ethics is different from religion.
ii. Ethical Standards are different from cultural traits.
(c) Explain Kohlberg’s Model of Cognitive Moral Development in brief. 07
OR
Q.4 (a) Elaborate your views over the Gandhian principles of trusteeship 03
in context to business ethics.
(b) Enlist roots of unethical behavior and the factors that contribute the 04
employees to think in an unethical manner.
(c) Neelam is working as senior HR manager at Zion IT company. 07
Mention the code of personal ethics she needs to possess as an
employee of the organization.
Q.5 (a) Enlist main pillars of character for any ethical decision maker. 03
(b) Distinguish between personal and business ethics by providing 04
appropriate example.
(c) Define white-collar crime (WCC). Enlist few of the most white- 07
collar offenses observed in recent times. Mention the penalties for
WCC’s.
OR
Q.5 (a) In recent times, education system has adopted a concept of 03
tutorship wherein passed out students or seniors tutor their juniors.
Provide your views by correlating it with ancient indian education
system.
(b) Justify: “Integrity and Transparency are the touchstones of 04
Business Ethics”.
(c) Briefly describe the ethical models that guides decision making. 07

**********

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:3150709 Date:03/02/2021
Subject Name:Professional ethics
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) Define Ethics, Personal Ethics and Professional Ethics. 03

(b) Describe Relationship between morality and Laws. 04
(c) Explain Morality, Etiquette and Professional Codes. 07

Q.2 (a) Explain Principles of Personal Ethics. 03

(b) Explain Principles of Professional Ethics. 04
(c) Explain Honesty, Integrity, Transparency are the touchstones of Business Ethics. 07

Q.3 (a) Explain concept of Ethical dilemmas. 03

(b) Explain types of approach to resolve ethical dilemmas? 04
(c) How to resolve ethical Problems? 07

Q.4 (a) Explain codes of personal ethics for Employees. 03

(b) Explain various Ethical models that guide decision making. 04
(c) Explain Kohlberg’s model of cognitive moral development. 07

Q.5 (a) List outs Latest Technologies used for disaster management. 03
(b) How to apply moral philosophy to Ethical decision making? 04
(c) Short note on Ethics of Swami Vivekananda. 07

Q.6 (a) Explain Rules for Ethical decision making for cross over conflicts. 03
(b) Explain influences on Ethical Decision making. 04
(c) Short note on Ethics of Mahatma Gandhi. 07

Q.7 (a) Explain Nature and Scope of Quality of work Life. 03

(b) Describe Lessons from Ancident Indian Education system. 04
(c) Short note on Ethics of Sri Aurobindo Ghose. 07

Q.8 (a) Enlist Advantages of Quality of work Life. 03

(b) How is the Law of Karma useful for the managers/ Professionals? 04
(c) Short note on Ethics of Rabindranath Tagore. 07

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022
Subject Code:2150703 Date:02/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) Give precise definition of Algorithm. Also discuss time and space 03
complexity of a computer algorithm.
(b) Explain the following terms in brief. 04
- directed graph
- minimum spanning tree
(c) Discuss insertion sort with its time complexity. Support your answer 07
with suitable example.

Q.2 (a) Write applications for string matching. 03

(b) Write a brief note on asymptotic notations. 04
(c) Sort the following numbers using heap sort. 07
30, 21, 55, 16, 19, 17, 34
OR
(c) Sort the following numbers using counting sort. 07
1, 3, 2, 4, 1, 2, 4, 3

Q.3 (a) Write general characteristics of greedy algorithms. 03

(b) Solve the following recurrence using master method 04
T(n) = 9T(n/3) + n.
(c) Discuss binary search using divide and conquer strategy. Support 07
your answer with proper example.
OR
Q.3 (a) Check the correctness for the following equality. 03
7n2 + 5n = O(n3)
(b) Discuss making change problem using dynamic programming. 04
(c) Describe Kruskal’s algorithm for finding minimum spanning tree. 07

Q.4 (a) Find out time complexity for the following pseudo code using O- 03
notation.
for(i = 0; i < n; i++)
{
for(j =0 ; j < n ; j++)
{
if( i < j )
c = c + 1;
}
}
(b) Explain Huffman code in brief. 04
(c) Elaborate matrix chain multiplication using dynamic programming 07
with proper illustration.
1
 OR

Q.4 (a) Write differences between greedy strategy and dynamic 03

programming.
(b) Multiply 1234 by 567 by divide and conquer method. 04
(c) Find an optimal solution for the following 0/1 knapsack problem using 07
dynamic programming.
Weight w = (w1,w2,w3) = (2,3,3)
Profit p = (p1,p2,p3) = (1,2,4)
Knapsack capacity m = 6

Q.5 (a) Briefly discuss principle of optimality in dynamic programming. 03

(b) Write a brief note on topological sort. 04
(c) Discuss 8-queens problem using backtracking. 07
OR
Q.5 (a) What is NP-Hard problems? 03
(b) Write a brief note on depth-first-search. 04
(c) Describe naïve string matching algorithm. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2022
Subject Code:2150703 Date:04-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) What is an algorithm? What are the properties of an algorithm? 03

(b) Explain the Big-Oh computation for each of the following control 04
structures.
(a) If-then-else (c) sequencing
(b) for loop (d) recursion
(c) Analyze the Insertion Sort algorithm in best and worst case. 07

Q.2 (a) Explain Asymptotic notations with examples. 03

(b) Solve the recurrence following relation. 04
T(n) = T(n/3) + T(2n/3) + Ө(n)
(c) Sort the list: 415, 213, 700, 515, 712, 615 using merge sort algorithm and 07
also explain the time complexity of merge sort algorithm.
OR
(c) Arrange the following data into ascending order using heap sort. Make 07
necessary assumptions if required. 34, 12, 42, 96, 56, 11, 78

Q.3 (a) Explain the Strassen’s matrix multiplication algorithm. Obtain its time 03
complexity.
(b) Find multiplication (A x B) of A = 2341 and B = 6780 using divide and 04
conquer methodology.
(c) Explain the concept of greedy technique for Prim’s algorithm. Also obtain 07
the Minimum Spanning Tree from the following graph.

OR
Q.3 (a) Arrange following growth rates in increasing order. 03
O(n1/4), O(n1.5), O(n3 log n), O(n1.02), Ω(n6 ), Ω(n!), O(√n), O(n6/2), Ω(2n )

1
 (b) Demonstrate Binary Search method to search Key = 14, form the array A= 04
{1,3,5,7,8,14,15,20}
(c) What are the Huffman trees? Construct the Huffman code for the 07
following data:
Character A B C D E F
Frequency 0.5 0.35 0.2 0.1 0.4 0.6

Q.4 (a) Write an algorithm for Naïve-String-Matching algorithm. 03

(b) Using the Dijkstra’s algorithm find the shortest path from A to F from the 04
following graph.

(c) Using Dynamic programming solve the below instance of the knapsack 07
problem with the knapsack capacity W=5

Item I1 I2 I3 I4
Weight 2 1 3 2
Value 12 10 20 15
OR
Q.4 (a) Explain string matching using finite automata with suitable example. 03
(b) Using Floyd Warshall’s algorithm find the shortest path distance between 04
every pair of vertices from the following graph.

(c) Find the total number of multiplications and optimal multiplication 07

sequence for the following three matrices using dynamic programming.
A = 5 x 5, B = 5 x 4, C = 4 x 8, C = 8 x 2

Q.5 (a) Differentiate between depth first search and breadth first search. 03
(b) Explain use of branch and bound technique for solving assignment 04
problem.
(c) Apply backtracking to the problem of finding Hamilton circuit in the 07
graph shown below.

OR

2
Q.5 (a) Draw the state space tree Diagram to generate the solutions to 03
4-Queen problem.
(b) Explain polynomial-time reduction algorithm. 04
(c) Demonstrate Topological sort for the following graph. 07

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

3
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – SUMMER 2021
Subject Code:2150703 Date:07/09/2021
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) Explain bubble sort in brief with an example. 03

(b) Discuss asymptotic notations in brief. 04
(c) Write an algorithm which finds the maximum number from a given 07
array of numbers using divide and conquer strategy. Explain the
same with proper illustration.

Q.2 (a) Write the differences between divide and conquer strategy and 03
dynamic programming.
(b) Write a brief note on time and space complexity of an algorithm. 04
(c) Arrange the following data into ascending order using heap sort. 07
Make necessary assumptions if required.
34, 12, 42, 96, 56, 11, 78
OR
(c) Solve the following knapsack problem using dynamic programming: 07
Weight W = (w1,w2,w3,w4,w5) = (1, 2, 5, 6, 7)
Profit V = (v1,v2,v3,v4,v5) = (1, 6, 18, 22, 28) and
Knapsack capacity m = 11.
Q.3 (a) Explain counting sort in brief. 03
(b) Describe master method to solve recurrences in brief. 04
(c) Find the total number of multiplications and optimal multiplication 07
sequence for the following three matrices using dynamic
programming.
A=2x5 B= 5x3 C=3x4
OR
Q.3 (a) Discuss the following terms in brief: 03
- Worst case analysis
- Best case analysis
(b) Find multiplication (A x B) of A = 2341 and B = 6780 using divide 04
and conquer methodology.
(c) Discuss Prims’ algorithm with an example. 07
Q.4 (a) Write the problem statement of making change problem. Take small 03
example to support your answer.
(b) What is Huffman code? Explain in brief. 04
(c) Write a note on the following: 07
- Topological sort
- Connected components
OR
Q.4 (a) Check the correctness of the following statement and give proper 03
justification of your answer:
“Greedy strategy does not give guarantee for optimal
1
 solution.”
(b) What is principle of optimality in dynamic programming? 04
(c) Write a note on the following: 07
- BFS
- DFS
Q.5 (a) Write various applications of string matching. 03
(b) Explain the following terms with neat diagram(s): 04
- Directed graph
- Weighted graph
(c) Elaborate 8-queens problem using backtracking. 07
OR
Q.5 (a) Write a brief note on NP-complete problem. 03
(b) Explain branch and bound method in short. 04
(c) Discuss Rabin-Karp algorithm for string matching. 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2021
Subject Code:2150703 Date:15/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) Write the precise definition of Algorithm. Explain time and space 03
complexity of algorithm in brief.
(b) Find the maximum number from the following using divide and 04
conquer strategy.
12, 54, 22,
(c) Write algorithm for90,bubble
26, 10,sort.
78 Apply bubble sort on the 07
following data:
64, 12, 80, 34, 56, 17, 47, 73

Q.2 (a) Find out time complexity for the following pseudo code using O- 03
notation.
for(i = 0; i < n; i++)
{
for(j = 0 ; j < n ; j++)
{
if( i != j )
x = x + 1;
}
}
(b) Briefly discuss Huffman code. 04
(c) Sort the following data in ascending order using heap sort. Write 07
all the necessary steps.
43, 34, 11, 56, 23, 90
OR
(c) Write the Master theorem and explain the same in brief. Solve the 07
following recurrence using it.
T(n) = 9T(n/3) + n
Q.3 (a) Write down the characteristics of Greedy Algorithm. 03
(b) Explain counting sort in brief. 04
(c) Discuss binary search with divide-and-conquer strategy. 07
OR
Q.3 (a) Write differences between dynamic programming and greedy 03
strategy.
(b) Multiply 1456 by 1024 by divide and conquer method. 04
(c) Explain 0/1 knapsack using suitable example. 07
Q.4 (a) Briefly explain assembly line scheduling problem. 03
(b) What is making change problem? Support your answer by taking 04
small example.
(c) Determine Longest Common Subsequence of {N,E,E,L,A,M} 07
and {E,N,G,I,N,E,E,R,I,N,G}.
1
 OR
Q.4 (a) Explain the following terms with brief discussion: 03
- articulation point
- directed graph
(b) Explain naïve string matching algorithm with example. 04
(c) Find an optimal parenthesization of a matrix-chain product whose 07
sequence of dimensions is {5, 2, 4, 5}
Q.5 (a) State pros and cons of breadth-first search. 03
(b) Explain 4-queens problem with backtracking. 04
(c) Discuss Kruskal’s algorithm for minimum spanning tree. 07
OR
Q.5 (a) Discuss NP-hard and NP-complete problems in brief. 03
(b) Write a brief note on topological sort. 04
(c) Explain Rabin-Karp algorithm. 07

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

2
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
 Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER– V EXAMINATION – SUMMER 2020
Subject Code: 2150703 Date:26/10/2020
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) Define the terms: 03

1) Principal of Optimality 2) Feasible solution 3) Quantifier
(b) Analyze Binary search algorithm in best and worst case. 04
(c) Define Asymptotic notation. Arrange the following functions in increasing 07
order of growth.
2n, n2, 1, log n, n log n, 3n and n.

Q.2 (a) Define the function types: 03

1) One-to-One 2) Into (Injective) and 3) Onto (Surjective)
(b) What is the smallest value of n such that an algorithm whose running time is 04
100n2 runs faster than an algorithm whose running time is 2n on the same
machine?
(c) Analyze Quick sort algorithm in best and worst case. 07
OR
(c) Analyze insertion sort algorithm in best and worst case. 07
Q.3 (a) Differentiate divide and conquer approach with dynamic programming 03
approach.
(b) Solve the following recurrence using Master Theorem. 04
T(n)=9T(n/3) + n.
(c) Write equation for Matrix Chain Multiplication using Dynamic programming. 07
Find out optimal sequence for multiplication:
A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal
solution.
OR
Q.3 (a) Differentiate greedy programming approach with dynamic programming 03
approach.
(b) Solve the following recurrence using Master Theorem. 04
T(n) = T(2n/3) + 1.
(c) Using greedy algorithm find an optimal schedule for following jobs with n=6. 07
Profits: (P1, P2, P3, P4, P5, P6) = (20, 15, 10, 7, 5, 3)
Deadline: (d1, d2, d3, d4, d5, d6) =(3, 1, 1, 3, 1, 3).
Q.4 (a) Define and explain P and NP problems with suitable example. 03
(b) Solve the following Knapsack Problem using greedy method. Number of 04
items = 7, knapsack capacity W = 15, weight vector = {2, 3, 5, 7, 1, 4, 1}
and profit vector = {10, 5, 15, 7, 6, 18, 3}.
(c) Find minimum spanning tree using Krushkal’s algorithm of the following 07
graph.

1
 OR
Q.4 (a) Define and explain NP-complete and NP-hard problems with suitable example. 03
(b) Explain Dijkstra’s algorithm to find the shortest path. 04
(c) Find minimum spanning tree using Prim’s algorithm of the following graph. 07

Q.5 (a) Explain the naive string matching algorithm 03

(b) Differentiate between depth first search and breadth first search. 04
(c) Working modulo q = 11. How many spurious hits does the Rabin-Karp matcher 07
encounter in the text T = 3141592653589793 when looking for the pattern P
=26?
OR
Q.5 (a) Explain polynomial-time reduction algorithm. 03
(b) Prove that if G is an undirected bipartite graph with an odd number of vertices, 04
then G is non-Hamiltonian.
(c) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 07
Queens Problem using Backtracking Method.

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER–V (NEW) EXAMINATION – WINTER 2018
Subject Code:2150703 Date:27/11/2018
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.

MARKS

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

(b) Differentiate branch and bound and back tracking algorithm. 04
(c) Analyze Selection sort algorithm in best case and worst case. 07

Q.2 (a) Solve the recurrence T(n) = 7T(n/2) + n3 03

(b) Explain: Articulation Point, Graph, Tree 04
(c) Write Merge sort algorithm and compute its worst case and best-case 07
time complexity. Sort the List G,U,J,A,R,A,T in alphabetical order
using merge sort.
OR
(c) Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42) 07
find the maximum profit using dynamic method.
Q.3 (a) Differentiate the Greedy And Dynamic Algorithm. 03
(b) Demonstrate Binary Search method to search Key = 14, form the array 04
A=<2,4,7,8,10,13,14,60> .
(c) Solve Making change problem using dynamic technique. d1 = 1, d2=2, 07
d3=4, d4=6, Calculate for making change of Rs. 10.
OR
Q.3 5
(a) Find out the NCR ( )Using Dynamic Method. 03
3
(b) Find single source shortest path using Dijkstra’s algorithm form a to e. 04

(c) For the following chain of matrices find the order of parenthesization 07
for the optimal chain multiplication (13,5,89,3,34).
Q.4 (a) Explain Tower of Hanoi Problem, Derive its recursion equation and 03
computer it’s time complexity.
(b) Explain finite automata algorithm for string matching. 04
(c) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} 07
OR
Q.4 (a) Explain Principle of Optimality with example. 03
(b) Define BFS. How it is differ from DFS. 04
(c) Solve the following instance of knapsack problem using Backtracking 07
Technique. The Capacity of the Knapsack W = 8 and w = (2,3,4,5) and
value v = (3,5,6,10)
Q.5 (a) Draw the state space tree Diagram for 4 Queen problem. 03
(b) Define P, NP, NP-Hard and NP-Complete Problem. 04

1
 (c) Find out the Minimum Spanning Tree using Kruskal Algorithm for 07
given Graph.

OR
Q.5 (a) Explain naïve string matching algorithm with example. 03
(b) Explain DFS algorithm in brief. 04
(c) Find all pair of shortest path using Floyd’s Algorithm for given graph 07

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

2
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE- SEMESTER–V (NEW) EXAMINATION – WINTER 2020
Subject Code:2150703 Date:22/01/2021
Subject Name:Analysis and 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.

Q.1 (a) Define O, Ω, θ notations with example. 03

(b) Sort following functions in increasing order of running time for large values 04
of n: n, log2n, 2n ,n2logn, n3
(c) (i) What are the different parameters to analyze any algorithm? 03
(ii) Solve the following using Master’s theorem:
A. T(n) = 2T(n/4) + 1 04
B. T(n) = 3T(n/3) + n

Q.2 (a) Explain Master Theorem for all three cases. 03

(b) (i) What is the smallest value of n such that an algorithm whose running time 04
is 100n2 is runs faster than an algorithm whose running time is 2n on the same
machine?
(ii) What is meaning of T (n) =O(1). Explain with suitable example.
(c) Given the four matrices P5x4, Q4x6, R6x2, T2x7. Find the optimal sequence for 07
the computation of multiplication operation.

Q.3 (a) Mention the parameters for finding suitable algorithm among many candidate 03
algorithms. Justify parameter with suitable example.
(b) i. Which version of algorithm is preferred when memory resources are 04
limited, Iterative or recursive? Justify your answer.
ii. An asymptotically fast algorithm running on Slow computer is better
than asymptotically slow algorithm is running on fast computer for
larger input size. (True/False) Justify your answer with supporting
arguments.
(c) Analyze Selection sort and Insertion Sort algorithms in best case and worst 07
case scenarios.

Q.4 (a) Merge sort algorithm have similar time complexity in best, average and worst 03
case. (True/False). Justify your answer.
(b) Differentiate between greedy approach and Dynamic approach.. 04
(c) How the selection of pivot affects the performance of Quick Sort? Discuss all 07
possible scenarios.

Q.5 (a) How to solve knapsack problem using dynamic programming? 03

(b) Given two strings from 26 symbols set, X="BITTER", Y = "BUTTER" obtain 04
the longest common subsequence.

1
 (c) Compare and contrast Branch and Bound and Backtracking Methods with 07
suitable example.

Q.6 (a) Generate Huffman Code for symbols with probability as 03

A1(0.5),A2(0.25),A3(0.125),A4(0.0625),A5(0.0625).
(b) Find the all pair shortest path using Floyd-Warshall Algorithm for directed 04
graph shown below:

(c) How to solve 0-1 knapsack problem using dynamic programming? Consider 07
Items having Value(Rs.)={60,100,120} , Weight(KG)={10,20,30}
respectively, Weight Capacity =50 KG.

Q.7 (a) Define terms: Articulation Point, Isolated , Adjacency 03

(b) Solve the following Task Assignment problem for minimization using 04
following 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
(c) Find minimum spanning tree for the following undirected weighted graph 07
using Kruskal’s algorithm.

Q.8 (a) What is the significance of Hashing in Rabin-Karp Pattern matching 03

algorithm?
(b) Draw the Finite automata which accepts String over 26 letter alphabet of 04
{A...Z} : ACACAGA
(c) Explain the concept of P, NP and NP-complete problem 07

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

2
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER–V (NEW) - EXAMINATION – SUMMER 2018
Subject Code:2150703 Date:04/05/2018
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.
Q.1 (a) Define Algorithm. Discuss key characteristics of algorithm. 03
(b) Prove or disprove that f(n) = 1 + 2 + 3 + .... + n ∈ Θ(n^2). 04

(c) Which are the basic steps of counting sort? Write counting sort algorithm. 07
Derive its time complexity in worst case.

Q.2 (a) What are the advantages of dynamic programming method over devide-&- 03
conquer method?

(b) Solve following recurrence using recursion tree method: T(n) = 3T(n/3) + 04
n^3.

(c) Write standard(conventional) algorithm and Strassen's algorithm for matrix 07

multiplication problem. What is the recurrence for Strassen's algorithm?
Solve it using master method to derive time complexity of Strassen's
algorithm.

OR
(c) Discuss best case, average case and worst case time complexity of quick sort. 07

Q.3 (a) Justify with example that shortest path problem satisfies the principle of 03
optimality.
(b) Which are the three basic steps of the development of the dynamic 04
programming algorithm? Mention any two examples of dynamic
programming that we are using in real life.
(c) Solve the following making change problem using dynamic programming 07
method: Amount = Rs. 7 and Denominations: (Rs. 1, Rs. 2 and Rs. 4)

OR
Q.3 (a) Justify with example that longest path problem does not satisfy the principle 03
of optimality.
(b) Discuss general characteristics of greedy method. Mention any two examples 04
of greedy method that we are using in real life.
 (c) Solve all pair shortest path problem for the following graph using Floyd's 07
algorithm.

Q.4 (a) What are the disadvantages of greedy method over dynamic programming 03
method?

(b) What is DFS? Explain with example. Show the ordering of vertices produced 04
by Topological-sort for the following graph.

(c) Solve the following Knapsack Problem using greedy method. Number of 07
items = 5, knapsack capacity W = 100, weight vector = {50, 40, 30, 20, 10}
and profit vector = {1, 2, 3, 4, 5}.

OR
Q.4 (a) Write an algorithm for Huffman code. 03
(b) What is an approximation algorithm? Explain performance ratio for 04
approximation algorithm.
(c) Explain use of branch and bound technique for solving assignment problem. 07

Q.5 (a) Write Naive string-matching algorithm. Explain notations used in the 03
algorithm.

(b) Explain polynomial-time reduction algorithm. 04

(c) Working modulo q = 11. How many spurious hits does the Rabin-Karp 07
matcher encounter in the text T = 3141592653589793 when looking for the
pattern P =26?
 OR

Q.5 (a) Which are the three major concepts used to show that a problem is an NP- 03
Complete problem?
(b) Explain breadth first search with example. 04
(c) Find minimum spanning tree for the following undirected weighted graph 07
using Kruskal’s algorithm.

*************
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER– V (New) EXAMINATION – WINTER 2019
Subject Code: 2150703 Date: 25/11/2019
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.

MARKS

Q.1 (a) Find Omega (Ω) notation of function f(n)=2n2 + 6 n * lg n + 6n. 03

(b) Define Big-oh and Theta notations with graph. 04
(c) Write sequential search algorithm and analyze it for worst case time 07
complexity. Represent its time complexity using Big-oh (O) notation.

Q.2 (a) Find upper bound of function f(n)= lg(n2) + n2 lg n. 03

(b) If P(n) = a0+ a1 n + a2 n2 + . . . . . . + amnm then prove that P(n) = 04
O(nm). 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/3) + T(2n/3) + Ө(n)
OR
(c) Solve following recurrence relation using suitable method and express 07
your answer using Big-oh (O) notation.
T(n) = 2 T(n/2) + n2
Q.3 (a) If T1(n) = O(f(n)) & T2(n) = O(g(n)) then prove that T1(n) + T2(n) = 03
max(O(g(n)), O(f(n))).
(b) Illustrate the working of the quick sort on input instance: 25, 29, 30, 04
35, 42, 47, 50, 52, 60. 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) Arrange following growth rates in increasing order. 03
O(n1/4), O(n1.5), O(n3 lg n), O(n1.02), Ω(n6), Ω(n!), O(√n), O(n6/2), Ω(2n)
(b) Illustrate the working of the merge sort algorithm on input instance: 04
10, 27, 30, 88, 17, 98, 42, 54, 72, 95. Also write best case time
complexity of merge sort algorithm.

1
 (c) What is a minimum spanning tree? Draw the minimum spanning tree 07
correspond to following graph using Prim’s algorithm.
B 8 C 7 D
4 9
2

A 11 I 4 14 E

8 7 6
10
H 1 G 2 F

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

(b) Consider the instance of the 0/1 (binary) knapsack problem as below 04
with P depicting the value and W depicting the weight of each item
whereas M denotes the total weight carrying capacity of the knapsack.
Find optimal answer using greedy design technique. Also write the
time complexity of greedy approach for solving knapsack problem.
P = [40 10 50 30 60] W = [80 10 40 20 90] M = 110
(c) Find the optimal way of multiplying following matrices using dynamic 07
programming. Also indicate optimal number of multiplications
required.
A:3 x 2, B: 2 x 5, C:5 x 4, D: 4 x 3, E: 3 x 3
OR
Q.4 (a) Explain depth first traversal using suitable example. 03
(b) Explain Binomial Coefficient algorithm using dynamic programming. 04
(c) Find the longest common subsequence for the following two sequences 07
using dynamic programming. Show the complete process.
X = 100101001
Y = 101001
Q.5 (a) Define P and NP problems. Also give example of each type of problem. 03
(b) Draw the state space tree diagram for 4 Queen problem and also show 04
the tree after applying backtracking.
(c) Explain Rabin – Karp algorithm with example. What is expected 07
running time of this algorithm?
OR
Q.5 (a) Define NP-Complete and NP-Hard problems. Also give examples. 03
(b) Explain the naive string matching algorithm. 04
(c) State whether Hamiltonian problem is a NP-Complete problem? 07
Justify your answer.

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