GATE AI 2025

Consider a hash table of size 10 with indices $\{0,1, \ldots, 9\}$, with the hash function $$ h(x)=3 x(\bmod 10) $$ where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1 , $4,5,6,14,15$. The indices where the keys 14 and 15 are stored are, respectively

The number of additions and multiplications involved in performing Gaussian elimination on any $n \times n$ upper triangular matrix is of the order

Let $G$ be a simple, unweighted, and undirected graph. A subset of the vertices and edges of $G$ are shown below. It is given that $a-b-c-d$ is a shortest path between $a$ and $d ; e-f-g-h$ is a shortest path between e and $h ; a-f-c$ - $h$ is a shortest path between $a$ and $h$. Which of the following is/are NOT the edges of $G$ ?

Suppose that insertion sort is applied to the array $[1,3,5,7,9,11, x, 15,13]$ and it takes exactly two swaps to sort the array. Select all possible values of $x$.

For which of the following inputs does binary search take time $O(\log n)$ in the worst case?

Consider a fact table in an OLAP application: Facts (D1, D2, val), where D1 and D2 are its dimension attributes and val is a dependent attribute. Suppose attribute D1 takes 3 values and D2 takes 2 values, and all combinations of these values are present in the table Facts. How many tuples are there in the result of the following query? SELECT D1, D2, sum(val) FROM Facts GROUP BY CUBE (D1, D2);

$$ \text { On a relation named Loan of a bank: } $$ Loan Loan_number Branch_name Amount L11 Banjra Hills 90000 L14 Kondapur 50000 L15 SR Nagar 4000 L22 SR Nagar 25000 L23 Balanagar 80000 L25 Kondapur 70000 L19 SR Nagar 65000 The following SQL query is executed SELECT L1.loan_number FROM Loan L1 WHERE L1.amount > (SELECT MAX (L2.amount) FROM Loan L2 WHERE L2.branch_name $=$ 'SR Nagar'); The number of rows returned by the query is _________

Consider the following two relations, named Customer and Person, in a database: Person ( aadhaar CHAR(12) PRIMARY KEY, name VARCHAR(32)); Customer ( name VARCHAR(32), email VARCHAR(32) PRIMARY KEY, phone CHAR(10), aadhaar CHAR(12), FOREIGN KEY (aadhaar) REFERENCES Person(aadhaar)); Which of the following statements is/are correct?

If a relational decomposition is not dependency-preserving, which one of the following relational operators will be executed more frequently in order to maintain the dependencies?

Consider a database relation $R$ with attributes ABCDEFG , and having the following functional dependencies: $$ \mathrm{A} \rightarrow \mathrm{BCEF} \quad \mathrm{E} \rightarrow \mathrm{DG} \quad \mathrm{BC} \rightarrow \mathrm{~A} $$ Which of the following statements is/are correct?

Consider the following three relations: Car (model, year, serial, color) Make (maker, model) Own (owner, serial) A tuple in Car represents a specific car of a given model, made in a given year, with a serial number and a color. A tuple in Make specifies that a maker company makes cars of a certain model. A tuple in Own specifies that an owner owns the car with a given serial number. Keys are underlined; (owner, serial) together form key for Own. ( $\bowtie $ denotes natural join) $$ \pi_{\text {owner }}(\text { Own } \bowtie \left(\sigma_{\text {color="red" }}\right. $$ $\left(\right.$ Car $\triangleright \triangleleft\left(\sigma_{\text {maker }=\text { "ABC }}\right.$ Make $\left.\left.\left.)\right)\right)\right)$ Which one of the following options describes what the above expression computes?

Consider the following tables, Loan and Borrower, of a bank. Loan loan_num branch_name amount L11 Banjara Hills 90000 L14 Kondapur 50000 L15 SR Nagar 40000 L22 SR Nagar 25000 L23 Balanagar 80000 L25 Kondapur 70000 L19 SR Nagar 65000 Borrower customer_name loan_num Anand L11 Karteek L11 Karteek L14 Ankita L15 Gopal L19 Karteek L22 Karteek L23 Sunil L23 Sunil L25 Query: $\quad \pi_{\text {branch_name, customer_name }}$ (Loan $\triangleright \triangleleft$ Borrower) $\div \pi_{\text {branch_name }}$ (Loan) where $\triangleright \triangleleft$ denotes natural join. The number of tuples returned by the above relational algebra query is __________

Consider the following pseudocode. Create empty stack S set $x=0$, flag $=0$, sum $=0$ Push $x$ onto $S$ while ( $S$ is not empty) $\{$ if (flag equals 0){ Set $x=x+1$ Push $x$ onto S} if ( $x$ equals 8 ): Set flag $=1$ if (flag equals 1){ $x=\operatorname{Pop}(\mathrm{S})$ if ( $x$ is odd): Pop (S) Set sum $=\operatorname{sum}+\mathrm{x}\}$ } Output sum The value of sum output by a program executing the above pseudocode is________

Consider the following Python declarations of two lists. $$ \begin{aligned} & A=[1,2,3] \\ & B=[4,5,6] \end{aligned} $$ Which one of the following statements results in $A=[1,2,3,4,5,6]$ ?

Consider the following Python code snippet. $\mathrm{A}=\{$ "this","that" $\}$ $B=\{$ "that","other" $\}$ $\mathrm{C}=\{$ "other","this"} while "other" in C : if "this" in A : $\mathrm{A}, \mathrm{B}, \mathrm{C}=\mathrm{A}-\mathrm{B}, \mathrm{B}-\mathrm{C}, \mathrm{C}-\mathrm{A}$ if "that" in B ; $\mathrm{A}, \mathrm{B}, \mathrm{C}=\mathrm{C}|\mathrm{A}, \mathrm{A}| \mathrm{B}, \mathrm{B} \mid \mathrm{C}$ When the above program is executed, at the end, which of the following sets contains "this"?

Consider the following Python code snippet. $\operatorname{def} f(a, b)$ : if ( $a==0$ ): return b $$ \begin{aligned} &\begin{aligned} & \text { if }(\mathrm{a} \% 2==1) \text { : } \\ & \text { return } 2 * f((a-1) / 2, b) \\ & \text { return } b+f(a-1, b) \\ & \operatorname{print}(f(15,10)) \end{aligned}\\ &\text { The value printed by the code snippet is__________ } \end{aligned} $$

Courage : Bravery :: Yearning : ___________ Select the most appropriate option to complete the analogy.

Column-I has statements made by Shanthala; and, Column-II has responses given by Kanishk. Column - I Column-II P. This house is in a mess. 1. Alright, I won't bring it up during our conversations. Q. I am not happy with the marks given to me. 2. Well, you can easily look it up. R. Politics is a subject I avoid talking about. 3. No problem, let me clear it up for you. S. I don't know what this word means. 4. Don't worry, I will take it up with your teacher. Identify the option that has the correct match between Column-I and ColumnII.

We ___________ tennis in the lawn when it suddenly started to rain. Select the most appropriate option to complete the above sentence.

A rectangle has a length L and a width W . where $\mathrm{L}>\mathrm{W}$. If the width, W , is increased by $10 \%$, which one of the following statements is correct for all values of L and W ?

If a real variable $x$ satisfies $3^{x^2}=27 \times 9^x$, then the value of $\frac{2^{x^2}}{\left(2^x\right)^2}$ is :

The number of patients per shift ( $X$ ) consulting Dr. Gita in her past 100 shifts is shown in the figure. If the amount she earns is Rs $1000(X-0.2)$, what is the average amount (in she has earned per shift in the past 100 shifts? Note : The figure shown is representative.

A $4 \times 4$ digital image has pixel intensities $(U)$ as shown in the figure. The number of pixels with $U \leq 4$ is: 0 1 0 2 4 7 3 3 5 5 4 4 6 7 3 2

Weight of a person can be expressed as a function of their age. The function usually varies from person to person. Suppose this function is identical for two brothers, and it monotonically increases till the age of 50 years and then it monotonically decreases. Let $a_1$ and $a_2$ (in years) denote the ages of the brothers and $a_1 < a_2$. Which one of the following statements is correct about their age on the day when they attain the same weight?

In the given figure, the numbers associated with the rectangle, triangle, and ellipse are 1,2 , and 3 , respectively. Which one among the given options is the most appropriate combination of P , Q , and R ?

A regular dodecagon (12-sided regular polygon) is inscribed in a circle of radius $r \mathrm{~cm}$ as shown in the figure. The side of the dodecagon is d cm . All the triangles (numbered 1 to 12) in the figure are used to form squares of side $r \mathrm{~cm}$ and each numbered triangle is used only once to form a square. The number of squares that can be formed and the number of triangles required to form each square, respectively, are: Note: The figure shown is representative.

Which of the following statements is/are correct in a Bayesian network?

The state graph shows the action cost along the edges and the heuristic function $h$ associated with each state. Suppose A* algorithm is applied on this state graph using priority queue to store the frontier. In what sequence are the nodes expanded?

Let X be a continuous random variable whose cumulative distribution function (CDF) $F_X(x)$, for some $t$, is given as follows: $$ F_X(x)=\left\{\begin{array}{cc} 0 & x \leq t \\ \frac{x-t}{4-t} & t \leq x \leq 4 \\ 1 & x \geq 4 \end{array}\right. $$ If the median of X is 3 , then what is the value of $t$ ?

A random variable X is said to be distributed as $\operatorname{Bernoulli}(\theta)$, denoted by $X \sim \operatorname{Bernoulli}(\theta)$, if $$ P(X=1)=\theta, P(X=0)=1-\theta $$ for $0<\theta<1$. Let $Y=\sum_{i=1}^{300} X_i$. Where $X_i \sim \operatorname{Bernoulli}(\theta), i=1,2, \ldots \ldots, 300$ be independent and identically distributed random variables with $\theta=0.25$. The value of $P(60 \leq \mathrm{Y} \leq 90)$, after approximation through Central Limit Theorem, is given by (Recall that $\phi(x)=\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^x e^{-\frac{t^2}{2}} d t$ )

For $x \in \mathbb{R}$, the floor function is denoted by $f(x)=\lfloor x\rfloor$ and defined as follows $\lfloor x\rfloor=k, k \leq x<k+1$, where $k$ is an integer. Let $Y=\lfloor X\rfloor$, where $X$ is an exponentially distributed random variable with mean $\frac{1}{\ln 10}$, where In denotes natural logarithm. For any positive integer $l$, one can write the probability of the event $Y=l$ as follows $$ P(Y=l)=q^l(1-q) $$ The value of $q$ is

Consider the cumulative distribution function (CDF) of a random variable X : $$ F_X(x)=\left\{\begin{array}{cc} 0 & x \leq-1 \\ \frac{1}{4}(x+1)^2 & -1 \leq x \leq 1 \\ 1 & x \geq 1 \end{array}\right. $$ The value of $P\left(X^2 \leq 0.25\right)$

It is given that $P(X \geq 2)=0.25$ for an exponentially distributed random variable $X$ with $E[X]=\frac{1}{\lambda}$, where $E[X]$ denotes the expectation of $X$. What is the value of $\lambda$ ? (ln denotes natural logarithm)

A bag contains 5 white balls and 10 black balls. In a random experiment, $n$ balls are drawn from the bag one at a time with replacement. Let $S_n$ denote the total number of black balls drawn in the experiment. The expectation of $S_{100}$ denoted by $E\left[S_{100}\right]=$ ___________ (Round off to one decimal place)

Let $X=a Z+b$, where Z is a standard normal random variable, and $a, b$ are two unknown constants. It is given that $$ \begin{aligned} E[X] & =1, E[(X-E[X]) Z] \\ & =-2, E\left[(X-E[X])^2\right]=4 \end{aligned} $$ Where $E[X]$ denotes the expectation of random variable X . The values of $a, b$ are:

Suppose $X$ and $Y$ are random variables. The conditional expectation of $X$ given $Y$ is denoted by $E[X \mid Y]$. Then $E[E[X \mid Y]]$ equals

Consider a coin-toss experiment where the probability of head showing up is $p$. In the $i^{\text {th }}$ coin toss, let $X_i=1$ if head appears, and $X_i=0$ if tail appears. Consider $$ \hat{p}=\frac{1}{n} \sum_{i=1}^n X_i $$ where $n$ is the total number of independent coin tosses. Which of the following statements is/are correct?

Let $Y=Z^2, Z=\frac{X-\mu}{\sigma}$, where $X$ is a normal random variable with mean $\mu$ and variance $\sigma^2$. The variance of $Y$ is

A random experiment consists of throwing 100 fair dice, each die having six faces numbered 1 to 6 . An event $A$ represents the set of all outcomes where at least one of the dice shows a 1 . Then, $\mathrm{P}(\mathrm{A})=$

There are three boxes containing white balls and black balls. Box-1 contains 2 black and 1 white balls. Box-2 contains 1 black and 2 white balls. Box-3 contains 3 black and 3 white balls. In a random experiment, one of these boxes is selected, where the probability of choosing Box-1 is $\frac{1}{2}$, Box-2 is $\frac{1}{6}$, and Box-3 is $\frac{1}{3}$. A ball is drawn at random from the selected box. Given that the ball drawn is white, the probability that it is drawn from Box-2 is ____________. (Round off to two decimal places)

Let $p$ and $q$ be any two propositions. Consider the following propositional statements. $$ \begin{aligned} & S_1: p \rightarrow q, \quad S_2: \neg p \wedge q, \quad S_3: \neg p \vee q, \\ & S_4: \neg p \vee \neg q, \end{aligned} $$ Where $\wedge$ denotes conjunction (AND operation), $\vee$ denotes disjunction (OR operation), and $\neg$ denotes negation (NOT operation). Which one of the following options is correct? (Note: $\equiv$ denotes logical equivalence)

Let $A=I_n+x x^T$, where $I_n$ is the $n \times n$ identity matrix and $x \in \mathbb{R}^n, x^T x=1$. Which of the following option is/are correct?

Let $A \in \mathbb{R}^{n \times n}$ be such that $A^3=A$. Which one of the following statements is ALWAYS correct?

The sum of the elements in each row of $A \in \mathbb{R}^{n \times n}$ is 1 . If $B=A^3-2 A^2+A$, which one of the following statements is correct (for $x \in \mathbb{R}^n$ )?

An $n \times n$ matrix $A$ with real entries satisfies the property: $\|A x\|^2=\|x\|^2$ for all $x \in R^n$ where $\|\cdot\|$ denotes the Euclidean norm. Which of the following statements is/are ALWAYS correct?

Which of the following statements is/are correct?

Consider a directed graph $G=(V, E)$, where $V=\{0,1,2, \ldots, 100\}$ and $E=\{(i$, $j): 0 < j-i \leq 2$, for all $i, j \in V\}$. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0 . The number of vertices that will be discovered after vertex 50 is___________

Let $f(x)=\frac{e^x-e^{-x}}{2}, x \in R$. Let $f^{(k)}(a)$ denote the $k^{\text {th }}$ derivative of $f$ evaluated at $a$. What is the value of $f^{(10)}(0)$ ?(Note: ! denotes factorial)

Consider two functions $f: \mathbb{R} \rightarrow \mathbb{R}$ and $g: \mathbb{R} \rightarrow(1, \infty)$. Both functions are differentiable at a point c . Which of the following functions is/are ALWAYS differentiable at c ? The symbol $\cdot$ denotes product and the symbol odenotes composition of functions.

$$\mathop {\lim }\limits_{t \to + \infty } \sqrt{t^2+t}-t= $$ (Round off to one decimal place)

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a twice-differentiable function and suppose its second derivative satisfies $f^{\prime \prime}(x)>0$ for all $x \in \mathbb{R}$. Which of the following statements is/are ALWAYS correct?

Consider the function $$ f(\mathrm{x})=\frac{x^3}{3}+\frac{7}{2} x^2+10 x+\frac{133}{2}, x \in[-8,0] . $$ Which of the following statements is/are correct?

Let $\quad f: \mathbb{R} \rightarrow \mathbb{R} \quad$ be such that $|f(x)-f(y)| \leq(x-y)^2$ for all $x, y \in \mathbb{R}$. Then $\quad f(1)-f(0)=$ ____________

Let $x_1, x_2, x_3, x_4, x_5$ be a system of orthonormal vectors in $\mathbb{R}^{10}$. Consider the matrix $A=x_1 x_1^T+\ldots . .+x_5 x_5^T$. Which of the following statements is/are correct?

Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function. For what ranges of $x$ and $y$, the right child of node $B$ and the right child of node $E$ will be pruned by alpha-beta pruning algorithm?

Consider a two-class problem in $R^d$ with class labels red and green. Let $\mu_{\text {red }}$ and $\mu_{\text {green }}$ be the means of the two classes. Given test sample $x \in R^d$, a classifier calculates the squared Euclidean distance (denoted by $\|\cdot\|^2$ ) between $x$ and the means of the two classes and assigns the class label that the sample x is closest to. That is, the classifier computes $$ f(x)=\left\|\mu_{\text {red }}-x\right\|^2-\left\|\mu_{\text {green }}-x\right\|^2 $$ and assigns the label red to $x$ if $f(x)<0$, and green otherwise. Which of the following statements is/are correct?

Consider the neural network shown in the figure with inputs: $u, v$ weights: $a, b, c, d, e, f$ output: $y$ R denotes the ReLU function, $\mathrm{R}(x)=\max (0, \mathrm{x})$. Given $u=2, v=3$, $a=1, b=1, c=1, d=-1, e=4, f=-1$, which one of following is correct?

Let $\left\{x_1, x_2, \ldots ., x_n\right\}$ be a set of linearly independent vectors in $\mathbb{R}^n$. Let the $(\mathrm{i}, \mathrm{j})$ - th element of matrix $A \in \mathbb{R}^{n \times n}$ be given by $A_{i j}=x_i^T x_j, 1 \leq i, j \leq n$. Which one of the following statements is correct?

Which of the following statements is/are correct about the rectified linear unit (ReLU) activation function defined as $\operatorname{ReLU}(x)=\max (x, 0)$, where $\mathrm{x} \in \mathbb{R}$ ?

Consider designing a linear binary classifier $f(x)=\operatorname{sign} g\left(w^T x+b\right), x \in \mathbb{R}^2$ on the following training data: Class -1: $\left\{\binom{2}{0},\binom{0}{2},\binom{2}{2}\right\}$, Class - 2: $\left\{\binom{0}{0}\right\}$ Hard-margin support vector machine (SVM) formulation is solved to obtain $w$ and $b$. Which of the following options is/are correct?

Let $D=\left\{x^{(1)}, \ldots ., x^{(n)}\right\}$ be a dataset of $n$ observations where each $x^i \in \mathbb{R}^{100}$. It is given that $\sum_{i=1}^n x^{(\mathrm{i})}=0$ The covariance matrix computed from $D$ has eigenvalues $\lambda_i=100^{2-i}, 1 \leq i \leq 100$. Let $u \in \mathbb{R}^{100}$ be the direction of maximum variance with $u^T u=1$. The value of $\frac{1}{n} \sum_{i=1}^n\left(u^T x^{(i)}\right)^2= $_________

Let $C_1$ and $C_2$ be two sets of objects. Let $D(x, y)$ be a measure of dissimilarity between two objects $x$ and $y$. Consider the following definitions of dissimilarity between $C_1$ and $C_2$. DIS-1 $\left(C_1, C_2\right)=\max _{x \in C_1, y \in C_2} D(x, y)$ DIS-2 $\left(C_1, C_2\right)=\min _{x \in C_1, y \in C_2} D(x, y)$ Which of the following statements Which of the following statements is/are correct?

Consider designing a linear classifier $$ y=\operatorname{sign}(f(x ; w ; b)), f(x ; w, b)=w^{\mathrm{T}} x+b $$ on a dataset $$ \begin{aligned} & D=\left\{\left(x_1, y_1\right),\left(x_2, y_2\right) \ldots \ldots\left(x_N, y_N\right)\right\} \\ & x_i \in \mathbb{R}^d, y_i \in\{+1,-1\}, i=1,2, \ldots \ldots, N \end{aligned} $$ Recall that the sign function outputs +1 if the argument is positive, and -1 if the argument is non-positive. The parameters $w$ and $b$ are updated as per the following training algorithm: $$ w_{\text {new }}=w_{\text {old }}+y_n x_n, b_{\text {new }}=b_{\text {old }}+y_n $$ Whenever sign $\left(f\left(x_n ; w_{\text {old }}, b_{\text {old }}\right)\right) \neq y_n$ In other words, whenever the classifier wrongly predicts a sample $\left(x_n, y_n\right)$ from the dataset, $w_{\text {old }}$ gets updated to $w_{\text {new }}$, and likewise $b_{\text {old }}$ gets updated to $b_{\text {new }}$. Consider the case $$ \left(x_n,+1\right), f\left(x_n ; w_{\text {old }}, b_{\text {old }}\right)<0 \text {. Then } $$

Given data $\{(-1,1),(2,-5),(3,5)\}$ of the form $(x, y)$, we fit a model $y=w x$ using linear least-squares regression. The optimal value of $w$ is _________

(Round off to three decimal places) The naive Bayes classifier is used to solve a two-class classification problem with class labels $y_1, y_2$. Suppose the prior probabilities are $P\left(y_1\right)=\frac{1}{3}$ and $P\left(y_2\right)=\frac{2}{3}$. Assuming a discrete feature space with $P\left(x \mid y_1\right)=\frac{3}{4}$ and $P\left(x \mid y_2\right)=\frac{1}{4}$ for a specific feature vector $x$. The probability of misclassifying $x$ is _________ (Round off to two decimal places)