search
Log In

Recent questions tagged cmi2013

2 votes
1 answer
1
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch ... on dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.
asked Jun 8, 2016 in Algorithms Arjun 375 views
3 votes
2 answers
2
Consider the code below, defining the function $\text{mystery}:$ mystery(a,b){ if (a < 0 or b < 0) return 0; else if (a == 0) return b+1; else if (b == 0) return mystery(a-1,1); else return mystery(a-1, mystery(a,b-1)); } Express $\text{mystery}(1, \:n)$ as a function of $n$. Express $\text{mystery}(2,\: n)$ as a function of $n$. Compute $\text{mystery}(3, \:2)$ and $\text{mystery}(3, 3)$.
asked May 23, 2016 in Algorithms jothee 218 views
1 vote
1 answer
3
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as ... next match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm.
asked May 23, 2016 in Algorithms jothee 241 views
3 votes
0 answers
4
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your ... constraints. Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
asked May 23, 2016 in Algorithms jothee 82 views
5 votes
0 answers
5
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.
asked May 23, 2016 in Algorithms jothee 310 views
1 vote
2 answers
6
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
asked May 23, 2016 in Graph Theory jothee 239 views
14 votes
2 answers
7
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on $10$ vertices. Let $u$, $v$, $ w$ be three distinct vertices in $G$. How many simple paths are there from $u$ to $v$ going through $w$?
asked May 23, 2016 in Graph Theory jothee 946 views
2 votes
1 answer
8
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be the value of $x$ interpreted as a binary number, where $a_0$ is the most significant bit. More formally, $val(x)$ is given by $\Sigma_{0 \leq i < n} 2^{n-1-i} .a_i$ Design a finite automaton that accepts exactly the set of binary strings $x$ such that $val(x)$ is divisible by either 4 or 5.
asked May 23, 2016 in Theory of Computation jothee 110 views
6 votes
2 answers
9
The below question is based on following program: procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for j := 1 to 100 do position := j; for i := j to 100 do if (A[i] > A[position]) then position := i; endfor tmp := A[j]; A[j] := A[ ... := tmp; endfor end The number of times the test $A[i] > A[\text{position}]$ is executed is: $100$ $5050$ $10000$ Depends on contents of $A$
asked May 23, 2016 in Algorithms jothee 519 views
9 votes
2 answers
10
The below question is based on the following program. procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for j := 1 to 100 do position := j; for i := j to 100 do if (A[i] > A[position]) then position := i; ... ]; A[position] := tmp; endfor end When the procedure terminates, the array A has been: Reversed Sorted in descending order Left unaltered Sorted in ascending order
asked May 23, 2016 in Algorithms jothee 428 views
3 votes
1 answer
11
In the passing out batch, $54$ students know Java, $39$ know Python and $43$ know C++. Of these, $15$ know both Java and Python, $17$ know both Python and C++ and $23$ know both Java and C++ and $11$ know all three languages. If there are $100$ students in the class, how many know none of these three languages? $3$ $8$ $17$ $19$
asked May 23, 2016 in Numerical Ability jothee 124 views
15 votes
3 answers
12
Consider the following two statements. There are infinitely many interesting whole numbers. There are finitely many uninteresting whole numbers. Which of the following is true? Statements $1$ and $2$ are equivalent. Statement $1$ implies statement $2$. Statement $2$ implies statement $1$. None of the above.
asked May 23, 2016 in Mathematical Logic jothee 711 views
16 votes
3 answers
13
A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of degree ... of degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
asked May 23, 2016 in Graph Theory jothee 983 views
27 votes
3 answers
14
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time: $O(nm \log m)$ $O(mn \log n)$ $O(m + n)$ $O(mn)$
asked May 23, 2016 in Algorithms jothee 1.8k views
1 vote
1 answer
15
Consider the set of all words over the alphabet $\{x, y, z\}$ where the number of $y$&rsquo;s is not divisible by 2 or 7 and no $x$ appears after a $z$. This language is: regular not known to be regular context-free but not regular recursively enumerable but not context-free
asked May 23, 2016 in Theory of Computation jothee 79 views
1 vote
1 answer
16
When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, ... by the user. A good data structure for accumulating the scores and ranking them is: a queue a heap a stack a binary search tree
asked May 23, 2016 in DS jothee 131 views
10 votes
4 answers
17
$10\%$ of all email you receive is spam. Your spam filter is $90\%$ reliable: that is, $90\%$ of the mails it marks as spam are indeed spam and $90\%$ of spam mails are correctly labeled as spam. If you see a mail marked spam by your filter, what is the probability that it really is spam? $10\%$ $50\%$ $70\%$ $90\%$
asked May 23, 2016 in Probability jothee 1.5k views
1 vote
0 answers
18
Ball Mart has $10^7$ different items in stock across all its stores worldwide. The company has collected billing data for $10^{10}$ customer transactions. Each individual bill has at most $10$ distinct items in it. Ball Mart's CEO wants to optimize the company's inventory ... is the most precise upper bound one can compute for the number of such items, given the data? $500$ $1000$ $5000$ $20000$
asked May 23, 2016 in Numerical Ability jothee 90 views
To see more, click for the full list of questions or popular tags.
...