Dark Mode

Recent activity by dragonball

1 answer

1

Quick Sort
In Quicksort let n/7 th smallest element is chosen using an O(n2 ) algorithm as the pivot. Calculate the worst case time complexity of the algorithm.

commented in Algorithms Oct 31, 2020

3.2k views

1 answer

2

Self Doubt - Quick Sort
Consider the following inputs: 1) 2 2 2 2 2 2 2 2) 1 2 3 4 5 6 7 3) 7 6 5 4 3 2 1 In all three cases, the worst-case time complexity of quicksort is O(n2) My doubt is if I am taking the middle element as a pivot, ... ), right? Can someone explain how we are saying worst-case time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?

commented in Algorithms Oct 31, 2020

604 views

2 answers

3

Quick Sort
Suppose we have a O(nlogn) 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 ... quick sort. Average case time complexity of modified quick sort is same as that of original quick sort. None of the above

commented in Algorithms Oct 31, 2020

4.4k views

1 answer

4

loader/linker
Que. What is the component that is responsible for loading the initial value in the program counter for an application program before it starts running? a)linker b)loader c)Boot Module d)Compiler

commented in Operating System Jul 13, 2020

734 views

3 answers

5

RAM Chip
A RAM chip has 7 address line , 8 data lines and 2 chips select lines. Then the number of memory locations is ... a. 2^12 b.2^10 c.2^19 d.2^13 Plz describe with a proper diagram and significance of each lines.

answer selected in CO and Architecture Apr 25, 2020

4.1k views

1 answer

6

Relative Addressing Mode
A two- word instruction is stored in a location A. The operand part of instruction holds B. If the addressing mode is relative , the operand is available in location : A. A+B+2 B.A+B+1 C.B+1 D.A+B Explain with diagram.

answer selected in CO and Architecture Sep 15, 2019

2.9k views

1 answer

7

Hash Function
Which of the following is the least suitable hash function H(x) where X is some non negative integer ? 1. h(k) =k%n 2.h(k) =k*k %n 3.h(k)=(gcd(k+1,2k+2) +k ) %n Linear probing is used for collision resolution .

commented in DS Aug 4, 2018

11.1k views

2 answers

8

Slowness and Fastness of any algorithm
How the slowness and the fastness of any algorithm depends ? Is (n/logn) is slower than log(logn) ?

answer selected in Algorithms Aug 3, 2018

274 views

0 answers

9

TRUE or FALSE
Schedulers can be implementd using Stack ? TRUE or FALSE ?

commented in Operating System Aug 2, 2018

124 views

9 answers

10

GATE CSE 2018 | Question: GA-7
If $pqr \ne 0$ and $p^{-x}=\dfrac{1}{q},q^{-y}=\dfrac{1}{r},r^{-z}=\dfrac{1}{p},$ what is the value of the product $xyz$ ? $-1$ $\dfrac{1}{pqr}$ $1$ $pqr$

answered in Quantitative Aptitude Feb 4, 2018

5.6k views

11 answers

11

GATE CSE 2018 | Question: 1
Which one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$, where $a_n = 2n +3 \text{ for all } n=0, 1, 2, \dots$? $\frac{3}{(1-x)^2}$ $\frac{3x}{(1-x)^2}$ $\frac{2-x}{(1-x)^2}$ $\frac{3-x}{(1-x)^2}$

answer edited in Combinatory Feb 4, 2018

18.2k views

2 answers

12

How to construct compound Automata ? and find the no of states in minimal FA ?
Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN . Also find no of states in its minimal FA

commented in Theory of Computation Feb 1, 2018

2.2k views

2 answers

13

GATE CSE 1987 | Question: 1-xix
Study the following program written in a block-structured language: Var x, y:interger; procedure P(n:interger); begin x:=(n+2)/(n-3); end; procedure Q Var x, y:interger; begin x:=3; y:=4; P(y); Write(x) __(1) end; begin x:=7; y:=8; Q; Write(x); ... marked $(1)$ and $(2)$ in the program if the variables are statically scoped? $3, 6$ $6, 7$ $3, 7$ None of the above.

comment edited in Compiler Design Jan 30, 2018

5.5k views

4 answers

14

GATE CSE 2016 Set 1 | Question: 36
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a = 3; void n(x) { x = x * a; print (x); } void m(y) { a = 1 ; a = y - a; n(a); print (a); } void main () { m(a); } $6,2$ $6,6$ $4,2$ $4,4$

commented in Compiler Design Jan 29, 2018

19.4k views

2 answers

15

GATE CSE 2007 | Question: 78
Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ ... $S \rightarrow bAA$ Which of the following strings is generated by the grammar? $aaaabb$ $aabbbb$ $aabbab$ $abbbba$

commented in Compiler Design Jan 29, 2018

9.3k views

4 answers

16

GATE CSE 1997 | Question: 11
Consider the grammar $S \rightarrow bSe$ $S \rightarrow PQR$ $P \rightarrow bPc$ $P \rightarrow \varepsilon$ $Q \rightarrow cQd$ $Q \rightarrow \varepsilon$ $R \rightarrow dRe$ $R \rightarrow \varepsilon$ where $S, P, Q, R$ ... $i, j, k, m$? Find the smallest string that has two parse trees.

commented in Compiler Design Jan 29, 2018

5.1k views

2 answers

17

GATE CSE 2001 | Question: 13
Consider the following C program: void abc(char*s) { if(s[0]=='\0')return; abc(s+1); abc(s+1); printf("%c",s[0]); } main() { abc("123"); } What will be the output of the program? If $abc(s)$ is called with a null-terminated string $s$ of length $n$ characters (not counting the null ('\0') character), how many characters will be printed by $abc(s)$?

commented in Programming Jan 28, 2018

9.6k views

9 answers

18

GATE CSE 2006 | Question: 80
A CPU has a $32 KB$ direct mapped cache with $128$ byte-block size. Suppose A is two dimensional array of size $512 \times512$ with elements that occupy $8$-bytes each. Consider the following two C code segments, $P1$ and $P2$. P1: for (i=0; i<512; i++) { for (j=0; ... $P1$ be $M_{1}$and that for $P2$ be $M_{2}$. The value of $M_{1}$ is: $0$ $2048$ $16384$ $262144$

commented in CO and Architecture Jan 26, 2018

13.4k views

1 answer

19

GATE IT 2007 | Question: 39
Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS. $R1→ Loc, Loc→ R2 \quad ≡ R1→ R2, R1 → Loc$ $R1→ Loc, Loc→ R2 \quad ≡ R1→ R2$ ... RHS be the same as executing the LHS irrespective of the instructions that follow ? i and iii i and iv ii and iii ii and iv

commented in CO and Architecture Jan 26, 2018

4.8k views

4 answers

20

GATE CSE 1992 | Question: 01-vi
In an $11$-bit computer instruction format, the size of address field is $4$-bits. The computer uses expanding OP code technique and has $5$ two-address instructions and $32$ one-address instructions. The number of zero-address instructions it can support is ________

commented in CO and Architecture Jan 25, 2018

10.9k views

2 answers

21

CO Addressing
A computer has 32 bit instruction and 12 bit address . If there are 250 two address instructions , the no. of one -address instructions can be ..... Plz formulate a generic solution for this with diagram .

asked in CO and Architecture Jan 25, 2018

2.4k views

9 answers

22

GATE CSE 2017 Set 1 | Question: 51
Consider a $2$-way set associative cache with $256$ blocks and uses $\text{LRU}$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory ... $10$ times. The number of conflict misses experienced by the cache is _________ .

commented in CO and Architecture Jan 23, 2018

32.6k views

9 answers

23

GATE CSE 2015 Set 2 | Question: 52
$\text{Host A}$ sends a $\text{UDP}$ datagram containing $8880\text{ bytes}$ of user data to $\text{host B}$ over an $\text{Ethernet LAN}.$ Ethernet frames may carry data up to $1500\text{ bytes (i.e. MTU = 1500 bytes)}.$ Size of $\text{UDP}$ ... be the contents of offset field in the last fragment? $6$ and $925$ $6$ and $7400$ $7$ and $1110$ $7$ and $8880$

commented in Computer Networks Jan 20, 2018

18.6k views

3 answers

24

GATE CSE 1997 | Question: 2.3
Purpose of a start bit in $\text{RS-232}$ serial communication protocol is: to synchronize receiver for receiving every byte to synchronize receiver for receiving a sequence of bytes a parity bit to synchronize receiver for receiving the last byte

commented in Computer Networks Jan 20, 2018

3.3k views

6 answers

25

GATE CSE 2006 | Question: 68
Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. ... strictly fewer rows than Query$2$ There exist databases for which Query$4$ will encounter an integrity violation at runtime

commented in Databases Jan 19, 2018

15.4k views

4 answers

26

GATE IT 2007 | Question: 65
Consider a selection of the form $\sigma_{A\leq 100} (r)$, where $r$ is a relation with $1000$ tuples. Assume that the attribute values for $A$ among the tuples are uniformly distributed in the interval $[0, 500].$ Which one of the following options is the best estimate of the number of tuples returned by the given selection query ? $50$ $100$ $150$ $200$

commented in Databases Jan 18, 2018

9.3k views

18 answers

27

GATE CSE 2017 Set 2 | Question: 44
Two transactions $T_1$ and $T_2$ are given as $T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)$ $T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)$ where $r_i(V)$ denotes a $\textit{read}$ operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a ... by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and $T_2$ is ______

commented in Databases Jan 18, 2018

56.3k views

1 answer

28

EMAT in OS
In a system, with virtual memory the memory access time is 400 nanoseconds, if the page fault service time is double the memory access time, then what is the effective memory access time (in nanoseconds) for 50 percent of page faults? Solution 1: EMAT=P(PS) ... +1/2 * 800 =600 Which solution is more appropriate in GATE point of view if Numerical Type question is given without options .

comment edited in Operating System Jan 16, 2018

1.3k views

1 answer

29

Intermediate Code Generation

commented in Compiler Design Jan 14, 2018

1.1k views

0 answers

30

commented in Compiler Design Jan 14, 2018

372 views