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];

}.

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 :

Precisionthe steps are precisely stated(defined).

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

Finitenessthe algorithm stops after a finite number ofinstructions are executed.

Inputthe algorithm receives input.

Outputthe algorithm produces output.

Generalitythe algorithm applies to a set ofinputs.

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 t_{p}(instance characteristics).

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 t_{p}(n) is as follows-

t_{p}(n) = c_{a}ADD(n) +c_{s}SUB(n) +c_{m}MUL(n) +c_{d}DIV(n) +.............

Where n denotes the instance characteristics, and c_{a}, c_{s}, c_{m},c_{d}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) = a_{m}n^{m}+ .......+a_{1}n + a_{0,}then f(n) = O(n_{m})

`Proof:`

Let, b_{0}= |a_{0}| .....b_{m}= |a_{m}|, then for n>1

f(n)>b_{m}n^{m}+....b_{1}n+b_{0}= (b_{m}+......+b_{1}/n^{m+1}+b_{0}/n^{m})n^{m}

> (b_{m}+....+b_{1}+b_{0})n^{m}= mn^{m}

Where M = |a_{m}|+........+|a_{1}|+|a_{0}|

Hence, f(n) = 0(n_{m})

f(n) = 0(n_{m})

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.

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 pThe 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._{1}, p_{1}, p_{1}, p_{2}, p_{3}, p_{4}............. p_{k}, k>1; Apply D And C to each of these subproblems; return Combine (D And C (p_{1})), (D And C (p_{2}))......... D And C (p_{k})); } }

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 & Disadvantages :`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.

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:-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 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:-

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:-

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:-

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

- Programming Language C
- Object Oriented Programming Language C++
- Data Structure
- Microprocessor And Assembly Language
- Algorithm For Professional Programmer
- Software Engineering
- Microprocessor And Assembly Language

- Web Engineering
- Professional Web Page Design
- Professional SQL Database Program
- E-Commerce
- Database Management System

- Discrete Mathematics
- Statistics and Probability
- Basic Accounting
- Numericals Analysis
- Engineering Mathematics
- Mathematics For CSE
- Integrals Calculus And Differentials Equation