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.

# Tag Info

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