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|c|c|c|c|c|c|}\hline \textbf{Year}& \textbf{2026 - 1}& \textbf{2026 - 2}& \textbf{2025 - 1}& \textbf{2025 - 2}& \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}&4&4&2&2&1&2&2&2&3&2&1&2.4&4\\\hline \textbf{2 Marks Count}&6&4&3&3&4&2&2&2&3&4&2&3.3&6\\\hline \textbf{Total Marks}&16&12&8&8&9&6&6&6&9&10&\bf{6}&\bf{9}&\bf{16}\\\hline \end{array}}}$$

Filter

Recent questions in Algorithms

0 0 votes
1 1 answer
1.7k
1.7k views
Cormen Edition 3 Exercise 10.2 Question 7 (Page No. 241)
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that need...
User Avatar
1 1 vote
1 1 answer
948
948 views
Cormen Edition 3 Exercise 10.2 Question 6 (Page No. 241)
The dynamic-set operation $UNION$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S=S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2...
User Avatar
1 1 vote
1 1 answer
876
876 views
Cormen Edition 3 Exercise 10.2 Question 5 (Page No. 240)
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?
User Avatar
0 0 votes
0 0 answers
571
571 views
Cormen Edition 3 Exercise 10.2 Question 4 (Page No. 240)
LIST-SEARCH’(L, k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return xAs written, each loop iteration in the LIST-SEARCH’ procedure requires two te...
User Avatar
2 2 votes
2 2 answers
690
690 views
Cormen Edition 3 Exercise 10.2 Question 3 (Page No. 240)
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.
User Avatar
1 1 vote
1 1 answer
692
692 views
Cormen Edition 3 Exercise 10.2 Question 2 (Page No. 240)
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.
User Avatar
0 0 votes
1 1 answer
850
850 views
Cormen Edition 3 Exercise 10.2 Question 1 (Page No. 240)
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?
User Avatar
4 4 votes
2 2 answers
1.7k
1.7k views
Cormen Edition 3 Exercise 10.1 Question 7 (Page No. 236)
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
User Avatar
1 1 vote
2 2 answers
909
909 views
Cormen Edition 3 Exercise 10.1 Question 6 (Page No. 236)
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
User Avatar
0 0 votes
1 1 answer
2.1k
2.1k views
Cormen Edition 3 Exercise 10.1 Question 5 (Page No. 236)
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double ended qu...
User Avatar
0 0 votes
1 1 answer
782
782 views
Cormen Edition 3 Exercise 10.1 Question 4 (Page No. 235)
Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.
User Avatar
0 0 votes
1 1 answer
690
690 views
Cormen Edition 3 Exercise 10.1 Question 3 (Page No. 235)
ENQUEUE(Q, x) 1 Q[Q.tail] = x 2 if Q.tail == Q.length 3 Q.tail = 1 4 else Q.tail = Q.tail + 1 DEQUEUE(Q) 1 x = Q[Q.head] 2 if Q.head == Q.length 3 Q.head = 1 4 else Q.hea...
User Avatar
1 1 vote
1 1 answer
3.5k
3.5k views
Cormen Edition 3 Exercise 10.1 Question 2 (Page No. 235)
Explain how to implement two stacks in one array $A[1...n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$....
User Avatar
2 2 votes
1 1 answer
820
820 views
Cormen Edition 3 Exercise 10.1 Question 1 (Page No. 235)
STACK-EMPTY(S) 1 if S.top == 0 2 return TRUE 3 else return FALSE PUSH(S , x) 1 S.top = S.top + 1 2 S[S.top] = x POP(S) 1 if STACK-EMPTY(S) 2 error “underflow” 3 else S.to...
User Avatar
0 0 votes
1 1 answer
1.9k
1.9k views
Cormen Edition 3 Exercise 9.1 Question 2 (Page No. 215)
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are p...
User Avatar
0 0 votes
2 2 answers
883
883 views
Cormen Edition 3 Exercise 9.1 Question 1 (Page No. 215)
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil -2$ comparisons in the worst case. (Hint: Also find the smallest element.)
User Avatar
1 1 vote
0 0 answers
637
637 views
Cormen Edition 3 Exercise 8.4 Question 5 (Page No. 204)
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_...
User Avatar
0 0 votes
0 0 answers
926
926 views
Cormen Edition 3 Exercise 8.4 Question 4 (Page No. 204)
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2,….,n$.Suppose that the points are uniformly distributed; that is, the ...
User Avatar
1 1 vote
1 1 answer
1.3k
1.3k views
Cormen Edition 3 Exercise 8.4 Question 3 (Page No. 204)
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
User Avatar
1 1 vote
1 1 answer
1.1k
1.1k views
Cormen Edition 3 Exercise 8.4 Question 2 (Page No. 204)
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its...
User Avatar
Page: