Recent questions tagged greedy-algorithms

Match the following:$\begin{array}{|l|l|l|l|} \hline (1) & \text{Multistage graph} & (P) & \text{Divide and conquer}\\ \hline (2) & \text{Convex hull } & (Q) & \text{Dept...

Consider a sorted array of $p$ numbers. What would be the time complexity of the best known algorithm to find a pair $x$ and $y$ such that $\left | x-y \right |$ $=$ $m$ ...

Consider the following instance of the knapsack problem: n=3 , W=50 , (v1,v2,v3) = (60,100,120) and weight (w1,w2,w3) = (10,20,30) .solve the given knapsack problem apply...

$\begin{bmatrix} 0& 29& 19& 25& 22\\ 20& 0& 21& 23& 21\\ 19& 21& 0& 21& 20\\ 25& 23& 21& 0& 32\\ 22& 21& 20& 22& 0 \end{bmatrix}$Find the shortest tour for given graph us...

Consider the Knapsack incidence with n=3(items) with weights {w1,w2,w3}={2,3,4} and profits are {p1,p2,p3}={1,2,5}Given the capacity is 5,{W/M = 5 } Find the optimal solu...

US portal Denominations are 1,10,21,34,70 , 100 and 350 . A) Make 140 Cents .Verify whether Greedy choice fails or notB) Make 182 Cents.Verify whether greedy choice fails...

Consider the following set of messages with their frequencies: $$\begin{array}{|c|c|c|} \hline \textbf{Message} & \textbf{Frequency} \\ \hline A & 50\: \text{million} \...

We are given $9$ tasks $T_1, T_2, \dots, T_9$. 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$...

Suppose we have a graph with a negative weight cycle reaching from the source. And if we try to compute shortest path using Dijkstra's algorithm which of the following is...

Find out maximum profit for fractional knapsack with maximum allowable weight $=14$ and $n=5$\[\left(\mathrm{P}_{1}, \mathrm{P}_{2}, \mathrm{P}_{3}, \mathrm{P}_{4}, \math...

Given the symbols A, B, C, D, E, F, G and H with the probabilities $\frac{1}{30}, \frac{1}{30}, \frac{1}{30}, \frac{2}{30}, \frac{3}{30}, \frac{5}{30}, \frac{5}{30}$ and ...

I think Dijkstra algo. works fine with negative weight in connected graphs but not with negative cycle..if we have -ve weight but no cycle then it will give the shortest ...

You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of so...

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively....

Let $F_1,F_2,..............F_n$ be files with length $L_1,L_2........L_n$ we would like to merge all of the files together to make a single file .The cost of merging file...

There are n white dots and n black dots. Equally spaced in a line. You want to connect each white dot with some block dot in one to one fashion with a minimum total lengt...

In Optimal merge pattern when do we get more than one tree(Sub trees) when creating a merge pattern?Can you explain/draw optimal merge tree for n=7, <8,15,3,10,20,2,30>