# Question
Title: What is a 'dynamic entity' in computer science?
I am doing some reading into computer science and how the computing system works in order to be ready for my 1st year at university doing a Computer Science degree. I came across a term within the definition for a computer system that I tried looking up for on the internet called 'dynamic entity'. The problem is, I couldn't specifically find the definition I was looking for that could explain simply what it meant. If there is someone who could explain this term for me in a simple, but easy to understand, explanation, I would be very grateful. Thank you.

The link I got the term from: https://books.google.co.uk/books?id=3ls6K2cJW\_0C&printsec=frontcover&dq=computer+science+easy+reading&hl=en&sa=X&ved=0ahUKEwjz2r\_cuIfkAhUxonEKHWBZAu8Q6AEIKzAA#v=onepage&q&f=true

The term can be found on page 4 of the book, where they explain what a computing system is.

# Answer
> 1 votes
There are no scientific term "dynamic entity", so meaning of this pair of words can be well stretched. In this particular case they could write something like "A computing system ... is a dynamic system", but apparently they didn't like the repetition, so they have decided to use a fuzzy word "entity". Also, there is a mathematical term Dynamical System, which doesn't have anything in common with what they are trying to say.

Essentially they mean that there is a lot of parts in a real computing system, which can change with time - hardware and software can be installed and uninstalled, software can be configured in many different ways, data comes into the system and gets out of it and so on. Sometimes even users and people, supporting a complex computing system, can be considered as a part of it.

---
Tags: operating-systems
---


title: minimum subset of dominating 2D points

text:
# Question
Title: minimum subset of dominating 2D points
From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?

$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in M such that $x \le a$ and $y \le b$

Another related question: is any minimal set also minimum?

It is trivial to find a minimal set in $|S|^2$ time complexity.

# Answer
> 5 votes
### $O(N^2)$ solution

First of all define dominant relation for points:

> Point $d(x\_d, y\_d)$ is dominating point $p(x\_p, y\_p)$ iff $x\_p \le x\_d$ and $y\_p \le y\_d$. Also easy to see that this relation is transitive, i.e. if $a$ dominating $b$ and $b$ dominating $c$, then $a$ dominating $c$.

Let $M$ be minimum(-size) dominating subset of set $S$. Now we need to check which point will be in $M$. Let answer on the question:

> Is $p \in S$ is $M$ or not?

We have 2 cases:

1. $\nexists d \in S, d$ is dominanting $p$, then $p \in M$, if we will not include $p$ in $M$ we will not be able to find a point that will dominate $p$.
2. $\exists d \in S, d$ is dominanting $p$, then $p \notin M$, because it will be more optimal include $d$ in $M$ and exclude $p$, as every point in $A$ that is dominated by $p$ is dominated by $d$ also, but $d$ is dominating at least one more point (itself).

*First case make sure that $M$ will dominate $S$, second case that $M$ is minimal among all dominating subsets.*

And now we have easy $O(N^2)$ solution: for each point $p \in S$ check membership in $M$; to do that we need to check that there is no point $d \in S$ that dominating $p$.

---

### $O(N \log N)$ solution

To construct solution with $O(N \log N)$ time-complexity, let see some example of sets $S = \\{A, B, C,..., N\\}$ and $M = \\{N, B, I, H\\}$:

To find $M$ we need to sort points in $S$ by $x$ in descending order, and if $x's$ the same by $y$ in descending order (it can be done in $O(N \log N)$, let call this sorted list $L$.

1. Include first point from $L$ in $M$ and remember this point as $T$.
2. Iterates through $L$ (let $C$ current considered point from $L$):
    * if $C$ is dominated by $T$ than skip $C$ and go to next point in $L$;
    * else include $C$ in $M$ and set $T = C$ This step can be performed in $O(N)$.

# Answer
> 2 votes
Yes. There is a divide-and-conquer algorithm whose running time is $O(n \log n)$. For an overview of the algorithm, see the following research paper:

A Calculator for Pareto Points. Marc Geilen and Twan Basten. Design, Automation & Test in Europe Conference & Exhibition 2007 (DATE'07), IEEE.

I believe the divide-and-conquer algorithm is initially due to Bentley and Kung.

See also the skyline problem, which is essentially the same problem in different terms: What are some interesting applications of the skyline problem?

# Answer
> 1 votes
Viewing $S$ as a partially ordered set, your question is equivalent to finding all maximal elements in $S$.

In fact, a dominating subset must contain all maximal elements, and the subset of all maximal elements is clearly a dominating subset.

Thus there is only one minimal dominating subset $M$, namely the set of all maximal elements in $S$, and the answer to your "another related question" is "yes".

There is an algorithm that finds $M$ in $O(N log(N))$ time, where $N = |S|$.

First sort the points according to $x$ coordinates (for points with same $x$ coordinates, sort according to $y$). Then, go through all the points from bigger $x$ to smaller $x$, add a point to $M$ if and only if its $y$ coordinate is strictly bigger than any $y$ coordinate you've seen before it.

This should be good enough in most applications.

# Answer
> -1 votes
I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows: 1. Consider the new array formed by multiplying the abssica array and the corresponding ordinate array and arrange it in ascending order. Next we arrange the abssica array and the ordinate array according to the new array formed. 2. Next we define the quantity:(diff of abssica)\*(diff of ordinate)=m. We initialize m=0 and also min=m. 3. Next we include the last elements of the new abssica and ordinate array formed by the arranging the original ones in M. 4. Now we check m for the second last point of the new abssica and ordinate array and if mmin we leave this point and check the third last point and this goes on till the new abssica and ordinate arrays get exhausted. Just tell me about the correctness of the algorithm. There is no need to worry about time complexity. Its O(nlgn).

---
Tags: algorithms, data-structures, time-complexity, sorting
---


# Question
Title: What is the official name of a specific type of combination algorithm
Say that I have the following set of variables:

`[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]`

The values represent a list of variables from a dataset. Each variable has a certain level of correlation with the target variable `$`. The correlation increases or decreases depending on the sort of combination you use against your target `$`. For example, `BCJX` might have a higher correlation with `$` than `OQTVW`. I'm going to test each possible combination against the training algorithm and output it all, with their accuracy score, in a concise CSV file. But I don't know the name of the algorithm that might combine these variables in every possible way.

In other words, I want to find the combination with the highest correlation value and the smallest dimension.

# Answer
> 1 votes
You are probably looking for subsets of a set. If a set has $n$ elements, it has $2^n$ subsets when counting also the empty set (there is a clear correspondence to all bit strings of length $n$). So if in your case $n=26$, there are about 67 million subsets of variables to check which might be unfeasible.

# Answer
> 0 votes
This seems reminiscent of design of experiments problem. (link) Rather than check every possible subset, it would be much more feasible do a sample which emphasizes maximizing change. The whole subject was pioneered by R.A. Fisher, who was hired to improve the yield of farmer's crops. Since each experiment required considerable time and land to execute, he wanted to make the most of every single experiment.

Generally, in real world examples, a large part of results are caused by just pairwise interactions. So, if for every two events (x,y), you have an experiment where both x and y happen, then you are likely to have very strong coverage of how the system behaves. With the lack of information provided, I am not sure there a limit to how many variables you can observe or not, but a common reseasonable event would be including a given variable A, as well as excluding A.

To say clearly, simply create a set of subsets $S$, such that for any two variables $A,B$, there exist at least one subset in $S$ containing both $A$ and $B$, a subset containing neither $A$ nor $B$, a subset containing $A$ but not $B$, and $B$ not $A$. While the power set grows exponentially, pairwise coverage is much, much, much smaller, and typically captures the essence of functions whose are not random and uncorrelated. Of course, increasing things to include all 3-way interactions or higher is also viable, and increases tyro coverage, but in many cases this is not necessary.

---
Tags: algorithms, machine-learning, python, features
---


# Question
Title: RSA cryptosystem: Encrypting a signed message
I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message.

If Bob wants to send a message $M$ to Alice:

1. Bob takes $M$ and encrypts it (using Alice's public key): $P\_A(M) = C$.
2. Sends $C$ to Alice.
3. She decrypts it using her private key: $S\_A(C) = S\_A(P\_A(M)) = M$.

---

If Alice wants to send a signed message $M'$ to Bob (page 961):

1. She computes the digital signature of $M'$ (with her private key): $\sigma = S\_A(M')$.
2. Sends the pair $(M', \sigma)$ to Bob.
3. Bob receives the pair and check the message authenticity by comparing $M'$ and $P\_A(\sigma)$.

---

If Alice want to send an encrypted, signed message $M'$ to Bob.

In cursive is what I think (I don't know how) it goes.

1. Alice first appends her digital signature to the message. *I guess we get $M'' = M'\sigma$, where $\sigma = S\_A(M')$*.
2. Encrypts the resulting message/signature pair with the public key of Bob (the recipient): *Is that $P\_B((M'', \sigma))$? What does this mean: $(P\_B(M''), P\_B(\sigma))$ or $(P\_B(M''), \sigma)$?. If the former, then what is the point of encrypting the digital signature?*.
3. The recipient decrypts the received message with his or her secret key to obtain both the original message and its digital signature. *I don't how this is done, since I don't know how steps 2 is performed.*

Thanks!

# Answer
> 1 votes
> Encrypts the resulting message/signature pair with the public key of Bob (the recipient): *Is that $P\_B((M'', \sigma))$? What does this mean: $(P\_B(M''), P\_B(\sigma))$ or $(P\_B(M''), \sigma)$?*

Neither. It's simply $P\_B(M'')$. The resulting message/signature pair refers to $M''$.

# Answer
> 0 votes
Practically, you don't need to encrypt the appended message again. You will encrypt the message and for the signature first you will create a `message digest` which is a hash of the original message. This message digest will then be encrypted with the private key using a mutually decided encryption algorithm.

Now you have an encrypted message and a digital signature (encryption of hash). You can append the two using a delimiter and send on the other side.

Once the other side recieves the combination, it can decrypt the message and also decrypt the signature. Now you have the original message and the original message digest. Now you will evaluate the hash of `original message` and match with the `original message digest`. If it matches it proves the authenticity.

Re-encrypting the appended message will not make sense because it will unnecessarily slow down the process.

---
Tags: cryptography, encryption
---


# Question
Title: Time complexity of finding predecessor for a dictionary implemented as a sorted array
I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it takes O(1) time.

If the data structure looks something like

```
[(k0, x), (k1, x), ...]

```

where the keys `k0` to `kn` are sorted, given `k`, I thought the `successor(D, k)` would first have to search the sorted array for `k` ( $ O(log n) $ ) and then get the successor ( $ O(1) $ ) since the array is sorted, and hence the overall time complexity should be $ O(log n) $ instead of $ O(1) $ as mentioned in the book. This should also apply for `predecessor(D, k)`.

For an unsorted array, the time complexity for predecessor and successor remain as $ O(n) $ since searching the unsorted array also takes $ O(n) $.

Did I misunderstand something?

# Answer
It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given *key*.

But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given *entry index*. Clearly this is O(1) for a sorted random access datastructure.

This particular interface is, in general, more useful and more efficient than the key-based interface previously presented, since it more accurately represents the cost of iterating through the dictionaries elements. Most such interfaces do, in fact, take some kind of cursor ("iterator" in C++ parlance) as an argument and return another cursor as a result.
> 1 votes

# Answer
Usually dictionaries are not sorted. There are no provisions for accessing items in sorted order, and finding the predecessor and successor *of a key* take O (n) and are not really useful.

What you *do* however is iterating through a dictionary, that is you have a loop that will visit each key, or each value, or each key-value pair in the dictionary exactly once. Such an iterator would keep track of a position of an item in the dictionary and would have to be able to find the previous or next position in a way that allows visiting each item exactly once, and that is preferably fast.

If you implement a dictionary as a sorted array, going to the previous or next position is trivially O(1), and it just happens to return the items in sorted order. A dictionary implemented as an unsorted array, with n/2 instead of log n access on average to find an existing item, can also trivially iterate in O(1) (and for small n it will be faster because n/2 is still not large compared to log n, and the code is faster).

If you implement a dictionary using a sorted tree, or a hash table, then iterating may be more difficult; but a sorted tree could be stored in an array, and a hash table will often use an array that is not very much bigger than n, so you would expect at least amortized O(1) to iterate (or O(n) to iterate through *all* elements).
> 0 votes

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


title: Linear programming with absolute values

text:
# Question
Title: Linear programming with absolute values
I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ?

Example of use of absolute values:

```
Minimize |a+b+c| + |a-c| s.t.
 |a| + b > 3
 | |a| - |b| | <= 5
 | |b| - 3 | = 0

```

# Answer
I've found out a very interesting document that answers my question: http://lpsolve.sourceforge.net/5.5/absolute.htm It's about integer programming and it covers all possible cases I think. See section **\>= minimum** to handle abs(X) \>= minimum. Here is another one with more tricks: http://orinanobworld.blogspot.de/2012/07/modeling-absolute-values.html

There are several methods described in the links above. The "Binary method" is exactly what I wanted: let's assume you want to remove $|x|$ ($x$ is a variable) wherever it appears in your program, and you know that $|x|$ cannot be greater than a constant $m$. Then, perform the following:

* add new variables $x^+$, $x^-$ and $b$
* add constraint $x = x^+ - x^-$
* add constraints $b \in \left\\{0,1\right\\}$, $0 \leq x^+ \leq b \cdot m$ and $0 \leq x^- \leq (1-b) \cdot m$
* replace $|x|$ by $x^+ + x^-$ wherever it appears
> 8 votes

# Answer
All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b \> 3$ is not convex, since $(4,0)$ and $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $\>$ to $\geq$). The constrict $|a|+b \leq 3$, however, can be used, since it is equivalent to the pair of constraints $a+b \leq 3$ and $(-a)+b \leq 3$.

So absolute values can sometimes be expressed in the language of linear programming, but not always.
> 10 votes

# Answer
I think you can just get rid of |x| if you slightly modify the simplex algorithm. Only variables that are in the basis set can ever be \> 0. So you let $x = x^+ - x^-$ with the additional condition that $x^+$, $x^-$ are not non-zero at the same time, and replace $|x| = x^+ + x^-$. You enforce the condition by not allowing $x^+$ and $x^-$ into the basis set at the same time.

I've not tried this actually :-( But a variation where I didn't want a variable to be restricted to positive values (just x ≤ 3 instead of 0 ≤ x ≤ 3) worked very well this way.
> 0 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a *probabilistic* multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?

# Answer
> -1 votes
There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong.

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.

---
Tags: probabilistic-algorithms, multiplication
---


# Question
Title: Solving/mitigating the free rider problem without requiring identification?
Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification?

In a web system, I want to distribute exactly one virtual dollar per day to each person, without requiring identification when a person creates an account.

A solution of mitigation, would mean for example that a specific person may get up to $2 per day (in case he created more than one account), but not much more.

The algorithm needs to distribute to every person about the same amount of money per day. So the ratio between the money distributed to every two different people per day should be around 1.

# Answer
> 3 votes
The term for the problem you seem most focused on is a Sybil attack whose typical solution is some form of identity.

Another mitigation is a proof of work system that makes account creation expensive. The goal is to have the cost of creating multiple accounts not be worth the gains. This is more effective when one needs *many* Sybil accounts to really benefit. Anything that made getting *two* accounts disincentivizingly costly, probably makes getting *one* account too annoying for legitimate users.

The Wikipedia page list another approach to dealing with this that is a bit interesting, and is described, for example, in "Sybil Detection via Distributed Sparse Cut Monitoring" by Aditya Kurve and George Kesidis referenced there. This, however, requires some way for the users to interact in your system (or in a system you have visibility into). In particular, it requires users to implicitly or explicitly "vouch" for other users. This graph of "vouchings for" will usually have atypical properties for subgraphs of Sybil accounts (e.g. being fully connected rather than a small-world graph).

In your context, you could attempt to use techniques similar to the fraud detection banks do and try to find patterns that suggest abuse, e.g. a bunch of users all transferring virtual currency to a single user in a short time frame.

Alternatively, and this is somewhat in line with a proof of work scheme, you can only provide this virtual payment when the user is doing the intended behavior. As a simple baseline, you may provide it only to users who are active a certain amount in the day. This also leads into to the fraud detection angle as many online games have similar systems to detect bots that are just pretending to behave like normal users.

---
Tags: algorithms, protocols
---


# Question
Title: Are chatbots a good example of overfitting?
In my highschool class we are learning about Artificial Intelligence, and especially the problems that come with machine learning. I was wondering if chatbots like cleverbot were good examples of overfitting. Obviously, when you get a reply that doesn't make sense, is that a result of the bot modeling a training dataset too closely, or is it something else completely? Thanks for the help

# Answer
> 3 votes
There is no expectation that an Machine Learning (ML) system will perform perfectly. Not just in the practical sense that we obviously haven't yet figured out how to make a human-level chatbot, but in a more formal sense that ML systems, particularly neural nets, but this is true for many other ML algorithms, approximate functions and this approximation is going to have some error.

So the fact that an ML system sometimes produces "incorrect" responses doesn't indicate anything. Overfitting is when the ML system performs extremely well on the training set and catastrophically poorly for even relatively small departures from the training set. To show this requires showing poor performance on many examples which are near the training set. Overfitting is unlikely when the training set is large compared to the number of parameters of the ML system (e.g. the weights of a neural network).

You can get nonsensical answers just as well from underfitting or false generalizations. The ML system can easily "learn" a "rule" that makes sense in some situations but not all but be either unable to model (underfitting) or unaware of (false generalization) the exceptions.

At the extremes, you're just off distribution, meaning the input you're giving the system is very unlike the input it was trained on. Obviously at this point there's no reason to expect it to perform well in any sense. An extreme example is training a chatbot on an English language corpus and then talking to it in Spanish.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s
> Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I'm not looking for the answer, right now I'm just trying to understand the question. I don't understand what sort of words would be accepted and what would be rejected. For example, I can't understand whether the following word would be accepted:

* 011011 ; where 01 is prefix and 1011 is suffix
* 011011 ; where 011 is prefix and 011 is suffix
* 011011 ; where 0110 is prefix and 11 is suffix

**My question is: Given a word, how do I know which part of it is the prefix?**

Please try to give an explanation without the actual PDA answer, I'd like to try it myself first.

# Answer
> 1 votes
If we have a word, $w=a\_1a\_2\dots a\_n$ where the $a\_i$ are characters from the underlying alphabet, then the prefixes of $w$ are the empty word, $\epsilon$, and the words $a\_1$, $a\_1a\_2$, $a\_1a\_2a\_3$, ..., $a\_1a\_2\dots a\_{n-1}a\_n$. In informal terms, the prefixes of a word consist of all left-hand segments of the word.

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


# Question
Title: What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?
Wikipedia says:

> A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and **intersection with regular language**.
>
> A full trio, also called a cone, is a trio closed under arbitrary homomorphism.
>
> A (full) semi-AFL is a (full) trio closed under union.
>
> A (full) AFL is a (full) semi-AFL closed under concatenation and the Kleene plus.

* I am wondering if the four concepts are required to be closed under intersection with regular language, not intersection with languages in the same family?
* why are intersection with regular languages required, not intersection?
* I wonder what the concepts are if changing closure under intersection with regular language, to closure under intersection with languages in the same family?

I asked these because I saw that the recursively enumerable languages, recursive languages, context-sensitive languages, regular languages are closed under intersection with languages in the same families, while context-free languages are not.

# Answer
> 4 votes
Because it is a very natural set of operations: the full trio operations (morphism, inverse morphism, intersection with regular languages) exactly corresponds to closure under finite state transductions.

We can formulate results for such nice families. Requiring too many properties would exclude some families of languages. Who wants to miss the context-free languages?

Likewise the Boolean operations (intersection, union, complement) form a nice set, but we do not always require them.

The notion "intersection closed full AFL" is well studied.

# Answer
> 2 votes
1. It is intersection with regular languages, as Wikipedia says (not intersection with other languages in the same family).
2. Because. Because that's what the definition says. Changing the definition would give a different concept. For instance, context-free languages are closed under intersection with regular languages, but not under intersection with other context-free languages, as you point out. This is what the standard definition says, and it is a useful concept. Beyond that, I'm not sure what you expect from a "why" question; it's a definition, and it is what it is.
3. I don't know if there is any standard name for such a concept.

# Answer
> 2 votes
Definitions are chosen, and associated with names, according to their utility in the development of the mathematical theory at hand. Sometimes they are defined very locally for a specific proof, but remain uninteresting outside that proof. Other are given a wider scope because they can be more widely useful.

There may be some aesthetics in the choice of definition, when it does reflect some deep structure of the problems, and that will contribute to usefulness. But a symmetry that is seldom encountered is probably not that useful, or indicative of deep mathematical structure.

I can only talk of my very limited experience. Closure under intersection with regular sets is almost ubiquitous for families of languges. No counter-example comes to my mind. Of course, it is always possible to contrive one, but not so easily (I guess) to contrive one that corresponds to a useful family of languages.

When you choose a definition, thus focussing you interest and your work on it, you have to ask yourself two questions:

* How often will it apply to problems you may be interested in, and how inportant these problems are likely to be (though that may be hard to estimate)
* How convenient is this definition is to derive general results that can be applied to whatever will fit the definition.

Trios and AFLs where defined as they have been by people who found that many families of languages met the corresponding definitions. Furthermore, from the definitions, there were able to prove a variety of results abstractedly for trios and AFLs, that can be applied without further effort to all these families.

They apparently had no incentive to do it for arbitrary intersection within the family. Hence no definition and no name, that I know of.

A further remark is that all these families include regular sets. Hence they are more likely to be closed under intersection with regular sets than under arbitrary intersection within the family (which does imply closure under intersection with regular sets). Hence the definition as chosen is more likely to be applicable, hence more generally useful. And it turn out to be already very useful by itself as remarked by Jan Hendrik.

The following is pure speculation on my part. It may also be that operations considered for closure correspond to interesting structural properties of languages. For example closure under union seems naturally associated with non-determinism (recall that deterministic context-free languages are not closed under union). It may be that there is no simple such property associated with intersection. But as I said, this is not based on hard understanding.

# Answer
> 1 votes
Closure under intersection with regular sets is natural in the sense that most machine models for language classes are finite-state based with some additional control mechanism, and by some standard constructions a finite automaton describing some other regular language could be coded into this finite-state mechanism to get closure under intersection. This is how most of the proofs that show this closure property work. I will give a more detailed and formal answer under some very specific framework below. But before some remarks on the boolean operations.

1) Note the curious fact that for a trio, closure under intersection is the same as closure under shuffle. The shuffle of two words is the language of all possible interleavings of two words, i.e., if $u,v \in X^\*$ for some alphabet $X$, then $$ u \diamond v := \\{ u\_1 v\_1 u\_2 v\_2 \cdots u\_k v\_k \mid k \ge 1, u\_i, v\_i \in X \cup \\{\varepsilon\\}\\}. $$ For languages $U, V \subseteq X^\*$ we set $U \diamond V = \bigcup\_{u \in U, v \in V} u\diamond v$. We can write the shuffle with intersection and the trio operations. Let $\overline X = \\{ \overline x : x \in X \\}$ be some disjoint copy of $X$ and $h : (X \cup \overline X)^\* \to X^\*$ the homomorphism given by $h(x) = h(\overline x) = x$ and $h\_1, h\_2 : (X \cup \overline X)^\* \to X$ two homomorphisms given by $h\_1(x) = h\_2(\overline x) = \varepsilon$, $h\_1(\overline x) = x$ and $h\_2(x) = x$. Then $$ U \diamond V = h(h\_1^{-1}(U) \cap h\_2^{-1}(V)). $$ This formula also gives that we always have closure under shuffle with regular languages in any trio. Conversely if a trio is closed under shuffle then $$ U \cap V = h((U \diamond \overline V) \cap (X\overline X)^\*) $$ where $\overline U = \\{ \overline u : u \in U \\}$ is the image of U under the homomorphism given by $x \mapsto \overline x$.

2) If we allow complementation as already mentioned many interesting and natural language classes are excluded. But this could be stated more formal as was done in Georg Zetzsche's dissertation Monoids as Storage Mechanisms.

> If a trio containing only recursively enumerable languages is closed under complementation, then it is precisely the class of all regular languages.

So, if we also want some meaningful way to talk about computability, there is not trio closed under complementation except the regular languages.

3) Let me make my intuitive remarks why closure under intersection with regular languages is a natural operation more precise, or represents a structural property as noted in @babou answer. As said it has to do with the fact that most machine models are finite state based with some additional control (a stack, an infinite tape, a linear bounded tape etc).

One way to make this more precise and unify these models is the notion of valence automata, which is also a central topic in the above mentioned dissertation. A valence automaton is essentially a finite automaton enriched with some ''counting mechanism/or storage mechanism'' in form of a monoid. Imagine you have some additional register that can save an element from some monoid, and you can alter it by multiplication with other monoid elements. The following monoids correspond to the following language classes.

```
Monoid      |  Language class
-------------------------------
B           |  Context-Free
F_2         |  Context-Free
B x B       |  Recursively Enumerable
1           |  Regular
Z^n         |  Blind counter languages
N^n         |  Partially blind counter languages

```

where B denotes the bicyclic monoid, F\_2 the free group of rank $2$, 1 the trivial monoid, Z the integers, and N the natural numbers, see the mentioned dissertation for more details.

By a slight modification of the product automaton construction we can show that if $U$ and $V$ are accepted by some valence automata over monoids $M$ and $N$, then $U \cap V$ is accepted by some valence automaton over $M \times N$. But if $V$ is regular, we can choose $N = 1$, the trivial monoid. Hence in this case $M \times N \cong M$, so that we have not left our language class, or said differently every language described by valence automata is closed under intersection with regular languages (and in fact they are semi AFL's).

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


# Question
Title: Differences between programming model and programming paradigm?
1. What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming language.)
2. Wikipedia tries to answer my question in 1:

> **Programming paradigms** can also be compared with **programming models** that are abstractions of computer systems. For example, the "von Neumann model" is a programming model used in traditional sequential computers. For parallel computing, there are many possible models typically reflecting different ways processors can be interconnected. The most common are based on shared memory, distributed memory with message passing, or a hybrid of the two.

But I don't understand it:

* Is it incorrect that the quote in Wikipedia says "the 'von Neumann model' is a programming model", because I understand that the Von Neumann model is an architectural model from https://en.wikipedia.org/wiki/Von\_Neumann\_architecture?
    * Are the parallel programming models "typically reflecting different ways processors can be interconnected"? Or are parallel architectural models "reflecting different ways processors can be interconnected" instead?
3. In order to answer the question in 1, could you clarify what a programming model is?

Is it correct that a programming model provided/implemented by a programming language or API library, and such implementation isn't unique?

From Rauber's Parallel Programming book, "programming model" is an abstraction above "model of computation (i.e. computational model)" which is in turn above "architectural model". I guess that a programming model isn't just used in parallel computing, but for a programming language, or API library.

# Answer
A programming model is implied by the system architecture. If your system architecture is a register machine, your programming model will consist of machine code operations on registers. If your architecture is a stack machine, your programming model will consist of stack operations. A Von Neumann architecture and a Harvard architecture will have other programming models. Self modifying code p.e. wil be possible in a Von Neumann architecture but not in a Harvard architecture.

A programming paradigm is more highlevel: it is the way a problem is modelled (imperative or declarative, Object oriented, functional, logic,...). A single paradigm language supports one of these. Multiparadigm languages are more a sort of Swiss armyknive which take elements out of more paradigms.

Every architecture (and corresponding model) will have his own set of machine code instructions. This machine code language itself will follow the imperative paradigm (do this , do that, read register A, add the value to register B,... or put a value on top af the stack, put another value on top of the stack, add the two values on top..., etc...)

(At least I never saw a non-imperative hardware processor)

A high level language (of whatever paradigm) will be compiled or interpreted to this machine code.

About parallelism: If we consider interconnected processors it will be clear that the way they interconnect will be part of the programming model. An old INMOS transputer p.e. connects with four other transputers. The machine code wil have instructions to communicate with the naburing transputers.

But also on recent systems the way to provide mutual exclusion will have to be resolved on low level. On a one processor system we will have to put the interrupts on and off when leaving or entering the critical section. On a multiprocessor system we will need a monoatomic 'test and set' instruction. This is part of the programming model.

Parallel computing paradigms are high level models to use parallelism. Think on languages who have threaded objects, or use semaphores and monitors as language elements.

When we program on different operating systems, different API's will be used. (or even if we program on the same system but we use an other library - a graphics library p.e.). This will change our programming model. the low level code will be different, but if there is a good abstraction (sort of code once, compile anywhere) this will be invisible in the high level language. If not, you will have to make small changes in your code. But since you will use the same high level language, there will be no change of paradigm.
> 5 votes

# Answer
There is no exact answer to your question. The terms "programming model" and "programming paradigm" are not exact technical terms that have fixed definitions. Depending on a context, some authors might define "programming model" in some specific way, but that will usually turn out to cover only some aspects of what people understand under "programming model".

As a good rule of thumb, you should run away from anyone using the word "paradigm". (I was a graduate student when the word was severly overused.)

Nevertheless, it is still very useful to *use* these phrases, even though they are not very precise. They are *helpful* in explaining and organizing various aspects of computation. But keep in mind that there are no accepted mathematical definitions that entirely cover the usage. Therefore, if you ask very precise questions, you will not get very precise answers, but rather opinions and helpful explanations.

In particular, you asked: "What is the relation and difference between a programming model and a programming paradigm?" Well, that depends on who you ask and what decade you live in. Here is what my dictionary says:

> *paradigm* – a worldview underlying the theories and methodology of a particular scientific subject
>
> *model* – a simplified description, especially a mathematical one, of a system or process, to assist calculations and predictions

So, a paradigm is a broader concept than a model. In any case, I advise you to not think about your question as one of *science* because it is not.
> 4 votes

# Answer
> `Programming model`s bridge the gap between the underlying `hardware architecture` and the supporting layers of software available to applications.
>
> `Programming model`s are different from both `programming language`s and `application programming interface`s (`API`s). Specifically, a programming model is an abstraction of the underlying computer system that allows for the expression of both `algorithm`s and `data structure`s.
>
> In comparison, languages and APIs provide implementations of these abstractions and allow the algorithms and data structures to be put into practice – a programming model exists independently of the choice of both the programming language and the supporting APIs.
>
> Programming models are typically focused on achieving increased developer productivity, performance, and portability to other system designs. The rapidly changing nature of processor architectures and the complexity of designing an exascale platform provide significant challenges for these goals. Several other factors are likely to impact the design of future programming models.

Source https://asc.llnl.gov/content/assets/docs/exascale-pmWG.pdf, "Advanced Simulation and Computing" (nuclear weapons)

More on twitter : `#ProgrammingModel`

Programming paradigms

> `Imperative Programming` with an explicit sequence of commands that update state.
>
> `Declarative Programming` by specifying the result you want, not how to get it.
>
> `Structured Programming` with clean, goto-free, nested control structures.
>
> `Procedural Imperative programming` with procedure calls.
>
> `Functional (Applicative) Programming` with function calls that avoid any global state.
>
> `Event-Driven Programming` with emitters and listeners of asynchronous actions.
>
> `Flow-Driven Programming` processes communicating with each other over predefined channels.
>
> `Logic (Rule-based) Programming` by specifying a set of facts and rules. An engine infers the answers to questions.

Source https://cs.lmu.edu/~ray/notes/paradigms/

Thinking through these definitions helps give answers to the question.

One way to reason would be to say that `programming model`s are closer to the design of a system / application and can be made of one or more `programming paradigm`s which are close to a programming language.

This can be seen very clearly in data science applications where a number of technologies are used, each with their own `programming paradigm`, but overall the system the architect should keep a cohesive `programming model`.

More on this way of reasoning : https://twitter.com/semanticbeeng/status/1103027054302425089?s=20
> 1 votes

---
Tags: terminology, programming-languages, computation-models, programming-paradigms
---


# Question
Title: Merge Sort Confusion - Initial Phase Missing?
Below is the solution to a merge sort exercise - "Use a merge sort to sort the list". I'm confused because I thought that there needed to be an initial phase of breaking the list in to sub-lists, yet here only the "reconstruction" phase is shown.

Am I missing something, or is there a problem with the given solution please?

# Answer
What is pictured is often called "bottom up mergesort", which is contrast to the "normal" mergesort, which you could call "top down merge sort".

You can find them contrasted in this article from Algorithms:

> Bottom-up mergesort. Even though we are thinking in terms of merging together two large subarrays, the fact is that most merges are merging together tiny subarrays. Another way to implement mergesort is to organize the merges so that we do all the merges of tiny arrays on one pass, then do a second pass to merge those arrays in pairs, and so forth, continuing until we do a merge that encompasses the whole array. This method requires even less code than the standard recursive implementation. We start by doing a pass of 1-by-1 merges (considering individual items as subarrays of size 1), then a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth.

We don't need to use recursive calls to decide how to break down the array. Rather, it's implicit which elements can be grouped with which elements by simply grouping them into powers of two. This version of merge sort can be more easily written without recursion, which removes some overhead. It's also seems more amenable to various optimizations, such as SIMD or other vectorized operations, loop unrolling, etc.
> 3 votes

# Answer
Presumably the diagram only shows the steps of merge-sort beyond the point where the sub-array to be sorted contains only one element, i.e. as you rightly said, the reconstruction phase.

In other words, your diagram may have skipped the first three levels of the procedure as shown above. Note that these levels can be reconstructed from the reconstruction phase, hence they may be dropped entirely.

I wouldn't say there is a problem in the solution, not one unintended at least. At the outset, it seems it is a niche notation the author of a book might have adopted for the sake of brevity.
> 2 votes

---
Tags: mergesort
---


# Question
Title: Why is this pushdown automaton for some palindromes right?
$B = \\{w \in \\{0,1\\}^\* | w^R = w, w \text{ length is odd} \\}$

Solution:

For example: $111$ should be accepted

steps are

$q\_1 \to q\_2$ stack: \[$\\$$\]

$q\_2 \to q\_2$ stack: $\[\\$, 1, 1\]$ (using up $11$ only having a single $1$ left)

$q\_2 \to q\_3$ stack: $\[\\$, 1, 1\]$ (no change except we lost our final $1$)

$q\_3 \to$ (no strings left to use)

I'm confused understanding this

# Answer
PDAs are *nondeterministic*. Although you have found a valid computation which does not lead to an accept state, a PDA is said to *accept* its input if there is *some* valid computation which does lead to an accept state.

In this case (input $111$), an accepting computation is:

1. $q\_1 \to q\_2$, stack: $\[\\$\]$
2. $q\_2 \to q\_2$, stack: $\[\\$, 1\]$
3. $q\_2 \to q\_3$, stack: $\[\\$, 1\]$
4. $q\_3 \to q\_3$, stack: $\[\\$\]$
5. $q\_3 \to q\_4$, stack: $\[\]$
> 0 votes

# Answer
A PDA is non-deterministic. Nondeterministic automata accept a string w if any path along which w might be processed results in w's being accepted. so the PDA will try all paths and only accept the string if one of these paths landed in an accept state.

**For a detailed explanation check these links:**

https://stackoverflow.com/questions/47214674/how-does-a-pushdown-automaton-know-how-to-read-a-palindrome?rq=1

Neso academy- Pushdown Automata Example (Even Palindrome) : https://www.youtube.com/watch?v=xHj2WI1Rrl4&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=82&app=desktop
> 0 votes

---
Tags: automata, pushdown-automata, correctness-proof
---


# Question
Title: Are every problems in EXP karp reducible to any EXP-Complete?
According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$ into $L$ in polynomial time. I believe this definition is fine but I have some observation that are confusing me. I construct a language $L''$ in $EXP$ such that $L''$ can not be convert into $L$ with polynomial time reductions and $L''$ is in $EXP$ with an algorithm M in this way:

let $f\_i$ be the iteration of all reductions.

1) $input(i,x)$

2) run $f\_i(i,x)$ in time at most $2^n$ if the computation time is greater than $n^{\log n}$ then accept.

3)else accept $(i,x)$ iff $f\_i(i,x) \not \in L$.

Obviously $Language(M) \in EXP$ so there exists a polynomial time reduction from $Language(M)$ to $L$ but this makes a contradiction because M prevents the reductions of less than $n^{\log n}$ time to $L$ and it is because of line 3 of algorithm.suppose $f\_j$ is polynomial reduction, the membership of $(i,x)$ in $L(M)$ is the opposite of the member ship of $f\_j(j,x)$ so $f\_j$ is not a reduction from L(M) to L by the line 3 of algorithm.

My question is: where is my mistake?

# Answer
> 2 votes
> Are every problems in EXP karp reducible to any EXP-Complete?

Yes. That's the definition of $\mathrm{EXP}$-completeness.

> My question is: where is my mistake?

Your mistake is in believing that $L''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you mean by "$M$ prevents the reductions" – you're trying to reduce from $L(M)$ to $L$, not from $L$ to $L(M)$.

On the other hand, $L''$ is not $\mathrm{EXP}$-complete, by the time hierarchy theorem. Any language reducible **to** $L''$ must be in time $O(2^{(\log (n^c))^2})$ for some $c$, but this is just time $O(2^{(c\log n)^2})=O(2^{(\log n)^2})$.

---
Tags: algorithms, polynomial-time-reductions
---


title: Merging nodes of a DAG

text:
# Question
Title: Merging nodes of a DAG
I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect **max** connected clusters of blue nodes and merge them. After each merge operation, the graph should remain acyclic. Let's say my graph contains blue nodes and white nodes.

A and B are connected, they may be merged:

The above graph is DAG. **Merging node {A,B} with node {D} is illegal since it creates a cycle!**

My current algorithm is based on union-find.

```
For each blue node b:
   Make-Set(b)
For each two connected blue nodes a,b:
   Union(a,b)
For each set://Created at the previous step
   merge all nodes of the set

```

The bug is the output graph contains cycles. **How can I avoid merges that create cycles in the graph?** Before each Union, I need to check that it "safe". **Safe** means that after merging cycle will not be created. I can find all passes between the set of a and set of b before Union but this solution is too expensive (time complexity). I can't use solutions with a quadratic time complexity since my graph is too big. Edit: We can merge nodes according to topological order but the following case will be messed (D):

Nodes A, B, and D may be merged, but we will merge only A and B. **Max Cluster example:** at the graph below the cluster is {A, B, C, D, E}

# Answer
> 1 votes
I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices.

Having the following DAG.

If we want to merge node **A** and **B**. We add a new node which has the similar attributes as A + B.

Then trasverse from new node **AB** (should be Depth-first):

* *If it find Node **A** or **B**, then the merge should be cancelled because it creates a cycle. simply delete Node **AB**.*
* If we do not se Node **A** or **B**, the merge is valid so delete node **A** and node **B**.

---
Tags: algorithms, graphs, dag
---


title: Binary Search Symbol Table

text:
# Question
Title: Binary Search Symbol Table
Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem:

```
3.1.15: Assume that searches are 1,000 times more frequent
than insertions for a BinarySearchST client. Estimate the
percentage of the total time that is devoted to insertions,
when the number of searches is 10^3, 10^6, and 10^9.

```

As stated in the problem Searches (S) = 1000 * Inserts (I)

* $S = 10^3 \to I = 1$
* $S = 10^6 \to I = 10^3$
* $S = 10^9 \to I = 10^6$

At this point in the book we are using simple arrays and linked lists to back symbol table (not efficient hash maps, trees, etc). This would mean searches take ~log2(N) time and insertions take ~N/2 time (assuming a uniform distribution on where inserts are placed).

Am I correct in calculating the % of insert to search time would approximately be:

$\frac{Inserts \times N/2}{Searches \times \log\_2(N)}$

Using $Searches = 10^3 \times Inserts$ this reduces to

$\frac{N/2}{(10^3 \times log\_2(N)}$

This would mean the percentage depends heavily on the initial size of the symbol table and is not a steady percentage that we can use to answer the question.

Any suggestions for what I am overlooking, should I be making an assumption about the initial size of the table?

# Answer
In computation, time consume depends deeply on the algorithm we choose. Since the search time consumes `log2(N)` and insertion time consumes `N/2`, the insertion time increases sharply as compared to the search time. The only thing is that they depend on `size of the symbol table`, not the `initial size` because insertion and search time depend on the actual size of data set.

The chart below shows Percentage of Insertion Time over Search Time in your case.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Perfect Probabilistic Encryption still requires key length about as long as message
Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E\_k$) and $n+10$-length messages. Then, show that there exist two messages $x\_0, x\_1 \in \\{0,1\\}^{n+10}$ and a function $A$ such that

$$\mathrm{Pr}\_{b \in \\{0,1\\}, k \in \\{0,1\\}^n}\[A(E\_k(x\_b)) = b \] \geq \frac{9}{10}.$$

(This is problem 9.4 from Arora/Barak Computational Complexity.)

My gut intuition says that the same idea from the proof in the deterministic case should carry over. WLOG let $x\_0 = 0^{n+10}$, and denote by $S$ the support of $E\_{U\_n}(0^{n+10})$. We will take $A$ to output $0$ if the input is in $S$. Then, assuming the condition stated in the problem fails to hold for all $x \in \\{0,1\\}^{n+10}$, we conclude that $\mathrm{Pr}\[E\_{U\_n}(x) \in S\] \geq 2/10$ for all $x$. This implies that there exists some key so that $E\_k$ maps at least $2/10$ of the $x$ into $S$ (the analogue of this statement in the deterministic case suffices to derive a contradiction), but now I don't really see how to continue. Is my choice of $A$ here correct, or should I be using a different approach?

# Answer
It seems you have to use some different approach. There is a hint in Arora/Barak's book. From that hint, I got the following solution.

Again we set $x\_0=0^{n+10}$. The algorithm $A$ works as follows. Let $y=E\_k(x\_b)$ be its input. Let $Y\_{x\_1}$ denote the set of ciphtertexts $y$ such that there exists some $k$ satisfying $D\_k(y)=x\_1$ ($D$ is the decryption algorithm). The algorithm $A$ outputs $1$ if and only if $y\in Y\_{x\_1}$ (so $A$ runs in polynomial time if P = NP). Then we have

$$\mathrm{Pr}\_{b \in \\{0,1\\}, k \in \\{0,1\\}^n}\[A(E\_k(x\_b)) = b \]=\frac{1}{2}\left(1-\mathrm{Pr}\_{k\in\\{0,1\\}^n}\[E\_k(x\_0)\in Y\_{x\_1}\]\right)+\frac{1}{2}.$$

If this probability is less than $9/10$ for all $x\_1\in \\{0,1\\}^{n+10}$, then we have $\mathrm{Pr}\_{k\in\\{0,1\\}^n}\[E\_k(x\_0)\in Y\_{x\_1}\]\>1/5$. This means $\mathrm{Pr}\_{k\in\\{0,1\\}^n,k'\in\\{0,1\\}^n}\[D\_{k'}(E\_k(x\_0))=x\_1\]\>2^{-n}/5$. Note this inequality holds for all $x\_1\in \\{0,1\\}^{n+10}$, which means

\begin{align} 1&=\mathrm{Pr}\_{k\in\\{0,1\\}^n,k'\in\\{0,1\\}^n}\[D\_{k'}(E\_k(x\_0))\in\\{0,1\\}^{n+10}\]\\ &=\sum\_{x\_1\in\\{0,1\\}^{n+10}}\mathrm{Pr}\_{k\in\\{0,1\\}^n,k'\in\\{0,1\\}^n}\[D\_{k'}(E\_k(x\_0))=x\_1\]\\ &\>\frac{2^{n+10}\cdot2^{-n}}{5}, \end{align}

a contradiction!
> 1 votes

---
Tags: cryptography, encryption
---


# Question
Title: Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states
So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you also need to know whether the reverse is true or not. Which is to say that the set of strings accepted by the DFA is described by the regex. I have no idea how to know if this is the case or not.

Could you guys tell me how to be sure if the DFA really recognizes the language described by the regex (000\* + 111\*)\*

# Answer
You state two questions.

(1) You are convinced that all the strings decribed by the RegEx are accepted by the DFA. In order to conclude equality you want to know the converse. Is every string accepted by the DFA also described by the RegEx? To do this, try to argue that every string accepted by the DFA consists of "blocks" of each time at least two the same letter. This is not very dificult: the states of the DFA here "count" symbols $0$ and $1$.

(2) In the title of the question you ask whether the number of states is minimal. This can be done by arguing the no states can be merged. This can be shown by giving for each pair of states a string that "distinguishes" the states: states $p$ and $q$ are distinguished if there is a string $w$ such that $w$ from one of $p$ and $q$ reaches an accepting state, while it does not reach an accepting state from the other.
Here this can be done by looking at most one letter ahead: can be reach an accepting state by $\lambda$, $0$ or $1$? For each of the six staes the answers are different.
> 1 votes

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


title: Reduction 3SAT and CLIQUE

text:
# Question
Title: Reduction 3SAT and CLIQUE
Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to write a paper on reductions (3SAT)

When doing the Reduction from the Clique Problem to 3SAT, I understand that we make clauses and every clause contains 3 literals (hence, 3SAT) but my problem comes when choosing what literals and why they choose them. How do I know which literals to choose? So I know that in every clause I'll have x1, x2 and x3, but how do I choose their assignment order? In one clause I have (x1 or x2 or x3) and in another I have (x1 or not x2 or not x3). How were these chosen?

Also, it seems they don't begin with a graph in mind already. What if I'm given a graph to begin with, how would I convert it into x1, x2, x3? If for clause I have 3 vertices, how would I assign them their respected boolean expression? Thank you very much

# Answer
> 12 votes
Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.

Given a graph $G = (V,E)$ and a number $k$, we will have variables $x\_{iv}$ for every $1 \leq i \leq k$ and every $v \in V$. You should think of $x\_{iv}$ as stating that $v$ is the $i$th vertex in the clique. We want to encode the following constraints:

1. For each $i$, there is an $i$th vertex in the clique: $\bigvee\_{v \in V} x\_{iv}$.
2. For each $i,j$, the $i$th vertex is different from the $j$th vertex: for each $v \in V$, $\lnot x\_{iv} \lor \lnot x\_{jv}$.
3. For each non-edge $(u,v) \notin E$, $u,v$ cannot both belong to the clique: for each $i,j$, $\lnot x\_{iu} \lor \lnot x\_{jv}$.

You can think of the second constraint as a special case of the third one.

If we take all these clauses together, we get a CNF which states that "the $x\_{iv}$ encode a $k$-clique in $G$". This CNF is satisfiable iff $G$ contains a $k$-clique.

If you want to get a 3CNF, all you need to do is to convert the constraints of the first kind into 3-clauses. There is a standard way to do this: if the vertices are $v\_1,\ldots,v\_n$, we replace $\bigvee\_{v \in V} x\_{iv}$ with $$ x\_{iv\_1} \lor x\_{iv\_2} \lor y\_{iv\_2} \\ \lnot y\_{iv\_2} \lor x\_{iv\_3} \lor y\_{iv\_3} \\ \lnot y\_{iv\_3} \lor x\_{iv\_4} \lor y\_{iv\_4} \\ \ldots \\ \lnot y\_{iv\_{n-2}} \lor x\_{iv\_{n-1}} \lor x\_{iv\_n} $$ Here the $y\_{iv}$ are new variables. This set of clauses is equivalent to the original clause $x\_{iv\_1} \lor x\_{iv\_2} \lor \cdots \lor x\_{iv\_n}$.

# Answer
> 0 votes
If you want to reduce Clique directly to 3SAT, you can design a boolean circuit, where the input is a graph and a subset of vertices, and the output is TRUE if that subset is a clique and FALSE otherwise.

If the graph has N vertices, you need:

* N variables, one for each vertex, which is TRUE if it is part of the subset and FALSE otherwise.
* N * (N - 1) variables, one for each pair of vertices, which is TRUE if they are connected, and FALSE otherwise.
* For each vertex, check that either it isn't part of the subset or it is connected to all vertices part of the subset (quadratic amount of operations, using ANDs and ORs). All the results must be ANDed together to produce the final decision bit.

Generally you want to specify things about the size of the clique. Therefore you need to perform binary addition to count the number of vertices that are in the subset (using the 0s and 1s in the input). Then you add any restrictions on the clique size with extra clauses.

*If you don't know how to convert a boolean circuit to a list of 3SAT clauses then this should make you understand: for an AND gate where A & B = C, there are 8 different possibilities for ABC: 000, 001, 010, 011, 100, 101, 110, 111. But half of them are incorrect. For example 110 is incorrect because 1 & 1 = 1. So at least one of the bits should be different. Therefore you must add the clause (!A | !B | C).*

Once you have found a satisfying assignment (good luck), read the 1s and 0s in the input part to extract the subset which is a clique.

---
Tags: algorithms, reductions, 3-sat
---


# Question
Title: What makes a common programming language non-context-sensitive but RE?
I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.

But I cannot pinpoint what aspect makes a programming language RE, **not** context-sensitive. For example, I'm guessing the variables in any scope structures like `for` can be described in a context-sensitive grammar with a fairly bulky (but finite) number of production rules.

One wild guess is that it's because of pointers or references, making it impossible to describe with a finite number of production rules. Can anyone teach me about why it is?

# Answer
I think you are conflating syntax and semantics.

A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means only that a compiler could convert the program into an executable, without saying anything about what that executable does.

That has basically nothing to do with the semantics of the program. We could design a programming language which is arbitrarily difficult to parse, but whose semantics are simple enough that the generated executable is guaranteed to be a complete function. (Removing all looping constructs is a good start.)

On the other hand, we could design a language which is trivial to parse, as are most stack languages, but whose semantics are effectively Turing complete (aside from the finiteness of memory in a physical realization of a processor.)
> 3 votes

# Answer
Let us view the programming language abstractly as the (finite) description of a Turing machine's operation, which I assume is what you are aiming at by saying the language is RE or context-sensitive. The setting here is us having a single machine (a "universal" interpreter) to which we feed inputs of the form $(P, x)$ where $P$ is a program, $x$ is an input for $P$, and, considering $P$ as a function operating on $x$, we wish to compute $P(x)$. Note this is quite a different setting than when recognizing the language of valid programs (see @rici's answer).

We know the context-sensitive languages are those recognizable with a *linear* space bound. This means a machine for this kind of language only uses as much memory as its input is long. In "programming language terms", this roughly corresponds to the input being processed in place (e.g., sorting an array in place). In contrast, a recursively enumerable language (in general) requires an *arbitrary* amount of space.

It seems to me this is as far as the abstraction takes us. Pinpointing a particular programming language construct is infeasible unless we also make explicit assumptions on said language (e.g., what paradigms it uses).
> 1 votes

---
Tags: formal-languages, context-sensitive
---


# Question
Title: What is the worst case time-complexity of removing the root of a Binary Search Tree?
My answer is constant time O(1) since an implementation would naturally have the pointer to the root. However, the solution guide I am looking at argues it is O(logN).

# Answer
I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward.

For it to then still be a *binary* tree that node needs to be closest to the root in value. The worst case will turn out to be that all nodes have two children, and in that case the node closest in value to the root is either the leftmost leaf on the right side or the rightmost leaf on the left side.

So with deletion we're looking at two operations to perform:

* finding the element to delete (that's $\mathcal{O}(1)$ when we're deleting the root, as You've correctly pointed out)
* finding a replacement for the root (turns out to be $\mathcal{O}(\log n)$ as we'll see...)

To find that replacement you have to traverse a full path from root to leaf, which in a binary tree could be anywhere between length $\log n$ and $n$. But note that if the path were any longer than $\log n$ nodes, we'd have to have some node with only one child, in which case we can simply move that node up a level and save ourselves any further effort. (This also kind of shows that the worst case is in fact what I've claimed above since in any other case we could stop earlier.)

Thus at worst we'll have $\mathcal{O}(\log n)$.
> 2 votes

---
Tags: time-complexity
---


title: Which order is "lexicographic order"?

text:
# Question
Title: Which order is "lexicographic order"?
To choose 3 items out of 5 items `[1, 2, 3, 4, 5]`, Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (lexicographic combinations)) gives:

```
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

```

or, if strictly following the algorithm, each combination is reversed, making it:

```
[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

```

while Combinatorial Algorithms by Nijenhuis and Wilf, 2nd Ed, 1978, p. 26 cited "alphabetic order" or "lexicographic order" of:

```
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], ...

```

so they are different. Which is actually lexicographic order, or are *all of them* lexicographic order, and why?

# Answer
There is no one universally accepted lexographical ordering. Any author is free to introduce their own ordering, as long as it is consistent within their scope of discussion.

It's just like binary tree traversing algorithms like preoder, inorder or postorder traversal. There is no one correct traversal, its upto the author to decide which one to use, and stick with it throughout their discussion about the topic.
> 1 votes

# Answer
I think this is the rule: if it is said to be lexicographic, then it is, it follows a particular order, as if the items are printed in a dictionary or phone book.

So for example:

```
apple
aquarium
banana

```

the above is the ordering that would be in a dictionary.

It can be:

```
1.0.0
1.2.18
1.3.0
2.0.1

```

the above can be considered to be lexicographic, if you consider them to be software version numbers.

And so

```
[1, 0, 0]
[1, 2, 18]
[1, 3, 0]
[2, 0, 1]

```

would be lexicographic order too.

Note that

```
 0.0.1
18.2.1
 0.3.1
 1.0.2

```

could be considered to be lexicographic also, if somehow, the right hand side is taken to be the most significant. In fact, the numbers above are just the original version numbers but written from right to left.

So can you say

```
0.1.0
2.1.18
3.1.0
0.2.1

```

is lexicographic too? I suppose you can, if somehow the most significant starts from the middle and go to the left and then to the right (and then to the left and to the right, if it is the ordering used). But it is just not commonly used.

The simple idea is: usually in the commonly used order: say, from left to right, it can be listed in that order in a dictionary or phone book (or some kind of sorted list).

So if we revisit Knuth's algorithm:

```
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

```

the above doesn't look like it is "lexicographic", but it is, when you read each item from right to left. If you read each item from right to left, it is the same as the following read from left to right. Looking at the following, it is lexicographic, if you view them as software version numbers, starting with 3.2.1:

```
[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

```

(or you can map 3 to "c", 2 to "b", 1 to "a", and the above becomes

```
[cba, dba, dca, dcb, eba, ... ]

```

and it is in fact the order how it would appear in a printed dictionary.)

So Wilf's algorithm generates them starting with `[1, 2, 3]` reading from left to right and work its way up, while Knuth's algorithm starts with `[3, 2, 1]`, also reading from left to right, and work its way up. Both are lexicographic, but in a different sequence.
> 1 votes

---
Tags: combinatorics, ordering
---


title: Weird implementation of quicksort

text:
# Question
Title: Weird implementation of quicksort
I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is a little different from the quick sort algorithm...

The original algorithm and question are:

```
QUICKSORT(A, p, r)
1 if p < r
2   then q = PARTITION(A, p, r)
3 QUICKSORT(A, p, q)
4 QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
1 x = A[p]
2 i = p − 1
3 j = r + 1
4 while TRUE
5   do repeat j = j − 1
6     until A[j] ≤ x
7   do repeat i = i + 1
8     until A[i] ≥ x
9   if i < j
10    then exchange values A[i] and A[j]
11    else return j

```

> * (Q1) Let us assume PARTITION(A, 1, 6) is applied to array A(= \[4, 3, 7, 8, 6, 2\]). Note that we assume the first element of the array is A\[1\], i.e., A\[1\] = 4 in this case. Describe the return value of PARTITION and the state of array A.
> * (Q2) Find the smallest total number of calls of PARTITION in order to complete QUICKSORT for any array of size 6.

I think this algorithm has many 'problems'. Firstly, in function QUICKSORT line 3, shouldn't it be QUICKSORT(A,p,q-1)? Then, in function PARTITION line 2 and line 8, if we take i's initial value as p-1, then according to A\[i\]\>=x, at start the A\[p\] will always be changed?! And in line 11 it did not change A\[p\] and A\[j\] finally......

However, as I tried to use this wierd algorithm to do Q1, the result after the first iteration is 237864, second is 234687, third is 234678. It worked!

So if you have ever seen this version of quick sort or you know the mechanism of it, could you give me some comments?

# Answer
Let us start with the subroutine PARTITION. The loop maintains the following invariant:

> $A\[k\] \geq x$ for all $k \geq j$, and $A\[k\] \leq x$ for all $k \leq i$.

If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A\[k\] \leq x$ for all $k \leq j$, and $A\[k\] \geq x$ for all $k \geq i \geq j$. In particular, if $k \leq j$ and $\ell \> j$ then $A\[k\] \leq A\[\ell\]$. This is what PARTITION promises:

> If PARTITION$(A,p,r)$ returns $q$, then $x \leq y$ for all $x \in A\[p\],\ldots,A\[q\]$ and $y \in A\[q+1\],\ldots,A\[r\]$.

Furthermore, the particular choice $x=A\[p\]$ guarantees that PARTITION terminates — I'll let you work out this detail yourself.

This promise given by PARTITION guarantees the correctness of QUICKSORT: PARTITION partitions the array into two halves such that in the sorted array, all elements in the first half precede all those in the second half. In order to complete the sort, it remains to sort each half separately.

What might be throwing you off is a different variant of quicksort, in which PARTITION gives a stronger promise: all elements in $A\[p\],\ldots,A\[q-1\]$ are at most the pivot $A\[q\]$, and all elements in $A\[q+1\],\ldots,A\[r\]$ are at least the pivot $A\[q\]$. The version you describe doesn't have this promise, but otherwise is very similar to the version that you are familiar with.
> 0 votes

---
Tags: algorithms, algorithm-analysis, sorting
---


title: HamiltonianCycles in Random Graphs

text:
# Question
Title: HamiltonianCycles in Random Graphs
Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \\{1,2,\cdots,n\\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $.

Is there anything we can say about the probability of the $G$ containing a $HAM$ Cycle?

This seems like a helpful quantity to figure out for certain computations

Generating random graphs and seeing what fraction contains a $HAM$ cycle can of-course be done.

What is the rate of increase of $P(G\text{ contains }HAMCYC)$ as $p$ increases?

# Answer
The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles.

In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following process:

* For every pair $\\{x,y\\} \in \[n\]$, let $\theta\_{xy} \sim U(\[0,1\])$ (independently).
* Define $G\_p = \\{ \\{x,y\\} : \theta\_{xy} \leq p \\}$.

By construction, $G\_p \sim G(n,p)$. As $p$ goes from 0 to 1, more and more edges are "exposed". Bollobás proved the following result:

> Let $p\_2$ be the minimum $p$ such that the minimal degree of $G\_p$ is at least 2.
>
> Let $p\_H$ be the minimum $p$ such that $G\_p$ is Hamiltonian.
>
> With high probability, $p\_2 = p\_H$.

The expected degree of a vertex is $p(n-1) \approx pn$. This suggests looking at $p = c/n$. A simple calculation shows that for appropriate values of $c$, the degree of a vertex has distribution roughly Poisson with expectation $c$. In particular, the probability that a vertex has degree less than 2 is roughly $q = e^{-c}(1 + c)$. A further calculation shows that these events for different vertices are roughly independent, and so the distribution of the number of vertices of degree less than 2 is roughly Poisson with expectation $nq$. In particular, the probability that the minimal degree is at least 2 is roughly $e^{-nq}$, for appropriate values of $c$. If $c = \log n + \log \log n + r$ then $q = \frac{\log n + \log \log n + r + 1}{e^rn\log n} \approx \frac{e^{-r}}{n}$, and so $e^{-nq} \approx e^{-e^{-r}}$. This suggests the following result:

> The probability that $G(n,p)$ is Hamiltonian for $p = \frac{\log n + \log\log n + r}{n}$ tends to $e^{-e^{-r}}$ for constant $r$.
>
> If $r \to -\infty$ the probability tends to zero, and if $r \to \infty$ it tends to one.

This result indeed holds.

---

You can see a final project of Brunet for some pointers. For more information, consult any decent textbook on random graphs; Hamiltonicity is a classical topic which would be covered in many of them.
> 3 votes

---
Tags: graphs, hamiltonian-circuit
---


# Question
Title: Algorithm for the complete parenthesization of n factors
Is there an algorithm that can list all possible parenthesizations of a given set of commutative factors?

This is related to the Catalan number. It, however, merely determines the number of such occurrences, while keeping a given factor order.

As an example (found at the above link): from "abcd", the algorithm should produce { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))" }.

Another related problem is the optimal matrix multiplication order, where given a number of matrices that ought to be multiplied together, the task is to parenthesize them in an order such as the resulting multiplication operations take the least computational resources. From this, I tried to work out an exhaustive way to list all possibilities, but wasn't able to.

Additionally, if the factors are commutative (thus not matrices in the general case), the number of combinations is larger than the Catalan number. As an example, given the above input, additional elements in the output are expected { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))", **"(ac)(bd)"**, **"d(b(ca))"**, **...** }. In other words, if the factors are commutative, the matrix chain multiplication problem and Catalan number considerations are no longer applicable (at least I can't make a fruitful connection).

So, the question focuses primarily on the algorithm for the general case, i.e. when commutative factors are involved.

# Answer
> 2 votes
As with most things involving trees, it's easiest to analyse recursively.

Given a one-element set $\\{a\\}$, the only parenthesisation is $(a)$.

Given a larger set $S$, we choose an arbitrary element $x \in S$. Then for each proper subset $T \subset (S \setminus \\{x\\}) $ we have parenthesisations $(p)(q)$ where $p$ is a parenthesisation of $\\{x\\} \cup T$ and $q$ is a parenthesisation of the remaining elements. There are a total of $(2|S| - 3)!!$ such.

---
Tags: algorithms
---


# Question
Title: AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?
I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them being 0?

# Answer
What matters is that the height of the tree is limited by $O(\log n)$. As long as you maintain that property your searches will remain efficient.

Forcing the height difference to be zero we get the above property. However we also get the property if we allow the difference to be 1. The crux is that the latter requires a lot less rebalancing to achieve. The average height of a node will very slightly increase due to our more relaxed tree structure but this downside is greatly overshadowed by the reduction in rebalancing operations.
> 0 votes

---
Tags: balanced-search-trees, binary-search-trees, avl-trees
---


# Question
Title: A number of points on a line, with initial positions and speeds - find a minimum time that any two points meet
How can I compute the minimum time for two points to meet in $O(N)$ time?

All I can think is to compute the time for all the point pairs and get the minimum.

Can anyone give me some hints?

# Answer
> 2 votes
I'm assuming we're given an **ordered** list $(y\_0,y\_1,...,y\_{n-1})$ of initial point positions together with a list $(s\_0,s\_1,...,s\_{n-1})$ of their speeds.

You can visualize moving points on a Cartesian plane with "position" and "time" coordinate axes - so the point $P\_i$ *trace* will be a ray $R\_i$, beginning at the point $(0,y\_i)$ and consisting of points $(t, y\_i+s\_it)$ for $t\ge0$. If points $P\_i$ and $P\_j$ meet at some time $t$ then their corresponding rays $R\_i$ and $R\_j$ will intersect, and their intersection point will be $(t,y)$ \- we'll call this time $t$ a *meeting time*.

**Observation.** If an intersection point $(t,y)$ for two rays $R\_i$ and $R\_j$ has a **minimal** meeting time $t$ among all the pairs $(i,j)$ where $i\lt j$, then $i=j-1$ (in other words - points $P\_i$ and $P\_j$ were initially **neighbor** ones - try to prove that).

So, it means that you can look for minimal meeting time among pairs of neighbor points only - their total number is $O(n)$, and the algorithm time is also linear. If the original list of points is not ordered by their coordinates, then the algorithm time will include sorting, which is $O(n\log(n))$.

---
Tags: algorithms
---


# Question
Title: Injectivity verification in o(n) space and O(n) time
The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $O(n)$ of hints, and I want an algorithm that will read $A$ and the oracle input (both read only) and determine either that $A$ has no duplicates, or that the oracle has given me a bad hint, in time $O(n)$ and much smaller read-write space ($O(1)$ or $O(\log n)$).

Can it be done?

# Answer
You haven't specified your exact computation model, so let me assume that you measure space in *words* of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.

The oracle should provide you with the relative order of the elements, say as an array $B$ whose entries are the numbers $1,\ldots,n$ in the appropriate order. This advice takes $O(n)$ words, and can be verified in $O(n)$ time and $O(1)$ additional space.

In slightly more detail, here is the verification algorithm:

```
for i from 1 to n:
  verify that 1 ≤ B[i] ≤ n
for i from 2 to n:
  verify that A[B[i-1]] < A[B[i]]

```

Let us prove that there exists an array $B$ for which the verification succeeds iff $A$ consists of distinct elements.

$\longleftarrow$ Suppose that $A$ consists of distinct elements. Order $A$ in increasing order: $A\[j\_1\] \< \cdots \< A\[j\_n\]$. If we take $B\[i\] = j\_i$ then the verification will succeed.

$\longrightarrow$ Suppose that the verification succeeds for some array $B$. Then $A\[B\[1\]\] \< \cdots \< A\[B\[n\]\]$. This implies that $A$ contains at least (and so exactly) $n$ distinct elements.
> 2 votes

---
Tags: complexity-theory, computation-models, space-complexity, oracle-machines
---


# Question
Title: The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)
In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2):

> Suppose that $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$. Then $\Sigma\_2$-$\mathsf{TIME}(n^{8}) \subseteq \mathsf{NTIME}(n^{9.6})$,

which they prove in the following way:

* If $L \in \Sigma\_2$-$\mathsf{TIME}(n^8)$, then $\exists$ TM $M$ which runs in time $O(|x|^8)$ s.t. $x \in L \leftrightarrow \exists u \in \\{0,1\\}^{c|x|^8} \forall v \in \\{0,1\\}^{d|x|^8} M(x,u,v) = 1$
* But if $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$, then

> by a simple padding argument, we have a deterministic algorithm $D$ that on inputs $x, u$ with $|x| = n$ and $|u| = cn^8$ runs in time $O((n^8)^{1.2}) = O(n^{9.6})$ and returns $1$ iff there exists some $v \in \\{0,1\\}^{dn^8}$ such that $M(x,u,v) = 0$

I struggle to see what this "simple padding argument" might be? That is, how do we get respective deterministic algorithm $D$ if we have the TM $M$?

# Answer
The language $$L\_1 = \\{(x,u) ~|~ \exists v\in \\{0,1\\}^{d|x|^8}M(x,u,v) = 0\\}$$ belongs to $NTIME(n)$ by design, since $|v| = O(|x| + |u|) = O(|x|^{8})$. By the assumption of the theorem, $L\_1$ is decidable by some deterministic $D$ in $O((|x|+|u|)^{1.2}) = O(|x|^{9.6})$ steps. The recipee for $D$ isn't important, but the existence of such algorithm $D$ leads to the last step of the proof.
> 2 votes

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


# Question
Title: What can't guarded fragment of FO express?
I have some basic confusions about the definition of the guarded fragment of first-order logic. Hopefully someone can tell me where I'm wrong.

GF in FO is defined by:

1. Atomic formulas, $x=y$ and $R(x\_1,...,x\_n)$, are guarded formulas.
2. If $\phi,\psi$ are guarded formulas, so are $\neg \phi$ and $\phi \wedge \psi$.
3. For variables $\\{x\_j,...,x\_m\\} \subseteq \\{x\_i,...,x\_n\\}$ and guarded fomula $\phi$ and atomic formula $A$, $\exists x\_j\ A(x\_i,...,x\_n) \wedge \phi(x\_j,...,x\_m)$ is a guarded formula.

My reasoning is: for arbitrary FO formula of form $\exists x\ \phi$, I can just pick some relation $T$ that's always true and over all variables, and it's then equivalent to $\exists x \ T \wedge \phi$, a guarded formula. Other forms follow from this. So FO reduces to GF.

But that's obviously not true. I can't figure out where my mistake is. Could someone let me know where I got it wrong?

For example, isn't $$ \forall x\ \exists y\ \forall z\ \phi $$ equivalent to $$ \forall x\ (T \to \exists y\ (T \wedge \forall z\ (T \to \phi))) $$

# Answer
> 2 votes
You're correct that, if the structure you're working with has a universal relation, then using that relation as a guard is equivalent to having no guard at all. However, you don't get to pick the interpretation of the relation symbols. For example, if you're trying to write a formula that is satisfied by exactly the class of 3-colourable graphs, then you should think in terms of an adversary supplying you with an arbitrary graph and your formula has to give the right answer, without being able to rely on any particular properties of the structure you're given.

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


# Question
Title: What is known about the sets enumerated by primitive recursive functions?
Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is *primitive recursively enumerable* if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, we can enumerate $S$ by calculating $\\{f(0), f(1) \ldots \\}$.

What is known about this class of sets? Where does it stand in terms of computability? I suspect that it contains sets that are not context free, and that it does not contain all recursive sets.

Has this been studied? Does anyone have a reference for this?

# Answer
In *"Extensions of some theorems of Gödel and Church"* it's shown by Barkley Rosser that these sets are exactly the recursive sets:

> **Corollary I**. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.

Note that the crux here is *repetitions*. Since you constructed *sets*, and comparing them with other *sets*, any repetitions do not violate their equality.
> 3 votes

---
Tags: computability, reference-request, primitive-recursion, chomsky-hierarchy
---


# Question
Title: Algorithm to find repeated patterns in a large string
For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching repeated substrings in a string. However, in my case I'm not looking for the longest substrings but rather smaller substrings that occur very often.

For example, say each command is represented by a letter, then a program might look like `xabca yabca xabca yabca`. If we are looking for the longest repeated substrings, the best result is `xabca yabca`. A "better" result would be `abca`, though. While being shorter, it occurs more often in the string. `a` occurs even more often on its own, but it would be considered a too short match. So an algorithm should be parameterizable by a minimum and maximum chunk length.

Things I have tried so far:

* I played with suffix trees to find the longest repeated substrings that occur at least *k* times. While that is simple to implement, it doesn't work well in my use case, because also overlapping substrings are found. Trying to remove those wasn't very successful either. The approach mentioned in this post either gave wrong or incomplete results (or I misunderstood the approach), and it also doesn't seem to be customizable. Suffix trees still seem the most promissing approach to me. Perhaps someone has an idea how to include the minumim/maximum chunk lengths into the search here?

*EDIT:* I finally found a working algorithm for the longest non-overlapping repeated substring, explained here. My current implementation works fine for smaller inputs but has an excessive memory consumption for inputs larger than 10 MB (which shouldn't be a problem of the algorithm per se).
* Another attempt was using the substring table that is created for the LZW compression algorithm. The problem with this approach is that is doesn't find repeated chunks that occur early and it also creates longer and longer table entries the farer it processes the input (which makes sense for compression but not in my use case).
* My best solution so far is the brute-force approach, i.e. building a dictionary of every possible substring and counting how often it occurs in the input. However, this is slow for large inputs and has a huge memory consumption.
* Another idea was searching for single commands that occur most frequently, and then somehow inspecting the local environments of those commands for repeated patterns. I didn't come up with a good algorithm here, though.

What else algorithms are there that could be useful in this scenario? What I'm looking for is not necessarily the best match but a good heuristics. My input data is pretty big, strings up to a length of about 100MB; the chunk sizes will usually be in the range from 10 to 50.

# Answer
> 2 votes
To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort.

If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of length 2, and then only consider min-length substrings that contain at least k of the most common 2-length substrings for some threshold k.

---
Tags: algorithms, search-algorithms, substrings
---


# Question
Title: Are there techniques to know how many times loops like these will run?
How do you evaluate how many times some loops will run, when you start to complicate the boundaries conditions? For example, take this function:

```
def f(n):
    s = 0
    for i in range(n):
        for j in range(i, (n + i**2) // (n - i) + 1):
            s += 1
    return s

for i in range(10):
    print(i, "->", f(i))

```

Output:

0 -> 0
1 -> 2
2 -> 5
3 -> 10
4 -> 17
5 -> 28
6 -> 42
7 -> 60
8 -> 83
9 -> 109
```

# Answer
If you approximate this as an integral of the second for loop you get, substituting $k=(n-i)$:

$$I\_n = \int\_1^n \frac{n+(n-k)^2-(n-k)+1}{k} dk = \int\_1^n 1+\frac{(n-k)^2+1}{k} dk$$

according to WA, the corresponding antiderivative is of the indefinite integral is:

$$(n^2+1)log(k) + \frac{1}{2}k(k-4n+2) +C$$

Thus, evaluating at $k=1$ and $n$ we get:

$$I\_n = (n^2+1)log(n)+\frac{-3+6n-3n^2}{2}$$

So, the discrete sum should approximately reflex that. I graphed it out on desmos, and it seems to show that the exact error grows infinitely, they are asymptotically equal.
> 1 votes

---
Tags: time-complexity
---


title: Loop invariant initialisation confusion

text:
# Question
Title: Loop invariant initialisation confusion
Consider the algorithm LastMatch below, which returns the offset (shift) of the last occurrence of the pattern P in text T, or -1 if P does not occur in T:

```
LastMatch(T,P)
 for(s = T.length - P.length downto 0)
   j = 1
   while(j =< P.length and P[j] == T[s + j])
     j++
   if(j == P.length + 1)
     return s
 return -1

```

I've been given a loop invariant for the while loop:

$\forall k(1 \leq k\<j \rightarrow P\[k\] ==T\[s+k\])$

The initialisation of this invariant confuses me. Before we enter the while loop, $j=1$. So we're asking is there a $1\leq k\<1$ such that $P\[k\] ==T\[s+k\]$?

I cannot find a $k$ which satisfies this inequality, so I do not understand what this is saying. So why is the invariant satisfied before we enter the loop? Is it because when I cannot find a $k$ it implies that $P\[k\]$ and $T\[s+k\]$ are both equal to the empty set?

# Answer
An implication is true if the antecedent is false.

If j is 1 then the antecedent is false no matter what k you choose, which means that the implication is vacuously true for every k. So the assertion is true.
> 0 votes

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


# Question
Title: Simulated annealing to find the correct permutation of 20 words
I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation.

I'm trying to figure out how to use simulated annealing to find the correct permutation of these 20 words. To begin with, I'm not even sure if I understand simulated annealing entirely, so I'll describe an algorithm that I think resembles simulated annealing.

For an arbitrary number (preferably a big number) of times, generate a random permutation and measure how correct it is. If the answer is more correct than any previous attempt, save the score and the sentence. Once we are done iterating, we have found something that it is probably close to the global maximum (the "correct" permutation).

I'm not sure where to go from there. Essentially, I have two questions.

1. Does that sound like a good approach?
2. Is my algorithm simulated annealing?

# Answer
> 1 votes
Simulated annealing, like gradient descent, needs a metric that identifies partial correctness. Unlike gradient descent, simulated annealing tries to escape local minima by randomly allowing state transitions that are not improvements.

Instead of randomly generating a new permutation each iteration, you should only generate a full random permutation at the beginning.

Just like gradient descent, in each iteration you must choose a random "neighbor" state that is close to the current state in the solution space. This is a crucial step that allows you to find a local minima before moving to a new "neighborhood". A simple and highly effective strategy for searching permutations is to swap the position of two randomly sampled words. This insures that the neighbors are very similar to each other and that any permutation can be reached in a reasonable number of transitions.

The "cooling schedule" is a function dependent on the time that controls the odds of keeping bad transitions. At the beginning lots of bad transitions are allowed. At the end the odds of allowing a bad transition are so low that it is effectively performing gradient descent. There is a proof that simulated annealing will arrive at an optimal solution if its cooling schedule is exponential and it is allowed to run indefinitely. This is a very good strategy even if you don't have an infinite number of CPU cycles to spare.

At each iteration you save a copy of the permutation if it is the best so far, because simulated annealing is not guaranteed to terminate on the best state it will visit.

# Answer
> 1 votes
No, that's not simulated annealing. It's not really even close.

Whether it will be a good enough approach will depend on your metric. Since you haven't told us what the metric is, it's not really possible to say. In the worst case, if your metric is sufficiently horrible, you might need to explore all $20!$ permutations. In any case, usually the only reliable way to find out whether your approach is a good one is to implement and see what happens. There are few theorems that gives useful provable results about how effective the approach will be; instead, you need to use empirical evaluation.

---
Tags: algorithms, permutations
---


title: TSP Variant --- Colored Path

text:
# Question
Title: TSP Variant --- Colored Path
Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be repeated. Then, you are given a sequence of colors, and you want to find the shortest path that follows this sequence. If all vertices are the same color, this is the same as TSP. However, if all vertices are different colors, there is only one solution.

Is this variant at all studied? Let $c$ be the maximum number of vertices which are the same color. Is the decision problem this variant NP-complete for some fixed, $c$, or alternatively is there a simple way to solve the decision problem polynomially for any finite $c$? Alternatively, one can bound $k$, the mamximum amount of times a given color appears in your path.

For $k=1$, it is polynomial. WLOG we can assume the path goes through colors $1,2,3,\ldots,x$. For each vertex of color 1, we consider each edge to a vertex of color 2. We keep track of the shortest path from color 1 to each vertex of color 2. Rinse and repeat for each color. This only requires $|\mathrm{color}\ i||\mathrm{color}\ i+1|$ additions and comparisons to get the shortest paths to each vertex of color $i+1$.

Additionally, I realize $k$ only matters if it is less than $c$, so bounded $c$ is polynomial if bounded $k$ is polynomial and bounded $k$ is NP-Complete if bounded $c$ is NP-Complete.

# Answer
> 2 votes
In this answer we prove the colored path problem is NP-hard for $c\ge 7$. I don't know whether it is NP-hard for $2\le c\le 6$. Without loss of generality, we prove the NP-hardness for the Hamiltonian Path problem variant, i.e., asking whether there exists such a colored Hamiltonian path, insteand of the TSP variant.

We use the normal reduction from 3SAT (with $n$ variables and $m$ clauses) to Hamiltonian Path with the following changes:

1. For each variable, we only have $2m$ nodes: $v\_1,v\_2,\ldots,v\_{2m}$. The $i$th clause corresponds to nodes $v\_i,v\_{i+1}$ and $v\_{2m-i+1},v\_{2m-i}$, i.e., if the $i$th clause contains the positive literal of this variable, we have the path $v\_i\rightarrow c\_i\rightarrow v\_{i+1}$, where $c\_i$ is the node corresponding to the $i$th clause; and if the $i$th clause contains the negative literal of this variable, we have the path $v\_{2m-i+1}\rightarrow c\_i\rightarrow v\_{2m-i}$. In addition, we add a *blank node* $b\_i$ between $v\_i$ and $v\_{i+1}$.
2. For each variable, for each $i$, we give $v\_i$ and $v\_{2m-i}$, $b\_i$ and $b\_{2m-i}$ the same color. In addition, we give $c\_i, b\_i, b\_{2m-i}$ the same color if the variable is contained in the $i$th clause.

The following graph is constructed from $(x\_1\vee \neg x\_2\vee x\_3) \wedge(x\_2\vee \neg x\_3\vee \neg x\_4)$. The number above a node represents its color.

3. We remove the edges to the sink node $t$. Instead, we add paths that pass through the blank nodes that may potentially not be visited due to visits of clause nodes. In the example above, the added edges form the following structure.

In the example above, we ask whether there is a Hamiltonian path with colors 1-2-3-4-5-4-3-2-6-3-7-8-7-3-6-...-11-3-8-14. You can check this reduction indeed works.

# Answer
> -1 votes
It is NP-complete.

It is obviously in NP.

To show it is NP-hard, reduce TSP to your problem. Say you require to repeat a certain sequence of colors. Just take the TSP instance and replace edges by paths with the repeat pattern of colors. Then the only legal way to move from one vertex to the next is by traversing that path.

---
Tags: np-complete, traveling-salesman
---