3

A basic result in elementary arithmetic states that $$ \log_a n = \log_a b \cdot \log_b n. $$ Indeed, on the one hand, $a^{\log_a n}$ by definition. On the other hand, $$ a^{\log_a b \cdot \log_b n} = (a^{\log_a b})^{\log_b n} = b^{\log_b n} = n. $$ Similarly, $$ \log_b n = \log_b a \cdot \log_a n. $$ This shows that every two logarithms only differ by a ...


2

When you get a question about a DAG, the first thing to do is a topological sort. Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.


2

You can find the median in linear time using the median of medians algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest. The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.


1

Your algorithm returns a cycle rather than a path. Here is a cycle: Here is a path: (Both images taken from Wikipedia.) To get a path from the cycle, simply remove one edge (this is my best guess for what return a path of that cycle means). Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.


1

The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough. Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral. One approach is by the Hough transform. To make it maximally efficient, ...


1

I don't know what you intended to write, but your loop runs in constant time if N <= 0, and will never finish if N > 0. If you start with i = 0, and multiply i by 5, guess what: It's still 0. I really can't see how you get to $i^5$. After k iterations, the initial value of i is replaced with $i * 5^k$; since the initial value is 0, it stays 0, and the ...


1

There are no set rules, but these type of details are sometimes omitted from the pseudocode listing. You might see something like ALGORITHM(S, n): For i = 1 to n do S = ADD(S, i) EndFor Then followed by something like "... the algorithm performs $\Theta(n)$ units of work assuming that the set $S$ is implemented as blah so that the addition of an element ...


1

As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$. We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ ...


1

All variables are understood to be positive integers. Let $n\mid m$ mean $n$ is a factor of $m$, a.k.a. $m$ is divisible by $n$ or $m=0\pmod n$. Is it correct that if $\gcd(n, k)=1$, then $n\mid\binom nk$? Yes. Since $k\binom nk=n\binom{n-1}{k-1}$, we know $k\binom nk$ is divisible by $n$. Since $\gcd(n,k)=1$, we must have $\binom nk$ is divisible by $...


1

Here's an O(1) space, O(n) time algorithm with Java code. Logic: Let $P_i$ denote the price of the stock on day $i$. Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$. If you had sold before day $i$ you can buy again at day $i$. ...


Only top voted, non community-wiki answers of a minimum length are eligible