Basics
Sum Rule: The rule of sum states that if there are $n$ choices for one action and $m$ choices for another action, and the two actions cannot be done at the same time, then there are $n+m$ ways to choose one of these actions.
Ex: If you have 2 chapters in TOC, 3 chapters in Algorithms, and 1 chapter in CN that are yet to be completed, How many choices of chapters do you have today to read from the uncovered syllabus?
I can pick any one of the 6 (i.e., 2 + 3 + 1) chapters to be completed.
Product Rule: The rule of product states that if there are n ways of doing something, and m ways of doing another thing after that, then there are $n \times m$ ways to perform both of these actions.
Ex: If you have 3 shirts and 4 pants in your ward board, you have total 12 (i.e., 3 multiplied by 4) ways to dress up today.
Please note that, this is not 3+4, why because, by choosing shirt, only partial part of the work completed not the complete work. Hence, sum rule can’t be used.
Choosing vs Permuting:
- Let there are five 1-mark questions in the exam, you need to answer four questions correctly for passing the exam. - Here order not matters - That is $\binom{5}{4}$
- Let there is a running race of 100 people. You need to choose 3 people for awarding first, second and third winners - Here order matters - That is $100*99*98$ or $\binom{100}{3}*(3!)$ - Here, people are not ordered by default, but they are ordered after the race.
Do not go blindly with ordered/un-ordered terms. Understand the context.
- Let GO decides to conduct interviews of any two rankers in top 100 rankers. Then howmany possibilities GO have to select two rankers where top ranker interviewed first and the other interviewed second? - Here order matters. That is $\binom{100}{2} \times (1)$ - Here, people are already ordered, we are just utilising the same order.
- Let GO decides to conduct interviews of any two rankers in top 100 rankers. Then howmany possibilities GO have to select two rankers and interviewed in any order? - Here order not matters. That is $\binom{100}{2} \times (2)$ - Here, people are already ordered, however, we are not utilising that order.
Howmany length 3 strings we can make with the alphabet set {A,B,C} ?
Here after choosing 3 alphabets from the set, we need to permute them. $ \Rightarrow \binom{3}{3} \times (3!)$
Howmany length 3 strings we can make with the {A,B,C,D} ?
Here after choosing 3 alphabets from the set, we need to permute them. $\Rightarrow \binom{4}{3} \times (3!)$
i.e., I will choose 3 alphabets from the 4 first, then I will permute them in 3! orders.
Howmany length 3 sets we can make with the {A,B,C,D} ?
Here after choosing 3 alphabets from the set, we can't permute them. $\Rightarrow \binom{4}{3} \times (1)$
i.e., I will choose 3 alphabets from the 4 first, that's it.
Howmany length 4 strings we can make with the {A,B,C,A} ?
Here after choosing 4 alphabets from the set, we need to permute them. However, there are same like elements present.
So, I will choose 2 positions in the 4 positions for A's and those will arrange in only one way. Remaining 2 positions for B and C and I will arrange them in 2! ways. $\Rightarrow [\binom{4}{2} \times (1!)] \times [\binom{2}{2} \times (2!) ] $
That is equivalent to say, $\frac{4!}{2!.2!} . (2!) = \frac{4!}{2!}$
In general, if $n_1 \text{ number of same elements}, n_2 \text{ number of same elements} \;and\; n_3 \text{ number of same elements} $ are present, then overall possibilities = $\frac{(n_1+n_2 + n_3)!}{(n_1)! \times (n_2)! \times (n_3)! }$
It is verymuch important to know "How that is equivalent ?" before going forward in this blog.
in total $n_1+n_2+n_3$ positions, first select $n_1$ positions for $n_1$ kind elements and permute them,
then remaining $n_2+n_3$ positions, select $n_2$ positions for $n_2$ kind elements and permute them,
after that in the remaining $n_3$ positions, fill with $n_3$ kind elements and permute them.
$= [\binom{n_1+n_2+n_3}{n_1} \times (1!)] \times [\binom{n_2+n_3}{n_2} \times (1!)] \times [\binom{n_3}{n_3} \times (1!)]$
$= [\frac{(n_1+n_2+n_3)!}{(n_1)! \times (n_2+n_3)!} \times (1!)] \times [\frac{(n_2+n_3)!}{(n_2)! \times (n_3)!} \times (1!)] \times [\frac{(n_3)!}{(n_3)! \times (1)!} \times (1!)]$
$= [\frac{(n_1+n_2+n_3)!}{(n_1)! \times (n_2+n_3)!} ] \times [\frac{(n_2+n_3)!}{(n_2)! \times (n_3)!} ] \times [\frac{(n_3)!}{(n_3)! }] \times (1!) \times (1!) \times (1!)$
$= [\frac{(n_1+n_2+n_3)!}{(n_1)! \times (n_2)! \times (n_3)!} ] \times (1!) \times (1!) \times (1!) $
$= [\frac{(n_1+n_2+n_3)!}{(n_1)! \times (n_2)! \times (n_3)!} ] $
This is same as following description in the DBMS transactions concept.
Consider there are n number of transactions $T_1, T_2, T_3 …. , T_n$ with $N_1, N_2, N_3 …. , N_n$ number of operations respectively. Please note that operations in a transactions has only one order.
Then total number of possible transactions = $\frac{(N_1+ N_2+ N_3 +\dots+N_n)!}{N_1! \times N_2! \times N_3! \times \dots \times N_n!}$
If operations in a $T_1$ can permute with some restrictions,
then total number of possible transactions = $\frac{(N_1+ N_2+ N_3 +\dots+N_n)!}{N_1! \times N_2! \times N_3! \times \dots \times N_n!} \times \underbrace{A}_\text{(internal permutation of T1 operations)} $
Directed Acyclic Graph
What is a Directed Acyclic Graph (DAG) ? - A graph that has nodes connected by directed edges, but no closed loops.
What is a topological sort of a DAG ? - Topological sorting of a DAG is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.
Real life example:
Topological sort of above graph indicate that, to join M.Tech in IIT, you need to get AIR Rank and Completion of B.Tech. To get AIR Rank, you need to write GATE.
In other words, first you need to write GATE exam, then you need get AIR Rank, you need to ensure that B.Tech completion, then only, you can join M.Tech in IIT.
Possible topological sorts:
- W,G, C, J
- W, C, G, J
- C, W, G, J
The key point in the topological sorting is, it indicates the prerequisites to complete some action.
What are the redundant links in DAG?
If you see the above image, we will notice that A -> B -> C -> D
That means, D will start after the completion of C, C will start after the completion of B and B will start after the completion of A. So, D will always start after the completion of A only. Hence, representing A-> D will be redundant. Representation of these type of links/dependencies in the graph are redundant.
Whenever, we are calculating topological sorts, removing redundant links make the life easier.
Q1. The number of different topological orderings of the vertices of the graph is ______ [https://gateoverflow.in/39669/gate-cse-2016-set-1-question-11]
Start and End have no choices.
Every topological order start with $a$ and ends with $f$.
Remaining are {b,c} and {d,e}
Hence number of topological orders = $\frac{(N_1+ N_2+ N_3 +\dots+N_n)!}{N_1! \times N_2! \times N_3! \times \dots \times N_n!}$ = $\frac{(2+2)!}{2! \times 2! } = 6$
Q2. How many Topological Orderings possible from A to H? [https://gateoverflow.in/240811/topological-sort]
There are 8 nodes, namely A, B, C, D, E, F, G, H where A is the first one and H is the last one.
Hence, every topological sort starts with A and ends with H.
There are two groups, {B, C, E} and {D, F, G}.
Please note that, every topological sort should contain all the above nodes. (6 nodes, 6 positions.)
- Choose 3 places in the 6 positions for {B, C, E} group and permute them with the given restrictions.
- Remaining 3 places for {D, F, G} group and permute them with the given restrictions.
Therefore our answer will be $ \underbrace{1}_\text{A} \times \binom{6}{3} . \underbrace{P}_\text{(internal permutation of the \{B,C, E\} group)} \times \binom{3}{3} \underbrace{Q}_\text{(internal permutation of the \{D,F, G\} group)} \times \underbrace{1}_\text{H}$
What is the internal permutation of the {B, C, E} group which has permutation restrictions?
Three positions with three elements. Fix the last element as E. Then remaining 2 positions with two elements, permute them. $\Rightarrow$ That is 2!.
What is the internal permutation of the {D, F, G} group which has permutation restrictions?
Three positions with three elements. Fix the first element as D. Then remaining 2 positions with two elements, permute them. $\Rightarrow$ That is 2!
Final answer of the question is = $ 1 \times \binom{6}{3} . (2!) \times \binom{3}{3} (2!) \times 1 = 80$
Practice Questions:
Hashing related questions:
Q1: A hash table of length $10$ uses open addressing with hash function $h(k) = k \: \mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the table is shown as below
$$\begin{array}{|l|l|}\hline \text{0} & \text{} \\ \hline \text{1} & \text{} \\\hline \text{2} & \text{42} \\ \hline \text{3} & \text{23} \\\hline \text{4} & \text{34} \\\hline \text{5} & \text{52} \\\hline \text{6} & \text{46} \\\hline \text{7} & \text{33} \\\hline \text{8} & \text{} \\\hline \text{9} & \text{} \\\hline \end{array}$$
How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? [https://gateoverflow.in/43327/gate-cse-2010-question-53]
If you observe the above question, it is indirectly saying that 52 should be inserted after the insertion of 42,23, 34; and 33 should be inserted after the insertion of 46, 52.
So, if we draw DAG and find the number of topological orders, then that is the final answer.
Answer available in the above mentioned link
Practice Questions:
Trees:
Q1. What are possible types of binary trees with $n=3$ nodes (Unlabelled) ?
Answer: $n^{th}- \text{catalan number.} \Rightarrow \frac{\binom{2n}{n}}{(n+1)} = \frac{\binom{6}{3}}{(4)} = 5$.
All those five patterns listed below:
Q2. What are possible types of binary trees with $n=3$ nodes (Labelled) ?
We need to label patterns mentioned in the Q1. For each of the above pattern, there are n ways to label the node. I mean, 1, 2 and 3 can be placed anywhere in the above pattern.
$\Rightarrow \frac{\binom{2n}{n}}{(n+1)}.(n!) = \frac{(2n)!}{(n+1)!} = \frac{6!}{(4!)} = 30$
Q3. What are possible types of binary search trees with $n=3$ nodes ? - This should be labelled only.
Once the tree structure fixed, as this is a BST, there is only one way to label the each structure. Then the answer for this questions = Number of un-labelled binary trees with $n=3$ nodes. = $\frac{\binom{2n}{n}}{(n+1)} = \frac{\binom{6}{3}}{(4)} = 5$
Recurrance relation available here: https://gateoverflow.in/897/gate-cse-2003-question-6
Q4. Suppose we want to create binary search using the key values 12,26,10,27,20, 15,42. Howmany insertion sequence exits, so that the below tree can be constructed? [https://gateoverflow.in/457646/binary-search-tree-insertion-sequences]
Here, the pattern is fixed. Hence, we can label the above structure in only one way. That is mentioned below:
However, there are multiple insertion sequences can be led to same binary search tree. I mean, after inserting 26, then you may insert 12 or 42. Both lead to construction of same BST. So, we need to find the how many such insertions possible.
If you observe, 15 should be inserted after 20 and 20 should be after 12. So, if we draw DAG and find the number of topological orders, then that is the final answer.
The DAG of the nodes (except root) mentioned below:
Relate with T1 and T2 where with 4 and 2 operations respectively. Further, T1 operations can be permute with some restrictions and no permutation between T2 operations.
Total insertion sequences = $\frac{(4+2)!}{(4!) \times (2!)} \times \underbrace{A}_\text{permutation of T1 operations} \times \underbrace{(1!)}_\text{permutation of T2 operations} $
What is the internal permutation of the {12,10,20,15} group which has permutation restrictions?
12 always first. Remaining 3 elements {10,20,15} with three positions
As 10 is free bird (it can occur at any time), choose 1 place in the 3 positions for 10. $\Rightarrow \binom{3}{1}$, remaining 2 positions for 20 and 15 where no internal permutation not possible.
$\Rightarrow 3*1$
So, the total insertion sequences = $\frac{(4+2)!}{(4!) \times (2!)} \times {3} \times (1!) $
Practice Questions:
Transaction related:
Q1. Two transactions $T_1$ and $T_2$ are given as
$T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)$
$T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)$
where $r_i(V)$ denotes a $\textit{read}$ operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a $\textit{write}$ operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and $T_2$ is ______
Answer is - https://gateoverflow.in/118640/gate-cse-2017-set-2-question-44?show=289691#a289691
Practice Questions:
Eventhough all of the above content is already available in the GO, the purpose of this blog is to consolidate that information into a single, comprehensive resource and connect the dots.
