title: An "easy" graph problem I can't solve

text:
# Question
Title: An "easy" graph problem I can't solve
The question is:

> A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2)
>
> And a origin vertex s.
>
> Write an efficient algorithm that finds the shortest paths (most easy in weight that is) from s to the rest of the vertices.

I really don't have a better idea than perform the Dijkstra algorithm, but I know it is not the right answer. Help anyone?

# Answer
For every edge $(u,v)$ with weight $2$, create a new node $w\_{u,v}$. Discard the edge $(u,v)$, and instead of it add two edges $(u,w\_{u,v})$ and $(w\_{u,v},v)$ with weight $1$.

Now you can use a standard unweighted pathfinding algorithm, such as BFS.
> 2 votes

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


# Question
Title: minimum insertions and deletions required to ensure that each value X occurs X times
I would like to brainstorm/get some advice/tips regarding the following question. Given an array,you can either insert elements or you can delete elements from it.Note the insertion/deletion must be done in such a way so that in the end,for any element X in the array,X occurs X times. The objective is to find the minimum no of moves you can make to achieve the desired result. For example if A is \[1,1,3,4,4,4\].Then we can delete one occurence of 1 and 3 respectively and add a 4 to give us \[1,4,4,4,4\].In the final array 1 occurs 1 time and 4 occurs 4 times.Answer is 3 Again if A is \[10,10,10\].Then you can simply remove all 10s to get 0.So the answer here is 3. One way of doing is to have a map that keeps track of how many times each value occurs. After this I tried using the approach mentioned in the below link(but it only handles deletions and not insertion) So I would like some tips on how to approach this problem while taking care of both insertion and deletions. ''' unordered map\<int, int\> map;

# Answer
Your approach seems good. Here is a high level description of the algorithm to solve this question:

1. Build a hashmap from the values in the array $A$ to the number of occurrences they have in that array. This can be done in $O(n)$, simply by going through $A$ and incrementing the count by $1$ for every element you see.
2. Start keeping track of the number of required insertion \ deletion operations. For simplicity, lets store it in a variable named $cnt$.
3. For every element $k$ in the hashmap, denote by $v(k)$ the number of occurrences it has in $A$. Then, do the following:

* Do $cnt\leftarrow cnt + \min(|v(k)-k|,v(k))$
4. Return the value of $cnt$

Basically, the algorithm tries to check for every value $k$ in $A$ which requires the least operations:

1. Inserting or deleting until there are $k$ copies of $k$: This will require $|v(k)-k|$ operations since there are currently $v(k)$ copies and we need exactly $k$ copies
2. Deleting until there aren't copies at all. This is the case in the example of the array $A=\[10,10,10\]$. In this case, we need $v(k)$ operations to delete all copies.

Those two cases cover all things we can do to make the array $A$ into a "correct" form. We will "fix" $A$ for a specific value $k$ by doing the case that requires the least operations, and hence we can calculate the number of required operations to "fix" a certain $k$ is: $\min(|v(k)-k|,v(k))$. Sum this up over all $k$'s, and you got yourself the answer!
> 1 votes

---
Tags: arrays
---


# Question
Title: What does it mean for a computer to be general-purpose?
There is a lot of Turing machine out there. Most of them are purpose-specific.

What make universal Turing machine universal? How do we know or prove if a computer is universal?

Edited: Is programmability of universal Turing machine the key to be universal?

# Answer
You're confusing a few concepts.

"General-purpose computer" is a high-level, not very well defined term. It's used to refer to computer hardware that is not designed for a specific task and should be able to accommodate most of today's usual (consumer) workloads with reasonable performance and efficiency. Most commercially sold computers and smartphones are considered general-purpose. Examples for non-general purpose hardware would be hardware for database servers or a computer for genome sequencing with additional circuitry or FPGA's.

A universal TM is a TM $A$ whose language is

$$ L(A) = \\{\langle M \rangle \\# w \mid M \text{ accepts } w \\} $$

This is just one of many equivalent ways to give the language. The point is that a universal TM can simulate any provided TM on any provided word.

If you "have" such a turing machine, it would be universal in the sense that you could use it to simulate any other turing machine. There isn't any meaning implied by the word "universal" other than that.

The term "universal computer" isn't used in computer science.

The turing machine is just a model for computability. It can be used to describe the process of computing anything that can be computed (cf. Church-Turing thesis). It's not an ideal model for computing by any other means.

Computer hardware is built to efficiently execute the widest variety of programs and therefore automatically strives to be like a universal turing machine. This, however, isn't really a goal per se. It's just a consequence of the power of the turing machine model.
> 4 votes

---
Tags: turing-machines, computer-architecture
---


# Question
Title: On counting number of vertices that have common neighbor
Suppose given a graph $G(V,E)$ that we want to count the number of pair of vertices that have common neighbor.

I think for any pair in $\binom{|V|}{2}$ we must check its neighbor that is common or not. So the running time is $O(V^3)$ in complete graphs.

My question is, are there simpler algorithm that run in $o(|V|^3)$?

# Answer
You can get a faster algorithm by using matrix multiplication. Let $A$ be the adjacency matrix of $G$, and compute $B=A^2$. Since $b\_{ik} = \sum\_{j=1}^{|V|} a\_{ij}a\_{jk}$, the entry $b\_{ik}$ is equal to the number of vertices that are adjacent to both $v\_i$ and $v\_k$. So, the total number of pairs that have a common neighbour is the number of non-zero entries in $B$.

Matrix multiplication can be done in $O(|V|^\omega)$, and counting the entries of $B$ in $O(|V|^2)$, so this algorithm runs in time $O(|V|^\omega)$. ($\omega$ is the smallest number s.t. any two $n\times n$ matrices can be computed in $O(n^\omega)$ time) Since $\omega \<3$, this algorithm runs in $o(|V|^3)$. How simple the algorithm will be depends on what algorithm you choose to do matrix multiplication.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Meaning of this two-variable asymptotic notation
What does $k \ln(k) = \Theta(n)$ mean? Does it mean that $k$ is a function of $n$ and we actually had better write $k(n)\ln(k(n)) = \Theta(n)$?

# Answer
It roughly means "for any two constants $0 \< c \< C$, the following holds whenever $k,n \in \mathbb{N}$ and $cn \leq k \ln k \leq Cn$".

For example, consider the claim "if $k = \Theta(n)$ then $(1+1/n)^k = \Theta(1)$". This means "for any two constants $0 \< c \< C$ there exist constants $0 \< m \< M$ such that following holds whenever $k,n \in \mathbb{N}$ and $cn \leq k \leq Cn$: $m \leq (1+1/n)^k \leq M$".

The assumptions on the domain of $k,n$ are usually clear from context, but do create an ambiguity, which is why the interpretation above is only rough.

---

Problem 3.2-8 from CLRS is as follows:

> Show that $k\ln k = \Theta(n)$ implies $k = \Theta\left(\frac{n}{\ln n}\right)$.

We can expand this as follows:

> For any two constants $0\<c\<C$ there exist constants $0\<m\<M$ such that the following holds: if $k,n \in \mathbb{N}$ satisfy $cn \leq k\ln k \leq Cn$ then $m\frac{n}{\ln n} \leq k \leq \frac{n}{\ln n}$.

However, this is certainly not the intended interpretation, since $\ln 1 = 0$, and so we get a division by zero! Instead, I propose the following interpretation:

> For any two constants $0\<c\<C$ there exist constants $0\<m\<M$ and $N\>0$ such that the following holds: if $k,n \geq N$ satisfy $cn \leq k\ln k \leq Cn$ then $m\frac{n}{\ln n} \leq k \leq M\frac{n}{\ln n}$.

This is in the spirit of the usual definition of big O.

The idea of the proof is that since $k\ln k = \Theta(n)$, we have $\ln k = \Theta(\ln n)$. Showing this requires some arithmetic.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Do identical algorithm end up having the same abstract syntax tree?
More often than not, most programming problem can be solved in more than 1 way. You see this in website for practicing solving coding challenges where you often have myriad of solutions to the same problem.

My question is, do all these myriad solution all turn to the same AST in the language used? For example if I have 5 solutions in python to a problem, would these 5 solutions end up getting transformed to the same syntax tree?

I guess the crux of my question is, is there a way to "mechanically" identify that two algorithm are the same?

# Answer
No.

In fact, it can be proven that you do not have an algorithm deciding whether two turing machines compute the same thing.

If you think about it a bit, you will see how being able to check if two TMs compute the same thing can solve the halting problem: If you are given a machine $M$ and an input $w$ to it, and want to check if $M$ will halt when it is fed with $w$, then construct the new machine $M\_w$, that will have the following pseudocode:

1. Ignore the input $x$ to the machine $M\_w$
2. Emulate $M$ on $w$
3. Return "true" for the input $x$ (that we totally ignored here), if the emulation stopped

This machine, will always return "true" if $M$ halts on $w$, but will never return "true" if $M$ doesn't halt. Now, we can easily construct another machine $M\_{true}$ that always returns true, and since we assumed we can compare two machines to see if they compute the same things, then we can compare $M\_w$ with $M\_{true}$. As we have seen, if $M\_w$ does indeed always return "true", then we know that $M$ halted on $w$, and if it doesn't always return "true" then we know that $M$ didn't halt on $w$.

In this way, we can see how knowing that two algorithms are the same can result us in solving an unsolvable problem. Hence, there is no "mechanical" way to check if two algorithms compute the same thing
> 0 votes

---
Tags: algorithms, syntax-trees
---


# Question
Title: Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?
Say you have the finite alphabet {*a*,*b*,*c*,*d*,*e*,*f*,*g*}. It's trivial to enumerate all strings of length \<= 1000 over that set.

But what would be an efficient way of specifying a subset of those strings that include "*e*" at least once?

The obvious and least efficient way is to enumerate all strings and discard the ones that don't feature the desired element, but is there a better way?

# Answer
For every position $0\le i\le 1000$, enumerate over all strings that have $e$ at their $i$'th spot. This can be easily done as you need to enumerate on strings with length $i-1$ and strings with length $n-i$, and concatenate them together with an $e$ between them. This can even be done in-place if you want to
> 2 votes

---
Tags: strings, enumeration
---


# Question
Title: Why is "Proof of Space" insufficient to secure a blockchain?
I just came across a blockchain concept called "Proof of Space-Time" in which participants compete to verify blocks by generating and storing essentially random data to answer essentially random cryptographic challenges. The more data they can afford to store, the higher their probability of winning a challenge.

The difference between "Proof of Space" and "Proof of Space-Time" is that the latter incorporates some way of determining *when* an answer was generated, and the result is that participants must continuously overwrite their storage with *current* random data (... which is, as a practical matter, less efficient than only generating and storing random answers one time for a given storage block).

I gather that there is some attack that makes "Proof of Space" alone insufficient, but what is it?

I.e., how can participants game the system to make it seem like they have dedicated more storage to the challenge than they actually have?

My first guess is that all computer storage – even that dedicated to other productive uses – can be sliced up to look random enough for the purposes of a proof-of-space challenge. But my first response it that could be mitigated by requiring that the answers be salted with specific data that would prevent completely arbitrary storage blocks from serving as valid answers.

---

The second page of the linked paper alludes to an adversarial strategy in which work (i.e., computing capacity) can be substituted for space (i.e., storage capacity). Space-Time answers can reduce the capacity for substitution, but I don't understand how that really applies.

Here's how I have tried to understand this:

1. Network participants generate random "proofs," which are data blocks that satisfy some network parameters that make them useless for other purposes.
2. The network issues a challenge in the form of a random number *x*.
3. Each participant answers with the hash of its proof that is closest to *x*. The winning participant is the one with the hash closest to *x*, and is verified by publishing its full proof.

The security of the network depends on honest participants controlling a majority of the network's storage resources.

Substituting computing capacity for storage capacity would be an attack on this security mechanism. As I understand it: A computing attack would wait to see the challenge and would then generate proofs and then store only the best proof for the particular challenge. But how meaningful is this attack? No matter how much greater the computing capacity than the storage capacity of the network, the time to answer can be reduced so that the probability of a computing attack overwhelming stored answers is negligible.

What am I missing?

# Answer
Here is a practical way to "attack" (i.e., substitute computation for storage) a static proof-of-space network: *Use a deterministic random-number-generator (RNG)*.

Here's an example based on a RNG that produces deterministic results based on a "seed."

1. Generate proofs using random seeds. Store each proof's hash (i.e., "answer") value. So instead of storing long proofs, only store the seed-hash pair.
2. If a full proof is requested then regenerate it based on the seed.
> 0 votes

---
Tags: blockchain
---


# Question
Title: What is the amount of programs for which we can solve the halting problem?
The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the halting problem is undecidable, it could still be that there is a program that can decide for every program except itself whether it halts or not.

So I am wondering, for what percentage of programs can we solve the halting problem? That is, if we assign a Gödel number G to every program. What is the value of the limit with respect to G to infinity of:

> ${s}/n$

where s = the number of programs with Gödel number 1 to G, for which we can decide whether it halts or not.

and n = the number of programs with Gödel number 1 to G, for which we cannot decide whether it halts or not.

I am not looking for a specific answer like 75%. I am looking for an answer like: less than 0.01 % or more than 9.99%, or anything really that gives a hint at an answer.

# Answer
> 6 votes
> The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not.

The undeicidability of the halting problem actually *doesn't* imply this. It means that there is no **single** algorithm that can tell whether any program halts. It does not mean that there is any **single** program for which **no algorithm** can correctly say whether or not it halts.

Note that a program either halts or doesn't **on each particular input**. The general halting problem is a function from `(program, input)` pairs to booleans. You're talking about the halting problem in terms of "this program halts, that one doesn't" without talking about inputs. So either you're thinking of one of the formalisms of the halting problem where you just assume you run all the programs with an empty input (or zero if the inputs are numbers, or whatever; it's all basically the same), or you're thinking of "for a given program, does it halt for all inputs" style versions of the halting problem. It doesn't matter though, for this discussion.

Whatever definition of "program halts" you're using, a program either halts or it doesn't. `HALT(P)` is True or False for all P. You claim that there must therefore be some program P for which no other program correctly computes `HALT(P)`, otherwise we could union up all the pointwise decision procedures for each individual P into one that works for all P.

In fact though, I can concretely give you a set of decision procedures such that for all P, one of them gives the correct answer to `HALT(P)`:

1. `regardless of input, return True`
2. `regardless of input, return False`

In the "just delegate to a subprogram that works for this particular input" strategy, you're actually doing all the *real* work in the part that decides how to delegate. If you could actually do such a delegation (such as by enumerating the pointwise decision procedures for the halting problem alongside the programs that they work on), you would **already** have decided the halting problem by the time the delegation part of the program is finished; the answer is just encoded in another program that you have to run, instead of a more direct encoding of boolean values.

To try to get an intuition for why this sort of delegation can't work, think about how you could actually attempt to implement it in (say) a Turing Machine.

If you have a unique pointwise solver for each program, then you simply can't hardwire them all into the Turing Machine, because there are an infinite number of them and you only have a finite number of states to implement them.

If you imagine that there are a finite number of sub-solvers to dispatch to (which is definitely possible, since "return True" and "return False" are a sufficient set), then you're assuming that your Turing Machine can analyse each input program to figure out which sub-solver would work on it. But how would you implement that analysis? It essentially **is** an obfuscated version of the halting problem. For **any** set of partial halting-problem solvers, you should be able to take any standard "halting problem is undecidable" proof and replace the part where the assumed solver outputs true or false with having it output an indication of which partial solver you should run; it'll be easy to use that to construct the same sort of contradictions. (i.e. "Which partial solver does the delegator indicate would correctly decide whether the delegator halts?")

Your argument hasn't shown that there must be a P for which there is no program that computes `HALT(P)` correctly. It actually shows that there is no algorithm for carrying out the delegation strategy you outlined.

Neither can you "enumerate a list of such decision procedures for each individual program" as mentioned in one of the comments. Well, technically you can, since my list of 2 programs above was such an enumeration, but you can't enumerate a list of decision procedures **paired with the programs that they work on**.

# Answer
> 6 votes
If we read the question as written then the answer is 100%. Let us be careful about what is being asked.

### Attempt 1

Consider the set of numbers $n$ such that the $n$-th program either halts or it does not. If you believe in classical logic then every number is in this set, because "the $n$-th program either halts or it does not" is an instance of the Law of Excluded middle. So the answer is 100%.

### Attempt 2

Sometimes people try to fix Attempt 1 by differentiating between "program $n$ halts or it does not" and "we have a decision procedure for $n$" (as witnessed by the comment "For every fixed program the halting problem is decidable." by adrianN above). That is, they think that it makes sense to have *many decision procedures, one for each number*. This leads to the following (failed) attempt:

Consdier the set of numbers $n$ such that there is a decision procedure for the halting of the $n$-th program. Once again every number is in this set:

1. If the $n$-th program halts then the decision procedure is `print "it halts"`.
2. If the $n$-th program does not halt then te decision procedure is `print "it does not halt"`.

However, and this is quite important:

* we are here *not* talking about a single (posssibly non-computable) decision procedure,
* we are talking about *many* decision procedures, one for each number (which is weird, which is why this is a failed attempt)
* if we try to combine the decision procedures together somehow, we have a problem: even though for each particular $n$ there is a decision procedure $D\_n$, the function $n \mapsto D\_n$ is *not* computable

### Attempt 3

The lesson learned from Attempt 2 is that we need *one decision procedure that handles all numbers*. But there is no such decision procedure because it would be a Halting oracle. We can still ask how well can we do with a single procedure?

Say that a procedure $P$ is a *partial Halting oracle* if, for every $n$,

* $P(n)$ is undefined, or
* $P(n) = 1$ and the $n$-th machine halts, or
* $P(n) = 0$ and the $n$-th machine does not halt.

Define the *success rate $s\_P$* of such a decision procedure $P$ to be $$s\_P = \lim\_{n \to \infty} \frac{\big|\\{i \leq n \mid \text{$P(i)$ defined}\\}\big|}{n}$$ Now we can ask whehter $s\_P$ is well-defined (does the limit exist)? If sohow big can $s\_P$ be?

**Summary:** The way you asked your question looks like you are going for Attempt 1 or Attempt 2, but it is not really clear. The problem is that you speak of "a solvable program". That does not make any sense. Every single program "is solvable" because it either halts or it does not (attempt 1, maybe attempt 2). You need to phrase the question carefully.

# Answer
> 4 votes
Andrej made a good point in that phrasing the question correctly is difficult and important. Your comment indicated that you wanted the answer to the only "interesting" way of formulating the question: "how well" can a program approximate the halting problem? I co-authored a paper on exactly this, and some related questions. It was published at ICALP 2015, then the long version was published in LMCS. A summary is below.

First, the notion of a "proportion of programs" is heavily dependent on how you enumerate all possible programs. Common programming languages are "sparse": if you generate a random string of bytes, it likely won't be a valid C program, for example. So most programs are "trivial", and once you choose the convention (e.g. nonsensical programs halt), then you can approximate the halting problem by saying "all programs halt", and be right almost 100% of the time. Of course, that's completely uninteresting. The right way to avoid this is to require the enumeration $A\_1, A\_2, ...$ to be *optimal*: for any other enumeration of programs $B\_1, B\_2, ...$ there exists a constant $K$ such that every program $B\_i$ is equivalent to some program $A\_j$ with $j\<i+K$. These "optimal programming languages" aren't hard to build, and they're important building blocks in the theory around Kolmogorov complexity.

OK, so now that the subtlety about programming language optimality is out of the way, are we done with the preliminaries? Not really: we also have to define what it mean for a decision procedure to *approximate* the halting problem. Is it allowed to never return for some outputs, like in Andrej's answer? Is it allowed to make mistakes? Let $P$ be the decision procedure: $P(i)$ tries to guess whether $A\_i$ halts. Let's define its success rate at step $n$:

$$ s\_P(n)=\frac{\left\\{i\<n \mid P(i) \text{ halts and is correct} \right\\}}{n} $$

Further, are we interested in the "guaranteed" rate of success for sufficiently large $N$? Or are we interested in "how muchthe $\liminf$ or the $\limsup$ of $s\_P(n)$? (See here for definitions.)

The outcome changes depending on the answers to the previous questions. But here is the tl;dr, with pointers to the theorems in the long version of our paper.

* For any procedure P, there will be an $\epsilon\>0$ and a $N$ such that for all $n\>N$, $s\_P(n)\<1-\epsilon$. This holds even if you allow $P$ both to never halt sometimes, and to make errors (Theorem 3.1.a.).
* Now, can we make the $\epsilon$ independent of the procedure $P$? Kind of: there exists a $\alpha$ such that for *any* procedure $P$, $\liminf\_n s\_P(n)\<1-\alpha$. Put another way, the rate of error is going to be above some fixed constant, infinitely many times. Again, this holds even with a $P$ that can both never return or be wrong (Theorem 3.1.b).
* OK, but can we make the $\limsup$ as high as we want? Yes! For every $\epsilon\>0$, there exists a procedure $P$ such that $\limsup\_n s\_P(n)\>1-\epsilon$ (Theorem 3.1.c).
    + Except! What if we force the procedure $P$ to be *error-free*, like in Andrej's answer? Can we still make the $\limsup$ as high as we want? The answer is a shocking *it depends on the optimal programming language*. This is, by the way, extremely surprising: almost every other result in algorithmic complexity does not depend on the choice of the language (Theorem 3.1.d).

The negative results (the first two bullet points) also hold if $P$ is allowed to be probabilistic in a "naive" sense (Theorem 3.3.), by letting the procedure have access to random bits. You can also formalize the notion of "solving the halting problem probabilistically" in a more complex way, that makes a little more sense in this context, in which case you get slightly (but not very) different results (Theorems 5.1, 5.3 and 5.5).

---
Tags: computability, halting-problem
---


# Question
Title: How to define a formal language for describing procedural activities
I do not have a formal computer science background here so I am looking for pointers.

How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing process, driving to a location etc.

Given the fact that these types of process does feel like algorithms, but they feel more open ended than normal algorithm represented by programming languages. For example a cooking recipes does not have to be 100% identical to result into the same dish. Also describing a step in a cooking recipe could be expressed in various ways since natural language is being used.

This same process can be made for manufacturing process, driving to a location etc.

What concepts or tools should I be looking at if I want to achieve this kind of things?

Would DSL? Do the job? Or would DSL be too restrictive? Because I am thinking how can one encode the various near infinity steps/procedures involved in an activity like cooking or manufacturing.

Pointers would be appreciated

# Answer
Your question is very broad and has possibly hundreds of answers depending on the interpretation. The fact you tagged it with "formal-languages" and "formal-grammars" suggests you are actually asking "how the syntax of a language describing this kind of stuff should look like". Sometimes, reading your question I feel you are actually asking "what kind of computational power should a language employ for encoding these processes."

Let's try to consider several aspects and draw a conclusion. If you are willing to describe some process (cooking/manufacturing/etc) you need to figure the most important elements to formalize and how they interact with each other; therefore depending on the purpose of the formalization the language will have to comply.

If you are willing to formalize for the sake of explaining the context to somebody else (man or machine) the formalism will be descriptional. In the case of a human-readable (but still formal) description, even XML could be a suitable candidate (depending on your requirements). In case, a machine-readable formal description was of interest for inference making and ontology (encoded in Description Logic with some set of axioms DL) could do.

If you are willing to verify the description satisfies several properties, the formalism will require the logic and the inference engine for doing so MC.

If you are willing to encode and run the description, the language will require several sub-languages that not only allow to declare the elements of the discussion but also how they interact. I'm thinking to the C language, where nothing is encoded and you have to describe the world through structures and functions. Or Java, where the same is accomplished through classes.

I think enough elements have been exposed, the short answer is: it depends on *what* you are interested in formalizing and *what* you want to achieve once the formalization is complete.

For example, suppose you want to grow virtual artificial plants, the most common way to go is employing L-systems, (L-systems). As you can see such formalism points out what can be described, how it can be done, the syntax for doing so, and eventually provides a computational procedure for doing it.

Hence, you should first decide precisely what you want to formalize, decide the restrictions of the formalization, and only then start pondering the actual grammar.

With respect to your question about DSL, let's consider this assertion: "Domain specific languages (DSLs) are languages whose syntax and notation are customized for a specific problem domain" taken from "A survey of grammatical inference in software engineering" by Andrew Stevenson and James R. Cordy. L-systems' grammar is a DSL, but their most unrestricted version can compute anything. So there are DSLs that can achieve any kind of computation and therefore are never "not enough". The same is true for Latex. Latex Is Turing Complete

I hope the example sheds some light on your doubts.
> 1 votes

# Answer
**~ Tl;dr.. ~**

*What you are referring to is an algorithm. No more - no less - a stepped and detailed description of a process, the follow-through of which will lead to the intended result. This answer comes in two parts. The first focuses mainly on the structure. It's follow-through results in a human readable algorithm. The second deals with turning said algorithm into an efficient input data structure for any parser program. Finally, I describe a few tools to help you out with this process.*

---

As *Chaos* mentioned in his or her answer, this question could be interpreted in many different ways. This is largely because of two missing pieces of info. One is the amount of granularity needed, although the line about DSL, which originally overlooked. The other is the end use . You mentioned encoding, but that is a very general term. For this reason I tried to answer the question from multiple angles and perspectives. Also, I try to do this all in a tutorial-like, step-by-step fashion to demonstrate the underlying concept of the algorithms.

---

```
                        ~~~ INTERPRETATION 1 ~~~

```

---

There is already a convention for listing processes such as cooking a certain dish. This is the **ordered list**. Whatever you choose as the final syntax, the ordered list should be the architecture. It provides readabilaty for people, and is the most efficient structure for any parser. It will let you use a one-way design as well as a stream for data transfer, as opposed to:

* scan-all
* then evaluate-all
* then-send-results

type design where each job must finish before the next can begin. This flow has advantages in certain situations, but being forced into it because of the input data structure is never ideal.

**THE STRUCTURE**

The purpose of an ordered list is just as it sounds, to describe processes that need to be broken down into steps, and where each of these steps needs to be completed in the correct order.

Another term for writing out an ordered list would be *defining an algorithm*. When we discussed algorithms in computer science class, our homework was to define an algorithm for hard-boiling an egg. To be correct, it had to be detailed enough that someone who didn't know what a boiled egg was could do it perfectly in one try, just by following the steps exactly.

The only difference between the two would be extra detail. A perfect algorithm has no extras. This is because they each achieve the same purpose, but they do so in different environments.

An algorithm is designed for computers. Computers could care less about a context. In programming, context is just an abstraction that people use to understand software and for a reference point from which to develop it.

Ordered lists, on the other hand, are usually meant for human consumption. When in code, they are just another abstraction. the actual data isn't in any particular order; usually it is randomly placed in the most efficient bytes in memory at runtime.

-- **PROCEDURE FOR CREATING AN ORDERED LIST** --

In order to write (or type) out an ordered list, you can follow these steps. For efficiency in making my point, I will list them using an ordered list.

***1.*** Write out a paragraph that describes your procedure in a chronological fashion (i.e. along a timeline; first step first, last step last.) **\*~~\*** The more detail the better. Use a sentence or two to describe each step (again, in order of occurrence.) You can include another sentence or two after these that provide extra detail about the step, as I have done here. To demonstrate this, I will add a double-hyphen before the 'extra' in each of thes steps.The extra detail is not necessary, but it often increases the quality of the end result. As a side note, the end result may (should) feel a bit like you are over-explaining, especially if you are describing a "mainstream" process to which most people have at least a bit exposure. This is how it should be. You should never assume that everyone already knows something, especially on the internet. Remember, you are writing for those who do not.

***2.*** Next, break your paragraph(s) up into small chunks by putting an empty line just before the start of each step. The end result should be a vertically aligned column of text 'chunks.' **\*~~\*** They should look like paragraphs, although they are not. While paragraphs group ideas, these are grouping steps, and any related info. In fact, step one above contains two paragraphs. I purposely left out the empty line between them, so as not to confuse the concepts.

***3.*** Add numbers, in order from 1 to *n* (*n* being the total number of steps) at the very beginning of each step. **\*~~\*** That's it for this step. You can put any type of numbers you want, but this is more in the domain of step...

***4.*** Now, all that is left is formatting. The implementation of this step depends on the context. That is, your reason for listing out the process will determine how the end result should look. **\*~~\*** For example, since I am writing this for a SE post, I have to format it according the guidelines of SE's flavor of markdown. Although markdown is technically a standard (I think?) Online implementations vary from one website to the next. Reddit, for instance, has a similar but different set of rules. If there are no rules in a given context, then it is entirely up to you. However, one rule always applies. **Be consistent.** Whatever you do, do it throughout. If you are typing, which is really the first (and probably the most important) formatting decision, and you decide to add bold-text step markers, be sure to add them to every step. Small changes to the styling will draw the reader's attention away from the content, making your writing harder to follow. This leads me to...

***5.*** Go back over your list and check for, spelling, grammar, and punctuation errors, readability, exclusion of important info, inclusion of extra info that takes away more than it adds, and finally, consistency. **\*~~\*** The importance of this last one is often underrated. In fact, I see it all the time when editing on SE. Just being consist with styling, along with things such as spellings (when referring to this network, I might write SE in one spot and se in another) or use of backticks \`\` on a specific word or phrase. These little things can destroy your credibility in the eyes of a reader without him or her even realizing it. Once this happens, the reader is not going to take any of your advice seriously. This defeats the entire purpose of writing it out in the first place.

And that is it for the general structure. This may seem basic and feel like it is common-knowledge, but that is because it works so well. The only way to further standardize it would be to add a syntax so that a computer can understand it as well. In fact, this is what the next section is all about is about.

---

```
                        ~~~  INTERPRETATION 2  ~~~

```

---

I guess this is really an extension of the first interpretation, although the first assumes that the desired solution looks at the question without consideration of parseability , and this looks at the question from more of a programmer's perspective.

The first perspective also assumes that you were looking for a general solution, whereas this answer is a bit more specific, as it builds on the first. It doesnt change much of what has been written thus far. Believe it or not, that overly verbose mess above is close to parseable if it is tweaked correctly.

Therefore, I will use it as an example for the next section.

**ADDING PARSE-ABLE SYNTAX TO EACH STEP**

At this point, your algorithm likely looks pretty polished... to human readers. The one above is (intentionally) a bit verbose However, if an average computer were to parse it, it would probably see the same thing you've seen if you've tried to read encrypted data.. a jumbled mess.

If parseability is your goal, this is not going to work.

Luckily, this is not as big of a problem as it looks. In fact, in some situations, a documented like the one above need not be changed. Thanks to a couple clever tools and a bit of foresight, we design the parser around the data structure just as easily (if not more so) as the alternative. In fact we wont even need to design the parser, because one of our tools is a *parser generator* (see below).

**RECOMMENDATION: FLEX & BISON**

You also mentioned tools. I know of two tools that are invaluable for this purpose. These are Flex and Bison. Both of these let you define a syntax (more precisely, a set of rules) as input. Once they are given this input, both can parse any document to check whether or not it complies to the syntax rules you have given.

Technically, Bison doesn't parse anything. Instead, it writes a parser program that does the parsing. This is were it gets the name parser generator.

They are both maintained by GNU, and so they are free software (a.k.a. open-source.)

The learning curve is not trivial,but it isn't horribly steep either. Any time you have a tool as flexible as these two, there will be some learning involved. They each have their own syntax for defining the input files.

**EXAMPLE USE CASE**

To demonstrate how bison can be used to solve your problem, I will give you an example use case. This is actually an account of how it helped (and is still helping) me through a predicament which was/is in some ways similar to yours.

I recently was in a situation where, like you, I needed to define a real world entities. Although, instead of actions, I was trying to do this for digital files.

A few weeks ago at work, I was tasked with designing a 'Swiss army knife' style tool for working with config files.One requirement was that the design needed to be centered around a home-grown file parser. Furthermore, it required the ability to be configured on the fly (in other words, it didn't need only parse one single syntax; the syntax had to be programmable).

For the next week or so, I found myself looking a lot at the concept of syntax. I was trying to visualize an abstraction loose enough that it would fit *any* syntax. I was stuck there for longer than I would like to admit.

By luck, I stumbled across Bison and Flex in a video. It provided the abstraction that I was looking for.

---

Now I will demonstrate how you can solve your issue with their help. one can easily set up a workflow, using either of these tools, to efficiently achieve not only an acceptable syntax, but also a parser written solely to parse this syntax. You can even build in rules to interact with whatever comes after the parser. Sort of like including the interface as well!

As I said before, we do not need to do much to the ordered list from the first part of this answer. This is because we can easily tell the parser to ignore most of it. This is one reason why the 'chunks' were so overly verbose.

To do this, just

* Be sure to include the **\*~~\*** after the minimum amount required in each step.
    + It can be any set of symbols, just as long as it will **never show up naturally.**
* Be sure to use a consistent descriptor for the numbers, or whatever you choose to use, at the start of each step.
    + The same rules apply as above.
* Include an extra step at the end that contains only the word 'end'.
* Include an extra instance of the **\*~~\*** descriptor at the very top of the file.
    + The top **\*~~\*** and the 'end' step will be required syntax for all subsequent lists of this type. you can even use them in your programs to detect this file type.
* Now you need only write a rule stating that any text appearing between **\*~~\*** and 'number' should be ignored.

This is easy to do, as the rules are written using regex. Now the fluff will be treated the same as comments in a programming language. At this point, you only need to worry about the structure of the First sentence or two in each step. The only thing left to do
is lay out the structure which these sentences need to follow. This will be domain specific, but fairly simple. The linked resources describe in detail how to create the templates.

---

* NOTE:\*

*Because of the extreme versatility of Flex and Bison, it is very hard for me to explain them within the scope of a SE answer. While I will keep editing in rounds until I have done so, I have also provided links to a few video tutorials below. Programs like this are easier to grasp with a quick tutorial. The first refers to Lex and Yakk.* These are predecessors to Flex and Bison. The latter are front end wrappers to the former, so the functionality is more or less the same.

Hopefully, my experience from above showed you that the biggest hurdle in defining a syntax is figuring out how to define define a syntax. You cant just say "it's yaml" or "It will be like Typescript, but with Java typechecking." What terms do you use? What needs to be where?

These problems are layered. Each is just a symptom of another. As my coworker said, it is just like an onion. You just keep peeling away at the layers, crying the entire time.

That is what makes these tools so valuable. They give you a convenient abstraction.

Another convenient analogy: Think of you problem as a puzzle. What you are after (if you are, indeed, referring to )Although it is a bit different for each tool.

Flex is known as a *lexigraphic* *analyzer*. Put simply, it takes the rules that you give it and analyzes any input against those checks.

Bison is a parser generator. It will output a fully functional file parser that follows your constraints. You tell it what the parser should expect, and it will return a parser. You can then add this parser to your own prograns, or do whatever you want with it (so long as it complies with the GNU GPL... XD).
> 0 votes

---
Tags: algorithms, formal-languages, formal-grammars, domain-specific-languages
---


# Question
Title: High Level description of Turing Machines
How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the symbols used to write down REs (U,\*,+, ...)

# Answer
Using a fixed alphabet $\Sigma$, one can define regular expressions over $\Sigma$ inductively:

* $\varnothing$ and each $a \in \Sigma$ are regular expressions.
* if $r$ and $e$ are regular expressions then so are $(r + e)$, $(r \cdot e)$, and $r^\ast$.

From there it is easy to define a context-free grammar for all regular expressions over $\Sigma$ with the following productions:

* $S \to \varnothing \mid a$ for all $a \in \Sigma$
* $S \to (S + S) \mid (S \cdot S) \mid S^\ast$

Hence, a Turing machine that accepts exactly these expressions only need to simulate a pushdown automaton that accepts the language of the grammar, which is essentially just checking whether there is a closing ) for each ( and there are never more ) than ( in each prefix, which is a standard exercise in each course or textbook on formal languages.
> 0 votes

---
Tags: turing-machines, regular-languages, regular-expressions, strings, symbolic-execution
---


# Question
Title: Print (not count) all possible path classic climbing stair problem)
I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization.

Also found a twisted version of the questions asking to print all possible path instead of counting. Wondering for the twisted version, if we have DP solution ?
Q: If there are n stairs, you can either take 1 or 2 steps at a time, how may way can you finish the stairs. we can just using fib to calculate it. What if you are ask print out all possible ways(not revision please). For example, if n = 5. we have as solution. pseudo code is welcome.

```
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]

```

# Answer
Here is pseudocode for solving this, using a recursive procedure:

All-Solutions($n$):

If $n=0$, return the solution *(empty sequence)*.

If $n=1$, return the solution $1$.

Otherwise:

1. Run All-Solutions($n-1$), and prefix $1$ to all results.
2. Run All-Solutions($n-2$), and prefix $2$ to all results.

---

There is also a simple iterative solution. Start with the solution composed of $n$ many $1$s, and iteratively try to increase it, until getting stuck. How to increase a solution?

* If a solution ends with $1,1$, replace this with $2$.
* If a solution ends with $2,1$, consider the suffix of the form $1,2,\ldots,2,1$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell$ many $1$s.
* If a solution ends with $2$, consider the suffix of the form $1,2,\ldots,2$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell-1$ many $1$s.

Here is an example, $n=5$: \begin{align} &1,1,1,1,1 \\ &1,1,1,2 \\ &1,1,2,1 \\ &1,2,1,1 \\ &1,2,2 \\ &2,1,1,1 \\ &2,1,2 \\ &2,2,1 \end{align}

Both solutions output the list in lexicographic order. The iterative one has $O(1)$ amortized update time. Indeed, the length of the list is $F\_{n+1}$, and the total length of suffixes is $F\_{n+3}-2$, and so the average length of a suffix is roughly $\phi^2 = \phi + 1 \approx 2.618$.
> 1 votes

# Answer
I was thinking same so I solved with python but in my question there were three step constrain instead of 2

```
def paths(n):
    if n==0:
        empty = []
        empty.append('')
        return empty
    if n<0:
        empty = []
        return empty

    paths1 = paths(n-1)
    paths2 = paths(n-2)
    paths3 = paths(n-3)

    path = []
    for i in paths1:
        path.append(i+'1')
    for i in paths2:
        path.append(i+'2')
    for i in paths3:
        path.append(i+'3')
    return path

```
> 0 votes

---
Tags: dynamic-programming
---


# Question
Title: Distinguish supervised learning , unsupervised learning and reinforcement learning
AlphaZero is a computer program that was originally built to master the games of chess, shogi and go. It was trained solely via "self-play", in parallel, with no access to opening books or endgame tables.

The Amazon.com e-commerce system identifies users of similar tastes in terms of their profiles and shopping orders. In this way, the marketing analysts understand the specific interests of each group of users and customize the ads personalized exclusively to those users.

Apple iPhone’s FaceID application matches a query face against a database of registered faces, typically employed to authenticate users through ID verification services. In this way, legitimate users can unlock a device, make payments, access sensitive data, and provide detailed facial expression tracking for Animoji and other features

AlphaZero is **reinforcement learning**, right? I think because AlphaZero improved and became increasingly stronger and better at learning and decision-making

The Amazon is **unsupervised learning**, right?

Apple iPhone’s FaceID application is **supervised learning**, right?

# Answer
I think you are correct. Here is a simple way to distinguish between the types of learnings:

1. Is the learning using some training data or not? If it is, then it is most likely **supervised** learning. If it isn't, there are two options
2. Assume the answer to the last question was false. Is there an interaction with the "environment" when the agent learns? If there is, it is **reinforcement** learning. If there isn't, then this is most likely **unsupervised** learning.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: is Turing machine the blue print for program (software) or computer (hardware)?
I often hear Turing machine is a mathematical model of computation. Sometimes, it's said to embody any computer program. Sometimes, it's said to be an idealised computing device consisting of a read/write head.

But is it a theoretical model for hardware or a theoretical model for software?

# Answer
> 2 votes
Very roughly, you can use the following analogies.

| Turing machine | Modern computer |
| --- | --- |
| Tape & head | RAM, disk, other forms of data storage |
| Instruction table | Electronic circuit |
| Turing machine | Any electronic device (thermostat, PC, phone, digital camera, electronic car key) |
| Universal Turing machine | Computer with a CPU or other programmable general-purpose device |
| Oracle machine | Electronic device with access to external source of information (keyboard, mouse, touchpad, various sensors) |
| Input | Data to be processed |
| Input to Universal Turing machine | Software |

But please, do not read too much into this analogy. It may help you understand the formal definition of Turing machines, but you should not try to analyze it as a mathematical definition, because it is not one.

# Answer
> 1 votes
The turing machine is a mathematical concept to describe computability and complexity. Although we often talk about a head moving across some infinite tape, this is just to aid thinking and understanding. You don't need that. The TM's formal definition only needs basic discrete mathematics.

Alan Turing wasn't interested in building a computer or some mechanical machine. He was interested in determining exactly what an algorithm is. He started by reflecting what an appropriately educated human being could compute given a pen and infinite piece of paper.

According to the Church-Turing thesis everything that can be computed can (also) be computed by a turing machine. Thus every computer program (which by definition is computable) can be executed by a suitable turing machine. In this sense, it could be considered a model for software, but a very weak one. Formally giving a turing machine that checks whether a string is a palindrome is tedious. Writing a Ruby or Python script to do that is a few lines.

---
Tags: turing-machines
---


# Question
Title: Is it possible to allow passing arguments as references without breaking referential transparency in functional languages?
Referential transparency is a relatively new concept to me, but I understood that it means that a function will always give the same answer given the same arguments.

Would passing arguments by reference break this property somehow in a functional language?

# Answer
> 3 votes
The only way to observe a difference between pass-by-value and pass-by-reference would be to mutate the reference. But, since referential transparency precludes mutation, that is not possible.

So, in other words: in a functional language, it is actually impossible to tell the difference between pass-by-value and pass-by-reference. As a consequence, the language implementor is free to choose either, or maybe even both, depending on performance, personal preference, ease of implementation, or really any criteria they want.

---
Tags: functional-programming
---


title: Interpreting = in aymptotic notation

text:
# Question
Title: Interpreting = in aymptotic notation
We can interpret $f(n) + o(f(n)) = \Theta(f(n))$ as for any $g(n) \in o(f(n))$ there exists some $h(n) \in \Theta(f(n))$ such that $f(n) + g(n) = h(n)$. But can we perceive it as for any $g(n) \in \Theta(f(n))$ there exists some $h(n) \in o(f(n))$ such that $f(n) + h(n) = g(n)$? If yes how do you prove this second relation?

# Answer
Let's consider $f(n)=n $. Obviously, $2n \in \Theta(n)$, but $2n$ is not element of set $n+o(n)$, because $2n -n =n \notin o(n)$.

On other hand: $g \in f + o(f) \Rightarrow g=f+ \phi = f+ f \varepsilon$, where $\varepsilon \to 0$ , so, in non negative case, we can have, for example, $f \leqslant g \leqslant 2f$. So, $f + o(f) \subset \Theta(f)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: how do i remove nodes with their children but keep ones that are already connected?
suppose you have graph G and you want to remove node n and n and all of his children but keep the ones that are connected to other nodes

if i want to delete A it will delete C but not D becase its connected to B. and if i want to delete D then E will not be deleted because it is connected to A

is there

# Answer
> 1 votes
What you can do is to look at the *in-degree* of a vertex. For every *out-neighbors* of the vertex you want to delete, decrease the in-degree by one. If the the in-degree drops to zero, you should delete the child.

It's not clear if you want to do this recursively as well, but that shouldn't be an issue. (I.e., if you have the total ordering a→b, b→c, a→c, and you delete a, should to delete b and c as well?)

---
Tags: graphs
---


# Question
Title: Recover a set with the information of the sums of all its subsets
I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$?

I have $2^n $ data. This is far more than $n$, the number of unknowns.

# Answer
> 29 votes
No you can't. Consider any set $S=\\{a,b,c\\}$ with $a+b+c=0$, and the set $S'=\\{a+b,b+c,c+a\\}$.

The subset sums for $S$ are $0, a, b, c, a+b, b+c, c+a, a+b+c=0$.

The subset sums for $S'$ are $0, a+b, b+c, c+a, a+2b+c=b, b+2c+a=c, c+2a+b = a, 2(a+b+c)=0$.

Hence, you can't distinguish $S$ and $S'$ from the subset sums: $0, a, b, c, a+b, b+c, c+a, 0$.

---

If all elements are non-negative, then the smallest subset sums should respectively correspond to the empty set and the singletons made up of the smallest two elements, thus you can know the smallest two elements. Once you know the smallest $k$ elements, you can know the subset sums corresponding to the subsets made up of these $k$ elements. Extract them, then the smallest subset sum should correspond to the $(k+1)$-th smallest element. Repeat the process above, you will finally get all elements.

# Answer
> 6 votes
If you know the sums of all the two element subsets you can recover the elements unless $n$ is a power of $2$. See

---
Tags: algorithms, sets
---


title: Showing NP is closed under intersection

text:
# Question
Title: Showing NP is closed under intersection
I was solving the following question:

> Show that $L\_1 \cap L\_2 \in \mathrm{NP}$ for $L\_1,L\_2 \in \mathrm{NP}$.

I came a cross this solution on the internet which is:

> $M$: On input $w$
>
> 1. Run $M\_1$ on $w$; if $M\_1$ rejects then REJECT
> 2. Else run $M\_2$ on $w$; if $M\_2$ rejects then REJECT
> 3. Else ACCEPT

But is it the proof true? Are we allowed to state "**if $M\_1$ rejects then do something**" knowing $M\_1$ is a nondeterministic machine? Perhaps the following could be a correct solution:

> $M$: on input $w$
>
> 1. Run $M\_1$ on $w$; if it accepts, then run $M\_2$ on $w$; if it accepts, then ACCEPT

The reason I think the first solution is not true is that in the nondeterministic case, having a decider for a language $L$ does not imply a decider for the language $\overline{L}$ (right?); if the first solution were correct and $M$ were a decider for $L$, wouldn't $M'$, that simulate $M$ and only reverses the answer, be a decider for $\overline{L}$?

# Answer
> 3 votes
Both solutions are fine; in fact, they are equivalent.

A nondeterministic Turing machine for a language $L$ runs on an input $x$ and either accepts or rejects. If $x \in L$ then some run will accept, and if $w \notin L$ then all runs will reject. (Since the machine is nondeterministic, it can have several different runs on the same input.)

In your case, you are given nondeterministic machines $M\_1,M\_2$ for $L\_1,L\_2$, and on input $x$, you simply run both of them on $x$, and accept if both runs accept. If $x \in L\_1 \cap L\_2$ then some run of $M\_1$ will accept and some run of $M\_2$ will accept, and consequently some run of your machine will accept. If $x \notin L\_1 \cap L\_2$, then $x \notin L\_1$ or $x \notin L\_2$. If $x \notin L\_1$ then no run of $M\_1$ will accept, and consequently no run of your machine will accept; and similarly for the other case.

---

Another way to see that NP is closed under intersection is using witnesses. A language $L$ is in NP if there is a polytime machine $M$ and a polynomial $p$, accepting two inputs $x,w$, such that:

* If $x \in L$ then $M$ accepts $(x,w)$ for some $w$ of length at most $p(|x|)$.
* If $x \notin L$ then $M$ rejects $(x,w)$ for all $w$ of length at most $p(|x|)$.

You are given machines $M\_1,M\_2$ for the languages $L\_1,L\_2$, and you construct a new machine $M$ that accepts $(x,(w\_1,w\_2))$ if $M\_1$ accepts $(x,w\_1)$ and $M\_2$ accepts $(x,w\_2)$. You are simply providing witnesses for both machines $M\_1,M\_2$ at once. Moreover, you can choose $p(n) = p\_1(n) + p\_2(n) + 3$, where $p\_1,p\_2$ are the polynomials of $M\_1,M\_2$; this is still a polynomial.

---

To check your understanding, try to prove the following generalization. Let $L\_1,\ldots,L\_n \in \mathsf{NP}$, with characteristic functions $\chi\_1,\ldots,\chi\_n$, that is, $\chi\_i(x) = 1$ if $x \in L\_i$ and $\chi\_i(x) = 0$ if $x \notin L\_i$.

If $f\colon \\{0,1\\}^n \to \\{0,1\\}$ is any monotone function then the following language is in $\mathsf{NP}$: $$ \\{x : f(\chi\_1(x),\ldots,\chi\_n(x)) = 1\\}. $$ (Your case takes $f$ to be the binary AND function $f(x,y) = xy$.)

In contrast, $\mathsf{NP}$ is closed under $f(x) = 1-x$ iff $\mathsf{NP}=\mathsf{coNP}$, which most researchers consider unlikely.

---

Finally, what goes wrong with the solution that runs a nondeterministic machine for $L$ and reverses the output? Let $M$ be the machine for $L$, and let $M'$ be the new machine. Thus:

* If $x \in L$ then $M$ accepts $x$ on some run, and so $M'$ rejects $x$ on some run.
* If $x \notin L$ then $M$ rejects $x$ on all runs, and so $M'$ accepts $x$ on all runs.

As you can see, while $L(M')$ certainly contains $\overline{L}$, it could be larger; in fact, it could well consist of *all* words, since we can always modify $M$ to reject on some run.

---
Tags: turing-machines, nondeterminism
---


title: Help Understanding the Halting Problem

text:
# Question
Title: Help Understanding the Halting Problem
There are certain points about the halting problem that do not make sense to me. I couldn't seem to find a good breakdown of it that addresses my notes below. I was wondering if someone could clarify or correct my understanding of it.

To start, every version of the proof I have heard seems vague on how it defines the halting check. So, I will go through each different version of what could constitute a halting check.

1. We define our halting check as a check on a program that may or may not requires input and is only haltable if it can NEVER go on indefinitely. For example, we have a piece of code that may take input and has an internal loop or logic. If any input would cause the loop to run indefinitely, then it is NOT haltable.
2. We define our halting check as a check on a program that may or may not require input and must have at least one set of input that would cause it to stop, to be considered haltable. For example, we have a piece of code that may take input and has an internal loop or logic. If any input would cause the loop to stop, then that program is haltable.
3. We define our halting check by the given parameters and not the program itself. So, this is not defining a program as halt-able or not. But, whether given certain input, if that input would cause the program to halt. For example, the program given input x halts, but given input y runs indefinitely. We would return halt for p(x) and return not halt for p(y). This is not defining a program as halt-able, but instead a program with input as halt-able or not.

We start with the normal halting problem premise:

1. We have the assumption that a program, we will call H, can be built such that it takes program x as input and determines if it is haltable. If the other program is haltable it returns true. If the other program is not haltable it returns false.
2. We now define a second program, which we will call H+. H+ will take a program x as input. If it determines that x is haltable, the program H+ will run forever. If it determines x is not haltable, the program H+ will halt.
3. Then we run some variation of H+(H+), or run H+ on itself and the result is a contradiction and this is the proof.

However, as I noted, this doesn't necessarily seem true as long as we stick to our definitions of haltable above.

1. Let's go through option 1. We have program H, that we reasonably know can return true or false. Some programs are haltable and some programs are not haltable. This is a fact. Based, on this, we know that H+ on certain programs x will occasionally run forever. So, H+(H+) should by definition stop. Outer H+ checks internal H+ to see if all paths are halt-able. It returns false, there are paths that are indefinite. So, the external H+ simply stops.
2. Let's go through option 2. This check is the same as above. We have program H, that we reasonably know can return true or false. Some programs are haltable and some programs are not haltable. This is a fact. Based, on this, we know that H+ will occasionally halt. So, H+(H+) should by definition run forever. Outer H+ checks internal H+ to see if it has any paths that are halt-able. It returns true, there are paths that would cause the internal H+ to halt. So, the external H+ simply runs forever.
3. Let's go through option 3. The initial way we would write this is H+(H+). We want to determine if this is haltable or not. Well, this program/method isn't complete, right? Since the internal H+ also needs a variable for us to do the check. So, it would need to be H+(H+(x)). Obviously, we can set that internal x to H or H+. But, by definition, those would also require input. Thus we couldn't provide the definition as we want to for the problem at hand. This doesn't prove that the program is a contradiction. It just proves that it can't be used to test the input we are trying to give to the program.

# Answer
It seems you are struggling to understand the *definition* of the halting problem. So I will try my best to define it so you can understand easily.

Our task, is to create some algorithm, which we will call $H$ and will solve the following problem:

* We are given inputs $\langle M, x\rangle$ such that $M$ is the description of *another* algorithm (for example, the text representing the code in a file), and $x$ is an arbitrary input to $M$, represented as a string
* Our job is to return $True$ if $M$ when fed with the input $x$ doesn't run forever (that is, there is some finite time such that after that much time $M$ will give us an answer). We will return $False$, if $M$ gets stuck in some sort of infinite loop when fed with the input $x$ (that is, no matter how much we will wait, it will never give us an answer)

Now, the halting problem theorem states that no matter how hard you will try, such an algorithm $H$ that solves this problem cannot exist.

---

To prove the non-existance of $H$ in the halting problem, here is what you do:

* Assume (towards contradiction) that such an $H$ does in fact exist.
* Now we want to get some contradiction. The basic idea is to *somehow* feed $H$ as an input to itself or some other similar program.

And those are the specifics:

We will build from $H$ a different algorithm $H^+$, that given an input $\langle M\rangle$ when $M$ is a description of another algorithm, it will get stuck in an infinite loop if $H(M,M)$ returns $True$ and otherwise halt.

Notice, that this new program $H^+$ gets a *single input*! Therefore, it is valid to ask what is the value of $H^+(H^+)$? But now you notice the weird part. You use $H^+$ on *itself*. You can think of this as a program that opens the file that stores the the code of it, and reading it. After you understand why this tricky part is valid, you will find that actually $H^+(H^+)$ cannot halt, as if it would have halted then $H(H^+,H^+)$ would have returned $True$, and by the definition of $H^+$ it means that it would have actually just gotten stuck in an infinite loop (and hence doesn't halt, in contradiction)! And a similar argument can prove that $H^+(H^+)$ also *must* halt, since otherwise $H(H^+,H^+)$ would have returned $False$, and you can complete it from here.
> 2 votes

---
Tags: halting-problem
---


# Question
Title: Average access time in two level cache system
In a two-level cache system, the level one cache has a hit time of 1 ns (inside the CPU), hit rate of 90%, and a miss penalty of 20 ns. The level two cache has a hit rate of 95% and a miss penalty of 220 ns. What is the average memory access time?

What is a two-level cache system and how to calculate the time required? Since the hit time of level two cache is missing...

# Answer
First Let's define all given things

* L1 Cache hit: 90% & Time: 1ns

L2 and RAM has hit rate 10% out of which 95% which is 9.5% in total

* L2 Cache hit: 9.5% & Time 20ns

RAM has hit rate 5% of 10% = 0.5%

* RAM hit: 0.5% & Time 220ns

### Formula Avg Memory Access Time

AMAT = L1\_hit * L1\_T + L2\_hit * L2\_T + RAM\_hit * RAM\_T

AMAT = 0.9\*1 + 9.5\*20 + 0.5\*220

AMAT = 300.9ns

### What is 2 level cache system:

First cache called L1 is reside on CPU is too fast. When CPU needs data, it checks in L1 cache but if it is not there it will go to L2. L2 cache is sometimes on CPU or outside CPU it depends on architecture of CPU. It does similarly and here also it missed then it fetch data from RAM which is expensive process.
> 1 votes

# Answer
Shouldn't the answer be 3.9ns? When looking at the percentages you gave AMAT = .9 * 1 + 9.5 * 20 + .5 * 220

this would mean you had a hit 950% of the time in l2 and 50% of the time in RAM.

This should have been: AMAT = .9 * 1 + .095 * 20 + .005 * 220

be careful about your percentages.
> 0 votes

---
Tags: cpu-cache, memory-access, performance
---


# Question
Title: Proving correctness of the Newton's Method for finding the square root of a number
I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK:

```
Y := X / 2.0;
while abs (X - Y ** 2) > Tol * X loop
    Y := 0.5 * (Y + X / Y);
end loop;
return Y;

```

The preconditions are that both X and Tol are greater then zero and the postcondition is simply the opposite of the while loop's condition.

Are there any invariants of the loop above that may help? Or maybe a different algorithm (eg. bisection) would be a better choice? So far I've tried showing that the value of the square root is always between `Y` and `X / Y` but that didn't get me anywhere.

# Answer
> 1 votes
Let $f(x) = x^2 - N$, where $N\>0$, and we will assume that $x\>0$.

Denote:

$$x' = \frac{1}{2} \left( x + \frac{N}{x} \right)$$

Then:

$$f(x') = \left( \frac{x^2 - N}{2x} \right)^2$$

Being a square, $f(x') \ge 0$, so after one iteration of Newton's method, we either find a root or we land in a region where $f$ is positive. So we will take one iteration for granted, and assume that $f(x) \> 0$.

In that case, $\frac{N}{x^2} \< 1$, and so:

$$\begin{eqnarray\*}\frac{f(x')}{f(x)} & = & \frac{x^2 - N}{4x^2} \\ & = & \frac{1}{4} \left( 1 - \frac{N}{x^2} \right) \\ & \< & \frac{1}{4}\end{eqnarray\*}$$

That is:

$$f(x') \< \frac{1}{4} f(x)$$

It follows that if $x\_0, x\_1, \ldots$ is a sequence of values produced by Newton's method, then there exists a constant $A$ such that for all $i\>1$:

$$\left|f(x\_i)\right| \< \frac{A}{4^i}$$

And so:

$$\lim\_{i \rightarrow \infty} f(x\_i) = 0 \Rightarrow \lim\_{i \rightarrow \infty} x\_i^2 = N$$

In general, Newton's method to find the root of $f(x)$ for a sufficiently continuous convex or concave function is to iterate:

$$x' = x - \frac{f(x)}{f'(x)}$$

To understand why this works, find the Taylor expansion of $f(x')$ around $x$.

# Answer
> 0 votes
I suggest you take some example values and see the pattern how Y actually changes. Observe that at the first iteration of the loop, Y may be too small, but only on the first iteration. Then you should see how Y changes after that.

With that, you should find a much stronger loop invariant that lets you actually prove convergence (if TOL is small enough and we ignore arithmetic overflow).

---
Tags: correctness-proof, loop-invariants
---


# Question
Title: Imperfection in randomness in VLC shuffle playlist - why?
Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs).

I know from my days as a computer science undergrad student that practical randomness is often good enough so we don't bother with true randomness for many applications. But I'd like to understand this better.

* why is real randomness not worth the effort?
* does pseudo-randomness not follow a uniform distribution?
* are software developers perfectly aware of behavior like I see in VLC and just see a tiny market segment as caring about it?

EDIT: actually, my VLC issue might be because of a broken link! But I'm sure I've seen this behavior with other music players like Apple Music. So apologies to the good folks who develop VLC.

# Answer
> 5 votes
This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, *independently* of previous songs. According to the coupon collector problem, if you have $n$ songs in your list and want to hear all of them, you will have to wait for roughly $n\ln n$ songs to be played. By that time, the average song will have been heard $\ln n$ times.

The problem seems to be not in VLC, but rather in the random experiment that VLC is trying to simulate. VLC is not trying to shuffle your playlist and play it through. Rather, it seems to just pick a new random song each time, regardless of the past.

# Answer
> 2 votes
I have a library of over two thousand songs and I've always noticed VLC's flawed shuffling system. It will play the same song every few songs, or it will prioritize songs from randomly picked folders. Recreating this phenomenon as I write this proves exactly that: With shuffle already selected I press open folder and select my music folder and a song from 'album a' plays. I skip the song and a song from 'album b' plays, followed by another song from 'album a', then another seemingly random song. On the fifth song: who would've guessed, another song from 'album a'.

Keep in mind that I have over two thousand songs and nearly four hundred albums. In hindsight, this phenomenon seemed to start noticeably occurring when I began organizing my music into subfolders ie. '\Music\Artist\Album\song.flac'. this may have something to do with this issue and I hope that it gets solved and fixed. Clearly this has been an issue for a while considering OP's dating of December 2019.

If anyone else has this issue and comes across this thread, I'd appreciate if you'd give your example plus some sort of demonstration of how your songs are layed out because this is a really interesting topic for me. :)

---
Tags: algorithms, randomized-algorithms, software-verification, mathematical-software
---


title: Are parse trees always produced?

text:
# Question
Title: Are parse trees always produced?
When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that

> Parse trees are not always produced.

So, what does it mean? I thought parse trees are always produced after lexical analysis part. Is there any example for it?

# Answer
It's possible to use an attribute grammar to directly compute three-address code or some other Intermediate Representation; there are examples in the Dragon Book (and possibly other texts). This is not usually recommended but it seems like there is always the temptation to ignore the advice.

Parsers which are not actually connected to a compiler often don't bother with a parse tree. For example, a directly executed calculator without loops or stored procedures would have little need for a parse tree, and I think the vast majority of calculator examples are directly executed (so the parser just executes each operator as it discovers the operands). That's unfortunate, in my opinion, because for real compilers building a tree is by far the simplest starting point, and it's not difficult; the calculator examples are misleading and not very good models.

So I suggest you stick with what you were taught. But it would be more realistic (truth in advertising, as they say) to replace "Parse trees **are** always produced." with "Parse trees **should** always be produced."

For a real-life example of a simple language which goes directly to Intermediate Representation, tou can take a look at Lua's hand-built parser.
> 2 votes

# Answer
The key feature of explicit parse trees (or, probably more accurately, abstract syntax trees) that makes them useful is that they are as close as it's possible to get the source program, while still following the structure of the source program. This makes them ideal for implementing any programming language feature which is better expressed in terms of the source language.

Perhaps the most obvious example is semantic analysis. Many modern programming languages have semantics which require reading in the whole program first (e.g. languages which don't require forward declarations). Any semantic error (e.g. a type error) should be reported to the user in a way that refers to the source program as closely as possible, so using an abstract syntax tree makes more sense than an intermediate representation.

(As an aside, generating high-quality diagnostic/error messages is an under-appreciated aspect of compiler development. These messages are, in a sense, the primary user interface of a compiler as far as a programmer is concerned.)

Another example is applying optimisations or transformations which are defined in terms of the source language, such as copy elision in C++. For retargetable compilers or compiler frameworks (e.g. GCC, LLVM), these transformations are neither source-language-independent, nor target-architecture-dependent, so implementing them on the ASTs prior to IR generation is usally the best option.
> 2 votes

---
Tags: compilers, parsers
---


# Question
Title: $(\log n)^{\log n}$ lower-bound and upper-bound
we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.

# Answer
> 7 votes
Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.

# Answer
> 2 votes
$$ \lim\_{n \to \infty} \frac{(\log n)^{\log n}}{n} = \lim\_{n \to \infty} \frac{2^{\log ( (\log n)^{\log n})}}{n} = \lim\_{n \to \infty} \frac{2^{(\log n) \cdot \log \log n}}{n} = \lim\_{n \to \infty} \frac{n^{\log \log n}}{n} = \lim\_{n \to \infty} n^{\log \log n -1} = +\infty. $$

# Answer
> 0 votes
We can show that $n=o\left(\log^{\log n} n\right)$.

Consider another form of $(\log^{\log n} n)$: $$\left(\log^{\log n} n\right)=n^{\log\log n}$$ $$=\prod\_{k=1}^{\log\log n}n=\underbrace{n\times n\times \dots\times n}\_{\log\log n \text{ times}}$$

Hence $$n\< \underbrace{n\times n\times\dots\times n}\_{\log\log n \text{ times}}.$$ So $n=o\left(\log^{\log n} n\right)$.

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis, big-o-notation
---


# Question
Title: Runtime complexity of algorithm that subtracts progressively larger amounts
How would you describe the runtime complexity if I have an algorithm that at each step, the size of the array reduced by an exponentially-increasing amount?

For example, for each step in the algorithm, it is actually processing `n - 2^k` items, where `k` is the number of steps it has run so far. So for the first step, we process `n - 1` items, the second `n - 2`, the third `n - 4`, the fourth `n - 8`, etc. until the subtracted amount exceeds `n` and the algorithm is done.

# Answer
It will be: $$T(n,k)=\sum\_{i=1}^k n-2^i=kn-\sum\_{i=1}^k2^i=kn-(2^{k+1}-1)=kn-2^{k+1}+1$$

If you want something without $k$, notice that $k\le \log(n)$ since otherwise you will process negative amount of items in some iteration. Then, this means that $T(n,k)=kn-2^{k+1}+1\le kn \le n\log(n)$ and hence $T(n,k)=O(n\log(n))$.

This is also tight, assuming that $k$ is large enough. Indeed, if we assume that $k=\log(n)$ then $2^{k+1}=2n$, and hence $T(n,k)=n\log(n)-2n+1=\Theta(n\log(n))$
> 1 votes

# Answer
Suppose for processing $n$ items of your array, you needs $\mathcal{O}(n)$ time. Let $T\_k(n)$ be running time of the algorithm:

$$T\_k(n) = \begin{cases} T\_{k-1}(n-2^k) + Θ(n-2^k) & \text{ if } n \geq 2^k, \\ 1 & \text{ Otherwise } . \end{cases}$$

Note that $k=\log n$ so the number of steps of recursion is at most $\log n$.
> 1 votes

---
Tags: runtime-analysis
---


# Question
Title: Do more registers increase clock cycle time?
While reading a book on computer organization, I ran into a design principle stating that "smaller is faster", indicating that fewer registers means less clock cycle time. Could you prove why?

# Answer
> 1 votes
There’s no “proof”. What you can do is try out different technologies and see that with every technology that you try the same thing happens.

Assume you work at Intel, which produces billions of processors with 16 integer registers. And you are the bright spark who decides that it would be better to have 32 integer registers. There are tons of changes to the processor to be made. One is “store some value into register k, for 0 \<= k \< 16” vs. “For 0 \<= k \< 32”.

You will find that the register file has twice the physical size, so data has to be transmitted over a longer distance, then the speed of light or more importantly the speed of an electrical signal moving through silicon comes into it, and more distance = more time. You will also find that the hardware picking one of 16 registers still leaves you with a choice of two out of 32 registers, so more time is needed. And the guys at Intel designing their chips have seen that over and over again over the last 50 years.

A shorter explanation is TANSTAAFL. Which is a universal law.

---
Tags: cpu, performance
---


title: Question about "with high probability"

text:
# Question
Title: Question about "with high probability"
An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$ big enough.

I often see that authors tend to try to prove an event $A$ happens with high probability by showing that $Pr(\bar A)\leq \frac{1}{n} \implies Pr(A) \geq 1-\frac{1}{n} \rightarrow 1$ as $n$ tends to infinity.

My question is, what is special about $\frac{1}{n}$? What if we prove that $Pr(\bar A)\leq \frac{1}{\log(n)} $, would this still count as "with high probability"?

# Answer
Yes. The common convension of "with high probability" (that I know of) states that for every $0\le \delta\<1$, there is some $n\_0$ such that for $n\>n\_0$ it holds that the probability $P(A)\>\delta$.

Therefore, showing that $P(A)\>1-\frac{1}{\log(n)}$ is enough to say that $A$ occures with probability $\rightarrow 1$, and hence is with high probability.
> 3 votes

# Answer
When I’m told “something happens with high probability” I don’t care about a limit, I care whether it’s going to happen or not. Say something happens with probability 1 - 1 / log n. Then if I try 100 n around a billion, the “high probability” will miss 3 of the 100 n.

If you can say with good conscience “if anyone observes this high probability event not happening, then it is most likely due to some hardware defect”, that’s when you can call it “high probability”.
> -4 votes

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


title: Really confused

text:
# Question
Title: Really confused
Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this?

P = NP

P ⊊ NP

P ≠ NP

NP ⊆ P

# Answer
What would happen if $P=NP$? Clearly $P$-complete $=P$, and hence also $NP$-complete = $NP$. This means that every language in $NP$ would also be in $NP$-complete. So finding a language that *isn't* $NP$-complete, means that we must have $P\neq NP$
> 1 votes

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


title: Applications of Complete Binary Tree?

text:
# Question
Title: Applications of Complete Binary Tree?
Wondering what are the real word applications of the **Complete binary trees** or **Almost complete binary trees** where the the last level of the tree may not be complete and all nodes in the last level are aligned to the left.

# Answer
That would be the binairy heap implementation of a priority queue.

The tree itself would be stored in an array, where access to children and parent is via computation of the position of the other nodes.
> 0 votes

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


# Question
Title: Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?
I have an algorithm with this time complexity:

$$ T(n) = O(n) + \frac{n}{\log n} \cdot \log \frac{n}{\log n}. $$

I tried to figure out how to solve this and I tried to say something like this : if I have $\frac{\log n}{n}$ then the value is going to be very small, if I switch between them the value becomes very big, so I came to this: $T(n) = O(n)+$ something very big.

I am trying to determine if the result is larger than linear time or not, but I am lost.

# Answer
> 4 votes
Clearly, $\log(\frac{n}{\log(n)}) \le \log(n)$.

Substitute this into the equation to get that $T=O(n)+\frac{n}{\log(n)}\left(\log\left(\frac{n}{\log(n)}\right)\right)\le O(n)+\frac{n}{\log(n)} \log(n)=O(n)+n=O(n)$

So $T=O(n)$, and indeed it is not bigger than linear time.

# Answer
> 1 votes
From the definition of big-O: $$f(n)=\mathcal{O}(n)$$ if there exists a positive constant real number $c$ that $$ f(n)\leq cn.$$ I claim that $$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n)$$ So, for proving it we act as follow $$\frac{n}{\log n} \log \frac{n}{\log n} \leq cn$$ multiply each side of inequality by ${\log n}$: $$n \log \frac{n}{\log n} \leq cn\log n$$ on the other hand we know that as $n\to \infty$ $$\log \frac{n}{\log n}\leq \log n$$

$$\rightarrow\forall c\geq 1\hspace{10pt} n \log n \leq cn\log n. \square$$

So $$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n).$$

# Answer
> 0 votes
Since we know $$\log \frac{a}{b} = \log a - \log b % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbWaaSaaaeaacaWGHbaabaGaamOyaaaacqGH9aqpciGGSbGa % ai4BaiaacEgacaWGHbGaeyOeI0IaciiBaiaac+gacaGGNbGaamOyaa % aa!43F0! $$ we can say: $$\frac{n}{{\log n}}.\log \frac{n}{{\log n}} = \frac{n}{{\log n}}(\log n - \log \log n) = n - \frac{{n.\log \log n}}{{\log n}} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % WGUbaabaGaciiBaiaac+gacaGGNbGaamOBaaaacaGGUaGaciiBaiaa % c+gacaGGNbWaaSaaaeaacaWGUbaabaGaciiBaiaac+gacaGGNbGaam % OBaaaacqGH9aqpdaWcaaqaaiaad6gaaeaaciGGSbGaai4BaiaacEga % caWGUbaaaiaacIcaciGGSbGaai4BaiaacEgacaWGUbGaeyOeI0Iaci % iBaiaac+gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaiaacMcacqGH % 9aqpcaWGUbGaeyOeI0YaaSaaaeaacaWGUbGaaiOlaiGacYgacaGGVb % Gaai4zaiGacYgacaGGVbGaai4zaiaad6gaaeaaciGGSbGaai4Baiaa % cEgacaWGUbaaaaaa!644A! $$ on the other hand, we know clearly $$\log \log n \< \log n % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaiabgYda8iGacYgacaGG % VbGaai4zaiaad6gaaaa!413D! $$ hence: $$\frac{{n.\log \log n}}{{\log n}} \< \frac{{n.\log n}}{{\log n}} \to \frac{{n.\log \log n}}{{\log n}} \< n \to \frac{{n.\log \log n}}{{\log n}} \in O\\;(n) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % WGUbGaaiOlaiGacYgacaGGVbGaai4zaiGacYgacaGGVbGaai4zaiaa % d6gaaeaaciGGSbGaai4BaiaacEgacaWGUbaaaiabgYda8maalaaaba % GaamOBaiaac6caciGGSbGaai4BaiaacEgacaWGUbaabaGaciiBaiaa % c+gacaGGNbGaamOBaaaacqGHsgIRdaWcaaqaaiaad6gacaGGUaGaci % iBaiaac+gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaaqaaiGacYga % caGGVbGaai4zaiaad6gaaaGaeyipaWJaamOBaiabgkziUoaalaaaba % GaamOBaiaac6caciGGSbGaai4BaiaacEgaciGGSbGaai4BaiaacEga % caWGUbaabaGaciiBaiaac+gacaGGNbGaamOBaaaacqGHiiIZcaWGpb % GaaGjbVlaacIcacaWGUbGaaiykaaaa!7045! $$ according to above explanation: $$T\\;(n) = O\\;(n) + n - O\\;(n) \to T\\;(n) \in O\\;(n) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamivaiaays % W7caGGOaGaamOBaiaacMcacqGH9aqpcaWGpbGaaGjbVlaacIcacaWG % UbGaaiykaiabgUcaRiaad6gacqGHsislcaWGpbGaaGjbVlaacIcaca % WGUbGaaiykaiabgkziUkaadsfacaaMe8Uaaiikaiaad6gacaGGPaGa % eyicI4Saam4taiaaysW7caGGOaGaamOBaiaacMcaaaa!5487! $$

---
Tags: time-complexity, asymptotics
---


title: Tic-Tac-Toe in PSPACE

text:
# Question
Title: Tic-Tac-Toe in PSPACE
Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?

# Answer
> 2 votes
An $n\times n$ grid takes $n^2$ memory cells. You don't need to remember the "history" of the game, as it is irrelevant.

---
Tags: complexity-theory, np, recursion, space-complexity
---


# Question
Title: Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string
This was an algorithm problem but I am having problems in formulating it.

I have a certain approach but I do not know how to fully execute:

**Given**

* 26 letters in total
* All possible strings of length n

*Example*

Find all possible strings of length 5 such that given \[{a, b, c}, {d, g, h}\], no two letters from each set can occur in that string:

* 'a' and 'd' can occur any number of times in the string, as well as 'a' and 'g'.
* no single instance of 'a' and 'b' occurring or 'b' and 'c' or 'a', 'b' and 'c' ( basically any pair )
* **No two sets will have any characters in common** such as \[{a, b, c}, {d, g, h}, {c, l, f}\] not allowed.

My *naive* approach

* Find all possible strings of length n consisting of characters other than the ones mentioned in the set of sets.
* Take a single set:
    + Take 1 character from a set.
        - Find the characters that are valid with this character and count the possible strings of length n.

But this does not take care of repetitions I think. So is there some other way or do I need to refine more?

# Answer
Let $n$ be the desired length of the strings to build. Then, let $S\_1, S\_2, \ldots, S\_k$ be the sets constraining the solution. We need to choose a total of $n$ letters, by choosing zero or one letter from each set, and possibly repeating the chosen letter. Then, we need to count all the possible ways of rearranging said choices. This means that for each set $S\_i$, we have three choices: how many times we will use a letter from that set, which of the $|S\_i|$ letters will it be, and where in the string are those letter going to appear.

Assume we will use a letter from $S\_1$ exactly $\ell$ times. We have $|S\_1|$ choices for said letter, ${n \choose \ell}$ choices for where to put the $\ell$ ocurrences, and then we need to decide what to do with the remaining $n-\ell$ positions to fill, now without having $S\_1$. This is hinting dynamic programming! Let $f(i, m)$ be the number of words of length $m$ you can make by using sets $S\_i$ through $S\_k$. This means the final answer will be $f(1, n)$.

Now, we can use the previous consideration to define a recursive equation for $f$. As we want all possible values of $\ell$, the number of occurrences for a given set, we can just sum over them.

$$ f(i, m) = f(i+1, m) + |S\_i|{\sum\_{\ell = 1}^m}\binom{m}{\ell}f(i+1, m-\ell) $$

with the base cases being $f(i, 0) = 1$ for all $i$, and $f(k, j) = |S\_k|$ for each $1 \leq j \leq m$. Note that $f(i+1, m)$ appears in the sum as we can choose not to use said set at all.

By implementing this recursive equation as a DP you get an algorithm :), maybe there is something even more efficient, but I can't think of anything right now.
> 0 votes

---
Tags: combinatorics, counting, word-combinatorics
---


# Question
Title: Given a rectangle and a circle (having a lattice point as a center) find the number of lattice points of the rectangle inside the circle
The title explains the question easily. Also the radius of the circle is always an integer. The naive algorithm I thought was to check each and every lattice point of the rectangle but I wonder if we can solve it in less time complexity.

*Here the lattice point means the simple integer point in 2D geometry plane*

# Answer
> 1 votes
The naive approach of checking every point in the rectangle would take $\Theta(wh)$ time, where $w$ is the width and $h$ is the height of the rectangle.

A moderate improvement on this is to scan every row (or column) of the rectangle and figure out where the circle starts and ends. Then, round up/down the circle endpoints, and simply subtract to know how many lattice points in the row lies in the circle. The time complexity is $\Theta(\min(w, h))$.

I would imagine that an excellent solution in $\Theta(1)$ time involves tricky algorithms and cases.

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


# Question
Title: Closest pair of points between two sets, in 2D
I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as possible. How efficiently can this be done? Can it be done in $O(n \log n)$ time, where $n = |S|+|T|$?

I know that if I'm given a single set $S$, then it's possible to find the closest pair of points $s,s' \in S$ in $O(n \log n)$ time using a standard divide-and-conquer algorithm. However, that algorithm doesn't seem to generalize to the case of two sets, because there's no connection between the distance between the two closest points within $S$ or $T$ vs. the distance between the two closest points across those sets.

I thought of storing the set $T$ in a $k$-d tree, then for each $s \in S$, using a nearest-neighbor query to find the closest point in $T$ to $s$. However, the worst-case running time of this might be as bad as $O(n^2)$ time. There are results saying that if the points of $T$ are randomly distributed, then the expected running time for each query is $O(\log n)$, so we'd obtain an algorithm with expected running time $O(n \log n)$ if we were guaranteed that the points are randomly distributed -- but I'm looking for an algorithm that will work for any collection of points (not necessarily randomly distributed).

Motivation: An efficient algorithm would be useful for this other question.

# Answer
> 13 votes
Yes, this can be $O(n \log n)$ time. Build a Voronoi diagram for $T$. Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in. The center of that cell is the point $t \in T$ that is closest to $s$.

You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log n)$ time, so the total running time is $O(n \log n)$ time.

# Answer
> 5 votes
I am expanding my comment into an answer, since I figured out a semi-satisfactory answer. **This only solves the problem for $L^1$-distance. This answer is basically wrong.**

This paper solves the problem of finding the closest pair of points in $d$ dimensions for the case when the sets are separated by a hyperplane in $O(n \log^{d-1} n)$.

For two dimensions, this solves the case in the answer you reference as your primary motivation for your question in $O(n \log n)$. It can also be used to solve the general case of the 2D problem in $O(n \log^2 n)$.

Given two sets $S, T$ of points in 2D, embed them in 3D space, displacing set $S$ by some $-\delta\_z$ and set $T$ by $\delta\_z$ in the $z$ direction. The choice of $\delta\_z$ can be made to not affect the choice of the closest pair of points by taking $\delta\_z$ to be smaller than the precision of your input points (and doubling the precision bits for each input coordinate). Use the 3D algorithm from the cited paper.

# Answer
> 1 votes
This can be done very easily with KDTrees. For example:

```
from sklearn.neighbors import KDTree
import numpy as np

n = 1000
a = np.random.random((n,3))
b = np.random.random((n,3))

tree = KDTree(a)
(distances, neighbors) = tree.query(b, k=1)

min_dist = distances.min()

```

The `KDTree` object enables assignments of nearest neighbors with a binary search. The `tree.query` function also has a `dualtree=True` argument that will use a tree for `b` as well that could be useful for larger trees. But for values of $n \le 10000$ I found `dualtree=False` (default) to be faster.

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


# Question
Title: Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?
The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's *Probability and Computing: Randomized Algorithms and Probabilistic Analysis*.

> Suppose that we have an algorithm that takes as input a string of $n$ bits. We are told that the expected running time is $O(n^2)$ if the input bits are chosen independently and uniformly at random. What can Markov's inequality tell us about the worst-case running time of this algorithm on inputs of size $n$?

Unlike most of the other exercises in the book which request either a proof or a numerical answer, the response expected in this problem is so open-ended that I can't easily verify the correctness (or more importantly in this case, the completeness) of my solution. I am concerned that I may have missed something that Markov's inequality may give us in my solution below.

**My Solution:**

Let $W(n)$ be the worst case runtime of the algorithm on an input of length $n$. Let $R\_n$ be the random variable denoting the runtime of the algorithm on an input of length $n$. By Markov's inequality,

$$\Pr(R\_n \geq W(n)) \leq \frac{O(n^2)}{W(n)}$$.

Since $W(n)$ is nonnegative, rearranging gives

$$W(n) \leq \frac{O(n^2)}{\Pr(R\_n \geq W(n))}$$

or alternatively,

$$W(n) = O\left( \frac{n^2}{\Pr(R\_n \geq W(n))} \right)$$.

This result is intuitive to me: the greater the probability that the algorithm assumes its worst case running time, the lower the worst case running time must be so as to preserve the mean running time (and vice-versa). Is there anything else that I am missing?

# Answer
Using Markov's inequality, you can get a range of running times with different probabilities. For example,

1. $$\Pr(R\_n \leq O(n^2)) \geq 1 - c, \quad \textrm{for some constant $c\<0$}$$.
2. $$\Pr(R\_n \leq O(n^3)) \geq 1 - \frac{c}{n}, \quad \textrm{for some constant $c\<0$}$$.
3. $$\Pr(R\_n \leq O(n^4)) \geq 1 - \frac{c}{n^2}, \quad \textrm{for some constant $c\<0$}$$.

and so on...

It means the worst-case time complexity could also be $\infty$. But the probability of happening that is super low (tending to $0$).

Also, note that for sufficiently large $n$, the probability of getting $o(n^2)$ is very good. For example, for any small constant $\epsilon \>0$,

$$\Pr(R\_n \leq O(n^{2+\epsilon})) \geq 1 - \frac{c}{n^{\epsilon}}, \quad \textrm{for some constant $c\<0$}$$.
> 1 votes

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