Recent questions tagged non-gatecse

Let $S$ be a set of $2n$ (not necessarily distinct) integers.Design an efficient algorithm that finds a partition of $S$ into $n$ pairs such that the maximum sum of the t...

An induced subgraph of an undirected graph $G = (V,E)$ is a graph formed from a non-empty subset $S$ of the vertices $V$ and all of the edges in $E$ connecting pairs of v...

Let $\mathscr{A} = (Q,\Sigma,\delta,q_0,F)$ be a finite-state automaton, where$Q$ is a finite set of states,$\Sigma$ is a finite alphabet,$\delta \subseteq Q \times \Sigm...

Suppose you are consulting for a company that manufactures PC equipment and ships it to distributors all over the country. For each of the next $n$ weeks, they have a pro...

Let $G = (V,E)$ be an undirected connected graph with a cost, $c_e \geq 0$ on each edge e. The costs on the edges may not all be different. A minimum-cost spanning tree o...

Let $S = \sum_{n\geq1} \dfrac{1}{n^2}$ and $A = \sum_{n\geq1}(-1)^{n+1}\dfrac{1}{n^2}$. Then which of the following statements is true?$S$ converges but $A$ does not conv...

Let $a, b$ and $c$ denote regular expressions. Which of the following is an identity$?$None of the choices$a . (b + c) = (b + c) . a$$$c^* . a^* . b^* = c^* . b^* . a^*$$...

Let $f(n) := 2^n, g(n) := n$ and $h(n) :=$ $n^{log n}$. Which of the following statements is true$?$log $h(n) = O(g(n))$ and log $h(n) = \Omega$(log $f(n)).$$f(n)= O(g(n)...

Consider $n$ points equi-separated on a circle of radius one.Fix one of the points, and consider the product of the lengths of the chord from this point to all the other ...

Let $\Sigma =$ {$a,b$}.For a word $w \in \Sigma^*$ and a letter $x \in \Sigma$, let $\#_x(w)$ denote the number of occurrences of $x$ in $w$. For example, for $w = abaab$...

Consider the following recurrence: $A_n$ is the sum of $A_{n-1}$ and a number chosen uniformly at random from {$1,...,n$}, starting from $A_0 :=1$. What is the expected v...

If $\lambda_1,...,\lambda_k$, where $k \geq 2$, are $k$ distinct eigenvalues of a singular $n \times n$ matrix $A$, with associated eigenvectors $v_1,...,v_k$, then which...

Let $X$ be a set of propositional formulas and let $f,g$ be two propositional formulas. An assignment is a function mapping propositional variables to {$true, false$}, an...

A cut-edge in a graph is an edge whose removal disconnects the graph. Let $T$ be a tree with $n$ vertices. Consider the following statements. $T$ has no cycles and $n-1$...

In how many different ways can you distribute three identical red balls and two identical blue balls into one white bin and one black bin$?$$9$$12$$32$$5$

Starting with $x_0 = 0$, suppose you do the following:, at the $n^{th}$ stepyou flip a fair coin: if it is heads then $x_n := x_{n-1} + 1$ and if it is tails then $x_n :=...

A graph property (of simple graphs) is said to be $monotone$ $increasing$ if whenever a graph $G = (V,E)$ has the property, then every graph $G' = (V,E')$ with $E \subset...

How many numbers $x \in$ {$1,...,99$} are there such that $x^{\lceil{\sqrt[3]{x}}\rceil}$ is a perfect cube$?$$4$$23$$19$$22$

Suppose that we roll a fair six-sided die until either a six comes up or we have rolled it ten times. The expected number of times we roll the die isLess than $5$.$8$More...

If $S$ is a set of size $n$, then how many triplets ($A,B,C$) $\subseteq S \times S \times S$ are there such that $A,B$ are disjoint subsets of $C?$$4^n$$3^n$$n^2$$n^n$

Suppose we pick two distinct elements uniformly at random from the set {$1,...,n$}. Let $p$ be the probability that one is twice the other. Which of the following stateme...

Consider the rational number $a_n$ defined recursively as $a_n$ = $\dfrac{1}{1 + a_{n-1}}$, where $a_0 := 0$. Let $F_n$ denote the $n^{th}$ fibonacci number, where $F_0 :...

A team plays in a best-of-three tournament. If they win a match, they are enthused and they win the next match with probability $\frac{3}{4}$. If they lose a match, they ...

Given a $4$-regular graph on $n 10$ vertices, the number of $3$-regular induced subgraphs on 5 vertices is $\binom{n}{5}$$n^5$0$n(n-1)...(n-5)$

What is the correct asymptotic of $\sum^{n}_{i=1} \dfrac {n}{i^2}?$$\Theta(n)$$\Theta(n$ log $n)$$\Theta(1)$$\Theta(n^2)$