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 independent 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

MONIKA SOM asked • 1 hour ago

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0×00400000, and a stack page starting at virtual address 0×FFFFF000. The amount of memory required for storing the page tables of this process is:

Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

- a)a path from s to t in the minimum weighted spanning tree
- b)a weighted shortest path from s to t
- c)an Euler walk from s to t
- d)a Hamiltonian path from s to

Correct answer is option 'A'. Can you explain this answer?

PIYUSH BHATI answered • 2 hours ago

Suppose shortest path from A->B is 6, but in MST, we have A->C->B (A->C = 4, C->B = 3), then along the path in MST, we have minimum congestion, i.e 4

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:

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.

Minimum cycle length can be 3, So, there must be atleast 3 spanning trees in any such Graph.

Consider the following directed graph.

- a)1
- b)2
- c)4
- d)6

Correct answer is option 'D'. Can you explain this answer?

SHYAKUL V answered • 2 hours ago

Following are different 6 Topological Sortings

a-b-c-d-e-f

a-d-e-b-c-f

a-b-d-c-e-f

a-d-b-c-e-f

a-b-d-e-c-f

a-d-b-e-c-f

a-d-e-b-c-f

a-b-d-c-e-f

a-d-b-c-e-f

a-b-d-e-c-f

a-d-b-e-c-f

Ayushi Sharma asked • 4 hours ago

Given the following expression grammar:

E -> E * F | F + E | F

F -> F - F | id

which of the following is true?

E -> E * F | F + E | F

F -> F - F | id

which of the following is true?

- a)* has higher precedence than +
- b)– has higher precedence than *
- c)+ and — have same precedence
- d)+ has higher precedence than *

Correct answer is option 'B'. Can you explain this answer?

Consider the following grammar G.

S → F ⎪ H

F → p ⎪ c

H → d ⎪ c

F → p ⎪ c

H → d ⎪ c

S1: LL(1) can parse all strings that are generated using grammar G.

S2: LR(1) can parse all strings that are generated using grammar G.

S2: LR(1) can parse all strings that are generated using grammar G.

- a)Only S1
- b)Only S2
- c)Both S1 and S2
- d)Neither S1 and S2

Correct answer is option 'D'. Can you explain this answer?

MANISH BAIS answered • 2 hours ago

The given grammar is ambiguous as there are two possible leftmost derivations for string "c".

First Leftmost Derivation

S → F

F → c

S → F

F → c

Second Leftmost Derivation

S → H

H → c

S → H

H → c

An Ambiguous grammar can neither be LL(1) nor LR(1)

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:

- 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.

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.

YAMUNA DEVI asked • 7 hours ago

A database table T1 has 2000 records and occupies 80 disk blocks. Another table T2 has 400 records and occupies 20 disk blocks. These two tables have to be joined as per a specified join condition that needs-to be evaluated for every pair of records from these two tables. The memory buffer space available can hold exactly one block of records for T1 and one block of records for T2 simultaneously at any point in time. No index is available on either table.

Q. If, instead of Nested-loop join, Block nested-loop join is used, again with the most appropriate choice of table in the outer loop, the reduction in number of block accesses required for reading the data will be

Q. If, instead of Nested-loop join, Block nested-loop join is used, again with the most appropriate choice of table in the outer loop, the reduction in number of block accesses required for reading the data will be

- a)0
- b)30400
- c)38400
- d)798400

Correct answer is option 'B'. Can you explain this answer?

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

P1()

{

C = B – 1;

B = 2*C;

}

{

C = B – 1;

B = 2*C;

}

P2()

{

D = 2 * B;

B = D - 1;

}

{

D = 2 * B;

B = D - 1;

}

The number of distinct values that B can possibly take after the execution is

- a)3
- b)2
- c)5
- d)4

Correct answer is option 'A'. Can you explain this answer?

ANKIT SINHA answered • 2 hours ago

There are following ways that concurrent processes can follow.

There are 3 different possible values of B: 2, 3 and 4.

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

Compute;

Wait(A);

Use R1;

Use R2;

Signal(B);

Wait(A);

Use R3;

Use R4;

Signal(B);

Wait(A);

Use R1;

Use R2;

Signal(B);

Wait(A);

Use R3;

Use R4;

Signal(B);

Compute;

Wait(B);

Use r1;

Signal(A);

Wait(B);

Use R2;

Use R3;

Signal(A);

Wait(B);

Use R4;

Signal(B);

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.

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.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________

- a)2
- b)3
- c)4
- d)5

Correct answer is option 'B'. Can you explain this answer?

NISHANT KUMAR answered • 2 hours ago

Below is NFA for the given regular expression (0 + 1)*(10)

Below is DFA for the same.

The intermediate code generated for the following syntax tree is:

- a)iac + cdb + - +
- b)iacb + cd uminus * - +
- c)iacb + cd * - +
- d)None of the above

Correct answer is option 'B'. Can you explain this answer?

Data Funda answered • 12 hours ago

In intermediate code generation second tome node vite will print

so ans B options is correct

so ans B options is correct

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.

Javed Ahmad asked • 10 hours ago

Which of the following is not true about comparison based sorting algorithms?

- a)The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
- b)Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
- c)Counting Sort is not a comparison based sorting algortihm
- d)Heap Sort is not a comparison based sorting algorithm

Correct answer is option 'D'. Can you explain this answer?

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.

Vaishnavi Kature asked • 10 hours ago

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

- a)Insertion Sort with time complexity O(kn)
- b)Heap Sort with time complexity O(nLogk)
- c)Quick Sort with time complexity O(kLogk)
- d)Merge Sort with time complexity O(kLogk)

Correct answer is option 'B'. Can you explain this answer?

In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

- a)x = 5 AND not(not(x = 5))
- b)x = 5 AND x> 4 and x < 6, where x is an integer
- c)x < 5 AND not (x = 5)
- d)None of the above

Correct answer is option 'C'. Can you explain this answer?

AYUSH TOMAR answered • 13 hours ago

For all values smaller than 5, x < 5 will always be true but x = 5 will be false.

Consider the following three table to store student enrollements in different courses.

Student(__EnrollNo__, Name)

Course(__CourseID__, Name)

EnrollMents(__EnrollNo, CourseID__)

Course(

EnrollMents(

- 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”).

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”.

(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 L
_{2}is context free. - b)Only L
_{2}and L_{3}are context free. - c)Only L
_{1}and L_{2}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.

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.

- 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.

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = kmod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?

- a)3
- b)4
- c)6
- d)7

Correct answer is option 'D'. Can you explain this answer?

VIKASH KUMAR answered • 13 hours ago

A given relation is known to be in third normal form. Select the statement which can be inferred from this

- a)All attributes contribute to the primary key.
- b)Each non-key attribute determine the primary key.
- c)Each non-key attribute is determine by the primary key.
- d)Every determinant is a candidate key.

Correct answer is option 'C'. Can you explain this answer?

AKHIL VO answered • 13 hours ago

A relation is in 3NF if for X →A

(i) X is a super key or candidate key

(ii) A is a prime attribute.

Hence, for A to be non-key attribute (non-prime attribute)

X must be satisfying (i)

(i) X is a super key or candidate key

(ii) A is a prime attribute.

Hence, for A to be non-key attribute (non-prime attribute)

X must be satisfying (i)

Vaishnavi Kature asked • 10 hours ago

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

- a)O(n^2 Logn)
- b)O(nLogn)
- c)O(n Logn Logn)
- d)none

Correct answer is option 'B'. Can you explain this answer?

Which of the following list represents the MVDs (Mean Value Dependencies), satisfied by a relation R(A, B, C) that has the following tuples: (a1, b1, c1),(a1, b1, c2), (a2, b1, c1), (a2, b1,c3).

- a)A —>—> B, B —> —> C. A —> —> BC, A B —> —>C , AC —> —> B, B —> —> A C ,BC—>—> A, C —>—> AB
- b)A—> —> B , A—> —> C, A—> —> BC , AB —> —> C, AC —> —> B, B —> —> AC, BC—> —> A, C —> —> A B
- c)B—> —> A, A —> —>C, A —> —> BC, A B —> —> C, AC —> —> B, B —> —> AC, BC—> —>A, C —> —> AB
- d)None of the above

Correct answer is option 'D'. Can you explain this answer?

DIVIJ NAGPAL answered • 13 hours ago

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 2^{x})

- a)power(2, n)
- b)power(2, n
^{2}) - c)power(2, (n
^{2}+ n)/2) - d)power(2, (n
^{2}- 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)

Which of the following is not O(n^2)?

- a)(15^10) * n + 12099
- b)n^1.98
- c)n^3 / (sqrt(n))
- d)(2^20) * n

Correct answer is option 'C'. Can you explain this answer?

AMAN RAJ answered • yesterday

The order of growth of option c is n^2.5 which is higher than n^2.

What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with **n** vertices?

- a)O(n^2logn)
- b)O(n^2logn)
- c)O(n^4)
- d)O(n^3)

Correct answer is option 'D'. Can you explain this answer?

NAVDEEP SINGH answered • yesterday

Floyd–Warshall algorithm uses three nested loops to calculate all pair shortest path. So, time complexity is O(n^3). Read here for more details.

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.

Sohi Jassu asked • 13 hours ago

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

- a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
- b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
- c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
- d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

Correct answer is option 'B'. Can you explain this answer?

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]

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.

----------------------------------------------

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.

What does the following C-statement declare?

int (*f) (int *);

int (*f) (int *);

- a)A function that takes an integer pointer as argument and returns an integer
- b)A function that takes an integer pointer as argument and returns an integer pointer
- c)A pointer to a function that takes an integer pointer as argument and returns an integer
- d)A function that takes an integer pointer as argument returns a function pointer

Correct answer is option 'C'. Can you explain this answer?

AKSHIT MALHOTRA answered • yesterday

int (*f) (int*);

return type int, (*f) is a pointer to a function the argument is (int*) an integer pointer So, int (*f) (int*) means a pointer to a function that takes an integer pointer as an argument and returns an integer.

return type int, (*f) is a pointer to a function the argument is (int*) an integer pointer So, int (*f) (int*) means a pointer to a function that takes an integer pointer as an argument and returns an integer.

Kashish Arora asked • 15 hours ago

Branch-scheme = (Branch - name, assets, branch- city)

Customer-scheme = (Customer-name, street, customer- city)

Deposit-scheme = (Branch-name, account-number, customer-name, balance)

Borrow-scheme = (Branch-name, loan-number, customer-name, amount)

Client-scheme = (Customer-name, banker-name)

Using relational algebra, the query that finds customers who have a balance of over 1000 is

Customer-scheme = (Customer-name, street, customer- city)

Deposit-scheme = (Branch-name, account-number, customer-name, balance)

Borrow-scheme = (Branch-name, loan-number, customer-name, amount)

Client-scheme = (Customer-name, banker-name)

Using relational algebra, the query that finds customers who have a balance of over 1000 is

- a)
- b)
- c)
- d)

Correct answer is option 'A'. Can you explain this answer?

What values of A, B, C and D satisfy the following simultaneous boolean equation?

1. A = 1. B = 0, C = 0, D = 1

2. A = 1, B = 1, C= 0, D = 0

3. A = 1, B = 0, C = 1, D = 1

4. A = 1, B = 0, C = 0, D = 0

2. A = 1, B = 1, C= 0, D = 0

3. A = 1, B = 0, C = 1, D = 1

4. A = 1, B = 0, C = 0, D = 0

- a)1 and 4
- b)2 and 3
- c)1 only
- d)None of these

Correct answer is option 'A'. Can you explain this answer?

AMISH KUMAR answered • yesterday

i.e. A must be 1 and B must be 0 From (ii) we have

i.e. C is also 0.

Putting the values of A, B and C in (iii)

Putting the values of A, B and C in (iii)

For, the above equation to be true D is independent.

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.

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.

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.

SHALU VERMA asked • 17 hours ago

Which one of the following statements is FALSE?

- a)Packet switching leads to better utilization of bandwidth resources than circuit switching
- b)Packet switching results in less variation in delay than circuit switching
- c)Packet switching requires more per-packet processing than circuit switching
- d)Packet switching can lead to reordering unlike in circuit switching

Correct answer is option 'B'. Can you explain this answer?

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.

JAGDEEP KUMAR asked • 19 hours ago

Which of the following languages is/are regular?

L1: {wxw^{R} ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} w^{R} is the reverse of string w

L2: {a^{n}b^{m} ⎪m ≠ n and m, n≥0

L3: {a^{p}b^{q}c^{r} ⎪ p, q, r ≥ 0}

L2: {a

L3: {a

- a)L1 and L3 only
- b)L2 only
- c)L2 and L3 only
- d)L3 only

Correct answer is option 'A'. Can you explain this answer?

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

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.

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.

Rasazna Kls asked • 19 hours ago

A priority queue can efficiently implemented using which of the following data structures? Assume that the number of insert and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost same.

- a)Array
- b)Linked List
- c)Heap Data Structures like Binary Heap, Fibonacci Heap
- d)None of the above

Correct answer is option 'C'. Can you explain this answer?

POOJA DAYA asked • 22 hours ago

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?

- a)N(logN base 3)
- b)N(logN base 2/3)
- c)N(logN base 1/3)
- d)N(logN base 3/2)

Correct answer is option 'D'. Can you explain this answer?

JYOTI DEVI asked • 23 hours ago

You want to check whether a given set of items is sorted. Which of the following sorting methods will be the most efficient if it is already is sorted order?

- a)Bubble sort
- b)Selection sort
- c)Insertion sort
- d)Merge sort

Correct answer is option 'A,C'. Can you explain this answer?

Nisi Gupta asked • 23 hours ago

Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500 KB, 300 KB, and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?

Correct answer is between '200 KB,300 KB'. Can you explain this answer?

ISHA DEVI asked • yesterday

The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X in this representation is

- a)2
^{-f}to 2^{i} - b)2
^{-f}to (2^{i}- 2^{-f}) - c)0 to 2
^{i} - d)0 to (2
^{i}- 2^{-f})

Correct answer is option 'D'. Can you explain this answer?

Sai Kumar asked • yesterday

Which of the following is true about Kruskal and Prim MST algorithms? Assume that Prim is implemented for adjacency list representation using Binary Heap and Kruskal is implemented using union by rank.

- a)Worst case time complexity of both algorithms is same.
- b)Worst case time complexity of Kruskal is better than Prim
- c)Worst case time complexity of Prim is better than Kruskal

Correct answer is option 'A'. Can you explain this answer?

POOJA THAKUR asked • yesterday

Consider the following 2 x 2 matrix A where two elements are unknown and are marked by ‘a’ and ‘b'. The eigenvalues of this matrix are -1 and 7. What are the values of ‘a’ and 'b'?

- a)a = 6, b = 4
- b)a = 4, b = 6
- c)a = 3, b = 5
- d)a = 5, b = 3

Correct answer is option 'D'. Can you explain this answer?

MONIKA MANKOTIA asked • yesterday

A 3000 km long trunk is used to transmit frames using a Go-Back-N protocol. The propagation speed is 6 jasec/ km and trunk data rate is 1.544 Mbps. We ignore the time taken to receive the bits in the acknowledgment. Frame size is 64 Bytes.

What is the maximum number of bits of the sequence number?

- a)5
- b)6
- c)7
- d)8

Correct answer is option 'C'. Can you explain this answer?

SUBHADIP KHAWAS asked • yesterday

If M is a square matrix with a zero determinant, which of the following assertion(S) is (are) correct?

S_{1}: Each row of M can be represented as a linear combination of the other rows.

S_{2}: Each column of M can be represented as a linear combination of the other columns.

S_{3}: MX = O has a nontrivial solution.

S_{4}: M has an inverse.

S

S

S

S

- a)S
_{3}and S_{2}only - b)S
_{1}and S_{4}only - c)S
_{1}and S_{3}only - d)S
_{1,}S_{2}and S_{3}only

Correct answer is option 'D'. Can you explain this answer?

Tarun Kumar asked • yesterday

The correct matching for the following pairs is:

(A) DMA I/O (1) High speed RAM

(B) Cache (2) Disk

(C) Interrupt I/O (3) Printer

(D) Condition Code Register (4) ALU

(A) DMA I/O (1) High speed RAM

(B) Cache (2) Disk

(C) Interrupt I/O (3) Printer

(D) Condition Code Register (4) ALU

- a)A-4 B-3 C-1 D-2
- b)A-2 B-1 C-3 D-4
- c)A-4 B-3 C-2 D-1
- d)A-2 B-3 C-4 D-1

Correct answer is option 'B'. Can you explain this answer?

Fetching relevant content for you

Ask a question