Recent posts in Algorithms

This document aims to give the reader an introduction to Catalan numbers, a sequence of numbers arising throughout mathematics.  Catalan number appears frequently in computer science and combinatorics counting problems.

Catalan number is the solution to -

• number of Binary Trees with n unlabelled vertices,
• number of Full Binary Trees with n+1 leaves (or 2n +1 vertices),
• number of possible Binary Search Trees (BSTs) with n distinct keys,
• number of stack-sortable permutations,
• number of ways to form a Balanced parentheses sequences with n pairs,
• number of paths on an n X n grid that stay below or touch the main diagonal,
• number of non-nesting and non-crossing matchings of 2n vertices,
• number of noncrossing handshakes possible across a round table between n pairs of people, and over 200 more different objects that can be counted by catalan number.

How do you prove that two counting problems have the same answer? The bijection principle tells us that if there is a bijection between two sets, then the sets have the same size. So let's find some bijections.

Below are proofs and interesting observations meant only for analysis-loving enthusiasts. I will start with basics and go as far as I know.

(0.1 and 0.2 are sort of prequel and from 1 onwards are some of the various families of mathematical objects that are counted by catalan numbers.)

0.1] Suppose you can only move unit-length east (E) amd unit-length north (N). A lattice path is a sequence of east (E) and north (N) steps starting at (0,0) and ending at (n,n) in a n x n grid.

Lemma: For any m and n, there are$\binom{m+n}{n}$ lattice paths from (0, 0) to (m, n) in the m × n grid.

Proof. Think of a lattice path as a sequence of letters indicating the steps, N for north and E for east. To reach (m, n), a lattice path must have exactly m E’s and n N’s, but can have them in any order.

Now think of a line of [m + n] empty boxes. In each box we can place either an E or an N. E in box i means “put i in the subset” and N in box i meaning “throw away i”. 

e.g. ENENNENE of 4X4 grid corresponds to the subset { 1, 3, 6, 8 } of [8].

For example, for (m, n) = (3, 2), the bijection with size 3 subsets of [5] is

So here we have a bijection between lattice paths of (m,n) with-

• m-sized subsets of a m+n sized set,
• possible schedules with two transactions of m and n respective number of operations, (refer to permutations-and-combinations-specific-to-dag)

e.g. ENNEENEN in 4X4 grid, at 3rd move #N's = 2 is more than #E's = 1, also at 2nd, 4th, 6th, 8th moves #N = #E.

A Dyck path is a lattice path that does not go above the line y = x or #E's >= #N's in every prefix of the sequence.

And, lattice paths that cross y = x line are non-Dyck paths. 

1] Dyck Paths:

Proposition: Lattice paths in n x n grid that cross the diagonal (non-Dyck paths) are in bijection with lattice paths in the (n − 1) × (n + 1) grid. 

Proof. Given a lattice path P in n x n grid crossing the line y = x. From the first vertex in the path that lies above y = x line, take reflection of steps. For example;

In P, blue portion ends at vertex (with last step p) which is the first vertex above y = x line. Keeping all steps same till p (blue part) and taking the reflection of all steps after this vertex (red part), we construct a lattice path $Q_{p}$. 

In the blue portion, there will always be exactly one more north(N) step than east step(E) by the definition of p. Since there are exactly n north steps and n east steps in P, there must be exactly one more east steps than north steps in the red portion of P.

Thus, both the blue and red portions of $Q_{p}$ will have one more north steps than east steps. Thus, $Q_{p}$ will have n − 1 total east steps and n + 1 total north steps. In other words, $Q_{p}$ will be a lattice path in the (n − 1) × (n + 1) grid. For the inverse bijection, just draw in the n × n diagonal in the (n − 1) × (n + 1) grid and do the same reflection again!

Hence, we have proven that Dyck paths of n x n grid are in bijection with lattice paths of the (n − 1) × (n + 1) grid. Now, it's time to introduce the Hero of the Town, Catalan Numbers,

$$\#\;of Dyck\; paths = Total\; lattice\; paths - \#\; of\; nonDyck\; paths$$

$$=\binom{2n}{n} - \binom{2n}{n-1}$$

After some complicated simplifications, it becomes, $$\frac{1}{n+1} \binom{2n}{n} = C_{n}(n^{th} catalan\:number)$$

Proposition: $C_{n}$ counts the number of lattice paths in the n × n grid that do not cross the line y = x (Dyck paths).

For some more examples:- 

For n = 2, there are four bad paths, and they biject to all lattice paths in the 1 × 3 grid (shown in figure below): And there are $C_{2}$ = 2 good paths (left for readers).

And, there are $C_{4}$ = 14 good paths in a 4 × 4 grid:

2] Balanced Parentheses:

A sequence is said to have balanced parentheses, if there are exactly n opening brackets and n closing brackets, and every opening bracket has a corresponding closing bracket of exact same type, properly nested in correct sequence and no bracket closes before its matching opener.

Proposition: Number of balanced parenthesis sequences with exactly n opening brackets and n closing brackets = $C_{n}$

Proof. Simply by replacing every opening bracket with E and every closing bracket with N, balanced parenthesis problem can be transformed into Dyck path problem we saw earlier. One can also show reverse bijection, hence proving that balanced parenthesis sequences are in bijection with Dyck paths.

3] Ballot Sequences:

A ballot sequence of length 2n is a sequence with n −1’s and n 1’s such that sum of every prefix of the sequence is nonnegative. Equivalently, as you read the sequence left-to-right, you always encounter at least as many 1's as −1’s. 

For example, (1, −1, 1, 1, −1, −1, −1, 1) has partial sums 1, 0, 1, 2, 1, 0, −1, and 0, so it is not a ballot sequence. 

For n = 3, there are five ballot sequences: (1, 1, 1, −1, −1, −1) (1, 1, −1, 1, −1, −1) (1, 1, −1, −1, 1, −1) (1, −1, 1, 1, −1, −1) (1, −1, 1, −1, 1, −1)

We show that ballot sequences are counted by Catalan numbers through a bijection to Dyck paths! 

Proposition: There are $C_{n}$ ballot sequences of length 2n. 

Proof. Given a ballot sequence, replace each 1 by E and each −1 by N and then it can be shown that Ballot Sequence problem are in bijection with Dyck paths.

When n = 3, we get the bijection:

4]  Stack-sortable Permutation

A one stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure.

Proposition: The number of one stack-sortable permutations of length n is the $n^{th}$-Catalan number $C_{n}$.

Algorithm to check whether a given permutation π is sorted:

• Initialize an empty stack
• For each input value x:
  • While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output
  • Push x onto the stack
• While the stack is nonempty, pop it to the output

OBSERVATIONS-

a]  If the elements a, b and c occur in the permutation π where a < b < c and b precedes c precedes a, then we say that π contains a 231-pattern.

Theorem: A permutation π is one stack sortable if and only if it does not contain a 231-pattern.

For instance, the sequence 3,2,1 is correctly sorted: the three elements are all pushed onto the stack, and then popped in the order 1,2,3. However, the sequence 2,3,1 is not correctly sorted: the algorithm first pushes 2, and pops it when it sees the larger input value 3, causing 2 to be output before 1 rather than after it.

b]  Because of the 231-pattern limitation, many permutations are not one stack sortable. To increase the number of sortable permutations, we can use two stacks. Take the output sequence of first stack and give it as a input to second stack. If finally obtained output sequence is sorted, then we say that the permutation π is two stack sortable.

Theorem: The number of 2 stack sortable n-permutations is $$\frac{2(3n!)}{(n+1)! (2n+1)!}$$

(proof conjectured by Julian West. For this blog a proof will not be shown)

5] Non-crossing Matchings and Non-nesting Matchings

A matching on 2n vertices can be drawn as a way to connect 2n nodes on the x-axis by arcs, with every node connected to precisely one other node by an arc drawn in the upper halfplane.

Non-crossing matchings- A matching is non-crossing if all arcs can be drawn in a way such that no pair of arcs intersects.

Proposition: The number of non-crossing matchings on 2n vertices is the $n^{th}$-Catalan number $C_{n}$.

For example, All non-crossing matchings on 6 vertices are shown in figure below,

Non-nesting matchings- A matching is non-nesting if all the arcs can be drawn in a way such that no arc is above the other, or, equivalently, there is no pair of arcs with ends at points (a1, b1) and (a2, b2) such that a1 < a2 < b2 < b1.

Proposition: The number of non-crossing matchings on 2n vertices is the $n^{th}$-Catalan number $C_{n}$.

For example, All non-nesting matchings on 6 vertices are shown in figure below,

6] Binary Trees

Proposition: Number of binary trees on n (unlabelled) vertices is the $n^{th}$-Catalan number $C_{n}$.

7] Binary Search Trees

Proposition: The number of structurally unique Binary Search Trees (BSTs) on n distinct keys corresponds exactly to the $n^{th}$-Catalan number $C_{n}$

Because a valid BST requires that all values in the left subtree be smaller than the root and all values in the right be larger, the trees are purely determined by their structural branching shapes.

8] Full Binary Trees

There is a bijection b/w full binary trees on 2n+1 vertices(or n+1 leaves) and binary trees on n vertices, therefore;

Proposition: The number of Full Binary Trees on n+1 leaves equals to the $(n)^{th}$-Catalan number $C_{n}$.

9] Mountain Ranges

A Mountain range is defined to be a path of n upstokes and n downstrokes that starts from (0,0) and ends at (2n,0) and never goes below horizon (x-axis).

For exmaple, below figure shows all possible mountain ranges of 3-upstrokes & 3-downstrokes (length 6)

Proposition: $C_{n}$​ is equal to the number of mountain ranges of length 2n consisting of n upstrokes and n downstrokes.

Below are two nice bijective proofs:

Proof 1. Show the bijection between this problem and Dyck path problem.

Given a sequence of n-upstrokes and n-downstrokes ending at (2n,0), convert horizon to y = x line of n x n grid with region above horizon to the region below y = x line. (doing this transforms our problem statement to finding dyck paths in n x n grid. You can relate to further steps if you understood dyck path proof)

Identify the first vertex below horizon (as first bad vertex) and take reflection of all strokes in the path after that vertex(upstrokes -> downstrokes and vice versa), keeping the part of path upto that vertex same. We will observe that we always end up at (2n, -2) irrespective of any bad path you take. 

Lets call the paths that crosses horizon as bad paths and that which don't as good paths. Also, we name lattice path before transformation (blue one) as P and after transformation (blue one upto first bad vertex and red one after that) as Q.

So, we proved that bad paths ending at (2n,0) is in bijection with all paths ending at (2n,-2), i.e. $\#of\;Bad\; paths\; ending\; at\; (2n,0) = Total\; lattice\; paths\;ending\;at\;(2n,-2)$

But, what is total paths ending at (2n,-2)? 

Paths in P ends up at (2n,0) because it has exactly n upstrokes and n downstrokes. Upto first bad vertex, # of downstrokes are exactly one more than # of upstrokes. Therefore, in remaining part of the path, # of upstrokes are exactly one more than # of downstrokes in P. Thus in Q, both part (one uptil P and other after P) has # of downstrokes exactly one more than # of upstrokes, i.e. (n-1) upstrokes and (n+1) downstrokes.

$$Total\; lattice\; paths\;ending\;at\;(2n,-2) = \binom{2n}{n-1}=\#of\; Bad\; paths\;ending\;at\;(2n,0)$$

$$\#of Good\; paths\; ending\; at\; (2n,0) = Total\; lattice\; paths\;ending\;at\;(2n,0) - \#of\; Bad\; paths\;ending\;at\;(2n,0)$$

$$=\binom{2n}{n} - \binom{2n}{n-1}$$

$$=\frac{1}{n+1} \binom{2n}{n} = C_{n}(n^{th} catalan\:number)$$

Each good path is termed as a mountain range.

Here, k = number of digits (in Radix Sort).

Most Important Points:

1. Bubble Sort 

• Idea: Compare adjacent elements and swap if wrong. After each pass in Bubble Sort, the largest unsorted element moves to its correct position at the end of the array.
• Pass Rule: After each pass → largest element goes to correct position. Total passes = n − 1
• Swaps: Total swaps = total inversions
• Recurrence: T(n) = T(n−1) + n
• Algo:

for(int i = 0; i < n-1; i++){
    bool swapped = false;
    for(int j = 0; j < n-i-1; j++){
        if(arr[j] > arr[j+1]){
            swap(arr[j], arr[j+1]);
            swapped = true;
        }
    }
    if(!swapped) break;   // optimized
}

2. Insertion Sort 

• Idea: In each pass, insert one element into its correct position in the already sorted left part.
• Passes: n − 1 passes
• Online Algorithm: Does not require all elements at once → can sort while receiving input.
• Adaptive: Time = O(n + x), x = number of inversions
• External Sorting Property: Can handle data in chunks → used inside external merge-based methods.

6. Quick Sort

• Idea: Choose a pivot → Partition array → Left: elements ≤ pivot Right: elements > pivot. Recursively sort both parts.
• If pivot always smallest/largest → Worst case O(n²)
• Tail recursion optimization possible
• Very fast in practice (better cache performance than merge sort)
• Deterministic Quick Sort: A specific input (like sorted array) can always cause worst case.
• Randomized Quick Sort: No input can always cause worst case. Pivot is random → worst case becomes very unlikely. 
• Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same.
• Algo:

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)!} ] $

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:

• https://gateoverflow.in/240941/topological-sort
• https://gateoverflow.in/253496/number-of-topological-order

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:

• https://gateoverflow.in/243402/hashing
• https://gateoverflow.in/245897/hashing-with-linear-probing

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:

• https://gateoverflow.in/3462/gate-it-2007-question-29
• https://gateoverflow.in/243285/avl-tree

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:

• https://gateoverflow.in/247402/self-doubt-conflict-serializable?show=259997

https://walkccc.me/CLRS/

This website contains nearly complete solutions to the bible textbook - Introduction to Algorithms Third Edition, published by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

hope this helps :)

https://algs4.cs.princeton.edu/cheatsheet/

Commonly encountered functions, helpful formulae and approximations, features of logarithms, asymptotic notations, and solutions to divide-and-conquer recurrences are among the mathematics used in the study of algorithms.

For more information visit GO Classroom: https://classroom.gateoverflow.in/course/view.php?id=2

Important Questions

http://gateoverflow.in/questions/algorithms?sort=featured

Sometimes we need to walk through a given algorithm to get the answer. These questions must not be missed as there is very little chance of a mistake.