# Recent questions tagged cmi2011

1 vote
1
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any ... of preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.
1 vote
2
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first element of ... bit. g2(n) if (n == 0) then return(0) else return f2(g2(n-1),g1(n)) endif What is the value of $g2(256)$ and $g2(257)$?
1 vote
3
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is ... or $\text{chapatis}$ between two big spoons and flipping the stack.) How many steps will your algorithm take in the worst case?
1 vote
4
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ ... $H$ such that we cannot find three distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,$ and $G − u_3$ is connected.
1 vote
5
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Given a good graph, devise a linear time algorithm to find two such vertices.
1 vote
6
Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\}^* \mid \text{ reverse}(w) \in L \}$ - here $reverse(w)$ denotes the string $w$ ... $x=yz, \: y \in L, \: z \in L^R \}$ is regular. How can you use $N$ to construct an automata for $L.L^R$?
7
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ ... bit. g2(n) if (n == 0) then return(0) else return f2(g2(n-1),g1(n)) endif What is the value of $g2(7)$ and $g2(8)$?
8
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest ... $\text{chapatis}$ between two big spoons and flipping the stack.) Give an algorithm for sorting the disks using this operation.
1 vote
9
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$. Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?
1 vote
10
Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\} | \text{ reverse}(w) \in L \}$ - here $reverse(w)$ ... in reverse. For example $reverse(0001) = 1000$. Show that $L^R$ is regular, How can you use $N$ to construct an automata to recognize $L^R$.
1 vote
11
Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered $1, 2, \dots , M$. You have $N$ players, numbered $1, 2, \dots , N$ from which to choose your team, where $N \geq M$. Each of the $M$ ... Propose an efficient algorithm to solve this problem and analyse its complexity.
12
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Show that for any subgraph $H$ of $G$, $H$ is good if and only if $G$ is good.
1 vote
13
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road leads to at ... . Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?
14
Consider the following functions $f$ and $g$: f(){ x = x+1; x = y*y; x = x-y; } g(){ y = y+1; y = x*x; y = y-x; } Suppose we start with initial values of $1$ for $x$ and $2$ for $y$ and then execute $f$ and $g$ in parallel-that is, at each step we either execute one statement ... Which of the following is not a possible final state? $x = 2, y = 2$ $x = 5, y = -1$ $x = -63, y = 72$ $x = 32, y = 5$
1 vote
15
You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your laptop? Turing machine Linear bounded automaton Pushdown automaton Finite state automaton
16
In programming languages like C, C++, Python $\dots$ the memory used by a program is typically separated into two parts, the stack and the heap. Consider the following statements: A stack is efficient for managing nested function calls. Stack space is limited while heap space is not. The stack ... $3$ are true but $2$ is false. $2$ and $3$ are true but $1$ is false. All three statements are true.
17
Let $G=(V, E)$ be a graph. Define $\overline{G}$ to be $(V, \overline{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \overline{E}$ if and only if $(u, v) \notin E$. Then which of the following is true? $\overline{G}$ is always connected. ... $G$ is not connected. At least one of $G$ and $\overline{G}$ connected. $G$ is not connected or $\overline{G}$ is not connected
1 vote
18
A valuable sword belonging to the Grand King was stolen, and the three suspects were Ibn, Hasan, and Abu. Ibn claimed that Hasan stole it, and Hasan claimed that Abu stole it. It was not clear that one of them stole it, but it was later learnt that no innocent person had lied. It was also learnt that the sword was stolen by only one person. Who stole the sword? Ibn Hasan Abu None of them
19
A $\text{3-ary}$ boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be $\text{3-ary}$ boolean functions. We say that $f$ and $g$ are neighbours if $f$ and $g$ agree on at least one input and disagree on at least one ... $\text{3-ary}$ boolean function $h$. How many neighbours does $h$ have? $128$ $132$ $254$ $256$
1 vote
20
Lavanya has to complete $12$ courses for her degree. There are six compulsory courses: Basic and Advanced Mathematics, Basic and Advanced Physics and Basic and Advanced Electronics. She also has to complete six Optional Courses. Each course takes one semester to complete. There are ... , what is the minimum number of semesters that Lavanya needs to complete her course requirements. $3$ $4$ $5$ $6$
1 vote
You have a bag with $347$ black balls and $278$ white balls. Without looking, you pick up two balls from the bag and apply the following rule. If both balls are of the same colour, you throw them both away. Otherwise, you throw away the black ball and ... are possible, but the probability of it being white is greater. Both colours are possible, but the probability of it being black is greater.
You have two six-sided cubic dice but they are numbered in a strange manner. On the first die, two opposite faces are numbered $1$, two opposite faces are numbered $3$ and the last pair of opposite faces are numbered $6$. On the second die, the three pairs of opposing ... than $7$. The probability that the sum is a multiple of $5$ is the same as the probability that the sum is a prime number.
Let L $\subseteq \{0, 1\}^&lowast;$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^&lowast;$, containing 2011 strings. Which of the following statements is true? Justify your answer. $L \: \: \cup \:\: F$ ... string. $L \: \cup \: F$ is never regular. $L \: \cup \: F$ is regular only if $L$ contains $\in$ (the empty string).