# Recent activity by Pranav Kant Gaur

1
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.
2
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
3
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false
4
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ are ... line graph of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
5
Which one of the following functions is continuous at $x = 3?$ $f(x) = \begin{cases} 2,&\text{if$x = 3$} \\ x-1& \text{if$x > 3$}\\ \frac{x+3}{3}&\text{if$x < 3$} \end{cases}$ $f(x) = \begin{cases} 4,&\text{if$x = 3$} \\ 8-x& \text{if$x \neq 3$} \end{cases}$ ... $} \\ x-4& \text{if$x > 3$} \end{cases}$ $f(x) = \begin{cases} \frac{1}{x^3-27}&\text{if$x \neq 3$} \end{cases}$
6
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
7
Hari(H), Gita(G), Irfan(I) and Saira(S) are siblings (i.e., brothers and sisters). All were born on 1st January. The age difference between any two successive siblings (that is born one after another) is less than three years. Given the following facts: Hari's age + Gita ... and Saira is not the youngest. There are no twins. In what order they were born (oldest first)? $HSIG$ $SGHI$ $IGSH$ $IHSG$
8
Consider the set of (column) vectors defined by$X = \left \{x \in R^3 \mid x_1 + x_2 + x_3 = 0, \text{ where } x^T = \left[x_1,x_2,x_3\right]^T\right \}$.Which of the following is TRUE? $\left\{\left[1,-1,0\right]^T,\left[1,0,-1\right]^T\right\}$ is a ... is a linearly independent set, but it does not span $X$ and therefore is not a basis of $X$. $X$ is not a subspace of $R^3$. None of the above
9
What is the number of tokens in the below C code? int foo(int i, int j){ return printf(" I do it correctly", i > j); }
10
#include <stdio.h> int main() { int i = 10; int *const p = &i; fd(&p); printf("%d\n", *p); } void fd(int **p) { int j = 11; *p = &j; printf("%d\n", **p); }
11
Consider the following recursive function which is used by dynamic programming. Assume for every function call T(i) it checks the table first, if its value is already computed it retrieves the value from table. Otherwise it calls a recursive function call to compute its ... The number of function calls that need the support of stack to complete the execution of the function T(12) are __________ .
12
A 2-km-long, 10-Mbps CSMA/CD LAN (not 802.3) has a propagation speed of 200 m/microsec. Repeaters are not allowed in this system. Data frames are 512 bits long, including 32 bits of header, checksum, and other overhead. The first ... frame. The effective data rate is _____________________ Mbps (correct to 2 decimal places), excluding overhead, assuming that there are no collisions?
13
Consider a system with a two-level paging scheme in which a regular memory access takes $150$ $nanoseconds$, and servicing a page fault takes $8$ $milliseconds$. An average instruction takes $100$ nanoseconds of CPU time, and two memory accesses. The TLB ... average instruction execution time? $\text{645 nanoseconds}$ $\text{1050 nanoseconds}$ $\text{1215 nanoseconds}$ $\text{1230 nanoseconds}$
14
A cube is built using $64$ cubic blocks of side one unit. After it is built, one cubic block is removed from every corner of the cube. The resulting surface area of the body (in square units) after the removal is ________. $56$ $64$ $72$ $96$
15
Archimedes said, "Give me a lever long enough and a fulcrum on which to place it, and I will move the world." The sentence above is an example of a ____________ statement. figurative collateral literal figurine
16
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$
17
Consider the following CFG, find the number of productions in the minimized grammar after it was convert it into Greibach normal form. S → AA| 0, A → SS | 1 plzzz explain how to convert the given grammer into gnf in detail.
18
Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE? These two elements can be determined using $O\left(\log^{100}n\right)$ comparisons. $O\left(\log^{100}n\right)$ ... $2(n - 1)$ comparisons. None of the above.
19
Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \langle 1,....,n \right \rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order given by this permutation. ... number of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$
20
I am getting independent but answer is given as dependent. Can some one tell me what worng with my approach
21
$f(x) = n^{log (n)}$ $g(x) = nlog (n)$ $h(x) = 2^{n}$ Arrange Them in Increasing Order of rate of growth
22
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.
23
You are lost in the National park of Kabrastan. The park population consists of tourists and Kabrastanis. Tourists comprise two-thirds of the population the park and give a correct answer to requests for directions with probability $\dfrac{3}{4}$. The air of Kabrastan has an amnesaic quality, however, ... $\left(\dfrac{1}{2}\right)$ $\left(\dfrac{2}{3}\right)$ $\left(\dfrac{3}{4}\right)$
24
How many ways are there to: Put n distinguishable balls in r distinguishable boxes? Put n indistinguishable balls in r distinguishable boxes? Put n distinguishable balls in r indistinguishable boxes? Put n indistinguishable balls in r indistinguishable boxes? Where, $r \geq n$
25
Question A subway train in a certain line runs after every half hour, between every midnight and 6 in the morning. What is the probability that a man entering the station at random will have to wait at least 20 minutes? I'm stuck here... It can be solved using ... ? in this case what is the upper limit of the integral ? URL : https://www.assignmentexpert.com/homework-answers/Math-Answer-40654.pdf
26
Given a sorted array of n elements where other than one element x every other element repeat two times. Then how much time will it take to find position of x?