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}}}$$

Most viewed questions in Algorithms

1 votes

1 answer

1801

Test algo

Deepalitrapti

834 views

Deepalitrapti asked Sep 20, 2018

2 votes

1 answer

1802

#HeapSort
What is the worst case time complexity of finding a element in max heap tree ? Explain.

What is the worst case time complexity of finding a element in max heap tree ?Explain.

S Harika

834 views

S Harika asked Apr 1, 2017

0 votes

1 answer

1803

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

833 views

ryandany07 asked Aug 18, 2022

1 votes

0 answers

1804

MadeEasy Test Series 2015: Algorithms - Graph Algorithms
Here i have option III is doubt.how option III always correct.one counter example is if i choose a tree where s is root node and v1& v2 are its child node then above question property i.e the vertices V1 and V2 that are simultaneously ... from vertex s in a digraph is satisfies.but there is no any path from v1 to v2 or from v2 to v1.

Here i have option III is doubt.how option III always correct.one counter example is if i choose a tree where s is root node and v1& v2 are its child node then above ques...

dileswar sahu

833 views

dileswar sahu asked Jul 19, 2016

0 votes

2 answers

1805

what is the divide and conquer recurrence that would arise for the problem
suppose you are given n bit integers asuming for common sense n as power of 2 .it is required to multiply them using divide and conquer method .what is the divide and conquer recurrence that would arise for the problem a) T(n)=4T(n/2)+c b) a) T(n)=2T(n/2)+n c) a) T(n)=4T(n/2)+n2 d) a) T(n)=4T(n)+n

suppose you are given n bit integers asuming for common sense n as power of 2 .it is required to multiply them using divide and conquer method .what is the divide and con...

ajit

830 views

ajit asked Sep 7, 2015

2 votes

1 answer

1806

NIELIT Scientific Assistant A 2020 November: 88
The given array is $\text{arr={1, 2, 4, 3}}$. Bubble sort is used to sort the array elements. How many passes will be done to sort the array? $4$ $2$ $1$ $3$

The given array is $\text{arr={1, 2, 4, 3}}$. Bubble sort is used to sort the array elements. How many passes will be done to sort the array?$4$$2$$1$$3$

gatecse

828 views

gatecse asked Dec 9, 2020

0 votes

1 answer

1807

ACE Algorithms volume 2 Divede and Conquer Q 11
Given two sorted double linked list L1 and L2 of n elements each, which of the following are true? (A) L1 and L2 can be merged into single sorted list in Θ(n) time. (B) L1 and L2 can be merged into single sorted list in Θ(1) time. ( ... merged into single sorted list in Θ(nlogn) time. (D) L1 and L2 can be merged into single sorted list in Θ(n2) time.

Given two sorted double linked list L1 and L2 of n elements each, which of the following are true?(A) L1 and L2 can be merged into single sorted list in Θ(n) time.(B) L1...

JAYKISHAN

828 views

JAYKISHAN asked Jul 5, 2018

0 votes

2 answers

1808

Made easy test

saumya mishra

828 views

saumya mishra asked May 30, 2018

3 votes

0 answers

1809

cormen
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by giving a counter example. I'm more interested in the converse. Please explain in detail.

Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by ...

Warlock lord

828 views

Warlock lord asked Sep 9, 2017

2 votes

1 answer

1810

Solve recurrence using Master theorem
$T(a)=0 \hspace{0.2cm} if \hspace{0.2cm} a=1$ $T(a)=2T(a/2) + ak \hspace{0.2cm} if \hspace{0.2cm} a=2^{p}, p>0$ where $a=\frac{n}{k}$ Answer: $\Theta (n \log (\frac{n}{k}))$, This is while (n/k) is power of 2. How can I solve it using master theorem?

$T(a)=0 \hspace{0.2cm} if \hspace{0.2cm} a=1$$T(a)=2T(a/2) + ak \hspace{0.2cm} if \hspace{0.2cm} a=2^{p}, p>0$where $a=\frac{n}{k}$Answer: $\Theta (n \log (\frac{n}{k}))$...

SomnathKayal

828 views

SomnathKayal asked Apr 8, 2016

0 votes

0 answers

1811

No of subsequence
I understand that number of subsequences for a string of length n is 2^n when we don’t have any repetition. What is the number of “unique” subsequence when we have repetitions. As in the string : aabbbccddd

I understand that number of subsequences for a string of length n is 2^n when we don’t have any repetition.What is the number of “unique” subsequence when we have r...

shaz

827 views

shaz asked Jan 8, 2019

0 votes

1 answer

1812

cormen
prove that if(n)=o(g(n)) if and only if g(n)=Ώ(f(n))? it comes under transitive property

prove that if(n)=o(g(n)) if and only if g(n)=Ώ(f(n))? it comes under transitive property

Shashank Kumar Mishr

826 views

Shashank Kumar Mishr asked Mar 7, 2017

0 votes

2 answers

1813

Problem on DFS
Answer given: C Please explain

Answer given: CPlease explain

shikharV

825 views

shikharV asked Nov 15, 2015

1 votes

2 answers

1814

TIme Complexity Algo
for(i=1 to n) { if(n mod i==0) { for(int j=1 to n) printf(j); } }

for(i=1 to n) { if(n mod i==0) { for(int j=1 to n) printf(j); } }

rahul sharma 5

824 views

rahul sharma 5 asked Dec 16, 2016

2 votes

0 answers

1815

Algorithm :- Detect Cycle in a graph
Write $O(n)$ time algorithm to find any cycles in a graph. Print NONE otherwise

Write $O(n)$ time algorithm to find any cycles in a graph. Print NONE otherwise

rahul sharma 5

823 views

rahul sharma 5 asked Apr 5, 2018

0 votes

2 answers

1816

Karumanchi

aditi19

822 views

aditi19 asked Nov 4, 2018

0 votes

1 answer

1817

Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)
Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?

Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search...

akash.dinkar12

821 views

akash.dinkar12 asked Jun 26, 2019

0 votes

0 answers

1818

A is polynomially reducible to B
Let there be two problems $A$ and $B$ It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomial reduction is carried out in time of $O(n).$The problem $B$ can be solved in $O(n^{3})$ time. what is the time taken to solve problem $'A'?$ $A)O(n)$ $A)O(n^{3})$ $A)O(2^{n})$ $D)$None of these

Let there be two problems $A$ and $B$It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomialreduction is carried out in time of $O(n).$The...

Lakshman Bhaiya

820 views

Lakshman Bhaiya asked Nov 3, 2018

3 votes

2 answers

1819

GATE Overflow | Algorithms | Test 1 | Question: 22
Consider the below statements: Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem. 1 is FALSE 2 is TRUE 1 is TRUE 2 is FALSE Both 1 and 2 are TRUE Both 1 and 2 are FALSE

Consider the below statements:Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.Adding a constant to every e...

Bikram

820 views

Bikram asked Oct 4, 2016

1 votes

3 answers

1820

#selfdoubt
Find the time complexity? for(i=1;i<=n;i++) { for(j=1;j<i;j++) { if((i℅j)==0) { for (k=1;k<=n;k++) { sum+=k; } } } }

Find the time complexity?for(i=1;i<=n;i++) { for(j=1;j<i;j++) { if((i℅j)==0) { for (k=1;k<=n;k++) { sum+=k; } } } }

Naveen Kumar 3

819 views

Naveen Kumar 3 asked Jun 20, 2018

Page:

« prev
1
...
86
87
88
89
90
91
92
93
94
95
96
...
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