DAA MTE Sample Question Solution

1. Construct a dynamic programming algo to find the length of the longest

common subsequence of two strings.

Suppose X and Y are the two given sequences

Initialize a table of LCS having a dimension of X.length * Y.length
XX.label = X
YY.label = Y
LCS[0][] = 0
LCS[][0] = 0
Loop starts from the LCS[1][1]
Now we will compare X[i] and Y[j]
if X[i] is equal to Y[j] then
LCS[i][j] = 1 + LCS[i-1][j-1]
Point an arrow LCS[i][j]
Else
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

For detailed explanation visit: https://www.javatpoint.com/longest-common-

subsequence

2. Explain what "asymptotic analysis" is and how it helps in evaluating the

efficiency of algorithms.

Asymptotic analysis is a mathematical technique that helps evaluate the

efficiency of algorithms. It describes how an algorithm's performance changes
as the size of its input increases.
How it works
 Asymptotic notations
Asymptotic analysis uses mathematical tools called asymptotic notations to
describe an algorithm's growth rate or time complexity.
 Big O notation
A common way to express asymptotic analysis in computer science. Big O
notation describes how the time or space needed by an algorithm grows as
the input size increases.
 Best-case, average-case, and worst-case
Asymptotic analysis can determine the run-time performance of an algorithm
in these three scenarios.
 Compare algorithms
Asymptotic analysis helps compare different algorithms based on their
efficiency for large problem sizes.
Benefits
 Understand algorithm behavior
Asymptotic analysis helps you understand how an algorithm performs in
realistic scenarios.
 Improve algorithms
Asymptotic analysis can help you identify areas for improvement in an
algorithm.
 Choose algorithms
Asymptotic analysis helps you choose one algorithm over another based on
your requirements.

 Ensure algorithm performance

Asymptotic analysis helps you ensure that an algorithm can perform without
crashes or severe delays.

3. Explain best-case, worst-case and average-case time complexity.

Best-case, worst-case, and average-case time complexity are ways to

categorize the time it takes an algorithm to complete a task.

Best-case The best-case time complexity is the minimum amount of time an

algorithm can take to complete a task. It represents the best possible outcome
for a program. For linear search, the best case occurs when x is present at
the first location. The number of operations in the best case is constant (not
dependent on n). So the order of growth of time taken in terms of input size is
constant.

Worst-case The worst-case time complexity is the maximum amount of time

an algorithm can take to complete a task. It represents the scenario that
results in the highest number of arithmetic operations. For Linear Search, the
worst case happens when the element to be searched (x) is not present in the
array. When x is not present, the search() function compares it with all the
elements of arr[] one by one.

Average-case The average-case time complexity is the average amount of

time an algorithm takes to complete a task. It's calculated by adding the
running times for each possible input combination and taking the average. We
must know (or predict) the distribution of cases. For the linear search problem,
let us assume that all cases are uniformly distributed (including the case of x
not being present in the array). So we sum all the cases and divide the sum
by (n+1). We take (n+1) to consider the case when the element is not present.

Why is Worst Case Analysis Mostly Used?

 Average Case : The average case analysis is not easy to do in most practical
cases and it is rarely done. In the average case analysis, we need to consider
every input, its frequency and time taken by it which may not be possible in
many scenarios

Best Case : The Best Case analysis is considered bogus. Guaranteeing a

lower bound on an algorithm doesn’t provide any information as in the worst
case, an algorithm may take years to run.

Worst Case: This is easier than average case and gives an upper bound
which is useful information to analyze software products.

4. Analyze the space complexity of an iterative approach to calculating

factorials and bubble sort.

In an iterative approach to calculating factorials, we use a loop to compute the

product of all integers from 1 to n. Let's analyze its space complexity:

Algorithm:

Space Complexity Analysis:

Variables Used:

 result: Stores the cumulative product. This is a single variable.

 i: Loop variable. Also a single variable.

Additional Memory:

 No additional memory (like arrays or recursion stacks) is required.

the size of n, the space complexity is 𝑂(1).

Since the algorithm only uses a constant number of variables irrespective of

2. Space Complexity of Bubble Sort

Bubble sort is a comparison-based sorting algorithm where adjacent elements
are swapped to order them correctly.
 Algorithm:

Space Complexity Analysis:

Input Array:

 Bubble sort operates in-place, meaning it modifies the input array

directly. No additional array is created.
Auxiliary Variables:

 i and j: Loop variables.

 Temporary variable for swapping (if implemented explicitly).
These variables occupy constant space.

Since no extra memory is used apart from the input array and a few loop
variables, the space complexity is O(1).
Summary:
Iterative Factorial: O(1)
Bubble Sort: O(1)
Both algorithms are space-efficient as they operate with a constant amount of
additional memory.

5. Design a recursive algorithm to calculate the factorial of a natural

number. Establish the recurrence relation for the number of basic
operations and solve it.

Recursive Algorithm to Calculate Factorial

A recursive algorithm for calculating the factorial of a natural number n
involves repeatedly breaking the problem down into smaller subproblems
using the relationship:
6. Describe the CONSOLIDATE and UNION operation in a Fibonacci Heap
using an appropriate example.

A Fibonacci Heap is a data structure for priority queue operations that

achieves O(1) amortized time for operations like insert and decrease-key,
and O(log n) for delete and extract-min. It is composed of a collection of
trees that follow the min-heap property (i.e., the key of the parent is smaller
than or equal to the keys of its children).

1. CONSOLIDATE Operation
The consolidate operation is a crucial step in the extract-min operation. Its
goal is to reduce the number of trees in the heap by merging trees of the
same degree into a single tree. This is achieved by repeatedly linking trees of
the same degree (number of children) until no two trees have the same
degree.

https://www.javatpoint.com/fibonacci-heap

2. UNION Operation
The union operation combines two Fibonacci Heaps into one. It is performed
by concatenating the root lists of both heaps and updating the min-node
pointer to the minimum of the two heaps’ min-node.

https://www.programiz.com/dsa/fibonacci-heap

7. Compare the trade-offs between various sorting algorithms using their

time and space complexities, considering algorithms like Merge Sort,
Quick Sort, and Heap Sort.

When comparing the time and space complexities of sorting algorithms like
Merge Sort, Quick Sort, and Heap Sort, you can consider things like:

Time complexity: The time it takes to run the algorithm

 Space complexity: The amount of memory required to run the algorithm
In-place sorting: Whether the algorithm sorts within the array

Extra memory required: How much extra memory the algorithm needs
Here's some information about the time and space complexities of these
algorithms:

Merge Sort
Has a time complexity of O(N log N) and a space complexity of O(N). Merge
Sort requires additional arrays for merging.

Quick Sort
Has a time complexity of O(N log N) and a space complexity of O(N). Quick
Sort can be implemented to be in-place, but it's not inherently stable. It
requires minimal extra memory, only for recursion.

Heap Sort
Has a time complexity of O(N log N) and a space complexity of O(1). Heap
Sort is an in-place sorting algorithm that doesn't require extra space.

8. Compare the trade-offs between dynamic programming and greedy

algorithms in terms of efficiency and applicability to different types of
problems.

Dynamic programming and greedy algorithms are both problem-solving

techniques used in algorithm design. They differ in their methodologies, and
the choice of which to use depends on the problem and its constraints.

Dynamic programming Greedy algorithms

Approach Breaks down problems into subproblems Makes locally optimal choices at each
and stores their solutions step

Optimality Ensures the optimality of the solution May not always produce an optimal
solution

Efficiency Can be more complex and time-consuming Often have lower time complexity
to implement compared to other algorithms

Applicability Used for problems with overlapping Used for problems with the optimal
subproblems and optimal substructure greedy choice property
 Explanation:

Dynamic programming
This technique is based on the principles of optimal substructure and
overlapping subproblems. It can be used to solve complex problems by
breaking them down into simpler subproblems.

Greedy algorithms
This method follows the strategy of making the most optimal choice at each
step. It can quickly arrive at a solution without the need for complex
backtracking.

Some examples of problems that can be solved using greedy algorithms

include Huffman coding, Prim's algorithm, and Kruskal's algorithm.

9. Explain the method of designing a greedy algorithm and the key steps
involved in its development.

To design a greedy algorithm, you can follow these steps:

Identify the problem: Understand the problem and determine if it can be

solved using a greedy approach.

Identify the objective function: Define what the solution will include, such as
the shortest path or the largest sum.

Identify subproblems: Find the best substructure or subproblem in the

problem.

Determine optimal solutions: Identify the optimal solutions for each

subproblem.

Create an iterative process: Create a way to go through all the subproblems

and build a solution.

Combine the solutions: Join the sub-solutions to form the overall optimal
solution.

Explanation
A greedy algorithm is a method for solving problems by making the best
choice at each step. The algorithm makes a greedy choice, which means
selecting the option that offers the most immediate benefit.
10. Describe the working of a greedy algorithm using the coin change
problem and traveling salesman problem as an example to illustrate the
process.

A greedy algorithm works by making the "best" choice available at each step,
aiming to find an optimal solution to a problem by always selecting the locally
optimal option, without considering the potential impact on future
choices. This strategy can be illustrated effectively using the Coin Change
Problem and the Traveling Salesman Problem (TSP).

Coin Change Problem:

 Problem Statement:
Given a set of coin denominations and a target amount, find the minimum
number of coins needed to make the exact amount.
 Greedy Approach:
 Sort the coin denominations in descending order.
 At each step, select the largest denomination coin that is less than or
equal to the remaining amount and add it to the solution.
 Repeat this process until the remaining amount becomes zero.

Example:
 Consider denominations: {25, 10, 5, 1} and target amount: 63
 Greedy Algorithm steps:
o Select the largest denomination (25), add 2 coins (50).
o Remaining amount: 13
o Select the next largest denomination (10), add 1 coin (10).
o Remaining amount: 3
o Select the next largest denomination (5), add 1 coin (5).
o Remaining amount: - add 3 coins of denomination 1.

Traveling Salesman Problem (TSP):

 Problem Statement:
Given a list of cities and the distances between them, find the shortest
possible route that visits each city exactly once and returns to the starting city.
 Greedy Approach (Nearest Neighbor):
 Start at an arbitrary city.
 At each step, select the unvisited city closest to the current city and
add it to the route.
 Continue this process until all cities have been visited.
Example:
 Cities: A, B, C, D, E
 Distance matrix:
o A - B: 5
o A - C: 7
o A - D: 2
 o B - C: 3
o B - D: 6
o C - D: 4
 Greedy Algorithm steps:
o Start at A.
o Select D (closest to A).
o Select C (closest to D).
o Select B (closest to C).
o Return to A.
 Route: A - D - C - B - A
Important Considerations:
 Not always optimal:
While simple to implement, greedy algorithms do not always guarantee the
optimal solution for all problems. For example, in certain scenarios with the
TSP, the nearest neighbor approach might not produce the shortest possible
route.
 Greedy Choice Property:
For a problem to be solved optimally with a greedy algorithm, it must exhibit
the "greedy choice property" - selecting the best option at each step must lead
to the overall optimal solution.
 Time Complexity:
Greedy algorithms are often efficient in terms of time complexity, as they only
need to make local decisions at each step.

11. Explain the Fib-Heap Extract min process and apply the process in the
given examples.

https://www.geeksforgeeks.org/fibonacci-heap-deletion-extract-min-and-
decrease-key/

12. Explain the travelling salesman problem with approximation and

Dynamic programming.

The travelling salesman problem using dynamic programming breaks the

problem into smaller subproblems. It solves these subproblems and stores the
results to avoid redundant calculations. Time Complexity: O(n² * 2^n).
Advantages: More efficient than brute-force and provides an exact solution.

The traveling salesman problem (TSP) is a well-known optimization problem

in computer science and operations research. It asks for the shortest route
that visits every city in a list exactly once and returns to the starting city.
 Explanation

What is the TSP?

The TSP is an NP-hard problem, which means that there is no known
algorithm that can solve all instances of the problem in polynomial time.

How is the TSP modeled?

The TSP can be modeled as a graph problem, where each vertex represents
a city and each edge represents the distance between two cities.

Approximation algorithms
Approximation algorithms try numerous permutations and select the shortest
route with the minimum cost.

Dynamic programming
Dynamic programming can be used to find the exact optimal solution, but it's
usually not practical for large problems.

13. Explain in detail about Prims’s algorithm with example and analyze its
efficiency.

Prim's algorithm is a greedy algorithm used to find the minimum spanning tree
(MST) of a weighted, undirected graph. It's a popular algorithm in graph
theory that's used in network design and clustering.
How it works
1. Start with a single vertex
2. Find the vertex with the lowest edge weight that connects to the current tree
3. Add that vertex and edge to the tree
4. Repeat until all vertices are included in the tree
Explanation
 Greedy algorithm
Prim's algorithm is a greedy algorithm, which means it selects the best option
available at the moment.
 Minimum spanning tree
The goal of Prim's algorithm is to find the MST, which is the collection of
edges that connects all vertices with the lowest total weight.
 Weighted graph
Each edge in a graph has a weight that indicates how long or costly it is to
travel between two nodes.
 Connected graph
For Prim's algorithm to work, all the nodes in the graph must be connected.
Example
You can imagine using Prim's algorithm to build a network of roads between
several towns.
Efficiency
 Greedy algorithms are often efficient and easy to implement. They can help
find a lower bound of the solution quality for many challenging real-world
problems.

14. Why Dijkartra and Bellmen ford algorithm are differing from each other?
Even both are single-source SP.

Dijkstra's algorithm and the Bellman-Ford algorithm differ in how they handle
graphs with negative edge weights:
 Dijkstra's algorithm
Can only be used for single-source shortest path problems with non-negative
edge weights.
 Bellman-Ford algorithm
Can be used for single-source shortest path problems with graphs that may
have negative edge weights. It can also detect negative weight cycles.
Explanation
 Dijkstra's algorithm
Solves the single-source shortest path problem by exploring all possible
ways.
 Bellman-Ford algorithm
Solves the single-source shortest path problem by computing shortest paths
from a single source vertex to all other vertices in a weighted digraph. It can
handle graphs with some edge weights that are negative numbers.
 Negative weight cycles
If a graph contains a negative cycle that is reachable from the source, then
there is no cheapest path. The Bellman-Ford algorithm can detect and report
the negative cycle.

15. Describe the structure of a Fibonacci Heap and explain the role of the
following components:
 Root list
 Marked nodes
 Child pointers
How do these contribute to its efficiency?

A Fibonacci heap is a collection of rooted trees that are min-heap ordered. The
structure of a Fibonacci heap includes:
 Root list: A circular, doubly linked list that links the roots of all the trees in the
heap
 Child lists: Doubly linked lists that maintain the elements in each level of the
heap
 Marked nodes: Nodes that have lost a child
  Pointers: Each node has pointers to its parent, left node, right node, and
child
 Min pointer: A pointer that keeps track of the minimum element in the heap
How these components contribute to efficiency:
 Root list
The root list allows for the efficient insertion and removal of nodes. For example,
to insert a new key, a single node is added to the root list. To merge two Fibonacci
heaps, the two root lists are merged.
 Child lists
The child lists allow for the efficient insertion and deletion of nodes in any position
in the list.
 Marked nodes
The marking of nodes allows the heap to track some history about each
node. For example, a node is marked when its child is cut from a tree.
 Min pointer
The min pointer allows for the efficient retrieval of the minimum element in the
heap.

16. Explain BST algorithm and its time complexity.

The time complexity of a binary search tree (BST) depends on the balance of
the tree. In a balanced BST, the time complexity is (O(log(n)) where n is the
number of nodes in the tree. In an unbalanced BST, the time complexity can
be O(n).
.
Explanation
 What is a BST?
A BST is a data structure that allows for fast lookup, insertion, and removal of
data items. It's also known as an ordered or sorted binary tree.
 How does a BST work?
The nodes in a BST are arranged so that each comparison skips about half of
the remaining tree. This means that the lookup performance is proportional to
the logarithm of the number of items stored in the tree.
 What is time complexity?
Time complexity is a measure of how much computer time it takes to run an
algorithm. It's usually expressed as a function of the size of the input.
 When is a BST balanced?
A BST is balanced if the height of the left and right subtrees of any node only
differs by one.
 What happens when a BST is unbalanced?
 of 𝑂(𝑛).
An unbalanced BST can lead to inefficient operations with a time complexity

.
 How can we improve the performance of a BST?
Self-balancing trees, such as AVL and red-black trees, are more effective than
basic BSTs.