Combinatorics - Counting Problems

Bijection Approach

Bijection is one of the approach used in combinatorics Bijection is transforming some new problem to known problem set. Bijection with another problem set reduces new problem to similar known problem.

Bijection with [Bit]strings

Problem Move from cordinate (0,0) to (3,4) with only a move in either x or y at a time

Bijection with the string with 3X and 4Y where X is move in X direction and Y is move in Y direction
like XXXYYYY
possible arrangements with 3X and 4Y

C(7 3)

Problem 5 objects to be placed in 3 boxes
Bijection to string with 2X where X divides the string like 2X in string will divide string in 3parts or 3boxes

********X***********X******
box1              box2                 box3

and 5Y where Y represents object to be placed
like XXXXXYY
Total arrangements C(7 2)

Problem 15 books are on shelf in how many ways to choose 5 books so that no two chosen book is adjacent

Bijection with bit string with 5 1's and 6 0's where 0 is for selected book and 1 for not selected book

lets take some instances for selecting books
101010101000
1000010010001001
00101001010001

now question states that there must be atleast one not selected book (0) between each selected book (1)

so the required base patten is
101010101
or more appropiately
10⁺10⁺10⁺10⁺
that is there should be at least one 0 between two 1's

Now remaining books are 15 - 9 = 6

there can be others books before between and after this pattern like

101010101 000000 after this pattern
000000101010101 before this pattern
1000010010001001 between this pattern

if we consider 10 to be one element now we have elements as

(10) (10) (10) (10) (1) 0 0 0 0 0 0

so its arrangement of this elements which is (11 6)

Problem  Number of subsets of set with n elements
Bijection n length bit string where  0 is for element not selected and 1 for element selected
so for set {x1,x2,x3....xn}
if we consider subset {x2,x5} we will have bit string 0100100..0 where 2nd and fifth are 1 rest zero
so if we count number bit strings with zero and 1 we would have the possible subsets
Number of subsets is 2^n as each position can be either zero or one


Placing n indistinguishable objects in k distinguishable boxes in general
Like we saw number of ways to put 3 objects in to 2 boxes

box1       box2

aaa

                  aaa

aa                a

a                 aa




This problem was mapped into problem of positioning 1 in the four bitstring where the left of 1 specify the number of objects in box1 and right of 1 specify number of object in box2
or we need one divider for making two boxes
**********|***********
box1                   box2
like 0001 divides object, all in box1 none in box2

that is if we have to place indistinguishable objects in k boxes then we would need k-1 dividers
so general formula for placing n indistinguishable objects in k distinguishable boxes is
(n+(k-1))C(k-1)


Each box contains at least one object
If the constraint is such that each box should contain atleast 1 object or box can not be empty

we first place one object in each box which can be done in 1 way since objects are indistinguishable and then distribute remaining n-k objects in k boxes which is (n-k)c(k-1)

or if we look at bitstring when there are three boxes 5 objects and atleast one objet should be there in each

we can assume following to be single object and find the possible combinations

(01) (010) 0 0

or its pattern

(0)+1(0)+1(0)+



Problem A doughnut shop offers Plain, Glazed, Hoclate and Jelly doughnuts How many different orders of dozen doughnuts are possible. Also find when we need to select atleast one from each variety

Of the dozen doughnuts the various possibilities are

we select 2P 3G 4H 3J or 7P 3G 0H 2J and so

we need to place 12 indistinguishable doughnuts in to 4 distinguishable boxes which is (12+(4-1))C(4-1) = 15C3

or if we map the problem to bit string it is like

(0)*1(0)*1(0)*1(0)*

zero's specify doughnut in that group consider simple instance like

000001000010010


At least one from all :
when we need to select atleast one from each variety its like selecting 4 doughnuts from each variety first which can be done in single way and then selecting 8 doughnuts

which is (8+4-1)C(4-1)


Problem. Consider number from 1 to 20 we need to select three numbers from this group then what is probabability of  getting pair of consecutive numbers in the three selected numbers.

Sample space S is  = (20 3) that is ways to select three numbers
the selected numbers could be like
1 2  5, 2 5 6,
so a consecutive pairs can be selected in 19 ways 12,23,34,45,... 1920
and then select any number this can be done in 18 ways (except two selected numbers)
giving E = 19*18 but
there are possibility when we select the consecutive number like 4 5 and we select other number as say 6 these selection will repeat when we select consecutive number 5 6 and select other number as 4
so this repeated selections will be when we select three consecutive numbers
so number of consecutive numbers is = 18
actual E= 19*18 -18
probability = E/S

Problem In how many ways can 2n students be paired up
Arrange students in row and first each two 12 34 ..
consider 4 students 1 2 3 4 now we first find the way to arrange them
4!
1234

1243
2143
2134
1324
1342
3124
3142
1423
1432
4132
4123
2341
2314
3214
3241
2431
2413
4231
4213
3412
3421
4321
4312

 we are overcounting here by
(number of ways of arranging first ) (number of ways of arranging second pair)
(2!)(2!)
now we are left with
//pending

Problem How many different outcomes are possible when 3 similar dice are tossed
Solution
If we had three distinct dice that is if we consider dice as numbered A B and C
then number of different outcomes are 6^3 that is we differentiate between outcomes
3 4 3 and
3 3 4

Here for similar dice number of different outcomes means that if on two dice its n1 and on third its n2
we donot differentiate between two dice which has n1 output so cases like
1 1 2
2 1 1
1 2 1 are all same
we can think of possible outputs as box numbered 1 2 3 4 5 6
then output of dice toss would be like

**       |         *        |              |            |           |

that is we got number 1 on two dice and number 2 on one here for six containers we have five separator
***|||||
so number of arrangements of  * and | that is C(8 3)

Number of partitions of set of n objects into k groups

Stirling number of second kind

S(n,0) = 0
S(n,1) =S(n,n) = 1

Triangular Property
S(n,k) = S(n-1,k-1)+k*S(n-1,k)
can be interpreted as partition of n objects into k groups would either contain subset {n} or it does not
If it contains the subset {n} then we have one group and remaining groups can be formed in S(n-1,k-1)
If it is not contained then we have n-1 objects which should be partitioned into k groups S(n-1,k)

that each number can be derived from number directly above it and before that.
for k between 0 to n
                0    1     2     3     4         ------->k size of partition
----------------------------
S(3,k) =  0    1     3      1
S(4,k) =  0    1     7      6     1

Sum {k=0 to n }(S(n,k))
that is partition of all size is done by bell number

Counting Functions

Consider set A of r elements and set B of n elements

Counting number of functions
each value from set A can be assinged any value from the set B

for each value there are n options so its n^r

Counting Injective functions
Injective function one-to-one function  states that  no two values from set A can be assigned same value from set B. So if we have

r>N we don't have sufficient values in the set B and from pigeonhole principle we can prove that atleast two values  will have same mappings so its 0

for r

Counting Bijections

Bijection states that every value in y should have their image in x + injection property

so for
r != n its 0 and for
r = n its n!


Counting Surjective functions

sujection or onto states that image of function is equal to its Range that is all the y in image are mapped to some x in domain

If r elements in the domain and n elements in the  image

we first partition r elements in the domain to map to all n elements in the image

1)partition the elements in set X, call it S(r,n), in to n partitions

if we partition above function where r=3 and n=2  we would have partitions like {12,3} {13,2} {23,1}

2) we pick value for each partition that is for (12) and for (3) we can pick value for them in n! ways

So we have number of onto functions = S(r,n)*n!
where S(r,n) is Stirling number


Another method for counting surjection

Let m be number of element in domain and n be number of element in co-domain
Using principle of inclusion and exclusion
let elements y1 y2 ..yn be not in range and conidtion p1 p2 ....pn represent this resp.
then for surjection there should be all element in codomain should be in range so

N(p1'p2'..pn') = N- N(p1p2p3)

that is condition when all elements not mapped = total number of function - condition when all the element are mapped

N= n^m

N(p1p2p3) = when 1 element is not mapped + when 2 elements are not mapped +.. when all m elements are not mapped

N(p1p2p3) = C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m

so total surjections are
n^m -C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m


Problems number of way to assign 5 different jobs to 4 different employee such that every employee gets at least one job

Solution
Its surjection from 5 to 4 elements n=4 and m=5

4^5 - c(4,1)3^5 + c(4,2) 2^5 - c(4,3)

References
Some useful links for combinatorics problems and solutions

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/assignments
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-sma-5512-fall-2002/assignments/ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/
http://www.geometer.org/mathcircles/solnscount.pdf
www.cs.pitt.edu/~adamlee/courses/fall_08/cs441/.../lecture21.pdf
http://2000clicks.com/MathHelp/CountingObjectsInBoxes.aspx
http://www.math.cornell.edu/~web4410/       //solutions to 'A course in combinatorics '

Aptitude - Part 1

A can do a unit of work in n days then working uniformly
A's one day work = 1/n -----------------(1)

Almost all work problems will make use of the formula below
if for a unit of work
A ---------  t1 days
B ---------- t2 days
we find one days work in such case here it is
A's --------one day work ---------- 1/t1
B's -------- one day work ---------- 1/t2
we add the work of persons not their time
A+B ----------one day work ---------- 1/t1+1/t2   --------------(2)

A+B ----------1/days work ------------ t1t2/t1+t2 days       ---------------------(3)
For a unit of work if
n person                -------        tdays
m person(m<n)  -------         t (n/m) days
                (m>n)    -------          t(m/n) day
Example It takes 4 men to finish work in 10 day. How many days will be required if only i)2 men work or ii)10 men work
For less men we would need more days
2 men would need 10(4/2) = 20 days
10 men would need 10(4/10) = 4 days

If na1 persons in group A can do  a piece of work in ta1 days. It takes na2(na2 > na1) persons from group B to do same piece of work in tb2 days. If na2 persosns from group A and nb2 persons from s group B works together how much time will it take


For a unit of work
na1 --------------- ta1 days
na2(na2 > na1) --------------- ta1(na1/na2) days

nb1--------------tb1 days
nb2(nb2<na1) <="" p="">

If 4 men or 6 women or 10 girls can do a piece of work in 10 days How many days are required for 3 men 8 women and 6 girls
Solution
For a unit of work
4men --------------10days
3men--------------10(4/3)days

6 women ----------------10days
8 women----------------10(6/8)days

10girls-----------------10days
6girls-------------------10(10/6)days

3men+8wome+6girl -------one days work ------- 3/40 + 8/60 + 6/100
for a unit of work
3men+8wome+6girl ------------------ ------- 1/(3/40 + 8/60 + 6/100)

If B is p% more efficient than A then
for unit of work
B--------------xdays
A-------------x(1+pf)days

If B is 100% more efficient than B then
A------------x(1+1) =2x  A takes twice the time B takes

If B is 40% more efficient than B then
A ------------x(1+.4)=1.4x

Poblem A is thrice as good a workman as B and therefore is able to finish a job in 60 days less than B. Working together, they can do it in:
Solution
let time taken by A to finish work be x
time taken by B would be 3x
and difference of their time is given as 3x - x = 60
x=30
so B time is 90
one days work of A+B = 1/30+1/90

Relation and Functions

Function
f(A) --> B
each element of A is mapped to exactly one element in B
A is domain and B is codomain, or B is image and A is pre image of B

Type of functions
one to one or injective :
if f(x) = f(y) then x=y for all x and y in the domain of f
that is no two values in the domain have same value in the range
f(x**2) is not function because x and -x both will have same value
or we can say f(x)!= f(y) when f!= y helpful in proving
there may be unmapped elements in one to one we have not restricted that till now

onto or surjective
if for every element in image B there is a corresponding element in A
by definition of function there should be image for all A and from onto we have constrained all B to have preimage

one to one correspondence or bijection
if it is both one to one and onto


Inverse or Invertible  and composition of function
If function is one to one and onto we can define inverse of function as f^-1(b) = a when f(a) = b
If it is not bijection then inverse would not be function at all

Let g be function from A to B and f be function from set B to set C  and range of g be subset of domain of f
The composition of function defined by
(f o g)(a) = f(g(a))
not commutative that is  (g o f)(a) != (f o g)(a)
Composition of funtion and its inverse forms identity element in either order
f^-1 o f (a) =  a and     f  o  f^-1 (a) =  a


Relation
set of ordered pair are called binary relation its subset of AxB

Number of relation on a set
if A has n elements then number of relation on A is subset of AxA since AxA has n^2 elements x and number of subsets of m elements is 2^m so there are 2^(n^2) relations on set A

Reflexive relation
A relation R on set A is reflexive if for every element a in A there is (a,a) in R
Symmetric
A relation R on set A is symmetric if (b,a) is any pair in R then we have (a,b) also in R
Antisymmetric
if there is (a,b) and (b,a) then a=b
that is it cannot have distinct a and b with this property
Transitive
if (a,b) and (b,c) then (a,c) should be in relation

Counting Relations
number of distinct reflexive relations on a set of n elements
we count reflexive relation on AxA that has n^2 elements
since all (a,a) pairs should be present for each n elements This has to be in the relation R and remaining pairs we can form from n^2-n elements So total number of relation is 2^n(n-1)
number of distinct irreflexive relations on set of n elements
its same as reflexive because  selection of diagonal elements is fixed that is they should not be selected and remaining n^2 - n elements for 2^n(n-1) number of relations

number of distinct symmetric relations
we have to count each pair (a,b) and (b,a) once since that is for each selection (a,b), (b,a) will be selected
for first element a we can select another element in n ways including the (a,a) pair
for second element b we select another element in n-1 ways  excluding the selection of a
so there are total n + n-1 + ...1 number of elements  = n(n+1)/2
or we can look at the matrix form to see that we need to select element on or above the diagonal which is n(n+1)/2
So total number of relations is 2^(n(n+1)/2)

number of antisymmetric relations
we can have a,b or b,a or none for two distinct elements
number of two distinct element subsets - C(n 2) = n(n-1)/2
and for each subset we have 3 choices therefore 3^n(n-1)/2
we can also select diagonal elements that is (a,a) so, those gives 2^n choices
Total number of relation 3^n(n-1) /2 * 2^n

Number of relations both reflexive and antisymmetric
diagonal element all has to included so single way to select them and rest we calculated above for antisymmetric that is 3^n(n-1) /2

Number of relations both irreflexive and symmetric
we can have all elements above the diagonal but not on the diagonal since we calculated for symmetric number of pairs as n(n+1)/2 we can deduct diagonal elements from this to get n(n-1)/2
so total number of relations = 2^n(n-1)/2

Combining relations
composition SoR is defined as all ordered pair where second element in R agrees with first element in S
example if R has ordered pair 2,3 and S has ordered pair 3,5 then SoR = 2,5
Power of relation is defined as
R^n = R^n-1 o R

Relation R on set A is transitive if and only if R^n is subset of R for n=1,2,3..

Closure of relation
reflexive closure is R U all diagonal elements (a,a)
symmetric closure is R U R^-1  where R^-1 is b,a whenever a,b
Transitive closure  Transitive closure of R equals connectivity relation R^*
There is pah from a to b of length n if and only if a,b is element of R^n


Transitive closure of n elements in 0-1 matrix is R* = R^1 U R^2 U ...R^n
all called union of boolean powers each boolean power takes n^2 * 2n-1 bit operations 
that is find the composite relation R o R and take union of all such
composite relation can be found by  same way we perform the matrix multiplication but
multiplication will be AND and addition will be OR


Warshalls algorithm to compute transitive closure
requires 2n^3 bit operations unlike boolean multiplication method that requires 2n^3* (n-1) bit operations
 based on construction of zero-one matrix



Congruence
a=b mod n
1)if a-b is integer multiple of n
a-b = kn or
2)a-b divides n that is a-b/n = k or
3)a mod n = b mod n that is both have the same remainder when divided by n

congruent class modulo m
a = b mod m
we find all a for which equivalent to b mod n that is a-b is integral multiple of n

when a=b we get 0/n which is divisible for a = b+m we get  (b+m - b)/m which is divisible so
[b]_m  ={b,b+m,b+2m...} U {b-m,b-2m,b-3m}

example for [13]_9 that is find a such that a=13 mod m
{13 13+9 13+2*9 ...} U {13-9 13-2*9 ....} = {13 22 31 ..}  U {4 -5 -14}

Modular exponential
find 103^45 mod 5
solution
1)we find that remainder increases  by going from  power of 1 to 2
2) we try to get to the 1 mod m
103 mod 5 = 3  mod 5  that is now we can put 3 at place of 103
103^2 mod 5 = (3)^2 mod 5 = 4 mod 5 //we can put 4 in place of 103^2
103^4 mod 5 =  (103^2)^2 mod 5 = 4^2 mod 5  = 1
now we can find 45 in terms of 4 that is 44+1
103^45 mod 5 =  (103 mod 5) (103^44 mod 5)
                       =  (3 mod 5) ((103^4)^11 mod 45) = 3

find 58^29 mod 11
58 mod 11 =3 mod 11
58^2 mod 11 = 9 mod 11
58^4
103^44 mod 5 = (103 ^ 4)^11 mod 5 =

property
1)if a = b mod m
b^n mod m = a^n  mod m

Methods for calculating modular exponention
1)calculate b^e and then find mod with that number
requires O(e) multiplications
operations takes lot of time
2)Memory efficient method
takes more number of operations but each operation takes less time making it faster
ensures that result always stays small
number of multiplications are O(e) only
but computation time decreases by O(e) from first because calculations involve much small number
3)right-to-left binary
reduces both operations and memory required
Total running time is O(log exponent)

Linear congruence theorem
ax = b mod m has solution if and only if b is divisible by gcd (a,m)
there will be exactly d solution in set {0 , 1, 2, ..n-1}
then use extended euclid algo to find all d solutions


Problem what is minimum number of ordered pair that should be chosen such that two pairs (a1,b1) and (a2,b2) in the chosen set has
a1= a2 mod 5 and b1 = b2 mod 3
Solution
we can rewrite the equation as a1 mod 5 = a2 mod 5 and b1 mod 3 = b2 mod 3
that is we need to find the ordered pair a1,b1 such that residue on mod 5 on first pair number is equal to residue from mod 5 on second pair number
number a1 will give residue {0 1 2 3 4} on mod 5 and number b1 will give residue {0 1 2} on mod 3
that is if we choose any pair like (7, 5) then residue is {2,2}
we have to find two pairs such that their residue in ordered pair is same that is if we got residue {2,3}  on first any ordered pair then there should be another set also with residue {2,3}
since there are 3*5 different pair of reside from pigeonhole principle we can deduce that there should be at least 16 pairs.



what in case of unordered pairs?


Equivalence relation
union of two equivalance relation is not equivalence relation
example R1 = congruence mod 3 and R2 = congruence mod 4 then
intersection of equivalence relation is equivalence relation
If R is transitive then R^2 =R

To prove relation is equivalence find the relation matrix
check if reflexive by diagonal elements
symmetric from symmetry of elements above and below
transitive by M^2 = M

Equivalence classes are found by finding all related elements like if relation (a,b)R(c,d) is equivalence relation if a+b = c+d
the we can find the equivalence class as
{1,2}  = {1,2} {2,1}
{1,3} = {1,3}{3,1} {2,2}
{1,4}={1,4}{4,1}{2,3}{3,2}

Partition
division non overlapping, non empty  that covers all elements
for equivalence relation, equivalence class forms partition

Number of partitions and Equivalence relation
the total number of partition of n element set is Bn Bell number
B(n+1) = {k=0 to n} C(n k)Bk

0  1    2    3    4    5    6     7
1  1    2    5   15  52  203

Partial order
reflexive
antisymmetric if aRb and bRa then a=b
transitive

called partially ordered set poset
if a and b are distinct element of partially ordered set and either a<=b or b<= a then they are comparable
if every two elements of poset are comparable it is called totally ordered
poset is called partial because some of the sets may be incomparable

well ordered set
if it is poset such that <= is total ordering and every non empty subset of S has a least element

Maximal and minimal elements of poset
Maximal if it is not less than any element of poset
greatest element is greater than every other element, its unique
element that is greater than all the elements in a subset A of poset then its called upper bound
least upper bound of subset A if x is upper bound that is less than every other upper bound of A


Lattice partially ordered set in which every element has both least upper bound and a greatest lower bound is called lattic


LCM GCD forms lattice that is each element at first level are primes like 2 3 5 and then elements above that are multiple of first level numbers like
2*2 , 2*3 , 2*5  3*2 ..
greatest upper bound gives GCD and lowest upper bound gives LCM

Problem
a)R =SxS
i)equivalence?
equivalence as reflexive symmetry and transitive fullfils
ii)poset
antisymmetry fails that is there are a,b and b,a both only if there is single element can it be partial ordered set
b)R={}
i)equivalence
not reflexive so not equivalence relation
can't be poset also

Graph Algorithms

Minimum Spanning Tree

Problem definition
In a weighted connected graph G(V,E,W) Find tree T that contains all the vertices in G and minimizes the sum of weight of all edges
Greedy approach to find minimum spanning tree,at each step one of the several possible choices is made that best choice

Safe edge is one that can be added to  subset of edges of minimum spanning tree A without violating the condition
A cut is any partition of V
If no edge in A crosses the cut then it respects the cut
An edge is light edge crossing the cut if its weight is minimum of any edge crossing the cut

Theorem In graph G if we partition set V into S and V-S and A is subset of edges of minimum spanning tree then a light edge {u,v} can be added to set A safely that is AU{u,v} is also subset of MST
If  edge u,v is not part of MST then there must be some other edge (xy) connecting the two partitions V  and V-S so if we add edge uv to it, it should create cycle but we have uv as light edge so
w(uv)<=w(xy)
so we have MST with uv also
But if all edges have distinct weights we cannot have this condition and only edge {u,v} can be part of MST

Generic- MST : Find a safe edge and add it to A to form MST

Kruskal algorithm
greedy algorithm because at each step adds the least possible weight edge to A.
set A in case of Kruskal algorithm is forest
It finds a safe edge to add to the growing forest by finding edge {u,v} of least weight that connects any two trees in forest

Kruskal algorithm
Kruskal(G,w)

For each vertex v in V(G)
  make-set(v)   //O(V)
sort the edges of G in nondecreasing order by weight   //greedy approach to take minimum weight
For each edge E{u,v} in the sorted list
if both endpoints do not belong to same tree then  //if belongs to same tree then we would have cycle
If Find-Set(u)  != Find-Set(v)          //O(E) for each edge
 then A =A U {u,v} // add edge E to set A
 Union(u,v)

we used disjoint set data structure to implement it

Running time
depends on the disjoint set operations
time to sort the edges takes (E log E)
creating a disjoint set of vertices that is that many number of distinct trees initially and the main loop to process each edge takes O(E+V)a(V), but since G is connected graph E >= V-1 and so it becomes O(E)a(V) (a takes into count the union at last when vertices are added to tree) where a(V) is (log V) = O(log E)
Total running time is O(E log E) also |e|<=|v|^2  so log E = O(log V) and we can also state running time as
O(E log V)


Prim Algorithm
also example greedy algorithm 
edges in the set A forms Tree that is it works by adding edges to a set A
operates like Dijkstra algorithm
It gradually creates a minimum tree that spans all the verties
At each step light edge is added to tree A that connects A to an isolated vertex
key concern is how to select
min priority queue is used to hold vertices not in tree A based on key field .For each vertex v, key[v] is the minimum weight of any edge connecting v to a vertex in the tree

Prim Algorithm
r is the starting vertex
At each step we update the adjacent veritces weight so that when we call extract-min on priority queue we get the light edge that is minimum weight edge
Prim(G,w,r)
for each vertex add set the key field to infinity and parent field to null except for the vertex r for which key field is set 0
set the min priority queue with this information
while queue is no empty
  u =  extract-min (Q)            // we process vertex in order on min key in Q
  for each edge v adjacent to u
   if v is in the priority queue and weight w(u,v) < key[v]  
    update the key and parent for vertex u

For every vertex v in Q, key[v] is the minimum weight of any edge connecting v to a vertex in the tree
Q will have non infinite key for those vertexes whose adjacent vertex has been processed or in other words we determine the cut of the graph and light edge is added to the set A.
set A and Q forms disjoint sets of cut.


Loop invariants
set A contains V-Q that is vertices processed and removed from queue
for all vertices in queue if parent is not null then key of vertie

Running time of prim algorithm
depends on how min priority queue is implemented
1)If binary min heap is used
we use build min heap to create vertex with key and parent fields it will takes O(V) time
 Extract min takes O(log V)  //when selecting the vertex in queue
and is called V times that is for each vertex  so extract min takes total of O(V logV)
Decrease key on binary heap = O(log V)  // when updating the key of adjacent vertices
and is called for all the adjacent vertices of v
sum of lenght of all adjacency list is 2|E| so decrease key is called O(E logV)
total time is O(V log V + E log V )
when graph is sparse we have e << v^2 and e = Th(v) so cost is O(V log V)
when graph is dense we have e ~= v^2, so cost is O(V^2 log V)
2)using fibonaci heap
extract min can be performed in O(log V)
and decrease key can be performed in O(1)
so total time is (VlogV+E)
for sparse we have e=Th(v) so  cost is O(VlogV)
for dense we have e ~= v^2 so cost is O(V^2)
3)using adjacency matrix
scans the list to find the smallest key   O(V)
 for each vertex update its adjacent vertex weight   //O(deg(u))
total cost is {sum over all vertices} O(V + deg[u])
so  total cost is O(V^2 + E) =O(V^2)

Negative edges in Kruskal and Prim algorithm
Negative edges does not affects the kruskal algorithm Both works correctly as should be
Light edge donot distinguish negative and positive edges

Shortest Path Problem

There is only one minimum spanning tree but in general there is different shortest path for each source

Optimal structure
each subpath of shortest path is shortest path

Cycle in graph
negative weight edges
there may be negative weight edges
If G contains no negative weight edges then shortest path weight remains well defined for all sources s
If there is negative weight cycle reachable from s then shortest path are not well defined
If there is negative weight cycle on some path from s to v then shortest path weight d(s,v) = -infinity

If vertex v is not reachable from s than d(s,v) = + infinity

Dijkstra algorithm requires no negative weight edge in the input
Bellman Ford algorithm allows negative  weight edge in input graph and produces correct answer as long as no negative weight cycles are reachable from source. It can detect the negative weight edge cycles and reprot there existence

Shortest path cannot contain negative edge cycles and also not positive weight edge cycles
zero weight edge cycle it can be on the shortest path but then we can also go via another path instead of zero cycle
So we will consider shortest path only for v-1 edges that is without any cycle

Relaxation step
Relax(u,v,w)  //relax edge {uv} having weight w
we update the distance on the vertex v like
if d(v) > d(u) +w(uv)
then update d(v) with d(u) + w(uv)

Each algorithm differs in how many times and in which order they relax edges.
Dijkstra algorithm relaxes each edge exactly once
In Bellman ford each edge is relaxed many times

Bellmand Ford Algorithm
solves single source shortest path in weighted directed graph G(V,E)
negative weight edges allowed
detects reachable negative weight edge cycles
algorithm returns boolean value indicating whether or not negative weight edge cycle exist If such cycle exists the algorithm indicates there is no solution If there is no cycle it  produces shortest path and weight

algorithm return TRUE if and only if the graph contains no negative weight cycle reachable from source s

Bellman-Ford(G,w,s)
Initialize(G,s )  //initializes the d(v) for each vertex to infinity and path s to zero
for i =1 to |V|-1  //remaining vertices other than source
  for each edge (u,v) in E(G)  //each pass relaxes each of the edge of the graph so |v-1|*|E| relaxation
    Relax(u,v,w)
for each edge (u,v) in E(G)   //check negative weight cycle
 check if d(v) > d(u) + w(u,v) 
    return FALSE              //if negative weight cycle exist
return TRUE

Running Time
Initialization takes O(V)
we relax each edge for each vertex that is O(VE)
check for negative cycle takes O(E)
total running time is O(VE)

For proving the correctness of the bellman ford we need to prove that each vertex v has shortest distance from s that is for each vertex v d[v]=shortest distance from s

Observations
does not always returns shortest path from s to t in all the graphs, when graph have negative weight cycle
If graph has all distinct vertices then shortest path between two vertices may not be unique, same weight path possible


Dijkstra algorithm
single source shortest path on directed weighted graph
no negative edges allowed
example of greedy algorithm
greedy algorithms doesnot always yields optimal result but in case of Dijkstra it return optimal weight path 
maintains set S of vertices whose final shortest path weight from source have already been determined
select vertex u whith minimum path estimate from remaining vertices and adds it to S and relaxes all edges leaving u

Dijkstra (G,w,s)
Initialize all vertices to infinity distance
build a min priority queue from vertex set V[G] //Q would always contain V-S
while priority queue is not empty    //runs for |V| times
 u = extract-min(Q)
 add u to S
 for each vertex v adjacent to u
  relax(u,v,w)

Running Time of Dijkstra
maintains min prioity queue by calling three operations
Insert(build heap) ,Extract-min(G) and Decrease-Key(Relax)
1)we take advantage of the vertices being numbered 1 to |V|-1
we can perform Insert and Decrease-key in O(1) and extract min in O(V) time
total running time O(V^2+E) = O(V^2)
2)If graph is sparse that is E =o(V^2/log V) we implement it using binary min heap
build heap O(V)
extract min O(log V) and there are V such extract so O(V log V)
Decrease key O(log V) , number of decrease key is of O(E) so total  O(ElogV)
Total running time = O((V+E)log V) = O(E log V)
3)with fibonacci heap we can achieve (V logV+E)

Observations
Dijkstra algorithm relaxes each edges only once
example when Dijkstra algorithm does not works
here we start from A relax edge AB and AC
B gets labeled (5,A) and C(10,A) So we choose B and relax edge BD, D gets new label (6,B)
D is processed then C is chosen and edge CB is relaxed and B gets new label (3,C)
D has label (6,B) while D should have been (4,B)

All pair Shortest Path

Breadth First Search
for searching graph
given graph G and source s BFS explores the edges of G to discover every vertex that is reachable from s
It computes the smallest number of edges from s
explores all vertices at distnace k from s before moving to k+1 vertices

To keep track of progress, colors each vertex white gray or black.
not processed white
when first encountered it becomes non white
three color for vertices
white -- not discovered yet
gray discovered but not processed
black all the adjacent vertices discovered and grayed


all vertices adjacent to black are discovered vertices
vertices adjacent to gray may not be discovered

constructs a breadth first tree initially containing only its root

FIFO queue used to process vertices in order in which they are discovered

BFS(G,s)
color each vertex white initially , their distance infinity
color sources s as gray that is processing starts with s
enqueue s
for each vertex in queue
u = dequeue(Q)
for each adjacent vertex v of u
if its not discovered yet that is color ==white
color it gray
increase weight by one d(v) = d(u)+1
enqueue(Q, u)
color v black that is all its adj have been discovered

Queue Q always consists of gray vertices


Running time
aggregate analysis
Enqueue and Dequeue O(1) time
each vertex is enqueued and dequeued once giving O(V)
since sum of lenght of all adjacency list is Th(E)
total time scanning adjacency list is O(E)

total running time of BFS is O(V+E)

breadth first search shortest path, that is, minimum number of edges or weight of 1 on each edge, for each vertex
if it is reachable else infinity

DFS
edges are explored out of most recently discovered vertex
when all edge o v has been discovered search backtracks to explore edges leaving the vertex from which v was discovered
predecessor graph of DFS may be composed of several trees unlike that or BFS

like BFS vertices are colored to indicate their state
white initially grayed when discovered and black when finished

DFS(G)
initialize each vertex color to white
time =0
for each vertex in V[G]
if we have white colored vertex call DFS-VISIT(u)

DFS-VISIT(u)
set color of u to gray indicating its discovered
time = time+1
d[u] =time // time when vertex u is discovered
for each vertex v adjacent to u
if it is white colored
then call DFS-VISIT(v)
set color of u to black indicating all adjacent discovered
f[u] = time+1 //when the search or u adjacent vertices finished


Running time
since DFSVISIT is called exactly once for each vertex it takes O(V) time
scanning adjacency list O(E)
total O(V+E)

properties of DFS
vertex v is a decendant of vertex u in the depth first forest if and only if v is discovered during the time in which u is gray

discovery and finishing time have discovery structure
parenthesis theorem
that either interval [d[u],[u]] and [d[v],f[v]] are entirely disjoint or one is completely contained in other


vertex v is proper decendant of vertex u in the depth first forest for a graph G if and only if
d[u] <> j & not edge of graph








 Problem Remove cycles from graph O(k) cycles 
Solution When traversing the graph check whether edge trying to relax goes to node that has been seen but not finished that is gray colored vertex then this is back edge and we can save all such edges and at last remove them It will take time of DFS algo that is O(V+E)


 Observation
DFS-VISIT if runs on BST it would return the smallest element as its first node and root as its last
Only in case of DFS does absence of back edges ensures acyclic graph not in case of BFS
BFS finds path using fewest number of edges the BFS depth of any vertex is at least as small as DFS depth of the same vertex Thus DFS tree has greater or equal depth that is if maximum distance between two vertices is T edges then in BFS depth is at most T but depth of DFS might be larger,DFS may have depth up to V-1 like in case of complete graph
If adjacency matrix is used instead of adjacency list in BFS it would run in O(V^2) instead of O(V+E)



dynamic programming solution
characterize structure of optimal solutiom
recursively define value of optimal soluion
computer in bottom up


Optimal sub structure
subpath of shotest path are also shortest paths
that is if p is shortest path from i to j then
d(i,j) = d(i,k)+w(i,k)

Recursive solution
let l^m(i,j) be minimum weight of any path from i to j with at most m edges
when m =0
l^m(i,j) = 0 if i=j
= infinity if i<>j
for m >= 1
we compute l

Probability - Counting, Conditional Probability and Distributions

Glossary
Countable set : A set is countable if it is finite or has same cardinality as set of natural numbers.

If E F G are three events then
1) only E occurs
 means F and G donot occur so EF'G'

2)both E and G but not F
EGF'

3) none of the event occurs
E'F'G'

4)at least one of the event occurs
(E'F'G')' => E U F U G

5)at least two events occurs
EF U EG U FG U EFG

6)all occurs
EFG

7) at most one of them occurs
exactly one of them  occurs or none occurs
EF'G' U E'FG' U E'F'G U E'F'G'

8) at most 2 of them occurs
none occurs U exactly one occurs U exactly two occurs

Observations
1) none event occurs(E'F'G') is not complement of all event occurs (EFG)

 

Fig. all event occurs

 

Fig none event occur

Inclusion and Exclusion

P(AB) : probability of events A and B occuring together (intersection)

P(A) probability of event A independent of any other event

P(A U B) = P(A) + P(B) - P(AB)
P(E U F U G) =P(E) + P(F) + P(G) - P(EF) - P(FG) - P(GE) + P(EFG)
P(at least 1 event) = 1- P(neither of 3 events occurs)

Conditional Probability
P(B/A) = P(AB)/P(A)
P(ABC) = P(A/BC)P(BC)
             = P(A/BC) P(B/C) P(C)

since we can write

P(AB) = P(B/A) P(A) or
P(AB) = P(A/B) P(B)

Some Counting problems
Problem Find number of ways in which digit 1 appears before digit 4 in permutations of number 12345

Solution

Since for any permutation number 1 will appear either before 4 or after 4,  and number of ways in which 1 can appear before 4 = number of ways in which 1 appears after 4

number of permutations = permutations in which 1 appears before 4 + permutations in which 1 appears after 4 i.e 2(n) = 5!
n=5!/2


Problem In how many of permutations of number 12345 is first digit greater than second digit

Solution1

we will look at each digit 1 2 3 4 5 at position 2 and will find number of permutations in which first digit is less than second digit 

1) second digit is 1 

no digit is less than 1 so we have 0 cases

2) second digit is 2

at first place we can have 1 and in remaining 3! i.e 1*3!

similarly

3)second digit 3 first place can be occupied by 1 2
2 * 3!

4) second digit 4
3*4!

5) second digit 5
4*3!

total permutaions in which first digit is less than second = 3!(1+2+3+4) = 10*3!
total permutations in which first digit is greater than second = 5!-10!*3! = 5!/2
1/2(5!)


Solution 2
Since for every permutation abcd (a > b)
there will be also be permutation bacd so all cases are equally likely that 1/2 of these will have first digit greater than second



Problem Suppose we randomly select a permutation from 20! permutations of  1,2,3,4, .....20. what is probability that 2 appears at earlier position than any other even number
Solution 1
for any  permutation of number say of digits 1,2,3
123
132
213
231
321
312
Probability of any digit appearing a particular position is equally likely
In above case at position 1, one, two and three all appears twice at position 2 also they appear equal number of time at other positions.

At positon 1 either one can appear or two or three so
P(1)+P(2)+P(3) = 1
and since all are equally probable we have
p=1/3

Now we look at the problem which asks for all such permutation where number 2 appears before any other even number
Since there are 10 even numbers and whatever position they occupy the digit 2 will occur as many number of times before other even numbers as any other even digit Therefore
p =1/10

Solution 2 

number will be of form even and odd like EEEEOEOE..
number of ways to select 10 positions for odd number = C(20 10)
and there are 10! possible arrangements so its 10!*C(20 10)

It leaves place for even numbers which we have to arrange such that we place 2 before any other even number since 2 can be placed in only one way that is before all remaining even numbers
Rest even numbers can be ordered in 9! ways

so number of ways to place 2 before  even numbers is  = 10! C(20 10) * 9!
Total ways to place 20 digits is 20!
P = 9!/10! =1/10

Probability  Problems
Problem An urn contains 5 red, 6 blue,8 green balls. If 3 balls are randomly selected. what is probability of drawing 3 balls of
i)same color
Sample Space: number of ways of drawing 3 balls is C(19 3)
Event Space: number of ways of drawing same color balls = number of ways of drawing 3 red balls + number of ways of drawing 3 green ball + number of ways of drawing 3 blue balls
= C(5 3) + C(6 3) + C(8 3)

without replacement
P =(C(5 3) + C(6 3) + C(8 3)) / C(19 3)

with replacement
P = (5/19)^3 + (8/3)^3 + (8/19)^3

ii)different colors
we want one ball of each color so its
C(5 1)*C(8 1)*C(6 1)
with replacement it would be
(5/19)(6/19)(8/19)

Problem If there are 12 persons in the room, what is probability that no two of them celebrate b'day in same month
Solution
Sample space : since each person can have their b'day in any of the 12 month so its (12)^12
Event space : 12*11*10 ...1 = 12!
P = 12!/12^12

Conditional Probability Problems
Problem Consider 3 urns Urn A contains 2 white and 4 red balls; urn B contains 8 white and 4 red balls and urn C contains 1 white and 3 red balls . If one ball is selected from each urn, what is probability
that ball chosen from urn A was white given that exactly 2 white balls were selected

Solution:
P(A) : probability of selecting white ball from A. similarly P(B) P(C)
P(W₂) : probability of selecting exactly two white balls independent of any other event
P(AW₂) : white ball from A and exactly one white from B and C = P(A)*P(exactly one white from B and C )


P(A|W₂) = P(AW₂)/P(W₂)

Probability of selecting exactly one white from B and C = P(BC')+P(B'C)
since B and C are independent events
its P(B)P(C') + P(B')P(C)

Probability of selecting exactly two white ball i.e P(W) =
P(ABC')+P(AB'C)+P(A'BC) = P(A)P(B)P(C')+P(A)P(B')P(C)+P(A')P(B)P(C)
since events A B and C are independent so P(ABC) =P(A)P(B)P(C)


P(A|W₂) = P(A)* (P(B)P(C') + P(B')P(C)) / P(A)P(B)P(C')+P(A)P(B')P(C)+P(A')P(B)P(C)

Problem In a college 52% are women. 5% students are majoring in CS.2% of students are women majoring in  CS.A student is selected at random what is probability
i)that student is female given that student is CS major
Solution
P(F|C) = P(FC) / P(C)
P(F) = .53  P(C) = .05
P(FC) = .02
If it had been "2% of women are majoring in CS"  we would have taken P(C|F) instead
P(F|C) = .02/.05

Problem 5% of men and .25% of women are colorblind.A color blind person is chosen at random. what is probability of this person being male.Assume equal number of men and women.
Solution
we need to find P(M|C)
P(M|C) = P(MC)/P(C)
given data is
P(C|M) = .05     P(C|W) =.0025    P(M)=P(W) =.50

P(C) = P(M)P(C|M) + P(W)P(C|W)
P(MC)= P(C/M)P(M)

           
Observation
When probability is given like t% of A are B
it means P(B|A), when A is the sample space then it becomes P(B)
Like in the problem above when it says
5% of student are women, we are given P(W|S) i.e P(W)
.25% of women are colorblind, we have P(C|W)


Problem Stores A, B and  C have 50, 75 and 100 employees, and, respectively, 50, 60 and 70% of these are women. Resignations are equally likely among all employees, regardless of sex.One employee resigns and this is woman. what is probability that she works in store C
Solution we need to find P(C|W)
P(C|W) = P(CW)/P(W)

given data is
P(W|A) = .50    P(W|B) = .60   P(W|C) =.70
n(A) = 50          n(B)=75           n(C)=100

P(W) = P(AW) + P(BW) + P(CW)
         = P(W|A)P(A) + P(W|B)P(B)+P(W|C)P(C)

P(A) = n(A) / (n(A)+n(B)+n(C)) similarly for P(B) and P(C)

P(CW)= P(W|C)P(C)



Problem Two cards are chosen at random without replacement
Events: B both cards are ace, A ace of spades is chosen, C atleast one ace is chosen
Find P(B/A),P(B/C)

Solution

 P(B/A) probability that both cards are ace when given that ace of spade is chosen

P(B/A) = P(AB)/P(A) = |AB| / |A|

|A| is number of outcomes in which ace of spades is chosen out of 2 chosen cards = 1*51
since there are two possibilites for ace of spade, it can be first or second card so  2*51 outcomes
|AB| = choose ace of spades and one other spade from remaining 3 = 1*3
and ace of spade can be first or second card so 2*1*3

P(B/A) = 3/51

ii)P(B/C) = P(BC)/P(C) =|BC|/|C|
here lets take case when order doesnot matters whether its first ace or second
Atleast one ace means total hands of card - none ace card
= (52 2) - (48 2) = 198
or we can find exactly one ace + exactly two ace to get atleas one ace
P(B/C) = (4 2) / 198

Some terminology
Probability Distribution(pd)
pd of a random variable X is description of the probabilities associated with possible values of X
sum(P(X=i)) = 1 ; for all possible values of X
that is sum of probability distribution over all the values of random variable is always 1
problems on Probability density
www.ma.utexas.edu/users/geir/teaching/m362k/dailyhw9solns.pdf   

Probability mass function(pmf)
PD can be described by function that specifies probability at each possible value of X
f_X(x) = P(X=x)

Variance of X
sum{over all random values} x^2f(x) - (Ex)^2

Var(X) = E[ (X - E(X))²] = E(X²) - E(X)²
 Properties of Variance
E(cX) = cE(X)
E(c) =c
E(X+Y)=E(X)+E(Y)
var(c) = 0
var(cx)=c^2 * var(x)
var(x+y) = var(x) + var(y) if x and y are independent


 Probability Distributions

Bernoulli Trial and Binomial distribution

Each performance of an experiment with only two independent outcome is bernoulli trial

Probability of k success in n independent trials
For n independent trial where result is either Failure or Success we have bijection with bitstring, let 1 represent success and 0 failure then in bit string of size n we need to have exactly k 1's which is C(n k)
and probability for n trials will be p^kq^n-k
binomial distribution b(k,n,p) = C(n k)p^kq^n-k

Fig Bernoulli trial

Expected Value and Variance of B(n,p)

If X is binomial random variable with probability p and total experiment n then expected value and variance depends on p and n only with following equation

E(X) = np  because each trial results in random value 1 and 0 so mean for single trial is
1*p+0*(1-p )= p so for n trial its np
 and Variance = np(1-p)
because variance for single trial is (x-u)^2 *f(x) that is (1-p)^2*p+(0-p)^2 * (1-p) =p(1-p)

Geometric Distribution 

Instead of fixed number of trials as in bernoulli here trials are conducted until success is obtained
In Bernoulli trial we have k success but here we run the trial until first success

When we have n-1 failures and 1 success on nth trial we have probability as
(1-p)^n-1*p this is known as geometric distribution
for x = 1,2,3 ..

distribution is
x        p(x)
----------
1       p
2       (1-p)p
3        (1-p)^2*p
4        (1-p)^3 * p
.
n         (1-p)^n-1 * p

Sum of probabilities
when infinite number of trials
sum(0;-) ( p+(1-p)p+(1-p)^2 * p .................... )    = 1
when k failures and then success
sum(0;k)P(X=r) = ( p+(1-p)p+(1-p)^2 * p ...................(1-p)^k * p)    = 1- (1-p)^k+1

Expected Value
E(x) = (i=1 to n)xP(x)
       = p + 2(1-p)p + 3 (1-p)^2 p + .......n(1-p)^n-1 p
multiply both side by (1-p)
(1-p)E(x) = (1-p)p + 2(1-p)^2 p + 3 (1-p)^2 p + .......n(1-p)^n p)
subtracting 2 from 1
E(x)  - (1-p)E(x) = p + (1-p)p + (1-p)^2 p ............n(1-p)^n p)
consider n to be infinity
pE(x) =  p(1+(1-p) + (1-p)^2+ ,...........)
          = p(1/p)
E(x) = 1/p

Variance is (1-p)/(p)^2

Negative Binomial distribution 
until  r success from n trials
E(x) = r/p and Variance = r(1-p)/p^2
f(x) = C(x-1,r-1)(1-p)^x-r * p^r

Hypergeometric Distribution

Problems on Random Variable and Expected Value

Problem Two balls are chosen from the urn containing 8 white 4 black and 2 orange balls.Suppose that we win 2 points for each black ball and lose 1 point for each white ball. X denotes our winnings what are possible values of x and probability associated with each

Solution

Find sample space for 2 selected balls then find X that is winning for that selection
Lets say for selection (W,B) and (B,W) we get the wining X as +1
P(X = 1) = P(W,B)+P(B,W) = 2* 8/14*4/13  =. 3516
similarly for others we can find

Problem Consider value of random variable as

i)Find P(X>0) where P(R) = 18/38 and P(R') = 28/38
Solution P(X>0) = P(X=1) which is
P(R) + P(R'RR) assuming independent event we can write P(R'RR) = P(R')P(R)P(R)

ii)Find E(X)

E(x) = (1,n) Σ xP(X=x)
we construct probability distribution
x          P(x)
---------------------------
+1       P(R)+P(R'RR) 
-1       P(R'R'R)+P(R'RR')
-3        P(R'R'R')


Problem Consider 4 bus  carrying 40, 33, 25, 50 students resp.One of the student is selected at random Let X denote number of students in the bus carrying this randomly selected student. One of the bus driver is also randomly selected. Let Y denote number of students on this bus
Find E(X) and E(Y)

Solution 

value of X is number of students in the bus since students can be selected from any of the bus
so
x         p(x)      
----------------------
40       40/148       
33       33/148
25        25/148
50        50/148

E(x) = 39.28

Value of Y is also same as X but probability of selection of driver from a particular bus is 1/4 since there are only 4 drivers one for each bus

x         p(y)    
--------------------

40        1/4

33       1/4

25        1/4

50        1/4

Variance(X)


Problem Suppose we toss fair coin until head comes up. X represent number of tosses what is E(x)distribution
x              p
1             1/2 (H)
2             1/2*1/2 (TH)
3             1/2*1/2*1/2 (TTH) ......

E(x) = (0 to .. ) i(1/2^i)
        = 1/(1/2) = 2

Problem Each sample of water has .10 chance of containing pollutant Find probability that in next 18 sample atleast 4 contain pollutant

Solution

X number of sample that contains pollutant its bernoulli trial with p=.10 and q =.9 n =18
P(X >= 4) =   sum(x=4;18) (18 x) p^x q^18-x
or P(X>=4) = 1 - P( X < 4)



Poisson Distribution

Example
Let t be expected number of occurrence of event year
divide in to n equal intervals and assume that in any given interval the number of occurence of event is either 1 or 0 The probability of occurrence of event is then  t/n
subjected to above assumption binomial distribution gives the probability of there being r occurence of event in n intervals
The assumption is important because if two occurrences of event can happen in single interval then trinomial distribution would be required.To ensure this assumption is valid n must be sufficiently large such that the intervals are sufficiently small

P(X=r) = C(n r) (t/n)^r (1-t/n)^n-r
by solving it we get  (t^r/r!) e^-t

Sum of probabilities
(1+t/1! + t/2! + .....)e^-t  =e^t * e^-t =1


//normal distribution

Geometric Probability

Problem Two friends agree to meet at a park with the following conditions. Each will reach the park between 4 pm and 5 pm and will see if the other has already arrived. if not, they will wait for 10 minutes or the end of the hour whichever is earlier are leave. what is the probability that the two will not meet?
Solution
We do not have any discrete time intervals in this problem the event space is on real axes. we can fin d answer to such question using the plot on real axes
Let x axis represent the time line for P1 and y axis be time line for P2
points on line y=x show the time when both of them arrive at the same time
In condition we are given that they wait for interval of time 10minutes that is if P1 arrives at time t then P2 either should arrive 10min before or 10min after P1. So our region is now bounded
which is total area - 2*area of remaining triangles
that is 60*60 - 2*(1/2* (60-10)*(60-10)) = 3600 - 2500 =1100
probability is 1100/3600 = 11/36

Normal Distribution
symmetric bell shaped curve

represented as N(mean, variance) or X ~ N(m,sd^2) meaning X is normally distributed with mean m and standard deviation sd
about 2/3rd of all cases fall within one standard deviation of mean
P(mean - sd <=X <= mean+sd) = .6826
about 95% fall within 2sd
P(mean - 2sd <=X <= mean+2sd) = .9544

Standard Normal variable 
 convert into standarized normal variable
z = (x- m)/sd
this changes X in to standarized normalization with m=0 and sd =1
z ~ N(0,1)

Properties
i) p(z<=a) = f(a) when a is positive
                = 1-f(-a) when a is negative
because 1-f(a)  will be symmetrical to f(-a)  for a>0
ii)p(z>=a)  = 1-f(a)
iii)p(a<=z<=b) = f(b) -f(a)
iv)p(-a<=z<=a) = 2f(a) -1

Problem  Consider X~  N(25000, 10000^2). Find P(x<=10000))
standard variable z = (x-25000)/10000
now for x =10000 we have z = -1.5 so
p(x<=10000) = p(z<=-1.5) =1-f(1.5)

Problem In family with 11 children what is probability that there will be more boys then girls
Mean for binomial distribution is Np = 11*1/2 = 5.5
variance =Npq = 5.5*1/2 = 2.75
for binomial it is P(x>=6)
for normal we would say P(z>=5.5)

Aptitude

Formulas
1) sp = cp(1+pf)
2) sp = cp(1 - lf)
3) when error in weighing, x gm is sold as y gm(x < y) then profit % is  ((y-x)/x)*100
4) when two items are sold at same price SP. sold item 1 at profit of x% and item 2 at loss of y%
      (2(1+xf)(1-yf) /( 2+xf-yf)  -1)*100 
    when xf and yf are same a^2/100
5) sp = mp(1-df)
6) Two discount of a% and b% on an item is equal to single discount of

    df = 1-(1-af)(1-bf)
7) If tax is t% then Pnew = Porg (1+tf)
8)Revenue = Price * Volume
cp = cost price
sp= selling price
pf = profit fraction
lf = loss fraction




Formula 1
If sp is selling price, cp cost price and pf profit fraction then
sp  = cp(1+pf)
Proof
p% = sp-cp/cp *100
pf = sp-cp/cp
cp *pf +cp = sp
sp=cp(1+pf)

Formula 2
sp = cp(1 - lf)
proof similar to above

Formula 3
when error in weighing, x gm is sold as y gm(x < y) then profit % is
((y-x)/x)*100
Assume t to be price/gm
cost price for x gm = xt
selling price is yt
so (yt - xt/xt)*100 = ((y -x) /x)* 100

Formula 3
when two items are sold at same price SP. sold item 1 at profit of x% and  item 2 at loss of y%
cp1
       \  ---------x% profit
        SP
      /   -------- y% loss
cp2

consider cost price of item 1 as cp1 and of item 2 as cp2
Assuming profit
overall gain  % = {(total selling price of two item) - (total cost price of two item)} / (total cost price of two item) * 100
i.e    ( (sp+sp) - (cp1+cp2) ) / (cp1+cp2)  * 100    or
(2sp /(cp1+cp2) - 1)  *100   --------- (1)

we can calculate cost price in terms of selling price for each item since we have been given profit/loss%

sp = cp1(1 + x_f) => cp1=sp/(1+x_f)           -------------------(2)
sp = cp2(1 - y_f) =>  cp2=sp(1+y_f)           --------------------(3)

putting in equation 1 we get

( 2sp / ( (sp/1+x_f ) + (sp/1-y_f)) -1 )* 100
(2(1+x_f)(1-y_f) /( 1+x_f+1-y_f) -1) *100
(2(1+xf)(1-yf) /( 2+xf-yf)  -1)*100     -------------- (4)

when xf and yf are same, call it af
((1-a_f²)  - 1 ) *100  = >  - (a_f²)*100  // negative number indicates he is at loss
or
loss in percentage a²/100

Problem 1 A person sells two items at Rs 100 one at profit of 10% and other at loss of  10%.Find overall gain% or loss%
Solution
From our formula above  1%  loss. Lets verify it
the item on which he gets profit its cost price CP1 = 100/(1.10) = ~ 90.90
the item on which he gets loss its cost price CP2 = 100/(.90) = ~  111.11

total cost price =  111.11+90.90 = 202.01
total selling price = 2*100 =200
total loss % = 202.01 - 200 / 202.01 * 100  ~= 1

Problem 2 A person sells two item at Rs 100 one at profit of 20% and other at loss of 15%.Find overall gain or loss percentage
Solution
From equation 4 above
we have (2(1+.20)(1-.15) / (2+.20-.15) ) - 1 * 100 =~ -(.49)%
that is loss of .49%

Formula 4
Discount % = (mp - sp) / mp * 100 or
sp = mp(1-df)

Problem Orange are available at Rs 8 per dozen and discount of 10% on that price. How many oranges can u buy for 2.4 rs
Solution sp = 8(1-.10) = 7.2 per dozen
simple proportion 7.2rs -----12 oranges
2.4rs ----------?
4 oranges

Formula
Two discount of a% and b% on an item is equal to single discount of
Discount of b% on item then
sp =(1-bf)mp
discount of a% on it
(1-af)((1-bf)mp)
consider single discount d then
(1-df)mp = (1-af)(1-bf)mp
(1-df)=(1-af)(1-bf)
df = 1-(1-af)(1-bf)

Problem discount of  of 20 and 40% on an item equals discount of
df = 1-(1-.20)(1-.40) =  1-.48 = .52 or 52%

Formula If tax is t% then
Pnew = Porg (1+tf)

Problem A tradesman gives 4% discount on the marked price and gives article free for buying every 15 articles and thus gains 35%. The marked price is above the cost price by
Solution
consider cost price of an item as cp and marked price  as mp
4% discount on item mp makes its sp = (1- .04)mp
for 15 items its total selling price would be 15(1-.04)mp and trademan gives an item free on this but he incurs the cost of this extra item
total cost price for this 16 item = 16cp
he incurs a gain of 35%
(15(1-.04)mp - 16cp)/16cp *100 =  35
14.4*mp = (.35+1)16cp
mp = 1.5 cp

Pipe and Cistern

1)we add or subtract the amount filled in 1hr
or we add or subtract the amount only and not time and that too on normalized scale


Direct proportion of time it takes and amount that is filled
)If tank can be filled in xhrs then part filled in 1hr is 1/x
or If in 1hr, 1/x of tank is filled then it take x hr to fill complete tank
If a tank is completely filled in x hrs then
time it takes to fill 1/p of tank is  (1/p)*x

Additive property for amount of tank filled
1)if in 1hr 1/x of tank is filled by a pipe then with k similar pipes opened simultaneously
amount filled would be k*(1/x)


2)when two inlet open simultaneously
one can fill in x hrs other in y hrs then time it takes to fill tank is  xy/(x+y) because
in 1hr both can fill 1/x + 1/y = (x+y)/xy so can be completely filled in xy/(x+y)

3)inlet fill in  x hr and outlet empties in y hr
If x>y that means it takes more time to fill the tank than to empty it
If tank is already 1/p filled then we need to empty this much part
part emptied in 1hr is 1/y-1/x
time to empty 1/p part is

4)If pipe A fills tank t hrs faster than pipe B it means time taken by A is 10 greater than B
A= x+10 hrs
B=x hrs

5)part filled by A and B simultaneously and rest filled with C, if total time taken is xhr then
part filled with A+B in t min + part filled with C in x-t min = 1
|-----t min----|----------30-t min ---------|
          A+B                               C

Train 

conversion from kmph to mph multiply by 5/18
1)If two trains start from point A and B and move towards each other
A|-------------------------|B
                      d
and after they cross each other it takes a hrs for train from A to reach B and b hr for train  from B to reach A
A|---------t|-------------|B
         d1              (d-d1)
let they meet after time t then assume distance traveled by A is d1 and by B is d-d1
and speed of train from A is x and from B is  y km/hr
then
d1= xt and d-d1 = ty
y/x  = (d-d1)/d1          ---------------(1)

Now to travel d-d1 by train from A takes a hrs to
d-d1 = xa  and d1= yb                   -------(2)

equating value of d-d1 and d1 in 1 we get
y/x = xa /yb
or  y^2/x^2  = a/b     ------------(3)

2) If a person sitting in train A moving at x kmph and train B of length l crosses  men in t time  then
relative speed of train  B is l/t
absolute speed of train when moving in opposite direction to A is x - l/t

3) If two trains are moving together either in opposite or same direction then find their relative speed and do the usual calculation
like if trains A is l1 in length and train B is l2 in length then if they are moving in opp direction its same as passing l1+l2 with relative speed

Clock

relation between speed of minute and hr hand and min hand and sec hand
in time of 60 min, hr hand moves 5unit
in time of 60 min, min hand moves 60 units. So,
hr hand is 12 times slower than min hand
in time of 60 min, sec hand moves 3600 units so
sec hand is 60 times faster than min hand

angle traversed in t hrs

min hand traverses 360 degree in 60 min
so in t hr angle traversed is
m=360*t

hr hand will traverse (360/12) degree in 60min
so in t hrs it will traverse
h=30t

second hand  traverses 360*60 degree in 60min
so in t hrs
s=21600t

Problem When the hands of clocks coincide?
Solution
For hr hand and min hand to coincide
m-h = 360*n  where n is integer >=0
360t - 30t = 360n
11t =12n
so at t = 12n/11 they overlap

For sec and hr hand to coincide
s-h =360m
21600t - 30t = 360m
21570t = 360m
719t =12m
so at t = 12/719 * m hr sec and hr hand coincide

For all to overlap
12n/11= 12m/719
719n = 11m

Problem How many times hr hand and sec hand coincide in 12hr
Solution
we know that they coincide at time t=12n/11 when n integer >=0
so considering the starting time as 12 o'clock for
n=0 or 12hrs at which they coincide
for n=1 t=12/11 or 1hr 5.45min
for n=2 t=24/11 or 2hr 10.90min

for n=10 t= 120/11 = 10 hr 54.54mins
and for n=11 its same as n=0 that is 12 o'clock
so they overlap 11 times in 12 hrs

60
Problem At what time between 4 and 5 oclock hands of clock are at right angle
360t-30t= 90n
330t = 90n
11t=3n
t=3n/11
for 4<5 we have n>=44/3 and n<= 55/3
for n =15
t= 3*15/11 = 4hr 60/11 min

A watch that gains and loses time
Problem
A watch which gains 5 seconds in 3 minutes was set right at 7 a.m. In the afternoon of the same day, when the watch indicated quarter past 4 o'clock, what is true tim
Solution
for each 3 min it gains 5 sec means
3 min on correct clock is 3min 5sec on this clock
or 1/60*(3+5/60)hr is 3/60 hr on correct clock
or 37/720 hr on this clock is 1/20 on correct clock
time spent from 7 am to 4.15pm is 9hr 15mins or 37/4hr
so 37/4 hr on this clock means time spent on correct clock is (1/20*37/4*720/37) or 9hrs

find the time spent on incorrect clock and then calculate proportionately time on correct clock

Problem A watch gains uniformly, at 8am on sunday it is 5mins behind and the following sunday at 8pm its 5min 48sec ahead .when was it correct
Solution
It will show the correct time when it has gained 5mins by which its lagging
time spent by incorrect clock is 7day 12 hrs or 180hrs
in 180 hrs watch gained 5+(5+48/60)  = 54/5

total time gained = the time by which it was lagging + new time it has gained

therefore 5mins are gained in (180*5)/(54/5) = 83hr 20min


Allegation and mixture
cp of cheaper              cp of dearer
  c                                           d
now required price is m
for a unit quantity how much we should add cheaper quantity and dearer quantity to make the price m
lets add cheaper quantity x amount
then dearer quantity has to be added 1-x
now
m*1 = cx +(1-x)d
(d-c)x = d-m
x = (d-m)/(d-c)
and
y= (m-c)/(d-c)
ratio of cheaper/dearer quantity = (d-m)/(m-c)

Problem in what ration water must be mixed so as to gain 20% by selling at cost price?
Solution
cost price should be such that it gives profit % of 20 that is
sp= (1+.2)cp or
cp = 10/12 * sp =5/6 sp
this is the price that he is getting now when he sells at sp he gets profit of 20%

water        milk
0                 cp1
mean  5/6 * sp

cp1 = sp because he is now selling the mixture at the cost of milk that is  what was R rs/lt for milk is not R rs/lt for mixture
so ratio of water to milk =  (1-5/6)/5/6  =  1/5

Time and work

A can do a unit of work in n days then working uniformly
A's one day work = 1/n -----------------(1)

Almost all work problems will make use of the formula below
if for a unit of work
A ---------  t1 days
B ---------- t2 days
we find one days work in such case here it is
A's --------one day work ---------- 1/t1
B's -------- one day work ---------- 1/t2
we add the work of persons not their time
A+B ----------one day work ---------- 1/t1+1/t2   --------------(2)

A+B ----------1/days work ------------ t1t2/t1+t2 days       ---------------------(3)
For a unit of work if
n person                -------        tdays
m person(m<n)  -------         t (n/m) days
                (m>n)    -------          t(m/n) day
Example It takes 4 men to finish work in 10 day. How many days will be required if only i)2 men work or ii)10 men work
For less men we would need more days
2 men would need 10(4/2) = 20 days
10 men would need 10(4/10) = 4 days

If na1 persons in group A can do  a piece of work in ta1 days. It takes na2(na2 > na1) persons from group B to do same piece of work in tb2 days. If na2 persosns from group A and nb2 persons from s group B works together how much time will it take


For a unit of work
na1 --------------- ta1 days
na2(na2 > na1) --------------- ta1(na1/na2) days

nb1--------------tb1 days
nb2(nb2<na1) <="" p="">

If 4 men or 6 women or 10 girls can do a piece of work in 10 days How many days are required for 3 men 8 women and 6 girls
Solution
For a unit of work
4men --------------10days
3men--------------10(4/3)days

6 women ----------------10days
8 women----------------10(6/8)days

10girls-----------------10days
6girls-------------------10(10/6)days

3men+8wome+6girl -------one days work ------- 3/40 + 8/60 + 6/100
for a unit of work
3men+8wome+6girl ------------------ ------- 1/(3/40 + 8/60 + 6/100)

If B is p% more efficient than A then
for unit of work
B--------------xdays
A-------------x(1+pf)days

If B is 100% more efficient than B then
A------------x(1+1) =2x  A takes twice the time B takes

If B is 40% more efficient than B then
A ------------x(1+.4)=1.4x

Poblem A is thrice as good a workman as B and therefore is able to finish a job in 60 days less than B. Working together, they can do it in:
Solution
let time taken by A to finish work be x
time taken by B would be 3x
and difference of their time is given as 3x - x = 60
x=30
so B time is 90
one days work of A+B = 1/30+1/90

Recurrence Relations

Recurrence	Algorithm	Big-Oh Solution
T(n) = T(n/2) + O(1)	Binary Search	O(log n)
T(n) = T(n-1) + O(1)	Sequential Search	O(n)
T(n) = 2 T(n/2) + O(1)	tree traversal	O(n)
T(n) = T(n-1) + O(n)	Selection Sort (other n2 sorts)	O(n2)
T(n) = 2 T(n/2) + O(n)	Mergesort (average case Quicksort)	O(n log n)

Recurrence of form
1.T(n)= T(k) + T(n-k+1)+C
2.T(n) =T(k)+T(n-k+1)+O(n)
3.T(n)=2T(n/2) +O(n)

solution
1. O(n) , relation T(..) on right contributing also Th(n)

2. O(nlogn) ,O(n) contributing to the time complexity

3.same as 2,O(n) contributing to the time complexity

solver recurrence
1) T_n=3T_n/2       
   Tn = 3(3T_n/2²) = (3ⁱ )Tn/2ⁱ =
   3^log₂n =n^log₂3
2) Tn = 3Tn−1+2.
   3ⁿ − 1.
3) Tn = 2T(n−1) + 2.
   2ⁿ⁺¹ − 2.

Lame’s theorem (Complexity of the Euclidean algorithm). Let a and b be positive integers with a ? b, n be the number of divisions used by the Euclidean algorithm to find gcd(a, b) and k is the number of decimal digits in b. Then n <= 5k.Note that k <= log10 b?+1. Therefore, n = O(log b) divisions are used by the Euclidean algorithm.

Couting problems with Recurrence Relations

Problem Find number of bit string s with no two consecutive 0's
lets call an be number of  bit strings of lenght n where we do not  have 2 consecutive zeros
1) number of bitstrings ending with 0 that should have 1 with them, that is of the form
----|10 and the first part can be occupied by any valid bit string that itsself donot have consecutive zero that is an-2
2) number bit strings ending in 1, ----|1 which is an-1
so an = an-1 + an-2 where initial conditions should be specified for a0 a1 and a2
a0 = 0
a1=2 {0,1}
a2 = 3{01,10,11}
the recurrence seems to be like Fibonacci sequence where a1 corresponds to f3, a2 to f4  i.e  an = Fn+2
This is also relation for subsets of n numbers which do not contain consecutive number
{1,2,3} subsets are F(5) i.e {empty,{1},{2},{3},{1,3}} 5 subsets

Problem Count all number of n digit where number of zero is even
1)any number of for 9,57 which has no zero is valid, and such numbers in form of recurrence is
n-1|9 , n-1|8 , n-1|7... that is all strings ending in some non zero digit and having first n-1 as valid string
i.e 9*an-1
2)we have not counted any number which has zero digit in it ...(we use little to much recursive thinking here)
numbers with zero digit can be formed by adding a zero to number with even number of zeros
number with even number of zeros = total numbers - number with odd zeros(which we have named an)
 10^n-1 - an-1
we get final reccurence as an = 8an-1 + 10^n-1

Solving Recurrence Relations


www.cs.duke.edu/courses/cps130/.../Homeworks/Solutions/H2-solution.pdf   //order of growth problem
www.cse.psu.edu/~berman/sol_565_1.pdf

1) If f(n) = Th(g(n))  { 0<=c1g(n) <= f(n) <= c2g(n) } for some n>= n0 and c1,c2,n0 >=0 
then f(n) = O(g(n)) because it implies 0<= f(n) <= c2g(n)

2)For polynomials p(n) = Th(n^d)

3)o notation
if f(n) = o(g(n))
f(n) becomes insignificant relative to  g(n) for large values of n


4) if
f(n) = w(g(n))



Comparing various functions time complexity
5) exponential and polynomial function
exponential functions with base greater than 1 grows faster than polynomial functions that is
n^b = o(a^n) for a > 1
lim{n->infty} ( n^b / a^n)  = 0

6)exponential e^x
e = 2.71828e^x = {sum o to inty}  x^i / i!
i.e e^x  >= 1+ x
when x = 0 its equality
if |x| <=1
e^x <= 1+x+x^2
so e^x = 1+x+Th(x^2)

7)logarithm functions
polylogatithmic functions grow more slowly than polynomial in the similar manner like polynomial grows slowly than exponential
we use substitution to prove that
substitute log n for n and 2^a for a


a^(log_bc) = c^(log_ba)
 abc converts to reverse, cba


8)
Transitivity is true for all five operators like
f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) =O(h(n))

Reflexivity is also true for O,Th and Omega that is for all asymptotic tight bounds
f(n) = O((n))

Symmetry is true for Th only that is
f(n) = Th(g(n)) if and only if  gn = Th(f(n))

Case when we might not be able to compare function like in case of
trignometric functions which oscillates n^(1+sin n) and n here 1+sin n oscillates between 0 and 2