DAA LAB VIVA BY:HEENA YASMIN (ASST.

PROFESSOR)

1) What is Algorithm?

The name 'Algorithm' refers to the sequence of instruction that must be followed to clarify a
problem.

The logical description of the instructions which may be executed to perform an essential
function.

Algorithms are usually generated independent of primary languages, i.e., an algorithm can be
achieved in more than one programming language.

2) What is Asymptotic Notation?

A way to represents the behavior of functions in the limit or without bounds.

The notations are described in terms of methods whose domains are the set of natural numbers
N= {0, 1, 2}

Such notations are convenient for defining the worst-case running time function T(n).

It can also be extended to the domain of the real number.

3) What is the time complexity of Algorithm?

The time complexity of an algorithm denoted the total time needed by the program to run to
completion. It is generally expressed by using the big O notation.

6) Explain the algorithms for QUICK sort (partition exchange sort) and give a suitable example.

Quicksort is based on division. It is also called a partition exchange sorting. The basic concept of
quick sort method is to pick one item from an array and rearranges the remaining item around it.
This element split the main list into two sublists. This chosen item is known as a pivot. Once the
pivot is selected, then it shifts all the components less than pivot to the left of value pivot, and all
the items higher than the pivot are shifted to the right side. This process of choosing pivot and
division the list is tested recursively until sub-lists consisting of only one element.

7) What is NP-Complete?

An NP-Complete problem is a problem in NP that is as difficult as any other trouble in this class
because any other dispute in NP can be decreased to it in Polynomial-time.

8) Differentiate Time Efficiency and Space Efficiency?

Time Efficiency measured by estimate the number of times the essential algorithms functions are
executed. Space Efficiency is measured by calculating the number of additional memory units
consumed by the algorithm.
1
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

9) What is Brute Force?

Brute Force is a straightforward method for solving problem, usually directly based on the
problem's statement and descriptions of the concepts involved.

10)What are the various criteria used to improve the effectiveness of the algorithm?

Input- Zero or more quantities are externally provided.

Output- At least one quantity is composed

Definiteness- Each instruction is simple and unambiguous

Finiteness- If we trace out the instructions of an algorithm, then for all step the algorithm
complete after a finite number of steps

Effectiveness- Every instruction must be elementary.

11) Explain the algorithms for Merge sort and give a suitable example.

The basic concept of merge sort has split the list into two smaller sub-lists of relatively equal
size. Recursively repeat this method until only one item is left in the sub-list. After this, various
sorted sub-lists are combined to form a sorted parent list. This method goes on recursively till the
original sorted list arrived.

12)What is Dynamic Programming?

DP is another method for problems with optimal substructure: An optimal solution to a problem
include optimal solutions to subproblems. This doesn't necessarily define that every optimal
solution to a subproblem will contribute to the primary solution.

For divide and conquer (top-down), the subproblems are independent, so we can resolve them
in any order.

For the greedy technique (bottom-up), we can always choose the "right" subproblem by a
greedy choice.

In dynamic programming, we solve many subproblems and save the results: not all of them
will contribute to solving the bigger problem. Because of optimal substructure, we can be sure
that at least some of the subproblems will be useful.

13) What is the Knapsack Problem?

2
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

Given n elements of known weights wiand values vi, i=1, 2? n, and a knapsack of capacity W,
find the most valuable subsets of the elements that fit the knapsack. It is convenient to order the

elements of a given instance in descending order by their value-to-weight ratios. Then the first
element gives the best payoff per weight unit, and the last one gives the worst payoff per weight
unit.

14) What is Warshall's Algorithm?

Warshall's algorithm is a function of dynamic programming procedure, which is used to find the
transitive closure of a directed graph.

15) What is a Greedy Algorithm?

A greedy technique for an optimization problem always makes the option which look best at the
moment and add it to the current subsolution.

16) List the advantage of the greedy algorithm.

1. The greedy method produces a feasible solution

2. The greedy method is very easy to solve a problem

3. The greedy method implements an optimal solution directly

17. What is Minimum Spanning Trees?

A spanning tree for a linked graph is a tree whose vertex set is the same as the vertex set of the
given graph, and whose edge set is a subgroup of the edge set of the given graph. i.e., any linked
graph will have a spanning tree.

Weight of a spanning tree w (T) is the total of weights of all edges in T. The Minimum spanning
tree (MST) is a spanning tree with the smallest feasible weight.

18. What is Kruskal?s Algorithm?

This is a greedy method. A greedy method chooses some local optimum (i.e., selection an edge
with the smallest weight in an MST).

Kruskal's algorithm works as follows:

Take a graph with 'n' vertices, keep on adding the shortest (least cost) edge, while avoiding the
generation of cycles, until (n - 1) edges have been added. Frequently two or more edges may
have the same rate. The order in which the edges are decided, in this method, does not matter.

3
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

Different Minimum spanning tree may result, but they will all have the same total price, which
will always be the minimum cost.

19. What is Floyd's algorithm?

Floyd's algorithm is a function, which is used to find all the pairs shortest paths problem. Floyd's
algorithm is relevant to both directed and undirected weighted graph, but they do not include a
cycle of a negative length.

20) What is prim's algorithm?

Prim's algorithm is a greedy and efficient technique, which is used to find the minimum spanning
the tree of a weighted linked graph.

21) How efficient is prim's algorithm?

The efficiency of the prim's methods depends on the data structure chosen for the graph.

22)What is Dijkstra's Algorithm?

Dijkstra's algorithm solves the single-source shortest path method of finding shortest paths from
a given vertex (the source), to another vertex of a weighted graph or digraph. Dijkstra's algorithm
implements a correct solution for a graph with non-negative weights.

23) What are the huffman trees?

A Huffman tree is a binary tree which reduces the weighted path length from the root to the
leaves, including a set of predefined weights. The essential application of Huffman trees is a
Huffman code.

24) What do you mean by Huffman code?

A Huffman code is an optimal prefix tree variable-length encoding technique which assign bit
strings to characters based on their frequency in a given text.

25) List the advantage of Huffman's encoding?

Huffman's encoding is one of the essential file compression techniques.

1. It is easy

2. It is flexibility

3. It implements optimal and minimum length encoding

4
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

26) What is dynamic Huffman coding?

In dynamic Huffman coding, the coding tree is updated each time a new character is read from
the source text. Dynamic Huffman n-coding used to overcome the disadvantage of the simplest
version.

27) What is backtracking?

Depth-first node generation with bounding method is known as backtracking. The backtracking
technique has its virtue the ability to yield the solution with far fewer than m trials.
28) Write the difference between the Dynamic programming and Greedy method.
Dynamic programming
1. Many numbers of decisions are generated.
2. It gives an optimal solution always
Greedy method
1. Only one sequence of decision is generated.
2. It does not require to provide an optimal solution always.

29) What is the use of Dijkstra's algorithm?

Dijkstra's procedure is used to solve the single-source shortest-paths method: for a given vertex
called the source in a weighted linked graph, find the shortest path to all its other vertices. The
single-source shortest-paths process asks for a family of paths, each leading from the source to
various vertex in the graph, though some direction may have edges in common.

30) What is meant by n-queen Problem?

The problem is to area n-queens on an n-by-n chessboard so that no two queens charge each
other by being same row or in the same column or the same diagonal.

31) What is the state-space tree?

The processing of backtracking is resolved by constructing a tree of choices being made. This is
known as state-space tree. Its root describes an initial state before the search for a solution starts.
The nodes of the first level in the tree describe the choices made for the first element of the
solution, the nodes in the second level describe the choices for the second element, and so on.
32)Name the five properties that need to be followed before writing an algorithm?
An algorithm must take input and output, be finite, definite, effective, and general

33).What determines an algorithm’s effectiveness?

An algorithm’s effectiveness is determined by its ability to contain only necessary steps and
work with input data. It should transfer any type of input or data.
34. Define time complexity and how is it calculated?
Time complexity is the time required for an algorithm’s execution. It can be calculated using
frequency count (step count) or asymptotic notations. Two components of time complexity are
the capacity of the system and the computer containing single or multiple processors.
35.What is space complexity and how is it calculated?
Space complexity is the amount of space an algorithm requires for its execution. It can be
calculated using the formula S of P = C plus S P, where C is a constant and S P is the space
complexity of the program.
5
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

36. What is the difference between time complexity and space complexity?
Time complexity measures the time required for an algorithm’s execution, while space
complexity measures the amount of space required for its execution.

37. Point out the difference between big-go and big omega notation?
Big-go notation represents the upper bound of an algorithm, while big omega notation represents
the lower bound of an algorithm

38.Why is Merge sort preferred over Quick Sort for sorting linked lists?
Answer: Merge Sort is preferred for sorting linked lists because its divide-and-conquer
approach easily divides the list into halves and merges them efficiently without requiring
random access, which is difficult in linked lists. Quick Sort’s reliance on random access and
potential worst-case time complexity makes it less suitable for linked lists.

39.What is the best sorting algorithm for large datasets?

Answer: For large datasets, efficient sorting algorithms like Merge Sort, Quick Sort, or Heap
Sort are commonly used due to their average time complexity of O(n log n), which performs
well even with large amounts of data.

40.How does Quick Sort work?

Quick Sort is a Divide and Conquer sorting algorithm. It chooses a pivot element and
rearrange the array so that elements smaller than the pivot are on the left, and elements greater
are on the right. Then, recursively apply the partitioning process to the left and right
subarrays. Subarrays of size one or zero are considered sorted.

41. What is the worst-case time complexity of Quick Sort?

In the worst case, Quick Sort may take O(N^2) time to sort the array. The worst case will
occur when everytime the problem of size N, gets divided into 2 subproblems of size 1 and N
– 1.

42. What is Divide and Conquer Algorithm?

A divide-and-conquer algorithm is a problem-solving technique that follows these steps:
 Divide: Break the problem down into smaller, independent subproblems.
 Conquer: Solve each subproblem recursively.
 Combine: Merge the solutions to the subproblems to solve the original problem.
In Divide-and-conquer algorithms, the problem is divided into smaller and smaller
subproblems, which are then solved independently. Merge Sort, Quick Sort, Fast Fourier
Transform are some examples of Divide and Conquer Algorithms.

43. How would you use Divide & Conquer to find the maximum and minimum of an
array?
To find the maximum and minimum of an array using Divide & Conquer, we can recursively
divide the array into smaller sub arrays until we reach the base case with just one or two
elements, then compare the max and min within each sub array.

44. What is the role of recursion in Divide & Conquer algorithms?

6
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

Recursion plays a fundamental role in Divide & Conquer algorithms by breaking down a
problem into smaller sub problems and solving them separately, then combining their
solutions to solve the larger problem.

45. Can you give any common examples of the types of problems where the Divide &
Conquer approach might be used?

Divide & Conquer is often used in scenarios such as sorting algorithms (e.g., Merge Sort,
Quick Sort), finding the maximum sub array sum, matrix multiplication, and various
searching algorithms.

46. How does the efficiency of Divide and Conquer algorithms compare to other
problem-solving techniques?
Divide and Conquer algorithms often exhibit efficient performance, especially for large-scale
problems, but the efficiency depends on factors like problem characteristics and
implementation details.

47. How does the QuickSort algorithm utilize the Divide and Conquer strategy?
QuickSort selects a pivot, partitions the array, recursively sorts the partitions, and combines
them, showcasing the Divide and Conquer strategy.

48. What is Backtracking Algorithm?

Backtracking is an algorithmic technique for solving problems recursively by trying to build a
solution incrementally, one piece at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time

49 Why is this called Backtracking?

Backtracking is a problem-solving technique that involves constructing a solution
incrementally, and backtracking when a dead end is reached. It is often used to find all
possible solutions to a problem, or to find the best solution.
In backtracking, a solution is represented as a set of assignments to variables. The algorithm
starts by assigning a value to the first variable. It then recursively assigns values to the
remaining variables, until a complete solution is found.
If, at any point, the algorithm reaches a dead end (i.e., no valid assignment can be made to a
variable), it backtracks to the previous variable and tries a different assignment.

50. Explain what is Explicit and implicit Backtracking Constraints?

Explicit backtracking constraints are explicitly stated in the problem definition, while implicit
backtracking constraints must be inferred from the problem’s logic.
 Both types of constraints can be used to guide the backtracking search.
 Explicit constraints are typically easier to identify and enforce, while implicit constraints
may require more careful analysis.
 By using both explicit and implicit constraints, backtracking algorithms can efficiently
find solutions to complex problems.
51. What are the main challenges or limitations associated with Backtracking
algorithms?

7
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

Backtracking can be computationally expensive and may explore many paths, leading to
inefficiency, especially in problems with large solution spaces.
52. Can you discuss a situation where Backtracking might be more suitable than other
algorithms?
Backtracking is often suitable for problems with numerous possibilities, like solving puzzles
or optimization problems, where exploring all options is essential.

53.What is a graph, and how does it differ from a tree in data structures?
A graph is a collection of nodes connected by edges, allowing for more complex relationships.
Unlike a tree, a graph has no strict hierarchy or parent-child relationships.

54. Explain the concepts of a directed graph and an undirected graph.

In a directed graph, edges have a specific direction, indicating a one-way relationship. In an
undirected graph, edges have no direction, representing a mutual connection.

55. What is a cycle in a graph, and how do you detect cycles algorithmically?
A cycle is a closed path in a graph. Cycles can be detected using algorithms like Depth-First
Search (DFS) or Union-Find.

56. Describe the breadth-first search (BFS) algorithm for traversing a graph.
BFS starts at a source node, explores its neighbors, and then move to their neighbors level by
level, using a queue data structure.

57. How does depth-first search (DFS) work, and what are its applications in graph
algorithms?
DFS explores as far as possible along each branch before backtracking. It’s used for traversal,
topological sorting, and solving problems like connected components.

58. What is Dijkstra’s algorithm, and how does it find the shortest path in a weighted
graph?
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a
weighted graph by iteratively selecting the node with the minimum distance.

59. Explain the concept of a minimum spanning tree and how Kruskal’s algorithm
achieves it.
A minimum spanning tree is a tree that spans all nodes in a graph with the minimum possible
total edge weights. Kruskal’s algorithm adds edges in ascending order of weight, avoiding
cycles.
60. What is the difference between a graph and a digraph in terms of representation and
algorithms?
A graph can be directed (digraph) or undirected, while a digraph has edges with specific
directions. Algorithms for digraphs often differ due to the directed nature.

61) What is the traveling salesman problem?

The traveling salesman problem is a classic optimization problem in which a salesman must
visit a set of cities, each only once, and return to his starting point, while minimizing the total
distance traveled.

8
DAA LAB VIVA BY:HEENA YASMIN (ASST.PROFESSOR)

62) What is a weighted graph?

Answer: A weighted graph is a graph in which each edge has a weight or cost assigned to it,

indicating the cost or distance between the two vertices it connects.