What is an algorithm? What is the need for an algorithm?

An algorithm is a well-defined computational procedure that takes some values or the set of
values, as an input and produces a set of values or some values, as an output.
What is the Complexity of Algorithm?
The complexity of the algorithm is a way to classify how efficient an algorithm is compared
to alternative ones. Its focus is on how execution time increases with the data set to be
processed. The computational complexity of the algorithm is important in computing.
It is very suitable to classify algorithm based on the relative amount of time or relative
amount of space they required and specify the growth of time/ space requirement as a
function of input size.
Time complexity
Time complexity is a Running time of a program as a function of the size of the input.
Space complexity
Space complexity analyzes the algorithms, based on how much space an algorithm needs to
complete its task. Space complexity analysis was critical in the early days of computing
(when storage space on the computer was limited).
Nowadays, the problem of space rarely occurs because space on the computer is broadly
enough.
We achieve the following types of analysis for complexity
Worst-case: f(n)
It is defined by the maximum number of steps taken on any instance of size n.
Best-case: f(n)
It is defined by the minimum number of steps taken on any instance of size n
Average-case: f(n)
It is defined by the average number of steps taken on any instance of size n.
5) What are the Asymptotic Notations?
Asymptotic analysis is used to measure the efficiency of an algorithm that doesn't depend on
machine-specific constants and prevents the algorithm from comparing the time taking
algorithm. Asymptotic notation is a mathematical tool that is used to represent the time
complexity of algorithms for asymptotic analysis.
The three most used asymptotic notation is as follows.
θ Notation
θ Notation defines the exact asymptotic behavior. To define a behavior, it bounds functions
from above and below. A convenient way to get Theta notation of an expression is to drop
low order terms and ignore leading constants.
The Big O notation bounds a function from above, it defines an upper bound of an algorithm.
Let's consider the case of insertion sort; it takes linear time in the best case and quadratic time
in the worst case. The time complexity of insertion sort is O(n2). It is useful when we only
have upper bound on time complexity of an algorithm.

Ω Notation

Just like Big O notation provides an asymptotic upper bound, the Ω Notation provides an
asymptotic lower bound on a function. It is useful when we have lower bound on time
complexity of an algorithm.

5. What are algorithm design techniques?

Algorithm design techniques ( or strategies or paradigms) are general approaches
to solving problems algorithmatically, applicable to a variety of problems from different
areas of computing. General design techniques are:
(i) Brute force (ii) divide and conquer
(iii) decrease and conquer (iv) transform and concquer
(v) greedy technique (vi) dynamic programming
(vii) backtracking (viii) branch and bound

. What are the characteristics of an algorithm?

Every algorithm should have the following five characteristics
(i) Input
(ii) Output
(iii) Definiteness
(iv) Effectiveness
(v) Termination
Therefore, an algorithm can be defined as a sequence of definite and effective
instructions, which terminates with the production of correct output from the given input.
In other words, viewed little more formally, an algorithm is a step by step formalization
of a mapping function to map input set onto an output set
39. Define the divide an conquer method.
Given a function to compute on ‘n’ inputs the divide-and-comquer strategy
suggests splitting the inputs in to’k’ distinct susbsets, 1<k <n, yielding ‘k’ subproblems.
The subproblems must be solved, and then a method must be found to combine
subsolutions into a solution of the whole. If the subproblems are still relatively large, then
the divide-and conquer strategy can possibly be reapplied.
What is the binary search?
If ‘q’ is always chosen such that ‘aq’ is the middle element(that is, q=[(n+1)/2),
then the resulting search algorithm is known as binary search.
. What is the maximum and minimum problem?
The problem is to find the maximum and minimum items in a set of ‘n’ elements. Though
this problem may look so simple as to be contrived, it allows us to demonstrate
divideand-conquer in simple setting.
48. What is the Quick sort?
Quicksort is divide and conquer strategy that works by partitioning it’s input
elements according to their value relative to some preselected element(pivot). it uses
recursion and the method is also called partition –exchange sort.
Explain the greedy method.
Greedy method is the most important design technique, which makes a choice that
looks best at that moment. A given ‘n’ inputs are required us to obtain a subset that
satisfies some constraints that is the feasible solution. A greedy method suggests that
one can device an algorithm that works in stages considering one input at a time.
. What is a minimum cost spanning tree?
A spanning tree of a connected graph is its connected acyclic subgraph that
contains all vertices of a graph. A minimum spanning tree of a weighted
connected graph is its spanning tree of the smallest weight where bweight of the
tree is the sum of weights on all its edges.
A minimum spanning subtree of a weighted graph (G,w) is a spanning subtree of
G of minimum weight w(T )= Σ w(e )
e€ T
Minimum Spanning Subtree Problem: Given a weighted connected undirected graph
(G,w), find a minimum spanning subtree

6. Specify the algorithms used for constructing Minimum cost spanning tree.
a) Prim’s Algorithm
b) Kruskal’s Algorithm

What is the order of growth in DAA?

The order of growth of an algorithm provides a rough estimate of the amount of time needed
to execute a computer program as the size of the input variable increases. The order of
growth does not take into account the constant factor that is required for fixed operations.
Instead, it emphasizes the operations that expand in proportion to the input size.

25. What is the Importance of Algorithms?

An algorithm is merely a procedure for accomplishing a goal. Computers, smartphones, and

websites can't perform their tasks or make decisions without them; they're the foundation of
programming. Many of the activities we engage in daily are, like algorithms, used by
technology.

26. Explain the Bubble sort algorithms.

Bubble sorting involves splitting the list into two parts. They are sorted and unsorted. The
smallest item in a sublist that hasn't been sorted is "bubbled." When the smallest piece of the
wall is shifted, the entire wall shifts forward one space. The idea behind bubble sort was to
highlight the item at the top of the list in a giant bubble. It does not matter if the highest or
lowest item is bubbled. In this variant, two adjacent components are switched around based
on a comparison. Since bubble sort performs a full array check, sorting a record with n
elements can take up to n-1 iterations.

27. Explain the Quick sort algorithms.

The Quicksort algorithm relies on division to sort the data. The term "partition exchange
sorting" is also used to refer to this technique in some contexts. The quick sort algorithm
involves picking one item from an array and then rearranging the rest of the data so that it
revolves around that item. This item caused the initial list to be divided in half. The "pivot" is
the currently chosen option. Any items whose values are less than the pivot are shifted to the
left, and those whose values are more significant than the pivot are shifted to the right when
the pivot is selected. Until sub-lists containing only one item are found, selecting a pivot and
dividing the list is repeated in a while loop.

28. What is DAA Programming?

Data Access Arrangements (DAAs) connect a computer and modem to a public telephone
network. DAAs, called TLICs, are telephony line interface circuits (or Modules).

29. What exactly is NP-Complete?

Any other NP problem can be simplified to an NP-Complete problem in a polynomial amount

of time, which means that an NP-Complete problem is just as tricky as any other problem in
this category.

30. What is the Knapsack Problem in DAA?

The DAA knapsack problem is challenging in combinatorial optimization. Given a set of

items with weights and values, find the optimal number of each item to include in the
collection such that the sum of the weights is as tiny as possible and the sum of the values is
as large as possible.

32. What exactly is Binary Search?

Binary search is superior to linear search. On a non-sorted data structure, however, it cannot
be tested. The basis of binary search is the divide-and-conquer tactic. The binary search starts
by testing the central element of the array's data. Doing this can determine whether a specific
event or piece of information occurs in the first or second half. We do not need to check the
second half if the object is found in the first half and vice versa if it is discovered in the
second half.

33. Explain the Insertion Sort algorithms.

In both selection and bubble sorts, items are interchanged. In contrast, insertion sort does not
exchange items. Like card insertion, the item is inserted into the insertion sort at the
appropriate location.

State single source shortest path algorithm (Dijkstra’s algorithm).

For a given vertex called the source in a weigted connected
graph,find shotrtest paths to all its other vertices.Dijikstra’s algorithm applies to
graph with non-negative weights only.
8. What is Knapsack problem?
A bag or sack is given capacity and n objects are given. Each object has weight
wi and
profit pi .Fraction of object is considered as xi (i.e) 0<=xi<=1 .If fraction is 1 then
entire object is put into sack. When we place this fraction into the sack we get wixi
and pixi.

9. Write any two characteristics of Greedy Algorithm?

* To solve a problem in an optimal way construct the solution from given set of
candidates.
* As the algorithm proceeds, two other sets get accumulated among this one set
contains
the candidates that have been already considered and chosen while the other set
contains
the candidates that have been considered but rejected.
10. What is the Greedy approach?
The method suggests constructing solution through sequence of steps,each
expanding partially constructed solution obtained so far,until a complete solution is
reached. On each step,the choice must be
• Feasible(satisfy problem constraints)
• Locally optimal(best local choice among all feasible choices available on that
step)
• Irrevocable(once made,it cant be changed)
11. What are the steps required to develop a greedy algorithm?
* Determine the optimal substructure of the problem.
* Develop a recursive solution.
* Prove that at any stage of recursion one of the optimal choices is greedy choice.
Thus it is always safe to make greedy choice.
* Show that all but one of the sub problems induced by having made the greedy
choice are empty.
* Develop a recursive algorithm and convert into iterative algorithm.
13. Define forest.
Collection of sub trees that are obtained when root node is eliminated is known as
forest
14. Write the difference between the Greedy method and Dynamic programming.
Greedy method Dynamic programming
Only one sequence of decision is
generated.
Many number of decisions are generated.
It does not guarantee to give an
optimal solution always.
It definitely gives an optimal solution
always.
15.state the requirement in optimal storage problem in tapes.
Finding a permutation for the n programs so that when they are stored on the tape in
this order the MRT is minimized.This problem fits the ordering paradigm.
16. state efficiency of prim’s algorithm.
O(|v|2) (WEIGHT MATRIX AND PRIORITY QUEUE AS UNORDERED ARRAY)
O(|E| LOG|V|) (ADJACENCY LIST AND PRIORITY QUEUE AS MIN-HEAP)
17. State Kruskal Algorithm.
The algorithm looks at a MST for a weighted connected graph as an acyclic subgraph
with |v|-1 edges for which the sum of edge weights is the smallest.
18. state efficiency of Dijkstra’s algorithm.