# Question
Title: Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}
Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i\*j ;i, j ≥ 1}

Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to just add a c for every a or b.

But I am having real trouble with this one. I am guessing Cfgs wouldnt be enough here, but idk.

Can anyone help? Thank you :)

# Answer
The language does not satisfy the pumping lemma.

Let $p\geq 1$, and consider the word $w=a^pb^pc^{p^2}$. Note that $w\in L$ and $|w|\>p$. Hence, there exists a partition $w=xuyvz$, such that $0\<|uv|\leq |uyv|\leq p$, and for all $i\geq 0$ it holds that $w\_i=xu^iyv^iz\in L$. Denote $n\_\sigma=\\#\_\sigma(uv)$ for all $\sigma\in \\{a,b,c\\}$. Then, $0\<n\_a+n\_b+n\_c\leq p$. Note also that since $|uyv|\leq p$, it follows that either $n\_a=0$ or $n\_c=0$. Moreover, by pumping with $i=0$, we have $w\_0=a^{p-n\_a}b^{p-n\_b}c^{p^2-n\_c}\in L$ and so $(p-n\_a)(p-n\_b)=p^2-n\_c$.

Cleary, $n\_c$ can't be zero as otherwise $(p-n\_a)(p-n\_b)=p^2$ which implies $n\_a=n\_b=0$. Thus, $n\_a=0$ and so $p(p-n\_b)=p^2-n\_c$.

After rearranging we have that $pn\_b=n\_c\>0$. Hence, $n\_b\neq 0$ and $n\_c\geq p$ and we reached a contradiction.
> 0 votes

---
Tags: formal-languages, context-free, formal-grammars, chomsky-hierarchy
---


title: Is English Turing-complete?

text:
# Question
Title: Is English Turing-complete?
Is English Turing-complete?

Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators used in programming that aren't used in person-to-person communication, at least in daily life.

Also, what level of English is required until it becomes Turing complete? For example: 1st grade? College level?

# Answer
English is neither a language with a given operational semantics nor a model of computation of any other kind. Your question does not make sense.
> 13 votes

# Answer
The problem with your question is that there are fundamental differences bewteen *natural languages* (such as English) and *programming languages* such as Java, Python, or Turing machines: natural languages are inherently ambiguous, while programming languages are inherently unambiguous. Because of this, as Andrej Bauer says, what it means for an English sentence to "compute" something can't be well defined in general.

For example, consider the following simple program (written in a Python-like pseudocode):

```
my_program(i):
    if i > 10:
        infinite_loop()
    else if i > 0:
        crash()
    else:
        print("Hello world!")

```

The thing to notice about this program (and *all* programs) is that there is only one possible semantics for the program. The program takes as input a natural number $i$ and its behavior is completely determined by what $i$ is. To be clear, the actual behavior may differ: if $i \> 10$ then it runs forever, if $i \in \\{1, 2, 3, \ldots, 9\\}$ it crashes, and if $i \le 0$ then it prints a string and terminates. But given a fixed value of the input $i$, the behavior is always the same; there is never any ambiguity about it. The compiler cannot simply choose to interpret your code differently than what you wrote, and say, crash when give input $i = 15$. In summary, **programs unambiguously correspond to a unique set of possible behaviors.**

In contrast, a natural language such as English if full of ambiguities that mean **English sentences do not always correspond to a unique set of possible behaviors.** A famous example of this is the Berry paradox, which is the following simple phrase:

```
The smallest positive integer not definable in under sixty letters.

```

This appears to be perfectly valid English; it makes sense. In fact, it appears to refer to an unambiguous integer. Yet, it actually does not. Because, suppose it referred to some integer $n$. Then $n$ is the smallest positive integer not definable in under sixty letters; but *the above is a description of $n$ in 57 letters!* So this is a contradiction. We can only conclude that, despite seeming to make sense, the above sentence does not actually refer unambiguously to a number. In other words, English is ambiguous.

The same problem, although less obviously paradoxical, happens all the time in everyday speaking; Wikipedia gives many examples, such as

```
I'm glad I'm a man, and so is Lola

```

which is perfectly valid English, but has not just two, but three different possible meanings.

Now returning to your question:

> Is English Turing-complete?

There is a fundamental issue here. It does not even make sense to refer to English as Turing complete or not, because we do not know any way of associating English sentences unambiguously to possible behaviors (or to possible Turing machines). While your argument is perfectly reasonable:

> Intuitively it makes sense that English is Turing complete since you can talk someone through building a Turing machine.

it falls apart, because although there are many ways of describing how to build a Turing machine, most of them will be ambiguous. So what do you define as a valid description? For example, is the following a valid description of the Turing machine?

```
The Turing machine with the smallest number of states that can't be described in 100 or fewer letters.

```

If it is not valid, then what is a valid description? If you manage to answer this, providing an unambiguous way to describe everything (such as, say, mathematical logic stated in English), then I claim that actually you are no longer speaking English! Instead, you have just invented a specialized *programming language*, a small subset of English for which you have defined the meaning of the words.
> 4 votes

# Answer
Yes it's "Turing complete" ... and the only words needed are those that you can use to describe the behaviour of a Turing machine:

"if you're wearing a hat of color $x$ and find (or don't find) a stone in the box in front of you, then wear a new hat of color $x'$, put/remove a stone in/from the box and move to the next/previous box"

... it could be a child game :-)
> 1 votes

# Answer
The simplest answer to the question that I can think of is that, if X is Turing-complete programming language then it must be possible to write a program in X to convert programs written in X to Turing-complete language Y, the Y must also be Turing-compete here, now just replace the X with English and Y with any programming language on earth, Humans have written documentations to create programming languages, to create compilers, also created algorithms before there was no programming language in existence, hence proved...
> 0 votes

---
Tags: turing-machines, turing-completeness
---


title: What exactly is delta reduction?

text:
# Question
Title: What exactly is delta reduction?
I have found two definitions of delta reduction:

1. Barry Watson defines it as the result of applying a primitive computation to terms in normal forms
2. But in Coq they define it as the substitution of a variable in a local context for its definition.

Although I wouldn't be entirely surprised if one turns out to be a special case of the other, at first impression they look like different reductions. So which one is correct?

Bonus points: in Coq they define even more reductions. Are these "recognised" in literature or are they specifically defined in Coq only? If they are generally accepted definitions, is there a comprehensive list of all known reductions beyond the standard alpha, beta, eta?

# Answer
Sadly, there is no clear consensus on what $\delta$-reduction is, other than the Greek letter $\delta$ being similar to the Latin "d" which also happens to be the first letter of "definition".

Indeed, the two definitions you give are both intuitively "replace a symbol $f$ by its definition $F$", where $F$ is uncurried in the first case, and curried in the second one.

This is related to $\mathsf{let}$-reduction as well, since a `let` is just introducing a symbol representing another term, though as the second link notes the semantics are slightly different (the $\mathsf{let}$ is deleted from the context in this case). This variant is called $\zeta$ in Coq parlance, also a very non-standard term, sadly.

Note that in **non-dependent** settings, these can *all* be replaced by $\beta$-reduction, changing a definition $$\mathsf{let}\ f := F\ \mathsf{in}\ t$$ by $$(\lambda f. t)\ F$$

but this **does not work** in dependently typed languages since the term $\lambda f. t$ may now be ill-typed!

Finally: in theorem proving settings, unfolding *all* the definitions to prove an equality isn't remotely practical, the sizes of terms become huge even with sharing. This means $\delta$-conversion needs to be done somewhat cleverly when performing conversion, and is a subject of study in its own right.
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Why are computability problems always written in full caps?
Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. *SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, VERTEX COVER*. Etc. They're not proper titles, just single words which don't mean much on their own.

Is there any reason for this terminology, especially the all caps part? Who started that terminology?

# Answer
> 26 votes
After the Cook-Levin Theorem Richard Karp realized that the complexity of computational problems could be compared. His paper was prepared in a type-writer font, and used underlining and all-caps for emphasis. Printing technology at the time.

Karp, R.M. (1972). Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA. https://doi.org/10.1007/978-1-4684-2001-2\_9

# Answer
> 14 votes
In the area of discrete mathematics, sets are usually typeset in capital letters. The above problem classes are sets of problems, e.g. SAT is the set of all boolean satisfiability problems.

Thus, the notation is probably consistent with what you are used to from set theory.

---
Tags: complexity-theory, computability, np-complete, np, decision-problem
---


# Question
Title: Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)\* and (ab)\* are:
(a+b)\* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)\* = { ε, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is confusing me!
I didn't find (a+b)\* = (ab)\* in rules of regular expressions.

# Answer
> 1 votes
The regular expressions $(a+b)^\*$ and $(ab)^\*$ represent languages according to the semantics of regular expressions. Formally, the language $L\[r\]$ corresponding to a regular expression $r$ is defined as follows:

* $L\[\emptyset\] = \emptyset$.
* $L\[\epsilon\] = \epsilon$.
* $L\[\sigma\] = \sigma$ for $\sigma \in \Sigma$.
* $L\[r\_1+r\_2\] = L\[r\_1\] \cup L\[r\_2\]$.
* $L\[r\_1r\_2\] = L\[r\_1\] L\[r\_2\]$, where $L\_1 L\_2 = \\{ w\_1w\_2 : w\_1 \in L\_1, w\_2 \in L\_2 \\}$.
* $L\[r^\*\] = L\[r\]^\*$, where $L^\* = \bigcup\_{n \geq 0} L^n$, and $L^n$ is defined recursively by $L^0 = \\{\epsilon\\}$ and $L^{n+1} = L^n L$.

Two languages over the same alphabet are equal if they are equal as sets, that is, if they contain the same words. In your case, you haven't specified the underlying alphabet $\Sigma$, so I'm assuming that $\Sigma = \\{a,b\\}$.

Now that you have all the definitions, you can check for yourself whether $L\[(a+b)^\*\]$ equals $L\[(ab)^\*\]$.

# Answer
> 0 votes
No, they are not equal but (a+b)\* and (a\*b\*)\* are equal.

# Answer
> 0 votes
No, $(ab)^\*=\\{\epsilon,ab,abab,abababa\cdots\\}$. The length is always even.

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


# Question
Title: Discrepancy in Time-Complexity of Bounded Halting Problem
Can you please help identify if the two following variants of the bounded halting problem are in different deterministic complexity classes?

$$ H1 = \\{ (\langle M \rangle, w, t) \mid \text{$M$ accepts $w$ in time at most $t$} \\} $$ $$ H2 = \\{ (\langle M \rangle, t) \mid \forall \text{$w$, $M$ accepts $w$ in time at most $t$} \\} $$ $$ \text{(where $t$ is binary-encoded for both)} $$ When I do the math, (ignoring simulation cost for readability), I get:

* $H1 = O(2^{N}) \in $ EXP-TIME
* $H2 = O(2^{N})\*O(2^{2^N}) \in $ 2-EXPTIME
* To illustrate my thinking, here are a few examples:

| t (base 10) | t (base 2) | N | H1 (Single Simulation) | Total Unique inputs length t | H2 |
| --- | --- | --- | --- | --- | --- |
| 2 | 10 | 2 | 2 steps = O(2^N) | 4 = O(2^(2^N)) | 8 = 4\*2 |
| 3 | 11 | 2 | 3 steps | 8 | 16 = 8\*3 |
| 4 | 100 | 3 | 4 steps | 16 | 48 = 16\*3 |
| 9 | 1001 | 4 | 9 steps | 512 | 2048 = 512\*4 |

Resources regarding *H2*:

Resources for *H1*:

---

**Update**: wiki exp-complete article now updated to describe H1

# Answer
I think it's simply that the Wikipedia page is a bit sloppy as it seems to be referring to $H\_1$ (based on the text), even though I agree with you in that it could read as if it was talking about $H\_2$. It is indeed true that $H\_1$ is EXP-complete. About the status of $H\_2$, I would also guess 2EXP-completeness, but the only obvious part is membership.
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: How to get a time estimation of an O(n) function to modern multi-core CPU time?
How to get an estimation of an O(n) function to modern multi-core CPU time? For instance, how can I find the time it takes to run an algorithm in a 4-core/8-core CPU when I know its O(n) ? I searched on google I find nothing about my question...

# Answer
> 2 votes
The answer to this question is not trivial.

First of all, let's talk about asymptotical analysis: if you have a (small) constant number of cores $k$, e.g. $k=8$ or $k=16$, even if your application has an ideal speedup of $k$, the asymptotic execution time is still $O(\frac{n}{k})=O(n)$. Thus, asymptotical analysis doesn't help us in this scenario.

Now, we have to talk about parallelizzability. Having more cores does not always mean having more speed. Consider the following problem:

You have a black-box function $f$ and you have a program which takes in input a value $x\in \mathbb{R}$ and an integer $n\geq 0$ and gives as output $f^n(x)$, where $f^n$ indicates the composition of $f$ $n$ times.

Since $f$ is a black-box function, in order to obtain $f^n(x)$ the only thing you can do is to apply $f$ iteratively, until you get $f^n(x)$. This program is clearly not parallelizable, because even if you have more than one core, the only thing you can do is iteratively apply $f$ to the new value.

If instead, you have some operation like summing two vectors of length $k$, you can make each core sum one component, obtaining so the maximum level of parallelization.

Between these two extreme examples, there is a world. You often can parallelize only a portion of your program.

Then, out of the ideal world, there is something called *overhead*, which is the cost of parallelizing. The parallelization needs to be managed by the programming language, for instance you need to create threads and assign the work to each thread and this has a cost.

If you try to parallelize the first program (the unparallelizable one) with all your $k$ cores, the only result you will obtain is a program which is slower than the sequential one, because you try to manage a lot of threads but then you end up using only one of them.

In conclusion, parallelization is not a trivial task and it has to be evaluated in specific use-cases with the opportune metrics instead of using asymptotic time complexity analysis alone (e.g. speedup, efficiency, scalability, etc)

# Answer
> 2 votes
Big-O tells you an upper limit for the execution time up to a constant factor. And the difference in execution time between a Zuse Z3 and today’s leader in the top 500 supercomputer list is also just a constant factor. So Big-O tells you nothing about the execution time.

If instead of Big-O you examine a problem much more carefully then you may be able to say “this problem takes roughly 123 n^2 fast instructions to find a solution, it is not limited by memory access, my processor can do about 2.5 instructions per cycle on average, at 3 billion cycles per second, and eight cores which need to perform 10% more instructions than a single core”, then you could estimate that the total time to run this for some n might be 123 n^2 * 1.1 / 60 billion seconds of 2.25 n^2 nanoseconds.

# Answer
> 1 votes
Knowing that the theoretical complexity of an algorithm is $O(n)$ tells you very little. Because

* it is only an upper bound, there is no guarantee that it is tight;
* the conversion to real-world times depends on the "hidden constant", which you don't know,
* more importantly, the usual models of computation rest on the assumption that memory accesses are done in constant time. This is plain wrong ! In fact, memory accesses take time that highly depends on $n$, on the pattern of accesses and other factors. The time is not even deterministic ! Running the same program twice on the same data, you may observe large deviations.

---

Regarding the behavior when you increase the number of cores, the answer is simple: the time does not depend on it because unless you explicitly parallelize it, your program will keep running on a single core. In fact it can run slower in case of switches between the cores, or contention caused by other tasks.

You might say that the time can reduce because other active tasks may run on other cores, but when you look at typical machine activity, you will notice that most of the cores are just idle.

---

Example activity:

---

If you are lucky, your algorithm might be parallelizable, but that usually comes at the cost of a (possibly complicated) rewrite. As synchronization and task decomposition add overhead, you will get less than speedup $n$ for $n$ threads.

If you are unlucky, no parallelization will be possible, or parallelization will result in a program that is slower than the single-threaded version.

---
Tags: big-o-notation
---


# Question
Title: Show that if <S1;S2,s> => * s', it is not necessarily the case that <S1,s> =>* s'
I am studying Structural Semantics for programming languages and I have come to this proof that I can not achieve.

Whith these rules plus Splitting and No interference, I am trying to get a proof.

I tried:

```
s0 in State
<S1,s> =>* s0

Stm0 in Stm
<Stm0, s0> =>* <S2,s'>

```

And somehow put S2 inside Stm0, but it does not make sense and can not get it to work.

I am sure it is something related to an intermediate state and make S2 jump to \<S2,s'\> from that state.

EDIT:

Hi, I did the following:

```
S1 = Skip, so
<Skip,s> => s
then
<Skip;S2,s> => <S2,s>, for s'=s

```

Can this serve as a proof?

# Answer
> 2 votes
The proof you give is a counterexample of the reciprocal. That is, you're giving an example where $\langle S\_1, s\rangle \Rightarrow^\* s'$ but not $\langle S\_1; S\_2, s\rangle \Rightarrow^\* s'$.

To prove the original statement, you would need to find an $s'$ such that $\langle S\_1; S\_2, s\rangle \Rightarrow^\* s'$ but $\langle S\_1, s\rangle \Rightarrow^\* s'$ does not hold. For example, if $S\_1 = \text{Skip}$ that means choosing $s'$ such that $\langle S\_2, s\rangle \Rightarrow^\* s'$ but $s' \not\Rightarrow^\* s$.

I'm not sure about the particulars of your language, but if $s = \\{x \mapsto 1, a \mapsto 2\\}$, $s' = \\{x \mapsto 2, a \mapsto 2\\}$ and $S\_2 = x := a$ then the required condition to holds.

---
Tags: programming-languages, operational-semantics
---


# Question
Title: How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?
I was confused how to label this `for (int interval = n/2; interval > 0; interval /= 2)`  with counting operation and estimating this operation so that I can get that exact Running time of this shell short algorithm

```
for (int interval = n/2; interval > 0; interval /= 2)
    {
        for (int i = interval; i < n; i += 1)
        {
            /* store a[i] to the variable temp and make the ith position empty */
            int temp = a[i];
            int j;
            for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
                a[j] = a[j - interval];

            // put temp (the original a[i]) in its correct position
            a[j] = temp;
        }
    }

```

```
               1    (1 or n-1)?
int interval   =     n / 2

```

now here with condition that I am referring as i \< 0 which is n+1 in other operation sample.

```
       (n+1)
interval > 0

```

I know that the operation of this is log base2

```
         log base 2
interval /= 2

```

# Answer
Rewrite it as follows:

```
interval = n/2
while (interval > 0) {
    ....
    interval = interval/2
}

```

Each of the three operations takes $O(1)$. The running time of the loop is the total running time of all iterations. It depends on what happens on each iteration. As an example, consider the code

```
for (interval = n/2; interval > 0; interval /= 2)
    interval = 0;

```

This code runs in $O(1)$.
> 0 votes

# Answer
Assuming that the body of the main loop takes `f(n)` operations, the total operation count will be (for `n` an exact power of `2`)

```
f(n/2) + f(n/4) + f(n/8) + ... f(2) + f(1).

```
> 0 votes

# Answer
To analyze the running time of loops, we need to know how many times the loop executes, and then we write the total time as the sum of the time needed for each execution. When a "for" loop is determined by an index that starts at one number, ends at another, and increments once per execution, this is easy, and can be translated directly to summation notation. For the following loop,

```
for (int i=a; i<=b; i++) {
   perform_1_operation;
}

```

we can write the number of operations performed as $$ \sum\_{i=a}^b O(1) = O(b-a)$$ And for the following nested loop

```
for (int i=a; i<=b; i++) {
   for (int j=i; j<=b; j++) {
       perform_1_operation;
    }
}

```

we can write the number of operations performed as $$ \sum\_{i=a}^b \sum\_{j=0}^i O(1) = \sum\_{i=a}^b O(i) = O(b^2-a^2)$$ (Don't worry too much about how I evaluated this if you aren't familiar.) But in your case, the first loop is not so easy. However, we can think about transforming it from

```
for (int interval = n/2; interval > 0; interval /= 2) {
    ...
}

```

to

```
for (int i=1; i<= log_2(n); i++) {
    interval = n/2^i;
    ...
}

```

which can then be analyzed as usual. You should spend some time picking specific values of $n$ and checking that these two loops are indeed the same, and then think about why it is true for any positive integer $n$.
> 0 votes

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


# Question
Title: Longest Increasing Co-Prime Subsequence?
This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.

Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing subsequence of this array such that every adjacent pair in the subsequence is co-prime, ie. $ gcd(a\_{i}, a\_{i + 1}) = 1 \space \forall \space 0 \<= i \< K - 1 $ where $ K $ is length of subsequence.

Would it be possible to have a solution better than $ O(N^2) $ if each number is in range $0$ to $10^5$?

I was exploring solutions using segment trees but it's very tricky, compared to a different version where adjacent pairs should be strictly non-coprime which would be trivial.

If there is some way to make it more efficient I would like to know.

# Answer
I think there is a slightly better algorithm, depending on the relative sizes on the upper bound $B=10^5$ and $N$.

The proposed algorithm proceeds like the usual DP algorithm, scanning the array from left to right, and at each array position $i$ you it computes what is the array position $j \< i$ that maximizes the value of $\text{dp}\[j\]$ subject to $A\_j \< A\_i$ and $\gcd(A\_j, A\_i) = 1$.

To compute $\text{dp}\[i\]$ you don't actually need to compute $j$, it suffices to compute $\text{dp}\[j\]$. So we will find it using binary search. The binary search condition is, is there a $j \< i$ such that $i$ can connect to $j$ and $dp\[j\] \geq k$?

We will actually count the number of such $j$ (and then check if its $0$ or $1$) doing inclusion exclusion. The formula for that number is $$\\#\big\\{j\<i : \gcd(A\_j, A\_i) = 1, A\_j \< A\_i \text{ and } \text{dp}\[j\] \geq k \big\\} = \sum\_{d|A\_i} \mu(d) M\_d^i(k)$$ Where $M\_d^i(k)$ is the number of indices $j\<i$ such that $d | A\_j$, $A\_j \< A\_i$ and $\text{dp}\[j\] \geq k$, and $\mu$ is the Mobius function.

If for each index $j$ such that $d | A\_j$ we consider the 2d point $(A\_j, \text{dp}\[j\])$ then $M\_d^i(k)$ is a query of the form "How many points are there in this (shifted) quadrant of the plane?", which can be solved in $O(\log N \log B)$ using lazy creation 2d segment trees. We need to store a segment tree like this for each possible $d$ (which are the divisors of elements of the array). And each time we compute a new value of the DP, we need to insert a point in all the required datastructures (which correspond to all divisors of the value $A\_i$).

If $D$ is a bound on the number of divisors for numbers less than $B$, then the complexity of this solution would be

$$O(N D \log^2 N \log B)$$

Note that $D$ grows slower than any polynomial with respect to $B$. In particular, for $B = 10^5$, $D \< 240$.
> 1 votes

---
Tags: data-structures, optimization, dynamic-programming, number-theory, longest-increasing-subsequence
---


title: R2000 ALU Design

text:
# Question
Title: R2000 ALU Design
probably a couple decades too late to ask this question, but does anyone know anything/have detailed documentation about the hardware/design underlying the ALU unit in the early MIPS R2000 CPU?

Ideally I am looking for a circuit diagram like the following:

I don't need/am already familiar with the information from spec sheets/RISC guides like this:

Unless MIPS Computer Systems/R2000 designers have talked about it somewhere, I believe this is a reverse engineering question.

# Answer
> 3 votes
What you're looking for is unlikely to have ever existed.

The R2000 ALU was almost certainly not designed in terms of gates, but either in a high-level synthesis language such as Verilog, or in terms of individual transistors.

John Hennessy, the main designer and one of the founders of MIPS, co-wrote two books on the subject. His co-author was David Patterson, who led the Berkeley RISC project that became the SPARC architecture.

The books are:

* Patterson, David; Hennessy, John (1996). *Computer Architecture: A Quantitative Approach* (1st ed.). Morgan Kaufmann. ISBN 978-1-55-860329-5.
* Patterson, David; Hennessy, John (1994). *Computer Organization and Design* (1st ed.). Morgan Kaufmann. ISBN 978-1-55-860281-6.

The latter book introduced the DLX, which is essentially a modernisation and clean-up of the MIPS I, and has much more detailed diagrams and explanations of the data path.

And an extended discussion, with many diagrams, of how to handle issues such as hazard detection and forwarding.

Needless to say, both books are worth your time to read, the latter one especially.

But, of course, you're asking about the ALU.

It's likely to be a lot simpler than you might think. Chapter 4 of *Computer Organization and Design* describes the DLX ALU, which is probably pretty much the same as the MIPS I integer ALU. It's made from a bunch of 1-bit ALUs which compute all of the interesting operations in parallel, followed by a multiplexer to select which one is to be computed.

The high-bit ALU is slightly modified with some additional circuitry to perform overflow detection. And so the ALU as a whole looks like this.

And that is probably as close as you're going to get.

---
Tags: computer-architecture, mips
---


# Question
Title: What exactly is stored in dynamic linking
I read that in dynamic linking we store the references to the the methods of the library , but a library is essentially a collection of files , and every file will have some code in it , so the reference is stored of which file?

# Answer
> 1 votes
A library is a single file, containing compiled code. It needn't be structured as the original files. The references are to all functions that were defined (and explicitly exported).

# Answer
> 1 votes
When you include an header, you declare to the compiler that you defined the functions found in the header somewhere. The compiler doesn't know where but it trusts you to provide those definitions during linking.

During compilation, the compiler compiles every source file independently. Each source file has to be self contained and contain at least all declarations for the functions you call. For functions that are not defined, the compiler leaves `call` instructions to those functions with an undefined address to reach them. It also leaves the symbol of the function (its name) along with a relocation method (see program counter or PC relative addresssing, absolute addressing, code models, etc). The exact way that it passes this information to the linker varies between executable file formats.

Once you call the linker, you have to provide all libraries that you call into (associated with each header that you include) including dynamic libraries. Otherwise, the linker complains that it didn't find the definition for certain of these functions and is thus not able to relocate the call instructions. The linker's job is to take all compiled object code files (unlinked code made by the compiler) and arrange them in proper order in code blocks with call instructions fixed to jump at the proper address for functions defined in other object code files or libraries. The standard libraries are often simply added by default to the linker's command line so that's why you might not need to add them manually in most cases.

For your question, in dynamic linking the reference is stored in the object file after compilation but the final executable contains a string which is the path of the library. The linker which is called after compilation doesn't yet know where this library is loaded so it leaves a path to the library as you provide yourself when you call it. The os then either loads that library in RAM anywhere it deems appropriate and fixes the relocations before jumping to your first instruction or, if the library is already loaded, it fixes the relocations directly and makes sure to adjust page tables to make sure the library is found in the address space of your program.

---
Tags: operating-systems
---


# Question
Title: Any text similarity algorithms for substrings?
I need to implement simple search on Python package names and I'm struggling with ranking the results. Considered Levenshtein distance, but it would give too low ranking for matches which contain the search term exactly but have a long extra prefix or suffix.

I was thinking of applying Levenshtein to each substring of the same length as the search term and then using the best result, but I'm hoping there is a more elegant solution.

Is there a well known algorithm, which considers both the length and the similarity of the match?

# Answer
It seems that in your context there can be prefixes or suffixes added to the substrings you care about, so for example you want the strings $w$ and $\alpha v \beta$ to be similar if $v$ and $w$ are themselves similar, with some penalty that depends on the length of the extra characters in $\alpha$ and $\beta$. This can be achieved in several ways:

1. As Yves Daoust commented, if you're defining a variation of Levenshtein's distance you are free to assign different weights to deletions, insertions and substitutions. Moreover, the weight can also depend specifically on the characters; for example, you could consider that using 'n' instead of 'm' is a common typo, and thus will penalize an 'n'-'m' substitution less than a 'a'-'z' substitution.
2. As suggested by Hendrik Jan's comment, the field of computational biology is extremely into the problem of (sub)-string similarity, and therefore their literature might be a great place to start. Here are some surveys found upon a quick Google search. String Similarity Search and Join : A Survey, A guided tour to approximate string matching, A Comparative Study on String Matching Algorithm of Biological Sequences

In order for anyone to be able to help you more precisely about defining a good similarity measure you'd need to provide the context of your application; there's not silver bullet here, and the best solution will depend on the specific constraints and goals of your context.
> 3 votes

# Answer
Jaro-Winkler distance could be what I need, as it has a performant implementation with permissive license (https://pypi.org/project/jarowinkler/)
> 0 votes

---
Tags: search-algorithms
---


# Question
Title: Solving recurrence $T(n) = T(n - 1) + n$ with substitution method
How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method? I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$: $$T(n) \leq O(n^2) \\ \leq c(n-1)^2+n \\ \leq cn^2+c-2cn+n$$ How can i continue?

# Answer
> 0 votes
We can prove easily in induction, that $T(n)=c + \sum\_{i=1}^n i$. Assume correctness for $n$, we will prove for $n+1$. Clearly, $T(n+1)=T(n)+(n+1)=c + n+1 + \sum\_{i=1}^n i = c \+ \sum\_{i=1}^{n+1} i$.

A nice result you are probably familiar with, if you learned about arithmetic progression series, is that $\sum\_{i=1}^n i = \frac{n(n+1)}{2}$

Thus, $T(n) = c + \frac{n(n+1)}{2} = \Theta(n^2)$

# Answer
> 0 votes
$$T(n)=T(n-1)+n=\\\=T(n-2)+(n-1)+n=\\\=\cdots=\\ =T(1)+2+\cdots+(n-1)+n =\\\= T(1) + \frac{n(n+1)}{2}-1 \in \Theta(n^2)$$

# Answer
> 0 votes
c + n - 2cn is always negative for c , n \>1 so T(n) \< cn2

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Fast construction of a static KD-tree without duplicates
From what I know, the classic way of constructing a KD-tree is with alternating dimensions and finding median at each level. In my dataset, I have a lot of duplicated points, and I want to incorporate the duplicates' filtering inside the creating of the KD-tree. However, I am not sure how to proceed.

1. Obvious option: just delete duplicates before creation of the tree and then create the static tree. This is my backup option but I am looking for something smarter/faster.
2. If such preprocessing is done to filter duplicates, is it not a good idea to also pre-sort the arrays at every dimension instead of finding median? The complexity reported everywhere is $O(kNlogN)$, so I do not see it faster than classic $O(NlogN)$ when finding median. However, I have seen some people claiming that pre-sorting is faster. Is that true?
3. Maybe there is some other efficient way how to handle removal of duplicates directly while constructing a Kd-tree? Maybe with iterative insertion to a Kd-tree instead of classic building procedure? But then pre-processing should include not only deletion of the duplicate points but also some ordering of the remaining points that would keep the tree balanced.

Any advise is appreciated.

# Answer
You can use hashing to detect duplicates at insertion time.

Assume you have your elements in an array $A\[1,\dots,n\]$. When inserting $A\[i\]$, you can apply an hash function $f$ to $A\[i\]$.

* If there is no collision, you push the pair $(A\[i\], i)$ in your hash table $T$ at position $i$, i.e. $T\bigl\[f\bigl(A\[i\]\bigr)\bigr\]\leftarrow (A\[i\],i \\, )$ and this operation requires a time proportional to the time required by computing $f(A\[i\])$.
* If a collision happens, i.e. $T\bigl\[f\bigl(A\[i\]\bigr)\bigr\]\neq \emptyset$, you have to check if the elements hashed in that position are equal to $A\[i\]$ or not, and you can access it through their indices stored within the values. You can keep $T\bigl\[f\bigl(A\[i\]\bigr)\bigr\]$ sorted with respect to $i$ so that is will be easy to look for $A\[i\]$ with a binary search in $O\Bigl(\log \Bigl( \bigl|T\[f\bigl(A\[i\]\bigr)\]\bigr|\Bigr)\Bigr)$. If $A\[i\]$ is found then it is not inserted again, otherwise it is inserted in $T\[f\bigl(A\[i\]\bigr)\]$ in the right position (found through binary search).

The expected number of collisions of different elements depends on the chosen hash function and on the hash table's dimension. If the hash function is chosen in a good way so that the elements are distributed evenly among $T$, then the expected number of elements in a cell of $T$ is $\frac{\\#\text{different elements in A}}{|T|}$.
> 1 votes

---
Tags: data-structures, kd-tree
---


# Question
Title: Is there any formalization of GADTs implemented in OCaml?
There are papers that describe how generalized algebraic datatypes (GADTs) are encoded in core Haskell (System FC)\[1\]\[2\], but I could not find any documentation on how OCaml formalizes/implements/encodes GADTs and how does it compare to Haskell GADTs.

**Question**: How are GADTs formalized/implemented/encoded in the core language of OCaml and how do they compare to Haskell?

To be more precise: I want to understand GADTs as implemented from a compiler writer/theoretician point of view and *not* from a point of view of a programmer as described here \[3\]\[4\].

1. OUTSIDEIN(X) Modular type inference with local assumptions
2. System F with type equality coercions
3. OCaml Manual GADT tutorial
4. Real world OCaml GADT

# Answer
The first work that talks about formalizing seems to be:

1. Xi, Hongwei, Chiyan Chen, and Gang Chen. “Guarded Recursive Datatype Constructors.” In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 224–35. POPL ’03. New York, NY, USA: Association for Computing Machinery, 2003. https://doi.org/10.1145/604131.604150.

The implementation aspects seems to be based on this presentation from OCaml workshop

2. Jacques Garrigue, Jacques Le Normand. "Adding GADTs to OCaml: the direct approach." ACM SIGPLAN Workshop on ML 2011. https://www.math.nagoya-u.ac.jp/~garrigue/papers/ml2011.pdf

Also some work on mechanized formalization of GADTs

3. Jacques Garrigue, Xuanrui Qi. "Formalizing OCaml GADT typing in Coq." The ML 2021. https://www.math.nagoya-u.ac.jp/~garrigue/cocti/ml2021.pdf
> 1 votes

---
Tags: programming-languages, functional-programming, data-types, ocaml
---


# Question
Title: What are the best parameters possible from a binary linear LDPC code where each parity-check matrix is the incidence matrix of a graph?
There is an obvious construction of linear codes from graphs, where each codeword is a cycle in the graph. Physical bits are edges in the graph, and constraints are vertices.

This has been used in the construction of good LDPC codes with expander graphs by Sipser and Spielman \[1\], but their construction uses Tanner codes, where the local codes at each vertex are some other good code; it also uses an edge-vertex incidence graph as a Tanner graph, rather than using the incidence matrix of a graph directly.

If we restrict ourselves to just the incidence matrix of graphs, with bounded vertex degree, what is the best possible asymptotic encoding rate and distance we can achieve? I assume that this will also use expander graphs.

\[1\] M. Sipser and D. A. Spielman, "Expander codes," in IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1710-1722, Nov. 1996, doi: 10.1109/18.556667.

# Answer
I have been pointed towards a reference which answers this precisely: https://link.springer.com/chapter/10.1007/978-3-642-01877-0\_21. Here, it is claimed that the best I can hope for is constant rate and logarithmic distance - although the paper only proves this for regular graphs.
> 0 votes

---
Tags: graphs, error-correcting-codes
---


# Question
Title: Correct term for a priority queue with unique elements
Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element `x` to the new value `p`" would make sense.

In this kind of an abstract container, if you insert some element ("key", but not in the sense of "priority key") with some priority, you cannot insert it again until it is extracted, but you can update its priority.

I would also like to know if there is some established interface for this kind of a priority queues.

# Answer
Let me clarify first that by "unique elements" I meant elements unique by their identities, not by their "values." (In case of mutable objects, distinct mutable objects may at some moment have identical "values.") The identities of elements have to be maintained while the elements are being moving inside the priority queue implementation.

I've decided to go with *indexed priority queue*.

It turns out that a similar term is used in *Algorithms* textbook by Robert Sedgewick and Kevin Wayne: they call it *index priority queue*.

I've also checked out *Algorithm Design* by Jon Kleinberg et Éva Tardos and *Introduction to Algorithms* by Cormen et al, but they do not use any special term for this kind of a PQ, and just keep calling it a priority queue.
> 0 votes

# Answer
I don't know of a name for the abstract data structure.

There is a well-established implementation of what you describe, though: *treaps*, a combination of BST and heap (i.e. priority queue). This is with priority and value/key being different things, though.

If priority and value are the same, use any priority queue and add uniqueness, i.e. by combining it with a set/dictionary data structure. (Treaps degenerate to sorted lists in this case.)
> 3 votes

# Answer
Does `PriorityQueueSet` sounds good? A sample signature of Java implementation

/\**

* A priority queue that also maintains a set of unique entries.
*
* @param type of the key to identify the entry
* @param type of the entry
* keyExtractor is used to extract the key from the entry
* valueComparator is used to sort the entries in the queue
*

\*/

public class PriorityQueueSet\<K, V\> extends PriorityQueue
> 1 votes

---
Tags: data-structures, terminology, priority-queues
---


# Question
Title: Is it possible to go from code to circuit?
I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?

# Answer
Yes, it is certainly possible.

There are compilers that will compile from code to circuits. Classic examples would be VHDL or AHDL compilers, but you can certainly do this for any other language, to the extent that you have an upper bound on the running time of the program or that you have an upper bound on the memory use of the program and are willing to have a circuit that contains stateful elements.

In fact, you can walk down to Fry's and buy something that basically has the form you asked for: it's called a computer. That's more or less what a computer does: it takes code written in a programming language and executes it efficiently, using an optimized circuit. The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer). However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits. The mapping is implemented by a compiler.
> 11 votes

# Answer
there are different ways to interpret your question but based on comments (incl yours) some of this may be helpful. there is a lot of research in converting higher level programming constructs into FPGAs, field programmable gate arrays, basically hardware where circuits are dynamically reconfigurable. (aka reconfigurable computing).

there is also a special language eg "C for FPGAs", a subset of full C, that is customized for this purpose.

as for getting efficient circuits for particular programs, that is another area of research/ optimization eg circuit optimization/ minimization/ compression. there are also optimization heuristics built as input preprocessors into most SAT solvers. more generally this is known as logic optimization and there are various techniques/ tools for that. also the general theory/ application of optimizing compilers has some overlap with circuit optimization. one simple, near "toy" example or model of a compiler optimization in some cases is short circuit evaluation. the general area you refer to is also an active area of research both theoretical/ applied & there are many related papers on the subject.
> 2 votes

# Answer
FPGA code is just another kind of code, and it's convertible.
I guess if you're making a real machine, it could be written in C, but I'm doing one now and I'm just using **sub-procedures in place of the electric modules**, and it seems to be like it could work, and you can even do it on the GPU to get that awesome speed out of it.

The variables are the same between gates and code.
The variables just mark where the gates are linking and it perfectly converts (you just do them as normal), FPGA code is probably the same and does this I bet!

Just using the C code directly to make a circuit I'm not doing but its close if it works or not, but I'm talking about handcrafting the code to make it easily convertible works, and makes the conversion process less of a headache.

If you use a virtual machine to run it, it goes slower, it's best if it's direct code what you're running 'cause then you can get more out of your computer, when you're debugging what's going to be the final circuit.
> 0 votes

---
Tags: compilers, interpreters
---


# Question
Title: How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?
I have been trying to understand how the language $L = \\{a^m b^n c^p d^q \mid m\*n=p+q\\}$) is context-sensitive?

I first encountered this question here.

Would be grateful if you could provide some intuition for identifying class of such language.

Thank you!

# Answer
> 1 votes
I think the language is indeed context-sensitive. Here is a non-contracting grammar generating it.

> $S \to A' \mid B' \mid aS' \mid \varepsilon$
>
> $A' \to aA' \mid a$ (in the case there is no $b$'s, then the word is $a^m$)
>
> $B' \to bB' \mid b$ (in the case there is no $a$'s, then the word is $b^n$)
>
> $S' \to S'A \mid BS'X\mid BX$
>
> $BA\to ABX$
>
> $XA \to AX$
>
> $XB \to BX$
>
> $aA \to aa$
>
> $aB\to ab$
>
> $bB \to bb$
>
> $bX\to bc \mid bd$
>
> $cX \to cc \mid cd$
>
> $dX \to dd$

The idea is the following:

* First, we distinguish the cases of the empty word, a word with no $b$'s and a word with no $a$'s. These cases can be treated with simple rules.
* In the other cases, the word is $a^mb^nc^pd^q$ with $m\>0$, $n\>0$ and $p+q\>0$ :
    + we first generate a word like $aB^nA^{m-1}X^n$;
    + we switch the positions of $B$'s and $A$'s. Each time a swap is done, we create a letter $X$. Since there are $(m-1)\times n$ total swaps, there will be $m\times n$ letters $X$;
    + then, using the starting $a$, we replace all variables with terminals. If there is still a $B$ to the left of an $A$, then the $A$ will never be transformed into a terminal (this insures that the grammar cannot generate words that are not in the language). The idea is the same with $A$'s or $B$'s to the left of an $X$.

There may be some mistakes in the grammar, but I think the general idea works.

---
Tags: complexity-theory, formal-grammars, context-sensitive
---


# Question
Title: From these functions, how to determine which grows faster without graphing?
How are you intuitively able to tell the Big-Oh of the functions and what order they are on? $$f(n)=3^n$$ $$g(n)=5^{3log\_3{n}}$$ Note this is $5$ raised to $3log\_3n$ $$h(n)=1024^{log\_2n}$$

# Answer
> 1 votes
Intuitively, the idea is to look at things that may even appear to be gigantic but that may end up getting swamped as *n* grows.

As an example, consider which of $f(n) = 3^n$ and $g(n) = 1024^{\log\_2 n}$ may grow faster. 1024 seems a lot larger than 3, but the 3’s pile up at the rate of an entire tripling with each unit increment of $n$. By contrast, those admittedly sizable 1024’s are only showing up at the rate of $\log\_2 n$, so for instance, once the 1024 corresponding to $n = 256$ makes its appearance, we don’t see the next 1024 until $n = 512$, and during $g$’s wait for it, $f$ will have grown by a factor of $3^{256}$. And things only gets worse for $g$ because the wait time for each new 1024 will **double** forever. So although 3 may be dwarfed by 1024, once $n$ gets warmed up, the 3’s easily win because there are just so many more of them than there are of the ever-rarer 1024’s.

And of course, that intuition is backed up by the algebra:

> $1024^{\log\_2 n} = 2^{10\log\_2 n} = n^{10}$,

and $(n+1)^{10}$ exceeds $n^{10}$ by only something along the lines of $10 n^9$, whereas $3^{n+1}$ is a full three times as large as $3^n$.

# Answer
> 0 votes
The exponential of a logarithm is a power ($a^{b\log\_c n}=e^{b\log a\log n/\log c}=n^{b\log a/\log c}$), so the exponential "wins".

To decide between the last two, you cannot spare the comparison of the exponents.

> $$5^{3/\log 3}=125^{1/\log3}\<1024^{1/\log 2}.$$

---
Tags: complexity-theory, time-complexity, asymptotics, big-o-notation
---


# Question
Title: How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages
On page 7/8, section 1.2, of *Practical Foundations of Programming Languages, 2nd edition*, Robert Harper gives this initial definition of abstract binding trees:

The smallest family of sets closed under the conditions

1. If $x \in \mathcal{X}\_s$, then $x \in \mathcal{B}\[\mathcal{X}\]\_s$
2. For each operator $o$ of arity $(\vec{s\_1}.s\_1,\ldots,\vec{s\_n}.s\_n)s$, if $a\_1 \in \mathcal{B}\[\mathcal{X},\vec{x\_1}\]\_{s\_1},\\,\ldots,\\, a\_n \in \mathcal{B}\[\mathcal{X},\vec{x\_n}\]\_{s\_n}$, then $o(\vec{x\_1}.a\_1;\ldots;\vec{x\_n}.a\_n) \in \mathcal{B}\[\mathcal{X}\]$

(Here $\mathcal{X}$ denotes a set of variables, $\mathcal{X},x$ the union of $\mathcal{X}$ with $\\{x\\}$ where $x$ is fresh for $\mathcal{X}$, $\vec{x}$ a sequence of variables,$\mathcal{X}\_s$ a set of variables of sort $s$, $\mathcal{B}\[X\]\_s$ the set of abstract binding trees of sort $s$ over the variables in $\mathcal{X}$

> This definition is *almost* correct, but fails to properly account for renaming of bound variables. An abt of the form $\text{let}(a\_1;x.\text{let}(a\_2;x.a\_3))$ is ill-formed according to this defnition, because the first binding adds $x$ to $\mathcal{X}$, which implies that the second cannot also add $x$ to $\mathcal{X},x$, because it is not fresh for $\mathcal{X},x$.

I am confused about his meaning here.

How does this definition result in an ill-formed abt?

By first/second binding does he mean **A)** outer/inner (read from left to right) or **B)** inner/outer (read from the inside out)?

What I think he is saying:
Because of the outer("first") binding of $x$, assume that $x$ occurs free in $a\_2$. For example $a\_2=x,\\, a\_3=x$. Then because $x$ occurs free in $a\_2$, it must be that $a\_2 \in \mathcal{B}\[\mathcal{X}\]$ where $\mathcal{X} = \\{x\\}$. Since $a\_3$ occurs inside an abstractor that binds $x$, $a\_3 \in \mathcal{B}\[\mathcal{X,x}\]$, but then $a\_3 \in \mathcal{B}\[\\{x\\},x\]$ which is ill-formed since $x$ is not fresh for $\\{x\\}$

But then I think of the concrete example $\text{let}(y,x.\text{let}(z,x.x))$ in which $a\_2 \in \mathcal{B}\[\\{z\\}\]$ and $a\_3 \in \mathcal{B}\[\\{z\\},x\]$, which poses no problems in this interpretation.

### Edit to elaborate on the accepted answer...

What I now believe Harper meant is that the outer binding of $x$ indicates that $x$ is considered to be among the free, or "already used" variables in the inner let. This may or may not mean that $x$ must actually appear free in the inner let.

In either case, it means that validation of abts for well-formedness must proceed from the outside-in. In the specific examples Harper gives, the outer binding of $x$ means $x \in X$ in the validation of the inner let:
if $a\_2 \in \mathcal{B}\[\mathcal{X}\]$ and $a\_3 \in \mathcal{B}\[\mathcal{X},x\] \ldots$ (\<-- ill formed; $x$ is not fresh for $\mathcal{X}$)

If in particular the wording means that $x$ must specifically appear free in the inner let, then in the given example, it would have to be in $a\_2$ as suggested in my question and in the answer below. This amounts to saying that a particular instance of an abt in $\mathcal{X}$ is not automatically an abt in $\mathcal{X}\cup\mathcal{Y}$ for any set of variables $\mathcal{Y}$.

# Answer
Just to clear something up that may not have been obvious, $\chi$ is a set and the notation $B\[\chi, x\]$ is meant to be ABTs under free variables that are either $x$ or are in $\chi$. In this notation I believe it is implied that $x \notin \chi$ when you write $B\[\chi, x\]$, which is important.

Using the definition of ABT above, you cannot prove for any $\chi$ that let(z, x.x) is in $B\[\chi,x\]$, but i claim that this is necessary to prove if you want to use it as the inner formula $a\_1$ in let(y, x.$a\_1$).

The reason you cannot prove let(z, x.x) is in $B\[\chi,x\]$ is because using the rule#1 stated above, the free variable $x$ is only an ABT in $B\[\chi\]$ when $x \in \chi$ (or alternatively: $x$ is only an ABT in $B\[\chi',x\]$ for some $\chi'$), but then using rule#2, we deduce $z \in B\[\chi\] \wedge x \in B\[\chi, x\] \rightarrow let\[z,x.x\] \in B\[\chi\]$. As I had mentioned in the first paragraph, this implies $x \notin \chi$, which means that the formula let(z, x.x) is ONLY in ABTs where $x$ is not a free variable.

The reason why $x$ needs to be free in this inner formula is because otherwise we cant apply rule#2 again on the outer formula let(y, x.$a\_1$).
> 4 votes

# Answer
Another attempt at explaining why the first definition doesn't work, so assume that we are using that definition.

Let the only sort be $\mathsf{Exp}$, let $\mathcal{X}\_{\mathsf{Exp}} = \\{y,z\\}$, and let $x$ be a variable (of sort $\mathsf{Exp}$) that is fresh for $\mathcal{X}$. Then $y,z \in \mathcal{B}\[\mathcal{X}\]\_{\mathsf{Exp}}$ and $x \in \mathcal{B}\[\mathcal{X},x\]\_{\mathsf{Exp}}$, which implies that

$$ \mathtt{let}(y; x.\\!x) \in \mathcal{B}\[\mathcal{X}\]\_{\mathsf{Exp}}, $$

since $\mathtt{let}$ has (generalised) arity $(\mathsf{Exp}, \mathsf{Exp}.\\!\mathsf{Exp})\mathsf{Exp}$. In order to show (the false proposition) that

$$ \mathtt{let}(z; x.\\!\mathtt{let}(y; x.\\!x)) \in \mathcal{B}\[\mathcal{X}\]\_{\mathsf{Exp}}, $$

we would need $\mathtt{let}(y; x.\\!x)$ to not only be in $\mathcal{B}\[\mathcal{X}\]\_{\mathsf{Exp}}$, but also in $\mathcal{B}\[\mathcal{X,x}\]\_{\mathsf{Exp}}$. And *this* is what is impossible, since this requires $x$ to be fresh for $\mathcal{X},x$. (For ABTs with fresh renaming $\mathcal{X} \subseteq \mathcal{Y}$ implies $\mathcal{B}\[\mathcal{X}\] \subseteq \mathcal{B}\[\mathcal{Y}\]$, cf. Exercise 1.2, but this doesn't hold for ABTs *without* fresh renaming.)

---

Instead use the second definition of ABTs. Let $\rho(x) = x'$ be a fresh renaming of $x$ (relative to $\mathcal{X}$), and let $\rho'(x') = x''$ be a fresh renaming relative to $\mathcal{X},x$. Then $\hat{\rho}'(x') = \rho(x') = x'' \in \mathcal{B}\[\mathcal{X},x',x''\]\_{\mathsf{Exp}}$, so we have

$$ \mathtt{let}(y; x'\\!.\\!x') \in \mathcal{B}\[\mathcal{X},x'\]\_{\mathsf{Exp}}, $$

since $\rho'$ was an arbitrary fresh renaming of $x'$. Next we have

$$ \hat{\rho}(\mathtt{let}(y; x.\\!x)) = \mathtt{let}(y; x'\\!.\\!x') \in \mathcal{B}\[\mathcal{X},x'\]\_{\mathsf{Exp}}, $$

and since $\rho$ was an arbitrary fresh renaming of $x$, this implies that

$$ \mathtt{let}(z; x.\\!\mathtt{let}(y; x.\\!x)) \in \mathcal{B}\[\mathcal{X}\]\_{\mathsf{Exp}}. $$
> 0 votes

---
Tags: type-theory, variable-binding, syntax-trees
---


# Question
Title: Can we compute in polynomial time, an upper bound on an optimal solution of an integer linear program?
Consider the following integer linear program (where $A$ is an integer matrix, $b$ an integer vector, and $c$ a positive integer vector): $$ \text{minimize}~~~ c\cdot x \\ \text{subject to}~~~ A\cdot x \geq b, ~~~ x\geq 0, ~~~ x~\text{is an integer vector.} $$ Denote its optimal value by $OPT(A,b,c)$. Computing $OPT(A,b,c)$ is NP-hard in general. We are interested in computing an upper bound on $OPT(A,b,c)$, that is, a number $M = MAX(A,b,c)$ such that $OPT(A,b,c) \leq M$, and the size of $M$ (in bits) is polynomial in the size of $A,b,c$.

Is there an algorithm that, given $A,b,c$, computes such an upper bound $MAX(A,b,c)$ in time polynomial in the size of $A,b,c$?

# Answer
While The bound given by @SilvioM in comments has polynomial size in A,b,c as requested, one cannot expect a polynomial time approximation for ILPs (see the second paragraph), and hence, probably also not an an upperbound polynomial in OPT. So this is probably as good as it gets.

The reason for this is that the well-known formulation of TSP as ILP is clearly a reduction from TSP to ILP. Since the general TSP does not admit a constant factor approximation, even when all weights are inegers (try to find a gap-reduction from Hamiltonian Cycle as a homework), and since this reduction clearly preserves approximation (since any feasible solution of one of them is a feasible solution of the other having the same target value), this excludes a constant factor approximation unless P=NP.
> 0 votes

---
Tags: linear-programming, integer-programming, upper-bound
---


# Question
Title: How to prove {a^(n^2) | n>0} is not context-free?
So I have a language: $$ L = \\{a^{n^2} \mid n \> 0\\} $$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?

# Answer
> 4 votes
\[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.\]

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p\>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|\>0$ and $|vxy|=t\le p$. Hence, we'll have $$ 0 \< |vy|=t\le p $$ This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have $$ p^2\<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p $$ Choosing $i=2$ gives us $$ p^2\<|uv^2xy^2z|\le p^2+p $$ Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.

---

This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.

# Answer
> 1 votes
## If still have your question, I thought this might help why using pump up i=2 we can show the language is not Context Free.

Let $s=a^{p^2}$

next string is for (n+1) : $s=a^{(p+1)^2}$

$s=uvxyz$$; |vxy|\leq P$$;|vy|\geq1$

at most length $|vy|=p$ pump up i=2 so the pumped string $p^2+p$ which is not in the language because: $ (p+1)^2 $\>$ (p^2+p)$ so the language given is not context-free.

# Answer
> 0 votes
A unary language (a language over a unary alphabet) is context-free iff it is regular. Moreover, such a language is context-free (or regular) iff the set of lengths of words in the language is eventually periodic.

The set $\\{n^2 : n \in \mathbb{N}\\}$ is not eventually periodic: the gap between adjacent elements increases without bound. So the language $\\{a^{n^2} : n \in \mathbb{N}\\}$ isn't regular or context-free.

# Answer
> 0 votes
Assume that the language $L = \\{a^{(n^2)} | n \> 0\\}$ is context-free and let N be the pumping length given by the Pumping Lemma.

Choose the string $u = a^{(N^2)}$, which is in the language L. According to the Pumping Lemma, u can be decomposed into vwxyz such that |wxy| ≤ N, |wy| \> 0, and $vw^mxy^mz$ is in L for every $m ≥ 0$.

When you choose m = 2, you pump the substring wxy, which increases the length of the string.

The length of the pumped string $vw^2xy^2z$ becomes $(N + n)^2$, where $n \in \mathbb{N}$. Now we now that |wy| = j + k, |w| = j, and |y| = k.

Now we know that this must be true $(N + n)^2 = N^2 + j+ k$.

From this equation, you deduce that $j + k = 2Nn + n^2$, which is greater than N since n \> 0.

This contradicts the Pumping Lemma's requirement that |wxy| ≤ N.

Therefore, the assumption that L is context-free must be incorrect.Thus, you conclude that the language $L = \\{a^{(n^2)} | n \> 0\\}$ is not context-free.

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


# Question
Title: The complexity of checking for short cycles in a graph
In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199).

Next, as for determining the existence of long cycles, I don't hold much hope for efficient algorithms. However, what about short cycles? For instance, 3-cycles, 4-cycles, and so on. For a $k$-cycle, at what value of $k$ does the algorithmic complexity transition from polynomial time to non-polynomial time? Is there a clear boundary?

# Answer
The problem of finding a simple $k$-cycle is FPT, which means that there exists an algorithm running in time $O(f(k) \cdot n^{O(1)})$.

Alon, Yuster, Zwick (Color coding, JACM 1995) give an algorithm for exact $k$-cycle in expected time $O(k! \log k \cdot n^\omega)$.

They also give an algorithm with worst case time $2^{O(k)} nm$ or $2^{O(k)} n^\omega$.

Fomin, Lokshtanov, Panolan, and Saurabh (JACM 2016) give a $O(2.619^k n^{O(1)})$ for finding a $k$-cycle.

As you can see, when $k$ approaches $n$, this looks more and more like an $c^n$ algorithm.

The best known randomized algorithm for detecting hamiltonicity is $O(1.657^n)$ by Björklund (SIAM J Computing, 2014), and to the best of my knowledge, the best algorithm for deterministic Hamiltonian Cycle is the $O(2^n n^2)$ algorithm by Bellman.
> 5 votes

# Answer
If your graph has $n$ vertices and you’re interested in $k$-cycles, then a brute-force inspection will look at each of the $n \choose k$ possible $k$-tuples. Thus, assuming that $k$ is small—in other words, that $k = O(1)$—that approach is $\Theta(n^k)$.
> 5 votes

---
Tags: graphs, time-complexity
---


title: Clique and verteces degree

text:
# Question
Title: Clique and verteces degree
We have a graph $G$ with $v$ vertices. In $G$ there is at least a maximum clique with $k$ vertices, with $k\lt v$. Is it true that there is at least a vertex of $G$ such that its degree is less than $k-1$?

# Answer
> 2 votes
The question is not clear. Is this the claim you are considering:

If the largest clique in a graph $G=\langle V,E\rangle$ is of size $k\<|V|$, then there exists a vertex $v\in V$ of degree $d\leq k-1$.

If so then the claim is wrong. Let $d\geq 2$ and consider the full bipartite graph $K\_{d,d}=\langle V,E\rangle$, where $V=L\cup R$ is a disjoint union of two sets of size $d$, and $E=\\{ \\{u,v\\} : u\in R, v\in L\\}$. Clearly, $K\_{d,d}$ is $d$-regular, and the largest clique in it is of size $k=2\leq d$.

---
Tags: graphs
---


# Question
Title: Matching the segments of a set to longer segments of another set
Consider a set $S$ of segments in the plane. Split each segment in $S$ into a few pieces, and slightly modify the extremities of each obtained segment (by adding a small random value to their coordinates, e.g.). Then consider the set of all obtained segments and add to this set a number of random segments. This gives a new (larger) set $S'$ of segments.

Given $S$ and $S'$, how to find the segments in $S'$ that (most probably) come from the pieces of segments in $S$? and how to find the segment in $S$ from which they were (most probably) obtained?

# Answer
> 1 votes
Here is a simple approach:

1. Let $E$ denote all the endpoints of $S$.
2. Find all segments in $S'$ that have an endpoint near a point of $E$.
3. For each such segment $s' \in S'$ with an endpoint near $e \in E$, test whether $s'$ is close to a portion of some segment in $S$. If it is, output it, remove $e$ from $E$, and add the other endpoint of $s'$ to $E$.
4. Go to step 2.

Step 2 can be implemented efficiently using a nearest-neighbor data structure. Step 3 can be implemented efficiently as well: associate each endpoint $e \in E$ to its corresponding segment $s \in S$; then given $e$, you can find the other endpoint of $s'$, call it $f$, and test whether $f$ is close to the line $s$.

# Answer
> 0 votes
Take all "new" segments in turn and compute a distance to the initial segments. Associate a new segment to the closest "old".

For the distance you might consider the average distance of every point of a segment to another, or to the line of support of the other.

# Answer
> 0 votes
One possible approach which will both solve the problem of detecting random segments from $S^{\prime}$ and associate original and modified segments is that of doing a nearest neighbor search of original segments in $S$ inside the new segments in $S^{\prime}$. In this way, you find for each original segment the closest one inside $S^{\prime}$ and the elements of $S^{\prime}$ which are not associated to any original segment at the end of the procedure are the random ones. You may exploit something like sweep line algorithm or kd-trees in some way to enhance the search and avoid a simple naive search.

For doing that you need to define a metric on segments, e.g. the average of the distances between left-most extremes and right-most extremes (i.e. you compare the two extremes with the smallest $x$ coordinate and the two with the biggest $x$ coordinate).

Keep in mind that this solution may give you totally wrong results. Indeed, it is impossible to associate modified segments to original ones without additional information on random modifications' distribution and magnitude, random segments' distribution and original segments' distributions.

---
Tags: algorithms, graphs, computational-geometry
---


title: Showing NP-Completeness

text:
# Question
Title: Showing NP-Completeness
I just newly started looking into computational complexity.

Since we don’t know if P = NP, we would like to have a way of saying “This problem is in NP and is really hard unless P = NP.”

This is made more formal by the notion of NP-completeness.

Therefore, we say a problem A is NP-complete if

(a) it is in NP, and (b) every problem B in NP is polynomial-time reducible to A.

Using a graph $G$ and an edge $e$ in $G$ as an example, how do I determine whether or not there is a Hamiltonian cycle that includes $e$?

With this, I could show that the problem is NP-complete and use the same approach for similar problems.

# Answer
> 1 votes
There is no known efficient way to determine whether or not there is a Hamiltonian cycle that includes $e$. That is a NP-complete problem. (If you could determine that, you could use that as a subroutine to test whether the graph contains any Hamiltonian cycle, and even to find a Hamiltonian cycle if one exists; so it's not reasonable to expect there to be an efficient algorithm to do that.)

# Answer
> 0 votes
A problem is in NP if every instance with the answer “yes” can be solved in polynomial time if you get a clever hint.

A problem X is NP complete if it is in NP (and not harder), and some NP-complete problem can be solved by solving X. That means if I take an instance Y of this other NP-complete problem then I can construct a problem X so a solution of X allows me to solve Y. That doesn’t require that X is easy to solve.

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


title: Assosciative mapping algorithm

text:
# Question
Title: Assosciative mapping algorithm
I have been studying the assosciative mapping in a cache.Every line in a cache has a unique address which is made of:the index and the offset bits which give the the cache set and the cache line and the tag bits.But which algorithm really decides where to put information from RAM into the cache?

# Answer
> 1 votes
## Preliminaries

In the case of a fully-associative or set-associative cache, there are multiple places where a cache line could be placed, which usually involves evicting an existing cache line.

From the classic paper *Design of CPU Cache Memories* by Alan Jay Smith, the mean memory access time is

$$T = m \times T\_m + T\_h + E$$

where $m$ is the miss ratio, $T\_m$ is the time to satisfy a cache miss, $T\_h$ is the time to satisfy a cache hit, and $E$ is the overhead of everything else in the system.

This is the number that you would typically try to optimise for.

The only numbers that the cache replacement policy have any control over are $m$ and $T\_m$. It can affect the miss ratio, but it can also affect the time to satisfy a cache miss, because some evictions are more expensive than others.

Fair warning, there is a *huge* design space to be explored here, and different algorithms tend to work better on different workloads. Although, as a general rule, pretty much any cache-replacement policy will work as well as any other when the working set is smaller than the cache size.

A CPU has access to quite a lot of information beyond "what is currently sitting in the cache", so let's take a look at some questions you can ask.

**Is there a store pending?**

On modern CPUs, stores are often buffered to reduce latency, and support speculative execution. This is especially useful if sequential consistency is not needed. For example, an extremely common case is issuing multiple stores to adjacent locations in the same cache line. These can be buffered until the cache line has been read, an optimisation known as write-combining.

If there is a pending store to a cache line, it would probably be a bad idea to evict that particular one.

**Does it need to be flushed?**

If a cache line is dirty, then it needs to be flushed to somewhere. This would typically be to RAM or a lower-level cache, but in a multiprocessing system, it's sometimes to another CPU's cache.

If the cache line is clean, then (to a first approximation) it just needs to be forgotten. This is much cheaper, so it may be worth prioritising clean cache lines.

**Was it used recently?**

Part of the theory behind why cache works in the first place is that the working set of a program, at any particular point in time, is smaller than the program's size. Therefore, the less recently a cache line has been used, the less likely it is to be needed soon.

**Is there a detectable access pattern?**

Modern CPUs, in particular, often have hardware to detect one specific case: scanning through an area of (virtual!) memory sequentially. Iterating through arrays, copying blocks of memory, etc are such common operations that this is almost always worth doing.

There are some optimisations a CPU can do when it detects this:

* *Prefetch* the next likely cache line in the sequential scan, even before it's been requested.
* Mark or record the previously used cache line in the scan as the most likely candidate for eviction. So, for example, the CPU might eagerly write-through such a cache line, even if this is not normally a write-through cache.

## Some example policies

With all that in mind, here are some specific policies. Bear in mind that all of the practical ones could be supplemented with some of the special-case optimisations mentioned above.

**Bélády's algorithm**

The optimal algortihm is Bélády's algorithm, also known as the clairvoyant algorithm. You simply evict the cache line that will not be needed for the longest time in the future.

This algorithm has the disadvantage that it's impossible to implement because it is not an *online* algorithm: it cannot use only information from the past and the present. But it's a useful theoretical tool for comparing other algorithms. No algorithm can do better than this, so an algorithm which gets close is, by definition, pretty good.

While we're on the topic, it would also be useful to know the worst-case, and turns out that, in the absence of information about the future, there is no deterministic online "worst" cache replacement algorithm, either. There are, however, some good (if that is the right word) approximations. For more on this, see Agrawal et al, *The Worst Page-Replacement Policy*.

**Least recently used**

The idea behind LRU is that you keep track of when a cache line is used, and if a cache line needs to be evicted, you evict the one that was used least recently. This need not be expensive; you could use a counter or a queue where an access moves that cache line to the front of the queue, and items are evicted off the back of the queue.

This seems like a good algorithm, but it has one very large drawback.

If the working set is smaller than or equal to the cache size, this algorithm performs extremely well. But for the case where the working set size is only just larger than the cache size, this algorithm can perform worst of all.

Consider a simple case of a program that accesses addresses 1, 2, 3, 4, and 5 in order, over and over again, and further suppose that the cache will only fit four addresses. We start by loading 1, 2, 3, then 4. When it comes time to access 5, an LRU replacement policy will eject 1, since it was least recently used. This is, however, also the *next* address that will be needed. And then, when it comes time to access 1 again, 2 will be evicted, since it was least recently used, which also happens to be the next address that will be needed.

So in this case, even though almost all of the working set will fit in cache, LRU has a cache miss rate of close to 100%.

A better algorithm in this scenario would be...

**Random Replacement**

Just pick one at random. Well, pseudo-random, but you get the idea. On average, this algorithm works *extremely* well considering how simple it is, and many CPUs (e.g. ARM) use it. It also has the advantage that no history information is needed.

**Not Recently Used**

This is kind of the converse of LRU. Essentially, you record which cache line was most recently used, and eject some other one. If you choose the other at random, this is known as Not Recently Used, or if you approximate a LRU cache somehow, it might be Pseudo-LRU.

NRU policies are very popular for implementing page replacement in operating systems and databases. You can think of the BSD two-handed clock algorithm as a kind of NRU policy, for example.

**Bélády approximations**

One broad set of approaches is based on the idea of using the same techniques used to speculate branches, to also speculate future cache needs. The theory here is that some *instructions* are more likely to generate cache-friendly accesses than others, so by using history and program counter information, we might be able to use information about the past to predict the future.

Some example algorithms that use this include Hawkeye, Harmony, and Mockingjay.

**Re-Reference Interval Prediction**

RRIP is a flexible family of policies proposed by Intel in 2010. It uses an integer (called the re-reference prediction value, or RRPV) associated with each cache line, which correlates with when the cache line is expected to be reused. When a cache line is needed, the one with the highest RRPV is evicted.

There is a large design space here, here is one example:

* When a cache line is loaded, its RRPV is set to the maximum value.
* When a cache line is reused, its RRPV is set to zero.
* When a cache line needs to be evicted, any cache line with the maximum RRPV is evicted. If none of them have the maximum value, then *all* RRPVs in the set are incremented until one does.

This policy performs extremely well when "scanning" (i.e. accessing a lot of memory consecutively, as with a memory copy), because it evicts cache lines that are used only once, while also allowing reused cache lines to stay in cache. However, it can cause thrashing if the working set is larger than cache, because it essentially degenerates to "most recently used".

An enhancement is to randomly set the RRPV of newly-loaded cache lines either to the maximum value or the maximum value minus one. This gives some cache lines a random chance to "stick" in cache.

**Set dueling**

Given that no single policy will probably work best for all computing scenarios, it can sometimes pay to try more than one.

In a multi-way set-associative cache, you could assign some of the sets to one policy and some the sets to a different policy, along with a counter that monitors which policy is doing better at the moment, and adjusting the number of sets which use which policy accordingly. This is known as set dueling.

---
Tags: computer-architecture, cache
---


title: (Zero-knowledge?) Proof of Connection

text:
# Question
Title: (Zero-knowledge?) Proof of Connection
I have a conundrum to solve but am not knowledgeable enough about cryptography to know whether it's possible to do, and if so, what method to use.

I am a Provider and my task is to prove to some outside Verifier the existence of a Connection to some device, beyond some reasonable probability $\epsilon$. The Verifier and the Prover have a communication channel and can ask each other questions. As a Prover, I could lie at any point, and pretend the Connection exists when it doesn't, or vice versa. I need a protocol that is secure in such a way that the Verifier can establish the Connection is genuinely there.

**Question 1**: Is there any such protocol that could do with with communication and computation on the Prover side alone?

**Question 2**: In case the former isn't possible, if the Device could do some computation (i.e. do (modular) arithmetic etc.) and the Connection could be used for that, would that make this possible?

I feel there are some cryptographic algorithms out there that are designed for this, but I don't quite know what they are. I have looked into Zero-Knowledge proofs, but all the examples I find aren't quite suitable to this kind of issue.

# Answer
> 1 votes
The Verifier must encrypt a message using the public encryption key of the device and ask the Prover to decrypt it. (Nobody knowing the private key.)

---
Tags: cryptography, authentication, zero-knowledge-proofs
---


# Question
Title: How do I prove the following invariant of this program?
I have been studying different topics within the realm of concurrent programming and came across "Lamport's bakery algorithm" which is based on the original version of the bakery algorithm by Peterson. While studying I came across a paper showcasing the following program:

with a question for the reader reading "**Show that `(p_3 v p_5) <==> n[0] > 0` is an invariant of the program. Show that it holds initially and that it is preserved under every transition of process p.**"

I have been trying to do this for a while but can't seem to come up with anything robust and convincing. I don't know how to go about showing this.

Here are my thoughts. One thing that is clear but not necessarily useful (might be, I don't know) is that both `n[0] > 0` and `n[1] > 0` hold initially. As `n[1] >= 0`, the assignment `n[0] = n[1] + 1 > 0` and it also sets `n[1] > 0`. Then there are two cases, say **p** manages to perform it's assignment first then it'll have the lower ticket number (`n[0] = 1` while `n[1]` becomes `2`) and as such higher priority and will enter it's critical section before **q**. Then **p** will perform `n[0] = 0`. Now the relevant conditions for **q** to enter it's critical section will hold and it'll enter. And the loop goes like that.

# Answer
Showing that $\forall p\in\mathcal{P}.(pc\_p=pc3 \lor pc\_p=pc5 \iff n\_p\gt0)$ requires some labour. While your intuition is correct, formally proving this fact requires a rigorous strategy.

***Preliminaries***

Let me put down some notation, so we can discuss unambiguosly. I assume the program implements a transition system having several states, that can be either initial or intermediate. Let $Q$ be a set of states, and let $I$ be a subset of $Q$, of initial states. By $s\_0$ and $s\_1$ we denote some state in $Q$. By $\rightarrow(\cdot,\cdot)$ we denote the transition step starting from $s\_0$ leading to $s\_1$. It is clear that the transition is instantaneous, atomic and is responsible for modifying the variables of the transition system. By $pc\_p$ we denote the value of the program counter for process $p$. By $s\_0.v$ we denote some variable $v$ associated to state $s\_0$.

***Discussion***

I would tackle the problem stating what an invariant is, from a formal perspective and then structure the proof. I would use a proof by induction, that is, I want to show the property holds in all initial states or intermediate states an no matter what the transition does, the property is preserved.

First things first, $P$ is an invariant property when it hold in all reachable states of the model. In this case the transition system that the program implements, let's call it $M$.

$Def:$ Property $P$ is an invariant of $M$.

$Invariant(M, P) := \forall s\_1\in Q(M) . reachable(s\_1) \Rightarrow P(s\_1)$

Then we define reachability; a state is reachable in case it is an initial state or there exists a reachable state that leads to it via some transition. Formally:

$Def:$ State $s\_1$ is reachable in $M$.

$Reachable(M, s\_1) := s\_1\in I(M) \lor (\exists s\_0\in Q(M):Reachable(s\_0)\land s\_0\rightarrow s\_1)$

Let's name the property $\phi := \forall p\in\mathcal{P}.(pc\_p=pc3 \lor pc\_p=pc5 \iff n\_p\gt0)$, it will be useful in a moment. We want to prove that $Invariant(M, \phi)$.

Before we start, I want to remark that to my understanding the property Lamport asks to prove involves a single process and not two. So the part of your sketch where you consider the behaviour of $q$ seems to be superfluous.

***Proof Sketch***

Now we can sketch the proof by induction. Let $$Invariant(M, \phi)$$ Then expanding the definition of invariant we get: $$\forall s\_1\in Q(M) . reachable(s\_1) \Rightarrow \phi(s\_1)$$

Here we need to employ an inductive schema allowing to structure the inductive hypothesis over reachability; we get: $$\forall s\_1\in Q(M) . s\_1\in I(M) \lor (\exists s\_0\in Q(M):Reachable(s\_0)\land \phi(s\_0)\land s\_0\rightarrow s\_1) \Rightarrow \phi(s\_1)$$

Consider some generic state $s\_1$, either it is initial or there exists some $s\_0$ leading there. Let's split the proof into two cases:

1. Let $s\_1$ be initial, then we need to prove that $s\_1\in I(M) \Rightarrow \phi(s\_1)$.
2. Let $s\_1$ be an intermediate state, then we need to prove that $\exists s\_0\in Q(M):Reachable(s\_0)\land \phi(s\_0) \land s\_0\rightarrow s\_1 \Rightarrow \phi(s\_1)$.

Let's start with the basis, case 1.: $s\_1\in I(M) \Rightarrow (s\_1.pc\_p=pc3 \lor s\_1.pc\_p=pc5 \iff s\_1.n\_p\gt0)$.

We have two cases:

1.1 $s\_1\in I(M) \Rightarrow (s\_1.pc\_p=pc3 \lor s\_1.pc\_p=pc5 \underline{\Rightarrow} s\_1.n\_p\gt0)$

1.2 $s\_1\in I(M) \Rightarrow (s\_1.pc\_p=pc3 \lor s\_1.pc\_p=pc5 \underline{\Leftarrow} s\_1.n\_p\gt0)$

$\phi$ is trivially satisfied by all initial states because in the initial state all processes still need to take a step, that is, none of them has $pc\_p=pc3$ or $pc\_p=pc4$, vacuously satisfying the implication of case 1.1. Conversely, initially, all processes have their $n\_p=0$, vacuously satisfying the premise of the implication in case 1.2.

Q.E.D., branch 1. is done.

Let's now focus on the inductive step, case 2., this is where the real work lies. We need to prove that: $$\exists s\_0\in Q(M):Reachable(s\_0)\land \phi(s\_0)\land s\_0\rightarrow s\_1 \Rightarrow \phi(s\_1)$$ To do so observe that $s\_0$ is a generic intermediate state that is known to be reachable, to satisfy the invariant property and to be linked to $s\_1$ via a transition step. We can consequently rewrite the goal as: $$Reachable(s\_0)\land \phi(s\_0) \land s\_0\rightarrow s\_1 \Rightarrow \phi(s\_1)$$ and consequently: $$Reachable(s\_0)\land (s\_0.pc\_p=pc3 \lor s\_0.pc\_p=pc5 \iff s\_0.n\_p\gt0) \land s\_0\rightarrow s\_1 \Rightarrow (s\_1.pc\_p=pc3 \lor s\_1.pc\_p=pc5 \iff s\_1.n\_p\gt0)$$

Here we are forced to analyse all possible transitions, and observe the property is preserved. This means you will have as many cases as there are transition steps: I will not carry out the whole process here for you because it is amenable to computer automation. So Case 2, is left to be proven. I will, however, provide an intuition regarding how to do so more efficiently: we need to observe that all states trivially satisfying the premise of the innermost implication (let it be $\Rightarrow$ or $\Leftarrow$) are not interesting, like we did in the analysis of the basis. Therefore, we can safely discard all transitions where $s\_1.pc\_p\neq3\lor s\_1.pc\_p\neq5$. As well as, all states where $s\_1.n\_p=0$.

You can do this because a step taken by the transition system must be consistent, that is, it honours program order. You can not jump from line 1 to line 4, the only possible step from line 1 leads to line 2.

Before we continue, we state a lemma that you have observed independently: $$\forall p\in\mathcal{P}.pc\_p=pc\_3 \Rightarrow n\_p\>0$$ and a second one: $$\forall p\in\mathcal{P}.pc\_p=pc\_1 \Rightarrow n\_p=0$$ The proof for these is totally analogous to the one I am developing, so I am not proving them. These may come in handy during the rest of your proof.

For the remaining cases, namely, those not trivially satisfying the conclusion, you need to employ the inductive hypothesis ($\phi(s\_0)$) or the transition step itself. In general when the inductive hypothesis does not hold, the transition step is responsible for enforcing the property.

This strategy will work for most invariant properties of concurrent software, especially safety properties that do not require infinite loops to be shown to hold.

I hope this explanation helps.
> 0 votes

# Answer
$$p\_3\lor p\_4\lor p\_5\implies n\[0\]\>0$$ is immediate from the invariant: $n\[0\]$ is always non-negative and only modified by the process $p$.

So $n\[0\]$ remains strictly positive from $p\_3$ to $p\_5$ inclusive as a postcondition of $p\_2$.

The reciprocal

$$n\[0\]\>0\implies p\_3\lor p\_4\lor p\_5$$ is true because at initialization, $n\[0\]=0$ and as a postcondition of $p\_5$, we also have $n\[0\]=0$ so that this always holds at $p\_1$ and $p\_2$.

---

For completeness: it is easy to see that the $n$'s are either nullified or incremented, so they remain non-negative. This is another (trivial) invariant.
> 0 votes

---
Tags: algorithms, logic, proof-techniques, parallel-computing, concurrency
---


# Question
Title: Uses of Hex and Octal numbers in programming
Where are these number patterns, Octal and Hex, being used? I read this but I want to know where they are used in programming.

# Answer
> 1 votes
The octal and hexadecimal bases are not useful by themselves but are needed as a compact and readable representation of binary numbers. For instance, writing $\text{AB00CDFF}$ is more convenient and less error prone than $10101011000000001100110111111111$.

So the question moves to the usefulness of binary numbers: these enter into play when the internal representation of numbers on computers makes a difference. For instance when using bitwise operations (collective boolean operations on bits) or bit field packing (storing several binary numbers in the same data). Or when data alignment matters (i.e. addresses multiple of some power of $2$)...

# Answer
> 0 votes
I used a lot of HEX values when creating emulators too. There's a really good video of someone creating a N64 emulator using C++, and using HEX values makes it sooo much easier when playing with memory addresses.

Javidx9 on YouTube does it, and I followed along with him a bit when making my own smaller CHIP8 emulator. It's real great stuff, and even doable in Python (to an extent, but it's easier in C++). https://www.youtube.com/watch?v=F8kx56OZQhg

---
Tags: number-formats, numeral-representations
---


# Question
Title: finding wrong elements in a descending sorted array using binary search
i have this question where im given a an array that contains the distance of a traveler from a certain destination at the i-th time of the day. ideally the array should be in descending order but the array could contain mistakes where the traveler gets further from the destenation and i should find at which index does that mistake happen using binary search. heres the code i wrote:

```
int find_mistake(int dist[] , int n){
    int l = 0 , r = n-1 , mid;
    while(l<=r){
        mid = (l+r)/2;
        if (dist[mid] > dist[mid - 1]){
            return mid;
        }
        else if (dist[mid] > dist[l]){
            r = mid ;
        }
        else{
            l = mid ;
        }

    }
    return -1;

```

i would be glad if someone pointed mistakes in it as ive seen other solution and im not sure about mine.

# Answer
> 1 votes
You can't solve this by binary search !

That's because even if you know the values at the endpoints of an interval containing the inversion, looking at the central value doesn't hint you in which half the inversion is. In the worst case, you can't spare an $O(n)$ search.

# Answer
> 0 votes
Let’s say you have one hundred data points. They should be in ascending order, but one of them has been modified.

If you look at all but two data points, and you didn’t look at the wrong one, then you have no idea which of the two was incorrect. It could be either.

Even if you looked at all data points except one: Say you have five points with values 1000, 1100, unknown, 1300, 1400. The “unknown” one could be 1350, and you wouldn’t know if that is the wrong value or the next one at 1300.

---
Tags: c
---


title: Are recursive Horn clauses first order?

text:
# Question
Title: Are recursive Horn clauses first order?
My understanding is that recursive definitions are considered second-order since they require the fixpoint operator in order to be formulated as "true" definitions. This is even though they contain no higher order quantifiers eg.

```
times(x,s(y)) = plus(x,times(x,y))
times(x,0) = 0

```

needs to be written as `times = \mu x. F(x)` for some F, and the fixpoint operator is second order. I believe the same is true for recursive Horn clauses. But then why is a Prolog program considered first order, since it typically contains many recursive rules?

# Answer
Horn clauses in prolog are *not* recursive definitions. They are *logical formulas*. For example,

```
times(_, 0, 0).
times(x, S(y), w) :- times(x,y,z), plus(x,z,w).

```

is *not* the definition of a recursive function, but just two logical formulas, written fully as \begin{gather\*} \forall x .\\, \mathtt{times}(x, 0, 0), \\ \forall x, y, w, z .\\, \mathtt{times}(x,y,z) \land \mathtt{plus}(x,z,w) \Rightarrow \mathtt{times}(x,S(y),w). \end{gather\*} Here $\mathtt{times}$ and $\mathtt{plus}$ are ternary relation symbols, $0$ is a constant, and $\mathtt{S}$ is a unary function symbol.

It is the case that the above formulas tell prolog how to search for solution to queries using a strategy (depth-first search) that resembles computation of functions given by recursive definitions, but the formulas themselves are just first-order logic statement.

As for the necessity of using the fixpoint $\mu$ operator for recursive definitions, there is no such necessity. We can directly define first-order functions using a schema that allows self reference. Such a schema *may* be translated to an application of $\mu$, but it does not have to be. One can explain it directly. For instance, primitive recursive functions are defined such a schema, without any fixed point operator.
> 4 votes

---
Tags: logic, recursion, prolog
---


# Question
Title: Asymptotic equivalence allows difference by a constant factor?
Wikipedia and other sources define "asymptotically equivalent" as: two functions $f$ and $g$ are asymptotically equivalent if:

$$ \lim\limits\_{x \to\infty}\frac{f(x)}{g(x)}=1 $$

But we regard $n^2$ and $2n^2$ as asymptotically equivalent, and these always have a ratio of 2 between them. Is there a different definition of "asymptotically equivalent" that I should be using?

This MIT Problem Session from 2020 illustrates calling $n^3$ and $\binom{n}{3}=\frac{n(n-1)(n-2)}{6}$ asymptotically equivalent. If you back up a bit from the time where the link starts, you'll see (actually, hear) the algebra spelled out.

# Answer
There are multiple notions/definitions of asymptotic. You need to pick one that is appropriate for your goals.

One approach to asymptotics is exactly as you have stated (see, e.g., https://en.wikipedia.org/wiki/Asymptotic\_analysis). This notion cares about constant factors. It is commonly used in mathematics. Standard notation is $f(x) \sim g(x)$.

Another approach to asymptotics ignores constant factors. This is standard in computer science. In particular, we write $f(x) = \Theta(g(x))$ for two functions that behave the same asymptotically, in this sense. See https://en.wikipedia.org/wiki/Big\_O\_notation.

Which one to use depends on what you care about. In computer science, we often care about analyzing the running time of algorithms, in a theoretical model where we ignore constant factors... hence we typically use the second notion.

I have only ever heard the phrase "asymptotically equivalent" used for the first kind of use of asymptotics, but I don't know whether that is an accepted terminology or just my personal experience.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Having trouble on logic behind recursion
I am struggling to write my own recursive function.I understand how to find the base case but I cant find easily the pattern on the relationship between 2 complicated cases.Do you know any website where I can practice that?

# Answer
The philosophy behind recursion is to decompose the problem in subproblem(s) *of the same nature* but easier in some respect, until the subproblems are so simple that you can solve them easily.

For instance, to sort an array, you can move the small elements on the first side and the large ones on the last side and sort the two sides separately. You trade a large problem for two easier ones (because the number of elements are smaller). When this number is tiny, you can sort by a straightforward method (in particular, sorting a single element is immediate).

The whole story is about reducing the problem to similar subproblems.
> 2 votes

# Answer
Well, the old adage ain't wrong: To understand recursion, you first need to understand recursion.

There are probably many books and webpages only a single search away.

I would recommend you try to do very simple recursive functions first and then gradually solve harder and harder problems. Make sure that you **understand why it works** each time you have solved a problem.

Things to practice: `factorial`, `fibonacci`, `linear search through a list`, `sum of elements in list`, `is_even(int)`, `map a function over a list`, `filter a list`, and then try even harder like `binary search` and `quicksort`. Once these are done, you can try first `hamming distance` and then `levenshtein distance`.
> 1 votes

# Answer
An important thing to remember about recursion is that it is just another programming tool. Like all tools, it works well for what it is intended for, but is a terrible choice when used inappropriately. My suggestion is to study the types of problems where the use of recursion makes a natural solution. In my field (embedded systems), I have found recursion to be useful just a few times over the last 40 years. I am sure it comes in more useful in other fields, but again, just remember it is only one of many tools you will need in the software engineering field.
> 1 votes

---
Tags: recursion
---


title: Dominating sets and treewidth

text:
# Question
Title: Dominating sets and treewidth
As input we are given a graph $G$ and an integer $k$ and are asked to find a dominating set of size **exactly** $k$ in $G$. This problem is clearly NP-hard, but does it become polynomial time solvable if we assume $G$ has bounded treewidth? For bounded treewidth graphs you can find a dominating set of size at most $k$ by dynamic programming, but does the problem become hard if you ask for a set of size exactly $k$?

# Answer
Every graph with a DS of size $\leq k$ has a DS of size exactly $k$ (assuming $k$ is bounded by the number of vertices) as every superset of a DS is itself a DS.
> 0 votes

---
Tags: algorithms, graphs, parameterized-complexity
---