Shopping cart0.00₹
Login

DAA Regular 2024 (NEP) Solved Question Paper Questions with Answers

DAA 2 Marks (IMP)

Section - A

Answer any TEN questions. Each question carries 2 marks. (10x2=20)

1. Define algorithm? Mention its criteria's.
  • An algorithm is a step – step procedure used for calculations, problem-solving, and decision making.
  • It is a finite sequence of well-defined, unambiguous instructions to achieve a particular outcome.

criteria’s.

  1. Finiteness

  2. Definiteness

  3. Input

  4. Output

2. Mention areas where algorithms are used.
  1. Data Analysis and Big Data
  2. Artificial Intelligence and Machine Learning
  3. Computer Science and Software Development

  4. Robotics and Automation

  5. Networking

3. Define asymptotic Notation? Name them.

Asymptotic Notation is used to describe the running time of an algorithm – how much time an algorithm takes with a given input, n. There are three different notations: big O, big Theta (Θ), and big Omega (Ω).

4. Define space complexity and time complexity.
  • Space complexity is a measure of the amount of memory required to run an algorithm. It is typically expressed as a function of the input size.
  • Time Complexity refers to the computational time an algorithm takes to run as a function of the length of the input. 
5. What is Prim’s Algorithm ?

Prim’s algorithm (also known as Jarník’s algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

6. Define Decrease - and - conquer.

Decrease-and-Conquer is an algorithmic design paradigm where a problem is solved by reducing its size (or complexity) to make it easier to solve. The key idea is to solve smaller subproblems recursively until a base case is reached.

or
  • Decrease: Reduce the problem to a smaller instance of the same problem.
  • Conquer: Solve the smaller problem, either iteratively or recursively.
7. Define decision tree? Mention key factors.

A decision tree is a graphical representation of possible solutions to a decision-making problem, which uses a tree-like model of decisions and their possible consequences. Decision trees are commonly used in data mining, machine learning, and artificial intelligence for classification and regression tasks.

or

A decision tree is a supervised learning algorithm used for both classification and regression tasks. It’s a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.

8. Define binary search.

Binary Search is an efficient algorithm used to find the position of a specific element in a sorted array or list. It operates on the principle of divide-and-conquer, repeatedly dividing the search interval in half until the target value is found or the interval is empty.

9. What is Dijkstras Algorithm?

Dijkstra’s algorithm is an algorithm used in graph theory to find the shortest path between vertices in a directed or weighted graph.

10. What is basic efficiency class? Name any two classes.

Basic efficiency class refers to categorizations of algorithms based on their time complexity and space complexity. These classes help identify how the performance of algorithms changes in relation to the size of the input data. By classifying algorithms into basic efficiency classes.

Two Basic Efficiency Classes

  1. Constant Time Complexity (O(1)).

  2. Linear Time Complexity (O(n)).

11. Define greedy method? Mention any one application of it.

The greedy method is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or the optimal solution at the moment.

12. What is NP class problem?

NP class (Non-deterministic Polynomial time) refers to a set of decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine.

Section - B

Answer any FOUR from the following questions. Each question carries 5 marks.(4*5=20)

13. Explain characteristics of Algorithm.
  1. Input: There are zero or more quantities, which are externally supplied.
  2. Output: At least one quantity is produced..
  3. Definiteness: Each instruction must be clear and unambiguous.
  4. Finiteness: If we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps;
  5. Effectiveness: Every instruction must be basic so that it can be carried out by a person using only pencil and paper.
14. Explain (theta ), big ‘O’, @ (omega) Notations with examples.

1. Big O Notation:

Big O notation represents the upper bound on worst-case Scenario of the growth rate of a function on the resource usage of an algorithm.

Big O Notation

2. Omega Notation:

Omega notation represent the lower bound as best case scenario of the growth rate of a function or the recourse usage of an algorithms.

Omega Notation

3. Theta Notation:

It represents both upper & lower bounds of the growth rate of a function or the resource usage of an algorithm.

Theta Notation
15. Write algorithm for quick sort.

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

Algorithm:

QUICKSORT (array A, start, end)
{
  if (start < end)
 {
  p = partition(A, start, end)
  QUICKSORT (A, start, p - 1)
  QUICKSORT (A, p + 1, end)
 }
}
PARTITION (array A, start, end) 
{
  pivot = A[end]
  i = start-1
  for j = start to end -1 do
  {
   if (A[j] < pivot) 
  {
   then i = i + 1
   swap A[i] with A[j]
 }}
 swap A[i+1] with A[end]
 return i+1
}

Time Complexity 

  1. Best case – O(n*logn)
  2. Average case – O(n*logn)
  3. Worst case – O(n2)
16. Explain basic tree traversal techniques. Write algorithm for them.

1. In-order Traversal:

  • In in-order traversal, the nodes are visited in the following order: left child, root, right child.
  • This traversal technique is commonly used in binary search trees to retrieve data in sorted order.
Algorithm:
Inorder(node)
if node == NULL
return
Inorder(node.left)
print(node.data)
Inorder(node.right)

2. Pre-order Traversal:

  • Pre-order traversal visits the nodes in the following order: root, left child, right child.
  • This traversal method is useful for creating a copy of the tree or prefix expression evaluation.
Algorithm:
Preorder(node)
if node == NULL
return
print(node.data)
Preorder(node.left)
Preorder(node.right)

3. Post-order Traversal:

  • Post-order traversal involves visiting the nodes in the following order: left child, right child, root.
  • This traversal approach is often used in deleting a tree or evaluating postfix expressions.
Algorithm:
Postorder(node)
if node == NULL
return
Postorder(node.left)
Postorder(node.right)
print(node.data)
17. Write pseudocode for Dijkstra’s Algorithm. 
function Dijkstra_Algorithm(Graph, source_node)

  for each node N in Graph:
     distance[N] = INFINITY
     previous[N] = NULL
     If N != source_node, add N to Priority Queue G
  distance[source_node] = 0

  while G is NOT empty:
     Q = node in G with the least distance[]
     mark Q visited
  for each unvisited neighbor node N of Q:
           temporary_distance = distance[Q] +
       distance_between(Q, N)
       if temporary_distance < distance[N]
  distance[N] := temporary_distance
  previous[N] := Q

// returning the final list of distance
return distance[], previous[]

Section - C

Answer any TWO of the following questions. Each question carries 10 marks. (2x10=20)

or
18. Explain Brute force method Mention its Applications. Solve selection sort for the Following Numbers 9,1,8,2,7,3,6,4,5

Brute force is an intuitive, direct, and straight forward technique of problem-solving in which all the possible ways or all the possible solutions to a given problem are enumerated.

Applications:

  • Search Problems
  • Password cracking
  • Traveling Salesman Problem
  • Knapsack Problem

Selection sort for the given numbers:

def selection_sort(arr):
 n = len(arr)
  for i in range(n):
   min_idx = i
  for j in range(i+1, n):
   if arr[min_idx] > arr[j]:
     min_idx = j
     arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Given numbers
numbers = [9, 1, 8, 2, 7, 3, 6, 4, 5]

# Apply selection sort
selection_sort(numbers)

print("Sorted array:")
print(numbers)

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
a) Explain travelling salesman problem. (5)

Path

a –> b –> c –> c –> a
a –> b –> c –> d –> a

a –> c –> d –> b –> a
a –> c –> b –> d –> a

a –> d –> c –> b –> a
a –> d –> b –> c –> a

Sum

3 + 4 + 2 + 6 = 15
3 + 9 + 2 + 8 = 22

6 + 4 + 2 + 8 = 15
6 + 9 + 4 + 8 = 27

8 + 2 + 9 + 3 = 22
8 + 4 + 9 + 6 = 27

Optimal minimum path is 15

The best optimal paths are:

a –> b –> d –> c –> a
a –> c –> d –> b –> a

or

The Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) is a classic and well-known computational problem in the field of optimization and algorithmic graph theory. It is a combinational optimization problem that seeks to find the shortest possible route that visits a set of given cities and returns to the original city.

Key Aspects:

  1. Objective:

    • The goal of the TSP is to find the shortest possible route that visits each city exactly once and returns to the original city.

  2. Combinatorial Nature:

    • The TSP is classed as an NP-hard problem, meaning that it is computationally infeasible to solve for large inputs using current algorithmic approaches.

  3. Applications:

    • TSP has wide-ranging practical applications such as vehicle routing, logistical planning, microchip fabrication, DNA sequencing, and network optimization.

  4. Complexity:

    • The number of possible solutions for the TSP grows factorially with the number of cities, resulting in a complex search space for finding the optimal route.

  5. Solution Approaches:

    • Various solution approaches are employed to address the TSP, including exact algorithms (such as dynamic programming and branch and bound) and approximate algorithms (such as genetic algorithms, simulated annealing, and ant colony optimization).

  6. Variants:

    • Variants of the TSP include the asymmetric TSP, in which the time or cost of travel between two cities can differ in each direction, and the TSP with time windows, where each city must be visited within a specified time window.

  7. Optimization:

    • TSP optimization aims to minimize the total distance traveled, although variants exist to minimize other factors such as time or costs.

  8. Significance:

    • Despite its computational complexity, the TSP remains a widely studied problem due to its real-world relevance and its representation of a fundamental class of optimization problems.
b) Discuss knapsack problem using greedy method. (5)

The Knapsack Problem is a classic optimization problem that deals with selecting a subset of items to maximize the total value while staying within a specified weight capacity. The problem can be divided into

Two main types:

  1. 0/1 Knapsack Problem: Each item can either be included in the knapsack or excluded (no fractions).

  2. Fractional Knapsack Problem: Items can be broken into smaller pieces; you can take any fraction of an item.

The greedy method is particularly effective for the Fractional Knapsack Problem because it allows for straightforward optimization by maximizing the value-to-weight ratio.

Problem Statement

Given:

  • A knapsack that can carry a maximum weight W.

  • A list of n items, each with a weight wi and value vi.

The goal is to maximize the total value in the knapsack without exceeding the weight limit W.

Greedy Strategy

The greedy approach for the Fractional Knapsack Problem involves the following steps:

  1. Calculate Value-to-Weight Ratio: For each item, compute the ratio viwi, which represents the value gained per unit of weight.

  2. Sort Items: Sort all items in descending order based on their value-to-weight ratio. This prioritizes selecting items that provide the most value for each unit of weight.

  3. Select Items:

    • Start with a total weight of 0 and total value of 0.

    • Iterate through the sorted list of items:

      • If the current item’s weight can fit in the knapsack without exceeding the capacity W, add the entire item to the knapsack (update total value and weight).

      • If the current item’s weight exceeds the remaining capacity, take the fraction of the item that fits into the knapsack (update total value accordingly) and terminate since the knapsack is now full.

function fractionalKnapsack(items, W):
// items is an array of tuples (value, weight)
// W is the maximum weight of the knapsack
totalValue = 0
// Calculate value-to-weight ratio and sort the items
for each item in items:
 item.ratio = item.value / item.weight

// Sort items by value-to-weight ratio in descending order
 items.sort(by descending item.ratio)

for each item in items:
 if W == 0:
 break // Knapsack is full

if item.weight <= W:
 W -= item.weight
 totalValue += item.value
else:
 totalValue += item.ratio * W // Take the fraction
 W = 0 // Knapsack is now full

return totalValue
a) Explain divide-and-conquer. Write pseudocode (5)

Divide and Conquer is a powerful algorithmic paradigm commonly used in computer science for solving complex problems by breaking them down into smaller, more manageable subproblems. The basic idea is to solve each of these subproblems independently, combining their solutions to form a solution to the original problem. 

Key Steps in Divide and Conquer:

  1. Divide: Break the problem into smaller subproblems. These subproblems should ideally be of the same type as the original problem but smaller in size.

  2. Conquer: Solve each of the subproblems independently, typically using the same divide and conquer strategy. If the subproblem size is small enough, solve the problem directly.

  3. Combine: Merge the solutions of the subproblems to obtain the solution for the original problem.

Pseudocode:

divide_and_conquer(problem):
if problem is small enough:
return solution to the base case
else:
divide problem into smaller subproblems
solve each subproblem recursively
combine the solutions to the subproblems
return the combined solution
b) Explain Kruskal’s Algorithm with example. (5)

Kruskal’s Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph. It follows the greedy approach that finds an optimum solution at every stage instead of focusing on a global optimum.

How the Kruskal’s algorithm works?

  1. First, sort all the edges from low weight to high.
  2. Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be added creates a cycle, then reject the edge.
  3. Continue to add the edges until we reach all vertices, and a minimum spanning tree is created.

Algorithm:

Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.  
Step 2: Create a set E that contains all the edges of the graph.  
Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning  
Step 4: Remove an edge from E with minimum weight  
Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F   
(for combining two trees into one tree).  
  ELSE  
  Discard the edge  
Step 6: END  
Example:

Now, let’s see the working of Kruskal’s algorithm using an example. It will be easier to understand Kruskal’s algorithm using an example.

Kruskal's Algorithm

The weight of the edges of the above graph is given in the below table –

EdgeABACADAEBCCDDE
Weight17105342

Now, sort the edges given above in the ascending order of their weights.

EdgeABDEBCCDAEACAD
Weight12345710

Now, let’s start constructing the minimum spanning tree.

Step 1 – First, add the edge AB with weight 1 to the MST.

Kruskal's Algorithm

Step 2 – Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Kruskal's Algorithm

Step 3 – Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Kruskal's Algorithm

Step 4 – Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Kruskal's Algorithm

Step 5 – After that, pick the edge AE with weight 5. Including this edge will create the cycle, so discard it.

Step 6 – Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.

Step 7 – Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal’s algorithm is –

Kruskal's Algorithm

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Now, the number of edges in the above tree equals the number of vertices minus 1. So, the algorithm stops here.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    error: Content is protected !!