ALGORITHMS

Q.4: What do you mean by recursion? Write its property.
Ans: Recursion: Recursive procedure contains either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure.
It has the following properties:
There must be certain criteria, called base criteria, for which the procedure does not call itself.
Each time the procedure does call itself; it must be closer to the base criteria.
Example:
Tower of Hanoi:
Algorithm: Tower of Hanoi (n, x, y, z).
//move the top n disks from tower x to tower y.
{
If(n≥1) then
{
Tower of Hanoi (n – 1, x, z, y);
Write(“Move top disk from” x “to top of tower” y );
Tower of Hanoi(n – 1, z, y, x);
}
}
Complexity of Tower of Hanoi problem:
Let, T(n) = no of movement needed to place n disks from source peg to destination peg.




T(n)={█(1; n=1@T(n-1)+1+T(n-1); n>1)┤
T(n) =T(n-1)+1+T(n-1)
=2T(n-1)+1
=2(2T(n-2)+1)+1
=2^2 T(n-2)+2+1
=2^3 T(n-3)+2^2+2+1


=2^(n-1) T(n-(n-1) )+2^(n-2)+ ………+2^2+2+1
=2^(n-1) T(1)+2^(n-2)+ ………+2^2+2+1
=1+2+2^2+ ………+2^(n-2)+2^(n-1)
[We know that, S=a+ar+ar^2+ ………+〖ar〗^n=a(r^(n+1)-1)/(r-1),r>0]
So, T(n)=(1 .(2^n-1) )/(2-1)=2^n-1
#Problem:
T(n)={█(2; n=0@2+T(n-1); n>0)┤
T(n) =2+T(n-1)
=2+(2+T(n-2))
=2(2)+T(n-2)
=3(2)+T(n-2)


=n(2)+T(n-n)
=2n+T(0)
=2n+2
Q.5: Describe different complexity of an algorithm.
Ans: Space complexity: The space complexity of an algorithm is the amount of memory it needs to run to completion. The space needed to each algorithm is seen to be the sum of the following component.
A fixed part that is independent of the characteristics (such as number, size) of the inputs and outputs.
A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instances being solved, the space needed by referenced variables.
The space needed by this algorithm sum of the4 following component:
Algorithm Sum (a, n)
{
s □(∶=) 0;
for i □(∶=) 1 to n do
s □(∶=) s + a [i];
return s;
}
The space requirement S(P) of any algorithm P may therefore be written as S(P)=c+S_P ,where S_P→ instance characteristic, and c → constant.
Time complexity: The time complexity of an algorithm is the amount of computer time it needs to run to completion. The time taken T (P) taken by a program P is the sum of the compiler time and run (or execution) time. The compiler time does not depend on the instance characteristics. We concern ourselves with just the run time of a program.
Run time is denoted by t_p(instance characteristics).
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 addition, subtraction, multiplication, division and so on and ADD, SUB, MUL, DIV and so on are functions whose values are the numbers of additions, subtractions, multiplications, divisions and so on that are performed when the code for P is used on an instance with characteristic n.
Q.6: Describe asymptotic notation.
Ans: Asymptotic notation: The notation that is used to describe the asymptotic running time of an algorithm are defined in terms of functions whose domains are the set of natural numbers; N = {0, 1,2, … …}
Big – O notation: The function f(n)=O(g(n) ) if and only if there exist positive constants C and no such that O≤f(n)≤Cg(n) for all n≥n_o.
We use O – notation to give an upper bound on a function to within a constant factor. For all values n to the right of n_o, the value of the function f(n) is on or below g(n).
Example: 3n + 2 = O(n) as 3n+ 2 ≤ 4n for all n≥2.
Omega (Ω) notation: The function f(n)=Ω(g(n) ) if and only if there exist positive constant C and no such that O≤Cg(n)≤f(n) for all n≥n_o.
We use Ω - notation to give an lower bound on a function to within a constant factor. For all values n to the right of n_o, the value of the function f(n) is on or below g(n).
Example: 3n + 2 = Ω(n) as 3n + 2 ≥ 3n for all n≥1.
Theta (θ) notation: The function f(n)= θ(g(n) ) if and only if there exist positive constant C_1,C_2 and n_o such that, O≤C_1 g(n)≤f(n)≤C_2 g(n) for all n≥n_o.
We use θ – notation to give an tight bound on a function to within a constant factor. For all values of n, the value of f(n) lies at or above C_1 g(n) and at or bellow C_2 g(n). We says, g(n) is asymptotically tight bound for f(n).
Example: 3n + 2 = θ(n) as 3n + 2 ≥ 3n for n≥ 2 and 3n + 2 ≤ 4n for n≥2. So, C_1=3, C_2=4 and n_o=2

ALGORITHMS

Algorithm 2.2: (Quadratic Equation) This algorithm inputs the coefficients A, B, C of a quadratic equation and outputs the real solutions, if any.
Step 1: Read A, B, C.
Step 2: Set D = B2 – 4AC.
Step 3: If D>0, then
Set X1 = (-B+√D)/2A and X2 = (-B-√D)/2A.
Write X1, X2.
Else if D = 0, then
Set X = -B/2A.
Write ‘UNIQUE SOLUTIONS ’, X.
Else
Write ‘NO REAL SOLUTIONS’.
[End of if structure]
Step 4: Exit.

Algorithm2.3: (Largest element in Array) Given, a non empty array DATA with N numerical values, this algorithm finds the location LOC and the value MAX of the largest element of DATA.
Step 1: Set K = 1, LOC = 1 and MAX = DATA [1].
Step 2: Repeat Steps 3 and 4 while K ≤ N.
Step 3: If MAX < DATA [K], then
Set LOC = K and MAX = DATA [K].
[End of if structure]
Step 4: Set K = K+1.
[End of step 2 loop]
Step 5: Write LOC, MAX.
Step 6: Exit.

Algorithm 2.4: (Linear search) A linear array DATA with N elements and a specific ITEM of information are given. This algorithm finds the location LOC of ITEM in the array DATA or sets LOC = 0.
Step 1: Set K = 1, LOC = 0.
Step 2: Repeat Steps 3 and 4 while LOC = 0and K≤ N.
Step 3: If ITEM = DATA [K] then Set LOC = K
Step 4: Set K = K+1.
[End of step 2 loop]
Step 5: If LOC = 0 then
Write ITEM is not in the array DATA.
Else
Write LOC is the location of ITEM.
[End of if structure]
Step 6: Exit.

Algorithm 3.1: (Delete) A text T and a pattern P are in memory. This algorithm deletes every occurrence of P in T.
Step 1: Set K = INDEX (T, P).
Step 2: Repeat while K ≠ 0
Set T = DELETE(T, INDEX(T,P),LENGTH(P))
Set K = INDEX (T, P).
Step 3: Write T.
Step 4: Exit.

Algorithm 3.2: (Replacement) A text T, pattern P and Q are in memory. This algorithm replaces every occurrence of P in T by Q.
Step 1: Set K = Index (T, P)
Step 2: Repeat while K ≠ 0.
Set T = REPLACE (T, P, Q).
Set K = INDEX (T, P).
[End of loop]
Step 3: Write T.
Step 4: Exit.

Algorithm 3.3: (Pattern matching) P and T are strings with length R and S, respectively, and are stored as arrays with one character per element. This algorithm finds the INDEX of P in T.
Step 1: Set K = 1 and MAX = S – R + 1.
Step 2: Repeat steps 3 to 5 while K ≤ MAX.
Step 3: Repeat for L = 1 to R.
If P[L] ≠ T[K + L – 1],
Then go to step 5.
[End of inner loop]
Step 4: Set INDEX = K and Exit.
Step 5: Set K = K + 1.
[End of step 2 outer loop]
Step 6: Set INDEX = 0.
Step 7: Exit.

DEFINATION AND OTHER ABOUT ALGORITHM

Q.1: What is an algorithm? Describe different criteria of an algorithm.

Ans: Definition: The word algorithm comes from the name of a Persian author, Abu Ja’far Mohammed ibn Musa al Khowarizmi (c. 825 A.D.). In computer science, “algorithm” refers to a method that can be used for the solution of a problem. An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.

Criteria: All algorithms must satisfy the following criteria:

1. Input: Zero or more quantities are externally supplied.


2. Output: At least one quantity is produced.


3. Definiteness: Each instruction is clear and unambiguous.


4. Finiteness: If we trace out the instructions of an algorithm, then for all cases, the algorithm terminate after a finite number of steps.


5. Effectiveness: Every instruction must be very basic so that it can be carried out, in principle by a person. Each operation is definite and it must be feasible.

Q.2: What are the important and active areas of research of an algorithm? Or describe the distinct area of algorithm.

Ans: There are four distinct areas of study we can identify.

1. How to device an algorithm: Creating an algorithm is an art which may never fully automate.


2. How to validate algorithms: Once an algorithm is devised, it is necessary to show that it computes the correct answer for all possible legal inputs. This process is called algorithm validation. The purpose of the validation is to assume us that this algorithm will work correctly independently of the issue concerning the programming language it will eventually be written in.


3. How to analyze algorithms: When an algorithm executes, it uses the computers CPU to perform operations and its memory to hold the program and data. Analysis of algorithm or performance analysis refers to the task of determining how much computing time and storage requires the algorithm.


4. How to test a program: Testing a program consists of two phases: debugging and profiling. Debugging is the process of executing programs on simple data sets to determine whether a faulty result occurs and correct them. Profiling or performance measurement is the process of executing a correct program on data sets and measuring the time and space it takes to compute the result.

Q.3: Describe the Pseudocode Conventions of algorithm specification.

Ans: Algorithm Specification (Pseudocode Convention): The most algorithms using a Pseudocode that resembles C and Pascal are given bellow:

1. Comments begin with // and continue until the end of line.


2. Blocks are indicated with matching braces: {and}.


3. An identifier begins with a letter. The data types of variables are not explicitly declared.


4. Assignment of values to variables is done using the assignment statement.                                     <variable> := <expression>;


5. Elements of multi dimensional arrays are accessed using [and].


6. for, while and repeat until looping statements are employed.


7. In order to produce boolean values true or false, the logical operations and, or, not and the relational operators <, ≤, =, ≠, ≥ and > are provided.


8. A conditional statement has the following for m:

if <condition> then <statement>

if <condition> <statement 1> else <statement 2>

1. Input and output are done using the instructions read and write.


2. There is only one type of procedure: Algorithm. An algorithm consists of a heading and a body. The heading and a body. The heading takes the form

Algorithm Name (<parameter list>).     

ALGORITHM DESIGN BLOG FOR STUDENTS

wait a while