Recent activity by Genius / GATE Overflow for GATE CSE

6 answers

1

GATE CSE 2008 | Question: 46
You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm ... $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ None of the above, as the tree cannot be uniquely determined

You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P...

39.2k views

commented Jun 29, 2023

2 answers

2

GATE CSE 2000 | Question: 21
(a) Suppose you are given an empty $B^+$ tree where each node (leaf and internal) can store up to $5$ key values. Suppose values $1, 2,\ldots 10$ are inserted, in order, into the tree. Show the tree pictorially after $6$ insertions, and ... what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).

(a) Suppose you are given an empty $B^+$ tree where each node (leaf and internal) can store up to $5$ key values. Suppose values $1, 2,\ldots 10$ are inserted, in order, ...

3.9k views

commented Jun 2, 2023

4 answers

3

GATE CSE 2021 Set 2 | Question: 48
Consider a three-level page table to translate a $39-$bit virtual address to a physical address as shown below: The page size is $\text{4 KB} \;(1\text{KB}=2^{10}$ bytes$)$ and page table entry size at every level is $8$ bytes. A ... $P$ across all levels is _________ $\text{KB}$.

Consider a three-level page table to translate a $39-$bit virtual address to a physical address as shown below:The page size is $\text{4 KB} \;(1\text{KB}=2^{10}$ bytes$)...

28.8k views

commented Apr 20, 2023

1 answer

4

GO Classes 2023 | IIITH Mock Test 1 | Question: 63
The arithmetic mean of five different natural numbers is $12$. The largest possible value among the numbers is $12$ $40$ $50$ $60$

The arithmetic mean of five different natural numbers is $12$. The largest possible value among the numbers is$12$ $40$ $50$ $60$

776 views

answered Apr 16, 2023

11 answers

5

GATE IT 2005 | Question: 41
Given below is a program which when executed spawns two concurrent processes : semaphore $X : = 0 ;$ /* Process now forks into concurrent processes $P1$ & $P2$ ... (II) are true. (I) is true but (II) is false. (II) is true but (I) is false Both (I) and (II) are false

Given below is a program which when executed spawns two concurrent processes :semaphore $X : = 0 ;$/* Process now forks into concurrent processes $P1$ & $P2$ */$\begin{ar...

24.1k views

commented Apr 15, 2023

10 answers

6

GATE CSE 2010 | Question: 39
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$

Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular express...

22.4k views

commented Apr 15, 2023

3 answers

7

GATE IT 2006 | Question: 31
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?$\{a^nb^nc^n \mid n ≥ 0\}$$\{a^lb^mc^n \mid ...

18.1k views

commented Mar 12, 2023

3 answers

8

NPTEL Assignment Question
Suppose there are k sorted lists (decreasing order) with n/k elements in each list. What is the time complexity to merge them into one single sorted list. Hint: Maintain a heap of k elements. Think which k elements to choose. A. O(nlogk) B. O(n) C. O(nk) D. O(nlogn)

Suppose there are k sorted lists (decreasing order) with n/k elements in each list.What is the time complexity to merge them into one single sorted list.Hint: Maintain a ...

734 views

commented Mar 5, 2023

2 answers

9

Peter Linz Edition 4 Exercise 3.1 Question 12 (Page No. 76)
Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

491 views

answered Mar 4, 2023

8 answers

10

GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$

34.4k views

commented Feb 28, 2023

2 answers

11

GATE CSE 1988 | Question: 15
Consider the DFA $M$ and NFA $M_{2}$ as defined below. Let the language accepted by machine $M$ be $L$. What language machine $M_{2}$ accepts, if $F2=A?$ $F2=B?$ $F2=C?$ $F2=D?$ $M=(Q, \Sigma, \delta, q_0, F)$ $M_{2}=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p,q \in Q; r \in F\}$

Consider the DFA $M$ and NFA $M_{2}$ as defined below. Let the language accepted by machine $M$ be $L$. What language machine $M_{2}$ accepts, if$F2=A?$$F2=B?$$F2=C?$$...

2.9k views

answered Feb 26, 2023

1 answer

12

Michael Sipser Edition 3 Exercise 1 Question 12 (Page No. 85)
Let $D = \{w \mid w $ contains an even number of a’s and an odd number of b’s and does not contain the substring $ab\}.$ Give a $\text{DFA}$ with five states that recognizes $\text{D}$ and a regular expression that generates $\text{D.}$ $($Suggestion: Describe $D$ more simply$.)$

Let $D = \{w \mid w $ contains an even number of a’s and an odd number of b’s and does not contain the substring $ab\}.$ Give a $\text{DFA}$ with five states that rec...

1.5k views

commented Feb 25, 2023

2 answers

13

GATE CSE 2023 | Question: 3
Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf{DLLdel}$ be another function that deletes a node in a doubly-linked list given a pointer to the node ... $\textsf{DLLdel}$ are $O(1)$ $\textsf{SLLdel}$ is $O(n)$ and $\textsf{DLLdel}$ is $O(1)$

Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf...

10.6k views

commented Feb 15, 2023

3 answers

14

GATE CSE 2023 | Question: 2
Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap? $23,17,10,6,13,14,1,5,7,12$ $23,17,14,7,13,10,1,5,6,12$ $23,17,14,6,13,10,1,5,7,15$ $23,14,17,1,10,13,16,12,7,5$

Which one of the following sequences when stored in an array at locations $A , \ldots, A[10]$ forms a max-heap?$23,17,10,6,13,14,1,5,7,12$$23,17,14,7,13,10,1,5,6,12$$23,1...

6.8k views

commented Feb 15, 2023

0 answers

15

Isi Kolkata 2022
Prove or disprove the following statements: (i) L1 = {0^i1^j | i, j ∈ N} is a regular language. (ii) L2 = {0^n1^n | n ∈ N} is a regular language. (iii) For x ∈ {0, 1}*, R(x) denotes the string obtained by reversing the string x. C(x) denotes the string ... 0 in the string x. L3 = {x ∈ {0, 1}* | x = R (C (x))} is a regular language. How to solve this in subjective way..

Prove or disprove the following statements:(i) L1 = {0^i1^j | i, j ∈ N} is a regular language.(ii) L2 = {0^n1^n | n ∈ N} is a regular language.(iii) For x ∈ {0, 1}*...

560 views

commented Feb 8, 2023

8 answers

16

GATE CSE 2016 Set 1 | Question: 14
Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? $P$: Minimum spanning tree of $G$ does not change. $Q$: Shortest path between any pair of vertices does not change. $P$ only $Q$ only Neither $P$ nor $Q$ Both $P$ and $Q$

Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following sta...

22.7k views

commented Jan 17, 2023

3 answers

17

GATE CSE 2018 | Question: 10
Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is $M$ units if the corresponding memory page is available in memory, and $D$ units if the memory access causes a page fault. It has been experimentally measured that the average ... $(X-M) / D-M)$ $(D-X) / D-M)$ $(X-M) / D-X)$

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is $M$ units if the corresponding memory p...

10.6k views

answered Jan 16, 2023

4 answers

18

GATE CSE 2021 Set 2 | Question: 33
A bag has $r$ red balls and $b$ black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is placed back into the bag along with another ball of the same colour. Note that the number of ...

A bag has $r$ red balls and $b$ black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and ...

10.9k views

commented Jan 6, 2023

2 answers

19

GO Classes Test Series 2023 | Linear Algebra | Test | Question: 10
What could be the possible values of $\operatorname{rank}(\mathrm{A})$ as "$a$" varies: $ A=\left[\begin{array}{ccc} 1 & 2 & a\\ -2 & 4 a & 2\\ a & -2 & 1 \end{array}\right] $ For some value ... $a$, rank could be $1$ For some value of $a$, rank could be $2$ For some value of $a$, rank could be $3$

What could be the possible values of $\operatorname{rank}(\mathrm{A})$ as "$a$" varies:$$A=\left[\begin{array}{ccc}1 & 2 & a\\-2 & 4 a & 2\\a & -2 & 1\end{array}\right]$$...

386 views

commented Jan 5, 2023

4 answers

20

GATE CSE 2014 Set 2 | Question: 32
Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts ... slice of $50$ milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.

Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU m...

12.3k views

commented Nov 16, 2022

5 answers

21

GATE CSE 2021 Set 2 | Question: 47
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three...

12.4k views

answered Oct 31, 2022

4 answers

22

GATE CSE 2021 Set 1 | Question: 27
The following relation records the age of $500$ employees of a company, where $empNo$ (indicating the employee number) is the key: $empAge(\underline{empNo},age)$ ... Employee numbers of all employees whose age is not the minimum Employee numbers of all employees whose age is the minimum

The following relation records the age of $500$ employees of a company, where $empNo$ (indicating the employee number) is the key:$$empAge(\underline{empNo},age)$$Conside...

7.1k views

answered Oct 31, 2022

3 answers

23

GATE CSE 2008 | Question: 66
A process executes the following code for(i=0; i<n; i++) fork(); The total number of child processes created is $n$ $2^n-1$ $2^n$ $2^{n+1} - 1$

A process executes the following codefor(i=0; i<n; i++) fork();The total number of child processes created is$n$$2^n-1$$2^n$$2^{n+1} - 1$

17.2k views

commented Oct 19, 2022

6 answers

24

GATE CSE 2021 Set 2 | Question: 17
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________

Consider the following deterministic finite automaton $\text{(DFA)}$The number of strings of length $8$ accepted by the above automaton is ___________

9.5k views

answered Oct 15, 2022

3 answers

25

GATE CSE 1997 | Question: 21
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where $L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$ $L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$

Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where$L^P = \left\{s \mid ss' ...

5.3k views

commented Oct 12, 2022

1 answer

26

GATE CSE 1996 | Question: 12
Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively. Display the transition diagram for a machine that recognizes $L_1.L_2$, obtained from transition diagrams for $M_1$ ... $\varepsilon$ transitions and no new states. (Final states are enclosed in double circles).

Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively.Display the transition diagram fo...

8.5k views

commented Oct 12, 2022

1 answer

27

Programming Quiz
Which one of the following features is supported by 𝐶 ++ but not by JAVA ? (a) Encapsulation (b) Multiple inheritance (c) Concurrency (d) Garbage collection

Which one of the following features is supported by 𝐶 ++ but not by JAVA ?(a) Encapsulation(b) Multiple inheritance(c) Concurrency(d) Garbage collection

1.0k views

answered Oct 8, 2022

2 answers

28

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 13
Consider two statements below - $\text{S1}:$ For all positive $f(n), f(n) + o(f(n)) = \theta(f(n)).$ $\text{S2}:$ For all positive $f(n), g(n)$ and $h(n),$ if $f(n) = O(g(n))$ ... $\text{S1}$ is True but $\text{S2}$ is False. $\text{S2}$ is True but $\text{S1}$ is False. Both are True. Both are False.

Consider two statements below -$\text{S1}:$ For all positive $f(n), f(n) + o(f(n)) = \theta(f(n)).$$\text{S2}:$ For all positive $f(n), g(n)$ and $h(n),$ if $f(n) = O(g(n...

1.6k views

answered Aug 17, 2022

3 answers

29

GO Classes Test Series 2024 | Discrete Mathematics | Test 4 | Question: 11
Consider the set of $4$-digit positive integers. How many of them are even and have distinct digits?

Consider the set of $4$-digit positive integers. How many of them are even and have distinct digits?

303 views

commented Aug 10, 2022

3 answers

30

GO Classes Test Series 2024 | Discrete Mathematics | Test 4 | Question: 12
Consider the set of $4$-digit positive integers. How many of them are odd and don’t have the property that the sum of their digits is even?

Consider the set of $4$-digit positive integers. How many of them are odd and don’t have the property that the sum of their digits is even?

504 views

answered Aug 7, 2022

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true