# CSE SOLUTION SITE

Algorithm Design Question List | Solve

### (15).Backtracking algorithm.

Algorithm Design Question List | Solve

# What is an algorithm? Write down the characteristics of an algorithm

An algorithm :

An algorithm is a sequence of unambiguous instructions for solving a problem i.e, for obtaining a required input in a finite amount of time.

The characteristics of an algorithm :

Precision the steps are precisely stated(defined).

Uniqueness results of each step are uniquely definedand only depend on the input and the result of the precedingsteps.

Finiteness the algorithm stops after a finite number ofinstructions are executed.

Output the algorithm produces output.

Generality the algorithm applies to a set ofinputs.

# What do you mean by time complexity?

Time complexity :

The time complexity of an algorithm is the amount of computer time it needs to run to completion. The time T (P) taken by a program P is the sum of the compile time and the run (or execution) time. The compile does not depend on the instance characteristics. This run time is denoted bby tp(instance characteristics).

# Calculate the time complexity of the following algorithm:- Algorithm Add (a, b, c, m, n) { for i:=1 to m do for j:=1 to n do c[i,j]=a[i,j]+b[i,j]; }

The expression tp(n) is as follows-

tp(n) = caADD (n) +csSUB (n) +cmMUL (n) +cdDIV (n) +.............
Where n denotes the instance characteristics, and ca, cs , cm ,cd and so on, respectively denote the time needed for an ADD, SUB, MUL, DIV, and so on, that performed when the code for p is used on an instance with characteristics n.

# Define Big "oh" (O) function.Prove that, if f(n) = amnm + .......+a1n + a0, then f(n) = O(nm)

Define Big "oh" (O) function.Prove that, if f(n) = amnm + .......+a1n + a0, then f(n) = O(nm)

`Proof:`
Let, b0 = |a0| .....bm = |am|, then for n>1
f(n)>bmnm+....b1n+b0 = (bm+......+b1/nm+1+b0/nm)nm
> (bm+....+b1+b0)nm = mnm

Where M = |am|+........+|a1|+|a0|

Hence, f(n) = 0(nm)

f(n) = 0(nm)

# What do you mean by performance measurement?

performance measurement :

Performance measurement is the process of collecting, analyzing and/or reporting information regarding the performance of an individual, group, organization, system or component. It can involve studying processes/strategies within organizations, or studying engineering processes/parameters/phenomena, to see whether output are in line with what was intended or should have been achieved.

# Write down the control abstractions for the divide and conquer strategy

The control abstractions for the divide and conquer strategy :

``` Algorithm D And C(P)
{

if small (p) then return S(P);

else

{

divide p into smaller instance p1, p1, p1, p2, p3, p4............. pk, k>1;

Apply D And C to each of these subproblems;

return Combine (D And C (p1)), (D And C (p2))......... D And C (pk));

}

}

```
The above divide and conquer algorithm processes a problem P having 'n' number of elements. First of all it checks whether the problem in simple enough to be solved individually using the functions small() which returns true if the problem is simple and false otherwise.If the problem is simple, its solution S(P) is returned.If the problem is not simple enough to be solved without dividing, it is subdivided into 'k' sub problems.After that, for each of the sub problem, the function D And Q is called recursively. On obtaining the solution of each sub problem, the function Combine() is used to integrate the solution of the sub problems. Then the final integrated solution is returned.

# What is Greedy Method?with Example

What is Greedy Method?with Example

`Greedy Method:`
An Algorithm which always takes the best intermediate or local solution while finding an answer.Greedy algorithms will always find the overall, or globally.Optimal solution for some optimization problems, but may find less-than optimal solutions for some instances of other problems.

`Example:`
1. Knapsack problem.
2. Prim’s algorithm.
3. Kruskal’s algorithm.
4. Dijkstra’s algorithm.

````Advantages:`

1.Greedy algorithm works fast when they work.

2.Simple algorithm.

3.Easy to implement.

`Disadvantages:`

1.  Greedy algorithm don’t always work.

2.  Hard to prove correct.

```

# What is Feasible Solution? What is Optimal Solution

Feasible Solution :

Any subset that satisfies some constraints is calld a feasible.

Optimal Solution :

A feasible solution that neither maximizes or minimizes a given objective function is called an optimal solution.

# Different types of algorithms

Different types of algorithms:-

```Every algorithm falls under a certain class.
Basically they are-

1)      Brute force
2)      Divide and conquer
3)      Decrease and conquer
4)      Dynamic programming
5)      Greedy algorithm
6)      Transform and conquer
7)      Backtracking algorithm
```

# Brute force algorithm

Brute force algorithm:

Brute force implies using the definition to solve the problem in a straightforward manner. This kind of problem is same as divide and conquer, except, here we are decreasing the problem in each iteration by a constant size instead of constant factor.

# Dynamic programming

Dynamic programming:-

The word 'dynamic' refers to the method in which the algorithm computes the result. Sometimes, a solution Here, we are trading space for time. i.e. - we are using more space to hold the computed values to increase the execution speed drastically. A good example for a problem that has overlapping sub-problem is the relation for Nth Fibonacci number. It is defined as F(n)= F(n-1) + F (n-2) .

# Greedy algorithm

Greedy algorithm:-

For many problems, making greedy choices leads to an optimal solution. These algorithms are applicable to For ex- consider the problem where you are given coins of certain denomination and asked to construct certain amount of money in inimum number of coins. Let the coins be of 1, 5, 10, 20 cents If we want change for 36 cents, we select the largest possible coin first (greedy choice). According to this process, we select the coins as follows- 20 20 + 10 20 + 10 + 5 20 + 10 + 5 + 1 = 36. For coins of given denomination, the greedy algorithm always works. But in general this is not true. Consider the denomination as 1, 3, 4 cents To make 6 cents, according to greedy algorithm the selected coins are 4 + 1 + 1 But, the minimum coins needed are only 2 (3 + 3) Hence, greedy algorithm is not the correct approach to solve the 'change making' problem. Infact, we can use dynamic programming to arrive at optimal solution to this problem.

# Transform and conquer

Transform and conquer:-

Sometimes it is very hard or not so apparent as to how to arrive at a solution for a particular problem. In this case, it is easier to transform the problem into something that we recognize, and then try to solve that Instead, we can find the GCD of the problem using a very fast algorithm known as Euclid's algorithm and then use that result to find the LCM as LCM ( a , b ) = (a * b) / GCD ( a , b )

# Backtracking algorithm

Backtracking algorithm:-

Backtracking approach is very similar to brute force approach. But the difference between backtracking and brute force is that, in brute force approach, we are generating every possible combination of solution and Ex- for an 8 X 8 chess board, if we follow brute force approach, we have to generate 4,426,165,368 solutions and test each of them. Whereas, in backtracking approach, it gets reduced to 40,320 solutions.

C o m p u t r F u n m e n t a l s
A n a l y s i s & D e s i g n
M a t h e m a t i c s

P h y s i c s
T h e o r y

O t h e r s