# Question
Title: Expected number of vertices with degree 2
A simple graph with $n$ vertices is constructed by randomly and independently placing an edge between every two vertices with probability $p$. What is the expected number of nodes with degree two?

---

I was only able to find the probability of any vertex having degree 2. Let me explain what I tried. For any vertex we can have n-1 edges connecting it(since its a simple graph), so for it to have degree = 2, two of these n-1 edges should be there, and rest not.

This gives: $\binom{n−2}{2}p^2(1−p)^{n−3}$.

# Answer
> 1 votes
Hint:

> Indicator random variables.

If that's not enough and you need a second hint:

> Use linearity of expectation.

---
Tags: graphs, probability-theory
---


# Question
Title: Are there practical methods for solving ILP?
Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ILP easy and fast in practice? Is this solution exact or approximate?

# Answer
> 8 votes
Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot. Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can find an approximate solution as well (find the best solution they can within the time constraints). There are no hard-and-fast rules.

Of course, ILP is NP-hard, so you should not expect any ILP solver to be able to efficiently solve all ILP instances. Rather, what seems to happen in practice is that some instances can be solved in a reasonable amount of time, but others appear to be very hard. However, ILP solvers incorporate many sophisticated techniques for speeding up the solver, and these are sometimes effective. There's no good way to know for sure in advance whether your specific instance will be solvable efficiently or not, but to try it.

Why is it useful to reduce some other problem to ILP? That's not always useful or interesting... but in some cases it is. For example, it lets you take advantage of the sophisticated methods already implemented in ILP solvers, without having to re-invent them in the context of your other problem.

---
Tags: optimization, heuristics, integer-programming
---


# Question
Title: First Order Logic, First Order Logic + Recurrence and SQL
we know that SQL standard is equivalent to First Order Logic (FOL). I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve that problem in PTIME. And I've seem the following table:

```
Query Language   Data Comp.   Expression Comp.
FOL              LOGSPACE     PSPACE
FP               PTIME        EXPTIME

```

I am not sure what is `FP`. But, I suppose that it is `FIXPOINT`. I mean, a first order logic with recursion + fixpoint.

I don't understand that table. I understand the Data Comp. But, I cannot what Expression Comp. means and why `Expression Comp.` for `FP` requires so much time.

# Answer
> 1 votes
Yes, FP will be first-order fixed-point logic.

Data complexity is the maximum complexity of the problem of evaluating a fixed formula of the logic on a database, as a function of the size of the database. Expression complexity (also known as formula complexity) is the complexity of evaluating a formula on a fixed database, as a function of the formula size (e.g., its length as a string of characters). Combined complexity, which isn't mentioned in your table, is the complexity of evaluating a formula on a database as a function of the size of those two things.

The expression complexity of first-order logic is high because, for example, a formula $\forall x\_1\dots \forall x\_k$ requires time $n^k$ to evaluate on a database of size $n$, so a formula of length $\ell$ can take time $n^\ell$, which is an exponential function of $\ell$ when $n$ is treated as a fixed constant. However, we can do this in polynomial space, since all we need to do is loop through potential values of variables and that requires storing just one value per variable.

---
Tags: database-theory, first-order-logic, descriptive-complexity
---


title: Master Theorem on a*T(n/b) + c?

text:
# Question
Title: Master Theorem on a*T(n/b) + c?
The recurrence equations solved by the Master Theorem are in the following format :

$ T(n) = a T(\frac{n}{b}) + f(n) $

but is it possible to use it on :

$ T(n) = a T(\frac{n}{b}) + c $

?

# Answer
Yes. The constant function $c$ plays the part of $f(n)$. Stated differently, you can use the function $f(n) = c$ to apply the master theorem.

A perhaps simpler way is to find a shift $d$ such that $S(n) := T(n) + d$ satisfies a nicer recurrence. We have $$ S(n) = T(n) + d = aT(n/b) + c + d = a(S(n/b)-d)+c+d = aS(n/b) +c+d-ad. $$ If $c+d-ad = 0$, then we get the simple recurrence $S(n) = aS(n/b)$, whose solution is $S(n) = n^{\log\_b a} S(1)$ (for powers of $b$). This happens when $d = c/(a-1)$. We conclude that $T(n) = n^{\log\_b a}(T(1) + c/(a-1)) - c/(a-1)$ (for powers of $b$).
> 2 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Implementing wait-free consensus with queues
Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the first process to dequeue it "wins".

However, it is also possible to do wait-free consensus with queues that start off empty (for example, given as an assignment here, question 1).

I wasn't able to come up with the algorithm - would like help.

A hand-wave explanation: Two processors run asynchronously and communicate via shared memory, with atomic reads and writes being basic operations. We want to solve the wait free consensus problem, where each process starts with a bit value and they need to agree on one of the values, in a way that is wait free: each processor can finish in a finite number of its own steps, regardless of the progress of the others. A result says that such a task can't be done, so we include objects with more powerful operations that will allow consensus. The consensus number of an object is the number of processors in the model that can reach consensus using it. The consensus number of a queue with just enq and deq is 2. Intuitively it isn't 3 because if a processor deqs empty, it can't know which of the other processors deqd the value.

# Answer
This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question.

> We study how initialization of shared objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus between two processes, we prove that an initially empty queue or stack **cannot**.
> However, **with a tiny extra resource such as a 1-bit safe register**, an empty queue or stack suffices to solve consensus.

Please check Section 5 for impossibility proof and algorithm.

---

Please also check the paper "On the Importance of Registers for Computability" by Rati Gelashvili, Mohsen Ghaffari, Jerry Li, and Nir Shavit, 2014.

In the second paragraph of Introduction, the authors claim that:

> (1) We show that $\ldots$ ***two queues in arbitrary initial states*** are sufficient for solving two process consensus.
>
> (2) On the other hand, we prove that it is **impossible** to solve two process consensus ***using a single empty queue***.

A little conclusion is:

> In other words, unless you have multiple queues or multiple registers, a queue’s ability to solve consensus is completely dependent on its initialization.

There are many propositions/lemmas/theorems in this paper. And they are not limited to the queue object. I think it may contain what you want to know (I will read it carefully when I have time).
> 6 votes

# Answer
did not find this in a published paper/ ref so far, however here is a similar exercise 2b with the basic structure of the algorithm outlined (with only one small missing piece.)

> Assume now that you do not have this initialized queue, but rather you have two initially empty queues. Take a look at the (incomplete) algorithm *proposei(v)*. Each process initially has a private input value *v.* In the algorithm, each process first enques a winner and then a loser ball in “its queue”. Complete the algorithm with the notation of the function *funci(Qj , Rj , v)* so that *proposei(v)* reaches consensus even if up to 1 process may fail. Make sure that you go through all the different executions and check whether they give a correct result.

Algorithm 1: *proposei(v)*

> Input: v ∈ V, i ∈ {1, 2}; processes pi ; empty queues Qi ; register array of size 2 Ri \[1, 2\]; initially false flags *flagi*
> 1. Qi.enq(”winner”);
> 2. Qi.enq(”loser”);
> 3. *flagi.*write(true);
> 4. resulti = v;
> 5. for j = 1, 2 do
> 6. if *flagj* == true then
> 7. resulti*funci*(Qj , Rj , resulti);
> 8. return resulti
> 2 votes

# Answer
There is a generic construction that turns a consensus algorithm for n processors that uses initialized objects into a consensus algorithm (for n processors) that uses n uninitialized copies of the same objects. By applying this construction to the 2-processors consensus algorithm that uses an initialized queue, one obtains a 2-processors consensus algorithm that uses 2 empty queues. The algorithm obtained has the same structure as the partial solution in vzn's answer.

The generic construction is described in Section 3.1 of Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. "Consensus power makes (some) sense!." Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing. ACM, 1994.
> 2 votes

---
Tags: algorithms, reference-request, concurrency, synchronization
---


title: Basic doubt in converting PDA to DPDA

text:
# Question
Title: Basic doubt in converting PDA to DPDA
This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism. When we have input a with Z at the bottom of the stack, then at the beginning it can do $(a,Z/aZ)$ or $(\epsilon,Z/Z)$ and go to final state, so automaton has 2 choices which can lead to 2 different states.

How do I convert it to DPDA ? How do I remove that $\epsilon$ transition from first state to make the PDA deterministic?

Here, the stack symbol is $Z$ and the transition $(a,Z/aZ)$ means on seeing input $a$ with $Z$ at the top of the stack, push $aZ$.

# Answer
> 2 votes
The DPDA could be constructed by adding explicit states and dropping too permisive epsilon transition.

I will denote accepting state by paranthesis around the name.

$(q\_0, \epsilon, Z, (q\_f), Z) \text{ accept empty string}$
$((q\_f), a, Z, q\_a, a)\text{ add initial a (or after cancellation occurs)}\\ ((q\_f), b, Z, q\_b, b)\text{ add initial b (or after cancellation occurs)}\\ (q\_a, b, a, q\_a, \epsilon) \text{ even out two symbols}\\ (q\_b, a, b, q\_b, \epsilon) \text{ even out two symbols}\\ (q\_a, \epsilon, Z, (q\_f), Z) \text{ accept, it happens only with empty stack}\\ (q\_b, \epsilon, Z, (q\_f), Z) \text{ accept, it happens only with empty stack}\\ (q\_a, a, a, q\_a, aa)\text{ add another a to stack}\\ (q\_b, b, b, q\_b, bb)\text{ add another b to stack}$

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: call by name : how are clashing variables handled?
In call by name : In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

ref : http://www.cs.sfu.ca/~cameron/Teaching/383/PassByName.html

Now consider the following code :

```
global int i = 100, j = 5;

void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}

main()
{
    P(i + j);
}

```

Will the variable i declared in function P get renamed before execution ? Which i ( global or local ) is accessed by x in print(x + 10) ? Which i ( global or local ) will get updated by (i = 200) ? What will be the output of the second print statement (220 or 120 ) ?

# Answer
> 3 votes
Programming languages do not "textually substitute" anything, that would be horribly inefficient. The "textual substitution" definition may be offered sometimes as a sort of textbook explanation, but it usually fails to capture all the details.

There are many techniques for dealing with the problem you describe. By the way, the problem is known as "variable capture" beacuse a binder "captures" a variable.

One possiblity is to eliminate all variable names and use de Bruijn indices instead. Substitution still requires a bit of work, namely *shifting* of indices, but at least one does not have to generate new names.

Another possibility is to create closures. These are used for evaluation of functions (I did not say "application"!), but in a call-by-name language we could use them for any expression. Briefly, when we evaluate `P(i + j)` in your code, we create a closure `(η, i + j)` where `η` tells us what the values of variables are at that point in the execution (so concretely, `η` would be something like `i ↦ 100, j ↦ 50, P ↦ ..., main ↦ ....`). When `P` actually needs the value of its argument, we evaluate `i + j` in the environment `η` (and not in the environment of `P`), so that `i + j` gets evaluated in the "old" environment.

There are still many other techniques for avoiding variable capture. Haskell compiles to a spineless tagless G-machine, or at least it used to.

# Answer
> 2 votes
As far as I know, call-by-name generally assumes *hygienic* calls, where no name leaks out of its scope. The simple way of implementing that is to α-convert the program: rename each bound variable to a newly-created unique name at compile time. Once all names are made unique, hygiene is automatic. A theoretical approach which abstracts away implementation details is de Bruijn indexing; a common pragmatic approach is to "rename" variables to their stack frame offsets (bearing in mind that the appropriate stack frame must also be identified).

Macro processors like the C preprocessor do unhygienic substitution, since they work by strict textual substitution. That is sometimes called call-by-name but most terms for it are less polite. I don't believe there is any theoretical model which avoids α-conversion in this way.

Assuming hygienic substitution (α-conversion), then:

> Will the variable i declared in function P get renamed before execution?

Yes, at compile time.

> Which i ( global or local ) is accessed by x in print(x + 10) ?

The global one.

> Which i ( global or local ) will get updated by (i = 200) ?

The local one.

> What will be the output of the second print statement (220 or 120 ) ?

120

# Answer
> -1 votes
Call by name has widely gone out of fashion. I have seen it in Algol 60, can't remember if it was in Algol 68, and I thought I hadn't seen it since, although the technology needed is in common use now again with closures etc. , and auto closures in Swift are actually the same as call by value parameters.

You wouldn't do this by name substitution. You would do this in your example by creating a chunk of code that adds the global int i and the global int j, and passing that code to P, where it can be executed whenever needed.

---
Tags: programming-languages
---


# Question
Title: any hope for a universal automatic parser?
Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and you want to make **some guesses on the corresponding syntactic tree**.

How would you try to achieve this, and would you have any hope to make it working on some toy problems ?

To be clear, the goal isn't to make a parser for 4 or 5 different (but similar) programming languages, but really to detect -from some examples- the regularity in how the data is structured, and build from it a syntactic tree, with the hope to generate a grammar, a syntactic parser and -let's dream- a semantic parser and an interpreter.

My thoughts : a major problem is that in general the grammar needed for parsing a given source code isn't LR(1), but only locally LR(1), and globally recursive. For example HTML contains some Javascript, itself containing some HTML+Javascript **hidden in a string** :

```
<html><body><script>

   document.onLoad = (function(){
            document.write("<div> <input type='button' value='click'   \
                       onClick='javascript:fn();'></input> </div>   \
                     <script>   \
                           function fn() { alert('wow a language nested into another'); }    \
                    </script> ");
</scritp></body></html>

```

For parsing this, you need to generate a grammar for HTML and another one for Javascript, and generate a recursive grammar saying that sometimes in the syntactic tree (from one node to its child) it can jump from one language to the other.

**Do you have any reference/idea on this problem?**

# Answer
You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those strings.

To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a grammar given a finite set of finite strings?, and the the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms.

There's no hope for automatically building an interpreter for the language, because that depends on the semantics (meaning) of the programs, and you can't determine that solely from the program source code; the most you can hope to learn is to characterize the syntax of the language, not the semantics.
> 10 votes

# Answer
It may be possible to automatically generate parsers for multiple programming languages using example-based machine translation systems. These systems have been used to translate natural languages, so it is also possible that they could be used to translate and parse programming languages.

Example-based machine translation systems can be designed to "learn" the grammar of multiple languages using parallel corpora. A parallel corpus for several programming languages could be written like this:

```
java
    System.out.println(a)
c#
    Console.WriteLine(a)
python
    print(a)

```

Programming languages can also be automatically translated using unsupervised learning models: Facebook recently did this using a system called TransCoder.
> 1 votes

---
Tags: formal-grammars, parsers, data-mining, learning-theory, structured-data
---


# Question
Title: Is machine learning a subarea of expert systems?
My question is short and straightforward: Can be considered "machine learning" a subarea of "expert systems"?

# Answer
That depends on your definition of an "expert system". Searching around, many definitions include a clear seperation between 'knowledge base' and 'inference rules', and machine learning most definitely does not always make this distinction.

In fact, unsupervised learning has no knowledge base whatsoever, and finds naturally occurring patterns in just unlabeled data.
> 0 votes

# Answer
I would see it the other way round: expert systems is a part of machine learning. Reason: using a neural network, training it means learning. However, a neural network is not an expert system (unless you stretch the definition of an expert system very much). A neural network does not use inference, for example.
> 0 votes

---
Tags: machine-learning, expert-systems
---


# Question
Title: Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?
I am reading http://okmij.org/ftp/gengo/applicative-symantics/AACG1.pdf and there is defined language TL (see last row in the table on page 4). It seems to me from this definition of TL, that lambda calculus is the language of universal logic - each connective (unary, binary, ternary, etc.; quantifiers can be expressed in this language as well - as unary functions) is just another function (of type t-\>t-\>t - for binary connective) and the only difference between this ***simple function*** and ***connective function*** is the following: connective functions have constraints in the form of logical rules (e.g. connective or quantifier introduction or elimination rules), simple functions have no such rules.

So - my questions are:

* Do I understand correctly, that lambda calculus is (can be) the language of Universal Logic (in the tradition of https://link.springer.com/journal/11787)? If no, then why not? If yes, then why there is no wide adoption of lambda calculus in the Univeral Logic community?
* Do I understand correctly that connectives are just another functions with the constraints. Is it possible to defined constraints on other functions (simple functions) in the lambda calculus without changing the base logic? I.s. how logical rules for connective functions differ from the user-defined additional rules/constraints for simple functions?

So - the fully hierarchy of the logics can be defined purely by the introduction of connective functions in lambda calculus and by the additional rules on them. So simple?

Of course, I am aware of Curry-Howard isomorphism but its talk about "propositions as types, proofs as lambda terms" is somehow disconnected with the straight appearance of lambda calculus as the language of universal logic. Maybe there exists answer that connects my feelings about lambda calculus as the language of universal logic with the CHI.

# Answer
> 3 votes
You are on your way to discovering the Curry-Howard correspondence.

---
Tags: formal-languages, logic, lambda-calculus, curry-howard, computational-linguistics
---


# Question
Title: Is there any data structure that can't be represented or described inside a computer?
We all know that, at least theoretically, there are several possible models of computation, varying in structure.

Strictly speaking, there are several (not just one) models of computation that exist or have been implemented in real life. Some machines (for example, amplifier circuits), though inexact, can be considered analog computers, but that's not what we commonly think of as 'computers', is it?

The machines that we usually think of as 'computers' are implementations of a computation model with discrete parts (discrete memory slots, discrete instructions and clock cycles, etc.) I've always wondered if there's some form of data that can't be represented/stored inside these discrete structures.

I've brought up this question in many websites, but I usually only find people who approach this issue with an incomplete picture of the problem, and without the required logical rigor.

I've been told that nothing with a continuous structure can be stored inside a computer, but from what I've gathered, this is not always true. Take the example of a circle (a geometrical shape). It's true that it has an infinite number of points in its circumference, but I can't say that they represent an infinite amount of information, since they can be derived from a very small number of parameters (center and radius) and a bunch of simple laws (algebra and symbolic math). My intuition tells me that this is the case for any geometrical shape, unless it has an infinite number of parameters, in which case I don't really know what to think.

Is my intuition accurate? Is this the case for any structure with a finite number of parameters? Are Von-Neumann/Harvard/... computers unfit to store certain data structure(s)? Has this been mathematically proven? Is the proof constructive? Are there any data structures that can't be stored in any known model of computation (or, for that matter, *any* model of computation)?

**Note**: I'm asking all of this from intuition. Even though I write code for a living, and harbor a great interest in Computer Science (and have *a little* knowledge of it through self-study), I am not a CS or Math graduate. From my limited, newbie perspective, I would think that this question belongs to the Theoretical Computer Science Stack Exchange, but I genuinely don't know if it's too basic, so I'll just play it safe for now.

# Answer
There is a systematic way of computing datatype representations of mathematical objects: anything that can be *described* in higher-order intuitionistic logic has a representation as a datatype. Because we are talking about *descriptions*, and not about proofs of theorems, it does not even matter much that the logic is intuitionistic and not classical. Pretty much any mathematical object you encounter in practice can be represented. Some examples that can be done easily: real numbers, the space of square-integrable measurable functions $L^2\[0,1\]$ and other infinite-dimensional Hilbert spaces, Banach spaces, the space of compact subspaces of $\mathbb{R}^n$, etc.

Roughly, the process goes as follows. Take you favorite model of computation and build a realizability topos from it. Then take your description of the mathematical object and interpret it in the topos. It will tell you how to represent data, because the topos is built in such a way that every object is equipped with a data representation, and every statement is witnessed by a program. In most cases we do not actually need the entire topos, the much smaller and easier subcategory of modest sets suffices.

There is an important caveat: in intuitionistic logic an object may have several inequivalent descriptions which are classically equivalent. These will lead to different data representations (and this is *good*, as it means we can express *more* computational distinctions).

The process of interpretation is automatic. To make that point, Chris Stone and I wrote a tool rz which does this. You can feed it the definition of real numbers, or an infinitely dimensional Banach space, or anything like that, and it spits out a specification. (The software experienced bitrot, I should update it, but the paper has many examples.)

Let me also address the common misconception that "non-computable objects cannot be represented in a computer". There is a difference between *non-computable* and *non-representable*. For example, the digits of a real number may be written down on the tape of a Turing machine. It doesn't matter whether the real number in question is computable, it *can* be stored on the tape. The question of "who stored it onto the tape" is a separate concern. You may object that the tape is not infinite. Actually, it is infinite in most textbooks. But people like to press this point, to which I have two responses.

First, we may replace the infinite tape with a potentially infinite tape, i.e., think of the real number as a *process* which emits digits on demand. This can be some sort of a physical process, say a quantum-mechanics experiment that produces bits by making measurements. Would anyone like to presuppose that the real number so obtained is computable? In this case they have to produce some evidence for such a claim. Good luck with that. The moral here is that it is largely irrelevant whether "all reals in this universe are computable". What is important is that we can represent whatever reals there are, and that would by definition be all of them.

Second, we can study models of computation that have no infinite components, for example the $\lambda$-calculus. In such models infinite data, say a real number, is represented by a program that produces the data, say the digits of the real number. So obviously only computable reals may be represented. *But this doesn't matter!* The corresponding realizability topos still thinks there are uncountably many reals, and is a self-consistent world of mathematics.

For further explanation on how to represent uncountable data, I refer to my blog post Representations of uncomputable and uncountable sets. It's a bit of a rant, actually.

The takeaway is the motto from my PhD thesis:

> *Data are continuous, programs are computable.*
> 6 votes

# Answer
This is a hard question to answer, given the vagueness of your notion of "parameter". For example, a typical real number as it is defined mathematically *cannot* be represented in a computer, using any number of standard arguments (see, e.g. the answers to this question).

Does this mean that a real number has an infinite number of parameters? In particular, your circle example is also faulty, since you need already 2 reals to represent one (which, as mentioned, are not representable).

If you then object that you are only interested in parameters which are themselves representable on a computer, then yes, all data structures that only require a finite number of parameters to describe can be represented on a computer. But this seems to beg the question a bit.

In general, all computable data structures are representable by an idealized VN computer, though often one has to decide how to represent the elements before determining whether they are computable. This paper by Casanova and Santini seems to address some of those issues, but it presupposes knowledge of the mathematical notion of computability.

Finally, I should note that figuring out the number of parameters to represent geometric objects like circles, parabola, etc is a very popular question in algebraic geometry which falls (mostly) outside the purview of computer science.
> -1 votes

---
Tags: algorithms, computability, data-structures, computation-models
---


# Question
Title: How to prove the NP-completeness of 15-Partition Problem
I would like to have a proof of the NP-completeness for 15-Partition Problem.

It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can be partitioned into subsets of 15 members that all have the same sum. More precisely, given a multiset *S* of *n* = 15 *m* positive integers, can *S* be partitioned into *m* subsets of 15 members *S1*, *S2*, …, *Sm* such that the sum of the numbers in each subset is equal?

It is not an excercise, it is a real problem dealing with load balancing. I did not expect someone would suspect it as a homework/excercise. I mentioned only related facts, obviously, I need to say more. I have a hardware switch with 15 ingoing ports and one outgoing port. Such switches, I have actually 6. That means, I have 15 x 6 = 90 ingoing ports. I have to connect cabels to these 90 ports and I can not affect how much data flows throught these 90 cabels. My task is to assign these 90 cabels to these 90 ports such that the output flow from each switch would be equal. I have already implemented 4 algorithms solving this problem based on dynamic programming, integer linear programming, differential evolution and reinforcement learning.

I would like to have an exact proof that the problem is not so easy to solve, i.e., I would like to prove it belongs to NPC.

Moreover, I have realized today, in case of total flow is not divisible by 6, all switches will not have the equal sum of flow on outgoing port. For example, total flow is 456 254 bytes, then Switch1 to Switch2 should have flow 76 043 bytes each and Switch3 to Switch6 should have flow 76 042 bytes. So maybe, I can not use 15-Partition Problem, not sure about it.

# Answer
I think this could work.

We multyply all the numbers by fifteen and we also multiply $B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers of size one for each bucket to the input.

As twelve is less than fifteen, we have to use exactly twelve of them to fill each bucket, then we have to use other three numbers to fill each bucket. As random\_hacker says in the comment, if we use more than twelve numbers in a bucket, we will not be able to cover the gaps in another bucket and so that bucket won´t be able to reach the quantity it should reach.

We see that if the big numbers fill the buckets in 15-partition, they also fill the buckets in 3-partition. Also, if we put four or more big numbers in a bucket, we will have more than fifteen numbers in that bucket
> 4 votes

# Answer
A lot of the difficulty of partitioning problems comes from the fact that someone wants exactly equal sum.

It is probably quite easy to find good approximations. Connect the six cables with the highest load. Add six more cables: the highest load to the lowest load box, then five more to match that total as close as possible. Repeat. Another 13 times. Check if that is good enough.
> 0 votes

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


title: Infix to postfix by stack

text:
# Question
Title: Infix to postfix by stack
Convert in postfix

(((P+Q)*(R+S))/T) +(A*(B+C)) note : there is * between (P+Q) (R+s) My attempt in image  and size of stack = 15 given, but iam getting size =13

# Answer
I don't know which way you are following to solve the problem. After seeing your problem I tried on the paper with the same above equation, got the correct postfix expression.

You can follow this link for understanding and be solving the infix to postfix expression https://www.youtube.com/watch?v=vXPL6UavUeA
> 0 votes

---
Tags: algorithms
---


title: Can every DFA be simulated by a PDA?

text:
# Question
Title: Can every DFA be simulated by a PDA?
Given a Deterministic Finite Automata (DFA) $M\_1$, does there always exist a Pushdown Automata (PDA) $M\_2$ that accepts the same language as $M\_1$? I.e. **can any DFA be simulated by a PDA?** Intuitively, it makes sense to me that a PDA is more powerful since it has an arbitrary amount of memory and can therefore accept more languages than a DFA, but how could this be formally proven?

# Answer
I hope this answer will help you to understand the mapping. Any DFA is also a PDA. The state transitions in the DFA are similar for PDA without stack. For every transition you perform in DFA, make the similar transition in PDA and do not push/pull from stack.

**For a transition**

In DFA : $\delta(q\_x,0) \rightarrow q\_y$

In stack : $\delta(q\_x,0) \rightarrow (q\_y,\epsilon)$

**For accepting state**

In DFA : $\delta(q\_x,0) \rightarrow q\_f$

In stack : $\delta(q\_x,0) \rightarrow (q\_f,\epsilon)$
> 1 votes

---
Tags: automata, finite-automata, pushdown-automata, simulation
---


# Question
Title: Hardware thread context and register renaming
I'm having some issues understanding what happens on a context switch with the physical register file in an out-of-order CPU that implements context switching. Suppose that a CPU consists of 4 hardware thread contexts and that the ISA consists of 32 architectural registers. Does the physical register file get overwritten when a context switch occurs, or do the 4 hardware thread contexts compete on the use of physical registers, for faster context switches (because they don't need to be overwritten)?

More concrete: "Does a CPU with 4 hardware thread contexts and an ISA consisting of 32 architectural registers and 96 physical registers in total make sense?"

# Answer
> 2 votes
I am not expert about hardware threading but I know two different ways to achieve it with potentially different answers:

* Architectures where the CPU executes one thread at a time but switches on some events (quantum expire, cache miss, switch instruction, ...). In that case, the CPU only really needs 32 registers and on a context switch it can store/load them from either physical registers or memory. Another option is to to register renaming (see below)
* Architectures where the CPU really executes the thread in parallel: this can be a Barrel processor that switches on every cycle, or a more complicated out-of-order architecture like Hyper-threading. In both cases, the CPU really needs 128 registers. The way it is usually implemented is that registers are renamed: the CPU has registers 0-95, and register i of thread j is renamed to 4\*i+j (for example register 2 of thread 3 is renamed 3\*32+2=98). The advantage of doing that is that the pipeline and functional units scheduling and all becomes almost thread agnostic.

---
Tags: computer-architecture, cpu, threads
---


title: Flaw in my NP = CoNP Proof?

text:
# Question
Title: Flaw in my NP = CoNP Proof?
I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?

Let A be some problem in NP, and let M be the decider for A. Let B be the complement, i.e. B is in CoNP. Since M is a decider, you can use it to decide B as well (just flip the answer). Doesn't that mean that we solve both NP and CoNP problems with the same M?

To put it more concretely.

Let A be some NP-complete problem, and let M be decider for A. Consider any problem B in CoNP. We consider its complement not-B, which is in NP, and then get a polynomial reduction to A. Then we run our decider M and flip our answer. We thus obtain a decider for B. This implies B is in NP as well.

May I know what is wrong with my reasoning?

# Answer
There are two possible bugs in this proof:

1. When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\subseteq EXP$ (or, after some optimization, $co-NP\subseteq PSPACE$).
2. When you say "decider" you mean a nondeterministic TM. In this case, flipping the answer will not necessarily complement the language. Indeed, the language of the flipped machine will be all the words for which *there exists* a rejecting run of $M$ on $w$
> 18 votes

# Answer
Here's another way of looking at the point that Shaull makes with respect to "deciders".

A problem is in **NP** if and only if there is an algorithm $V: \\{0,1\\}^n \times \\{0,1\\}^{\mathrm{poly}(n)} \to \\{0,1\\}$ such that

* for every YES instance $x \in \\{0,1\\}^n$, there is a certificate $p \in \\{0,1\\}^{\mathrm{poly}(n)}$ such that $V(x,p) = 1$; and
* for every NO instance $x \in \\{0,1\\}^n$, we have $V(x,p) = 0$ for all $p \in \\{0,1\\}^{\mathrm{poly}(n)}$.

These are usually described as the *completeness* and *soundness* conditions for the **NP** verification algorithm: the "completeness" condition says that *every* YES instance has a certificate, and the "soundness" condition says that the algorithm is never fooled by a NO instance. For **coNP** it's the other way around: there is a verifier algorithm which will accept at least one certificate for any NO instance, but which can never be fooled by a YES instance.

If you want to show that **NP****coNP**, you have to show that every **NP** problem has a **coNP**-type verifier, which can certify NO instances instead of YES instances. You cannot do this with a nondeterministic Turing machine: there's no way that we know of, for instance, to efficiently map instances of SAT to one another, in such a way that *all* unsatisfiable formulae are mapped to satisfiable ones, *and vice versa*. (Negating the output ofr the formula isn't enough, for example: a formula which is satisfiable but not a tautology would just get mapped to a different formula which was satisfiable but not a tautology, when we would require an unsatisfiable formula instead.) There is simply no way that we know of to 'fool' a nondeterministic machine into detecting anything like all of its paths being rejecting paths.

You might ask: "Doesn't the nondeterministic Turing machine *know* what result it gets?" The answer would be *no*, it doesn't. The working of the non-deterministic machine doesn't give it access to any information about more than one computational path at once: you might think of it working in many paths in parallel, but within each path it only knows about that one path. If you try to equip it with the ability to "realize" whether or not there are any solutions as some point, you are instead describing a machine *with an* **NP** *oracle*, which is more (potentially!) powerful than a simple nondeterministic Turing machine.

* For instance, if you equip a (deterministic) Turing machine with an **NP** oracle, then the problems which can be solved in polynomial time on that machine is called $\Delta\_2^{\mathrm P}$, which is often written $\mathsf{P}^{\mathsf{NP}}$. The "oracle" allows the machine to simply recieve answers to **NP**-complete problems in a single step, and so $\mathsf{P}^{\mathsf{NP}}$ obviously contains **P**; and because you can negate answers, it also obviously contains **coNP**. But we don't know whether the reverse containments hold, exactly because we don't know how to trick nondeterministic Turing machines into detecting NO answers.
* What's more, if you give a *nondeterministic* Turing machine the ability to come to a realisation about the outcome of a problem in **NP**, the problems which *that* machine can solve in polynomial time is called $\Sigma\_2^{\mathrm P}$, or $\mathsf{NP}^{\mathsf{NP}}$, and this is widely believed to be strictly larger than the class $\mathsf{P}^{\mathsf{NP}}$. This also contains both **NP** and **coNP** — but like **NP**, it isn't known to be closed under complements: the nondeterministic oracle machine might be able to know when a problem in **NP** has a NO answer because of the oracle, but it would still be stuck to operating within one of *its own* (quite powerful) computational branches, so that it would not be able to tell if all of *its own* computational branches were rejecting.

If you keep on supplying the machine with more powerful oracles for solving problems in $\mathsf{NP}$, $\mathsf{NP}^{\mathsf{NP}}$, and so forth, you end up defining the classes of the polynomial hierarchy, which are thought to be all distinct from one another from the first level onwards.

So, no, there's no machine (deterministic or otherwise) which can simply 'decide' that a problem is a YES or NO instance efficiently, unless we use oracles; but even with such an oracle, we end up with a machine which is (probably) *more* powerful than either **NP** or **coNP**, not one which shows that they're equal.
> 16 votes

# Answer
Your reasoning implies that RE=coRE, but this is provably false. You could try to figure out a proof of that and then see where your reduction fails.

Recall that RE is the complexity class of recursively enumerable languages, which are languages of the form $\\{ x : P \text{ halts on input } x \\}$. You can also think of it in non-deterministic terms: RE is the class of languages of the form $\\{ x : (x,w) \in L' \text{ for some } w \\}$, where $L'$ is recursive (computable).

Here is a proof that both definitions match. Suppose first $L = \\{ x : p \text{ halts on input } x \\}$. Let $L' = \\{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \\}$. The language $L'$ is recursive and $L = \\{ x : (x,w) \in L' \text{ for some } w \\}$.

For the other direction, let $L = \\{ x : (x,w) \in L' \text{ for some } w \\}$, where $L'$ is recursive, say computed by the program $P(x,w)$. We construct a new program $Q(x)$ which enumerates all possible $w$ and runs $P(x,w)$ on all $w$, in order. If $P(x,w)$ ever accepts for some $w$, then $Q$ halts. It's not hard to check that $L = \\{ x : Q \text{ halts on input } x \\}$.

For your convenience, here are outlines for a proof that RE is different from coRE. The language $L = \\{(P,x) : P \text{ halts on input x}\\}$ is clearly recursively enumerable: a program for it simply runs $P$ on $x$. Suppose there was a program $H$ such that $H(P,x)$ halts if and only if $(P,x) \notin L$. We define a new program $G$ by $G(x)=H(x,x)$. Is $(G,G) \in L$? If so, then $G$ halts on $G$, so $H$ halts on $(G,G)$, so $(G,G) \notin L$. If $(G,G) \notin L$, then $G$ doesn't halt on $G$, so $H$ doesn't halt on $(G,G)$, so $(G,G) \in L$. This contradiction shows that $H$ cannot exist.

Now try to run your proof in this case and see what goes wrong. In more detail, try to construct the program $H$ using your recipe, and follow the proof - at some point something wouldn't be quite right.
> 6 votes

# Answer
Here's a TL;DR version; I've also posted a longer answer to a similar question.

Suppose we have a language $A$ that's decided in polynomial time by nondeterministic Turing machine $M$. The point is that $x\in A$ iff there $M$ has *some* accepting path on input $x$. However, since $M$ is nondeterministic, there may also be rejecting paths when it runs on $x$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language.

It is this asymmetry of definition (accept if *any* path accepts; reject only if *all* paths reject) that makes the **NP** vs **co-NP** problem difficult.
> 2 votes

# Answer
I actually agree that your nondeterministic machine M can decide whether a given input string is in B. However, it "decides" slightly differently than the way it decides if a given input is in A. In the latter case, it does so by (nondeterministically) finding an accepting state. In the former case, it does so by failing to find any accepting states. Why does this difference matter? Let's see:

## When asking M "Is the string in the language A?"

M reaches an accept state. This, you can prove (see, for example, the Sipser book theorem 7.20) implies that there is a deterministic machine that verifies the string is in A in polynomial time

## When asking M "Is the string in the language B?"

M reaches reject states on all branches of its nondeterministic computation. If you think about how the verifier proof above works, you will see that it cannot be accomplished in this situation. This is roughly because the verifier uses the path that M takes through its state space as "proof". In this case, there is no one such path.

## Conclusion:

If you consider the existence of a polynomial time deterministic verifier for a language to be the definition of an NP language (which you should), the existence of M does not prove that B is in NP.
> -2 votes

---
Tags: complexity-theory, p-vs-np, check-my-proof, np
---


# Question
Title: Trying to understand CLRS bucket sort analysis
I'm trying to understand the analysis of **bucket sort** in CLRS. Specifically, **equation 8.2** that states:

$$ E\[{n\_i^2}\] = 2 - \frac{1}{n} $$

To prove, CLRS:

Random variable denoting number of elements that fall into bucket i:

$$ {n\_i} $$

An indicator random variable that a given element in the input falls into a particular bucket.

$$ X{\_i}{\_j} $$

so

$$ {n\_i} = \sum\_{j=1}^{n}X{\_i}{\_j} $$

Now, CLRS says to ***expand the square and regroup the terms***:

$$ E\[{n\_i^2}\] = E\left\[\left(\sum\_{j=1}^{n}X{\_i}{\_j}\right)^2\right\] $$

I can see how the above goes to the next step:

$$ = E\left\[\sum\_{j=1}^{n}\sum\_{k=1}^{n}X\_{ij}X\_{ik}\right\]$$

I'm confused as to how the above turns into:

$$ = E\left\[\sum\_{j=1}^{n}X\_{ij}^2 + \sum\_{1 \<= j \<= n}\sum\_{1 \<= k \<= n, k != j}X\_{ij}X\_{ik}\right\] $$

For what it's worth, the **Algorithms in a Nutshell** books has a section on bucket sort that also analyzes why it's 2 - 1/n, and it helps me see things a bit more clearly, but still am unclear about the above. From the AiaN book:

$$ E\[n\_i^2\] = Var\[{n\_i}\]+ E^2\[n\_i\]$$

where

$$ Var\[{n\_i}\] = n * p * (1-p) = n * \frac{1}{n} * \left(1 - \frac{1}{n}\right) = 1 - \frac{1}{n} $$

and

$$ E\[{n\_i}\] = n * p = n * \frac{1}{n} = 1$$

which equals 2 - 1/n

# Answer
You are asking why

$\qquad\displaystyle \sum\_{j=1}^{n}\sum\_{k=1}^{n}X\_{ij}X\_{ik} \quad=\quad \sum\_{j=1}^{n}X\_{ij}^2 + \sum\_{j = 1}^{n}\sum\_{1 \leq k \leq n,\\ k \neq j}X\_{ij}X\_{ik}$

holds (in expectation, but that's irrelevant for this; it might not always be, though!).

Note that the left-hand side and the second summand on the right-hand site are identical except for the $k \neq j$ constraint. That is, the difference between the two terms is exactly

$\qquad\displaystyle \sum\_{j=1}^n \sum\_{1 \leq k \leq n,\\k=j} X\_{ij}X\_{ik} \quad=\quad \sum\_{j=1}^n X\_{ij}X\_{ij} \quad=\quad \sum\_{j=1}^{n}X\_{ij}^2$.

No deep insight here, just basic manipulation of sums.
> 2 votes

---
Tags: algorithm-analysis, probability-theory, average-case
---


# Question
Title: Enforcing application layer consensus on top of a distributed consensus protocol
If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value. Different algorithms can handle different types of failures or misbehavior by some of the peers, network disconnections or partitions, lost messages, and so on. For example, PBFT has the property that any small group of peers (less than a third) cannot prevent the remaining peers from achieving a common understanding of the data value.

BUT there is nothing in these algorithms that prevents any peer from setting the data to a value that they shouldn't set it to. So "consensus" just means we all agree that the value has been set to X. It does not mean we all agree that X is the correct value.

Is that right? And, if so, is there some general research into how to enforce a set of application-specific rules about who is allowed to set the data to a given value?

For example, Bitcoin has a set of rules that ensure that only "valid" transactions are accepted by the network. So, for example, Joe can't give Fred the same bitcoin that he's already given to Mary. Joe can't give Fred a bitcoin unless someone else already gave Joe that bitcoin, or Joe earned that bitcoin by mining. And so on...

So what we have in Bitcoin are a set of application-layer rules that make sense for money, and these rules are embedded in the distributed consensus protocol used by Bitcoin (i.e. blockchain and proof-of-work and the bitcoin reference implementation).

However, what if I have a different set of rules that make sense in MY application - how can I ensure that a distributed consensus protocol (e.g. PBFT) not only ensures consensus across all peers about what the data value is, handling various failures and misbehavior by peers, and ALSO ensures that only "legal" values are set by the peers.

For example, I might have rules like: The value can only increase - nobody is allowed to decrease it. Except on Sundays, when it can be decreased, but must only be set to an even value. Except peer P can set it to whatever value they want to. And if the value=5, then peer Q is the only one who can change it. And so on... (Believe me, I have a real-world problem that requires this kind of complexity.)

Ideally, the rules would be expressed in a formal language, and the distributed consensus protocol would reject any attempts by any peers to change the data value in a way that does not conform to the rules.

Could I do this by implementing PBFT and adding in a check where each peer checks that a proposed new value is consistent with the rules, and then refusing to accept (possibly broadcasting a NACK) if the proposed change is not valid?

I'm wondering if this has already been studied. Perhaps this is the same as the concept of "consistency" in a distributed database, but I don't want to use a database replication solution, because I want eventual consistency, not strong consistency, and I want the kind of fault-tolerance that PBFT provides.

Thanks!

Duncan

# Answer
> 1 votes
You've asked multiple questions here. I'll answer the first one.

Typically consensus means that all the honest participants have the same view of the state of the system. There's not necessarily a guarantee that this state is "correct" in any sense (some protocols might also provide that guarantee, but it is in some sense a separate or additional request).

Often there are some rules about what kinds of state changes are "valid" or "allowed", and the honest participants are also tasked with ensuring that every state transition is valid; they won't generate or request transitions that aren't valid, and they won't accept transitions from others that are invalid. If you do this right then you get the additional guarantee that all the honest participants have the same view of the state of the system, and this state is valid.

There are multiple ways to define which states or transitions are valid. One way is by defining a state machine (like a DFA) that represents which state changes are valid; then the protocol provides a distributed implementation of the state machine.

I'm not an expert, but if you want to get a more authoritative answer, you could read the literature about state machine replication. It's probably worth reading the PBFT paper, which is presented as an instance of state machine replication.

---
Tags: algorithms, distributed-systems, fault-tolerance, byzantine
---


# Question
Title: Using computer vision instead of algorithms?
I have been thinking of a problem i have here with a calendar scheduler where i basically want to split a year into seconds and have access to the dataset of whole year.

In this year i assign blocks of time that varies in size can be big or can be small, it has to be placed in non assigned places ( which isnt occoupied with blocks already ) - also the option to insert so the map changes all the time.

To do this programatically, if i ex have a 10 day in seconds block i want to fit it, today i would go through the whole year and try to compare 10 days of seconds ( alot of bytes if 1 byte represent a second ) this is a heavy process.

But if i ex illustrate my year visually ( ok it would be a very wide image ) and look at the size of the block i need to fit in, i am visually super fast in spotting places where it might fit or fit.

Would this be possible to do with computervision ? Or will the computing power in computer vision be way over the line compared to what any algorithm can do ?

# Answer
> 1 votes
Your analogy is mistaken. You assume that, if you glanced at your calendar, you would quickly be able to identify all ten-day blocks of free time. Actually I bet you'd have all kinds of problems with that.

Can you really tell at a glance the difference between a free block of $863\ 999$s (ten days minus a second) and one of $864\\,000$s? Honestly, even if you just divided my calendar into days, I'd have to count the length of blocks between about eight and twelve days to check whether they were really more or less than ten.

---
Tags: machine-learning, search-algorithms, computer-vision, python
---


# Question
Title: Machine learning - PCA and KNN on rgb images are too slow
I work with python and images of tables (taken from above). My aim is to take a photo of a random table and then find the most similar tables to it in my database. By most similar I mean tables of similar shape(square, rectangular, round, oval), texture, colour etc.

For now, I am just running a PCA and then a KNN on all the pixels of rgb images of tables to let my computer find the most similar ones among them. Obviously the k-nearest neighbours of a table image must be images with tables which are very similar to it. The images are common images of tables and are of 529x940 dimensions.

My final goal is to run this program with 2000 or even 4000 table images so I need a more efficient machine learning algorithm for my task than the PCA and the KNN.

Can you recommend me another more efficient machine learning algorithm for this task? Is Support Vector Machine significantly or Histogram of Gradient better for this task?

# Answer
> 1 votes
One possible approach is to train a classifier that, given a table, outputs its shape; train a classifier that, given a table, outputs its texture; train a classifier that, given a table, outputs its colour; and so on for each of the feature values you care about. Thus, given a table, you can compute a feature vector that has the value of each of these attributes. You can then define a distance metric on these feature vectors (e.g., some kind of weighted L2 distance), which will let you measure how similar two tables are by comparing their feature vectors.

Once you've done this, there's a straightforward way to find the most similar tables. Use the classifiers to find the feature vectors for all the tables. Then, use k-nearest neighbors to find the k most similar images to each given image. If the number of features is not too large, this should be efficient, as you are now doing k-NN in a low-dimensional space. For instance, you can use k-d trees or other data structures for nearest neighbor search to speed up the search. These data structures are a lot more efficient when the number of dimensions is small.

I expect this should be plenty efficient for your needs. Handling 4000 table images should be no problem.

There are other possible approaches as well, but the above is the first thing I'd try.

---
Tags: machine-learning, computer-vision
---


# Question
Title: How many node does the final B-tree have?
I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is:

> Suppose that we insert the keys $\\{1,2,...,n\\}$ into an empty B-tree with minimum degree 2. How many nodes does the final B-tree have?

I think given that a node will have between $t-1$ and $2t-1$ keys, where $t$ is the minimum degree, so the answer for this question will be somewhere between $n$ and $n/3$? This is where I'm stuck, any help would be appreciated.

# Answer
> 3 votes
Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children.
If we imagine to construct a minimun nodes b-tree, we'll have:
$n = 1 + 2 + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$
where every addend is the number of nodes for every level, from the root (that can contains even one key), to the leaves level, and where h is the height of the b-tree;
If you consider the series, you have $n=1+2 \frac{ \lceil m/2\rceil^{h-1}-1}{\lceil m/2\rceil-1}$.
Instead, if you consider the maximum number of nodes, you will have:
$n= 1+m+m^2+...+m^{h-1} = \frac{m^h-1}{m-1}$.
where at the same way, every addend is the number of nodes for every level, and where h is the height of the b-tree;
You can easily find the result if you substitute 2 instead of m in the formula.

---
Tags: data-structures, search-trees, balanced-search-trees, b-tree
---


# Question
Title: explaining $\lambda$-calculus/functional programming to someone used to Turing machines/procedural programming?
**I have the following background:**

* I have experience with object-oriented programming languages
* I find Turing machines and the concept of a "procedure" very intuitive.

Yet I'm interested to understand the idea behind the abstract $\lambda$-calculus, and its application in the form of functional programming.

**When I read about either $\lambda$-calculus or functional programming, these explanations tend to either:**

1. make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.
2. or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

**So I am looking for a general, principled, theoretical understanding of the conceptual and formal difference between (1) $\lambda$-calculus and Turing machines, and between (2) functional programming and procedural programming.**

# Answer
> 4 votes
I'd like to second both Derek Elkins' and Chi's comments. You can do Functional Programming in most languages, but it requires the discipline to adhere to the functional principles. It's probably harder to learn FP in a language like Javascript\Python because you'll have to fight against the urge to do things the old way you already know.

In a Functional Programming Language (i.e. purely functional) you'll have to do stuff THE FUNCTIONAL WAY, without taking corners. Also, doing practical stuff means you'll have to learn some theory as well.

---

> 1. make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.

Something I really like about functional languages (and is kinda contained in what you said about error-proneness) is they often have some pretty amazing Type Systems.

Let's look at a "Hello World" in C:

```
#include <stdio.h>

int main(){
    printf("Hello World\n");
    return 0;
}

```

The function `main` takes no arguments and returns an `Int`, but there's no way I would know that it is actually doing IO inside it's body, unless I look at the functions body.

I can even change it and only get a warning.

```
#include <stdio.h>

char* main(){
    printf("Hello World\n");
    return 0;
}

hello.c:3:7: warning: return type of ‘main’ is not ‘int’ [-Wmain]
 char* main(){

```

The same code in Haskell,

```
module Main where

main :: IO ()
main = do
  putStrLn "hello world"

```

The function `putStrLn` has type `Str -> IO()`, to put it simply, it takes a String and returns some `IO()` stuff. Main also returns `IO()`.

If I try to change the main's type to `main :: String` I would get the following error:

```
module Main where

main :: String
main = do
  putStrLn "hello world"

hello/src/Main.hs:4:1: error:

    • Couldn't match type ‘[Char]’ with ‘IO t0’
      Expected type: IO t0
        Actual type: String
    • In the expression: main
      When checking the type of the IO action ‘main’
  |
4 | main = do
  | ^

hello/src/Main.hs:5:3: error:
    • Couldn't match type ‘IO ()’ with ‘[Char]’
      Expected type: String
        Actual type: IO ()
    • In a stmt of a 'do' block: putStrLn "hello world"
      In the expression: do putStrLn "hello world"
      In an equation for ‘main’: main = do putStrLn "hello world"
  |
5 |   putStrLn "hello world"
  |   ^^^^^^^^^^^^^^^^^^^^^^

```

That is, Haskell is telling me that `putStrLn` will return some `IO()`, so `main` is expected to do the same, since it returns `putStrLn`. Actually it wasn't even required to give `main` a type, since Haskell has a pretty powerful Type System based on Hindley–Milner Type Inference.

This was a really trivial example, but it is often the case that most Runtime Errors in many languages will be caught as Compilation Errors in pure functional languages. Some languages, like Coq, are so strong that you can prove theorems with it!

> 2. or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

This is actually a problem with Haskell (Survey 2017)

> Most people want the Haskell community to be bigger. To that end, many people want the community to be less divisive (for example Stack versus Cabal) or less elitist (for example putting down other languages). Also more beginner and intermediate documentation and tutorials would help.

---

Some pure Functional languages you might want to give a try:

* Haskell
* Elm
* Coq

Here are some references I've been using through the years to get some familiarity with FP and it's theory.

Some references on the $\lambda$-Calculus:

**Books**

**Lecture Notes**

**Quick Talks**

**Lectures**

Some theory about Functional Programming:

**Books**

Implementation of Functional Programming Languages

**Lecture Notes**

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Finite Automata: Final vs Accepting States
What is the difference between a final and accepting state when addressing an automaton?

As I understand it, a final state is depicted (traditionally) with a double circle, and apparently so is an accepting state. So if they are both depicted with the same symbol, what makes a state particularly accepting?

# Answer
Those are two words that mean exactly the same thing.
> 5 votes

---
Tags: automata, terminology, finite-automata
---


title: assigning running time

text:
# Question
Title: assigning running time
I'm trying to assign running times to loops of code to roughly get the upper asymptotic ($O$) running time.

```
while (j < n2) {                                   # executes n2-1 times
    int k = 0;
    while ((k < n1) && (seq[k] < seq2[j])) {       # executes (n2-1)*n1times
      k = k + 1;
      }
     // we want to insert seq2[j] at seq[k]
     // so we move seq[k] through seq[n1 - 1] to the right
     for (int i = n1; i > k; i = i - 1) {         # some n-k times
        seq[i] = seq[i - 1];
      }
     seq[k] = seq2[j];
     j = j + 1;
     n1 = n1 + 1;
}

```

I know this is bad but would this algorithm worst running time be something in O(n^2) because there is one main loop and then two separate nested loops inside the main loop?

Thanks

# Answer
It's hard to say without seeing the preceding code. If `seq` is initially empty the the run time of the outer loop is $O(n2)$ and the first nested loop is $O(k)$ and the second nested loop is $O(n1-k)$. The total running time would be $O(n2)\*(O(k)+O(n1-k))$ which is $O(n^2)$.

However if seq has some initial elements, the worst case running time for the algorithm is $O(\infty)$. The problem is with the nested while loop `seq[k]>seq2[j]`. If any of the first `n` elements in `seq` are `>` `seq2[j]` the loop will not increment and run endlessly. Also you may run into array index out of range errors.

For example if `seq` = 2 , 1 , 0 and `seq2` = 1 , 2 , 3. Then `seq[0] > seq2[0]` would be equivalent to `2 > 1` which i s `false` and `k` would never increment. The solution would be to use

```
n1 = sizeof(seq)/sizeof(seq[0])  # number of elements in seq
int k = 0;
for(; k < n1 ; k++){             # iterate over seq
    if( seq[k] >= seq2[j] )      # until an we find an element in seq >= seq2[j]
        break;

```
> 0 votes

---
Tags: algorithms, time-complexity, runtime-analysis
---


# Question
Title: Simulating AVL Tree Right, then Left rotation
I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to rebalance the tree. However, what would the actual steps to rebalance the tree look like?

Before insert (balanced):

```
    3
   / \
  2   7
 /   / \
1   4   8
      \
       6

```

After insert, but before balancing (unbalanced):

```
    3
   / \
  2   7
 /   / \
1   4   8
      \
       6
      /
     5

```

# Answer
the first step is notice that 4 node is unbalanced with balancing factor of $-2$, and a RL case
What you need to do is to do a RR rotation on the child of unbalanced node, that is 6 node.
the aspect of your tree should be this:

```
    3
   / \
  2   7
 /   / \
1   4   8
     \
      5
       \
        6

```

After, you have to do a LL rotation on the 4 node, and your tree should become like this:

```
    3
   / \
  2   7
 /   / \
1   5   8
   / \
  4   6

```

And you have rebalanced your tree.
> 0 votes

---
Tags: data-structures, balanced-search-trees, binary-search-trees
---


# Question
Title: Dijkstra for negative weights by adding a constant
I have slight modification for graphs which has negative weights for finding shortest path . If the graph has all non negative weights then by Dijkstra's algorithm , it can be done in **O(VlogV + E)** . So for the graphs having negative edge weights , find ***min(weights) = K*** and subtract K from all weights so that we end up with positive weights. Then apply Dijkstra's instead of bellman ford algorithm which takes **O(VE)** time to find path and then add K to all paths. Does this method work? If it does then why bellman ford algo is still relevant , If not why?

# Answer
> 1 votes
No, this doesn't work. A path of length $\ell$ will have $\ell K$ added to its weight, so your transformation can make a path with several light edges weigh more than a path with a few medium-weight edges. (Consider the effect of adding $2$ to each weight in a path of two weight-$1$ edges vs a path of a single weight-$3$ edge.)

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


# Question
Title: How to Identify which instructions are represented by this microcode
I'm having issues with a question how to identify which instruction are represented by this microcode. The pc starts at 5000 and 7000 and 7001 have values 31 and 64 - I'm really confused how to approach this wouldn't each line be an instruction?

```
 MAR = PC, PC+1, Assert MAR
 IR = MBR, decodes IR
 put addr 7000 into MAR, Assert MAR
Move MBR to R1
MAR = PC, PC+1, Assert MAR
IR = MBR, decodes IR
 put addr 7001 into MAR, Assert MAR
 Move MBR to R2
 MAR = PC, PC+1, Assert MAR
  IR = MBR, decode IR
 R1 = R1 + R2
MAR = PC, PC+1, Assert MAR

```

# Answer
Microcode instruction sets typically have more fields than ordinary instruction sets.

Sometimes this is called wide word, as a very long instruction can offer access to multiple hardware components in the same cycle for many operations to be performed in parallel.

In simpler microcoded systems, instead of being wide in the extreme, the numerous (smaller) fields offer access to simple operations (though still in parallel), like read from memory, write, transfer one register to another, etc..

We also generally won't see overlapping fields in microcoded instruction sets, like we do with normal instruction sets. Look at MIPS for example, which has half a dozen different instruction forms, like J-type and R-type where the fields overlap and the hardware decides how the fields are to be interpreted based on the instruction type.

In microcode, you just use the fields you need in each microcoded instruction, instead of choosing a different instruction type. This keeps the micro-machine simpler, at an expense of either needing a wider microcoded instruction set, or having fewer micromachine features, like fewer micromachine registers and/or hardware units (like adders).

Because of the large number of instruction fields in each microcoded instruction, we can expect multiple operations per instruction.

In your example, I think we can assume the following are all encoded in a *single* instruction:

```
MAR = PC       // transfer PC to address bus
PC = PC + 1    // increment PC register
IR = MBR       // transfer data bus to IR register
Assert MR      // assert memory read

```

And it looks like the "put addr 7000 into MAR, Assert MAR" is a programming comment associated with this instruction.

---

N.S. Matloff has a description of a 32-bit microcoded instruction set that looks roughly like what you're showing. You can see the large number of fields, and also that by comparison to a normal instruction set. There are fields of the instruction for branching, fields for alu operation, register source & target, memory access, etc.. These fields exist in every instruction; there are no overlapping fields as there is only one instruction type.
> 3 votes

---
Tags: computer-architecture, operating-systems, code-generation
---


# Question
Title: Finding an element in an unsorted array equal to its rank in $O(n)$ time
I'm trying to figure out a way to think about this problem. Background: Given an unsorted array of distinct integers (can be positive or negative), I want to determine if there is an element in the array that is equal to its rank (i.e. if I do $S = Sort(Array)$, I want to find an element s.t. $S\[i\] = i$).

Some approaches I have thought about.

* Radix sort: But there's no guarantee on what is the largest/smallest element here
* Any comparison based sorting method: But that gets me at least $O(n \lg n)$ time.

So it seems that I am not supposed to sort before I figure out what the ranks of the elements in the array are. I also feel that it needs to be a selection type algorithm, but I am not sure how that can be applied here. Any ideas on where to go from here?

# Answer
> 1 votes
You can preprocess the array to transform all negative numbers to $0$, and to transform numbers greater than $n$ to $n+1$. This transformation does not change the result because negative numbers and numbers greater than $n$ is not able to equal to its rank. This transformation only costs $O(n)$ time.

Now you can do counting sorting with $O(n)$ time.

---
Tags: algorithms, sorting
---


title: Understanding about creating a DFA

text:
# Question
Title: Understanding about creating a DFA
This is a school assignment, I am fairly new to DFA's.

```
L = {ww|w∈{0,1}*

```

I feel like I need to put this in words to understand how it works.

Translating L:

> W can be a string of an infinite combination of 1s and 0s.
> WW is just a string that repeats itself.

For example W="101011", WW = "101011101011".

Im not a 100% on this. Not really sure how to create a DFA out of this.

Am I correct with my "translation"? If you can help me further into making a DFA much appreciated.

# Answer
> 1 votes
You cannot make a DFA for this language because its not a Regular language in fact its not even a context free language so you can't even make a PDA for it

to prove its not regular and not context free you should use pumping lemma

but you can make a linear bounded automata for this language so therefore its a context sensitive language

hint for the linear bounded automata: put both of the w's in the tape and separate them with 0, then compare them.

also here's some examples for some of the strings in the language :

00 , 11 , 0101 , 1010 , 110110 ...

---
Tags: finite-automata
---


# Question
Title: Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms
The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford algorithm can work with and detect -negative edge cycles.

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node $a$ in following graph:

My shortest path tree after running Dijkstra came like this:

Then why texts say that Dijkstra need all non negative edge weights? I feel that it should be no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

# Answer
> Then why texts say that Dijkstra need all non negative edge weights?

Because it has to work for *all* cases, not only a few examples.

> I feel that it should be no -ve edge weight cycle reachable from source node.

Try proving that claim and see where it leads. If you're successful, great; if not, trying to prove the opposite will fix your intuition.

See also here for a high-level argument.

> The smallest example where Dijsktra fails has four nodes, no (directed) cycle at all, and no negative-value cycle:
> 4 votes

# Answer
Raphael's answer is spot on, but let me offer some additional perspective as well.

> Then why texts say that Dijkstra need all non negative edge weights?

Because we've been unable to prove it works otherwise.

In fact, imagine that negative edge-weights were allowed. In one extreme, this means that *all* edge weights can be negative. So we could take any graph that we want, make all weights equal to -1, and give it to the algorithm and find a shortest path between $s$ and $t$. This shortest path maximizes the length of the path (in terms of the number of edges), so we'll get a Hamiltonian path between $s$ and $t$ if it exists. But as far as we know, there is no polynomial-time algorithm for solving the problem!
> 2 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Neural net that alters its own parameters
Is it possible for an AI neural net to be able to modify its own parameters/hyperparameters and/or add new parameters/hyperparameters? If so, how has it been implemented? For example, to simulate a human mind, could the net utilize 3 basic emotional parameters before realizing it needs many more and subsequently creating them?

# Answer
One can do whatever he likes.

If your algorithm allows richer structure modification than simply adjusting weights, then you can obtain a "net which alters itself", though this doesn't have any special/magical meaning.

Suppose for example that your net's inputs correspond to some properties of an image, and you have a " hidden node" whose input is the average pixel value. During training, you can see whether adding this node lowers your training error, and if so, add it. One can claim that the net magically realized that it needs to use the average pixel value, but this is merely a direct result of your learning algorithm definition.
> 2 votes

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?
It is within *polynomial* hierarchy so I assumed it is decidable. The picture like this further hinted in that direction. Yet, in a paper on page 2 I read

> Satisfiability of \[...\] is highly undecidable **(i.e., $\Sigma^1\_1$-hard)**

which implies that $\Sigma^1\_1$-hard is undecidable. Do authors mean something else by "highly undecidable" or $\Sigma^1\_1$-hard is really undecidable? In the latter case, why is it included inside decidable PSPACE? (or I misunderstanding things...)

# Answer
> 7 votes
The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy.

The similarities are obvious, both notations talk about formulas with increasing quantifier complexity. The important distinction is that the polynomial hierarchy talks about bounded quantification, i.e. your space is limited (the witnesses must be of polynomial size). If the quantification is not bounded you have much more power, e.g. a formula for "program $p$ halts on input $x$" can be written in a $\Sigma\_1$ form, which means that the halting problem is in the first level of the arithmetical hierarchy.

To avoid confusion the levels of the polynomial hierarchy are actually denoted by $\Sigma\_i^p$, however when it is obvious from the context the $p$ is usually omitted. Note that the superscript in $\Sigma\_1^1$ means that the quantification is over sets, which puts it above any level in the arithmetical hierarchy with quantification over the naturals.

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


# Question
Title: Does this proof work for infinite regular languages
My proof was deemed false because it does not work for infinite regular languages, but I don't understand why.

Prove: "If we remove one string from any nonempty regular set, the resulting set is still regular.

I used to lemmas:

* A set containing only one string is trivially a regular language
* The union operator is closed in the class of regular languages

Given these two lemmas, I made the claim that any regular language $L$ can be written in the form $$L = \bigcup\_{e \in L}\\{e\\}$$

Then, one picks an arbitrary string $r \in L$ to remove, and expresses $L$ in the same manner with $r$ distinct: $$L = \bigcup\_{e \in (L - \\{r\\})}\\{e\\} \cup \\{r\\}, \quad r \in L$$

Finally, we simply remove $r$ from the union and obtain: $$L' = \bigcup\_{e \in (L - \\{r\\})}\\{e\\}$$

$L'$ is also regular by the two lemmas introduced earlier.

# Answer
The problem with your argument is in the interpretation of the second lemma. Closure under union says "If $L\_1$ and $L\_2$ are regular languages, then $L\_1\cup L\_2$ is regular." By induction, then, the union of any *finite* collection of regular languages is regular. You cannot, however, conclude that the union of an arbitrary collection of regular languages is regular, as Raphael pointed out, since your observation $$ L=\bigcup\_{e\\,\in\\, L}\\{e\\} $$ is true for *any* language at all, regular or not, so since a single string language is regular, then *every* language would be regular.

---

What you could do is exploit some other closure properties of regular languages. For instance

1. If $L\_1$ and $L\_2$ are regular languages, so is $L\_1\cap L\_2$.
2. If $L$ is a regular language, its complement $\overline{L}$ is too.
3. We can thus write the set difference $A\setminus B$ as $A\cap\overline{B}$ so regular languages are closed under set difference.
4. If $L$ is any regular language and $e\in L$ is any string in $L$, then $L\setminus \\{e\\}$ must also be regular.
> 2 votes

# Answer
The problem is that you don't actually *show* anything.

*Every* language can be expressed as union of singletons. So being able to write down $L'$ as such does not show it's regular. For all we know, it may not even be recursively enumerable.
> 1 votes

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


# Question
Title: How to compute all primes between upto $n$ in time $O(n)$ time?
Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$.

1. For $j=2$ to $j=\sqrt n$
2. mark multiples of $j$ from $A$

Running time of this algorithm is $O(n \log n).$ It is easy to see that after first iteration there will be $n/2$ many unmarked elements and so on.

**The problem with this method is that some of the elements may be marked more than one time.**

**Question :** How to compute all the primes upto $n$ in $O(n)$ time?

# Answer
> 5 votes
You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.

---
Tags: algorithms, enumeration, primes
---


# Question
Title: Proof of contention of the wait-free consensus algorithm
I know that this is a known theorem but I can't find its proof. The theorem is:

> The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write operations) is $n$.

Can someone link me to a proof or an explanation?

# Answer
This is the classical "critical-state argument", also called "bivalence argument", used by Fischer, Lynch, and Paterson to prove the impossibility of consensus in an asynchronous message-passing system where one processor may fail.

For (wait-free) binary consensus, the critical-state argument says that there must exist a state S of the system such that both decisions are still possible starting from S, but for every immediate successor S' of S the decision is determined. Thus we can partition the processors into two teams $\Pi\_0$ and $\Pi\_1$ such that a step of a processor from team $\Pi\_0$ from S eventually results in decision 0 while a step of a processor from team $\Pi\_1$ from S eventually results in the decision 1.

Now suppose that, in S, the next step of processor $p\_0$ is to modify object $O\_1$, and the next step of processor $p\_1$ is to modify object $O\_2\neq O\_1$. Wlog we can assume $p\_0\in\Pi\_0$ and $p\_1\in\Pi\_1$. Since $O\_2\neq O\_1$, the steps of $p\_0$ and $p\_1$ commute and lead to the same state S'' regardless of their order. Moreover, since $p\_0\in\Pi\_0$, the consensus decision from S'' is 0. However, since $p\_1\in\Pi\_1$, the consensus decision from S'' is also 1, which is a contradiction.

The case in which some processors are about to perform a pure read operation similarly leads to a contradiction.

We conclude that in state S, all processors are about to modify the same object. Thus in any consensus algorithm there is at least one system state in which all processors are about to modify the same object.
> 3 votes

---
Tags: algorithms, reference-request, proof-techniques, concurrency
---


title: Where is PCP(1,1) located?

text:
# Question
Title: Where is PCP(1,1) located?
The PCP-Theorem states that $PCP(log(n), 1) = NP$. So can anyone explain, where $PCP(1,1)$ is located in relation to other classes? My thoughts:

$P \subseteq PCP(1,1) \subseteq PCP(log(n)) = NP$ Is there some theorem like "$P \neq NP \implies PCP(1,1) ...$" What is the relation to the probabilistic classes like $BPP$ and $RP$?

# Answer
$PCP\left(O(1),O(1)\right)=P$.

Suppose you are allowed to toss at most $r$ coins, and that the proof length is bounded by $l\in\mathbb{N}$. Given input $x$, you can compute the acceptance probability of the verifier relative to any proof in $\\{0,1\\}^{\le l}$. To do this, for every proof $\pi\in\\{0,1\\}^{\le l}$ and every possible outcome of the random coins $w\in\\{0,1\\}^r$, simulate $V^{\pi}(x,w)$ and count the number of $w$'s who caused $V^\pi$ to accept. Note that this requires only polynomial time in $|x|$. Now, accept $x$ iff during this process you have found a proof $\pi$ which causes $V$ to accept $x$ with probability $1$.

Note that the constant bound on the proof length does not immediately follow from the definition (in the above you only have a constant bound on the number of queries), but follows from the fact that if $L\in PCP(r(n),q(n))$, then $L$ has proofs of length $\le 2^{r(n)}q(n)$. See this question for details.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: NP completeness proof of sensor selection problem
There are $n$ points in a plane.

The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from the selected set of points.

I am trying to use the sensor coverage problem where the idea is to place sensors in the plane where all $n$ points are reached. However, it allows the sensors to be placed at non-$n$ points which my problem doesn't allow. Is there some way I can still show that the problem is NP-complete by subset selection or any other approach.

Thanks!

# Answer
> 1 votes
Your problem is an instance of a geometric cover problem. Specifically, it appears to be very close to the discrete unit disc cover problem (just scale down all distances by a factor of $d$), which is apparently NP-hard but also admits reasonable approximation algorithms.

---
Tags: np-complete, np-hard, np, set-cover
---


title: Finding common structure in strings

text:
# Question
Title: Finding common structure in strings
I don't even know the right words to describe my problem, so I'll start with an example:

"aabaa", "ccrcc", "ffaff" are equivalent to some extent, because they all have the same length and follow the same formula: twice one letter, once another letter and finally twice the first letter again.

As I said, I lack even the vocabulary to describe this commonality of structure, so the first part of my question is: what is this kind of structure called and how is it studied?

The second part of my question is: do you know of an algorithm to transform a string into a representation of its structure? Or maybe more simply, an algorithm that would assess if two strings share the same structure?

# Answer
What you're describing seems to be isomorphisms between strings. (Note that there happens to be a more complicated notion that is also called 'string isomorphism', but that isn't what we're talking about here.)

You can 'describe the structure' of these strings as follows: replace each character with the number of different characters excluding itself before it in the original string. If you do this for the three strings you mentioned, you get the string '00100' in all three cases.

This also gives an algorithm to test whether two strings are isomorphic: apply the above transformation on both strings and test whether the results are equal.
> 3 votes

# Answer
This is an instance of an equivalence relation.

Consider the following transformation. Replace the first (leftmost) letter in the word (and all its occurrences) with '0'. Then replace the next letter that you haven't touched yet with a '1'. And so on.

For instance, 'ccrcc' is transformed to '00100'.

This transformation gives you a canonical form: if two words have the same structure, after this transformation, the result will be the same. So now you can detect equivalence by examining the transformed version.
> 1 votes

---
Tags: algorithms, strings
---


# Question
Title: How can I make a pipeline with undefined/unlimited stages?
I've been told that if you understand a pipeline then you should be able to make it with any depth, but I can only do 4 stages and *maybe* 5 if the memory is not too slow. How can I learn how to make infinite pipelines?

# Answer
> 1 votes
The thing about the MIPS/DLX-ish pipeline that you're probably talking about is that all of the pipeline control is central. There is a pipeline/hazard circuit which knows what's going on everywhere, and it does all the hard work.

This is probably why you asked the question: you can already see that there is no way this will scale!

There are three main techniques to construct a deep pipeline:

* Nest pipelines and use hierarchical control.
* Eliminate central control by making control as local as possible.
* Reduce the need for control by designing the pipeline so that some situations that would require control never happen, or turn into an easier-to-handle control situation.

We'll take a look at these in turn, but bear in mind that all of these techniques can be mixed and matched as appropriate.

**Hierarchical control**

This is the simplest modification to what you've already seen. The idea here is that each logical unit in a CPU (e.g. instruction fetch unit, integer unit, load/store unit) may be a small pipeline by itself. Then you can decide what control needs to happen within that unit and what control needs to happen between units.

If you think about an instruction fetch unit, for example, there are various reasons why it might stall: it might be experiencing a cache miss, it might be recovering from a mispredicted branch, or whatever. In many situations, the control for the core as a whole may not care *why* the IFU is stalling, it only matters that it *is* stalling, because that means it isn't supplying instructions to the next stage. So the IFU may implement its own control, and communicate with higher-level control using coarser signals.

An extreme example of this is to use a coprocessor design. Coprocessors don't have to be on separate chips; the MIPS architecture uses a coprocessor for the MMU, for example. It isn't really a separate processor, but it is wired up to the core's control system as if it were.

This was an especially popular technique back in the day when CPUs came on more than one physical die such as POWER1.

**Local control**

Based on the previous idea, another way of coordinating different units is to just let them communicate with their surrounding units. There will probably still need to be some central control, but this could be reserved for large-scale events such as recovering from a fault or bad speculation.

So, for example, a unit which can't take any more work at the moment (whether it's because it's doing a multi-cycle operation, stalled on a cache miss, or stalled because the unit it needs to send a result to is itself busy) might simply provide a signal which says "I cannot take any more work right now". Any unit which wants to feed it work looks for that signal.

Another example of something that could reasonably be called "local control" is to use busses with arbitration. You can move data through the CPU using busses, and if two units want to write to the same bus at the same time, they decide between them that one will back off. You might use this in a Tomasulo pipeline.

An extreme example of local control is the counterflow pipeline. This is an example of a pipeline which can be arbitrarily deep using *only* local control, to the point where the pipeline could in principle be made completely asynchronous.

**Redesign**

If it is possible to eliminate the need for control by redesigning the pipeline, this is always worth considering. The classic example is register renaming, which effectively eliminates WAR hazards for registers. If a hazard is impossible, there doesn't need to be any control for it!

There are endless variations on this theme. For example, register renaming when there aren't "enough" physical registers available turns the WAR hazard into a stall in the rename stage. A stall early in the pipeline may be easier to control than a hazard late in a deep pipeline, because there are fewer cases to consider.

Another variation is to use speculation with a general recovery mechanism. If you think of a SPARC/MIPS-like pipeline, there is a delay slot after every branch, which is only possible because the pipeline is short. In a deeper pipeline, the most common solution is to speculate the branch and then use a general pipeline recovery mechanism if we got it wrong.

It's a similar story with instructions that could fault. Any memory access could cause a page fault. Any division could be a division by zero. We effectively "speculate" that this didn't happen, and fall back on the general recovery mechanism if it actually did. That way we don't need special control for a page fault.

A good place to start on this is Mike Johnson's book *Superscalar Microprocessor Design* (1991). It's old but it's full of good stuff that explains how these sorts of things actually work in practice.

---
Tags: cpu-pipelines
---


# Question
Title: Reservoir sampling algorithm probability
I'm reading about the reservoir sampling technique called *Algorithm R*.

The idea is we can take a sample of size $n$ from a population of size $N$ even when $N$ is unknown/too expensive to retrieve in $N$ time. I quote a sample implementation from wikipedia:

> ```
> (*
>  S has items to sample, R will contain the result
> *)
> ReservoirSample(S[1..n], R[1..k])
>  // fill the reservoir array
>  for i = 1 to k
>      R[i] := S[i]
>
>  // replace elements with gradually decreasing probability
>  for i = k+1 to n
>    j := random(1, i)   // important: inclusive range
>    if j <= k
>        R[j] := S[i]
>
> ```

The explanation for why this works:

> The algorithm creates a "reservoir" array of size $k$ and populates it with the first $k$ items of $S$.

That is pretty clear, the first for loop in the code sample does that. Then:

> It then iterates through the remaining elements of $S$ until $S$ is exhausted. At the $i$-th element of $S$, the algorithm generates a random number $j$ between $1$ and $i$. If $j$ is less than or equal to $k$, the $j$-th element of the reservoir array is replaced with the $i$-th element of $S$.

Also clear. But here comes the Math:

> In effect, for all $i$, the $i$-th element of $S$ is chosen to be included in the reservoir with probability $\frac{k}{i}$.

Hmm, I'm probably not well versed enougn in probablility theory, so can someone explain in more detail how the probability is $\frac{k}{i}$?

What I also don't get: do all elements have the same chance of being included in the (final) reservoir? From my understanding, it seems like the probability decreases for the elements at the end of $S$ to be included, then the reservoir will be skewed towards including the earlier elements, or am I misled?

# Answer
The whole reason for performing this sampling method is to get an uniform sample even if the population size is unknown at the start. So, if this method works, the probability cannot be skewed.

What happens, is that the samples chosen in the beginning have a chance to be overwritten by the samples chosen later. Intuitively, this balances it somewhat. But we must show that this 'balance' holds precisely:

The probability of $\frac{k}{i}$ refers to the probability that sample $i$ is added to the reservoir, as it is added when a uniform random integer from $\[1,i\]$ is less than $k$, i.e. $k$ positions in the range $\[1,i\]$ lead to inclusion in the reservoir. (Total number of events is $i$, number of events that we 'want' is $k$, all events are equally likely, so final probability is $\frac{k}{i}$)

Now what is the probability that $i$, when chosen, remains in the reservoir until the end? It gets removed when a single integer in the range $\[1,m\]$ is picked, for all $i\<m\leq N$. The probability that it doesn't get replaced at position $m$ is $1-\frac{1}{m}$. As these events are independent, the total probability that $i$ doesn't get replaced is $\prod\_{m=i+1}^N (1-\frac{1}{m}) = \frac{i}{N}$ $^\*$. As $i$ is in the reservoir at the end if it gets picked and not replaced, this probability is $\frac{k}{i}\cdot \frac{i}{N} = \frac{k}{N}$.

We're not done yet, as the calculation above only holds for the samples not originally in the reservoir. However, that case is similar: as they are always put in the reservoir, we only need the probability they stay, which is $\prod\_{m=k+1}^N (1-\frac{1}{m}) = \frac{k}{N}$.

So the probability of being included in the final sample is the same for all positions, which means the final sample is uniform.

\*: The expression $\prod\_{m=i+1}^N (1-\frac{1}{m})$ can be simplified as follows:

\begin{align}\prod\_{m=i+1}^N (1-\frac{1}{m}) &= \prod\_{m=i+1}^N (\frac{m-1}{m})\\ &= \frac{i}{i+1}\cdot\frac{i+1}{i+2}\cdots \frac{N-2}{N-1}\cdot \frac{N-1}{N}\\ &= i\cdot\frac{i+1}{i+1}\cdot\frac{i+2}{i+2} \cdots \frac{N-1}{N-1}\cdot \frac{1}{N} =\frac{i}{N}. \end{align}

It is also possible to show by induction on $N$, but I think the previous is more insightful.
> 8 votes

---
Tags: algorithms, probability-theory
---