Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
4

Consider the following graph $G = (V, E)$ where $$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$ If your example started at $1$, it will add $3$ to the list and then it will add $1$. In the next step the algorithm will choose $2$ as an unvisited vertex, which has an edge to a visited vertex $3$. Hence, It will conclude that the graph is not a DAG. However, the ...


3

The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise. Two examples of such functions are the maximum ...


2

To compute the node degree distribution, compute the degree of each node in the graph; then compute the distribution of these numbers (e.g., display a histogram of them). Each of those tasks is a straightforward coding exercise.


2

It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$. The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration. The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{...


2

Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows: $$ Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c. $$ Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back: $$ T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n). $$


1

Yes, of course. $2^{f(n}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times. The answer to your other questions are also yes, by the time hierarchy theorem.


1

Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is. Now by reducing set cover to your problem,...


1

Define S(k) = $T(2^{2^k})$. Then S(k) = $T(2^{2^k})$ = $T(2^{2^{k-1}}) + c$ = $T(2^{2^{k-2}}) + 2c$ = ... = $T(2^{2^{k-k}}) + k\cdot c$ = $T(2) + k\cdot c$.


1

Why don't we just use DFS to find shortest path in DAG? For this try to find shortest path from source vertex $0$ to all vertex in following graph. In particular if DFS visits $1$ first from $0$ then it will assign shortest path distance $10$ to $4$ which is wrong.


1

The only question is in the tile so I'm going to answer that. A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$. As a counter example look at the following graph: If vertex $a$ is visited before vertex $b$ you will not necessarily discover the shortest path from $s$ to $b$. Also, the same example shows ...


1

It depends on which data structure you use to store the graph. For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}[i]$ as $\texttt{...


1

As you mention, you can show inductively that $T(n) = T(n^{1/2^k}) + kc$, with base case $T(n) = O(1)$ for $n \leq 2$ (say). It follows that $T(n) = \Theta(\ell)$, where $\ell$ is the minimal number such that $n^{1/2^\ell} \leq 2$. Taking a log, we get $\frac{\log n}{2^\ell} \leq 1$, or $\log n \leq 2^\ell$. Taking another log, we get $\log \log n \leq \ell$....


1

Bigoh notation $O$: This is anlogous to $\le$. $f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$ Smalloh notation $o$: This is anlogous to $<$ relation. Now, $f(n) = o(g(n))$ means that if you are given any constant $c>0$ you will be able to find out some constant $n_0&...


1

In short and simple, I will show you why. Suppose, you have a factorization algorithm. Except for the small difference that one accepts integers for input and the other $Tally$. As you can see both code snippets are similar. x = input integer factors = []; for i in range(1, x + 1): if x % i == 0: factors.append(i) print(factors) Notice that ...


1

For almost 40 years it was thought that an intuitive two-pointers based algorithm for finding a maximum-area triangle inside a convex polygon was correct. It was proved incorrect in https://arxiv.org/abs/1705.11035.


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