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