GATE CS Chapter-wise PYQs

**Solution:** 1. The given recurrence relation is: with the base case $T(0) = 1$. 2. We solve this recurrence by unrolling it. Substitute $T(n-1)$: Substitute $T(n-2)$: 3. Generalizing this pattern for $k$ steps, we observe: 4. To reach the base case $T(0)$, we set $n-k = 0$, which implies $k=n$. Substitute $k=n$ into the generalized equation: 5. Given $T(0) = 1$, substitute this value: 6. Evaluate the sum $\sum_{i=0}^{n-1} (n-i)$. Let $j = n-i$. When $i=0$, $j=n$. When $i=n-1$, $j=n-(n-1) = 1$. So the sum becomes $\sum_{j=1}^{n} j$. The sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$. 7. Substitute the sum back into the expression for $T(n)$: 8. Now, we determine the asymptotic complexity $\Theta(T(n))$. The highest power of $n$ in the polynomial $(n^2 + n + 2)$ is $n^2$. Therefore, $T(n)$ is asymptotically equivalent to $n^2 2^n$. 9. Comparing this with the given options, the correct option is $T(n) = \Theta(n^2 2^n)$. Answer: \boxed{T(n) = \Theta(n^2 2^n)}

**Solution:** **Step 1: Calculate the total number of ternary strings of length 5.** The alphabet is $\{a, b, c\}$, which has 3 symbols. The length of the string is 5. For each position in the string, there are 3 choices. **Step 2: Calculate the number of ternary strings of length 5 that contain NO consecutive identical symbols.** Let the string be $s_1 s_2 s_3 s_4 s_5$. For the first position ($s_1$), there are 3 choices (a, b, or c). For the second position ($s_2$), it cannot be the same as $s_1$, so there are 2 choices. For the third position ($s_3$), it cannot be the same as $s_2$, so there are 2 choices. For the fourth position ($s_4$), it cannot be the same as $s_3$, so there are 2 choices. For the fifth position ($s_5$), it cannot be the same as $s_4$, so there are 2 choices. **Step 3: Calculate the number of strings that contain at least one occurrence of two consecutive symbols.** This can be found by subtracting the number of strings with no consecutive identical symbols from the total number of strings. Answer: \boxed{195}

The given recurrence relation is: We need to find the asymptotic complexity of $T(n)$. **Step 1: Change of variable** Let $n = 2^k$. This implies $k = \log_2 n$. Then $\sqrt{n} = \sqrt{2^k} = 2^{k/2}$. Substitute these into the recurrence relation for $n \geq 1$: **Step 2: Define a new function $S(k)$** Let $S(k) = T(2^k)$. The recurrence relation can now be written in terms of $S(k)$: **Step 3: Divide by $2^k$** To simplify the recurrence, divide both sides by $2^k$: **Step 4: Define another new function $R(k)$** Let $R(k) = \frac{S(k)}{2^k}$. The recurrence relation simplifies to: **Step 5: Solve the recurrence for $R(k)$** This is a standard recurrence relation. We can solve it by repeated substitution: \begin{align*} R(k) &= R(k/2) + 1 \\ &= (R(k/4) + 1) + 1 = R(k/4) + 2 \\ &= (R(k/8) + 1) + 2 = R(k/8) + 3 \\ & \quad \vdots \\ &= R(k/2^m) + m \end{align*} To find the asymptotic behavior, we continue this process until $k/2^m$ reaches a constant base value (e.g., $1$). If $k/2^m = 1$, then $m = \log_2 k$. Thus, $R(k) = R(1) + \log_2 k$. Asymptotically, $R(k) = \Theta(\log k)$. **Step 6: Substitute back to find $T(n)$** We have $R(k) = \frac{S(k)}{2^k}$. So, $S(k) = 2^k R(k)$. Substituting $R(k) = \Theta(\log k)$: Now, substitute back $S(k) = T(2^k)$ and $n = 2^k$ (which implies $k = \log_2 n$): Since $\log_2 (\log_2 n) = \frac{\ln(\log_2 n)}{\ln 2}$, and constant factors do not affect asymptotic notation, we have $\log_2 (\log_2 n) = \Theta(\ln(\log_2 n))$. Also, $\ln(\log_2 n) = \ln\left(\frac{\ln n}{\ln 2}\right) = \ln(\ln n) - \ln(\ln 2)$. Therefore, $\log_2 (\log_2 n) = \Theta(\ln(\ln n)) = \Theta(\log \log n)$. Substituting this back into the expression for $T(n)$: **Step 7: Check the base case** The base case $T(1)=1$ corresponds to $k=0$ in our substitution ($n=2^k$). The asymptotic analysis holds for sufficiently large $n$, typically $n \geq 2$ for $\log \log n$ to be defined. The base case does not alter the asymptotic complexity. **Step 8: Compare with options** The derived complexity is $T(n) = \Theta(n \log \log n)$. Comparing this with the given options: 1. $T(n) = \Theta(n \log \log n)$ 2. $T(n) = \Theta(n \log n)$ 3. $T(n) = \Theta(n^2 \log n)$ 4. $T(n) = \Theta(n^2 \log \log n)$ The first option matches our result. The final answer is $\boxed{T(n) = \Theta(n \log \log n)}$.

1. **Formulate the characteristic equation:** The given recurrence relation is $T(n) = 5T(n-1) - 6T(n-2)$. Rearranging it to a homogeneous form: The characteristic equation is obtained by substituting $T(n) = r^n$: 2. **Solve the characteristic equation for roots:** We factor the quadratic equation: The roots are $r_1 = 2$ and $r_2 = 3$. 3. **Write the general solution:** Since the roots are distinct, the general solution for $T(n)$ is of the form: where $A$ and $B$ are constants. 4. **Use base cases to find constants $A$ and $B$:** We are given the base cases $T(0) = 1$ and $T(1) = 2$. For $n=0$: Since $T(0) = 1$, we have: For $n=1$: Since $T(1) = 2$, we have: From Equation 1, we can express $A$ as $A = 1 - B$. Substitute this into Equation 2: Now substitute $B = 0$ back into $A = 1 - B$: 5. **Write the particular solution:** Substitute the values of $A=1$ and $B=0$ into the general solution: 6. **Determine the asymptotic behavior:** The particular solution is $T(n) = 2^n$. Therefore, the asymptotic behavior of $T(n)$ is $\Theta(2^n)$. Answer: \boxed{T(n) = \Theta(2^n)}

To find the probability of getting all distinct numbers when six unbiased dice are rolled simultaneously, we need to determine the total number of possible outcomes and the number of favorable outcomes. **Step 1: Calculate the total number of possible outcomes.** Each die has 6 faces (1, 2, 3, 4, 5, 6). Since six dice are rolled, and each roll is independent, the total number of possible outcomes is $6 \times 6 \times 6 \times 6 \times 6 \times 6$. **Step 2: Calculate the number of favorable outcomes.** We want to get all distinct numbers (i.e., 1, 2, 3, 4, 5, and 6). This means: The first die can show any of the 6 numbers. The second die can show any of the remaining 5 numbers (to be distinct from the first). The third die can show any of the remaining 4 numbers. The fourth die can show any of the remaining 3 numbers. The fifth die can show any of the remaining 2 numbers. The sixth die can show the last remaining number. This is equivalent to the number of permutations of 6 distinct items taken 6 at a time, which is $P(6, 6)$ or $6!$. **Step 3: Calculate the probability.** The probability of an event is given by the ratio of favorable outcomes to the total number of possible outcomes. Substitute the calculated values: Now, simplify the fraction: Cancel out one 6 from the numerator and denominator: Divide both numerator and denominator by 6: Divide both numerator and denominator by 4: The final probability is $\frac{5}{324}$. Answer: \boxed{\frac{5}{324}}

Let $U = \{1, 2, \dots, n\}$, where $n$ is a large positive integer greater than $1000$. Let $k$ be a positive integer less than $n$. Let $A, B$ be subsets of $U$ with $|A| = |B| = k$ and $A \cap B = \emptyset$. A permutation of $U$ separates $A$ from $B$ if one of the following is true: 1. All members of $A$ appear in the permutation before any of the members of $B$. 2. All members of $B$ appear in the permutation before any of the members of $A$. Since $A \cap B = \emptyset$, these two conditions are mutually exclusive. We can calculate the number of permutations for each case and then sum them up. **Step 1: Calculate the number of permutations where all members of $A$ appear before any members of $B$.** Let $S = A \cup B$. Since $A$ and $B$ are disjoint and each has $k$ elements, the size of $S$ is $|S| = |A| + |B| = k + k = 2k$. The remaining elements are $U \setminus S$, which has $n - 2k$ elements. To construct a permutation where all elements of $A$ appear before all elements of $B$, we can follow these steps: 1. **Choose $2k$ positions** out of the $n$ available positions in the permutation for the elements of the set $S = A \cup B$. The number of ways to do this is $\binom{n}{2k}$. 2. **Arrange the elements of $S$** in these $2k$ chosen positions such that all elements of $A$ come before all elements of $B$. This means that the first $k$ of these $2k$ chosen positions must be filled by elements of $A$, and the next $k$ positions must be filled by elements of $B$. * The $k$ elements of $A$ can be arranged in the first $k$ designated positions in $k!$ ways. * The $k$ elements of $B$ can be arranged in the next $k$ designated positions in $k!$ ways. So, the number of ways to arrange elements of $S$ in the chosen $2k$ positions, satisfying the condition, is $k! \times k! = (k!)^2$. 3. **Arrange the remaining $n - 2k$ elements** (from $U \setminus S$) in the remaining $n - 2k$ positions. The number of ways to do this is $(n - 2k)!$. Combining these steps, the total number of permutations for this case (A before B) is: We know that $\binom{n}{2k} = \frac{n!}{(2k)!(n - 2k)!}$. Substituting this into the expression: **Step 2: Calculate the number of permutations where all members of $B$ appear before any members of $A$.** This case is symmetric to Step 1. The logic and calculations are identical, simply swapping the roles of $A$ and $B$. 1. **Choose $2k$ positions** out of the $n$ available positions for the elements of $S = A \cup B$. The number of ways to do this is $\binom{n}{2k}$. 2. **Arrange the elements of $S$** in these $2k$ chosen positions such that all elements of $B$ come before all elements of $A$. * The $k$ elements of $B$ can be arranged in the first $k$ designated positions in $k!$ ways. * The $k$ elements of $A$ can be arranged in the next $k$ designated positions in $k!$ ways. So, the number of ways to arrange elements of $S$ in the chosen $2k$ positions, satisfying the condition, is $k! \times k! = (k!)^2$. 3. **Arrange the remaining $n - 2k$ elements** (from $U \setminus S$) in the remaining $n - 2k$ positions. The number of ways to do this is $(n - 2k)!$. Combining these steps, the total number of permutations for this case (B before A) is: Which simplifies to: **Step 3: Total number of permutations that separate $A$ from $B$.** Since the two cases (A before B, and B before A) are mutually exclusive, the total number of permutations that separate $A$ from $B$ is the sum of the permutations from Case 1 and Case 2. The final answer is $\boxed{2\binom{n}{2k} (n - 2k)! (k!)^2}$.

**Step 1: Formulate the characteristic equation** The given recurrence relation for the Lucas sequence is $L_n = L_{n-1} + L_{n-2}$ for $n \geq 3$. The characteristic equation for this recurrence relation is: **Step 2: Solve the characteristic equation** Using the quadratic formula: Let the two roots be and **Step 3: Write the general form of the solution** The general solution for the Lucas sequence is of the form: **Step 4: Use initial conditions to find constants A and B** We are given $L_1 = 1$ and $L_2 = 3$. For $n=1$: For $n=2$: Since $r_1$ and $r_2$ are roots of $r^2 - r - 1 = 0$, we know $r_1^2 = r_1 + 1$ and $r_2^2 = r_2 + 1$. Substitute these into the equation for $L_2$: From equation (1), we know $A r_1 + B r_2 = 1$. Substitute this value: Now we have a system of two linear equations for A and B: 1. 2. From (2), $B = 2 - A$. Substitute this into (1): Calculate $r_1 - r_2$: Substitute this back: Now, substitute $A=1$ into $A+B=2$: **Step 5: Write the final closed-form expression** Substitute the values of $A=1$ and $B=1$ back into the general solution: **Step 6: Compare with the given options** The derived formula is: Let's check the options (with corrected MathJax for `\left` and `\right`): 1. 2. 3. 4. Our result matches option 1. The final answer is $\boxed{L_n = \left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n}$.

The given recurrence relations are: Let's derive a general form for $f(n)$ based on its binary representation. Let $n$ be represented in binary as $n = (b_k b_{k-1} \dots b_1 b_0)_2 = \sum_{i=0}^k b_i 2^i$. From the recurrence, we can observe the pattern based on the last bit $b_0$: If $b_0 = 0$, then $n$ is even, $n = 2 \lfloor n/2 \rfloor$. The recurrence is $f(n) = 2 f(\lfloor n/2 \rfloor) - 1$. If $b_0 = 1$, then $n$ is odd, $n = 2 \lfloor n/2 \rfloor + 1$. The recurrence is $f(n) = 2 f(\lfloor n/2 \rfloor) + 1$. Let's define a new sequence $c_i$ based on the binary digits $b_i$: If $b_i = 0$, let $c_i = -1$. If $b_i = 1$, let $c_i = 1$. Then, the recurrence can be uniformly written as $f(n) = 2 f(\lfloor n/2 \rfloor) + c_0$. Applying this recursively: Continuing this expansion until $f(1)$: This is the general form for $f(n)$. Let's verify this general form with a few examples: - For $n=1 = (1)_2$: $b_0=1 \implies c_0=1$. $f(1) = c_0 2^0 = 1 \cdot 1 = 1$. (Correct) - For $n=2 = (10)_2$: $b_1=1, b_0=0 \implies c_1=1, c_0=-1$. $f(2) = c_0 2^0 + c_1 2^1 = (-1) \cdot 1 + (1) \cdot 2 = -1+2=1$. (Correct) - For $n=3 = (11)_2$: $b_1=1, b_0=1 \implies c_1=1, c_0=1$. $f(3) = c_0 2^0 + c_1 2^1 = (1) \cdot 1 + (1) \cdot 2 = 1+2=3$. (Correct) Now, let's evaluate each option: **Option 1: $f(2^n-1)=2^n-1$** The binary representation of $2^n-1$ is $\underbrace{11\dots1}_{n \text{ times}}$. This means $b_i=1$ for all $i=0, 1, \dots, n-1$. Therefore, $c_i=1$ for all $i=0, 1, \dots, n-1$. This statement is **TRUE**. **Option 2: $f(2^n)=1$** The binary representation of $2^n$ is $1\underbrace{00\dots0}_{n \text{ times}}$. This means $b_n=1$, and $b_i=0$ for $i=0, 1, \dots, n-1$. Therefore, $c_n=1$, and $c_i=-1$ for $i=0, 1, \dots, n-1$. This statement is **TRUE**. **Option 3: $f(5 \cdot 2^n)=2^{n+1}+1$** The binary representation of $5$ is $(101)_2$. The binary representation of $5 \cdot 2^n$ is $(101\underbrace{00\dots0}_{n \text{ times}})_2$. This means $b_{n+2}=1, b_{n+1}=0, b_n=1$, and $b_i=0$ for $i=0, 1, \dots, n-1$. Therefore, $c_{n+2}=1, c_{n+1}=-1, c_n=1$, and $c_i=-1$ for $i=0, 1, \dots, n-1$. This statement is **TRUE**. **Option 4: $f(2^n+1)=2^n+1$** The binary representation of $2^n+1$ is $1\underbrace{00\dots0}_{n-1 \text{ times}}1$. This means $b_n=1, b_0=1$, and $b_i=0$ for $i=1, 2, \dots, n-1$. Therefore, $c_n=1, c_0=1$, and $c_i=-1$ for $i=1, 2, \dots, n-1$. The sum $\sum_{i=1}^{n-1} 2^i = (2^n-1) - 2^0 = 2^n-1-1 = 2^n-2$. For this statement to be true, $2^n+1$ must be equal to $3$. This implies $2^n=2$, so $n=1$. Since the statement is not true for all $n \ge 1$ (e.g., for $n=2$, $f(2^2+1)=f(5)=3$, but $2^2+1=5$), this statement is **FALSE**. The statements that are TRUE are Option 1, Option 2, and Option 3. Answer: $\boxed{f(2^n-1)=2^n-1, f(2^n)=1, f(5 \cdot 2^n)=2^{n+1}+1}$