Recent questions tagged algorithms - GATE CSE Doubts

0 votes

1 answer

Uppcl ae2019
In an RSA cryptosystem a participant use two prime number p=3 and q=11 to generate his public key and private key.If the private key is 7,the how will the text COMPUTER be encrypted using public key? 1.27 9 19 4 12 4 25 27 2.9 27 4 25 21 8 26 24 3.27 9 19 4 21 8 26 24 4.9 27 4 25 12 4 25 27

asked Nov 8 in Computer Networks by amit166 (30 points) | 16 views

0 votes

0 answers

Algorithms-DP (Ref: Gatebook Test series & https://www.cs.umd.edu/class/fall2014/cmsc351/HW/hw4-solutions.pdf)

asked Nov 6 in Algorithms by Kushagra गुप्ता (102 points) | 9 views

0 votes

1 answer

Introduction to algorithms(Cormen)-2e-Chapter:15-DP

asked Nov 4 in Algorithms by Kushagra गुप्ता (102 points) | 34 views

0 votes

0 answers

Applied Gate Test series
Find the time complexity of codes below – for(i=1;i<n*n*n*;i*=n) { for(j=0;j<n;j+=2) { for(k=1;k<n;k*=3) { //constant; } } } for(i=0;i<n;i++) { if(i mod 2 ==0) { for(j=i;j<n;j++) { if(i%2==0 && j%2==0) printf("Gate 2020"); } } }

asked Nov 3 in Algorithms by MRINMOY_HALDER (34 points) | 31 views

0 votes

0 answers

Made easy Algorithm book
Suppose that you are running Dijkstra’s Algorithm on the edge-weighted digraph below starting from vertex A. Vertex Distance Parent A 0 NULL B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What is the possible value of expression x+y?

asked Nov 1 in Algorithms by Akash Papnai (6 points) | 8 views

0 votes

1 answer

Find number of Minimum cost spanning tree possible? (MadeEasy Test Series)

asked Oct 19 in Algorithms by luc_Bloodstone (14 points) | 41 views

0 votes

1 answer

#Self Doubt Huffman Coding!
Hello all, I've this trivial doubt in Huffman coding algorithms questions - Mostly there's a question of type - What is the min expected length of the message? Now my doubt is in some questions - after finding expected length of message = no of bits ... t figure out in which case one has to divide and in which case not to divide with total number of characters? Thank you

asked Oct 14 in Algorithms by iarnav (71 points) | 24 views

0 votes

1 answer

Deletion of an element from Heap
The best time required to delete an element x,if present, in a min-heapof n elements is O(logn) O(n) O(n logn) None of these

asked Oct 13 in Algorithms by Shivateja MST (45 points) | 21 views

0 votes

1 answer

Difference between logarithmic notations
Can any one please tell what is difference between (log^2)n ,(logn)^2 and loglogn? Are these equal?

asked Oct 12 in Algorithms by Shivateja MST (45 points) | 30 views

0 votes

0 answers

geekforgeeks
int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } my doubt is an inner loop (J) is depend on i variable which is run n times. now how to evaluate the inner loop. please explain in details how TC is calculated.

asked Oct 10 in Algorithms by Hira Thakur (8 points) | 9 views

0 votes

1 answer

MadeEasy Workbook, DRDO 2008
Consider a sequence A of length n which is sorted except for one item that appears out of order.Which of the following can sort the sequence in O(n) time? (a) Heap sort (b) Quick sort (c) Merge sort (d) Insertion sort

asked Oct 9 in Algorithms by Ansaaa24 (8 points) | 24 views

0 votes

1 answer

Algorithm-self doubt(recurrence)
How to solve recurrence relation $T(n)=O(n)+2T(4n/5)$ Thank-you

asked Oct 9 in Algorithms by Ekta07_GATE (22 points) | 15 views

0 votes

0 answers

Self Doubt - Selection Sort Minimum Number of Swaps?

asked Oct 5 in Algorithms by iarnav (71 points) | 17 views

0 votes

0 answers

#Algorithms Sorting TIFR 2010 Self Doubt
Please this question - https://gateoverflow.in/19036/tifr2010-b-27 Someone students are saying Answer D) is correct and that also makes sense as they provided the counter example to prove that, but best answer says C. So, does Insertion sort on ... sequence ordering can make n(n-1)/2 comparisons? Also, it's not coming up anywhere on Google. Kindly help!

asked Oct 1 in Algorithms by iarnav (71 points) | 14 views

0 votes

0 answers

Self Doubt - Minimum number of swaps to sort an array.

asked Sep 27 in Algorithms by iarnav (71 points) | 30 views

0 votes

0 answers

#Algortihms (GeeksforGeeks) Self Doubt - Search an element in an unsorted array using minimum number of comparisons?

asked Sep 27 in Algorithms by iarnav (71 points) | 16 views

+1 vote

1 answer

Algorithm-ACE Test
You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements.The elements in a given subsequence are all smaller than the elements in succeeding subsequences and larger than all elements in preceding subsequence.Thus all that ... varient of sorting problem is A)$\Omega(n \log k)$ B)$\Omega(k \log n)$ C)$\Omega(n)$

asked Sep 26 in Algorithms by srestha (428 points) | 44 views

0 votes

0 answers

Algorithm :Virtual Gate
In the knapsack problem, we are given a set of n item, where each item i is specified by a size si and a value vi. We are also given a size bound S(the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of ... XXXX in the algo? No statement needed, it is already a complete algo. a[S][n]=result a[n][S]=result a[n][n]=result

asked Sep 20 in Algorithms by srestha (428 points) | 11 views

0 votes

0 answers

Algo Measy 2020

asked Sep 20 in Algorithms by GAITONDE (1.5k points) | 21 views

+1 vote

1 answer

Algo Made easy : GATE 2020
The Dimensions are A (5 x 10) , B(10 x 3) C(3 x12) D (12x3) My ans 303, ans given 405, which is right?

asked Sep 20 in Algorithms by GAITONDE (1.5k points) | 26 views

0 votes

1 answer

Algorithm: Made Easy
My ans is 14, but ME says 17.. Who is right?

asked Sep 20 in Algorithms by GAITONDE (1.5k points) | 33 views

0 votes

0 answers

Virtual Gate Test Series :Algorithm
Consider the following pseudocode, that computes kth power of x func(x,k){ IF k=0 return 1 ELSE IF k is even return(func(x,k/2))*(func(x,k/2)) } The time complexity $T(k)$ and space complexity $S(k)$ are $(A)T(k)=T(k/2)+c$, $S(k)=O(logk)$ $(A)T(k)=2T(k/2)+c$, $S(k)=O(k)$ $(A)T(k)=2T(k/2)+c$, $S(k)=O(logk)$ (D)None of these

asked Sep 19 in Algorithms by srestha (428 points) | 21 views

0 votes

1 answer

GATE 2009-39 (Re-visited Regarding a doubt)
Say we have an array like this→ [2,4,1,19,6,18,20,5] Here the $(n/4)th$ smallest element is → 2nd smallest element since the array size is 8. In this array the second smallest element is $2$ Now if we divide it according to the pivot we have a recurrence ... T(n)=T(n-1) + O(1) + O(n) So isn't this the worst case where the complexity is $O(n^2)$ ?

asked Sep 19 in Programming by GAITONDE (1.5k points) | 29 views

0 votes

0 answers

Algorithm :ACE Practice Test
Consider the following instance of OBST(Optimal Binary Search Tree) problem $n=4,$ $<a_{1},a_{2},a_{3},a_{4}>=<do,if,int,while>$ $P(1...4)=<3,3,1,1>$ $Q(0….4)=<2,3,1,1,1>$ The cost of OBST is___________ Is there any formula to calculate it??

asked Sep 16 in Algorithms by srestha (428 points) | 9 views

0 votes

3 answers

Self doubt on evaluation
What will be solution for $2^{2^{2^{2}}}$?? How to evaluate it? Left to right or right to left??

asked Sep 12 in Algorithms by srestha (428 points) | 17 views

0 votes

0 answers

Made easy Test Series question....
Consider th following cases for quick sort to sort an array of n element $a[0...n-1]$ i) Choosing the pivot element randomly from the given array ii) choosing median element as pivot. Iii) Choosing middle element as pivot For which of the above cases quick sort always gives $O(nlogn)$ time complexity?

asked Sep 11 in Algorithms by `JEET (157 points) | 9 views

0 votes

2 answers

Made easy test series question.
For the below message number of bits required in Huffman Coding is: abbaabccdabcd

asked Sep 11 in Algorithms by `JEET (157 points) | 23 views

0 votes

0 answers

Algorithm design / Jon Kleinberg, Éva Tardos.—1st ed excercises page 197

asked Sep 11 in Algorithms by nongshaba (7 points) | 14 views

0 votes

1 answer

Made easy test series.
Let $g(n) = \Omega(n)$, $f(n) = O(n)$ and $h(n) = \theta(n)$ then what is the time complexity of $[g(n) f(n) + h(n)]$ How to solve such questions?

asked Sep 11 in Algorithms by `JEET (157 points) | 17 views

0 votes

0 answers

Made Easy online test series
Consider an array A of length n, array contain number between (1 – 10), in any arbitary order, best sorting algorithm takes $650$ ns if $n = 50$, the time required by algorithm if n = 300.

asked Sep 11 in Algorithms by `JEET (157 points) | 9 views

0 votes

0 answers

Introduction to algorithm by Cormen Chapter 22 Lemma 22.2

asked Sep 9 in Algorithms by Lovejeet Singh (6 points) | 18 views

0 votes

4 answers

CLRS: Kruskal's algorithm
Suppose edge weights are integers in the range 1 to W, where W is a constant. How fast can Kruskal’s algorithm run?

asked Sep 2 in Algorithms by Sambhrant Maurya (277 points) | 18 views

+1 vote

1 answer

Gatebook TS: Algorithms
An array is said to be -ordered if for each such that . for example, the array 1 4 2 6 3 7 5 8 is 2-ordered. In a 2-ordered array of 2N elements, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?

asked Sep 1 in Algorithms by Sambhrant Maurya (277 points) | 21 views

0 votes

2 answers

Gatebook: Algorithms
Of the following, which gives the best upper bound for the value of where is a solution of the recurrence , with

asked Sep 1 in Algorithms by Sambhrant Maurya (277 points) | 30 views

0 votes

0 answers

Gatebook test series
Below is the implementation of merge sort. void sort(int a, int lo, int hi){ if(hi<=lo) return; int mid = lo + (hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); } Assume that merge function merges the elements a[lo] to a[mid] and a[mid+ ... a[mid]<=a[mid+1]. The number of comparisons needed to merge sort a sorted array is: O(n log n) O(n) O(1) O(log n)

asked Sep 1 in Algorithms by Sambhrant Maurya (277 points) | 13 views

0 votes

3 answers

[GATEBOOK TESTSERIES] WHICH IS CORRECT?
Suppose we are sorting an array of ten integers using some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 1 2 3 4 5 0 6 7 8 9 Which statement is ... algorithm might be insertion sort, but could not be selection sort. D. The algorithm is neither selection sort nor insertion sort.

asked Aug 31 in Algorithms by ummokkate (45 points) | 27 views

0 votes

2 answers

what does tightest lower bound means??
Here the tightest lower bound means?. (Please suggest some source if possible for such questions) https://gateoverflow.in/1026/gate2004-29

asked Aug 26 in Algorithms by Rishav_Bhatt (8 points) | 30 views

0 votes

1 answer

LCS exercise (Cormen)
We know that the longest common subsequence of 2 sequence X and Y of length m and n respectively can be determined in O (mn). But if we only have to determine the length of the longest common subsequence and not the actual subsequence we can compute it in O(n+m). Can anyone please suggest an algorithm with the complexity O(n+m)?

asked Aug 26 in Algorithms by Chirag Shilwant (7 points) | 28 views

0 votes

3 answers

Algorithms - Time Complexity analysis
1 .Let P be the problem. Suppose that the worst case asymptotic running time complexity of P is in O($n^2$lgn) and is also in Ω(n). Now let A be an algorithm that solves P. Which of the following is correct about A: A has worst-case time ... time case complexity of an algorithm is θ(n). The Algorithm executes in time T(n) = Ω($n^2$) for every input data.

asked Aug 22 in Algorithms by sagar2405 (87 points) | 45 views

0 votes

0 answers

Algorithms - Time complexity
1 .Solve the recurrence: $T(n) = 2T(\sqrt n) + log\ n$ $T(n) = T(\frac{n}{2}) + 2T(\frac{n}{4}) +n$ 2 .$f(n) = n^{1.01}$ and $g(n) = n(log\ n)^2$ then which one is true $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ $f(n) = \Theta(g(n))$ 3 . $f(n) = n^{\frac{1}{2}}, g(n) = 1$, then is it correct $g(n) = o(fn)$ {$o$ = small o Not big $O$} Please solve the above questions.

asked Aug 22 in Algorithms by sagar2405 (87 points) | 15 views

Page:

1,942 questions

1,184 answers

5,507 comments

89,631 users