B.E / B.Tech.

PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023

Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Design an algorithm to generate the subsets of a given set

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023

Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Implement the recursive algorithm and compute the order of growth from log2n to n!.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Demonstrate a set of activities, along with the starting and finishing time of each activity,
find the maximum number of activities performed by a single person assuming that a
person can only work on a single activity at a time

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023

Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Find all possible solutions for the five queen problems using the backtracking approach.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Suppose we have 8 coins and we want to find which one is the fake coin; assume that we
know the fake coin is lighter than the real ones. In how many steps can you guarantee to
find the fake coin? What are the steps? 1. Put 4 coins on each side of the balance.
Discard the coins on the side that is heavier because we know the fake coin is on the
lighter side. 2. From the 4 put 2 coins on each side of the balance. Discard the coins on
the side that is heavier. We now know that the fake coin is one of two. 3. Put one coin on
each side. The coin that is lighter is the fake coin.

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Implement the recurrence equation for the running time of Slow heap.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023

Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Implement the bottom up (non-recursively) for the example 6, 5, 3, 1, 8, 7, 2, 4.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Implement the non-recursive algorithm and compute the order of growth from log2n to
n!

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023

Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Suppose you are given the coins 1 cent, 5 cents, and 10 cents with N = 10 cents, what are
the total number of combinations of the coins you can arrange to obtain 10 cents.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Let there be N workers and N jobs. Any worker can be assigned to perform any job,
incurring some cost that may vary depending on the work-job assignment. It is required to
perform all jobs by assigning exactly one worker to each job and exactly one job to each
agent in such a way that the total cost of the assignment is minimized.

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

You are given a sequence of coins of various denominations as part of the coin change
problem. For example, consider the following array a collection of coins, with each
element representing a different denomination.
{ 2, 3, 5, 10, 20, 30, 50 }
Our goal is to use these coins to accumulate a certain amount of money while using the
fewest (or optimal) coins. Furthermore, you can assume that a given denomination has
an infinite number of coins. To put it another way, you can use a specific denomination
as many times as you want.

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

A thief enters a house for robbing it. He can carry a maximal weight of 5 kg into his bag.
There are 4 items in the house with the following weights and values. What items should
thief take if he either takes the item completely or leaves it completely?

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

For example, we have two items having weights 2kg and 3kg, respectively. If we pick
the 2kg item then we cannot pick 1kg item from the 2kg item (item is not divisible); we
have to pick the 2kg item completely. This is a 0/1 knapsack problem in which either we
pick the item completely or we will pick that item. Find the solution by dynamic
programming algorithm.?

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Use Simplex method to solve the farmer’s problem given below.

A farmer has a 320 acre farm on which she plants two crops: corn and soybeans. For each
acre of corn planted, her expenses are $50 and for each acre of soybeans planted, her
expenses are $100. Each acre of corn requires 100 bushels of storage and yields a profit of
$60; each acre of soybeans requires 40 bushels of storage and yields a profit of $90. If the
total amount of storage space available is 19,200 bushels and the farmer has only $20,000
on hand, how many acres of each crop should she plant in order to maximize her profit?
What will her profit be if she follows this strategy.

OUTPUT
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE RECORD
MARKS
(20) (30) RESULTS (10) (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Suppose we have 12 coins and we want to find which one is the fake coin; assume that
we know the fake coin is lighter than the real ones. In how many steps can you guarantee
to find the fake coin? What are the steps? How do the number of steps compare with the
8 coin example? 1. Put 6 coins on each side of the balance. Discard the coins on the side
that is heavier because we know the fake coin is on the lighter side. 2. From the 6 put 3
coins on each side of the balance. Discard the coins on the side that is heavier. We now
know that the fake coin is one of three. 3. Put one coin on each side and leave the other
off the balance. If one of the coins on the balance is lighter, then it is the fake. If the
balance is level then the coin to the side is the fake.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Demonstrate a set of tasks with deadlines and total profit earned on completing a task,
find maximum profit earned by executing the tasks within the specified deadlines.
Assume that a task takes one unit of time to execute, and it can’t execute beyond its
deadline. Also, only a single task will be executed at a time.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

The above graph shows a set of cities and distance between every pair of cities. Solve
using branch and bound method to find shortest distance

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers
as follows:

a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21

A Huffman code is used to represent the characters. What is the sequence of characters
corresponding to the following code?

110111100111010

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Consider the following directed weighted graph.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER

B.E / B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2023
Third Semester
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS
(Regulations 2021)

Time: 3 Hours Max. Marks 100

Construct two square matrices A and B of size n x n each, find their multiplication matrix
using Strassen’s Matrix Multiplication.

OUTPUT RECORD
TOTAL
AIM & ALGORTHIM PROGRAM & VIVA VICE (10)
MARKS
(20) (30) RESULTS (10)
(100)
(30)

INTERNAL EXAMINER EXTERNAL EXAMINER