Question Bank - DAA

1) Define feasible and optimal solution.

Feasible and Optimal Solution:

• In optimization problems, a feasible solution satisfies all problem constraints but isn’t
necessarily the most efficient or cost-effective choice. For example, in a transportation
problem where we need to deliver goods using trucks with limited capacity, any
allocation of goods that respects the capacity limits is feasible.
• An optimal solution is a feasible solution that either maximizes or minimizes the
objective function (like cost, time, or profit). Using the transportation example, the
optimal solution would minimize transportation costs while still delivering all goods
within capacity limits.

2) Write short note on optimal merge pattern.

Optimal Merge Pattern:

• When merging multiple sorted lists, the goal is to minimize the total number of
comparisons. The optimal merge pattern can be computed by repeatedly merging the
smallest lists first. This pattern follows a process similar to Huffman coding, where a
tree structure minimizes the overall path length. In merging terms, this translates to
minimizing comparisons required to merge all lists into one.

3) Explain knapsack problem in detail.

Knapsack Problem:

• Given a knapsack with a weight limit and items with specific weights and values, the
objective is to maximize the total value without exceeding the weight. There are two
main versions:
o 0/1 Knapsack: Each item is either fully included or excluded (binary choice),
solved using dynamic programming.
o Fractional Knapsack: Items can be split into fractions, so it's possible to take
only a part of an item. This is solved greedily by taking items with the highest
value-to-weight ratio until the knapsack is full.
4) Explain binary search? Write algorithm for it. Consider the following elements of
array.
Index 1 2 3 4 5 6 7 8 9 10
Element -15 -10 0 7 12 30 45 58 82 104

Binary Search and Algorithm:

• Binary search works on sorted arrays, reducing the search space by half each time,
which gives a time complexity of O(log⁡n)O(\log n)O(logn).
• Algorithm:
1. Start with low at the start and high at the end of the array.
2. Find the middle element at mid = (low + high) / 2.
3. If array[mid] is the target, return mid.
4. If array[mid] is greater than the target, search in the left half by setting high =
mid - 1.
5. Otherwise, search in the right half by setting low = mid + 1.
6. Repeat until the target is found or low > high.

5)Explain activity selection problem.

Activity Selection Problem:

• This is about selecting the maximum number of non-overlapping activities from a list,
each with a start and end time. By sorting activities by end times and always choosing
the next compatible activity, a greedy approach ensures the maximum number of
activities is selected.

6)Explain quick sort with suitable example.

Quick Sort:
• Quick sort is an efficient sorting algorithm that works by selecting a pivot element and
partitioning the array around it, placing elements smaller than the pivot to the left and
larger to the right. This process is repeated recursively on each partition. The choice
of pivot greatly affects performance, but on average, the time complexity is O(nlogn).

7)Write a short note on Strassen’s matrix multiplication.

Strassen’s Matrix Multiplication:

• Strassen’s algorithm improves traditional matrix multiplication by breaking matrices
into smaller submatrices and combining them in fewer operations. Specifically, it
reduces the required multiplications from 8 (in a naive method) to 7 for each step,
resulting in an overall time complexity of O(n2.81)O(n^{2.81})O(n2.81).
 8)What is difference between divide and conquer dynamic programming?

Divide and Conquer vs. Dynamic Programming:

• Divide and Conquer divides a problem into independent subproblems that don’t
overlap (e.g., merge sort). Each subproblem is solved separately, and results are
combined.
• Dynamic Programming is used when subproblems overlap (e.g., Fibonacci sequence)
by storing solutions to subproblems, thus reducing the number of calculations.

9)What is backtracking?

• Backtracking:

• Backtracking is a recursive method to solve problems incrementally by building a

solution piece by piece and removing parts that fail to satisfy constraints. It’s
commonly used in puzzles like the N-Queens problem, where queens are placed on a
chessboard one by one. If a placement conflicts, it backtracks and tries another
configuration.

10)Explain sum of subset problem with suitable example.

• Subset Sum Problem:

• In this problem, given a set of numbers, the goal is to find subsets that sum to a
specific target value. Using recursion or dynamic programming, you decide for each
element to include it in the subset or exclude it, testing if any combination meets the
target. Dynamic programming helps store solutions to subproblems (e.g., for each
subset sum up to the target).

11)Explain all pairs shortest path.

• All Pairs Shortest Path:

• This problem seeks the shortest path between every pair of nodes in a weighted graph.
The Floyd-Warshall algorithm solves it using dynamic programming by checking if
the path between each pair can be minimized through an intermediate node. The
algorithm iterates through each node as an intermediary and updates path lengths.
 12)Define:

i. P-class problem
ii. Np hard problem
iii. Np complete problem

• Definitions of Complexity Classes:

• P-class: Problems solvable in polynomial time (e.g., sorting a list).

• NP-hard: Problems as hard as the most difficult problems in NP. Solutions are not
guaranteed to be verified in polynomial time.
• NP-complete: Problems in NP that are verifiable in polynomial time and are as hard as
any other NP problem.

13)Define Algorithm? State the main characteristics of Algorithm.

• Algorithm and Characteristics:

• An algorithm is a clear step-by-step solution to a problem. Characteristics include:

o Finiteness: Algorithm halts after a limited number of steps.
o Definiteness: Each step is precisely defined.
o Input/Output: Takes inputs and produces outputs.
o Effectiveness: Each operation can be carried out in finite time.

14)Describe Asymptotic notations with expression.

• Asymptotic Notations:

• Notations are used to describe an algorithm’s behavior as input size grows.

o Big O (O): Upper bound, representing the worst-case scenario.
o Omega (Ω): Lower bound, representing the best-case scenario.
o Theta (Θ): Represents the exact growth rate when upper and lower bounds are
the same.

15)Evaluate 9T(n/3) + n.

• Evaluate 9T(n/3) + n:

• This recurrence can be evaluated using the Master theorem, which gives solutions for
recurrences of the form T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n),
allowing us to determine asymptotic behavior based on values of aaa, bbb, and
f(n)f(n)f(n).
16)Describe an algorithm for Merge Sort and find its time complexity.

• Merge Sort Algorithm and Time Complexity:

• Merge Sort splits an array into halves, recursively sorts each half, and merges them.
This requires O(nlog⁡n)O(n \log n)O(nlogn) time because it divides the array
O(log⁡n)O(\log n)O(logn) times and merges takes O(n)O(n)O(n) at each level.

17) Solve using Strassen’s matrix multiplication, and Calculate its time complexity.

• Strassen’s Matrix Multiplication Calculation:

• Strassen’s algorithm splits matrices into quadrants and recursively computes sums and
products to reduce operations. It’s faster than conventional methods, particularly for
large matrices, due to its complexity of O(n2.81)O(n^{2.81})O(n2.81).

18)Apply branch and bound technique to solve travelling salesman problem for the graph
whose matrix is

 20 30 10 11
15  16 4 2
3 5  2 4
19 6 18  3
16 4 7 16 

• Branch and Bound for TSP:

• Branch and Bound optimizes the traveling salesman problem by exploring paths and
using bounds (cost limits) to prune paths that exceed known solutions. This approach
prevents unnecessary path calculations.

19)Describe Graph Coloring Problem with suitable example.

• Graph Coloring Problem:

• This problem assigns colors to graph vertices so no two adjacent vertices share the
same color. For example, in scheduling exams for courses with overlapping students,
each course is a vertex, and a color represents a timeslot.
20) Solve the Fractional Knapsack problem Given n = 5 objects and a knapsack

Capacity W =60 profit= (30, 20,100,90,160) Weight = (5,10,20,30,40).

• Fractional Knapsack Problem:

• Items are sorted by value-to-weight ratio, and the knapsack is filled by taking items
with the highest ratios first. If the knapsack reaches capacity with only part of an item,
that fraction is taken. This greedy approach ensures optimal total value.

21)Solve Job sequencing with deadlines n = 4, p = (100,10,15,27) and d = (2,1,2,1) find

optimal solution.

• Job Sequencing with Deadlines:

• In this problem, jobs must be scheduled to maximize profit within given deadlines.
Jobs are first sorted by profit, and then scheduled in the latest possible time slots
before their deadlines, maximizing total profit within the given time constraints.

22) Calculate the shortest path by using Floyd’s Warshall Algorithm.

0 4 5
2 0 
 -3 0

• Floyd-Warshall Algorithm for Shortest Path:

• Floyd-Warshall is a dynamic programming algorithm that checks for each pair of

nodes if a shorter path exists by routing through an intermediate node. It updates paths
in a matrix, progressively refining the shortest paths between all node pairs.
 23) Differentiate between Dynamic Programming and greedy Approach.

• Dynamic Programming vs. Greedy Approach:

• Dynamic Programming solves overlapping subproblems by storing solutions, ideal for

problems like the knapsack where choices affect subsequent subproblems.
• Greedy Approach makes the best local choice at each step, like in the activity
selection problem. It doesn’t backtrack or revise choices, aiming for efficiency but not
always guaranteeing the best solution for all types of problems.

24) Solve using Huffman coding.

Message = BCCABBDDAECCBBAEDDCC

• Huffman Coding:

• Huffman coding builds a binary tree from character frequencies, assigning shorter
codes to more frequent characters. Each character's frequency determines its path
length, so the total length of encoded data is minimized, making it a powerful
technique for data compression.