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 criterion-3; 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 relevant computational model is more important 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 �1. A difference in running times on small inputs is not what really distinguishes efficient algorithms from inefficient ones.�2. 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.�3. 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 �

n Linear

log n Logarithmic

n^2 n-sqaure

n^3 Cubic

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 Logarithmic nlog(n)
• Quadratic n^2
• Cubic n^3
• Exponential 2^n
• Factorial n!
• Best case: C_best -Minimum time to execute
• Average case:C_avg- Average time to execute
• Worst case: C_worst– Maximum time to execute

Algorithm Efficiency Analysis

There are two kinds of efficiency: Time Efficiency And Space Efficiency.

Time efficiency, also called time complexity, indicates how fast an algorithm in question runs.

​

Space efficiency, also called space complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and output.

we primarily concentrate on time efficiency

Identify the most important operation of the algorithm, called the basic operation,

The operation contributing the most to the total running time

Compute the number of times the basic operation is executed.

​

ALGORITHM --------------(A[0..n - 1], K)

{

while i < n and A[i] ∕= K do

i ← i + 1

if i < n

return i

else

return -1

}

Amortized efficiency ( cost Amortized efficiency).

It applies not to a single run of an algorithm but rather to a sequence of operations performed on the same data structure.

​

It turns out that in some situations a single operation can be expensive, but the total time for an entire sequence of n such operations is always significantly better than the worst-case

​

Efficiency of that single operation multiplied by n.

​

We can “amortize” the high cost of such a worst-case occurrence over the entire sequence

​

in a manner similar to the way a business would amortize the cost of an expensive item over the years of the item’sl productive�

Asymptotic Notations and Basic Efficiency Classes

To compare and rank such orders of growth, computer scientists use three notations.

O (big oh), Ω(big omega), and ⱷ (big theta).

O(g(n)) is the set of all functions with a lower or same order of growth

n ^2+1 ∈ O(n^2), 100n^2 + 5 ∈ O(n^2), 1/2 n(n - 1) ∈ O(n^2)

Consider n >=1 Therefore

​

​

Using Limits for Comparing Orders of Growth

Formal definitions of O,Ω, ⱷ are indispensable they are rarely used for comparing the orders of growth

​

A better method for comparing order of growth is based on computing the limits of ratio of two functions being compared.

​

​

​

​

0 –Order of g(n) has high order of growth than t(n)

C – Both have same order of growth

∞ - Order of t(n) has high order of growth than g(n)

While comparing two rules are useful

1. L’Hopital’s rule 2: Stirling’s formula ��

Mathematical Analysis of Non-recursive Algorithms

General Plan for Analyzing the Time Efficiency of Non-recursive Algorithms

1. Decide on a parameter (or parameters) indicating an input’s size.

2. Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)

3. Check whether the number of times the basic operation is executed depends only on the size of an input. If it also depends on some additional property, the worst-case, average-case, and, if necessary, best-case efficiencies have to be investigated separately.

4. Set up a sum expressing the number of times the algorithm’s basic operation is executed

5. Using standard formulas and rules of sum manipulation, either find a closed form formula for the count or, at the very least, establish its order of growth

ALGORITHM MaxElement(A[0..n - 1])

for i = 1 to n - 1 do

{

if (A[i] > maxval) then

​

maxval ← A[i]

}

return maxval

ALGORITHM UniqueElemen(A[0..n - 1])

{

for i = 0 to n - 2 do

{

for j ← i + 1 to n - 1 do

{

if A[i] = A[j] then

return false }

}

return true �

ALGORITHM

MatrixMultiplication(A[0..n – 1)

for i = 0 to n - 1 do

for j = 0 to n - 1 do

{

C[i, j] ← 0.0

F

or k = 0 to n - 1 do

{

C[i, j] ← C[i, j] + A[i, k] ∗ B[k, j]

}

}

return C

ALGORITHM Binary(n)

{

count ← 1

while n > 1 do

{

count ← count + 1

n ← ⌊n/2⌋

}

return count �

ALGORITHM Mystery(n)

S ← 0

for i ← 1 to n do

S ← S + i ∗ i

return S �

ALGORITHM Secret(A[0..n - 1])

minval ← A[0];

maxval ← A[0]

for i ← 1 to n - 1 do

if A[i] < minval

minval ← A[i]

if A[i] > maxval

maxval ← A[i]

return maxval - minva �

Mathematical Analysis of Recursive Algorithms

General Plan for Analyzing the Time Efficiency of Recursive Algorithms

1. Decide on a parameter (or parameters) indicating an input’s size.

and determine the stopping criteria of recursion

2. Identify the algorithm’s basic operation.

3. Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately.

4. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.

5. Solve the recurrence or, at least, ascertain the order of growth of its solution�

ALGORITHM F(n)

if n = 0 then

return 1

else

return F (n - 1) ∗ n

F (n) = F (n - 1) * n for n > 0

and f(1) =1

M(n) = M(n - 1) + 1 for all n > 0

T(n)=t(n-1) +1

T(n-1): to calculate n-1 terms

1: for multiplication with previous term

General equation of recursion

T(n)=aT(n/b)+f(n)

• We can use backward substitutions method to solve this

Tower of Hanoi puzzle.

• In this puzzle, There are n disks of different sizes that can slide onto any of three pegs.
• Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top.
• The goal is to move all the disks to the third peg, using the second one as an auxiliary, if necessary.
• We can move only one disk at a time, and it is forbidden to place a larger disk on top of a smaller one.

The recursive solution

• To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
1. First move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary)
2. Move the largest disk directly from peg 1 to peg 3,
3. Finally, move recursively n-1 disks from peg 2 to peg 3 (using peg 1 as auxiliary).
• If n = 1, we move the single disk directly from the source peg to the destination peg.

Algorithm

TowerOfHanoi(n, source, dest, aux)

{

If (n == 1) then

move disk from source to dest else

{

TowerOfHanoi (n - 1, source, aux, dest) move disk from source to dest TowerOfHanoi (n - 1, aux, dest, source)

}

Backward substitutions method:

• The pattern of the first three sums on the left suggests that the next one will be

2⁴ M(n − 4) + 2³ + 2² + 2 + 1, and generally, after i substitutions, we get

• Since the initial condition is specified for n = 1, which is achieved for i = n - 1,

we get the following formula for the solution to recurrence

• Basic operation is Addition
• The recurrence relation can be written as
• Assuming n = 2^k

General equation of recursion

T(n)=aT(n/b)+f(n)

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 �

Exhaustive search

Many important problems require finding an element with a special property in a domain that grows exponentially (or faster) with an instance size.

Many combinatorial objects such as permutations, combinations have this property

Exhaustive search is simply a brute-force approach to combinatorial problems. It suggests generating each and every element of the problem domain, selecting those of them that satisfy all the constraints

Traveling Salesman Problem(TSP)

“shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started” conveniently modeled by a weighted graph

Hamiltonian circuit of the graph. (A Hamiltonian circuit is defined as a cycle that passes through all the vertices of the graph exactly once. It is named after the Irish mathematician

Knapsack Problem

Given n items of known weights w1, w2, . . . , wn and

values v1, v2, . . . , vn and

a knapsack of capacity W,

find the most valuable subset of the items that fit into the knapsack. �

Decrease and Conquer

Topological Sorting

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

sum= 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 (x > a[mid]) then

low :=mid+ 1;

else

return mid;�

}

return 0; � } �

Algorithm BinSearch (a,i,l,x)�{�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

{. mid:=(i + j)/2

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

ALGORITHM Mergesort(A[0..n − 1])

{

if n > 1

copy A[0..⌊n/2⌋ − 1] to B[0..⌊n/2⌋ − 1]

​

copy A[⌊n/2⌋..n − 1] to C[0..⌈n/2⌉ − 1]

​

Mergesort(B[0..⌊n/2⌋ − 1])

​

Mergesort(C[0..⌈n/2⌉ − 1])

​

Merge(B, C, A)

}

ALGORITHM Merge(B[0..p − 1], C[0..q − 1], A[0..p + q − 1])

//Merges two sorted arrays into one sorted array

//Input: Arrays B[0..p − 1] and C[0..q − 1] both sorted

//Output: Sorted array A[0..p + q − 1] of the elements of B and C

i ← 0; j ← 0; k ← 0

while (i < p and j < q )do

if B[i] ≤ C[j]

A[k] ← B[i]; i ← i + 1

Else

A[k] ← C[j]; j ← j + 1

k ← k + 1

if i = p

copy C[j..q − 1] to A[k..p + q − 1]

else

copy B[i..p − 1] to A[k..p + q − 1]

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

number of key comparisons C(n) is

C(n) = 2C(n/2) + Cmerge(n) for n > 1, C(1) = 0

At each step, exactly one comparison is made

worst case smaller elements may come from the alternating arrays �Therefore, for the worst case, Cmerge(n) = n - 1 �C worst(n) = 2Cworst(n/2) + n - 1 for n > 1, Cworst(1) = 0 �n = 2^k: C worst(n) = n log2 n - n + 1

​

Using Masters Theorem

​

T(n)=2t(n/2)+f(n) = 2t(n/2)+n-1

a = 2 b=2 d=? f(n)= n-1 therefor f(n)=(n-1)^1 Therefore d=1

a==b^d Therefor T(n)=n^d*log2n=nlogn

​

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

​

ALGORITHM Quicksort(A[l..r])

{

//Input: Subarray of array A[0..n - 1],

//defined by its left and right

// indices l and r

//Output: Subarray A[l..r]

//sorted in nondecreasing order

if l < r

s ←Partition(A[l..r])

//s is a split position

Quicksort(A[l..s - 1])

Quicksort(A[s + 1..r])

} �

ALGORITHM HoarePartition(A[l..r])

//using the first element as a pivot

//Output: Partition of A[l..r], with the split position returned as this function’s value

p ← A[l]

i ← l;

j ← r + 1

repeat

repeat

i ← i + 1

until A[i] ≥ p

repeat

j ← j - 1

until A[j] ≤ p

swap(A[i], A[j])

until i ≥ j

swap(A[i], A[j])

//undo last swap when i ≥ j

swap(A[l], A[j])

return j �

Cbest(n) = 2Cbest(n/2) + n

for n > 1, Cbest(1) = 0.

Using Master Theorem

T(n)=nlogn

Multiplication of Large Integers

23 = 2 . 10^1 + 3 . 10^0 and

14 = 1 . 10^1 + 4 . 10^0.

23 ∗ 14 = (2 . 10^1 + 3 . 10^0) ∗ (1 . 10^1 + 4 . 10^0)

= (2 ∗ 1)10^2 + (2 ∗ 4 + 3 ∗ 1)10^1 + (3 ∗ 4)10^0.

2 ∗ 4 + 3 ∗ 1 = (2 + 3) ∗ (1 + 4) - 2 ∗ 1 - 3 ∗ 4.

For any pair of two-digit numbers a = a1a0 and b = b1b0, their product c can be computed by the formula

c = a ∗ b = c2*10^2 + c1*10^1 + c0,

Where

c2 = a1 ∗ b1 is the product of their first halves,

c0 = a0 ∗ b0 is the product of their second halves,

c1 = (a1 + a0) ∗ (b1 + b0) - (c2 + c0)

the product of the sum of the a’s halves

the sum of the b’s halves minus the sum of c2 and c0. ����

Lets assume two big integers of n digits

a,b

We will determine two half of the digit

a=a1ao b=b1bo

Ex a=3456 =34*10^2 + 56 for n with 4 digits

Hence for n digit number a=a1*10^n/2+a0 and b=b1*10^n/2+b0

​

c = a ∗ b = (a1*10^n/2 + a0) ∗ (b1*10^n/2 + b0)

= (a1 ∗ b1)10^n + (a1 ∗ b0 + a0 ∗ b1)10^n/2 + (a0 ∗ b0) = c210^n + c1*10^n/2 + c0,

​

M(n) = 3M(n/2) for n > 1, M(1) = 1. n = 2^k yields

AVL TREES

AVL tree is a self-balancing binary search tree invented by

G.M. Adelson-Velsky and E.M. Lendis

In an AVL tree, the heights of the two sub-trees of a node may differ by at most one.

Due to this property, the AVL tree is also known as a height-balanced tree.

Balance factor = Height (left sub-tree) – Height (right sub-tree)

AVL tree stores an additional variable called the Balance Factor at every node.

Every node has a balance factor associated with it

A binary search tree in which every node has a balance factor of –1, 0, or 1 is said to be height balanced �Left-heavy : Balance factor is 1 ( Left side up by 1 level)

Right-heavy : Balance factor is -1 ( Right side is up by 1 level)

Critical node is the nearest ancestor node on the path from the inserted node to the root whose balance factor >1 or <-1

When New Node is inserted if the Balance factor does not change , the Tree is retained as It is:

If the balance factor after Inserting New Node is not 1,0 or -1 we change the arrangement of Nodes Through Rotations

LL rotation The new node is inserted in the left sub-tree of the left sub-tree of the critical node.

RR rotation The new node is inserted in the right sub-tree of the right sub-tree of the critical node.

LR rotation The new node is inserted in the right sub-tree of the left sub-tree of the critical node.

RL rotation The new node is inserted in the left sub-tree of the right sub-tree of the critical node

R0 Rotation: Performed to delete a node which has balance factor 0

( Similar to LL rotation)

R1 Rotation: Is applied to delete a node having balance factor 1

R-1 Rotation: Is applied to delete a node having balance factor -1 close to critical node Similar to LR Rotation

2-3 Trees

A 2-3 tree is a tree that can have Two Types of nodes of 2-nodes and 3-nodes

A 2-node contains a single key K and has two children: the left child whose keys are less than K, and the right child whose keys are greater than K

​

3-node contains two ordered keys K1 and K2 : has 3 children

Left Child > K1 Middle Child between K1 and K2 Right child > k2

All its leaves of 2-3 Tree are on the same level

​

Heap and Heap Sort

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 (less than) mor equal to the keys in its children

�

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

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

Dynamic 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

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 variation of this approach. The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows. If a partially constructed solution can be developed further without violating the problem’s constraints, it is done by taking the first remaining legitimate option for the next component. If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered. In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option.

​

n-Queens Problem�As our first example, we use : the n-queens problem. The problem is to 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. For n = 1, the problem has a trivial solution, and it is easy to see that there is no solution for n = 2 and n = 3.

So let us consider the four-queens�problem and solve it by the backtracking technique �