Register

Search results for isi2011

6 votes
2 answers
1
ISI2011-PCB-CS-4a
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that $L$ is not regular. $L^2$ is regular.
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that$L$ is not regular.$L^2$ is regular.
User Avatar
2 votes
2 answers
5
ISI2011-PCB-CS-5a
Consider relations $R(A, B)$ and $S(B, C)$. Find a propositional formula $\phi$ such that the following two relational algebra expressions produce the same answer. $\pi_{A,B}(\sigma_\phi(R \bowtie S))$ $R \cap ({\rho_T(A)}(\pi_C(S)) \times \pi_B(S))$
Consider relations $R(A, B)$ and $S(B, C)$. Find a propositional formula $\phi$ such that the following two relational algebra expressions produce the same answer.$\pi_{A...
User Avatar
3 votes
4 answers
6
ISI2011-PCB-CS-3a
Solve the following recurrence ($n$ is a natural number): $T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$
Solve the following recurrence ($n$ is a natural number):$$T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$$
User Avatar
2 votes
1 answer
9
ISI2011-PCB-A-3b
The numbers $1, 2, \dots , 10$ are arranged in a circle in some order. Show that it is always possible to find three adjacent numbers whose sum is at least $17$, irrespective of the ordering.
The numbers $1, 2, \dots , 10$ are arranged in a circle in some order. Show that it is always possible to find three adjacent numbers whose sum is at least $17$, irrespec...
User Avatar
10 votes
2 answers
10
ISI2011-PCB-A-2a
Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of $a, b, c, d$.
Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of ...
User Avatar
2 votes
0 answers
19
ISI2011-PCB-A-4a
Consider six distinct points in a plane. Let $m$ and $M$ denote the minimum and maximum distance between any pair of points. Show that $M/m \geq \sqrt{3}$.
Consider six distinct points in a plane. Let $m$ and $M$ denote the minimum and maximum distance between any pair of points. Show that $M/m \geq \sqrt{3}$.
User Avatar
2 votes
0 answers
20
ISI2011-PCB-A-1
Let $D = \{d_1, d_2, \dots, d_k\}$ be the set of distinct divisors of a positive integer $n$ ($D$ includes 1 and $n$). Then show that $\Sigma_{i=1}^k \sin^{-1} \sqrt{\log_nd_i}=\frac{\pi}{4} \times k$. hint: $\sin^{−1} x + \sin^{−1} \sqrt{1-x^2} = \frac{\pi}{2}$
Let $D = \{d_1, d_2, \dots, d_k\}$ be the set of distinct divisors of a positive integer $n$ ($D$ includes 1 and $n$). Then show that$\Sigma_{i=1}^k \sin^{-1} \sqrt{\log_...
User Avatar
To see more, click for the full list of questions or popular tags.