Recent questions tagged algorithms

Consider two DNA sequences represented by strings $S_1=$ "AGGTAB" and $S_2=$ "GXTXAYB". To analyse their relationship, a bioinformatician wants to find the shortest possi...

The five items, A, B, C, D, and E, are pushed in a stack, one after the other, starting from A. The stack is popped four times and each element is inserted in a queue. Th...

Consider the following binary search tree T given below. Which node contains the fourth smallest element in $T$ ?Q V W X

If one uses the straight two-way merge sort algorithm to sort the following elements in ascending order: $20,47,15,8,9,4,40,30,12,17$, then the order of these elements af...

A file contains the following characters with the given frequencies:a: $45$b: $13$c: $12$d: $16$e: $9$f: $5$What is the total number of bits required to encode the messag...

Consider the following weighted, directed graph. If Dijkstra's single-source shortest path algorithm is run with source vertex 'S', what is the order in which the vertice...

Consider a connected, undirected graph $G=(V, E)$ with a weight function $w: E \rightarrow \mathbb{R}^{+}$ where all edge weights are distinct. Let $T$ be the Minimum Spa...

Consider the following recurrence:$$\begin{aligned}& T(n)=2 T(\sqrt{n})+1 \\& T(1)=1\end{aligned}$$Which of the following is NOT true?$T(n)=O(\log \log n)$ $T(n)=O(\log n...

The recurrence relation that arises in relation with the complexity of binary search is$T(n)=2 T(n / 2)+k$, where k is constant $T(n)=T(n / 2)+k$, where k is constant $T(...

Arrange the following recurrence relations in increasing order of their time capacity.(A) $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+1$(B) $\mathrm{T}(\mathrm{n})...

Which of the following is not time complexity of the following code:(O represents big-oh) for (i=1 to n): // Some constant time operation,O(1) // Then a loop that runs lo...

If the array $A$ contains elements $25,40,23,7,54,78$ and $2$ in that order, The element at $3^{\text {rd }}$ position of the array after $3^{\text {rd }}$ pass of insert...

G is an undirected graph with vertex set ( $\mathrm{v} 1, \mathrm{v} 2, \mathrm{v3}, \mathrm{v4}, \mathrm{v5}, \mathrm{v6}, \mathrm{v7}$ ) and edge set [ $\mathrm{v} 1 \m...

A Huffman tree is constructed for the following data: $[A, B, C, D, E]$ with frequency $\{0.17$, $0.11,0.24,0.33$ and $0.15$} respectively. $1000001101$ is decoded asBACE...

How to check if f(n) is polynomially greater than g(n)?

Which of the following technique is used for Clipping?Stack based SeedScan Line SeedSutherland-CohenInverse Scaling

Match List I with List II$\begin{array}{|ll|ll|} \hline & \textbf{List I} & & \textbf{List II} \\ \hline \text{A.} & \text{Circular Queue} & \text{I.} & \text{Print Queue...

Which of the following algorithms are based on the Breadth First Search (BFS) ?Prim's algorithmsKruskal algorithmsDijkstra algorithmsGreedy algorithmsDynamic ProgrammingC...

Let T(n) = 2T(n/2) + O(n), Where "O" is big-oh . What will be asymptotic notation on T(n)?options are MSQa).Theta(n)b).Theta(nlogn)c).Theta(n^2)d).O(n^3)

Match List - I with List - II.$\begin{array}{|ll|ll|} \hline & \textbf{List - I} & & \text{List - II} \\ \hline & \textbf{(Algorithms)} & & \textbf{(Characteristics)} \\ ...

Consider the weights and values of items listed below. Note that there is only one unit of each item.\[\begin{array}{|l|c|c|}\hline\text{Item number} & \text{Weight (in K...

We are given 8 tasks $T_1, T_2, \ldots, T_8$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ ...

Consider the following functions:$$\begin{aligned}& \mathrm{f}(\mathrm{n})=3 \mathrm{n}^{\sqrt{\mathrm{n}}} \\& \mathrm{~g}(\mathrm{n})=2^{\sqrt{\mathrm{n}}\log _2{\mathr...

If algorithm $A$ and another algorithm $B$ take $\log _2(n)$ and $\sqrt{ } n$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these...

Given a 2-D array mat where the elements of each row are sorted in non-decreasing order and the first element of a row is greater than the last element of the previous ro...

We have an array $A$ of $n$ numbers, where $n$ is a power of $2$.We build a full binary tree on top of the array $A.$ The elements of the array are leaves of the tree, nu...

We have an array $A$ of $n$ numbers, where $n$ is a power of $2$.We build a full binary tree on top of the array $A.$ The elements of the array are leaves of the tree, nu...

You are given two sorted arrays, each of length $n$. What is the best possible time complexity (in the worst case) to find the median of the combined $2 n$ elements?$O(n)...