How to sample random game input that looks similar to human control? What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this seems really pointless, the computer managed to beat the game that way.

However in this project, buttons are pressed at random, so the behaviour of the character is very far from what you would expect from a human player.
What I would like to do is to be able to produce a series of inputs that 'look like' one produced by a human player.

A good way to do that may be to record a sequence of inputs as played by a human player, use this data in order to produce a Markov Chain.

However I think a human player may exhibit a behaviour that is not easily taken into account by a Markov Chain. For example in order to double jump, it is generally a bad idea to have the second jump right after the first. So a typical sequence of inputs would look something like this (where f=forward and j=jump)
f-f-f-j-f-f-f-f-f-f-f-f-f-j-f-f-f

This sequence of inputs may be common when the game is played by a human, but in order to have a Markov Chain produce such a sequence of inputs, it means that the states have to correspond to sequences of inputs of length (at least) 10, hence a huge state diagram.

Is there an alternative to (or a variation of) Markov chains that can take this kind of behaviour into account?

NB: English is my 2nd language so I apologize if this question is poorly worded...

A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many different internal states you need, and then you can learn the model from the data.

If you want to model a bunch of different things inside the hidden state (running/not running, has weapon/doesn't have weapon, ...) you can switch to some kind of recurrent neural net (e.g. LSTM)


Can a regular expression be any string from the language described by it? Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?

Your question is unclear. However "a language (that has strings of infinite length)" cannot exist. By definition a language only contains words of finite length.
Let $\Sigma$ be a (finite) alphabet and $\epsilon$ denote the empty word.
A language is a subset of $\Sigma^*$, where $\Sigma^*$ is defined as $\Sigma^* = \cup_{i=1}^{\infty} \Sigma^i$, $\Sigma^0 = \{ \epsilon \}$, and $\Sigma^i = \{xy : x \in \Sigma^{i-1}, y \in \Sigma\}$ for $i>0$.
As you can see, a string of infinite length does not belong to any $\Sigma^i$ and therefore it belongs to neither $\Sigma^*$ nor to any of its subsets.


Computing with number of stack items For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete?

Is it enough to be able to access just the top-most item? Two items? Three? Any item?

In the case of Forth, is it necessary to have rot, pick, roll? Why does rot operates with exactly top three items?

It depends on what kinds of things you can store on the stack.

If each item on the stack is of unbounded size, you can simulate a two-counter machine, which is Turing-complete.  Therefore, in this case, you can achieve Turing-completeness with just the ability to access the top two items on the stack.

If items are bounded-size, restricting to access a bounded number of top-most items of the stack gives something equivalent in power to a PDA.  (For instance, suppose all you can do is access the top 5 items of the stack, and use that together with a finite control to transition to a new state of the finite control and either push/pop.  Then grouping the items into 5-tuples, we can build an equivalent machine where you only need to access the topmost item.  That machine is a PDA.)  Therefore, in this case, it's not Turing complete with access to any finite number of items at the top of the stack.


What does the phrase "Simple For Loops" mean in computability theory? I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?

The Phrase:
An upper bound of the number of iterations of every loop can be determined before entering the loop

The Wikipedia page

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:

x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x

This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time.

A better explanation is the LOOP programming languages. Every loop in LOOP runs $x_i$ times, where $x_i$ is a variable, and the number of iterations is the value of $x_i$ before the loop is run. For example:

  LOOP x DO
      x ← x + 1
  END

is a problem that doubles $x$, and

  z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END

is a problem that assigns $x + y$ to $z$.

A function can be computed in LOOP (using a reasonable input/output convention) iff it is primitive recursive. So if you only allow loops in which the number of iterations is the value of some variable just before the loop, then the resulting function will be primitive recursive, and furthermore, every primitive recursive function can be computed only using such loops.


Longest path in a directed acyclic graph with constraints Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'.

What is the complexity of this problem?

You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$.

If $|E_i\setminus D'| = 0$ then:
$$
d[v_i][0] = 0
$$

otherwise:
$$
d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\in D'})\\
$$

If $|E_i| = 0$ then:
$$d[v_i][1] = -\infty$$
otherwise:
$$d[v_i][1] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \in D'}, d[v_j][1]_{(v_j, v_i) \not\in D'})
$$

It's easy to see that $d[v_i][0]$ is equal to length of longest path ending in $v_i$ without edges from $D'$ and $d[v_i][1]$ is equal to length of longest path ending in $v_i$ with exactly one edge from from $D'$. After that you need to find largest of $d[v_i][1]$. You can also store the id of the node for which we found the maximal value during dynamic programming to recreate the path.


If a DFA can be simulated by a real program, can it be simulated by a TM In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says that the $\mathsf{DFA}$ can be simulated by some $\mathsf{TM}$? Could a program be used in place of a $\mathsf{TM}$ in a proof of decidability?

I know that Java being Turing-complete would mean that it can simulate any $\mathsf{TM}$, so this is sort of the reverse of Turing-completeness I guess.

Assuming the same limited view on computation as Turing machines, then yes: typical programming languages are Turing complete and thus (for all we know) equivalent in power to TMs.

A simpler proof presents itself, too: if you look closely enough, finite automata are just Turing machines that don't use their tape.

Keep in mind, though, that Turing machines lack some features of modern real machines/languages: distributed computation (i.e. communication), user interaction, online algorithms and never terminating systems with continuous I/O (e.g. operating systems) are just some examples. If your simulation program uses such features, the simulation may not carry over to TMs.


Should check all $2^n$ possibilities in array? Suppose I have an array of numbers, and a function boolean isPrime(int n) that I'm allowed to use.

Boolean isPrime(int n) receives a number n and return true if the received number is a prime and false otherwise.

I need to write a function int foo(int[] a) that receives the given array and return the biggest prime number that I can "create" by adding values from the given array.

For example: for the array 8,11,8,2 the function foo should return 19

It's not a homework or something, I noticed that in a lot of job exams there is this type of question. It looks simple and naïve, but it's not.

There are a lot of possibles, for array with size $n$ the are $2^n$ possible combinations.
In the given example the possibilities are:$\{8,11,2,8+11,8+8,8+2,8+11+8,\dots\}$

What's the best way to approach this type of question? I'm sure that it's related to some smart algorithm.

The query complexity of your problem, which is the number of oracle calls that any correct algorithm needs to make, is $2^n-1$ (or even $2^n$, if the oracle is allowed to return "No" on all inputs, in which case the answer to your problem is "Infeasible"). This assumes your oracle is a black box. When your oracle is given explicitly, the complexity of the problem could depend on the oracle. For the primality oracle, your problem is likely hard, but this could be challenging to prove since the additive properties of primes are not well-understood.

Indeed, suppose that you have an algorithm solving your problem on arrays of length $n$ using less than $2^n-1$ oracle calls in the worst case. Run it on the array $1,2,4,\ldots,2^{n-1}$. Whenever the oracle asks a question, always return "No" (i.e., cannot be used). When the algorithm has finished, there are at least two sets $S,T$ that have not been queried. There we can consider two oracles, one that says "Yes" only on $\Sigma(S)$ (the sum of elements in $S$) and the other that says "Yes" only on $\Sigma(T)$. By construction, $\Sigma(S) \neq \Sigma(T)$, and so the correct answer is different in both cases. However, the algorithm cannot distinguish between the two oracles, and so its output will be wrong for at least one of these two oracles.

If we allow the oracle to return "No" on all inputs, then we can get a contradiction even given an algorithm that makes exactly $2^n-1$ oracle calls in the worst case. Running it on the same array and answering every query negatively, there is always a set $S$ which has not been queried, and the algorithm cannot distinguish between the oracle which answers "Yes" only on $S$ (in which case the answer is $S$) and the oracle which always answers "No" (in which case the answer is "Infeasible").


How to convert a decimal number to ASCII representation The question that was in my lecture notes said

    "Encode the decimal number 2370  in ASCII. "

and the answer given there is

    32 33 37 30 (ASCII code representation)

My question is how do we get this? Do we simply add 30 to each digit? I am sorry if this is a very obvious question I do not know the correct way to look up the ASCII table for conversions. Any help would be appreciated.

PS: This is not my homework, my course finished today morning. Just asking out of curiosity.

The ASCII encodings for digits 0 to 9 are 48 to 57 in decimal, or 30 to 39 in hexadecimal.


How to prove {a^(n^2) | n>0} is not context-free? So I have a language:
$$
L = \{a^{n^2} \mid n > 0\}
$$
I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.]

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|>0$ and $|vxy|=t\le p$. Hence, we'll have
$$
0 < |vy|=t\le p
$$
This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have
$$
p^2<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p
$$
Choosing $i=2$ gives us
$$
p^2<|uv^2xy^2z|\le p^2+p
$$
Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.

This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.


Is the clique problem NP-complete also on bipartite or planar graphs? We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?

In a bipartite graph there can be no clique of size three. Not much of a problem that is left I guess?

(edit) Sorry, that was too fast, I realize thanks to comment by Nicholas below. To make up for it I googled a reference.

The maximum edge biclique problem is NP-complete by Ren*e Peeters. Discrete Applied Mathematics 131 (2003) 651 – 654

(ps) So I understand that my answer relates to a question that changes the types of graphs we are looking for, kind of bipartite cliques, whereas the other answer restricts the set of graphs we are looking in to planar. In planar graphs cliques can have size at most four, thanks to Kuratowski.


Solving diophantine equations -- does having a bound on the size of the solution help? Let's define the following languages over the alphabet $\Sigma=\{0,1\}$:

H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, i.e. there exists a root/solution in $\Bbb{Z}^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

RH10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, each integer in the closed interval $[-2^n,2^n]$ or in other words there exists a root/solution in $[-2^n,2^n]^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

If RH10 can be solved in deterministic polynomial time, does this imply that H10 is decidable?  If there is a polynomial-time algorithm for RH10, then it can't be enumerating all possible solutions in $[-2^n,2^n]^n$ (there are too many of them to try in polynomial time), so it seems like it must somehow find solutions regardless of how large they are, and thus also be able to solve H10 too.  Is that right? Does it follow from this that $P$ is unequal to $NP$, as H10 is known to be, in fact, undecidable?

No.

If I follow you correctly, your argument is that if P=NP, then $\mathrm{RH}10\in \mathrm{P}$ and the same procedure would be a valid algorithm for $\mathrm{H}10$, which contradicts with the fact that $\mathrm{H}10$ is undecidable.

The step that lacks proof is the claim that the implication:

  if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

To see that this claim doesn't follow, consider what a polynomial algorithm to solve $\mathrm{RH}10$ could be doing. We only know it lies in P somehow, so let's assume it runs in $O(n^k)$ time for some $k\in\mathbb{N}$. Let $l$ be such that we can verify whether a value is a solution for a Diophantine equation with $n$ variables in $O(n^l)$ time.

It is possible that this is done by the following algorithm $A$, given an instance $I$ of $\mathrm{RH}10$:

Identify a set $S\subseteq [-2^n,2^n]^n$ of size $O(n^{k-l})$ in $O(n^k)$ time such that $s$ is a solution to the Diophantine equation encoded in $I$ if and only if $s\in S$.
Iterate over all elements in $s\in S$ and test whether it is a solution of $I$. If a solution is found, report that $I$ has a solution, otherwise report it has not.

Observe that this is a valid algorithm to solve $\mathrm{RH}10$ in $O(n^k)$ if and only if there exist a procedure to carry out step 1. We don't know whether this is true, it is unlikely, but we don't know so it is at least possible.

Now, does the existence of algorithm $A$ give us a procedure to decide $\mathrm{H}10$? No. Algorithm $A$ requires that the solution values are restricted to some finite subset of $\mathbb{Z}^n$ to work. This is true even if we only use step 1. I hope it is clear that the existence of algorithm $A$ brings us no closer to deciding $\mathrm{H}10$.

Therefore, it is clear that the claim that

  if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

is not motivated, as the possibility of the existence of algorithm $A$ is not dis-proven, while we have seen that the existence of algorithm $A$ contradicts your claim.


Efficiently computing or approximating the VC-dimension of a neural network My goal is to solve the following problem, which I have described by its input and output:
Input:
A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$).
Output:
The VC-dimension (or an approximation of it) for the neural network with topology $G$.
More specifics:

Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
The learning algorithm is fixed (say backward-propagation).
The $n$ source nodes are the input neurons and can only take strings from $\{-1,1\}^n$ as input.
The sink node is the output unit. It outputs a real value from $[-1,1]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

Question
Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?
Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?
Notes
I asked a similar question on stats.SE but it generated no interest.

If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.

It's not strictly an answer to your question, but it might help you on the way. The result is due to Baum and Haussler (1989).


How to position images within a canvas while avoiding overlapping I have a canvas. On this canvas, I want to position 1, 2 or 3 images.  The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left corner.  To make sure that the images do not leave the canvas, I am doing this:
image_topLeft_x_position = random.randint(0, (canvas_width - logo_width))

image_topLeft_y_position = random.randint(0, (canvas_height - logo_height))

I can save these locations in a list of tuples like this:
locations = [(image_topLeft_x_position, image_topLeft_y_position)]

After saving a location, I want to generate new locations within the canvas that don't overlap with the previous ones.  However, I've been stuck on this problem for well over a day. Any help is appreciated.

If there is a place for the new image to fit, there must be a place where the left edge of the new image is aligned with either the left edge of the canvas or of some previous image. The same true for the top edge of the new image.  So, if you've already placed 2 images, you only have to try 3 possibilities for the left edge and 3 possibilities for the top edge, or a total of 9 candidate positions in total.  Given a candidate position, you should be easily able to test whether a new image can be placed there without overlapping any prior image.


Minimal number of states for an NFA of all different words Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.
Also, for me $k$ is a known constant. So the language ìs regular (at most $(2^k)\cdot (2^k-1)$ words).
I want to build the most efficient NFA for $L$. So far, I have been able to cone up with an NFA of $O(k^2)$ states, but I want to find one with $O(k)$ states. Of course one could argue that as $k$ is constant, its the same as $O(1)$, but assuming $k$ is a constant parameter - that is, given a value of $k$, I construct $L$ and an NFA for $L$ with $O(k)$ states.
My idea to use $k^2$ states:

A path for each index, as $u$ and $v$ of size $k$... they differ means there is at least one $1\leq i \leq k$ where they differ at that character.
Read '0' in $i$th character and '1' in $i+k+1$th character (due to '@'). Or other way.
In between make sure that $u$s length and $v$s length is $k$. Which characters you read in between? I don't care.

But this will give me around $2k$ states (I can do a bit less, but still $O(k)$) for each index. Total $O(k^2)$, as there are $k$ indices.
I would ask for a way to improve my idea, to use $O(k)$ states. Or maybe a totally different approach.

Here is a matching $\Omega(k^2)$ lower bound.
Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:

There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
There is some word $z$ such that starting at $q$, after reading $z$ the NFA could be at an accepting state.

Since all words in $L$ have the same length, the sets $Q_i$ must be disjoint.
Now let $i \in \{0,\ldots,k\}$. For every word $w \in \{0,1\}^i$, let $Q_i(w) \subseteq Q_i$ be the set of states that the NFA could be in after reading $w$. I claim that if $w_1 \neq w_2$ then $Q_i(w_1) \neq Q_i(w_2)$. Indeed, the NFA behaves differently after reading $w_1$ and $w_2$: it accepts $w_1 0^{k-i} @ w_2 0^{k-i}$ but rejects $w_2 0^{k-i} @ w_2 0^{k-i}$. It follows that $2^{|Q_i|} \geq 2^i$, and so $|Q_i| \geq i$. Therefore the NFA has at least
$$ \sum_{i=0}^k i = \Omega(k^2) $$
many states.


Simple graph canonization algorithm I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if they are isomorphic.

In particular, I'm looking for a simple algorithm that is easy to implement with a reasonable performance on most graphs (worst case super-polynomial, of course). I'm expecting small graphs, so performance doesn't have to be stellar, just good enough.

Unfortunately, most things I've found are highly complex and more interested in expressing deep mathematical connections than simply describing the algorithm. I'm afraid I don't have the time to dive that deep. Can anyone give me a shortcut?

I'm hoping for something like the Floyd-Warshall algorithm. Not optimal, but good enough, and easy to implement.

Brendan McKay and Adolfo Piperno have written a survey paper regarding this question in 2013. They present several efficient computer programs that canonicalize many graphs faster than you would imagine. There is no need (and no point) in implementing these algorithms yourself - they are available online, even as source code.


Doubt regarding cache hit ratios and access time Question 1: What is the average access time for a 3-level memory system with access time $T_1$, $2T_1$ and $3T_1$? (Hit ratio $h_1$ = $h_2$ = 0.9)

The solution given is: $0.9[T_1] + 0.1(0.9[2*T_1] + 0.1[3*T_1]) = 1.11[T_1]$  (Method 1)

Here, they have considered the page won't be copied to the lower level. Otherwise, it would have been like the following

If a page is not there in cache, it would be copied from main memory to cache and then accessed. $T_1 + 2T_1$

If a page is not there even in main memory, it would be brought to main memory, then cache and then accessed. $T_1 + 2T_1 + 3T_1$

$0.9[T_1] + 0.1(0.9[T_1+2*T_1] + 0.1[T_1 + 2*T_2 + 3*T_1]) = 1.23[T_1]$  (Method 2)

I went through another similar problem.

Question 2

Cache Access Time = 20ns
Memory Access Time = 120ns
Hit Ratio = 0.8
Some other useless information below...
Cache Block size = 16 words
Set size = 2 blocks
Number of sets = 128
Size of main memory address = 21bits
What is the hit ratio if the average access time is increased by 40ns?
(A) Remains same      (B) 0.921     (C) 0.467      (D) 0.592

I simply calculated it using Method 1 as follows

Effective access time = 0.8*20 + 0.2*(120) = 40ns
Increase by 40ns, so new time = 80ns
80 = h*20 + (1-h)*120
Hit ratio = 0.4

But this is not in the options

But when I calculated it using Method 2

Effective access time = 0.8*20 + 0.2*(20 + 120) = 44ns
Increase by 40ns, so new time = 84ns
84 = h*20 + (1-h)*120
Hit ratio = 0.467

That is option (C)

Here, the answer is coming using Method 2 but in the above question they are using Method 1.

How do I know which method to take while solving such problems? Whether would the missed page be brought into the lower memory (cache) or not?

I think, that the part with some other useless information... in your problem specification must contain some information on solving your problem. As I was trying to calculate the numbers that you got I found some errors, and I thought there must be some more input. Let me first explain:

Your formulas are incorrect for both Method 1 and Method 2. When accessing some memory level you ALWAYS access this level, not with probability! Explanation goes something like this: You ACCESS $L1$, if you MISS (some probability), you go to $L2$. On $L2$ you again make an ACCESS, and if you MISS (with some probability), you move to $L3)...

So Method 1 with your first problem would be:
$$[T1]+0.1([2*T1]+0.1*[3*T1])=1.23[T1]$$

And Method 2 for first problem: $$[T1]+0.1([T1+2*T1]+0.1[T1+2∗T1+3∗T1])=1.36[T1]$$

So now looking at your second problem, you can solve it by using Method 1:

New Method 1

Effective access time = 20 + 0.2*(120) = 44ns
Increase by 40ns, so new time = 84ns
84 = 20 + (1-h)*120
Hit ratio = 0.467

Note that here I assumed you made a mistake with answer $(C)$ in your problem description (it is not $0.4467$, but it is $0.467$).

Now if you would have miss penalties defined in your problem statement, then you would use Method 2. Miss penalty just says, that if you do not get a result in your current level, then you have to copy it from the upper level. Now let us assume, that miss penalty on second level is 300ns (that means copying the contents to level 1 and accessing it). Everything else stays the same. The calculations would go:

New Method 2

Effective access time = 20 + 0.2*(120+0.2*300) = 56ns
Increase by 40ns, so new time = 96ns
96 = 20 + (1-h)*(120+(1-h)*300)
Hit ratio = 0.65840

One other caution... You need to use the same formula for calculating the average access time if you chose one method. (In your Method 2 you calculated access time by Method 2 and then calculated the new hit ratio with Method 1)

So how do you know which method to choose? From the problem description! If you have miss penalty given, then you take the second approach. If you do not have miss penalty, then you use the first approach.


Recursive DP vs Graph Traversal solutions to path-based problems I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can take it to the bottom left of the grid".  Or similarly sometimes they ask if the particular destination can be reached at all with some obstacles.

I've seen it solved with recursive DP solutions where you essentially start at the beginning state and recursively call the same function on all states reachable from the current state and the base case is when you reach the target state.  Also sometimes memoization is used to optimize it.

However I think these types of problems can also be seen as graph traversal problems.  The beginning state would be a node and each node has children which are the states that can be reached from the current node creating a directed graph. So finding a path to the target state can be done via a graph traversal algorithm.

So I guess my question is which is what are the tradeoffs for each approach? Or are they in some cases equivalent?

Both approaches are valid.  Assuming you're using memoization, they're largely equivalent; two different ways of thinking about the same thing.


Can the foundation of computer science be implemented to include new rules of inference so that computer can do causal reasoning? The idea I'm thinking of is about a top-down approach for AI. I would like to know if there can be a model for computers so that they can perform causal reasoning. It seems that causal relation can be simplified to be a  mathematical structure, as an acyclic directed graph. If using type theory, one builds some "time types" $\{\sigma_i,i\in\mathbb{N}\}$ ($\mathbb{N}$ as an index set denoting time points). The variable inhabit different time types means they are at different time points. The signature can be constructed according to the existing causal relation. The formation rule is such constructed that the rules for formulas with variables from the same time types are the same as usual logic, and the rules for different time types are based on the causal relation.

Can someone comment about this idea and give some general review about the development of top-down approach, also about causal reasoning?

This is a hot topic at the moment. Read this recent paper by Judea Pearl for example. In general, ML and AI are not very good at causal inference at the moment, because it requires a symbolic representation to build causal graphs. Attempts are being made, however, see e.g. https://arxiv.org/abs/1711.08936 or https://arxiv.org/abs/1709.05321.


Importance of recursion in computability theory It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?

In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people).

Several definitions of "computable" were proposed, of which three are best known:

The $\lambda$-calculus
Recursive functions
Turing machines

These turned out to define the same class of number-theoretic functions. Because recursive functions are older than Turing machines, and the even older $\lambda$-calculus was not immediately accepted as an adequate notion of computability, the adjective "recursive" was used widely (recursive functions, recursive sets, recursively enumerable sets, etc.)

Later on, there was an effort, popularized by Robert Soare, to change "recursive" to "computable". Thus we nowadays speak of computable functions and computably enumerable sets. But many older textbooks, and many people, still prefer the "recursive" terminology.

So much for the history. We can also ask whether recursion is important for computation from a purely mathematical point of view. The answer is a very definite "yes!". Recursion lies at the basis of general-purpose programming languages (even while loops are just a form of recursion because while p do c is the same as if p then (c; while p do c)), and many fundamental data stuctures, such as lists and trees, are recursive. Recursion is simply unavoidable in computer science, and in computability theory specifically.


Will floating point code return the same arithmetical results on two different computers? Say I am using boost or the built-in float or double mathematical libraries of my C++ compiler.

I distribute the program.

Will the execution of my C++ program on different machines given different floating point results given that the FPU is CPU specific and AMD may not return exactly the same thing as Intel or ARM.

Should I use fixed-point algorithms to circumvent this possibility?

Would the answer be different if my program was written in something other than C++?

As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot execute the same machine code on both Intel and ARM, so this answer is only hypothetic. Even on different Intel processors you have to take special care that exactly the same machine code gets executed. Some third party libraries like Intel-MKL use different machine specific code on different processors, and other libraries like FFTW measure speed at runtime, and select different algorithms (and hence different code) based on the outcome of these measurements.

Sometimes the compiler is able to inline a certain function (for example your rounding logic), and then you can end up with different results for identical input to that function at different parts of your code. Another very real non-reproducability for distributed floating point computations are potential reductions are the end of the computation. Because the result here depends on the order of the reduction steps, it is very easy to end up with slightly non-repreducible results.

I have run into the issues in the past, but never considered this to be a reason to switch to fixed-point algorithms. For robustness problems of "computational geometry" related code on the other hand, I consider integer or fixed point arithmetic to be an appropriate solution.

  Should I use fixed-point algorithms to circumvent this possibility?

In conclusion, there are several issues related floating point numbers, and even some problems where floating point numbers are not the most appropriate solution, but in general floating point arithmetic is still the way to go. So no, you should not abandon floating arithmetic in general, but only in the specific cases where it causes unsurmountable robustness problems.


Eigenvalue computation for large graph Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it can be oriented but for the ease of the solution let's say it's not, so the matrix is symmetric. Moreover the matrix of adjacency is highly sparse.

I need to calculate the eigenvalues, but the major problem as I see it is that computing eigenvalues for large adjacency matrices cost a lot on time complexity due to matrices operations.  If I can't efficiently compute all the eigenvalues, even a method to find the largest eigenvalue would be nice.

I've searched through the literature in vain, is there an algorithm or other approach to solve this?

There are many methods for computing the eigenvalues of a matrix.

If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests.  Typically the power method takes $O(n)$ time to find (an approximation to) the largest eigenvalue of a $n \times n$ matrix, if the matrix is sparse (it has $O(1)$ non-zero entries per row), with a constant of proportionality that depends on the matrix (and specifically on the value of $|\lambda_1/\lambda_2|$).

A generalization is the Lanczos algorithm, which lets you find the top $k$ eigenvalues in a sparse Hermitian matrix in $O(kn)$ time, with a constant of proportionality that depends on the matrix.  Arnoldi iteration is a generalization to non-Hermitian matrices.

If you want to find all eigenvalues, there are multiple methods.  The QR algorithm has $O(n^3)$ running time, though it doesn't take advantage of the sparsity of your matrix.  Arnoldi iteration can apparently be used to find all eigenvalues, or the $k$ largest eigenvalues, but I don't know what its asymptotic running time is.  There are apparently also software libraries that support eigenvalue computation on sparse matrices, e.g., Eigen, ARPACK, SuperLU, Spectra, OpenNL.  I have no experience with them and cannot recommend one.

For more you might check Computational Science.SE, e.g., https://scicomp.stackexchange.com/questions/tagged/sparse+eigenvalues.


Finding the minimum subset within a cycle Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $[c,d]$. Assume no two values are identical. For $(a,b)$, if $a > b$, the range is $[a,d] \cup [c,b]$; otherwise, it is $[a,b]$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

There exists an $O(n \log n)$ algorithm to find the smallest subset when, for any pair, $a$ is strictly less than $b$. I can run this algorithm for each pair to determine my solution. However, what is a more efficient algorithm to obtain the smallest subset?

Using Kaveh's reduction in this related question, we only have to solve the case where the given intervals cover the entire circle $[c,d]$.

Here's an algorithm that almost calculates the optimum, in $O(n\log n)$. Replace each interval $[a,d] \cup [c,b]$ by the two intervals $[a,d],[c,b]$, and now solve the original problem. Let $O$ be the optimum of the original problem, and $S$ be the optimum of the new problem. I claim that $S-1 \leq O \leq S$.

First, given any solution to the new problem, we can find a solution to the old problem with the same cost, showing that $O \leq S$. For the other direction, take some optimal solution. If it doesn't use any split interval, then $S = O$. Otherwise, let $I_\min$ be the split interval minimizing $a$, and let $I_\max$ be the split interval maximizing $b$. If we drop all other split intervals, then whatever remains is still a cover of the circle. If $I_\min \neq I_\max$ then $S = O$, and otherwise all we know is that $S \leq O+1$.

It's plausible that this algorithm can be adapted somehow to actually find the optimum. (Most algorithms that work on interval graphs also work on circular-arc graphs.)


Which graph partitioning algorithm can solve this problem? In brief:
Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing")
Constraint: All the vertices in each cluster should be directly connected.
Goal: the deviance of the cluster-sums should be as small as possible. (In other words, the sum of loads of all clusters should be as balanced as possible.)

Examples:
An infeasible example: ADG CE BF. Reason: The vertices are not directly connected within each cluster.
A feasible but bad example: AB CD EFG. Reason: The load is not optimally balanced (Difference 14 14 59 is too large).
The optimal solution: ABCD EF G. Reason: the difference among three cluster-sums (28 29 30 respectively) is the smallest.
Which algorithm can get the optimal solution?

Your problem is $\text{NP}$-hard. To see why, consider the version of the 3-Partition problem where we're given multiset $ X = \{ x_1, x_2, \ldots, x_{3n}\}$ of $3n$ nonnegative integers, and we need to decide whether $X$ can be partitioned into three disjoint multisets with the same sum each. Clearly, an instance $X = \{ x_1, x_2, \ldots, x_{3n}\}$ of the 3-Partition problem can be translated in polynomial time into a complete graph $G = \langle V, E \rangle$, where $V = \{ v_i\}_{i\in [3n]}$  and for each $v_i$, we have that the weight $w(v_i) = x_i$. That is, we view the integers as $3n$ vertices, and every two vertices are connected with an edge. Obviously, a balanced 3-clustering of $G$ corresponds to an appropriate 3-partition of the multiset $X$.


Why is determining if there is a solution to a Battleship puzzle NP-Complete? This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't understand why this can't be done in polynomial time. Given constraints that no two ships can be orthogonally or diagonally adjacent, why not just create a grid where there are 2 times as many columns as "bins" with enough rows to put a "separator" run in between every ship. I've seen the reduction demonstrated this way and it seems like it could be done in polynomial time.

As Andreas T mentions, what you're missing is that the grid is part of the instance.
The instance specifies both the grid and the ships.

Why can't the Battleship puzzle be solved in polynomial time? This is the one million dollar question (literally). But since the paper you mention proves that Battleship is NP-complete, the widely believed conjecture P≠NP implies that Battleship cannot be solved in polynomial time.

The paper goes on to prove that Battleship cannot be solved in polynomial time even when the solution is unique, unless NP=RP, which is also considered unlikely. This is a more realistic version of the problem, since in practice Battleship problems have a unique solution.


Why is Max SAT in P if SAT in P? It holds that if SAT could be solved in poly time, one can also find in poly time the assignment that satisfies most clauses of the original formula.
Does anyone have any idea how to show this?
Let's assume we have algorithm A to decide in poly time if a given formula could be satisfied or not. How one can use this to find in poly time the assignment that satisfies most clauses.
I know that using this assumption leads to also being able to find satisfying assignment in poly time (if the formula is in SAT), but if the formula is not in SAT how can we find what is the sub-formula with maximum clauses that belongs to SAT without iterating over the powerset of the clauses which will lead to exp time algorithm?

Suppose that you have a CNF formula $x$ with input size $n$, and that you can solve $\text{SAT}$ in $O(n^c)$ time for some constant $c$.

We construct a new formula $y$. For each clause $l_i$ in $x$, with terms $v_{i,k}$, add a new variable $t_i$ and the CNF clauses $\bigwedge_i(\neg t_i \vee l_i)$ and $ \bigwedge_{i,k} (t_i \vee \neg v_{i,k})$.

Now this formula is only satisfiable if $t_i$ is assigned a truth value equal to $l_i$, and our input size is bounded by linear function of the original size. We then add a "at least $k$ out of $n$" constraint to this formula on the $t$ variables. This also adds a polynomial number of clauses. Now the formula is only satisfiable if at least $k$ clauses of the original formula are satisfiable.

Now we can simply solve $\log_2(n)$ instances of the above formula, doing a binary search with $k$ to find the maximal number of clauses that are satisfiable simultaneously.


How to compute relative error for the rounding of floating point numbers when the rounded number is 0? I have asked this question on Stack Overflow, I am asking it here in the hope to get more traction.

The relative rounding error for a floating point number x is defined as

$e_r = |\frac{(round(x)  - x)}{x}| = |\frac{round(x)}{x} - 1|$ (1)

Assuming that the rounding to nearest mode is used for $round(x)$, the absolute rounding error $|round(x) - x|$ is going to be less than 0.5 ulp(E(x)), where the ulp are units in the last place

$ulp(E) = 2^E \cdot \epsilon$

and $E(x)$ is the exponent used for $x$, and $\epsilon$ is the machine epsilon $\epsilon=2^{-(p-1)}$, $p$ is precision (24 for the single precision and 53 for the double precision IEEE formats).

Using this, the relative error can be expressed for any real number $x$

$e_r = |\frac{(round(x)  - x)}{x}| = \frac{|(round(x)  - x)|}{|x|} < |0.5 \cdot 2^E \cdot 2^{-(p-1)}| / |2^E| < 0.5 \epsilon$

For denormalized numbers $0 < x < 2^Em \epsilon$, where Em is the minimal exponent (-126 for single precision, -1022 for double):

$0 < x \le 0.5 \cdot \epsilon \cdot 2^{Em}$

the rounding always goes to $0$!

If the round(x) is 0, then by (1)

$e_r =|\frac{(0 - 1)}{1}| = |1|$ !

How is the relative error computed for such numbers? Should the relative error be even used for the numbers that are rounded to 0?

If x = 0 and is rounded to 0 then the error is 0, and the relative error is whatever you want it to be.

If x ≠ 0 and is rounded to 0, then the absolute error is x, and the relative error is 1 (or 100% if that is more intuitive).

If x = 0 and is round to y ≠ 0 then the absolute error is y, and the relative error is infinite or undefined, whatever you prefer.


What is the real reason that Bubble Sort runs at O(n) in best case? In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only comparisons and no swaps in the inner loop.

But is that correct?  Are comparisons not counted in the complexity ? Only swaps?

Other sources claim the reason is only because it can be optimized with a ' flag' checking if it entered the inner loop.  In that case there would be ZERO swaps and n comparisons. ( If this reason is correct, can't I optimize other sorting algorithms this way? Likesay, selection sort?)

What is the correct reason?   I questioned both of the reasons!

EDIT: this is what is said in the link: "In the best case, it is of order n because it just compares the elements and doesn’t swap them"

Understanding how Bubble Sort works is of course really the key here.

The main part for unraveling this is that Bubble Sort goes back to the start if it ever performs a swap. If it never performs a swap, it runs along the array once, comparing each element to the one after it, and thus performing $O(n)$ comparisons.

So both sources are correct. The comparisons are counted in the complexity, you just do more of them (and some other things) if you need to swap stuff.

The reason this doesn't work for something like Selection Sort is that Selection Sort looks for the next element to place at the end of the sorted section in each pass. It doesn't know where that element is, and moreover, it always "moves" something (even if it's a trivial move), and whether you made a trivial move doesn't affect whether you will next time either (whereas in Bubble Sort, if you don't move anything, you know you never will).

You could add a check at the start to see if the array is already sorted of course.

Other sorting algorithms can benefit from similar cases to that in Bubble Sort though; Insertion Sort for example has best case $O(n)$ behaviour as well.


Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$ Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I haven't worked with sums so I don't know their properties, but I was thinking if there is some way to rewrite the formula to get faster calculations.

Let $A = \sum_{i=1}^n A_i$. We have
$$
\begin{align*}
A^3 &= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i < j < k} A_i A_j A_k \\ &=
\sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i < j < k} A_i A_j A_k.
\end{align*}
$$
This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that every symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B_d := \sum_{i=1}^n A_i^d$. For example,
$$
\sum_{i<j<k} A_i A_j A_k = \frac{B_1^3+2B_3-3B_1B_2}{6}.
$$


Euler graph k-coloring (np-completeness proof) I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable.

Define an Euler graph as a graph that 1) is connected, and 2) has every vertex with even degree.

Input: An Euler graph and an integer $k$.
Problem: is the given graph $k-colorable$?

Show that the above is NP-complete.

My attempt:
The problem is in NP since, given some solution "certificate" consisting of $k$ sets of vertices (where all vertices in a set are assigned the same colors), the solution can be verified in polynomial time: Just go thru each vertex and ensure that none of its neighboring vertices are contained in the same set as that vertex. Since a vertex can have at most $n - 1$ neighbors (where $n = |V|$), this should take asymtotically $O(n^2)$ time.

Reduction: reduce the general $k-coloring$ (chromatic number) problem (which is known to be NP complete). Here is where I run into some questions...

My initial thinking was that, given an instance of the general $k-coloring$ problem, with a graph $G$ and an integer $k$, we can construct $G'$ and $k'$ by adding a single vertex to $G$, and connecting that vertex to every odd vertex in $G$, while letting $k' = k$. But then I saw this wouldn't work for a 2-vertex tree graph. Letting $k' = k + 1$ is no good either, because this wouldn't work for the graph consisting of the shape of a square with a diagonal segment added to it.

So now I'm thinking, why not just locate every pair of odd-degree vertices in $G$ and connect each pair with a single edge, while letting $k' = k$? Would this reduction work, or are there still cases where this wouldn't work?

A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other.

In your case, one idea that does work pairs up odd-degree vertices and connects every pair to a new vertex. Now all the degrees are even, and the new graph is $k$-colorable iff the old one is $k$-colorable, assuming $k > 2$. I'll let you figure out why this works.

While this idea is similar to your own idea of connected pairs of odd-degree vertices, your idea is problematic since it is not clear that if the original graph is $k$-colorable then so is the new graph. Indeed, if two vertices that you connected were colored using the same color then you cannot use the same coloring for the new graph. The idea described in the previous paragraph is very similar but doesn't suffer from this shortcoming.


Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs?

Example 1:
set(a, b, c, d, e)
pairs(a>b, ce)

Example 2:
set(a, b, c, d, e)
pairs(a>b, d>b, c>d, d>e)

The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.

Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible orderings consistent with the partial order. I'm not sure that their algorithm is efficient, though. The best constant in the big O is the subject of the 1/3–2/3 conjecture.


How to use a greedy algorithm to find the non-decreasing sequence closest to the given one? You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence. Define the deviation of such a sequence to be $\max(|a_1-b_1|, \ldots, |a_n-b_n|)$. Design an algorithm that finds the $b_i$'s with the minimum deviation in runtime $O(n\sqrt[4]{l})$.

I honestly have no clue whatsoever how to even begin to solve this question. It looks like a dynamic programming question to me, but the professor said that this should be solved using a greedy algorithm. It would be much appreciated if someone can point me in the right direction by giving a small hint.

Let's start with the following observation:

  Let $max$ denote the maximum of the sequence $a_1,...,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ is optimal.

Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation from the minimum of the sequence (since any subsequent $b_i$ must be greater or equal to $b_1$), or we choose $b_1$ small and suffer from the deviation to $max$. The average minimizes the maximal deviation.

We can now try to generalize this observation to use on general sequences $a_1,...,a_n$. For instance, we can partition any sequence into subsequences, such that each begins with the maximum of the respective subsequence.

  Example: $(2,6,4,1,5,2,8,7,5,1)$ is partitioned into $(2)$, $(6,4,1,5,2)$, and $(8,7,5,1)$.

Given this partitioning, we can now solve each these subsequences separately, and obtain an assignment of the $b_i$'s, which however might violate the non-decreasing condition. This can be fixed without losing optimality.

Observe that the last subsequence always contains the maximum $max$ of the whole sequence (otherwise, there would be another subsequence after it). Let $w_1,w_2,...,w_k$ be the values we assigned to the $k$ subsequences. Now, to achieve non-decreasingness in $w_1,...,w_k$, we start from the back at $w_k$ and work our way to the front. If $w_{k-1}$ is larger than $w_k$, we simply set $w_{k-1}:=w_k$. If it is smaller, we keep it. Then, we proceed with comparing $w_{k-2}$ with $w_{k-1}$ and so on. Note that lowering any $w_i$ to the value of $w_{i+1}$ never increases the deviation, since the maximium value in the subsequence assigned with $w_i$ is always lower than the maximum in the subsequence assigned with $w_{i+1}$.

This algorithm should be correct, I think. Concerning the running time, the key step is computing the increasing maxima for the subsequences, which is possible in $O(n)$? Not sure where $l$ contributes.


How would one simulate the law of conservation of energy? I'm new to computer science, but I've studied physics for a while. I'm just curious, if one wanted to make a simulation of the law of conservation of energy, on a large scale, how would it be done? Most simulations take shortcuts for objects off screen, or may even skip them entirely during iterations. The objects may be frozen in place of screen, or grouped together if not interacting. Can these tricks be applied when simulating conservation of energy, without violating the law? Thanks.

I'm having a lot of trouble understanding the question as posed, but I think it's worth making a few general comments about conservation laws and how they are used in physical simulation.

Conservation laws happen because of Noether's theorem. When you are investigating how some physical system evolves over time, it's usually the case that the exact moment when $t=0$ is an arbitrary choice; you could start it 10 seconds later and the system would evolve the same. This is known as time translation symmetry. Any physical system which is time translation invariant is a system where energy is conserved.

Let's take as an example the problem of simulating a gas, where viscosity can be ignored, in one dimension.

We denote $\rho(x,t)$ as the density of the gas at a time and place, $v(x,t)$ is the velocity, $E(x,t)$ is the energy, and $p(x,t)$ is the pressure.

Then the equations we are solving are the Euler equations:

$$\frac{\partial}{\partial t}  \rho + \frac{\partial}{\partial x}  \rho v = 0$$
$$\frac{\partial}{\partial t}  \rho v + \frac{\partial}{\partial x}  \left( \rho v^2 + p \right) = 0$$
$$\frac{\partial}{\partial t}  E + \frac{\partial}{\partial x}  v\left(E + p\right) = 0$$

The pressure is defined in terms of the other variables, called the "equation of state". If we assume an ideal gas, $E = \frac{p}{\gamma - 1} + \frac{1}{2} \rho v^2$ where $\gamma$ is the heat capacity ratio, which is different for different gases.

The Euler equations are, respectively, conservation of mass, conservation of momentum (note that $\rho v$ is momentum), and conservation of energy. The equations state that a local change of (say) energy in time is balanced exactly by a change in space. So those three conservation laws are, in a deep sense, exactly the system that you are trying to simulate.

So I think that it's misleading to think of conservation of energy as something to exploit in simulating some physical system. Conservation of energy is a central part of the system that you're trying to simulate.

One last thing: Physical simulation, especially of thermodynamic systems, suffers from a phenomenon known as "numerical dissipation" or "numerical dispersion". The fact that you are using discrete time steps to simulate a continuous system means that something has to give, and depending on the numerical methods that you are using, this sometimes translates as unwanted diffusion of some quantity that should be locally conserved. Like energy.


Explaining NFA in words I have an NFA, and the question I am asked is :
Let  <  < . Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.
In simple English, my answer is
The NFA accepts strings over alphabet {a, b, c} such that the last symbol appears twice.
Which I know is correct, however my problem lies in the question where "a < b < c". How does this affect my NFA and is my answer still correct? My answer seems really short for 6 marks.

The automaton accepts all non-empty strings in which the last symbol $\sigma$ appears at least twice, and all symbols appearing between its penultimate appearance and its last appearance are smaller than $\sigma$.


Merging sorted arrays and finding Big O bounds Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, all the way until $xn$ for the cost of merging. How would one go about finding the tightest possible Big-O bound for the cost of all the merges? I don't know how to go about this, I have tried writing an equation for the sequence, and that might be where I am going wrong.
The sequence would look something like $2n+3n+4n \dots +kn = n(2+3+4+5+ \dots +k)$ and I'm not sure where to go next.

In case the order of the elements does not matter:

I assume your arrays are not sorted and you don't care of the order of the elements when you merge them.

If you store your arrays as a linked list, then merging list1 and list2 takes $O(1)$ time: you just point list1's tail to list2's head or vice versa depending how you are going to merge. So for $x$ arrays it wil take $O(x)$ time.

If you initially store them as $x$ separate static arrays (by static I mean their size is fixed and the arrays do not grow) then at each step you will need to create a new array of larger size to combine two previous arrays by copying each element one-by-one. Thus, initially it will take $2n$ steps, then $3n$ an so on. Then the total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

If your array is dynamic, i.e., you can append one element to the end of the arrays in $O(1)$ time, then you just append all elements to the first array in $O(nx)$ time.

In case the arrays are sorted and the order of the elements does matter:

The underlying structure does not provide an advantage, whether it is a linked list or dynamic array. Again assume that elements are stored as $x$ separate static arrays. Then we merge two arrays like in the Merge sort algorithm. The total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

But you could use the same procedure exactly like in the Merge sort algorithm by pairwise merging arrays at each stage. This will take $O(nx\log_2{x})$ time.


Interpreting camera matrix I'm having some trouble interpreting the camera matrix $K = \begin{bmatrix} f_x & s & x_0 \\ 0 & f_y & y_0 \\ 0 & 0 & 1 \end{bmatrix}$ after it multiplies some 3D vector.

Assume that $f_x = f_y = f$ and $s = 1$

$\begin{bmatrix} f & 1 & x_0 \\ 0 & f & y_0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} X \\ Y \\ Z \end{bmatrix} = \begin{bmatrix}Xf+Y+x_0Z \\ Yf + y_0Z \\ Z \end{bmatrix} \propto \begin{bmatrix} \frac{X}{Z}f + \frac{Y}{Z} + x_0 \\ \frac{Y}{Z}f + y_0 \\ 1\end{bmatrix}$

So the last vector is the imaged point in homogenous coordinates. However, I'm having trouble interpreting what each of the components are physically doing. An explanation would be much appreciated!

I should mention that I'm familiar with the constants, focal length, skew, and principle point. I just can't tell what they are doing in this configuration.

I will try to help you with this, even if incomplete.

Generally speaking (I don't know if you already know this or not), the camera matrix $K$ tells you how the pinhole camera projects each point in a 3D world, with some coordinates $(X,Y,Z)$ into an image-plane point, with coordinates $(x,y)$. A good reference is Wikipedia. Looking at the diagrams provided there, the 3D point has coordinates labelled $(X_1,X_2,X_3)$, which can be the same ones as our $(X,Y,Z)$ here, and the projected 2D point has coordinates $(y_1,y_2)$, which map to our $(x,y)$ here.

Let's delve into specific cases:

In the case the 3D point is $(0,0,Z)$, the point will be mapped to $(x_0,y_0)$, as the equation you provided shows. Why: in this case, the 3D point is along the line that is perpendicular to the image plane and which goes through the principal point of the camera, regardless of distance $Z$ to the camera.
For some fixed $(X,Y)$ in the 3D world, let's increase $Z$ endlessly. What happens is that, the bigger the distance $Z$ to the camera, the nearer to the camera's principal point $(x_0,y_0)$ the projected point will be. As an example, imagine a road photographed by a camera, such as this one. See how the 3D points that form the surface of the road converge to the principal point of the camera when their distance to the camera increases. This relates to the fact "parallel lines intersect themselves at infinity".

Now that we presented some specific cases, let's go a little backward in terms of why this matrix makes sense in the first place. It has to do with simple trigonometry around similar triangles. Please look at the Wikipedia article where it shows the similar triangles diagram and the corresponding mathematical formulation; you'll see the resemblance with $f\frac{X}{Z}$ and $f\frac{Y}{Z}$ elements you provided.

Now, you provided a camera matrix with high skew ($s=1$). In a pinhole camera model, you should have $s=0$, which means no skew at all, and so kill that $\frac{Y}{Z}$ parcel you have at your first entry, which only confuses you further. Skew in a camera is typically due to digitization effects and is very close to zero, not $s=1$ as you provided.

For further knowledge about this topic, I highly recommend the book Computer Vision: Algorithms and Applications
by Richard Szeliski available freely as PDF at the same link.

I just came across this good article that also thoroughly explores the pinhole camera model. It includes an interactive applet at its bottom.

I hope this helped you get a first understanding of how those entries make any sense.


Is automatic multicore support at the hardware or compiler level possible? Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance.

However, multicore support currently appears to require the programmer to manually divide the work, control communication/synchronization, etc. For many processor intensive games and simulations (such as DCS), such complicated multithreading effort has been limited, and these programs depend extremely heavily on single thread performance.

Could a processor with multiple cores divide the work automatically?

Alternatively, could a compile convert single-threaded code to mulithreaded code?
In the current world, multicore support has to be done by hand as far as I know, with a result being that many processor intensive games and simulations (such as DCS) depend extremely heavily on one CPU core to avoid complicated multithreading.

The short answer: yes it's possible, but right now it generates slower code.

The long answer: the thing to keep in mind here synchronization. Computation is not just a bunch of independent computations. The results of one computation are used in other ones. Sometimes the order doesn't matter, and sometimes it does.

Take for example, some hard to evaluate function $f$. If we want to compute $f(f(10) + f(20))$, we can evaluate $f(10)$ and $f(20)$ in parallel, but we can't evaluate the final result until we've done the two inner evaluations and added them together.

This process of making sure things happen in the right order is called synchronization. There are many ways to ensure synchronization happens and that the code produces the same result even if some operations are moved around.

There are many models of concurrency: some have shared memory with locks on variables, some have totally separate processes that pass messages. But in every model, the synchronization carries some overhead. Acquiring a lock, sending a message between processes, each of these adds time that wouldn't be required if you evaluated the code sequentially.

Likewise, scheduling causes some overhead. If you have 200 processes and only 8 cores, you will probably be slower than if you have, say 20 processes and 8 cores, since you have to do a lot more work scheduling, but don't get additional parallelism.

The key, then, is to adjust the "granularity" of your concurrency. Too coarse and you don't make use of all the processors, but too fine and you get too much overhead from synchronization and scheduling.

This sort of analysis is hard, and right now compilers don't do it well enough to make general code faster, but I suspect with heuristics, and maybe even a bit of AI/machine learning, in the future we'll be able to automatically adjust the granularity automatically.

I'm not a hardware person, but my guess is that computing these sorts of things are way too complicated and time-consuming to be done on-the-fly at the CPU level.

At a compiler level, it's possible, but depends on your language constructs. I'm fairly certain finding the "optimal" parallelization of a program is undecidable, since you can probably construct some example where you can parallelize a program iff an arbitrary program halts.

However, like most program analyses, we can do "safe" approximations. In particular, there has been interesting research into automatically parallelizing "pure" functional languages like Haskell. When any side-effects of a function are captured by the type system, it's a lot easier for the compiler to know what operations can safely be performed in parallel. But to my knowledge, none of these efforts have succeeded so far in producing fast code.


2-3 tree: Sum of leaves in a given range I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which their key is within a given interval. The time complexity of the function needs to be $O(\log n)$.
I thought about saving for each internal node the sum of the leaves in its subtree, but I don't know how to continue from there.

Storing the sum for internal nodes is a good plan.
For every query you also need to search for the two bounds of the interval, and find the leftmost and rightmost leaf with elements in the interval. (The bounds themselves do not need to be in the tree.) The two search paths will split a a certain node. Continue there. While searching for the leftmost leaf you include all sums to the right.


Simplify complexity of n multichoose k I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression.  In my case, $k$ may be greater than $n$ and they grow independently.

Specifically, I'd expect some explicit exponential expression.
The best I could find so far is that based on Stirling's approximation $O(n!) \approx O((n/2)^n)$, so I can use that, but I wondered if I could get anything nicer.

$$O\left({{n+k-1}\choose{k}}\right) = O(?)$$

Edit: This answer is for $k<n$. Without bounding $k$ in terms of $n$ the expression is unbounded.

If $k=n-1$ then your expression becomes
$O\left ({{2(n-1)}\choose{n-1}}\right)$. Notice that by Stirling's formula for any $0<\alpha<1$
$${m \choose {\alpha m}}= \Theta(m^{-{1/2}} 2^{H(\alpha)m}),$$
where $H(q)=-q \log q - (1-q) \log (1-q)$ is the binary entropy. In particular $H(1/2)=1$. Therefore we have for $k=n-1$
$$O\left ({{2(n-1)}\choose{n-1}}\right)=\Theta((2n-2)^{-{1/2}} 2^{2n-2})=\Theta\left(\frac{ 4^{n}}{\sqrt{n}}\right).$$

Since the upper bound $k=n-1$ is the worst case (
I leave it as an exercise to show this), your expression is $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$.


Is there a systematic way to know when to alpha-transform free variables? So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$

... but why?

$g$ is a free variable in each expression, and my understanding is that you must ${\alpha}$-convert free standing variables in unrelated expressions.  Shouldn't we instead end up with something like

$(g (g (g (g_2 (g_2 (g_2 (g_2\ z)))))))$?

The answer here is the same as in the other question: one thing is missing here!

Your addition result should be:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

Note that $g$ is now a lambda parameter, not a free variable! So now if you want to apply this to something, it'll get substituted in the same everywhere:

$$7 q r = (\lambda g . \lambda z . 7 g z) q r = q q q q q q q r$$


How to remove cycles from a directed graph I saw this from SO which led to Feedback Arc Set, which describes the problem nicely:

  In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG).

I am wondering how this is done. Given a graph such as this:

a -> b
b -> c
c -> d
d -> a

Or a for loop flattened out such as:

somemethod -> forloop start
forloop start -> forloop next
forloop next -> forloop result
forloop next -> forloop next // i+1
forloop next -> forloop end
forloop end -> forloop result
forloop result -> next method

Wondering how you can possibly remove the cycles from a graph like that.

There is a paper "breaking cycles in noisy hierarchies" which talks about leveraging graph hierarchy to delete cycle edges to reduce a directed graph to a DAG.

The reduced DAG will maintain the graph hierarchy of the original graph as much as possible.

The corresponding code is available on Github: https://github.com/zhenv5/breaking_cycles_in_noisy_hierarchies


What is 0.1 converted to 8bit IEEE754? 0.1 via $32\text{ bit}$ is rather easy:

Sign: $0_2 = 0_{10}$

Exponent: $123_{10} = 01111011_2$

Mantissa: $5033165_{10} = 100110011001100110011001101_2$

Now, how do you calculate this, if you've only $8\text{ bit}$ available?
Sign: $1\text{ bit}$, Exponent: $2\text{ bit}$, Mantissa: $5\text{ bit}$

My idea: $S=0; E=01; M=00001$

What do you think?

For $8$-bit floating point, you should look at $A$-law and $\mu$-law encoding standards:

http://en.wikipedia.org/wiki/%CE%9C-law_algorithm

http://en.wikipedia.org/wiki/A-law_algorithm

Depending on your input range, you may need some scaling.


If an algorithm solves an NP problem, for what f(n) can we claim that R belongs to TIME(f(n))? Let $R$ be some problem in NP.

Suppose algorithm of solution check M(x,y) runs in time $O(n^3)$ and uses $y$ additional information, s.t $y \leq 5 \log n$ bits.

For what $f(n)$ can we claim that $R$ belongs to $\textbf{TIME}$$(f(n))$?

I have no idea how to solve this.

Suppose, for clarity:

$X$ is the input, and $|X|$ = $n$
$Y^*$ is a "yes" certificate, $|Y^*| \leq 5\log n$ bits
$M$ is an algorithm that verifies the instance $X$ given certificate $Y^*$ in
$O(n^3)$ time.

There are $2^{|Y^*|}$ possible binary certificates of length $|Y^*|$, so algorithm $A$ that checks all possible certificates $Y_i$ of length $5\log n$ will have exactly $ 2^{5\log n} = n^5$ certificates to check.

Since each certificate takes $O(n^3)$ time to verify (with $M$), $A$ will run in $O(n^8)$. If $X \in R$, a certificate $Y^*$ that verifies it exists and $A$ will find it (because it checks them all).

It follows that $A$ accepts $R$ and runs in $O(n^8)$ time, so $R \in \textbf{TIME}(n^8)$


Proof that a language involving $gcd$ is not context-free How would you prove that the following language is not context-free?

$$ L= \{a^n b^m |\, gcd(n,m)=1 \}$$

I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.

Let $p$ be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose $m \neq n$ such that $m,n \geq p$ and are both prime. Then clearly $s = a^{n}b^{m} \in L$.

By the pumping lemma we can divide $s$ such that $s=uvxyz$ and

$|vxy| \leq p$
$|vy| \geq 0$
$s' = uv^{i}xy^{i}z \in L$ for all $i \in \mathbb{N}$

For this language we get three similar cases, and one trivial case. The trivial case is where either $v$ or $y$ contains both $a$'s and $b$'s, in which case $s'$ doesn't have the correct ordering, and thus $s'\notin L$.

The nontrivial cases:

 $v$ and $y$ are both strings of $a$'s, then when we pump $s$ we get $s' = a^{n+ik}b^{n}$ where $k\geq 1$. Then $s' \in L$ if $gcd(n+ik,m)=1$, however the modular equation $n+ik\equiv 0 (m)$ has the solution $i \equiv nk^{-1} (m)$, and as $m$ is prime we are guaranteed that $k^{-1}$ exists. Therefore any element of the residue class $i \equiv nk^{-1} (m)$ would give us $gcd(n+ik,m) > 1$. Ergo $s' \notin L$.

Short version: we can pump the string so that $n+ik$ is a multiple of $m$ for any $k$ with $1 \leq k \leq p < m,n$ (which is what we set up at the start).

$v$ and $y$ are both strings of $b$'s, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.

$v = a^{k}$ and $y = b^{h}$ for some $k$ and $h$ with $1 \leq k+h \leq p$. Then when we pump we get $s' = a^{n+ik}b^{m+ih}$. Now $s' \in L$ if $n+ik \equiv m+ih (m)$ has no solution, but as I'm sure you can see from here, rearranging just gives $n+i(k+h)\equiv 0(m)$, and as before this has solution $i \equiv n(k+h)^{-1}(m)$. So again we derive a contradiction.

Thus there is at least one string in $L$ that cannot be divided as per the pumping lemma and still have all pumping results remain in $L$. Therefore $L$ is not context free. $Q.E.D$

Some additional notes: of course there is an infinite number of strings which can't be pumped, and it's not actually necessary for $m$ and $n$ to be prime, it just simplifies that argument, as we don't have to fiddle around with a prime decomposition - though if you did want to, you just pick one of the prime factors and do the same (or even all of them if you want).


Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1) There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to this:

  Given an n-tuple of integers, how do I derive a stateless pseudorandom number / hash value in the half-open interval [0,1)?

The usual “solution” people use in this situation is to multiply the parameters by some large primes, or bit-shift them, or do any other complex calculation which produces a result that is “random enough” for the given purpose.  I guess these algorithms have been cargo-culted over a long time, maybe from a PRNG implementation.

Instead of copying one of the circulating code snippets, I'd like to really understand what's going on here.  Is there an algorithm or a set of algorithms which should typically be used in this kind of situation, and if so, what's the proper way to choose the constants?

Every hash function is stateless; that's part of the definition of what it means to be a hash function.

A simple approach is to take a representation of the input in binary, using any standard encoding for the integers and for $n$-vectors of integers, and then hash the result using your favorite hash function.  The output will be a binary string.  Treat it as the binary representation of a number in the range $[0,1)$ (put a decimal point before the start of it, and interpret it in base 2).  That's your output.

Then, choose a suitable hash function for hashing binary strings.  If you need it for cryptographic purposes, you could use SHA256.  If you need it for non-cryptographic purposes, there are many standard, fast hash functions; choose one that meets your requirements.  Since you didn't state any precise requirements in the question, we have no basis to select among any of the standard solutions.


Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k? As an example, here are all possible trees for the case $k=3$:

On each node written is its arity (= the number of children).

While this should be solvable by dynamic programming, I think there was a combinatoric result on this (either exact or a rather fine grained upper bound). Does anybody know it?

Edit:

The size of the tree is the number of nodes it has, so the biggest tree would be the one with the maximum number of nodes.

Let $B(n)$ be the size of the largest tree, where the arities of each path from root to leaf add up to $n$.

If the root of such a tree has arity $k$, then the paths for each of the $k$ subtrees must add up to $n-k$. As the subtrees must be optimal, the tree has size $1+k\cdot B(n-k)$.

A formula for $B(n)$ just maximizes that expression over $k$, using the previous values $B(n-1), B(n-2),\dots$.

I tried to do this by hand, and found (with the help of @Sudix, thanks) $1,2,3,5,7,11,16,23,34,\dots$. This seems to be A239288 in Sloanes Online Encyclopedia of Integer Sequences. The recursion given there is similar, but not exactly the same.

The explanation of the sequence there is: "Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n". That indeed is the same sequence: if the sequence of arities along the path from the root is x0, x1,..., xk these should sum to n, and the number of nodes indeed is the given formula.

Another remark at Sloane is interesting: "For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k)". This seems to suggest that for values larger than 24 the root of the tree always has three children.


Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable? Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of

$\{D\mid D\text{ is a DFA and }L(D) = S\}$ and
$\{G\mid G\text{ is a CFG and }L(G) = S\}$

decidable?

I know that the easier question of whether $D$ or $G$ generates a particular string $w$ or whether the language is the empty-language is decidable, but how can I decide on a particular set of strings?

I am thinking for the case of DFA I can do something like set-difference and check if $L(D/S)$ is empty.

For the case of CFG since it is not closed under complement is this question undecideable?

Let's assume that $S$ is regular and given in some explicit form (DFA, regular grammar, regular expression, what have you). Given a DFA $D$, we can compute a DFA for $L(D) \triangle S$ (here $\triangle$ is symmetric difference) and check whether it is empty or not. This allows us to decide whether $L(D) = S$ or not.

Given a CFG $G$, we can compute a CFG $G'$ for $G \cap \overline{S}$, and then check whether $L(G') = \emptyset$. This allows us to check whether $L(G) \subseteq S$. However, in general we cannot check the opposite inclusion: determining whether $L(G) = \Sigma^*$ is undecidable (the universality problem). However, if $S$ is finite, we can check whether $G$ generates each of the strings in $S$, and thereby solve the problem.


Solving AlienTiles with an A* heuristic Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.

One candidate approach: for each color $c \in \{\text{green}, \text{blue}, \text{purple}\}$, try to define a distance heuristic $f_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$.  For instance, if $s$ is a state, then $f_\text{green}(s)$ should be an estimate of the distance to the all-green state.

Next, given these heuristics, define a distance heuristic

$$f(s) = \min(f_\text{green}(s), f_\text{blue}(s), f_\text{purple}(s)).$$

Then you could use $f$ as your distance heuristic with $A^*$.

I leave it up to you to see if you can find a suitable definition of $f_c(s)$.  One candidate would be the number of tiles in $s$ whose color is not $c$, but that's probably not going to work; you'll probably need something smarter.

If you're willing to use something other than the $A^*$ algorithm, there is an elegant solution to this problem using linear algebra.

Identify the colors red, green, blue, purple with the integers $0$, $1$, $2$, $3$, taken modulo 4 (so you are working in $\mathbb{Z}/4\mathbb{Z}$).  Now you can solve the problem using linear algebra.  In particular, the state $s$ is a $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$.  Clicking on a tile at position $i,j$ corresponds to updating the state from $s$ to $s+v_{i,j}$, where $v_{i,j}$ is a fixed $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$.  Thus, you can get from state $s$ to state $s'$ if and only if $s'-s$ is in the linear span of the $v_{i,j}$.  If it is in the span, then find coefficients $c_{i,j} \in \mathbb{Z}/4\mathbb{Z}$ such that

$$s' - s = \sum_{i,j} c_{i,j} v_{i,j},$$

and this will give you a solution method: for each $i,j$, click on tile $i,j$ exactly $c_{i,j}$ times (order is irrelevant).  You can use generalized Gaussian elimination to check whether $s'-s$ is in the span, and if so, to find the coefficients $c_{i,j}$.


What is meant by $\operatorname{poly}(|F|, n, e)$? When I am reading a paper I found a notation $\operatorname{poly}( |F|,n,$$\frac{1}{\epsilon}) $.
Its not clear to me that what this notation represents. Can you please help me out?

$F=\mathrm{poly}(n)$ means that $F$ is polynomial in $n$, i.e., that there exists a constants $c$ such that $F=\Theta(n^c)$. (sometimes it might mean upper-bounded by polynomial, that is $F=O(n^c)$)

For multiple variable, the same applies, $\mathrm{poly}(n,m)$ means polynomial both in $n$ and $m$, that is, there are constants $c_1,c_2$ and the quantity is $\Theta(n^{c_1}m^{c_2})$. (again, the more common use is for $O(n^{c_1}m^{c_2})$)


Can algorithm discovery be brute forced? Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of polynomial time algorithms for NP-complete problems.

Of course, rather than pure brute force, perhaps some intelligent force could be applied as a refinement.

My back-of-the-napkin-ish attempt to answer the question. Just an exercise; I don't really trust it.

In theory, yes - absolutely. The question is whether, in practice, it could be done in a reasonable amount of time in a cost-effective manner.
The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
Roughly how many bits does it take to write algorithms? To answer this question, I googled for a quick sort implementation in c, and compiled it to machine code. The result was about 10,000 bytes. So 80,000 bits. Let's say 100,000 bits for a round number.
There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
You'd have to test each of these permutations. Let's say it takes 1 minute to test a permutation of 1's and 0's. Then that'd take $10^{30,097}$ years to finish testing. No good.
Perhaps the parameters could be tweaked. Let's try just 1,000 bits and 1 second to test each permutation. $2^{1000} = 10^{301}$ permutations. That'd take $10^{295}$ years.
Even if we used a lot of computing power, that'd still only cut the exponent down by 5 or 10, maybe. So ultimately, it seems impractical to actually brute force. The question then becomes whether we can combine intelligent force with brute force in algorithm generation.
Even though brute force seems impractical, I wonder if future generations will have insane computational power that we would never dream of. If so, brute forcing algorithm generation may be possible. Of course, they may have figured out all the algorithms by then.

You are correct in saying that algorithms are no more than a sequence of strings. However, you should make the distinction between syntactic and semantic properties of the algorithm. Syntactic properties are those relating to the actual code, e.g. what is the length of the program? how many "while" loops does it contain? Semantic properties are related to what the program actually does, e.g. is there some input that would cause this program to go into an infinite loop?

The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code.
So in fact, the situation is worse than what you think. Even the craziest hardware won't help us, since such tasks are impossible for a computer.

As a side note, suppose your situation was better, and you try to cope with some decidable problem which has an exponential lower bound (i.e. all algorithms for this problem would require exponential time, not just brute force search, even the "smart" ones). Again, better hardware won't help you. For some intuition regarding your parameters, you have $\approx 10^{80}$ atoms in the universe, so performing this amount of operations is hopeless. What you need is a smarter algorithm, but we started with a problem that unfortunately has an exponential lower bound.


Is the infinite language unrecognizable in a Turing machine? This question is building up on an older one, here.

But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?
That means 1, 11, 11111, 1111111, and so on are all accepted.

I believe the TM is unrecognizable. This is because for it to be recognizable, we would have to halt. Yet, with no upper limit, we can have $1^\infty$ - meaning we will never halt. Does this work?

The above was an example of a language, didn't think it would be recognizable. A better way to phrase my question is: Is there a language of any number of $1$s over $\Sigma=\{0, 1\}$ that you can make unrecognizable?

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable.

A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we can indeed build a Turing machine that does this!

Algorithm:
    Check the number under the head.
    If it's 0, fail.
    If it's the end of the string, accept.
    If it's 1, move to the right and repeat.

The key is, while there's no upper limit, $x$ has to be a natural number—and $\infty$ is not a natural number. In other words, while $x$ can be arbitrarily large, it has to have some finite value. It can't actually be $\infty$.


Polynomial time algorithm for finding two or more vertex-disjoint cycles The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a graph.

The difficulty however comes when we are required to find in polynomial time whether 2 vertex disjoint cycles exist in an arbitrary graph. Is there such a polynomial time algorithm which finds whether 2 vertex disjoint cycles exist in an arbitrary graph?

By vertex disjoint cycles, I mean cycles which do not share a common vertex.

The structure of graphs without two vertex-disjoint cycles is well understood (see for example Bollobás, Extremal graph theory), having been researched in 1965 by Dirac and the 17-year old Lovász (separately).

Theorem 1. Suppose that $G$ has minimum degree at least $3$. Then $G$ has no two vertex-disjoint cycles if and only if one of the following holds:

$G \setminus \{v\}$ is a forest for some vertex $v$.
$G$ is a wheel (a cycle plus a vertex connected to all vertices in the cycle).
$G$ is $K_5$, the clique on 5 vertices.
$G \setminus \{v,u,w\}$ is an independent set for some three vertices $v,u,w$.

Theorem 2. A graph $G$ has no two vertex-disjoint cycles if and only if either $G \setminus \{v\}$ is a forest for some $v$, or $G$ is obtained from one of the graphs $H$ in Theorem 1 by subdividing edges, adding a forest, and possibly connecting each tree in the forest by a unique path to $H$.

Theorem 1 can clearly be implemented algorithmically in polynomial time. In order to implement Theorem 2, we need to undo the subdivision and remove the forest and its attaching paths. We can identify the forest by removing isolated trees and identifying paths leading to trees. We can then undo the subdivision by compressing paths, reducing to the case of Theorem 1. It seems that everything can be implemented in polynomial time.


Is closed form of summation less costly? I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does.

Here's the original sum

Sum(N)
   total = 0
   for x = 1 to N
       total = total + x
   ret total

Here's the closed form

Sum(N)
    ret N*(N-1)/2

I think the argument is that '*' is only a single operation vs many '+' operations, but I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Please correct me if my above claims are incorrect. My questions are: Does the closed form in this particular case yield fewer steps? Is closed form intended to reduce number of operations on the machine itself, and does it ever do that?

I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Try being more imaginative.  I'm pretty sure that you were taught at school how to calculate, say, $38\times 144$ without adding $144$ thirty-seven times.


Topological Sort without modifying the graph or marking edges I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of view: Kahn's algorithm modifies the graph (by removing edges) and the DFS-based one marks nodes, which would require me to modify my node classes (by adding a boolean field) and is furthermore not thread safe.

Are there more practical approaches, that preserve the asymptotic runtime but do not interfere with my business logic so much?

Instead of seting a 'mark' flag;

 node.Marked = true;

You can maintain a set of marked nodes in a hashtable or similar;

 hashTable[node] = true;

You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.


What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square? I recently saw a problem from Numberphile here, where the goal is to arrange the numbers $1,\ldots,n$ so that the sum of adjacent numbers is a perfect square. This question from Mathematics Stack Exchange has a good analysis of the generalization of the problem for arbitrary powers, but I have been unable to find an analysis of the complexity class of the decision version of the problem. It is $NP$ since you can check if an arrangement satisfies the square sum condition efficiently, but I have been unable to come up with a better algorithm than creating the associated graph and solving the Hamiltonian path problem.

So my question is if this problem is $NP$-complete or if there is a polynomial time algorithm that can decide if $1,\ldots,n$ can be arranged to satisfy the square-sum condition.

Arranging the integers means to find a permutation $a_1, \ldots, a_n$ of $1,\ldots, n$ with the property that for all $1 < i < n$, $a_i + a_{i+1}$ and $a_i + a_{i-1}$ are perfect squares.

Whether this problem is in NP or not (or rather, in NP or not known to be in NP) depends on how you encode the input. If you encode the input in binary (or in decimal), then the input "$N$" has length $n = O(\log N)$, whereas the obvious witness has length $\Theta(N\log N)$, which is exponential in $n$ (of course, there could be a more compact witness), giving a complexity upper bound of only NEXP. In contrast, if you encode the input in unary (that is, as $1^N$, i.e., $N$ times the symbol $1$), then the input length is $N$ as well, and so the witness has polynomial length, putting the problem in NP.

Even if you use the second encoding, it seems unlikely that the problem is NP-complete. Most NP-complete problems involve a lot of data, and even the few problems which have a constant number of integers as input have more than one integer as input. Of course, formally, speaking, you can think of the input to any problem as a single integer. But semantically, there is a big difference.

What is the complexity of the problem, then? If there is a nice characterization of the values of $N$ for which such an arrangement exists, then it is likely that implementing the characterization would put the problem in P (even using binary encoding). As an extreme example, if such an arrangement exists for all large enough $N$, or doesn't exist for all large enough $N$, then the problem can be solved in linear time. If there is no simple characterization, then the problem might indeed be difficult, but probably not NP-complete or NEXP-complete.


Does DFS in an unweighted DAG find the shortest path for each vertex from a source? I have many questions which related to this topic.
I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths  of all vertex by asking about each vertex whether it's weighted higher than edge plus previous vertex.
The point is, I don't understand since we are in DAG why isn't DFS alone enough to find shortest paths. Both weighted and unweighted.
I also don't understand why we need a stack in topological sort. If you were to perform a DFS on some DAG. It will automatically produce a topological sort, if you do a pre-order DFS traverse.

The only question is in the tile so I'm going to answer that.

A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$.
As a counter example look at the following graph:

If vertex $a$ is visited before vertex $b$ you will not necessarily discover the shortest path from $s$ to $b$.

Also, the same example shows that the order in which vertices are considered by a preorder DFS traversal is not necessarily a topological sort.
Indeed, if $b$ is visited before $a$ the order would be: $s, b, a$ but there is an edge from $a$ to $b$.