# Question
Title: Is effective solvability a coherent and/or useful concept?
I am aware of Turing's proof of the undecidability of the halting problem (and I think I understand it). What I'm asking is quite different. I shall define what I mean by "effectively solvable":

> A problem $P$ is **effectively solvable** if there exists an agent $A\_P$, such that for any specific instance of $P \\, (P\_i)$, $A$ can solve that instance of the problem $(P\_i)$ in a finite time.

Imagine $A\_P$ as a superintelligence with unbounded (but finite) computational power, and unbounded (but finite) memory. $P$ is effectively solvable if $A\_P$ would eventually (in finite time) produce a correct solution for any given instance of $P$.
It may be the case that there does not exist any algorithm that "solves" a certain class of problems say sigma $\*$ problems (suppose that sigma problems are a certain kind of mathematical problem). However, this does not mean the problem is not effectively solvable. For any given sigma problem, a sufficiently intelligent agent (or sufficiently competent mathematician) may be able to eventually find its solution(s) (or determine that no such solutions exist) using an (**unbounded**) number of mathematical tricks. The mathematical methods applied to sigma problems is limited only by the creativity of the agent concerned. There are essentially an infinite number of strategies, from which a finite subset may be drawn from in sequence (forming an algorithm) to apply to a particular sigma problem.
Effective solvability (or effective decidability) is different from the traditional notion of decidability in that problem that are effectively solvable do not require a finite number of steps which always guarantee a solution. In fact, for each instance of an effectively solvable problem, a different algorithm may be used. There may be no general algorithm that solves all instances of a problem, but for each instance of the problem, a tailor made algorithm may exist.
Going entirely off my intuition here, I think the following is a definition of "effectively solvable":

> A problem $P$ is effectively solvable for $A\_P$ if $\not\exists$ an instance $P\_i$ of $P | A\_P$ does not solve $P\_i$ in finite sequence of steps.

**OR:**

> A problem $P$ is effectively solvable if $\forall$ instances $P\_i$ of $P$, $A\_P$ can correctly solve $P\_i$ in finite time.

If there is a tailor made algorithm for every instance $P\_i$ of a problem $P$, then a sufficiently intelligent agent can in practice solve every instance of the problem (by searching solution space for said algorithm when confronted with that instance of the problem). Thus even if in theory no general solution to the problem exists, in practice, specific solutions to each $P\_i$ always exist (provided the above criteria is satisfied).
While some of such problems may be "undecidable", they are in actuality (for all practical purposes) "effectively solvable".
The set of effectively solvable problems is a superset (and I believe that it is a proper superset) of the set of decidable problems.
I do not know whether the halting problem is effectively solvable (I'm starting to believe that it's not). That's not my major interest though (I am curious to the answer) What I am truly interested in is effective solvability.
I am interested in effective solvability, because the range of problems that can be solved by an AI is not (necessarily) the range of problems that can be solved by a Turing machine, but the range of problems that are effectively solvable. I feel that the traditional (Turing) notion of decidability is insufficient when the computer is a sufficiently (pun intended) intelligent agent. Thus when we ask the question:
"What problems can a computer solve?"
I feel the set of effectively solvable problems and not (necessarily) the set of decidable problems is the answer.

> What are some problems that are not effectively solvable by your definition?

I do not know of any, and I suspected there may be none. To hazard a guess however:

1. Problems which may involve randomness may not be effectively solvable. In particular if the computer gets the right answer, but doesn't know it got the right answer, then it can never solve that instance of the problem. Such problems are thus not effectively solvable.
As a concrete example of such a problem, imagine a machine delta. Delta is non deterministic. Delta (uses its input) to randomly select/construct an arbitrary Turing machine $M$. Delta halts if $M$ halts, and delta runs forever if $M$ runs forever. Does delta halt in a particular input is not effectively solvable.
2. Any problem for which there exists a single instance of the problem for which there does not exist in algorithm that always produces the correct answer for that instance of the problem are not effectively solvable.
In general, non deterministic problems may be not effectively solvable.

Let the sufficiently intelligent agent be Omega. For the problem that Omega is tasked to solve, Omega can solve instances of that problem even if Omega does not have a general algorithm for all instances of the problem. Omega can craft a tailor-made solution (algorithm) to any specific instance of a problem. Let all tailor-made algorithms (TMAs) Omega uses on instances of any problem use steps that come from a (countably) infinite set $S$. Consider the set of all finite sequences of steps from $S$, let's call this $T$. $T$ is the set of all possible TMAs that Omega can use on any instance of $S$. $T$ can be thought of as the "toolkit" of Omega. When Omega encounters a particular instance of a particular problem (for which Omega has no general algorithm to solve), Omega crafts a TMA to solve that particular instance. This crafting can be thought of as Omega selecting a TMA from $T$.

$T$ is countably infinite. Thus Omega's actual operation is selecting an algorithm from an infinite set of algorithms whenever faced with a particular instance of a problem. However, Omega has only finite memory. Thus, Omega never actually stores $T$ in memory. What happens is that whenever Omega faces a certain $P\_i$, Omega tries an algorithm to solve that $P\_i$. This algorithm may be generated on the spot. However, if Omega faced an infinite number of $P\_i$s for some $P$, then it could be seen how Omega employs an infinite number of TMAs to solve each instance of $P$.

It may very well be the case (and it probably is), that Omega selects TMAs from a subset (finite or infinite. The set of TMAs I can draw from in attempting a solution is infinite, but most of that set would contain ineffective algorithms, and I don't actually consider them. The set of TMAs I draw from is most likely finite, though as it is a function of my knowledge, experiences etc, it may be unbounded).
As Omega increases in intelligence, the set of TMAs it can draw from becomes increasingly larger (as meaningful as this concept is when the two sets (if both are infinite) have the same cardinality). Higher intelligence gives Omega a larger toolkit.
When we say Omega can effectively solve $P$, we're saying that if Omega was fed sequences of some $P\_i$ endlessly, that there would never come a $P\_i$, for which Omega would fail to solve $P\_i$ in a finite time. It is this sense in which we consider Omega hypothetically attempting all $P\_i$, in which it becomes useful to think of Omega has having an infinite set of algorithms from which it can draw from.
Omega is not a hyper computer or Turing oracle, and may be safely thought of as a Turing machine (or equivalent model of computation). Omega is only faced with specific instances of a problem, and does not need to have a general solution of the problem to be considered as effectively solving it.
Assume Omega can effectively solve $P$, but does not know a general algorithm to solve $P$. If for each $P\_i$, Omega adopts $t\_i$, then you could construct a method for solving $P$ as follows:

> If $P\_i$, then do $t\_i$.

However, if the sets of all instances of $P$ is an infinite set, then the above method would also contain an infinite number of steps. Does, the above method is **not** an algorithm.
Yet, it may be the case that Omega does not have a general algorithm for solving $P$, but there does not exist some $P\_i$, which Omega would not solve in finite time.
Effective solvability can be seen as asking if there is an infinite sequence of steps that solve the problem in the general case. Thus, if a problem is effectively solvable, there may be no algorithm that solves that problem (as such an algorithm would need an infinite number of steps). It is because effective solvability permits methods which contain an infinite number of steps, that I assert that the space of effectively solvable problems is a superset of the space of Turing decidable problems. It is why I draw the distinction between effective solvability and Turing decidability.
The way I think of Omega employs the concept of Vingean uncertainty. The more intelligent Omega is, the more confident I am that Omega would reliably achieve its goals (in this case solve specific instances of specific problems) and the less knowledge I possess of the particular steps Omega would take in achieving it's goals.
Omega is of arbitrarily high intelligence. If I am to ask the question of "What problems can Omega solve?", then the space of all effectively solvable problems seems like the correct answer to me (I am very convinced that the space of Turing decidable problems may be a wrong answer).

---

# Tl;Dr

Let's say we have a super intelligent AI of arbitrarily high intelligence with unbounded (but finite) processing power and unbounded (but finite) memory called Omega. Omega is implemented on a Turing machine (or other equivalent model of computation). When Omega is faced with an instance $P\_i$ of a problem $P$, being sufficiently intelligent, (unless that instance of the problem is unsolvable)Omega can craft a Tailor Made Algorithm (TMA) $t\_i$ to solve said $P\_i$. It may be the case that there does not exist a $P\_i$, which if faced with, Omega would not successfully craft a $t\_i$ to solve it in unbounded (but finite) time. In this case, while Omega cannot decide $P$, we say that Omega can effectively solve $P$.
If Omega can effectively solve $P$, then an algorithm to solve $P$ in the general case can be crafted as follows:

> If $P\_i$ then do $t\_i$.

However, if the set of instances of $P\_i$ is infinite, then the algorithm described above is infinite. Thus, even if Omega does not have an algorithm to solve the decision problem in the general case, it can effectively solve that problem.
This relies on there being no instances of the problem that are themselves not decidable. If for all instances of the problem it is decidable, then it **might** be effectively solvable. I used "of arbitrarily high intelligence because if an agent is sufficiently intelligent, then giving them unbounded (but finite) processing power, unbounded (but finite) memory, and unbounded (but finite) time would let the agent solve that instance of the problem.

---

# Questions

## Does a concept of effective solvability already exist?

## Is effective solvability a coherent concept?

## Is it a useful concept?

Please point me in the right direction to do further study on effective solvability.

# Answer
By your definition, all problems with defined finite solutions are effectively solvable. Just set the algorithm $A(P\_i)$ to be "output $x$", where $x$ is the solution to $P\_i$. For example, the algorithm you would use to solve the instance of IS\_PRIME on 37 is "output yes."

Now the algorithm picking algorithms to apply is uncomputable, but you said you didn't care about that.
> 7 votes

# Answer
I don't totally understand the question, but I think that the answer is this:

**Theorem:** Let $\\{A\_i\\}$ be a sequence of Turing Machines such that $A\_i$ computes $f(i)$ on an empty input. Then there exists a single Turing Machine $T\_f(x)$ that computes $f$.

You also have the ability to build Turing machines that interlace, like so:

1. Run $A\_1$ for one step
2. Run $A\_1$ for two more steps
3. Run $A\_2$ for two steps
4. Run $A\_1$ for three more steps
5. Run $A\_2$ for three more steps
6. Run $A\_3$ for three steps

...

Stop when $A\_x$ finishes and return what it returned.

---

I think that you misunderstand the meaning of the word computable. If you can deterministically solve a problem with pencil and paper, then that problem is computable. The definitions happens to encapsulate what a computer can do, but that's not where it came from. In particular, nothing in the following quote is correct

> I am interested in effective solvability, because the range of problems that can be solved by an AI is not (necessarily) the range of problems that can be solved by a Turing machine, but the range of problems that are effectively solvable. I feel that the traditional notion of decidability is outdated when the computer is a sufficiently intelligent agent (one may make the argument that machine learning already renders traditional decidability obsolete as far as this problem is concerned

It is conceivable that the computable functions are not exactly the same as the function that can be actually calculated by a physical computer, but that has nothing to do with AI or Machine Learning. Those things do not increase the realm of things solvable by a computer.
> 4 votes

# Answer
> A problem $P$ is **effectively** solvable if there exists an agent $A\_P$, such that for any specific instance of $P$ ($P\_i$), $A$ can solve that instance of the problem ($P\_i$) in a finite time.

This definition hinges entirely on what you define an "agent" to be. If $A\_P$ is a Turing machine, then your definition is identical to the usual notion of decidability. An infinite (countable) computable sequence of Turing machines cannot decide anything that a single Turing machine can't decide.

Alternatively, you could define $A\_P$ to be some kind of oracle that can magically choose the appropriate algorithm. But you have to specify what kind of oracle it is, so as not to trivialize the definition. (For instance, as others have already pointed out, any instance of any problem can be "solved" by the trivial algorithm that simply prints the correct answer.) And you seem to be interested in a class that corresponds to real, implementable machines, which rules out oracles.
> 2 votes

# Answer
Your notion of effectiveness implies a physical (material) criterion of verification. Keep in mind that computational models, albeit $-$ to some extent $-$ materially realizable, are nonetheless essentially mathematical in nature. In other words, they try to be *ahistorical*.

An example might help clarify the issue. We know the solution to the Busy Beaver problem up to 4 states. Generic approaches (which included computer algorithms) have helped those who attempted to solve the problem in this limited version, by greatly reducing the problem space, but in the end they had to rely on their ability to analyse every single remaining Turing machine, to see how it behaves. In that effort, they had to treat them as singular problems, *not anymore as members of a problem set*.

So, what you see is that, from a (meta)mathematical point of view, this problem that we still view as a set, is in fact grouped only by its definition, but cannot be associated to a single formalized strategy of resolution. This means that the identity of the hipothetical agent that solves all instances of the problem can only be given historically, and your attempt at giving an abstract characterization of it is inevitably aporetic (meaning that it leads nowhere).
> 1 votes

---
Tags: computability, undecidability, computation-models
---


# Question
Title: Is it possible to construct 3-dimensional microchips?
In our daily computer, the microchips in it are 2-dimensional, but could it be possible to produce 3-dimensional ones, in some way similar to the brain structure?

# Answer
Yes, it's possible to build 3-dimensional integrated circuits: we already know how to do that, and many chips already use 3D integration.

Building chips whose structure is similar to the brain structure is a different question. Circuits on current chips (whether 2-dimensional or 3-dimensional) are very different from the structure of the brain.
> 3 votes

# Answer
I don't see the point. For better neutral networks, you need better connectivity between processors, which can be done with parallel processing. You also need machine learning algorithms that are o optimized for the hardware. But, you could theoretically build a processor, many of them inextricably linked to each other for better processing. Really, only time will tell.
> 1 votes

# Answer
The latest chips are from more than 10 layers. The layers are constructed essentially with advanced photography.

In the earlier eras of the chip manufacturing, there was also a different technology common: ion implantation. It works by shooting the target wafer with accelerated ions. Their penetration depth was much higher as the current photographyical technologies. The technology has became rare today, mainly on engineering and cost/profit predictability reasons.

However, the current chip technology has a limit: to make photography, we need to be able to mirror photons. With ultraviolet light it is yet possible, but with rontgen, it is practically not. There is no matter what could reflect it, and it has unavoidable physical reason. The current last developments are going into the high ultraviolet spectrum, with extreme costs. After that, the development will stop.

However, also the number of the layers of the current chip production could be increased, or the ion implantation could get space again. Thus, a major development into this direction is not closed out in the future, although the current cutting edge is the tuning of the EULV.

You would have problems with their cooling - a $\mathrm{cm}^3$ silicon cube, from millions of layers, can be cooled like a $\approx \mathrm{cm}^2$-sized traditional chip. Having a such a "3d-chip", it should be cooled by some very exotic way (like having a lattice of cooling channels in it), or the chip itself should be very exotic to avoid the heat problem.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Using Pascal's Triangle to implement queues and stacks using heaps
I have the following question as homework in an algorithms, analysis and data structures class:

And here's an answer I wrote up:

> A queue is a first-in-first-out data structure. A heap is a data structure that makes searching for objects in a sortable space faster than linear search.
>
> Now, every data structure needs to implement at least four basic operations: create, read, update, and delete. In this case, create would add an object to the queue-heap, read would return information about an object in the queue-heap, update would change somevalue in an object in the queue-heap, and delete would remove an object from the queue-heap.
>
> Because the public interface of this data structure is presented as a queue, there are several design considerations to make: should it be possible to read objects only from the front of the queue? What about the middle of the queue? The back? And so on for creating ( or inserting ) objects in the queue, updating, removing and so on. Similarly, the public interface ought to implement methods such as "get next" or "pop front", "get previous" or "pop back", "cycle to next", "cycle previous", and so on.
>
> In fact, one might argue that the only invariant property of a queue is that it records some sense of order amongst objects: regardless of how the queue got in any given state, at any given moment some object is first, some other object is second, another object is third, and so on.
>
> So, we have to record order.
>
> Suppose you put objects in the heap not based on their value, but rather gave each object a natural number corresponding to its order in the queue. Then, the root element of the heap would be position one in the queue, the root's left child would be the second item in the queue, the root's right child would be the third element in the queue and so on.
>
> Now, when we try to implement queue-like methods such as "get next", "get previous", etc. we have a problem: given any object in the heap, if we are asked to get the object to the left or the right in the queue, we have to somehow interpolate from the object's place in line ( a natural number ) how to traverse the parent, children, siblings, and cousins in order to return the correct object.
>
> Notice, however, that there is a neat bijection from each object's place in the queue ( a natural number ) to the n-choose-k address of a slot in Pascal's Triangle: the first object in the queue is zero-choose-zero, the second object is one-choose-zero, third is one-choose-one, the fourth is three-choose-zero, the fifth object is three-choose-one, the seventh is three-choose-three, the eighth is seven-choose-zero, and so on.
>
> Here are the first few elements of the bijection again written as a sequence: \< (0,0), (1,0), (1,1), (3,0), (3,1), (3,2), (3,3), (7,0), ..., (7,7), (15,0), ... \>
>
> In other words, the place of an object in the queue is determined by the bijection f(n,k) = n + k + 1.
>
> So, rather than recording the place of an object in the queue via natural number, record it on the object using the tuple, n-choose-k address of a position in Pascal's Triangle.
>
> Similarly, store metadata about the queue-heap on the main data structure itself. Namely, the tuple, n-choose-k address of the last element in the queue, a pointer to the object that is currently considered the front of the queue, etc. ( You could also cycle objects so that the object at the front of the queue is always at the root of the heap, but that might be less efficient than simply abusing space consumption, procedurally cycling through the queue using arithmetic on n-choose-k tuples, and running garbage collection based on some sort of load factor. )
>
> Some of the queue-like methods could be implemented like this:

```
procedure queueHeap.getNext():
    if this.current.n == this.current.k:
        next = this.read(2^(this.current.n + 1) - 1,0);
    else
        if isEven(this.current.k):
            next = this.current.parent.rightChild;
        else:
            next = this.current.parent.parent.rightChild.leftChild;

    return next;

```

> procedure queueHeap.read(n,k) can use modular arithmetic and relationships between the n-choose-k addresses of the object under a "read head" and the object being sought to navigate from the root of the heap to the object being sought directly.
>
> So, it is possible to implement a queue as a heap using n-choose-k tuples as addresses as well as a stack. ( A stack would merely present different methods on the data structure's public interface to give the end user a sense of first-in-first-out ordering. )

Is this implementation correct? Is it novel? Is it efficient?

# Answer
I assume that the data stuctures given are abstract. They can only be updated using their interface operations.

A *(fifo) queue* has indeed `init`, `enqueue(item)` "at the end", `dequeue(item)` retrieve "from the beginning" and the test `isempty`. Upto small personal preferences.

I also think that the *heap* here means the binary heap implementation of the *priority queue*, which keeps a set of items with their piorities, and has similarly `init`, `add(item,prio)` any item , `delmax(item)` remove the item with maximal priority and the test `isempty`. Perhaps also `getmax(item)` to look at the maximal element without deleting.

That's all. No explicit positions you can look at or refer to. Positions are used in implementing the data structures usually using an array (for binary heap, or fixed size queue) or a pointer list.

For me the only feasible way to implement a queue using a heap is to use the priorities to get the elements in the same order as the linear order of the queue. Start with priority zero for the first element added, and decrease the priority for each next element, so that the first element always has highest priority and is retrieved using `getmax` to implement `dequeue`.

As you are given a heap, perhaps you are also allowed to use the standard operations that move the elements up and down the heap, as part of the implementation. However these operations are also priority based and do not explicitly look at positions, so I do not see much advantage here.
> 2 votes

---
Tags: algorithms, data-structures, heaps, counting, queues
---


title: Does $n\log n = O(n \log n + n)$ hold?

text:
# Question
Title: Does $n\log n = O(n \log n + n)$ hold?
> Does $n\log n = O(n \log n + n)$ hold?

I don't think it does trivially because I think as $n$ grows larger, $n\log n$ will converge to one value, and as the $+ n$ grows, $n\log n + n$. But I am uneasy about my initial thoughts about this. For example, mergesorting a list and then iterating through each element to compare for the smallest difference would result in a running time of $O(n\log n+n)$, yet mergesort is $O(n\log n)$.

# Answer
I'm not sure what do you mean that "$n \log n$ will converge to one value" because in fact $\log n$ diverges to infinity (so is $n \log n$).

Recall that $f(n) \in O(g(n))$ iff exists constants $c, N$ so that $f(n) \leq c \\, g(n)$ for every $n \geq N$ (intuitively, $f(n)$ could be bound above by a constant multiple of $g(n)$ as $n$ grows large enough).

$n \log n \in O(n \log n + n)$ is then obviously true since $n \log n + n \> n \log n$.

It is worth noting that the other side $n \log n + n \in O(n \log n)$ also holds because $n \leq n \log n$ as $n \geq \mathrm{e}$, so choosing $(c, N) = (2, \mathrm{e})$ proves this.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Computer Networks: Does integrity depend on confidentiality?
I'm taking the course computer networks and we currently had our second lecture. We got the following question:

> What are the differences between integrity and confidentiality of a message? Is confidentiality possible without integrity? What about integrity without confidentiality? Explain.

From what I understand the main difference between confidentiality and integrity is that "confidentiality" should prevent from spying on the message / intruders. And "integrity" is to ensure that the original message hasn't been altered in any way (modification/deletion/insertion).

What I'm unsure about: Does confidentiality mean that a possible interuder can't decode the ciphertext, or does this mean he can't even intercept the cipher?

To the two questions about the dependecies of integrity and confidentiality: At first I thought: If an intruder can't intercept the message (break confidentiality), there's no way he can alter the message in any way (break integrity). But the more I think about that, the less certain I become. Especially when I think about deletion of a message.

Thanks a lot in advance for clearing things up.

> P.S: I hope "confidentiality" and "integrity" are the right terms in English. We learned "Vertraulichkeit" & "Integrität" in German.

# Answer
Confidentiality means that only the sender and receiver know the message. We ensure confidentiality by encrypting the message.

Integrity roughly means that the message being sent cannot be modified in transit. In more detail, it means that there is a way for the receiver to check that the message has not been tampered with. We ensure integrity by adding a hash or checksum to the message.

The two properties are completely independent:

* Confidentiality without integrity: Suppose I am sending you a cryptographic key, encrypted using a key we share. An attacker replaces the message with garbage having the same format. You will not notice any difference. The attacker has no way to read the original message, but they can modify it without you knowing it.
* Integrity without confidentiality: I can send you a signed message by encrypting a hash of the message using my private key. Anybody can verify that the hash matches the message using my public key, but I'm the only person who can sign it. There is no way to modify the message without invalidating the signature, but the message itself is free for all to see.
> 0 votes

---
Tags: computer-networks, integrity
---


# Question
Title: Figuring out the language accepted by a DFA?
I have been asked to give a formal description of a finite state machine. I have tried for over five hours to minimize it, to understand what gets accepted, and what gets refused, to no avail. I really am in need of help. If solving the problem does not seem reasonable, I would really appreciate any tips to attack this problem. The machine looks as such:

Things I've tried: I tried minimizing it, but the minimized version no longer accepts the same language. I tried looking at what gets accepted. I looked at how one can reach state q1 (through loops and what not), and how one can reach state q4 (through the same idea). When I tried this, I couldn't find a reasonable answer. Example:

For q1: 4 ways to get to q1:

a run of a's,

loops of the manner (q1-\>q2-\>q3-\>q1),

loops of the manner (q1-\>q2-\>q4-\>q3-\>q1),

and loops of the manner (q1-\>q2-\>q4-\>q3-\>q2-\>q4-\>q1).

I would follow a similar thought process for arriving to q4. However, I can't seem to write a language that encompasses all of the possible combinations of these, along with the union of the two. I appreciate any help. Thank you very much.

EDIT: My attempt at minimizing the state machine :

I look at the state diagram of the state machine, which looks something like the following:

The 0 equivalence looks like this: \[Q2 Q3\] \[Q1 Q4\]

1 equivalence looks the same

This means we only have two states. I'll denote \[Q1 Q4\] by A, and \[Q2 Q3\] by B. Initial and final state is A, and the other is B, which is not final.

A on a goes to A, A on b goes to B.

B on a goes to B, B on b goes to A.

resulting in the following state machine:

In the initial machine, bbb is accepted, but not in the minimized version. Hence, I don't know where I went wrong.

# Answer
> 1 votes
The DFA is already minimal. In the table below, I give words which separate all pairs of states: $$ \begin{array}{c|c|c|c|c} & q\_1 & q\_2 & q\_3 & q\_4 \\\hline q\_1 & & \epsilon & \epsilon & b \\\hline q\_2 & \epsilon & & ba & \epsilon \\\hline q\_3 & \epsilon & ba & & \epsilon \\\hline q\_4 & b & \epsilon & \epsilon & \\ \end{array} $$ As for the language accepted by this DFA, the best I got is $$ \begin{align\*} &(a^? (a^{even} b)^+ a^{odd} b)^\* a^\* + \\ &(a^? (a^{even} b)^+ a^{odd} b)^\* a^?(a^{even} b)^+a^{even} b, \end{align\*} $$ where $a^? = a + \epsilon$, $a^{even} = (aa)^\*$, $a^{odd}=a(aa)^\*$, and $r^+ = rr^\*$.

There might be a simpler description.

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


# Question
Title: modular arithmetic in rolling hash algorithm
My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we still get the right answer. Is there any mathematical theroem anyone could quote which would help me understand?

So i get,

```
xi = (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1
xi+1 = (xi - (ti)R^0)/R + (ti+m)R^M

```

but whats the guarantee,

```
xi = [ (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1 ] mod Q
xi+1 = [ (xi - (ti)R^0)/R + (ti+m)R^M ] mod Q

```

.. and so on will be correct even after introducing mod Q

Pretty sure its some basic mod arithmetic theorem i am missing here.

# Answer
What you are missing is the identity $$ (a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}. $$
> 2 votes

# Answer
The video actually does it the other way around, kicking out the term with the highest power and then multiplying by R. It turns out to not really make a difference, but this is clearly always possible regardless of whether modular arithmetic is used or not.

Going back to what you wrote though. Without the modular arithmetic, the division by R is possible because the dividend is a multiple of R (it was carefully constructed to be).

With the modular arithmetic, the division by R is possible because R and Q are chosen such that $\gcd(R, Q) = 1$, therefore R has a modular multiplicative inverse modulo Q and can *always* be divided by. As a bonus, dividing by R becomes a multiplication, which is easier than integer division even if it is by a constant.
> 2 votes

---
Tags: modular-arithmetic, rolling-hash
---


# Question
Title: Is it necessary to learn how to prove Mathematical theorems as a CS Student?
I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:

> **Problem 4.** If a set, $A$, is finite, then $|A| \< 2^{|A|} = |\cal P(A)|$, and so there is no surjection from set $A$ to its powerset. Show that this is still true if $A$ is infinite. *Hint:* Remember Russell's paradox and consider $\\{x \in A \mid x \notin f(x)\\}$ where $f$ is such a surjection.

My question is: am I expected to prove these math theorems and should I focus on my proving skills (because they are proving to be quite difficult for me at the moment)? Do they make me a better problem solver in later courses such as Data Structures and Algorithms?

# Answer
Writing computer programs that work *is* a theorem proving activity. Full stop.
> 3 votes

# Answer
There are several different ways to answer your question.

First, in the particular course you are taking now, part of the material is mathematical proofs. In order to succeed in this course, you need to be able to prove mathematical theorems. There are several reasons for this requirement:

* Some more advanced classes also involve proving theorems.
* The concept of proof and mathematical validity is important even if you don't expect to actively prove theorems. You need to understand the difference between a heuristic algorithm and an algorithm which is *guaranteed* to always work efficiently.
* Programming is an abstract pursue, and requires a certain way of thought. Mathematics is one way to develop this way of thought, since it forces you to think in abstract terms.

Second, while more advance proofs do involve a lot of problem solving, in this particular problem you are handed out the solution, and your task is to convert the hint into a formal proof (in the sense of your class). At this stage of your class, you are not required to be able to create completely new proofs. Rather, the emphasis is on you understanding *what* is a mathematical proof and *how* it is written. Later on you might be given more creative tasks.

Third, the course you're taking will also teach you basic mathematical concepts that might be useful for you in the future. For example, one of the topics you are taught is propositional logic. You could encounter propositional logic in database theory, verification, and elsewhere. The only way to understand such an abstract concept is to play with it, and the way we play with concepts in mathematics is by proving simple statements.

Fourth, you mention that proving theorems is hard for you at the moment. This is why you're taking this class. One goal of the course is to teach you how to prove theorems. You might find it hard, but if the course goes slowly enough, you will eventually find it easy, and will have gained an invaluable skill. In a similar vein, you might have encountered the jump in difficulty level from high school to undergraduate studies. It requires some adjustment, but eventually you will gain the relevant studying skills.
> 2 votes

# Answer
Computer Science as it's taught in universities has a large overlap with applied maths. If you want to succeed in your coursework you have to be able to prove mathematical theorems. A strong foundation in maths is required to do original research (or even understand existing results!) in many fields of computer science. Universities traditionally prepare their students for research.

This is very different from working as a software engineer, where mathematical skills are almost completely unnecessary. You can write great, useful software without understanding basic proof techniques. Almost all software is incredibly mundane when viewed from a science point of view. The hard part in software engineering usually is taming complexity and understanding user requirements.
> 2 votes

# Answer
A (probably incomplete but too long for a comment) thought of a student:

I never understood the bad blood between students and the proofs. To me, they are the real essence behind the theorems: a theorem is just a claim, the proof is the reason why that claim is considered a theorem.

Every time I see a proof, I try to understand how the author thinks about that particular topic. Of course, sometimes often it can be hard, but the more time you spend on studying proofs the more you learn.

Long story short: the proofs are the difference between science and magic.

---

To answer your question: **yes**, you will see theorems (and their proofs) everywhere during your courses (mathematical sciences are built up theorem by theorem), and **yes**, they will teach you how to reason, and hence you will become a better problem solver.

---

Ironically, the major current challenge in computer science is really about proof: informally, it asks whether *proving* something is more difficult than *checking* the correctness of a proof. Since the answer is believed to be yes, this teach us an important thing: don't just check the proof step-by-step (which is easier) but really try to understand what is going on.
> 0 votes

---
Tags: logic, proof-techniques, discrete-mathematics, propositional-logic
---


# Question
Title: Pseudo random, unqiue integer numbers in a given range
I need an algorithm that gives me integer numbers with the following features:

* Numbers must be in a given range $\[n..m\]$;
* Numbers must be returned in pseudo-random order (random at visual inspection is enough; it is more important that numbers are well distributed over the given range);
* Numbers may not repeat before each number in the range $\[n..m\]$ has been returned once;
* Range may be huge (up to $2^{64}$; this excludes all list/shuffle based algorithms);
* It should be possible to seed the function so it returns numbers in different order on repetition;
* Algorithm should be as fast as possible and should return in constant time.

I wrote code that uses table based bit swapping and optionally XOR and/or addition. It works very well for bit-aligned $n$ and $m$. However it is a bit slow and if the range $n..m$ is not aligned to bits (i.e., $n$ other than $2^x$ and $m$ other than $2^y$), I get either gaps within the returned numbers or extremely non-constant runtime behavior.

How can this be solved?

# Answer
Without loss of generality, we can assume you need numbers in the range $\\{0,..,n-1\\}$. (Just add the appropriate offset.)

This can be solved by constructing a random permutation $f:\\{0,\dots,n-1\\} \to \\{0,\dots,n-1\\}$, then outputting the values $f(0),f(1),f(2),f(3),\dots$ as your sequence of pseudorandom numbers. Those numbers won't repeat until each number in the range has been defined. If $f$ can be computed efficiently, this will be fast.

So how do we construct such a random function $f$? One approach is to use format-preserving encryption, a technique from cryptography that allows you to construct a function $f$ that is a bijection on the set $\\{0,\dots,n-1\\}$ (for any $n$ of your choice), and that appears pseudorandom. There are many FPE algorithms.

See https://blog.cryptographyengineering.com/2011/11/10/format-preserving-encryption-or-how-to/ and https://crypto.stackexchange.com/questions/tagged/format-preserving for more (e.g., https://crypto.stackexchange.com/q/41450/351, https://crypto.stackexchange.com/q/504/351, https://crypto.stackexchange.com/q/29073/351, https://crypto.stackexchange.com/q/20035/351, https://crypto.stackexchange.com/q/16561/351, https://crypto.stackexchange.com/q/18988/351).
> 4 votes

# Answer
You can use a Linear Feedback Shift Register to generate a maximum length sequence that cycles through all numbers that fit into the size of the LFSR without repetition. This is used in computer games for the so-called Fizzlefade effect. LFSRs are really efficient, so this might fit your performance requirements.

(This is of course a special case of the general technique mentioned by D.W.)
> 1 votes

---
Tags: pseudo-random-generators, random-number-generator
---


# Question
Title: What does $\omega{(1)}\cdot O(logN)$ mean?
What does $\omega{(1)}$ mean as a factor? In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$. In this example, what is the meaning of the additional factor $\omega(1)?$

# Answer
It presumably means a product of the form $f(N)\\,g(N)$, where $f(N)\in\omega(1)$ and $g(N) \in O(\log n)$.

However, that's a very strange thing to write, since *every* well-behaved function $h$ can be written in this way. If $h\in\omega(1)$, write it as $h(N)\cdot1$, which is valid, since $1\in O(\log N)$; if $h\in O(1)$, write it was $N\cdot (h(N)/N)$.
> 6 votes

---
Tags: asymptotics
---


# Question
Title: Example of decidable set whose preimage is not decidable
I know that if a set is a decidable, there exists an algorithm that enumerates it and prints value 1 if a given element belongs to the set and 0 otherwise. Therefore, its image is decidable, too. I think, though, that this is not true for the preimage of of the set under a partially computable function. Can someone provide an example that might help me to understand it, please?

# Answer
> 2 votes
Consider the set $S$ consisting of everything, and the partially computable function $f$ which on input $n$ simulates the $n$th Turing machine, returning whatever the machine outputs (if it ever halts!). The preimage of $S$ under $f$ is the set of all halting Turing machines, which isn't decidable.

---
Tags: computability
---


title: Regular Expression converted to NFA

text:
# Question
Title: Regular Expression converted to NFA
Hello, all,

First time poster, here. Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular expression to a nondeterministic finite automaton. The regular expression is given as:

(0 union 1)\* 000 (0 union 1)\*

Which I interpret as:

"Any number of 0's or 1's, followed by 000, followed by any number of 0's or 1's."

This is the solution that I came up with:

However, the professor of this course I am taking provided a solution, albeit unsimplified, that is different from mine. I am wondering where I went wrong. I have asked this same question to my professor via e-mail (distance ed.), but since I am not expecting a reply based on past experience, I have also asked this question here. Any help you can provide would be greatly appreciated.

# Answer
> 2 votes
Notice that the word 000 is not accepted by your automaton. To see why your automaton is wrong. Look at the strongly connected component that includes the initial state (the first two states in your figure, lets call them $q\_0$ and $q\_1$). This component is meant to read the (0|1)\* prefix. Hence, you must be allowed to get out of this component(i.e., guess when to start reading the 000 part of the word) from either $q\_0$ or $q\_1$. To fix your solution, you should add a transition, labeled with 0, from $q\_0$ to the third state in your figure (lets call it $q\_3$). Or you can replace the whole component with a single state q. such that q is initial, has a self-loop labeled with 0,1 and has a transition, labeled with 0, to $q\_3$.

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


# Question
Title: Trying to solve the recurrence relation by comparing 3 cases of master theorem
I am trying to understand how the master theorem is invoked on the following recurrence relation:

$$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$

So basically, I found the following source where they have Master theorem definition defined.

I found the similar solution (See the Link #1 in the comment below) where they are trying to solve the same problem (Problem #c). I

In the solution, they have mentioned the following :

We have :

n0.5logb(a) = nlogb(6006)1/2

= n0.5log2(6006)1/2

and so on and so forth. I am not able to understand how they compared the results with the given equation.

# Answer
You determine $a$, $b$, and $f$ using pattern matching.

The Master theorem applies for recurrences of the form

$\qquad\displaystyle T(n) = a T(n/b) + f(n)$;

you have

$\qquad\displaystyle T(n) = \sqrt{6006} \cdot T(n/2) + n^{\sqrt{6006}}$.

Just by comparing the two formulae, you determine that

$\qquad\begin{align\*} a &= \sqrt{6006},\\ b &= 2, \quad\text{and} \\ f &= n \mapsto n^{\sqrt{6006}}. \end{align\*}$

Now you go through the three cases and check which applies (if any). See also here.
> 3 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Canonical representation of finite maps on non-overlapping finite rational intervals
I would like to have a canonical representation of a map from rational intervals (f, t\] with f, t ∈ ℚ to some irrelevant value type. These intervals are non-overlapping and there exist only finitely many such keys in the map. I would like to be able to implement the following functions on this representation:

1. Lookup by rationals (not by ranges, as it is unclear what exactly that would mean)
2. Insertion by ranges. This will partial overwrite existing intervals (which are split in the process)
3. Compare two maps for equality by comparing their representation.
4. Create an empty map.

Particularly interesting are cases such as inserting two adjacent intervals with the same value V. I think for the map to be canonical, this case would have to be indistinguishable from inserting the joined interval with value V.

As always with (me and) canonical representations, I have failed to come up with any good leads on google (scholar). Is anyone aware of a result for this particular problem? I would be very thankful for any pointers to papers or implementations.

# Answer
It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests. I'll describe how below. (If you care about theoretical worst-case complexity, there are some caveats, but those caveats can probably be ignored for practical implementation.)

You can handle the lookup, insertion, and creation operations using a balanced binary search tree on the endpoints of the intervals. If you have $n$ intervals, you'll have at most $2n$ endpoints, so you have a balanced tree on $O(n)$ leaves. Lookup and insertion can be done in $O(\lg n)$ time, using an appropriate balanced tree data structure, which is efficient.

Ensuring it has a canonical representation is difficult; I don't know how to do that, while ensuring efficiency. The standard data structures don't have a canonical representation: there are many possibilities for the structure of the tree, for any given contents, and they use these degrees of freedom to help make the operations efficient.

But we can still support the "equality-test" operation efficient, without needing a canonical representation. We'll construct a custom hash function, which produces a hash value $H(f)$ based on the contents of the map $f$ (regardless of the underlying structure of the tree or how the map is stored). Then we can do efficient equality tests: given two maps, we compare their hashes. If their hashes are different, we know they are different maps. If their hashes are the same, we can compare them exhaustively; with a reasonable hash function, the chances of two different maps yielding the same hash will have negligible probability. If you use a cryptographic-strength hash, that possibility is so exponentially rare that you can use a simpler procedure: if the hashes match, then the maps match, and there's no need to check any further. This yields a procedure that is $O(1)$ time to compare equality in practice.

So how do we build the hash function $H$? We'll use an associative hash function. Let $(G,+)$ be an abelian group, and a conventional hash function $h:\\{0,1\\}^\* \to G$. Suppose the map $f$ maps the interval $\[\ell\_i,u\_i\]$ to the value $v\_i$ for $i=1,2,\dots,n$. Then we'll define the hash of $f$ to be

$$H(f) = \sum\_{i=1}^n h(\ell\_i,u\_i,v\_i).$$

Notice that the hash value depends only on the map itself, and not on the structure of the tree used to store the map.

We'll update the hash of the map each time that we update the data structure. This is easy to do, thanks to the structure of $f$ and the fact that $+$ is commutative (since $G$ is abelian). If the map $f'$ is defined by removing an interval $\[\ell,u\] \mapsto v$ from the map $f$, then their hashes are related by

$$H(f') = H(f) - h(\ell,u,v),$$

which can be computed in $O(1)$ time. Similarly for adding an interval that doesn't overlap any other intervals. Adding an interval that overlaps an existing interval (triggering a split) can be done by deleting the existing intervals and adding in the new intervals. Each of these operations takes $O(1)$ time.

(Alternatively, you can choose a non-abelian group $G$ and then augment the binary tree: in each node, you store the hash of the map that corresponds to the subtree rooted at that node. In this way you can update the hash values for all nodes each time you update the tree.)

It remains to instantiate the hash $H$ by choosing an appropriate group $G$ and an appropriate hash $h$. I suggest that you use a cryptographic hash function for $h$, such as SHA256; that way you can treat collisions as effectively impossible in practice. You can find analysis of how to choose the group $G$ in the cryptographic literature: see https://crypto.stackexchange.com/q/11420/351, https://crypto.stackexchange.com/a/17936/351, and https://crypto.stackexchange.com/q/8615/351.
> 2 votes

# Answer
Here is another solution. You can use the SeqHash data structure in the following paper:

VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich. CCS 2014.

The SeqHash data structure is a tree-based data structure that lets you store a sequence of numbers. You can do each of the following operations in at most $O((\log n)^2)$ time: create an empty sequence; find the $i$th number in the sequence; concatenate two sequences; compare two sequences for equality; extract a prefix or suffix or any consecutive range of the sequence.

We can use this to implement what you want.

1. First, to store a set of ranges, we extract the endpoints of the ranges, put them in sorted order, and store that sequence in SeqHash. Thus if the ranges are $\[x\_1,x\_2\], \[x\_3,x\_4\], \dots$, we store the sequence $x\_1,x\_2,x\_3,x\_4,\dots$ in SeqHash.
2. Second, we augment the data structure to store the mapping: if the range $\[x\_i,x\_{i+1}\]$ maps to the value $v$, we store the value $v$ with the left endpoint $x\_i$ of the range in the SeqHash data structure. Thus, each leaf in the SeqHash data structure stores not only the number $x\_i$ but also the value $v$ its corresponding range maps to (or null, if $x\_i$ is not the left endpoint of a range).
3. Third, insertion is supported as follows: to insert a range, we find where the spot where it will go using binary search, then extract the prefix before the spot and the suffix after the spot, then concatenate the prefix, the new range, and the suffix. Thus we implement insertion using concatenation.

This then yields a solution to your problem.
> 2 votes

---
Tags: data-structures, intervals, equality
---


# Question
Title: Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively
Given integers $g, h, k, n$ how to find the smallest integer with $k\ 1$-bits that is the sum of two integers with $g, h\ 1$-bits respectively. Moreover, all three numbers (summands and sum) can have at most $n$ bits, i.e. the result is the n-bit number with $k\ 1$'s and $(k - n)$ zeros, for instance $\underbrace{0...0}\_\text{n -k}\underbrace{1...1}\_\text{k}$. These $1$-bits don't have to be consecutive. Of course, such a number may not exist at all. You can think of this output integer (if it exists) as a permutation of a set of $n - k$ zeroes and $k$ ones.

I have a strong feeling that this is a dynamic programming problem but I can't get what is a subproblem here. I actually have no clue about DP relation for this problem. Could anyone give me some hints?

**UPDATE.** I've came up with the following plan:

Let $dp(g, h, k, n, carry)$ be such a sum, where $carry$ is an optional bit for carrying. Then $dp(g, h, k, n + 1, 0)$ = $min\\{dp(g,h,k, n,0),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 0) \\2^n + dp(g,h,k - 1, n,1)\\ 2^n + dp(g - 1, h, k-1, n, 0), \ \ :(1, 0) \\ 2^n + dp(g, h - 1, k - 1, n, 0), \ \ :(0, 1) \\}$

$dp(g, h, k, n + 1, 1)$ = $min\\{dp(g - 1, h, k, n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(1, 0) \\ dp(g, h - 1, k , n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 1) \\ dp(g-1,h-1,k, n,0)\ \ \ \ \ \ \ \ \ \ \ \ \ \ :(1, 1)\\ 2^n + dp(g - 1, h - 1, k - 1, n, 1)\\}$

I realized that this is too complex for me to handle on my own. I don't know what are the initial values (or base case of recursion in top-down approach) of this DP-table should be. Provided $g + h = k \leq n$ it is obvious that $dp(g, h, k, n, ?) = 2^k - 1$. As the question mark indicates, I don't understand what to do with the optional carrying bit in this case. I do not really understand how I should indicate there is no such sum, etc. Also, how to fill this DP-table? Should I use top-down approach? I need further help to proceed.

# Answer
> 2 votes
We are looking for a sum $z = x + y$, where $z$ has $k$ bits set, $x$ and $y$ have $g$ and $h$ bits set, and $z$ is as small as possible. We assume $g ≥ h$. A solution can be found directly, without any dynamic programming.

We add the numbers $x$ and $y$ from the lowest to the highest bit, taking carries into account. If we add two bits 0 + 0 without a carry, these bits can be removed without changing the number of bits set, but making the result smaller.

We can also take any pairs where we add 1 + 0 without carry, or 0 + 1 without carry, and move those pairs to the lowest bit positions. This doesn't change the number of bits set, but moving a 1 bit in the result to a lower bit position will not make the result larger, but may make it smaller.

Now if we add two bits 0 + 0 with carry, then we can remove these bits as well, but it is slightly more complicated. Obviously we can remove them if they are the highest bits. Otherwise, since adding 0 + 0 with or without carry does not produce a carry, and we removed all pairs 0 + 0 without carry, and moved all pairs 0 + 1 or 1 + 0 without carry to the lowest bit positions, the next higher bits must be 1 + 1. Adding 0 + 0 with carry gives a result of 1 and no carry, then adding 1 + 1 without carry gives a result of 0 with a carry. If we remove the two 0 bits, then we add 1 + 1 with carry, which gives a result of 1 with a carry. The number of bits set is unchanged, but a zero bit is removed in the result, making the result smaller.

So we are adding any number of pairs 0 + 1 or 1 + 0, then we may have a pair 1 + 1 producing a carry, followed by any number of pairs 1 + 1, 1 + 0 or 0 + 1. Starting with the addition 1+1 we will always have a carry, and adding 1 + 1 with carry produces a 1 with carry, while adding 1 + 0 or 0 + 1 with carry produces a 0 with carry. Reordering these pairs makes no difference to the number of bits set, but by moving all pairs 1 + 1 as far as possible to the lower positions we move 1-bits to lower positions in the result, making the result smaller.

Adding the initial 1+0 and 0+1 pairs produces exactly one bit set in the output for each bit set in the input. Adding 1+1 produces 0 output bits; each further pair produces one output bit set less than the input bits, and finally one bit will be set in the output from the final carry. If this optional range consists of j pairs, then we lose j output bits (for example, 111 + 111 = 1110, j = 3, six bits set in the input, 3 bits set in the output).

We see that we have no solution if $k \> g + h$. If $k = g + h$ then one optimal solution is $x = (2^g - 1)·2^h$, y = (2^h - 1).

If $k \< g + h$, then we let $j = (g + h) - k$. We need to lose exactly $j$ bits set, so the range of bit producing carries must be $j$ bits long. In this range, from j+1 to 2j bits are initially set; we get the smallest possible sum if we have as many pairs 1+1 as possible. If g + h ≤ j then there is no solution. We construct the numbers x, y as follows:

We have $a$ 1+1 pairs, where $a = min (k, j, h)$. Then we add $b = j-a$ pairs at higher and $c = k - a$ pairs at lower bit positions. Of these pairs, we have $g-a$ pairs 1+0, and $h-a$ pairs 0+1.

As an example: Let k = 10, g = 14, h = 3. j = 7, a = min (k, j, h) = min (10, 7, 3) = 3, b = j-a = 7-3 = 4, c = k - a = 10 - 3 = 7. We have

```
x =   1111 111 1111111
y =   0000 111 0000000
z = 1 0000 110 1111111

```

# Answer
> 1 votes
The subproblems are *roughly*: Given integers $g',h',k',n'$, find the smallest $n'$-bit integer of weight $k'$ which is the sum of integers of weights $g',h'$. Here $g' \leq g$, $h' \leq h$, $k' \leq k$, and $n' \leq n$. (You also need to worry about carry from the addition, which is where the *roughly* comes in.)

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Expressing statements on elephants in propositional logic
If I wanted to create a sentence like:

> African elephants can carry coconuts; Asian elephants cannot.

How would I do that with propositional logic?

# Answer
> 2 votes
If you're willing to consider predicate logic (with predicates and quantifiers), there's a plausible way to express this. Let $P(x)$ stand for the proposition "$x$ can carry coconuts". Let $S$ denote the set of African elephants and $T$ denote the set of Asian elephants. Then one interpretation of your sentence is

$$\forall x \in S . P(x) \quad \land \quad \forall y \in T . \neg P(y).$$

Propositional logic doesn't allow quantifiers or predicates; I don't see any reasonable way to express that sentence in pure propositional logic.

Important caveat: logic is not a way of encoding all English sentences. It is not intended as a model of conversational language. Rather, it is a way of making precise certain mathematical subjects, and supporting a particular type of mathematical reasoning. So don't expect it to be more than it is.

# Answer
> 0 votes
lacking a better context and restraining this to propositional logic you can only do this:

p: African elephants carry coconuts q: Asian elephants carry coconuts

Then what is given can be restated symbolically as $p; \neg q$
or
$p \land \neg q$ depending on how you interpret the original prompt.

# Answer
> 0 votes
You can divide a sentence into three core statements:

$a$: "$X$ is African elephant";

$b$: "$X$ is Asian elephant";

$c$: "$X$ can carry coconuts".

So, now you can make a formula from this: $(a\rightarrow c)\land(b\rightarrow\overline c)$.

---
Tags: propositional-logic
---


# Question
Title: When you do a remote desktop connect to another pc which pc's processing power do you have?
Are you just accessing the data and things on the PC you are connecting to or, if it had a better processor/ram/etc, are you able to take advantage of that?

# Answer
When you remote desktop into another computer you are actually using that computers hardware. You are not running a virtual machine of that computer, which would take your main computers resources.
> 2 votes

---
Tags: computer-networks
---


# Question
Title: What's the difference between $O(1)$ and $o(1)$?
What's the difference between $O(1)$ and $o(1)$ ?

# Answer
A function is $O(1)$ if it is bounded from above. It is $o(1)$ if it tends to zero. Any function which is $o(1)$ is also $O(1)$.

For example, $\sin^2 x$ is $O(1)$ but not $o(1)$, and $1/x$ is both $O(1)$ and $o(1)$.
> 7 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Enumerable disjoint subsets whose union is equal to the union of the sets
I'm given that two sets, $A$ and $B$ are enumerable. I have to show that there exist subsets $A \supset C$ and $B \supset D$ ($C$ and $D$ also enumerable) such that $C$ and $D$ are disjoint and $A\cup B = C \cup D$. I was thinking to take $A=B=\\{0,1\\}$ and define $C=\\{n : f(n)=1\\}$, $D=\\{n: f(n)=0\\}$. Do you think this is right?

# Answer
> 3 votes
This answer assumes that *enumerable* means *recursively enumerable*.

Here is an enumerator for $C$:

* Run enumerators for $A,B$ in parallel.
* Whenever the enumerator for $A$ outputs a word, check whether the word has already been enumerated by the enumerator for $B$; if it hasn't, output it and continue.

The enumerator for $D$ is defined symmetrically.

# Answer
> 2 votes
Can you use the fact that a subset of an enumerable set is enumerable? If you can, then you could choose $C=A$ and $D=B\setminus A$ (set difference). Then $C$ and $D$ are enumerable and it's easy to show that $A\cup B=C\cup D$.

---
Tags: computability, semi-decidability
---


# Question
Title: Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$
Which of the following sounds better (or more rigorously):

1. x grows with $N^2$ or
2. x grows with $O(N^2)$ or
3. x grows quadratically with $N$.

# Answer
> 3 votes
The three options have different meanings in mathematics:

1. The first option means that $x$ increases as $N^2$ increases.
2. The second doesn't really make sense.
3. The third has the meaning you are presumably after (perhaps "with" is better replaced by "in").

You can rephrase the first two options as follows:

1. $x$ grows as $N^2$ - this is informal, and doesn't differentiate between $x \sim N^2$ and $x = \Theta(N^2)$.
2. $x$ grows as $O(N^2)$ - this is an awkward phrasing, and it is better to use symbols: $x = O(N^2)$. Note, however, that this is *not* the same as your third option - it corresponds to $x$ growing *at most* quadratically in $N$. To get the same meaning, you have to use big Theta: $x = \Theta(N^2)$.

You mention rigor. Rigor is a property of proofs, whereas here there are no proofs. Your descriptions might be informal, but could help explain rigorous proofs.

The best two options are "$x$ grows quadratically in $N$" and $x = \Theta(N^2)$". Both are acceptable.

---
Tags: terminology, asymptotics, landau-notation
---


# Question
Title: What is the algorithm for Blockchain's Byzantine Fault Tolerance?
This person was asked: "Why is a blockchain implementation different than a distributed consensus system like Raft?"

In part of their answer they replied:

> For one, Raft is not Byzantine fault tolerant, i.e., not designed to account for arbitrary failures. If a participant fails by telling different peers different things, consensus fails. In context of blockchain, this would be equivalent of a malicious consensus participant lying.

Another wrote:

> As others have mentioned, Blockchain has Byzantine Fault Tolerance. Raft and other consensus based systems such as Paxos do not.

My question is: **What is the algorithm for Blockchain's Byzantine Fault Tolerance?**

# Answer
> 4 votes
Actually the differences are more intricate than that. A problem here might be that the properties of "blockchains" are not very well specified and the term is used for a wide variety of things (going as far as simple databases) for marketing. So let's see what is out there.

When you are designing a fault tolerant system there are multiple properties to take into account. These include:

**Crash or byzantine failures**

> Should the system be designed to withstand nodes just stopping to do anything (i.e. no messages at all) or should it also consider nodes which exhibit arbitrary behaviour?

**Eventual or strong consistency**

> Should the system provide certainty, that some state is final and not revertible or are we okay with irreversibility with high probability?

**Open or closed membership**

> Is it known in advance (and to all nodes) who is participating in the protocol? E.g. a reliable database used by google has a defined number of nodes, which are known to all other nodes. In Bitcoin it is unclear even how many miners are participating in the consensus algorithm.

There are a few more things, but these are the most important ones. I am regularly contacted by people who want to use blockchain technology and the conversations always come down to figuring out what requirements regarding these three properties they have and then I recommend some system.

For the most well known ones the properties are:

* Bitcoin / Ethereum: Byzantine failures, eventual consistency, open membership
* RAFT / Paxos: Crash failures, strong consistency, closed membership
* PBFT / Zyzzyva: Byzantine failures, strong consistency, closed membership

When choosing a system you try to take the easiest one possible, as the stronger models normally come with a large penalty in latency and throughput for transactions.

Crash failures are easier than byzantine failures. This is easy to show, as byzantine failures include crash failures. Most of the algorithms include some kind of voting. Having a majority is sufficient with crash failures to make decisions, while byzantine failing nodes might send different votes to different receivers. This might lead to two honest nodes seeing different results for the overall vote and getting out of sync.

Open membership is much more difficult than closed membership, as sibyl attacks, where an attacker generates many identities need to be counteracted by something like proof-of-work or proof-of-stake. This is the main new thing Bitcoin invented and that created the blockchain hype. A chain of blocks of transactions has existed before, as batched commits of transactions was a standard thing for at least 20 years before Bitcoin.

Applying this to the algorithms I listed:

The overhead of RAFT is small, PBFT and Zyzzyva already have a significant amount of communication overhead ( O(n^2) messages and a large number of signatures). Systems like Bitcoin and Ethereum have latencies in the order of minutes to hours (depending on your required level of security).

---
Tags: algorithms, fault-tolerance, blockchain, byzantine
---


# Question
Title: Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$
This is my take :

Epsilon ---\> 1

0 --\> 2

01 ---\> 3

10 ---\> 4

11 ---\> 5

001 ---\> 6

010 ---\> 7

. . .

So therefore we can count them.

But based on this video : https://www.youtube.com/watch?v=oe-ZAJQz9Cc&index=5&list=PLsFENPUZBqiqbnD-WatYxUhRWLMNDoMun

They should not be countable, but i did not understand that video, the guy says all possible languages over $\\{0,1\\}^{\*}$ are uncountable!

# Answer
The language $$L= (0+1)^\*$$ (the set of all strings over $0$ and $1$) is countable. Furthermore, any subset of $L$ is also countable. However, the set of all sublanguages of $L$ $$S = P(L) = \\{M \mid M \subseteq L\\}$$ (a set of sets in fact) is not countable. This video proves this using the diagonalization argument.

$S$ and $L$ are two different sets. In fact, $L$ is a member of $S$.
> 3 votes

---
Tags: formal-languages, uncountability
---


# Question
Title: Choosing $n$ points to get the closest sum
Let's say there is a set of $N$ real numbers, $x\_i, i\in\\{1,2,...,N\\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, $y$, i.e. minimising $$ f(J) = \left\[y - \sum\_{j\in J}x\_j \right\]^2 s.t. ~J \subset \\{1,2,...,N\\} ~\mathrm{and}~ |J| = n $$ To get the exact solution, I think this is an $NP$ problem, so is there any random algorithm to find the (approximate) solution reasonably fast?

# Answer
> 2 votes
Round the $x\_i$ into multiples of $(\epsilon/n) N$ (for a parameter $\epsilon \> 0$ of your choice) which we will denote by $y\_i$, and use dynamic programming to solve your problem for the $y\_i$ in time $O(n^2N/\epsilon)$, coming up with a set $J$. Since $\sum\_{j \in J} |x\_j - y\_j| \leq \epsilon N$, this will go you the correct answer up to an additive error of $\epsilon N$.

(Ricky Demer suggested the same solution in the comments to the post.)

---
Tags: algorithms, optimization, randomized-algorithms
---


# Question
Title: Find all group of neighbors with a constraint weight
Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs.

I have nodes that have weights with each other. I want to find all unique groups of nodes, with the constraint that every node in the group has a weight with every other node a value that is less than a certain pre-specified constant.

Let's take an example. The following is a table of weights where the row number and column number can be considered as node numbers.

```
6   15   25    4    6    1    4
15  28   19   20   15   28    6
25  19    4   26    2   10    2
4   20   26   15    1   15   29
6   15    2    1   13   20   15
1   28   10   15   12    5   16
4    6    2   29   15   16    7

```

Considering a weight limit of 15 the result I generated using my brute force solution looks like the following:

```
1  5  4
1  6  4
1  7  5  2
1  7  6
2  7  5  3
3  7  5
3  7  6
4  5
4  6
5  7
6  7

```

Now consider the first result `1 5 4` the weight between 1 and 5, w(1,5)=6; w(1,4) = 4; w(5,4) = 1. we can't add node 6 to this group because w(5,6) = 20.

The solution I have now takes forever when the dataset is larger. Is there an optimized algorithm that I am missing? Thanks for the help.

# Answer
Your problem is the same as listing all cliques in a graph.

Given your weight matrix, construct a graph in which two vertices are connected if the weight between them is below the threshold. A clique in this graph is the same as the sets of vertices you are interested in.

A graph could contain exponentially many cliques - even exponentially many maximum cliques (consider for example $n/3$ paths of edge-length 2). So in general you will need exponential time to list all cliques.
> 2 votes

---
Tags: nearest-neighbour
---


# Question
Title: Is the equality of two DFAs a decidable problem?
So given two DFAs, is the problem of finding if they generate the same language a Decidable problem?

I already know that Equality of two CFL is not Decidable

but what about Equality of two DFAs? considering most of the problems with DFAs are decidable, is this decidable as well ?

# Answer
> 23 votes
In order to decide whether the languages generated by two DFAs $A\_1,A\_2$ by the same, construct a DFA $A\_\Delta$ for the symmetric difference $L(A\_1) \Delta L(A\_2) := (L(A\_1) \setminus L(A\_2)) \cup (L(A\_2) \setminus L(A\_1))$, and check whether $L(A\_\Delta) = \emptyset$.

Here are some more details. You can construct $A\_\Delta$ using the *product construction*: construct a product automaton, and use $(F\_1 \times \overline{F\_2}) \cup (\overline{F\_1} \times F\_2)$ as the set of accepting states.

In order to check whether $L(A\_\Delta)$ is empty or not, it suffices to check whether some accepting state is reachable from the initial state, and this can be done using BFS/DFS.

# Answer
> 4 votes
Given two DFA $D\_1$ and $D\_2$, equality of of $D\_1$ and $D\_2$ and checking if $D\_1$ and $D\_2$ generate the same language are same things.

Yes, this problem is decidable. You can minimize both $D\_1$ and $D\_2$ and compare their transition functions. Given a DFA, the minimization algorithm reduces the number of states to a minimum number and this DFA is unique. Here is alternative approach.

---
Tags: computability, automata, finite-automata, decision-problem
---


# Question
Title: Does overclocking a cpu speed up a poorly optimised process?
*Perhaps this isn't exactly a computer science question, but I thought this wouldn't strictly fit in Electrical Engineering either. Let me know if I should move this somewhere else*

Suppose I have a process that is single-threaded and rather poorly optimised. It doesn't max out my processor, and instead stays stuck at around 20% usage. Would overclocking my CPU even really affect the running speed?

# Answer
Optimization is not really something that should be guessed at. Instead you need to measure what is going on to determine the chokepoints and where changes need to be made.

A faster processor may have little or no effect especially since the CPU utilization is not maxed out. CPU speed affects only those parts of the program which are actually running on the CPU. If the program is waiting for something else such as an I/O operation, a faster CPU doesn't help. The chokepoint is not the CPU speed but rather the I/O speed.

So you may have a faster CPU but that just means that your program gets to a place where it has to wait for something else to happen a bit faster. If your program requires user input then no matter how fast the CPU, the program is still bounded by the speed of a human doing the input.

Program speed also is affected by the algorithms being used. A faster CPU may help a bad algorithm go faster, a kind of linear increase, a better algorithm may provide several orders of magnitude improvement in speed and performance.

Another possible throughput increase can come from multi-threading. This only really helps if you can divide out the overall problem into multiple, asynchronous tasks that can be run simultaneously and the results of each task combined when all are done. The more need there is for synchronizing tasks and events the more likely that multi-threading will not provide that much of an improvement.

With multi-threading there is always the question of how many separately running cores are in the CPU or how many CPUs are being used for the program.

Multi-threading with a single core on a single CPU may or may not help since the various threads are sharing the same core and CPU. It depends on whether some threads are able to progress while other threads are waiting for some resource or event to happen such as I/O to complete.

If you are able to divide out the program into multiple threads and assign the different threads to different CPU cores or multiple processes and assign the different processes to different CPUs then more things can be happening simultaneously. However if all those threads are not compute intensive and are waiting rather than running then it may not make that much difference.

Finally the actual hardware design can make a large difference in the throughput of a CPU. Overclocking a CPU means that it is running faster however it is the same hardware. The differences in throughput between various CPU generations is not due to just CPU clock speed. There are also hardware improvements so that two CPUs with the same clock speed will show very different processing throughput because the hardware design of one is superior to the other. This is where design details such as branch prediction, prefetch, size of the onboard cache, and other hardware details really make a difference.
> 9 votes

# Answer
Yes, overclocking will speed up the process, but probably not by much.

If the program can't utilize a CPU core to 100% that means it's waiting for something, most likely IO. That waiting won't be sped up as CPU speed increases. However, at least sometimes the program will do some computation on the CPU. For those operations a faster clock helps.

Most likely you would see a 10% utilization if you doubled your processor speed since the waiting time dominates. How much overclocking helps depends on the exact program.
> 3 votes

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


# Question
Title: The communication complexity of Hamming distance mod $4$
If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$? It seems this is hard to search for online but I am sure it must be well known.

The one-way deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the messages she sends him. He does this by flipping each bit in his string in turn and seeing if the Hamming distance mod $4$ goes up or down (also mod $4$).

If we change the question to ask for the Hamming distance mod $2$ then Alice need only send $1$ bit to Bob. That is the Hamming weight of her string mod $2$.

# Answer
> 4 votes
Consider the following task $f$: Given $x,y \in \\{0,1\\}^n$, Alice and Bob need to determine whether $d(x,y) \bmod{4} \in \\{0,1\\}$, where $d(x,y)$ is the Hamming distance between $x$ and $y$.

Let $M\_f$ denote the matrix corresponding to this problem: $M\_f(x,y) = 1$ if the answer is Yes, and $M\_f(x,y) = -1$ if the answer is No. The discrepancy method shows that $$ R\_\epsilon(f) \geq \log \frac{1-2\epsilon}{\lambda\_{\max}(M\_f)/2^n}. $$ In our case, you can calculate that $\lambda\_{\max}(M\_f) = 2^{\lceil n/2 \rceil}$ (I checked this for a few $n$ using Krawtchouk polynomials, but presumably there is a simple proof, since all the eigenvalues are nice). For even $n$, this implies that $$ R\_\epsilon(f) \geq \log \frac{1-2\epsilon}{2^{-n/2}} = \frac{n}{2} + \log(1-2\epsilon). $$

(When $n$ is odd, the lower bound is slightly worse.)

Exactly the same bound is obtained if we replace the condition $d(x,y) \bmod{4} \in \\{0,1\\}$ with the condition $d(x,y) \bmod{4} \in \\{0,3\\}$.

---
Tags: communication-complexity
---


title: Inferring used fields in return type

text:
# Question
Title: Inferring used fields in return type
A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example:

```
get_user(id) {
  return sql_query("SELECT * FROM users WHERE id=$1", id);
}

render_some_webpage() {
  // ...
  print get_user(session.user_id).username;
  // ...
}

```

While this would work, it requires the database to send back a bunch of user fields when only the username is used (it's not a big deal in this trivial example, but gets much worse when associations/joins are involved). This problem is normally solved via adding an additional argument to `get_user` with a list of required fields, but that's far from a perfect solution. It seems the language could infer which fields of the user were actually used and allow `get_user` to act on this information (by only fetching the username).

Is this a known concept? Are there languages that implement this idea?

# Answer
Few otherwise general-purpose languages bother to deeply integrate with (relational) databases. Most languages I've seen that do do some integration (though fairly shallowly) are bolt-on abominations. Links is quite a bit more principled, and I believe can actually more or less do what you want. It's a statically typed functional language whose goal was to collapse multi-tier web applications into one coherent (source) program.

In Haskell, a general-purpose, statically typed, purely functional language with no database integration, you can use the type class system and type inference to propagate information about the used fields back to the query site. The simplest approach to this will not actually know what columns are on the table, and so will lead to queries that may access columns that don't exist. Part of the reason I think Links can do what you want is that the type systems of Haskell and Links have some relation, and Phil Wadler, one of the primary designers of Links, is also the *creator* of type classes. (The mechanism is different though, using row types rather than type classes. Indeed, the approach in Haskell would be more like a poor man's row types.)

That said, it's not clear how desirable this actually is, especially when given a clean, modular syntax for making queries e.g. something like C#'s Linq. Using Linq is like your solution of passing in the list of required fields except you have the full flexibility of, at least, Linq's query syntax and so you aren't just slinging strings about and thus can't typo one of the fields. You're still required to change the query to return the appropriate fields, but often you do want some awareness and control over the query. (This is especially true if the code isn't validated against the schema and so typoing a field name can lead to non-existent column names in the query.)
> 1 votes

# Answer
I know that this is probably not relevant to you, but the general problem is undecidable.

Consider this:

```
render_some_webpage() {
  ...
  user = get_user(session.user_id)
  ...
  if some_function(x) == 0
      print user.name
  else
      print user.email
  end
  ...
}

```

Now, the properties of `user` that `get_user` has to retrieve depend on the return value of an arbitrary function, determining which is (in general) not computable.

Of course, easier problems can be solved: here, we could just get `name` *and* `email` and be happy about all the properties we saved regardless. We can make the compiler as smart as possible, and apply the optimisation if it can figure something out.
> 0 votes

---
Tags: compilers, databases, type-inference, data-flow-analysis
---


title: Find a CFG for univocalic words

text:
# Question
Title: Find a CFG for univocalic words
I'm trying to figure out how to create a CFG for univocalic words...

Univocalic words are words that have only one the same vowel letter throughout the word

Example: September, Anna

Would appreciate any of your help..

# Answer
Try the following grammar (which can be transformed into a regular grammar):

$S \rightarrow A \mid E \mid I \mid O\mid U$
$A \rightarrow aA \mid bA \mid cA \mid \dots \mid zA \mid \epsilon$ (all consonants and only 'a')
$E \rightarrow eE \mid bE \mid cE \mid \dots \mid zE \mid \epsilon$ (all consonants and only 'e')
$I \rightarrow iI \mid bI \mid cI \mid \dots \mid zI \mid \epsilon$ (all consonants and only 'i')
$O \rightarrow oO \mid bO \mid cO \mid \dots \mid zO \mid \epsilon$ (all consonants and only 'o')
$U \rightarrow uU \mid bU \mid cU \mid \dots \mid zU \mid \epsilon$ (all consonants and only 'u')

Example 1: $S \Rightarrow A \Rightarrow aA \Rightarrow anA \Rightarrow annA \Rightarrow annaA \Rightarrow anna$

Example 2: $S \Rightarrow E \Rightarrow sE \Rightarrow seE \Rightarrow sepE \Rightarrow septE \Rightarrow septeE \Rightarrow septemE \Rightarrow$ $septembE \Rightarrow septembeE \Rightarrow septemberE \Rightarrow september$

**Warning**: do not expect that this grammar generates only English dictionary words. For example it does generate a nonsense such as 'aagfdadgsa'.
> 0 votes

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


# Question
Title: Amortized analysis of resizing array implementation of a stack
Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne:

> Proposition E. In the resizing array implementation of Stack (Algorithm 1.1), the average number of array accesses for any sequence of operations starting from an empty data structure is constant in the worst case.
>
> Proof sketch: For each push() that causes the array to grow ( say from size N to size 2N), consider the N/2 - 1 push() operations that most recently caused the stack size to grow to k, for k from N/2 + 2 to N. Averaging the 4N array accesses to grow the array with N/2 array accesses (one for each push), we get an average cost of 9 array accesses per operation.

It is unclear to me why **4N** array accesses are required to grow the array. From my understanding, in the proof they describe the case when the array grows from size N to 2N, and for that it should require only 2N array accesses (copy the first N elements, 2 array accesses per element).

# Answer
> 2 votes
They include the initialization of the new array.

From page 207 of the text:

> Q. Does `int[] a = new int[N]` count as *N* array accesses (to initialize entries to 0)?
>
> A. Most likely yes, so we make that assumption in this book, though a sophisticated compiler implementation might try to avoid this cost for huge sparse arrays.

---
Tags: algorithms, amortized-analysis
---


# Question
Title: The optimal way to reverse engineer a binary classification problem
I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.

In a scenario very similar to popular binary classification machine learning contests, competitors are required to submit their answers to the test set containing N data points. The accuracy of the submission will be announced. The competitors can then submit a new answer, and the new accuracy will always be published, no matter improved or not.

If the competitor has no information about the test set at all, what is the optimal way (in the sense that the least submissions are needed) to crack the challenge?

# Answer
Your problem is tackled in Vaishampayan, Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle. Vaishampayan relates this problem to one considered in Lev and Yuster, On the size of dissociated bases, and the upshot (if I understand things correctly) is that a random test set of size $O(N/\log N)$ (for an appropriate hidden constant) would do if you don't care about carrying the decoding procedure efficiently. Vaishampayan describes a more structured solution using $o(N)$ tests which can be implemented efficiently.
> 3 votes

# Answer
Here is another interesting scheme, which might be better if your initial classifier has high accuracy. Suppose your classifier has a 99% accuracy, i.e., an 1% error rate. Divide the test set into $N/100$ blocks of 100 data points. We will work on one block at a time, for each block recovering the correct classification of all 100 data points in that block.

Note that we expect about 37% of the blocks to be have no errors (all 100 data points are classified correctly by your classifier), 37% to have one error, and 26% to have two or more errors. We can figure out how many errors are present in a block by making a single query: flip the prediction for all 100 data points in the block (leaving the other $N-100$ predictions unchanged), submit it, and see how much the accuracy decreases. If the number of correct predictions decreases by 100, then the original predictions were all correct; if it decreases by 98, then there was 1 error in the original predictions; otherwise there were 2 or more errors.

Also, you can find the locations of the errors. For instance, if there is a single error, you can find the location of the error by doing binary search: split the block in half, and test whether the error is in the first half or second half by testing the number of errors in the first half. Recurse. This will find the location of a single error using $\lg 100$ submissions on average. In general, if there are $k$ errors in the block, you can find the location of them using at most $k \lg 100$ submissions.

Once you have finished this procedure for a block, you know the correct classification of all points within the block.

Since the number of errors in each block has a Poisson distribution, the average number of errors is 1. Therefore, on average we will do $1 + \lg 100 \approx 7.6$ submissions per block. After $(N/100) \times (1 + \lg 100) \approx 0.076 N$ submissions, you learn the correct classification for all points in the test set. You can of course generalize; if the error rate is $1/m$, then you can use blocks of size $m$, and you'll need about $(N/m) (1 + \lg m)$ submissions to reverse engineer the test set.

This shows that the higher the initial accuracy of your classifier, the fewer number of submissions needed to reverse engineer the correct classification of all data points in the test set.

As a heuristic, you can also recover the correct classification for some number of data points (by processing some of the blocks as above), then add those to your training set, and make new predictions on the remaining data points in the test set. If you are lucky, perhaps your classification accuracy on the remainder will improve (thanks to the additional training data), and perhaps even fewer submissions will be needed.
> 0 votes

---
Tags: algorithms, optimization, combinatorics, probability-theory, information-theory
---


# Question
Title: Given a maze, check if set of points is forming some-type of closed shape
Let's say we have given 2-dimensional maze in form of matrix, conisting only of the letters `x` and `.`. For example the following maze:

```
xxxxx 11111    .....
x...x 1...1    .xxx.
x.x.x 1.2.1    .x.x.
x...x 1...1    .x.x.
xxxxx 11111    .....

```

Let's group those elements, we will group x's only, such that two elements will be in one group if they share at least one of the 8 sides (4 regular and 4 diagonal). Up here is one way how to group them, now for each of those groups we want to check if they are forming closed figure (in the first maze there is closed figure and in the second there isn't because the area of x's isn't closed).

**What I think for the solution**

I was thinking that we should find 4 points first that are important for each figure, those are: the top right, top left, bottom left and bottom right nodes, and now check if there is path from the top right to top left and bottom right, from the top left to bottom left and from the bottom left to the bottom right. But, it turns out that this is not working always.

# Answer
> 1 votes
Label open space in same way you label the x's, if a set of x's touches more than one label it contains a closed space.

# Answer
> 0 votes
My solution might be a little more complicated but if I wanted to solve this I would check the boundaries of the maze first, if there are no `.` anywhere on the left side, right side top and bottom. If there are no `.`'s we could assume the figure is closed.

Another interesting way to determine if the figure is closed or open, we could iterate through each vertical slice of the figure checking if any of of the `.` are on a border or touch a `.` on the border we could consider that `.` open as well. After you could iterate up again checking if any `.`'s are now touching open `.`'s. Finally you could iterate down one last time checking if there are any orphaned `.`'s if that's the case, the figure contains a closed figure and the check fails.

# Answer
> 0 votes
Add an "external" border marked with $\*$ and with a single $\\$$ in the top-left corner:

```
$******   $******
*xxxxx*   *.....*
*x...x*   *.xxx.*
*x.x.x*   *.x.x.*
*x...x*   *.x.x.*
*xxxxx*   *.....*
*******   *******

```

A maze has a closed shape if and only if there exists a point $.$ from which we cannot reach $\\$$ "walking" through "$.$" or "$\*$"

In order to find such a point simply apply a flood fill algorithm starting from $\\$$ (and considering $\*$ and $.$ as "white" to be filled).

For the two mazes of your example we get:

```
$FFFFFF   $FFFFFF
FxxxxxF   FFFFFFF
Fx...xF   FFxxxFF
Fx.x.xF   FFxFxFF
Fx...xF   FFxFxFF
FxxxxxF   FFFFFFF
FFFFFFF   FFFFFFF

```

As you can see in the first case there are a bunch of "." that are not connected to $\\$$ ... they lay undisturbed in a closed shape.

---
Tags: graphs
---


# Question
Title: How could an SMT solver be implemented as simple as possible?
I'm trying to figure out how an SMT solver works as simple as possible. Let's assume we have a simple input program with symbolic values `x` and `y`. E.g.

```
if (x+y < 20) {
   if (x > 10) {
      if (y > 10) {
        assume(false);
      }
   }
}

```

Here we have different paths, depending on the conditions. To reach `assume(false)` each condition has to be true, so our outcoming formula is:

$x+y \< 20 \\,\\,\\,\\,\\,\wedge \\,\\,\\,\\,\\, x \> 10 \\,\\,\\,\\,\\, \wedge \\,\\,\\,\\,\\, y \> 10$

So far, so good. What happens next, step by step?

I would like to implement, as simple as possible, a solver which gets as input something like the formula above and delivers specific output to reach the end of the path - here `assume(false)`, i.e. `x = 2147483647, y = 2147483647` (jfi: `x+y` would be `-2`) - for overflow detection or similar.

I know there are a lot of SMT solvers on the internet, but I couldn't find a really simple self-explaining one. Looking forward to a suggestion.

# Answer
> 6 votes
What happens next is that we invoke a SMT solver to try to check whether the formula

$$x+y \< 20 \quad \land \quad x \> 10 \quad \land \quad y \> 10$$

is satisfiable. The solver tries to find values for $x,y$ that make this formula true. If it finds such a value, then it knows the `assume(false)` statement is reachable. (I am guessing you meant to write `assert(false)`, not `assume(false)`.) If the formula is not satisfiable, then that statement is not reachable.

So basically you are asking: how do SMT solvers work? That is too broad for this site, but there are lots of places that explain how SAT solvers and SMT solvers work. I would suggest doing some research; you will find many explanations. You could start with the DPLL algorithm for SAT.

There is little point in implementing your own solver. Your solver will probably perform far worse than existing tools. There has been a lot of research into building effective solvers, and the techniques required are non-trivial. Instead, I'd recommend you simply use an existing solver, such as Z3.

If you just want to implement one for fun, the most straightforward approach is probably to bit-blast to SAT: treat each bit of (the binary representation of) $x,y$ as a boolean variable, then write down a boolean formula (on those boolean variables) that expresses the requirement that $x+y\<20$. How can you do that? Write a boolean circuit that computes $x+y$ and compares the sum to 20, then convert that circuit from CircuitSAT to SAT. Finally, invoke an off-the-shelf SAT solver to check satisfiability of this boolean formula. You'll need to do some research to understand each of these steps, but there's a lot written on how to do that.

# Answer
> 3 votes
You may not need a general SMT solver. In this case, you have a bunch of inequalities conjoined together, which you can solve as a linear program.

A simpler alternative to an SMT solver is to implement the theory as an add-on to a logic program. Most decent Prolog implementations, for example, have a CLP(R) or CLP(Q) library which can solve equality and inequality constraints over reals or rationals.

---
Tags: satisfiability, constraint-satisfaction, smt-solvers
---


# Question
Title: Are two states equivalent in a DFA if on the same input the states transition to each other?
Suppose you have three states in an DFA $q\_{1}$, $q\_{2}$ and $q\_{3}$, all non-accepting. Suppose $a$ and $b$ are two symbols, such that:

$\delta(q\_{1},a)=q\_{2}\\ \delta(q\_{2},a)=q\_{1}$

and

$\delta(q\_{1},b)=q\_{3}\\ \delta(q\_{2},b)=q\_{3}$

Are the states $q\_{1}$ and $q\_{2}$ considered equivalent?

# Answer
> 1 votes
Not necessarily. If there is another symbol in the alphabet, $c$, such that $q\_1$ transitions to $q\_4$ on $c$ but $q\_2$ transitions to $q\_5$ then they are clearly not equivalent.

# Answer
> 3 votes
> "We say that states $p$ and $q$ are *equivalent* if:
>
> * For all input strings $w$, $\hat{\delta}(p,w)$ is an accepting state if and only if $\hat{\delta}(q,w)$ is an accepting state."
>
> (John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to automata theory, languages, and computation, 2nd edition.)

So if the automaton doesn't accept any strings, there cannot be a string that *distinguishes* the two states, and therefore there cannot be an equivalence between two states.

# Answer
> 2 votes
Please read about DFA minimization, in your case $q\_1$ and $q\_2$ are nondistinguishable, both are nonaccepting states. The transition for $b$ is the same, for $a$ they alternate between each other, so you can say that $q\_1$ and $q\_2$ are equivalent.

# Answer
> 2 votes
If $q\_1, q\_2, q\_3$ are the only three states in a DFA and all three are non-accepting then the language of the DFA is empty and so $q\_1, q\_2, q\_3$ are all equivalent. If there are other states in the DFA as well, then two states can only be equivalent if both lead to a non-accepting state or if both lead to an accepting state for any given string. You are only checking for one symbol, i.e. string of length 1, which is not enough to prove equivalence.

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


title: Storing the stream in less space

text:
# Question
Title: Storing the stream in less space
Suppose that a stream of data is arriving like $(4,5) (5,6), \cdots ,(7,8)$, where for each particular tuple $(a,b)$, we have $a \in \[n\]$ and $b \in \[k\]$. I want to store this stream. In my setting $k = O(n^2)$, and there are no duplicates, so the stream has at most $nk$ pairs.

I want a data structure that supports three operations:

* Insert$(a,b)$, for $a \in \[n\]$ and $b \in \[k\]$, adds the pair $(a,b)$ to the stream
* Search$(a,b)$, for $a \in \[n\]$ and $b \in \[k\]$, checks whether the pair $(a,b)$ is in the stream
* Delete$(a,b)$, for $a \in \[n\]$ and $b \in \[k\]$, removes $(a,b)$ from the stream.

I don't need to preserve the order of the stream. I'm looking for a data structure where each operation should take $O(1)$ time. Also I want the space usage to be at most $O(n)$ bits of space. It is OK if the data structure is probabilistic.

# Answer
Unfortunately you will always need space $\Omega(nk)$ to support your operations.

Consider all possible contents of your stream, i.e. all subsets of $\[n\]\times \[k\]$. There are $2^{nk}$ such subsets. Take two different subsets out of this, lets say $M$ and $M'$. Since the sets are different, there is an element $(a,b)$ which is contained in $M$ but not in $M'$ or the other way around. Now we perform the operation $\mathrm{Search}(a,b)$, for which the answer should be "Yes" for $M$ and "No" for $M'$ (or vice versa). It follows that both sets need a different storage content.

Moreover, this shows that each data structure needs a different storage content for each of the subsets. It follows that each data structure needs $\Omega(nk)$ bits of space to perform your operations (even without the delete operation and without constant time querying).
> 2 votes

---
Tags: algorithms, data-structures
---