search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Recent questions tagged cmi2011

1 vote
2 answers
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.
asked May 27, 2016 in Graph Theory jothee 283 views
1 vote
1 answer
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)$?
asked May 27, 2016 in Algorithms jothee 162 views
1 vote
1 answer
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?
asked May 27, 2016 in Algorithms jothee 184 views
1 vote
1 answer
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.
asked May 27, 2016 in Graph Theory jothee 204 views
1 vote
1 answer
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.
asked May 27, 2016 in Graph Theory jothee 213 views
1 vote
1 answer
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$?
asked May 27, 2016 in Theory of Computation jothee 183 views
2 votes
0 answers
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)$?
asked May 20, 2016 in DS jothee 161 views
12 votes
3 answers
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.
asked May 19, 2016 in Algorithms jothee 816 views
1 vote
1 answer
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?
asked May 19, 2016 in Algorithms jothee 153 views
1 vote
1 answer
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$.
asked May 19, 2016 in Theory of Computation jothee 159 views
1 vote
1 answer
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.
asked May 19, 2016 in Algorithms jothee 181 views
3 votes
1 answer
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.
asked May 19, 2016 in Set Theory & Algebra jothee 183 views
1 vote
2 answers
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?
asked May 19, 2016 in Graph Theory jothee 251 views
4 votes
1 answer
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$
asked May 19, 2016 in Operating System jothee 184 views
1 vote
1 answer
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
asked May 19, 2016 in Theory of Computation jothee 484 views
10 votes
3 answers
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.
asked May 19, 2016 in Compiler Design jothee 797 views
22 votes
3 answers
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
asked May 19, 2016 in Graph Theory jothee 948 views
1 vote
2 answers
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
asked May 19, 2016 in Quantitative Aptitude jothee 2k views
2 votes
2 answers
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$
asked May 19, 2016 in Set Theory & Algebra jothee 366 views
1 vote
1 answer
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$
asked May 19, 2016 in Quantitative Aptitude jothee 537 views
1 vote
3 answers
21
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.
asked May 19, 2016 in Probability jothee 333 views
1 vote
1 answer
22
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.
asked May 19, 2016 in Probability jothee 291 views
1 vote
1 answer
23
Let L $\subseteq \{0, 1\}^∗$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^∗$, 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).
asked May 19, 2016 in Theory of Computation jothee 333 views
To see more, click for the full list of questions or popular tags.
...