# Question
Title: Prove that the total distance is minimised (when travelling across the longest path)
Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have to return where I started.

As my specification is not really clear I made up an example: Consider the graph (which is a tree here - undirected weighted acyclic graph) to have nodes as cities and edges as roads between cities. I need to deliver something to every city (visit every node at least once). I can start from any city and end at any city that I choose to.

I read the following result. Find the two cities in the graph that are the farthest apart (call them $c1$ and $c2$). Start from one of them ($c1$ or $c2$), visit every other city along the way until I reach ($c2$ or $c1$). This minimises the total distance to travel.

How should I prove that this is the minimum distance ?

I attempted the following. I have the final route and I call edges, $m\_1, m\_2, ..., m\_i$ and $e\_1, e\_2, ..., e\_j$. Where $m\_1, m\_2, ..., m\_i$ are the edges along the cities that are the farthest apart ($c1$ and $c2$) and $e\_1, e\_2, ..., e\_j$ are everything else in the graph. As I start from $c1$, I travel along edges labelled m exactly once and everything else labelled e is a digression and go back and forth twice on those edges, before I reach $c2$.

We know that $m\_1, m\_2, ..., m\_i$ and $e\_1, e\_2, ..., e\_j$ taken together include all the edges on the graph (as it is a tree, there's only a unique path between every two nodes). So the distance I travel could be given as $2(e\_1 + e\_2 + .... + e\_j) + (m\_1 + m\_2 + ... + m\_i)$.

I need to prove that this sum is less than every other route that I can take to reach all the cities. My intuition says that this has to be the shortest route. I feel that have to use the fact that $(m\_1 + m\_2 + ... + m\_i)$ is the maximum between any two nodes in the graph somehow (is that called the diameter ?), and arrive at a contradiction.

This is the kind of picture I have in my mind (red edges are in ($m\_1, m\_2, ..., m\_i$) and the grey ones are everything else),

That graph is still a tree (please ignore the arrow head in the edges that show how I decide to travel). I don't to where to go from here. I would appreciate a proof that is simple to understand (This is not a homework or anything related to coursework.)

# Answer
> 4 votes
Let $x$ be a vertex of your tree and consider a shortest route that visits every vertex and returns to $x$. It's easy to see that, regardless of the choice of $x$, any minimal route walks along every edge exactly twice: it must use each edge at least twice, or it wouldn't be able to get back to $x$; if it uses an edge more than twice, you can rearrange to avoid the backtracking. Therefore, all such minimal routes have the same length, regardless of the choice of $x$. Call that length $L$ (which is $2(n-1)$ if the tree is unweighted and there are $n$ vertices, but this isn't important).

Now, given a minimal route from $x$, let $y$ be the last vertex to be visited for the first time (i.e., the vertex which, when you first visit it, you say "Aha, now I've been to every vertex!"). The minimal route visits every vertex on its way from $x$ to $y$, and then returns immediately to $x$ along the unique shortest path. Let $L\_{xy}$ be the length of the walk taken from $x$ to $y$. We know that $L=L\_{xy}+d(x,y)$, and $L$ and $d(x,y)$ don't depend on how we got to $y$, so $L\_{x,y}$ also doesn't depend on the route and we can say that $L\_{xy}$ is the length of any minimal walk from $x$ to $y$ that visits every vertex.

The vertex $y$ must be a leaf: if it wasn't, when you first visited $y$, you wouldn't have visited any of the vertices "beyond" it. Further, for any leaf $z$ of the tree, there are minimal routes from $x$ back to itself such that $z$ is the last vertex visited for the first time: let $v\_1v\_2\dots v\_t$ be the path from $v\_1=x$ to $z=v\_t$ and don't go to $v\_{i+1}$ until you've already visited every other descendant of $v\_i$.

So, to get the longest walk from $x$ that visits every vertex, pick a route whose $y$ is the leaf at greatest distance from $x$. None of the above depends on which vertex was chosen as $x$, $L\_{xy}=L-d(x,y)$ is minimized by choosing $x$ and $y$ to be the vertices at greatest possible distance in the tree, which are both leaves.

# Answer
> 4 votes
Here is a proof rigorous enough that should be easy enough to understand as well.

Let $T=(V,E)$. Let $j$ be a journey that passes every city, starting at city $s$ and finishing at city $f$. Let $t\_e$ is the number of times $j$ goes through edge $e$. Let $P$ be the unique path from $s$ to $f$.

Claim 1: $t\_e\ge 1$.
Proof: If we remove edge $e$ from $T$, $T$ is separated into two trees that are disconnected to each other. If $t\_e\not\ge1$, i.e., $j$ does not include $e$, that means $j$ is disconnected, which is false.

Claim 2: $t\_e\ge 2$ if $e\not\in P$.
Proof. Let $e\not\in P$. If we remove edge $e$ from $T$, $T$ is separated into two smaller trees that are disconnected to each other. Denote those two trees $T\_1$ and $T\_2$. Since $P$ is connected, $P$ is in $T\_1$ entirely or $T\_2$ entirely. That means both $s$ and $f$ are in $T\_1$ or both are in $T\_2$. Starting at $s$ in one of the smaller trees, $j$ must go to the other smaller tree through $e$ before returning to $f$ through $e$ again.

The total distance of $j$ is $$\begin{align}{\sum\_{e\in E}t\_ee}&=\sum\_{e\in P}t\_ee + \sum\_{e\in E\text{ and }e\not\in P}t\_ee\\ &=\sum\_{e\in E}2e + \sum\_{e\in P}(t\_e-2)e + \sum\_{e\in E\text{ and }e\not\in P}(t\_e-2)e\\ &\ge\sum\_{e\in E}2e + \sum\_{e\in P}(t\_e-2)e \\ &\ge\sum\_{e\in E}2e - \sum\_{e\in P}e \\ &\ge\sum\_{e\in E}2e - \text{ diameter of } T \\ \end{align}$$

The other part of the proof is to show the journey can be as short as $\displaystyle{\sum\_{e\in E}2e - \sum\_{e\in P}e}$ for any path $P$, as indicated by the picture in the question. We can prove by induction on $n$, the number of nodes that is not on $P$. The base case when $n=0$ is clear. For the induction step, we can find a leaf that is not in $P$. (Pick any edge not in $P$, whose removal splits $T$ into two smaller trees. Pick any leaf in the smaller tree that does not contain $P$.) Then we can extend a journey that misses that leaf by inserting into that journey an excursion that goes to that leaf and then returns back.

---

Here is a related exercise.

**Exercise.** Prove the following algorithm finds a diameter of a given tree.

1. Let $u$ be a node.
2. Find $v$, one of the farthest nodes from $u$.
3. Find $w$, one of the farthest nodes from $v$.
4. return the path from $v$ to $w$.

---
Tags: graphs, trees, correctness-proof
---


# Question
Title: What is the language L, generated by the grammar G?
Given the grammar $G = (Ν, Σ, Π, S)$, where $Ν = \\{S\\}$, $Σ = \\{0, 1\\}$, $Π = \\{S → ε, S → 0, S → 1, S → 0S0, S → 1S1\\}$, and $S$ is $S$. What is the language generated by the grammar?

# Answer
This is the general solution to your problem:

Depending on the syntax that you are used to, might be used instead of , but both symbols mean the same. In the case of the provided grammar, there is an infinite amount of words that can be generated, so you would rather not use a set of single, explicit words to represent the language. The kind of language created by your grammar is a non-deterministic context-free language (NCFL) and a common way of displaying it is:
> 1 votes

# Answer
As grammar G is given G = (Ν, Σ, Π, S), where Ν = {S} and Σ = {0, 1} so using this Π = {S → ε, S → 0, S → 1, S → 0S0, S → 1S1} we evaluate a language L by putting non-terminal value and generating new strings that can be a part of language L and accepted by the grammar rule: so L={ ε, 0 , 1, 00,11,000,111,010,101,0000,1111,00100,00000,11111,11011,....} so on and so forth. we will just evaluate a non-terminal with a terminal value and get a resultant string.
> 0 votes

---
Tags: context-free
---


title: How to solve equations using big Θ

text:
# Question
Title: How to solve equations using big Θ
How would I prove that the statement

$10n^3+3n=Θ(n^3)$

is true/false?

# Answer
Remember that, $10n^3+3n=Θ(n^3)$ is an abuse of notation. Think of $Θ(n^3)$ as a set/class of functions. You are prove to that $10n^3+3n$ belongs to that set.

Simply put, every element in the set has a property, and everything that has the property belongs to the set ("if and only if" is the mathy way they say this). A function $f(n)$ belongs to $Θ(g(n))$ if that property holds.

So, what is that property exactly ?

$C\_1g(n) ≤ f(n) ≤ C\_2 g(n)$ whenever $n \> k$

Well, what does that mean ? For a decently large $n$, every element (called $f(n)$ here) in the set (which is $Θ(g(n))$ here), is smaller than a constant ($C\_2$) times $g(n)$, and also it is always larger than a different constant ($C\_1$) times $g(n)$.

Note that that the inequality implies, $\frac{f(n)}{g(n)} ≤ C\_2$ and $C\_1 ≤ \frac{f(n)}{g(n)}$. All we have left to do is to find such a $C\_1$ and $C\_2$.

Consider

$\frac{10n^3+3n}{n^3}$

this is always less than or equal to $\frac{10n^3+3n^3}{n^3}$ \- because we assume $n$ is a positive integer and so $n^3$ is always at least $n$ \- which is less than or equal to $13$. This proves the $\frac{f(n)}{g(n)} ≤ C\_2$ part.

Moreover $\frac{10n^3+3n}{n^3}$ is greater than or equal to $\frac{10n^3}{n^3}$. Again as n is positive dropping $3n$ could only make it smaller. This implies the constant $C\_1$ is $10$, the second part.

The first part proves that $f(n)$ belongs to $O(g(n))$ and the second proves $\Omega(g(n))$ which implies $Θ(g(n))$ usually.

So this gives a sloppy bound that this function could only be 13 times as big, and 10 times as small. $10n^3 ≤ 10n^3 + 3n ≤ 13n^3$. To be precise we assumed $n\>1$ and $k=1$ here. Use the limit definition for an exact proof. But this is pragmatic and should be enough in most cases.
> 2 votes

# Answer
This isn't really an equation. The equals sign in the middle is an abuse of notation: $\Theta(n^3)$ is a set of functions, not a single function, so it should more properly be written $(10n^3+n) \in \Theta(n^3)$.

The formal definition of $\Theta(n^3)$ is something like this:

> $\Theta(n^3)$ is the set of all functions $f(n)$ such that, for some specific choice of constants $N, C, D$, then $n \> N \implies Cn^3 \< f(n) \< Dn^3$.

Basically, when $n$ gets really big, $\Theta(n^3)$ means that the function starts to "look like" $n^3$, up to a constant factor. There's a useful lemma here which helps more:

> For a function $f(n)$, if $\lim\_{n \rightarrow \infty} \frac{f(n)}{n^3}$ exists and is a positive constant, then $f(n) \in \Theta(n^3)$.

This is much easier to use here, in my opinion. With a bit of algebra, we can say that $\lim\_{n \rightarrow \infty} \frac{10n^3+n}{n^3} = \lim\_{n \rightarrow \infty} \frac{10n^3}{n^3} + \lim\_{n \rightarrow \infty} \frac{n}{n^3} = 10+0 = 10$. Since ten is a positive constant, we've shown that $(10n^3+n) \in \Theta(n^3)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Prove that $I(A;B|C)=0$ given $I(A;B)=0$
Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn diagram this seems trivially true, but I just cannot find a way to prove it.

# Answer
$I(A;B\mid C)$ indicates "the reduction in the uncertainty of $A$ due to knowledge of $B$ when $C$ is given".

To find an example where $I(A;B\mid C)\not= 0$, we can see if the combination of $B$ and $C$ can help determine $A$ even though knowing $B$ alone does not help at all.

So let us try to create $A$ from the combination of $B$ and $C$. Let $B$ and $C$ be two simplest non-trivial independent random variables, $$P(B=0, C=0)=P(B=0, C=1)=P(B=1, C=0)=P(B=1, C=1)=1/4.$$ Let $A$ be 0 if $B$ and $C$ turns out the same and 1 otherwise.

We can check that $A$, $B$ and $C$ are pairwise independent. However, given the values of any two of them, the third one is determined. (In modulo arithmetic, $B+C=A(\bmod 2)$). When $C$ is given, we will not know anything more about $A$; if $B$ is known additionally, we will know $A$ completely. The above shows how we can find and understand an example. Beginners are encouraged to verify various "obvious" (or "obscure") claims above by using the corresponding definitions.

---

**Exercise**. Verify that $I(A;B)=0$ and $I(A;B\mid C)=1$ in the example above.
> 3 votes

# Answer
Your claim is false. Let $A,B,C$ range uniformly over the set $$ \\{(x,y,z) \in \\{0,1\\}^3 : x \oplus y \oplus z = 0 \\}. $$ On the one hand, $I(A;B) = 0$. On the other hand, $I(A;B|C) = 1$.
> 3 votes

---
Tags: information-theory
---


# Question
Title: Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10
The solution is to find the upper and lower bounds from:

```
2T(n-2) < T(n) < 2T(n-1) + 10

```

So I have to find

```
T(n) > 2T(n-2)

```

and

```
T(n) < 2T(n-1) + 10

```

My question about this solution method is not how to solve those recurrence relations. It's about why this method can be used in the first place. I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds. Is there a way to solve the recurrence relation without using this method and finding out the precise runtime?

# Answer
> 4 votes
The goal of a recurrence relation is to make a complicated problem easier to think about, which is very general. It allows us to express a function in terms of itself, but still reason about what the value of the function for an input is.

Sometimes you care about the exact value of the function, in which case you'd prefer to rewrite it in an exactly equivalent way (or just plug in a number and follow the recursion chain until you have your answer).

Other times, you're just worried about the extreme "if my worst enemy plugged a value into this function, what would it do?" case.

Rewriting the equation as an inequality let's us remove an entire recursive call of the function, which makes doing substitutions to figure out an easier to reason about form of the function a more achievable goal.

So yes, $T(N) = T(N-1) + T(N-2) + 10$, may exactly describe the run time of your program, or the amount of money in my bank account after $N$ days (I wish), but we don't care about that precision, because $T(N) \< 2T(N-1) + 10$ is an upperbound, and we just want to know that our program will finish before the heat death of the universe, or that I have enough money in my bank account for dinner.

Note the benefit here. Perhaps because your algorithm had a recursive nature to it, it might have been really easy to come up with the $T(N) = T(N-1) + T(N-2) + 10$ description of the run time. Easy to come up with, but hard to think about what the function actually means. So now that we have this building block, we come up with an upper bound (that we know is true), but has less recursion (which our brains don't like). This is nice on its own, but it also let's us continue to expand the recursive definition until we understand the underlying pattern, and can remove the recursion completely.

# Answer
> 2 votes
> I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds.

No, solving a recurrence is solving a recurrence. It's unfortunate that students often get the impression that recurrence relations are necessarily about running times. Wouldn't it be bizarre if a physicist believed that multiplication is "calculating a force" because they'd learnt that $F=ma$?

And why should solutions always be exact? Maybe you need it exact, maybe you don't. Suppose you want to fill your kids' circular paddling pool with water, and it's $1.5\\,\mathrm{m}$ across and $20\\,\mathrm{cm}$ deep. How much water do you need? Are you going to insist that the answer is $225\pi/2$ litres or is "between $353$ and $354$" litres good enough? Or even just "about $350$ litres"?

# Answer
> 1 votes
Given the recurrence

$\qquad\displaystyle T(n) = T(n-1) + T(n-2) + 10$

with reasonable initial conditions, e.g. $T(0) = 1$ and $T(1) = 2$, it is easy to see that $T$ is *strictly increasing*. (I leave a proof as exercise; use that $T(n) \geq 0$ for all $n$ here.) That means that $T(n-1) \> T(n-2)$ and therewith, indeed,

$\qquad\displaystyle 2T(n-2) + 10 \leq T(n) \leq 2T(n-1) + 10$

for $n \geq 2$. The more you learn about $T(n-1) - T(n-2)$, the tighter you can make these bounds!

As a consequence, with

$\qquad\displaystyle T\_l(n) = 2T\_l(n-2) + 10$ and

$\qquad\displaystyle T\_u(n) = 2T\_u(n-1) + 10$

we obtain that

$\qquad\displaystyle T\_l(n) \leq T(n) \leq T\_u(n)$.

Solve those two simpler recurrences (again, details left as excercise) and you obtain that

$\qquad\displaystyle T \in \Omega(\sqrt{2}^n) \cap O(2^n)$,

where exact figures instead of Landau bounds are quite achievable with basic techniques.

# Answer
> 0 votes
By substituting $F(n)=T(n)+10$, we obtain exactly the relation of the Fibonacci series, which grows as $O(e^n)$.

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: Can someone explain why the MAX-CUT problem is in NP?
Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset?

I'm a little confused on showing how the problem is NP, in terms of a certificate and certifier.

# Answer
The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $k$ and answer accordingly YES or NO.
> 4 votes

# Answer
Problems that ask “is there an X with property Y” are very often in NP: If it is possible to show in polynomial time that an X has property Y, but also if for every X with property Y there is a proof that it has property Y that can be checked in polynomial time (this covers those cases where a proof that X has property Y is itself hard to find).
> 0 votes

---
Tags: algorithms, complexity-theory, np, decision-problem
---


title: Amortized analysis of max-heap

text:
# Question
Title: Amortized analysis of max-heap
Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time.

> Question: If extract max is $O(1)$ amortized does that mean worst case is $O(n)$?

My answer: No, A sequence of $n$ EXTRACT\_MAX will cost $O(n\log n)$. This is because in a Heap the leaves are almost on the same level and the number of leaves in a Heap is $O(n/2) = O(n)$. Calling EXTRACT\_MAX each time removes the maximum element from the root and replace it with a new second maximum element and decrement a leaf. Thus, decrementing all the leaves (which are of $O(n)$) will take $O(\log n)$ time each as all leaves are almost in the same level totally giving a time complexity of $O(n\log n)^{1/4}$.

Does this make sense?

# Answer
If an operation, any operation, has an amortised cost of O(1), then performing it n times has cost O(n), by definition of “amortised cost”. Either your amortised cost is wrong, or your total cost is (assuming you change “O(n log n)” to “not O(n)”, to be a bit pedantic).
> 1 votes

# Answer
Your proposed answer contradicts itself, so no, it doesn't make sense. It starts by saying it will take $O(n \log n)$ time and concludes by saying it will take time $O(n \log n)^{1/4}$ time. You need to decide which you mean. And it's not clear where the $1/4$ came from.
> 1 votes

---
Tags: amortized-analysis
---


# Question
Title: 3SAT instance with EXACTLY 3 instances of each literal
I'm trying to solve a question which requires me to

1. prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined) and each clause contains exactly 3 literals is always satisfiable.
2. Find a polynomial time algorithm to find a satisfying assignment for it.

**My Solution**

I'm not sure how to prove part 1. I'm trying to solve 2 by reducing it to an instance of Vertex Cover in which each literal has 2 nodes - one positive, one negative - and each node is connected to the other literals its in a clause with. A vertex cover of size m = # of literals will give us the assignment needed.

Im not sure of I'm along the right path or not? Any help would be appreciated!

# Answer
It looks like you missed the promising reformulation of this 3SAT. The simple idea is to select a different variable for each clause.

## Always satisfiable

Let the variables be $V=\\{v\_1, v\_2, \cdots, v\_n\\}$ and the clauses be $C=\\{c\_1,c\_2,\cdots, c\_m\\}$.

Construct a bipartite graph $G=(C,V)$, where $(c,v)$ is an edge if $v$ or $\neg v$ is a literal of $c$. The given conditions mean the degree of each clause and the degree of each variable are 3.

For a subset $W$ of $C$, let $N(W)$ denote the set of all variables adjacent to some clause in $W$. Consider the edges that have one endpoint in $W$. The number of them is exactly $3|W|$ and at most $3|N(W)|$. Hence $|W|\leq |N(W)|.$ By Hall's marriage theorem, for each clause $c$, we can select a distinct variable $m(c)$ such that $(c,m(c))$ is an edge.

For all clause $c$ do the following. If $m(c)$ is a literal of $c$, set $m(c)$ to be true. Otherwise, $\neg m(c)$ is a literal $c$ and we set $m(c)$ to be false. In either case, $c$ becomes true.

### Polynomial algorithm

The proof above actually gives the outline of an algorithm. Each step of the algorithm takes polynomial time. In particular, the application of Hall's marriage theorem can be implemented in polynomial time as, for example shown here.

### A generalization

Here is a natural generalization.

**Exercise.** Generalize to the case when each variable appears in at most $r$ clauses and each clause contains at least $r$ distinct variables, where $r\ge1$.
> 5 votes

---
Tags: algorithms, graphs
---


# Question
Title: Determine endpoint of a graph given as a list of nodes + direct successors and predecessors
**EDIT @20190313**

I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and every node stores a list of adjacent nodes, its direct successors and predecessors. The graph is in fact highly non weakly-connected, in the sense that the number of its weakly-connected components is quite big. I must everyday find the weakly-connected components of the graph and determine sink nodes of every weakly-connected components, and know from one day to the next any new sink node for every weakly-connected components. (From one day to the next, only new sink nodes might be added, with their associated edges.)

---

I fix a type T once for all. (Concretely, `T` is a c# class, but that doesn't matter.) On `T` I have the notion of direct successor and direct predecessor. (Imagine the two notions modelled byt two `T × T --> bool` functions.) The notion is nice in the sense that `t'` is a direct successor of `t` if and only if `t` is a direct predecessor of `t'`. For an object `t` of type `T` I note `d(t)` the set (in the usual sense) of its direct predecessors and successors.

Each day I receive an xml containing the list of all (xml representations) of objects of type `t`, the representation of `t` "containing" `d(t)`.

For an object `t` and an integer k\>0 I note `S(t,k)` (resp. `P(t,k)`) the set of rank-k successors (resp. predecessors) of `t`, this set being recursively defined as `S(t,1)` (resp. `P(t,1)`) being the set of direct successors (resp. predecessors) of `t`, and `S(t,k)` (resp. `P(t,k)`) being the set of direct successors (resp. predecessors) of object from `S(t,k-1)` (resp. `P(t,k-1)`). Finally I note `F(t,k)` the union of `S(t,k)` and `P(t,k)`, and `G(t)` the union of all `F(t,k)` for k\>1.

`G(t)` as defined is only a set, but can be turned into a graph as follows : each object of `G(t)` is a node, and two nodes `t,t'` are connected by an arrow going from `t` to `t'` if `t'` is a direct successor of `t`. The graph `G(t)` is connected by contruction and I note `B(G(t))` its end points : the objects `x` in `G(t)` that don't have any direct successor (i.e. such that `S(x,1)` is empty).

I note `X` the set of all objects from the xml, and `G1,...,GN` all graphs. They obviously partition `X`.

My task is the following : every day, for any object `t` from `X`, I have to be able to determine the set `B(G(t))` as fast as possible and the graph `G(t)` as fast as possible. (I can imagine that the two tasks may not necessarily be related.) Of course, every day I can save all graphs and their endpoints, if that could help for the task the next day.

(From one day to the next the only changes that occur are new direct successors added to objects that are endpoints and deaths (meaning that we know that the dead object will never have direct successors anymore until its rebirth) and rebirth (meaning that the object can now start to have direct successors.)

What are my options here ?

# Answer
It appears this is an instance of "incremental graph connectivity". There are very efficient algorithms for this.

First, let's identify the weakly connected graph components and keep track of them as the graph changes. In undirected graphs, it's easy to keep track of connected components as you add vertices and/or edges, using a union-find data structure. In particular, each time you add a vertex, you use the MakeSet function to put it in a component of its own, and each time you add an edge, you use the Union function to merge the two associated components. You can use this to keep track of the weakly connected components in your directed graph.

This can be done $O(\alpha(n))$ time per operation (i.e., per vertex or edge added).

Your "ends" are normally called "sink vertices". You can keep track of the "ends" of each weakly connected component by associating a doubly linked list with each component; that list contains all of the sink vertices in that component. Also, each sink vertex should have a pointer to the placed in the doubly-linked list where it appears. When you merge two components, you can concatenate their lists in $O(1)$ time. Also, when you add an edge, you check if this turns a sink vertex into a non-sink; if so, you follow the pointer from that vertex to find its place in the doubly-linked list, and remove it from the doubly linked list. This too can be done in $O(1)$ time. In all, this takes an additional $O(1)$ time per vertex or edge added, which is dominated by the cost of the union-find data structure.
> 0 votes

---
Tags: graphs
---


# Question
Title: O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?
Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.

If

* s = little string and S = len(s)
* b = big string and B = len(b)

then I believe it would be something along the lines of (pseudocode):

```
hs = hash(s)
for every position, substring of length S in B:
    h_sub = hash(substring)
    if hs == h_sub:
         print position

```

Note that the `for` loop will run `B-S+1` times, so whatever happens inside the loop must be O(1) in order for the whole thing to be O(B).

This assumes that there exists a O(1) hash function `hash(s)` that only returns the same hash when two words are permutations of each other, and never collide otherwise.

**What is this hash function?** It seems like you'd have to iterate through every letter in `substring` to calculate `h_sub` and I don't see how that can happen in less than O(S) time. This answer seemed promising but then someone found a non-valid collision.

I learned about the radix-2p hash for this problem in school and we had to prove it as a homework exercise so I am convinced of its correctness.

However in the calculation $k = \sum\_{i=0}^{n-1} x\_i(2^{p})^i$, the exponent on the $2^p$ always changes depending on the position of the letter $x\_i$ within the substring, so I don't see how we can avoid having to iterate anew through all S letters of the substring when we calculate $k \text{ mod } (2^p-1)$.

Am I missing something or is there another approach entirely? Thanks.

# Answer
I think a hash is the wrong approach. Instead you can use auxiliary variables: an array $A$ and an integer $c$. Basically $A$ tracks the error in the number of occurrences of each character and $c$ tracks the number of non-zero errors. Instead of a hash update you update the count of the character which drops out, then update $c$ if it changed from or to zero, then repeat for the character which is coming in. After that, if $c=0$ you found a permutation of $s$.
> 2 votes

# Answer
One simple hash is

$$\text{hash}(s) = s\[0\] + s\[1\] + \dots + s\[n-1\] \bmod p,$$

where $s\[0\],\dots,s\[n-1\]$ are the characters of the string $s$. You could also replace addition modulo $p$ with xor, or any other commutative operation. You also need the hash to be a rolling hash so that you can compute $\text{hash}(B\[i+1..i+k\])$ from $\text{hash}(B\[i..i+k-1\])$ efficiently, but fortunately the above hash functions have that property.

The worst-case running time could be $O(|s| \cdot |B|)$ (because in principle you could have a hash collision in every position), but in practice it will often run in time $O(|B|)$ if the strings $s,B$ aren't "too unfriendly".

If you want stronger guarantees, or just want to heuristically reduce hash collisions, here is a better hash:

$$\text{hash}(s) = \sum\_{i=0}^{n-1} T\[s\[i\]\] \bmod p,$$

where $T\[\cdot\]$ is a lookup table with one entry per possible character value. (For example, if every character is a 8-bit byte, then $T$ is a lookup table with 256 entries.) This hash will have fewer collisions, and still has all the properties needed -- it is commutative and a rolling hash. If you fill in the entries of $T$ randomly, one can prove stronger guarantees: the expected running time will be $O(|B|)$, and the running time will be at most $c \cdot |B|$ with probability exponentially small in $c$ (so in practice the running time can be upper-bounded by something like $100 \cdot |B|$ for all intents and purposes). This is a consequence of the fact that $\Pr\[\text{hash}(s) = \text{hash}(t)\] \le 1/p$ for all $s \ne t$, when $T$ is initialized in this way.
> 1 votes

---
Tags: strings, hash, permutations, substrings
---


title: Doubt in definition of Float

text:
# Question
Title: Doubt in definition of Float
Can anyone tell the meaning of the bold portion?

> Float: It is used to store decimal numbers **(numbers with floating point value) with single precision.**

# Answer
You seem to be asking about some text on this page: https://www.geeksforgeeks.org/data-types-in-c/

The text about the `float` type is intended to say that `float` stores a single precision floating point value. The "single precision" refers to a specific well-known format for storing floating point values in computers; single precision values are 32 bits in size.

Floating point values are values represented internally in a fashion somewhat similar to scientific notation but using 2 instead of 10 as the number raised to a power. The 32 bits are separated in a *sign*, *exponent*, and *mantissa*, and the value stored by a floating point variable is:

$$ (-1)^\mathit{sign} \times 2^\mathit{exponent} \times (1.\mathit{mantissa}) $$

(Technically here, I'm talking about *binary* floating point, but that's what C's `float` type is.)

In a single precision float, the exponent is eight bits wide and the mantissa is twenty-three bits. (the sign is always one bit in any size floating point value)

The practical upshot of this is that you can use `float` variables to store real values that aren't integers; for example 1.5 or 3.14159. You should be aware that the way binary floating point numbers work is sometimes confusing and frustrating to new programmers; a basic guide to those issues can be found at https://floating-point-gui.de/.
> 1 votes

---
Tags: floating-point, c
---


# Question
Title: Expected value of the distance between nodes in a binary tree
If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T?

---

My question here is, how do I correctly approach this question?

---

(Also tell me how to develop numerical skill in algorithm?)

# Answer
> 3 votes
Let's name the nodes $\mathit{node0}$ through $\mathit{node15}$. (with the implication that that's the order of the nodes)

I would approach this problem first by saying "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?" Then I'd ask the question "what if $a$ is $\mathit{node1}$?", etc. Presumably along the way there would be patterns and symmetries I could make use of so I wouldn't need to do a long calculation 16 times.

So let's take that first question: "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?"

First off, the distance between $\mathit{node0}$ and $\mathit{node0}$ is $0$. To $\mathit{node1}$, the distance is $2$. To nodes $\mathit{node2}$ or $\mathit{node3}$, the distance is $4$. To the four nodes $\mathit{node4}$ through $\mathit{node7}$, the distance is $6$. To the remaining eight nodes the distance is $8$.

So the expected distance when $a$ is $\mathit{node0}$ is $(0 + 2 + 2\*4 + 4\*6 + 8\*8)/16 = 6.125$.

Now figure out the expected distance when $a$ is $\mathit{node1}$, and then other nodes. (there is an obvious pattern - prove it)

Then average over those results to find the answer.

Often, you will find a shorter or more elegant solution to a problem as you are working on it. This is normal, and should not be taken as a sign that your initial approach was wrong or that you should have seen the more elegant approach without trying your initial approach first, any more than a writer should expect to write an essay without first writing some notes or a rough draft.

Unfortunately, though writers are often trained in the idea of rough drafts and revisions, solutions to math or computer science problems are usually only presented in their final form without much indication of the bumbling around and blind corners that really went into discovering the elegant explanation.

---
Tags: algorithms
---


title: Implicit nil checks in algorithms

text:
# Question
Title: Implicit nil checks in algorithms
I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms?

To be more precise, I am implementing a red-black tree and the grandparent of a node is passed to a rotation function, but if correctly understand the algorithm, the grandparent might be nil at the time the rotation function is called.

I should probably warp such calls into a conditional block, but I was curious to know if this is common for algorithms to be specified that way, and if there are any additional advices on how to handle those cases.

Thank you

# Answer
The concept of a nil pointer is an implementation detail which is programming language specific. In some implementations, an attempt to accept the grandparent when there is none will just trigger an exception. This hints that the algorithm designer should not worry about nil pointers.

Indeed, in your example, the rotation function should simply not be called on a node with no grandparent. If you use the data structure correctly, then this will simply not happen. There are only two cases in which you would try to rotate a node without grandparent:

* Implementation bug. You haven't coded the algorithm correctly.
* Non-conforming usage. Your program for some reason calls the rotation procedure directly.

If your program is correct and it is used according to the interface of the data structure, then you will never attempt to rotate a node without a grandparent. Therefore if your code is attempting to dereference a nil pointer, you can be sure that there is some bug in your code. During development, you should probably raise an exception. For production code, you should follow whatever convention you do in any other part of your code.
> 7 votes

---
Tags: algorithms
---


# Question
Title: Running time complexity of finding maximal power of divisor that divides natural number
Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of two $b$-digit numbers has time complexity $O(b^{\log\_{3}{5}})$. (Ie. I use the Toom-Cook algorithm.) Then it can be shown that the naive repeated division approach has a complexity that's worse than $O(\log^{2}(n))$.

An alternative I considered is performing a binary search like algorithm on $\\{0, 1, ... \log{n}\\}$, where I assume that $\log{n}$ is given. This means that instead of checking all $\log{n}$ candidate powers, it suffices to consider only $\log{\log{n}}$ elements of the above set of possible powers. For each candidate power $p^f$ a division $p^f \vert n$ is required, which can be performed in $O(b^{\log\_{3}{5}})$. We only need to compute the maximal power of $p$, $p^{\log{n}}$ as we can store intermediate powers (even if we use repeated squaring , precisely because a binary search is performed on our search space). The cost of computing $x^y$ via repeated squaring is $O((y \log{x})^{\log\_{3}{5}})$. Hence the overall complexity of this approach is $$O(\textit{exponentation\_cost} + \textit{division\_costs}) = O((\log{n} \log{p})^{\log\_{3}{5}} + \log{\log{n}} \cdot (\log{n})^{\log\_{3}{5}})$$

Now supposing that $p$ is small relative to $n$, that is $p \in O(\log{n})$, then the above expression belongs $O((\log{n} \log{\log{n}})^{\log\_3{5}})$, which isn't too bad.

My questions are:

1. Does the above analysis look sensible?
2. Is there a standard/better way to do this?

# Answer
> 1 votes
Here is one more approach you could consider, depending on whether you care more about theoretical running time or pragmatic solutions:

1. Use binary search to find the smallest $k$ such that $p^{2^k}|n$ but $p^{2^{k+1}}\not|n$.
2. Compute $m = (n/p^{2^k}) \bmod p^{2^k}$.
3. Recursively find the smallest $i$ such that $p^i|m$ but $p^{i+1}\not|m$.

(In the third step, you know $0 \le i \< 2^k$, so you have a narrower range for your search, and $m$ is smaller than $n$, so you are working with smaller numbers.)

Then it follows that the solution to your problem is $e=2^k + i$.

Note that $k \le \lg {\log n \over \log p}$, so you can find $k$ with binary search in $O(\log \log {\log n \over \log p})$ steps, where each step does a single trial division. In the worst case, $m$ might not be much smaller than $n$, so this might not save you much. But in many cases, $m$ will be vastly smaller than $n$, so step 3 is a lot easier than the original problem. In particular, on average $m$ will be on the order of magnitude of $\sqrt{n}$ or less, so heuristically we might expect that after $\lg \lg n$ recursions we're dealing with constant-sized numbers, and heuristically we might expect the total running time to be dominated by step 1. This won't always be true in the sense of worst-case complexity, though.

# Answer
> 0 votes
If p divides n and p \> sqrt(n) then the maximum power is 1 :-)

Note that if the maximum power is large then p must be small, and the time for division is substantially shorter. I’d first want to know what the practical use of this is. For example if p is 10 digits an n is random, it is very unlikely that the largest power is not 1. If p=2 is start by calculating n modulo 2^30.

---
Tags: complexity-theory, time-complexity, runtime-analysis, arithmetic, number-theory
---


# Question
Title: How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

If I have a recursive function like this for example (This is just an example, its not a real thing, it just demonstrates my question):

```
someFunction(n){
  base case:
    return 0
  if (some case)
    return someFunction(3n/4)
  else if (some other cases)
    return someFunction(n/4)
}

```

As we can see, the recursion calls itself in different cases and in different cases, the n is fractioned by different value, how can I write down the recursive formula for finding out the run time?

Is the formula something like:

```
T(n) = T(3n/4)?
T(n) = T(n/4)?
T(n) = T(3n/4) + T(n/4)?
T(n) = (Probability of first case)*T(3n/4) + (Probability of first case)*T(n/4)?

```

What if I have no idea what is my probability for each case?

# Answer
If you want to find the *worst-case* asymptotic running time, then you can't use probabilities; you have to assume that at each branch, it takes the slower path. Thus you get a recurrence relation

$$T(n) = \max(T(3n/4), T(n/4)) + O(1).$$

If you want to find the *expected* running time, then you can use probabilities:

$$T(n) = p\_0(n) T(3n/4) + p\_1(n) T(n/4) + O(1)$$

where $p\_0(n)$ is the probability of taking the "then" branch and $p\_1(n)$ is the probability of taking the "else" branch. If you don't know the probabilities, this kind of analysis won't be useful and you presumably won't be able to calculate the expected running time. There are some important caveats here as well; the random choice must depend only on internal random choices of the algorithm, not on $n$, or else funny things can happen.

Solving the recurrence relations above is a separate matter. Often it suffices to apply the master theorem.

Normally, in theoretical computer science, if we are talking about asymptotic running time, the default assumption is that you are talking about worst-case running time. If you want to focus on something else (e.g., expected running time), it's important to state that explicitly, otherwise you might cause confusion among readers.

Since you seem to lack some basic understanding of running time analysis, I suggest studying big-O notation, running time analysis, and recurrence relations. This is a slightly tricky example, and it's not the simplest one to start with to start learning the subject. We do have some resources on that subject here; see, e.g., How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Sorting functions by asymptotic growth, Is there a system behind the magic of algorithm analysis?, Solving or approximating recurrence relations for sequences of numbers, and a good algorithms textbook.
> 1 votes

# Answer
Well, it is called maths. You’d have to figure out when and how often “some case” and “other case” happens, if there is a system that you can detect, and so on. For an upper bound, you may assume that you always take the branch that takes longer; that upper bound might be much too high.

Once you encounter problems that don’t fit into well-known patterns, you just have to handle them individually.
> 0 votes

---
Tags: runtime-analysis, recurrence-relation, big-o-notation
---


# Question
Title: Communication complexity: fooling set bound for inner product function
I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n) $$

$D(IP)$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $n^2$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.

# Answer
> 0 votes
Let $(x\_i,y\_i)$ be a fooling set for inner product, of size $m$. Construct an $m \times n$ matrix $X$ whose rows are $x\_i$ and an $n \times m$ matrix $Y$ whose columns are $y\_i$, and consider the matrix $M = XY$ (arithmetic is over the field $\mathbb{F}\_2$). The decomposition $M=XY$ shows that $M$ has rank at most $n$.

Suppose first that $\mathrm{IP}(x\_i,y\_i) = 1$ for all $i$, and so for each $i \neq j$, either $\mathrm{IP}(x\_i,y\_j) = 0$ or $\mathrm{IP}(x\_j,y\_i) = 0$. Consider the Hadamard (entrywise) product of $M$ and $M^T$. It is known that rank is submultiplicative with respect to entrywise product, and so the rank of $M \circ M^T$ is at most $n^2$. On the other hand, $M \circ M^T$ is the identity matrix, and so has rank $m$. We conclude that $m \leq n^2$.

When $\mathrm{IP}(x\_i,y\_i) = 0$ for all $i$, we consider the matrix $M' = M+J$, where $J$ is the all ones matrix. Since $J$ has rank 1, the rank of $M'$ is at most $n+1$, and so the argument in the preceding paragraph shows that $m \leq (n+1)^2$.

---
Tags: communication-complexity
---


# Question
Title: Smallest convex set containing given point
Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is there an (efficient) algorithm that finds $n+1$-subset of $M$ with smallest convex hull that contains $x$ (or, $k$-subset for some $k \< n + 1$ if such exists)? "Smallest" is defined according to the volume in $R^n$ (or $R^{k-1}$). "Efficient" would imply something much better than the brute force strategy that examines all $n+1$-subsets of $M$.

# Answer
Here is an idea to find a "smallish" simplex containing your given point $x$. It does not find a smallest simplex (except by luck).

Construct the convex hull $H$ of your set of $M$ points. For each $p$ of your set $M$, shoot a ray from $p$ through $x$ until it hits a facet $F$ of $H$. Then $F \cup p$ is a simplex containing $x$. Repeat for all $p \in M$ and retain the smallest volume simplex.

It is easy to create examples where this is terrible, as it is biased toward a simplex containing a facet of the hull. One can imagine various heuristics to improve, for example, discarding from $M$ the vertices of $H$ and repeating.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: What is the asymptotic complexity of the following code snippet?
```
for (i = 2; i < n; i = i * i) {
  for (j = 1; j < i / 2; j = j + 1) {
    sum = sum + 1;
  }
}

```

I know that the outer loop can run for a maximum of $n^2$ times and the inner loop will run for $\frac{n^2}{4}$ times.

# Answer
> 1 votes
The second loop runs in $O(i)$. The first loop goes over the powers $2^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is $$ O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}), $$ where $m$ is the maximal integer such that $2^{2^m} \< n$. We can bound $$ 2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} \< 2n. $$ Therefore the overall running time is $O(n)$.

In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log\_2 \log\_2 (n-1) \rfloor}})$, with a bit more work.

# Answer
> 0 votes
Since $i$ iterates in powers of $2$ to reach a value $n$. The average complexity will be $log\_{2}(n)$ only for outer loop.

But when $i$ = $2$ ,its value will raise in terms of powers of $2$ .The same will be true for inner loop iterations(Let's just ignore the divided by $2$ factor since $2$ is a constant). The total running time in terms of number of iterations of inner loop can be summed as

$i^1 + i^2 + i^3 + \cdots + i^{log\_{2}(n)}$

OR

$2^1 + 2^2 + 2^3 + \cdots + 2^{log\_{2}(n)}$.

But for any positive integer $x,$ $2^1 + 2^2 + 2^3 + \cdots + 2^{x-1}= 2^{x}-2$. So the total number of steps will be

$2\*2^{log\_{2}(n)}-2$

Now because $2^{log\_{2}(n)}=n$ we can write the number of steps as

$2n-2$

Ignore all constants you get the complexity $O(n)$

# Answer
> 0 votes
You are asking for asymptotic complexity. O(n) is obviously an upper bound. However, for every epsilon there are plenty values of n that execute in less than n * epsilon steps, so that upper bound is quite useless. “N^2/4” is *way* off the mark. For example, for 257\<= n\<= 65536, there are only about 256 steps, far less than n.

Let f(n) = floor (log(log(n))), where log is the base 2 logarithm. Let g(x) = 2^(2^x)), then the asymptotic complexity is $\Theta(g(f(n))$

PS. Yuval is right, it’s floor(log(log(n-1)), not n.

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Proof of Brzozowski's algorithm for DFA minimization?
Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it correct? Any proof accessible to CS undergraduates would be very welcome.

# Answer
> 9 votes
The proof of Brzozowski's result is technical, but not very complicated. In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-determinization.)

First one needs some good view of the different automata involved. And nerves of steel.

**The construction of Brzozowski.** Let $A = (Q, \Sigma, \delta, q\_0, F)$ be a deterministic automaton for the language $L=L(A)$. We assume that all states of $Q$ are reachable from the initial state $q\_0$.

In the first step one reverses the automaton: all edges are inverted, and inital and final states are swapped. Informally we get the automaton $\mathrm{rev}(A) = (Q, \Sigma, \delta^{-1}, F, q\_0)$.

In the second step one determinizes the automaton so obtained, by the standard construction, but keeping only reachable states. We get $A'= \mathrm{det}(\mathrm{rev}(A)) = (Q', \Sigma, \delta', q'\_0, F')$. The states of $A'$ are sets of states for $\mathrm{rev}(A)$: $Q'\subseteq 2^Q$; the initial state consists of the initial states for $\mathrm{rev}(A)$, which are final states in $Q$: $q'\_0 = F$; the final states in $A'$ are the states that contain a final state for $\mathrm{rev}(A)$: $U\in F'$ iff $q\_0\in U$.

The key of the proof is the following important relation between automata $A$ and $A'$.

> **Basic Observation:** *$q\in \delta'(X,w^R)$ iff $\delta(q,w) \in X$*.

**Proof** (one side only). $q\in \delta'(X,w^R)$ iff there exists a state $p$ in $X$ and a path from $p$ to $q$ in $\mathrm{rev}(A)$ with label $w^R$. But that means there is a path from $q$ to $p$ with label $w$ in $A$, or $\delta(q,w) = p$; thus $\delta(q,w) \in X$. **end-of-proof.**

As announced, this is used to prove the essential property we need.

> **Property:** *$A'$ is minimal* (and deterministic for $L^R$).

**Proof.** Let $U$ and $V$ be two states in $A'$ that cannot be distinguished. This means that for any string $w^R$ we have $\delta'(U,w^R) \in F'$ iff $\delta'(V,w^R) \in F'$. We show that now $U$ and $V$ are equal.

By the construction of $F'$ we can rephrase indistinguishability as $\delta'(U,w^R) \ni q\_0$ iff $\delta'(V,w^R) \ni q\_0$.

Apply the Basic Observation, and we have $\delta(q\_0,w) \in U$ iff $\delta(q\_0,w) \in V$.

From this equality $U=V$ follows, as all states in $Q$ are assumed to be reachable, thus for any state $p$ in $U$ or $V$ there is a string $w$ such that $p = \delta(q\_0,w)$. **end-of-proof.**

But even after proving, the result is still real magic!

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: FSM (Finite State Automaton and PDA (Push Down Automaton
Say we have the following language, some number of a's and b's followed by three a's followed by some number of a's and b's

Show how you can create a finite state machine that will accept the words in the language and reject words, not in the language. Show the transition rules.

Show how you can create a PDA or push down automata that will accept the words in the language and reject words, not in the language. Show the transition rules.

# Answer
> 0 votes
Clearly the regular expression is `(a+b)*aaa(a+b)*`; one can now draw DFA/NFA based on this!
For the PDA one can do as follows: having a DFA/NFA write the same transition rules for PDA while having somy dummy stack operation (say pushing the symbol into the stack; and never pop it out) finally accept by final state in PDA (one can now empty the stack if required; and accept via empty stack)

---
Tags: algorithm-analysis
---


# Question
Title: Minimizing catastrophic risk in Gale-Shapley matching
In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much larger than the total number of residency slots available - several students are left unmatched.

If a particular student's primary concern is simply matching *somewhere*, is there any strategy they can adopt that outperforms ranking hospitals according to their true preference?

# Answer
(In theory) No, no other strategy will help. In the student-proposing version of the deferred acceptance algorithm, it is a theorem\[0\] that each student's optimal action is to report her true preference order. It's a dominant strategy, meaning this is optimal regardless of what others submit. This implies that if the student is unmatched when submitting her true preferences, then there is no other submission she could make that would have gotten her matched\[1\].

Note deferred acceptance still works for weak preference orderings (see \[0\]), so e.g. here the student is indifferent between all hospitals and prefers them all to being unmatched. The dominant-strategy guarantee of deferred acceptance still holds.

(In practice) In practice, students don't interview or rank all possible hospitals. So a student could likely improve her chances by trying to interview and rank mostly lower-prestige programs where the competition is lower.

\[0\] e.g. Theorem 8 of the survey by Al Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. https://web.stanford.edu/~alroth/papers/GaleandShapley.revised.IJGT.pdf

\[1\] I am assuming she prefers any match to being unmatched.
> 2 votes

# Answer
The following is not rigorous, but I believe it illustrates why the student's preferences should be true.

The relevant conditions can be reduced to the following. For every program with N slots, a student will be ranked either 1) in the first N slots, 2) in the remaining slots, or 0) not at all. If the student is in group 2, then the outcome is "conditional" - it depends how many of the program's preferred students matched elsewhere.

If we make a table of two programs' grouping for a given student, and designate a definite match with a capital letter, and a conditional match with a lower case letter, we get the following:

If student ranks A over B

```
B\A 1   2   0
1   A   aB  B
2   A   ab  b
0   A   a   -

```

If student ranks B over A

```
B\A 1   2   0
1   B   B   B
2   bA  ba  b
0   A   a   -

```

You can see that each table has the same number of matches and the same number of conditional matches. The only difference is that 4 of the 9 scenarios end with a preference for the program ranked highest.

Even if you have an oracle and can predict in which programs a conditional acceptance will succeed or fail, there is no advantage to switching order. If you change all the conditionals to either guarantees or no-matches, the total chance of matching still does not change. What changes is the chance of getting the school you want. If for example 'a'-\>'-' and 'b'-\>'B', then putting B first means matching with A in only 1 of 7 successful scenarios instead of in 3 of 7.

This should generalize to more than 2 programs. If B is the program being ranked higher than the true preference, then A stands for any other program which may rank the student.

The only way to maximize chance of matching is to maximize the number of programs applied for. *(And attempt to maximize one's position on each program's ranking of candidates, but that's not a science problem).*
> 0 votes

---
Tags: algorithms, graphs, matching, bipartite-matching
---


# Question
Title: Why object non-optional ignore its weak property? [Swift]
I have 2 classes **Car** and **Owner**, they have weak preference to each other. After I assign nil to one object. That object is still not deallocated. Like code bellow, as far as I understand object **vinfast (Car)** must be deallocated because its reference count equal zero.

Especially is if I change **james (Owner)** to optional, it works. **james** is non-optional, it doesn't work.

Can someone help me explain why **vinfast (Car)** is deallocated if and only if **james (Owner)** is optional?

```
import Foundation

class Car {
    var model: String
    weak var owner: Owner?

    init(model: String) {
        self.model = model
        print("Car is being allocated")
    }

    deinit {
        //is not called
        print("Car have been deallocated")
    }
}

class Owner {
    weak var car: Car?
}

var vinfast: Car? = Car(model: "Go1")
let james: Owner = Owner()
james.car = vinfast
vinfast = nil

```

Output:

> Car is being allocated

# Answer
I just found that it belongs to Playground issues (Swift 4.2), after I create small project and put it inside. The code run as well, that object is deallocated.
> 0 votes

---
Tags: memory-management
---


# Question
Title: Proof of NP Completeness of set-partition problem
I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help.

# MY METHOD

In subset sum problem we have to find a subset $S\_1$ of set $S$ so that it sums to a number $t$ and in set partition problem we need to find a subset $X\_1$ of set $X$ such that summation of numbers in set $X\_1$ is half of that in $X$.

So let us take instance of subset sum problem where $t = (\text{sum of numbers in }X) / 2$. If we can solve the set partition problem than we solved the subset sum problem too. But we know that subset sum is NP Complete so subset sum problem is also NP Complete (I know how to prove it is NP).

I am having doubt whether we can make a choice of $t$ like that or not. Please help.

# Answer
No, your can't arbitrarily choose $t$ so your proof is incorrect.

In fact, you have build a reduction from the following variant of subset sum problem to partition problem:

> Given a set $S$ of integers whose sum is $s$, is there a subset of $S$ whose sum is $s/2$?

This variant is different from the normal subset problem, and you cannot assert it is NP-complete (though it in fact is), so your proof is incorrect.

You can find a complete proof here.
> 1 votes

---
Tags: np-complete, check-my-answer, subset-sum
---


# Question
Title: What does Stroustrup mean by 7/8ths of MIPS being in the vector units?
In his article Software Development for Infrastructure Stroustrup states the following:

> Hardware improvements make the problems and costs resulting from isolating software from hardware far worse than they used to be. For a typical desktop machine,
>
> * 3/4ths of the MIPS are in the GPU;
> * from what’s left, 7/8ths are in the vector units; and
> * 7/8ths of that are in the “other” cores.
>
> So a single-threaded, nonvectorized, non-GPU-utilizing application has access to roughly 0.4 percent of the compute power available on the device (taken from Russell Williams).

Now I understand the GPU and threading issues of performance. But since threading and vectorization are mentioned as separate things, I would like to know what does it exactly mean when you say that vector units are X% of the computing power.

# Answer
Imagine you have a 256 bit vector floating point unit which can perform eight 32 bit operations in parallel. How many operations per second can you perform with or without using the vector FPU?

Imagine you have eight cores. How many operations can you perform in one second using one core or all eight cores?
> 1 votes

# Answer
Typical desktop machine may include:

* 2 TFLOPS mid-class desktop GPU
* 4-core CPU with 512 GFLOPS total in AVX2 units, and 64 GFLOPS total in scalar units. Single-threaded, scalar code has only access to 16 GFLOPS
> 1 votes

---
Tags: optimization
---


# Question
Title: Can all $O(n)$ problems be solved without nested loops?
There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a question, can all such implementations be simplified or converted to an implementation with only top layer loops? Namely, can all problems that have an $O(n)$ algorithm be solved with an algorithm without nested loops?

# Answer
> 4 votes
You can write an interpreter for any reasonable instruction set usin a single loop with a very, very long if/ else if / else if... statement. That should cover about all solvable problems. You can calculate the Ackerman function with one loop without recursion (not in the lifetime of the universe for n \>= 4, but in principle).

---
Tags: algorithms, complexity-theory, time-complexity, asymptotics
---


# Question
Title: Is it possible to make partition of Quicksort run in O(lg n)?
I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.

# Answer
No. The partition operation must access every item in the list: if there is any item it does not look at, then you don't know which side of the partition it belongs on. Consequently, the partition operation cannot run any faster than $O(n)$ time, where $n$ is the length of the list.
> 3 votes

# Answer
No, this doesn't work. Whatever method it uses, your partitioning still has to look at every element of the list, even if that's hidden inside recursions.

Mathematically, you're confusing the recurrence $T(n)=2T(n/2)+c$ with the binary search recurrence $T'(n)=T'(n/2)+c$. $T'=\Theta(\log n)$ but $T(n)=\Theta(n)$. In binary search, you only have to recurse on one half; having to visit both halves kills you.

In fact, it's probably even worse. Saying that your partitioning scheme runs in time $T(n)=2T(n/2)+c$ is saying that you can combine the partitions of the two halves in constant time. The only way I can think of doing that would be using some kind of linked list data structure. But then splitting the list requires finding the middle, which is still $\Theta(n)$. Maybe you could do something with binary trees but, man, this is getting complicated and your best possible outcome is a complicated way of getting the $\Theta(n)$ partitioning time we already had with the simple algorithm on an array.
> 1 votes

---
Tags: quicksort
---


# Question
Title: How to partition a set in order to minimize the number of the elements and their interactions?
Given two sets $S\_1$ and $S\_2$ of $n$ elements each. Each set $S\_1$ (resp. $S\_2$) has a revenue $R\_1$ (resp. $R\_2$). Each element $i$ of $S\_1$ (resp. $S\_2$) has a gain $g\_{i1}$ (resp. $g\_{i2}$). From set $S\_1$ (resp. $S\_2$), choose a subset of elements $O\_1$ (and $O\_2$) such that:

* $\sum\_{i\in O\_1}g\_{i1}\geqslant R\_1$;
* $\sum\_{i\in O\_2}g\_{i2}\geqslant R\_2$;
* $|O\_1|+|O\_2|+|O\_1\cap O\_2|$ is minimized.

Can we solve this problem in polynomial-time?

I started by a greedy approach which chooses the elements by increasing order of their gains. I tried few examples but this does not provide optimal results.

I am now trying to prove that it is NP-hard using a reduction from PARTITION. Any hints?

# Answer
Consider the following two variants of subset sum problem:

# Variant 1

> Given a set of $2n$ positive integer elements and a positive integer target $W$, is there a subset with size $n$, whose sum is $W$?

# Variant 2

> Given a set of $n$ positive integer elements and a positive integer target $W$, where $(\text{the maximum element})\< 2\times(\text{the minimum element})$, is there a subset whose sum is $W$?

Variant 1 is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Variant 2 is also NP-hard by a reduction from Variant 1. Given an instance of Variant 1, we add a large enough integer $M$ to each element so that the new elements satisfy the constraint in Variant 2. Now the answer to Variant 1 is "yes" if and only if there is a subset of the new elements whose sum is $W+nM$ (since $M$ is large enough, the subset must have size $n$).

Now we show a reduction from Variant 2 to (the decision version of) your problem, so your problem is NP-hard.

Given an instance of Variant 2, we construct $S\_1=S\_2$ as the same set as the given instance. Let $s$ denote the sum of all elements. We set $R\_1=W$ and $R\_2=s-W$. The gain of each element is the same as itself.

Now if there is a subset $O\subseteq S\_1=S\_2$ whose sum is $W$, then we can choose $O\_1=O$ and $O\_2=S\_2\backslash O$, meaning there is a solution to your problem with $|O\_1|+|O\_2|+|O\_1\cap O\_2|\le n$.

On the other hand, if there is a solution to your problem with $|O\_1|+|O\_2|+|O\_1\cap O\_2|\le n$, then $2|O\_1\cap O\_2|\le n-|O\_1\cup O\_2|$. Let $\min$ and $\max$ be the minimum and maximum elements respectively. We have $$\sum\_{e\in O\_1\cap O\_2}e\le |O\_1\cap O\_2|\max\le 2|O\_1\cap O\_2|\min\le(n-|O\_1\cup O\_2|)\min\le\sum\_{e\notin O\_1\cup O\_2}e.$$

This means $$ \sum\_{e\notin O\_1}e=\sum\_{e\in O\_2}e-\sum\_{e\in O\_1\cap O\_2}e+\sum\_{e\notin O\_1\cup O\_2}e\ge \sum\_{e\in O\_2}e\ge s-W. $$

Note $\sum\_{e\in O\_1}e\ge W$ and $\sum\_{e\notin O\_1}e+\sum\_{e\in O\_1}e=s$, we have $\sum\_{e\in O\_1}e=W$ and $\sum\_{e\notin O\_1}e =s-W$, which means there is a subset $O\subseteq S\_1=S\_2$ whose sum is $W$.
> 2 votes

---
Tags: algorithms, np-complete, np-hard, knapsack-problems
---


title: Regular grammar with at most one c

text:
# Question
Title: Regular grammar with at most one c
I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression `((a|b)*|c)(a|b)*` but am unsure where to go from here; my previous attempts have ended up allowing multiple c's.

The solution I has gives (N={s,t}, T={a,b,c}, s, R), s→є, s→as, s→bs, s→ct, t→at, t→bt, t→є, however I do not see how this limits the number of c's generated to at most 1.

# Answer
The rule s-\>ct can only be done once, becuase after that there is no more s left, and from t you cannot generate more s. Thus at most one c can be generated, because no other rule generates c.

Also the rest of the grammar looks fine.
> 0 votes

# Answer
You should reason: It contains no $c$ or one $c$.

If no $c$, it is $(a|b)^\*$.

If exactly one $c$, it has "no c" before the lonely $c$ and "no c" after, i.e., $(a|b)^\*c(a|b)^\*$.

Join them to get $(a|b)^\*|(a|b)^\*c(a|b)^\*$. Or you could factorize to give $(a|b)^\*(\epsilon|c(a|b)^\*)$.
> 0 votes

---
Tags: regular-languages, formal-grammars
---


title: Complexity of an encoded turing machine

text:
# Question
Title: Complexity of an encoded turing machine
This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it.

First, we have the variable `m` which is a binary encoding such as `100#001#010` which is translated to `[4, 1, 2]`

Next is the variable `n` = the total length of the input/encoding

And `k` which is the largest number in the list (4 in the previous list)

Now we set $f(n)$ as the turing machine that took `m` as input, and want to see if $f(n) = O(g(n))$ where $g(n)$ is a polynomial.

How can I solve this on $f(n) = m (log (n)) (log (k))$?

# Answer
> 1 votes
Your question is rather unclear but I think it's something like this:

> I have a Turing machine and I want to figure out if it runs in polynomial time. That means that its running time must be bounded by a polynomial function of the input's length. I've figured out an expression for its running time but this expression is in terms of, e.g., some of the numbers represented in the input, and not just the input's length. How do I proceed from here?

So you've computed a running time that's something like $f(n, x\_1, x\_2, ...)$ where the $n$ is the input length and the $x\_i$ are other quantities associated with the input. What you need to do is bound how big those quantities in terms of $n$ and then substitute those bounds into&nbsp:$f$, to obtain a function whose only input is $n$.

For example, your input includes a list of numbers. That list could have as many as roughly $n/2$ entries, since it could be $0\\#0\\#0\\#\ldots$. If the list has just one entry, that number has roughly $n$ bits, so the biggest number in the list could be as big as $2^n$ or so.

In other situations, you might know more about the input. Perhaps the entries in the list all have to be different. Then the input can't be $0\\#0\\#0\\#\dots$ and the entries themselves have to get longer than just one bit. If you had $k$ entries in the list, they'd need about $\log k$ bits each, at a minimum, so you'd have $k\log k\leq n$, which you can try to solve and use.

Then, substitute everything you get into $f$ and see what you get. For the example you have in your question, it's something like $|m|=\Theta(n)$, $k=\Theta(2^n)$, so $|m|(\log n)(\log k)$ is about $n(\log n)(\log 2^n) = n^2\log n$.

---
Tags: complexity-theory, turing-machines, polynomial-time
---


# Question
Title: Find K-subset that includes the most W-subsets
I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma\_0, \ldots, \sigma\_{N - 1} \subset S$, each with $W \ll N$ elements. Subsets can overlap partially or totally.

For a given $K \< N$ (but $K \gg W$), I want to determine the subset $X\_K \subset N$ so that:

* $X\_K$ has $K$ elements.
* $X\_K$ includes the largest possible amount of subsets among $\sigma\_0, \ldots, \sigma\_{N -1}$.

Example:

$S = \\{A, B, C, D, E\\}$, $W = 3$

$\\{\sigma\_0, \ldots, \sigma\_4\\}= \\{\\{A, B, C\\}, \\{A, B, C\\}, \\{B, C, D\\}, \\{A, B, E\\}, \\{A, B, D\\}\\}$

$X\_4 = \\{A, B, C, D\\}$ (as it includes $\sigma\_0, \sigma\_1, \sigma\_2$ and $\sigma\_4$)

What is the best algorithm to find $X\_K$?

# Answer
I had the same problem a few days ago and I used the following heuristic to do it. According to my first impression it seems to work.

My specific use case was to determine a strategy in which sequence I should convert function implementations from one programming language into another so that we can execute as many test runs with as little effort as possible (in this case the set of functions is $S$ and the test runs are $\Sigma$ and our goal is to cover as many $\sigma \in \Sigma$ as possible with as few elements from $S$ as possible).

# Example Data

So let's setup some example data. We have five sets $\sigma$ with different elements inside.

$$ \sigma\_1 = \\{s\_1, s\_3, s\_4\\} \\ \sigma\_2 = \\{s\_1, s\_5, s\_6\\} \\ \sigma\_3 = \\{s\_1, s\_3 \\} \\ \sigma\_4 = \\{s\_1, s\_3, s\_4, s\_5, s\_6\\} \\ \sigma\_5 = \\{s\_1, s\_2, s\_3, s\_6\\} $$

# My Current Approach

I give each $s\_j$ a rating based on the total number of time it exists. Then I check how many elements each $\sigma$ contains. I will then calculate the division between these two numbers and select the $\sigma$ with the highest rating as first winner.

In my opinion this should give me the *quick win* sets first. I will get at least one set covered and I try to trade-off between trying to get the smallest set first, and trying to select the $s$ that are used the most (i.e. with which I could probably cover the most $\sigma$).

Let me explain this approach on the example above. If we count the number of occurrences for each $s$, we get:

$$ \text{Usages}(s\_1) = 5 \\ \text{Usages}(s\_2) = 1 \\ \text{Usages}(s\_3) = 4 \\ \text{Usages}(s\_4) = 2 \\ \text{Usages}(s\_5) = 2 \\ \text{Usages}(s\_6) = 3 $$

If we use these and the number of elements in each $\sigma$ we get the following ratings:

$$ \text{Rating}(\sigma\_1) = \frac{\text{Usages}(s\_1) + \text{Usages}(s\_3) + \text{Usages}(s\_4)}{3} = \frac{5 + 4 + 2}{3} = \frac{11}{3} = 3.67 \\ \text{Rating}(\sigma\_2) = \frac{5 + 2 + 3}{3} = \frac{10}{3} = 3.33 \\ \text{Rating}(\sigma\_3) = \frac{5 + 4}{2} = \frac{9}{2} = 4.5 \\ \text{Rating}(\sigma\_4) = \frac{5 + 4 + 2 + 2 + 3}{5} = \frac{16}{5} = 3.2 \\ \text{Rating}(\sigma\_5) = \frac{5 + 1 + 4 + 3}{4} = \frac{13}{4} = 3.25 $$

In this case, I would add the elements $\\{s\_1, s\_3\\}$ to my set $X\_k$ first.

For the next iteration I would delete $\sigma\_3$ from the candidates and repeat the process.

# Related Problems

I think that is problem is closely related to the *set cover problem*. However, it is different and I did not find a way to convert my problem into a set coverage problem. It also was different to any other algorithm I found in the area of set cover problem (e.g. set packing, dominating set, maximum coverage problem). Maximum coverage problem seems to come very close, but it is again a bit different.
> 1 votes

---
Tags: algorithms, optimization, sets
---


# Question
Title: If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a **black box** and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

**If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.**

# Answer
For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
> 30 votes

# Answer
It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
> 25 votes

---
Tags: algorithms, np-complete, reductions, traveling-salesman, sudoku
---


title: NP-hard in what parameter?

text:
# Question
Title: NP-hard in what parameter?
I often read statements such as "the run-time of algorithm X is polynomial **in m and n**". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one parameter but not the other one, so if this is not the case, it is important to emphasize that it is polynomial in both parameters.

However, I have never read a statement such as "the problem is NP-hard **in m and n**". A problem is always claimed to be NP-hard, period. My first question is: why? Apparently the same rationale is true here too: a problem may be NP-hard in one parameter, but at the same time, it may have an algorithm with run-time polynomial in the other parameter.

My second question: what is an accurate description of a problem with two parameters: $m$ and $n$, that (1) for a fixed $m$, can be solved in time polynomial in $n$, (2) for a fixed $n$, it is NP-hard (with respect to $m$)?

# Answer
> 3 votes
> A problem is always claimed to be NP-hard, period.

Indeed, a problem's definition already contains a specification of its parameters. (See the entries in Richard Karp's seminal collection of NP-complete problems for several examples.) Usually, there is no need to make explicit reference to the parameters *per se*, as they are "automatically scaled" by the input length; for your two parameters $m$ and $n$, for instance, the input could simply be encoded as $0^m1^n$. Hence, for abstract problem instances, it usually suffices to refer strictly to the input length, which is indeed how time complexity is defined (i.e., as the number of computation steps as a function of the input length).

Studying how different requirements on the parameters impact the problem's complexity is the object of study of parameterized complexity theory. For example, the set of SAT formulas with $k$ many variables, $k$ being a fixed parameter (i.e., constant), is decidable in polynomial time (in the formula's length); in parameterized complexity terms, this means SAT is *fixed-parameter tractable*. It is only as the number of variables is also allowed to scale (in the input length) that SAT becomes NP-hard.

# Answer
> 2 votes
The question is "**NP**-hard in what parameter?". In fact, we can also ask "**P** in what parameter?", "**NP** in what parameter?" and "**NP**-complete in what parameter?". In fact, a better question might be "**P** or **NP** or **NP**-complete or **NP**-hard in which input?"

### Formal definitions

Here are the formal definitions of **P**, **NP**, etc as copied and slighted edited from Wikipedia. (In fact, these definition are not very formal. They are just formal enough for this exposition.)

> The class **P** consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input.
> The class **NP** consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.
> A **NP**-complete problem is a problem in **NP** to which any other problem in **NP** can be reduced in polynomial time.
> A decision problem $H$ is **NP**-hard when for every problem $L$ in **NP**, there is a polynomial-time reduction from $L$ to $H$.

Readers should review the formal definition of a decision problem and a polynomial-time reduction as well. Note the polynomial-time reduction above means many-one reduction, a.k.a. Karp reduction instead of other kinds of reductions.

### In which input (in which parameter)?

> A problem is always claimed to be NP-hard, period. My first question is: why? Apparently the same rationale is true here too: a problem may be NP-hard in one parameter, but at the same time, it may have an algorithm with run-time polynomial in the other parameter.

Since we should have specified the input when we define a decision problem, possibly implicitly, there is no need to repeat what are the input when we say that problem is in $P$ or in **NP** or **NP**-complete or **NP**-hard. In fact, we should not mention what are in the input again in order to avoid duplicate data/specification. That is why we see lots of statement like "that problem is **NP**-hard", period.

It is, on the other hand, important to make sure what are the inputs. For example, a previous version of a question about NP-completeness does not specify very clearly the inputs, which in their default format render the problem unlikely in $NP$. The question was updated to specify that one of the input values should be given in unary.

### Family of decision problems

What about a family of decision problems? For example, suppose we have a decision problem $p(s,t)$ for all $(s,t)\in \Bbb N\times\Bbb N$ such that

* for fixed $s$, problem $h\_s$ that is the union of all problems of the form $p(s,t)$ is **NP**-hard and
* for fixed $t$, problem $e\_t$ that is the union of all problems of the form $p(s,t)$ is in **P**.

We can just describe the situation like the above formally, or more or less. Let $p$ be the union of all $p(s,t)$. Informally, we could also say problem $p$ is in $P$ for fixed $t$ and **NP**-hard for fixed $s$, as shown in the second question.

It is correct to say that $p$ is also **NP**-hard, since $p$ contains, for example, $h\_3$ that is **NP**-hard. However, that statement is weaker than "$h\_s$ is **NP**-hard for all $s$".

Furthermore, we can have, of course, more than 2 parameters to specify a family of decision problems. The usage will be similar. For example, we could have a family of problems $p(s,t,u)$ which is in **P** for fixed $s$ and $t$ and which is **NP**-hard for fixed $u$.

# Answer
> 1 votes
There is no such thing as "**NP**-hard with respect to some parameter".

A problem $X$ is **NP**-hard if, for every $Y$ in **NP**, there is a polynomial-time Turing machine computing a function $f$ such that $y\in Y$ if, and only if, $f(y)\in X$. That Turing machine running in polynomial time means that it runs in time $|y|^k$ for some $k$.

Notice that this has nothing to do with any parameter of the **NP**-hard problem $X$, and it can't depend on parameters of the **NP** problem $Y$ because there have to be reductions from *every* **NP** problem.

---
Tags: terminology
---


# Question
Title: Prove that the next multiple of 4 is obtained using the next formula
I was reading an assembly procedure that needed to align addresses on 4 bytes boundary for performance reasons so it has used the next statement that i formulated as a theorem to be proven.

Let $s$ be an integer that is not a multiple of 4 ($s \\% 4 \neq 0$). $m$, the first next multiple of 4 such that $m \gt s$ is obtained using the following formula, where the operands are expressed in base 2 (Binary): $m = s + (\lnot s \land 11)$ ($\lnot a$ will return the 2's complement of $a$).

How to prove that ?

# Answer
Suppose that $s = 4a+b$, where $0 \leq b \< 4$; by assumption, $b \neq 0$. If the numbers are $n$ bit long, then $\lnot s = 2^n - s = 4(2^{n-2}-a) + (4-b)$. Since $b \neq 0$, the last two bits of $\lnot s$ will be $4-b \in \\{1,2,3\\}$. Therefore $(\lnot s) \land (11)\_2 = 4-b$. Adding this to $s$, we get $4a+b+4-b = 4(a+1)$.
> 1 votes

---
Tags: arithmetic, binary, assembly
---


# Question
Title: Help with understanding why we need an expectation in the loss
I am reading the paper SV2P - Stochastic Varaiational Video Prediction (https://arxiv.org/abs/1710.11252). In it the authors use the loss shown in the image:

Why do we need expectation in the reconstruction loss? I think that the loss is similar to the one used in the VAE paper.

# Answer
> 1 votes
It's because $z$ is a random variable, and the term is a function of $z$. So, without the expectation, the $\log$ term would be a random variable, and you can't use that as a loss; the loss needs to be a number. You *can* use its mean (its expectation).

---
Tags: machine-learning, research
---


# Question
Title: Combinatorial Optimization: Shortest distance given sets of drivers and riders
**Problem:**

I have 2 sets, one of ***drivers*** and one of ***riders***. All my participants need to reach one common ***destination***. I wish to calculate the ***shortest combined distance*** in order for all participant to reach said destination. Although the goal is not to reduce the number of cars, drivers can be considered as passengers if the resulting distance is smaller.

**Constraints:**

* Riders and drivers have distinct starting locations
* All participants must reach the destination (common to all)
* The riders need to be picked up by a driver
* The drivers' cars have limited capacity and the capacity is individual to each car

---

I'm failing to understand what type of problem I'm facing, and I'm seeking some help.

1. **Vehicle Routing Problem**

I've thought of solving it as the Vehicle Routing Problem. A Capacitated Open Vehicle Routing Problem (COVRP) to be more exact. Drivers would act as the vehicle fleet and riders as the customers. A capacitated version because cars have limited seats, and an open version because drivers depart from unique positions and don't return to the "depot" but instead end on the destination.

**Problem:** In the VRP, not all vehicles of the fleet are used, and the remaining ones are left in their respective "depots". For my problem, I would need all participants to reach the final destination, so I need for existing vehicles to be considered as possible pick-ups for other vehicles.

I could just send the remaining drivers straight to the destination. But that wouldn't really provide a minimum distance solution to my problem, as better ones could be accomplished if the drivers could serve as customers.

2. **Minimum Spanning Tree**

As an MST problem, I could use the destination as the root and my participants (drivers and riders) as nodes. Each sub-graph originating from the root would be a cluster to be picked up by a driver.

**Problem:** The sub-graphs aren't guaranteed to have a driver's node in one end (to be used as a starting point and prevent doubling back on edges), and the sub-graphs may have paths with more nodes than available seats.

The capacitated MST variant introduces capacity to the solution, but it is a fixed capacity. Driver's cars have different capacities, so the MST sub-graphs would need to have individual sizes and each sub-graph would need to encompass the driver of the corresponding capacity.

---

Am I wrongfully categorizing my scenario as a combinatorial optimization problem? I appreciate any help to fix the above-mentioned problems or to correctly categorize my computational problem.

---

**Edit:** If I managed to group the riders with drivers (with the use of some heuristic), then the remaining set would be drivers and their assigned passengers, or basically a list of clusters of 1+ participants.

I could then apply a capacitated MST solution to this collection. With the destination as root, the sub-graphs would be groupings of the previous clusters. Ideally, each sub-graph would have different capacities in accordance with the seats of the containing cars.

I'm not sure that's possible, so I thought about doing a loop:

* What're the most available seats in a single car?
* Run the capacitated MST with that seat capacity
* Get the sub-graph containing the car of the corresponding capacity
* Remove all the clusters of that sub-graph from future computations
* Repeat with the remaining cluster, until no more computations are possible

The problem I see arising is if the selected pivot car is in the middle of the sub-graph, meaning that it would need to double-back on edges because it wasn't a terminal node.

Still doesn't feel like a proper solution...

---

Thanks for the help!

# Answer
These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have).

My favorite "big hammer" for this kind of scheduling problem is to use integer linear programming, as that has been used successfully for a number of different scheduling and operations research tasks.

The best way to formulate this as an ILP problem may depend on the parameters (how many drivers and riders you have), but let me describe one illustrative approach. Suppose each car can have up to 5 riders. Then consider all possible ways to choose a combination $S$ of 1 driver and up to 5 riders. For each such, compute the total distance $d\_S$ of the shortest route that involves that driver picking up all riders and taking them to the destination (this might involve $5!=120$ shortest-path computations). Now introduce a zero-or-one variable $x\_S$ for each combination $S$, with the intended meaning that $x\_S=1$ means we select that combination. We require that each participant is selected exactly once; thus, for each participant $p$, we add the equality $\sum\_S x\_S = 1$, where $S$ ranges over all combinations with $p \in S$. Then, we minimize the linear objective $\sum\_S d\_S x\_S$, where $S$ ranges over all combinations. This ensures we minimize the total distance, while ensuring every participant reaches the destination.

Then, apply an off-the-shelf ILP solver. If the number of riders and drivers is small enough, it should find an optimal solution. If it is taking too long, many ILP solvers will let you terminate them early and report the best solution found so far, which may be effective at finding a good but not optimal solution.

This particular formulation might work well if the number of riders is not too large. If the number of riders is very large, you might need to consider other formulations.
> 1 votes

---
Tags: shortest-path, minimum-spanning-tree, routing
---


title: Random access memory and data

text:
# Question
Title: Random access memory and data
What kind of data is stored in the RAM when it is fresh out of manufacture? Apart from certain basic instructions (if yes, what are they), are there numbers stored as well or are most of the memory cells just empty?

# Answer
RAM is cleared after each power cycle. The power-up value of cells depends on the technology.

* Static RAM content is usually random (there is no preference between 0 and 1, but the same chip may present similar patterns after each power-up).
* Dynamic RAM has the value corresponding to empty capacitors in the RAM array, which usually corresponds to ones, but there is no guarantee. Dynamic RAM can retain data for several seconds when unpowered (very dependant on temperature) : One cannot assume a known state at power-up and recent DRAM (DDR3, DDR4...) need complex initialization sequences where the RAM controller stores and checks some values like FFFF/0000/AAAA/5555, ...)
> 5 votes

# Answer
Memory cells are just electronic components whose voltage is used to store information: you can think of it as high voltage meaning a binary 1 and low voltage meaning a binary 0. Everything that is stored is either binary 1s or binary 0s.

As such, there isn't really any such thing as "empty" and, as far as RAM goes, there isn't really any voltage if the memory isn't connected to some kind of power source.
> 1 votes

---
Tags: memory-allocation
---


# Question
Title: What does $O(\alpha(n))$ amortized time mean?
DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect.

from a set of consectutive integers like $S = \\{1,2,3,5,6\\}$

Provide a data structure and an algorithm for DELETE that takes $O(\alpha(n))$ amortized time

---

not sure what what does $O(\alpha(n))$ amortized time mean?

I was thinking AVL trees ? I know the worst case is $O(\log n)$ for that. Not sure what $O(\alpha(n))$ amortized time means though.

# Answer
> 6 votes
$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$.

In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, which are pretty much the fastest data structures you'll ever use.

EDIT: $^nb$ indicates "tetration", that is, iterated exponents. It grows ridiculously quickly: $O(^n2)$ is worse than $O(n!)$.

# Answer
> 3 votes
$\alpha(n)$ is the inverse Ackerman function.

---
Tags: data-structures, time-complexity, amortized-analysis
---


title: Name of double sided search algorithms

text:
# Question
Title: Name of double sided search algorithms
I modeled the function double\_sided\_breadth\_first\_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an effort to improve efficiency. I have not seen this applied to bfs before. Does anyone know the name of this algorithm? Does it have a name? I saw the technique for doing a double sided Dijkstra algorithm, doing the iteration on the smaller vertex with smaller degree described online but can't find the page now. Does anyone know of a references for the Dijkstra style algorithm I just described?

More detailed description of algorithm I am trying to research: Do a two sided breadth first search starting at both vertices. At each iteration expand the boundary of the smaller boundary.

The pseudo code is as follows

```
double_sided_breadth_first_search( ug, vertex0, vertex1 )
  #ug undirected graph as an adjacency list, ie hash map from vertex to set of neighbor vertices
  # vertex0, vertex1 - the two vertices that we wan't to connect
  boundary0 = { vertex0 }
  boundary1 = { vertex1 }
  visited = hashmap from vertex => vertex0 or vertex1
  common_vertex = null
  distance = 0
  while |boundary0| > 0 and |boundary1| > 0 and common_vertex is null {
    distance = distance + 1
    if |boundary0| <= |boundary1| then
       expand boundary0, mark vertices in new boundary with vertex0
        set common_vertex if one is marked as vertex1
    else
       expand boundary1, mark vertices in new boundary with vertex1
        set common_vertex if one is marked as vertex0
  }
  if common_vertex not null {
    return distance
  } else {
    error
  }

```

Here is python code that implements the algorithm

# Answer
What you have implemented is a variation of bidirectional Dijksktra's algorithm.

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed or undirected graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. When each search is Dijkstra's algorithm, we end up with **bidirectional Dijkstra's algorithm**.

In which order the algorithm should expand the search in each direction and in which efficient condition the algorithm can stop the search are two obvious and critical factors for a bidirectional search. They are studied in quite a few papers.

It looks like there is not a special or specific name for the variation of bidirectional Dijkstra's algorithm that expands the search from the side whose front is nearer to its starting points. One reason to explain away the lack of a name is that it is not easy to argue that strategy should offer a nicer heuristic when compared to other strategies.

You may want to read the Wikipedia article on bidirectional search.
> 1 votes

---
Tags: algorithms, terminology, search-algorithms
---


# Question
Title: Distance function such that we visit every "color region" once
Consider the following image:

Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right.

We must go through each color exactly once, and once we go outside a color, we can't go back to the same one.

Here is a example of what I think is a optimal path:

---

As per dikisjtra algorithm, we update the distance at once node if `d[current] + weight(this_node, next_node) < d[next_node]`. Usually these weights are given to us, but in this case, we must create a weight function such that given any two pixels `(x1,y1),(x2,y2)`, our path follows something like what I have drawn in white.

You can assume all the colors are indeed different, even though they might look similar because of shades.

I am thinking of the following conditions to check in the weight condition:

going from old color -\> same color -\> maybe a weight of 5

going from old color -\> new color -\> a low weight of 1

What are the cases of the weights I can assign so dijikistra finds the path shown in white?

# Answer
Summary of your problem: You have a graph and a particular path through the graph, and you want to assign weights to the edges so that running Dijkstra's algorithm on that graph will give you that path.

Solution to your problem: assign a weight of 1 to each edge in the path, and a weight of $\infty$ (or some very large number) to each edge not in the path. (It suffices to choose a weight that is larger than the number of vertices in the graph.) You can easily verify that the shortest path only uses edges of weight 1 (any path that includes any other edge will have a total distance that is larger than that of the desired path).
> 1 votes

---
Tags: algorithms, graphs, shortest-path, minimum-spanning-tree
---


# Question
Title: Counting models satisfying a boolean formula
I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, *Theor. Comput. Sci.* 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C\_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.

I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?

# Answer
For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with

```
count = 0
j = number of variables
for v1 = 0 to 1 do
    for v2 = 0 to 1 do
        ...
        for vj = 0 to 1 do
            if formula_value(phi, v1, ..., vj) == true
                count = count + 1

```

This runs in time $\Theta(2^j) = O(2^k) = \Theta(1)$, since $k$ is fixed.
> 3 votes

---
Tags: combinatorics, satisfiability, 2-sat
---