Prove or disprove NP-Completeness: An optimal ordering problem Consider assigning a single object to $n$ potential receivers. It can only be assigned to one person.

For each receiver $k$, there is a value of profit $v_k$ and a probability $p_k$.
 Fix an ordering of the receivers, then for the $i$th receiver he accept the object with probability $p_i$, if he does, we gain a value $v_i$; if he doesn't, consider the next person in the ordering.

Then the expected value we gain is

$E(V)=p_1v_1+(1-p_1)p_2v_2+\cdots +(1-p_1)(1-p_2)\cdots (1-p_{n-1})p_nv_n$

It can be easily seen: to maximize the expected value we gain, the ordering should be in the decrease of the $v$.

But since passing through the potential receivers the object defects the value of it, the $i$th receiver has a parameter $w_i$ where $w_1>w_2>\cdots>w_n$.

$v_k$ is assigned to each person $k$, and $w_i$ is assigned to the $i$th person in the ordering. For example if the $3$rd person in the ordering is person $5$, then he has $v_5$ and $w_3$.

so the expected value changes to

$E(v)=p_1w_1v_1+(1-p_1)p_2w_2v_2+\cdots+(1-p_1)(1-p_2)\cdots(1-p_{n-1})p_nw_nv_n$

Is there a polynomial algorithm to give an optimal ordering that maximizes the expected value? Or should this be NP-Complete?

Any hint is appreciated. Thanks in advance.

I think your question is better written as follows (to avoid ambiguity):
Find an order $\mathbf{s}=(s_1,s_2,...s_n)$ (that is, a permutation of $(1,...,n)$) such that
$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}w_1v_{s_1}+(1-p_{s_1})p_{s_2}w_2v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}w_nv_{s_n}.
$$
is maximized, where $w_i$ is the positive weight for the expected achievable value at the $i^{th}$ stage, $\mathbf{v}=\{v_1,v_2,\ldots,v_n\}$ and $\mathbf{p}=\{p_1,p_2,\ldots,p_n\}$ are the positive profits and the probabilities associated with the $n$ receivers. If $w_i$ is a linearly decreasing function, say, if $w_i=1-i\tau$, the objective function becomes:

$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}(1-\tau)v_{s_1}+(1-p_{s_1})p_{s_2}(1-2\tau)v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}(1-n\tau)v_{s_n}.
$$

Now, let us consider the following two orders which differ only in the $(i-1)^{th}$ and the $i^{th}$ positions: $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ and $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$. It is easy to show that

$$
E_\mathbf{s}>E_\mathbf{\tilde{s}}\Leftrightarrow\frac{v_1}{\frac{\tau}{\theta_1}+w_i }>\frac{v_2}{\frac{\tau}{\theta_2}+w_i }.
$$
which (I believe) implies that the problem cannot be solved by a simple index policy (i.e., a sorting algorithm), because whether $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ or $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$ is better really depends on $w_i$ (or the stage number $i$).

Here is a paper Optimal wideband spectrum sensing order based on decision-making tree in cognitive radio, which gives an exact algorithm assuming $w_i=1-i\tau$ and they claim that it runs in polynomial time $O(n^3)$, although the space complexity seems to be exponential.

I believe their algorithm holds for general monotonically decreasing $w_i$ values (with respect to $i$).

However, it seems that they solve the problem by finding the optimum from a set of candidate sequences. The running time is assumed to be proportional to the size of this candidate set. In order to find this candidate set, a branch and bound approach is adopted, but the time needed to compute this candidate set is ignored. So I double if their running time claim is valid.. I would really appeciate it if someone can convince me that their $O(n^3)$ claim is valid (and so it only takes at most $O(n^3)$ time to find the candidate set)? or if the problem (with $w_i=1-i\tau$) is actually np-hard? Thank you!


Algorithm to maximize function of subsets Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties.

What algorithm is most relevant in finding the subset of S that maximizes f?

The algorithm that iterates through every $2^{1000}$ subsets.  Sorry, but stated like this, the answer is that there is no solution.

For every algorithm you come up with, I can come up with a subset $T \subseteq S$ such that $T$ is the last of all sets to be tested, and be the max of $f$.


Changing variables in recurrence relations Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations.

The following method can be illustrated with this example. Suppose we have the recurrence

$$T(n) = 2T(\sqrt n) + \log n$$

Initially they make the substitution m = lg(n), and then plug it back in to the recurrence and get:

$$T(2^m) = 2T(2^{\frac{m}{2}}) + m$$

Up to this point I understand perfectly. This next step is the one that's confusing to me.

They now "rename" the recurrence $S(m)$ and let $S(m) = T(2^m)$, which apparently produces

$$S(m) = 2S(m/2) + m$$

For some reason it's not clear to me why this renaming works, and it just seems like cheating. Can anyone explain this better?

It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.

This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. Remember that $T(2^m) = 2T(2^\frac{m}{2}) + m$. Notice that, $S(m/2) = T(2^\frac{m}{2})$. If this particular point is still unclear, let $k =m/2$ and notice all we are doing is this $S(k) = T(2^k)$. Now, we can express $S(m)$ by expanding it to:
$$ S(m) = 2S(m/2) + m.$$ Solving for $S$ we see that it resolves to our familiar friend $O(m \log m)$.  Now that we've solved $S$ we want to express this in terms of $T(n)$. To do this, merely plug back in our original value for $m$ and we have $T \in O(\log n \log \log n)$.


Schwartz-Zippel lemma question Schwartz-Zippel lemma is as follows. Let $f(x_1,\ldots,x_n)$ be a polynomial of total degree at most $d$ over a field $\mathbb{F}$ and assume that $f$ is not identically zero. Pick uniformally at random elements $r_1,\ldots,r_n$ from the field $\mathbb{F}$ then probability that
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
Let us assume that $f$ is multiplinear which means each of the monomial in the polynomial $f$ is of same degree. My question is as follows. Is the following bound (given below) tight or we can come up with a better bound?
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$

If $f = \prod_{i=1}^d x_i$ is a single monomial then
$$
\Pr[f=0] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}.
$$
(The second bound is Bonferroni's inequality.)
This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.
The bound $1-(1-1/|\mathbb{F}|)^d$ is tight for multilinear polynomials, see this answer on math.se.


Better way to formulate these constraints? I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:

If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j'\neq j$.
If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j$ at time $t'\neq t$ using processor $k'\neq k$.

In other words, both constraints say that once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine.

For the first constraint, I write it as $x_{ijt}^k+x_{ij't'}^{k'}\leq 1$, for all $i,j'\neq j, k, k',t,t'$.

For the second constraint, I write it as $x_{ijt}^k+x_{ijt'}^{k'}\leq 1$, for all $i,j, k\neq k',t\neq t'$.

Can I improve this formulation?

Here is a different way to formulate the situation, which is simpler conceptually and which might be implemented more easily, although the number of variables is still the same (which can be not reduced fundamentally, anyway).

"Once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine". It looks like it is assumed that a processor is attached to the same machine regardless of the job or time. That means there is only one degree of freedom about the variable $j$ and $k$.

Let us use a new index $p=(j,k)$ to denote a pair of machine and a processor on it. Let binary variable $x_i^{pt}$ be $1$ iff job $i$ is assigned to processor $p$ at time $t$ (the index $t$ and $p$ is put together since they represent the resources). Then we can express the constraints as a single inequality,
 $$x_i^{pt}+x_i^{p't'}\leq 1\quad \text{ for all }p\neq p',t,t', i$$

In the actual programming, we can pack $j$ and $k$ side by side to form $p$ as the union structure in C/C++. For example, let $p$ be a 32-bit unsigned integer whose upper 16 bits is $j$ and whose lower 16 bits is $k$. We can also use a hash table with $p$ as keys and $(j,k)$ as values.


Is this problem in NP? I am new in complexity theory and have a doubt.
If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) Output all the words in D that can be generated by the symbols in L So, for the example above a program will output: "abY";"ba";"000001◄" Question is: is this problem in NP?
Thank you in advance.

Your question makes a category error. Your problem is an enumeration problem ("List all the things with property X") but NP is a class of decision problems ("Does the input have property X?").

In any case, there is an obvious deterministic polynomial time algorithm for your problem. Just check each character of each string against $L$. If $L$ is fixed, this runs in linear time; if it's a part of the input, it runs in quadratic time.


How to find number of permutations of 1-N length, each [1-N] with k values This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values.

A real-world example might include 5 different single-digit combination locks.

How many different ways could I lock a single gate, assuming that I can use any number of locks?

Assuming that each lock takes values ([1-3], [1-3], [1-3], [1-3], [1-3]) There would be 3^5 ==  243 possible combinations. But I'm also interested in calculating the total number of combinations possible by using subsets of the 5 locks, so adding the solution for each combination of four locks, each combination of 3 locks and so on. The solution would also ideally be generalisable so that each list of values can differ i.e. ([1-2], [1-10], [A-C] ... )

Does there exist a mathematical solution to this problem?

edit:

In the main, the question is about a general purpose mathematical solution. For example, to find the number of combination of a set of length (3), one uses 3! ie. 6 combinations of [1,2,3].

I was wondering if there exists a general purpose solution to the above scenario. If not, I would think it could be possible to program something to recurse over the possibilities, which I guess is why I decided to post it here first as my search for a mathematical solution came up empty handed.

Some examples of inputs and outputs as requested:

input = [A,B,C] [1,2,3,4,5] [G,H]

output combinations are all possible combinations of those three lists, without needing to sample all three lists. Note combinations, hence [A1G] == [G1A]

i.e. (this is not all the combinations):
A
B
C
A1
A2
A3
...
C4
C5
A1G
A1H
A2G
A2H
...
C5G
C5H
...
1
2
3
4
5
1G
1H
.
.
5G
5H
..
G
H

(Your lock values are all distinct. We could instead consider the locks distinct.)

We add a nil value to each lock, representing the lock not being included. Using your example, we get ...

input = [A,B,C,nil] [1,2,3,4,5,nil] [G,H,nil]

... to choose from. There are ...

$$4 \times 6 \times 3 = 72 $$

... ways to do this.

In general, from sets $Locks$, there are ...(

$$\prod_{l \in Locks} (\vert l \vert + 1)$$

... ways.

So far, so mathematical. Now let's generate the possibilities. I'll have to use a programming language. My choice is Clojure, a Lisp. We should be able to at least verify the above result.

(def locks '[[A,B,C] [1,2,3,4,5] [G,H]])

(defn combos [ls]
  (if (empty? ls)
    [()]
    (let [[l & ls] ls
          sub-list (combos ls)]
      (concat
        sub-list
        (for [x l, y sub-list] (cons x y))))))

Now

(count (combos locks))
=> 72

... as expected.

There are better ways to depict the problem space, but this'll surely do.


Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$ I need to construct linear bounded automaton for the language $L = \{ a^{n!} : n \geq 0 \}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a. I might want to hear a few suggestions, as I am experiencing difficulty in developing the specific LBA for it.

The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: divide $m$ by $c$, and increment $c$. The algorithm terminates when one of the following happens: $m = 1$, in which case you can declare success; or $m$ is not divisible by $c$, in which case you can declare failure.


Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify? I'm looking for a problem that allows me to generate random instances which:

Take arbitrary time to compute (i.e., I can generate an instance that I know would take at least 10 days to solve in an Intel I7);
Is inherently sequential (no matter how many processors you throw at it, it won't be solved faster than 10 days);
Can produce N (say, 2^256) equiprobable outputs;
Given an output, it is easy to verify it is correct.

Example:

Find the smallest N such that sha256^N(seed) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. But verifying is hard: the only way to prove an N is correct is re-doing the whole computation, so it doesn't really fit.
Find an N such that sha256(seed+N) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. It is easy to verify the output is correct. But it is embarrassingly parallel.

Requirements 1-3 describe a timelock puzzle, also known as timed-release cryptography or time capsule cryptography.  For instance, https://crypto.stackexchange.com/q/606/351.

Requirement 4 says it also has to be easy to verify a correct solution.  I don't know of any standard scheme for timelock puzzles that happens to satisfy all four requirements, but you can invent one.

For instance, here is one simple approach that works, if you trust the creator of the puzzle to not try to play games with you.  The creator picks a random AES key $k$, encrypts $k$ using the timed-release cryptography / timelock puzzle, and publishes the ciphertext as well as a SHA256 hash of $k$.  Now requirements 1-3 are satisfied (it'll take a precisely-controllable amount of time for anyone else to recover $k$), and once you've found $k$, it is easy to verify that you found it correctly by hashing it and comparing the result to the publicly known hash.

For more on timelock puzzles, see also:

https://crypto.stackexchange.com/q/5831/351
https://crypto.stackexchange.com/q/9327/351
https://security.stackexchange.com/q/89094/971

and papers in the cryptographic research literature.


Are all Recursively Enumerable languages which are not Recursive also Undecidable? Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable?
R.E. ==> Recursively Enumerable

A language is recursive (newer terminology: computable, also decidable) is there is a Turing machine that always halts that recognizes the language. It is recursively enumerable (new: computably enumerable) if there is a Turing machine that accepts it (it halts and accepts for strings in the language, it might never halt for strings not in the language). If the language is not recursive, it isn't decidable ("recursive" and "decidable" are alternative terms for the same class of languages).


Why can any polynomial and exponential be represented as a recurrence? I posted this question on math.SE but I haven't got any reply so I'm posting here also.

I am reading The Algorithm Design Manual by Steven S Skiena.

In Section 4.10.1 Recurrence Relations, I understand what a recurrence relation is, but after that following statements have been given:

  Any polynomial can be represented by a recurrence, such as the linear function:
  $a_n = a_{n-1} + 1, a_1 = 1 \implies a_n = n$

  Any exponential can be represented by a recurrence:
  $a_n = 2a_{n-1}, a_1 = 1 \implies a_n = 2^{n-1}$

Can anyone explain me the above statements by proving them for any linear function and exponential function, respectively?

EDITED : After help from Raphael and Yuval Filmus , I concluded following prove. Correct me if I am wrong

For any Liner function, General form is $a_n = \alpha n + \beta$
$a_n - a_{n-1} = \alpha n + \beta - (\alpha (n-1) + \beta)$
$a_n - a_{n-1} = \alpha n + \beta - \alpha n + \alpha - \beta$
$a_n - a_{n-1} = \alpha \implies a_n = a_{n-1} +\alpha $
As relation holds in question,  $a_n = a_{n-1} + 1 \implies \alpha = 1 $
Now,
$a_{n-1} = a_{n-2} + \alpha , a_{n-2} = a_{n-3} + \alpha , a_{n-3} = a_{n-4} + \alpha , ...$
Therefore, we can expres $a_{n}$ in terms of $a_{n-2}$ and so on
$a_{n} = a_{n-2} + \alpha + \alpha \implies a_{n} = a_{n-2} + 2\alpha $
We can generalize
$a_{n} = \alpha + (n-1)\alpha  \implies a_{n} = n\alpha $
As $\alpha = 1 \implies a_{n} = n$

For Exponential, General form is $a_n = cb^n$
$a_n - a_{n-1} = cb^n - cb^{n-1} \implies a_n - a_{n-1} = cb^n - cb^n . b^{-1}$
$a_n - a_{n-1} = cb^n\left(1 - \dfrac{1}{b}\right) $
Substitute  $a_n = cb^n$
$a_n - a_{n-1} = a_n\left(1 - \dfrac{1}{b}\right) $
$a_{n-1} = \dfrac{a_n}{b} \implies a_{n} = ba_{n-1}  $
As relation holds in question,  $a_n = 2a_{n-1}  \implies b = 2 $
Now, $a_n = cb^n \implies a_1 = cb^1$
Substitute $a_1 = 1$ and $b=2 \implies c = \dfrac{1}{2}$
Substitute c and b in general form i.e. $a_n = cb^n$
$a_n = \dfrac{1}{2}2^n \implies a_n =2^n2^{-1} \implies a_n = 2^{n-1} $

The general form for a polynomial is $a_n = \sum_{i=0}^k c_i n^i$. Thus, for $n>0$, we have
$$a_n - a_{n-1} = \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,$$
which can be transformed into the recurrence
$$a_n = a_{n-1} + \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,~~~ a_0 = c_0.$$

For exponentials, the general form is $a_n = c\cdot b^n$. In complete analogy to the example in the book, this is generated by the recurrence
$$a_n = b\cdot a_{n-1},~~~ a_0 = c.$$


Can a No-Knowledge Proof exist? A Knowledge Proof is a mechanism by which a 'prover' entity can show to a 'verifier' entity that it possesses some certain information without revealing what that specific information is (within some arbitrarily small tolerance of certainty).
Is it possible for a 'prover' to show to a 'verifier' that it does not possess some certain information (without the 'prover' being computationally limited, etc.)?

No.  An algorithm that has access to some information can always ignore it and make decisions without looking at it, and then its externally observable behavior will be indistinguishable from an algorithm that doesn't have access to that information; so no verifier can tell the two apart.
I suggest being a bit cautious: when we talk about words like "knowledge" in the context of algorithm, we are applying some human intuition and interpretation to the underlying mathematics.  The precise meaning is given by the formal mathematical definition.
Incidentally, it's called a proof of knowledge, not a knowledge proof.


Find the $k$-th lexicographically smallest hamiltonian circuit Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order.

For example, if we have complete graph with $4$ nodes, and $12$ edges. The smallest hamiltonian circuit is $1 - 2 - 3 - 4$, the second one is $1 - 2 - 4 - 3$. Since finding hamiltonian circuit is NP Hard, what is the best complexity we can get this algorithm at?

Hamiltonian circuit is path that visits each node exactly once.

For the purpose of the problem, the circuit should begin in node $1$

What I think

If we have adjacent list of nodes connected to node $1$, sorted, then the permutations numbered from $[1, x]$ will pass in the first node, the on the second node the permutations numbered $[x, y]$ will pass the second node, etc..

Now our task is actually to find the $x, y...$ And we can solve for the second node (that we called from node $1$) for each of nodes adjacent to it, but this leads us to time complexity of $O(N!)$. Can we do it faster?

Counting the number of Hamiltonian circuits in a graph is $\mathsf{\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph.

As an aside, let me mention that listing things in lexicographical order might be harder than listing them in any order. A case in point is the complexity of finding a [maximal independent set], which is an independent set which cannot be enlarged (but not necessarily one which has maximum size). A maximal independent set can easily be found by going over the vertices in some arbitrary order, putting the problem in the complexity class $\mathsf{P}$. This algorithm can be improved, and in fact a maximal independent set can be found in $\mathsf{NC^2}$. In contrast, finding the lexicographically first maximal independent set (that is, deciding whether a given vertex belongs to this set) is $\mathsf{P}$-complete.


Why is this grammar ambiguous? S ::= x
S ::= if E then S
S ::= if E then S else S

This is example if E then if E then x else x proves that it is ambiguous but I don't see why? Isn't it just an if statement within an if statement.

Rici is correct.  The statement could be reasonably interpreted, as you first assumed:

if E then ( if E then x ) else x

It may also be interpreted:

if E then ( if E then x else x )

In a context-free grammar, the allowable set of expressions are determined through substitution.  In the first interpretation I took your third statement and substituted the first S for the second statement, and then replaced all remain S with x.  In the second interpretation, I took your second statement and replaced it with the third statement, and replaced the remaining S with x using the first statement.


Applying BNF rules to themselves? Say we have some BNF rules for example:

$$A ::= B C$$
$$Dx ::= ExFx$$
$$x ::= y$$

So we might start with $Dx$ and apply rule 2 to get $Ex Fx$ and then apply rule 3 to get $Ey Fy$. But starting with $Dy$ we can't get anything. Unless...

What if we extend the BNF rules to let the rules apply to other rules. Then we could take rule 3 and apply it to rule 2 (interpreted as a string) to get a new rule:

$$Dy ::= EyFy$$

My question is, if we allow such creation of new rules like this. What kind of grammar do we end up with? What is the name of it? Is it equivalent to church lambda calculus?

Using these rules we could express the grammar where the quantity matches the noun and determiner like this:

$$amount ::= singular|plural \\
NP(amount) ::= det(amount)\ \ noun(amount) \\
det(singular) ::= a | one \\
det(plural) ::= some | two | three \\
noun(singular) ::= cat | dog \\
noun(plural) ::= cats| dogs
$$

From which we would get $some\ cats$ and $one\ dog$ for example.

There seem to be several levels of such grammars.

If the number of possible $y$ is finite, then each $By$ can be coded as a separate variable (like $B_y$) and your grammar is basically a "compressed" context-free grammar.

In case of an infinite number of values the $y$ can behave like stacks of symbols (which can be pushed, popped and copied to other variables) a possible formalism is that of indexed grammars.

Even more is possible with attribute grammars, where the attributes can be operated on (you can add for instance the attributes of children). Moreover the values can be passed either up or down the derivation tree (synthesized or inherited).


Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$ Let us say there is a Turing Machine $M$ and a string $x$.  So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the string it would halt after a finite time and I would get my answer.  But how do I know if the machine loops on the string or not.

One possible way is to see if a configuration repeats itself. However, the machine has no way of knowing  if the configuration has occurred before because it cannot store them . So, we would never get an answer. So, how will I be able to tell whether or not $x$ is accpted or rejected or looped upon by $M$.

Halting problem is generally unsolvable. The states don't have to repeat. But if you know that they will, see cycle detection.


Brandes' betweenness algorithm for weighted undirected graph I am studying Brandes' betweenness algorithm for weighted undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm),

If a node is first encountered, then we have to check d[neighbor_node] < 0.
But if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?
If greater, then do I have to delete previous updates like Queue, Pre[] and others?

Note: I assume that the OP is talking about Algorithm 1 in the paper "A Faster Algorithm for Betweenness Centrality" By Ulrik Brandes.

You probably have noticed that Algorithm 1 in the paper is for unweighted graphs. In this case, Dijkstra's algorithm@wiki amounts to BFS and a shortest path for a vertex $v$ is found immediately when $v$ is first encountered (in the pseudo-code, it is represented by if d[w] < 0 then). This property is due to the layer-by-layer search feature of BFS.

  $Q_1:$ If a node is the first occurrence , then we have to check d[neighbor_node] < 0. However, if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?

For weighted graphs,  the property mentioned above does not necessarily hold. So you need to replace (meaning the following is not needed any more) the if d[w] < 0 then predicate by a slightly involved one suitable for weighted graphs:

          [foreach] neighbor w of v [do] [if] d[v] + length(w,v) < d[w] [then]

Note that for weighted graph, you should use a priority queue.

  $Q_2:$ If greater, then do I have to delete previous updates like Queue, Pre[] and others?

No. You set d[], P[], sigma[] only when a shortest path is found. It is valid all the time once it is set. No need to update them later.


Understanding google's user level threads in kernel threads I came across Paul Turner work on increasing efficiency of M:N threading model. I am not able to grasp the concept at slide 18 of LPC-User-Threading

It says : for two threads A and B :

Minimal scheduling operation.
● B inherits A’s virtual runtime.
● B was not runnable, so we don’t need to remove it from runqueues.
● B holds references on same objects as A

What does virtual runtime mean in this case ?

Will not a random thread B inheriting A's environment and referencing same objects cause any problems ?

The video is present at video for the interested.

This is talking about user level threads, so they should all have the same memory context (virtual memory map).  So while the threads need to be careful in doing so, they can all access each other's objects directly without using inter-process communication.

The scheduler will give each thread a time slot to run in (length possibly depending on priority).  He is discussing an addition to the kernel to allow a request:

  pid_t switchto_switch(pid_t tid)

  Synchronously transfer control to target sibling thread, leaving the
  current thread unscheduled.
  Analogous to: Atomically { Resume(t1); Wait(NULL); }

So as a programmer, if you had work on a task that you need to stop and wait for information from another task before you can continue, then you could request to immediately switch to that specific thread.

Your intial thread would immediately be put in a wait state, and the other thread would resume execution using the initial thread's currently scheduled time ("B inherits A’s virtual runtime").


Closure of context-free languages under regular quotient Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that
$C / R = \{w| \exists x \in R: wx \in C\}$
is also a context-free language?

Let me prove the following more general statement:

  Every full trio is closed under right quotient by a regular language.

Let $\mathcal{L}$ be the full trio, let $L \in \mathcal{L}$ be a language over $\Sigma$, and let $R$ be a regular language over $\Sigma$. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$. Define the homomorphism $h\colon \Sigma \cup \Sigma' \to \Sigma$ by $h(\sigma) = h(\sigma') = \sigma$, and define the homomorphism $k\colon \Sigma \cup \Sigma' \to \Sigma$ by $k(\sigma') = \sigma$, $k(\sigma) = \epsilon$. Then
$$
L/R = k(h^{-1}(L) \cap \Sigma^{\prime *} R).
$$


Trying to figure out the best way to approach this problem with Computer Vision Newbie to CV here so sorry of this is basic.  Here's the deal, I have a program that I run many times. and each run I produce a screenshot.  I need to compare screenshots from N-1 and N runs and make sure they aren't different in any dramatic way.  Of course there are some minor changes like logos and pictures getting updated, etc.
SO far I've used something as simple as absdiff from opencv to highlight the difference regions and then use some sort of threshold to determine whether something passes or not. But I want to make it slightly intelligent but I'm not 100% sure how to proceed.  Google hasn't yielded ghe best answers.
Essentially, I want to train the model on many different pairs of images and have the output be binary, yes or no depending on whether it should pass or not.  In theory, I should be able to plug in 2 images and based on previous training, it should be able to tell me whether there is significant difference or not.  What are some ways I might approach this, particularly with regards to what kinds of models to use.  Thank you!

I am skeptical whether computer vision is going to be the most effective approach, but you can certainly do it.  There is lots of work on image similarity metrics using neural networks (Siamese networks, triplet loss, etc.) and you could certainly implement any of those architectures, acquire a few thousand labels, and train on it.  I would suggest pre-training on some standard similarity dataset (e.g., start with LPIPS) and then fine-tune on your data.  But be prepared that this might or might not be effective.
It might be more effective to extract features and then build a ML model that works with those features rather than with the raw images.  For instance, OCR both images and compare them; compute L1 and L2 distance; etc.


Space efficient representation of Regular graphs Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time. Assume that neighbours of each vertex are ordered.

Note that $k=O(\log n)$

Is there an representation of graph $G$ that takes $o(nk)$ space in words such that query can be solved in $O(1)$

No.  Even ignoring the requirement to answer queries, you can't store such a graph in $o(nk)$ space, assuming each word is $\Theta(\lg n)$ bits long (i.e., each word has space to store the index of a single vertex).

In particular, there are ${n-1 \choose k}$ ways to choose $k$ neighbors of a single vertex, so there are ${n-1 \choose k}^n$ possible $k$-regular graphs.  Now

$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$

Thus, information-theoretically, you need at least $\Omega(kn \lg(n/k))$ bits to store such a graph, or equivalently, at least $\Omega(kn \lg(n/k)/\lg n)$ words.  Notice that for $k=O(\log n)$, we have $\lg(n/k)/\lg n = \Theta(1)$.

Therefore, we find that we need at least $\Omega(kn)$ words just to represent all possible $k$-regular graphs, so there is no hope for a data structure with space complexity $o(kn)$, even if you ignore the query time requirement.


Compiler Design Question $\text{Consider the following ANSI C code:}$
int main(){
 Integer x;
 return 0;
}

$\text{What will be the type of error?}$
$\text{a) Lexical}$,
$\text{b) Syntax}$,
$\text{c) Semantic}$,
$\text{d) None}$  $\tag {GATE-CS 2021}$
According to me, Syntax Analysis phase should detect the error as there is no grammar in C which produces Integer x or in tokenized form id id. Any help is appreciated. :)

Your statement "Integer x;" is syntactically "identifier identifier;" which is a perfectly fine variable declaration. Semantically, the first identifier must be defined as a type, and the second identifier must not be defined as a variable in the same scope. The first condition fails, therefore ...
And you might download a copy of the C Standard to check if "int main()" is acceptable, or whether it must be "int main(void)", which is preferable and might be required.


DLOGTIME complexity class and testing the length of the input string I read that testing the length of the input string is in DLOGTIME.

The question is how can testing the length of the input string be in DLOGTIME?

$\text{DLOGTIME} = O(\log n)$, so what number would be in $n$? (as it seems that $n$ is definitely not the length of the input string..... or is it?)

So, to summarize, can anyone show me how the algorithm performs and how it is in DLOGTIME? At this point, it seems to me that $n$ is just an arbitary number..

Note: I know what binary search is :) so you do not need to explain me about what that is.

It is hard to answer the question without further context.

Complexity is typically defined in terms of the size of the input (the number of bits needed to represent the input) and therefor depends on the representation you choose for the inputs. (More formally, a language or a formal computational problem is defined over strings of the alphabet, and the complexity is defined based on that, how you interpret these strings as objects (e.g. graphs, natural numbers, etc.) doesn't have an effect on the complexity, a "problem" corresponds to several (formal) computational problems based on the representations used.)

The complexity class $\mathsf{DLogTime}$ is defined as deterministic logarithmic time in the input size, $n$ is the size of the input. I guess you are confused because we typically use Turing machines for defining complexity classes but that may not make sense for sublinear time since one cannot even read the input. For sublinear time the model of computation is typically considered to be Random Access Machines where one can access any bit of the input directly without going over all previous bits using indexes (kind of similar to how memory works in real computers).

One can find the length of the input in two steps using an index variable (a binary number):

Start from 1 and repeatedly double the value till the memory square corresponding to it is blank (an upper bound on the length of the input),
Do a binary search to find the last nonblank symbol. (Blank symbol is not used in the input.)

If the input is a string of length $n$ then this algorithm will find the size of the input in binary in time $O(\lg n)$.


How does the computer determine whether a number is smaller or greater than another? It might sound like a stupid question but I'm really curious to know how a computer knows that $1<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is A,B,C,D,...? Is it somewhere stored in the hardware or does the operating system provide this kind of information?

First your integer numbers are converted into binary numbers. For example, the integer 2 is converted to 0010.

The CPU uses a digital comparator:

  A digital comparator or magnitude comparator is a hardware electronic
  device that takes two numbers as input in binary form and determines
  whether one number is greater than or less than or equal to the other
  number.

  Comparators are used in central processing units (CPU) and microcontrollers.

  Source: https://en.wikipedia.org/wiki/Digital_comparator

In comparator hardware some gates are used (AND, OR, NAND, NOR, XOR, etc). These gates take binary inputs and give result in binary. The output can be seen from a truth table.

Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

Here 0 & 1 are  electronic voltages for the gate.
1 - Represents some threshold voltage which indicates some positive voltage. 0 - Represents the voltage below than the threshold.

E.g. suppose a comparator works on 5 volt (it is consideration for explanation) then:
Voltage more than 3 volt can be considered as binary-1.  Voltage below than 3 volt be considered as binary-0

If a gate gets one input as 3.5 volt and another input as 2 volt then it considers as, it takes one input as binary 1 & another input as binary 0.

These sequences of 1's & 0's are provided very fastly through the switching circuit.

The operation of a two bit digital comparator can be expressed as a truth table:

 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

To quote from Wikipedia:

  Examples:
  Consider two 4-bit binary numbers A and B such that

  Here each subscript represents one of the digits in the numbers.

  Equality

  The binary numbers A and B will be equal if all the pairs of significant  digits of both numbers are equal, i.e.,
   .  .   .

  Since the numbers are binary, the digits are either 0 or 1 and the boolean  function for equality of any two digits  and >  can be expressed as

    is 1 only if  and    are equal.

  For the equality of A and B, all  variables (for i=0,1,2,3) must be 1.
  So the quality condition of A and B can be implemented using the AND operation as

  The binary variable (A=B) is 1 only if all pairs of digits of the two numbers are equal.

  Inequality

  In order to manually determine the greater of two binary numbers, we inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B.
  This sequential comparison can be expressed logically as:


Does hardness of a special case imply hardness of a general case? I am wondering in general if it is correct to claim that if a special case of a problem is NP-Hard, the general case of that problem is NP-
Hard too?

For example: Min Set-Cover is NP-Hard does it imply without having to prove that Min Set-k-Cover where each element needs to be covered k times is NP-Hard too?

If frafl's answer doesn't give it away immediately, perhaps think in the reverse direction, if the special case is NP-hard, what would be implied by the general case being in P?


Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language?

One of the trivial ways I know of is to convert $G$ into a CNF form. which motivates my second question,

Can two different Context-Free-Grammars in CNF, $G_c$ and $G_c^\prime$, generate the same language? (I would appreciate a proof of it)

Chomsky normal forms are not unique. If they were, we'd have an algorithm for deciding whether two CF grammars are equal. But equivalence of CF grammars is undecidable.


Determine if a language is decidable $$ L=\{<M>|M\ is\ a\ TM\ ;\ ∃x,|x|<5 ;\ M\ rejects\ x\} $$

How can i prove that $L \notin R$?
I can't see how Rice's theorem be used here since the conditions are not met (The constrain $M\ rejects\ x$ is about the machine architecture and cannot be expreseed by a non-trivial language)

Actually "M rejects $x$" just means that $x \notin L(M)$, which is a statement about languages so Rice's theorem applies.

Use the decider for $L$ to solve the halting problem: On input $M$ and $w$, construct the machine $M_w$ that ignores its input and simulates $M$ on $w$. If the simulation halts, $M_w$ accepts. Otherwise, it doesn't.

So $M_w$ either accepts all strings (if $M$ halts on $w$) or no strings (if $M$ doesn't halt on $w$). You apply your decider to $M_w$. If $M_w$ accepts all strings, the decider will REJECT: the machine doesn't reject any short strings. If $M_w$ accepts no strings, the decider will ACCEPT: the machine rejects some short strings (in fact, all of them). We return the opposite answer, solving the halting problem.

It follows that a decider for $L$ can effectively solve the halting problem; therefore, such a decider does not exist.


What is the time complexity for getting the size of a heap? Assuming the regular Heap ADT.

What is the time complexity of getting its size ?

I tend to think that because insert is O(log(n)), then I always know the last index of my heap. So in order to get its size all I need is to return the last index + 1.

However I have seen in some places that refer to the size of the heap's complexity as O(n), since I need to count all the nodes in my heap.

Why am I wrong ?

If you're talking about an ADT, you can't really say. It depends on the implementation. You can certainly do it in O(1) (for example by keeping a counter).


Dynamic programming: Knapsack with repetition, Find the number of redundant machines I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted to solve the following exercise that is related with this topic, and so far I think I have a way how to approach it , but I am stuck at one point. Please, if you can, read my solution and tell me whether I am doing something wrong. I absolutely do not want you to solve it for me, just give me some help/hints.

A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine M_i. Each machine M_i has a probability r_i of functioning reliably and a probability 1-r_i of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r_1,r_2,...,r_n. To improve this probability we add redundancy, by having m_i
copies of the machine M_i that performs stage i. The probability that all m_i copies fail simultaneously is only (1-r_i)^(m_i), so the probability that stage i is completed correctly is 1-(1-r_i)^(mi) and the probability that the whole system works is prod(i=1,n){1-(1-r_i)^(m_i)}. Each machine M_i has a cost c_i, and there is a total budget B to buy machines. (Assume that B and c_i are positive integers.) Given the probabilities r_1,...,r_n, the costs c_1,...,c_n, and the budget B, find the redundancies m_1,...,m_n that are within the available budget and that maximize the probability that the system works correctly .

________________________ MY PROPOSED SOLUTION

We need to make sure that all the given probabilities are different from 0, meaning for all r_1 !=0 (if we had a probability 0 the system would not work)
We must make sure that we have at least one machine of each type, meaning we have one copy of each machine (if we do not have a certain machine, like in point 1 the system would not work). In addition, by having already a copy of machines from m_1,...,m_n, the total cost of this machines would be sum(i=1,n)=c_i. This means that from the total budget B we need to subtract this cost, and get the extra budget for the redundant machines. B_extra= B-sum(i=1,n)=c_i
To find the redundant number of machines we just need to model the problem as knapsack. Subproblem: K(c) ->maximum probability that a system works correctly. Recursive relationship:

for c=1 to B_extra
 K(c) = max{K(c-c_i)*(1-(1-r_i)^(m_i)):c_i<=c}

Now, the points where I am stuck and need help are:

The way I am defining the problem, is it correct or am I missing any special case? I think that the recursive relationship should work fine; any reason why it shouldn't?
How should I keep track of the number of m_i machines. I know that the initial value for each m_i is one (from point 2 we need at least one copy of each machine). Should I just keep track of another variable in the problem K(c, m) and every time increase m_i++?

the maximum sucesss probability would be the minimum failed probability, and each machine should be at least 1, so we can reduce the original package B into B'= B-sum(c_i), and each machine's dp[i][0] should be initialized as fail probability (1 - r_i).

so, we can find the dp state transition based on the modified knapsack(size is B') problem as above:

dp[i][c]    = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i))
    0<= c <=B' , 1<=i<=n, B' = B-sum(c_i)

intitial of the dp array would be like this:

dp[0][0~B'] = 1
dp[i][0]    = 1-r_i, 1<=i<=n

so the pseudocode would be like :

 for(int i = 1 ; i<=n;++i)
  for(int c = cost[i] ; c<=B';++c)
     dp[i][c] = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i)))


Cost of find operation on a tree data-structure I implement my data sets with a tree data-structure.

The tree data-structure has a method named MakeSet which creates a set with one node. The tree data-structure has also a method named Merge(i,j) which merges trees of set i and set j in this way: the set with smaller depth becomes a child of the root of the set with larger depth.

I do MakeSet $n$ times and I do MergeSet $n-1$  times with a random order. Then I do a Find operation. What is the cost of Find in a worst case scenario?

I feel like the answer might be $O(n\log{n})$, because after doing $n$ MakeSet and $n-1$ MergeSet, it might be safe to say that we have a tree with $n$ nodes and height of $\log{n}$. I'm not sure.

Since my two comments already form the solution, I can also write the answer in total.

If you have a datastructure consisting of a bunch of trees, then the worst-case cost of a Find-Operation is the maximal height of a tree in your data structure. Your trees are built from $n$ trees consisting of a single node each by $n-1$ Merge-Operations. A Merge-Operation merges two trees such that the tree of smaller height is added to the root of the tree of larger height.

First observation:
If you merge two trees of different height, then the resulting tree has the same height as the initial tree of larger height.

Second observation:
If you merge two trees of the same height $h$, then the resultung tree has height $h+1$.

Conclusion: To increase the maximum height from $h$ to $h+1$, you first need two trees of height $h$.
So the worst-case scenario in your setting is the following:
You initially merge two trees consisting of a single node each. This gives a tree of height $1$. You now need to merge two other trees consisting of a single node each such that a second tree of height $1$ occurs. If you now merge this trees of height $1$, then you have a resulting tree of height $2$. Now if you want to increase the height again, you need again $4$ of the initial trees to construct an other tree of height $2$.

The iteration of that argument shows that you can only increase the height $\log n$ times, where $n$ is the number of initial trees.


Can I remove left recursion on this grammar $S \rightarrow Sa \mid S \mid \epsilon$

This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but I think it gives something like that :

$S \rightarrow S'$

$S' \rightarrow aS \mid S' \mid \epsilon $

but this is equivalent to say

$S' \rightarrow aS' \mid S' \mid \epsilon $

Is this the right way to think about this?

Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$.

If you analyze carefully you will see that you are not applying Algorithm 4.19 at all. We are just removing left recursion where we have only immediate left recursion.

Cycles are of the form $A\rightarrow B, B\rightarrow C, C\rightarrow A$. When we remove left recursion in immediate left recursive grammars, we are ignoring $S\rightarrow S$.

Also presence of $\epsilon$ creates problem for the algorithm 4.19 given in the red dragon book (2007 edition), but the method of removing left recursion in immediate left recursive grammar works even in the presence of $\epsilon$.


Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism? Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”:

decreased transistor size (thereby decreasing delay time between computations).
increased transistor quantity

It seems to me that the first factor should speed up any existing design (it simply allows a higher frequency of computations without a change in design), but it seems to me that the second factor generally requires a change in design in order to actually improve performance.

So I am trying to understand how increasing the number of transistors in a CPU can help you increase computations. I’ve looked online but couldn’t find a definitive answer.

My current understanding is that in order to leverage an increase in transistors to get increased performance, you need to employ various kinds of parallelism.

By increasing the word size of CPU’s from 1 bit to 2 bit to 64 bit, modern CPU’s can use bit-level parallelism to perform more computations in a single instruction.
By employing smart control architectures (i.e. in the control unit), a CPU can smartly handle multiple instructions that don’t require the same CPU components at the same time, thereby employing instruction-level parallelism
By splitting instructions into parts, a CPU can get parallelism through pipelining, by performing the first parts of instruction B before the last parts of instruction A are done.

These are various ways in which we can use more transistors to get more performance, and they all use the increased number of transistors in some way to perform the same computations that earlier computers did, but now they do it in parallel.

Is my understanding correct, that the primary/only channel through which increased transistor count results in increased performance is through parallelism? Or are there ways that we can use increased transistor count to improve performance that rely on other techniques than parallelism?

There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance.

One of them is parallelism, as you point out.

A second technique trading off more transistors for performance is speculation.  Often speculative execution of some kind is combined with parallelism, and this kind of performance optimization happens at all levels.  For example:
A carry-select adder compputes both a+b+0 and a+b+1 and then selects the correct answer when the carry bit becomes available.
In predicated execution we might execute instructions before we know their results are needed, and then commit the results to the register file only once we know the computation was needed.
In checkpoint repair we speculatively execute instructions that follow an instruction that might (but probably won't) cause an interrupt.  And similar approaches can be used to speculatively execute the instructions that follow a branch instruction.  Prefetching uses extra transistors to fetch data or instructions that might (but won't necessarily) be needed in the future.

Both branch speculation and prefetching are often augmented with even more transistors to predict what intructions/data has the highest probability of being useful in the future.

A third approach for trading off transistors for performance is caching.  A cache is a (usually small and fast) memory used to store the results of expensive work, so that if an identical request is made in the future the result can be returned from the cache rather than by recomputing the result.


If $L$ is recursively enumerable (or recursive) then so is $L′$ Given a language $L \subset \{0, 1 \}^*\#\{0, 1 \}^*$ and a language $$L'=\{u \in \{0,1\}^* | \textrm{ There is a word }w \in \{0,1\}^*  \text{, so } u\#w \in L\}$$

Prove or disprove:

If $L$ is recursively enumerable, then $L'$ is recursively enumerable.
If $L$ is recursive, then $L'$ is recursive.

My idea for 1:
Since we know by the definition of $L'$ that for every $u \in L'$, there must be a $w \in \{0,1\}^*$, so $u\#w \in L$. So we can construct a Turing-machine $M_f$, which decides the function $f: \sum ^* \to \sum ^*$ where $\sum^*$ is the alphabet, so  $$u \in L' \iff f(u) = u \# w \in L$$
So $L'$ is reducible with $L' \le L$, and because $L$ is recursively enumerable, $L'$ is recursively enumerable.

Regarding the second questions, I would argue the same but I think it is possible to construct a more detailed turing machine. Any hints?

The second item is in fact false. Consider the language $L$ consisting of $u\# w$ such that the $u$th Turing machine halts within $w$ steps. This is recursive, but $L'$ is the language corresponding to the halting problem.


Is it possible to define a pairwise function that can either append to a tuple or make a tuple, potentially with nested tuples? I lack the vocabulary to appropriately express the question succinctly, so I apologize if the title question is confusing.

Suppose you can define a binary infix operator that produces tuples, and you want this operator to be able to simultaneously:

Extend a tuple to arbitrary length by appending additional elements
Support nested tuples (in that they are not "flattened" into the tuple)

Suppose the operator is represented by ., I can do (1.) in pseudocode by:

define generic <Type T (T != Tuple), Type U>
operator (.) (T left, U right) => Tuple<T, U> {
  createTuple(left, right);
}

define generic <Type... T, Type U>
operator (.) (Tuple<...T> left, U right) => Tuple<...T, U> {
  appendTuple(left, right);
}

This violates (2.) though, if the leftmost value is a tuple:

# Good
1 . 2 . 3 . 4 -> (1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

# Also good
1 . (2, 3) . 4 -> (1, (2, 3)) . 4 -> (1, (2, 3), 4)

# Bad
(1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

What I'd like is to get ((1, 2), 3, 4) for the last example. The only way I can think to do this would require constraining the types, which I would like to avoid. Is something like this even possible, in any programming language or type system?

The problem with this is that there is no way to distinguish between (1, 2) and 1 . 2: both have to produce (1, 2). This means that for a left-associative ., 1 . 2 . 3 and (1, 2) . 3 have to produce the same result. (And switching to right-associative . does not help: it has the same issue with 1 . (2, 3).)

Some ways I could think of bypassing this:

The . operator does not directly produce a tuple, instead it produces a wrapper for a tuple. This way, you can distinguish between 1 . 2 and (1, 2). But you also have to include an "unwrap" operation at the end. Though that could be handled by an implicit conversion, which makes the unwrap operation invisible in code.
The . operator looks like it's binary, but it's actually variadic. I.e. (1, 2) . 3 . 4 compiles to operator(.) ((1, 2), 3, 4). Though I don't know of any language that would do something like this.


Generating a random path in a grid without deadlock I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice.

One simple solution would be keep randomly choosing a neighbour of the last cell to add to the path. I found that for small density (i.e. $L < 0.625n^2$), I can repeat this algorithm a large amount (at least $1000$) times and can almost find some complete path without deadlock, i.e. without a a state where the path is incomplete but there is no more move available (i.e. all neighbours of the current cell is already filled). A DFS can lead to a deadlock state, and from my experiments, most of the end states are deadlocks, hence it is very hard to get to a complete state with DFS. But for larger density, it is nearly impossible to avoid deadlock no matter how many times I repeat.

My second attempt is to backtrack one step if the current $i^{th}$ step results in a deadlock (i.e. delete the last action from the list of possible actions at $(i-1)^{th}$ step and randomly choose a remaining action to retry). However it apparently took forever to finish the path (it kept going forward and backward when $i$ reaches $0.625n^2$).

Is there any suggestion for a fast algorithm that have fairly high probability of avoiding deadlocks? I'm fine with pseudo-randomness.

You have a solid grid graph, and want to generate a random Hamiltonian path in it.  The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers.  Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev.  arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.

Other related work that might possibly be of interest:

The following paper proposes an algorithm to count the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs.  Y. H. Harris Kwong, D. G. Rogers.  European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes

Enumeration of tours in Hamiltonian rectangular lattice graphs.  Basil R. Myers.  Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects.  So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find a Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output):

Hamiltonian Cycles in Solid Grid Graphs.  Christopher Umans, William Lenhart.  FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.


Decide $\{a^nb^n\mid n>0\}$ in log space Given $S = \{a^n b^n \mid n > 0\}$, show $S$ is deterministically decidable in log space.

Hint: to count up to $n$ you need $\log n$ bits.

This comes from some lecture notes at https://www.cise.ufl.edu/research/OptimaNetSci/slides/ThangSept20.pdf

but they did not show how to prove it. Any ideas?  (Was posted in wrong section before)

The hint that you have pretty much solves the problem.
Essentially you need two counters; one for a and one for b.

If the first occurrence is not an a, you reject.
Start counting as. You will encounter n of those, until the end of input, or you find a different character. When you stop reading as, at that point you have n in binary. Essentially, every time you read an a, you simply perform addition in the counter that is used for counting as.
If you have reached the end of input, or if the next character is not b, you reject.
Start counting bs in the same manner as you were counting as until you reach the end of input or encounter a different character. You will read at most n bs, by checking every time that you read a b if you have read less than n characters. This is again straightforward because the two counters for a and b are in binary. If you read a different character you reject. If you reach the end of input after n bs, then you accept; otherwise reject (there is another character coming up - might even be a b).

Thus, we need O(log(n)) space.


Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions Assume $X$ and $N$ are two sets of vectors (observations) from a normal distribution, where $X$ represents clean data and $N$ represents noise; and $A$ a projection matrix of a filter. The scenario is that our clean data was corrupted by a multiplicative noise via matrix $A$ and an additive noise of $N$:

$$Y=A X + N.$$

How can we learn the projection matrix $A$ and $N$ from the training data $X,Y$? Does the Gaussian assumption of $A$, $N$ and $X$ help to have a better estimation or guide to use a specific solution?

Here is matlab code for the training data, noise and a simple projection:

    dataVariance = .10;
    noiseVariance = .05;
    mixtureCenters=randn(13,1);
    X=randn(13, 1000)*sqrt(dataVariance ) + repmat(mixtureCenters,1,1000);

    %N and A are unknown and we want to estimate them.
    N=randn(13, 1000)*sqrt(noiseVariance ) + repmat(mixtureCenters,1,1000);
    A=2*eye(13);

    Y=A*X+N;

    for iter=1:1000
        A_hat,N_hat = training(X_hat,X,Y);
    end

Note: if necessary, for each estimation of $A$, an error can be calculated for an estimation of $N$ using a current $A$.

For example:

for iterate=1:1000
  initiate A
  estimate N using current A (N=Y-A*X)
  calculate error of estimation (err=Y-A*X+N)
  update A

But I would prefer not to go for gradient descent approaches.

Your problem is that of multivariate linear regression. Finding each row of $A$ corresponds to a classical linear regression problem, which can be solved using the method of least squares, which is optimal here since the noise is Gaussian.

Once you have an estimate for $A$, you can estimate the parameters of $N$ by isolating $N = Y-AX$. (This is not necessarily the optimal method since you only have an estimate for $A$, but practically it might be good enough.)


Prove that following graph problem is in $L$ I have some interesting problem:

  Prove that following problem is in $L$ (decidable in logarythmic
  time).   Decide if given undirected graph $G=(\{1,\ldots,n\}, E)$ such
  that $\forall_{i,j\in \{1,\ldots,n\}} i\le j \to \operatorname{dist}(1, i) \le \operatorname{dist}(1,j)$.
  Graph is represented as adjacent matrix.

This is exercise that I can't deal with it. I know USTCON problem and I suppose that it may be useful (crucial) here. However, I can't solve it. Can anyone try to  help me defeat it ?

Let $N_k$ be the set of vertices at distance $k$ from 1. A graph satisfies the property if the sets $N_k$ are intervals, and $N_{k-1} < N_k$ (every member of $N_{k-1}$ is smaller than every member of $N_k$). We will check this property inductively: assuming $N_{k-1}$ is known (starting with $N_0 = \{1\}$), we will show how to calculate $N_k$ and verify that it has the correct properties.

Suppose that $N_{k-1} = \{a,\ldots,b\}$. If $b = n$, we can stop. Otherwise, go over all neighbors of the vertices in $N_{k-1}$, and record the minimal and maximal indices $c,d$ encountered among those larger than $b$. Verify that $c = b+1$. Now go over all $e \in \{c,\ldots,d\}$, and verify that it is a neighbor of some vertex in $N_{k-1}$. If so, we have verified that $N_k = \{c,\ldots,d\}$, and can continue with $N_{k+1}$.

You can check that this algorithm can be implemented in logspace.


Sum of sequence complexity I try to find out what is the time complexity of this program:

for (int i =0; i < n; i++)
{
    for (int j = i+1; j < n; j++)
    {
         //Do something O(1)
    }
}

I tried to find any explanation, As I see, it something like Arithmetic progression sum (n(n-1)/2).

Is it? or it's just O(n^2)

The inner loop will iterate once with $j=i+1$, once again with $j=i+2$, and so on, up to the last iteration with $j=n-1$, so there will be, for each $i$ in the outer loop, $(i+1)-(n-1)-1=n+i-1$ time contributions from the inner loop. Add these to get your answer.


If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP? Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, then you should also believe that sound arguments for $P\ne NP$ are lacking. Or are there good arguments for $P\ne NP$ being unlikely, in a similar vein to say, the Riemann hypothesis holding for large numbers, or the very high lower bounds on the number of existing primes with a small distance apart viz. the Twin Prime conjecture?

People are skeptical because:

No proof has come from an expert without having been rescinded shortly thereafter
So much effort has been put into finding a proof, with no success, that it's assumed one will be either substantially complicated, or invent new mathematics for the proof
The "proofs" that arise frequently fail to address hurdles which are known to exist. For example, many claim that 3SAT is not in P, while providing an argument that also applies to 2SAT.

To be clear, the skepticism is of the proofs, not of the result itself.


Group isomorphism to graph ismorphism In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For example, on the stated page it says that graph isomorphism is a more general problem than group isomorphism.

Hence I am posing the following

  Given a group $G$ can someone give a construction of a graph
  $\Gamma(G)$ of size polynomial in $|G|$ such that $$\Gamma(G) \cong
 \Gamma(H) \iff G \cong H$$ for groups $G$ and $H?$

The reduction is described in a classic paper of Miller.


Must a function in lambda-calculus which inputs a boolean function be defined in a certian way? This question is my best attempt to get at a more general question about what one can get from terms in the lambda calculus.

Using the church encoding, we define booleans by
$\texttt{true} = \lambda x,y.x$ and $\texttt{false} = \lambda x,y.y$

Define the set of terms $Bool = \{\texttt{true}, \texttt{false}\}$, and
let $Bool \to Bool = \{g \; | \; \text{if } b \in Bool \text{ then } g \; b \in Bool\}$

Let $f$ be a term with the property that if $g \in Bool \to Bool$ then $f \; g$ normalizes to a boolean.

Intuitively, I believe $f$ can be either a constant function or it can use $g$. Precisely:
Is it true that any such f satisfies one of the following properties:

There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = b $
There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = g \; b $
There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = not (g \; b) $
EDIT: as Derik points out, the above three cases only capture 6 of the 16 set-theoretic functions of type (Bool -> Bool) -> Bool. The point was can $f$ be defined in a way other than those set theoretic ones.

(where $a = b$ means that $a$ normalizes to $b$)

If we assume that $g$ normalizes when applied to any Boolean input, then we can apply it to true and false, and then we can can compute any Boolean function of those two values. That is, we can readily produce all $16$ possible set theoretic functions, $2^{2^2}$. Your schemas only cover $6$ of those.

But the story goes further, your definition of $f\in(Bool\to Bool)\to Bool$ does not require that $f$ only apply its argument to Booleans. Similarly, $g\in Bool\to Bool$ does not restrict $g$'s behavior for all other inputs. At this point, there are all kinds of additional possibilities (even when restricting to $Bool\to Bool$ inputs) where $f$ applies its argument to other things and performs some other calculation to ultimately produce a Boolean. So there are many other potential terms. If you want tighter guarantees, you may want to consider looking at typed lambda calculi.

(As a tangent, but an interesting tangent, is the class of sequentially realizable functionals. These include functions which are mathematical functions but which aren't implementable in a "pure" way, i.e. they require things like exceptions or mutable state to be implemented.)


Big-O complexity of finding exception handler for zero-cost exceptions I am wondering what the time complexity of finding the most appropriate exception handler for dispatching zero-cost exceptions is.

For zero-cost (this refers to execution under the assumption that no exceptoins occur) exception dispatching, the compiler stores a big table of all possible exceptions. An entry consists of Type, Handler, start+end of the try-block.

Then one can find the most appropriate handler by

taking those with a try-block enclosing the address where the exception occured
then of those, choosing the most specific type
if one is found: done, else: move up the callstack

Naively I would say: O(callstacksize * sizeoftable).

But we have to be able to do better. I looks to me the callstacksize factor wont go away, but what about the sizeoftable factor?

There should be more performing way to search through the handlers. What is the best we can do O-notation-wise?

The crucial data structure here is an interval tree, that can be pre-computed at compile time, which has a complexity of $O(\log n + k)$ to find all $k$ ranges that contain a certain point, assuming there are a total of $n$ ranges. Here your ranges are exception blocks in the compiled code and your point is the instruction address.

I will assume the C++ model of one try block followed by one or more catch blocks that may or may not match a thrown exception and I will assume that a compiled program has $n$ try blocks in total.

Then when an exception is thrown it takes $\log n$ time to find the $k$ relevant try blocks in the current call frame (which we order by specificity, which is done by minimizing range size). And for each relevant try block there may be one or more relevant catch block, which may or may not match. If none match we go to our caller and search again.

But at some point we find a matching exception (or halt). The total complexity then is $O(c\log n + k)$, where $c$ is the number of calling frames we had to go up, and $k$ is the total number of relevant catch blocks that we considered for matching.

This is assuming that you do exception type matching at runtime, instead of maintaining separate tables per exception type. Since $k$ is generally very small, this is a sensible approach. You can get better asymptotic runtimes in terms of $k$, but I described a practical approach.


What makes a metaheuristic meta? According to Wikipedia:

  ...metaheuristic is a higher-level procedure or heuristic designed to
  find, generate, or select a lower-level procedure or heuristic
  (partial search algorithm) that may provide a sufficiently good
  solution to an optimization problem...

So a metaheuristic is something like a shaman (master algorithm), who tries to heal a person (solve a mathematical problem) by mixing various spells and herbs (simple heuristics). But why is Evolutionary computation considered a metaheuristic, instead of a simple heuristic:

https://en.wikipedia.org/wiki/Metaheuristic#/media/File:Metaheuristics_classification.svg

What are the simple heuristics that evolutionary computation is composed of? Is it the crossover, mutation, fitness based selection? Are these the simple heuristics?

Also related: Difference between heuristic and approximation algorithm?

The distinguishing factor is that meta-heuristics are problem independent.

Look at something like Travelling Salesman. You have 2-OPT, 3-OPT, Nearest Neighbour heuristics. These are all things that really don't carry much meaning outside the specific problem of Travelling Salesman.

A Meta-heuristic, on the other hand, assumes no prior knowledge of the problem. It's not saying "this is something that's likely to produce a good solution to our problem," it's saying that "this is something that is likely to produce good search results in general."

For TSP, the heuristic is that similar solutions will have correlated fitness values. More precicely, the simple heuristic is that, given your current population, the best solutions will look similar to the best ones in your population.

This is where "meta" comes in. Your population is always evolving, which means your heuristic is evolving as your search continues.

When I learned about metaheuristics, they talked less about pure GAs and more about combined techniques, things like Genetic Local Search or Probabilistic Model-based GAs. For PMBAs, it's easier to see the heuristic evolving: you choose some probabilistic model (such as Baysean networks) modelling correlations between input bits and fitness. You search, but the heuristic for which nodes you look at next isn't something static determined beforehand, it's dynamic, based on your probability model. The model keeps evolving, which means the search keeps evolving.

The slides from the class I took are here, you might find them interesting.


Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$ I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.
$T(n)= 5T(n/4) + n^2$
Guess: $T(n) = O(n^2)$
Prove: $T(n) \leq cn^2 $
Breakdown
$ T(n) \leq 5(c(n/4)^2) + n^2 $
$ = (5/16)cn^2 + n^2 $
$ \leq cn^2 $
For the last step to hold I'm not sure what the value of c should be because of the (5/16). My guess would be c >= 1 and I'm not sure if that would hold.

Your constant $c$ needs to satisfy
$$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$
that is,
$$ \frac{5}{16} c + 1 \leq c. $$
Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.


Complement of $a^n b^n c^n$ I am trying to find the complement of the language $L = \{ a^n b^n c^n \mid n \ge 0\}$.

I know that one of the things I gotta do is take out $n \ge 0$ so $\{a^n b^n c^n \mid n > 0\}$ but I feel there is not enough.Is making it so $a^i b^j c^k$ so that $i \neq j \neq k$ enough and make it so that $i,j,k > 0$?

Or am I completely off track?

The complement is the set of all strings over alphabet $\{a,b,c\}$ that are not of the form $a^i b^i c^i$ for some $i\geq 0$.  That includes all strings $a^ib^jc^k$ where $i\neq j$, $i\neq k$ and/or $j\neq k$, as you say, but also some other strings.  Mouse-over the box below for a hint.

   For example, $bacbabc$ is in the complement.


Find the subset of k element between n that maximize the total distance Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm.

$$S_{max} = \arg \max_S\sum_{i,j \in S, i \ne j} d(x_i,x_j)$$

In my specific case, $Q\subset \{ 0, 1 \} ^m $, thus  $d(\cdot,\cdot)$ is equal to the Hamming distance.

Is there any efficient way to solve this problem? Is it possible to rewrite it in another simpler way?

This problem smells like it might be NP-hard, though I have no proof.  If you are looking for a proof of NP-hardness, my advice would be to go through Garey & Johnson (or some other list of NP-complete problems) and look for all problems that seem plausibly related: e.g., ones that involve the hypercube, bitvectors and the Hamming distance, clustering in general metric spaces, or total/average distance in some general metric space.  Then, edit your question to list all of those known-NP-complete and plausibly-related problems in your question... and try to see if you can find a reduction from any of them to your problem.

If you are less concerned about theoretical results and instead are looking to solve this in practice as efficiently as possible, some of the techniques in Maximize distance between k nodes in a graph can be adapted to your problem.  In particular, I'll suggest two candidate approaches: if you want an exact solution, try using ILP; if you want an approximate solution, try FPF.

You can formulate your problem as an instance of integer linear programming (ILP).  Introduce variables $y_i$, where $y_i$ indicates whether the $i$th point $x_i$ is included in $S_{max}$, and $z_{i,j}$, with the intended meaning that $z_{i,j} = y_i \land y_j$.  Constrain each of these to be zero-or-one integer variables.  Add the constraints $\sum_i y_i \le k$ and $z_{i,j} \le y_i$ and $z_{i,j} \le y_j$ and $z_{i,j}=z_{j,i}$.  Your goal is to maximize the objective function

$$\sum_{i,j} d(x_i,x_j) z_{i,j}.$$

You can optionally add the extra constraints $y_i+y_j-1 \le z_{i,j}$ and/or $z_{i,j}+z_{j,k}-1 \le z_{i,k}$ and/or $\sum z_{i,j} \le k(k-1)$; this will increase the number of constraints, but might help the solver find a solution more quickly.  Now give this ILP instance to an off-the-shelf ILP solver, and hope that it can find a solution efficiently.

If you want a fast heuristic to find an approximate solution, you could try using FPF, as described here.  You could also try a greedy algorithm: at the $i$th iteration, select the vertex $x_j$ that increases the total distance of all the vertices selected so far by as much as possible.  Neither of these is guaranteed to find an optimal solution, and the solution they output probably won't be optimal, but if you're lucky, they might be not-too-much-worse than optimal.


Travelling Salesman Problem Easy Algorithms I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript).
Unluckily all of the ones i found are really hard to understand/ to implement.

The ones i already have are the nearest/farthest-neighbour-algorithms. Do you guys have any other suggestions?

It is an extremely hard problem to solve. But some reasonable heuristics are easy to explain/code.

One is to start at a random vertex, each step move to the vertex that hasn't been visited yet that is closest. Rinse and repeat.

Another is to start with a minimal spanning tree of the graph, pick any vertex as starting point (root), and visit the vertices in preorder. If you are asked to visit a vertex that you already visited, just skip it for the next one in preorder. Think about it as walking along the "outside" of the tree, taking shortcuts to the next when asked to visit a vertex again. This works rather well if the distances have the triangular property (i.e., $c(u v) \le c(u x) + c(x v)$ for all vertices).

See if you can come up with another idea.


All prefixes with same length as their suffix is a regular language Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking the set of even length strings over $\Sigma^*$ (given by $(00\cup01\cup10\cup11)^*$) and then interescting with $L$, which would be regular because the intersection of regular languages is regular. Then, the set of prefixes of this language is regular (by a previous exercise), but that's useless because that set of strings isn't actually the set $\frac{1}{2}L$. In particular, we didn't constrain the prefixes to be the ones with equal length suffixes.
Baically, I'm really stuck on how to make a FA that recognizes the length of the strings. Namely, given $x$ how do we add $\epsilon$ transitions to arrive at $xy$ with $|x| = |y|$, which we then pass in $xy$ to the FA for $L$? Thanks in advance, I've been scratching my head on this for a while.

Given a DFA $A$ for $L$, construct an NFA which operates as follows:

The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
The NFA will maintain two states, $q_1,q_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ (which corresponds to a symbol in $y$), and advance $q_1$ using $\sigma$ and $q_2$ using $\tau$.
The NFA is at an accepting case if $q_1 = q$ and $q_2$ is an accepting state of $A$.


Box representation in modern languages I'm studying value representation in modern languages. The idea is that since in many situations the size of objects can be unknown, one can introduce a box representation of it. This box representation is just a block stored at the heap with a tag to identify it.

My questions is as follows: who deals with the size of the block? who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it. But then what is done in compile time? How does a compiler represent objects at compile time?

I'm not sure I completely understand your questions. Still:

  who deals with the size of the block?

If the compiler does not know the size, it can write the size at the very beginning the block, after (or before) the tag. Some convention must be established -- this is something that must be decided when designing the runtime system.

  who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it.

If the type is known by the compiler, the compiler can emit code to put the right tag. Otherwise, the compiler must emit code which will compute the tag at runtime, e.g. fetching it from some other block, and store it at the start of the block.

  But then what is done in compile time? How does a compiler represent objects at compile time?

It does not have to. A compiler must emit target code which, at runtime, will deal with the tags.

Further, note that tags are not always needed. If the language is (statically) typed, the compiler might know the size and type of everything, hence there would be no need to store tags at runtime.


Prove vertices of polygon are endpoints of disjoint line segments If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the endpoints of the segments and every segment is an edge on the boundary of the polygon.

Here is a simple counter example :

You most join the two leftmost vertices to the two middle vertices, and both ways to do that don't work.


NP-complete problem of partitioning into several sets with a Hamiltonian cycle How to prove the $NP$-completeness of the language $L$ = $\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so,
that all the corresponding induced subgraphs have a Hamiltonian cycle}.
I had no problems how to prove that this language is in the $NP$, but it is not clear to me how to prove that this language is in the $NP-hard$ class.

You can map any $\text{HamiltonianCycle}$ instance $G$ to an $L$-instance $(G, 1)$, yielding a polynomial time reduction from an $\mathsf{NP}$-complete problem to $L$ which implies the $\mathsf{NP}$-hardness of $L$.


Complexity of self-reducible set I am trying to solve the following problem:

  A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\right| < \left|x\right|$, $\left|r(x)\right| < |x|$, and $l$ and $r$ are both deterministic polynomial time computable functions.  What is the maximum possible complexity of a self-reducible set (you can choose $l$ and $r$)? For your complexity estimate, prove upper and lower bounds.

Now, I think $S \in P$, because to decide if $x \in S$, we can simply iterate $l$ and $r$ until they both get to $1$ or not, and since the length must decrease each time, the time taken will be polynomial in the length of $x$.  Is this correct?

Also, what could the problem mean by a lower bound? By defining $l$ and $r$ to be $1$, we get $\Sigma^*$, the set of all strings, which is regular...

Suppose for simplicity that $|l(x)| = |r(x)| = |x|-1$. If $L(n),R(n)$ are the time complexities for computing $l,r$ on inputs of length $n$, then the time complexity for computing membership in $S$ satisfies the recurrence
$$ T(n) \geq L(n) + R(n) + 2T(n-1). $$
Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.

If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c < 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).

So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.


Measuring and maintaining the diversity of individuals in Genetic Algorithm While I was using the Genetic Algorithm to generate full correct Sudoku grids starting from a population of random grids, I occasionally face the problem of the process being stuck on a local maxima until the population loses its diversity.

So, I decided to find a mechanism for maintaining the diversity of the population to avoid the problem. What I thought about was:

Measuring the diversity of each individual by computing how different it is from the rest of the population:

For each individual $i$ : $$diversity_i = \sum_j distance(i, j)$$ and I used the hamming distance as the $distance$ function.
Ranking the individuals (for selection) based on both their diversity and their fitness.

I faced two problem with this approach:

Computing the diversity this way is expensive as it requires $n^2$ call to the $distance$ function (which is itself not a constant time function), raising the following question: what is a relatively optimal way for measuring the diversity of a population?
How to rank the individuals of a population based on both diversity and fitness?

How to rank the individuals of a population based on both diversity and fitness?

You can combine diversity and fitness into a single score: $$score(i) = fitness(i) + k \cdot diversity(i)$$

It's a standard approach and doesn't require significant changes to the algorithm. Unfortunately $k$ is problem-specific.

Alternatively change the standard GA to a multi-objective evolutionary  algorithm (MOEA).

This needs a lot of changes (e.g. the algorithm now needs to maintain a set of Pareto optimal individuals).

MOEA is probably a overkill for what you're doing. Indeed it's very interesting and a good training.

  Computing the diversity this way is expensive... What is a relatively optimal way for measuring the diversity of a population?

The genotypic / structural approach to diversity isn't the only workable one.

Instead of measuring how differently the individuals look like, measure how  differently those individuals behave (phenotypic diversity).

A great advantage is the ease of computation: often an acceptable approximation is the simple fitness value.

Schemes like Fitness Uniform Selection / Fitness Uniform Optimization generate selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness:

Evolution of the population under FUSS versus standard selection schemes (STD): STD may get stuck in a local optimum if all unfit individuals were eliminated too quickly. In FUSS, all fitness levels remain occupied
with “free” drift within and in-between fitness levels, from which new mutants are steadily created, occasionally leading to further evolution in a more promising direction (from "Fitness Uniform Optimization" - Marcus Hutter & Shane Legg).


How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus? How do we show $$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$$?

I was going through the slides here  and it asked to do the above but by page 16 of the slides we have not defined what lambda applications are suppose to be. Thus is remained complete unclear because I don't know what the syntax:

$$\lambda x . x (\lambda y .y)$$

means. Can someone clarify to me how to proof this rigurously using alpha-conversion et al?

i.e. without using $\beta$ equivalence which is the application rule I assume.

The two terms are in the same $\alpha$-equivalence class.
In lamba calculus, we can rename bound symbols without changing the meaning of the term.
$\lambda x.x$ and $\lambda y.y$ both mean "a function that takes one input and returns it". A variable is bound by the first matching lambda above it in the term-tree.
We often $\alpha$-rename bound variables before $\beta$-reduction to make sure unbound variables do not get caputured after the reduction step.

To answer your question:

$$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda x.x (\lambda x'.x')$$ (rename bound $y$)
$$\equiv_{\alpha} \lambda y.y (\lambda x'.x')$$ (rename bound $x$)
$$\equiv_{\alpha} \lambda y.y (\lambda x.x)$$ (rename bound $x'$)
This gives us $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x.x)$


Fitness functions for low-dimensional parts of cooperative coevolution algorithms In cooperative coevolution algorithms, a high dimensional vector is broken into smaller vectors, each of which is optimized separately using EAs for fewer dimensions and then recombined.

What is the fitness function used to optimize those?
It can't be the same benchmark function, as those are for higher dimensions.

I am specifically talking with respect to the algorithm DECC-G ("Large Scale Evolutionary Optimization Using Cooperative Coevolution" by Z. Yang, K. Tang, X. Yao). What is the fitness function used to optimize subpop in SaNSDE and wpop in DE?

Every sub-vector is evaluated by concatenating it with the best-fit individuals (sub-vectors) from the rest of the sub-populations to form a so called context vector.

The context vector contains all the parameters required by the benchmark function and is fed into it for fitness evaluation.

This is actually where the cooperation happens.

DECC-G is "just" a cooperative co-evolutionary (CC) scheme based on Differential Evolution (DE) and a random split/grouping of the vectors/individuals (-G).

It shares with the other co-evolutionary algorithms the general architecture:

(Coevolutionary model of three species shown from the perspective of each in turn. Image from Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents by Mitchell A. Potter, Kenneth A. De Jong)

As a side note the reference implementation of DECC-G can be found here.


Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1 So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be selected etc.

I can think of a DP algorithm to solve that which takes $O(nk)$ time (I don't think that I need to describe it, it's fairly easy to think). But I don't know if binary search can be used to find the answer more efficiently.

This may sound like a weird problem but it's part of a DP algorithm I'm trying to figure out and so the complexity will be multiplied with $kn$ so it would be great if I found a solution with $O(k)$ complexity.

A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \epsilon})$-algorithm is known.

For this we'll use the result that MAXCONV can be solved in $\mathcal{O}(n^{2 - \epsilon})$ iff MAXCONV UPPERBOUND can be solved in $\mathcal{O}(n^{2 - \epsilon})$ (reference: "On Problems Equivalent to (min,+)-Convolution", ICALP 2017)

To show this, first note that we may drop the requirement that the arrays are sorted. To show this, take arbitrary values $b_{i}[j]$, set $V = 2 \max_{i, j} |b_{i}[j]|$, and set $a_{i}[j] = b_{i}[j] + Vj$. Now $a_{i}[j+1] - a_{i}[j] = b_{i}[j+1] - b_{i}[j] + V \geq 0 \geq 0$, and the answer for $a$s is exactly $(k+1)V$ more than the answer for $b$s.

In a MAXCONV UPPERBOUND instance $(a[i])_{i = 0}^{n-1}, (b[i])_{i = 0}^{n-1}, (c[i])_{i = 0}^{n-1}$ we are asked if for all $k$ we have $\max_{i+j = k} a[i] + b[j] \leq c[k]$. To reduce it to our problem, set $a_{1}[j+1] = a[j]$, $a_{2}[j+1] = b[j]$ and $a_{3}[j] = -c[n-j]$. Further set $a_{1}[n+1] = a_{2}[n+1] = a_{3}[n+1] = -\infty$. Now the answer is positive if and only if at least one of the upper bounds doesn't hold: if the answer is positive, then $a_{1}[x] + a_{2}[y] + a_{3}[z] > 0$ for some $x + y + z = n+2$, hence $a[x-1] + b[y-1] > c[(x-1)+(y-1)]$ and the upper bound for $k = x+y-2$ doesn't hold. Similarly if $a[i] + b[j] > c[i+j]$, we have $a_{1}[i+1] + a_{2}[j+1] + a_{3}[n+2 - (i+1) - (j+1)] = a[i] + b[j] - c[i+j] > 0$.