New answers tagged

1

You are on the right track. Connect the starting node $s$ to each node in the first layer with an edge of capacity one. Since the balls $b_{i1}$ and $b_{i2}$ cannot stored in the same bin, for each bin $X$ in $\hat B_{i1}\cap\hat B_{i2}$, instead of connecting $b_{i1}$ and $b_{i2}$ directly to the node $X$ in the second layer, construct a node $c_{i,X}$ ...


3

Here are the first few values of the expression $\sum_{k=1}^n (-1)^k k$, starting with $n = 1$: $$ -1, 1, -2, 2, -3, 3, -4, 4, -5, 5,\ldots$$ Hopefully you can spot the pattern.


1

Let $G=(V, R \cup G \cup Y)$, where $R$, $G$, and $Y$ are the sets of red, green, and yellow edges, respectively. I assume you want to find the shortest walk between a pair of given vertices. Let these vertices be $s$ and $t$. Create the graph $G'=(V', E')$ where $V' = \{s', t'\} \cup \bigcup\limits_{v \in V} \{v_r, v_g, v_b \}$ and $E'= \{ (u_r, v_g) \mid (...


1

Hint: how does Kruskal's algorithm work? What can you say about the execution of Kruskal on the new graph?


3

Define $T^-(n) = T^-(n/2) + n$ and $T^+(n) = T^+(n/2) + 3n$. You can see that $T^-(n) \le T(n) \le T^+(n)$. Since the master theorem applies to both $T^-(n)$ and $T^+(n)$ which have solution $\Theta(n)$, you can also conclude that $T(n)=\Theta(n)$.


5

Since $|\cos n| \leq 1$, we have $1 \leq 2-\cos n \leq 3$, and so $$ T(n) = T(n/2) + \Theta(n). $$ This is something that the master theorem can handle.


4

$n(2-\cos n)$ always lies between $n$ and $3n$. On expansion, we get: $T(n) \leq 3 (n+n/2+n/4+\dotsc+1) \leq 6n$ and $T(n) \geq (n+n/2+n/4+\dotsc+1) \geq n$ Hence, $T(n) = \Theta(n)$.


4

The distinction is given at Wolfram. The Euler graph is a graph in which all vertices have an even degree. This graph can be disconnected also. The Eulerian graph is a graph in which there exists an Eulerian cycle. Equivalently, the graph must be connected and every vertex has an even degree. In other words, all Eulerian graphs are Euler graphs but not vice-...


1

If someone is not aware of method to solve this recurrence, then We can solve this by Substitution Given, $$T(n)=2T(\frac{n}{2})+1$$ Now, going by relation, $$T(\frac{n}{2})=2T(\frac{n}{4})+1$$ We will Substitute this in Original Recurrence Relation Therefore, $$T(n)=2T(\frac{n}{2})+1$$ $$T(n)=2 \Biggl(2T(\frac{n}{4})+1\Biggr) + 1$$ $$T(n)=2 \Biggl(2T(\frac{...


Top 50 recent answers are included