DAA (Design & Analysis of Algorithms) 2 Marks Questions with Answers

DAA (NEP & CBCS) Questions with Answers

2 Marks (Important)

1. What is an algorithm?

An algorithm is a set of instructions that a computer follows to solve a problem. Algorithms can tell a computer how to process data, perform calculations, or make decisions.

2. Define Space 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.

3. List of various algorithm design strategies.

Greedy
Backtracking
Brute force
Randomized
Recursion
Divide and conquer
Dynamic programming
Branch and bound
Approximation
Iteration

4. What is performance measurement?

Performance measurement is generally defined as regular measurement of outcomes and results, which generates reliable data on the effectiveness and efficiency of programs.

5. List out algorithm techniques.

Brute-Force Search
Divide and Conquer
Dynamic Programming
Greedy Algorithms
Backtracking
Branch and Bound
Randomized Algorithms
Bitwise Algorithms
Approximation Algorithms

6. What is best-case complexity?

The complexity of an algorithm is the amount of time and space it needs to solve a problem.

7. Define order of an algorithm.

The order of an algorithm is a measure of its efficiency, especially in the worst-case scenario. It depends on the nature and size of the inputs.

8. What is an b-spaced array.

A b-spaced array is an array in which the elements are spaced b elements apart. For example, an array with the elements 1, 3, 5, 7 is a 2-spaced array.

9. What is an optimal solution.

an optimal solution refers to the most desirable outcome of a decision-making process. In DAA (Data Analytics and AI), this can be achieved through the use of optimization techniques such as linear programming, integer programming, and dynamic programming.

10.Write how to analyze the performance of an algorithm.

Time Complexity Analysis
Space Complexity Analysis
Worst, Average, and Best Case Analysis
Asymptotic Analysis
Empirical Performance Evaluation:
Benchmarking
Scalability Assessment
Trade-off Analysis

11. Define recursive algorithm.

A recursive algorithm is a type of algorithm that calls itself with smaller input values. It returns the result for the current input by performing basic operations on the returned value for the smaller input.

12. Define non recursive algorithm.

A non-recursive algorithm is a method of solving a problem or achieving a task that does not rely on calling itself repeatedly, as opposed to a recursive algorithm. Instead, the algorithm must proceed through the problem by working with a stack of local data, using loops and if/else statements to accomplish the desired outcome.

13. Define asymptotic notations.

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 (Ω).

14. Define mathematical analysis of an algorithm.

mathematical analysis of an algorithm is the process of evaluating and understanding the algorithm’s performance characteristics and efficiency. It involves studying how the algorithm’s space requirements and running time grow as the input size increases.

15. What is travelling sales person problem?

Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

16. Which data structure is used for implementing BFS traversal?

Breadth-First Search uses a queue data structure technique to store the vertices.

17. What is knapsack problem?

In the knapsack problem, you need to pack a set of items, with given values and sizes (such as weights or volumes), into a container with a maximum capacity . If the total size of the items exceeds the capacity, you can’t pack them all.

18. Give the time complexity and space complexity of TSP.

Time complexity: O(N^2*logN), Where N is the number of cities.
Space complexity: O(N).
O(n! n): where n is the number of cities, n! possible permutations of the cities.
O(N): it only requires storage for the permutations and the distances between the
cities.

19. What are the constraints for knapsack problem.

Load balance, Vertical stability, Fragility of items, Volume limit, Weight limit.

20. Write linear search algorithm.

def linear_search(arr, target): 
 for i in range(len(arr)): 
  if arr[i] == target: 
   return i 
return -1

21. Differentiate between DFS and BFS.

BFS	DFS
BFS stands for Breadth First Search.	DFS stands for Depth First Search.
BFS(Breadth First Search) uses Queue data structure for finding the shortest path.	DFS(Depth First Search) uses Stack data structure.
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.	DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
BFS builds the tree level by level.	DFS builds the tree sub-tree by subtree.
It works on the concept of FIFO (First In First Out).	It works on the concept of LIFO (Last In First Out).
BFS is more suitable for searching vertices closer to the given source.	DFS is more suitable when there are solutions away from source.
BFS is used in various applications such as bipartite graphs, shortest paths, etc.	DFS is used in various applications such as acyclic graphs and finding strongly connected components etc.

22. Write the complexity of merge sort.

The time complexity of merge sort is O(n log n) in all three cases
The space complexity of merge sort is O(n) in the worst case

23. Write the time and space complexity of quicksort

The space complexity of quick sort is O(log n)
The time complexity of quick sort is O(n log n)

24. Write the time and space complexity of binary search

The time complexity of binary search is O(log n).
space complexity is O(1).

25. Write the time and space complexity of sequential search

The time complexity is O(n)
The space complexity is O(1)

26. Quicksort is more efficient than merge sort. Judge your answer.

Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets. whereas Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets

27. Write down the control abstraction for divide and conquer.

The control abstraction for divide and conquer in DAA is DANDC(P), where P is the problem to be solved. The algorithm works by recursively dividing the problem into smaller subproblems, solving each subproblem, and then combining the solutions to the subproblems to solve the original problem.

28. Illustrate the tree structure of merge sort algorithm of 10 elements.

 [5, 2, 9, 1, 5, 6, 3, 6, 7, 8]
       /              \
[5, 2, 9, 1, 5] [6, 3, 6, 7, 8]
    /   \              /  \
[5, 2] [9, 1, 5] [6, 3] [6, 7, 8]
 /  \      /  \      / \     / \
[5] [2] [9] [1, 5] [6] [3] [6] [7] [8]
 /   \     /    /   \
[1] [5] - [3] [6] [7, 8] (For Example)

29. List any four examples of problems using Divide and Conquer

Binary Search is a searching algorithm.
Quicksort is a sorting algorithm.
Merge Sort is also a sorting algorithm.
Maximal Subarray Problem
Fast Fourier Transform (FFT)

30. State the average case and worst case complexity of quicksort.

Time complexity	Description
O(n log n)	Average case
O(n^2)	Worst case
O(n log n)	Best case

31. Write the complexity of a) Selection sort b) Merge sort

Selection Sort:

Time Complexity:

Worst Case: O(n^2)
Average Case: O(n^2)
Best Case: O(n)

Space Complexity: O(1)

Mergesort:

Time Complexity:

Worst Case: O(n log n)
Average Case: O(n log n)
Best Case: O(n log n)

Space Complexity: O(n)

32. Define divide and conquer method.

The divide and conquer method is a strategy for solving problems by breaking them down into smaller pieces, solving the pieces, and then combining the solutions into a global solution.

33. Write the time complexity of binary search algorithm.

The time complexity of binary search is O(log n)
The space complexity of binary search is O(1)

34. Write the time complexity of binary search algorithm.

The time complexity of binary search is O(log n)
The space complexity of binary search is O(1)

35. Define Kruskal's algorithm.

Kruskal’s algorithm is a popular algorithm used in data structures and algorithms (DAA) for finding the minimum weight spanning tree of a connected, undirected graph. It is a greedy algorithm, meaning that it makes the locally optimal choice at each step, with the goal of finding the globally optimal solution.

36. Define Dikstra’s algorithm.

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

37. Define the use of greedy technique.

Greedy technique in DAA refers to a type of algorithm that solves problems by making locally optimal choices at each step, with the hope of finding a global optimum. In the context of DAA (Data Warehousing and OLAP), greedy techniques are used for query optimization, data aggregation, and indexing.

38. Define 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.

39. What is DFS and BFS method used in Graph technique ?

DFS: Explores as deeply as possible along one path before Uses a stack for exploration. Good for finding all possible paths.
BFS: Explores all neighbors at the current level before moving to the next Uses a queue for exploration. Good for finding the shortest path.

40. What are implicit and explicit methods ?

Implicit: Data structures implicitly represent the algorithm’s (e.g., stacks and queues in DFS/BFS)
Explicit: Code explicitly defines the algorithm’s (e.g., loops and conditional statements)

41. Define Greedy with example.

Makes locally optimal choices at each step with the hope of finding a global
Example: Dijkstra’s algorithm for finding shortest

42. Define tree traversal. Mention tree traversal techniques.

Visiting tree nodes in a specific order.
Techniques: In-order, Pre-Order, Post-Order (for binary trees), Level-order (BFS)

43. Differentiate Prim’s and Kruskal’s Algorithm.

Both find Minimum Spanning Trees (MSTs).

Prim’s: Starts with a node and expands by adding the cheapest edge to unvisited
Kruskal’s: Sorts edges by weight, adds them to create a forest, stops when all nodes are

44. What are the criteria to judge an Algorithm ?

Correctness: Produces the right output for all valid
Efficiency: Time and space
Readability: Easy to understand and
Maintainability: Easy to fix and

45. What are the three cases of problem to be tested while analyzing algorithm ?

Best case, Average case, Worst case, Boundary conditions, Error case.

46. Define live node and dead node.

Live: Can be explored further (DFS).
Dead: No unexplored neighbors (DFS).

47. Define feasible solution and optimal solution.

Feasible: Satisfies all problem
Optimal: Best possible solution among all feasible

48. State the pre condition for list of numbers, if binary search is to be carried out.

List must be sorted in ascending or descending

49. Write Best, Average, and Worst Case Time Complexity of Binary search for successful search.

Best: O(1) (if element is in the middle)
Average: O(log n)
Worst: O(log n) (if element is not present)

50. What is minimum Cost Spanning Tree?

A subgraph connecting all nodes with the minimum total edge
a minimum cost spanning tree of a connected graph with weighted edges is the tree that connects all vertices of the graph while ensuring that the total cost of all edges is the smallest possible

51. What do you mean by “Principle of optimality” w.r.t. Dynamic programming

Optimal solution to a problem can be constructed from optimal solutions to its
We divide a problem into smaller nested subproblems, and then combine the solutions to reach an overall solution.

52. List the Tree Traversal orders and Graph Search and Traversal Methods

Tree Traversal: In-order, Pre-order, Post-order, Level-order (BFS)
Graph Traversal: Depth-first search, Breadth-first search

53. Define a process framework.

A structured approach for defining and developing Process frameworks are reference models that support the description, assessment, and optimization of business processes

54. List any 4 characteristics of a good design.

Correctness: Meets requirements and
Efficiency: Uses resources
Readability: Easy to understand and
Flexibility: Adaptable to

55. Write the complexity of merge sort.

Time: O(n log n)
Space: O(n)

56. What you meant by Dynamic programming with Examples?

Solves problems by breaking them into subproblems and storing results to avoid redundant calculations.
Example: Fibonacci sequence, longest common

57. Write Bellman and Ford algorithm to compute the shortest paths.

Computes shortest paths in graphs with negative edge

58. What is travelling sales person problem?

The Traveling Salesman Problem (TSP) is a complex algorithmic problem that involves finding the shortest route for a salesperson to take. The problem involves finding the shortest path that visits a set of vertices and returns to the first.

59. Which data structure is used for implementing BFS traversal?