title: Proof of correctness of this algorithm

text:
# Question
Title: Proof of correctness of this algorithm
Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A\_i \le A\_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A\_i + A\_j = n$. Simple enough, here's an algorithm that does it:

```
CheckForPair(A, n, i, j):
    if i >= j or outOfBound:
        return false
    v := A[i] + A[j]
    if v = n:
        return true
    if v < n:
        return CheckForPair(A, n, i + 1, j)
    if v > n:
        return CheckForPair(A, n, i, j - 1)

CheckForPair(A, n):
    return ChcekForPair(A, n, 1, |A|)

```

Mathematically,

> $$ \begin{align} CheckForPair(A, n, i, j) &= \begin{cases} false & \text{if $i \ge j$ or $i \< 1$ or $j \> |A|$,} \\ true & \text{if $A\_i + A\_j = n$,} \\ CheckForPair(A, n, i + 1, j) & \text{if $A\_i + A\_j \< n$,} \\ CheckForPair(A, n, i, j - 1) & \text{if $A\_i + A\_j \> n$} \\ \end{cases} \\ \\ CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|) \end{align} $$

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

* if $A\_i$ + $A\_j \< n$, then $i$ must increase because $j$ cannot increase.
* if $A\_i$ + $A\_j \> n$, then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.

# Answer
> 1 votes
It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$ CFP(n,A) = \begin{cases} False& \text{if }A=\[\\;\]\\ True& \text{if } first(A) + last(A) = n\\ CFP(n,tail(A))&\text{if }first(A)+last(A)\<n \\ CFP(n,init(A))&\text{otherwise} \end{cases} $$ where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:

1. |A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A\_i+A\_j=n$.
2. We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A\_i+A\_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:
    * $A\_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
    * $A\_j = last(A)$: Analog to the previous case.
    * $first(A)\<A\_i\leq A\_j\<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.

---
Tags: algorithms, correctness-proof
---


# Question
Title: Could the execution of a Haskell program be considered as a proof using equational reasoning
Could the execution of a Haskell program be considered as a proof in equational reasoning. This follows on from my earlier question on Haskell and inductive proof. Currently I am stuck between morally yes, but technically perhaps no. Below are two Haskell programs together with what I consider to be paper based equational proofs of very simple theorems. I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a), so the proofs use ground terms or values.

```
-- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
theoremZ = z == 4
-- Paper based equational proof of Prog 1
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
theoremSize =  size (Add (Add Empty 1) 2) == 2
-- Paper based equational proof of Prog 2
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)

```

# Answer
"Equational logic" has a fairly specific meaning, while you seem to be vaguely referring to the notion of "equational reasoning" which makes your question not meaningful. If we tried to take your question at face value, we immediately run into issues. Before we can talk about whether computation corresponds to proof in the logic, we'd first need to be able represent Haskell programs as terms in the logic! That can't be done, at least, not in a naive way. To handle binding forms and beta reduction, would require something like nominal/higher-order equational logic or utilizing explicit substitutions. This is just the beginning. Another question is: what do you want to constitute a Haskell program? Haskell is a Church-style language, meaning you need the type information to execute the code, i.e. a Haskell program has no meaning without type information. So does "Haskell program" mean some representation with all type information included, or do you intend to model type inference equationally somehow? Once you figure all that out, you then need some equations for your equational logic, at which point you run into another problem: Haskell has no formal semantics.

Let's step way back. For just plain arithmetic, how do we show that $2+2=1+3$? One answer is that we have an equational logic with equations like $2 = 1+1$, $3=1+(1+1)$, $(x+y)+z=x+(y+z)$, $x+y = y+x$, $0+x = x$. We might prove the equality then by using $2=1+1$ twice to get $(1+1)+(1+1) = 1+3$ then use associativity to get $1+(1+(1+1))$, and then $3 = 1+(1+1)$ to get $1+3 = 1+3$ which is then true by reflexivity. There are many other proofs besides this one that could be formulated. Just given a list of equations gives you no guidance on the proof approach, i.e. which equations to apply when and in which direction. Furthermore, if you fail to find a proof, you don't know if that's just because you weren't clever enough, or if there actually is no proof (i.e. the expressions are not equal). Both of these problems are solved by formulating a notion of "normal form" and a rewrite system that takes any term to its normal form. This is what Knuth-Bendix completion and its successors do1. In this case, each rewrite rule is derived from an equational proof, and the sequence of steps can be interpreted as stitching together these proofs with transitivity.

But this is not what people are thinking when they compute by hand, it's not what your calculator/computer is doing, and it's not even what automated theorem provers/proof assistants are typically doing2. Typically this is turned around: we have an algorithm for addition, and two expressions are considered equal when the algorithm produces the same result for both of them (where "the same" here means syntactically identical). In other words, computation comes first and "equality" is a derived concept.

For arithmetic, one might argue about which perspective is more "fundamental", but for a programming language it's clear computation is the fundamental notion. This computational approach frees us to use any representation of "terms" we want and any algorithmic approach we want as long as it's (ultimately) deterministic. Of course, this presumes that normal forms exist and are computable. For a general programming language, neither statement is true. Computing a normal form is then usually semidecidable, and the "equality" gets weakened to a partial equivalence relation. Most proof assistants avoid this issue by restricting to strongly normalizing languages. Computational Type Theory/NuPRL takes a very different approach. It exposes the operational semantics of its built-in notion of computation and gives the user some control over that computation process, e.g. "perform one beta reduction". We can then define "equality" as $x = y$ iff $x \leadsto^\* x'$ and $y\leadsto^\* y'$ and $x' =\_\alpha y'$ where $\leadsto^\*$ is the reflexive, transitive closure of the one-step reduction relation. This captures the previous notion when $x$ and $y$ have normal forms, but it allows equating expressions that lack normal forms as well, as long as they reduce to a common expression. This casts us back into the world where there's no obvious strategy, and we can't in general be sure whether two expression are unequal or we have simply failed to find a proof. That's unavoidable, since this notion of equality is not decidable.

Unsurprisingly, the steps of your "equational proofs" don't directly have to do with equality, but are, instead, sketches of proofs that e.g. $1+(2+1)\leadsto^\* 4$ with respect to a hypothetical operational semantics for Haskell.

1 For just checking whether two ground terms are equal, a simpler algorithm called congruence closure can be used.

2 It (or congruence closure) is what most automated theorem provers are doing if you do literally present a series of equations and then ask if two expressions are equal, but not if numbers are built-in nor, more for proof assistants, if you define addition algorithmically. More generally, many proof assistants have built-in notion of computation, and many automated theorem provers heavily rely on decision procedures.
> 2 votes

---
Tags: proof-techniques, functional-programming
---


# Question
Title: Are linear languages always unambiguous?
Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?

# Answer
The linear language $\\{ a^ib^jc^k \mid i=j \text{ or } j=k\\}$ is inherently ambiguous.
> 3 votes

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


# Question
Title: If two vertices point to one another in a directed graph, is the graph then considered cyclic?
Suppose you have a directed graph. Vertices *a* and *b* are part of the graph. There is an arrow pointing from *a* to *b* and an arrow pointing from *b* to *a*. Does this make the directed graph cyclic?

# Answer
> 3 votes
Yes the graph is cyclic. It does not matter how many vertices are there. If a cycle can be formed then the graph is cyclic. You can even form a cyclic graph with one node. This cycle would be called a self loop.

---
Tags: graphs
---


# Question
Title: Problem with solving the recurrence $T(n) = 2T(\sqrt n) + \log n$
This question has already been asked before in this site, but the details of none of them is my question and none of them answer my question. The following is an example recurrence given in *introduction to algorithms* book by CLRS .

$$T(n) = 2T(\sqrt n) + \log n$$

It is solved by changing the variables. It renames the $m = \log n$ and it yields

$$T(2^m) = 2T(2^{m/2}) + m$$

and it renames $S(m) = T(2^m)$, so it produces new recurrence

$$ S(m) = 2S(m/2) + m $$

which is easy to solve.

I have two problems with this solution:

1- renaming $S(m) = T(2^m)$ must yield $S(m) = S(m/2) + \log m$, since we can't change the argument of the $T$ and leave the $m$ as it was. We can use $S(m) = S(m/2) + m$ only if the original recurrence was $T(2^m) = 2T(2^{m/2}) + 2^m$

2- The second problem is, even if the above renaming is true, $2T(\dfrac{2^m}{2})$ would be $S(m/2)$ not the $2T(2^{m/2})$

thanks in advance.

# Answer
> 1 votes
Regarding your 1st problem: You don't need to change $m$ to $\log m$. Let's suppose $f(x)=g(y)$.Then you do not need substitute $y$ anywhere. Because $y$ if substituted would again produce $y$. If you substitute $y$, you must substitute it by $g^{-1}f(x)$=$g^{-1}g(y)=y$. You can see you are again getting $y$.

Regarding your second problem: $S(m)=T(2^m)$

Let $y=m/2$

$$S(y)=T(2^y)$$

$$S(m/2)=T(2^{m/2})$$

You must substitute $m$ by $m/2$. What you are doing is dividing $2^m$ by $2$ which is completely wrong.

---
Tags: recurrence-relation
---


# Question
Title: For which level of PH is $\operatorname{VALID}$ complete
I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv\_m^p \operatorname{VALID}.$$ This can easily be seen by changing instances of each problem into their logical negation, then a formula is a tautology iff its negation is not satisfiable.

My question is now, for which level of the polynomial time hierarchy PH is $\operatorname{VALID}$ complete. Here a quick definition of PH

$$ \Sigma\_0 = \Pi\_0=\operatorname{P},\quad \Sigma\_{n+1} = \operatorname{NP}(\Sigma\_n),\quad \Pi\_{n+1} = \operatorname{co}-\Sigma\_{n+1},\quad \Delta\_{n+1} = \operatorname{P}(\Sigma\_{n}).$$

I made the following observations: $\overline{\operatorname{SAT}}\in \operatorname{co}-\operatorname{NP}$, so that by the reduction given earlier we have that $\operatorname{VALID} \in \operatorname{P}(\operatorname{co}-\operatorname{NP})= \operatorname{P}(\operatorname{NP}) = \Delta\_2$. So my quess would be that the first level of PH for which $\operatorname{VALID}$ is complete is $\Delta\_2$.

If $\overline{\operatorname{SAT}}$ is hard for $\operatorname{co}-\operatorname{NP}$ then I think the result follows, but I cannot seem to corroborate this with solid arguments.

Also, the reduction given seems so simple ($\phi \mapsto \lnot \phi$) that it seems that the class $\operatorname{P}(\operatorname{co}-\operatorname{NP})$ might be a bit overkill.

I would be grateful for any shared insights into this problem.

# Answer
> 1 votes
Just like SAT is NP-complete, $\overline{SAT}$ is coNP-complete. More generally, if $L$ is $\Sigma\_k$-complete then $\overline{L}$ is $\Pi\_k$-complete (and vice versa). You can prove this using the definitions.

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


title: Universal Lossless Compression?

text:
# Question
Title: Universal Lossless Compression?
It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p \< n ( 2^n-1)$. Via the pigeon hole principle, if we only tried to compress files of size $n$ with a single algorithm, there would be at least one file it was impossible to compress.

If we wanted to be able to compress files with differing lengths $n\_k$, the number of files of length $n\_k$ we can compress for each $n\_k$ becomes even smaller.

Today when reading a story about how a file that was several gigabytes when compressed uncompressed to one gigabyte, I had an idea for a universal compression algorithm.

---

Let $a\_i$ be a compression algorithm.
Let $g\_j$ be a file.
$|g\_j|$ denotes the length of $g\_j$.
Let $f(a\_i, g\_j)$ be a function that returns $(|g\_j| - |a\_i(g\_j)|)$.

Let $S\_N = \\{g\_j : |g\_j| \le N\\}$.

Let $A = \\{a\_i : \\, \forall \\, g\_j \in S\_N \\, \exists a\_i in A : f(a\_i, g\_j) \gt \lceil(\log\_2{\\#A})\rceil\\}$.
$\\#A$ denotes the number of elements in $A$.

Let $m$ be the length of the label of the compression algorithm chosen. The first $m$ bytes of every compressed file denote the compression algorithm chosen.
$m = \lceil(\log\_2{\\#A})\rceil$.

Then you can compress all $g\_j \in S\_N$, by iterating through A until you find $a\_i : f(a\_i,g\_j) - m \gt 0$.

Even better.

For each $g\_j$, let $a\_j$ be the corresponding compression algorithm.

Let $h(a\_i, g\_j) = f(a\_i,g\_j) - m$.

$${ \\, \forall \\, a\_i \in A, g\_j \in S\_N, a\_j = \displaystyle{ \underset{a\_i \in A, g\_j \in S} { \operatorname{argmax} } } \\, (h(a\_i, g\_j))}$$

---

Is there a reason why the above is not done?

While the above is an algorithm, and one could argue that the pigeon hole principle thus applies, this does not imply what it may at first seem to imply. The above algorithm call it $a^v$ is a little different.

Let $a\_i: S\_N \to Y\_N^i$ denote that algorithm $a\_i$ maps a family of files $(S\_N = \\{g\_j : |g\_j| \le N\\})$ is mapped to another family of files $Y\_N = \\{y\_j : y\_j = a\_i(g\_j)\\}$.

$\forall a\_i \in A, a\_i: S\_N \to Y\_N^i$.
However, $a^v : S\_{N+m} \to Y\_{N+m}^v$.
So $a^v$ compresses a different family of files from $a\_i \ in A$.

The pigeon hole principle merely states that $a^v$ cannot compress all files of length $N+m$; this is irrelevant, since $a^v$ only intends to compress a small subset of files of length $N+m$ (those whose first $m$ bits are the labels of some $a\_i \in A$.

# Answer
> 2 votes
> Then you can compress all $g\_j ∈ S\_N$, by iterating through $A$ until you find $a\_i|f(a\_i,g\_j)−m\>0$.

I'm not sure what the notation means (the pipe here, and also $\\#A$ elsewhere), but still: this is not a meaningful algorithm since the set

> $\qquad A = \\{a\_i : \\, \forall \\, g\_j \in S\_N \\, f(a\_i, g\_j) \gt \lceil(\log\_2{\\#A})\rceil\\}$

is empty.

I think you got lost in notation. $S\_N$ = $\Sigma^{\leq n}$ and $A$ is the set of all algorithms that compress *all* strings in $S\_N$ by at least some non-zero number of bits. As you cited, there are no such algorithms.

In the updated question, you write:

> $\qquad A = \\{a\_i : \\, \forall \\, g\_j \in S\_N \\, \exists a\_i \in A : f(a\_i, g\_j) \gt \lceil(\log\_2{\\#A})\rceil\\}$

This definition is circular, hence $A$ is not well-defined. Did you mean

$\qquad A = \\{ a \mid \exists g \in S\_N. f(a, g) \> x \\}$

with $x \> 0$ something that does *not* depend on $A$?

Now $A$ is infinite (and undecidable as per Rice's theorem) and, arguably, completely useless: any string `s` can be compressed well by the trivial algorithm

```
compress_s(x) {
    if x == s
        return "0"
    else
        return "0" + x
    end
}

```

Note that this version of $A$ contains all these bogus algorithms. So, you have thrown all information while compressing, instead encoding the string in the algorithm's source code (mathematically and literally).

And, as others note, the resulting algorithm would *still* be subject to the pidgeon-hole principle.

> Is there a reason why the above is not done?

Even if it were possible, it'd be horribly inefficient. In essence, the idea of your algorithm is:

> Try all (compression) algorithms (I know); pick the smallest result and encode the result together with its code.

That's clearly neither a clever nor a useful algorithmic idea.

---
Tags: algorithms, data-compression, check-my-answer
---


title: Merge 2 Binary Heaps

text:
# Question
Title: Merge 2 Binary Heaps
I want to merge $2$ binary heaps. Which is the fastest algorithm to do so. Also would like to know its time complexity.

I know how to do it linear time $O(n)$, I want to know if there is something faster (probably there is).

# Answer
It is possible to merge two standard binary heaps in $\mathcal O(\log n)$ time, picking $\pm\infty$ setting the both heaps as children and then extracting top element (this operation takes $\mathcal O(\log n)$ time).

You might be also interested in paper about faster merge in $\log k * \log n$, but it is non-standard, pointer based implementation. The standard approach is to use array. The other operations take a bit longer though.

Another idea is to use Binomial heap or Leftist heap, with merge operation in $\mathcal O(\log n)$ time or Fibonacci, Pairing, Brodal or Rank-pairing heap to support merge in $\Theta(1)$ time.

The list is described at Wikipedia, Binomial heap. Although marvelous at first glance they hide larger constant and increase time of standard operations on heaps, for example find min may be $\mathcal O(\log n)$ instead of $\Theta(1)$.

If you want the asymptoticaly fastest algorithm then any of mentioned are good. For practical purposes I would recommend the Pairing heap, which is a form of multiway tree, easy to implement (comparing with Brodal for example).
> 1 votes

---
Tags: data-structures, heaps
---


# Question
Title: Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text
I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".

```
Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G_f
    Let P be a simple s-t path in G_f
    f' = augment(f,P)
    Update f to f'
    Update the residual graph G_f to be G_f'
Endwhile
Return f

```

This seems to make sense to me. However, prior to displaying this pseudocode, the textbook gives pseudocode for the augment subroutine:

```
augment(f,P)
Let b = bottleneck(P,f)
For each edge (u,v) in P
    If e = (u,v) is a forward edge then
        increase f(e) in G by b
    Else ((u,v) is a backward edge, and let e = (v,u))
        decrease f(e) in G by b
    Endif
Endfor
Return(f)

```

Unfortunately, the textbook does not give any implemenation details on the bottleneck() subroutine.

But what I cannot understand is why we would need to pass the flow function $f$, to the bottleneck subroutine?

It seems that the bottleneck routine is looking at a simple s-t path in the residual graph $G\_f$. Hence bottleneck is only concerned with the residual capacity along each edge. When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity. Hence, a call such as bottleneck($P$) would seem to suffice which simply looked for the minimum capacity along the edges in $P$.

Can someone shed any light on why we pass $f$ to this bottleneck subroutine?

# Answer
This is *pseudocode*, not the end-all be-all of the algorithm implementation. It is a very high level overview and by nature is left up to interpretation for the implementation. That being said...

> "When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity."

This is not necessarily the case. You can analyze the residual graph in place, simply based on $f$ and $G$. By this, I mean it is not necessary to explicitly create a new graph $G\_f$ because $G\_f$ is merely a function of $G$ and $f$.

If this is the case, then the flow function $f$ is passed in to compute the residual capacity of each edge in the path. Similarly to how $G\_f$ can be computed in place, if we have a path $P\_f$ (from $s$ to $t$) in $G\_f$, it doesn't necessarily have to an explicit path in $G\_f$. It could be a path in $G$ for which we must compute $P\_f$. This is when we might require $f$ to compute the bottleneck.

Again, this is just pseudocode and if you implement in a slightly different way than is described, that's okay as long as the procedure is correct.
> 3 votes

---
Tags: algorithms, graphs, network-flow, ford-fulkerson
---


# Question
Title: Turing reduction problem, intersection is equal to an empty set
$L\_c=\\{\langle M\_1 \rangle, \langle M\_2 \rangle):L(M\_1)\cap L(M\_2)=\emptyset\\}$ prove to be undecidable. My approach: We will prove this by reduction $L\_{\emptyset} \leq\_T L\_c$ We begin by assuming that $L\_c$ is decidable and that we have access to a black box $Q$ which decides it. We want to construct another Turing machine $H$ which decides $L\_{\emptyset}$.

```
H = “On input (< M >, w).
    Construct the following machine M’
M’ = “On input w.
    Ignore input w and reject.
    Run decider Q on (< M >,< M’>)
    If Q accepts, reject.
    If Q reject, accept.

```

I'm mainly concerned about my choice of $L\_{\emptyset}$ (maybe $L\_{halt}$ is better suited here?) and the part where I run the decider $Q$ on ($\langle M \rangle, \langle M'\rangle)$. Any help would be much appreciated, Thank you!

# Answer
> 1 votes
Assume $L\_c$ is decidable. We will reduce $A\_{TM} =\\{x\mid M\_x \text{ halts on } x\\}$ (the Halting problem language) to $L\_c$. On input $x $ create a TM $M'$ which halts on only $x$. Then $L(M') = \\{x\\}$ and $M\_x$ halts on $x$ iff $L(M\_x) \cap L(M') = \\{x\\} \neq \emptyset$ iff $\left(\langle M\_x \rangle, \langle M' \rangle \right) \notin L\_c$. Thus, to check if $M\_x$ halts on $x$ we check if $\left(\langle M\_x \rangle, \langle M' \rangle \right) \notin L\_c$.

---
Tags: computability, reductions
---


title: Find size of 4th jug using the other 3

text:
# Question
Title: Find size of 4th jug using the other 3
> We have 3 jugs with capacities A, B and C. How can we create an algorithm that will find out how to measure D liters?

This is my task for one online course I'm taking. I have no idea where to start. I don't even understand how are these four related to each other. I will be thankful for any help or clarification of the problem.

# Answer
Construct (mentally) a graph whose vertex set consists of triplets $(a,b,c)$ denoting the amount of water in each of the three bowls. Edges correspond to allowable operations (which you haven't specified). There is also a distinguished vertex, which is the starting position (which you haven't specified), and a bunch of target vertices (in which $D \in \\{a,b,c\\}$). You want to know whether a target vertex is reachable from the starting position. The obvious thing to try is some graph search algorithm such as BFS, DFS, or A\*. These algorithms don't actually require you to construct the entire graph ahead of time.

There might be more efficient algorithms, but this is the baseline against which more sophisticated algorithms should be compared.
> 1 votes

# Answer
This is a generalisation of an old puzzle. We assume that you can pour water into a jug until it is full, that you can pour water from one jug into another until either the first is empty or the second is full, and that you can empty a jug. You should also assume that you have a fourth container of unknown capacity $\> D$, and that you can only pour fluid into the container but not remove it.

That way you can measure various amounts of water. For example, fill the first jug with $A$ liters. If $B \< A$, pour water from the first to the second jug until it is full, so the first jug contains $A-B$ and the second contains $B$.

So you write down all the ways that you can produce various amounts of fluid. And then you write an algorithm that tries out possibilities and finds one that fills the last container with $D$.

Your headline describes a slightly different problem.
> 1 votes

# Answer
A *configuration* describes the amount of water in each jug. The initial configuration is all jugs empty.

The moves from a configuration are as follows:

* Fill a jug.
* Empty a jug.
* Pour as much as possible from one jug into another.

Use breadth-first search to explore the possible configurations. Stop when you find a configuration with $D$ in a jug.

Assuming that the capacities of the jugs are rational relative to one another, there are a finite number of configurations; so any kind of search will terminate. But BFS will find the quickest route to a configuration.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Create a DFA and a NFA where the word includes (two) consecutive zeroes
I have chosen an example task to see if I understood DFA and NFA correctly.

So let's say we have that task:

> Given alphabet $\Sigma = \\{0,1\\}$ and the language $L = \\{w \mid w \text{ includes two consecutive zeroes}\\}$. Create a DFA and a NFA for the language with as less as possible states.

The following description is just a rough one (there are much more attitudes a DFA / NFA has). Please tell me if it's correct anyway because these are the ones I'm not sure about.

For this example, each state of the DFA needs at least two outgoing arrows. So each state needs at least one outgoing arrow $0$ and one outgoing arrow $1$ because we have $\Sigma = \\{0,1\\}$. We do not really need to care about incoming arrows, there can be any number of incoming arrows.

For the NFA, however, we do not need to care how many outgoing / incoming arrows we use for each state.

So here I made a DFA and a NFA where the words include two consecutive zeroes. Did I do it correctly?

# Answer
> 1 votes
The difference of DFA and NFA is in the transition map (or "outgoing arrows" as you describe) and has nothing to do with "incoming arrows". Namely, if $\Sigma$ is the input alphabet then the transition function of the DFA must be uniquely defined for each state and input symbol pair

$$\delta(q,a) = p, \text { for } q,p \in Q, a\in \Sigma$$

In case of the NFA the transition function maps each pair $(q,a)$ to a subset of states $Q$ $$\delta(q,a) = Q' = \\{p\_1, p\_2, \dots, p\_n\\}, \text { for } Q' \subseteq Q, a\in \Sigma$$

In simply words, for DFA for each input symbol a state must have exactly one outgoing arrow, but in the case NFA for each input symbol a state may have more than one outgoing arrows or no outgoing arrow.

In your example $\Sigma=\\{0,1\\}$ and thus the DFA must have exactly two outgoing arrows for each state, but the NFA may have no outgoing arrow or up to $|Q|$ outgoing arrows.

---
Tags: finite-automata
---


# Question
Title: maximizing inner product of vectors in an ellipsoid and a given vector
I have been wrestling with this for quite a long time but couldn't convince myself that the following is true:

What I do understand: $\theta\_a$ denotes the set of points that are within the ellipsoid. Also, $A\_{t, a}$ is a matrix that "describes" the shape of the ellipsoid. $\hat{\theta}\_{t,a}$ is the red point that is the center of the ellipsoid, and $c\_t$ is the "radius" of the ellipsoid.

I cannot show to myself that $\displaystyle\max\_{\theta\_{a}} x\_{t,a}^{T} \theta\_{a}$ can be derived into the LHS form: $x\_{t,a}^{T} \hat{\theta}\_{t,a} + c\_t \sqrt{x\_{t,a}^{T} A\_{t,a}^{-1} x\_{t,a}}$

Can anyone show me how this is true?

Thanks!

For more context, you can view it here: http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf

# Answer
> 1 votes
There must be something wrong if you look at the dimensions. Actually the constraint should be $$(\theta\_a-\hat{\theta}\_{t,a})^TA\_{t,a}(\theta\_a-\hat{\theta}\_{t,a})\leq c\_t^2.$$

The inner product takes its maximum on the boundary of the ellipsoid so we can make the constraint a equation. The gradient of Lagrange function has to be zero at the maximum: $$\left\\{\begin{array}{rcl} x+2\lambda A(\theta-\hat{\theta}) &=&\vec{0} \\ (\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&=&0 \end{array}\right.$$

So $$x^T(\theta-\hat{\theta})=2\lambda(\theta-\hat{\theta})^TA(\theta-\hat{\theta})=2\lambda c^2,$$ $$x^TA^{-1}x=4\lambda^2(\theta-\hat{\theta})^TAA^{-1}A(\theta-\hat{\theta})=4\lambda^2c^2,$$ which implies $x^T\theta=x^T\hat{\theta}\pm c\sqrt{x^TA^{-1}x}$. Since it's the maximum we take the positive sign here, so we have the LHS you wanted.

---
Tags: machine-learning, linear-algebra, statistics
---


# Question
Title: Why do floating point values have infinity?
Why do floating point values have infinity instead of just a higher exponent?

# Answer
Because sometimes there just isn't an exponent high enough.

First of all, there is no way to effectively represent all real numbers in a reasonable computational model: it is sufficient to observe that the set of configurations of e.g. a Turing Machine is countably infinite, and the set of real numbers is uncountably infinite. Floating point numbers, are ultimately an approximation of what the "actual" computation would be; models for exact real computation exist but as we said before they necessarily "miss" some numbers.

INF and NaN are part of the IEEE standard for rather practical reasons, namely to give meaning to computations that should fail, for a reason or another, and handle such cases in a safe way. We could, as you are basically suggesting, take a floating point model that is finite but unbounded, dynamically adding more space as we need it. As others have already commented, this kind of generalization is actually missing the point: the strength of floating point computations is that they can be performed very efficiently on hardware, and a dynamic solution would be infeasibly more complex.

But even assuming such a model, we aren't really addressing the core of the issue. Let's say that at a certain point we ask the machine to perform the computation $\log(0)$. Mathematically, it doesn't make any sense, because $\log$ isn't defined on $0$. If we didn't have a special value like -INF to return, we would have to abort the computation (or have the program diverge, or terminate in some kind of error state). You might think that such a thing is reasonable: after all, if we had the machine compute $\log(0)$ the program must be wrong in a way or another.

But it gets worse. In any floating point model, there is a smallest positive number that we can distinguish from zero, let that number be $\varepsilon$. Now, we ask the machine to compute $\delta = e^{-10}\varepsilon$ and then $\log(\delta)$. Observe that all those operations are mathematically legit, for instance we can easily see that $\log(\delta) = \log(\varepsilon)-10$. However $\delta \< \varepsilon$, which means that our model literally cannot tell $\delta$ and $0$ apart, by definition of $\varepsilon$. It is much less reasonable to make the entire program fail, now.

Special values like NaN and INF manage to at least salvage the "logical" aspect of the computation, correctly handling equality/inequality checking and the sign, if applicable (i.e. +INF is greater than everything else, NAN is not equal to NAN and so on).
> 6 votes

---
Tags: floating-point
---


# Question
Title: What operation is the algorithm performing?
```
unsigned int input = 0xC116D9B5709FED85 unsigned int output = 0
while (input > 0 )
{
if (( input mod 2) == 1)
{
output += 1
}
input = floor(input / 2)
 }
 return output

```

I understand how the algorithm is working and using mod to break the input and then counting the number of times input is modded by 2 where it resulted 1. Basically checking if the number is odd. My question in the first place is howcome we can even store a huge hex like the one in question in an unsigned int. Doesn't it exceed the size limit of unsigned int. Secondly, if someone can help me understand the question would help alot.

# Answer
The algorithms counts the number of $1$s in the binary expansion of the input. The code as written seems a little weird because it’s not a function that can be applied to an input, it’s being specifically applied to the defined number. I certainly couldn’t tell you why it’s being applied to that number without a lot more context.
> 0 votes

---
Tags: algorithms, c++
---


# Question
Title: Write Serialization for Cache Coherence in the presence of Store Buffers
One of the requirements for a coherent memory system is write serialization - "two writes to address X by any two processors are observed in the same order by all processors". I am not sure how this condition would be met when the CPU cores have a store buffer into which stores are retired before updating the memory hierarchy.

Suppose Cores A and B both retire a store to address X (which is cached by both A and B), and these stores are now in the store buffers and are yet to update the cache. Now loads from address X on both cores A and B could retire after obtaining the load value from the store buffers ie loads from X on core A see value written by the store to X on core A, similarly, loads from X on core B see value written by the store to X on core B. Say now, the store to X from core A sends a read-upgrade message to core B. What happens next on core B? After coherence transactions have completed for A, the store to X on B updates the local cache. After the stores to X from A and B have completed the final value of X is the store by B.

Above, the order for values seen by A for X are write by A followed by the write to B. But this doesn't seem to be the order seen by B. So the question is how is write serialization enforced when store buffers are being used?

(This is based on my understand of the various material I have read and would appreciate it if anyone can point to sources that discuss these issues in detail)

# Answer
> 7 votes
From a *coherence* perspective, I think your example is coherent. All processors believe that the write and read from A happened first, then the write and read from B happened later.

From a *consistency* standpoint you need to be more careful. (Consistency is the global ordering of memory operations to *different* addresses.) The way consistency is handled in practice is that the store buffer sits before retirement, not after. The store buffer acts as a little coherent cache for the speculative memory state. A store instruction is not permitted to retire until its processor has acquired write ownership of the appropriate cache line.

The store buffer needs to be aware of all the coherence traffic reaching the cache. If a speculative load gets its value from the store buffer, but the corresponding memory location is invalidated before the load retires, the load (and everything following it in the reorder-buffer) needs to be squashed and reexecuted.

# Answer
> 5 votes
Situations like the one you describe are the reason why processor manuals for architectures with store buffers such as intel tend to state that two stores by cores *i* and *j* are seen in the same order by all *other* cores.

Common techniques for enforcing sequential consistency for certain memory locations include *fence instructions* and *bus locking*. How these techniques work exactly depends somewhat on the architecture. How they work in principle is described in modern textbooks such as Michael L Scott's *Shared-Memory Synchronization*. Details for architectures are contained in the manufacturers' handbooks. For instance, Intel publishes 4,670p software developer manuals that describe what they think they are doing. (This does of course include much more but I'm not aware of any other comprehensive source.) Scientists who try to prove anything about the behaviour of their programs when running on Intel's x86 or ARM nowadays are rather fond of the formalisations Peter Sewell et. al. in Cambridge (UK) produced. These are still abstractions of what's really going on but they do model store buffers and their effect. These formalisations have been experimentally verified. For a start I'd recommend their Communication of the ACM 2010 paper. More can be found at his web page.

# Answer
> 2 votes
The short answer is this: Store buffers make the memory system fast and inconsistent.

Consider a file system that always does the right thing; a write to a file is immediately visible to all others, and that it handles concurrent writes from multiple clients correctly. Everyone can see the writes serialized. It is a strongly consistent file system.

Now imagine that the programmer creates a convenience library that buffers all writes, and periodically delivers them to the file system. This works just fine if the file is not shared. There is no inconsistency if there is no other viewer. But it is clearly a problem if the file is shared, and it is not the file system's fault. Adding buffering messed it up.

If you treat the convenience library as the interface between the file system and your program (in effect, the API *is* the file system for all you care), then all you see is an inconsistent file system. On the other hand, if you know about the buffering, and if the API provides a sync() call where it waits until the buffers are drained, then a write(X); sync() combination on one client and a write(Y); sync() combination on another client is equivalent to having made calls to the underlying API. We are back to regaining consistency, at the expense of waiting.

In your question, the cache coherent memory is the file system, the store buffer is the user-side buffer, and the sync() call is an mfence or equivalent "barrier" instruction.

The cache coherence protocol (MESI) is strongly consistent (linearizable), but requires coordination, which can suck out performance. We know that most memory (95% or more) is never shared with another process, so why make the CPU wait unnecessarily for all accesses? Hence store buffering and no fences required.

However, for those cases where it is absolutely imperative that we need strong consistency (updates to shared memory addresses), then the program must issue a fence instruction. In higher-level languages like C++ and Java, there are several constructs and qualifiers (synchronised, volatile, final) that introduce these fences at the right moments. But if you mistakenly omit to use one of these facilities, prepare to spend a long time figuring out what happened. This is what makes shared memory concurrent programming so error-prone. And this is why Java programmers should know about store buffers.

---
Tags: computer-architecture, concurrency, cpu-cache
---


# Question
Title: proving {$a^ib^jc^k : j = i \lor j = k$} is not regular
i had troubles proving this is not regular using the pumping lemma {$a^ib^jc^k : j = i \lor j = k$}. Not sure how to approach this anymore, and help would be appreciated

# Answer
If you intersect your language with $a^+ b^+$ then you get $\\{ a^n b^n : n \ge 1 \\}$, whose irregularity you probably know how to prove.
> 0 votes

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


# Question
Title: How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem
I try to solve the following exercise:

**We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT problem, if it accommodates more).**

I have solved it in the following way:

Let (w) be the string to which I compute K (w).

(1). I have a TM 'G', which generates TM descriptions in order of length 'Mi'.

(2). The generated descriptions 'Mi' and (w) are inputs of a TM that has a Oracle for the Membership Problem TMO 'Memb'.

* If TMO 'Memb' rejects then TM 'G' generates a new description Mi + 1, returns to step (1). * If you accept this description Mi and (w), they pass as input to the TM 'R', go to step (3).

(3). TM 'R' runs the description Mi with input (w) and prints the number of steps (t).

(4). Then K(w) would be |\< Mi \>| + t

It would be necessary to run TM 'R' or I can replace the problem of the Membership with the one of the HALT Problem and this gives me that number of steps that I calculate with TM 'R'?

regards

# Answer
> 1 votes
Here is the idea. Given a string $x$ whose Kolmogorov complexity you want to calculate, go over all programs in non-decreasing order of length. For each program $p$, check using the oracle whether it halts, and if so, check whether it outputs $x$. If it does, the Kolmogorov complexity is the length of $p$. Otherwise, go to the next program. Eventually you will find a program computing $x$. The program you will find is a shortest one since we go over all programs in non-decreasing order of length.

---
Tags: turing-machines, halting-problem, oracle-machines, kolmogorov-complexity
---


# Question
Title: Proving that no two state DFA accept the language L = {$0^i : \forall i \ge 0$} $\lor$ {$^i : \forall i \ge 0$}
how do i prove that no DFA with two states can accept the language

$$ L = \\{0^i : i \ge 0\\} \cup \\{ 1^i : i \ge 0\\}. $$

I had a lot of troubles coming up with anything that made sense.

# Answer
> 2 votes
Use Myhill–Nerode theory. Here are four words which are pairwise incomparable: $$ \epsilon,0,1,01. $$

The following table gives words separating them: $$ \begin{array}{c|c|c|c|c} & \epsilon & 0 & 1 & 01 \\\hline \epsilon & & 1 & 0 & \epsilon\\\hline 0 & 1 & & 0 & \epsilon\\\hline 1 & 0 & 0 & & \epsilon\\\hline 01 & \epsilon & \epsilon & \epsilon & \end{array} $$

According to Myhill–Nerode theory, every DFA for $L$ must contain at least four states. It is not too hard to construct a DFA containing four states, so four is the minimal number of states.

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


title: Create DFA with String of {a,b}

text:
# Question
Title: Create DFA with String of {a,b}
I Want to Create Regular Expression from string of {a,b} that it contains neither the substring ab NOR ba?How I can do it?

# Answer
> 0 votes
If a string over $\\{a,b\\}$ contains neither $ab$ nor $ba$ as a substring, then all of its letters must be the same (why?). You can use this to create a regular expression for the language of all such strings.

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


# Question
Title: Fastest way to check if prefix of small string is substring of big string
Let's say we have given 2 strings $A, B$, and let's suppose that the size of $A$ is pretty small (100 characters) and the size of $B$ is pretty big (1 million).

We define prefix of string $S$ as string $Y$ that contains the first $x$ letters (size of prefix always is less than or equal to size of whole string).

And the problem is to check for all prefixes of $A$, they are not too many if they are substrings of string $B$.

It is pretty slow if for each prefix we are traversing the whole string, is it possible to do something faster, maybe using string hasing?

# Answer
Why would you need to traverse the big string for each prefix? Let's say A = "Some short string". So you traverse string B, looking for the letter "S". If not found, then no prefix of A is contained in B. If found, you found the prefix "S", and start at that point searching for "So". And so on.
> 1 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: Is $x^2+x+1 (mod 2)$ a one-way function?
Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}\_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}\[(-1)^{x}|x \rangle + |1-x \rangle\]$ (Fourier transform). So, the 1-1 correspondence $x^2+x+1 = NOT(x^2+x)$ holds over $F\_{2^3}$, where the input is the zero polynomial $x^2+x$ and the output is the positive polynomial $x^2+x+1$ (arXiv:1609.01541, eprint.iacr.org/2017/681). Notice that the bijection $x^2+x+1 (mod 2)$ = $x^2 \oplus x \oplus 1$ = $x \land x \oplus x \oplus 1$ = $ x \oplus x \oplus 1$ = $x \oplus NOT(x)$, which corresponds to a coin toss.

It is important to note that the construction works for bit strings of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$.

Considering that pseudorandom generators exist if and only if one-way functions exist (pseudorandom generator theorem) is $x^2+x+1 (mod 2)$ a one-way function ?

# Answer
> 2 votes
A one-way function is a function from $\\{0,1\\}^\*$ to $\\{0,1\\}^\*$ which satisfies certain properties. Your function only accepts a single bit as input, so in particular isn't a one-way function.

---

We don't know whether one-way functions exist, though many people conjecture that they do. Proving that one-way functions exist is harder than proving $\mathsf{P} \neq \mathsf{NP}$, that is, if one-way functions exist then $\mathsf{P} \neq \mathsf{NP}$. Therefore proving that a given function is one-way is expected to be very difficult, though some candidates do exist.

---
Tags: pseudo-random-generators, one-way-functions
---


title: Infix to postfix conversion

text:
# Question
Title: Infix to postfix conversion
I am somewhat stuck in converting an expression with negative numbers from infix to postfix.

Suppose we have a expression like

a = -b - (-c - d) .

At some places I read that you can parathesize the negative numbers to solve the problem. But if I parathesize them as

a = (-b) - ((-c) - d), then at the beginning of the postfix expression I would get "ab-" which means a-b and is incorrect.

Can someone help me?

# Answer
Canonically, we convert from infix to postfix form only expressions. However, you can enhance this by introducing the assignment operator `=` in addition to the standard four binary operators `+`, `-`, `*`, and `/`. Just define the conversion as: `a = b` becomes `ab=`. So for example, `a = x + 5` becomes `ax5+=`.

As for the negative numbers, you can parenthesize them (as you suggest). For example, `a = -b + 2` becomes `a(-b)2+=` or just separate each operand or operator by a single space, for example the previous postfix expression can be written as `a -b 2 + =`. This is another example: `derv = -dy/dx + 5*(-x)` becomes `derv(-dy)dx/5(-x)*+=` or `derv -dy dx / 5 -x * + =`.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How does left-factoring prevent backtracking?
I read that deterministic grammar helps in preventing backtracking.

Consider a grammar

$$A \rightarrow ab \mid ac \mid ad$$.

Here if input is "ad" then the compiler needs to check each of ab, ac .. and backtrack until it gets to last production.

To eliminate non determinism we modify the grammar as

$$A \rightarrow aB$$ $$B\rightarrow b\mid c\mid d$$

I don't understand how will this modified grammar prevent backtracking . If we again give the same input "ad" then in B production , it will again back track for b and c until it reaches d.

So how does left factoring actually solve this problem ?

# Answer
> 1 votes
Suppose the input is `ab`. In compiler terms you have two tokens `a` and `b` which are read in linear sequence. So, when you read `a` it is not clear which production rule to apply since you have three possible rules which begin with `a`: $A \rightarrow ab \mid ac \mid ad$. To choose the right production rule you need check all possible rules which is done by backtracking.

However, if you factor this grammar then you have only one production rule which begins with `a`: $A \rightarrow aB$ which is the only single possible rule and thus there is no need in backtracking.

Nondeterminism, when parsing, can be resolved using lookahead technique, where left-factoring is one of the steps in order to transform the initial grammar into $LL(k)$-grammar. For more details please read about $LL(k)$-parsers.

---
Tags: formal-grammars, compilers
---


# Question
Title: How can one tell when will the state of the circuit components change?
The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The CPU clock has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the system clock and multiplies it by a number, which is either fixed or unlocked (black edition models).

\bib{38243}{misc}{
title={What are system clock and CPU clock; and what are their functions?},
author={Benjoyo (https://cs.stackexchange.com/users/27547/benjoyo)},
note={URL: https://cs.stackexchange.com/q/38243 (version: 2015-02-11)},
eprint={https://cs.stackexchange.com/q/38243},
organization={Computer Science Stack Exchange}
}

This answer states that the clock components change state only when the signal is high. Why is it so?

# Answer
It is not necessarily true, this is only one possible way of achieving synchronization. One could arbitrarily decide that it happens when the signal is low, or when the signal goes from low to high (rising edge), or high to low (falling edge), or even both. This wikipedia page contains more information.
> 0 votes

---
Tags: computer-architecture, cpu, clocks
---


# Question
Title: Linear programming with inequality constraints treated lexicographically
I'm trying to solve optimization problems of the form: $\min\\{cx|Ax\preceq b,\\;x\geq 0\\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied lexicographically. I'm guessing these inequalities are treated conditionally by means of binary variables thus transforming the problem into a mixed integer linear program. I'm also aware of the more direct approach, which is solving a sequence of linear programs, starting with $\min\\{cx|A\_{1}x\leq b\_{1},\\;x\geq 0\\}$ and continuing with linear programs of the form $\min\\{cx|A\_{i}x=b\_{i},\\;A\_{k}x\leq b\_{k},\\;1\leq i\<k,\\;x\geq 0\\}$ whenever the inequality constraint at $k-1$ is satisfied in strict equality.

I'm interested in a solution by means of binary variables if there is any, or any other approach. Thanks in advance for your help.

# Answer
> 0 votes
One possible solution aside from solving the sequence of linear programs could be solving the following MILP, in which $\epsilon$ is a very small positive number and $M$ a big one: $$ \min cx\\ \text{s.t.}\quad Ax+s=b\\ \epsilon y\_{1}\leq s\_{1}\leq My\_{1}\\ -M y\_{1}+\epsilon y\_{2}\leq s\_{2}\leq M y\_{2}\\ \vdots\\ -M (y\_{1}+y\_{2}+...+y\_{m-1})+\epsilon y\_{m}\leq s\_{m}\leq M y\_{m}\\ y\_{1},y\_{2},\ldots,y\_{m}\in \\{0,1\\}\\ x\geq 0 $$ As I said in the above comment. This allows to solve the more general problem $\min\\{cx|A^{1}x\\{\preceq \text{or}\succeq\\}b^{1},A^{2}x\\{\preceq \text{or}\succeq\\}b^{2},…,A^{l}\\{\preceq \text{or}\succeq\\}b^{l},x\geq0\\}$; which, I believe, cannot be solved sequentially. Nevertheless, I have not been able to test it exhaustively, so if anyone can spot errors or maybe find a better way, I would be very grateful.

# Answer
> 2 votes
# If you want to have only initial constraints to be strictly equal and rest of them should be strictly less

First, add regular constraints: $$ A\_i x \le b\_i $$ Next, add checks for equality as in https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ : $$ e\_i = A\_i x \stackrel{?}{=} b\_i $$ Finally, we want only some initial of these variable to be true, and for that we can use material implication as in https://blog.adamfurmanek.pl/2015/08/22/ilp-part-1/ : $$ e\_{i+1} \implies e\_i = 1 $$ or we can simply add the following constraints: $$ e\_{i+1} \le e\_i $$

Disclaimer: I am the author of the blog posts but I don't want to advertise here, only include them as a reference.

# If you want some initial of the constraints to be strictly equal, the next one should be strictly less, and rest of them can be not satisfied

Do not add any regular constraints.

Create equality constraints as before: $$ e\_i = A\_i x \stackrel{?}{=} b\_i $$

Calculate prefix conjunction of equality constraints: $$ E\_i = e\_1 \wedge e\_2 \wedge \ldots \wedge e\_{i} $$

Variables $E\_i$ indicates whether first $i$ constraints are strictly equal.

Next, calculate less than constraints: $$ l\_i = A\_i x \stackrel{?}{\<} b\_i $$

Finally, make sure that after $i$ initial strictly equal constraints there is a strictly less constraint or another strictly equal constraint satisfied: $$ E\_i \implies \left( l\_{i+1} \vee E\_{i+1} \right) = 1 $$

---
Tags: linear-programming, integer-programming
---


# Question
Title: Theoretical precision needed to get $n$-bits of the evaluation of some sum
Let $P,Q$ two **integral** polynomials of height bounded by let say $H\>0$ --- that is every coefficient of $p$ or $Q$ is bounded in absolute value by $H$ --- and degree at most $d$.

Let $A$ a set of $d$ reals.

I want to evaluate the sum: $$ S = \sum\_{\alpha \in A} P(\alpha)Q(\alpha), $$ and more precisely I want to get the $n$ first bits of this value.

I can assert that this sum is bounded by a constant $K'\>0$.

What would be the minimal number of bits of precision on the elements $\alpha\in A$ I need to be able to compute the $n$ first bits of $S$?

NB: The representation of the reals of $A$ can be whatever (fixed point, floating point, ... ) I'm able to efficiently compute them at arbitrary precision.

# Answer
I may be misunderstanding the question, but I don't think we have enough information to tell.

Consider, for example:

$$A = \left\\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\\}$$

and:

$$P(x) = \left( x - \frac{1}{4} - \varepsilon \right) \left( x - \frac{1}{2} + \varepsilon \right) \left( x - \frac{3}{4} - \varepsilon \right)$$ $$Q(x) = 1$$

for some small $\varepsilon$.

Assuming that $\varepsilon$ is small enough, both polynomials are height-bounded by 1.

The sum is:

$$S = - \frac{5}{16}\varepsilon + \varepsilon^3$$

The question is how you would evaluate $P$.

$$P(x) = \left(-\frac{3}{32} - \frac{5}{16}\varepsilon + \frac{1}{2}\varepsilon^2 + \varepsilon^3\right) + \left( \frac{11}{16} + \varepsilon - \varepsilon^2\right) x + \left(-\frac{3}{2} - \varepsilon\right) x^2 + x^3$$

The number of bits of precision on the elements of $A$ are not relevant here; they are precisely representable with two significant bits. It seems to me that the precision you need to do the intermediate computation is more important.

For a small enough $\varepsilon$, you are going to get catastrophic cancellation whether you use the factorised form of $P$ or you use a method such as Horner's rule. At the very least, you need enough bits to represent $-\frac{3}{32} - \frac{5}{16}\varepsilon$ such that you have $n$ significant bits in the $\varepsilon$ term, so you can subtract $-\frac{3}{32}$ to get a good enough answer.
> 1 votes

---
Tags: numerical-algorithms, numerical-analysis
---


# Question
Title: Exhaustive search algorithms for np-complete problems
Somewhere in the forum (a question about p vs np) I read that no exhaustive search algorithm exists for np-complete problems with better time complexity than $2^N$, however the subset sum problem has an algorithm with worst case complexity $O(2^{N/2}$), this looks much better than $2^N$, what is wrong with this?

# Answer
$O(2^{n/2})$ is still $\mathcal{EXP}$.

The claim you report is known as the *exponential-time hypothesis* and is a stronger statement than $\mathcal{P} \neq \mathcal{NP}$. We don't actually know if it's true or not.
> 2 votes

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


title: NP-hardness of MCSP

text:
# Question
Title: NP-hardness of MCSP
*Ryan Williams and Cody Murray* in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time $O(n^{1/2} - \epsilon))$. He has done it by showing even stronger statement that: Even Parity can't reduced to MCSP using local reductions. In the same paper, he has mentioned in footnotes that "Dhiraj Holden and Chris Umans (personal communication) proved independently that there is no TIME(poly(logn)) reduction from SAT to MCSP unless NEXP $\subseteq \Sigma\_{2}^{P}$".

The problem is: $TIME(poly(log n))$ is much smaller than $O(n^{1/2} - \epsilon)$ for any $\epsilon$. (Since you are allowed only poly(log n) time to calculate each bit of output instead of $O(n^{1/2} - \epsilon)$). So, If MCSP is not locally hard(unconditionally), then how come under the much stricter reduction $TIME(poly(log n))$, it is still possible to prove MCSP is NP-hard?

# Answer
> 1 votes
The footnote mentions an earlier unpublished result which is superseded by a result proved in the paper.

# Answer
> 2 votes
The reductions considered by Murray and Williams are *local*: each bit of the output can be computed in time $O(n^{1/2-\epsilon})$ (on a RAM). In contrast, Allender et al. consider logspace reductions, in which each bit can be computed in logarithmic space. The latter notion of reductions is stronger since an algorithm running in space $C\log n$ could run in time $n^C$, where $C$ is an arbitrary constant (which could be larger than 1/2).

---
Tags: complexity-theory, reductions, circuits
---


title: Lexical analysis

text:
# Question
Title: Lexical analysis
Will the below statement cause any lexical error ?

```
int a123c ;

```

According to me, int would be tokenized as a keyword and there would be a lexical error when "a123c" would be encountered as it doesn't fall into any token category.

I read this question https://stackoverflow.com/questions/31369524/clarification-regarding-lexical-errors-in-c

Here the accepted answer says that there is no lexical error.

Also will a statement like

```
int x = 192.24.43.13 ;

```

cause any lexical error ?

I am confused.

# Answer
Which error message is generated by which phase of a compiler depends on the underlying language structure and implementation of the compiler.

Nevertheless, lexical analyzer is responsible for generating tokens, so at this phase you could check if some lexeme/token is valid or not. For example, you could check if the symbol `$` belongs to the source language. It is similar to reading an English text and checking if words belong to the English dictionary.

The syntax analyzer on the other hands checks if the sequence of tokens constitutes a legal program structure by analyzing the sequence of tokens (not characters). For example, it may check if a curled left bracket may follow the `if` keyword, or what token should follow what token in general. It is similar reading reading an English text and checking if "*He/She*" may be followed by a verb.

Assuming you are using a C/C++ compiler the first statement will not produce an error. You can read this related post.

As for the second line, this is what I got when tried to compile `int x = 192.24.43.13 ;`

`error: invalid suffix '.43.13' on floating constant`

This seems to be produced by a lexical analyzer. It complains about the structure of the floating point number.

I also tried to compile this line `int x = 192.24 .43.13 ;` which produced

`error: expected ';' at end of declaration`

which seems to be produced by a syntax analyzer.

Other possible lexical errors or warnings may be produced by the following lines

```
char ch = '12'; /* multi-character character constant */
char *a = "sdsd /* missing terminating '"' character */
/* this is unterminated comment

```
> 1 votes

---
Tags: compilers
---


# Question
Title: Converting Recursion into Into Iteration
While reading **Code Complete** second edition, I came across this line:

> You can do anything with stacks and iteration that you can do with recursion.

Is this true? or there are functions, that must be implemented recursively, and can't be done otherwise ?

# Answer
> 1 votes
Your CPU uses stacks and iteration to run *any* program, including programs based on recursion.

If you are unsure how this works, I suggest picking up an appropriate textbook.

---
Tags: recursion
---


# Question
Title: The set of turing machine that stops with input zero is not recursive
If M is a Turing Machine, consider the subset of $\mathbb{N}$ defined as: $$ \mathrm{ZTM} = \\{ x \mid M\_x(0)\downarrow \\} $$

i.e. the set of 'indexes' of machines that halt on zero. It is possible to use Rice's theorem to prove that this set is r.e. but not recursive.

But I'd like to have a direct proof, using directly some diagonalization argument if possible.

# Answer
> 1 votes
Hint: if you want to know whether $M$ accepts $w$, build a machine that replaces its input with $w$ and then does whatever $M$ does.

---
Tags: computability, turing-machines, termination
---


# Question
Title: Prove that $L_1 = \{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\}$ is not regular using Pumping lemma
I have been trying to understand Pumping lemmas for a while now, I am doing this exercise and I *think* that the pin has finally dropped. However, I am unsure if I am doing it even remotely correctly. I will briefly explain my attempt and thus my solution. Thereafter I would discuss a few points that are not as clear to me just yet. The exercise is the same as in the title. Here is my solution, but in-case you have forgotten:

Prove that $L\_1 = \left\\{\\, 0^m 1^k 2^n \\,\vert\\, \lvert m - n \rvert = k \\,\right\\}$ is not regular using Pumping lemma

So, in order to show that a language is not regular, we first must assume it to be regular (in-order to be able to use pumping lemma). If $L\_1$ is regular, then there exists a constant $n$ such that $ s \in L\_1 $ and $ |s| \ge n$ implies that there is a string $xyz$ satisfying

1. $s = xyz$
2. $ |y| \ge 1 $ and $ |xy| \le n $
3. $xy^iz \in L1 $ for all $ i \ge 0 $

We'll try to extract a contradiction. This is how I did it
I first create a string such that $ m + k = n $, my string was $0^1 1^1 2^2$ or just $0 1 2 2 $ I then split this string into three parts $ x y z $ so that $x = 0 \\ y = 1 \\ z = 22$

I then selected $ i \Rightarrow 2 $ which gives us , by the third rule, $ xy^2z $. This gives us the string
$ 01122 \notin L1 $ because $1 + 2 \neq 2 $

That is my solution, I hope you could understand it. Now to my discussion points:
As you see, I have provided a contradiction, which should be enough. However, what I also want to know is that in other exercises , say $\\{\\, a^n b^n \\,|\\, n \ge 1 \\,\\}$ you select a Pumping length $P$ and then typically get a string that is $a^p b^p$ i.e say that $ P = 3 $ you'd get $aaabbb $ AND then you divide into strings, but since the powers are all different in my exercise, picking a $P$ would not be as helpful, right?

Is it possible to select a Pumping length $P$ here too? Do I need to check the other conditions as well? As I understand it, a language is proven non-regular if it can't satisfy all of the requirements at the same time.

To clarify the question, when I meant 'how do I apply $P$'? I meant, how do I apply to the already existing powers ($m$, $k$ and $n$). Do I simply attach P to each power which would make it $ 0^{PM} 1^{PK} 2^{PN} $ ? A follow-up question: When I select $P$, must I then also select $M$, $K$ and $N$? So say I select $ P = 3 $ , should I *also* select $M = 1$, $K = 1$ and $N = 2$?

Thanks to the guy down under I know understand how to select a string ($ 0^p 1^p 2^2p $) for instance. But, then I don't know how to split the string. Can do it like this:

$x= 0^r$ , $y=0^{p-r}1^t$ and $z = 1^{p-t}2^{2p} $? Would this string be in the language ? I assume it would be as $xyz = 0^p 1^p 2^{2p} $ BUT Idk, I might be doing it all wrong

Then if I select $i = 2$ so $xy^2z$ I would get $xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{p-t}2^{2p} = 0^{2p-r}1^{p + t}2^{2p} \notin L$ Thus our contradiction, is this correct thinking then?

To answer the guy below:
Assume $L$ is regular, then there exist a constant $p$ such that $ s \in L$ and $|s| \ge p$ implies that there exist string $xyz$ satisfying following:
$1) s = xyz$
$2) |y| \ge 1$ and $|xy| \le p $
$3) xy^iz \in L$ for very $i \ge 0$

(Which answers your first question)
We pick our string $s = o^p 1^p 2^{2p}$ as the property of a string in a language must be $m + k = n $ $ (p + p = 2p)$
We then split the string into three parts $xyz$ , I am going to split them differently to you. $x = 0^p$ $ y = 1^p $ and $z = 2^{2p} $ if we then select $ i = 2$ we get $xy^2z = 0^p 1^{2p} 2^{2p} \notin L $ BECAUSE $ 1 + 2 \neq 2$

# Answer
For your choice of $s=0^11^12^2$, the pumping lemma might not apply. Remember, assuming that the language is regular means that there is an (unknown) integer $p$ such that the pumping lemma applies to every string of length $p$ or more. You don't know what $p$ is: if it were, say, 6 then since $|s|=4$ the PL simply wouldn't apply to your string and you could draw no conclusion.

That's why the strings chosen for pumping almost invariably involve $p$: it's there to assure that no matter what $p$ was, the pumped string would be at least $p$ characters long. For your example, you could choose $0^p1^p2^{2p}$ or $0^p1\\,2^{p+1}$ or $0^p2^p$ even something like $0^{p^2}1^{2p+1}2^{(p+1)^2}$.

---

Here's what a PL proof of this result looks like, with some bits for you to fill in: Assume the language $L$ is regular. Choose $s=0^p1^p2^{2p}\in L$, where $p$ is the integer of the pumping lemma (why can we say the PL applies to $s$?). Then if we write $s=xyz$ as in the PL, we'll have $y=0^t$ for some $0\<t\le p$ (why?) and then $xy^2z\notin L$ (why?), a contradiction (why?).

---

The proof without the PL is an example of a more or less common idiom: using closure properties. If $L$ were regular, then $L\cap 0^\*2^\*$ would be also, since regular languages are closed under intersection. However $$ L\cap 0^\*2^\*=\\{0^n2^n\mid n\ge 0\\} $$ (since we set $k=0$ when doing the intersection) but we know that that language isn't regular, so we have a contradiction and hence $L$ must not be regular.
> 1 votes

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


# Question
Title: Closure property of recursively enumerable language
I read that recursively enumerable languages are closed under intersection but not under set difference.

We know that, $A \cap B = A - ( A - B)$.

Now for LHS (left-hand side) to be closed under intersection, RHS(right-hand side) should be closed under set difference .

But we know that RHS is not closed under set difference so LHS is also not closed under intersection.

Suppose we assume that R.E is closed under intersection then,

$A \cap B = \overline{(\overline{A} \cup \overline{B})}$.

Now LHS can be closed only if RHS is closed under complement (as R.E languages are already closed under union). But we know R.E is not closed under complement, so again a contradiction.

So, R.E should not be closed under intersection right ?

# Answer
> 4 votes
Basically, "R.e. sets are closed under intersection means that for **any two r.e. sets** $A \cap B$ is again r.e, but when we say that r.e. are not closed under some set-theoretic operation it means there are at least one pair of r.e sets which results in **not-r.e.** set under that operation no matter it is set-theoretic difference or complement. In other words,

* R.e. sets are closed under a set theoretic operation $\star$ means that for any pair $A$ and $B$, $A\star B$ is r.e.
* R.e. sets are NOT closed under a set theoretic operation $\star$ means that NOT for all pair $A$ and $B$, $A\star B$ is r.e. In simple words, **there may be** sets $A$ and $B$ such that $A\star B$ is r.e., and **there exist** other sets $C$ and $D$ such that $C \star D$ is not r.e.

For example, the set $N - 2N$ (the set of all odd positive integers is r.e (even recursive), but the set $N - A\_{TM}$ is clearly not r.e. ($A\_{TM}$ denotes the set of Halting problem).

---
Tags: computability, closure-properties
---


# Question
Title: Reducing products in HoTT to church/scott encodings
So I am currently going though the HoTT book with some people. I made the claim that most inductive types we will see can be reduced to types containing only dependent function types and universes by taking the type of the recuror as inspiration for the equivalent type. I started to sketch how I thought this would work and after some stumbling I came to what I thought was an answer.

$$\cdot \times \cdot \equiv \prod\_{A, B, C : \mathcal{U}} (A \to B \to C) \to C$$ $$ (\cdot, \cdot) \equiv \lambda a : A. \lambda b : B. \lambda C : \mathcal{U}. \lambda g : A \to B \to C. g(a)(b)$$ $$ ind\_{A \times B} \equiv \lambda C. \lambda g. \lambda p. g(pr\_1(p))(pr\_2(p)) $$

This gives the correct defining equations (defining equations for $pr\_1$ and $pr\_2$ omitted) but this would mean that $ind\_{A \times B}$ would have the wrong type.

$$\text{ind}\_{A \times B} : \prod\_{C : A \times B \to \mathcal{U}} (\prod\_{a:A} \prod\_{b:B} C((a, b))) \to \prod\_{p : A \times B} C((pr\_1(p), pr\_2(p)))$$

And there doesn't seem to be a simple fix to this. I also thought about the following definition.

$$ ind\_{A \times B} \equiv \lambda C. \lambda g. \lambda p. p(C(p))(g) $$

But this just doesn't typecheck.

Another idea I had is to use $uniq\_{A \times B}$ to convert $C((pr\_1(p), pr\_2(p)))$ to $C(p)$ but it's not clear how to make that work. First off I'd have to show how to reduce identity types dependent function types which is proving even harder in my scribblings than products. Additionally $uniq\_{A \times B}$ doesn't seem to be definable without the proper form of induction so even if I allowed myself identity types as presented in the book I'd be no closer to having a definition of $uniq\_{A \times B}$

So it seems like we can define the recursor here but not the inductor. We can define something that's pretty close to looking like the inductor but doesn't quite make it. The recursion lets us perform logic taking this type to be the meaning of logical conjunction but it doesn't let us prove things about products which seems lacking.

Can we make the sort of reduction I claimed can be made? That is, can we define a type using only dependent function types and universes that has a pairing function and inductor with the same defining equations and types as products? It's my growing suspicion that I made a false claim. It seems like we're able to get so frustratingly close but just not quite make it. If we can't define it what kind of argument explains why we can't? Do products as presented in the HoTT book increase the strength of the system?

# Answer
> 8 votes
The standard reference I often give is Induction is not derivable in second order dependent type theory by Herman Geuvers, which says that there is no type

$$N : \mathrm{Type}$$

with functions $$Z:N\qquad S:N\rightarrow N $$

such that

$$\mathrm{ind}:\Pi P:N\rightarrow \mathrm{Type}.P\ Z\rightarrow (\Pi m:N.P\ m\rightarrow P\ (S\ m))\rightarrow \Pi n:N. P\ n $$

is provable. This suggests that indeed, such an encoding cannot work for pairs as you describe.

The system this is proven for is a subset of the Calculus of Constructions, which contains powerful product types and a universe. I suspect this result can be extended to the system you are interested in, depending on what you have.

Sadly, I don't know the complete answer to your question. I suspect that adding certain parametricity principles "internally" is exactly what is required to make these encodings work with the full induction principle. Neel Krishnaswami, whose knowledge is a strict superset of my own, wrote a paper along these lines with Derek Dreyer:

Internalizing Relational Parametricity in the Extensional Calculus of Constructions

Also of interest is the following paper by Bernardy, Jansson and Patterson (Bernardy has thought deeply about these topics):

Parametricity and Dependent Types

Obviously parametricity has a strong relationship with HoTT in general, but I don't know what the details are. I think Steve Awodey has considered these questions, since the encoding trick is useful in contexts where we don't really know what the eliminators should look like.

# Answer
> 8 votes
To get your idea working you need something extra, as was pointed out in @cody's answer. Sam Speight worked under the supervision of Steve Awodey to see what can be achieved in HoTT using an impredicative universe, see Impredicative Encodings of Inductive Types in HoTT blog post.

---
Tags: type-theory, type-checking, dependent-types, homotopy-type-theory
---


# Question
Title: Splitting the array in the median-of-median solution for $k$th smallest element problem
Regarding the median of medians solution to the $k$th smallest element in an array, why does the algorithm split the array into subarrays of length $n/5$, where $n$ is the length of the initial array? Why not $n/7$ or $n/3$? Why 5??

# Answer
> 2 votes
Along with the explanation given on wikipedia, I'll try to give more visual examples. The main point is that subarrays of length $ \frac{n}{3}$ make it a non-linear algorithm.

We can actually check out the 3 scenarios you discuss. I'm going to be referring to area diagrams similar to the one depicted on wikipedia. These area diagrams are a useful abstraction to see how large of a subproblem we might have to recurse on in the worst case. The area diagrams will look something like this:

Where $M$ is median of medians, $(\< M)$ and $(\> M)$ represent the area (amount of values in the array) that are potentially less than $M$ and greater than $M$ respectively, in the worst/best case. Note that in the area diagrams I present I say the area is roughly (**~**) some value. This is because it may be off by one or two and I am largely ignoring these small constants because they will be insignificant to the analysis. If you are bothered by this, you can assume $n$ is of a useful form such that the values are exact.

### For $\frac{n}{3}$ size subarrays we will end up with an area diagram like this:

It is clear that in the worst case we will have to recurse on roughly $\frac{4 n}{6}$ elements in the array. This will give us a recurrence relation: $$\begin{align} T(n) & = T\left(\frac{n}{3}\right) + T\left(\frac{4n}{6}\right) + cn\\ & = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn \end{align}$$ This actually turns out to be on the order of $O(n \log n)$. I won't go through an explicit proof of this recurrence because I'm sure it's been done before. If you wish to prove it to yourself, you can use a similar approach to this, or use the recursion tree method, or use the Akra-Bazzi method. So this subarray size won't work because we now have non-linear time complexity.

### For $\frac{n}{5}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + cn$$

This is linear $O(n)$! You can use this method directly to prove it is linear.

### For $\frac{n}{7}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{7}\right) + T\left(\frac{10n}{14}\right) + cn$$

This is also linear! Again, you can use the method I described above to prove this.

### So in conclusion

Diving the subarrays into length $\frac{n}{3}$ will not be good because it is non-linear! Diving the subarrays into length $\frac{n}{5}$ or $\frac{n}{7}$ will be very good because it is linear! You can actually go on to use $\frac{n}{9}, \frac{n}{11}, \ldots$ and still get linear time!

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


# Question
Title: Non-quadratic search for specific difference between elements in sorted array
New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either adjacent or nonadjacent elements in a sorted array of integers?

For example, if you have an array that's already been sorted, like so:

```
[1, 4, 6, 6, 10, 12, 13, 15, 16]

```

And you want to find if there's a difference between any of these elements that equals `3`, the pairs here would be `4, 1` and `15, 12` and `13, 10`.

But is there an algorithmic approach that would allow me to find these pairs without using two for loops?

# Answer
I know of two.

1. Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the difference of the pointed-to elements is too small, and the right pointer leftward whenever it is too large; the invariant here is that any satisfying pair must be taken from the interval of elements spanned by the 2 pointers.
2. Build a hash table containing every element as key (the value for each key is unimportant), then loop through every element $x$ again, checking whether $x+d$ or $x−d$ is in the hashtable.
> 3 votes

# Answer
Since the array is sorted, you can use two pointers technique. Set both of them on first element $v\_1$. First pointer called $i\_1$ indicates smaller item, second pointer called $i\_2$ indicates bigger one. When $v\_{i\_2} - v\_{i\_1}$ is bigger or equal than required difference, move pointer $i\_1$ forward, otherwise move pointer $i\_2$. Since each pointer traverses each item exactly once, this is effectively linear solution.
> 1 votes

---
Tags: algorithms, asymptotics, search
---


# Question
Title: Deterministic finite automata that accepts the only the string "aabb"
Lets construct a DFA over{a,b} That accepts only the string "aabb" in it. My problem with this video is that the tutor has moved arrow from state D to B why didn't he set a self loop on D .Im really helpless .

Move forward to minute 11

# Answer
Your purpose is to detect a substring $aabb$. When the FA is in state $D$ it already has read $aab$ (pay attention that in order to get to $D$ from the start state the FA must read $aab$ or $a\dots aab$). While in state $D$ there are two possible inputs: $a$ or $b$. If it reads $a$ it enters the state $B$ because it already has $a$ (it remains to read $abb$). On $b$ it enters the accept state. If on $a$ it stays on $D$ then it would accept a wrong string, for example, $aabab$ which does not contain $aabb$ as a substring. In other words, on $a$ you should send it back to the state $B$ as if FA switches from state $A$ into state $B$.
> 1 votes

---
Tags: turing-machines, automata, finite-automata
---


# Question
Title: Does Bloom filter with false positive rate greater than 0.5 make sense?
If the false positive error rate is greater than 0.5 then a Bloom filter is no different from coin flip, right?

Still, if one does implement this data structure with, say, P=0.55 then it would still work.

Should the constructor method of a Bloom filter implementation forbid values of P greater than 0.5?

# Answer
A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential *performance* issue, but not a *correctness* issue.

One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify this a bit, to see what I mean.

Suppose that you are trying to represent some subset of a universe of $S \subseteq U$. We'll further assume that you are testing elements of $U$ for membership in $S$ with equal probability.

* Let $p$ be the proportion of elements that are in the set (i.e. $p = \frac{|S|}{|U|}$).
* Let $c\_p$ be the cost of a precise test (measured in time, cycles, disk accesses, or whatever seems appropriate).
* Let $c\_b$ be the cost of a Bloom filter test, and we hope that $c\_b \< c\_p$.
* Let $q$ be the false positive rate of the Bloom filter.

If we only performed precise tests, the cost of each test is $c\_p$.

If we perform a Bloom filter test first, the cost of each test is $c\_b$ plus $c\_p$ times probability that we need to perform a precise test, whether due to true positives or false positives.

By the inclusion-exclusion principle, the average cost of this test is:

$$c\_b + c\_p(p + q - pq)$$

As long as $c\_p \> c\_b + c\_p(p + q - pq)$, the Bloom filter test gives you a net performance gain.

As you can see, the false positive rate $q$ is not the only important number here; Bloom filters with higher $q$ may, for example, have smaller $c\_b$ because physically smaller data structures are more cache-friendly.

For completeness, I will note that having a backup precise test isn't the *only* use case for Bloom filters. There are other situations where false positives are tolerable.

Consider a network protocol where two systems on different machines need to be kept in sync. You would like to only transmit the changes, to save bandwidth. But occasionally transmitting some data that you don't need to transmit is not as bad as failing to transmit data that needs to be transmitted. It may be wasteful to over-transmit, but it's not incorrect to do so.
> 5 votes

# Answer
In the same way that 0.5 is the error of a coin flip, 0.166666 is the error of a die throw. There's nothing sacred in the probability 0.5.

A Bloom filter gives you a guarantee that a coin flip cannot – it has no false negatives. Even if its false positive rate is 0.9, it still gives you some information.

Whether or not a high false positive rate is helpful or not depends on the application. A false positive rate of 0.5 still means that you filter half of the elements outside your set.
> 1 votes

---
Tags: data-structures, bloom-filters
---


title: Google's Deep Dreamer

text:
# Question
Title: Google's Deep Dreamer
I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system.

Could anyone explain to me in a step by step way, what the program does and how it does it.

# Answer
Google's Deep Dream project is research being done to visualize neural networks' learning to understand more about them.

First, you have to understand a Deep Belief Network on a high level. In short, it's a way for machines to 'learn' about data (images, in this case). That works, essentially, by transforming an input by several matrices (layers) through the network to get an output. Deep Belief Networks are trained to reconstruct their original image. All of the images are generally of some type, like animals. After some training, they begin to recognize basic features that are common between members of the training set, such as edges or colors.

The images published for the Deep Dream project are different ways of visualizing the data from trained networks. For some of the images, they observe the state of the image in layers between the input and output, resulting in artistic looking sketches of the original. For other images, they start with one image that is not related to the training set, send it through the network, then send the output through the network repeatedly to accentuate features that the network found in the image.
> 3 votes

# Answer
there are several basic concepts going on here that are not all explained in a straightforward/ brief way in most references, of which there are now many, which tend to range from scientific articles to handwaving/ "glossing over" popular science accounts.

1. train a "deep" artificial neural network using large amounts of image data. sometimes this is collected from youtube videos, and there are other large standard "corpuses" (collections) of data used in machine learning. this is also usually done on a cluster supercomputer.
2. now you have weights and a network for this ANN. the weights are "frozen" and one can analyze what types of "stimulus" "most excite" certain "neurons" in this ANN. the ANN will have neurons that classify based on image types. one can choose different neurons that were assigned during training.
3. the stimulus is a 2d matrix of pixels, usually grayscale, but possibly in color. a test stimulus starts out as a random noisy array. then the array is slowly perturbed so that it increases the excitation of the target neuron. this is using an optimization algorithm that is basically "reverse engineering" the stimulus independent of the learning algorithm etc., using the fixed network & frozen weights.
4. eventually this optimization of the stimulus does not increase the excitation of the target neuron any more. this is a sort of "optimal stimulus". this is the "resulting image".

volumes more could be written. a key concept is that the ANNs are embodying a real world implementation of "feature detectors" which have been studied for decades in neurobiology and CS. more detail can be found in this nice recent blog post by Oygard "Visualizing google classes" which step-by-step replicates the results using open source/ open science.
> 1 votes

# Answer
So far nothing's been said about technical details of DeepDream. I'll fill the blank.

The procedure is the following: pick some layer from the network (usually a convolutional layer), pass the starting image through the network to extract features at the chosen layer, set the gradient at that layer equal to the activations themselves, and then backpropagate to the image.

Why does it make sense? Intuitively, it amplifies the features that are maximally activated in the network. By backpropagating this gradient, we'll make an image update that will boost any of the existing activations. If there's a cat-like detector in the layer and the image contains some patch that looks a bit like a cat, DeepDream boosts this activation by updating this patch to be even more cat-like. As a result, DeepDream is trying to find cats and dogs everywhere in the image (ImageNet dataset has lots of dogs, so the network has many dog-related neurons).

If you look at the code, the key part is `objective_L2` function that makes this: $dx = x$ and then backpropagates.
> 1 votes

# Answer
Simply put, you:

1. Pick a layer
2. Forward propagate to that layer
3. **Set the gradient at that layer to the activation at that layer**.
4. Backpropagate to update the image

The general idea is that you want that layer's most activated neurons to change the image the most. So step 3 is actually just an ***easy hack*** to make sure **the higher the activation of the neuron, the larger the gradient that gets backpropagated from that neuron** and the more that neuron influences the change in weights.

As a result, you amplify the features in the image which those highest-activated neurons were already somewhat detecting in the beginning.

Some concise slides: http://www.cs.toronto.edu/~rgrosse/courses/csc321\_2017/slides/lec13b.pdf
> 1 votes

# Answer
So, what happens in deep dream is that instead of minimizing the cost function in neural network, we try to maximize the output value of n-1/n-2 layer. And in this way we change our image, to maximize output value of n-1/n-2 layer.

**Explanation**

The higher layers(n-1/n-2) stores high level features information like buildings, ears of a cat etc. The lower layers (2nd/3rd) store information about edges, corners in a specific place etc.

So when we try to maximize the output of higher layers, we see more of higher level things like buildings, cats etc(this depends on what data is the model trained on earlier). In other way, we are saying we want more cats, buildlings. So anything that lightly resembles these things, it will be made more prominent.

Similarly, when we try to maximize lower layers output, we see more of edges like things.

You can watch the following video from computerPhile to understand more about Google's deep dream. "Deep Dream"!
> -1 votes

---
Tags: machine-learning, image-processing, graphics, applied-theory, intuition
---


# Question
Title: Finding the Largest "Ordered" Difference in Elements of an Array
Suppose we are given an array of positive integers $P = \[p\_1, p\_2, \dots, p\_N\]$ where each $p\_i$ represents the price of a product on a different day $i = 1 \dots N$.

I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.

One easy solution is the following "exhaustive algorithm":

```
profit = 0
for i = 1 to N-1
  for j = i+1 to N
    if P(j) - P(i) > profit
      profit = P(j) - P(i)

```

The issue with this however is that it takes time $\Omega(N^2)$.

Can anyone think of something faster?

# Answer
The first observation is that the strategy of buying at the lowest price or selling at the highest price does not always maximize the profit. As you also note, the simple brute-force method works by trying every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $n \choose 2$ dates and $n \choose 2$ is $\Theta(n^2)$.

To achieve $o(n^2)$ running time, a simple transformation is applied to the input array. Instead of looking at the daily prices given, we will instead work with the daily *change* in price, where change on day $i$ is the difference between the prices after day $i-1$ and after day $i$. With a transformed input array like this, we now want to find the nonempty, contiguous subarray whose values have the largest sum. This contiguous subarray is called the maximum subarray.

For a detailed divide-and-conquer algorithm running in $\Theta(n \log n)$ time, see for example Chapter 4 of the Cormen et al. book, 3rd edition, page 68-74. The Wikipedia page also mentions Kadane's linear time algorithm and gives pseudocode.
> 6 votes

# Answer
I think I figured out an $O(N)$ algorithm that works for this case. The algorithm is similar to mergesort except that no sorting is done, and merging two sub-arrays together involves tracking the minimum buy price and the maximum sell price within the combined array. The tricky part involves making sure that you cannot buy before you sell.

Here is some MATLAB code that I wrote for this problem. The code assumes that the prices in the 'left' array occur before the prices 'right' array

Here is some pseudocode:

```
function [min_price max_price] = mergeprice(P)

N = length(P)

if N == 1 %base case for recursion

    min_price = P;
    max_price = P;

else %recursion

    %find midpoint of price list
    M = floor(N/2);

    %call mergeprice recursively to get min / max of price list
    left = P(1:M);
    right = P(M+1:N);
    [left_min_price left_max_price] = mergeprice(left);
    [right_min_price right_max_price] = mergeprice(right);

    %find the largest profit in the combined list using comparisons
    if (left_min_price <= right_min_price) && (left_max_price <= right_max_price)

        min_price = left_min_price;
        max_price = right_max_price;

    elseif (left_min_price <= right_min_price) && (left_max_price >= right_max_price)

        min_price = left_min_price;
        max_price = left_max_price;

    elseif (left_min_price >= right_min_price) && (left_max_price <= right_max_price)

        min_price = right_min_price;
        max_price = right_max_price;

    elseif (left_min_price >= right_min_price) && (left_max_price >= right_max_price)

        if left_max_price - left_min_price >= right_max_price - right_min_price

            min_price = left_min_price;
            max_price = left_max_price;

        else

            min_price = right_min_price;
            max_price = right_max_price;

        end

    end

end

end

```
> 0 votes

# Answer
Calculate The difference of contiguous profits in a array And apply kadane's algorithm on that array. You can solve this in O(n).
> 0 votes

# Answer
You can do it in O(n) time by using Kadane's algorithm. First transform the array A\[1..n\] to B\[1..n\] such that B\[i\] = Sum(A\[1\] to A\[i\]). and find the longest common subsequence in the new array
> -1 votes

---
Tags: algorithms, arrays
---


title: Complement of DPDA

text:
# Question
Title: Complement of DPDA
I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA.

Why can't we do the same with NPDA ?

Also is DCFL closed under complement just because we can toggle the states of DPDA ?

# Answer
The semantics of deterministic automata is symmetric with respect to acceptance and non-acceptance. The same doesn't hold for non-deterministic automata: a non-deterministic automaton accepts a word if it accepts on *some* computation path, but it rejects a word if it rejects on *all* computation paths. This is why complementing the set of accepting states works for deterministic automata but not for non-deterministic automata.

I suggest picking a simple example and seeing what goes wrong. For example, consider the following NFA:

This NFA accepts $\Sigma^\*$. If we complement its set of accepting states, it still accepts $\Sigma^\*$.

Finally, you ask whether the family of deterministic context-free languages is closed under complementation. This is indeed the case, for the reason you mention: given a DPDA for a language, if we complement the set of accepting states then we get a DPDA for the complement of the language. The same doesn't work for general PDAs, and indeed there are context-free languages whose complement isn't context-free.
> 3 votes

---
Tags: closure-properties, pushdown-automata
---


# Question
Title: If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular
I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step?

Thanks.

# Answer
You can show that if $L\_1 \subseteq L\_2$ and $L\_2$ is regular, then $L\_2 \setminus L\_1$ is regular iff $L\_1$ is regular. This follows from the product construction, for example. Taking $L\_2 = \Sigma^\*$, we find that $\Sigma^\* \setminus L\_1$ is regular iff $L\_1$ is regular. Hence if $L\_1$ is *any* non-regular language, then it refutes your statement taken with $L\_2 = \Sigma^\*$.
> 4 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


title: RICE theorem applications

text:
# Question
Title: RICE theorem applications
I am having some confusion in understanding RICE's theorem.

It says every non trivial property of RE in undecidable.

I need to understand when to apply RICE's theorem and when to not.

Questions like:- Turing machine makes at least five moves,It accepts a string input of length atleast five ,TM halts for every input on length \<50 are all decidable.

But these are NON TRIVIAL properties?Some TM will make 5 moves and some will not,Some will halt on every input \<50 and some will not?So if this is Non trivial property then why cant we apply RICE's theorem?

On other side questions like:- TM accepts at least 10 strings is undecidable because some TM will say yes and some will say NO.Then why can't we use same concept on above mentioned questions?

Please help me in understanding how to identify whether question is based on Rice's theorem or not?

# Answer
The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM $M$ belongs to the set, and $N$ is a TM equivalent to $M$, then the encoding of $N$ must also belong to the set.

Equivalence here means that the TMs $M,N$ terminate on the same inputs, with the same output (including acceptance).

Conditions like "halts in 50 steps" break equivalence, in general. I.e. it is possible that $M$ halts in 10 steps with output zero on every input, yet $N$ does the same after "wasting" 100 steps. So, Rice can not be applied to these.

> Questions like:- Turing machine makes at least five moves,It accepts a string input of length at least five ,TM halts for every input on length \<50 are all decidable.

No. The property "at least five moves" is decidable. The properties "accepts a string of at least five" and "halts for every input of length \<50" are NOT decidable. Indeed, these properties only care about the input/output behavior of the TM, hence if $M$ satisfies one of those, and $N$ is equivalent, then $N$ also satisfies the same property. So, Rice applies to those.
> 6 votes

# Answer
I think rice theorem considers non trivial property of language not Turing machines. The properties that you have mentioned are not related t languages, they are related the machines. A non trivial property for languages would be "Does the language generated by a turing machine contain string of length 10?".
> 0 votes

---
Tags: rice-theorem
---