Design and Analysis of Algorithm

Syllabus

�

�

�

�

�

�

�

�

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

​

An algorithm is a finite set of instructions that, if followed ,accomplishes a particular task

​

An algorithm is an abstract representation of solution to a given problem represented as finite sequence of instruction or step

All algorithms must satisfy the following criteria / Properties:

�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 terminates 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 using only pencil and paper. It is not enough that each operation be definite as in criterion3; it also must be feasible� �

​

Notion / Flow /Understanding of Algorithm

• The non ambiguity requirement for each step of an algorithm cannot be compromised.
• The range of inputs for which an algorithm works has to be specified carefully
• .The same algorithm can be represented in several different ways.
• There may exist several algorithms for solving the same problem. �

Fundamentals of Algorithmic Problem Solving

Understanding the Problem �A good design of algorithm needs proper understanding of problem

If an existing algorithm is applicable select it to solve the problem

Discuss with peers to clarify all doubts regarding the problem in hand.

Clearly understand the input details (instance) required as input

Ascertaining the Capabilities of the Computational Device �To analyze an algorithm, we always need a model of computation.

Sequential model

(Object oriented)

Parallel model

Quantum Model

Basically choosing computational model is more relevant when solving complex problems

Choosing between Exact and Approximate Problem Solving �Solving the problem exactly or solving it approximately. In the former case, an algorithm is called an exact algorithm; in the latter case, an algorithm is called an approximation algorithm.

Few problems cannot have exact solution such as extracting square roots, solving nonlinear equations, and evaluating definite integrals.

Many a times find exact solution may slower execution speed, Some approximation algorithm solves sophisticated problem exactly �

�

​

Algorithm Design Technique

A general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing

Design techniques includes understanding analyzing exiting algorithms,

These will act as guide to solve new problem

Algorithm design is a creative art, needs creative thinking and practice

Techniques allows us to classify the algorithm

​

Designing an Algorithm and Data Structures

designing an algorithm for a particular problem is a challenging task

Few problem may need combining more than one algorithm

Few problems do not have a well known solution

Good algorithm must have a good and appropriate data structure

Good algorithm + good data structure -> Good Program

Methods of Specifying an Algorithm

1. Natural language
2. Pseudo code
3. Flowchart / Any other design tools

​

Converting algorithm to a program needs careful selection of programing domain statements� �

��

� �

Proving an Algorithm’s Correctness

prove that the algorithm yields a required result for every legitimate input in a finite amount of time

Common technique for proving correctness is to use mathematical induction

The notion of correctness for approximation algorithms is less straightforward�than it is for exact algorithms.

Analyzing an Algorithm

Analyzing an Algorithm requires to prove the algorithm efficiently solves the given problem

time efficiency which indicating how fast the algorithm runs

Space efficiency which indicates estimated memory required

Other desirable analysis are

Simplicity

Generality

Coding an Algorithm

A process wherein the algorithm is represented as a computer program

The coded program is executed to check that, algorithm in fact solves the problem properly efficiently

​

As a rule, a good algorithm is a result of repeated effort and rework. � �

� �� ��

Important Problem Types

Sorting�Searching�String processing�Graph problems

Travelling salesman problem, Graph coloring, routing�Combinatorial problems

Set based�Geometric problems

Numerical problems �

Units for Measuring Running Time�Some standard unit of time measurement such as a second, or millisecond, and so on can be used to measure the running time of a program after implementing the algorithm. But the Drawbacks are:� Dependence on the speed of a particular computer.� Dependence on the quality of a program implementing the algorithm.� The compiler used in generating the machine code.� The difficulty of clocking the actual running time of the program.

�Solution, we need metric to measure an algorithm’s efficiency that does not depend on these extraneous factors.

�One possible approach is to count the number of times each of the algorithm’s operations is executed. This approach is excessively difficult. The most important operation (+, -, *, /) of the algorithm, called the basic operation.

�Computing the number of times the basic operation is executed is easy. The total running time is determined by basic operations count �

Orders of Growth, Break Even Point � A difference in running times on small inputs is not what really distinguishes efficient algorithms from inefficient ones.

� For example, the greatest common divisor of two small numbers, it is not immediately clear how much more efficient Euclid’s algorithm is compared to the other algorithms, the difference in algorithm efficiencies becomes clear for larger numbers only.

� For large values of n, it is the function’s order of growth that counts which contains values of a few functions particularly important for analysis of algorithms �

Break Even Point

Identifying exact break even point is practically not viable

• Constant class O(1)
• Logarithmic class log(n)
• Linear class O(n)
• Poly Logratithmic nlog(n)
• Quadratic n^2
• Cubic n^3
• Exponential 2^n
• Factorial n!
• Best case -Minimum time to execute
• Average case- Average time to execute
• Worst case – Maximum time to execute

Selection Sort

ALGORITHM SelectionSort(A[0..n - 1])�//Sorts a given array by selection sort�//Input: An array A[0..n - 1] of orderable elements�//Output: Array A[0..n - 1] sorted in non decreasing order�for i ← 0 to n - 2 do� min ← i� for j ← i + 1 to n - 1 do� if A[j] < A[min]

min ← j� swap A[i] and A[min] �

ALGORITHM BubbleSort(A[0..n - 1])�//Sorts a given array by bubble sort�//Input: An array A[0..n - 1] of orderable elements�//Output: Array A[0..n - 1] sorted in non decreasing order�for i ← 0 to n - 2 do� for j ← 0 to n - 2 - i do� if A[j + 1] < A[j]

swap A[j] and A[j + 1] �

ALGORITHM SequentialSearch2(A[0..n], K)�//Implements sequential search with a search key as a sentinel�//Input: An array A of n elements and a search key K�//Output: The index of the first element in A[0..n - 1] whose value is�// equal to K or -1 if no such element is found�A[n]← K�i ← 0�while A[i]= K do� i ← i + 1� if i < n

return i� else

return -1 �

Brute-Force String Matching

ALGORITHM BruteForceStringMatch(T [0..n - 1], P[0..m - 1])�//Implements brute-force string matching�//Input: An array T [0..n - 1] of n characters representing a text and�for i ← 0 to n - m do� j ← 0� while j < m and P[j] = T[i + j] do� j ← j + 1� if j = m

return i�return -1 �

Divide-and-Conquer

1. A problem is divided into several sub problems of the same type, ideally of�about equal size.�2. The sub problems are solved (typically recursively, though sometimes a different algorithm is employed, especially when sub problems become small enough).�3. If necessary, the solutions to the sub problems are combined to get a solution�to the original problem.

Example Sum of n values

a1+a2+a3+a4+……..an

=(a1+a2+…….+an/2) +( an/2+1+….an)

We can divide list till the size of the problem is small enough to solve trivially

​

1 If a function is give to solve for n values D and C splits input into subsets

2 Each sub problem is solved independently

3 The solution of the sub problem is combined

4 Most of these solution are best expressed as recursive solution

​

�

Algorithm DAndC(P)�{

if Small(P) then return S(P);� else� {� divide P into smaller instances <Pi,P2,..., Pk, k >� Apply DAndC to each of these sub problems;

Return Combine(DAndC(Pi),DAndC(P2), ..,DAndC(Pn));

}

}

​

Masters Theorem

Ex:

t(n)=2t(n/2)+1

Here a=2 b=2 f(n)->n^d

F(n)=1 Hence d=0

a>b^d Hence t(n)=O(n^log ₂ 2)=O(n)

​

t(n)=t(n/2)+1

a=1 b=2 f(n)->n^d Hence d=0

a==b^d Hence t(n)=O(n^d log ₂ n)=O((n^0 log ₂ n)=log ₂ n

​

​

Algorithm BinSearch (a,n,x)� // Given an array a[l:n] of elements in non decreasing� // order,n > 0,determine whether x is present, and

// if so ,return j such that x = a[j]; else return 0.�{�low :=1;high :=n;� while (low<=high) do

{� mid:=[(low+high)/2;� if (x <a[mid]) then

high :=mid-1;� else

If (a>a[mid]) then

low :=mid+ 1;

else

return mid;�

}

return 0; � } �

Algorithm BinSearch (a,i,l,x)� // Given an array a[l:n] of elements in non decreasing� // order,n > 0,determine whether x is present, and

// if so ,return j such that x = a[j]; else return 0.�{�if(i==l) then // If Small(P)�{� If (x = a[ i ]) then

return i;� else

return 0;� else �{

// Reduce P into a smaller sub problem.� mid:=(i+l)/2;� if (x = a[mid]) then

return mid;� else

if (x < a[mid]) then� return BinSrch (a,i,mid-1,x);� else

return BinSrch (a, mid +1,l x );� }

}

Algorithm MaxMin(a, j, max, min)

// a[i:n] is a global array. Parameters i and j are integers, 1<=i<=j<=n.

// The effect is to set max and min to the largest and smallest values in a(I,j)

{

if (i = j) then

max:=min:=a[i]; // Small(P)

else

if (i = =j)then // Another case of Small(P)

if (a[i]<a[j]) then

max :=a[j]; min=a[ i ];

else

max:=a[i]; min:=a[j];

else

{ //n is not small, divide P into sub problems determine value of mid . mid:=(i + j)/2

// Solve the sub problems.

MaxMin(i,mid,max,min);

MaxMin(mid+i,j,maxi,mini);

// Combine the solutions.

if (max<maxi) then max:=maxi;

if (min >mini)then min:=mini; }

​

Merge(low, mid, high) Merge(1,1,2)

h :=low; i=low; j :=mid+ 1;�while ((h < mid) and (j < high)) do�{�if (a[ h ] <a[ j ] )then�{�b[ I ] :=a[ h] ;

h :=h + 1;�}

Else

{�b[ I ] -=a[ j ] ;

j :=j+ l;�}

i:=i + 1;�}

//b[ ] is an auxiliary array �

if (h >mid) then�for k :=j to high do�{�b[i]:=a[k];

i :=i + 1;�}

else�for k :=h to mid do�{�b[i] :=a[k];

i :=i + 1;�}�for k :=low to high do

a[k] :=b[k]; �

H=1 i=1 j=2

QUICK SORT (C.A. R.Hoare )

• Quick sort use divide and conquer approach such that no merging and use of auxiliary array is required ( An example of In place sorting and external sorting)
• It performs sorting by selecting during each iteration one element called pivot element
• The pivot element is placed such that all elements preceding this are smaller or equal to selected element
• All elements succeeding this are greater or equal.
• The sorting is again performed on the divided list by selecting new element
• In quick sort, the division into two sub arrays is made so that the�sorted sub arrays do not need to be merged later. This is accomplished by�rearranging the elements in a[l:n] such that a[i] < a[j]for all i between1�and m and all j between m+1and n for some m, 1< m < n.
• Thus, the elements in a[l:m] and a[rn+1:n] can be independently sorted
• . If m = 1 and p = n, then a[n+1] must be defined and must be greater than or equal to all elements in a[l:n] � �

​

DFS and BFS

Topological Sorting

Greedy method

Greedy Method is a general purpose solution applicable to wide variety of problems

In most of these problems we have N inputs and require us to obtain a subset that satisfies some constrain

​

Example:

Fill a Five KG capacity Bag with different Items for sale

Item No of packets Item weight Profit

Item 1 06 250 gram 100

Item 2 05 500 gram 050

Item 3 08 400 gram 075

Item 4 03 1000 gram 125

​

Which items to stored in Bag will give maximum profit?

​

Any item which can be stored without acceding the capacity is

feasible solution

​

Any combination of item that will yield maximum profit is optimal solution

In greedy method suggests that one can devise an algorithm that works

in stages considering one input at a time

​

At each stage a decision is made regarding whether a particular input is in an optimal solution. This is done by considering the inputs in an order determined by some selection procedure.

​

If the inclusion of the next input into the partially constructed optimal

Solution will result in an infeasible solution then this input is not added to the partial solution. Other wise it is added.

​

The selection procedure itself is based on some optimization measure

​

One method generally available is to produce large set of subset and try each one of them a subset method is applicable n! ( combinatorial problem)

​

​

Algorithm Greedy( a, n)

{

Solution = 0

for(i=1; i<=n ; i ++)

{

x=select(a);

if Feasible ( Solution, x);

solution= Solution U x

}

return Solution

}

Change Problem

​

You have a set of coins / Notes

​

5, 10, 20, 50 ,

​

Decide what should be the optimal number of change we should give when requested

​

Ex Give change of Rs 100

​

If(i=0; i<4;I++)

{

if(V >=Note[ i ])

num_notes [ i ]= V / Note [ i ];

V= V % Note { i ];

}

Return Num_notes;

Change for 300 ?

​

Change for 480 ?

Greedy Knapsack ( General Method )

1. A Knapsack with capacity M is available
2. Knapsack is to be filled with item with different weights

w1,w2, w3,… wn wi>0

• When object wi is added to Knapsack we earn Profit p1,p2,p3,

…pn pi > 0

Let xi denote fraction of weight such that

profit = profit + xi* Pi

xi=1 if complete object is added

Problem: Select object to fill knapsack such that profit is maximized = pi * xi is maximized

Subjected to constraint wi * xi <= M

Example

N=3 M=20

(w1,w2,w3)=(18,15,10)

(p1,p2,p3) = ( 25, 24, 15)

​

Algorithm greedyKnapsack(W,P,M,n)

{

for(i=0; I < n; i++)

x[ I ]=0;

V=M;

for ( i=0;i<n;i++)

{

if (w[ i ] > V) then break;

x[ i ] =1;

V = V – w[ i];

P = P + x[ i ] * P[ i ] ;

}

if ( i < n ) w [i]= V/ w[i];

P= P + x[i] * P [i];

}

Return P;

}

​

M=20, n=3

W1=18 W2=15 W3=10

P1=25 P2=24 P3=15

Not an optimal solution

M=20, n=3

W1=18 W2=15 W3=10

P1=25 P2=24 P3=15

Arrange items in descending order of profit / Weight =Pi/Wi

P1/W1=1.38, P2/W2=1.6 P3/W3=1.5

1.6-1.5-1.38 = ( W2,W3,W1) (P2,P3,P1)

To obtain optimal solution Arrange items in decreasing order of profit / weight

Knapsack Problem Memory Method

N= 4 M=5, W=(2,1,3,2) P=(12,10,20,15)

V[I,J]=V[I-1,J] If J<Wi

Else

V[I,j]=Max{ v[i-1,j],v[i-1, j-wi]+pi if j>=W

J Value= 0 to M

I Value =0 to N

Profit table V[I,j] of size N+1 * M+1 will store profit earned

Value of V[0,j] =0 Value of V[I,0]=0 { Initialization of table}

Dynamic method to solve knapsack problem

Backward Method with memory function

Initialization of Table

Start with calculating v(4,5)

Selection of object is done through observing entries in table V( i,j)

If(v ( i , j) <> v( i -1,j) item selected and i=i-1, j=j-wi for next observation

N= 4 M=5, W=(2,1,3,2) P=(12,10,20,15)

V(4,5) i=4 j=5 w4=2 j-w4=5-2=3 > =0

V(4,5)=max{ v(3,5), v(3,3)+15 } Find value for v(3,5) and v(3,3) ---A

​

V(3,5)=max(v(2,5),v(2,2)+20) --1

V(2,5)=max(v(1,5),v(1,4)+10) - --2

V(1,5)=max(v(0,5),v(0,3)+12) = 12 --3

V(1,4)=max(v(0,4),v(0,2)+12)=12 --4

V(2,2)=max(v(1,2),v(1,1)+10) --5

V(1,1)=v(0,1)=0 --6

V(1,2)=max(v(0,2),v(0,1)+12=12 --7 Substitute 6,7 in 5

V(2,2)=12

V(3,5)=32 –Check result

Substitute 3 and 4 in 2

V(2,5)=max(v(1,5),v(1,4)+10)=max(12,12+10)=max(12,22)=22

V(2,5)=22-----8

V(3,3)=max(v(2,3),v(2,0)+20)

V(2,3)=max(v(1,3),v(1,2)+10) --8

V(1,3)=max(v(0,3),v(0,1)+12)=12 --9

V(1,2)=max(v(0,2),v(0,1)+12=12 --10

Substitute 6,7 in 5

v(2,3)=max(12,22)=22 -11

V(2,0)=v(1,0) =0

V(3,3)= max( v(2,3),v(2,0)+20)=22---12 Find answer for A

`

Solve:

1 Note down results obtained in previous step

2 Once filled follow steps to determine value of Xi

3 Generate weight set

V( i, j ) <> v ( i-1,j) include Wi and i=i-1, j=j-wi

V( i, j)==v(i-1,j) then exclude Wi and i=i-1 j=j-0

V(4,5) <> V(3,5) Hence w4=1 and i=i-1= 3 j=j-w4=5-2=3

V(3,3) ==v(2,3) Hence w3=0 i=i-1=2 j=j-0=3

V(2,3) <> V(1,3) Hence w2=1 and i=i-1=2-1=1, j=j-w2=3-1=2

V(1,2) <> V(0,2) Hence w1=1 and I =i-1=0 j=j-w1=2-2=0

Result (w1,w2,w3) or Result=(1,1,0,1)

N= 4 M=5, W=(2,1,3,2) P=(12,10,20,15)

Job Sequencing with dead lines

1. Set of jobs j1,j2,j3----jn are given, each job must be complete within thier given deadline d1,d2,d3----dn di>0
2. Each job needs one unit time to complete.
3. Only one machine is available to complete / process job
4. When a job completes within dead line Di profit p1,p2,….pn pi>0 is earned.
5. We have to sequence the job in a order where maximum jobs are processed within their respective deadline and we maximize profit

Ex:

Four jobs are given (j1,j2,j3,j4)

dead lines (d1,d2,d3,d4)=(2,1,2,1)

Profit (p1,p2,p3,p4)=(100,10,15,22)

Solution:

(j1,j2) in order j2,j1 P=110

(j1,j3) Profit =115

(j1,j4) in order (j4,j1) profit 122

(j1,j2,j3) –not feasible

(j2,j3) in order (j3,j2)=25

Solution is to explore all subset of combination 2^n ( exponential Problem)

​

Optimal solution:

1. Arrange the job in decreasing order of profit.
2. Create an array with size equal to maximum deadline
3. Select the job arranged in step 1 and assign array slot equal to dead line
4. Update profit as jobs are added

Example

Four jobs are given (j1,j2,j3,j4) =(d1,d2,d3,d4)=(2,1,2,1)=(p1,p2,p3,p4)=(100,10,15,22)

1: (100,22,15,10)=(p1,p4,p3,p2)=(j1,j4,j3,j2)

2.

​

​

​

3. p=100

​

​

​

p=100+22=122

No other jobs can be added as job slots are full {j4,j1} optimal solution

​

Find solution to : P=(3,5,18,20,6,1,38) D=(1,3,3,4,1,2,1)

DEFINITION A spanning tree of an undirected connected graph is it connected�acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. The minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph

single-source shortest-paths problem (Dijkstra’s algorithm )

for a given vertex called the source in a weighted connected graph, find shortest paths to all its other vertices.

1. Dijkstra’s algorithm finds the shortest paths to a graph’s vertices in order of�their distance from a given source
2. First finds the shortest path from the source to a vertex nearest to it �among all vertex connected to source vertex
3. Let this vertex be V, when we reach V we find the next nearest vertex U among all vertex adjacent to V �At any point smallest distance is D(V)+w(V,U) among all U adjacent V��

Source vertex a – find shortest path to all other vertex

from a to b : a - b of length 3�from a to d : a - b - d of length 5�from a to c : a - b - c of length 7�from a to e : a - b - d - e of length 9

Huffman’s algorithm�Step 1 Initialize n one-node trees and label them with the symbols of the alphabet given. Record the frequency of each symbol in its tree’s root to indicate the tree’s weight. (More generally, the weight of a tree will be equal to the sum of the frequencies in the tree’s leaves.)

�Step 2 Repeat the following operation until a single tree is obtained.

Find two trees with the smallest weight

Make them the left and right sub tree of a new tree and record the sum of their weights in the root of the new tree as its weight �

Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence frequencies in a text made up of these symbols:

0.25

0.40

0.25

0.60

0.40

0.25

0.60

1.0

Encode word CAD_BAD

Draw Huffman Tree

What is the compression ratio

Decode 100010111001010 �

Warshall’s Algorithm

Warshalls algorithm determines the transitive closure of an undirected /Directed graph with no negative cycle

transitive closure of a directed graph with n vertices can be defined as the n × n boolean matrix T = {tij}, in which the element in the i th row and the j th column is 1 if there exists a nontrivial path (i.e., directed path of a positive length) from the ith vertex to the jth vertex; otherwise, tij is 0. �

1. If an element in R^k(i,j) is 1 it remains 1 for all next iterations
2. If an element R^k(i,j) 0 is to be replaced by 1 only if R^k-1(i,k) =1 and R^k-1(k,j) =1

Find solution

Heap and Heap Sort

Notion of �DEFINITION the Heap

A heap can be defined as a binary tree with keys assigned to its nodes, one key per node, provided the following two conditions are met:

�1. The shape property—the binary tree is essentially complete (or simply complete), i.e., all its levels are full except possibly the last level, where only some rightmost leaves may be missing.

�2. The parental dominance or heap property—the key in each node is greater than or equal to the keys in its children. (This condition is considered automatically satisfied for all leaves.) �

�

Important Properties Of Heaps

�1. There exists exactly one essentially complete binary tree with n nodes. Its height is equal to h=log2 (n).�2. The root of a heap always contains its largest element / Smallest element �3. A node of a heap considered with all its descendants is also a heap.�4. A heap can be implemented as an array by recording its elements in the top down, left-to-right fashion. It is convenient to store the heap’s elements in positions 1 through n of such an array, leaving H[0] either unused or putting there a sentinel whose value is greater than every element in the heap. In such a representation,�a. the parental node keys will be in the first [n/ 2] positions of the array while the leaf keys will occupy the last n/2 positions;�b. the children of a key in the array’s parental position i (1 ≤ i ≤ n/2) will be in positions 2i and 2i + 1, and, correspondingly, the parent of a key in position i (2 ≤ i ≤ n) will be in position [i/2] �

2, 9, 7, 6, 5, 8. �

40,80,35,90,45, 50, 70

1

3

Backward Approach with Directed graph of K number of stages

d (k-1,j)=c(j,t) if path available else infinity

d (4,7)=7 d(4,8)=3

​

d( 3,4)=min{ 1+ d (4,7), 4+ d(4,8)} =min{8,7}=7

d( 3,5)=min{ 6+ d (4,7), 2+ d(4,8)} =min{13,9}=9

​

d( 3,6)=min{ 6+ d (4,7), 2+ d(4,8)} =min{13,5}=5

​

d( 2,2)=min{ 3+ d (3,4), 1+ d(3,5), 3+ d(3,6) } =min{10, 10, 8}=8

​

d( 2,3)=min{ 6+ d (3,4), 5+ d(3,5), 3+ d(3,6) } =min{ 13, 14, 8}=8

​

d( s,2)=min{ 5+ d (2,2), 2+ d(2,3) } =min{13, 10}=10

​

Path s-> 3 🡪 6 🡪 8 🡪 t 2+3+2+3 =10

1

Input Enhancement in String Matching

String Matching: finding an occurrence of a given string of m characters called the pattern in a longer string of n characters called the text.

Brute force approach O(nm), this can be reduced with variable shifting of pattern

​

Horspool’s Algorithm �Consider, as an example, searching for the pattern BARBER in some text:�s0--------- . . . C--------------- ------------ sn � B A R B E R

Staring with letter R if all character matches we consider the pattern is matched

If a mismatch occurs, we need to shift the pattern to the right

Shift should be as large as possible

While matching the following cases can occur

​

Case 1: If there are no c’s in the pattern—e.g., c is letter S in our example—�we can safely shift the pattern by its entire. If the rightmost character does not match with the text

s0 . . . S . . . sn-1� B A R B E R� B A R B E R �

Case 2 If there are occurrences of character c in the pattern but it is n the last one there—e.g., c is letter B in our example—the shift should align the rightmost occurrence of c in the pattern with the c in the text:

s0 . . . B . . . sn-1

B A R B E R� B A R B E R

​

Case 3: If c happens to be the last character in the pattern but there are no c’s�among its other m - 1 characters—e.g., c is letter R in our example—the situation is similar to that of Case 1 and the pattern should be shifted by the entire pattern’s length m:

s0 . . . M E R . . . sn-1

L E A D E R

L E A D E R

​

Case 4: Finally, if c happens to be the last character in the pattern and there�are other c’s among its first m - 1 characters—e.g., c is letter R in our example—the situation is similar to that of Case 2 and the rightmost occurrence of c among the first m - 1 characters in the pattern should be aligned with the text’s c: � � � � � ��

s0 . . . A R . . . sn-1

R E O R D E R

R E O R D E R

We can pre compute shift sizes and store them in a table called shift table

Horspool’s algorithm�Step 1 For a given pattern of length m and the alphabet used in both the pattern and text, construct the shift table as described above.�Step 2 Align the pattern against the beginning of the text.�Step 3 Repeat the following until either a matching substring is found or the pattern reaches beyond the last character of the text. Starting with the last character in the pattern, compare the corresponding characters in the pattern and text until either all m characters are matched (then stop) or a mismatching pair is encountered. In the latter case, retrieve the entry t(c) from the c’s column of the shift table where c is the text’s character currently aligned against the last character of the pattern, and shift the pattern by t(c) characters to the right along the text �

ALGORITHM ShiftTable(P [0..m - 1])�//Fills the shift table used by Horspool’s �//Input: Pattern P [0..m - 1] and an alphabet of possible characters�//Output: Table[0..size - 1] indexed by the alphabet’s characters and �// filled with shift sizes computed

for i ← 0 to size-1 do Table[ i ] ← m�for j ← 0 to m - 2 do Table[P[ j ] ] ← m - 1 - j�return Table �

ALGORITHM HorspoolMatching(P [0..m − 1], T [0..n − 1])

{

//Implements Horspool’s algorithm for string matching

//Input: Pattern P [0..m − 1] and text T [0..n − 1]

//Output: The index of the left end of the first matching substring

// or −1 if there are no matches

ShiftTable(P [0..m − 1])

//generate Table of shifts

i ← m − 1 //position of the pattern’s right end

while i ≤ n − 1 do

{

k ← 0 //number of matched characters

while (k ≤ m − 1 and P [m − 1 − k] = = T [i − k] ) do

{

k ← k + 1

if (k == m)

return ( i − m + 1 )

else � i ← i + Table[T[ i ] ]

}

}

return −1

}

ALGORITHM ComparisonCountingSort(A[0..n - 1])�//Sorts an array by comparison counting�//Input: An array A[0..n - 1] of orderable elements�//Output: Array S[0..n - 1] of A’s elements sorted in nondecreasing order�for i ← 0 to n - 1 do Count[i] ← 0;�for i ← 0 to n - 2 do�for j ← i + 1 to n - 1 do� if A[i] < A[j]� Count[j] ← Count[j] + 1� else

Count[i] ← Count[i] + 1�for i ← 0 to n - 1 do S[Count[i]] ← A[i]�return S

�

ALGORITHM DistributionCountingSort(A[0..n − 1], l, u)

//Sorts an array of integers from a limited range by distribution counting

//Input: An array A[0..n − 1] of integers between l and u (l ≤ u)

//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order

for j ← 0 to u − l do D[j] ← 0 //initialize frequencies

for i ← 0 to n − 1 do D[A[i] − l] ← D[A[i] − l] + 1

//compute frequencies

for j ← 1 to u − l do D[j] ← D[j − 1] + D[j] //reuse for distribution

for i ← n − 1 downto 0 do

j ← A[i] − l

S[D[j] − 1] ← A[i]

D[j] ← D[j] − 1

return S

Warshall’s Algorithm�An adjacency matrix A = {a ij} of a directed graph is the boolean matrix that has 1 in its ith row and jth column if and only if there is a directed edge from the I th vertex to the jth vertex.

We may also be interested in a matrix containing the information about the existence of directed paths of arbitrary lengths between vertices of a given graph.

Such a matrix, called the transitive closure of the digraph, would allow us to determine in constant time whether the j th vertex is reachable from the I th vertex

The transitive closure of a directed graph with n vertices can be defined as the n × n boolean matrix T = {t ij}, in which the element in the I th row and the j th column is 1 if there exists a nontrivial path (i.e., directed path of a positive length) from the I th vertex to the j th vertex; otherwise, t ij is 0 � �

SINGLE-SOURCE SHORTEST PATHS ( BelllmanFord Algorithm)

The Knapsack Problem and Memory Functions

Let us consider an instance defined by the�first i items, 1 ≤ i ≤ n, with weights w1, . . . , wi, values v1, . . . , vi, and knapsack capacity j, 1 ≤ j ≤ W. Let F (i, j) be the value of an optimal solution to this instance, i.e., the value of the most valuable subset of the first i items that fit into the knapsack of capacity j. We can divide all the subsets of the first i items that fit the knapsack of capacity j into two categories: those that do not include the ith item and those that do.

Note the following:

�1. Among the subsets that do not include the ith item, the value of an optimal�subset is, by definition, F (i - 1, j)

�2. Among the subsets that do include the ith item (hence, j - wi ≥ 0), an optimal�subset is made up of this item and an optimal subset of the first i - 1 items�that fits into the knapsack of capacity j - wi. The value of such an optimal�subset is vi + F (i - 1, j - wi).

​

​

​

V[ i, j ]= max(v[i-1,j],v[i-1,j-wi]+pi wi <j

​

= v[i-1,j] wi >j

= 0

P, NP, and NP-Complete Problems

If worst case time complexity of an algorithm is represented by some polynomial ie O(p(n)). They are refereed as polynomial time algorithm

​

Ex O(n^2), O(n^2logn), nlogn, n^3

P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. This class of problems is called polynomial. P class

​

Deterministic: Final outcome can be determined, execution steps are clearly mentioned and solves problem in polynomial time.�

​

​

Problems that can be solved in polynomial time are called tractable, and�problems that cannot be solved in polynomial time are called intractable

Program Halting Contradiction

DEFINITION 2 Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. This class of problems is called polynomial Class P

​

Not all decidable problems can be solved in Polynomial time

Ex Hamiltonial Circuit, Graph coloring, Knapsack, Graph Coloring etc

​

Solving such problems can be computationally difficult, checking whether a proposed solution actually solves the problem is computationally easy �

nondeterministic algorithm : Are two stage problem takes input I and

Step 1: Generates an arbitrary string S as a solution to I called guessing stage

Step 2: Deterministic stage Takes S and I as input and returns Yes if S is solution to I

Else does not halt or returns No

​

Nondeterministic algorithm is said to be nondeterministic polynomial if the time efficiency of its verification stage is polynomial.

​

Class NP: Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms. This class of problems is called Nondeterministic polynomial. (NP class)

​

A decision problem D1 is said to be polynomially reducible to�a decision problem D2, if there exists a function t that transforms instances of D1�to instances of D2 such that:�1. t maps all yes instances of D1 to yes instances of D2 and all no instances of D1�to no instances of D2�2. t is computable by a polynomial time algorithm ���

A decision problem D is said to be NP-complete if:�1. It belongs to class NP�2. Every problem in NP is polynomially reducible to D �

NP-hard problems—Problems that are at least as hard as NP-complete problems.�Hence, there are no known polynomial-time algorithms for these problems, and�there are serious theoretical reasons to believe that such algorithms do not exist

( Travelling salesman and Knapsack are well known problems in this category)

​

However, approximate solutions can be obtained, by applying approximation algorithm

​

These can be solved employing Heuristic algorithm

Backtracking, Branch and Bound (FIFO and LIFO), A*, AO*, two way Search

Backtracking

Backtracking is a more intelligent approach. ( Heuristic apprach)

1. Construct solutions one component at a time
2. Evaluate the partially constructed candidates
1. If a partially constructed solution can be developed further without violating the problem’s constraints,
2. Consider remaining legitimate option for the next component
3. If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered
4. Backtracks to replace the last component of the partially constructed solution with its next option. (Go back to previous legitimate state)

n-Queens Problem�n-queens problem. place n queens on an n × n chessboard so that no two queens attack each other

by being in the same row or in the same column or on the same diagonal. �

Branch-and-Bound

optimal solution is a feasible solution with the best value of the objective function

Branch and Bound works with following principles in addition to Back tracking

1. Every node is labeled with estimated optimal value, (determined heuristically)

The above value serves as a guide line to decide weather to explore further or not

2. A value of the best solution obtained so far is utilized to stop further exploration

Job Assignment problem

​

​

​

​

​

​

​

Problem Assign one job to each person, the total cost of the processing all job should be minimum

​

​

�

Knapsack Problem

ub = v + (W - w)(Vi+1/Wi+1) To determine upper bound .(maximization)

Initially v=0 w=0 -> ub=0+(10-0)*(10)=100

If item 1 is included ub=40+(10-4)*6=76

If item 1 not included ub=0+10*6=60 (inferior)

Item 2 cannot be included as capacity is 6 after selecting item 1 hence

Ub=40+6*5=70

( use above method to generate state space tree)

Travelling sales person problem

Lower bound =lb = s/2 =lb = [(1 + 3) + (3 + 6) + (1 + 2) + (3 + 4) + (2 + 3)]/2]= 14.

Least weighted outgoing 2 edges/branch connected to vertex are employed�