1.

int search(int arr[], int n, int x)

2. {
3. int i;
int k= 5;
4. for (i = 0; i < n; i++)
5. {
for (j= 0;j<n;j++)
{
if (arr[i] == x)
}}
return i;
7. return -1;
8. }
 Advanced Algorithms
• What are algorithms
• Why do we need them
• How to evaluate them (Which is better etc)
• How to represent them in terms of
effectiveness
 Growth of Functions
One of the important criteria in evaluating
algorithms is the time it takes to complete a job.

The quantities often used for the estimate are the

worst case execution time,
and average execution time of an algorithm,

and they are represented by the number of some

key operations executed to perform the required
computation.
 Evaluation of Algorithms
• To have a meaningful comparison of
algorithms, the estimate of computation time
must be
– independent of the programming language,
– compiler, and computer used;
– must reflect on the size of the problem being
solved;
– must not depend on specific instances of the
problem being solved
 Asymptotic notation
The notations 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, . . .}.
Such notations are convenient for describing the
worst-case running-time function T(n), which is
usually defined only on integer input sizes.
However can be extended on real numbers as
and when required.
 Type of Asymptotic notation
• Big – Oh ( Represented by capital ‘O’)
– Like we say O(n)
• Big-Omega or (omega )notation. Written as
Ω (n)
• Theta Notation written as Θ(n)
• Little-O Notation: o(n)
• Little Omega Notation : ω(n)
 Big –oh ( O notation)
• The O (pronounced big-oh) is the formal method of
expressing the upper bound of an algorithm's
running time.
• Meaning It's a measure of the longest amount
(maximum) of time it could possibly take for the
algorithm to complete.
• More formally, for non-negative
functions, f(n) and g(n), if there exists an
integer n0 and a constant c > 0 such that for all
integers n > n0 , f(n) ≤ cg(n), whenever n > n0
• then f(n) is Big O ofg(n). This is denoted as
"f(n) = O(g(n))"
 Elements of Greedy Algorithms
• A greedy algorithm always makes the choice that
looks best at the moment
• Key point: Greed makes a locally optimal choice
in the hope that this choice will lead to a globally
optimal solution
• Note: Greedy algorithms do not always yield
optimal solutions, but for SOME problems they do
Examples: – Minimum Spanning Tree (Kruskal’s
algorithm) – Optimal Prefix Codes (Huffman’s
algorithm)
Activity selection Problem
 Huffman Codes

needed to encode a message

A = { a, b, c, d, e, f }
F = { 9 8 6 3 15 2 }
 abcdef
26 +17
= 43

ab
cfde 17
26

e a b
15 9 8

This is the required Huffman Tree

 Now creating Huffman codes
Write the codes for each
Staring from the root
Alphabet starting from Assign ‘0’ to left node
abcdef
the root
26 +17
And ‘1’ to right node
0 = 43
1
ab
cfde 17
26
1 0 1
0
e a b
0 1 15 9 8
Huffman Codes
a : 10
0 1 b : 11
c : 001
d : 0001
e : 01
f : 0000
• A { a, b, c, d, e, f}
• F { 2, 8, 3, 7, 9, 4}
• a= 0110, 0010, 0000, 1111
• b=
• c=
• d=
• e=
• f=
Solution
 Activity selection problem
• You are given n activities with their start and
finish times.
• Select the maximum number of activities that
can be performed by a single person, assuming
that a person can only work on a single activity
at a time.
• The Activity Selection Problem is an optimization
problem which deals with the selection of non-
conflicting activities that needs to be executed by a
single person or machine in a given time frame.
 Consider the following 6 activities.
Activities= {a, b, c, d, e, f}
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
1. Sort the activities according to their finishing time
(smallest finish time first)
2. Select the first activity from the sorted array and print it.
3. Do following for remaining activities in the sorted array.
a) If the start time of this activity is greater than or
equal to the finish time of previously selected activity then
select this activity and print it.
The selected activities are : {a, b, d, e}
Example 1
 Solution

• a2, a3, a5, a6

 Example 2
A list of different activities with starting and ending times.
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
A1, A2, A3, A4, A5, A6

A2, A3, A5, A6

Example 3
 Minimum Spanning Tree (Kruskal Algorithm)

• 1. Sort all the edges in Increasing order of

their weight.
2. Pick the smallest weight edge. Check if it
forms a cycle with the spanning tree formed
so far. If cycle is not formed, include this
edge. Else, discard it.
3. Repeat step#2 for the remaining edges.
Example 1
Pick edge 0-1: No cycle is formed, include
it.
Example 2
 Elements of Dynamic Programming
• Dynamic programming, like the divide-and-conquer
method, solves problems by combining the solutions to
subproblems ( "Programming" in this context refers to a
tabular method, not to writing computer code.)
• divide-and-conquer algorithms partition the problem into
independent subproblems, solve the subproblems
recursively, and then combine their solutions to solve the
original problem.
• In contrast, dynamic programming is applicable when
the subproblems are not independent, that is, when
subproblems share subsubproblems.
•A dynamic-programming algorithm solves each subsubproblem just once and
then saves its answer in a table, thereby avoiding the work of recomputing the
answer every time it solves each subsubproblem
• Dynamic programming is typically applied to optimization
problems.
• In such problems there can be many possible solutions.
• Each solution has a value, and we wish to find a solution
with the optimal (minimum or maximum) value. We call
such a solution an optimal solution to the problem.
• The development of a dynamic-programming algorithm can be
broken into a sequence of four steps.
• 1. Characterize the structure of an optimal solution.
• 2. Recursively define the value of an optimal solution.
• 3. Compute the value of an optimal solution in a bottom-up
fashion.
• 4. Construct an optimal solution from computed
information.
Longest Common Sub-Sequence
Example
 Steps
1. Create a Matrix of order (n+1 X m+1)
Where n= No. Of elements in X
m = No. Of elements in Y
 Step 2
Fill the first row and 1st column with ‘0’
 Step 3: Traverse row by row and do the
following
• Starting from ‘A’ we will match it with the corresponding
column value (i.e. ‘B’) . If different, leave blank, if same put
a (tilt arrow) at that corresponding cell.
• Continue for all the rows

0 up 0 up 0 up 1 1 left 1

1 1 left 1 left 1 up 2 2 left

1 up 1 up 2 2 left 2 up 2 up
1 1 up 2 up 2 up 3 3 left

1 up 2 2 up 2 up 3 up 3 up
Now for filling the blank cells we will
proceed as follows.
• For any particular blank cell: Look for the
value in the upper cell and the left cell of the
chosen cell.
• Whichever is the bigger value, we will put that
value in this chosen cell and put an arrow in
the direction of the bigger value OR
(depending upon which is bigger)
• However if the value are same we will put
upper cell value and put an arrow pointing
upwards in that cell
• Whenever we encounter a tilt arrow
• We will check the value in the upper diagonal
cell 0

(0+1)=1

• Add 1 to the value in the diagonal cell and put

the final result in your selected cell.
• Start from the last element of the matrix and move in the direction of the
arrows.
• Whenever you encounter a tilt arrow (encircle it )
• When you reach the beginning of the matrix, stop.
• Write the encircled elements of the row from top to bottom: B, C, B, A
• Find LCS for input Sequences
X =“ABCDGH” and
Y =AEDFHR”
• LCS for input Sequences
X= “AGGTAB”
and Y = “GXTXAYB”
• sequence X: ABCDEFG
sequence Y: BCDGK
 A B C D G H
0 0 0 0 0 0 0
A 0 1 1L 1L 1L 1L 1L
E 0 1U 1U 1U 1U 1U 1U
D 0 1U 1U 1U 2 2L 2L
F 0 1U 1U 1U 2U 2U 2U
H 0 1U 1U 1U 2U 2U 3
R 0 1U 1U 1U 2U 2U 3U
 A G G T A B
0 0 0 0 0 0 0
G 0
X 0
T 0
X 0
A 0
Y 0
B 0
 B C D G K
0 0 0 0 0 0
A 0
B 0
C 0
D 0
E 0
F 0
G 0
Algorithm
 Disjoint Sets Data Structure
Two sets are said to be disjoint if they have no
element in common
 Medians and Order Statistics
Order statistics
The ith order statistic of a set of ‘n’ numbers is
the i th smallest number in the set.
Total elements L= 9, n = 3
4, 6, 2, 71, 62, 23, 42, 8, 5
nth element from the back
Data Link to
next node
• We can, of course, select the ith order statistic
by sorting the input and indexing the ith
element of the output.
 Sorting Algorithms
Using Divide and Conquer Approach
• Merge Sort
• Quick Sort
 Merge Sort
• Is a type of divide and conquer algorithm
• Is given by the recurrence function
T(n) = 2 T( n/2) + n
Basic Steps of Merge sort are
1. Divide an array A into sub-arrays B and C
2. Sort sub-array B recursively : You get sorted
sub-array B
3. Sort sub-array C recursively : You get sorted
sub-array C
4. Combine (merge) B and C to get the final
sorted array A
 Merge Sort
1. Divide Step
• If a given array A has zero or one element, simply return;
it is already sorted.
• Otherwise, split A[p .. r] into two sub-arrays A[p .. q]
and A[q + 1 .. r], each containing about half of the
elements of A[p .. r]. That is, q is the halfway point
of A[p .. r].
2. Conquer Step
• Conquer by recursively sorting the two sub-arrays A[p .. q]
and A[q + 1 .. r].
3. Combine Step
• Combine the elements back in A[p .. r] by merging the two
sorted sub-arrays A[p .. q] and A[q + 1 .. r] into a sorted
sequence.
 Pseudo code for the algorithm
• Input: An unsorted array ‘A’ with first = 1 , last = n;
• Output: Sorted Array ‘A’
• Procedure: Mergesort( A[first ...... Last])
• Begin
• If (first = = last) then return A[first]
• Else
• mid= (first + last)/2
• For (i=1 to mid)
• { B[i] = A[i] }
• For (i= mid+1 to n)
• { C[i]= A[i]) }
• Mergesort (B[1 .... mid])
• Mergesort(C[mid+1 ..... n] )
• Merge (B,C, A)
• Begin :
Merge(B,C,A)
• i= 1 // counter for array B • If ( i > m ) then // A is exhausted
• While ( k < = m + n ) do
• j= 1 //counter for array C
• { A[k] = C[j]
• k=1 // counter for array A • j++
• m= length(B) • k=j+1
• n= length(C) • k++
• While(( i < = m) and (j < = n)) • }
do • Else if ( j > n ) // B is exhausted
• While ( k < = m + n ) do
• { If (B[i] < C[i]) then
• { A[k] = B[j]
• { A[k]= B[i] • i++
• i = i+1 } • k=i+1
• Else • k++
• { A[k] = C[i] •}
•}
• j=j+1 }
• k = k+1}
Merge Sort
Working of Merge Sort
 Quick Sort
• This algorithm also uses divide and conquer
approach
• However, Instead of simple dividing the array
into two parts, it uses a pivot element to
divide the array into two parts.
Basic idea of quick sort
 Q

Q
P: Pivot Element
i=0
j=1

Check whether arr[ j ] < Pivot

If NO, increment j by 1
Check whether arr[ j ] < Pivot
If YES, increment i by 1
Swap arr[i] with arr[j]
i is incremented by 1
arr[i] swapped with arr[j]
 Dijkstra Algorithm
• This is an algorithm for finding the shortest
path starting from a single source.
Step 1: Make the cost of start node as 0
(zero) and make the cost of all the other
nodes as (infinity)
Step 2: Now from the start node, select the adjacent
node (here we have ‘b’ and ‘c’ as the neighbours of ‘a’)

• Find the cost of going from a to b and a to c as

follows
a to b = cost of a + cost of edge (ab) = 0 + 4 = 4
a to c = cost of a + cost of edge(ac) = 0+ 2 = 2
Now compare these cost with already assigned
cost of node b and c respectively.
Now update node ‘b’ with cost = 4
And update node ‘c with cost = 2
(as 4, 2 are less than infinity)
Now from node b and c, chose the one
with smaller cost and update the cost of
its neighbours
 We have chosen ‘c’ and its neighbours are ‘b’ ‘d’
and ‘e’

• So update the vertices b, d and e

• Cost of b = cost of ‘c’ + cost of edge cb (2+1) = 3, which is <
earlier cost of b (which is 4 , hence update). Similarly for ‘d’
and ‘e’ as well
 Now we have the nodes ‘b’, ‘d’ and ‘e’. Choose the
smallest among them.
‘b’ = 3, d= 10 and e= 12. Therefore we will choose ‘b’

Now we have ‘e’ and ‘d’ . So we will choose ‘d’

• After the above step , we have ‘e’ and ‘z’ so
we will choose ‘e’ and update the cost
 So finally we get

This is the required single source shortest path

 Example 2

T=8
X=9
Y=5
Z=7
Solution
B= 5
Example 2
A=2
C= 6
D=7
Solution
 Bellman Ford Algorithm
• This is also a single source shortest path algorithm
• The difference between this and dijikstra algorithm is that, it can
also works in case the graph has negative edges
• Bellman-Ford algorithm returns a boolean value indicating
whether or not there is a negative-weight cycle that is reachable
from the source. If there is such a cycle, the algorithm indicates
that no solution exists. If there is no such cycle, the algorithm
produces the shortest paths and their weights.

• The algorithm returns TRUE if and only if the graph contains no

negative-weight cycles that are reachable from the source.
 All pair Shortest Path
• Floyd Warshall Algorithm
We will first fill the S table :

1. Fill‘-’ in (1,1), (2,2), (3,3), (4,4) (diagonal cells)

2. Fill all the cells in column 1 with ‘1’
3. Fill all the cells in column 2 with ‘2’
4. Fill all the cells in column 3 with ‘3’
5. Fill all the cells in column 4 with ‘4’
We will fill the D table :

1. Fill ‘-’in (1,1), (2,2), (3,3), (4,4)

(diagonal cells)
• Proceeding in the same way we will fill all the cell with the
exact edge weight. If so path exists between any two pair of
vertices we will put (infinity)
• After filling all the cells of the ‘D’ table it will look like
• And your D0 And S0 completes here
 Time to create D1 and S1

We will fill D1 and S1 using

D0 and S0
For filling rest of the entries
 1
1

Since the value of C23 in D1 is same as in D0 . Therefore fill

Therefore fill C23 and C32 with 1

 3
2
 5 4

5 2
 3 4
3 3
 3 2

3 2
 7 2

7 2
 3 4
3 3
Proceeding in the same way we find
D3 and S3
Now using D3 and S3 we will find the shortest path
Continuing in the same way we get
the final table as
• There are 19 balls which are identical in looks,
shapes and sizes. However one ball has less
weight than the other balls. What is the
minimum number of comparison in which you
can identify the ball when you have a
weighing balance.
9 9

(L) (R)
4 4
• There is a farmer who wishes to cross a river but
he is not alone. He also has a goat, a wolf, and a
cabbage along with him. There is only one boat
available that can support the farmer and either of
F,W,G,C
the goat, wolf or cabbage. So at a time, the boat
can have only two objects (farmerFG and one other).
F
• But the problem is, if the goat and wolf are left
FC
alone (either in the boat or onshore), the wolf will
eat the goat.
FG Similarly, if the Goat
C and cabbage are
left alone, then goat will eat the cabbage. How
C,F W
many minimum trips for the farmer to get
everything on the other side F,G,C,W
(without any harm)?
Crossing the river counts as one trip.
• There are 1000 wine bottles. One of the bottles
contains poisoned wine. A rat dies after one
hour of drinking the poisoned wine. How many
minimum rats are needed to figure out which
bottle contains poison in hour.
• A dealer has 1000 coins and 10 bags. He has
to divide the coins over the ten bags so that
he can make any number of coins simply by
handing over a few bags. How must divide his
money into the ten bags?
• You are blindfolded and 10 coins are place
in front of you on table. You are allowed to
touch the coins, but can’t tell which way
up they are by feeling them. You are told
that there are 5 coins head up, and 5 coins
tails up but not which ones are which.
• Can you make two piles of coins each
with the same number of heads
up? You can flip the coins any number of
times.
• 17 COINS
• TWO PLAYER GAME
• EACH CHANCE , A PLAYER CAN TAKE (1,2,3,OR MAX 4 COINS)
• HE CANNOT PASS THE CHANCE
• THE PLAYER WHO HAS THE LAST CHANCE TO PICK THE COIN IS
THE WINNER.

P1 P2

4 2
1 2
3