title: Find shortest path for a volatile graph

text:
# Question
Title: Find shortest path for a volatile graph
Let me define a volatile graph first:

It is an undirected graph in which the weight of each edge varies every time we query it. That is, when we request the weight w(e) of edge e, we obtain an approximate value ˆw(e) defined as follows: wˆ(e) = w(e) + η, where η ∼ N (0, σ). Here, N (0, σ) is a Gaussian distribution with mean zero and standard deviation σ.

How to obtain a shortest path for such a graph. Let it be denoted as (G, u, v, p). Find the correct shortest path between vertices u and v on a volatile graph G with confidence p. We can define p in any manner we want as long as it is consistent to the fact that as p grows, the probability that our algorithm returns the true shortest path should also grow

# Answer
> 1 votes
Here is a rough sketch of an iteratively improving algorithm that I believe should work pretty well while minimizing the number of queries we do. It can also immediately start finding paths and slowly improve the paths it finds as it goes.

The first step is to evaluate every edge (if you wish to improve initial accuracy, evaluate every edge $k$ times) and use Dijkstra's to find the shortest distance $d\_v$ from every vertex $v$ to the target vertex. This forms our initial belief of the graph.

Our goal is to find an accurate $\mu\_e$ average weight for each vertex, but we want to be most certain about our precision "near" what we believe to be the optimal path(s). We do this by repeatedly finding a path from the start vertex to the target, in a probabilistic fashion, by repeating the following procedure:

If we are currently at vertex $v$ we have a choice from some edges. We currently believe that each edge has weight $\mu\_e$, and when we take that edge we would get to vertex $w$ with remaining (believed) distance $d\_w$. We consider this a multi-armed bandit problem, where choosing edge $e$ going to vertex $w$ would have cost $\mu\_e + d\_w$, and we want to minimize cost. We use this to probabilistically choose an edge, we query its weight, we update $\mu\_e$ and $d$ with this new weight and then move to $w$.

As we keep repeating the above process we will balance exploration of the graph with exploitation automatically due to the multi-armed bandit.

---
Tags: shortest-path
---


# Question
Title: Solving "coin exchange" for coins of power values by greedy algorithm
When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?

For example, if $a = 3$, $n =3$, we get the following coin values: 1, 3, 9, 27. When total exchange is 16, answer is 4 coins, as returned by greedy algorithm, $16=9+3+3+1$.

# Answer
> 2 votes
For the coin values: 1, 3, 9, 27, suppose $16 = a\_0 + 3a\_1 + 9a\_2 + 27a\_3$ is the coin exchange with minimal number of coins. Note that $16\equiv a\_0 \equiv 1(\operatorname{mod}3)$. If $a\_0 \ge 3$, then we can subtract 3 from $a\_0$ and add 1 to $a\_1$ to obtain coin exchange with less number of coins. So, $a\_0$ must be the remainder of 16 divided by 3. Hopefully, you can see where I am going.

---

**All numbers or variables below are nonnegative integers.** $(d\_nd\_{n-1}\cdots d\_0)\_a$ means the integer with those digits in base $a$, i.e., $(d\_nd\_{n-1}\cdots d\_0)\_a=\sum\_{i=0}^{n}d\_ia^i$ where $d\_i\lt a $ for $i\le n$.

Here is the general theorem.

**(Greedy algorithm works for power coins)** Let $a\ge2$ and $n\ge0$. If $e\_na^n+(e\_{n-1}e\_{n-2}\cdots e\_0)\_a=\sum\_{i=0}^nc\_ia^i$, then $ \sum\_{i=0}^ne\_i\le\sum\_{i=0}^nc\_i$.

Proof by mathematical induction on $n\ge0$.

The base case, when $n=0$ is trivial.

Suppose it is true for some $n\ge0$. Let us check the case of $n+1$. Suppose $m=e\_{n+1}a^{n+1}+(e\_ne\_{n-1}\cdots e\_0)\_a=\sum\_{i=0}^{n+1}c\_ia^i$. Note that $e\_0$ is the remainder of $m$ divided by $a$.

If $c\_{0}\ge a$, we can subtract $a$ from $c\_0$ and add $1$ to $c\_1$ to reduce sum $\sum\_{i=0}^{n+1}c\_i$. Without loss of generality we can assume $c\_{0}\lt a$, i.e., $c\_0$ is also the remainder of $m$ divided by $a$.

Now let $m'=(m-e\_0)/a=(m-c\_0)/a$. Then $m'=e\_{n+1}a^{n}+(e\_{n}e\_{n-1}\cdots e\_1)\_a=\sum\_{i=0}^{n}c\_{i+1}a^i$. By induction hypothesis, we know $\sum\_{i=0}^ne\_{i+1}\le\sum\_{i=0}^nc\_{i+1}$. Adding $e\_0=c\_0$ to both sides, we obtained the wanted inequality for the case of $n+1$. Q.E.D.

What is left to be explained is that $\sum\_{i=0}^ne\_i$ does come from the greedy algorithm. That easy task will be left for interested readers to verify.

---
Tags: greedy-algorithms, coin-change
---


# Question
Title: How many solutions are there for a XOR-SAT formula?
Does anyone know how many solutions there are for a XOR-SAT formula? And how do the variables in solutions distribute? For example, if (x0=1, x1=0, x2=1) is a solution for a XOR-SAT formula, how does x0 distribute in different solutions? Thanks!

# Answer
The answer depends on the instance of the problem; For example;

$$(x\_0 \oplus x\_1) \wedge (x\_0 \oplus \neg x\_1)$$ has no solution at all.

However;

$$(x\_0 \oplus x\_1) \wedge (x\_0 )$$ has solutions.

Finding the solutions, or the inconsistency is not that hard. You convert the problem into a linear system of equations as;

$$(x\_0 + x\_1) \equiv 1 \mod 2, \text{ and }$$$$ (x\_0 + (1 + x\_1)) \equiv 1 \mod 2 $$

and than the problem can be solved by the Gaussian elimination.
> 1 votes

---
Tags: satisfiability, xor
---


title: Adding two running time from a function

text:
# Question
Title: Adding two running time from a function
I have a method `Func()` that has two inner methods `Func1()` and `Func2()`.

`Func1()` has a running time of $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))$ and `Func2()` has a running time of $O(k \lvert K \rvert \lvert V\rvert)$.

What is the running time of `Func()`?

Is it $\max \\{ O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert)),O(k \lvert K \rvert \lvert V\rvert)\\} $? or $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))+O(k \lvert K \rvert \lvert V\rvert)$?

If it is the latter one, how can it be simplified?

# Answer
> 1 votes
* The summation rule of the big-O notation;

Given $T\_1(n) \in \mathcal{O}(f(n))$ and $T\_2(n) \in \mathcal{O}(g(n))$, than $$T\_1(n)+T\_2(n) \in \mathcal{O}(\max(f(n),g(n)).$$

So, if you call $Func1()$ and $Func1()$ inside of your function $Func()$ only once and there is no other significant computation, $Func()$'s running time is;

$$Func() \in \mathcal{O}(\max(k |M^2|(|L|+|M|\log |M|), k | K | | V | )) $$

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Circuits vs Turing Machines in the "nonuniform model of computation"
I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the problem. The authors refer to this as a nonuniform model of computation.

My question is: why do we need to use circuits for this type of model? Couldn't we just as well allow for a different Turing machine for each input size? Is there some subtle reason for why we need to use circuits in order to study this model of computation?

# Answer
You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss.

You could obviously talk about a sequence of machines $M\_n$, where $M\_i$ knows how to handle strings of length $i$, and you don't care about how it behaves on different strings (such a definition of nonuniform classes would be equivalent). However, in this case, you don't really use the power of Turing machines. What you care about is only $M\_k|\_{\\{0,1\\}^k}$, which is completely determined by a computation table of size $T\_k\times T\_k$ where $T\_k$ is the maximal running time of $M\_k$ on length $k$ inputs. This table corresponds to a circuit of size $\le T\_k^2$ (this can be improved), which now becomes the more natural object to discuss.
> 3 votes

---
Tags: complexity-theory, turing-machines, circuits
---


# Question
Title: Proof for Turing Machines being able to simulate any algorithm in the same time complexity
I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the algorithm while doing proofs.

However, I am unable to find a proof for this statement. Is there a formal proof of why the Turing Machine model should be able to simulate any algorithm within the same time complexity?

# Answer
This is not a formal statement, but either a definition or an empirical observation. The full claim is something like the following:

"A reasonable model of computation (for discrete data) together with a reasonable notion of time complexity will have the property that it can be simulated by a Turing machine with at most polynomial increase in time complexity."

The two occurances of "reasonable" here are generally not seen as formal notions, but rather as informal notions. We can trivially define models of computation with notions of time complexity not having the property above, but these models do appear artificial. On the other hand, models people actually want to use have the property.

Any attempt to formally define what a "reasonable model of computation with time complexity" is would probably include the possibility of polytime-simulation by a TM as an axiom.
> 2 votes

---
Tags: turing-machines, proof-techniques
---


# Question
Title: The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is
In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

1. min(M,N)
2. max(M,N)
3. M+N
4. MN Answer given is M+N but my understanding is

According to the given question the communication between sender and receiver is unidirectional or bi directional?

If it is unidirectional then answer should be max (N,M) , as sender will send N frames and each frame should have unique sequence number and if it is bidirectional then it should be M+N as both will have their Frames In transition with unique sequence number.

Is my interpretation is correct? Please correct me if I am wrong!! If not why M+N is correct?

# Answer
Your interpretation of bidirectional is correct.

First of all, it should be **bi-directional**. Here is the reason. The receiver window size M is not equal to sender window size N so it **must** be bidirectional. If it is unidirectional, then the receive window should be 1 for Go-Back-N protocol and N for Selective-Repeat protocol.

Then it is very straightforward: the minimum sequence number should be N+M. For example, the sender could choose \[0, N-1\] as sequence numbers while the receiver could choose \[10000, 10000+M-1\] as sequence numbers.

One thing to note, this problem is not strict. If you use Selective-Repeat protocol, then the minimum sequence number should be 2\*(N+M) to handle both new packet and a retransmission.
> 0 votes

---
Tags: computer-networks, network-flow
---


title: Proof that the grammar is LL(2)

text:
# Question
Title: Proof that the grammar is LL(2)
I am given the following grammar:

$ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $

and I have to prove it is LL(2).

I know what LL(k) means - one can choose a production based on k characters from the input.

So consider the input $ababa$. Of course we start with $S$, so we apply the production to $AabAba$. Now we see $ab$ in the input, so we choose the production to $\epsilon$ for the first $A$. We get rid of the $ab$ and we have $aba$.

And what now? A while ago, we've chosen $\epsilon$ for $A$, seeing $ab$ in the input. Now we see the same thing, but are supposed to choose $A \rightarrow a$. But, as I understand, we cannot do this, because that would mean nondeterminism.

Is this a counterexample? How is this grammar LL(2)?

# Answer
Sippu and Soisalon-Soininen (1982) carefully distinguish between two definitions of LL(k) grammars, one of which -- the one I think you are using -- they call *strong* LL(k):

> A grammar $G$ is $\text{LL}(k)$ if $\text{FIRST}\_k(\omega\_1\delta)$ and $\text{FIRST}\_k(\omega\_2\delta)$ are disjoint whenever $xA\delta$ is a left sentential form of $G$ and $A \to \omega\_1$ and $A \to \omega\_2$ are distinct productions of $G$.
>
> Grammar $G$ is $\text{strong LL}(k)$ if $\text{FIRST}\_k(\omega\_1\text{FOLLOW}\_k(A))$ and $\text{FIRST}\_k(\omega\_2\text{FOLLOW}\_k(A))$ are disjoint whenever $A \to \omega\_1$ and $A \to \omega\_2$ are distinct productions of $G$.

The difference has to do with the state machine. A grammar is $\text{strong LL}(k)$ if you can use the same procedure to decide which production for a non-terminal to use regardless of the contents of the parser stack. An $\text{LL}(k)$ grammar, on the other hand, can use the contents of the stack ($x$ in the above definition) as well as the lookahead. (For these purposes the contents of the stack can be condensed into a finite state automaton.)

While the two definitions are not equivalent -- the strong condition is much more restrictive -- it can be demonstrated that every $\text{LL}(k)$ grammar can be changed to a $\text{strong LL}(k)$ grammar simply by labelling each usage of a non-terminal. So in the case of your grammar, which is $\text{LL}(k)$ but not $\text{strong LL}(k)$, we can create the equivalent grammar:

$\begin{align} S &\to A\_1abA\_2ba \\ A\_1 &\to a | \epsilon \\ A\_2 &\to a | \epsilon \\ \end{align}$

which is $\text{strong LL}(k)$.

For more details, see the paper linked above.
> 2 votes

---
Tags: formal-grammars, parsers, ll-k
---


title: Confusion regarding dependencies

text:
# Question
Title: Confusion regarding dependencies
Let say we have a relation with 5 attributes `{A, B, C, D, E}`. Let say we have two candidate keys as `A` and `B,C`. Let us say we have a partial dependency as `B -> E` with regards to the candidate key `B,C`. The database designer decides that A will be the primary key of the relation. Now since we had `B -> E`, will it be called a partial dependency or a transitive dependency? Is the relation `2NF` or not even `2NF`?

# Answer
As the definition of the 2NF is:

> **A functional dependency on part of any candidate key is a violation of 2NF**. In addition to the primary key, the relation may contain other candidate keys; it is necessary to establish that no non-prime attributes have part-key dependencies on any of these candidate keys.

This schema is not in 2NF.
> 1 votes

---
Tags: normal-forms
---


# Question
Title: What is the definition of computable partial function?
Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input on which $f$ is defined. But then what should $T$ do on inputs from $\mathbb{N}$ for which $f$ is undefined, and what should it do on inputs that do not represent a natural number? Should it halt or not?

# Answer
A Turing machine $\Phi$ computes a partial function $f:$ $\subseteq\mathbb{N}\rightarrow\mathbb{N}$ iff:

* For each $n\in dom(f)$, $\Phi(n)$ halts and equals $f(n)$.
* For each $n\not\in dom(f)$, $\Phi(n)$ diverges (that is, never halts).

What about when we feed $\Phi$ a "nonsense" input - that is, some string *not* corresponding to a natural number? Well, we don't actually place any requirements on how $\Phi$ behaves in such a case, so there isn't anything to say there. *(One reason this should feel fine is that it is computable to tell whether a given finite string represents a natural number - so we're not missing anything interesting by ignoring the behavior of $\Phi$ on nonsense inputs.)*

---

Note that there is a related, weaker notion:

* One partial function $f$ *extends* another partial function $g$ if $dom(f)\supseteq dom(g)$ and for all $n\in dom(g)$ we have $f(n)=g(n)$.
* We can say that a partial function $g$ is *extendible to a partial computable function* if there is some computable partial function $f$ which extends $g$.

It turns out that "extendible to a partial computable function" is a *strictly weaker condition* than being a partial computable function; this is easy to prove by a simple cardinality argument *(exercise)*.

More interestingly, we can cook up partial computable functions which are not extendible to any total computable function - sort of "fundamentally incomplete" functions which are nonetheless computable. A classic example comes from Godel's incompleteness theorem:

> Fixing some appropriately-computable bijection $b$ between sentences in the language of arithmetic and natural numbers, let $h(x)$ be the least $n$ such that there is a proof of $b^{-1}(x)$ of length $n$, and be undefined otherwise. Then $h$ is a partial computable function which cannot be extended to a total computable function.

Here "proof" means "proof *from PA*" (or your favorite axiom system). The reason that $h$ can't be extended to a total computable function is simple: if $f$ were a total computable function extending $h$, we could tell whether a given sentence $\varphi$ was provable from PA by searching for a proof of $\varphi$ of length at most $f(b(\varphi))$ \- if we find one it is, and if we don't find one it isn't. But from this data we could built a complete consistent computable extension of PA *(exercise)*, contradicting Godel's incompleteness theorem.

The (non-)extendibility of partial computable functions to total, or otherwise "frequently-defined," computable functions is an important topic in computability theory.
> 4 votes

---
Tags: computability, computation-models, primitive-recursion
---


# Question
Title: Using pumping lemma to prove {a^ib^j | i > j} non-regular
I'm having issues using the pumping lemma to prove $L\_2 = \\{a^ib^j \mid i \> j \\}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$

So I've done some digging. On page 2 here I found a proof. However, it doesn't make sense to me.

Here is the proof, I will list my understandings as we go through the proof:

> Assume by way of contradiction that $L\_2\in \mathrm{REG}$, then $L\_2$ satisfies the conditions of the pumping lemma. Let $p \> 0$ be the pumping constant. Consider the word $w = a^{p+1}b^p$.

Makes complete sense.

> Clearly $w \in L\_2$ and $|w| \> p$, so according to the pumping lemma there exist $x, y, z ∈ Σ^∗$ such that $w = xyz,$ $ |xy| ≤ p,$ $ |y| \> 0$ and for all $i ≥ 0$ it holds that $xy^iz ∈ L$.

Now if an $i$ is chosen to be $0$, this would conflict with $|y| \> 0$? It seems it's using $L$ instead of $L2$. Is there a reasoning?

> Since $|xy| ≤ p$, then $x = a^n, y = a^m$, and $z = a^kb^{p+1}$ such that $m + n + k = p$, and $m \> 0$.

This makes sense to me, as $z$ is equal to the rest of the $a's$ not in $x$ and $y$ plus all the $b's$.

> We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^{p+1}$. Since $m+n+k = p+1$ and $m \> 0$, then $n+k \< p+ 1$.

Now this doesn't make sense to me. Pumping down ridding of $y$ contradicts the $|y| \> 0$ rule and how does $m+n+k$ change to now equal $p+1$

> Thus, $xz \notin L\_1$, in contradiction to the pumping lemma. So $L\_2$ is not regular. Note that it is crucial to “pump down” for this language.

If you guys can help me understand this proof, that would be great thanks

# Answer
> 2 votes
> Now if an $i$ is chosen to be 0, this would conflict with $|y|\>0$?

Note it's $|y|\>0$, not $|y^i|\>0$, so there's no problem.

All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.

... Clearly $w \in L\_2$ and $|w| \> p$, so according to the pumping lemma there exist $x, y, z \in \Sigma^∗$ such that $w = xyz,$ $ |xy| \le p,$ $ |y| \> 0$ and for all $i \ge 0$ it holds that $xy^iz \in L$. Since $|xy| \le p$, then $x = a^n, y = a^m$, and $z = a^kb^\color{red}p$ such that $m + n + k = \color{red}{p+1}$, and $m \> 0$. We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^\color{red}p$. Since $m+n+k = p+1$ and $m \>0$, then $n+k \color{red}{\le p}$ ...

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Converting an infix expression to postfix
So the question is to convert the following expression to postfix:

```
(a+b)^(p+q)^(r*s*t)

```

The answer I get when I calculate is: `ab+pq+^rs*t*^`

**But** the answer is given to be `ab+pq+rs*t*^^`

I assume that the step when you need to push second '^' into stack when there is already a '^' in the stack is where I went wrong (I pop out the '^' before pushing). Shouldn't we pop out the first '^' as they are of equal precedence ? Or is it an exception to '^' operator ?

# Answer
There is a sort of an exception to '^', the exponentiation operator since it is **right associative**. That is, $a^{b^c}$ means $a^{\left({b^c}\right)}$ instead of $\left(a^b\right)^c$. That is, `(a+b)^(p+q)^(r*s*t)` means `(a+b)^((p+q)^(r*s*t))` instead of `((a+b)^(p+q))^(r*s*t)`.

When you reach the first `^` while evaluating postfix expression `ab+pq+rs*t*^^`, you will pop out the result of `rs*t*` and the result of `pq+`. You get the expected exponentiation as expected.
> 0 votes

---
Tags: stacks
---


# Question
Title: Stable matching with asymmetric arrays (gale shapley)
I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms.

One of the answer suggested to add 5 dummy students to make number of students equal to 10.

Lets suppose before adding the dummy students the preferences are below -:

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

d1 - s1 s5 s3 s4 s2

d2 - s2 s3 s1 s5 s4

d3 - s3 s5 s4 s1 s2

d4 - s3 s5 s4 s2 s1

d5 - s2 s5 s3 s1 s4

d6 - s3 s4 s5 s1 s2

d7 - s2 s4 s5 s1 s3

d8 - s3 s5 s1 s4 s2

d9 - s2 s5 s3 s1 s4

d10 - s5 s2 s1 s3 s4

How should I go about this after adding the dummy students. My approach is below -: I am putting 5 dummy student in lower preference for dorms and giving random dorms preference to dummy students. Dummy students are denoted by ds.

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

ds1 - d6 d2 d9 d10 d4 d5 d3 d1 d8 d7

ds2 - d4 d2 d6 d3 d10 d9 d5 d7 d1 d8

ds3 - d7 d3 d5 d1 d10 d9 d2 d8 d4 d6

ds4 - d2 d8 d1 d10 d6 d3 d4 d5 d9 d7

ds5 - d10 d2 d6 d3 d4 d5 d1 d7 d9 d8

d1 - s1 s5 s3 s4 s2 ds1 ds2 ds3 ds4 ds5

d2 - s2 s3 s1 s5 s4 ds1 ds2 ds3 ds4 ds5

d3 - s3 s5 s4 s1 s2 ds1 ds2 ds3 ds4 ds5

d4 - s3 s5 s4 s2 s1 ds1 ds2 ds3 ds4 ds5

d5 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d6 - s3 s4 s5 s1 s2 ds1 ds2 ds3 ds4 ds5

d7 - s2 s4 s5 s1 s3 ds1 ds2 ds3 ds4 ds5

d8 - s3 s5 s1 s4 s2 ds1 ds2 ds3 ds4 ds5

d9 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d10 - s5 s2 s1 s3 s4 ds1 ds2 ds3 ds4 ds5

If i solve the above with gale shapley will I get the right results?? In other words, will I get the stable matching?

# Answer
This will give you a stable matching when you will use the Gale Shapley algorithm. You can use the below code. a and b are dictionaries in the code

```
def insert_dummies(a,b):
  length_a=len(a.keys())
  length_b=len(b.keys())
  items_a=list(a.keys())
  items_b=list(b.keys())
  dummy_list=[]
  if length_a>length_b:
    dummy_number=length_a-length_b
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_a:
      f=0
      while dummy_number>f:
        a.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        b[z]=items_a
        n=n+1
  if length_a<length_b:
    dummy_number=length_b-length_a
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_b:
      f=0
      while dummy_number>f:
        b.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        a[z]=items_b
        n=n+1
    else:
        return

  return a,b

#This function returns the result of the algorithm. Parameter 'a' refers to the preferences of the gender
#that we want to find the optimized solution for, while the parameter 'b' refers to the preferences of the other gender.
def StableMatching(a, b):
    #this function returns a stable matching
    dict_a = a.keys()  #This list contains the names of the group for we are optimizing.
    names1 = list(dict_a)
    dict_b = b.keys() #This list contains the names of the other group.
    names2 = list(dict_b)
    i = 0
    engaged = []
    #This dictionary contains the names of the gender for which we attempt to find the optimized solution.
    times = {}
    t = 0
    position_existing = 0
    position_potential = 0
    counter = 0
    #Can have the values 'free' or 'not free'.
    a_p = {}
    while(counter < len(names1)):
        a_p.update({names1[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Can have the values 'free' or 'not free'.
    b_p = {}
    while(counter < len(names2)):
        b_p.update({names2[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Initialization of times dictionary.
    while(counter < len(names1)):
        times.update({names1[counter]: 0})
        counter = counter + 1

    #The value -1 has the meaning that when all men or women are paired, the loop stops;
    while((i != -1) and (a_p[names1[i]] == 'free') and (times[names1[i]] < len(names2))):
        #The man/woman who is next in the ranking of the proposals.
        w = a[names1[i]][times[names1[i]]]
        if(b_p[w] == 'free'):
            a_p[names1[i]] = 'not free'
            b_p[w] = 'not free'
            t = (names1[i], w)
            engaged.append(t)
            times[names1[i]] = times[names1[i]] + 1
        else:
            q = 0
            while(q < (len(engaged))):
                  if(w in engaged[q]):
                      t1 = engaged[q]
                      l = 0
                      while(l < len(names1)):
                          if(names1[i] == b[w][l]):
                              position_potential = l
                              l = len(names1)
                          l = l + 1
                      l = 0
                      while(l < len(names1)):
                          if(t1[0] == b[w][l]):
                              position_existing = l
                              l = len(names1)
                          l = l + 1
                      if(position_potential < position_existing):
                          t = (names1[i], w)
                          engaged.append(t)
                          del(engaged[q])
                          a_p[names1[i]] = 'not free'
                          a_p[t1[0]] = 'free'
                          q = len(engaged)
                  q = q + 1

            times[names1[i]] = times[names1[i]] + 1
        i = i + 1
        #If the variable i has passed from all the men/women then it starts from the beginning
        #in order to check the ones who remain single.
        if(i == len(names1)):
            i = 0
        if(a_p[names1[i]] == 'not free'):
            k = 0
            z = False
            while((k < len(names1)) and (z == False)):
                if(a_p[names1[k]] == 'free'):
                    i = k
                    z = True
                k = k + 1
            if((k == len(names1)) and (z == False)):
                i = -1
    engaged_dict = dict(engaged)
    return engaged_dict

```
> 0 votes

---
Tags: algorithms, optimization, matching
---


# Question
Title: Several simple propositions about regular languages
I'm trying to prove, that the following statements are either true or false. Unfortunately, I'm having a hard time finding formal proofs for my answers. I hope you can help me out a bit.

Let $A,B$ be two subsets of $\\{0,1\\}^\*$

1. If $A$ is regular pumpable and $B \subseteq A$, then B is regular pumpable too.
2. If $A$ not regular pumpable and $A ⊆ B$, then $B$ is not regular pumpable too.
3. If $A$ is regular and $B \subseteq A$, then B is regular too.
4. If $A \cap B$ is regular, then $A$ and $B$ are regular too.
5. There is at least one finite language on the alphabet $\\{0,1\\}$, that doesn't meet the pumping lemma.

# Answer
> 1 votes
I'm assuming regular pumpable means regular? you should check out Apass Jack's answer by the way, I'm just going to elaborate a bit.

1. Your proof is not correct, since the fact that "pumped" strings are in $ A$ doesn't imply it is in $B$. Take for instance $ A = 0^\*, B = (00)^\*,$ and pumping length = 1. The same pumping length can't really be transferred to B.
2. The fact that $ A $ is not pumpable doesn't immediately transfer to $ B$ not being pumpable. When you do proofs you should be really convinced that the implications work, and a good way to check that is by making counter examples. For instance, let $ A = \\{ 0^n1^n | n \in \mathbb{N} \\} $ and $ B = (0+1)^n $.
3. I'm not sure how this differs from 1.
4. Certainly you can think of none regular languages that have nothing in common? Or you can chose a none regular language and change its alphabet (like $ 0^n1^n $ and $ a^nb^n$). Obviously their intersection is regular (the empty set), but neither of them are.
5. To prove that all finite languages are regular, you can construct a DFA that has a branch dedicated to each string in a finite language. The states are finite since there are only finite number of such strings, and obviously that this DFA accepts all and only strings in the finite language.

# Answer
> 1 votes
In all following counterexamples, $A$ and $B$ are subset of the full language $F=\\{0,1\\}^\*$. Note that $F$ is a regular language.

> If $A$ is regular pumpable $B\subseteq A$, then $B$ is regular pumpable too.

Counterexample: $A=F$ while $B$ is any non-regular-pumpable language.

(It is taken for granted that a language being regular-pumpable means it is able to be pumped like a regular language. There are different ways to define being able to be pumped like a regular language; however it is defined, $\\{0^n1^n\mid n\ge 0\\}$ will not be regular pumpable. I made this note since some non-regular languages can be pumped like a regular language. For example, $\\{ 01^{n^2} \mid n \ge 1 \\} \cup \\{ 0^kw \mid k\neq 1, w\in \\{1\\}^\* \\}$ is non-regular but can be pumped by the most common version of the pumping lemma for regular languages.)

(In case "regular pumpable" for a language is defined simply as "regular", just let $A=F$ and B be any non-regular language for a counterexample.)

> If $A$ not regular pumpable and $A\subseteq B$, then $B$ is not regular pumpable too.

Counterexample: $B=F$.

> If $A$ is regular and $B\subseteq A$, then $B$ is regular too.

Counterexample: $A=F$ while $B$ is non-regular.

> If $A\cap B$ is regular, then $A$ and $B$ are regular too.

Counterexample: $A$ is not regular while $B=F\setminus A$. $A\cap B=\emptyset$ is regular.

> There is at least one finite language on the alphabet $\\{0,1\\}$, that doesn't meet the pumping lemma rules.

That is not true. All finite languages are regular and, thus, meeting the pumping lemma rules.

---

> How do you come to that conclusion?

Mostly experience and knowledge plus a bit of luck. Before proving any proposition, you would like to do some sanity check with some simple and/or extreme cases. For example, you might have noticed that I have used the simple and extreme language $F$ several times.

---
Tags: regular-languages, pumping-lemma
---


title: XOR two numbers

text:
# Question
Title: XOR two numbers
Is there an intuitive meaning of XOR of two numbers not involving binary and just decimal? Or is is always converted into binary and then XORed?

# Answer
> 8 votes
Bitwise operations like (bitwise) AND, OR, and XOR don't make much sense from the perspective of decimal expansion. They do make some sense in bases which are powers of 2 like hexadecimal, since in such bases they also operate digit by digit.

# Answer
> 7 votes
There are only 16 distinct binary operations possible for $a$ op $b$, i.e., $0, 1, a, b, \overline{a}, \overline{b}, ab, a\overline{b}, \overline{a}b, \overline{a}\overline{b}, a+b, a+\overline{b}, \overline{a}+b, \overline{a}+\overline{b},ab+\overline{a}\overline{b}$ and $a\overline{b}+\overline{a}b$. XOR is $a\overline{b}+\overline{a}b$.

With decimal digits you have a staggering possibility of $10^{100}$ functions. However, the idea of XOR can be easily duplicated. Nevertheless the idea of doing bitwise XOR is not acceptable, 0000 $\oplus$ 0000 is 1111 which is 15, not a decimal digit.

Let us try to do something like XOR for tertiary digits, i.e. 0,1,2. What we want is this: if $a$ XOR $b$ is $c$, then $a$ XOR $c$ should be $b$ and $b$ XOR $c$ should be $a$. So we should have the following:

$a \oplus b$ = $c$ $\Leftrightarrow$ $a \oplus c$ = $b$ $\Leftrightarrow$ $b \oplus c$ = $a$, for every choice of $ a,b, c \in \\{0, 1, 2\\}$.

Also we would like to have $ a \oplus b = b \oplus a$.

With this in mind we can have the following table:

```
XOR | 0 1 2
-----------
0   | 0 2 1
1   | 2 1 0
2   | 1 0 2

```

And we can have yet another table

```
XOR | 0 1 2
-----------
0   | 1 0 2
1   | 0 2 1
2   | 2 1 0

```

If we want to define XOR for decimal preserving the above mentioned property we can do it similarly. Of course, there wont be a unique way to this. And since there is no unique way to do this, there is no standard definition of XOR for decimal digits. It is cook your own definition kind of thing.

# Answer
> 2 votes
No, there is no intuitive meaning in terms of decimal. Bitwise operations are defined (literally) as operations on bits, and bits don't correspond directly to decimal digits.

# Answer
> 1 votes
XOR does have meaning on how decimal numbers are stored especially if you are considering using signed decimal notation. I think of XOR because it is useful in calculations requiring the 2's Complement.

You need to learn how negative numbers are stored in computers and also consider instances where Big Endian and Little Endian are used when testing your code.

# Answer
> -1 votes
Normal "or" operation contains "and +or" (means we also treat the both true cases as true which is and) but this doesn't gives rise to all possible combinations. For example consider there is one red and one white box, which contain balls of a certain colour. If the box contains same colour ball (eg., red box-red ball) let's denote that by bit 1 and denote all other cases by bit 0. We want to know whether only one box contains the same colour ball or both. In this case the normal "or" operation can't give the required output so we use exclusive or "xor" operation. Xor is used to compare if two signals (inputs) have correlation (similarity). So the physical meaning is not decimal or hexadecimal format the input is. It will always be converted to binary format to compare the similarity between two numbers. In a nutshell mainly tells the similarity between two things.

---
Tags: logic, arithmetic, xor
---


# Question
Title: What happens if you run Kosaraju’s algorithm on a DAG?
What happens if you run Kosaraju’s algorithm for finding strongly connected components of directed graphs on a DAG?

# Answer
We should think about the property of SCC(strongly connected component)

A directed graph $G(V, E)$ is acyclic if and only if $G$ has no SCCs with more that one vertex. Because a directed cycle is SCC by definition of the cycle.

Hence, the result of the **Kosaraju’s algorithm on a DAG** will return $|V|$ trivial SCCs. In other words, it returns $\\{\\{v\\}\mid v\in V\\}$.
> 3 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?
$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff

1. If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$ is recursively enumerable, then $L'$ is in $S$
2. If $L$ is an infinite language in $S$, then there exists at least one finite subset of $L$ that is in $S$
3. The set of all finite languages in $S$ is enumerable, i.e. a Turing machine can list all the finite languages in $S$

Source of the statement: https://cs.stackexchange.com/q/2322 and some online notes

Isn't the 3rd one contradictory to the 1st one?

# Answer
No, it is not contradictory. Both conditions are *positive* in the sense that they "put things in $S$", so they cannot be at odds with each other.

There is an equivalent formulation of $S$: there is an r.e. set $B$ of finite languages such that $$S = \\{L \mid \text{$L$ is r.e. and $\exists L\_0 \in B \\,.\\, L\_0 \subseteq L$}\\}.$$ In words: $S$ is generated by an r.e. set of finite language $B$ in the following way: $S$ contains precisely all r.e. languages which contain an element of $B$.
> 2 votes

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: The reverse DFA is not working as expected
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:

And I reversed the DFA according to this answer (designing a DFA and the reverse of it)

I expected this DFA to accept all strings that start with "10" but it is not. What is my mistake in drawing the reverse DFA?

# Answer
Answering my own question based on the comment by Hendrik Jan:

The reverse DFA is correct. It is just that it is not deterministic. It's an NFA, so we should follow all the paths possible. And if we do so, it will accept all the strings starting with "10".

Example: assume we want to test this string: "10001". and assume that states are named 1, 2, and 3 from the right. By following this path, the NFA accepts the input string: "1,2,2,2,3,3"
> 1 votes

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Making sure the Branch Target Buffer stays accurate
As i've been told , a Branch Target Buffer (BTB) acts a lot like a cache for Branches , keeping a map of where branches are in the address space.

If implemented well , it should allow the processor to detect branches before even decoding them , redirecting the PC to the presumed target ( with the help of the branch predictor proper).

But the BTB is presumed to be accurate about where the branches are. You don't want the processor to jump when encountering an ADD instruction for example , meaning the instruction PC has to be an exact match with what is in the BTB.

Here's my question :

Most Processors support self modifying code (for better or for worse). This means that a branch instruction in main memory has the potential to be overwritten by data or another instruction. If said branch is already present in the BTB , this could result in BTB information being stale. In such a case , the processor might jump in response to a non-existent branch , resulting in an incorrect program result.

My initial solution to this was to just compare every memory write against what is present in the BTB. But this would be inefficient (requiring additional ports and potentially slowing down the machine) and most memory writes to not overwrite branch instructions or instructions at all for that matter.

Is there a better way to do this? something i've missed ?

I've looked around already , but couldn't find any information .

# Answer
> 1 votes
The BTB is not really presumed to be accurate. It cannot be accurate. Even putting SMC aside, indirect and other variable-target jumps cannot have their target predicted perfectly. That is not a correctness problem though, the control flow instructions can be executed and at that point it becomes possible to verify the actual target and do the usual front-end-redirect and pipeline flush if the target does not match.

But that does not solve the SMC problem in general. If you need to make SMC work as if the processor is strictly serial, some extra checks are necessary. The checks can be quite conservative and still perform well when SMC isn't happening, which is usually the main case. For example, you can check whether a write is to a code page, and insert an appropriate flush (after the write) if it does. Of course such a coarse test is easily fooled by just marking a data page executable, even if it is never jumped into, needlessly degrading performance. An other strategy might be to check, at retirement of any instruction, whether its page is marked dirty (this makes SMC have a "long shadow", any modification "ruins" a code page until its dirty bit is reset). More precise mechanisms are possible.

---
Tags: computer-architecture
---


# Question
Title: Logic gate which checks if the input is a negative number and changes its output based on that
I need to create a HDL which will use logic gates to demonstrate if something is a negative number in two's complement. The input is 8 bits, while the output is 1 bit, and if the input is a negative number then the output should be true, and in any other case, the output should be false.

I've noticed that all the negative numbers in two's complement start with a 1 in their binary notation, i.e the number -8 is written as 1000 in binary, -7 as 1001 and so on until 0, which is when it switches to 0000, 1 being 0001 and so on until +7.

I originally had the idea of using a Not gate for this, but i'm not entirely sure how it would work out. I tried something like:

```
Not(in=in[1], out=in[2]);
Not(in=in[2], out=in[3]);

```

etc but it didn't work. I also thought of using an Or gate, as if either of the inputs are true (negative number) then the output would also be true to signify a negative number, but if both of the inputs are false (not negative) then the output would also be false.

Any help?

# Answer
You miss the obvious solution, just wire the MSB to output.
> 2 votes

---
Tags: logic, boolean-algebra
---


# Question
Title: How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?
How to show that the following language is not regular with the pumping lemma?

$$L=\left\\{0^{n\lceil\log\_2 n\rceil} \\,\middle|\\, n\in \mathbb{N}-\\{0\\}\right\\}.$$

# Answer
> 3 votes
(**Dense-length lemma for regular languages**) Let $R$ be an regular language that has infinitely many words. Then there exists a number $d$ such that for any word in $R$, there is another word such that the difference of the lengths of both words is less than $d$.

The above lemma says, basically, the lengths of words in a regular language cannot be too sparse anywhere. It can be proved easily using the pumping lemma for regular languages.

Let us take a look at $L$. The lengths of its word are $\\{n\lceil\log\_2 n\rceil \\,\mid n\in \Bbb{N}-\\{0\\}\\}$. When $n$ goes larger and larger, the lengths become sparser and sparser because of the factor $\lceil\log\_2n\rceil$. In fact, if $n\>2^d$, $m\>2^d$ and $n\not=m$, then $\left|n\lceil\log\_2n\rceil-m\lceil\log\_2m\rceil\right| \> d$. So $L$ cannot be regular because of the above lemma.

---

Exercise 1. Prove the dense-length lemma for regular languages.

Exercise 2. Prove the dense-length lemma also holds for context-free languages that have infinitely many words.

Exercise 3. Does the dense-length lemma hold for context-sensitive languages?

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Using Yao's principle to find a lower bound
This is a HW question, so I'm not expecting any answers, just a general guidance/help.

Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\\{ 0,1\right\\} ^{n}$, a function $f:\left\\{ 0,1\right\\} ^{n}\to\left\\{ 0,1\right\\} ^{n}$ will be called **s-difference-preserving** if for all $x,y\in\left\\{ 0,1\right\\} ^{n}$ s.t. $x\neq y$: $x\oplus y=s\iff f\left(x\right)=f\left(y\right)$ (where $\oplus$ is the bitwise xor operation).

Given a difference-preserving (that is, there exists such s so it is s-difference-preserving) function $f$, we talk about algorithms that find such $s$.

We need to prove that every such random (las-vegas) algorithm worst case (w.c. input) average (on the randomness of the algorithm) complexity is $\Omega\left(\sqrt{2^{n}}\right)$. Where by complexity, we talk about **query-complexity**. That is, how many times we need to query f, to find a value for an input $x$ \- that is, find $f\left(x\right)$.

What I know and tried so far:

I assume this is a classic problem for Yao's principle.
So I want to find a distribution, and an optimal deterministic algorithm for it (optimal on average, on that distribution), such that its query-complexity is \Omega\left(\sqrt{2^{n}}\right) on average on that distribution.

Given an $s$, it's easy to create an s-difference-preserving function, since any $s$ defines a partition of pairs on $\left\\{ 0,1\right\\} ^{n}$. So we just need to choose a different value for every pair $x,y$ s.t. $x\oplus y=s$.

I also know $f\left(0\right)=f\left(s\right)$, and that to find $s$ for a fuction, it's enough to find a pair $x,y$ s.t. $f\left(x\right)=f\left(y\right)$, and then calculate $x\oplus y$.

I thought of defining $\forall i\in\left\[\sqrt{2^{n}}\right\]:\ s\_{i}=i\cdot\sqrt{2^{n}}-1$. And create $s\_{i}$-difference-preserving function $\forall i\in\left\[\sqrt{2^{n}}\right\]$.

Define a uniform distribution on them and have the deterministic algorithm check the values of every $s\_{i}$. This is done in $\sqrt{2^{n}}$ queries on average.
But I don't know how to prove this algorithm is optimal for that distribution. Furthermore, I suspect it isn't, since then I would be able to do the same with $s\_{i},\ \forall i\in\left\[2^{n}\right\]$ and “prove” a lower bound of $2^{n}$ which is probably not true.

I would love any help with this.
Also, not as part of the HW, but because I'm interested (these are questions we don't need to submit a solution to), can you think of any deterministic algorithm for the general problem? can you think of any monte carlo random algorithm (with 0.5 chance of success)?

I hope this is not too long, and written clearly enough. Would appreciate any help. Thanks!

# Answer
Suppose that there exists a Las Vegas algorithm $A^f$ asking $q(n)=o\big(2^{n/2}\big)$ queries. Let $Q\_f\subseteq\\{0,1\\}^n$ be the random variable which denotes the set of queries raised by the algorithm with oracle $f$.

Sample $f$ from the uniform distribution over the collection of all difference preserving functions, and choose $s\in\\{0,1\\}^n$ uniformly at random, both independently from your algorithm's coins. Let us now ask what is the probability that there exists $g,g':\\{0,1\\}^n\rightarrow\\{0,1\\}^n$ such that $g,g'$ agrees with $f$ on $Q\_f$, $g$ is $s$-difference preserving, and $g'$ is not. We denote this probability by $p\_A$. Note that if $p\_A\>0$ then your algorithm cannot respond correctly on all inputs, since there exists $f,s$ such that $f|\_{Q\_f}$ has both $s$-preserving and non $s$-preserving extensions.

If $f|\_{Q\_f}$ does not have an $s$-preserving extension, then either there exists $x\in Q\_f$ such that $x\oplus s\in Q\_f$, or we have $x,y\in Q\_f$ with $f(x)=f(y)$. For the first case, Note that $x\oplus s$ is uniformly distributed over $\\{0,1\\}^n$ and independent of $Q\_f$, thus the probability that there exists such $x$ is bounded by $\sum\limits\_{x\in Q\_f}\frac{|Q\_f|}{2^n}\le\frac{q^2(n)}{2^n}=o(1)$. A similar bound is obtained for finding a collision for a random $f$ (the preimage of any element in the range of $f$ is of size 2). Additionally, $f$ is not $s$ preserving with probability $\ge\frac{1}{2^n}$, so we can also (with high probability) find a non $s$ difference preserving extension for $f$.
> 1 votes

---
Tags: algorithms, randomized-algorithms, lower-bounds, xor
---


# Question
Title: How to eliminate ambiguity of the follwing CFG?
Consider the following CFG:

$S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$

The CFG produces $a^\*bbb...ccc...d^\*$ (equal number of b,c) and $aaa...b^\*c^\*ddd...$ (equal number of a,d)

There is ambiguity since $abbccd$ can be derived respectively by $S\to AED$ and $S \to F$. I try to rewrite the production rule like: $$S\to AED\\E\to BC$$ But my CFG produces $a^\*b^\*c^\*d^\*$ which is different from original. Could anyone give me some tips?

# Answer
Basically you have $L = L\_1 \cup L\_2$ where $L\_1 \cap L\_2 \ne \emptyset$. So naively writing the two productions:

$$L \to L\_1 \\ L \to L\_2 $$ will create an ambiguity. What's needed is to create $Ḷ\_1' = L\_1 - L\_2$ in order to use the CFG $$L \to L\_1' \\ L \to L\_2 $$ This produces the same language, resolving the ambiguities in favour of $L\_2$.

Context-free languages are not closed under set difference, so this is not a general solution. But in this particular case there is no problem.

Suppose we start with the two languages $L\_1 = \\{ a^ib^jc^kd^i \\}$ and $L\_2 = \\{ a^ib^jc^jd^k \\}$, which are not disjoint since $\\{a^ib^jc^jd^i\\}$ is a subset of both.

So we define $$Ḷ\_1' = L\_1 - L\_2 = \\{ a^ib^jc^kd^i \mid j \ne k\\}$$ and are pleased to observe that it is context-free:

$$\begin{align}L\_1' &\to E \mid a \\; L\_1'\\; d\\ E &\to B \mid C \mid b \\; E \\;c\\ B &\to b \mid B b \\ C &\to c \mid C c \end{align}$$

Meanwhile, $L\_2$ is simply

$$\begin{align}L\_2 &\to A\\; F\\; D \\ F &\to \lambda \mid b\\;F\\;c \\ A &\to \lambda \mid A a \\ D &\to \lambda \mid D d \end{align}$$
> 1 votes

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: Traversing a graph in finite time, maximizing utility
I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any action to another after completing that particular action, and each transition takes a unique, finite time. Our goal is maximize the sum of the utilities after the time horizon has ended.

I am currently thinking of this as a graph problem, and have some trouble formalizing it.

Let the nodes be the actions, and the edges be the transition between the actions. Each node have some value, and take some time T. How do I find the path in this graph which maximizes the utility, and takes time less than or equal to T?

# Answer
> 3 votes
This problem is an instance of the Orienteering problem, a combination of the knapsack and the travelling salesman.

A good survey is https://www.sciencedirect.com/science/article/pii/S0377221710002973

# Answer
> 4 votes
I think this is the knapsack problem, with the following correspondences:

* item: activity
* item weight: activity performance time
* item value: activity utility
* knapsack maximum weight: finite time horizon T

One solves it using dynamic programming.

(I don't think a graph model would be useful here, as it does not seem easy to encode the problem into a standard graph problem.)

---
Tags: graphs, weighted-graphs
---


# Question
Title: Can such an operation be done with two stacks?
Assume a Forth-like environment with two stacks, a main one and an auxiliary one. The following operations can be done on the main stack: `DUP` (duplicate the top element), `SWAP` (swap the top two elements), `DROP` (drop the top value), `PUSH` (move the top value to the auxiliary stack) and `PULL` (move the top value of the auxiliary stack to the primary one).

If the main stack is organized like this (top-bottom): `x <x elements> y <y elements> z <z elements>`, where x, y and z are integers preceding the corresponding number of arbitrary elements, is it possible to re-arrange it like this: `x <x elements> z <z elements> y <y elements>` using only the operations described above?

If not, what operations can be added to satisfy this condition?

# Answer
> 1 votes
You do not need more operations. In fact, you do not need DUP and DROP, either. **All you need are SWAP, PUSH and PULL**.

The list of states of main stack below shows how the initial state `1 a 3 p q r 2 x y` is changed to `1 a 2 x y 3 p q r`. The auxiliary stack is at left hand side growing to the right from its bottom at the very left. The main stack is at right hand side growing to the left from it bottom at the very right. `<-` means PUSHing to the auxiliary stack and `->` mean PULLing from the auxiliary stack.

```
   <- 1 a 3 p q r 2 x y  //initial state
 1  <-  a 3 p q r 2 x y
 1 a  <-  3 p q r 2 x y
 1 a 3  <-  p q r 2 x y
 1 a 3 p  <-  q r 2 x y
 1 a 3 p q      r 2 x y  //then SWAP
 1 a 3 p q  ->  2 r x y
 1 a 3 p      q 2 r x y  //then SWAP
 1 a 3 p  ->  2 q r x y
 1 a 3      p 2 q r x y  //then SWAP
 1 a 3  ->  2 p q r x y
 1 a      3 2 p q r x y  //then SWAP
 1 a  <-  2 3 p q r x y
 1 a 2  <-  3 p q r x y
 1 a 2 3  <-  p q r x y
 1 a 2 3 p  <-  q r x y
 1 a 2 3 p q      r x y  //then SWAP
 1 a 2 3 p q  ->  x r y
 1 a 2 3 p      q x r y  //then SWAP
 1 a 2 3 p  ->  x q r y
 1 a 2 3      p x q r y  //then SWAP
 1 a 2 3  ->  x p q r y
 1 a 2      3 x p q r y  //then SWAP
 1 a 2  <-  x 3 p q r y
 1 a 2 x  <-  3 p q r y
 1 a 2 x 3  <-  p q r y
 1 a 2 x 3 p  <-  q r y
 1 a 2 x 3 p q      r y  //then SWAP
 1 a 2 x 3 p q  ->  y r
 1 a 2 x 3 p      q y r  //then SWAP
 1 a 2 x 3 p  ->  y q r
 1 a 2 x 3      p y q r  //then SWAP
 1 a 2 x 3  ->  y p q r
 1 a 2 x      3 y p q r  //then SWAP
 1 a 2 x  ->  y 3 p q r
 1 a 2  ->  x y 3 p q r
 1 a  ->  2 x y 3 p q r
 1  ->  a 2 x y 3 p q r
      1 a 2 x y 3 p q r  //final state

```

Once you have checked the above procedure, you will understand how to proceed in the general situations. In fact, what have been shown above is, basically, the well-known fact that if you can swap any two adjacent elements in an array, you can sort all elements in the array into any permutation you wanted.

---
Tags: stacks
---


# Question
Title: Understanding basic queue and dequeue operations
CLRS gives the following implementation for a queue's enqueue and dequeue operations

```
head = 1
tail = 1

ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1
else Q.head = Q.head + 1
return x

```

but I'm having trouble understanding why both

```
if Q.tail == Q.length
    Q.tail = 1

```

and

```
if Q.head == Q.length
    Q.head = 1

```

are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?

# Answer
> 3 votes
CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position.

From the book,

> The elements in the queue are in locations head\[Q\], head \[Q\] + 1, . . . , tail \[Q\] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.

Thus,

> if Q.tail == Q.length

This is for the condition when the tail points to the last element.

> if Q.head == Q.length

This is for the condition when the head points to the last element.

In both cases, we move to the first element due to circular nature.

An example would be this:

---
Tags: data-structures, queues
---


# Question
Title: Complexity of two cycles which differ by $1$ in length
Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length.

What is the complexity of this problem?

# Answer
> 0 votes
It belongs to NP obviously, and is NP-complete by a reduction from the Hamilton cycle problem on bipartite graph.

Given a bipartite graph with $2n$ vertices, add an isolated simple cycle of length $2n+1$. Since there is no odd cycle in a bipartite graph, the new graph has two cycles which differ by 1 in length if and only if there is a Hamilton cycle in the bipartite graph.

---
Tags: complexity-theory, graphs, np-complete, np-hard, np
---


# Question
Title: How can a 64-bit processor address 2^64 different memory locations at a time?
I understand that a 64-bit processor can hold a 64-bit long address and that a 64-bit address can represent $2^{64}$ different values. But I don't understand why that processor can address $2^{64}$ different locations in memory at one time and thus process billions of billions of GB at a time (theoretically).

I haven't found a satisfying answer on google. On google they just explain that a 64-bit address can represent $2^{64}$ different values and thus it equates to the processor being able to process $2^{64}$ values (or memory locations) at a single time, though I am interested in as much detail as possible regarding how exactly that looks like.

64-bit address means for me that this address can have one of $2^{64}$ possible values and not that it can process $2^{64}$ at a time.

# Answer
It's not clear where you found this claim so it's hard to tell exactly what it's supposed to mean.

But, obviously, no, the CPU can't access every memory location simultaneously. Each CPU instruction can only access some fixed small number of memory locations at a time, and only a fixed small number of instructions can be executing simultaneously.
> 2 votes

# Answer
Let us use an analogy hear we know that phone number we use is 10 digits hence we can have $10^{10}$ unique phone numbers or combinations hear, but you may call only a few numbers at a time. similarly if you have 32 bit address lines you can address up to $2^{32}$ memory locations & each memory location can store one byte(8bits)of data, hence total memory accessed is 4GB(4 giga bytes). but if the processor is 32 bit doesn't mean that it's address bus is 32 bit, it might have more address busses ,for example take processor which is 32 bit. It's address maybe 64 bit ,the address is stored in two 32 bit registers, while addressing they combine them to enhance address capability to $2^{64}B$. Note:- 8 bits=1byte(1B),1024B($2^{10}B$)=1KB,1024KB($2^{20}B$)=1MB,1024MB($2^{30}B$)=1GB hence$2^{32}B=2^2\*2^{30}B=4GB$,so you can find out what $2^{64}$is.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...

> Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$

So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ \[0,1\] and returns $0$ if $f \< 0.5$, $1$ if $f \geq 0.5$.

I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $\frac{1}{4}$... and I can expand that solution to any $p$ where $p = \frac{1}{2^x}$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...

I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?

# Answer
> 3 votes
Suppose $p=\sum\limits\_{n=1}^\infty \frac{1}{2^n}p\_n$, where $p\_n\in\\{0,1\\}$, i.e. $p\_1p\_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c\_1c\_2...$ until you reach $i$ such that $p\_i \neq c\_i$, and output heads iff $p\_i\>c\_i$. The probability of generating heads in exactly $k$ iterations is $2^{-(k-1)}\frac{p\_k}{2}$, thus the probability of generating heads is $\sum\limits\_{k=1}^{\infty}2^{-k}p\_k =p$. The expected number of iterations is $2$.

Note that the above requires you to be able to output $p\_i$ given $i$, so this will not work for noncomputable $p$.

---
Tags: logic, probability-theory, random-number-generator
---


# Question
Title: If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?
I came across this question while studying for an exam:

> T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ time algorithm.

I think the answer is false, since we can't reduce NP-complete to NP-hard in linear time, right? Or am I completely misunderstanding reductions/NP problems? Any help would be greatly appreciated. Thank you.

# Answer
Yes, the answer the the question is "false".

By contradiction, assume every problem in $NP$ has a $O(n^k)$ algorithm, for some fixed $k$. That is, $NP \subseteq {\sf DTIME}(O(n^k))$

This would contradict the time hierarchy theorem, which implies the *strict* inclusion

$$ {\sf DTIME}(O(n^k)) \subset {\sf DTIME}(O(n^{2k})) $$

However, we also have

$$ {\sf DTIME}(O(n^{2k})) \subseteq NP \subseteq {\sf DTIME}(O(n^{k})) $$

which contradicts the previous strict inclusion.
> 4 votes

# Answer
> If $\mathbf{P} = \mathbf{NP}$, can all $\mathbf{NP}$ problems be solved within time $O(n^k)$ for fixed $k$?

No, because the time hierarchy theorem says that there are problems that can be solved in time $O(n^{k+1})$ that can't be solved in time $O(n^k)$.

> we can't reduce NP-complete to NP-hard in linear time

Any $\mathbf{NP}$-complete problem is $\mathbf{NP}$-hard by definition.
> 3 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard, np
---


# Question
Title: How to prove that the erosion of a convex set by a convex set will result in a convex set?
How to prove that given convex sets A and B, the erosion of A by B will result in C - a convex set, too?

I was given this question as a test-preparation, and I think it shuold be a proof, but I don't know how to prove it.

A convex set is a set where every line connecting 2 dots in the set, must be part of the set, too. Now, if I would take a convex set A, I don't see how can I use erosion on it to get a non-convex set. Every example I try to create ends up the empty set, because the "holes" in B that are suppose to the "holes" in C, make C be all-zero.

Can someone help with a direction to a proof? Thanks

# Answer
(**Convexity is closed under intersection**) Given a family of convex set $C\_i$, where $i\in I$ for some index set $I$, then $\cap\_{i\in I}C\_i$ is convex.

In other words, the intersection of convex sets are convex.

Proof. Suppose two points $p$ and $q$ are in $\cap\_{i\in I}C\_i$. That is, for each $i\in I$, $p\in C\_i$ and $q\in C\_i$. Consider $L$, the line segment between $p$ and $q$. By the definition of convexity, $L\subseteq C\_i$. That is $L\subseteq \cap\_{i\in I}C\_i$. By the definition of convexity again, $\cap\_{i\in I}C\_i$$ is convex.

(**Convexity is closed under translation**) If $C$ is a convex set, then $C\_t=\\{x+t\mid x\in C\\}$ is also convex.

In other words, if you translate a convex set, you will get a convex set.

Proof is skipped.

(Convexity is closed under erosion) Suppose $A$ is a convex set. Let $B$ be another set. Then the erosion of $A$ by $B$ is convex.

Proof. I will let you figure out given the above two lemmas. Another hint is given in the statement itself, which is, you do not need $B$ to be convex at all.

---

Is the erosion of $A$ by $B$ always empty?

Imagine both $A$ and $B$ are disks centered at the origin. $A$ is a huge while $B$ is a very small. Then the "erosion" by $B$ can only remove a small stripe along the circumference of $A$. The inner part of $A$ will not be "eroded". So the erosion of $A$ by $B$ will keep a significant part of $A$.

You can also check an example on Wikipedia.
> 3 votes

# Answer
I'll add here a full answer using @Apass.Jack helpful hints:

Erosion of $A$ by $B$ can be represented as $\cap\_{b\in B} A\_{-b}$, meaning a intersection of all sets A translated by $-b$ for all $b$ in $B$.

Given the 2nd lemma - *Convexity is closed under translation*, so all the sets in the intersection are convex. Using that, and the 1st lemma - *Convexity is closed under intersection*, we end up with a convex set :-)

Using this proof it is obvious that B need not be convex set at all, since no matter what is the shape of B, the translation of A by any $-b \in B$ would still be *convex set* if A is convex.
> 2 votes

# Answer
This can be deduced from the definition of the *erosion*. According to the wiki article we define $$B\_z=\\{b+z\mid b\in B\\}$$ and the *erosion* of the 'binary image' $A$ by the 'structuring element' $B$ as $$A\circleddash B=\\{z \in E\mid B\_z\subseteq A\\}$$ The symbol $E$ is either $\mathbb{R}^n$ or $\mathbb{Z}^n.$

Now assume that $A$ is convex and $z\_1, z\_2 \in A \circleddash B$ and $z\_3$ is on the line between $z\_1$ and $z\_2.$ We have to show that $z\_3 \in A \circleddash B$, which means $B\_{z\_3}\subseteq A.$

Then there is a $\lambda\_3 \in \[0,1\]$ such that

$$z\_3=\lambda\_3 z\_1+(1-\lambda\_3) z\_2.$$

If $t\_3 \in B\_{z\_3}$ then $t\_3-z\_3 \in B$ and so $$t\_3-z\_3+z\_1 \in B\_{z\_1}\subseteq A$$ $$t\_3-z\_3+z\_2 \in B\_{z\_2}\subseteq A$$ Because both numbers are in the convex set $A$ and
$$\lambda\_3(t\_3-z\_3+z\_1)+(1-\lambda\_3)(t\_3-z\_3+z\_2)=t\_3$$ we have $t\_3 \in A.$ This holds for all $t\_3 \in B\_{z\_3}.$ So $B\_{z\_3} \subseteq A$ and this implies $z\_3 \in A\circleddash B.$ Therefore $A\circleddash B$ is convex.
> 2 votes

---
Tags: image-processing
---


# Question
Title: Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity?
With locality sensitive hashing (specifically multi-probe hashing http://www.cs.princeton.edu/cass/papers/mplsh\_vldb07.pdf) how are the guarantee of similarity returns made? Why are there multiple tables involved in the hash indexing? Wouldn't that make it LESS probable that an item hashed to a bucket is similar to another rather than the reverse?

# Answer
LSH indexing first concatenates $k$ simple hash functions $h$ to produce a function $g$. Note that $g$ is a regular LSH function, only with slightly different parameters. In particular, probabilities of collision decrease for both near and far objects. The new probabilities are $p'=p^k$.

Then they take $L$ such functions $g$ and produce $L$ hash tables. Then we search through *all* the hash tables, one by one. This effectively increases the probability of collision. The new probabilities are $p''=1-(1-p^k)^L$. Note that this function has a sigmoid shape.

It may seem weird to first reduce $p$ and then increase it. However, the parameters $k, L$ are useful knobs for controlling the behavior of the algorithm. You could certainly run with $k=L=1$, but larger values may perform better.
> 1 votes

# Answer
Why? Because using a single hash table is not sufficient: you might miss some matches. Suppose that if you use a single hash table, then a lookup has a 50% chance of returning each match that exists (and a 50% chance of failing to find the match). Then you might choose to use 100 hash tables; look up in each table; and combine all the results from all of the lookups: if you find a match in any of the 100 lookups, then you output it. This reduces the chances of missing a valid match: the probability that a valid match is not found in *any* of the 100 tables is reduced to $1/2^{100}$.

This is why using multiple hash tables helps. It reduces the chances of errors. It does come at some cost -- you increase the space usage and the time to find matches -- but it can be a useful tradeoff, as a linear increase in space and time leads to an exponential decrease in the error probability.
> 0 votes

---
Tags: hashing
---


# Question
Title: How does the system know how to read the correct block from a disk?
I am watching this video (https://www.youtube.com/watch?v=aZjYr87r1b8) and up to the ~6 minute mark, he explains the disk structure and how when you want to read a block, the spinner spins to the correct sector and the arm to the correct track. How do the spinner know where the correct sector is? How does the arm know where the correct track is? And how do they know they are reading from the beginning of the block and not in the middle of it?

# Answer
Finding the right track is relatively easy. There is a motor which can be moved a precise distance. Then the head can measure magnetism to the right and the left and use this to move to the precise centre of the track.

The sectors all have a header. The read head passes sectors at high speed. The start of the header has a distinct pattern that cannot be found inside a sector. So the read head can wait until it finds the start of a sector. The header also contains a number identifying the sector so the read head knows when it reaches the correct sector and can start reading.

In practice, all sectors on the track will be read in case another sector is needed soon after.
> 1 votes

---
Tags: memory-hardware
---


# Question
Title: How do you go from $\log P = \log N$ to the next step?
> Let \begin{align\*} &P=2^{\log\_2 N}\\ &\Rightarrow \log\_2 P = \log\_2 N\\ &\Rightarrow P=N\\ &\Rightarrow 2^{\log\_2 N}=N\\,. \end{align\*}

I don't understand how can you just drop the logs and go straight to $P = N$. Can someone please explain this to me? Am I missing a log rule?

# Answer
Two positive real numbers are equal if and only if their logarithms are equal. This is because $\log$ is a strictly increasing function that grows without bound and is defined for all positive reals: it is, therefore, a bijection from $\mathbb{R}\_{\>0}$ to $\mathbb{R}$.

Clearly, if $x=y$ then $\log x=\log y$. If $x\neq y$ then suppose $x\>y$ (the case $x\<y$ is identical). Because $\log$ is strictly increasing, $x\>y$ implies that $\log x\>\log y$ so, in particular, $\log x\neq \log y$. Therefore, $x=y$ if, and only if, $\log x=\log y$.
> 3 votes

# Answer
Let us review the definition of log, as shown on Wikipedia, slightly edited.

> In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number $x$ is the exponent to which another fixed number, the base $b$, must be raised, to produce that number $x$.
>
> More explicitly, the defining relation between exponentiation and logarithm is
> $\quad\log \_{b}(x)=y$ exactly if and only if $b^{y}=x$. For example, $log\_2 64 = 6$, as $64 = 2^6$.

Let us take a look at the deductions in the question.

\begin{align\*} &P=2^{\log\_2 N}\\ &\Rightarrow \log\_2 P = \log\_2 N &\text {// the first implication}\\ &\Rightarrow P=N &\text {// the second implication}\\ &\Rightarrow 2^{\log\_2 N}=N\\,. &\text {// the third implication}\\ \end{align\*}

If you replace $b$ by 2, $y$ by $\log\_2N$, and $x$ by $P$ in the definition, you have obtained the first implication. You can also say, since the result of raising 2 to the exponent $\log\_2N$ is $P$, then by definition, that exponent, $\log\_2N$ is $\log\_2P$.

Now look at the second equality. **You can raise 2 to the power of the left hand side, obtaining $P$ by definition. You can also raise 2 to the power of the right hand side, obtaining $N$ by definition. So $P=N$, which is the second implication**.

In fact, you can go directly from the first equality to the third equality by definition directly. Since $\log\_2 N$ is the exponent to which 2 must be raised to produce $N$, i.e., $2^{(\log\_2N)}=N$, so $P=N$.

Well, I cannot say the third implication is wrong in the sense that you can never say it is wrong that "2=2" implies "3=3" since both of them are correct.

Instead, I will say the last equality is the very definition of logarithm. If you raise 2 to the power of some number and you get $N$, then that (unique) number is (defined as) $\log\_2N$.

---

The most powerful, most basic, most natural and most correct way in mathematics is **(using) definitions**. People sometimes forget about what or where are the definitions. Instead they might resort to some kind of intuition, which might be helpful and important in various ways. However, the definitions will always be the most fundamental piece that one should be become familiar. For myself, I believe I should have read most if not every definition in math that I am supposed to read at least 10 times. Your mileage may vary a lot, of course.

By the way, here is the more complete definition/explanation of logarithm.

> In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number $x$ is the exponent to which another fixed number, the base $b$, must be raised, to produce that number $x$. In the simplest case the logarithm counts repeated multiplication of the same factor; e.g., since 1000 = 10 × 10 × 10 = 103, the "logarithm to base 10" of 1000 is 3. The logarithm of $x$ to base $b$ is denoted as $log\_b (x)$ (or, without parentheses, as $\log\_b x$, or even without explicit base as $\log x$, when no confusion is possible). More generally, exponentiation allows any positive real number to be raised to any real power, always producing a positive result, so the logarithm for any two positive real numbers $b$ and $x$ where $b$ is not equal to 1, is always a unique real number y. More explicitly, the defining relation between exponentiation and logarithm is:
> $\quad\log \_{b}(x)=y$ exactly if $b^{y}=x$. For example, $log\_2 64 = 6$, as $64 = 2^6$.

Please note that, there is a fundamental piece that is not include in that part of Wikipedia entry. That is, why can we define the inverse function of exponentiation? Recall that not all functions can have inverse functions. That question is addressed later at https://en.wikipedia.org/wiki/Logarithm#Logarithmic\_function. From logic point of view, we should first prove that exponentiation with some base is strictly decreasing when the base is smaller than 1 and strictly increasing when the base is greater than 1. Then we can define its inverse, logarithm with respect to that base.
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: Post numbers in DFS tree of an undirected graph
How could you prove:
An edge (u,v) is part of an **undirected graph G**. If post(u) $\<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the DFS tree.

So far I have understood that it does in fact imply that so I need to prove this. I have thought of doing it by contradiction but not exactly sure how I would go about doing that.

# Answer
> 1 votes
You conclusion is correct.

Here is (the sketch of) a proof.

* If pre($u$) \< pre($v$), the search must discover and finish $v$ before it finishes $u$, since $v$ is on $u$’s adjacency list. That is, post($v$) \< post($u$) and $v$ is in the subtree rooted at $u$.
* If pre($v$) \< pre($u$), the search must discover and finish $u$ before it finishes $v$, since $u$ is on $v$’s adjacency list. That is, post($u$) \< post($v$) and $u$ is in the subtree rooted at $v$.

---
Tags: algorithms, graphs, graph-traversal
---


title: Confluence of beta expansion

text:
# Question
Title: Confluence of beta expansion
Let $\to\_\beta$ be $\beta$-reduction in the $\lambda$-calculus. Define $\beta$-expansion $\leftarrow\_\beta$ by $t'\leftarrow\_\beta t \iff t\to\_\beta t'$.

Is $\leftarrow\_\beta$ confluent? In other words, do we have that for any $l,d,r$, if $l \to\_\beta^\* d\leftarrow\_\beta^\* r$, then there exists $u$ such that $l\leftarrow\_\beta^\* u \to\_\beta^\* r$?

Keywords: Upward confluence, upside down CR property

---

I started by looking at the weaker property: local confluence (i.e. if $l \to\_\beta d\leftarrow\_\beta r$, then $l\leftarrow\_\beta^\* u \to\_\beta^\* r$). Even if this were true, it would not imply confluence since $\beta$-expansion is non-terminating, but I thought that it would help me understand the obstacles.

**(Top)** In the case where both reductions are at top-level, the hypothesis becomes $(\lambda x\_1.b\_1)a\_1\rightarrow b\_1\[a\_1/x\_1\]=b\_2\[a\_2/x\_2\]\leftarrow (\lambda x\_2.b\_2)a\_2$. Up to $\alpha$-renaming, we can assume that $x\_1\not =x\_2$, and that neither $x\_1$ nor $x\_2$ is free in those terms.

**(Throw)** If $x\_1$ is not free in $b\_1$, we have $b\_1=b\_2\[a\_2/x\_2\]$ and therefore have $(\lambda x\_1.b\_1)a\_1=(\lambda x\_1.b\_2\[a\_2/x\_2\])a\_1\leftarrow(\lambda x\_1.(\lambda x\_2.b\_2)a\_2)a\_1\rightarrow (\lambda x\_2.b\_2)a\_2$.

A naive proof by induction (on $b\_1$ and $b\_2$) for the case (Top) would be as follows:

* If $b\_1$ is a variable $y\_1$,

+ If $y\_1=x\_1$, the hypothesis becomes $(\lambda x\_1.x\_1)a\_1\rightarrow a\_1=b\_2\[a\_2/x\_2\]\leftarrow (\lambda x\_2.b\_2)a\_2$, and we indeed have $(\lambda x\_1.x\_1)a\_1=(\lambda x\_1.x\_1)(b\_2\[a\_2/x\_2\])\leftarrow (\lambda x\_1.x\_1)((\lambda x\_2.b\_2)a\_2)\rightarrow (\lambda x\_2.b\_2)a\_2$.
    + If $y\_1\not=x\_1$, then we can simply use (Throw).
* The same proofs apply is $b\_2$ is a variable.
* For $b\_1=\lambda y.c\_1$ and $b\_2=\lambda y.c\_2$, the hypothesis becomes $(\lambda x\_1.\lambda y. c\_1)a\_1\rightarrow \lambda y.c\_1\[a\_1/x\_1\]=\lambda y.c\_2\[a\_2/x\_2\]\leftarrow (\lambda x\_2.\lambda y.c\_2)a\_2$ and the induction hypothesis gives $d$ such that $(\lambda x\_1.c\_1)a\_1\leftarrow d\rightarrow (\lambda x\_2.c\_2)a\_2$ which implies that $\lambda y.(\lambda x\_1.c\_1)a\_1\leftarrow \lambda y.d\rightarrow \lambda y.(\lambda x\_2.c\_2)a\_2$. Unfortunately, we do not have $\lambda y.(\lambda x\_2.c\_2)a\_2\rightarrow (\lambda x\_2.\lambda y.c\_2)a\_2$. (This makes me think of $\sigma$-reduction.)
* A similar problem arises for applications: the $\lambda$s are not where they should be.

# Answer
> 8 votes
Two counterexamples are:

* $(\lambda x. b x (b c)) c$ and $(\lambda x. x x) (b c)$ (Plotkin).
* $(\lambda x. a (b x)) (c d)$ and $a ((\lambda y. b (c y)) d)$ (Van Oostrom).

The counterexample detailed below is given in *The Lambda Calculus: Its Syntax and Semantics* by H.P. Barenredgt, revised edition (1984), exercise 3.5.11 (vii). It is attributed to Plotkin (no precise reference). I give an incomplete proof which is adapted from a proof by Vincent van Oostrom of a different counterexample, in *Take Five: an Easy Expansion Exercise* (1996) \[PDF\].

The basis of the proof is the standardization theorem, which allows us to consider only beta expansions of a certain form. Intuitively speaking, a **standard reduction** is a reduction that makes all of its contractions from left to right. More precisely, a reduction is non-standard iff there is a step $M\_i$ whose redex is a residual of a redex to the left of the redex of a previous step $M\_j$; “left” and “right” for a redex are defined by the position of the $\lambda$ that is eliminated when the redex is contracted. The standardization theorem states that there if $M \rightarrow\_\beta^\* N$ then there is a standard reduction from $M$ to $N$.

Let $L = (\lambda x. b x (b c)) c$ and $R = (\lambda x. x x) (b c)$. Both terms beta-reduce to $b c (b c)$ in one step.

Suppose that there is a common ancestor $A$ such that $L \leftarrow\_\beta^\* A \rightarrow\_\beta^\* R$. Thanks to the standardization theorem, we can assume that both reductions are standard. Without loss of generality, suppose that $A$ is the first step where these reductions differ. Of these two reductions, let $\sigma$ be the one where the redex of the first step is to the left of the other, and write $A = C\_1\[(\lambda z. M) N\]$ where $C\_1$ is the context of this contraction and $(\lambda z. M) N$ is the redex. Let $\tau$ be the other reduction.

Since $\tau$ is standard and its first step is to the right of the hole in $C\_1$, it cannot contract at $C\_1$ nor to the left of it. Therefore the final term of $\tau$ is of the form $C\_2\[(\lambda z. M') N'\]$ where the parts of $C\_1$ and $C\_2$ to the left of their holes are identical, $M \rightarrow\_\beta^\* M'$ and $N \rightarrow\_\beta^\* N'$. Since $\sigma$ starts by reducing at $C\_1$ and never reduces further left, its final term must be of the form $C\_3\[S\]$ where the part of $C\_3$ to the left of its hole is identical to the left part of $C\_1$ and $C\_2$, and $M\[z \leftarrow N\] \rightarrow\_\beta^\* S$.

Observe that each of $L$ and $R$ contains a single lambda which is to the left of the application operator at the top level. Since $\tau$ preserves the lambda of $\lambda z. M$, this lambda is the one in whichever of $L$ or $R$ is the final term of $\tau$, and in that term the argument of the application is obtained by reducing $N$. The redex is at the toplevel, meaning that $C\_1 = C\_2 = C\_3 = \[\]$.

* If $\tau$ ends in $R$, then $M \rightarrow\_\beta^\* z z$, $N \rightarrow\_\beta^\* b c$ and $M\[z \leftarrow N\] \rightarrow\_\beta^\* (\lambda x. b x (b c)) c$. If $N$ has a descendant in $L$ then this descendant must also reduce to $b c$ which is the normal form of $N$. In particular, no descendant of $N$ can be a lambda, so $\sigma$ cannot contract a subterm of the form $\check{N} P$ where $\check{N}$ is a descendant of $N$. Since the only subterm of $L$ that reduces to $b c$ is $b c$, the sole possible descendant of $N$ in $L$ is the sole occurrence of $b c$ itself.
* If $\tau$ ends in $L$, then $M \rightarrow\_\beta^\* b z (b c)$, $N \rightarrow\_\beta^\* c$, and $M\[z \leftarrow N\] \rightarrow\_\beta^\* (\lambda x. x x) (b c)$. If $N$ has a descendant in $R$ then this descendant must also reduce to $c$ by confluence.

*At this point, the conclusion should follow easily according to van Oostrom, but I'm missing something: I don't see how tracing the descendants of $N$ gives any information about $M$. Apologies for the incomplete post, I'll think about it overnight.*

# Answer
> 0 votes
Note that $\beta$-reduction can make any term disappear. Assuming that variable $x$ does not appear free in a term $v$, you have $(\lambda x.v)\\;t\_1 \to\_\beta v$ and $(\lambda x.v)\\;t\_2 \to\_\beta v$ for any terms $t\_1$ and $t\_2$. As a consequence, the fact that reverse $\beta$-reduction is confluent is somewhat equivalent to: for all terms $t\_1$ and $t\_2$, there is a term $u$ such that $u \to\_\beta^\ast t\_1$ and $u \to\_\beta^\ast t\_2$. This seems very false to me!

---
Tags: lambda-calculus, term-rewriting
---


# Question
Title: Finding the Kth largest element can be optimized to O(n) only if k is a constant?
There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$.

The thing I don't understand is.... Those algorithms wouldn't work if $k$ is dependent on $N$. Therefore $k$ must be a constant.

But if it's a constant why isn't it easiest to simply loop like bubble sort for $k$ times? So you pushed the $k$ largest elements to the end of the array. No? Complexity would be $O(nk)$ but $k$ is a const so it would be $O(n)$.

Why do we need crazy algorithms like median of medians and using quicksort if this alone works?

# Answer
The $k$th largest element can be found in time $O(n)$ for *all* $k$ using a *deterministic* algorithm. See Wikipedia or many textbooks, such as Cormen et al., Introduction to Algorithms.

Given the $k$th largest element, you can find the $k$ largest elements in $O(n)$ using a simple scan. If all elements are distinct, you just output all elements which are at least as large as the $k$th largest. Without this assumption, you output all elements which are strictly larger than that element, and then enough copies of the $k$th largest one.
> 1 votes

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, quicksort
---


# Question
Title: First problem to be considered np complete?
What is the first problem that was demonstrated to be NP-Complete?

# Answer
> 1 votes
You can find the original paper of Cook online: The complexity of theorem-proving procedures. You can also find Levin's paper in Russian: Universal Sequential Search Problems. A translation can be found in the appendix to a historical survey by Trakhtenbrot: A Survey of Russian Approaches to *Perebor* (Brute-Force Search) Algorithms. You can even find Karp's Reducibility Among Combinatorial Problems.

Cook showed that the set of DNF tautologies (i.e., the complement of SAT) is NP-complete in his sense (oracle reducibility). Karp mentioned that SAT is actually NP-complete with respect to many-one reductions. Levin's paper mentions six different problems, but has no proofs (as was customary).

---
Tags: algorithms, np-complete, np
---


# Question
Title: Finding a local peak in an array in O(log N)?
So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the solution.

Please can someone explain it Mathematically.

# Answer
> 4 votes
To reformulate the question, there is the following problem: given an array of numbers, find an index in the array that is a *local maximum*, meaning the value at that index $\ge$ the values at adjacent indices.

The algorithm suggested works as follows. Perform a binary search on the array. At each iteration choose a middle element of the array; examine its neighbors; if it is a local maximum or the binary search has narrowed down to just one item, output its index; otherwise recurse on a side with a greater neighbor. Clearly this algorithm runs in $O(\log n)$.

Your question is why this algorithm works.

The first observation is that every array has a local maximum. That is because an array of length 1 has a local maximum and if every array of length $n$ has a local maximum then given an array of length $n+1$, either its first element is a local maximum or each local maximum in the sub-array starting at the second element is a local maximum of the full array.

Now suppose there are two consecutive elements of the array $a, b$ and $a \< b$. Every local maximum of the sub-array starting at $b$ is a local maximum of the full array and as shown in the previous paragraph, there must be at least one. Similarly if $a \> b$, every local maximum of the sub-array ending at $a$ is a local maximum of the full array and there must be at least one. The algorithm always recurses to one of those mentioned sub-arrays and therefore when it gets to a single-element sub-array, whose only element is a local maximum of itself, that element is also a local maximum of the sub-array in the previous step, which must be a local maximum of the sub-array two steps prior, etc., all the way back to the full array.

# Answer
> 3 votes
No, it is not possible to find the max (peak) element in an unsorted array better than $\mathcal{O}(n)$.

When you executed your algorithm $\mathcal{A}$ that has $c \log n$ compare operations, that means; $\mathcal{A}$ only compared $c \log n$ elements. The remaining are not compared by $\mathcal{A}$.

We can easily construct an adversary argument for any $\mathcal{O}(\log n)$ algorithm by just placing the peak, within the elements for $\mathcal{A}$ didn't touch.

---
Tags: algorithms, search-problem
---


# Question
Title: Stop and Wait retransmission of packets?
In a communication link out of p packets one packet will be lost. If stop and wait protocol is used then expected number of retransmissions for a packet?

(A) P/(1-P)

(B) P

(C) 1/(1-P)

(D) 1/P

I am getting option a) as answer. Anyway to solve this?

# Answer
Suppose that the probability that a packet is lost is $1/p$. Then the number of packets you need to send until the packet is sent successfully is a geometric random variable with success probability $1-1/p$. Hence the expected number of packets you need to send is $1/(1-1/p) = p/(p-1)$. The expected number of *re*transmissions is $p/(p-1) - 1 = 1/(p-1)$. So none of the answers is correct.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: how is an arbitrary dimension "reshaper" turned into a function given a linear index?
i have an arbitrary "reshaping" function which, given a linear sequential array can "reshape" it to 2D or 3D. the order in which the X-dimension, Y-dimension and Z-dimension may all be changed, as well as the *size* of the X, Y and Z dimensions, may all be changed, *at runtime*. consequently it is not possible to use static compilers or static allocation.

here is a function that, for the *full* sequential range, prints out a corresponding (remapped) set of indices:

```
(xdim, ydim, zdim) = (3, 2, 5)
lims = [xdim, ydim, zdim]
idxs = [0,0,0]
order = [1,0,2]

for idx in range(xdim * ydim * zdim):
    new_idx = idxs[0] + idxs[1] * xdim + idxs[2] * xdim * ydim
    print new_idx,
    for i in range(3):
        idxs[order[i]] = idxs[order[i]] + 1
        if (idxs[order[i]] != lims[order[i]]):
            break
        print
    idxs[order[i]] = 0

```

what i *actually* need is a function which, when it is passed an arbitrary index, returns *one* (correct) remapped index.

i suppose what i could hypothetically do is have a function that sets up the full array (at startup time), and indexes it. i would however like to see an algorithmic version of the above.

# Answer
If the index of $(i,j,k)$ is $p = i + xj + xyk$ then you can compute $i,j,k$ given $p$ as follows:

```
i = p mod x
j = (p / x) mod y
k = (p / x) / y

```

Using this you can solve your problem.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Regular expression for words where the same symbol can repeat at most two times consecutively?
Having the alphabet $\\{a, b\\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?

For example, I can't have ${baaab}$ nor ${abbba}$, but I can have ${abbaabba}$.

# Answer
Every string over $\\{a,b\\}$ can be decomposed into *runs* of the same letter. For example, $$ abbaabba = a^1 b^2 a^2 b^2 a. $$ Since the alphabet is binary, the runs just alternate between the two letter. In your case, every run has length 1 or 2. We can distinguish between four types of words in your language, depending on which run is first and which run is last; additionally there are some corner cases. The set of words in your language in which the first run is $a$s and the last run is $b$s corresponds to the regular expression $((a+aa)(b+bb))^+$.

I'll let you figure out the rest.
> 1 votes

# Answer
How about this C++ code?

```
string loc;
char sent[] = {a, b};
for (int i=0; i<N; i++)
{
   int pos = rand()%2;
   if (i>=2)
   {
      if (loc[i-2]==loc[i-1])
      {
         if (sent[i-2] == loc[i-1)
           loc.push_back(sent[!loc[i-1]]);
         else
           loc.push_back(sent[loc[i-1]]);
      }
      else
        loc.push_back(sent[pos]);
   }
   else
     loc.push_back(sent[pos]);
}

```
> -2 votes

---
Tags: formal-languages, regular-expressions
---


# Question
Title: Is SAT known to be non-context-free or even non-regular?
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.

Has something similar been done for SAT?

# Answer
One possible encoding of SAT is as a string over the alphabet $\\{x,\land,\lor,\lnot,0,1\\}$ which encodes a satisfiable CNF. This language is not regular since intersecting it with an appropriate regular expression, we obtain the language semantically representing $x\_i \land \lnot x\_i$, which is essentially the language of squares $ww$, classically known to be non-regular. The same argument also shows that UNSAT is not context-free. It is highly likely that similar arguments (perhaps using fancier template formulas) would show that SAT is also not context-free.
> 3 votes

---
Tags: complexity-theory, regular-languages, context-free, np-complete, np-hard
---


# Question
Title: Relation beetween log-space reduction and polynomial time reduction
I read somewhere that given two languages $A$ and $B$, if $A \le\_{\log} B$, then $A \le\_P B$ (with $\le\_{\log}$ the log-space reduction and $\le\_P$ the polynomial time reduction), but I'm not sure about the proof.

Could someone help me with that please.

# Answer
Every terminating Turing machine running in logarithmic space terminates in polynomial time. This is because the number of configurations in a logarithmic space Turing machine is polynomial; a logspace Turing machine running longer than the number of configurations will necessarily repeat a configuration, and so will never terminate.

More generally, $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{O(f(n))})$ for similar reasons. This gives not only $\mathsf{L} \subseteq \mathsf{P}$ but also $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.
> 2 votes

---
Tags: complexity-theory, space-complexity, polynomial-time
---


title: Running time based on smallest subtree

text:
# Question
Title: Running time based on smallest subtree
I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More specifically, at each node, a constant amount of time is required for each node in the smallest of its 2 subtrees.

The running time for a tree with $n$ nodes is then easily bounded by $O(n^2)$, however, I conjecture that the running time is bounded by $O(n \log n)$, since I think $\sum\_{x\in V(T)}\min(|V\_l(x)|, |V\_r(x)|) \leq O(n \log n)$ holds.

How would I go about proving this?

# Answer
> 1 votes
A nice question!

As the OP has pointed out, it is enough to show the following inequality for any tree $T$ of $n\gt0$ nodes, where for any node $x$, $l(x)$ is the number of nodes in the left subtree of $x$ and $r(x)$ is the number of nodes in the right subtree of $x$.

$$\sum\_{x\in V(T)}\min(l(x), r(x)) \leq n \log n$$

Proof by mathematical induction.

* base case when $n=1$. Both side is 0.
* Suppose it is true when the number of nodes in the tree is smaller than $n$. Let us consider a tree $T$ with $n\>1$ node. Let the left subtree $T\_l$ of the root node has $p$ node and the right subtree $T\_r$ of the root node has $n-1-p$ node. There are two cases.
    + $p=0$ or $p=n-1$ is easy.
    + $p\neq0$ and $p\neq n-1$. (This case is only possible when $n\ge3$.) WLOG assume $p\le n-1-p$; otherwise we can switch the left subtree and the right subtree.

$$\begin{aligned} &\sum\_{x\in V(T)}\min(l(x), r(x)) \\ &= \min(p, n-1-p) + \sum\_{x\in V(T\_l)}\min(l(x), r(x))+\sum\_{x\in V(T\_r)}\min(l(x), r(x))\\ &\leq p + p\log p +(n-1-p)\log(n-1-p)\\ &= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\ &= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\ &\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\ &\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\ &= (1- 2\log2)p + (n-1)\log n\\ &\le n\log n \end{aligned}$$

Proof is done. Note that we have actually proved a tighter upper bound, $\frac1{2}n \log\_2 n$.

---
Tags: runtime-analysis, binary-trees
---


# Question
Title: what does the redundancy of a code means?
I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code *was only* $\log(6n-3)$ bits.

But *what does that means?* I was trying to get that from the proof of that fact but what they proved instead was that

*there exists a such (with the structure they propose) code whose redundancy is at most* $\log(6n-3)$ *bits*

and in the proof itself they just said that the cardinality of the code is greater or equal than $\frac{2^n}{6n-3}$.

How does that proved the hypothesis?

Also, if I have my own code how do I compute the redundancy (or a reasonable bound on it?)

# Answer
A linear error-correcting code encodes $m$ message bits using $w$ encoded bits. The redundancy is $r = w-m$. In other words, it is a collection of $M = 2^m$ codewords out of the possible $W = 2^w$ words of length $w$. We can extract the redundancy using the formula $$ r = \log\_2 \frac{W}{M}. $$ This formula makes sense for arbitrary error-correcting codes.

In your case, codewords are of length $n$, and there are at least $2^n/(6n-3)$ of them. Therefore the redundancy is at most $$ \log\_2 \frac{2^n}{2^n/(6n-3)} = \log\_2 (6n-3). $$
> 2 votes

---
Tags: information-theory, coding-theory, error-correcting-codes
---