Recent questions tagged cmi2018

Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$?$aba$$bab$$abba$$aabb$

Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend....

In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional ...

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...

How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$$\binom...

Let $C_{n}$ be the number of strings $w$ consisting of $n$ $X's$ and $n$ $Y's$ such that no initial segment of $w$ has more $Y's$ than $X's.$ Now consider the following p...

There are $7$ switches on a switchboard, some of which are on and some of which are off. In one move, you pick any $2$ switches and toggle each of them-if the switch you ...

Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes plac...

What does the following function compute in terms of $n$ and $d$, for integer value of $n$ and $d,d>1?$ Note that $a//b$ denotes the quotient(integer part) of $a \div b,$...

Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$Give an example ...

A student requests a recommendation letter from a professor. The professor gives three sealed envelopes. Each envelope contains either a good recommendation letter or a b...

Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...

You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by ...

Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\...

You are playing an old-style video game in which you have to shoot down alien spaceships as they fly across the screen from left to right. Each spaceship flies across the...

A First In First Out queue is a data structure supporting the operation Enque, Deque, Print, Enque(x) adds the item $x$ to the tail of the queue. Deque removes the elemen...