# Question
Title: How does "solving" a game like connect four or tic-tac-toe work?
To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all the possible combinations).

If I were to try every possible move for some game I would get a tree of all the moves and each branch of that tree would represent a single game and each node on a branch would represent a move.

The last node of each branch is the finished game. Some will be ties, some will be won and some lost. Now the question is how am I supposed to create a winning strategy from that tree? It basically boils down to: *if you know every possible position for a game, how would you go about winning?*

It sounds like a trivial question when you say it out loud (and maybe it is), but it just doesn't click for me. Any insights are appreciated.

# Answer
> 5 votes
In short, minimax is what you're looking for.

We say that a game is valued $1$ if player 1 wins, $-1$ if player 2 wins and $0$ if it's a tie.

You have your brute-forced game tree. At each level you check who's turn it is. If it's player 1's turn, he/she will try to maximize the outcome. If it's player 2's turn he/she will try to minimize the outcome.

So you apply that. Literally. At each node you take the maximum or minimum of the child nodes and assign it to that node, depending on the depth at which you're looking (AKA who's turn it is). Then the value of the root node is the outcome of the game with perfect play.

# Answer
> 3 votes
For simple games, you use the following strategy:

You check whether a game position is won, lost, drawn, or not decided yet. In the first three cases, the position has a value of +1, -1, or 0. In the latter case, you try out all your possible moves, calculate the value of every move recursively, and the value of the position is the value created by your best move, and the move that you make is one that created the highest value.

Obviously when you try a move and do the recursion, you have to do the calculation for the other player, who will judge a position exactly in the opposite way that you do.

That's the easy part. There are optimisations (like if your first move is a winner, you don't have to check the other moves. If your first move is a draw, then you don't need to completely evaluate the other moves, just far enough to prove or disprove that they are winning moves. If you can encounter the same position in different ways, then you store the value of a position instead of computing it again. ).

Most games are too complex for this, so you assign real values between +1 and -1, where positive values are positions that are more likely to win, and negative values are positions that are more likely to lose, and optimise the value, calculating not to the end of the game but only as far as you can.

# Answer
> 2 votes
Someone should mention the term "backward induction" here. The idea of backward induction is to start at the leaves of the game tree (when an end condition is reached) and label each Win, Lose, Draw for player 1 according to the rules of the game. Now work backward, looking at nodes whose children have all been labeled. The player who moves at that node will pick an optimal decision, i.e. a move leading to a child labeled a win for them, or draw if none are available. So label this node with the appropriate outcome. Repeat until reaching the root, which will be labeled as a draw or a win for one of the players. We will have also computed, for each node in the tree, an optimal move for the corresponding player.

---
Tags: algorithms, game-theory
---


# Question
Title: Can we easily check if we can place two not-intersecting circles inside a convex polygon
We have given convex polygon of $N$ vertices, and two circles of radius $r$. Is it possible to check if we can place those two circles completely inside the polygon, such that they don't intersect, but they might have one point in common.

For example if we have given square with sides of length $1$, and $r = 0.25$. Then the answer should be yes, as we can place those two circles.

# Answer
Let $P$ be the given polygon. Let $Q$ be the set of points inside $P$ whose distance to the boundary of $P$ is at least $r$. Your requirement can be met iff the diameter of $Q$ is at least $2r$. Indeed a radius $r$ circle lies inside $P$ iff its center is in $Q$, and two such circles are disjoint iff the distance between their centers is at least $2r$.

The problem of finding $Q$ is called inward polygon offsetting. That link has a lot of discussion about the general case, but it should be much simpler when $P$ is convex.

Suppose the vertices of $P$ are $p\_1,\ldots,p\_n$ in counterclockwise order. Let $R$ denote rotation counterclockwise by $90^\circ$. Let $n\_i$ be the outward unit normal vector to edge $p\_ip\_{i+1}$, namely $n\_i=R(p\_i-p\_{i+1})/|R(p\_i-p\_{i+1})|$. Let $e\_i$ denote this edge shifted by $r$, namely the line from $p\_i-rn\_i$ to $p\_{i+1}-rn\_i$. Now we can iteratively construct a path $q$ which will become the boundary of $q$. In iteration $1$, let $q=e\_1$. In iteration $i$, find the intersection of $q$ with $e\_i$, discard the part of $q$ after the intersection and append the part of $e\_i$ after the intersection (we should look for the intersection starting from the end of $q$; the more segments we have to check, the more vertices we can discard, so the algorithm will still be $O(n)$). After $n$ iterations, find where $q$ intersects itself and discard excess vertices to obtain a closed path; this is the boundary of $Q$.

Once we have $Q$, we can find its diameter using the Rotating calipers algorithm.
> 5 votes

---
Tags: computational-geometry
---


# Question
Title: Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties
What is an algorithm that will take as an **input** a flat list of objects with a varying degree of overlapping properties:

```
thing1 (instance of "Mammal", but we don't know this now)
  -eatsFood
  -reproduces
  -hasMilk

thing2 (instance of "Emu", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -doesNotFly

thing3 (instance of "Eagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing4 (another instance of "Eagle", we just know it has the same "shape" as thing 3)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing5 (instance of "BaldEagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies
  -hasWhiteHead

```

And return as an **output** a hierarchical class structure/inheritance tree/taxonomy like the following?

Notes:

1. The algorithm is able to identify a hierarchical structure in the objects' properties, including abstract classes that are not explicitly present as objects in our data set. For example, there are no instances of "Bird" or "Animal" in our object data set, however the algorithm is able to identify that "Eagle" and "Emu" both inherit from a common parent class (the abstract class "Bird") and that both the "Bird" and "Mammal" classes inherit from a common parent class (the abstract class "Animal").
2. The algorithm doesn't know or care about the class names ("Animal", "Mammal", "Bird", "Emu", "Eagle", "Bald Eagle"). We generate those ourselves based on the properties of the classes the algorithm has generated. I just put them here to aid the example, but they're not part of the algorithm.
3. The list of an object's properties in the data set will not necessarily be "in order" like they are here. Don't assume any order to the properties in the raw data.

# Answer
> 1 votes
It looks like your problem can be solved by transitive reduction followed by some post-processing.

Build a directed graph, with one vertex per "object shape". Draw an edge $u \to v$ if $u$ contains all of the fields of $v$ (possibly plus some more). This should form a dag. Now compute the transitive reduction of this dag. The result should be a tree (or forest of trees).

This almost gives you the desired solution. The one thing it doesn't do is invent new abstract base classes that weren't already present in the input. So, we can do some post-processing to create them. First, if the result has more than one tree, we'll create a new root (an abstract base class) that is a parent of all of those trees. The result is a (directed) tree.

Examine each node that has more than two children. This is the only place where we need to create new abstract base classes. Let $S$ denote the set of children. Now you have some choices about how you want to form a hierarchy based for $S$; there are multiple possibilities that are all consistent with the input data, and the question doesn't specify any criteria for choosing among them. So, I'll have you let you decide on how you want to select among them.

---

What's the running time? Constructing the graph and computing the transitive reduction can be done in $O(n^3)$ time, where $n$ is the number of different object shapes present in the input. (In fact, given the structure of the input, in this particular case it can actually be done in $O(n^2)$ time, but maybe that isn't important, since I suspect in practice $n$ might be fairly small.) The post-processing can also be done in $O(n^3)$ time (probably less if you care). So the overall running time is at most $O(n^3)$.

Of course, we can de-duplicate the shapes in the input before doing any processing: there is no need to keep more than one object of any particular shape. So, the running time depends only on $n$, the number of distinct shapes in the input, not on the number of objects in the input. It's easy to do the de-duplication in linear time using a hash table.

---
Tags: algorithms, graphs, data-structures, trees, object-oriented
---


# Question
Title: P vs NP and can an oracle make P=EXPTIME?
As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$.

I don't fully understand this logic. Diagnolization (Time Hierarchy Theorem) proves that $P \neq EXPTIME$. Does it therefore mean that there is no oracle $X$ that could ever make $P^X = EXPTIME^X$ ?

# Answer
> 3 votes
First let me try to be a bit more precise about your first sentence. The reasoning you list shows that no relativizing proof can prove or disprove P=NP. "Diagonalization" is a fuzzy concept, and depending on what you mean by it, might or might not relativize -- diagonalization proofs tend to relativize, but no guarantees. So the oracle result rules out some/many kinds of diagonalization proofs, but maybe not all. See, e.g., https://cstheory.stackexchange.com/q/6575/5038.

Second, let's discuss your final question. Yes, it is indeed true that $P^X \ne EXPTIME^X$ for all $X$; there is no oracle $X$ that will make them equal. I'll talk through why that is. The standard way to prove $P \ne EXPTIME$ is to prove $TIME(p(n)) \ne TIME(p(n)^2)$ (the time hierarchy theorem), then notice that this implies $P \ne EXPTIME$ (since $TIME(2^n) \ne TIME(2^{2n})$, but $P \subseteq TIME(2^n)$ and $TIME(2^{2n}) \subseteq EXPTIME$). The proof of $TIME(p(n)) \ne TIME(p(n)^2)$ uses diagonalization. This proof does indeed relativize. In particular, for all oracles $X$, we do indeed have $TIME^X(p(n)) \ne TIME^X(p(n)^2)$. It follows that, for all oracles $X$, we have $P^X \ne EXPTIME^X$ (by the same argument as before).

See also: https://cstheory.stackexchange.com/q/8902/5038, https://cstheory.stackexchange.com/q/6575/5038.

# Answer
> 2 votes
The time hierarchy theorem relativizes, meaning that it also holds in the oracle Turing machine model. Intuitively, the diagonalization proof of the time hierarchy theorem only uses the fact that we can encode Turing machines as strings and have the ability to simulate some machine given its encoding. These properties also hold when we proceed to talk about the relativized (oracle) world.

In the P vs NP case however, one cannot hope for a relativizing proof, since we know that the answer depends on the oracle. Thus, a black box treatment of the oracle Turing machine would not be enough here.

---
Tags: time-complexity, p-vs-np
---


# Question
Title: Password authentication over an insecure connection
I was thinking a way to send password to server secure way without using secure connection,I found one solution.I want to find flaw in this.(Note: I am begginer,dont judge me, I know little about cryptography and little about networks)

So server contains hashed version of my password. When i want to send password I send server request to generate me random key(big enough it is less likely to be same ). Then I hash password and add that hash to key and hash it again.I send that final hash to server. Server use key and hash the hashed password from database the same way and compare my hash with it.If it is the same,password is correct.

Ex. (Simplified) I want to send password "test123" to server. I request random key and server sends me key "999". I hash "test123" and get lets say "abc" ,and hash "abc999" and get "efg" and send that to server. Server recieves my "efg" , then gets "abc" hashed password from database, adds key "999" and gets "efg" ,so "efg"=="efg" ,password correct.

The someone listening the connection can't use the same hash because it will get different key.

# Answer
First, note that a way to perform password authentication, or any kind of user authentication, over a connection is only useful if you assume that the attacker can see the data exchanged over the connection, but not modify the data. If the attacker is a man-in-the-middle who can suppress data between the client and the server or send packets that the legitimate parties will accept, then this is pointless. A man-in-the-middle can wait until the client has authenticated to the server, and then hijack the connection.

Establishing a secure connection is a solved problem as long as the client can verify that it's connecting to the right server. So user authentication over an insecure connection is not an interesting problem to solve. However, user authentication over a secure connection (i.e. no third party can see or modify the data) to an untrusted server is an interesting problem. Let's see how your protocol performs in this scenario.

> So server contains hashed version of my password.

You're assuming that the server knows $H(P)$ where $H$ is a hash function and $P$ is the password. Actually, what the server knows is $PH(S,P)$ where $PH$ is a password hashing function and $S$ is a salt — see How to securely hash passwords for an explanation. You can fix this by having the server send the salt to the client, but that weakens the security of the system because it means that the salt is public — anyone can start a client connection to obtain the hash for an account.

> When i want to send password I send server request to generate me random key(big enough it is less likely to be same ). Then I hash password and add that hash to key and hash it again.

That's not a key, but as a nonce. But ok, that's just a matter of terminology. The server sends a nonce $N$ and the salt $S$, and the client calculates $H(N || PH(S,P))$ ($||$ is concatenation).

> I send that final hash to server. Server use key and hash the hashed password from database the same way and compare my hash with it.If it is the same,password is correct.

The server receives $H(N || PH(S, P\_c))$ where $P\_c$ is the password used by the client. It knows $N$ and $PH(S, P\_g)$ where $P\_s$ is the genuine password. It is indeed the case that $H(N || PH(S, P\_c))$ = $H(N || PH(S, P\_s))$ if and only if $P\_c = P\_s$ with overwhelming probability, assuming that $H$ is a cryptographic hashing function. So your scheme works.

However, there's a second flaw (in addition to having to publish the hash), and this one is devastating. Suppose that an adversary manages to obtain the copy of the hashed password on the server. Breaching password databases is a common attack, so it's very important to defend against it. The adversary doesn't know $P\_s$ but they know $PH(S, P\_s)$. Then they can straightforwardly calculate $H(N || PH(S, P\_s))$, and impersonate the user.

In a nutshell, you've changed the protocol from requiring the client to know the password, to requiring the client to know the hash of the password. So the hash has become the password! This completely defeats the point of hashing passwords.

More generally, suppose you want a user authentication scheme where the client doesn't have to send the password to the server, but only some *proof of possession* of the password from which the password cannot be reconstructed. This either requires the server to know the password so that they can make the same calculations as the client, or else it requires using some method for not-knowing the password that isn't a hash.

There are methods that allow a client to know some secret value (the “password”) and to use it to authenticate to a server without requiring the server to know this secret value. They involve mathematical functions that have different properties compared to hashes. The most straightforward is public-key authentication: the client knows a private key, and the server knows the corresponding public key. The client *signs* a message using the private key, containing a nonce generated by the server. When the server receives the signed message, it can verify that the signature is genuine, using only the public key.
> 1 votes

# Answer
If you don't use a secure connection, it is vulnerable to man-in-the-middle attacks, so not secure.

If you do use a secure connection, then it is no better than sending the password directly.
> 1 votes

---
Tags: computer-networks, security, authentication
---


# Question
Title: Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)
I'm working on some lecture notes and wondered if there was a good example algorithm for the recurrence equation

$$T(n) = T(n/2) + n$$

I know that I can do selection in this running time, but that is a probabilistic algorithm, and I was hoping not to introduce this algorithm at this point in my lecture notes. I plan to introduce the selection problem in a later chapter after describing quick-sort. Is there a good example of an algorithm that has this recurrence equation as worst-case?

# Answer
I ended up using *binary sum*, i.e., adding the numbers in a list pairwise:

```
def binary_sum(x):
    if len(x) == 0: return 0
    if len(x) == 1: return x[0]

    # O(n) work
    y = []
    for i in range(1, len(x), 2):
        y.append(x[i - 1] + x[i])
    if i + 1 < len(x): # handle odd lengths
        y[0] += x[i + 1]

    return binary_sum(y) # recurse on n//2 size

```

I justify this with a story about numerical issues when adding numbers of very different orders of magnitude.
> 0 votes

# Answer
Bottom-up heap construction. Choose one application of sift-down as your unit of measurement. Then the recurrence is $T(n) = T(n/2) + n$.

If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to

$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum\_{h=0}^{\lg n} h\frac{n}{2^h} \< n\sum\_{h=0}^\infty \frac{h}{2^h}$$

and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum\_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.
> 2 votes

---
Tags: divide-and-conquer
---


# Question
Title: How many bits does a data bus need to have?
Using the following context as an example for the calculations:

> **Data bus** connecting the processor to a memory **32 bits**, considering a memory with capacity of **16kB**.

---

## How many bits does a data bus need to have?

# Answer
Unless the bus is multiplexed, every data bit is conveyed by a distinct data line, hence $32$.

This does not account for the address bus.
> 1 votes

---
Tags: computer-architecture
---


title: NP Class Definition of a Certificate

text:
# Question
Title: NP Class Definition of a Certificate
Given the definition for all x ∈ Σ∗

> x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1

Lets say the input x = ababab

Then the certificate u shouldn't be longer than p(|x|).

But what would be p(|x|)? In my example?

# Answer
> 1 votes
In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $u$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $u$ is indeed a valid vertex cover.

# Answer
> 0 votes
A language $L$ is in NP if there exists a polynomial $p$ and a Turing machine $M$ running in polynomial time such that $$ x \in L \text{ iff there exists } u \in \Sigma^\* \text{ with } |u| \leq p(|x|) \text{ such that } M(x,u) = 1. $$ Asking what is $p$ is exactly the same as asking what is $M$. When proving that a language is in NP, we have to specify both $p$ and $M$.

---
Tags: np, nondeterminism, polynomial-time
---


title: Reduce Max-Cut to Max-2SAT

text:
# Question
Title: Reduce Max-Cut to Max-2SAT
I would like to find a reduction from Max-Cut to Max-2Sat. Could someone shed light on this problem, preferably spiced with some intuition?

Thanks, Matan.

# Answer
Given an instance $G = (V,E)$ for Max-Cut, we create an instance of Max-2Sat with one variable $x\_v$ per vertex $v \in V$, and two clauses per edge $(v,w) \in E$: $$ x\_v \lor x\_w, \qquad\overline{x\_v} \lor \overline{x\_w}. $$ Every subset of $V$ corresponds to a truth assignment for the $x\_v$ in a natural way. Furthermore, the number of clauses satisfied is exactly $$ |E| + |E(V,\overline{V})|. $$ Intuitively, the edge $(v,w)$ is cut iff $(x\_v \lor x\_w) \land (\overline{x\_v} \lor \overline{x\_w})$, and this is why this reduction works.
> 2 votes

---
Tags: complexity-theory, graphs, satisfiability
---


title: Planar embeddings of planar graph

text:
# Question
Title: Planar embeddings of planar graph
Let $G=(V,E)$ be a *planar* graph, only specified by its set of vertices and edges. Suppose $|V|=n$. According to Fary's theorem, there exists a *planar embedding* of $G$ with straight line segments. Then this embedding can be represented by a set of points in the plane (each $v\in V$ is represented by a unique point $p\_v$ and there is a line segment between $p\_u$ and $p\_v$ iff $(u,v)\in E$)

Questions :

1. Is it possible to find this set of points in **polynomial time** (i.e. $n^{O(1)}$) ?
2. What if we force the points to have integer coordinates ?
3. Can we force the maximum (euclidian) distance between any two points to be $n^{O(1)}$ ?

Such statements could be very useful for proving lower bounds for some geometrical problems

# Answer
Quoting directly from the Wikipedia article linked in the question:

> De Fraysseix, Pach and Pollack showed how to find in linear time a straight-line drawing in a grid with dimensions linear in the size of the graph

As I commented earlier, this answers all three questions.
> 3 votes

---
Tags: graphs, polynomial-time, planar-graphs
---


# Question
Title: Infinite Union operation of Formal Languages
Is every formal language not closed under infinite union operation ? I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any counter-example for other languages. Intuitively , I think it should not be closed but intuition could be wrong also. So please clarify whether every language (like DCFLs,CFLs , Recursive , Recursively Enumerable) is closed or not under infinite union operation.

# Answer
> 3 votes
Virtually every standard language class contains singleton languages, e.g. those languages containing exactly one word ($L\_w = \\{w\\}$).

If a class containing every $L\_w$ were closed under infinite union then it would contain any arbitrary infinite language $L$ since

$$ L = \bigcup\_{w\in L} L\_w $$

More in general, we can write any language (finite or infinite) using an infinite union of singletons or empty languages.

$$ L = \bigcup\_{w \in \Sigma^\*} \\{w\ |\ w\in L\\} $$

where $\\{w\ |\ w\in L\\}$ is $\\{w\\}$ when $w\in L$ and the empty language otherwise. (I wish set comprehensions had a standard notation for free and bound variables! Here, $w$ is free.)

# Answer
> 1 votes
Languages aren't closed under operations; sets of languages can be.

The set of all languages is closed under infinite union. So, the answer to your question at the start of your post is "no".

The set of DCFLs is not closed under union, so not closed under infinite union, either. For the rest, see Infinite Union of Recursive language, Is an inﬁnite union of context-free languages always context-free?, and Infinite union of recursive languages.

# Answer
> 1 votes
To add a more concrete example to chi's answer, in the case of CFL's, think about the following infinite union: $$\bigcup\_{i=1}^\infty\\{0^i1^i2^i\\} = \\{0^n1^n 2^n|n\>0\\}$$ which is a known example of a non context-free language.

---
Tags: formal-languages
---


# Question
Title: How could you characterize "true randomness" of a finite sequence?
This question occurred to me while reading http://arxiv.org/abs/1806.08762/ Any observed sequence is necessarily finite, and any finite sequence is computable, either by explicitly storing all the data and just printing it, or by fitting an $n^{th}$-degree polynomial to an $n$-length sequence, etc.

So there's no such thing as an uncomputable (finite) sequence, whereby the article's title "Experimentally probing the incomputability of quantum randomness", initially struck me as somewhat of a non-sequitur (although the details of the article made somewhat more sense of it).

But pursuing the classical non-sequitur sense that initially occurred to me, suppose you have some process purported to be "truly random". So prove it! At best, you can give me a finite sequence generated by that process. Then I just fit a polynomial to it, and poof, it's pseudo-random. So my question... what analysis of such a finite sequence would prove that in the $n\to\infty$ limit, your finite pseudo-random sequence would be truly random (or, in some epsilon-delta sense, approach true randomness to any desired accuracy)?

For definiteness and simplicity, and for another argument, suppose we're talking about a sequence of random integers from, say, $1$ to $k$. Then there are $k^n$ $n$-length sequences, and not only can we fit a polynomial to each one, we can use some standard enumeration to enumerate them all. Then, choosing a single (random or not) number $1\ldots k^n$ corresponds to choosing an entire (random or not) sequence. But "single numbers" aren't typically considered random in the first place, whereby (one might argue) neither should finite sequences be. So, again, how could you prove that the $n\to\infty$ limit of the sequence generated by a physical (and supposedly random) process is truly random?

What occurred to me as a possible answer is that if "truly\_random"$\sim$uncomputable, then consider a sequence of computable functions, say our polynomials $f\_n(i), i=1\ldots n$, such that $1\le f\_n(i)\le k$ is the $i^{th}$ number of the experimentally-generated $n$-length sequence. Then we'd want to prove that, given a finite number of such computable $f\_n$'s, the function $\lim\_{n\to\infty}f\_n$ is uncomputable. Can that be done (or provably not done), and would it characterize "true randomness"?

**Edit
---------**
Re @orlp's comment, below: Yeah, I guess I phrased that imprecisely. Indeed, you can even construct a more trivial counterexample to my imprecise wording, using the halting problem.

Suppose you claim the have a (let's say **C** language) function **int halts(int n)** whose input is the Godel number of a program, and whose output is $1$ if program **n** halts, or $0$ if not (and let's say $-1$ if **n** is the Godel number of a string that's not a valid program, just so **halts()** is a total function on domain $\mathbb N$). Then $\mathbf{\mbox{halts()}:}\mathbb N\to\\{0,1;-1\\}$.

And let's say ancillary function **int godel(char \*filename)** reads the contents of text file **filename**, returning its godel number. Now write the following little **C** program and put it in file **doIhalt.c**

```
int main ( int argc, char *argv[] ) {
  int halts(), godel();
  while ( halts(godel("doIhalt.c")) == 1 ) ;
  exit ( 0 ); }

```

So our **doIhalt** program runs forever if **halts()** says it halts, and contrariwise halts immediately if **halts()** says it runs forever. Thus, if **n=godel("doIhalt.c")** is the Godel number of that program, the one single number **halts(n)** is immediately uncomputable. You don't even need a finite sequence at all, as in @orlp's example, to achieve an uncomputable number.

By computability here, however, we're talking about recursive enumerability, whereby the individual elements of our set of integers are given, and the question is whether or not there's a program that enumerates them all. For computer-generated pseudo-random numbers, the answer's a foregone conclusion, "yes". But we're asking about some black-box physical process that's somehow generating number-after-number. And after some finite time we've accumulated a finte sequence of its output. So we obviously have in our hands all those numbers -- that's the premise to begin with. And I was saying, or trying to say, that a finite set of numbers which we "have in our hands" is necessarily computable (meaning r.e.). So how would you say that precisely -- and much more succinctly than I elaborated it above?

In any case, my question then was whether or not the behavior of that black-box physical process is "truly random" -- how could we answer that question given only a finite sequence of the box's output (a prefix string, so to speak).

**Edit#2
-------------**
Re @D.W.'s comment below his answer. Okay, considering that the preceding $\lim\_{n\to\infty}f\_n$ limit isn't well-defined, the alternative standard characterization involves algorithmic complexity, as follows.

First, to briefly recapitulate, we've got a black-box physical process, generating (maybe random) integers, $r\_i$, one after another, in the range $1\le r\_i\le k$. And for the first $n$ of them, $r\_1,r\_2,...,r\_n$ we construct a function $f\_n(i)=r\_i,\ i=1...n$. So $f\_{n+1}$ might necessarily be very different than $f\_n$, or it might be quite similar.

Note that a program for the simplest $f\_1$ function would just store $r\_1$ and print it. Any kind of algorithm to compute that one-number-domain function would surely be more complicated than just printing it. Indeed, let $K(f\_n)$ denote the Kolmogorov/algorithmic complexity of (the simplest program that computes) function $f\_n$. So the first few $f\_n$'s probably just store-and-print all the corresponding $r\_i,\ i=1...n$.

But eventually, as $n$ gets large enough, storing-and-printing would presumably not be the shortest/simplest way to generate all the necessary $n$ values $r\_i,\ i=1...n$. The length/complexity of an algorithm would be shorter than all the necessary data. But, of course, that's **\>\>only if\<\<** there exists such an algorithm in the first place.

So, for a pseudo-random number generator, we know there's an algorithm. So $lim\_{n\to\infty}K(f\_n)=const$ because that same algorithm computes as many random numbers as you like. Otherwise, for "truly random" sequences, the limit diverges because there's no algorithm, and there's ultimately no alternative to storing-and-printing all the data.

I'm not sure whether or not the above satisfies all (or even some of) @D.W.'s objections below, but in any case, given a finite "prefix string" of the black-box's output $r\_i,\ i=1...n$, you still can't tell (I don't think) whether or not that $K(\cdot)$ limit converges.

# Answer
> 6 votes
Answer to original question:

Your question is based on some faulty premises and misunderstandings.

A word/string is neither computable nor uncomputable. Rather, we apply uncomputability to languages (sets of strings), or to functions. See https://en.wikipedia.org/wiki/Formal\_language and https://en.wikipedia.org/wiki/Computable\_function.

You can't prove that a source is random by looking at a single output from it (and this has nothing to do with computability or uncomputability). Instead, the way you prove a source is random is by proving something about the process that generates it. See How best to statistically verify random numbers?. So, being able to find a pattern in a single output of some source (e.g., being able to fit a polynomial to that output) neither proves that the source is random nor that the source is not random.

Finally, "truly random" is not equivalent to "computable". They are not really comparable concepts.

Answer to edit #2:

I think you are asking about the Kolmogorov complexity of a random sequence. In particular, let $r\_1,r\_2,r\_3,\dots$ be chosen uniformly and independently at random from $\\{1,\dots,k\\}$, and let $f\_n:\\{1,\dots,n\\} \to \\{1,\dots,k\\}$ be the function defined by $f\_n(i) = r\_i$. Then with probability 1,

$$\lim\_{n \to \infty} K(f\_n) = \infty,$$

and in particular, with probability exponentially close to 1, we have $K(f\_n) = n + O(1)$, so $K(f\_n) \to \infty$ as $n \to \infty$. This means that you can't save much space compared to "store-and-print" (with high probability, no more than a constant number of bits).

Of course, the Kolmogorov complexity is not computable, so this is not a useful way to distinguish random data from pseudorandom data.

---
Tags: randomness
---


title: Time complexity for this simple loop

text:
# Question
Title: Time complexity for this simple loop
This is the code:

```
j=2
while j<(n*n)
     j=j*j

```

---

At first my approach was to treat this like this loop

```
i=1
while (i<n)
    i=i*2

```

Which generates on $i$ various powers of $2$ ($i=2^0, 2^1, 2^2....2^k$).

At a certain $k$ iteration, $i$ is equal to or exceeds $n$. So $2^k=n$ is the time when the `while` stops.

We find $k=log\_2(n)$ which is the number of times the entire `while` loop has been executed, so $T(n)=\theta(log\_2n)$.

---

So my idea for the first algorithm was this: `j=j*j` generates on $j$ different powers of himself, so you can describe it as $j^2$. The problem is that I can't shove in a $k$ iterations in the counting.

The solution for this is actually $log(log(n))$.

Why is this? Can I improve my logic?

# Answer
Iterating `i=2*i` generates the powers of two, as you mentioned.

$$ 2=2^1 \quad 2\*2^1=2^2 \quad 2\*2^2 = 2^3 \quad 2\*3^2 = 2^4 \quad \ldots $$

Iterating `j=j*j` instead does something more aggressive:

$$ 2 = 2^1 \quad 2^1\*2^1=2^2 \quad 2^2\*2^2=2^4 \quad 2^4\*2^4=2^8 \quad\ldots $$

Note how the exponents grow. In the `i` sequence they are $1,2,3,4,\ldots$. But in the `j` sequence they are $1,2,4,8,\ldots$. That is, the exponents themselves grow exponentially!

So, the $k$-th element in the first sequence is $2^k$ while in the second it is $2^{2^k}$. That's why the first loop has complexity $O(\log\_2 n)$ and the second one $O(\log\_2 (log\_2 n))$.
> 2 votes

# Answer
You're on the right track. For the simpler code, you correctly wrote down the sequence of values that are produced: $2^0,2^1,2^2,\dots$. In particular, the $t$th output is $2^t$. Then you were able to find where the loop stops by setting $2^t=n$ and solving for $t$. That's a great approach.

Try doing the same thing for your actual example. Hint: the first two outputs are $j$ and $j^2$. What's next? Can you generalize What is the $t$th output? Can you write an equation that represents where the loop stops and solve for $t$?
> 2 votes

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


title: Turing Machine DTime(log(n))

text:
# Question
Title: Turing Machine DTime(log(n))
An Exercise from a Textbook:

> L3 := {ε,01,0011}
>
> is L3 ∈ DTime(log(n))

The answer says yes it is, it is even in DTime(1).

How is this possible? I would say it takes at least n steps to check the word. How is it possible to do it in less than n steps?

# Answer
To add to old's answer, saying a TM runs in $O(1)$ means that the number of steps the TM makes cannot become infinitely large depending on the size of the input, and is always bounded by some constant. It is true that in this case, for some inputs, the number of steps will be exactly the size of the input, and technically depend on the size of the input. However, this isn't the case for any input of size $\>4$, and therefore the $O(1)$ notation is correct.
> 1 votes

# Answer
Your Turing machine just needs to read the first four symbols one the input tape that will be sufficient to to solve the problem $L3$.
> 2 votes

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


# Question
Title: What will happen if input is larger than required in a NFA
This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be reached with the first 3 inputs only ,so what will happen after that ?

# Answer
> 1 votes
An NFA accepts a string $w$ if it has an *accepting computation*. An accepting computation is an expression of the form $$ q\_0 \stackrel{x\_1}{\to} q\_1 \stackrel{x\_2}{\to} q\_2 \to \cdots \to \stackrel{x\_m}{\to} q\_m $$ where:

1. Each $x\_i$ is either a single letter or $\epsilon$.
2. $x\_1 x\_2 \ldots x\_m = w$.
3. For every $1 \leq i \leq m$, $q\_i \in \delta(q\_{i-1}, x\_i)$.
4. $q\_0$ is the initial state, and $q\_m$ is an accepting state.

If there are no accepting computations for $w$, then the NFA doesn't accept $w$.

The string $1001$ has no accepting computation. In contrast, the string $1111$ does have an accepting computation: $$ q\_1 \stackrel1\to q\_1 \stackrel1\to q\_2 \stackrel1\to q\_3 \stackrel1\to q\_4 $$ Therefore the NFA does accept $1111$.

---

Another way to define the language accepted by an NFA is through the *possible states* function. We define $\delta(q,x)$ to be the set of possible states that the NFA is in when it reads the word $x$. You can define $\delta(q,x)$ inductively. The NFA accepts $x$ if $\delta(q\_0,x)$ contains an accepting state, where $q\_0$ is the initial state. For example, in the case of $1001$,

1. $\delta(q\_1, \epsilon) = \\{ q\_1 \\}$.
2. $\delta(q\_1, 1) = \\{ q\_1, q\_2 \\}$.
3. $\delta(q\_1, 10) = \\{ q\_1, q\_3 \\}$.
4. $\delta(q\_1, 100) = \\{ q\_1, q\_4 \\}$.
5. $\delta(q\_1, 1001) = \\{ q\_1, q\_2 \\}$.

Since neither $q\_1$ nor $q\_2$ are accepting states, the NFA doesn't accept $1001$. In contrast, for the word $1111$ we have:

1. $\delta(q\_1, \epsilon) = \\{ q\_1 \\}$.
2. $\delta(q\_1, 1) = \\{ q\_1, q\_2 \\}$.
3. $\delta(q\_1, 11) = \\{ q\_1, q\_2, q\_3 \\}$.
4. $\delta(q\_1, 111) = \\{ q\_1, q\_2, q\_3, q\_4 \\}$.
5. $\delta(q\_1, 1111) = \\{ q\_1, q\_2, q\_3, q\_4 \\}$.

Since $q\_4$ is an accepting state, the NFA accepts $1111$.

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


# Question
Title: How do you protect an AI from a human doing "illogical" moves?
Using a monte carlo approach and evalutation function. Some moves will deemed to be more advantageous than others.

As a computer plays itself, it will generally go for the best moves possible. And hence train itself to deal with these moves.

But what if a human does a few seemingly detrimental moves to throw the AI off track. And then using the human's expertise, go on to win the game?

How can one train an AI to account for this?

Or must we assume that it can generalise board positions from "perfect" games to board positions of imperfect games?

(Presumably AlphaZero has no problem with this? Has anyone ever tried to trick AlphaZero by doing a few silly moves?)

# Answer
> 3 votes
In principle, the problem of building an AI where this can never happen seems equivalent to the problem of building an AI that plays perfectly.

More precisely: If the AI can perfectly evaluate the value of each board position, then it is also able to play perfectly even if the adversary plays imperfectly. Conversely, if there is a situation where the AI can be tricked by playing an inferior move, then that means there is a board position that the AI evaluates incorrectly.

So avoiding this situation seems as hard as building an AI that never makes the wrong decision. If we knew how to do that, we would have a perfect solution to the game. There are some games (e.g., tic-tac-toe, Connect 4) where we *do* know how to achieve perfect play, but for more challenging games (e.g., chess), we don't know how to achieve perfect play. As I result, it seems likely there exists a board position where playing an inferior move helps you win where you otherwise wouldn't have.

This means that we need to focus on solutions that reduce the risk/likelihood of this bad situation, as we cannot eliminate it entirely.

When the AI is trained using statistical machine learning (as AlphaGo and AlphaZero are), you can think of this as avoiding overfitting -- you don't want to overfit to any one opponent strategy. One way that AlphaZero is trained is to play simulated games against multiple opponents -- not just against itself, but against multiple versions of itself, including older (and presumably inferior) versions of itself. This helps avoid getting stuck in a narrow portion of the space, e.g., where white always plays the Ruy Lopez opening and black always plays the Morphy defense. This may partly help make the AI more robust against inferior moves, but it is not a complete solution.

In Monte Carlo tree search (MCTS), the algorithm considers random moves for the opponent. These are drawn from a random distribution that is biased towards moves the algorithm thinks is better, but there is definitely a significant chance during any playout that we'll simulate what happens if the opponent makes a move we consider detrimental/inferior. This helps MCTS be robust against even inferior moves. It's not perfect, but it's already baked into the MCTS algorithm.

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


# Question
Title: Shortest travelling cost if we have bunch of points in 2D plane
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane and any two of them were Source and Destination. I was asked to calculate the least cost to travel all the points starting from the source and ending on Destination point. The cost to travel between any two points is |x1 - x2| + |y1 - y2|.

So, what I thought of doing was construct a cost matrix and apply Dijkstra since I thought constructing the shortest path tree must be the solution.

But I couldn't think on how to construct this cost matrix. What is the best approach for this?

# Answer
> 2 votes
This is the Traveling Salesman Problem with the $L\_1$ metric (also known as the Manhattan distance).

Unfortunately, this version of the TSP is also NP-hard. Therefore, there is no algorithm that always produces the optimal solution, is efficient, and works for all inputs. Instead, you'll have to use a heuristic or approximation, or accept a solution that can take exponential time in the worst case. Dijkstra's algorithm won't suffice.

Strictly speaking, the standard formulation of the TSP doesn't allow you to visit any point more than once. However, in this situation allowing you to visit a point more than once doesn't make the problem any easier, since visiting a point more than once will never help you find a shorter solution.

Perhaps the following paper will be useful:

The L1 Traveling Salesman Problem. Donald C.S. Allison, M.T. Noga, Information Processing Letters, vol 18, 1984, pp.195-199.

# Answer
> 1 votes
As D.W. mentioned, this is a version of the Travelling Salesman Problem.

TSP is (in general) NP-hard, which is unfortunate. For small enough numbers of points (10-ish) you could try all the permutations by brute force, but the $O(n!)$ complexity is nasty.

Since your method of computing the cost of travel is the $L\_1$ metric (once again, as D.W. pointed out before me), you can use Christofides algorithm, which guarantees a $3\over 2$ approximation ratio.

Note that TSP is usually concerned with closed tours (source = destination), so you might need to make some modifications. This will be simple for the brute-force approach, but I'm not aware of an elegant modification for Christofides.

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


# Question
Title: Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?
In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$.

Intuitively, with a fixed parameter $k$, in the worst case, the exhaustive search needs to check whether every vertex subset of size $k$ is vertex cover. The number of vertex subset of size $k$ is $\dbinom{n}{k}$, and we have $\dbinom{n}{k}=O(n^{k})$. Meanwhile, the number of steps to check a vertex subset of size $k$ is $O(kn)$, since we only need to verify whether the number of edge connected to or contained in the vertex subset is $m$, where $m$ is the number of edge in the graph. Thus, the time complexity of the exhaustive search is $O(k n^{k+1})$.

Is there any problem with my above analysis? And how to get a exhaustive search algorithm of time complexity $2^{k}n^{O(1)}$?

# Answer
The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading.

The classic algorithm goes as follows:

1. If all edges are covered, succeed.
2. If you already have chosen $k$ vertices, fail.
3. Consider the first uncovered edge.
4. One of its endpoints must be in the vertex cover. This leads to two possibilities, on which you recurse. In each branch of the recursion, continue at 1.

The recursion has depth $k$ and branches binarily. Thus there are $2^k$ paths in the search tree. Each step can be processed in polynomial time.

\[EDIT\]

Success in Step 1 means that the current candidate set is indeed a vertex cover, so the algorithm may accept.

Failure in Step 2 means that the current candidate set cannot be extended to a vertex cover of size $k$, so the search must continue in another branch.

Also, thanks to chi for pointing out an ambiguity.
> 8 votes

# Answer
This is just a Hint :

Let me give you a different algorithm. Suppose vertices of the input graph $G$ are numbered from $v\_1$ to $v\_n$. Now assume you have a size $k+1$ solution set i.e. a vertex cover set. How much time it will take to compress the solution set of size $k+1$ to $k$ ( think ).

Algorithm :

1. Initially put $v\_1,v\_2,\cdots v\_{k+1}$ into solution size.
2. Check is it possible to compress the above set of size $k+1$ to $k$ vertex cover
3. If yes then do it

Now how to check whether it is possible or not to compress the vertex cover of size $k+1$ to size $k$ is by brute forcing on set of size $k+1$. Try all $k+1\choose k$ subsets of vertex cover of size $k+1$ and check whether they are vertex cover or not.
> 1 votes

---
Tags: np-complete, parameterized-complexity
---


# Question
Title: How to properly calculate the order of growth of an exponential algorithm?
I'm reading SICP, and I'm a little bit confuse about this statement:

> Consider the problem of computing the exponential of a given number. We would like a procedure that takes as arguments a base b and a positive integer exponent n and computes b n . One way to do this is via the recursive definition
>
> ```
> b n = b ⋅ b n − 1 ,
> b 0 = 1
>
> ```
>
> which translates readily into the procedure
>
> ```
> (define (expt b n)
>   (if (= n 0)
>       1
>       (* b (expt b (- n 1)))))
>
> ```
>
> This is a linear recursive process, which requires Θ ( n ) steps and Θ ( n ) space.

I did a tree illustrating the process generated by the procedure:

```
(expt 2 2)
|
|
|
(expt 2 1)

```

Which makes the statement "This is a linear recursive process, which requires Θ ( n ) steps and Θ ( n ) space." true. But when I use a substitution model, it seems that requires 0 ( n ^ 2) steps and space:

```
(expt 2 2)
    (* 2 (expt 2 1))
    (* 2 2)
4

```

Thank you.

# Answer
> 1 votes
In this answer we assume the arithmetic model of computation, in which each arithmetic operation has cost 1.

The question has bad notation. Define function `expt b n` to compute `b^n` as:

```
expt b 0 = 1
expt b n = b ⋅ expt b (n − 1)

```

Computing `expt b n` requires computing `n-1`, computing `expt b (n-1)`, and multiplying that expression by `b`. So the cost of `expt b n` is $2 +$ the cost of `expt b (n-1)`. `expt b 0` has cost 0.

Putting the above together, we see the cost of `exp b n` is $2 +$ the cost of `exp b (n-1)`, $= 4 +$ the cost of `exp b (n-2)`, $\ldots$, $= 2n +$ the cost of `exp b 0`, $= 2n$.

---
Tags: algorithms
---


# Question
Title: What does machine code actually look like while being run?
When machine code is actually being executed by hardware and the CPU, what does it look like?

Would it look like binary, as in instructions being represented by ones and zeros, or would it be something made up of hexadecimal digits where opcodes are bytes presented as hex numbers which can be broken back down into binary numbers, like bytecode?

# Answer
> 38 votes
The best answer I can give is, it doesn't really "look" like anything. The instruction currently being executed by the CPU is represented by a series of wires, some of which have a high voltage, some of which have a low voltage.

You can interpret the high and low voltages as zeroes and ones, but you can equally well interpret groups of high and low voltages as hexadecimal digits, or as an assembly instruction like `ADD $0 $1` (which is closest to how the CPU interprets it). These numbers and mnemonics themselves are conveniences for humans to read; internally, it's nothing but voltages on wires.

Out of these options, binary is "closest to the metal", in that the zeroes and ones map directly to the high and low voltages on the wires. But none of the others are incorrect, and they're frequently more useful: there's a reason people look at hex-dumps of executables, but almost never binary-dumps.

# Answer
> 11 votes
"Look like" implies a metaphor. If we take "what will it look like" literally, it's going to look like a fancy etched piece of silicon sitting on its motherboard. Clearly metaphor was the goal. To build the metaphor, we need to look at what it really is first. Then we can build a metaphor that is acceptable. This is a bit long, but fortunately, it ends with a **video** metaphor for you.

The machine code is actually stored in memory as bits. Memory chips are typically DRAM, which stores those bits as voltages across a capacitor and electrons. The two are connected -- its hard to talk about the voltages without the electrons. Sometimes its convenient to talk about one or the other, but understand that where one goes, the other follows.

The journey of machine code starts with a "fetch." A particular pattern of voltages is applied to the wires of the RAM chip indicating that this particular set of bits should be sent to the CPU. Why? Don't know don't care. Typically that signal is sent because the CPU finished the last instruction and is asking for a new one as an instinctive response, like a dog asking for a second treat after you gave it the first one. This process starts off with some primordial kick in the pants caused by a natural instability in the CPU. When a power supply applies a constant voltage to the chip, the rises in voltage eventually lead to the CPU putting the correct voltages on the RAM chips to go get the first instructions (I'm handwaving the BIOS layer a bit, because its not important to the story. Look it up).

Modern memory streams data in parallel. This means the bits that make up the machine code are split up into "lanes" (32 or 64 are common) which is the logical way of saying the 32/64 wires from the RAM to the CPU. The voltage on those lines is raised and lowered as needed to transmit it into the CPU.

Once its in the CPU it can go do its work. This is the realm of microarchitecture, and it can get complicated because this is literally a billion dollar industry. Those voltages affect transistors, which affect other voltages, in ways which we might describe as "adding bits" or "multiplication." They're really all just voltages that represent those bits, in the same way we might scribble the 5 character string "2+2=4" on a piece of paper and say we did mathematics. The pencil graphite is not the number two. It's just the physical representation we're using for that number.

So that's what the real system does, at a tremendously high level. I've skipped well... pretty much everything... but it's decent enough to be able to get back to your actual question. What would it \[metaphorically\] look like?

**As it so happens, I think Martin Molin may have constructed the best metaphor, with his Marble Machine.** The machine code is encoded (by hand) onto some Lego Technics strips in the middle as pegs, rather than voltages on a capacitor. This is more like EPROM than DRAM, but both hold data. The marbles are like the electrons, being moved about by voltages (or gravity, in the case of marbles). And as the electrons move, they apply force to gates which do things.

His machine is simple, compared to a modern CPU, but it's not all that bad, as far as metaphors go. *And it's catchy!*

# Answer
> 10 votes
Check out this video, in particular 1:00 to 1:17. That's exactly what it looks like when a program is running on a computer. The two rows of lights show the current contents of the address register and the data register. The PDP-11 doesn't have an instruction register, but if there were one and there were lights on the front to show its contents, it would look pretty much the same. 16 lights- some of them on, some of them off.

If you really liked flashing lights, you could have more lights to show the current contents of the six registers, the stack pointer, the program counter... for a further 32768 lights you could have a light for each bit of the cache. You could even have a light for each bit of memory... but that really would be a lot of lights.

This is a PDP11-70 which runs at 15.2 MHz, and each instruction takes about 1.5 microseconds to execute. The human eye can detect changes down to 1/10 second, and in that time, the PDP-11 can execute 60,000 instructions. Basically, everything is a blur.

# Answer
> 7 votes
The hardware designers implementing and testing (and testing and testing) the processor actually do use visual models to see what their designs are doing. Most (if not all) HDL simulation tools output wave views of all of the registers and wires to allow for easy debugging. The screenshot below (taken from here) shows these waves from the VCS simulator for a RISC-V processor running a few instructions.

This is a pretty simple example that shows a small subset of the logic involved in a full processor design. You could open these views up for the entire processor and watch the data propagate through the logic. If you want to see the machine code running, as you mentioned, you could look at the waves for the instruction register or the bus the processor uses to read the instructions out of memory. Most wave viewers have flexible viewing options for buses and registers that let you display their values as binary, hex, octal, and even as enum labels. In some, you can even define your own functions for mapping bit patterns do displayed values.

It's worth noting that this is just a representation of a simulation of the processor. There's no way to get these kinds of views for an already-fabricated processor chip.

# Answer
> 2 votes
Imagine a blind man stumbling down a alley under construction. Everywhere there are holes and rifts, so naturally he should fall. Not this blind man, for he has a paper scroll with instructions, when to wait, when to move, where to move and how to manipulate his environment to reach the end of the road. That is what assembly is, a blindly followed lists of instructions- they only make sense for this alley and for this blind man. You can in theory even reconstruct a 3d model from the instructions alone (Decompiling).

Every change to the platform, make it necessary to recompile the instructions for the blind man. You need to know the hardware(the layout of the construction site), the human typed intention instructions (High Level Code ) like "I want you to jump over all fences you encounter in a row until you haven 12 fences behind you" and the abilitys of the blind men (CPU). Does he have short term memory, the ability to do several things at once?

Taking all these informations and forging a coherent instruction scroll is the job of the compiler.

So can i describe how a programm looks? No. But can we describe how it would feel to execute it? Yes, it would feel like a jump and run, like mirrors-edge without seeing something, following a precise list of instructions, wherever it may take you.

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


# Question
Title: Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer?
Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.

Here is the problem description:

> For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
>
> The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
>
> You can assume that no duplicate edges will appear in edges. Since all edges are undirected, \[0, 1\] is the same as \[1, 0\] and thus will not appear together in edges.

**Example 1 :**

Input: n = 4, edges = \[\[1, 0\], \[1, 2\], \[1, 3\]\]

```
    0
    |
    1
   / \
  2   3

```

Output: 1

**Example 2 :**

Input: n = 6, edges = \[\[0, 3\], \[1, 3\], \[2, 3\], \[4, 3\], \[5, 4\]\]

```
 0  1  2
  \ | /
    3
    |
    4
    |
    5

```

Output: 3, 4

Here is the solution I tried to understand:

> The basic idea is "keep deleting leaves layer-by-layer, until reach the root."
>
> Specifically, first find all the leaves, then remove them. After removing, some nodes will become new leaves. So we can continue remove them. Eventually, there is only 1 or 2 nodes left. If there is only one node left, it is the root. If there are 2 nodes, either of them could be a possible root.

I'm not sure I understand it so I could explain it to somebody. Why does deleting leaves layer-by-layer give us the answer?

# Answer
Let $T$ be a tree, and let $T'$ be the tree formed from $T$ by removing all leaves (vertices of degree 1). Assume that $T$ contains at least three vertices, so that $T'$ is not empty. This implies that every leaf $f \in T$ has a (unique) neighbor $p(f) \in T$ which is not a leaf.

For $v \in T$, denote by $h\_v(T)$ the height of $T$ when rooted at $v$. I claim that the following hold:

> For every vertex $v \in T'$, $$ h\_v(T) = h\_v(T') + 1. $$ For every leaf $f \in T \setminus T'$, $$ h\_f(T) = h\_{p(f)}(T) + 1. $$

For the first claim, consider $T$ rooted at a non-leaf $v$. The height of $T$ is the length of the maximal root-to-leaf path. Every such path gets shortened by one in $T'$, implying that $h\_v(T) = h\_v(T') + 1$.

For the second claim, let $x$ be a leaf farthest away from $p(f)$. We can assuming that $x \neq f$ since $p(f)$ has at least two neighbors, and $f$ is at minimal distance from $p(f)$. Clearly $d(f,x) = d(p(f),x) + 1$, and so $h\_f(T) \geq h\_{p(f)}(T) + 1$. The other direction follows from the triangle inequality, which implies that $d(f,y) \leq d(p(f),y) + 1$ for all nodes $y$.

**The algorithm.** If $T$ contains one or two vertices, then clearly all vertices are *centers* (roots of minimum height trees). Otherwise, by the second claim, no leaf can be a center, and so by the first claim, the centers of $T$ are the same as the centers of $T'$. This suggests the following algorithm for computing the centers of $T$:

> 1. While $T$ contains at least three vertices, remove all leaves of $T$.
> 2. Once $T$ contains one or two vertices, return all vertices of $T$.

The correctness of the algorithm follows the reasoning stated above.
> 6 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: Confusion about the definition of de Bruijn terms in the TAPL book
I'm working through Types and Programming Languages right now, and I'm a little confused about the recursive definition given for nameless/de Bruijn terms (chapter 6, definition 6.1.2). Below is the definition given:

> Let $\mathcal{T}$ be the smallest family of sets $\\{\mathcal{T}\_0, \mathcal{T}\_1, \mathcal{T}\_2, \ldots \\}$ such that
>
> 1. $k \in \mathcal{T}\_n$ whenever $0 \leq k \< n$;
> 2. if $t\_1 \in \mathcal{T}\_n$ and $n \> 0$, then $\lambda.t\_1 \in \mathcal{T}\_{n-1}$;
> 3. if $t\_i \in \mathcal{T}\_n$ and $t\_2 \in \mathcal{T}\_n$, then $(t\_1 t\_2) \in \mathcal{T}\_n$.

It further clarifies that the elements of $\mathcal{T}\_n$ are terms with *at most* $n$ free variables, numbered between $0$ and $n-1$.

I think I understand the first two points, but the third is confusing me. Here's my understanding of what the points mean:

1. The numbers $0, 1, \ldots, n-1$ are all terms in $\mathcal{T}\_n$ (representing $n$ unbound variables).
2. $t\_1$ has at most $n$ free variables, and $\lambda. t\_1$ binds a single variable ($0$), so it has at most $n-1$ free variables.

Assuming these are correct, my current feeling about point 3 is that $(t\_1 t\_2)$ should actually be in $\mathcal{T}\_{2n}$, because the resultant term will have up to $2n$ free variables ($n$ each). I don't follow how $(t\_1 t\_2) \in \mathcal{T}\_n$.

Could somebody help correct my understanding?

# Answer
The $n$ isn't indexing how many *references to* variables there are, it's indexing how many free variables are able to be referred to.

You can think of $0,1,\dots,n-1$ as being variables $v\_0,v\_1,\dots,v\_{n-1}$. A term in $\mathcal T\_n$ is a term that is allowed to refer to variables $v\_0$ through $v\_{n-1}$. If you have two terms of $\mathcal T\_n$, then each is allowed to use variables $v\_0$ to $v\_{n-1}$. If you combine them into a new compound term, i.e. $(t\_1, t\_2)$, then that compound term still only refers to/uses the free variables $v\_0$ through $v\_{n-1}$. A use of a free variable $v\_{n+4}$ hasn't suddenly appeared.

In the $\lambda.t\_1\in\mathcal T\_{n-1}$ case, while $t\_1$ can contain an instance of $n-1$, i.e. an occurrence of $v\_{n-1}$, such an occurence doesn't refer to a *free* variable. It refers to the variable bound by the $\lambda$. (Or $v\_0$ doesn't depending on the convention: de Bruijn levels vs de Bruijn indices.) You could describe this as $\mathcal T\_n$ only allows occurrences of $v\_m$ if $v\_m$ is under at least $m-n+1$ lambdas. From this perspective, $(t\_1,t\_2)\in\mathcal T\_n$ when $t\_1,t\_2\in\mathcal T\_n$, is just saying that if all occurrences of $v\_m$ in $t\_1$ and $t\_2$ occur under at least $m-n+1$ lambdas, then they still occur under at least $m-n+1$ lambdas in $(t\_1,t\_2)$ since we haven't added or removed any lambdas.
> 5 votes

# Answer
This is crucial:

> It further clarifies that the elements of $\mathcal{T}\_n$ are terms with *at most* $n$ free variables, numbered between $0$ and $n-1$.

Then, in the rest of your argument, you forgot the "numbered between $0$ and $n-1$" part.

Item 3 states that, if $t\_1$ has its free variables among $\\{0,\ldots,n-1\\}$ and $t\_2$ also has its free variables among $\\{0,\ldots,n-1\\}$, then $(t\_1 t\_2)$ has its free variables among $\\{0,\ldots,n-1\\}$.

So, your issue was that it is not enough to count the number of free variables in $t\_1$ and $t\_2$, since knowing only that we can only conclude that $(t\_1t\_2)$ doubles the number of free variables (at most). We need to remember that the free variables are actually the same.
> 4 votes

---
Tags: programming-languages, lambda-calculus, type-theory, types-and-programming-languages
---


title: CPU pipelining stages

text:
# Question
Title: CPU pipelining stages
I have read that in some pipelined architectures, memory access requires more than just one clock cycle. In that case how does processor handles the next instruction if the next instruction tries to access something the previous memory instruction has yet to write to its register files?

# Answer
> 3 votes
There are many ways this kind of situation be handled.

1. Clever compilers

If you are are writing the contents of, lets say register 5 to the memory location 0x12345, and the next instruction is reading from the memory location 0x12345 and the variable allocated at memory location 0x12345 is not "volatile", compiler will optimize your code so that the next instruction will use the contents of register 5, instead of reading data from the memory.

2. Instruction reordering

Ordering of the instructions are changed so that the next instruction is pushed down, as far as required without compromising the outcome of the program. This way, more non-dependent instruction can be executed until the memory write is complete.

3. Multiple threads

When the scheduler detects that there is a read after write dependency, it can pick another thread for thread for the IF stage. That way, the current thread will stay inactive until the memory write is complete. Once completed it becomes active again, and will get picked up by the scheduler when a similar situation arises for the current thread.

4. Bubbles

And of course, you can have many bubbles in the pipeline, until the write is complete :-). BTW, this is a bad idea.

---
Tags: computer-architecture, cpu-pipelines, mips
---


# Question
Title: Minimise given size using dynamic programming
> Given numbers $0\<x\_1\<x\_2\< \dots\<x\_{n^2}\<1,$ for every subset of $n$ of them $x\_{i\_1}\<x\_{i\_2}\< \dots\<x\_{i\_n},$ let us consider the size: $$\max\\{x\_{i\_1}, x\_{i\_2}-x\_{i\_1}, x\_{i\_3}-x\_{i\_2},\dots,x\_{i\_n}-x\_{i\_{n-1}},1-x\_{i\_n}\\}$$
>
> Give an algorithm to find the minimal size that subset of $n$ numbers can achieve.

My thoughts:

I would like to use dynamic programming.

I started by defining the following:

$$d(1) = x\_{i\_1}, d(j)=\max\\{d(j-1), x\_{i\_j}-x\_{i\_{j-1}}\\}$$

The solution to the problem will have to minimise the following:

$$\max\\{d(n),1-x\_{i\_n}\\}$$

---

I got stuck here, and my question is how can I continue to finish the solution.

Any help is appreciated.

# Answer
A dynamic programming approach would be: $f (p, k)$ is the minimum size when we considered prefix $\\{x\_1, x\_2, \ldots, x\_p\\}$, and selected exactly $k$ items from it, the last one being $x\_p$. We add sentinels $x\_0 = 0$ and $x\_{n^2 + 1} = 1$ for our comfort.

Base: $f (0, 0) = 0$.

Transitions: $f (p, k) = \min\limits\_{q = 1, 2, \ldots, p - 1} \max \left\\{f (q, k - 1), x\_p - x\_q\right\\}$.

Answer: $f (n^2 + 1, n + 1)$, the point number $n + 1$ being the added value $x\_{n^2 + 1} = 1$.

In total, this takes $O(n^2)$ to calculate a single $f (p, k)$, and there are $O (n^3)$ such values, so the approach will take $O(n^5)$ time and $O(n^3)$ memory.

---

The memory could be reduced to $O(n^2)$ by calculating iteratively, like:

```
for k = 1, 2, ..., n+1:
    for p = 1, 2, ..., n^2 + 1:
        calculate f (p, k)

```

And storing $f (p, k)$ only for the current and the previous values of $k$ at every moment: the storage strategy can be to store $f (p, k)$ in `f[p][k mod 2]`.

---

The time could be perhaps reduced to $O(n^3)$ by altering the function to optimize the $O (n^2)$ transition cost to something like $O (1)$ amortized. But instead, let us consider another approach.

Say we want the answer to be at most $s$. We can then greedily construct a subset. First, let $x\_{i\_1}$ be the greatest possible: $i\_1 = \max i : x\_i \le s$. Next, let $x\_{i\_2}$ be the greatest possible: $i\_2 = \max i: x\_i - x\_{i\_1} \le s$. Then define $i\_3 = \max i: x\_i - x\_{i\_2} \le s$, and so on. If this leads to $x\_{i\_n}$ such that $1 - x\_{i\_n} \> s$, the answer can't be $s$. Otherwise, we just constructed a subset of $\le n$ elements with the answer at most $s$. As the value $i$ is always increasing, for a given fixed value $s$, the check whether $s$ can be the answer takes $O (n^2)$ time and $O (1)$ additional memory.

What's left is to run a binary search over the value $s$, and for each candidate $s$, execute the greedy algorithm above. The number of binary search iterations can be $\log n$ (there are $O (n^4)$ possible candidates for $s$), or $\log C$ where $C$ is the required precision. For example, if all $x\_i$ are integers from $0$ to $L$, we have a binary search over integers from $0$ to $L \cdot n^2$, so it will complete in $O (\log (L \cdot n^2))$.

In total, this approach takes $O (n^2 \log n)$ or $O (n^2 \log C)$, which is better than an optimized dynamic programming approach would achieve.
> 2 votes

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


title: Probabilisitc timed automaton

text:
# Question
Title: Probabilisitc timed automaton
I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP. However, is there anything else? Are they still memoryless? I am not able to find any information about this topic.

# Answer
> 1 votes
The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different:

* MDPs typically have a reward function assigned, while PTAs do not necessarily have to have them.
* It is a bit imprecise to state that the "objectives is to solve the non-determinism of a MDP" -- it depends on what you want to do. PTAs are foremost models that you can analyse. Resolving the non-determinism means computing a policy, which makes sense if you have some kind of optimization criterion that you want to follow. This could be a temporal logic formula.
* In MDPs, the classical question is to find a policy that maximizes the limsup average payoff or the discounted payoff. In the latter case, there exist optimal memoryless policies (which is the result that you refer to). In PTAs, asking the same question is kind-of odd as the number of states in PTAs is *infinite* and there is (by default) nothing to optimize. A state consists of a *location* and a *valuation to the clocks*. This is already the case for timed automata, from which PTAs inherit many of their properties (and hardness results).
* The questions typically asked for PTAs are whether there exist policies that raise the probability of some temporal property holding along a trace over some given limit. A paper my Norman et al. (http://www.prismmodelchecker.org/papers/fmsd-ptas.pdf) contains details. They also define reward structures for PTAs, but the do not need to be concerned with discounted payoff optimization, like it is common in the MDP research case.

---
Tags: automata, probability-theory, markov-chains
---


# Question
Title: Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$
I'm trying to design a CFG that accept the words of the following language:

$$L = \\{a^i(b+c)^jd^k \mid i\<j+k; \quad i,j,k\>0\\}$$

My first approximation would be to do $i = j+k$ as something like:

$S\to aSd \mid X$

$X\to aXY \mid aY $

$Y\to b \mid c$

But then I don't know how to make the jump to the $\<$.

# Answer
Whenever you see a condition $i\<j+k$, you can translate that to the condition $i+\ell=j+k$ where $\ell\>0$, then use the methods you know for handling $=$ instead of $\<$.

See our reference question on this subject for more systematic answers.
> 1 votes

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


title: $DTIME(f(n)) \subset of DSPACE(f(n))$

text:
# Question
Title: $DTIME(f(n)) \subset of DSPACE(f(n))$
I think this is again an easy one:

> $DTIME(f(n)) \subset DSPACE(f(n))$

They say its trivial but I dont see it, why?

And would

> $DTIME(f(n^2)) \subset DSPACE(f(n^2))$

also be true? if yes why or why not?

# Answer
In each time step, the Turing machine can only move one position. Therefore, after $T$ time steps, the Turing machine can only have visited at most $T$ different positions, so its space usage (the number of cells it has visited or written to) must be at most $T$. Thus, the space complexity of any Turing machine is at most its time complexity.
> 1 votes

# Answer
If space is greater than time, as it must surf the space (in the related Turing machine), it will be contradicted by time is less than space. Hence, we can find that all problems which are in $DTIME(f(n))$ are in $DSPACE(f(n))$. and the proof is completed.

On the other hand, the size of input is important. Hence, if we set $m = n^2$ we reach to the first relation. Hence, it is true again.
> 1 votes

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


title: Resolution of Barber paradox

text:
# Question
Title: Resolution of Barber paradox
I am trying to prove using the resolution technique that the following two clauses are contradicting:

1. $\forall\_x Shaves(Barber, x) \iff \neg Shaves(x, x)$
2. $\exists\_x Shaves(x, Barber)$

After turing those into the conjunctive normal form and skolemization I get the following clauses:

1. $\neg Shaves(Barber, x)\ \lor\ \neg Shaves(x, x)$
2. $Shaves(Barber, x)\ \lor\ Shaves(x, x)$
3. $Shaves(Someone, Barber)$

where $Someone$ is a Skolem constant (a Skolem function of of zero arity).

I am unable to prove that this set of clauses is contradicting. It looks like something is missing. Shouldn't there be a clause, which prevents $Someone$ from being a barber as well?

# Answer
> 5 votes
No, you don't need to specially add any such clause.

Here's where I think you might have gone wrong. The result is not 3 clauses (3 conjunctions). The result is a bunch of clauses. We get one clause of the form $\neg Shaves(Barber, x)\ \lor\ \neg Shaves(x, x)$ for each $x$, one of the form $Shaves(Barber, x)\ \lor\ Shaves(x, x)$ for each $x$, and one last clause $Shaves(Someone, Barber)$. Thus, if there are $n$ people ($n$ possible values of $x$), the CNF form has $2n+1$ clauses in it.

Finally, note that the Barber is one of those $n$ people. Thus, for the clauses corresponding to the case $x=Barber$, we get a clause $\neg Shaves(Barber, Barber)\ \lor\ \neg Shaves(Barber, Barber)$ and a clause $Shaves(Barber, Barber)\ \lor\ Shaves(Barber, Barber)$. Now you should be able to find a contradiction in there.

---
Tags: first-order-logic
---


# Question
Title: Lower upper bound on # variables in k-SAT with m clauses
If I have an instance of $k$-SAT with $m$ clauses, then a trivial upper bound on the number of variables $n$ is given by $n \leq mk$. But we can only have $n = mk$ when no variable is repeated and that would be a trivial yes-case of k-SAT. I am making some running time analysis based on number of clauses, and therefore need to eliminate $n$ from my formula.

So my question is, can I make a lower upper bound on the number of variables, above which the instances will always be trivial?

I have a feeling that $\frac{1}{2}mk$ should be possible (I even think I had the argument for this in my head at some point), because $mk$ is actually an upper bound on the number of literals, not variables, but I can't be sure that all literals are present in both negated and unnegated form, and therefore can't seem to find an argument for this.

# Answer
> 1 votes
If you want to prove the worst-case running time of your algorithm, you probably don't need to prove that. It's probably enough that there *exists* instances of SAT with (say) $\frac12 mk$ variables that are NP-hard; and that can be proven.

When each variable occurs only twice in the formula, SAT can be solved in polynomial time (via resolution).

With the restriction that each variable can occur up to three times in the formula, SAT remains NP-hard. (Proof: start with an ordinary CNF formula $\varphi$. If $x\_i$ appears $k$ times, introduce variables $x\_{i,1},\dots,x\_{i,k}$, replace the $j$th occurrence of $x\_i$ with $x\_{i,j}$, and add clauses for $\neg x\_{i,1} \lor x\_{i,2},\neg x\_{i,2} \lor x\_{i,3},\dots,\neg x\_{i,k-1} \lor x\_{i,k}, \neg x\_{i,k} \lor x\_{i,1}$.)

Therefore, there exists a class of instances of $k$-SAT with $m$ clauses and $\frac{1}{3} mk$ variables, such that solving those instances is NP-hard.

To answer your original question, there is no useful answer to your original question. For all $\varepsilon\>0$, there exists a class of instances of $k$-SAT with $m$ clauses and $(1-\varepsilon)mk$ variables that is NP-hard. In particular, take an ordinary CNF formula $\varphi$ with $n$ variables and then just append useless clauses of the form $x\_{t} \lor x\_{t+1} \lor \cdots \lor x\_{t+k}$; each useless clause mentions $k$ new variables that appear only in that one clause and nowhere else. The resulting formula is exactly as hard as $\varphi$, but now has a number of variables that is an arbitrarily large fraction of $mk$.

---
Tags: satisfiability
---


# Question
Title: How to design an algorithm to generate balanced teams?
I am trying to design an algorithm that allows to create balanced teams for a summer camp. There are about a 100 campers of different ages. Gender ratio isn't necessarily 50/50. Also there are a different number of campers for each age group. The idea is to create fair and well-balanced teams while having approximately the same amount of boys and girls in each team as well as the same number of kids in each age group per team. The usual approach is to make a list and manually make the teams (prior to the camp), but this is stupid and has a lot of balancing issues.

My idea is to create an algorithm based on some kind of score (eg. time to run an obstacle course) simple enough to be programmed in excel or some other tool everybody knows how to use. My first idea of how it could look like is:

1. Separating boys and girls into different categories
2. Ordering them from fast to slow (this should still make it so that the oldest kids are roughly at the top of the list and the slowest at the bottom)
3. Design algorithm that creates teams with the same averages while taking kids from all over the list. This is the part I'm having trouble with because I don't want to use iterative methods.
4. Once I have the boys teams and girl teams ready mix them together so that

4.1 Each group has the same amount of kids (number of boys + number of girls)

4.2 The average time of each team should be as close as possible (here are iterative methods ok because there are less combinations)

If anyone has experience, ideas or has seen something similar I'd gladly read it.

# Answer
There's probably a tradeoff between ease of implementation and the quality of the solution. I'll list a few possible approaches. The first step is to pick a way to measure the quality (imbalance/unfairness) of a proposed solution. One possibility would be the variance of the team averages; another would be the gap between the largest team average and the smallest team average. Then, pick one of the following methods to choose an assignment that is as good as possible, under this quality measure:

1. **Random.** The simplest to implement method is random assignment. Randomly assign each kid to a team (subject to the requirement that each team has the same number of boys and same number of girls). Measure the quality of each assignment. Do this for 1000 random assignments. Pick the best one. That's very easy to implement.

Here is a simple way to do the random assignment: randomly re-order the list of kids, and put the first $k$ into the first team, the next $k$ into the second team, and so on, where $k$ is the desired team size. To also ensure gender equality, do this separately for the boys and girls.
2. **A greedy heuristic.** A different approach is to assign the kids to teams in a heuristic way. Sort the kids from slowest to fasteast. Now iterate over the kids in this order and, for each kid, assign that kid to a team. Assign the kid to the fastest team (measured by their average speed given the current assignment). If some teams currently have fewer members than others, only choose among the teams with the fewest members. To ensure gender equality, when a boy picks a team, have them only pick among the teams with the fewest number of boys; and symmetrically for girls. There are other heuristics you could consider, but this seems like it might yield good results.
3. **Random + heuristic.** You can combine the first two ideas. First, randomly pick a fraction of the kids, and then randomly assign them to teams. Second, assign the rest of the kids via the above heuristic. You can repeat 1000 times and take the best assignment seen so far.

It will probably help to ensure that the initial random assignment assigns the same number of boys and girls to each team.
4. **Simulated annealing.** A more sophisticated method is to start with a random assignment and use simulated annealing to improve it. In each step, you randomly pick a pair of kids of the same gender but from different teams, and you consider what would happen if you swapped them. Depending on how this affects the quality of the solution, you decide whether to make the swap or not, in a particular way. Simulated annealing might improve on the other methods, but it is also a little fiddly, as there are parameters you have to tune to get it to work to best effect.
5. **Integer linear programming.** If you're willing to measure quality by the difference between the largest team average and the smallest team average, a more sophisticated method still is to use integer linear programming. You have a zero-or-one integer variable $x\_{i,j}$ indicating that the $i$th kid is assigned to the $j$th team, and then you can write down linear inequalities that capture the requirements on a solution to be valid. This can potentially give you the optimal solution.

I suspect the latter two approaches are more complicated than is really necessary and just trying a bunch of random assignments might be good enough.

In general, your problem is NP-hard; it is as hard as bin-packing. If you cared enough you could investigate the heuristics and approximations for bin-packing and try seeing if you can adapt them to your problem. I don't know that that will be worth the effort.
> 3 votes

---
Tags: algorithms
---


title: Decomposing NP-hard sets

text:
# Question
Title: Decomposing NP-hard sets
Suppose A∪B is NP-hard, does it follow that A is NP-hard or B is NP-hard?

Equivalently, is the property "not NP-hard" closed under union?

A related question was already asked:

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

but it seems no consensus was formed.

# Answer
If $P = NP$, then the only not-$NP$-hard sets are $\emptyset$ and $\Sigma^\*$, and the statement trivially holds. So let us assume $P \neq NP$.

Then whenever $X$ is $NP$-hard, both $X$ and $X^C$ must contain an infinite c.e. set, namely "the image of the positive SAT-instances under the reduction" and "the image of the negative SAT-instances under the reduction". For if either of these sets were finite, we could get a P-algorithm for SAT.

By diagonalization, we can construct some set $X$ such that neither $X$ nor $X^C$ contain an infinite c.e.-set. Then $SAT \cap X$ and $SAT \cap X^C$ do not contain infinite c.e. sets, hence are both not $NP$-hard. But their union is SAT, and hence $NP$-hard.

To get a decidable counterexample, it should suffice to note that if $X$ is NP-hard, we not only have infinite c.e.~subsets of $X$ and $X^C$, but actually ones which can be computed in exponential time. Diagonalizing against those should doable in a decidable way; but I have not worked out the details.
> 2 votes

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


title: How can two maps be compared?

text:
# Question
Title: How can two maps be compared?
The scenario is the creation of street maps. For example, two people at Open Street map edit the same part of the map at the same time. Now the one that submits the data later should see a diff. Assume they both started with no vertex, but they had the same aerial image as a basis to create the digital map.

Let's define a street map $M$ as a set of vertices and edges $M := (V, E)$ with

\begin{align} V &\subseteq \mathbb{R}^2\\ E &\subseteq V \times V \end{align}

I want to compare two maps $M\_1$ and $M\_2$, where $M\_1$ was there first. Think of two teams creatings a map from satellite images on Open Street Maps (OSM).

What I want to understand is:

* How many roads (edges) are new?
* How many roads (edges) were removed?
* How many roads (edges) were changed?

I only could think of Dynamic Time Warping to get a score how much things have changed. But very likely no single vertex will be exactly the same, but most will be close.

## What is a change?

A "change" is fuzzy in this context. If it is only about a single vertex, I would say if the geo-positions of that vertex only changed by \< 10cm, it is for sure only a change. Likely also if it is less than 1m due to the lack of precision in GPS (and likely also the aerial image).

It is more complicated for streets which consist of multiple line segments and not necessarily the same number of line segments. If one knows which line segments should belong together, I would use the Douglas-Peucker algorithm to reduce the street with more line segments to have an equal amount of line segments as the second street. Then one can check if a single vertex is over the threshold to determine if a segment is different. In this case different would mean there is a "removed" and "new" segment.

But when we cannot have such a mapping I only see the possibility to check everything for change. And this does not cover the case of a change in between.

For example, obviously street (a) and street (b) have quite a bit in common, besides only point (a). They have the whole line segment AY in common.

```
a: A---------------------------------X

b: A---------------------Y
                          \
                           \---------Z

```

# Answer
As a map is a geometric object, you can use from the concept of **map matching** in computational geometry. Also, some measures like Frechet Distance could help you to compare two maps on the plane.
> 3 votes

# Answer
It seems the idea you are floating is some variation of graph edit distance. The concept is general, and you need to decide a couple of things to fit your application:

1. Representation of your type of graph (which I see you already described in OP)
2. Set of graph operations allowed to be performed. (you listed rather informally)
3. The cost of performing each operation (may be dependent on input graph on top of being dependent which operation is used.)
4. editing path --- description how each elementary operations can be composed together and how composing them effects the cost. Do the cost just add up? or just take the maximum cost of the two operations being composed? In simpler case this might be just a string of editing operations $$(e\_1,e\_2,\ldots,e\_n)$$ and the cost might simply be inductive as $$cost(e\_1,e\_2,\ldots,e\_n) = cost(e\_1) +cost(e\_2,\ldots,e\_n)$$

My description might be a bit too general. Maybe take a look at the basic example in the page I linked above first.

Editing cost also could reflects the idea of metric space, in particular: $$cost(e\_1) + cost(e\_2) \geq cost(e\_1,e\_2)$$ and $$0 = cost(id)$$ where $id$ stands for identity operation of doing nothing.

These two condition is the most important out of the standard four as pointed out by Lawvere's generalised metric space

---

For an advanced example, the algebraic description of tree-width, clique-width and rank-width can be thought of as instances of the more general view on graph edit distance I just mentioned.

This answer is relevant to my current research work.
> 2 votes

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


# Question
Title: Choosing Fitness function for float output in Genetic algorithm
I have a NN that has ten outputs. The output values range between 0 and 1. The elements in the target array are all zeros except one element, which is "one".

I am searching for a Fitness Function that will correctly evaluate (score) the Neural Networks.

Currently, I am trying to calculate the distance between the target and the output arrays. The issue is that at the beginning all my NNs return results that are very close to each other and I can't properly choose the fittest individuals.

For Example:

```
NN1 -> FF score:0.10030096 -> Rank?
NN2 -> FF score:0.09996143 -> Rank?
NN3 -> FF score:0.10015215 -> Rank?

```

Any suggestions?

# Answer
The standard solution is: Use a softmax layer at the output of your neural network, and use the cross-entropy loss as your fitness function.
> 0 votes

---
Tags: genetic-algorithms
---


# Question
Title: Efficient membership check in multiple ranges
Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l\_n$, upper bound $u\_n$).

The program receives a number $x$; it must return all ranges in $S$ that enclose $x$.

An example in practical terms: in timeseries data, you have a set of $n$ independent events that occur over ranges of times. Given a point in time, you want to find the events that coincided with that point.

The naîve $O(n)$ solution:

```
out ← {}
for r in S:
  if (r.l ≤ x and r.u ≥ x):
    out.add(r)
return out

```

Is there a strategy for sublinear membership checking (in terms of $n$)?

# Answer
> 1 votes
An interval tree can retrieve intervals containing a specified point in $O(\log n)$. If the set of intervals is fixed, it is very easy to implement.

---
Tags: complexity-theory, search-algorithms
---


title: Can we reduce an NP to an NP Problem?

text:
# Question
Title: Can we reduce an NP to an NP Problem?
Lets say Problem A,B are in NP.

Can we reduce Problem A to B? Meaning A $≤\_p$ B? or A $≤\_t$ B

Is there a difference in "hardness" of a Problem even in NP?

Or must Problem B at least be NP-Complete?

# Answer
It depends on the problems. Just knowing that $A$ and $B$ are in $NP$ doesn't tell you whether $A$ is reducible to $B$.

If $B$ is in $P$ and $A$ is $NP$-complete, then $A$ cannot be reduced to $B$ (unless $P=NP$).

If $A$ is in $P$ then it can be reduced to any problem $B$ except $\emptyset$ and $\Sigma^\*$.

If $B$ is $NP$-complete then any problem (in $NP$) can be reduced to it.
> 2 votes

# Answer
Ladner's theorem tells us that if $A$ is non-trivial, $A \<\_m B$ and $B$ is in $NP$, then there is some $C$ with $A \<\_m C \<\_m B$. Note that $A \<\_m C$ means that $A$ is polytime many-one reducible to $C$, but not vice versa.

So not only are there different levels of hardness inside $NP$, provided that $P \neq NP$, but these levels are even dense (between any two levels is another level).

Provided that $P \neq NP$, we can also get plenty of incomparable problems inside $NP$.
> 2 votes

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


# Question
Title: By what criteria is the base value selected in Rabin Karp algorithm?
In the Rabin Karp algorithm the rolling hash is calculated as follows:

```
H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0

```

where `a` is a constant. On what basis is this `a` selected? In Cormen they have used a value 10 and at some other places it is 26. By observation, when the string is of digits they have taken a = 10 and when the string is of English characters then they have taken a = 26. Is it not possible to compute the hash value using a = 10 for English characters. If not what flaws does it introduce or i am assuming it wrong. I would appreciate help.

# Answer
1. hash values, by definition, may collide
2. this hash is computed (implicitly) by modulo of 2^N if you use N-bit integers
3. recommended value of "a" is any large prime number, f.e. 123456791

With a=10, it will definitely still work, although you can easily build a hash collision. With a=123456791 you may need more time to build a hash collision, but they still exists. As D.W. said, it's better to have "a" coprime to 2^N and to hash size, so both a=10 and a=26 aren't the best choice, especially if you compute hashes of strings longer than N chars.

One more note - this formula is detail of rolling hash algorithm, not Rabin-Karp. Rabin-Karp string search algo may be used with arbitrary rolling hash, and moreover - AFAIR their own paper described this algo using CRC as rolling hash:
> 4 votes

# Answer
You can use any value you want, but it is best to choose a value that is relatively prime to the modulus, as that reduces the number of hash collisions.

For efficiency you might want to choose a value that is small (like 3), as that may make some computations faster.
> 4 votes

# Answer
If hash function uses 10, you cannot correctly compute string.

> Text : ABAAAK
>
> Pattern : ABA

Then, Let's compute by using value 10 for pattern P.

$ABA = 65\*10^2+66\*10^1+65\*10^0=7,225$

We can find match at shift 0, $ABA=ABA=7225$. But, we also can find match of hash value $ABA=AAK=7,225$ at shift 3.

It is the flaw of 10-base hash function for matching of upper alphabet string. If you use 26-base for this problem, $AAB=45,721 \neq AAK=45,705$.

Plz try yourself bro.
> 0 votes

---
Tags: algorithms, string-matching, rolling-hash
---


# Question
Title: How to find a possibility of match in Naive Bayes Classifier?
My math level is very very poor so I can't get the statistics.
Can anyone explain in simple words? I.e. if I have frequency data:

```
Apple:
    Colors:
        Green = 3, Red = 2, Orange = 0;
    Shape:
        Sphere = 5, Ellipsoid = 0.
Orange:
    Colors:
        Green = 0, Red = 0, Orange = 5;
    Shape:
        Sphere = 5, Ellipsoid = 0.

```

I have many so fruits with frequencies, of course.
**How can I get a possibility for object `{Color: Red, Shape: Sphere}` that it's an apple?**

# Answer
> 2 votes
Let $A$ and $O$ be the events apple and orange (fruit). Let $R$ and $S$ be the events red and sphere.

By Bayes' law, $$\Pr\[A | R \wedge S\] = \frac{ \Pr\[R \wedge S | A\] \Pr\[A\] }{ \Pr\[R \wedge S\] };$$ $$\Pr\[O | R \wedge S\] = \frac{ \Pr\[R \wedge S | O\] \Pr\[O\] }{ \Pr\[R \wedge S\] }.$$ By total probability adding to 1, we also have $$\Pr\[A | R \wedge S\] + \Pr\[O | R \wedge S\] = 1$$ and therefore $$\Pr\[R \wedge S | A\] \Pr\[A\] + \Pr\[R \wedge S | O\] \Pr\[O\] = \Pr\[R \wedge S\]$$ so $$\Pr\[A | R \wedge S\] = \frac{\Pr\[R \wedge S | A\] \Pr\[A\] }{ \Pr\[R \wedge S | A\] \Pr\[A\] + \Pr\[R \wedge S | O\] \Pr\[O\]}.$$ By the Naive Bayes assumption of independence of features conditioned on class, $$\Pr\[R \wedge S | A\] = \Pr\[R | A\] \Pr\[S | A\];$$ $$\Pr\[R \wedge S | O\] = \Pr\[R | O\] \Pr\[S | O\].$$ Putting it together, we get $$\Pr\[A | R \wedge S\] = \frac{\Pr\[R | A\] \Pr\[S | A\] \Pr\[A\] }{ \Pr\[R | A\] \Pr\[S | A\] \Pr\[A\] + \Pr\[R | O\] \Pr\[S | O\] \Pr\[O\]}.$$

Now plug and chug. From the data $\Pr\[R | A\] = \frac{ \Pr\[R \wedge A\] }{ \Pr\[A\] } = \frac{2}{5}$, etc. Note: I am assuming the empirical distribution is the true distribution, an assumption your teacher probably expects you to make but not made in practice.

---
Tags: classification, statistics
---


title: Centre, diameter, and radius of graph

text:
# Question
Title: Centre, diameter, and radius of graph
I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.

Ques1. If $x,y$ are two vertices such that distance between them is $D$, then is it true that any shortest path between them will contain at least one centre?

Ques2. If $D=2R$, then does the graph contains only one centre?

Ques3. Also, can we say that if $D\<\<2R$, then graph would contain a lot of centres? (Intuitively I feel so because in figure below, $D$ is smaller than $2R$, and graph contains a lot of centres, the red coloured vertices.)

# Answer
A quick way of gaining some confidence or disproving a conjecture is using a computer to generate examples.

For Q1, if $x,y \in V$ such that $d(x,y) = D$, it is not true that any shortest path between $x$ and $y$ contains at least one central vertex (highlighted in red). Here, you can walk from 1 to 6 via 9, 5, and 8 avoiding the red vertex.

For Q2, the answer is also no. Below is a graph whose radius is 2 and diameter is 4. It has 3 central vertices (highlighted in red).

You can use ideas from these counterexamples to optimize the graphs further.
> 3 votes

---
Tags: graphs, combinatorics, discrete-mathematics
---