Courses

Computer Science Engineering (CSE)

Ask a question

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum indepen­dent set of G is
  • a)
    12
  • b)
    8
  • c)
    Less than 8
  • d)
    More than 12
Correct answer is option 'A'. Can you explain this answer?

PANKAJ BISHT answered  •  2 hours ago
Background Explanation: Vertex cover is a set S of vertices of a graph such that each edge of the graph is incident to at least one vertex of S. Independent set of a graph is a set of vertices such that none of the vertices in this set have an edge connecting them i.e. no two are adjacent. A single vertex is an independent set, but we are interested in maximum independent set, that is largest set which is independent set. Relation between Independent Set and Vertex Cover : An interesting fact is, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set. How? removing all vertices of minimum vertex cover leads to maximum independent set. So if S is the size of minimum vertex cover of G(V,E) then the size of maximum independent set of G is |V| - S. Solution: size of minimum vertex cover = 8 size of maximum independent set = 20 - 8 =12 Therefore, correct answer is (A). References : vertex cover maximum independent set.

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
  • a)
    1
  • b)
    2
  • c)
    3
  • d)
    n
Correct answer is option 'C'. Can you explain this answer?

SUDHANSHU MISHRA answered  •  2 hours ago
A graph is connected iff all nodes can be traversed from each node. For a graph with n nodes, there will be n-1 minimum number of edges. 
Given that there are n edges, that means a cycle is there in the graph.
The simplex graph with these conditions may be:
Now we can make a different spanning tree by removing one edge from the cycle, one at a time.
Minimum cycle length can be 3, So, there must be atleast 3 spanning trees in any such Graph.

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is 
  • a)
    7
  • b)
    8
  • c)
    9
  • d)
    10
Correct answer is option 'A'. Can you explain this answer?

JAYANARAYANAN.M.S MURALI.C.C answered  •  2 hours ago
20-7 -> 13 will be in blocked state, when we perform 12 V(S) operation makes 12 more process to get chance for execution from blocked state. So one process will be left in the queue (blocked state) here i have considered that if a process is in under CS then it not get blocked by other process.

Consider the procedure below for the Producer-Consumer problem which uses semaphores:
 
Q. Which one of the following is TRUE?
  • a)
    The producer will be able to add an item to the buffer, but the consumer can never consume it.
  • b)
    The consumer will remove no more than one item from the buffer.
  • c)
    Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
  • d)
    The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.
Correct answer is option 'C'. Can you explain this answer?

SHUBHAM KUMAR answered  •  2 hours ago
Initially, there is no element in the buffer. 
Semaphore s = 1 and semaphore n = 0. 
We assume that initially control goes to the consumer when buffer is empty. 
semWait(s) decrements the value of semaphore ‘s’ . Now, s = 0 and semWait(n) decrements the value of semaphore ‘n’. Since, the value of semaphore ‘n’ becomes less than 0 , the control stucks in while loop of function semWait() and a deadlock arises. 
 
Thus, deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty. 

Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below.
Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes:
  • P2 must complete use of R1 before P1 gets access to R1
  • P1 must complete use of R2 before P2 gets access to R2.
  • P2 must complete use of R3 before P1 gets access to R3.
  • P1 must complete use of R4 before P2 gets access to R4.
There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?
  • a)
    1
  • b)
    2
  • c)
    3
  • d)
    4
Correct answer is option 'B'. Can you explain this answer?

KUMAR UTKARSH answered  •  2 hours ago
P1:
Compute;
Wait(A);
Use R1;
Use R2;
Signal(B);
Wait(A);
Use R3;
Use R4;
Signal(B);
P2:
Compute;
Wait(B);
Use r1;
Signal(A);
Wait(B);
Use R2;
Use R3;
Signal(A);
Wait(B);
Use R4;
Signal(B);
In process p1, initially control will be stuck in while loop of Wait(A) because A = 0. In process p2, Wait(B) decrements the value of B to 0 . Now, P2 uses the resource R1 and increments the value to A to 1 so that process P1 can enter its critical section and use resource R1. 
Thus, P2 will complete use of R1 before P1 gets access to R1. 
Now, in P2 values of B = 0. So, P2 can not use resource R2 till P1 uses R2 and calls function Signal(B) to increment the value of B to 1. Thus, P1 will complete use of R2 before P2 gets access to R2. 
Now, semaphore A = 0. So, P1 can not execute further and gets stuck in while loop of function Wait(A). Process P2 uses R3 and increments the value of semaphore A to 1.Now, P1 can enter its critical section to use R3. Thus, P2 will complete use of R3 before P1 gets access to R3. 
Now, P1 will use R4 and increments the value of B to 1 so that P2 can enter is critical section to use R4. Thus, P1 will complete use of R4 before P2 gets access to R4. 
Thus, option (B) is correct. 
Please comment below if you find anything wrong in the above post.

Consider the following two statements: 
  • a)
    Only S1 is correct
  • b)
    Only S2 is correct
  • c)
    Both S1 and S2 are correct
  • d)
    None of S1 and S2 is correct
Correct answer is option 'A'. Can you explain this answer?

HIND PRATAP answered  •  13 hours ago
We can easily build a DFA for S1. All we need to check is whether input string has even number of 0's. Therefore S1 is regular. We can't make a DFA for S2. For S2, we need a stack. Therefore S2 is not regular.

Which of the following decision problems are undecidable
  • a)
    I and IV only
  • b)
    II and III only
  • c)
    III and IV only
  • d)
    II and IV only
Correct answer is option 'C'. Can you explain this answer?

ABHINAV RANA answered  •  13 hours ago
A problem is undecidable if there is no algorithm to find the solution for it. Problem give in III and IV have no solutions, so these are undecidable.

Consider the following three table to store student enrollements in different courses.
Student(EnrollNo, Name)
Course(CourseID, Name)
EnrollMents(EnrollNo, CourseID)
Q. What does the following query do?
  • a)
    Name of all students who are either enrolled in "DBMS" or "OS" courses
  • b)
    Name of all students who are enrolled in "DBMS" and "OS"
  • c)
    Name of all students who are either enrolled in "DBMS" or "OS" or both.
  • d)
    Non of the above
Correct answer is option 'B'. Can you explain this answer?

SHARDUL VINOD answered  •  13 hours ago
Background Reading: The above query is an example of nested query i.e. query within a query. Firstly the inner query is solved and then the outer one depending on the result of the inner query.
  • WHERE IN returns values that matches values in a list or subquery.
  • WHERE IN is a shorthand for multiple OR conditions.
Here, firstly the inner query is solved. It returns all the Enrollment
Numbers (SELECT S2.EnrollNo) of students where the students’ enrollment
number matches with the enrollment number of the courses
(WHERE S2.EnrollNo = E2.EnrollNo) which have the course IDs whose Course
Name is “OS” (E2.CourseID = C2.CourseID and C2.Name = “OS”).
Hence all the enrollment IDs are filtered out for the students who are enrolled for the “OS” course.
The outer query works similarly and filters out all the all tuples where the Students Enrollment Number matches with the Enrollment Number where the course ID’s are for the course names “DBMS”
(S.EnrollNo = E.EnrollNo AND C.Name =”DBMS” AND E.CourseID = C.CourseId) and additionally matches with the ones that are returned by the inner query i.e. Enrollment Number of students who are enrolled for the course “OS”.
Hence the above queries returns names of all students (SELECT S.Name) who have enrolled for both courses “DBMS” and “OS”. Hence option (B).

Consider the languages
  • a)
    Only L2 is context free.
  • b)
    Only L2 and L3 are context free.
  • c)
    Only L1 and L2 are context free.
  • d)
    All are context free
Correct answer is option 'D'. Can you explain this answer?

CHANDRA BHANU answered  •  13 hours ago
All are context free.
L1 -> Push 0 on stack and when 1 comes, start popping. If stack becomes empty and 1's are remaining start pushing 1. At
end of string accept if stack is non- empty.
L2 -> Do the same as for L1, but accept if stack is empty at end of string.
L3 -> Do, the same as for L2, but for each 0, push two 0's on stack and start the stack with a 0.
L4 -> Do the same as for L1, but for each 0, push two 0's on stack
All are in fact DCFL. Pushing two 0's on stack might sound non-trivial but we can do this by pushing one symbol and going
to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

In the automaton below, s is the start state and t is the only final state.
 
Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true? 
  • a)
    The automaton accepts u and v but not w
  • b)
    The automaton accepts each of u, v, and w
  • c)
    The automaton rejects each of u, v, and w
  • d)
    The automaton accepts u but rejects v and w
Correct answer is option 'D'. Can you explain this answer?

SAHIL KUMAR answered  •  13 hours ago
For the acceptance and rejection of any string we can simply check for the movement on each input alphabet between states. A string is accepted if we stop at any final state of the DFA. For string u=abbaba the string ends at t (final state) hence it is accepted by the DFA. For string v=bab the string ends at s (non-final state) and hence rejected by the DFA. For string w=aabb the string ends at s (non-final state) and hence rejected by the DFA. 

Which of the following statement is/are incorrect? 
A: A schedule following strict two phase locking protocol is conflict serializable as well as recoverable.
B: Checkpoint in schedules are inserted to ensure recoverability.
  • a)
    Only 1
  • b)
    Only 2
  • c)
    Both 1 and 2
  • d)
    None
Correct answer is option 'B'. Can you explain this answer?

ANUJ BAGGA answered  •  yesterday
Basic two phase locking protocol ensures only conflict serializability and strict two phase locking protocol ensures recoverability as well. So statement A is correct. Checkpoints are inserted to minimize the task of undo-redo in recoverability. So, statement B is not correct. Hence correct option B is correct choice.

The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2, x) is same as 2x)
  • a)
    power(2, n)
  • b)
    power(2, n2)
  • c)
    power(2, (n2 + n)/2)
  • d)
    power(2, (n2 - n)/2)
Correct answer is option 'C'. Can you explain this answer?

HIMANK RAWAT answered  •  yesterday
We are considering a symmetric matrix (given in question). So, we need to look at half of elements ie. either upper or lower traingle i.e. A[i][j] = A[j][i] Hence, No. of elements = (n^2 + n)/2 Since, we have only two elements : 0 & 1 No. of choices = 2 Therefore, No. of possibilities = 2 ^ (No. of elements) = 2 ^ ((n^2 + n)/2) = power (2 , (n^2 + n)/2) 

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be
  • a)
    best if A is in row-major, and B is in column- major order
  • b)
    best if both are in row-major order
  • c)
    best if both are in column-major order
  • d)
    independent of the storage scheme
Correct answer is option 'D'. Can you explain this answer?

DHIRENDRA GUPTA answered  •  yesterday
This is a trick question. Note that the questions asks about time complexity, not time taken by the program. for time complexity, it doesn't matter how we store array elements, we always need to access same number of elements of M1 and M2 to multiply the matrices. It is always constant or O(1) time to do element access in arrays, the constants may differ for different schemes, but not the time complexity.

How many substrings (of all lengths inclusive) can be formed from a character string of length n ? Assume all characters to be distinct, prove your answer.
  • a)
    1+[n(n+1)/2]
  • b)
    1-[n(n+1)/2]
  • c)
    [n(n+1)/2]
  • d)
    [n(n-1)/2]
Correct answer is option 'A'. Can you explain this answer?

SPARSH PANWAR answered  •  yesterday
Lets take an example . lets consider the given string is GATE.
so set of string of length 1 ={G,A,T,E} ; cardinality of set = 4
set of string of length 2 ={GA,AT,TE}
set of string of length 3={GAT,ATE}
set of strings of length 4 ={GATE}
and set of string of length 0 ={}
and we cant have any substring of length 5 as given string has only 4 length.
so total no of substrings are possible =0's length substring + 1lengths substrings + 2 length substrings +3 length substrings + 4 length substrings = 1+4+3+2+1
means for 1 length string to n length substrings . it will sum of the n natural no from 1 to n.
so 1+2+3+............... +n = n(n+1)/2
so total no substrings possible = 0 length strings + n(n+1)/2= 1+[n(n+1)/2]
so total no of substrings possible in n length string (All length inclusive) = 1+[n(n+1)/2]

Let X and Y be finite sets and f: X -> Y be a function. Which one of the following statements is TRUE? 
  • a)
    For any subsets A and B of X,|f(A∪B)| = |f(A)|+|f(B)|
  • b)
    For any subsets A and B of X, f(A∩B) = f(A)∩f(B)
  • c)
    For any subsets A and B of X, |f(A∩B)| =min{|f(A)|,|f(B)|}
  • d)
    For any subsets S and T of Y, f-1(S∩T) =f-1(s)∩f-1(T)
Correct answer is option 'D'. Can you explain this answer?

ARYAMAN PANDEY answered  •  yesterday
Let x = {a, b, c} and y = {1, 2} A Function f maps each element of x to 1 in y. f(a)=1 , f(b)=1 , f(c) =1 A = {a, b} B = {b, c}
----------------------------------------------
A] |f(A u B) | = |f({a, b, c})| = 3 | f(A)|+|f(B)| = 2 + 2 = 4 , LHS != RHS.
----------------------------------------------
B] f(A ∩ B) = f({b}) = { 1 } f(A) ∩ f(B) = {1, 1} ∩ {1, 1} = {1, 1} LHS != RHS
-----------------------------------------------
C] |f(A ∩ B)| = |f({b})| = |{ 1 }| = 1 min{|f(A)|,|f(B)|} = min(2,2) = 2 LHS != RHS
-----------------------------------------------
D] In a function a value can be mapped only to one value.

Assume that you are flipping a fair coin, i.e. probability of heads or tails is equal. Then the expected number of coin flips required to obtain two consecutive heads for the first time is.
  • a)
    4
  • b)
    3
  • c)
    6
  • d)
    10
  • e)
    5
Correct answer is option 'C'. Can you explain this answer?

ANURAG PANDEY answered  •  yesterday
Let the expected number of coin flips be . The case analysis goes as follows:
a. If the first flip is a tails, then we have wasted one flip. The probability of this event is 1/2 and the total number of flips required is X + 1.
b. If the first flip is a heads and second flip is a tails, then we have wasted two flips. The probability of this event is 1/4 and the total number of flips required is X + 2 as the same scenario as beginning is there even after 2 tosses.
c. If the first flip is a heads and second flip is also heads, then we are done. The probability of this event is 1/4 and the total number of flips required is 2.

Thus, the expected number of coin flips for getting two consecutive heads is 6.  

What is the time complexity of Huffman Coding?
  • a)
    O(N)
  • b)
    O(NlogN)
  • c)
    O(N(logN)^2)
  • d)
    O(N^2)
Correct answer is option 'B'. Can you explain this answer?

SUBHADIP KHAWAS answered  •  yesterday
O(nlogn) where n is the number of unique characters. If there are n nodes, extractMin() is called 2*(n – 1) times. extractMin() takes O(logn) time as it calles minHeapify(). So, overall complexity is O(nlogn). See here for more details of the algorithm.

Consider the function f(x) = sin x in the interval x = [π/4 , 7π /4]. The number and location(s) of the local minima of this function are
  • a)
    One, at  π/2
  • b)
    One, at  3π/2
  • c)
    Two, at 
  • d)
    Two, at  π/2 and 3π/2
  • e)
    Two, at π/4 and 3π/2 
Correct answer is option 'D'. Can you explain this answer?

VUTUKURI SMS answered  •  yesterday
which lie between given domain in question
it means it is local maxima and at which is local minima and since it at  is local maxima so before it graph is strictly increasing so  is also local minima
so there is two local minima  
Sine function increases till π/2 and so for the considered interval π/4 would be a local minimum. From π/2, value of sine keeps on decresing till 3π/2 and hence 3π/2 would be another local minima. So, (D) is the correct answer here.

Let    be a context free grammar where the rule set R is    Which of the following statements is true?
  • a)
    G is not ambiguous
  • b)
    There exis x,y ∈ L(G) such that xy ∉ L(G)
  • c)
    There is a deterministic pushdown automaton that accepts L(G)
  • d)
    We can find a deterministic finite state automaton that accepts L(G)
Correct answer is option 'C'. Can you explain this answer?

PAWAN KUMAR answered  •  yesterday
It will be easy to analyze the problem if we replace terminal a and b by ( and ) respectively. 
S →(S) | SS | ε
L(G) = balanced parentheses [each left parenthesis has a matching right parenthesis and are well nested ]
example () , ()(), (()), (()()()).
String () can be derived by above three way each having different derivation tree.
So G is Ambiguous
b) Concatenation of two balance parenthesis will be balanced also . eq. x = (()) y= () xy= (())().
c) We can design Deterministic PDA for L. put left parenthesis (only) in stack and pop with right parenthesis.
d) We cannot design DFA for L because we need a stack to match left parenthesis with right parenthesis.
only option C is true.

Fetching relevant content for you
Ask a question

Recommended Tests

Recommended Content

Related Courses

Follow Us
© 2015-20 EduRev