Register

Web Page

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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 1&2&2& 2 &3&2&1&2&3
\\\hline\textbf{2 Marks Count} &4&2&2& 2 &3&4&2&2.83&4
\\\hline\textbf{Total Marks} &9&6&6& 6 &9&10&\bf{6} & \bf{7.67}&\bf{10}\\\hline
\end{array}}}$$

Filter

Recent questions in Algorithms

#3641
4.3k
views
5 answers
2 votes
Time complexity
Given a sorted array of n elements where other than one element x every other element repeat two times. Then how much time will it take to find position of x?
User Avatar
#3642
165
views
0 answers
0 votes
Asymptotics notations
Write true/false(log n)! and (log logn)! are polynomially bounded.What does this mean?
User Avatar
#3643
337
views
0 answers
1 votes
ISI2013-PCB-CS-1c
Consider the $\text{fast square}$ and $\text{multiply algorithm}$ to calculate $x^y \text{ mod } N$ as given below, where $x, \: y,\: N$ are positive integers ... is $O(log^2 \: N)$, when the positive integers involved are less than $N$.]
User Avatar
#3644
364
views
0 answers
1 votes
ISI2013-PCB-CS-1a,b
Consider the $fast \: square$ and $multiply \: algorithm$ to calculate $x^y \: mod \: N$ as given below, where $x, \: y,\: N$ ... , 64-bit unsigned integers). Discuss whether your program works perfectly for all possible input combinations.
User Avatar
#3645
11.8k
views
1 answers
8 votes
ISRO2011-56
Let $T(n)$ be defined by $T(1) =10$ and $T(n+1)=2n+T(n)$ for all integers $n \geq 1$. Which of the following represents the order of growth of $T(n)$ as a function of $n$?$O(n)$O(n \log n)$O(n^2)$O(n^3)$
User Avatar
#3646
1.1k
views
2 answers
0 votes
Recursion
Identify the false statement a. When a module calls a subroutine recursively ,in each call , all of the information is popped in the same order when sub ... either solves only part of the problem or it reduces the size of the problem
User Avatar
#3647
756
views
1 answers
1 votes
ISI2014-PCB-CS-3b
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
User Avatar
#3648
767
views
1 answers
1 votes
ISI2014-PCB-CS-3a
Let $A$ and $B$ be two arrays, each containing $n$ distinct integers. Each of them is sorted in increasing order. Let $C = A \cup B$. Design an algorithm for computing the median of $C$ as efficiently as you can.
User Avatar
#3649
626
views
1 answers
1 votes
ISI2014-PCB-CS-1
Assume you have a chocolate bar containing a number of small identical squares arranged in a rectangular pattern. Our job is to split the bar into small ... the length and the breadth according to your strategy of breaking the chocolate.
User Avatar
#3650
534
views
1 answers
1 votes
ISI2014-PCB-A-1b
Let $x, y$ be two non-negative integers $< 2^{32}$. By $x \wedge y$ we mean the integer represented by the bitwise logical $AND$ of the 32- bit binary ... the output of the pseudo-code for an arbitrary non-negative integer $x < 2^{32}$?
User Avatar
#3651
2.3k
views
1 answers
0 votes
Problem on Contiguous Memory allocation
There are 5 processes in a job queueProcessMemoryRequired TimeP1600kb10 msP21000kb5 msP3300kb20 msP4700kb 8 msP5500kb15 msMemory is byte addressableIf the size of the memory is 2000 kb and ... ) P1, P2 only(C) P3, P4 only(D) None of these
User Avatar
#3652
616
views
2 answers
3 votes
ISI2015-PCB-CS-2b
Let $P_1(x, y_1),\: P_2(x, y_2), \dots, P_n(x, y_n)$ be a collection of $n$ distinct points lying on a vertical line $L$. The value of $x$ is stored in a ... $R$ from $S$ to $D$ through $P_k$ is minimized.
User Avatar
#3653
1.1k
views
4 answers
11 votes
ISI2015-PCB-CS-2a
You are given two strings $S$ and $T$, each of length $\alpha$, consisting only of lower case English letters $(a,b, \dots ,z)$. Propose an $O(\alpha)$-time ... $T\: = \text{ retinaa}$, your algorithm should return $\text{NO}$.
User Avatar
#3654
563
views
1 answers
2 votes
ISI2015-PCB-A-1
Given an array $A$ of n positive integers, write a program segment / pseudo-code to print the histogram of $A$ using the hash character ($\#$). Your histogram should consist of $n$ vertical ...
User Avatar
#3655
2.6k
views
1 answers
4 votes
Dijkstra algorithm
Let $G(V,E)$ an undirected graph with positive edge weights. Dijkstra single source shortest path algorithm can be implemented using sorted linked list data structure. What will be time complexity?$O(|V|^2)$O(|V|^3)$O(|V|log|V|)$
User Avatar
#3656
936
views
1 answers
0 votes
Improvemet on bubble sort
Which of the following can make for an improved version of bubble sort?(A) Traverse the array left to right during odd passes and right to left during even passes, in ... in a separate array and make all the swaps at one go(D) None of these
User Avatar
#3657
1.3k
views
1 answers
7 votes
CMI2012-B-05b
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We ... the statement is false.All the shortest paths from $s$ to the other vertices are unchanged.
User Avatar
#3658
1.6k
views
4 answers
12 votes
CMI2012-B-03b
Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist ... $l$ such that $A[k]+A[l] = x$.Design an $O(n)$ algorithm for this problem.
User Avatar
#3659
557
views
1 answers
1 votes
CMI2011-B-07b
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots[ \: ]$ denotes the empty list, and ... return f2(g2(n-1),g1(n)) endifWhat is the value of $g2(256)$ and $g2(257)$?
User Avatar
#3660
540
views
1 answers
1 votes
CMI2011-B-06b
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different ... flipping the stack.)How many steps will your algorithm take in the worst case?
User Avatar
Page: