Why do we use worse-case when categorising problems? Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.

Why don't we use the average case?

I imagine we could have a problem in NP when we look at it's worse-case, but when we look at it's average-case we could have a really efficient algorithm. This is just intuition and not sure of an example.

For something like cryptography, I'm guessing this is not desirable.

Because average case requires a definition of "average". Specifically, average over what distribution of inputs?

Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing.

On the other hand, average-case doesn't necessarily correspond to anything very much. Suppose you just take the uniform distribution over inputs of a given length. Why would you feel that the mean number of steps the algorithm takes is a useful measure of anything? Probably your inputs don't look much like a uniform distribution. The mean based on any distribution doesn't give you any guarantees about actual performance on specific instances.

Also, and this might, sadly, be the real reason, average-case complexity is hard. It means you have to understand how the algorithm behaves on essentially all possible inputs, and getting good bounds for all kinds of input is a lot of work.

One place where average-case is used is amortized analysis.  Consider a dynamically sized hash table where, if the table is more than, say, three-quarters full, you copy everything into a new table that's double the size.  In this situation, inserting an element into a table of size $n$ can take up to $2n$ steps, which is horrible in the worst case. However, you only need to do this expensive copying operation once every $3n/4$ steps. On average, then, each insert operation causes $2n/(3n/4)=8/3$ amount of the work needed to double the size of the hash table. So, in a very strong sense, the average cost of growing the table is just a constant amount per insertion, and this is completely independent of what insertions are done.  This is practically very useful when analyzing algorithms that use hash tables.


Cost at Each Level of a Recursion Tree Given a recursive function $T(n)=T(a_1\cdot n)+\dots +T(a_k\cdot n)+\Theta(n)$ such that $\forall a_i: 0<a_i<1$, what is the most general thing I can say about the sum of the cost of the nodes at each level of the recursion tree?  I've looked at a few, and for the ones I've looked at it's always come out to $(a_1+\dots +a_k)^i$ where $i$ is the level in the tree.

Could anyone explain this?  If it matters it's in the context of trying to prove that $T(n)=\Theta(n) \Leftrightarrow a_1+\dots +a_k < 1$

You are right!

The work $W$ at each node (of level $i$), splits into $Wa_1, Wa_2, \dots, Wa_k$ at level $i+1$.

If you add them up, you get that the total work at level $i+1$ is $a_1 + a_2 + \dots + a_k$ times the total work at level $i$.

Of course, this assumes that your $\Theta(n)$ is some exact $cn$, but this argument is good enough to prove that $T(n) = O(n)$. Proving $T(n) = \Omega(n)$ is trivial.

btw, I recommend you look at Akra-Bazzi as a useful tool, if you are interested in such questions.


Circles covering a rectangular, how to verify it? This may be basic to some of you, but excuse my inexperience with comp. geometry:

Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$  and each having radii $r$. Also given a rectangle. All objects are on a plane. How to verify that every point inside the rectangle (including its edges) is fully covered by the circles. That is, each point in the rectangle lay on at least one of the circles.

Anyone have hints ? I am currently trying with voronoi diagrams.

Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time.

Now you have a set of convex shapes, thus the furthest point away from the center of the disk inside the cell is a vertex on the cell. Compute the furthest point for each cell can be done in $O(n)$ time. If for all of them, it is within $r$, then the set of disks covers the rectangle.

A $O(n \log n)$ algorithm.


Dynamic programming: speed of top down vs bottom up approaches I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?

I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result[i], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.

Or maybe there was just a bug in my top down approach.

Update:
The problem on LeetCode is:
" You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1."

I defined an array result of size amount+1; result[i] is the minimum number of coins needed to reach amount i (with result[0] = 0).

If we have N coins, and coin j has value V[j], the recursion is:
result[i] = 1 + minimum of result[i-V[j]] for all j=1...N (only the j for which i-V[j]>=0)

I used a bottom up and top down approach to compute result[amount]:

If we don't have a coin of value 1, we won't need to compute result[i] for every i with a top down approach.

The time limit was exceeded for top down with this input: Coins: [186,419,83,408], Amount: 6249

Top down approach would be faster in cases where the no of entries that you have to compute are significantly less than than the total number of entries. Remember, recursive approach is slow than iterative approach because there is some overhead of function call too.

Top down approach fails in some cases because it works by recursion. In recursion you require space (stack space) for storing each function call. Now, if the depth of your recursion tree is large you may run out of stack space. In that cases iterative approach (like bottom to top approach) works because you can use memory from heap and running out of stack space is not an issue there.


Proof of Dijkstra Algorithm Optimality Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing)

I became curious when Wikipedia mentioned it as the 'best known' rather than the 'best possible'. Is a proof of its optimality an open problem?

There is no non-trivial complexity lower bound on any interesting problem. In particular, any algorithm not running in $O(|V|+|E|)$ is not known to be tight.
That said, you might be able to show a lower bound in some restricted model, say the decision tree model. For example, it might be possible that any comparison-based algorithm must make $\Omega(|E|+|V|\log|V|)$ comparisons in the worst case, though I am not aware of any such work on the single-source shortest path problem. See also the related question on cstheory.

Another avenue for obtaining conditional lower bounds is accepting some widely believed complexity assumption such as the Exponential Time Hypothesis or some version of the 3SUM hypothesis (whose strongest version was recently disproved by Grønlund and Pettie), though I'm not aware of any such work either in the present case.


How to convert a Turing Machine program to a tiling using Wang Tiles? This is a cross-post from a post on MathSE due to lack of answers.

To illustrate my question I provide the following example.

The website Online Turing Machine provides a Turing Machine simulator. The following program adds 1 to any binary number.

q0,1  =>  q0,1,>
q0,0  =>  q0,0,>
q0,_  =>  q1,_,<
q1,0  =>  q3,1,>
q1,1  =>  q1,0,<
q1,_  =>  q3,1,>

A program line has the following format:

state, character read => new state, character written, direction tape

In the program above q0 is the initial state and q3 is the accepting state.

In Tilings and Patterns by Gruenbaum and Shephard, 11.4 "Computing By Tiles" I read that it is possible to convert any turing machine program to a tiling of the plane using Wang tiles. The book contains an example tiling which calculates the Fibonacci numbers. The procedure, recipe, to convert a Turing machine program to a set of Wang tiles is not entirely clear to me.

Question: What is the algorithm to convert a Turing Machine program line by line to a set of tiling of the plane using Wang Tiles? And how does it work on the Turing machine in the given example?

Update:

Image is that of a Wang tile that adds 1 to a binary: 111 + 1 = 1000 where 1 is red, 0 is cyan. Aiming to generate tiles like this from any Turing Machine. First row 111, last row 1000.

(partial answer) via wikipedia, the conversion/reduction of TMs to Wang tiling was 1st proven in this paper, & there are possibly later simplifications:

Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).


Is this $\beta$-reduction well defined? Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it $\alpha$ and $y$. Namely:

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

but

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

I am afraid that I might be making considerable mistakes but this is only the case because I have been studying $\lambda$-calculus for just one day.

Thank you very much in advance for your comments and suggestions.

Beta-reduction is only allowed when the argument does not contain any free variable that is bound in the function. So before you can beta-reduce $(\lambda x. \lambda y.x) y$, you must rename the bound variable $y$ using alpha-conversion.

Formally speaking, beta-reduction and equivalence are defined not over lambda terms, but over lambda terms modulo alpha-conversion. So by performing alpha-conversion, you are not changing the term.

$$
  (\lambda x. \lambda y.x) y =_\alpha (\lambda x. \lambda z.x) y
  \to_\beta \lambda z.y
$$

An alternative approach is to treat terms syntactically, and allow the beta-reduction, but perform the alpha-conversion as part of the substitution. The two approaches can be shown formally to be equivalent (for almost all uses of the lambda calculus, this is an unimportant presentation detail).

$$
  (\lambda x. \lambda y.x) y \to_\beta (\lambda y.x)[x\leftarrow y]
  =_\alpha (\lambda z.x)[x\leftarrow y] = (\lambda x.y)
$$


Efficient Array Normalization I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this?

The runtime I achieve is 2N. Any better idea?

normalize(array)
{
   sum = 0;

   for i = 0 to array.size() do
      sum += array[i];
   end

   for i = 0 to array.size() do
      array[i] /= sum;
   end
}

Given that at least N "operations" are needed since each array element is affected, you can't get the number of operations down by much. It's not clear what your complexity measure exactly is – why is sum += array[i] a single operation? What about the loop? The actual CPU needs to increment i and compare it to array.size(), there are jumps involved and so on. The operation sum += array[i] is probably more than one instruction. Not to mention things you actually forgot to count, like sum = 0.

That said, I can't see how to improve on your algorithm, and I don't think it's possible, though as mentioned above, the notion of complexity is very shaky here, so perhaps there is a "trick" which will work under your complexity measure, whatever it is.


How is the loop invariant obtained in this square root bound finding algorithm? Originally on math.SE but unanswered there.

Consider the following algorithm.

u := 0
v := n+1;
while ( (u + 1) is not equal to v) do
   x :=  (u + v) / 2;
   if ( x * x <= n)
     u := x;
   else
     v := x;
   end_if
end_while

where u, v, and n are integers and the division operation is integer division.

Explain what is computed by the algorithm.
Using your answer to part I as the post-condition for the algorithm, establish a loop invariant and show that
the algorithm terminates and is correct.

In class, the post-condition was found to be $0 \leq u^2 \leq n < (u + 1)^2$ and the
Invariant is $0 \leq u^2 \leq n < v^2, u + 1 \leq v$.  I don't really understand on how the post-condition and invariants were obtained.  I figure the post condition was $u + 1 = v$... which is clearly not the case.  So I am wondering on how the post-condition and invariant was obtained.  I'm also wondering on how the pre-condition can be obtained by using the post-condition.

Gilles is right that the general technique is to go fishing for interesting observations.

In this case, you may observe that the program is an instance of binary search, because it has the following shape:

while i + 1 != k
  j := strictly_between(i, k)
  if f(j) <= X then i := j
  if f(j) > X then k := j

Then you just plug in your particular f, X, ... into the general invariant for binary search.  Dijkstra has a nice discussion of binary search.


Are all $\Sigma^0_1$ sets of infinite sequences infinite? I think I figured out some things about $\Sigma^0_1$ and $\Pi^0_1$ in the arithmetical hierarchy, for sets of infinite sequences, and I'm hoping I can get confirmation that I'm right, or can understand the ways in which my thinking is incorrect.
What I think I have figured out is that every set of infinite sequences in $\Sigma^0_1$ must be infinite in size--in fact uncountable--since a sentence containing only existential quantifiers over indexes into a sequence can only require that some digits satisfy a predicate.  Therefore, any sequence satisfying the sentence would do because of a property of a finite number of locations in the sequence.  All subsequent digits after those locations would be allowed to vary freely, in which case the number of sequences with the same initial pattern would be uncountable.
By contrast, sets of infinite sequences in $\Pi^0_1$ may be either be finite or infinite, I think.  For example:
$\{x: (\forall n)\, x[n]=0\}$ contains only one element, $000\ldots$ .
$\{x: (\forall n)\, x[n]=0$ if $n$ is odd$\}$ allows the digits at the even-numbered locations to vary freely, so the number of sequences that satisfy this predicate for all $n$ is uncountable.
Is this correct?  Are there ways in which I'm confused, or some obvious nuance that I'm missing?

First observe that any $S \subseteq \{0,1\}^\mathbb{N}$ described by a $\Delta^0_1$-formula is clopen (open and closed subset), where we topologize with the product topology. Indeed, the subbasic sets of the form $B_{i,k} = \{x \in \{0,1\}^\mathbb{N} \mid x(i) = k\}$ are clopen by definition, and then complements (negation), finite unions (disjunction and bounded $\exists$) and intersections (conjunction and bounded $\forall$) of those are still clopen.
A $\Sigma^0_1$ subset $S \subseteq \{0,1\}^\mathbb{N}$ is a countable union of $\Delta^0_1$ sets, therefore it is open. But every open subset of $\{0,1\}^\mathbb{N}$ is either empty, or it contains a basic open set and is therefore uncountable.


Create a turing machine for log base 2 of n How would someone create a Turing machine that computes ⌈log2(n)⌉?
I know that:
n = 1, 2, 3, 4, 5, 6, 7, 8, ...
f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...
And that I want the input tape to have n 1's in it to represent the number i.e. 8 would be
###11111111###
How would the the turing machine for this be created?

The value of $\lceil\log_2(n)\rceil$ is more or less equal to the number of bits in the binary representation of $n$ (except if $n$ is a power of 2).
You can then imagine a Turing Machine with an input tape (on which is written the number), a work tape and an output tape. First, you need to convert your unary number on the input tape, into binary on the work tape. This can be done with a simple incrementation Turing Machine (you can decide on the side of the least significant bit, but imho left is easier). Then, you need to count the number of bits in the binary number, and write a $1$ for each bit counted. You can use an additionnal state, to detect is the number is a power of 2 (a $1$ followed only by $0$).
This machine can be reduced to two tapes by replacing bits by $1$ on the work tape (except maybe for the last one which needs to become $\#$ if $n$ is a power of $2$). It can be further reduced to one tape by using the read part of the tape to write the binary number (and another symbol than $\#$ to replace the $1$ which are read).
Let's be more formal:
I consider a Turing Machine $(Q, \Sigma, \Gamma, \delta, q_0, q_f, \#)$ where $Q$ is the set of states of the TM; $\Sigma = \{1\}$ is the input alphabet; $\Gamma = \{0, 1, \\\$, \#\}$ is the work alphabet ($\\\$$ is a symbol to separate the input and the output), $\delta$ is the transition function, $q_0\in Q$ is the initial state, $q_f \in Q$ is the final state and $\#$ is the blank symbol. The Turing Machine I imagined is composed of 13 states, it may be possible to do better. Here is the detail on each state (to understand how the TM works) :

$q_0$: initial state
$q_1$: I have read only one $1$ in the input
$q_2$: I have read only two $1$'s in the input
$q_3$: I am reading another $1$ in the input ($q_1$ and $q_2$ make it easier to separate the input and the output)
$q_4$: I am returning to the most left to increment the binary representation
$q_5$: I am incrementing, and there is still a carry
$q_6$: I have finished incrementing, I return to the input to read $1$'s
$q_7$: I have finished reading completely the input, I am returning to the most left to transform the binary representation of $n$ into unary representation of $\lceil\log_2 n\rceil$
$q_8$: I am replacing $0$'s by $1$'s without having seen a single $1$
$q_9$: I am replacing $0$'s by $1$'s having seen a single $1$
$q_{10}$: I am replacing $0$'s by $1$'s having seen at least two $1$'s (therefore $n$ is not a power of $2$)
$q_{11}$: I have concluded that $n$ is a power of $2$, so the last $1$ must be replaced by $\#$
$q_f$: final state

Here is the detail of the transition function, state by state. The first column is the current state of the Turing Machine, the last 4 correspond to the read tape symbol. Each box is given as a triple $(\alpha, q, d)$ where $\alpha$ is the symbol written on the tape, $q$ is the next state and $d$ is the direction of the head shift.

State
$0$
$1$
$\\\$$
$\#$

$q_0$
-
$1, q_1, \rightarrow$
-
$\#, q_f, \rightarrow$

$q_1$
-
$1, q_2, \rightarrow$
-
$\#, q_{11}, \leftarrow$

$q_2$
-
$\\\$, q_3, \rightarrow$
-
$\#, q_{11}, \leftarrow$

$q_3$
-
$\\\$, q_4, \leftarrow$
$\\\$, q_3, \rightarrow$
$\#, q_{7}, \leftarrow$

$q_4$
$0, q_4, \leftarrow$
$1, q_4, \leftarrow$
$\\\$, q_4, \leftarrow$
$\#, q_{5}, \rightarrow$

$q_5$
$1, q_6, \rightarrow$
$0, q_5, \rightarrow$
$1, q_6, \rightarrow$
-

$q_6$
$0, q_6, \rightarrow$
$1, q_6, \rightarrow$
$\\\$, q_3, \rightarrow$
-

$q_7$
$0, q_7, \leftarrow$
$1, q_7, \leftarrow$
$\#, q_7, \leftarrow$
$\#, q_8, \rightarrow$

$q_8$
$1, q_8, \rightarrow$
$1, q_9, \rightarrow$
-
-

$q_9$
$1, q_9, \rightarrow$
$1, q_{10}, \rightarrow$
-
$\#,q_{11},\leftarrow$

$q_{10}$
$1, q_{10}, \rightarrow$
$1, q_{10}, \rightarrow$
-
$\#,q_f,\leftarrow$

$q_{11}$
-
$\#, q_f, \rightarrow$
-
-

Here is a simulation of this TM : http://turingmachinesimulator.com/shared/eikrrbjoiz


Could AI be used to detect when a human is picking survey response options randomly? Context: I am a clinical psych researcher dabbling in machine learning.
Humans cannot be truly random. Therefore, could machine learning be used to analyze a string of numbers and determine the probability that said string was generated by a human or by a computer? Taking it a step further, could machine learning be used to look at survey responses and determine the likelihood as to whether the participant was answering questions honestly, or whether they "Christmas-tree'd" either part of or all of the survey? If so, would this be dependent on the specific questions that each survey item asked, or simply on the type of survey question (e.g., Likert-type, sliding scale, ruler, yes/no or true/false questions, free response, etc.)?

AI is probably not the best tool for this job.  Several classical techniques in survey design include:

Consistency check: ask the same question in several ways, spread out across the survey, and check if they've answered consistently.

Open-ended questions: ask an open-ended question, see if they write nonsense or the bare minimum.

Attention check questions: e.g., "What is your favorite color?  Regardless of your favorite color, please pick the second option."  Beware that these are controversial and have pros and cons.

Recruitment: recruit subjects who are less likely to try to cheat you.  Pay them a reasonable wage for their time.

My experience is that it is easy to be overly worried about respondents answering dishonestly; if you follow basic good practices, the overwhelming majority of respondents will try to be helpful and won't try to cheat you.


Deciding whether set of running times is infinite I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$.

\begin{align}
\mathrm{Count}(M)= \{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly $k$ steps}\}.
\end{align}

I need to check whether the language $L$ is in RE, and whether it is in R.
$$L= \{ \langle M \rangle \mid \text{$\mathrm{Count}(M)$ is an infinite set}\}.$$

My idea for a solution starts with:
even though $L$ is an infinite language, it contains $\mathrm{Count}(M_i)$ that halts eventually. Each $M$ in $L$ must halt, and $\mathrm{Count}(M)$ is infinite.

So, in order to prove that $L$ is in RE, can I simply say every $M$ in $L$ halts eventually?

Suppose $L \in \textrm{RE}$.
Given a Turing machine $M$ you can construct another Turing machine $M'$ that takes an input $x$ and simulates $M$ on an empty input for at most $|x|$ steps.

If $M$ eventually halts, say after $c$ steps, $M'$ will always halt after at most $f(c)$ steps, (for some function $f$), regardless of the choice of $x$. This shows that $\textrm{Count}(M') \subseteq \{ 1, \dots, f(c) \}$ is a finite set.

If $M$ does not halt, then $M'$ will halt after simulating $|x|$ steps of $M$ for every choice of $x$. By picking different values of $x$ it is possible to build an infinite set of inputs such that each input results in a different running time of $M'$ (e.g, start with $x=$"1" and let $s$ be the number of steps taken by $M'$ on input $x$. The next value of $x$ will be a string of $s+1$ ones, so that $M'$ necessarily halts after some number $\ell$ of steps such that $\ell \ge s+1$. The next value of $x$ will have $\ell+1$ ones, and so on).

This shows that $\textrm{Count}(M')$ is an infinite set.

Therefore, since $L \in \textrm{RE}$ you have just found a way to accept all (and only) the Turing machines $M$ that do not halt on an empty input, showing that the complement of the halting problem is in $\textrm{RE}$.
This is a contradiction as it would imply that the halting problem is in $\textrm{R}$.


Complexity of cyclic sort I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$:

Input: A[1], ..., A[n]
i ← 1
while i ⩽ n:
  j ← A[i]
  if A[i] ≠ A[j]:
    swap A[i] and A[j]
  else:
    i ← i + 1
  end if
end while

How can I prove that in worst case, the running time of this algorithm is still asymptotically $O(N)$?

My observation:

Although $i$ will not increase right after each swap, when it does increase, the next number of required swaps will also decrease.
The maximum number of swaps at $i = 1$ will be $N-1$.

Second question is: Is the running time still $O(N)$ if it contains duplicate numbers?

We can write each permutation of $1,\ldots,n$ in cycle notation, which will help us understand the behavior of the algorithm.

Suppose that $i = 1$. If $1$ is a fixed point, then the algorithm simply moves on. Otherwise, suppose that the cycle involving $1$ is $(1\;a_2\;a_3\;\cdots\;a_\ell)$, which means that $a_2 = A[1]$, $a_3 = A[2]$, ..., $a_\ell = A[a_{\ell-1}]$ and $1 = A[a_\ell]$. The algorithm will exchange $A[1]$ and $A[a_2]$, so that $A[1] = a_3$ and $A[a_2] = a_2$. This has the effect of removing $a_2$ from the cycle. After $\ell-1$ such steps, the cycle is no more, and $i$ will be increased.

If the permutation has cycles of lengths $\ell_1,\ldots,\ell_r$, then the total number of swaps performed by the algorithm is $(\ell_1-1) + \cdots + (\ell_r-1) = n-r \leq n-1$. This explains your observation that the maximum number of swaps is $n - 1$.

At each iteration of the main loop, either we perform a swap, or we increase $i$. The former can happen at most $n-1$ times, and the latter at most $n$ times. Since each iteration runs in time $O(1)$, in total the algorithm runs in $O(n)$.


Do undecidable languages exist in constructivist logic? Constructivist logic is a system which removes the Law of the Excluded Middle, as well as
Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't allow for proof by contradiction.

I'm wondering, is anyone familiar with how this affects results regarding Turing Machines and formal languages? I notice that almost every proof that a language is undecidable relies on proof by contradiction. Both the Diagonalization argument and the concept of a reduction work this way. Can there ever be a "constructive" proof of the existence of an undecidable language, and if so, what would it look like?

EDIT: To be clear, my understanding of proof by contradiction in constructivist logic was wrong, and the answers have clarified this.

Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works.

Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the form "P and not P", but of the form "x = x + 1".

Of course, now you might be wondering whether constructive logic admits "x = x + 1" as a contradiction. It does. The main property of a contradiction is that anything follows from a contradiction, and using "x = x + 1", I can indeed constructively prove "x = y" for any two natural numbers.

One thing which might be different about a constructive proof is the way in which "undecidable" is defined. In classical logic, every language must either be decidable or undecidable; so "undecidable" simply means "not decidable". In constructive logic, however, "not" isn't a primitive logical operation, so we cannot express undecidability this way. Instead, we say that a language is undecidable if assuming that it is decidable leads to a contradiction.

In fact, even though "not" isn't a primitive in constructive logic, we typically define "not P" as syntactic sugar for "P can be used to construct a contradiction", so a proof by contradiction is actually the only way to constructively prove a statement of the form "not P" such as "language L is undecidable".


Algorithm to reconstruct sentence from shuffled string Given a dictionary of words, and given a string which is an anagram of concatenation of group of words from the dictionary, is there an efficient algorithm to find valid set of  words that can form this string ?

eg1: dict = [ 'dog', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ]

If we join the words in the answer to form the string, we can see that it is an anagram of the input string s

eg2: dict = [ 'dog', 'act', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ] or [ 'act', 'cat', 'dog' ] or [ 'act', 'act', 'dog' ]

In the above case any of the above list is valid as the string formed by them is an anagram of the input string s

We can brute force but there seems to be overlapping sub problems. Can this be solved in polynomial time ?

This is NP-hard, so it's very unlikely there's a polynomial-time solution.  To see this, notice that any instance of the NP-hard problem Exact Cover can easily be encoded as an instance of your problem in such a way that there is a solution to this encoded instance if and only if there is a solution to the original Exact Cover instance.


Predicting next action to take to reach a final state Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data?

For example, a robot starts at a certain state, then takes an action to get to another state. This occurs continuously for many iterations (imagine the robot is randomly exploring a room). If the robot is at a specific starting state, and I desire the robot to end up in a different state, is there an algorithm that could recommend the best next action (or set of next actions) to take to reach that final desired state?

One approach I've tried is to use a neural network with the current state and the next state being the input and the action to get from the current state to the next state being the output. The network would know for a single state how to get to a next desired state that is one action away. The issue is, what if the desired state is many actions away?

You can represent the problem as a directed graph where the nodes are the states and the edges are the action that signifies the transition from one state to another if the action is performed. Once this is done you can use various graph path finding algorithms to find the sequence of actions to reach a specific state from a starting state.


Techniques to prove a language is not DCFL I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL.

Are there any other techniques that will help me to prove a language L is not DCFL?

There is a direct type of argument, related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). Then if one input string is the prefix of another, the computation for the longer string must have the shorter computation as prefix. Thus, the computation accepts at (at least) two moments.

As an example, $\{ a^n b^m \mid n\ge1, m=n \mbox{ or } m=2n \}$ is not DCFL; which is seen as follows.

Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewire $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\{ a^nb^nc^n\mid n\ge 1\}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.


Solving membership problem for a PDA-generated language without converting the PDA to a CFG The classic solution for the membership problem of a language generated by a PDA is to convert said PDA to a CFG and then to use CYK or a similar algorithm. I was wondering if there are any known algorithms to solve this problem without a conversion to a CFG.

My attempt at a naive solution was to "emulate" a PDA, but if there's a transition of form $(q, \varepsilon, A, q, AA)$, then the stack grows infinitely and emulation never halts.

Yes, it is possible.   Given a pushdown automaton $P$ and a word $x$, you can easily construct a new pushdown automaton $P'$ such that $L(P') = L(P) \cap \{x\}$.  This works by using a product construction to expand the finite-state control of $P$ by a factor of $n$, where $n$ is the length of $x$.

Now, you can test whether $P$ accepts any non-empty word.  One way to do this is by computing the set of all reachable configurations of $P$.  This set is an infinite set, but it turns out to be a regular set, and you can construct a finite automaton that represents the set of reachable configurations.  One way to do that is using an algorithm for computing post*; see Section 2.2.2 of Analysis Techniques for Information Security, by Anupam Datta, Somesh Jha, Ninghui Li, David Melski, and Thomas Reps.  (You can view this as an improvement to Tomita's algorithm that works for arbitrary PDAs, not merely the ones that arise from a LR(k) parser.  Cycles are not a problem.)

This may be morally isomorphic to converting $P$ to a context-free grammar, intersecting that grammar with the regular language $\{x\}$ using the product construction, and then using standard algorithms to test whether that generates a non-empty language.  That in turn may be morally isomorphic to converting $P$ to a context-free grammar and then using CYK parsing.

The running time of all of these methods is $O(n^3)$, so while the algorithm looks different on paper, it does not lead to any improvement in running time.  The PDA-based approach does have the advantage that it is easily adapted to on-the-fly processing of the word $x$.


Worst case bisection of binary tree My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.

Nobody said that $3/4$ was the optimal number. In fact, it seems like $2/3$ might be achievable. Starting at the root, consider a walk which always chooses the child with the larger subtree. Consider the first time that you reach a node whose subtree contains less than $2/3$ of the nodes. Its parent's subtree contains more than $2/3$ of the nodes, so the subtree rooted at its larger child contains at least $1/3$ of the nodes. So we have found a node whose subtree contains between $1/3$ and $2/3$ of the nodes.

Considering the tree with one root and two children, we see that we can't in general obtain a better balanced partition.


Long multiplication school method: number of primitive operations to calculate first partial product? Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long multiplication.

I have read in my introductory book (Mehlhörn's 'Algorithms and Data Structures') that each partial product requires 2n + 1 primitive operations.

Now I understand, I think, where the +1 comes from for the first partial product at least, as in there being one extra digit in the result for the first partial product, but I don't understand why it is "2n" + 1, as it seems to me it would be more like n + 1, so I am defintely missing something important here. By 'partial product', I mean the result arising from the first intermediate calculation of the multiplication problem.

I am of course also totally confused about quantifying the rest of the primitive operations required to get the final result/product! But I would just like to understand where the 2n is coming from for now for the first partial product. Just to add my guess from what I have seen in addition: does the 2 in 2n refer to a maximum guiding number, rather than a definitive one?

Here is a link to the chapter in the book I am learning from: http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Appetizer.pdf

I understood primitive operations to mean: addition and multiplication.
The author does write at bottom of pg.1

"...we have two primitive operations at our disposal: the addition of three digits with a two-digit result (this is sometimes called a full adder), and the multiplication of two digits with a two-digit result"

The product of two n-digit numbers when they multiplied together needs then: 3n^2 + 2n primitive operations.

It is the algorithm as per the method taught at school for long multiplication problems.

(All of this is on pgs 1 and 2 of chapter)

Perhaps the following example will be useful. Suppose that $n = 3$, and we want to multiply $a_2 a_1 a_0$ by $b$. We first compute
$$
\begin{align*}
a_0 \times b &= c_0 d_0 \\
a_1 \times b &= c_1 d_1 \\
a_2 \times b &= c_2 d_2
\end{align*}
$$
(Here $c_0 d_0$ is a two-digit integer.)
So far we have done 3 operations (for general $n$, this will be $n$ operations).

Now we wish to perform the addition
$$
\begin{array}{cccc}
0&d_2&d_1&d_0\\
c_2&c_1&c_0&0 \\\hline
r_3&r_2&r_1&r_0
\end{array}
$$
The book states that you need 4 operations for this (and in general, $n+1$), though 2 are enough (in general, $n-1$):
$$
\begin{align*}
r_0 &= d_0 \\
s_1 r_1 &= d_1 + c_0 \\
s_2 r_2 &= d_2 + c_1 + s_1 \\
r_3 = s_2
\end{align*}
$$
Here $s_1,s_2$ are carry bits, and the first and last operations are for free (though the author charges one operation for each).

Summarizing, if you only charge addition and multiplication, only $2n-1$ operations are needed. If you also charge moves, $2n+1$ operations are needed. (The moves can be eliminated, though. Exercise.)


IF A is reduced to B and B belongs to NPC then where does A belongs to? i came across a question with no proper explnation.
IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P.
i know why it is as harder as NHP but i am not able to figure out about P class.

according to me if A > B(A polynomial time reducible to B) and B belongs to NPH then A is as easier as NPC and as harder as NPH.
A cannot belong to P since if A belongs to P then then in polynomial time i can solve P and in additional polynomial time i can reduce the results of A to suffice results of B.but as given B belongs to NPH and thus no polynomial time algorithm exists to solve B. which is contradiction to the assumption of A belongs to P.
can someone explain what mistake am i making?

If A reduce to B and B belongs to NPC, then surely A is in NP, but may or may not be NPC. A belongs to P is another question. If there given P = NP, then A would be belongs in P also.


Proof that $(L_{all})^C$ is not recursively enumerable The problem:

We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$

Hence, $L_{all}$ is the set of all encoded Turing machines (the $\operatorname{Kod}()$ is the encoding function) which accept all words as input.

One needs to show that $(L_{all})^C$, the complement of $L_{all}$ is not in $\mathcal{L}_{RE}$, that means it is not recursively enumerable.

By definition, in $(L_{all})^C$ we have all strings which do not represent correctly encoded Turing machines as well as encoded Turing machines which reject at least one word from the alphabet.

What have I tried so far:

One idea was to use the diagonalization argument that can be used to prove that $L_{diag}$, the diagonal language is not recursively enumerable. This however doesn't seem to work.
I tried to prove that the statement is wrong (i.e. $(L_{all})^C)$ is recursively enumerable: The proof would more or less go like this (not very formal): Let $A$ be a Turing machine deciding if $x \in  (L_{all})^C$. We first check if $A$'s input is a correctly encoded Turing machine ($x = \operatorname{Kod}(M)$), if not we reject. If it is, we associate every word from $\Sigma^*$ with a prime $p$ and then use this to simulate all words on $M$ at once, (in the $p^i$th step of $A$ we simulate the $i$th step of $M$ on the $p$th word). This is where my counter proof fails. Since there are uncountably infinitely many words in $\Sigma^*$ and only countably infinitely many primes. However I do not see a way how I can use this fact to prove the original statement.

Any suggestion or hints would be greatly appreciated since I am genuinely interested how one approaches such a proof.

Full disclosure
 This was a bonus question on an old exam (not connected to homework) and I am curious how one can prove this, especially since it seems to be somewhat counter intuitive.

Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input.

Here is a computable reduction from HALT to $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in L_{all}$. This shows that $L_{all}$ cannot be co-r.e. Indeed, if $L_{all}$ were co-r.e. then HALT would be co-r.e. Since HALT is also known to be r.e., it would be recursive; but we know that HALT is not recursive.

Here is a computable reduction from HALT to the complement of $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which on input $n$ runs $T$ on the empty input for $n$ steps; if $T$ halted, $T'$ enters an infinite loop, and otherwise $T'$ halts. You can check that $T \in \mathrm{HALT}$ iff $T' \notin L_{all}$. This shows that $L_{all}$ cannot be r.e. Indeed, if $L_{all}$ were r.e. then HALT would be co-r.e., and we get a contradiction like in the preceding paragraph.

In fact, $L_{all}$ is $\Pi_2$-complete; it is sometimes known as TOT or TOTAL. Thus $L_{all}$ is stronger than HALT, which is only $\Sigma_1$-complete.


Has the concept of using a hand checked simple theorem prover to validate more complex theorem provers been explored before? More specifically, has anyone used a chain of theorem provers to validate a highly evolved theorem prover, starting with a very simple hand checked prover such that each new theorem prover is used to validate a somewhat more complex theorem prover, rinse repeat?

This would be something along the lines of induction, I guess. In that you'd have just as much confidence in the complex prover at the end as the hand checked prover you started with.

If it has been explored (wouldn't be surprised), a pointer towards more resources would be welcome.

Not that I know of.  A more typical architecture is to decompose the theorem prover into a prover plus a proof checker.  Then only the proof checker needs to be validated.  If proofs are expressed in a simple enough language, then the proof checker might be extremely simple.  All of the smarts can go into the prover (which tries various strategies to try to find a valid proof), but it doesn't need to be validated, since its output will always be checked by the proof checker.


Turing Reduction vs Karp Reduction When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages?

I've read about Karp Reduction mainly used in the Context of reducing a Language:

e.g. L1 $≤_p$ L2

The huge difference is that a Turing reduction allows you to call the black-box more than once. Suppose you have the $\mathtt{GraphColor?(G, k)}$ decision problem which tells you if the graph $G$ can be colored with $k$ colors. A Karp reduction only allows you to call this problem exactly once. But a Turing reduction allows you to call $\mathtt{GraphColor?(G, k)}$ a polynomial number of times. So if you want to figure out the chromatic number of the graph, call the function with $k=1, k=2, \ldots$ and so on until you get something that works. To make it more efficient, use binary search instead.


Distance vector in a weighted graph I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv_i$ is the shortest distance from $1$ to $i$. All edge weights are positive integers. I have to show that every distance vector $Dv$ satisfies:

$Dv_1 = 0$.
For all $j \neq 1$ there exists $i$ such that $Dv_j = Dv_i + w(i,j)$.
For all $i,j$ it holds that $Dv_j \leq Dv_i + w(i,j)$.

I think that 1 is trivial: from 1 to 1 you have no distance. But the rest? Can you give me an idea how to prove 2 and 3?

Hint for 2: If $1,\ldots,i,j$ is a shortest path from $1$ to $j$ then $1,\ldots,i$ is a shortest path from $1$ to $i$.

Hint for 3: If $1,\ldots,i$ is a path from $1$ to $i$ then $1,\ldots,i,j$ is a path from $1$ to $j$.

In both cases $\ldots$ represents some list of vertices.


Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces Imagine a finite $n*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can detect a simple cycle in $H$ in linear time. However, such a search cannot efficiently find all simple cycles in $H$ as the number of cycles can grow exponentially (?) with the numer of vertices of $H$.

Remark: Since I'm referring to a square grid graph, we have maximum degree 4 for the vertices of $H$. Furthermore, $H$ does not have to be strongly connected. It does not have to have a "reasonable" data structure.

I wonder: What is the time complexity for finding the simple cycle, should it exist, that encloses (surrounds) the most faces? That simple cycle $C(V'',E'')$ is of course itself a subgraph of $H$.

Edit: I would like to add that the very same problem but with a directed graph is also of interest! :-)

Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time.
You can find the number of faces in each component by Euler's identity. This can be done in linear time per component.
Pick the component with the largest number of faces and find the cycle bordering that component. This can be done with a single line sweep, which is $O(V' \log V')$.


Finding all soldier wins Consider the following game (see also this question):
One day a castle is attacked at sunrise (by surprise) by n soldiers.
Each soldier carries a canon and a rifle.
The castle has strength s.
On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points).
After all the soldiers have fired, the castle sends dpw defenders to battle them.
In the ensuing days the castle and the soldiers battle it out following these rules:

All the soldiers fire first. A soldier can fire his canon at the
castle or his rifle at one of the defenders (but not both and each
soldier can only shoot once). One shot at a defender kills him. One
shot at the castle decreases its strength by 1.

Then each of the d defenders shoots at one soldier (and only
one) killing him.

If the castle still has strength points (i.e. s>0) it sends a
new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.

Repeat 1 through 3 on each new day.

If all soldiers are killed by the defenders, the castle wins.

If there are zero defenders after the soldiers shoot and the
castle strength is zero, the soldiers win.

The answer to this question gives the strategy the soldiers should follow to win in a minimum number of rounds.
If $$n\leq s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n$$, the strategy that leads to a victory for the soldiers in the minimum number of rounds consists of the soldiers shooting only at the castle in the first and second days and destroying it, and from then on, the soldiers trade fire with the remaining defenders winning in a total of
$2+\max(k,0)$ days, where
$$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
If $dpw<n$, the soldiers can win in a minimum of $c+\max(k,0)$ days, where
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$
and
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
In this case they shoot, in each round, at the defenders first then the castle for $c$ days which is the time it takes to destroy the castle.
What is an algorithm to find systematically all the strategies that lead to a win by the soldiers not just the minimum day strategy?
For example if $n=10, s=12, dpw=10$, there are 2 solutions in which the soldiers win:
The first where the number of soldiers, defenders and castle strength goes like this (in 3 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
round2:'soldiers': 8, 'defenders': 2, 'castle-strength': 0
round3:'soldiers': 8, 'defenders': 0, 'castle-strength': 0

and the second solution where it goes like this (4 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 1
round3:'soldiers': 6, 'defenders': 3, 'castle-strength': 0
round4:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

(in the particular case where $dpw=n$, like in the example above, there is an infinite number of solutions as @rotia points out, where the 10 soldiers eliminate the 10 defenders in either the 3rd or 4th or 5th... round before destroying the castle)

In the case $n\leq s<2n,dpw\geq n, 2n<dpw+s<(\phi+1)n$, a possible way of finding all soldiers wins is following this approach:

Have the soldiers attack only the castle in the first 2 days, then
once destroyed attack the defenders on the subsequent days. This
gives you the minimum number of days solution.
Have the soldiers attack the castle on the first day, then have
$n-1$ of the soldiers attack the castle on the second day and $1$ of
the soldiers attack the defenders on that second day. Finally
destroy the castle on the third day and let the soldiers battle it
out in the remainder of the days. This gives you the minimum number
of days solution+1 (if there is one).
Have the soldiers attack the castle on the first day, then have
$n-2$ of the soldiers attack the castle on the second day and $2$ of
the soldiers attack the defenders on that second day. On the third
day, the remaining soldiers but 1 attack the castle and the rest
attack the defenders. Finally on the fourth day the remaining
soldiers destroy the castle and let the soldiers battle it out in
the remainder of the days. This gives you the minimum number of days
solution+2 (if there is one).
etc
The basic idea of this approach is to consider the cases where the castle is destroyed on day 2, on day 3, on day 4, etc

For this to work well it would be useful to know not just the minimum number of days it takes for the soldiers to win but also the maximum number of days it takes. It might be possible to find this mathematically.

Also note that there are cases like this

solution 1 (3 rounds)

  start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

  round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

  round2:'soldiers': 6, 'defenders': 4, 'castle-strength': 0

  round3:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

solution 2 (5 rounds)

  start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

  round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

  round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 3

  round3:'soldiers': 4, 'defenders': 5, 'castle-strength': 0

  round4:'soldiers': 3, 'defenders': 1, 'castle-strength': 0

  round5:'soldiers': 3, 'defenders': 0, 'castle-strength': 0

i.e. there might be gaps (there is no solution in 4 rounds)


Conventions on NP regarding certificates with length exponential in a variable $k$ Non-computer scientist here.  Suppose you have a problem of the following general form:

  There is a class of objects, and a restricted set of moves to pass between objects.  It is known that all such objects are related by this set of moves.  There's a problem of the form "Given two objects $X_1$ and $X_2$, can you move between them in at most $k$ moves?"

An example would be where the objects are graphs on the same number of vertices, and the moves are deletion and addition of edges.  This question is obviously NP in the sense that you can just list the additions/deletions made to get a certificate.

Now the problem is if there is no a priori upper bound on how many moves you might need to move between two objects.  In the previous example, If the graphs have $n$ vertices then you need at most $n(n-1)/2$ additions/deletions to pass between any two graphs (going from $n$ disjoint vertices to the complete graph on $n$ vertices).  Thus, asking the question with very large $k>n(n-1)/2$ can be answered easily, so the problem is in NP regardless of $k$.

However, if there is no such bound, then maybe $k$ could be very large compared to the size of your objects, requiring a large certificate compared to the size of the input (since $k$ only needs $\log k$ bits).  So if $k$ is fixed before the statement of the problem then it is in NP, but if $k$ is given together with the input then it is not.

What's the convention for dealing with this type of situation?  Do you just say that the problem is NP for any fixed $k$?

No, you don't say it is NP for any fixed k, since that's not right; NP means something specific, and that's not it.  Instead, I would suggest that you describe the situation, as you did, in a self-contained way, since your definition is different from the ones where we have existing terminology.


How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$? Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the number of disk accesses?

Are there known algorithms for this problem? I searched for external matrix multiplication etc. but couldn't find much.

"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access.

From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012):

  Blocking a matrix multiply routine works by partitioning the matrices
  into submatrices and then exploiting the mathematical fact that these
  submatrices can be manipulated just like scalars.

"The cache performance and optimizations of blocked algorithms" by Lam, Rothbrg, and Wolf (1991):

  ...presents cache performance data for blocked programs and evaluates
  several optimizations to improve this performance.

More lecture notes:

Matrix Computations (CS 6210): Week 1 by David Bindel (accessed
Feb 23, 2016)
CS 267 Applications of Parallel Computers Lecture 2:
Memory Hierarchies and Optimizing Matrix Multiplication by James
Demmel (accessed Feb 23, 2016)


Skolemization with multiple arguments -- how to unify Edit:  answerers keep finding (valid!) problems with my example.  I'll try again.  The older version is below the horizontal line.  Thanks to Klaus below for pointing out the last problem.

My question is how to unify skolemizations that have differing numbers of arguments.  As he points out, there is rarely any need for this.  For example, if the statements are

Some homes are blue.
There is a home with two stories.

The skolemizations here should not unify, because we can't know from this if a blue home is two-storied.

If we're going to ever need to unify one skolemization with another, we'll need to know we're talking about the same home.  This would do it:

Jane's and Mark's home is blue (their only home).
Jane's home has two stories (her only home).

Here it is in FOPC:

$$
    \exists x: has(Jane,x) \wedge has(Mark,x) \wedge home(x) \wedge blue(x) \wedge
$$
$$
(\forall y: has(Jane,y) \wedge home(y) \implies x=y) \wedge
$$
$$
(\forall y: has(Mark,y) \wedge home(y) \implies x=y)
$$
and
$$
    \exists x: has(Jane,x) \wedge home(x) \wedge twoStories(x) \wedge (\forall y: (has (Jane,y) \wedge home(y) \implies x=y)
$$

Converting to conjunctive normal form with skolemization gives us this set:

$$
    has(Jane,skolem1(Jane,Mark))
$$
$$
    has(Mark,skolem1(Jane,Mark))
$$
$$
    home(skolem1(Jane,Mark))
$$
$$
    blue(skolem1(Jane,Mark))
$$
$$
 \neg has(Jane,y) \vee \neg home(y) \vee skolem1(Jane,Mark) =y
$$
$$
 \neg has(Mark,y) \vee \neg home(y) \vee skolem1(Jane,Mark)=y
$$

$$
 home(skolem2(Jane))
$$
$$
 twoStories(skolem2(Jane))
$$
$$ \neg has (Jane,y) \vee \neg home(y) \vee skolem2(Jane)=y
$$

Now, if I want to reason about whether there's a blue house with two stories -- which I should be able to start by resolving the first and last clauses in the set -- I can't, because the two skolemizations can't unify: they have different numbers of arguments.

Is there a good protocol of picking arguments to prevent this problem -- other than applying human intelligence after the mismatch is noticed?

Here is the old version.  It's significantly different, but as Klaus pointed out, the old version simply doesn't give us a skolemization problem (or even a skolem for the first statement):

"Everybody who has a home pays utilities on it," encoded as

$$
     \forall x: has(x,skolem1(x)) \wedge home(skolem1(x)) \implies paysUtilsOn(x, skolem1(x))
$$
or
$$
    \bar has(x, skolem1(x)) \vee ~home(skolem1(x)) \vee paysUtilsOn(x, skolem1(x))
$$
and "Jane and Mark have a home," encoded as
$$
    has(Jane,skolem2(Jane,Mark)) \wedge has(Mark,skolem2(Jane,Mark)) \wedge home(skolem2(Jane,Mark))
$$
or
$$
    has(Jane,skolem2(Jane,Mark))
$$
$$
has(Mark,skolem2(Jane,Mark))
$$
$$
    home(skolem2(Jane,Mark))
$$

I want to use resolution to prove Jane pays utilities.  The problem is that skolem1 has 1 argument and skolem2 has 2 arguments, so they don't unify.

I'm not sure if this matters -- could I just refer to skolem1 and skolem2 and forget the arguments entirely?  If it does matter, how do I resolve the problem so that skolem1 and skolem2 can unify, and resolution can work?  Not by finding a way around the problem, but by truly using skolemization correctly.  The issue is what to do with skolems that have different argument lists if they seem to occur naturally.

"Everyone has a heart" gets first encoded first as $\forall x. \text{Person}(x) \Rightarrow \exists y. \text{Hart}(y) \wedge \text{Has}(x,y)$. Then you get the Skolemization (that you found in RN) from that.

Now "Everybody who has a house pays utilities" is just $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ because there is no assertion that anything exists in this statement. However, if you want to spell out what houseowner means, $\forall x.\text{Houseowner}(x) \Leftrightarrow (\text{Person}(x)\wedge\exists y.\text{House}(y) \wedge Has(x,y))$. And you can skolemize that... but it's not even needed for what you want to infer.

As to "Jane and Mark have a house", it's actually a bit ambiguous. Do they have the same house? But that's an irrelevant detail if you just encode $\text{Houseower}(\text{Jane}) \wedge \text{Houseower}(\text{Mark})$. From that it immediately follows that $\text{Houseower}(\text{Jane})$ and using $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ it follows that $\text{PaysUtilities}(\text{Jane})$ with the obvious unification $x=\text{Jane}$.

As you can see, the definition of houseowner (which asserts the existence of a house etc.) is completely irrelevant to the inference you wanted. In general, not every "has" in the English language gets translated into a binary predicate, unless it's relevant to what you want to prove. Nobody managed to invent a rigorous way to formally and universally translate all of English (or any other natural language) into first-order logic. While there are some guidelines, a translation of a problem statement from natural language to FO ultimately uses a problem-specific encoding method.

Also note that your first sentence "Everybody who has a house pays utilities" bears some resemblance to a donkey sentence, but it's not actually one; you'd have to say "Everybody who has a house pays utilities on it" to get a donkey sentence.


A Case Distinction on Dynamic Programming: Example Needed! I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See for example Cormen, Leiserson et al: "Introduction to Algorithms" for an introduction.

I focus on the table-based computation scheme in two dimensions (row-by-row filling) and investigate the structure of cell dependencies, i.e. which cells need to be done before another can be computed. We denote with $\Gamma(\mathbf{i})$ the set of indices of cells the cell $\mathbf{i}$ depends on. Note that $\Gamma$ needs to be cycle-free.

I abstract from the actual function that is computed and concentrate on its recursive structure. Formally, I consider a recurrrence $d$ to be dynamic programming if it has the form

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

with $\mathbf{i} \in [0\dots m] \times [0\dots n]$, $\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$ and $f$ some (computable) function that does not use $d$ other than via $\widetilde{\Gamma}_d$.

When restricting the granularity of $\Gamma_d$ to rough areas (to the left, top-left, top, top-right, ... of the current cell) one observes that there are essentially three cases (up to symmetries and rotation) of valid dynamic programming recursions that inform how the table can be filled:

The red areas denote (overapproximations of) $\Gamma$. Cases one and two admit subsets, case three is the worst case (up to index transformation). Note that it is not strictly required that the whole red areas are covered by $\Gamma$; some cells in every red part of the table are sufficient to paint it red. White areas are explictly required to not contain any required cells.

Examples for case one are edit distance and longest common subsequence, case two applies to Bellman & Ford and CYK. Less obvious examples include such that work on the diagonals rather than rows (or columns) as they can be rotated to fit the proposed cases; see Joe's answer for an example.

I have no (natural) example for case three, though! So my question is: What are examples for case three dynamic programming recursions/problems?

There are plenty of other examples of dynamic programming algorithms that don't fit your pattern at all.

The longest increasing subsequence problem requires only a one-dimensional table.
There are several natural dynamic programming algorithms whose tables require three or even more dimensions.  For example: Find the maximum-area white rectangle in a bitmap.  The natural dynamic programming algorithm uses a three-dimensional table.
But most importantly, dynamic programming isn't about tables; it's about unwinding recursion.  There are lots of natural dynamic programming algorithms where the data structure used to store intermediate results is not an array, because the recurrence being unwound isn't over a range of integers.  Two easy examples are finding the largest independent set of vertices in a tree, and finding the largest common subtree of two trees.  A more complex example is the $(1+\epsilon)$-approximation algorithm for the Euclidean traveling salesman problem by Arora and Mitchell.


Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free? I cannot go on with this exercise:

  Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free.

Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > 0$ such that every $z \in L$ of size at least $N$ has a decomposition $z = uvwxy$ such that

$|vwx| \leq N$.
$|vx| \geq 1$.
For all $i \geq 0$, $z_i = uv^iwx^iy$ is in $L$.

Let's use $z= a^{2^N+1}b^N$.

Then
$|z| = 2{^N+1} +N > N$ and $v= a^h$ and $x= b^k$ with $1 \leq h+k \leq N$.

So $z_i = a^{2^N+1}a^{h(i-1)} b^{N-k}b^{k(i-1)}$.

So if there exists $i > 0$ such that $2^N+1+h(i-1) \leq 2^{N+(i-1)k}$, then $z_i \notin L$.

How can I go on to show that $L$ is not context-free?

According to Parikh's theorem, if your language were context-free, then the set S = $\{(n,m) : n > 2^m\}$ would be semi-linear. Every linear subset of $S$ has a constant second coordinate, as we show below. Therefore you need an infinite number of linear sets to cover $S$, showing that it is not semi-linear.

It remains to show that every linear subset of $S$ has constant second coordinate. Indeed, consider any linear subset of $S$. By definition, such a subset is of the form $u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_r$. By assumption there exists some $i > 0$ such that $u_i = (a,b)$, where $b \neq 0$. Let $u_0 = (n',m')$. It is not hard to check that for some $t$, $n' + at \leq 2^{m' + tb}$, since the left-hand side grows linearly, whereas the right-hand side grows exponentially. This contradicts the fact that the subset is a subset of $S$.


Bayes nets - calculating probabilities Given a Bayesian network, say a -> b -> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?

Bayesian networks encode a factorization of the joint probability distribution of a set of variables. Specifically, each variable is conditionally independent of all its non-descendants given its parents.

The joint probability distribution can be written as:

$P(X) = \prod_i P(X_i|Pa(X_i))$

where Pa(X) are the parents of X in the network.

You should be able to find the answer to your question by computing this quantity for your specific network and CPTs.


How to use succinct circuits to construct an EXPTIME complete problem? When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar for EXPTIME-completeness. Wikipedia mentions:

  Another set of important EXPTIME-complete problems relates to succinct
  circuits. Succinct circuits are simple machines used to describe some
  graphs in exponentially less space. They accept two vertex numbers as
  input and output whether there is an edge between them. For many
  natural P-complete graph problems, where the graph is expressed in a
  natural representation such as an adjacency matrix, solving the same
  problem on a succinct circuit representation is EXPTIME-complete,
  because the input is exponentially smaller; but this requires
  nontrivial proof, since succinct circuits can only describe a subclass
  of graphs.[8]

  8:  Papadimitriou (1994), section 20.1, page 492.

I understand the concept that you can describe some graphs using exponentially less space and use that as input, but I can't find the mentioned resource or find out how succinct graphs work exactly or how to construct an EXPTIME-complete problem.

Since you're having trouble getting hold of Papadimitriou's classic textbook Computational Complexity, let me suggest another resource: Papadimitriou's paper with Yannakakis, A note on succinct representations of graphs. They prove the following general result:

  Suppose that $L$ is a P-complete problem, and that there is a polytime reduction $f$ from the Circuit Value Problem to $L$ in which, given an input $x_1\ldots x_n$ of size $n$, the $j$th bit of $f(x)$ is, irrespective of $x$, either constant of equals some input bit or its negation. Then the succinct version of $L$, which consists of pairs $\langle n,C \rangle$, where $C$ is a circuit on $\lceil \log_2 n \rceil$ inputs, such that $C(0) \ldots C(n-1) \in L$, is EXPTIME-complete.

The hard part of the proof uses the construction in the Cook–Levin theorem.


Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators? Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators.

Is it the case that the construction of the SLR(1) parser and the LALR(1) always yield the same table?

If not, what happens if the grammar G is SLR(1)?

I'm particularly interested in this question about the following grammar:

\begin{align*}
    C &\to E \, \text{rel} \, E \mid C \& C \mid ! \, C \mid \text{pred}\, ( \,Es\, ) \\
    E &\to \text{num} \mid \text{id} \mid E\, +\, E \mid E\, *\, E \mid - \,E \mid ( \,E \,)  \\
    Es &\to E \mid E\, ,\, Es
\end{align*}

Using a custom SLR and LALR table generator I obtain exactly the same table for the above grammar, with some shift/reduce conflicts that can be resolved by giving precedences in the order &, !, rel, +, *, - and left associativity to &, + and *.  I'm in doubt whether my implementation is incorrect or the tables are really the same, and if this is the case whether there is some general rule that applies in certain circumstances.

If a grammar is SLR(1), then: [Note 1]

The SLR(1) and LALR(1) state machines will have the same states

The set of shift transitions in the two machines will be identical (as will the goto actions).

The set of accept transitions in the two machines will be identical.

The set of reduction actions in the LALR(1) machine will be a subset of the set of reduction actions in the SLR(1) machine.

In other words, it is possible for there to be a reduce action in the SLR(1) machine which is an error (or unspecified) action in the LALR(1) machine. In the case of an input which triggers such a reduce in the SLR(1) machine, that input will still eventually trigger an error before another shift transition is taken.
The difference comes from the fact that the SLR(1) algorithm generates a reduction action for a state with a reducible item for any lookahead in the follow set of the LHS of that item. The LALR(1) algorithm only includes the lookaheads which are feasible in the context of the state.
For example, here's a simple grammar:
\begin{align*}
S &\to A \, [ \, A\, ] \\
A &\to \epsilon \, \mid \, ( \, A \, )
\end{align*}
The follow set of $A$ is $ \{ ) , [ , ] \} $.
Now consider any state in which $A$ follows the dot. For example:
\begin{align*}
A &\to ( \, \centerdot A \, ) \\
A &\to \centerdot \\
A &\to \centerdot \, ( \, A \, )
\end{align*}
This state has a shift action on $($ and a reduction action for $A \to$. It's clear that the reduction action should only be performed if the lookahead is $)$; any other lookahead is an error. But since $[$ and $]$ are in the follow set for $A$, the SLR(1) algorithm includes reduction actions for those lookaheads as well. The error will be detected after the subsequent goto action in the state $A \to ( \, A \, \centerdot \, )$. In the LALR(1) table, these two lookaheads will lead directly to an error.
However, there are other entries in the LALR(1) table for this grammar in which the LALR(1) parser will also execute reductions with a lookahead which obviously cannot be shifted. Only in an LR(1) parser are errors detected immediately. (That's not a good reason to use a canonical LR(1) parser).
Notes

I take the view that if conflicting transitions are generated, then the construction algorithm fails and no parser is produced. That's the way the algorithms are described in Aho, Sethi & Ullman, for example (the so-called "Dragon Book"). If you take the equally valid view that a parser is always produced, but is not necessarily deterministic, then the following statements would be true for all grammars.


match an array with a given set of arrays We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values.

Then we're given an array X (this array is certainly part of our set) and we have to find to which array of our set it corresponds to.

Of course, we can check all 36 elements of X against each of 36 elements of our 24 arrays and find out with which it corresponds to.

I'm trying to reduce this number of 36 comparisons.

My naive approach is something like this:

Take all possible subsets of 0..35, except the empty subset.
Each of this subsets denotes which elements we should compare.
Use each of this subsets with input all the 24 arrays of our given set and check which of these subsets produce as output the given set of our 24 arrays, these are valid subsets.
From these valid subsets, the one with the fewer elements is our solution.

Unfortunately, all possible subsets of 0..35 excluding the empty subset is $2^{36}-1$

I was wondering if there could be another approach to the problem.

Many different arrays X will be matched against the given set of 24 arrays so any preprocessing of the 24 arrays is really worth the effort.

User JarkkoL suggested to precompute CRC32 of the set of the given arrays and then compare with the CRC32 of the array X.

Still, I'm wondering if there's a smart way not to calculate CRC32 for the whole array. I'm looking for the smallest possible number of elements for which I should compute it.

You could calculate something like crc32 of the arrays and compare them with the crc32 of the new array. If the crc32's of the arrays match then you can do further check if the elements actually match (in case there is crc32 collision, which is very rare). If you know the new array exists in the set, you could select crc32 seed value which avoids the crc32 collisions, so once you find the crc32 match you can be sure it's the correct one without comparing the elements at all (just test max 24 ints). You could try something more lightweight than crc32 too if that's a performance issue.

If you would really want to push this, you could then sort the arrays by the checksum value and find the matching checksum with binary search, thus cutting the number of comparisons to log2(24)=5. Maybe not worth it for such a small amount of arrays though.


Proving Big Omega of a polynomial without limits Here is the definition of $\Omega$:

  $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$.

Here is one theorem:

  If $f(n) = a_m n^m + \cdots + a_1 n + a_0$ and $a_m > 0$, then $f(n) = \Omega(n^m)$.

I want to prove this, without using limits. Despite many hours of searching across the internet, all I could find is proofs using limits. Is there any other way?

Define $M = \max(|a_0|/a_m, |a_1|/a_m, \ldots, |a_{m-1}|/a_m)$, and take $c = a_m/2$ and $n_0 = 2mM$. Then for $n \geq n_0$,
$$
\begin{align*}
f(n) &= a_m n^m \left(1 + \frac{a_{m-1}}{a_m} \cdot \frac{1}{n} + \cdots + \frac{a_1}{a_m} \cdot \frac{1}{n^{m-1}} + \frac{a_0}{a_m} \cdot \frac{1}{n^m}\right) \\ &\geq
a_m n^m \left(1 - \frac{M}{n_0} - \cdots - \frac{M}{n_0^{m-1}} - \frac{M}{n_0^M}\right) \\ &\geq
a_m n^m \left(1 - \frac{mM}{n_0}\right) \\ &=
c n^m.
\end{align*}
$$


Modelling using propositions, syntax and standards One of the first programs I wrote when learning Java was a console application modelling the operation of an elevator. I'm trying to teach myself propositional logic and so I thought, why not use the same example?

So, suppose I have been given the task of modelling the main functions of an elevator system using propositions and predicates...

Opening and closing doors (allowing entrance and exit at appropriate
times)
Storing and responding to floor requests from users
Processing information from sensors (elevator load, floor position
and speed sensors)
Displaying status information on the displays (at each floor and in
the cab)

My Google searches have returned very little in the way of useful insight into how this should be done or any standards that might exist. What would be the best way to do this?

Would something like this be appropriate?:

$$ F = requestedFloor, L = loadSensor(load), C = loadSensor(capacity) $$
$$ F ∧ L < C → move(F) ∧ display: print(currentFloor)  $$
$$ floorSensor(currentFloor) < F  → move(up)$$
$$ floorSensor(currentFloor) > F  → move(down)$$

Which is simple enough, right? If there is a floor requested and load is less than capacity then move to that floor. Also, print the floor to the display.

If anyone has any suggestions or can provide some examples of how I might model this I'd love to hear them.

Generally you have:

Some boolean variables that collectively represent the current state, say $s,t,u$.
Some boolean variables that collectively represents the inputs, say $i,j,k$.  For instance, you might have one variable per sensor (assuming each sensor returns a boolean value).
Some boolean variables that collectively represents the inputs, say $o,p,q$.  For instance, you might have one variable per actuator (assuming each actuator can be either on or off).
Some boolean variables that collectively represent the next state.  You could give them a different name (e.g., $x,y,z$), but often, to help us remember the relationship to the variables for the current state, we used primed versions of the variables for the current state.  So, the next state might be represented by $s',t',u'$.

Now, we introduce a predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ to represent the transition relation.  The idea is that if this is true, it means the following: if you're in state $s,t,u$ and you receive inputs $i,j,k$, then you output $o,p,q$ AND transition to the state $s',t',u'$.  You can use boolean logic to express the predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ as a boolean formula, using AND, NOT, OR, implication, etc.

Then you also need to describe the initial state of the system.  For instance, it might be $(s,t,u)=(T,F,T)$.

As you can see, the notation can get a bit much.  Often we collect all the variables associated with the current state into a vector $s$ of variables, $s=(s_1,\dots,s_k)$ where the state is $k$ bits (it is represented by $k$ boolean variables), and collect all of the variables associated with the input into a vector $i$ of variables, $i=(i_1,\dots,i_m)$; you similarly collect all the output variables into a vector $o=(o_1,\dots)$; and the next state is given by a vector $s'=(s'_1,\dots,s'_k)$ represents the next state.

As a generalization, you can consider variables that have more than two possible values (they aren't restricted to be booleans).  Booleans are convenient for digital logic implementation, but more general variables can enable a specification that is easier to think about and understand.

So, basically, yes, this is compatible with the kind of approach you were showing.


Hoare logic - partial/total correctnes and strength invariant I'm studying Hoare logic and I can't understand the relation between partial and total correctness regarding loop invariant. Suppose for example that I have the following program:

{X ≥ 0}
Y := 0;
Z := 0;
{Y =2Z}
while (Z ̸= X) do (
Z := Z + 1;
Y := Y + 2 )
{Y =2X}

The solutions says that for partial correctness I can use the invariant Inv = 2Z.
But when I have to prove total correctness the invariant must be strengthened with X - Z >= 0.
Which is the hoare logic property that let me strength the invariant, adding the condition to it, only for total correctness?

You're misunderstanding.  It's not that when you try to prove total correctness, Hoare logic somehow magically finds a stronger invariant for you.  Hoare logic doesn't find the invariant for you -- either way, you have to find the invariant yourself and then prove it.

Rather, it's that you need to prove a stronger invariant if you want to prove total correctness.  A weaker invariant can suffice to show partial correctness.  Therefore, total correctness can often be harder to prove than partial correctness (proving total correctness requires more work, because you have to prove a stronger, more detailed invariant).


Using two hash functions for increased password security? Forgive me for my brief knowledge on hash functions as I am not from a computer science background, however I am researching password security for my thesis and have been looking into hashing functions for password security. I understand that a password goes through a hashing function and is stored in a separate database, at which point if the user enters the same password at a later date, that entry is then ran through the same hashing function and checked the output is the same. My question is, if lots of companies are being breached and passwords have been found out using the algorithms, would it be more secure to then use a second hashing function on the already hashed password and store all the password entries 'double hashed'?

Simply hashed passwords are susceptible to brute force or rainbow table attacks.  Hashing the passwords again will simply increase the cost of computing an entry in these tables (by one hash), but that is not an appreciable increase in the challenge of cracking them.

Several techniques available in practice including salt ing the password, wherein you prepend the password with a random substring (known as the salt), which you also prepend (in plaintext) to the hash.  So, whereas a password "hello" might hash to h("hello"), the salted password would be foo || h("foo" || "hello").  If "foo" is random, then this means that I may need to store all possible salted hashes for a given password in order to crack it.

To complicate the crack-ability of the password hash even further, one may add a pepper, which is a random (but not published) string prepended to password before hashing.  Checking a password in this case requires checking all possible peppers with a given password to see if any hash to the stored hash value.


Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes? So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ by keeping track of the which squares are filled in the $n$th column, which gives $2^m$ cases to keep track of for each value of $n$, with the cases related between $n-1$ and $n$ based on how the empty spaces in the $(n-1)$th column are filled with horizontal and vertical dominoes. I was wondering, are there any significant improvements known for this type of recursion? For example can we take advantage of symmetry somehow and e.g. only keep track of the lengths of the contiguous filled squares and contiguous empty squares? Or other improvements? If improvements are possible, does it change the asymptotics of the number of cases that need to be tracked?

From my answer on math.SE:

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

$$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

You can find a nice exposition for the $1\times 2$ case in the first chapter of Kenyon's lecture notes.


The complexity of the reachability-coreachability analysis of a finite state machine Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is coreachable if there exists a string $s$ such that $\delta(q,s) \in Q_{m}$.

I'm wondering what is the computational complexity of the reachability-coreachability analysis of a FSM, as a function of $|Q|=n$.  In particular, the input is a FSM $A$, and I'd like the algorithm to output a list of all states that are reachable, and a list of all states that are coreachable.  What is the worst-case asymptotic complexity of this function, as a function of $n$?

Let $m\ge1$ be the size of the alphabet $\Sigma$.

Let us restrict our attention to the two most common models of finite state machines (FSM), deterministic finite automatons (DFA) and non-deterministic finite automatons (NFA). We know that FSM corresponds naturally to the directed multi-graph as explained by Wikipedia entry on state diagram.

A $n$-state $DFA$ $D=(Q,\Sigma,\delta,q_0,F)$ corresponds a directed multi-graph $G$, whose nodes are also $Q$ and all of whose nodes have outdegree $m$. Whenever we mention some $q\in Q$, it will be clear whether we mean the state $q$ in $D$ or the node $q$ in $G$. It takes $O(mn)$ time to convert $D$ to $G$.

The problem of determining all reachable states from state $q_0$ in $D$ corresponds to the problem of determining all reachable nodes from node $q_0$ in $G$. If we use the classic breadth first traversal starting from node $q_0$ to solve the later problem, the worst case happens when we have to go through all arcs in $G$, which is $\Theta(mn)$ time-complexity.  In fact, for any algorithm to determine the set of all reachable nodes, all edges must be checked.
The problem of determining all co-reachable states in $D$ corresponds to the problem of determining all reachable nodes from $q'$ in graph $G'$, where $G'$ is $G$ with all edges reversed and with one extra node $q'$ that is connected to all node $q_i\in F$. The conversion from $G$ to $G'$ takes $O(mn+n) = O(mn)$ time. If we use the classic breadth first traversal starting from node $q'$ to solve the later problem of all reachable nodes, the worst case happens when we have to go through all arcs in $G'$, which is $\Theta(m(n+1)=\Theta(mn)$ time-complexity. In fact, it is easy to see that asymptotically, solving the problem of co-reachability has the same worst-case time-complexity as solving the problem of reachability.

To summarize, the worse case to determine the reachability or co-reachability of a $n$-state DFA takes $\Theta(mn)$ time.

In this section, we will explain the exact meaning of the statement "all edges must be checked" for the case of reachable states.

(All edges by adversary) Let $G$ be a multi-graph $G$ of $n$ nodes and a start node $q_0$. Each node $q$ has exactly $m$ outgoing edges $\{q_\sigma\mid \sigma\in\Sigma \}$. The only way for us to know the other endpoint of $q_\sigma$ is to inquire from a truthful smart adversary $A$, who can config the other endpoint on the fly. Each inquiry must be "which node is the endpoint of $q_\sigma$ other than $q$?" for some $v$ and $\sigma$. The minimal number of inquiries needed to determine the set of reachable nodes from $q_0$ is $mn$.

Proof. Let $Q=\{q_0, q_1, \cdots, q_{n-1}\}$.

Here is $A$'s strategy to reply to the inquiry. Initialize $n$ empty set $S_q$, $q\in Q$. For an inquiry about $q_\sigma$ with $q=q_i$, there are five cases.

if $i\lt n-2$ and $\#S_q\lt m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
if $i\lt n-2$ and $\#S_q= m-1$, reply that $q_\sigma= (q,q_{i+1})$. Add $\sigma$ to $S_q$.
if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}\lt 2m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}= 2m-1$, reply $q_\sigma=(q_{n-2}, q_{n-1})$ when $q=q_{n-2}$ and reply $q_\sigma=(q_{n-1}, q_0)$ when $q=q_{n-1}$. Add $\sigma$ to $S_q$.
if $\#S_\sigma= m$, the inquiry must have been done before and, hence, reply the same as before.

I will leave the rest of the proof as an exercise.

Exercise 1. Finish the proof of "all edges by adversary". Show that $A$'s strategy is consistent in the sense that there is one such $G$ that all replies of $A$ are true. Furthermore, after $mn-1$ inquires, we cannot determine whether $q_{n-1}$ is reachable from $q_0$ or not.

Interested readers can do the following exercise that deals with NFA.

Exercise 2. the worse case to determine the reachability or co-reachability of a $n$-state NFA takes $\Theta(mn^2)$ time.


MDS minimization with gradient descent I have the following multiple dimensional scaling (MDS) minimization problem in vectors $v_1, v_2, \dots, v_n \in \mathbb R^2$

$$\min_{v_1, v_2, \dots, v_n} \sum_{i,j} \left( \|v_i - v_j\| - d_{i,j} \right)^2$$

which I wish to solve numerically using gradient descent. I know all the values of $d_{i,j}$.

I am confused because the input to gradient descent is just a vector, but for this problem it is $n$ vectors. I've come across scant information about a gradient-matrix and matrix calculus but I don't understand enough to see how this is analgous with vector calculus and hence gradient descent.

Is solving this minimization problem via gradient descent possible and why?
How else could I solve this minimization problem numerically for $v_1, v_2 \dots, v_n$?

Just concatenate all of the variables into a single, long vector.  In your case, you'll have a $2n$-dimensional vector:

$$v = (v_{1,x},v_{1,y},v_{2,x},v_{2,y},\dots,v_{n,x},v_{n,y})$$

where $v_{i,x}$ is the x-coordinate of $v_i$ and $v_{i,y}$ is the y-coordinate of $v_i$.  Now treat this as a function of $v$, i.e.,

$$f(v) = \sum_{i,j} (||v_i - v_j|| - d_{i,j})^2$$

This gives you an objective function $f: \mathbb{R}^{2n} \to \mathbb{R}$, which you can try to maximize.  For instance, you can apply the gradient descent method to $f$ (after computing the partial derivatives of $f$).

That said: for your particular problem, gradient descent might not work very well, unless you happen to have a starting point (initial value for $v_1,\dots,v_n$) that is close to the optimum value.  There might be many local optima that gradient descent could get stuck in.  The only way to know for sure is to experiment with a bit and see what happens.


How can we get a Las Vegas algorithm from a Monte Carlo one? I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills.

Here is the exercise:

Exercise 1.3: Consider a Monte Carlo algorithm $A$ for a problem $\Pi$ whose expected running time $T(n)$ on any instance of size $n$ and that produces a correct solution with probability $\gamma(n)$. Suppose further that given a solution to $\Pi$, we can verify its correctness in time $t(n)$. Show how to obtain a Las Vegas algorithm that always gives a correct answer to $\Pi$ and runs in time at most $(T(n)+t(n))/\gamma(n)$.

My attempt to solve this exercise is:

Algorithm LA
1) for i = 1 to 1/gamma(n) do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

The idea of my Las Vegas algorithm LV was to re-run the Monte Carlo algorithm, MC in my code, some iterations until the correct answer is given.

I found that $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^i$. So I choose the iterations from 1 to 1/gamma(n). In this case, $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^{1/\gamma(n)}$ which goes either to $0$ or $1/e$ as $\gamma(n)$ goes to either $1$ or to $0$, respectively. I think this does not answer the question.

How would you solve this problem?

First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is zero.

So, the algorithm should be as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

Also, verify the solution from MC(n) by the given in the question which takes t(n) running time; because you don't know that monte carlo algorithm outputs correct or not. Also I removed the else condition, I don't see it is important here. So, the algorithm should be edited as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     answer_from_verifier = output_Verify(solMC)
3)     if answer_from_verifier is correct
4)         return solMC
7)     end
8) end

Now, the expected running time is:

$E[X]= \sum_{i=0}^{\infty} (1-\gamma)^i \gamma (i+1) (T(n)+t(n)) $

$= \gamma (T(n) + t(n)) \sum_{i=0}^{\infty} (1-\gamma)^i (i+1)$

$= \gamma (T(n) + t(n)) . 1/\gamma^2$

$= \frac{T(n)+t(n)}{\gamma} $


Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible.

I tried to work with Min-Max Fibonacci heaps and pointer to median, but got stuck.

I believe the $Insert$ operation can be done in $O(\log n)$ amortized-time.

Any help is appreciated.

It should be possible with everything O (1) amortized if the insertions and deletions are random: If there are n items, try to keep track of the sqrt (n) smallest items, largest items, and items around the median.

If you insert or remove an item within the smallest, largest or median items, that's $O(n^{1/2})$ because you need to insert or remove one of $n^{1/2}$ elements, and happens with probability $O(1/n^{1/2})$, so total O (1).

Whenever you insert or remove one of the elements before the median elements, the range of the "median" elements shifts. When the items that were supposed to be around the median don't contain the median element anymore, you need to find elements around the median again, which should happen in O (n). If insertion / deletions are random, then I think the balance shifts by $n^{1/2}$ only after a large number of insertions / deletions. You'll have to check the maths.

And of course all this only works if insertions / deletions are random. Otherwise you need something significantly more clever.

PS. D.W.'s comment indicates (unless I'm very wrong) that if you can find the median and insert items in O (f(n)) amortized in the worst case, then you can sort an array in O (n·f(n)), which means f(n) cannot be better than log n asymptotically in the worst case.


Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible? could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to give a group of talented high schoolers who haven't seen matrices before a sketch/cursory proof of the result, but I couldn't think of a good way to explain it.

The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by
$$
\begin{align*}
L(i,i) &= \sum_{j \neq i} X(i,j) \\
L(i,j) &= - X(i,j).
\end{align*}
$$
Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K_n$ we can associate a degree $n-1$ monomial $X(T)$ as follows. Root the tree at the vertex $n$. For every non-root vertex $i$ with parent $j$, we include the variable $X(i,j)$ in the monomial. In total $X(T)$ is a product of $n-1$ monomials, one for every edge in the tree.

Let $M$ be the $(n,n)$ minor of $L$. We will show that $\det M = \sum_T X(T)$. You can derive the matrix-tree theorem from this statement by substituting the actual graph for the indeterminates $X(i,j)$. If you wish, you can run the entire proof after doing the substitution, and then you don't have to talk about indeterminates.

Recall that
$$\det M = \sum_{\pi \in S_{n-1}} (-1)^\pi \prod_{i=1}^{n-1} M_{i\pi(i)}.$$
We can write every permutation $\pi$ as a product of cycles $\pi_1,\ldots,\pi_{\ell(\pi)}$ and of fixed points $F(\pi)$, and then we get
$$
\begin{align*}
\det M &= \sum_\pi (-1)^\pi \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} (-X(i,\pi(i))) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right) \\ &=
\sum_\pi (-1)^{\ell(\pi)} \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} X(i,\pi(i)) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right),
\end{align*}
$$
using the formula $(-1)^\pi = \prod_{t=1}^{\ell(\pi)} (-1)^{|\pi_t|+1}$. We can rewrite this as
$$ \det M = \sum_\pi D(\pi), $$
where $D(\pi)$ is the expression appearing above.

If we open up all the sums, we find that $\det M$ is a (weighted) sum of monomials of the form $X(\alpha) = \prod_{i=1}^{n-1} X(i,\alpha(i))$. For each $\alpha$, we can look at the directed graph in which $i$ points at $\alpha(i)$. It's not hard to see that each such graph consists of a (possibly empty) collection of cycles $\alpha_1,\ldots,\alpha_{\ell(\alpha)}$ and a tree $T(\alpha)$ rooted at $n$. We will show that the coefficient of $X(\alpha)$ equals $1$ if $\ell(\alpha) = 0$, and vanishes otherwise. This will complete the proof.

Consider first the case that $\ell(\alpha) = 0$. In this case the only permutation $\pi$ for which $X(\alpha)$ appears in $D(\pi)$ is the identity permutation (since every $X(\beta)$ appearing in any other $D(\pi)$ contains some cycle), ans so the coefficient of $X(\alpha)$ in $\det M$ is indeed $1$.

Next, consider the case in which $\ell = \ell(\alpha) \neq 0$. In this case, for every subset $S$ of the cycles of $T(\alpha)$, $X(\alpha)$ appears in $D(\pi)$ for $\pi = \pi(S)$ which consists of the cycles in $S$, and it only appears in these $D(\pi)$. For every $S$, the coefficient of $X(\alpha)$ in $D(\pi(S))$ is $(-1)^{|S|}$. Therefore the total coefficient of $X(\alpha)$ in $\det M$ is
$$
\sum_{S \subseteq \{\alpha_1,\ldots,\alpha_\ell\}} (-1)^{|S|} =
\sum_{S_1 \subseteq \{\alpha_1\}} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_1| + \cdots + |S_\ell|} = \\
\sum_{S_1 \subseteq \{\alpha_1\}} (-1)^{|S_1|} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_\ell|} = (1-1)^\ell = 0.
$$
(This is just inclusion-exclusion. The previous case is the case $\ell=0$.)
This completes the proof.

This proof is taken from lecture notes by Jacques Verstraete. See also Mark Muldoon's lecture notes, which presents this argument as a version of inclusion-exclusion.


Is it true that all languages which have polynomial circuits are in PSPACE? I just read about polynomial-size circuit families and I have a question as the title. I know P/poly is defined as the class PSIZE of languages that have polynomial-size circuits. But what about other languages in other classes that have polynomial circuits?

Some languages in P/poly are undecidable. For example, any language over the alphabet {a} is in P/poly because for any string length n, either an is in the language or it is not, so the advice string for length n can just be whether or not to accept the string. However, there are uncountably many languages over this alphabet and only countably many Turing machines, so infinitely many of these languages are undecidable.

Every language in PSPACE is, by definition, decidable. Therefore, PSPACE ≠ P/poly.

Hope this helps!