Tuesday, March 15, 2011

Latex

ExampleLaTeX codeResult
Polynomial {tex}a^2+b^2=c^2{/tex} {tex}a^2+b^2=c^2{/tex}
Quadratic formula {tex}x={-b\pm\sqrt{b^2-4ac} \over 2a}}{/tex} {tex}x={-b\pm\sqrt{b^2-4ac} \over 2a}}{/tex}
Tall parentheses and fractions {tex}2 = \left( \frac{\left(3-x\right) \times 2}{3-x} \right){/tex} {tex}2 = \left( \frac{\left(3-x\right) \times 2}{3-x} \right){/tex}
{tex}S_{\text{new}} = S_{\text{old}} - \frac{ \left( 5-T \right) ^2} {2}{/tex} {tex}S_{\text{new}} = S_{\text{old}} - \frac{ \left( 5-T \right) ^2} {2}{/tex}
Integrals \int_a^x \!\!\!\int_a^s f(y)\,dy\,ds = \int_a^x f(y)(x-y)\,dy{/tex} \int_a^x \!\!\!\int_a^s f(y)\,dy\,ds = \int_a^x f(y)(x-y)\,dy{/tex}
Summation {tex}\sum_{m=1}^\infty \sum_{n=1}^\infty \frac{m^2\,n} {3^m\left(m \,3^n+n \,3^m\right)}{/tex} {tex}\sum_{m=1}^\infty \sum_{n=1}^\infty \frac{m^2\,n} {3^m\left(m \,3^n+n \,3^m\right)}{/tex}
Differential equation {tex}u'' + p(x)u' + q(x)u = f(x),\quad x>a{/tex} {tex}u'' + p(x)u' + q(x)u = f(x),\quad x>a{/tex}
Complex numbers {tex}|\bar{z}| = |z|, |(\bar{z})^n| = |z|^n, \arg(z^n) = n \arg(z){/tex} {tex}|\bar{z}| = |z|, |(\bar{z})^n| = |z|^n, \arg(z^n) = n \arg(z){/tex}
Limits {tex}\lim_{z\rightarrow z_0} f(z)=f(z_0){/tex} {tex}\lim_{z\rightarrow z_0} f(z)=f(z_0){/tex}
Integration with limits and fractions {tex}\int\limits_{ -\infty }^{a} \frac{e^{-(x-\mu)/s}} {s(1+e^{-(x-\mu)/s})^2} \,dx = {1 \over 1+e^{-(a-\mu)/s}}{/tex} {tex}\int\limits_{ -\infty }^{a} \frac{e^{-(x-\mu)/s}} {s(1+e^{-(x-\mu)/s})^2} \,dx = {1 \over 1+e^{-(a-\mu)/s}}{/tex}
Continuation and cases {tex}f(x) =
\begin{cases}
1 & -1 \le x < 0 \\
\frac{1}{2} & x = 0 \\
1 - x^2 & \mbox{otherwise}
\end{cases}{
/tex}
{tex}f(x) =
\begin{cases}
1 & -1 \le x < 0 \\
\frac{1}{2} & x = 0 \\
1 - x^2 & \mbox{otherwise}
\end{cases}{
/tex}
Prefixed subscript {tex}{}_pF_q(a_1, \dots, a_p;c_1, \dots, c_q;z) \\ ~\qquad = \sum_{n=0}^\infty \frac {(a_1)_n \cdots (a_p)_n}{(c_1)_n \cdots (c_q)_n} \frac {z^n}{n!}{/tex} {tex}{}_pF_q(a_1, \dots, a_p;c_1, \dots, c_q;z) \\ ~\qquad = \sum_{n=0}^\infty \frac {(a_1)_n \cdots (a_p)_n}{(c_1)_n \cdots (c_q)_n} \frac {z^n}{n!}{/tex}

Tuesday, March 1, 2011

Asymptotic growth of function (Comparision)

Rules for comparing asymptotic growth of functions
1)f(n) < g(n) if





2) if f(n) < g(n)  then 1/g(n) < 1/f(n)

Ordering functions according to their asymptotic growth

1) nα < nβ 
whenever β>α
Examples
n1.2 < n2
n0.02 < n0.2

2) 1 < log(log n) < log n < nε < nC < nlog n < Cn < nn < CCn
where 0 < ε < 1 and C > 1
because  f(n)/g(n) --> infinity  as n --> infinity  for each f(n) < g(n)
Examples
nlog n < 2n
log n < n0.0001
nn < 22n

3)Using the reciprocal rule in above hierarchy we can deduce that
1/nε < 1 / log n 
1/nε < 1
and so on

4) log n!  <  n log n

5)2n  <  en  <  n!  < 22n

Reference
Concrete Mathematics, Graham Knuth Pattasnik
Algorithms, Cormen   Leiserson   Rivest

Tuesday, February 15, 2011

Symbolic logic - First order predicate logic

Implication
premise --->consequence
p-->q

p q   -->
------------
0 0   1
0 1   1
1 0   0
1 1   1
used terms to express this are
1)p is sufficient for q     //
2)q is necessary for p
2)q if p
3)q whenever p
4)p only if q

Converse is q-->p
contrapositive  is -q --> -p
Biconditional  p <--> q     true when truth values same for p and q
statements like ' if and only if '  or  'p is necessary and sufficient for q'

Conjunction
A and B


Exclusive disjunction
(p Ú q) · ~(p · q) either p is true or q is true but not both

A compound proposition that is always true is Tautology and
which is always false is Contradiction
p and q are logically equivalent if p <---> q is tautology that is p and q have same truth values


Quantifiers
Universal Quantification
proposition function P(x) is true for all values of x in the universe of discourse
statement like for all x or for every x
equivalent to P(x1) and P(x2) and P.........(xn) where xi is universe of discourse

Everything  is
Everything is beautiful
∀y F(y)

Nothing is
 Nothing is beautiful
∀y ¬ F(y)


Existential Quantification
there exists an element x in the universe of discourse such that P(x) is true
statement like there is an x such that or there is at least one x such that
equivalent to P(x1) or P(x2) ...  p(xn)

Consider predicate F(y) which is true if y is beautiful
something is
 existential quantifiers tell that there is something or some y for which F(y) is true
something is beautiful
∃y F(y)

something is not
something is not beautiful
there is some y which is not beautiful
∃y ¬ F(y)

Nothing is
Nothing is beautiful
It is not the case that something is beautiful
 ¬∃y F(y)
that is negation of something becomes nothing

Everything is
everything is beautiful
It is not the case that something is not beautiful
¬∃y ¬ F(y)


Property of connectives
1)A -> B <===> -B -> -A
2)A->B <==> -A or B
3)∀y (P(y) and Q(y))  = ∀P(y) and ∀Q(y)
not true for OR that is universal quantification is not distributive over OR operator
4)∃y (P(y) OR Q(y))  = ∃y P(y) OR ∃y Q(y)
not true for AND that is existential quantification is not distributive over AND

Law of quantification
Distributive law
∀x (P(x) and Q(x)) <==>  ∀xP(x) and ∀xQ(x)
∃x (P(x) or Q(x))  <==> ∃y P(x) or ∃y Q(x)
∀xP(x) or ∀xQ(x)  ==> ∀x (P(x) or Q(x))
∃x (P(x) and Q(x))  ==> ∃y P(x) and ∃y Q(x)

example
∀x P(x) means (P(a) and P(b))
∃x P(x) means P(a) or P(b)
The best way  to understand the distributive property is to expand  the symbol ∀ and ∃ into basic definition of AND and OR
Consider  p(x) be cube(x) and q(x) be small(x) then
1)∀x cube(x) or ∀x small(x)  ==> ∀x (cube(x) or small(x))
 we can write the same as
Lhs: ( cube(a) and cube(b) ) or ( small(s) and small(t) )
these is true when either there exist two cubes a and b or two small objects s and t
Rhs: (cube(a) or small(a)) and (cube(b) or small(b))
if Lhs is true then this is also true because its true when either a  and b  is cube or small

but the reverse of the implication says that  if a is cube and b is small then lhs should be true but it is not so not bidirectional

Quantifier Independence
∀y∀x F(x,y)  <==>∀x∀y F(x,y)
∃y∃x F(x,y)  <==>∃x∃y F(x,y)
∃y∀x F(x,y)  ==>∀x∃y F(x,y)
but not ∀x∃y F(x,y)  ==>∃y∀x F(x,y)

Translating statement in predicate logic


1) Barber Paradox
the statement says "Barber shaves those residents who donot shave themselves"
∃y ∈ S : Barber(y) ∧ (∀x ∈ S : (Shaves(y, x) ↔ ¬Shaves(x, x)))
here paradox because when x=y  then it can never be true
remember to check for extreme cases always

2)
i) Some A's are B's
there exist some x that is both A and B

∃x(A(x) & B(x))

ii)Some A's are not B's
ther exist some x that is A and is not B
∃x(A(x) & ¬B(x))

iii)All A's are B's
for all x if it is A then it is B
∀x(Ax → Bx)

iv)No A's are B's
It is not the case that there exist some x that is A and is also B
¬∃x(Ax & Bx)
for all x if it is A then it is not B
∀x(Ax → ¬Bx)

3)implication we use with universal quantification and with existential quantification we use and connective
example S: Some lions don't drink coffee

L(x) :  x is lion
P(x) : x is pet
D(x) : x drinks coffee
S1:  ∃x (L(x) P(x)) is wrong
S2 : ∃x (L(x) AND P(x)) is correct

4)statement involving : and, but, moreover, however,although, and even though are conjunction

5)unless means disjunction

http://www.earlham.edu/~peters/courses/log/transtip.htm 
www.niu.edu/~gpynn/205_11_handout.pdf

Monday, February 14, 2011

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 '

Tuesday, February 8, 2011

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

BTree Algorithms

If t is minimum degree  of B tree

For nodes other than root
Minimum number of keys
Every node other than root must have atleast t-1 keys 
so every internal node must have at  least t childrens



 Maximum number of keys
every node can contain at most 2t-1 keys
therefore internal node can have at most 2t children

For root

For Non empty tree root should have at least 1 children

Height of B Tree
Height of Btree is function of total number of keys in Btree

number of nodes at depth 1 has to be >=2 So we have atleast 2 nodes at depth 1
next level would have t nodes for each node in level 1 so t*2
depth 3 t^2*2
for depth h  it has at least t^h-1 * 2
Each node has t-1 number of keys 
so the tree has at least 1+ (t-1) * {sum i to h}2t^i-1    keys
n >= 1+ (t-1) * {sum i to h}2t^i-1
n>=2t^h -1
h <= log(t, (n+1)/2)

Operations on Btree
n(x)+1 way branching decision since there are n+1 different choices to follow
Searching
Search (x,k)
find the smallest index such that k < key[xi]  //from left find the position which is just greater than k
if its the key k then return the index and node
else
if its leaf then return NIL         //failed search
 else
        Disk-Read(ci[x])           // bring the new children in memory and 
      Search(ci[x],k)                  //search child

Performance
Children is brought in memory  if key not found in present node
number of disk pages accessed is height of tree  Th(h) = Th(log(t,n))
searching the index at each node takes O(t)
so total time = O(ht) =O(t log(t,n)) that is for each disk read we have to search that nodes keys

Create Empty Btree
Create Root
B-Tree -Create(T)
allocate a disk page  x //O(1)
set it as leaf and number of keys n[x]= 0
write it back to disk
assign it as root root(T)=x
O(1) disk operations and O(1) CPU time

Insert Key
New key has to be inserted such that it maintains the B tree property of min and max nodes

If leaf y is full then it contains all 2t-1 key, that is, maximum allowed and we
split the node y around its median key key[y] into two nodes having t-1 keys each
move y to parent to identify dividing point
If y's parent is full then it must be splited too

We can insert the key on pass from root to leaf node
Travel down the tree searching for the position where the new key belongs and split each full node we come along the way including the leaf 

Insert(T,k)
If root is full that is it has 2t-1 keys then
  s= allocate-node() //make new node s as root
  set r as child of s
  split child (s,1,r)    //
  Insert-Nonfull(s,k)  //insert key k in non full node s
else
 Insert Nonfull(r,k)

Performance : O(th) time and disk access =O(h)

B tree increases in height at top not at bottom unlike binary tree

Insert-Nonfull(x,k)
i =n[x]
If x is leaf node then  // that is we have only root and its not full

  while k < keyi[x]       //traversing  from right key
          key(i+1)=key(i)         // move the key to right
             i=i-1
   key(i+1)[x] =k           //store the key at position i+1
   Disk Write(x)
Else  //when not leaf
  loop to find right index in x to search which children
  Disk-Read(ci[x]) //read that children in memory
  If the children is full
   Split-Tree(x,i,c[x])
   if k > keyi[x]
     traverse i+1
Insert-Nonfull(ci[x],k)

Performance
There are O(1) disk read and write operations on each recursion so total O(h)
CPU time O(th)
tail recursion so can be converted into while loop and allowing number of block in memory O(1)




Split Node
inputs :   x non full node. child of x, y, is full
output : will split child y and adjusts x to have additional child

Height of tree increases by one on split of root
Its the only operation which increases the height

Split(x,i,y)
y is ith child of x
divides child y into y and z,

z = allocate-node()            // to have last t-1 keys that is,  larger t-1 keys
for index j to t-1
 change key position       // what was j+t key in y will be now jth key in z
if node y is not leaf then
 change child positions for z //what is j+t child in y is jth child of z
similarly move the index position and key for x to make space for
median[y]
key[xi] = key[yt]
and n[x] = n[x] + 1

Disk-Write(y,z,x)

Performance
O(t) time  to change the children and keys of x and z
and O(1) disk operation

Deletion
Deletion from an internal node requires that nodes be rearranged that is when  interal node has minimum number of keys

Btree-Delete deletes the key k from the subtree rooted at x.
guarantees that whenever procedure is called recursively on node x, the number of keys is at least t that is 1 more than required to satisfy B tree property
allows to delete a key from the tree in one pass without back up

Procedure
preceding child is the left child
predecessor of key is the largest key in its left child
1)If  key k is in node which is leaf then delete key k from x
2)If key k is in internal node x then
 i) if child y that precedes x has at least t keys then find the predecessor k' of k in the subtree rooted at y.
   Recursively delete k' and replace k by k' in x
 ii)If child z that follows k in the node x has atleast t keys then find successor k' of k in subtree rooted at z
iii)If both y and z have only t-1 keys then merge k and all of z in to y so that now


B+ tree
order of m : internal node can contain m-1 keys

Deletion
We always delete key from leaf
If key is in index also we delete from there also

Redistribution of leaf node:
middle key is copied up and sibling is borrowed
if sibling has atleast t/2 keys than we can redistribute the sibling (same parent as L)
Key is deleted from leaf and a key is borrowed from sibling inserted into L and a common parent is changed to middle key that is if
             k |  l  |  m |   
            /   \     \      \
          /       \     \      \
      a  b     c d e
delete a 
key a is in node L(a,b)
and if we delete a and t -1 = 2 that is fill factor is 2 then
1)we can borrow a key c from sibling
2) we have to replace k also with the middle key after sorting these two sibling that is d
so we move d to parent

             d |  l  |  m |   

            /   \     \      \

          /       \     \      \

      a  c      d e

Merging 
toss parent index entry and pull down index's parent if index deficient
If the sibling do not have sufficient node then we merge L with its sibling

          q
        /    \
   o  p    d |  l  |   

 /  |  |     /   \     \     
          /       \     \   
      a  c      d e

delete c
key c is in L (a,c)
since siblings do not have sufficient keys we merge L and sibling (d e)
and delete the parent d but that would make parent node l deficient so we need to merge index page also
we pull down  parent of l, q down that is
          q

        /    \

   o  p      l     

 /  |  |     /   \          
          /       \      
      a d e

               

   o  p q  l     

 /  |  |     /   \          
          /       \      
      a d e



Redistribution in Non leaf node

         q

        /    \

r  o  p      l     

 /  |  |     /   \          
       t   /       \      
      a d e


here we can move p to position of q and q with l
right child of  p will become left child of new position of q
          p

        /    \

r  o       q  l     

/  |        /   \          
          /       \      
         t        a d e



1)If index page and leaf page are not below fill factor
delete record from leaf page Arrange keys in ascending order to fill void
If key appears in the index page use next key to replace it
First check left then right for merging

2)If leaf page is below fill and index page not then
combine leaf page and its siblings
Change index page to reflect change
3)If both index and leaf are below fill then
Combine leaf and siblings
Adjust index page
Combine index with its siblings

Problem 


If we delete 60 in above  case from node 60 65 we will have less than 2(fill factor) in the node so we must merge this node with left node 50 55 and also we have to delete its index 75 But deleting index
Merging of leaf pages reduces the index entry by one
will result in less than fill factor for parent 85 so index pages need to be merged Since 60 is the only key and merging reduces the key so we need to delete the root

 Problem


 Deleting 25 from 25 28 30 leaves number of keys above fill factor so we delete 25 from leaf and we need to delete corresponding key also and fill that position in parent with key next to 25 that is 28

 If it had been 25 alone in that node we would have deleted that node and also 25 from parent and set left of parent 25 to left of 50
Problem
Delete 6 from above tree
Deleting 6 we need to delete from index also which would leave index below fill factor so we need to merge index pages


avid.cs.umass.edu/courses/445/f2008/17-tree-indexes-2.pdf

Wednesday, January 19, 2011

Operating system Problems

Deadlock problems
Things to Remember
1)Using Banker Algorithm you always work on NEED not MAX claim
2)We add the Allocation NOT  the NEED to Avaiable
3)Available resources, when total resources is given = total - allocated
4)when a new process enters the system find its need request and new available as
new available = available = request for process
5)A process might not be in deadlock or safe state then it is in unsafe state that is a process might not request the maximum need and so wont go in deadlock
6)Deadlock can involve process not in circular chain if they request resource currently held by process in circular chain
7)When available is greater than need of every process we have safe sequence

Problems
Problem Consider p processes each needs a max of m resources and a total  r resources are available. What should be relation between p,m,r  to make the system deadlock free?

Solution:
The worst case is when every process is holding m-1 resource and a process requests 1 more resource and that cannot be fullfilled if we only had one more resource we can allocated any process that resource and full fill others need also  So total number of resources should be

r > (m-1)*p

we can prove that system can safely reach the state where each process is allocated m-1 resource


We can also interpret above equation as
mp < r + p
that is sum of all the resource need of all process should be less than r+p

Problem A system has 3 processes and 4 available resources with max need of each process as 2
Prove that system is always deadlock free
Solution we check the worst case we derived above that is
r>(m-1)p
here m=2 and p=3 so r should be greater than 3 Hence its deadlock free


Detect Deadlock from code
whenever we are asked to find if the system is in deadlock we have to look if
1)request of the form below and
2)processes p0 and p1 executed simultaneously

p0                       p1
Request Ri     request Rj
request Rj      request Ri

 Problem


Solution:
Even processes requests
Ri
Ri+2
that is requests resource i and i+2 from beginning

odd process requests
R(n-i)
R(n-i-2)
that is ith and i-2 from last

consider even process as index i and odd as j
Now system can be in deadlock when

1)Ri = Rn-j-2 that is
i = n-j-2
i+j = n-2
and
2) i+2 = n-j that is
i+j = n-2

So we have equation  i+j=n-2
if this is satisfied for any two processes then only deadlock is possible
but we know that i is even and j is odd so
1) i+j is odd and RHS n-2 can be odd only when n is odd and also
2) if number of process are k then i and j has to be < k

Lets see for
1)n=41 and k=19
n-2 = 39 and maximum j can be 19 and i 18 which combine donot ma ke 39 so no deadlock possible
2)when n=21 and k=12
we have n-2 = 19 and i max can be 12 and j 11 which can make the total sum so lets check
when i =10 and j=9 . yes we have deadlock

Scheduling Problems
Things to Remember
In round robin overhead is minimized when time quanta q is maximized
In round robin we use queue order that is does not necessarily
Convoy effect when process needs to use resource for a small time but other process is holding it for long time. FCFS scheduling may suffer convoy effect.
I/O bound process do not use their entire CPU quanta. Better utilization by giving high priority to I/O bound process because of convoy effect


Problem
Use time q=5ms

Solution
Round robin
Shown below is gantt chart with queue


waiting time
total time that is time from arrival to completion - time executing (given in table)
for P1 : 55 - 20 = 35
for p2 : (77-4) - 32= 41
for p3 : 59-14-9 = 36
for p4 : 65-12-11=42
Average 38.5


Shortest Job first
p1 p4 p3 p2
Average = 17.75


Shortest Remaining First




Problem Consider Exponential average to predict length of next CPU burst
1) a=0
then system always uses past history to predict CPU burst without taking in account the recent observation
2)a=.99
then gives very high weight to recent observation and very less to past history and hence almost no memory is required for history


Problem 10 i/o bound process and 1 cpu bound process Each I/O bound process issues I/O operation once for every 1ms of CPU computing and each I/O takes 10ms to complete . context switch overhead = .1ms What is CPU utilization for
1)q=1 ms
Solution CPU utilization is (execution time )/(execution time + overhead time)
for each time quanta system incurs cost of .1 so
1/1.1 = .91
2)q=10ms
A cpu bound process will run for 10ms then a context switch of .1ms total 10.1
each i/o bound process interrupts cpu to context switch for I/O activity after 1ms so total is 1.1 and for 10 process would be 10*1.1
for a execution time of 20ms we have
CPU utilization  = 20/21.1 = .94

Multiprogramming
If a job spends p fraction of time in I/O waiting then
with sequential execution CPU utilization is 1-p
If p =.60 that is its spending 60% of time doing I/O then CPU utilization is only 40%
For multiprogramming with n jobs in the memory
probability that all n processes are waiting for I/O is p^n
CPU utilization is 1-P^n that is probability that at least one process is ready for CPU
this is on the assumption of no cpu overhead

Problem  Suppose two jobs, each of which needs 10 minutes of CPU time, start simultaneously. Assume 50% I/O wait time.
a) How long will it take for both to complete if they run sequentially?
solution Each process takes total of 10 min for I/O + 10 min for CPU that is 20
Total time for complete T = 20min +20min = 40mins
b) How long if they run in parallel?
probability p for which time is spent in I/O
p = 1/2 //50% I/O
CPU utilization = 1-p^2 = .75
T*.75=20


File system
Inode
A files block are scattered randomly
Inodes keeps pointer to data blocks
Each Inode has 15 pointers
First 12 points directly to data block
13th points to indirect block that is block containing data block
14th points to doubly indirect block that is points to block containing 128 addresses of indirectblock
15th points to triply indirect block that is block which points to doubly indirect block
Consider block size of 4K as in unix file system
then 12 direct block pointer can point to 12*4K =48K
if each pointer is of 4 byte then a single block can accomodate 4K/4 = 1K
one indirect can point to 1K*4K =4MB
one doubly indirect 1K*1K*4K


Problem  Let there be 8 direct block pointers, and a singly, doubly, and triply indirect pointer in each inode and  that the system block size and the disk sector size are both 4K. If the disk block pointer is 32 bits, with 8 bits for identifying physical disk, and 24 bits to identify the physical block, then:
1)maximum file size?
Solution each block can hold = 4K/4 = 1K pointers
so direct blocks = 8*4K
single indirect =1K*4K
double indirect =1K*1K*4K
triple indirect = 1K*1K*1K*4K
all sums around 4TB

2)what is maximum file system partition size
Since disk block pointer is 32 bit it can point 2^32 blocks
which includes 8 bits to identify physical disk and 24 bits to identify block
since each block is 4K so total = 16TB

3)assuming inode in memory how many disk access are required for byte position 2634012
since each block is of 4K we find the offset 2634012 modulo 4K = 284  and block number is 643
this block will be addressed by single indirect block so number of access = 1for accessing indirect block and 1 for accessing the actual block =2


Memory Management

.
Remember to always add the time to check cache or tlb even when we have miss.

Problem Assuming single level page table If a memory reference takes 100 nanoseconds, time for memory mapped reference is ?
i)when no TLB
 100 for accessing Page table and 100ns for accessing actual data frame
ii)TLB with access time 15ns and .9 memory hit in TLB
 if page number is present in TLB then 15+100
 if page number not found in TLB then 15+100+100
Hence EMAT = 115*.9 + 215*.1

Problem Consider demand paging with the page table held in registers, memory access times
8 msecs for  page fault if --  empty page is available or the replaced page is not modified,
20 msecs if the replaced page is modified
70% of the time the page to be replaced is modified
100 nsecs memory access time


What is the maximum acceptable page fault rate (P) for an effective access time of no more than 200 nsecs?
Solution
p = page fault rate
and m be percentage of time page is modified then

EMAT >= 1-p(memory access time) + p (m (time to write back dirty page & service fault) + (1-m)(time to service page fault))

.2 >= 1-p(.1)+ p (.70*20000 + .30*8000)

Problem Consider average size of a process as p, size of a page table entry is e, what page size minimizes wasted space due to internal fragmentation and page table?
 Solution
page tables used to store the frame number and control bits is actually a overhead or wasted space
so we calculate wasted space  = space used by page table + space wasted due to internal fragmentation
avg number of pages =p/s
and total size of all pages =pe/s
avg space wasted due to internal fragmentation s/2

so total waste = pe/s + s/2
to find min take derivative
- pe/s^2 + 1/2 = 0
 pe/s^2 = 1/2
 s = sqrt(2pe)

 
Problem Consider the average process size is 128 KB and the number of page entries is 8. What will be appropriate page size
Solution



Page replacement
one has reference time highest means it was referenced farthest on left 
FIFO doesnot depend on the reference time but on the load time
NRU replaces one with r=0,w=0
second chance replaces earliest page with r=0
 If you are given page has been modified written to or dirty then it takes 2 I/O for replacing that page
1 to bring in new page and 1 to write back this page
Virtual to physical address binding takes place during runtime

Consider the following piece of code which multiplies two matrices:
int a[1024][1024], b[1024][1024], c[1024][1024];
multiply()
{
   unsigned i, j, k;
   for(i = 0; i < 1024; i++)
       for(j = 0; j < 1024; j++)
           for(k = 0; k < 1024; k++)
               c[i][j] += a[i,k] * b[k,j];
}
Assume that the binary for executing this function fits in one page, and the stack also fits in one page. Assume further that an integer requires 4 bytes for storage. Compute the number of TLB misses if the page size is 4096 and the TLB has 8 entries with a replacement policy consisting of LRU.
Solution:
1024*(2+1024*1024) = 1073743872
The binary and the stack each fit in one page, thus each takes one entry in the TLB. While the function is running, it is accessing the binary page and the stack page all the time. So the two TLB entries for these two pages would reside in the TLB all the time and the data can only take the remaining 6 TLB entries.
We assume the two entries are already in TLB when the function begins to run. Then we need only consider those data pages.
Since an integer requires 4 bytes for storage and the page size is 4096 bytes, each array requires 1024 pages. Suppose each row of an array is stored in one page. Then these pages can be represented as a[0..1023], b[0..1023], c[0..1023]: Page a[0] contains the elements a[0][0..1023], page a[1] contains the elements a[1][0..1023], etc.
For a fixed value of i, say 0, the function loops over j and k, we have the following reference string:
a[0], b[0], c[0], a[0], b[1], c[0], ¡ a[0], b[1023], c[0]
¡
a[0], b[0], c[0], a[0], b[1], c[0], ¡ a[0], b[1023], c[0]
For the reference string (1024 rows in total), a[0], c[0] will contribute two TLB misses. Since a[0] and b[0] each will be accessed every four memory references, the two pages will not be replaced by the LRU algorithm. For each page in b[0..1023], it will incur one TLB miss every time it is accessed. So the number of TLB misses for the second inner loop is
2+1024*1024 = 1048578
So the total number of TLB misses is 1024*1048578 = 1073743872
Partitions
It is possible to get the new block from the external fragmentation

Problem Consider following hole sizes in memory in  this order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB. Which hole is taken for successive segment
request of 12KB, 10KB, 9KB for
a. First fit?
20KB , 10KB,18KB
b. Best fit?
12KB, 10KB,9KB
c. Worst fit?
20KB,18KB,12KB
d. Next fit?
20KB,18KB,9KB

Secondary storage problems
Problem Consider
10000 RPM spindle speed,
300 Sectors per track,
512 Bytes per sector,
9801 cylinders (tracks per platter side),
24 tracks per cylinder (12 platters),

6ms average seek time,
0.6 ms track-to-track seek time.

Suppose you want to read a 4,608MB file under the following two sets of assumptions:
a) Assume the file is allocated consecutive sectors and tracks on one surface of one of the platters. How long does it take to read the file’s data and what is the average throughput?

Solution
total time to read file =avg seek time+ avg rotational delay + transfer time
rotational delay = 60s/m  / 10000rev/min= 6ms /rev

Calculate bandwidth
total number of bytes in track = total number of sectors * number of bytes per sector = 300*512 = 153600 bytes/sector
bandwidth = number of bytes in track/ rotational delay = 153600/6 bytes/sec
transfer time for x bytes = x/bandwidth = 6*x/156300

For file
Number of blocks in file = 4608000 / 512 blocks = 9000 blocks
or total of  30 tracks

transfer for first track T1 = average seek + average rotational + transfer time
=6ms+3ms+6ms =15
For remaining tracks it would be 6ms transfer time for track + .6ms track to track time
6.6*29
total time =15 +6.6*9
average throughput is 4608000/total time



b) If the individual blocks are randomly scattered over the disk how long will it now
take to transfer this file and what is the average transfer rate?



we read each sector with same avg rotational delay and  avg seek time
so each request is uniform with time of 6ms avg seek time+3ms of avg rotational dealy+6/300 to read a sector =9.02
and there are 9000 such sectors so total time would be 9000*9.02ms

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