Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design techniques: Greedy, Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning trees, Shortest paths.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 2 &3&2&3&2&0&2&2&3&3&0&2.2&3
\\\hline\textbf{2 Marks Count} & 2 &3&4&4&2&4&2&3&2&3&2&2.9&4
\\\hline\textbf{Total Marks} & 6 &9&10&11&6&8&6&8&7&9&\bf{6}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Recent questions in Algorithms

2 votes

0 answers

221

I-Gate Question
Consider the following algorithm, Dosomething( x, n) { m= n, temp= 1,z= x; while(m>0) do { while((m mod z)=0) do { m= Floor(m/2); z=z^2; } m = m-1, temp= temp* z; } return temp; } The complexity of above algorithm is Theta(log n) Theta(n log n) Theta(n^2) Theta(n)

Consider the following algorithm,Dosomething( x, n){m= n, temp= 1,z= x;while(m>0) do{while((m mod z)=0) do{m= Floor(m/2);z=z^2;}m = m-1, temp= temp* z;}return temp;}The c...

loki2023

367 views

loki2023 asked Aug 23, 2022

0 votes

1 answer

222

Dynamic Programming
int max(int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that can be // put in a knapsack of capacity W int knapSack(int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // If ... , wt, val, n - 1), knapSack(W, wt, val, n - 1)); } This statement implies that the max value return by the two different recursive problems right?

int max(int a, int b) { return (a b) ? a : b; }// Returns the maximum value that can be// put in a knapsack of capacity Wint knapSack(int W, int wt[], int val[], int n){...

ryandany07

842 views

ryandany07 asked Aug 18, 2022

0 votes

2 answers

223

Madeeasy Test Series
A hash table of size 10 using open addressing with linear probing and hash function is h(k)= (k)mod10 , where k is key value , initially table is empty . Following keys are inserted into table in given order . 44,87,43,68,30,20,67 How many number of probes required to insert 17 in table after inserting above keys?

A hash table of size 10 using open addressing with linear probing and hash function is h(k)= (k)mod10 , where k is key value , initially table is empty . Following keys a...

Manisha Jaishwal

998 views

Manisha Jaishwal asked Jul 25, 2022

0 votes

1 answer

224

NIELIT 2021 Dec Scientist B - Section B: 71
The number of operations in matrix multiplication $\text{M1, M2, M3, M4}$ and $\text{M5}$ of sizes $5\times 10, 10\times 100, 100\times 2, 2\times 20$ and $20\times 50$ respectively will be: $5830$ $4600$ $6900$ $12890$

The number of operations in matrix multiplication $\text{M1, M2, M3, M4}$ and $\text{M5}$ of sizes $5\times 10, 10\times 100, 100\times 2, 2\times 20$ and $20\times 50$ r...

admin

450 views

admin asked Jul 21, 2022

1 votes

1 answer

225

#doubt
BigO notation of T(n)=T(n-1)+ √n ; n>=1 =0. ; Otherwise

BigO notation ofT(n)=T(n-1)+ √n ; n>=1 =0. ; Otherwise

Subbu.

479 views

Subbu. asked Jul 18, 2022

0 votes

1 answer

226

#Dfs And Bfs
Please list the problems where BFS alone can do and DFS alone can do and both can do??

Please list the problems where BFS alone can do and DFS alone can do and both can do??

Subbu.

348 views

Subbu. asked Jul 16, 2022

0 votes

0 answers

227

Iteration Functions (Cormen)
Iterative functions: f(n)= n/logn c=2 What is f*(n) ? How to solve this question?

Iterative functions:f(n)= n/lognc=2What is f*(n) ?How to solve this question?

mb14

312 views

mb14 asked Jul 6, 2022

0 votes

0 answers

228

what is the running time of the following iterative algorithm? b) It is possible to talk about the best, average and worst running times for this algorithm. Why?

what is the running time of the following iterative algorithm?b) It is possible to talk about the best, average and worst running times for this algorithm. Why? pseudo co...

usdid

504 views

usdid asked Jul 2, 2022

0 votes

0 answers

229

please tell me whether the Branch & Bound concept and NP Hard & NP Complete concepts are there for gate or not in algorithms?

With in this less time I have to Complete many Subjects So,please tell me wether NP Hard& NP Complete concept in algorithm is there for gate or not?

Vijay_Ram

266 views

Vijay_Ram asked Jul 2, 2022

0 votes

1 answer

230

Shortest path in DAG and Travelling salesman problem are in DSA gate syllabus??

Vink7389

203 views

Vink7389 asked Jun 27, 2022

2 votes

1 answer

231

Recurrence Tree Method
T(n) = 5T(n/3) + T(2n/3) + 1. My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.

T(n) = 5T(n/3) + T(2n/3) + 1.My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.

yuyutsu

632 views

yuyutsu asked Jun 22, 2022

3 votes

1 answer

232

GO Classes Test Series 2023 | Algorithms | Test 2 | Question: 8
Let $T(n)$ be $ T(n)=T(n-1)+n^{2} $$ T(1) = 1 $ What will be asymptotic bound on $T(n) ?$ $\Theta\left(\mathrm{n}^ 2\right)$ $\Theta\left(n^ 3\right)$ $\Theta\left(n^ 4\right)$ $\Theta\left(n^ 2 \log n\right)$

Let $T(n)$ be$$T(n)=T(n-1)+n^{2} $$$$T(1) = 1$$What will be asymptotic bound on $T(n) ?$$\Theta\left(\mathrm{n}^ 2\right)$$\Theta\left(n^ 3\right)$$\Theta\left(n^ 4\right...

GO Classes

298 views

GO Classes asked Jun 19, 2022

3 votes

1 answer

233

GO Classes Test Series 2023 | Algorithms | Test 2 | Question: 12
Let $T(n)$ be $ T(n)=T(\sqrt{n})+1 $ What will be asymptotic bound on $T(n)$? $\Theta(\log n)$ $\Theta(\sqrt{n})$ $\Theta(\log \log n)$ $\Theta\left((\log n)^ 2\right)$

Let $T(n)$ be$$T(n)=T(\sqrt{n})+1$$What will be asymptotic bound on $T(n)$?$\Theta(\log n)$$\Theta(\sqrt{n})$$\Theta(\log \log n)$$\Theta\left((\log n)^ 2\right)$

GO Classes

222 views

GO Classes asked Jun 19, 2022

5 votes

1 answer

234

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 2
If we have an array of size $\mathrm{N}$ with only $3$ different values for its elements, what is the probability that the first partition results in a completely sorted array? Assume there are an equal number of each element in the array. $1 / 2$ $1 / 3$ $1 / 4$ $2 / 3$

If we have an array of size $\mathrm{N}$ with only $3$ different values for its elements, what is the probability that the first partition results in a completely sorted ...

GO Classes

513 views

GO Classes asked Jun 13, 2022

8 votes

3 answers

235

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 9
Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In other words, find the largest element, the second largest element, the ... the subarray) $\Theta(\log n)$ $\Theta(n)$ $\Theta(n \log n)$ $\Theta\left(n^{2}\right)$

Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In ot...

GO Classes

799 views

GO Classes asked Jun 13, 2022

3 votes

2 answers

236

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 13
Consider the following recurrence equation $T(n)=A n^{2}+B n+C$. We determine the constants $A, B, C$ using the following recursive equation. Assume $n$ is a power of $2.$ $ T(n)= \begin{cases}4 T(n / 2)+n+6, & n \geq 2 \\ 2, & n=1\end{cases} $ What will be the value of $A+B+C ?$ $1$ $2$ $3$ $4$

Consider the following recurrence equation $T(n)=A n^{2}+B n+C$.We determine the constants $A, B, C$ using the following recursive equation.Assume $n$ is a power of $2.$$...

GO Classes

291 views

GO Classes asked Jun 13, 2022

5 votes

1 answer

237

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 17
Consider the following pseudo-code of function fun(). fun() takes k arrays as input and return merged array of all. Assume that merge function takes $O(p+q)$ where $p$ is length of first input array to merge and $q$ is length of second input array to merge. In the ... $T(k)=O(n k \log k)$ $T(k)=O(n k \log n)$ $T(k)=O(n \log nk )$

Consider the following pseudo-code of function fun(). fun() takes k arrays as input and return merged array of all. Assume that merge function takes $O(p+q)$ where $p$ is...

GO Classes

298 views

GO Classes asked Jun 13, 2022

4 votes

1 answer

238

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 19
You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$ ... complexity of best divide and conquer algorithm? $\Theta(\log n)$ $\Theta(n \log n)$ $\Theta(n)$ $\Theta\left(n^{2}\right)$

You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$” bit-array. This means that for some (unknown) in...

GO Classes

249 views

GO Classes asked Jun 13, 2022

5 votes

1 answer

239

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 20
Suppose that a randomized algorithm succeeds with probability $p$ (with $0<p<1).$ Let $n$ be independent trials we need to run the algorithm to ensure that, with probability at least $1-\epsilon$, at least one trial succeeds. Which of the ... $1-p^{n} \leq \epsilon$ $p^{n} \leq \epsilon$ $p^{n} \leq \epsilon$

Suppose that a randomized algorithm succeeds with probability $p$ (with $0<p<1).$ Let $n$ be independent trials we need to run the algorithm to ensure that, with probab...

GO Classes

236 views

GO Classes asked Jun 13, 2022

1 votes

1 answer

240

Solve equation using master theorem T(n) = 8T(n/2) + 3n^2
I can't figure out how to proceed and which case it's falling under after calculating h(n)

I can't figure out how to proceed and which case it's falling under after calculating h(n)

ItzDc

3.0k views

ItzDc asked Jun 3, 2022

Page:

« prev
1
...
7
8
9
10
11
12
13
14
15
16
17
...
242
next »

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