ADA
algo solution maual
1
Any algo whose worst running time is lowest, is least dependent on the initial order of input (or in
general, is least dependent on anything at all - since we've assuming the worst that could ever
happen anyways )
So amongst comparison sorts, the running time of a merge sort or a heap sort would be least
dependent (or as I said, not at all dependent) on your initial input ordering .
2I
t needs O(n) time and O(1) space. Just a minor modification of the basic algorithm to determine
max element in an array.
.... max = A[0]
.... count = 1
.... for(i = 1; i < N; i++)
..... begin
...... if(A[ i ] == max)
........... ++count
...... else if(A[ i ] > max)
........... max = A[ i ]
........... count = 1 //mark this step - found a new max element hence reset count
...... endif
.... endfor
.... print "Max value = " max
.... print "Number of occurences = " count
Time = O(n)
Space = O(1)
3.
time complexity of code
for(int i=0;i < =n;i++)
for(j=0;j < =log(i);j++)
printf("puneet")
printf executes for
log(1) + log(2) + log(3) + log(4) + log(5) + ...log(n) times
Page 1
ADA
= log (n!) times
so complexity is O(log(n!))
think u'll have to take into account the complexity of the function log(i) here coz its calculated
from the series
ln(1+x)=x-(x^2/2)+(x^3/3)-(x^4/4)+...
now obviously this is not linear time, and it depends on the accuracy till which the maths library
calculates it. Sot i dont think he complexity is O(log(n!)).
printf executes for
(log(1) +1)+ (log(2)+1) + (log(3)+1) + (log(4)+1) + ...(log(n)+1) times
= (n+log (n!)) times
still the complexity is O(log(n!)) becoz log(n!) is greater than n for larger values of n.eg if base of
log is "e" then for n > =6 log(n!) is greater than n. if base of log is 10 then for n > =25 log(n!) is
greater than
4.for(i=0;i < =n*n;i++)
for(j=i;j < =n/2;j++)
printf("x");
I think its O(n^3)...And moreover there isn't any hidden landmine in it as well
break outer loop into 2 parts
1) 0 < i < =(n/2) (usual nested loop)
2) n/2 < i < =n*n (inner loop doesn't work)
so both r O(n^2)
5ques: >
the input is a set s containing n real number sorted in increasing order and a real number x we
have to develop algo to know wheather there are two elements of s whose sum is exactly x
use linear search
steps:
1. move in the array and stop at the point where u get an element > =x
2. now subtract that number from x and search the number in the array to the left from start..
3. now move backwards from the number(where we stopped) and repeat the same for all other
Page 2
ADA
let us say the array is 1,2,5,6,7,8,19,20,34,36,45,76,86
we have to search for the sum X=38
1. start from 1....stop at 36
2. now search for the number 38-36=2 in the left side of the array
3. suppose if 2 was not there....then move backwards from 36 to 34 and repeat step 2
or
have two pointers one at the beginning and one at the end.....
add the elements pointed to , move the last pointer if the sum > x or else move the first pointer
6 ques:decimal to binary conv without loop
Use recursion.
binary(unsigned int n)
{.
....if(n > =2)
..........binary(n/2);
.....printf("%u",n&1);
}
q:7suppose we are given 3 sequences a,b,c of length n,m,p all soted we have to merge this into d of
length m+n+p,how can we generalize this for say n sequences,what is the complexity of this??
ans:
Kind of merge sort..
take two sorted array (size m and n).. merge them into a one sorted array(size m+n)
repeate this process recursively till u get a single sorted array..
the method will b lik described above
and its complexity should b (n-1) times complexity of a single merge between two lists.
repeate this process recursively till u get a single sorted array..
> > > > > another approach
Better way of doing it for n sequences is to construct a heap of n elements which contain the min
elemets from the n sequences.If an element is removed from the heap, add the new element from
the sequence from which it is removed.
If each sequence is very long,this method is very efficient as u read the element into the memory
only once. (external mem algos)
Time Complexity will be O(nm log n) -- > each sequence has m elements,n sequences
Page 3
ADA
ques8 :suppose we have to draw a set of closed curves c1,c2....,cn in the plane according to th
below rules:
1. no curve intersect itself
2.c1 is drawn arbitarily
3 for every i > =2.ci intersects each of c1,c2,...,ci-1 in exactly two distinct point
4no three curves meet at a single point.
let r(n) denote the number of regions in the plane defined by constructing n closed curves by the
above rules.how can we dervie grneral recurrence relation for r(n) in terms of r(n-1) and how can
we compute r(1) and r(20)
ans:
r(n) = r(n-1) + 2 * (n-1)
r(1) = 1
basically, when a new curve is added, each already existing curve (total n-1 in number) are
bisected in two regions. This gives additional n-1 regions. Further n-1 more regions are formed
which share boundaries with the new curve.
Solving above recurrnce relation gives
r(n) = n(n-1) + 1
which gives r(20) = 381
ques:9 let x and y be strings of symbols from some alphabet .consider the operations of deleting a
symbol from x,inserting a symbol into x and replacing a symbol of x by another symbol ,how can
we design algo to find the minimum number of such operation needed to transform x into y..
ans:the edit distance between two strings of characters is the number of operations required to
transform one of them into the other. There are several different algorithms to define or calculate
this metric:
Hamming distance
Levenshtein distance
Damerau-Levenshtein distance
Jaro-Winkler distance
Wagner-Fischer edit distance
Ukkonen
Hirshberg
the Hamming distance between two strings of equal length is the number of positions for which
the corresponding symbols are different. Put another way, it measures the minimum number of
substitutions required to change one into the other, or the number of errors that transformed one
string into the other.
1011101 and 1001001 is 2.
Page 4
ADA
algo:
The following C++ function will compute the Hamming distance of two integers (considered as
binary values, that is, as sequences of bits). The running time of this procedure is proportional to
the Hamming distance rather than to the number of bits in the inputs.
int hamdist(int x, int y)
{
int dist = 0, val = x^y;
while(val)
{
++dist;
val &= val - 1;
}
return dist;
}
ques:10
how many comparisons are required for finding both largest and smallest elements in aset of n
elements,what could be the algo for that
ans:
Number of addition operation is i guess (n-2).. Correct me if i am wrong.
MIN-MAX(A) //assume n is odd
min=max=A[1]
for i=2 to length[A] step 2
do if A[.i] < A.[i+1]
then if min > A[.i]
then min=A[.i]
if max < A[.i+1]
then max = A[.i+1]
else if min > A.[i+1]
then min = A[.i+1]
if max < A[.i]
then max = A[.i]
return min, max
#pairs: [n/2]
#comparisons/per pair:3
# total comparisons: 3 [n/2],
i.e., [3n/2] -2.
Similarly, write the code
for n being even. The # total
comparisons is 3n/2-2, i.e.,
Page 5
ADA
[3n/2] -2.
ques:11 is there any way to evaluate the polynomial - >
summation with condition 1 < =i < =j < =n xixj=x1x2+x2x3+.......+x(n-1)xn
with fewer then n-1 multiplication's and 2n-4 additions
ANS:
1 < = i < j < = n
then expression is x1(x2+...+xn) + x2(x3+...+xn) + ... + x(n-1)xn,
which would require n-1 multplication and 2n-4 addition according to following pseudo-code.
temp_sum = xn
result = x(n-1) * xn
for i= (n-1) to 2,
temp_sum += x(i)
result += temp_sum * x(i-1)
end_for
As far as reducing number of operations is concerned, I do not know. I tried rewriting original
expression as 0.5 * ( ( x1 + x2 + ... + xn )^2 - ( x1^2 + x2^2 + ... + xn^2 ) ), but it doesn't help.
so try on your own
ques:12
to find the kth smallest element in a set of n elements,how many comparisons are required ??,what
is the algo for that??
ans:
Well calculations i am not sure. but this is the age old strategy.
This algorithm is modificaiton of quick sort.. Choose a pivot and apply the partition step of the
algorithm.
If position of the pivot is k. u are done
If position of the pivot in the array is greater than k then repeat this algorithm on the left
partition.
If position of the pivot is less than k then repeat the algorithm on the right partition.
Let me give a shot at number of comparisons. Let assume that number are uniformly distributed
in the array. Then first iteration will take n comparison. here we can assume that both the
partitions are of roughly same size. And we are going to throw out one partition. So number of
elements to be tackled in the next iteration are n/2 and thats max num of comparisons .
So total comparison in this case will be less than
n + n/2 + n/4 ....log n terms. < = n( 1 +1/2 + 1/4 ...... upto infinity) =2n.
so i think on an average we shld be done in less than 2n comparisons.
i overlooked the title, the worst case in this algorithm will be if the array is already sorted and u
are asking me to find smallest element. in that case i will take n^2 ops.. so here this strategy may
not be good (ofcourse provided i am choosing the pivot as always the last element. but i think this
problem can a be avoided if i choose my pivot randomly.)
Page 6
ADA
> > another use median as pivot. worst case=O(n)
ques13:given three arrays of n real numbers i.e +ve or -ve,we have to determine if there are three
numbers one from each array whose sum is 0,what is the complexity of that??
ans:
if u consider a naive algo it can be done in O(n ^ 3 ) time.. take one element from each of the
arrays..
that will have 3 loops.. so O(n ^ 3) time..
but u can do in O(n lgn) time like this..
1)sort each of the arrays in O(n lgn).
2)merge all in a 3n array this can be done in O(n) time.
3)then maintain 2 arrays one with -ve other with +ve elements
4)for each of the +element in the array do binary search in -ve array for its negetive counterpart.
(also as there can be more than one no like this check the neighbouring values too.)
this step will take o(n lgn) time that is o(lgn) time for each of the +n elements
another view i think::
in O(n ^ 2 logn) we may find
sort 3 arrays
for each element (let say x) in array1
{
for each element (let say y) in array 2
binary search -(x+y) in array 3
for each element (let say z) in array 3
binary search for -(x + z) in array 2
}
repeat this
This can't be done in better than O(n^2) time (& O(1) space). There is a flaw in line (4) of
algorithms. Think properly if you can.
q:14let m be an mxn matrix of of 0 and 1,how can we find a smallest sxn submatrix S of m such
that if m(i)(j)=1 then for some 1 < k < s.. S(k,j)=1,also what is the worst time it takes..
ans:this is a standard problem in computer science
ANS:
http://en.wikipedia.org/wiki/Set_cover
The set covering problem is a classical question in computer science and complexity theory. As
input you are given several sets. They may have some elements in common. You must select a
minimum number of these sets so that the sets you have picked contain all the elements that are
Page 7
ADA
contained in any of the sets in the input. It was one of Karp's 21 NP-complete problems shown to
be NP-complete in 1972.
More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose
union is . In the set covering decision problem, the input is a pair and an integer k; the question is
whether there is a set covering of size k or less. In the set covering optimization problem, the input
is a pair , and the task is to find a set covering which uses the fewest sets.
The decision version of set covering is NP complete, and the optimization version of set cover is NP
hard.
Set covering is equivalent to the Hitting set problem. It is easy to see this by observing that an
instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by
vertices on the left, the universe represented by vertices on the right, and edges representing the
inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices
which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the
left-vertices using a minimum subset of the right vertices. Converting from one problem to the
other is therefore achieved by interchanging the two sets of vertices.
The set covering problem can be seen as a finite version of the notion of compactness in topology,
where the elements of certain infinite families of sets can be covered by choosing only finitely
many of them.
q:15
suppose we are given an input ,points in the plane a,b,c,d,we wish to place four circles centered at
each of these points,so that no two circles overlaps each other and the avg radius is as large as
possible,how can we design algo for this,what is it's complexity...
ANS:
this is an optimization problem
max r1+r2+r3...+rn
s.t
r1+r2 < = d12
r2+r3 < = d23
r1+r3 < = d13 nd so on
Use simplex algorithm to get the optimal solution.
I dont know if this can be done using some sort of dynamic programming or greedy algorithm
approach.
question:
Page 8
ADA
question::16
You have an array of 2n+1 elements, in which each but one element is present twice.
You have to find out the remaining 1 element.
ans:
Sort the numbers using some sort algo that takes O(n log n).
Then use something like this
for(i = 0;i < 2n;i=i+2)
{i
f(a == a[i+1]
i++;
else
return a;
}
return a[2n];
or
try this
for( i = 0,xor = 0 ;i < 2*n + 1 ;++i)
xor ^= x[..i..];
return xor;
quest:17
solution of this recurrence
t(n)=t(n/2)+bigoh(square root of n) for n > 3 else t(n)=1
ANS:
Page 9
ADA
well the solution to this recurrence is theta_of(sqrt(n))..........i just guessed it and proved using
substitution metho
> > > > T(n)=c1*sqrt(n)/sqrt(2)+c2*sqrt(n)
> > > > T(n)=(c1+c2)*sqrt(n)
> > > > T(n)=(c1+c2)*sqrt(n) < =c*sqrt(n)
if we choose c1=1 c2=1 and c=10 the above inequality holds...........end_of_proof..............
the lower bound can be prooved similarly........
> > > another view
lower bound cannot be proved. theta(sqrt(n)) is incorrect. problem statement has bigoh.
counter-example: t(n) = t(n/2) + 1
ower bound : theta(log(n))
Q:18
evaluate big O ,omega and thita
int try(int n)
{i
f n < 3 return(1);
return(try(n-3) + try(n-1) - try(n-2));
}
void main(int m)
{i
nt n;
for(n=0;n < m;n++)
printf("\n%d",try(n));
}
ANS: > > > > > > > > > > > > >
he recurrence relation for above program could be possibly.....
T(n)=T(n-1)+T(n-2)+T(n-3)+O(1)
and this is multiplied by m times......so i guess answer should be O(m*n^2).........is it correct???
Page 10
ADA
Q: > > 19
suppose we are given multiplication of two polynomials a1*x raised to i1+a2*x raised to i2+...)
and b1* x raised to j1+b2* x raised to j2.....
in which the coefficients of the answers c1* x raised to i1+j1+...) are generated in order as the
input coefficients are being multiplied..
how can we design algo for this in most efficient time and space.?.
ANS:
use divide and conquer u can do it in O(n power logn base 3)
or
FFT is the fastest known method. Polynomial multiplication is convolution of the series of
coefficients. This should be O(nLogn)
q20
suppose you are given n men and n women and two n x n arrays p and q such that
p(i,j) is the preference of man i for woman j and q(i,j) is the preference of woman i for man j,how
can we design algorithm which finds a pairing of men and women such that the sum of product is
maximized...
ans:
G1 = (V1, E1)
G2 = (V2, E2)
[1] With the help of two matrices p and q (both being directed and weighted) convert them to
undirected graph.
u - > v = w1
v - > u = w2
then undirected edge (u, v) should have weight
w(u, v) = w1*w2
Note: if (u, v) isn't belongs to E1 (or E2) then it's directed weight should be taken as zero.
i.e. w1(u, v) = 0
[2] Now run MST with a little difference. You choose the safe edge with highest weight.
q: quick sort with two partition
ANS:
Page 11
ADA
A very naive way can be ...
Choose 2 random elements x and y as partitions.
Make sure that x != y
Use the partition value 'x' and apply the standard partitioning algorithm.
Suppose after running this algorithm, 'x' is placed at index 'i'.
Now, either y < x or y > x.
So, now you can apply the same standard partitioning algorithm on the subinterval
[0, i-1] (if y < x) or [i+1, N] (if y > x)
So, now you get 3 subsets, instead of 2. Apply quicksort recursively on those 3 subsets too. Not
sure whether this will be more or less efficient than the actual QuickSort.
I will try to program this in my leisure time, and will let you know.
In the meantime, I am sure other algorithm wizards can definitely come up with better versions
analysis:
BTW, I dont think my method achieves any improvement.
For average case,
T(n) = 3n/2 + 3T(n/3)
In each pass, O(n) time for partition using 'x' and O(n/2) for partition using 'y'
This gives
T(n) = 1.5 nlogn + n
So, we should think of developing a partitioning algorithm which implements positioning both 'x'
and 'y' in O(n) time in 1 go.
I don't think there is any use of doing QuickSort using 2 partition elements.
Consider this case - suppose the size of array to be sorted is 1 million (1,000,000).
You choose x and y as partition elements, and after partitionning, it is found that there are say less
than 5 elements between x and y.
So, this will only worsen the performance as compared to standard QuickSort.and rem the quick
sort is the algo used for sorting very large data say just said....
Page 12
ADA
Q > > > > >
suppose we are given sequence of n songs where the ith song is i subscript i min long,we want to
place all of the songs on an ordered series of Cd's(eg. cd1,cd2,.....,cdk),where each cd can hold m
min's,fuerthermore,the songs must be recorded in the given order spng1,song2,...,songn.no song
may be spilt across cd's,the goal is to determine how to place them on the cd's as to minimize the
number of cd's needed..,
how can we design efficient algorithm for this..
ANS:
This problem reminds me of the 0/1 knapsack problem
my question:
Let T be an array that contains n integers. An integer is a majority element in T if it appears
strictly more than n/2 times in T. Give an algorithm that can decide whether an array T contains a
majority element and if so find it. Your algorithm must run in linear time in the worst case.
ANS:
guess
????
here it is > >
This modification of quick sort:
Select a pivot randomly. run partition. Find the position of the pivot say p. calculate size of left
partition if it is greater than n/2 your then your majoriy element is likely in this part of the array.
repeat the algorithm in this part
but if left partion has length less than n/2 so the majority is likely to be in the right parition.
continue this alorithm on that partition.
This will go on till the partition size remamins staionary or drops below n/2. In first case u have
the majority element in second case u dont.
Since in each case we are working on only one parition this shld be done in o(n) time
use stack
if stack is empty
Page 13
ADA
push the element
if stack is not empty compare current element with stack top
if both r same push
else pop
finally
if there exists an element that is majority element
or by pruning also u can do it in linear time by only comparisions by taking another array
if ( median == min || median == max )
return median
else
return "NO"
In the worst case this could happen:
We find the pivot and it turns out to be the last element
e.g.
2 2 2 2 5 7 9
The next time you pick a pivot, in the worst case it turns out to be 7 (in this case)
so we continue this process.
This will be an O(n^2) algo.
Correct me if i'm wrong.
Finding the median involves sorting which is O(nlogn) for comparison sort algos. Unless you do
radix or bucket sort (for small n)
http://en.wikipedia.org/wiki/Selection_algorithm > > try this
If there is no space constraint then we can use hashtable to find it. Traverse each element in the
array. if this element is not present in Hashtable then place it in HT with count value 1 else
increment the count value of corresponding element. at last check the count value to find the Max.
Q:
how do we generailize huffma's algorithm to ternary codewards i.e codewards using 3 symbols
0,1,2..
ANS > > > > > > > > > > >
Page 14
ADA
what's the problem in this it is easy,extension of huffman's algo
simply apply the algo to make a new node
and according to priority queue keep on adding two trees frequencies
ya you will get a skewed tree if the frequencies of trees satisfies triangle inequality law
Q > > > > > > >
we are given all the numbers in a table
so that all -ve values precede all nonnegative values.the items need not be sorted completely,just
seprated b/w -ve and nonnegative,we have to degin algo for this with constraint that the sol should
require min.. number of comparisons...
ANS:
i guess it can be done in O(n).. the way we do partition in quick sort... only diff will be instead of
picking an element and then partiotionin it.. partition it wid respect to 0...
Page 15
algo solution maual
1
Any algo whose worst running time is lowest, is least dependent on the initial order of input (or in
general, is least dependent on anything at all - since we've assuming the worst that could ever
happen anyways )
So amongst comparison sorts, the running time of a merge sort or a heap sort would be least
dependent (or as I said, not at all dependent) on your initial input ordering .
2I
t needs O(n) time and O(1) space. Just a minor modification of the basic algorithm to determine
max element in an array.
.... max = A[0]
.... count = 1
.... for(i = 1; i < N; i++)
..... begin
...... if(A[ i ] == max)
........... ++count
...... else if(A[ i ] > max)
........... max = A[ i ]
........... count = 1 //mark this step - found a new max element hence reset count
...... endif
.... endfor
.... print "Max value = " max
.... print "Number of occurences = " count
Time = O(n)
Space = O(1)
3.
time complexity of code
for(int i=0;i < =n;i++)
for(j=0;j < =log(i);j++)
printf("puneet")
printf executes for
log(1) + log(2) + log(3) + log(4) + log(5) + ...log(n) times
Page 1
ADA
= log (n!) times
so complexity is O(log(n!))
think u'll have to take into account the complexity of the function log(i) here coz its calculated
from the series
ln(1+x)=x-(x^2/2)+(x^3/3)-(x^4/4)+...
now obviously this is not linear time, and it depends on the accuracy till which the maths library
calculates it. Sot i dont think he complexity is O(log(n!)).
printf executes for
(log(1) +1)+ (log(2)+1) + (log(3)+1) + (log(4)+1) + ...(log(n)+1) times
= (n+log (n!)) times
still the complexity is O(log(n!)) becoz log(n!) is greater than n for larger values of n.eg if base of
log is "e" then for n > =6 log(n!) is greater than n. if base of log is 10 then for n > =25 log(n!) is
greater than
4.for(i=0;i < =n*n;i++)
for(j=i;j < =n/2;j++)
printf("x");
I think its O(n^3)...And moreover there isn't any hidden landmine in it as well
break outer loop into 2 parts
1) 0 < i < =(n/2) (usual nested loop)
2) n/2 < i < =n*n (inner loop doesn't work)
so both r O(n^2)
5ques: >
the input is a set s containing n real number sorted in increasing order and a real number x we
have to develop algo to know wheather there are two elements of s whose sum is exactly x
use linear search
steps:
1. move in the array and stop at the point where u get an element > =x
2. now subtract that number from x and search the number in the array to the left from start..
3. now move backwards from the number(where we stopped) and repeat the same for all other
Page 2
ADA
let us say the array is 1,2,5,6,7,8,19,20,34,36,45,76,86
we have to search for the sum X=38
1. start from 1....stop at 36
2. now search for the number 38-36=2 in the left side of the array
3. suppose if 2 was not there....then move backwards from 36 to 34 and repeat step 2
or
have two pointers one at the beginning and one at the end.....
add the elements pointed to , move the last pointer if the sum > x or else move the first pointer
6 ques:decimal to binary conv without loop
Use recursion.
binary(unsigned int n)
{.
....if(n > =2)
..........binary(n/2);
.....printf("%u",n&1);
}
q:7suppose we are given 3 sequences a,b,c of length n,m,p all soted we have to merge this into d of
length m+n+p,how can we generalize this for say n sequences,what is the complexity of this??
ans:
Kind of merge sort..
take two sorted array (size m and n).. merge them into a one sorted array(size m+n)
repeate this process recursively till u get a single sorted array..
the method will b lik described above
and its complexity should b (n-1) times complexity of a single merge between two lists.
repeate this process recursively till u get a single sorted array..
> > > > > another approach
Better way of doing it for n sequences is to construct a heap of n elements which contain the min
elemets from the n sequences.If an element is removed from the heap, add the new element from
the sequence from which it is removed.
If each sequence is very long,this method is very efficient as u read the element into the memory
only once. (external mem algos)
Time Complexity will be O(nm log n) -- > each sequence has m elements,n sequences
Page 3
ADA
ques8 :suppose we have to draw a set of closed curves c1,c2....,cn in the plane according to th
below rules:
1. no curve intersect itself
2.c1 is drawn arbitarily
3 for every i > =2.ci intersects each of c1,c2,...,ci-1 in exactly two distinct point
4no three curves meet at a single point.
let r(n) denote the number of regions in the plane defined by constructing n closed curves by the
above rules.how can we dervie grneral recurrence relation for r(n) in terms of r(n-1) and how can
we compute r(1) and r(20)
ans:
r(n) = r(n-1) + 2 * (n-1)
r(1) = 1
basically, when a new curve is added, each already existing curve (total n-1 in number) are
bisected in two regions. This gives additional n-1 regions. Further n-1 more regions are formed
which share boundaries with the new curve.
Solving above recurrnce relation gives
r(n) = n(n-1) + 1
which gives r(20) = 381
ques:9 let x and y be strings of symbols from some alphabet .consider the operations of deleting a
symbol from x,inserting a symbol into x and replacing a symbol of x by another symbol ,how can
we design algo to find the minimum number of such operation needed to transform x into y..
ans:the edit distance between two strings of characters is the number of operations required to
transform one of them into the other. There are several different algorithms to define or calculate
this metric:
Hamming distance
Levenshtein distance
Damerau-Levenshtein distance
Jaro-Winkler distance
Wagner-Fischer edit distance
Ukkonen
Hirshberg
the Hamming distance between two strings of equal length is the number of positions for which
the corresponding symbols are different. Put another way, it measures the minimum number of
substitutions required to change one into the other, or the number of errors that transformed one
string into the other.
1011101 and 1001001 is 2.
Page 4
ADA
algo:
The following C++ function will compute the Hamming distance of two integers (considered as
binary values, that is, as sequences of bits). The running time of this procedure is proportional to
the Hamming distance rather than to the number of bits in the inputs.
int hamdist(int x, int y)
{
int dist = 0, val = x^y;
while(val)
{
++dist;
val &= val - 1;
}
return dist;
}
ques:10
how many comparisons are required for finding both largest and smallest elements in aset of n
elements,what could be the algo for that
ans:
Number of addition operation is i guess (n-2).. Correct me if i am wrong.
MIN-MAX(A) //assume n is odd
min=max=A[1]
for i=2 to length[A] step 2
do if A[.i] < A.[i+1]
then if min > A[.i]
then min=A[.i]
if max < A[.i+1]
then max = A[.i+1]
else if min > A.[i+1]
then min = A[.i+1]
if max < A[.i]
then max = A[.i]
return min, max
#pairs: [n/2]
#comparisons/per pair:3
# total comparisons: 3 [n/2],
i.e., [3n/2] -2.
Similarly, write the code
for n being even. The # total
comparisons is 3n/2-2, i.e.,
Page 5
ADA
[3n/2] -2.
ques:11 is there any way to evaluate the polynomial - >
summation with condition 1 < =i < =j < =n xixj=x1x2+x2x3+.......+x(n-1)xn
with fewer then n-1 multiplication's and 2n-4 additions
ANS:
1 < = i < j < = n
then expression is x1(x2+...+xn) + x2(x3+...+xn) + ... + x(n-1)xn,
which would require n-1 multplication and 2n-4 addition according to following pseudo-code.
temp_sum = xn
result = x(n-1) * xn
for i= (n-1) to 2,
temp_sum += x(i)
result += temp_sum * x(i-1)
end_for
As far as reducing number of operations is concerned, I do not know. I tried rewriting original
expression as 0.5 * ( ( x1 + x2 + ... + xn )^2 - ( x1^2 + x2^2 + ... + xn^2 ) ), but it doesn't help.
so try on your own
ques:12
to find the kth smallest element in a set of n elements,how many comparisons are required ??,what
is the algo for that??
ans:
Well calculations i am not sure. but this is the age old strategy.
This algorithm is modificaiton of quick sort.. Choose a pivot and apply the partition step of the
algorithm.
If position of the pivot is k. u are done
If position of the pivot in the array is greater than k then repeat this algorithm on the left
partition.
If position of the pivot is less than k then repeat the algorithm on the right partition.
Let me give a shot at number of comparisons. Let assume that number are uniformly distributed
in the array. Then first iteration will take n comparison. here we can assume that both the
partitions are of roughly same size. And we are going to throw out one partition. So number of
elements to be tackled in the next iteration are n/2 and thats max num of comparisons .
So total comparison in this case will be less than
n + n/2 + n/4 ....log n terms. < = n( 1 +1/2 + 1/4 ...... upto infinity) =2n.
so i think on an average we shld be done in less than 2n comparisons.
i overlooked the title, the worst case in this algorithm will be if the array is already sorted and u
are asking me to find smallest element. in that case i will take n^2 ops.. so here this strategy may
not be good (ofcourse provided i am choosing the pivot as always the last element. but i think this
problem can a be avoided if i choose my pivot randomly.)
Page 6
ADA
> > another use median as pivot. worst case=O(n)
ques13:given three arrays of n real numbers i.e +ve or -ve,we have to determine if there are three
numbers one from each array whose sum is 0,what is the complexity of that??
ans:
if u consider a naive algo it can be done in O(n ^ 3 ) time.. take one element from each of the
arrays..
that will have 3 loops.. so O(n ^ 3) time..
but u can do in O(n lgn) time like this..
1)sort each of the arrays in O(n lgn).
2)merge all in a 3n array this can be done in O(n) time.
3)then maintain 2 arrays one with -ve other with +ve elements
4)for each of the +element in the array do binary search in -ve array for its negetive counterpart.
(also as there can be more than one no like this check the neighbouring values too.)
this step will take o(n lgn) time that is o(lgn) time for each of the +n elements
another view i think::
in O(n ^ 2 logn) we may find
sort 3 arrays
for each element (let say x) in array1
{
for each element (let say y) in array 2
binary search -(x+y) in array 3
for each element (let say z) in array 3
binary search for -(x + z) in array 2
}
repeat this
This can't be done in better than O(n^2) time (& O(1) space). There is a flaw in line (4) of
algorithms. Think properly if you can.
q:14let m be an mxn matrix of of 0 and 1,how can we find a smallest sxn submatrix S of m such
that if m(i)(j)=1 then for some 1 < k < s.. S(k,j)=1,also what is the worst time it takes..
ans:this is a standard problem in computer science
ANS:
http://en.wikipedia.org/wiki/Set_cover
The set covering problem is a classical question in computer science and complexity theory. As
input you are given several sets. They may have some elements in common. You must select a
minimum number of these sets so that the sets you have picked contain all the elements that are
Page 7
ADA
contained in any of the sets in the input. It was one of Karp's 21 NP-complete problems shown to
be NP-complete in 1972.
More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose
union is . In the set covering decision problem, the input is a pair and an integer k; the question is
whether there is a set covering of size k or less. In the set covering optimization problem, the input
is a pair , and the task is to find a set covering which uses the fewest sets.
The decision version of set covering is NP complete, and the optimization version of set cover is NP
hard.
Set covering is equivalent to the Hitting set problem. It is easy to see this by observing that an
instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by
vertices on the left, the universe represented by vertices on the right, and edges representing the
inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices
which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the
left-vertices using a minimum subset of the right vertices. Converting from one problem to the
other is therefore achieved by interchanging the two sets of vertices.
The set covering problem can be seen as a finite version of the notion of compactness in topology,
where the elements of certain infinite families of sets can be covered by choosing only finitely
many of them.
q:15
suppose we are given an input ,points in the plane a,b,c,d,we wish to place four circles centered at
each of these points,so that no two circles overlaps each other and the avg radius is as large as
possible,how can we design algo for this,what is it's complexity...
ANS:
this is an optimization problem
max r1+r2+r3...+rn
s.t
r1+r2 < = d12
r2+r3 < = d23
r1+r3 < = d13 nd so on
Use simplex algorithm to get the optimal solution.
I dont know if this can be done using some sort of dynamic programming or greedy algorithm
approach.
question:
Page 8
ADA
question::16
You have an array of 2n+1 elements, in which each but one element is present twice.
You have to find out the remaining 1 element.
ans:
Sort the numbers using some sort algo that takes O(n log n).
Then use something like this
for(i = 0;i < 2n;i=i+2)
{i
f(a == a[i+1]
i++;
else
return a;
}
return a[2n];
or
try this
for( i = 0,xor = 0 ;i < 2*n + 1 ;++i)
xor ^= x[..i..];
return xor;
quest:17
solution of this recurrence
t(n)=t(n/2)+bigoh(square root of n) for n > 3 else t(n)=1
ANS:
Page 9
ADA
well the solution to this recurrence is theta_of(sqrt(n))..........i just guessed it and proved using
substitution metho
> > > > T(n)=c1*sqrt(n)/sqrt(2)+c2*sqrt(n)
> > > > T(n)=(c1+c2)*sqrt(n)
> > > > T(n)=(c1+c2)*sqrt(n) < =c*sqrt(n)
if we choose c1=1 c2=1 and c=10 the above inequality holds...........end_of_proof..............
the lower bound can be prooved similarly........
> > > another view
lower bound cannot be proved. theta(sqrt(n)) is incorrect. problem statement has bigoh.
counter-example: t(n) = t(n/2) + 1
ower bound : theta(log(n))
Q:18
evaluate big O ,omega and thita
int try(int n)
{i
f n < 3 return(1);
return(try(n-3) + try(n-1) - try(n-2));
}
void main(int m)
{i
nt n;
for(n=0;n < m;n++)
printf("\n%d",try(n));
}
ANS: > > > > > > > > > > > > >
he recurrence relation for above program could be possibly.....
T(n)=T(n-1)+T(n-2)+T(n-3)+O(1)
and this is multiplied by m times......so i guess answer should be O(m*n^2).........is it correct???
Page 10
ADA
Q: > > 19
suppose we are given multiplication of two polynomials a1*x raised to i1+a2*x raised to i2+...)
and b1* x raised to j1+b2* x raised to j2.....
in which the coefficients of the answers c1* x raised to i1+j1+...) are generated in order as the
input coefficients are being multiplied..
how can we design algo for this in most efficient time and space.?.
ANS:
use divide and conquer u can do it in O(n power logn base 3)
or
FFT is the fastest known method. Polynomial multiplication is convolution of the series of
coefficients. This should be O(nLogn)
q20
suppose you are given n men and n women and two n x n arrays p and q such that
p(i,j) is the preference of man i for woman j and q(i,j) is the preference of woman i for man j,how
can we design algorithm which finds a pairing of men and women such that the sum of product is
maximized...
ans:
G1 = (V1, E1)
G2 = (V2, E2)
[1] With the help of two matrices p and q (both being directed and weighted) convert them to
undirected graph.
u - > v = w1
v - > u = w2
then undirected edge (u, v) should have weight
w(u, v) = w1*w2
Note: if (u, v) isn't belongs to E1 (or E2) then it's directed weight should be taken as zero.
i.e. w1(u, v) = 0
[2] Now run MST with a little difference. You choose the safe edge with highest weight.
q: quick sort with two partition
ANS:
Page 11
ADA
A very naive way can be ...
Choose 2 random elements x and y as partitions.
Make sure that x != y
Use the partition value 'x' and apply the standard partitioning algorithm.
Suppose after running this algorithm, 'x' is placed at index 'i'.
Now, either y < x or y > x.
So, now you can apply the same standard partitioning algorithm on the subinterval
[0, i-1] (if y < x) or [i+1, N] (if y > x)
So, now you get 3 subsets, instead of 2. Apply quicksort recursively on those 3 subsets too. Not
sure whether this will be more or less efficient than the actual QuickSort.
I will try to program this in my leisure time, and will let you know.
In the meantime, I am sure other algorithm wizards can definitely come up with better versions
analysis:
BTW, I dont think my method achieves any improvement.
For average case,
T(n) = 3n/2 + 3T(n/3)
In each pass, O(n) time for partition using 'x' and O(n/2) for partition using 'y'
This gives
T(n) = 1.5 nlogn + n
So, we should think of developing a partitioning algorithm which implements positioning both 'x'
and 'y' in O(n) time in 1 go.
I don't think there is any use of doing QuickSort using 2 partition elements.
Consider this case - suppose the size of array to be sorted is 1 million (1,000,000).
You choose x and y as partition elements, and after partitionning, it is found that there are say less
than 5 elements between x and y.
So, this will only worsen the performance as compared to standard QuickSort.and rem the quick
sort is the algo used for sorting very large data say just said....
Page 12
ADA
Q > > > > >
suppose we are given sequence of n songs where the ith song is i subscript i min long,we want to
place all of the songs on an ordered series of Cd's(eg. cd1,cd2,.....,cdk),where each cd can hold m
min's,fuerthermore,the songs must be recorded in the given order spng1,song2,...,songn.no song
may be spilt across cd's,the goal is to determine how to place them on the cd's as to minimize the
number of cd's needed..,
how can we design efficient algorithm for this..
ANS:
This problem reminds me of the 0/1 knapsack problem
my question:
Let T be an array that contains n integers. An integer is a majority element in T if it appears
strictly more than n/2 times in T. Give an algorithm that can decide whether an array T contains a
majority element and if so find it. Your algorithm must run in linear time in the worst case.
ANS:
guess
????
here it is > >
This modification of quick sort:
Select a pivot randomly. run partition. Find the position of the pivot say p. calculate size of left
partition if it is greater than n/2 your then your majoriy element is likely in this part of the array.
repeat the algorithm in this part
but if left partion has length less than n/2 so the majority is likely to be in the right parition.
continue this alorithm on that partition.
This will go on till the partition size remamins staionary or drops below n/2. In first case u have
the majority element in second case u dont.
Since in each case we are working on only one parition this shld be done in o(n) time
use stack
if stack is empty
Page 13
ADA
push the element
if stack is not empty compare current element with stack top
if both r same push
else pop
finally
if there exists an element that is majority element
or by pruning also u can do it in linear time by only comparisions by taking another array
if ( median == min || median == max )
return median
else
return "NO"
In the worst case this could happen:
We find the pivot and it turns out to be the last element
e.g.
2 2 2 2 5 7 9
The next time you pick a pivot, in the worst case it turns out to be 7 (in this case)
so we continue this process.
This will be an O(n^2) algo.
Correct me if i'm wrong.
Finding the median involves sorting which is O(nlogn) for comparison sort algos. Unless you do
radix or bucket sort (for small n)
http://en.wikipedia.org/wiki/Selection_algorithm > > try this
If there is no space constraint then we can use hashtable to find it. Traverse each element in the
array. if this element is not present in Hashtable then place it in HT with count value 1 else
increment the count value of corresponding element. at last check the count value to find the Max.
Q:
how do we generailize huffma's algorithm to ternary codewards i.e codewards using 3 symbols
0,1,2..
ANS > > > > > > > > > > >
Page 14
ADA
what's the problem in this it is easy,extension of huffman's algo
simply apply the algo to make a new node
and according to priority queue keep on adding two trees frequencies
ya you will get a skewed tree if the frequencies of trees satisfies triangle inequality law
Q > > > > > > >
we are given all the numbers in a table
so that all -ve values precede all nonnegative values.the items need not be sorted completely,just
seprated b/w -ve and nonnegative,we have to degin algo for this with constraint that the sol should
require min.. number of comparisons...
ANS:
i guess it can be done in O(n).. the way we do partition in quick sort... only diff will be instead of
picking an element and then partiotionin it.. partition it wid respect to 0...
Page 15
