New answers tagged

0

If you don’t know quickselect: Just implement Quicksort, but every time Quicksort would sort a sub array, you don’t do it if you don’t need it to find out which items I to j are.


3

I could do QuickSelect (j - i) times to get all the elements Overkill. Two calls to QuickSelect and one linear pass are sufficient.


0

For coffee, you can replace the less than with $$\leq n^3-1$$ and since you’re counting the number of doubling, the answer will be $$\lfloor(\log(n^3-1,2))+1\rfloor$$ For mocha firstly notice inner loop is equivalent to r+=i and the sum becomes $$16 \cdot \lfloor(n/16)\cdot(\lfloor(n/16)+1)/2 \rfloor \rfloor$$ I’m pretty sure you can work out the last ...


0

Simple answer No, we cannot sort start time in ascending order to get a valid dynamic programming algorithm. A counterexample As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we have $p_4=3$ and $OPT(4)=1+OPT(3)$. By definition, $OPT(3)$ equals to the optimal value ...


1

First of all, let me clarify a few points about your example: Bellman-Ford-Moore consists of two phases, stages or steps, each one consisting of a number of iterations as they are implemented with loops. The first phase computes the cost of the shortest-path to reach each vertex from the start vertex and it consists of two nested loops; the second one ...


1

Just solve both cases separately. I.e., consider cases for $m < k$ and $m = k$ separately. The solution for the first one (i.e., $T(n, k - 1)$) gives the starting point for the second recurrence (i.e., $T'(n) = T(n, k)$, presumably for $n \ge k$).


2

When $d = \Theta(n^\alpha)$, we have $\log_d n = \Theta(1)$, and so there is no difference between $d^2\log_d^2 n$ and $d^2\log_d n$ (or rather, the two differ only by a constant factor). When $d$ is polylogarithmic in $n$, $\log_d n = \log n / \log d = \Theta(\log n/\log \log n)$, and so $\log^2_d n = \Theta((\log n / \log\log n)^2)$ is asymptotically ...


1

Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation. In your case, Worst case: The required element is not present in the array (or is the last element of the array) : O(M) Best case: The element is found in the first position itself: O(1) Average case: Average of all ...


0

Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle. Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible ...


1

There is an $O(k)$ algorithm [1]. [1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214.


0

Instead of collecting each partial product then adding all of them at the end, let's keep a register that is 2n digits long, initially full of zeros, and we will update it as we go. After each n + 1 digit-long partial product, we add it into the sum register. We need to shift it one digit higher each round. We need to do n + 1 additions, then need to do ...


0

I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases. Combinations So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways. $$\sum_{k=0}^n{n\choose k} = 2^n$$ This is a subtle hint ...


0

I see two ways of doing it / thinking about it, which are essentially equivalent. Method 1: Use recursion to implement your DFS. When at a node of your tree, you just need to recursively call the DFS on every child node, then output/store the current node (or the other way around). The backtracking will take care of itself. If you don't want to use ...


0

Let us start with the subroutine PARTITION. The loop maintains the following invariant: $A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$. If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq ...


Top 50 recent answers are included