LTL Formula Until with same atoms (aUa) I am trying to solve some past papers in preparations for my next exam and I've stumbled across the following exercise:

While I managed to solve most parts of the exercise, I am still unsure about the formula ((b)U(b)). I am unsure which node I should start checking from and on the general definition of U.

As far as I understood a state matches a general formula aUb if it satisfies the proposition b. So in this example would the states s1, s2 and s4 all satisfy ((b)U(b))? Am I approaching this the wrong way?

Thanks a lot

First of all LTL is defined over traces. In verification, we typically say that a state satisfies some LTL formula if all of the traces starting in the state satisfy the formula. I henceforth assume that this is what is meant in the question and this definition has been given in your course.

The Until operator is defined over a word as follows:

$$
w \models \psi \mathcal{U} \phi \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models \psi \wedge m^j \models \phi
$$

In this equation, $w^i$ represents the word starting at position $i$, where all letters before position $i$ have been removed. Applied to the concretization $\psi = b$ and $\phi = b$, we have:

$$
w \models b \mathcal{U} b \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models n \wedge m^j \models b
$$

Note that without loss of generality, we can assume that the $i$ searched for in the definition is always 0, because for $j=0$, we need to have $w^0 \models b$ for a word $w$ to be a model of $b \mathcal{U} b$. But then we can also choose $i=0$. Then the definition simplifies to:

$$
w \models b \mathcal{U} b \quad \text{ iff } \quad m^0 \models b
$$

Hence, you are searching for all states for which all outgoing paths start with a $b$ state, which is equivalent to saying that you search for all states in which $b$ hold.


Language of context-sensitive grammar I have the following context-sensitive grammar:

$$
\begin{align*}
&S \to xSy \mid a \mid b \\
&Xa \to aa \\
&Xb \to bb \\
&Y \to a
\end{align*}
$$

I know what it does, as it always ends in $a$ and is preceded by 3 $a$s or 3 $b$s. I'm just not sure how to write this in set notation and would appreciate any help. Would it be something like this?
$$ L = \{a^n,b^m \mid n \ge 1, 0 < m \le 3 \} $$

There are basically two possible types of derivations:

Ones that start $S \to^* X^naY^n$.
Ones that start $S \to^* X^nbY^n$.

Derivations of the first type will produce $a^{2n+1}$, those of the second type will produce $b^{n+1} a^n$.


Generate all combinations of a set/array with specific conditions Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions:

Element values range between 0-11
Set length is between 1-12
All sets must begin with 0 ([ 0 ])
Value of element n must be greater than value of element n-1

I want to generate every possible combination of sets with those conditions. So here's a few examples:

[ 0 ],
[ 0, 1 ],
[ 0, 2 ],
[ 0, 3, 5 ],
[ 0, 8, 9, 11 ]

All the way to:

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]

The main language I'm using is Javascript, but if you're use to dealing with C/C++/Python examples in those languages work too. Just no ASM or Perl please. :)

Let $k = 11$ in your problem, so we want to generate all sets with values in the range $0$ to $k$ and with between $1$ and $12$ elements. Then you can do the following:

First generate all sets for $k-1$ (recursively)
Then, for each set, make two copies, one with a $k$ on the end and one without a $k$ on the end.

If you prefer doing it iteratively, here is this described in an iterative fashion (pseudocode):

generate_all_subsets(k):
    let sets = [[0]]
    for i from 1 to k:
        for each set in sets:
            add sets + [k] to sets
            # (now there are two copies: sets, and sets + [k],
            #  so the size of 'sets' has doubled)
    return sets


Big Omega of a while loop I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is Ω(1), because it takes at least constant time.

What if let's say I have a while loop i < n, then its O(n), but does that mean that its Ω(1) or Ω(sqrt(n)) or something else because we can say that it takes at least constant time? I just don't understand, its straightforward with upper bound, but lower bound confuses me a lot.

I am confused about this code. Can we say that its lower bound time is Ω(sqrt(n)) or perhaps Ω(log n), because it can do at least as good?

i=1
while(i<n)
 i+i
end

Any code that gets executed takes time $\Omega(1)$. That's the most you can say if you don't know anything more about the code. For example, if all your know is that your loop has the form while i < n ..., then it could be that $i = n$, so the loop immediately terminates.

Here are some concrete cases in which we can calculate the complexity:

i = 1
while i < n:
  i = i + 1

This runs in time $\Theta(n)$.

i = 1
while i < n:
  i = i + i

This runs in time $\Theta(\log n)$.

i = 1
j = 1
while i < n:
  i = i + j
  j = j + 1

This runs in time $\Theta(\sqrt{n})$.

See if you can prove all these claims.


Explanation of implication-introduction rule I read in Proofs and Types by Girard et alii. the following excerpt that talks about the calculus of natural deduction:

  Now a sentence at a leaf (of the deduction tree) can be dead, when it
  no longer plays an active part in the proof. Dead sentences are
  obtained by killing live ones. The typical example is the
  $\implies$-introduction rule:

  $$ \dfrac{\stackrel{[A]}{\stackrel{\vdots}{B}}}{A \implies B} $$

  It must be understood thus: starting from a deduction of B, in which
  we choose a certain number of occurrences of $A$ as hypotheses (the
  number is arbitrary: 0,1,250,$\ldots$), we form a new deduction of
  which the conclusion is $A \implies B$, but in which all these
  occurrences of $A$ have been dicharged, ie. killed. There may be other
  occurrences of $A$ which we have chosen not to discharge.

  This rule illustrates very well the illusion of the tree-like
  notation: it is of critical importance to know when a hypothesis was
  discharged, and so it is essential to record this. But if we do this
  in the exmaple above, this means we have to link the crossed A with
  the line of the $\implies$I rule; but it is no longer a genuine tree
  we are considering.

May I ask you for an explanation and example of this situation?

Every assumption that is introduced between brackets has to be discharged at some point for the proof to be complete. Otherwise, we could prove that $A$ is true for any given $A$ as follows.

[A]¹
───
 A

This proof is incorrect, we have not discharged the initial assumption. The following proof of $A\to A$ would be correct, as it discharges the assumption (and the implication introduction rule is necessary to do so!).

 [A]¹
 ───
  A
───── (discharging ¹)
A → A

Now, let's compare two derivations of $A \to A \times A$ and $A \to A \to A \times A$. On the first one, we will discharge the two occurrences of $A$ at the same time (on the same deduction step). On the second one, we will discharge the two occurrences on two separate steps.

First proof

  [A]¹   [A]²
  ─────────
    A × A
───────────── (discharging ¹ and ²)
  A → A × A

Second proof

 [A]¹    [A]²
 ──────────
   A × A
───────────── (discharging ¹, note that ² is still alive!)
  A → A × A
──────────────── (discharging ²)
 A → A → A × A

Maybe looking at this from the perspective of the simply-typed lambda calculus is more illuminating. Instead of tracking superscripts, variable
names represent which assumptions are we choosing to discard at each point. Note the difference between the two proofs, and how the introduction rule of the implication corresponds to a lambda abstraction,
while the introduction rule of the conjunction corresponds to a pair type.

First proof

   a : A   a : A
   ─────────────
   (a,a) : A × A
 ────────────────────
 λa.(a,a) : A → A × A

Second proof

     a : A   b : A
     ─────────────
     (a,b) : A × A
   ────────────────────
   λb.(a,b) : A → A × A
 ───────────────────────────
 λa.λb.(a,b) : A → A → A × A

(I am using a lambda interpreter I wrote to generate these derivation trees. It may be useful for you if you are interested in the connection between propositional intuitionistic logic and lambda calculus.)


Multitape Turing machine with multiple non-blank tapes A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank.

Are there any formulations of a Turing machine that allow other tapes to be not blank? Why does the condition that the input only appears on one tape exist?

The restriction to a single non-blank tape at the start (and a single output tape too) is just convention – it makes the definitions a little simpler and maybe simplifies the analysis a little.

The reason we can make this restriction is that it makes no difference to the class of functions that are computable and it also makes no significant difference to the running time of algorithms. Any interesting Turing machine algorithm is going to need linear time since, otherwise, it can't even read all its input. For example, how would a Turing machine know to halt after $\log n$ steps? It's not read all its input in that time, so it doesn't even know what $n$ is!

This means that any linear-time preprocessing you do before the main part of your algorithm can't affect the asymptotic running time. So, in particular, you can check that, for example, your single input tape consists of three binary numbers separated by semi-colons, and copy those three numbers onto three separate tapes. Then you can run your main algorithm that thinks it has three different input tapes.
Likewise, any Turing machine must run in time at least linear in the size of its output. This means that, if you have a machine whose output is spread across multiple tapes, you can postprocess that by copying it onto a single tape with the different parts separated by some special character.

As Raphael points out in his comment, there is at least one model that has more than one non-empty tape at the start. Probabilitstic Turing machines can be defined either by having multiple possible transitions from each state, each with an associated probability. Alternatively, they can be defined as deterministic Turing machine that has access to an infinite tape initialized with random bits. Note that this takes us outside the standard Turing machien model because we now have an infinite input. (This equivalence of a probabilistic machine on deterministic data versus a deterministic machine on random data is closely related to Yao's principle.)


Dependency on adjacent blocks decreases as block count increases The following is an excerpt from Information Theory: A Tutorial Introduction, page 65.

Now, supposing the identity of each letter in English does not depend
on any letter that is more than 10 letters away. In practice, the
dependency between letters diminishes rapidly as inter-letter distance
increase, as shown in Fig. 3.6. Once the block length has grown to $N =
 10$, the identity of every letter in a given block $B_k$ depends on other
letters in that block and exactly two other blocks: the previous block
$B_{k-1}$ and the next block $B_{k+1}$. All other blocks contain letters
which are more than 10 letters away from, and therefore independent
of, every letter in block $B_k$.
If the original text is sufficiently long, and if there are a large number of blocks, then the dependency between adjacent blocks just
described accounts for a tiny proportion of the overall dependency
between blocks. Thus, the more blocks there are, and the longer each
block is, the smaller the dependency between blocks. By analogy, it
is as if each block is one of a large number of independent
super-symbols, and if the blocks are independent then finding their
entropy is relatively simple. The only question is, how long do those
blocks have to be to ensure that they are independent?
The block
length beyond which inter-letter dependence falls to zero is called
correlation length $N_C$. Once the block length exceeds the correlation
length, it is as if all  blocks are effectively independent, so
increasing the block length $N$ beyond $N_C$ has a negligible effect on
the estimated entropy $G_N$. At this point, $G_N$ equals the entropy of
English; that is $G_N = H$. This matters because Shannon's theorems are
expressed in terms of infinite block lengths, but in practice these
theorems apply to any block length which exceeds the correlation
length  of the sequence under consideration.

Given some block, I can't see how block count decreases dependency on two blocks adjacent to it. Could someone, please, explain?

The more blocks there are, and the longer each block is, the smaller the dependency between blocks.

There are two tendencies. Let us explain one by one.

(Tendency of more blocks) Assume the block size does not change. The more blocks there are in a string, the smaller the dependency between blocks.

Suppose the block size is greater than 10. Suppose there are $N$ blocks. Since each block depends only two other blocks, the previous block and the next block, the total number of (unordered) dependent pairs of blocks is $N-1$ as each block is dependent on its next block except that there is no next block to the last block. There are $N(N-1)/2$ (unordered) pairs of blocks in total. The ratio of dependent pairs to all pairs, $\dfrac{N-1}{N(N-1)/2}=\dfrac 2N$ becomes smaller and smaller and can be arbitrarily close to 0 when $N$ goes bigger and bigger. That is one way in which we can understand the meaning of tendency of more blocks.

If the block size is not greater than 10, we can argue similarly since each block will depends on at most previous $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks and next $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks.

(Tendency of longer blocks) The larger each block size is, the smaller the dependency between adjacent blocks.

Consider two adjacent blocks $B$ and $C$ with $C$ following $B$. Let us consider the ordered pairs of letters where the first letter is in $B$ and the second letter is in $C$. Since every letter does not depend on any letter that is more than 10 letters away, there are at most $1+2+\cdots+10=55$ such pairs in which the two letters are dependent. As the block size $S$ goes bigger and bigger, the number of all possible pairs $S\times S$ becomes bigger and bigger quadratically. However, the number of dependent pairs stays at 55 once the block size is no less than 10. Hence the ratio of dependent pairs to all pairs becomes smaller and smaller. This is one way how we can understand the meaning of tendency of longer blocks.

If we agree that the nearer the letters, the stronger the dependency between them, then we can see that the dependency between adjacent blocks becomes smaller and smaller when the block size grows bigger and bigger even if we do not require the block sizes are no less than 10.

The above explanation follows roughly the same style as the original text. To be more precise, we should define the correlation of two blocks in mathematical terms and we should show how the ordered dependent pairs of letters from two blocks contribute/determine to the correlation of two blocks. That will not be an easy undertaking to be done rigorously. However, it is, I believe, intuitively clear that ratio of dependent pairs from two blocks to the total pairs is in proportional (not necessarily linearly) to the dependency of the two blocks, as long as the latter is defined reasonably. So the above explanation should convince you the correctness of the quoted conclusion. After all, that quoted conclusion is supposed to be easy and intuitive to understand.

  Given some block, I can't see how block count decreases dependency on two blocks adjacent to it.

If "block count" means the number of letters in a block,  then "larger block count decreases dependency between the given block and either of the two blocks adjacent to it" is the tendency of more blocks as I have explained in the above.

If we consider "block count" as the number of blocks, then "larger block count" does not decreases dependency between the given block and either of the two blocks adjacent to it, as you believed.


Checking two properties of a tree I have the following definition:
A green-blue tree is a binary tree that follows the following properties:

Each green node has only blue descendants.
Every path that goes from a node to a leaf has the same number of blue nodes.

This is an example of a green-blue tree:

For the first part, we can ensure that every node has only blue descendants in $O(n)$, being $n$ the number of nodes.
The algorithm could be as follows:
bool descendants_condition(node):
    if node == nullptr:
        return true
    if node.info == green;
        return descendants_condition(node->left) and
               descendants_condition(node->right);
    else:
        return only_blue_nodes(node->left) and
               only_blue_nodes(node->right);

For the second part, I'm trying to avoid checking every path from every node to the leafs. I have the following intuition:

If a node is a leaf, the condition is satisfied
If a node is not a leaf, we should have the same number of blue nodes in the right and in the left.

However, this is not enough for me, and I would like to see a proof of this condition.

This is not a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem.
Notice that in any path from the root to a leaf, say $v_1,\dots, v_k$ we must have that the number of green nodes is at most $1$ (by the first property). Also, notice that the number of blue nodes in the path, is the depth of the leaf $v_k$ minus either one or zero, depending on whether there was a green node in that path.
So, in order to count the number of blue nodes in a path you have to do the following two things:

Write at every leaf its depth (can be done in $O(n)$)
Write at every leaf whether there was a green node in the path from the root to it (think about it, it also can be done in $O(n)$)

Then finally you go through all leaves, calculate the number of blue nodes using this information, and make sure all leaves have the same value of it.


How to write a recursive function that with certain time complexity I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

public void run(int n)

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.
The set $\{0,1\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.


Double floating precision exercise today I had to deal with this exercise:

  If $x \approx y$, we might expect some cancellation in computing $log(x)- log(y)$. On the other hand, $log(x) - log(y) = log(\frac{x}{y})$, and the latter involves no cancellation. Does this mean that computing $log(\frac{x}{y})$ is likely to give a better result? (Hint: For what value is the log
  function sensitive (highly elastic)?)

I would assume that in double precision the second expression would be more accurate, but replicating the calculations in R did not show any differences between these two expressions.

x1 <- (1/0.999999999999)
y1 <- (1/0.99999999999999)

log(x1)-log(y1)
log((x1/y1))
1/log(1.00000001)

Assume that every single operation has a relative error ≤ eps. Starting with this, what if x = 1.001 and y = 0.999, or x = 10.01 and y = 9.99, or x = 1,001,000,000 and y = 999,000,000? How is log (x / y) affected, and how is log (x) - log (y) affected?


Understanding Randomized Select algorithm Here is the algorithm in pseudo code:

Where $A$ is the array to search, $p$ is the starting index in the array, $r$ is the ending index and $i$ represent the number of smaller values we want from our goal value, the $i$ smallest number in the array.

I dont understand the $k$.

It gets a value that dont realy represent the index of the value in the original array, but the index value in the sub array we are at, at the recursion process.

Similarly, it doesnt represent the amount of values that are smaller than the pivot we are at, but the number of smaller values in the current sub array in the recursive process.

So how can we check between $i$ and $k$? They dont talk on the same arrays...

Thank you.

The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \leq A[q+1],\ldots,A[r]$.

The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A[p],\ldots,A[r]$. To see this, let us assume from now on that all elements of $A$ are distinct (this will slightly simplify the arguments). Then the $q-p$ elements $A[p],\ldots,A[q-1]$ are smaller than $A[q]$, and the rest are larger than $A[q]$.

If $i = k$, then we are done. If $i < k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[p],\ldots,A[q-1]$ (since the $i$th smallest element is smaller than $A[q]$, which is the $k$th smallest element), and moreover, it is the $i$th smallest element in that subarray. If $i > k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[q+1],\ldots,A[r]$ (since the $i$th smallest element is larger than $A[q]$, which is the $k$th smallest element), and moreover, it is that $(i-k)$th smallest element in that subarray (since the $k$ elements $A[p],\ldots,A[q]$ are already smaller than it).


Given an amount of sets with numbers, find a set of numbers not including any of the given Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the whole set) For example :Setting the max number 8 and given the sets

{1,2}
 {2,3}
 {7}
 {3,4}
 {5,6,4},
one maximum solution is the set {1, 3, 5, 6, 8}. I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem, but that seems to work only if the sets were consisted only from pairs,which doesn't stand.Any idea?Thanks in advance.

I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem

I think that´s a good start. The problem you are looking for is independent set but in hypergraphs instead of regular graphs.

The opposite of the independent set problem in hypergraphs is the vertex cover problem as it is in regular graphs. Well, that problem is equal to the hitting set problem: https://en.wikipedia.org/wiki/Vertex_cover#Vertex_cover_in_hypergraphs.

Something that i will do is:

Sepparate from the universe set all elements that doesn´t appear in a given set and insert those elements inside the solution set: In your example the number 8. So the universe will be $\{1, 2, 3, 4, 5, 6, 7\}$ and the solution set will be $\{8\}$
Transform the hitting set instance into set cover. We will have the following subsets in your example:  $\{1\}$ ,  $\{1, 2\}$ ,  $\{2, 4\}$,  $\{4,5\}$,  $\{5\}$,  $\{5\}$,  $\{3\}$.
We find the minimum hitting set and we pick the complement of the minimum hitting set, we add those elements to the solution set and we are done. In your example the minimum hitting set will be:  $\{2, 4, 7\}$. The complement will be $\{1, 3 ,5 ,6\}$. By adding the elements of the complement set to the solution set we have the solution to the problem.


Question about the conditions to find articulation points in a graph I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.
In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:

The traversal order at which we visited the vertex
The highest reachable ancestor from the tree for each vertex

After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:

If the root has more than 1 child, it is an articulation point
If we have an edge A -> B which is a bridge, then A is an articulation point
If we have an edge A -> B (A is parent of B) and the highest reachable node from B is A, then A is an articulation point.

I wrote a program to test this and it works on the graphs I tested it against:
// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
    if(pre[node] != 0) {
        lo[parent] = Math.min(lo[parent], pre[node]);
        return;
    }

    pre[node] = index;
    lo[node] = index;
    index++;

    int childCount = 0;
    for(int child: graph[node]) {
        if(pre[child] != 0)
            childCount++;
        if(child == parent)
            continue;
        dfsFindArticulationPoints(child, node);
        lo[node] = Math.min(lo[child], lo[node]);

        // Check case 2 and 3
        if(node != 0 && pre[node] <= lo[child])
            articulationPoints.add(node);
    }

    // Check case 1
    if(node == 0 && childCount > 1)
        articulationPoints.add(0);
}

My Question:
I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?
Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?

Here is the proof:
Given we have A -> B as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 subsets - the first containing the root and the second containing B.
For the subset containing B to be disjoint from the root if A is removed, B should not have a link to any node from root ... A that is it should not be able to reach a vertex higher than itself. This is possible only if:

A -> B is a bridge meaning the highest node reachable from B is itself
A is the only node B is connected to that is above it. This way if we remove A the highest node reachable from B is itself.


Polynomial time reducibility is an equivalence relation How do I prove the following statement?

The relation $≤_p$ (polynomial time reduction) is an equivalence relation.

A polynomial-time reduction from $A$ to $B$ is a polynomial-time computable function $f$ that maps an instance $x$ of a problem (language) $A$ to an instance $f(x)$ of a problem $B$ such that $x \in A \iff f(x) \in B$.
Polynomial-time (Karp) reductions are reflexive (since $A \le_p A$), as it follows by choosing $f(x) = x$.
Polynomial-time reductions are transitive, i.e, if $A \le_p B$ and $B \le_p C$ then $A \le_p C$ by choosing $f = h \circ g$, where $g$ (resp. $h$) is a polynomial-time computable function such that $x \in A \iff g(x) \in B$ (resp. $x \in B \iff h(x) \in C)$.
However, Polynomial-time reductions are not symmetric. That is, it is not true that $A \le_p B \implies B \le_p A$.
Consider for example a binary alphabet, $A = \{0,1\}^*$, and $B = \{0\}$.
The function $f(x) =0$ is a valid polynomial-time reduction from $A$ to $B$ but there is no polynomial-time reduction from $B$ to $A$.


Understanding denormalized numbers in floating point representation I am confused about how denormalized numbers work in floating point representation.

I was referring to Stallings book and this article. The book initially explains floating point number format in general and then explains IEEE 754 floating point format. I will tell explicitly when I am talking about floating point format in general and when about IEEE 754.

First let me tell you what I understand. Lets consider single precision (32 bit) numbers. As shown in the book, the normalized numbers in IEEE 754 takes following form:

In both general and IEEE 754 floating point number,

Sign bit is 0 for positive number, 1 for negative number.
Fraction aka significand has implicit leading 1.
Biased component is exponent with bias 127.

With this information, I am able to come p with range of normalized numbers in IEEE 754 standard. Its $\pm2^{-126}$ to $(2-2^{-23})\times 2^{127}$ as given in that article. This is how I interpret, how its derived.

Max significand: $(1.\underbrace{11..11}_{23\text{ bits}})_2=(2-2^{-23})_{10}$
Min significand: $(1.\underbrace{00..00}_{23\text{ bits}})_2=(1)_{10}$ and is simply omitted from multiplication to $\pm2^{-126}$
Min exponent: Biased: $(00000001)_2=(1)_{10}$, Unbiased: $1-127=-126$
Max exponent: Biased: $(11111110)_2=(254)_{10}$, Unbiased: $254-127=127$

I know that significand in de-normalized range does not have implicit leading 1 and in fact has leading 0.

Doubts

I have following doubts about denormalized range in IEEE 754 format:

As give in that article, how is the denormalized single precision range is $\pm 2^{-149}$ to ${(1-2^{-23})\times2^{-126}}$
Consider below table from Stallings book.
In this, in the biased exponent column, entries for positive and negative denormalized (last two) rows is $0$, but in the value column, the exponent of $2$ is $e-126$, even though there is no $e$ elsewhere in those rows.

Now consider the below table given under summary section of that article. Note that in 2nd row and 5th last row of denormalized real, "Exponent" column says $00..00$, however in value column, there is $+1$ in the exponent: $2^{(-b\color{red}{+1})}$. From where this $+1$ came?
How exponents in the book (as explained in the question 2) and the exponent in the article (as explained in the question 3) compare and how they lead to the range asked in question 1?

Although, the question is a bit old, but it may help people coming here for similar question.

A vital detail was missed out in the article that you referred to and it is that the standard chose to interpret an all 0s exponent to be equivalent to '-126' and not '-127'. One place, where I found a nice explanation (and an explicit statement about this truth) is this article. To quote from it:

  Subnormal Numbers: When all the exponent bits are 0 and the
  leading hidden bit of the siginificand is 0, then the floating point
  number is called a subnormal number. Thus, one logical representation of a subnormal number is

  (–1)s × 0.f × 2–127 (all 0s for the exponent) ,

  where f has at least one 1 (otherwise the number will be taken as
  0). However, the standard uses –126, i.e., bias +1 for the exponent
  rather than –127 which is the bias for some not so obvious reason,
  possibly because by using –126 instead of –127, the gap between
  the largest subnormal number and the smallest normalized number is smaller.

  The largest subnormal number is 0.999999988×2–126. It is close
  to the smallest normalized number 2–126.


How to prevent deletion in an array in the B method I have created a very basic model of an array list in the B method as shown below

MACHINE Array(TYPE)

VARIABLES block

INVARIANT block : seq(TYPE)

INITIALISATION block := []

OPERATIONS

add(e) =
   PRE e : TYPE
   THEN block := block <- e
   END;

remove =
   PRE block /= []
   THEN block := tail(block)
   END;

res <-- showArray =
    res := block;

res <-- getfront =
   PRE block /= []
   THEN res := first(block)
   END

END

However what I am trying to achieve is to create a model that prevents deletion from the list, so when an element is added, it cannot be deleted.

What should I add in the invariant to achieve this?

You cannot add such a property to your invariant because the invariant describes how a valid state might look like but not how it can be altered.

The operations are responsible for specifying the behaviour of the model. If you want to prevent that an element will be removed from the array, just do not specify that as a possible behaviour. In your example above, just remove the operation remove.

Every valid refinement is then not allowed to remove an element.


Search spaces and computation time This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that.

Consider a problem P where we are given:

the initial space of possibilities is exponential in the size of the input,
the search space decreases monotonically as we read the input,
for the algorithm that correctly computes P and has the minimum worst-case performance, the search space is still exponential in the size of the input even after the final input is read.

Can we conclude that P requires exponential time? If not, what would a polynomial-time counterexample look like?

No, in general you can't assume that an exponential search space requires exponential time to search. Linear programming generally has an exponential search space but can be done in (weakly) polynomial time.


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

The original algorithm and question are:

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

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

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

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

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

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

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

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

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

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

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

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

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


How do I stop "cheating" in reinforcement learning (MLP+Evo. Algorithm)? I have a two hidden-layer MLP. I am trying to teach it classification of the sine function. For instance, if there is an [x,y] point above the sine function, the ANN should classify that point as a 1. Otherwise, it should be classified as a 0.

It should end up like this. Points above y=sin(x) should be blue. Points below should be red. The network is just outputting 1s or 0s, so we are plotting the point along with a binary value (0=red,1=blue).

Graphic done with Matplotlib.

I feedforwarded my ANN thousands of random points, calculated the error between desired and output, and used that as fitness for an evolutionary algorithm that would evolve the network weights. The lower the error, the more likely the weights would be bred and preserved for the next round.

Unfortunately, the algorithm found a way to "break" the network. It was able to minimize the error while outputting the wrong values. For instance, one network and weight iteration I evolved outputted 0 for all inputs I would give it, even though I got the error down to 0 when I evolved the weights. It's a beauty. The plot is below.

My Python code is pretty big, so I will spare how I wrote the MLP and show you just a few snippets of relevant code.

Here, we have lists of random points and are feeding them through the MLP. If it is trained properly, the error will be close to 0 because the MLP correctly classifies each point.

    i=0
    error = 0
    while i < 100:
        output1 = feedForward(neuralNet, [xValsAbove[i], yValsAbove[i]]) # feedforward a point that is above the sine function.
        output2 = feedForward(neuralNet, [xValsBelow[i], yValsBelow[i]]) # feedforward a point that is below the sine function.

        if output1 < 0.99:
            error += 1 - output1
        if output2 > 0.01:
            error += output2
        i+=1
    return error

So, let's start evolving. Generate a bunch of random weights. Feed them a few thousand random points each in a range of -50 to 50 on both axes. Select the ones with the lowest classification error. Continue. After 50 generations, my error is down to 2 or 3. Looks good. Let's feed it a bunch of test points and see how it did.

???

Can anyone help me here?

You are minimizing the wrong loss function.  In other words, you have picked a poor objective function.

Look up the standard objective functions that are used for training neural networks for boolean classification tasks: e.g., mean-squared error, or cross-entropy loss.  This is covered in standard tutorials.  They don't use the function you show.  The function you picked looks... odd, so I suspect it is the source of your porblem.


Show that the halting problem is decidable for one-pass Turing machines $L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and   } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable.

I thought of checking the encoding of $M$ first and determine whether its transition function moves only right (Can I do that?). If so then try to simulate $M$ on $x$ for $|Q|+1$ steps, if it stops then $<\!M,x\!>\, \in L$ otherwise it is not.

Is this correct?

I assume $Q$ is state set of $M$. If so, this runtime bound does not make much sense; in particular, a Turing machine with three states can move to the end of the input and check whether $x$ is an even number; it is clearly not enough to wait three steps.

The next question is whether there is a computable bound on the runtime of halting one-pass machines. Unfortunately, there is not: $M$ might be nondeterministic and halt after an arbitrary amount of steps.

So we determinise $M$ while simulating (that is computable) and look for a bound for all paths. Now we are getting somewhere: after having consumed the input, there are two cases. Either $M$ halts or it enters a loop. As it only moves right (into empty tape), such loops can be detected.

   Putting things together, we simulate a determinisation of $M$. We run every branch until $x$ is consumed¹ and then for another $|Q|\cdot|\Sigma_T|$ steps, $Q$ the set of states and $\Sigma_T$ the tape alphabet of $M$. At this point $M$ has either stopped or loops (in this branch), which we detect by a pair of current state and tape symbol occuring for the second time. We only have to check finitely many branches up to a computable bound, therefore $L$ is recursive.

$M$ might loop here already if not moving the head is allowed, but that can be detected, too.


top-N recommendation in collaborative filtering I have started to read about user-based and item-based collaborative filtering techniques. I understand how a rating of the target user for a particular item is predicted. How top-N recommendation list is created in user-based/item-based collaborative filtering??

Apache Mahout has several implementations about this problem. Most common approach is to predict all unrated items of a particular user and sorting items by their predicted values. Then you can select top N items to recommend. (see class AllUnknownItemsCandidateItemsStrategy in Mahout).

A version of this implementation with better performance and low accuracy is SamplingCandidateItemsStrategy. This one does not select all unrated items to predict, instead it selects some of them randomly with a given rate and then predict only these items. Finally you can select best predicted items as usual. Advantage of this method is to predict less items but since you eliminate some items randomly accuracy of this method obviously will be worse.

Moreover, there are other implementations which use item based similarity to select candidate items such as  AllSimilarItemsCandidateItemsStrategy,  PreferredItemsNeighborhoodCandidateItemsStrategy,

AllSimilarItemsCandidateItemsStrategy finds similar items of the customer's preferred items and predicts this set. It has a better accuracy since you select relevant items for customer but selecting candidate items phase requires effort.

These are some methods which are used generally.


How do I build a left derivation tree from an expression including right-to-left associativity? Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? For example, the expression a + b ** c ** d where ** is right-to-left associative, and + is left-to-right associative.

In a leftmost derivation, you always expand the leftmost non-terminal, by definition. The question is, what do you expand it to, since you usually have more than one choice.


Number of Different AVL Tree I studying the related question.

https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node

but it's not so general.

In-fact, We want to know with N keys, how many different AVL Tree, we can make?

we know with N=1 key is 1 AVL Tree. with N=2 key we have 2 different AVL Tree, but in general we can make any recurrence formula? for example for N=4, N=5 and so on.

Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$:

$$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr),~ n\geq h > 1,$$

with the initial conditions $a_{n,h} = 0$, if $h>n$ or $h\in\{0,1\}, n\neq h$, and $a_{0,0} = a_{1,1} = 1$.

The numbers you are looking for then are $a_n = \sum_h a_{n,h}$.

Unfortunately there apparently is no known closed form for this sequence. The OEIS has a list of the first 1000 terms and maple + mathematica code to compute further ones (via the recursion).


Subtracting a two's complement value from another two's complement value I'm trying to solve the following problem:

$$ 6AD3 - AF20 $$

Both of these are hex values in two's complement.

I keep getting one answer but it's turning out worng. What I tried to do, was take the complement of AF20, which I got as 50D1, and instead of subtracting, I added it to 6AD3, and I got BBA4, however, I am being told this is the wrong answer.

Where am I going wrong?

Converting 6AD3 to binary gives 0110 1010 1101 0011 (the division to 4's is just to make it readable)

Converting AF20 to binary gives 1010 1111 0010 0000
To complement the latter in two's complement, we take the bitwise negation (one's complement) and add 1.

So the one's complement is 0101 0000 1101 1111, and adding 1 gives us
0101 0000 1110 0000
Adding this to 0110 1010 1101 0011 we have:

0101 0000 1110 0000

+

0110 1010 1101 0011

=

1011 1011 1011 0011

Which is BBB3.


What do "patterns, which separately match parts of a page" and "interactions between patterns" mean? Database System Concepts by Abraham Silberschatz, Henry F. Korth and S. Sudarshan says

  Information extraction using simple patterns, which  separately
  match parts of a page, is relatively error prone. Machine-learning techniques
  can perform much more sophisticated analysis, based on interactions between
  patterns, to minimize errors in the information extracted, while maximizing the
  amount of information extracted.

What do "patterns, which  separately match parts of a page" and "interactions between patterns" mean respectively?

Simple patterns could mean regular expressions or extended regular expressions, each of which can be used to match parts of a page without considering the impact of other matches.

Interactions between patterns could mean the conditional probabilities among all findings, either the matched patterns or the unmatched patterns. Additionally, they could mean more complicated probabilistic or logical rules.

We could dive a lot deeper and wider into the subject of information extraction. However, the understanding as basic as the above should be suffice for a first-time reading.


What is the difference between language hierarchy and Grammar hierarchy for LL and LR? Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR.

Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the hierarchy is valid for language as well as grammar i,e if a grammar is LL1 then it must be LR(1); If a language is LL(1) then it must be LR(1).

Language theoretic comparison of LL and LR grammars

In the above link there is mention about two type of hierarchy. One for grammar, another for language. The two hierarchies are different at some points.

For e,g for grammar hierarchy $LALR(1)\subset LR(1)$ but for language hierarchy
$LALR(1)=LR(1)$. I accept the grammar hierarchy. But the language hierarchy confuses me. Basically this hierarchy says that LALR(1) language set is equal to LR(1) language set.

How could this be true?

There are some grammars which are LR(1) but not LALR(1). So the language produced by these grammars should be LR(1) but not LALR(1) thus violating the language hierarchy.

I must be making some kind of mistake. please someone point that out?

A language is in a class if there exist a grammar of that class which generates the language.  Stating that for languages $LALR(1)=LR(1)$, means that when you have a $LR(1)$ grammar you can build a $LALR(1)$ grammar for the same language.  The grammar may be more complex than the $LR(1)$ grammar (for instance, it may use equivalent but different non-terminals to provide the finer distinction of contexts that $LR(1)$ gives for free).


Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept Originally posted in Stack Overflow but was told to post here.
Context: I am doing a PCA on a $M \times N \, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these values, so I need to remove all of them, which means I need to delete the whole corresponding row or column. Of course I want to keep the maximum amount of data. The invalid entries represent ~30% of data, but most of it is completely filled in a few lines, few of it is scattered in the rest of the matrix.
Some possible approaches:

Similar to this problem, where I format my matrix such that valid data entries are equal to 1 and invalid entries to a huge negative number. However, all proposed solutions are of exponential complexity and my problem is simpler.

Computing the ratio (invalid data / valid data) for each row or column, and deleting the highest ratio(s). Recompute the ratios for the sub-matrix and remove the highest(s) ratios. (not sure how many lines or columns we can remove safely in one step), and so on until there is no invalid data left. It seems like an okay solution, but I am unsure it always gives the optimal solution.

My guess is that it is a standard data analysis problem, but surprisingly I could not find a solution online.

Here is a solution based on back-tracking. You probably need to double check but it seemed ok on my side. Should take 1h on a 30x900 matrix, but you can use multi-threading in the bottom for loop to speed it up.
import numpy as np
from tqdm import tqdm

def hash_list(l1, l2):
    return str(sorted(l1)) + str(sorted(l2))  # could be faster

def max_matrix(a):
    # the process:
    # we construct list of rows and columns to select, which keep only valid values (a[rows, columns] = 1 everywhere)
    # at each step, for each other row/column, if it can be added in a valid way, we carry on deeper
    # when it's not possible to extend anymore
    # we backtrack to where we were and try to add the next possible row/column.
    # we store in res the visited valid rows/columns, which prevents most redundant computations
    res = {}
    M, N = a.shape

    def make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right'):
        assert len(sel_columns) + len(other_columns) == M
        assert len(sel_rows) + len(other_rows) == N
        h = hash_list(sel_columns, sel_rows) + d
        if h in res: # we went through this already
            return

        # attempting to add a column
        if d == 'right':
            for i in other_columns:
                if 0 not in a[i, sel_rows]:
                    # we can append it: let's try to go left or right from there
                    other_columns.remove(i)
                    sel_columns.append(i)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')

        # attempting to add a row
        else:
            for j in other_rows:
                if 0 not in a[sel_columns, j]:
                    # we can append it: let's try to go left or right from there
                    other_rows.remove(j)
                    sel_rows.append(j)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')

        # this position has been visited.
        res[h] = (sel_columns, sel_rows)

    # now launching from all possible first positions.
    for i in tqdm(range(M)):
        for j in range(N):
            if a[i, j] == 1:
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='right')
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='left')

    return res

if __name__ == '__main__':
    a = np.random.uniform(size=(30, 900))
    a[a > 0.3] = 1
    a[a <= 0.3] = 0
    a = a.astype(np.uint8)
    print(a)
    res = max_matrix(a)

    # just looking through the results to see the best configuration. (all valid configurations are stored btw)
    res_max = 0
    l1_max, l2_max = [], []

    for _, (l1, l2) in res.items():
        if len(l1) * len(l2) > res_max:
            res_max = len(l1) * len(l2)
            l1_max = l1
            l2_max = l2
    print(res_max, l1_max, l2_max)


undecidable problem and its negation is undecidable A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.

However, can anybody give me an example in which both a problem and its complement are undecidable and not semidecidable? I thought about the diagonalization language Ld, but it does not seem to me that the complement is undecidable.

In that case, does that mean that a Turing Machine M can "lose" some strings that instead should be recognized, since they're part of the language we're trying to indentify?

Consider the following language:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

$L_2$ is undecidable and not semi-decidable, and same is true of its complement.  Why?  The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at the complement of $L_2$, the same thing happens for $M_1$.  This can be formalized more carefully using reductions.

More generally, if $L$ is a language that is undecidable and not semi-decidable, then

$$L' = \{(x,y) : x \in L, y \notin L\}$$

meets your requirements: $L'$ is undecidable and not semi-decidable, and the same is true of the complement of $L'$.


Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$ Let the sequence $r$ be defined by:

$$\begin{align*}r_{1} &= 1\\
r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$

Prove by induction that $r_n$ is $O(\log_2(\log_2n))$.

My idea is to find the closed form function of r and then use the big O definition on the closed form function but I'm having a hard time even finding the function in the first place. Any help? Also is this even the right way to approach this proof?

Thanks.

To prove $r_n = O(\lg \lg n)$ by induction on $n$, suppose $r_n \le c (\lg \lg n)$ is true for $n$ and consider $r_{n+1}$:

$$r_{n+1} = 1 + r_{\lfloor \sqrt{n+1} \rfloor} \le 1 + c(\lg \lg (\lfloor \sqrt{n+1} \rfloor)) \le 1 + c(\lg \lg \sqrt{n+1}) \\ = 1 + c(\lg (1/2\lg (n+1)) = 1 + c(-1 + \lg \lg(n+1)) \\ = 1-c + c(\lg \lg (n+1)) $$

Take $c = 1$.

If you don't stick to the mathematical induction, there is an easier method with less computation by "change-of-variable" (ignore the things of "taking floor"):

Take $m = \lg n$. Consider another sequence $s$ with $s(m) = r(2^{m})$:

$$r(2^{m}) = 1 + r(2^{m/2}) \Rightarrow s(m) = 1 + s(m/2) = \Theta(\lg m) \quad \text{(by the master theorem)}$$

Substitute $m = \lg n$ into the last equation, we have $r(n) = \Theta(\lg \lg n)$.


Prove/Disprove: NP is closed under "mixed" complexity Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:

$\displaystyle x_{i} \in \{0,1\}^{*}$

$\displaystyle x_{1} x_{3} ...x_{n-1} \in S_{1}$

$\displaystyle x_{2} x_{4} ...x_{n} \in S_{2}$

Prove or disprove: if $\displaystyle S_{1} ,S_{2} \in NP$, then $\displaystyle S_{1}°S_{2} \in NP$
I have a feeling it is a proof, simply because I wouldn't know how to disprove it. I know it should come down to finding a certificate $\displaystyle c$ such that $\displaystyle V( x,c) =1$ if'f $\displaystyle x\in S_{1}°S_{2}$, based on the certificates of $\displaystyle S_{1} ,S_{2}$.
The thing is I don't really know what the division of the word $\displaystyle x$ is. So how can I check if part of the word is in $\displaystyle S_{1}$ and the other in $\displaystyle S_{2}$? I could maybe define the $\displaystyle c$ in this way, that it gives you the division, but I don't really know how to define it properly.
Any help?
Keep in mind that's the first time for me studying this subject

The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows:

Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $x_1x_3 \ldots x_{n-1} \in S_1$ and $x_2x_4 \ldots x_n \in S_2$.

In terms of witnesses, a witness for $x \in S$ has the following form:

An even number $n$ and $n$ strings $x_1,\ldots,x_n$.
A witness $w_1$ for $S_1$.
A witness $w_2$ for $S_2$.

To verify this witness, we check:

$x = x_1 \ldots x_n$.
$w_1$ is a witness for $x_1 x_3 \ldots x_{n-1} \in S_1$.
$w_2$ is a witness for $x_2 x_4 \ldots x_n \in S_2$.


Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1} The question is in title. Let me repeat:

  What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$

I feel both NFA and DFA will take following form:

and thus both have $n+1$ states. Am I correct with this? Or the DFA needs to take following form?

I feel its not necessary to have transitions defined for every symbol for every state, mainly because it does not eliminate "deterministic" nature of the automaton. Am I right?

You can define DFAs in both ways. One can require the transition function to be total, but it is indeed fine to define DFAs without this requirement. You (or your lecturer) just choose one definition and stick with it.


Are problems in NP decidable in polynomial time by NDTMs, or just recognisable? So if we have a problem in NP, does that mean that we can create, by definition, a NDTM that always accepts or rejects in polynomial time?  The alternative I'm thinking of would be if the NDTM could only be guaranteed to accept in polynomial time.  Rejecting could take longer or forever.

The decision problems studied in computational complexity theory are all decidable. One cannot define the worst-case time complexity for Turing machines that may fail to halt.


DRAM write operation In a typical read operation from a dram chip, all the banks are equipped with sense amplifiers which select one bit from each bank using column multiplexer.
But how does write operation takes place? How does only one column in a bank is written in a particular row?

When reading the row then bits are amplified and sent back on the line as part of the feedback circuit. The bits are also stored in a small chunk of SRAM where they are cached for reads and writes.

writes to the rows don't happen immediately, only when unloading the data from the cache.

When unloading the cache the feedback circuit normally used to refresh the data is overridden with the new values in the row. All bits of the row are written.


execises in computational complexity I am trying to get better in proofs and deep understanding of concept of computational complexity. Unfortunately, so far, with no success.

In order to get more intuition, I decided to do more exercises, but most of them are still difficult for me.

I am looking for exercises with solutions in field of computational complexity. Sometimes on course pages there are homeworks with solutions.

I am asking if you aware about any decent course on computational complexity with exercises and solutions on course page, please let me know.

I had a course held by Jiri Srba a few years ago on basic complexity and computability theory is good, I would say. The second part (Lecture 9 to 15) goes through time and space complexity, shows some important results on the field and has pdf's of both exercises and solutions for each lecture.
It is based on the book "Introduction to the Theory of Computation" by Michael Sipser, which also has a good walkthrough of both topics in general.

Link: https://intranet.cs.aau.dk/education/courses/2010/cc/course-plan/ (owned by Aalborg University)

Good luck!


Time Series Prediction with an LSTM I have a time series that I want to predict with an LSTM.  I am able to get very good results using 50 datapoints predicting 51, but I struggle to get any accuracy using something like 200 datapoints to predict 220.  After an epoch, my network outputs 0 for all inputs.  Is there a technique for predicting multiple timesteps ahead of the final output with a neural network?

For example, would it make more sense to predict 1 timestep ahead 20 times in a row feeding the outputs back in to get to that 20th timestep?  Training it on a sequence followed by the timestep 20 ahead does not seem to work so far.

Yes, you could try applying the LSTM iteratively 20 times.  In other words: use the first 200 datapoints to predict the 201th; then use datapoints 2..201 to predict the 202th; and so on, until you predict the 220th.  You'll have to evaluate how well this works on a test set; it might work, or it might not.

This could still fail badly.  It could even be that there is just no way to predict 20 timesteps out.  For instance, it's possible that the short-term correlation is high but the long-term correlation is low.  Think of the weather: it's possible to predict tomorrow's weather with relatively high accuracy, but seems to be extremely hard to predict the weather 3 weeks out.  So there might just be fundamental barriers to making predictions that far into the future.


Fast computing of a matrix power for large integer values in C++ I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix.
My objective is to compute the power of the squared matrix M^t for very large t values (for example t = 4000).
I work in R and I have used the R function matrix.power from the matrixcalc R package.
I'm exploring the possibility to write a code for matrix power in C++ and then import it in R through the R package Rcpp.
One alternative would be to use the matrix multiplication approach (as in the matrix.power function in R), but looking around I have understood that there might be faster approaches to calculate a matrix power.
Do you have any experience on that? Does anyone know a library in C++ that does matrix power calculation fast and efficiently?
Consider that I'm working on a Mac0s laptop with 16 GB of RAM and 4 CPUs.

Since your matrices are small $(50 \times 50)$, you  can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$.
Write $t$ in binary so that  $t = 2^{k_1} + 2^{k_2} + \dots + 2^{k_\ell}$.
Then $M^t = \prod_{i=1}^\ell M^{2^{k_i}}$. Moreover, for $k_i \ge 1$  you have $M^{2^{k_i}} = \left( M^{2^{k_i - 1}} \right)^2$, so you need at most $O(\log t)$ matrix multiplications.
Here is a pseudocode where "&" denotes "bitwise and" and "~" denotes "bitwise not":
Power(M, t):
  if(t & 1):        //Handle odd values of t (this saves a multiplication later)
     R = M;
     t = t & ~1;    //Clear the least significant bit of t
  else:
     R = I;

  i=1;
  B=M;                //B will always be M^i, where i is a power of 2
  while t!=0:
     i = i*2;         //Advance i to the next power of 2
     B = B*B;         //B was M^(i/2) and is now M^i

     if(t & i):       //i is of the form 2^j. Is the j-th bit of t set?
        R = R*B;      //Multiply the result with B=A^i
        t = t & ~i;   //Clear the j-th bit of t

  Return R;


Asserting Run Time From Big O Function Related to this, but I felt it was more appropriate to ask as a separate question:

The complexity of Shor's algorithm is of order

$$O\left(n^2\,\log(n)\,\log(\log(n))\right)$$

with $n$ the bit length of the number to be factored. This paper asserts that on a terahertz range quantum computer (i.e. $10^6$ instructions per second) a thousand digit decimal number will take 84 seconds to factorize. It makes this assertion based on taking $\log$ to be $\ln$. By changing the $\log$ base it's obviously possible to get quite different answers e.g. $\log_2$ gives a result of 460 seconds.

My question is, is it at all meaningful/correct make such precise assertions as to run time based on this information?

The base of logarithms is irrelevant in big-O notation, since
$$\log_b x = \frac{\log_a x}{\log_a b} = O(\log_a x)\,,$$
so $O(\log_a x)$ and $O(\log_b x)$ denote exactly the same class of functions.

The assertions made by the paper about how long a certain computer would take to solve some problem don't appear to be well founded.  As a minor issue, doesn't "terahertz range computer" mean $10^{12}$ operations per second, not one million per second?  But the major point is that $O(n^2\log n\log\log n)$ is not the same thing as $n^2\log n\log\log n$: it's merely a statement that, there's some constant $c$ such that, for large enough $n$, the number of computation steps is at most $cn^2\log n\log\log n$.  In particular, it doesn't tell us what the value of $c$ is: it could be $10^{-100}$ or $10^{100}$ or anything else. Further, the analysis is never sufficiently precise to equate some number of "computation steps" with an actual number of machine instructions.

You simply cannot turn an asymptotic expression such as this into a running time in seconds without more information.  One possible way to obtain the value of $c$ would be to time the actual execution of the program, but this isn't possible as we don't have any quantum computers that can run Shor's algorithm on $1000$-digit numbers. I don't see anything that would enable the authors of the paper to give precise wall-clock running times for a program on a computer that doesn't exist.

It appears that the authors are using $\ln$ to denote base-$2$ logarithms, since they say that a $k$-digit number equates to $k\ln10$ bits.  A  1000-digit number is about 3300 bits and
$$3300^2\log_2 3300\log_2\log_2 3300\approx 451\times 10^6\,,$$
so that's certainly not where the $84$-second claim comes from.

It seems, in fact, to come from interpreting $\ln$ as meaning the natural logarithm. Based on the incorrect claim that a $1000$-digit number has $1000\log_e 10\approx 2300$ bits, we get
$$2300^2\log_e 2300\log_e\log_e2300\approx 84\times 10^6\,.$$
This calculation is not meaningful in any way.


TM1 accepts w1 vs TM1 halts on w1 What is difference between following two problems, their decidability and recognizability status:

Given Turing Machine TM "accepts" given string w.
Given Turing Machine TM "halts on" given string w.

I feel first problem means,

  whether given TM "halts by accepting" given string

and second problem means,

  whether given TM "halts by accepting or rejecting" given string

If I am correct, then is their any difference between their decidability and recognizability status?

For 2nd language, if TM accepts w, then it will eventually halt, but if it does not accept w, then it may keep looping infinitely. Hence its undecidable but recognizable.

I believe 1st problem is subset of 2nd problem and hence it is definitely recognizable. But I am confused about decidability of 1st problem, since it eliminates "halt by rejecting" criteria from 2nd problem. Does that make it decidable?

Your intuition is correct in defining the two problems. In fact accepting also means halting but halting does not necessarily mean accepting (it could also reject).
Remember that when a Turing Machine is run on an input it can do three things: Accept, Reject, Loop Forever.
In the first two cases the machine stops, in the third obviously not.

As for decidability, note that both problems are the Halting Problem because the first case  implies a halting, even if it excludes the fact that
the arrest is due to reject, therefore they are both undecidable.


A variant of travel salesman problem in grid graph In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. The problem is to determine the starting position and the directions of robot so it can cover the whole grid (also in some situations there can be no solution). An example of this game is shown below, where the starting position is chosen to be near the lower right corner, in this example, robot fail to cover the whole places. The movement constraint of robot is similar to ricochet robot but this robot can only visit a place once. I want to know if this problem has been studied before and if there is efficient algorithm to solve it. Currently I just use depth first search to attack this problem, which is quite slow on a large grid. I think this problem can be transformed into a boolean satisfiability problem. I found that this problem is called full house and is published by Erich Friedman.

This is similar (but not identical) to the game Zen Puzzle Garden. The important difference for the purposes of your question is that in ZPG you can also have “walkable” squares which the robot (or rather monk, in that game) can walk freely across without leaving a trace.

It is known that ZPG is NP-complete, but our proof makes critical use of these walkable squares and so it does not extend to this problem.

When I was working on the proof above, I spent some time thinking about whether it was possible to show NP-hardness without using walkable squares, but without success. As far as I know the question is still open.


Church–Turing thesis and infinite Turing machines What exactly is the definition of church turing thesis? It's really confusing.
I want to prove the following statement:

A Turing machine with infinitely many states is more powerful than a regular Turing machine, as it can accept all languages.

How does this statement not contradict the Church–Turing thesis?
I don't exactly understand the definition of the Church–Turing thesis, and how it applies in this context.

The Church–Turing thesis is the following philosophical claim:

Our intuitive notion of computability coincides with the mathematical notion of computability.

Here the mathematical notion of computability states that a language is computable if some Turing machine computes it, and the intuitive notion of computability is necessarily vague.
Turing machines with infinitely many states can compute any language (exercise), and so are more powerful than the usual Turing machines, which can only compute computable languages. We know that not all languages are computable. Indeed, almost all languages are uncomputable, since there are only countably many computable languages, but uncountably many languages. Also, certain concrete languages such as the Halting Problem are known to be uncomputable.


Speeding up a program solving Icosoku I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin."

I created a computer program which solves this puzzle by randomly choosing any two triangular tiles and then exchanging them (giving each tile a random orientation) if and only if the total discrepency (which can be measured in various ways) between each number on the pins and the total number of dots on the five joining corners of each pin decreases. But I have found that it takes hundreds or even thousands of iterations to finally get a solution for most initial configurations. I would like my program to take less time. Any suggestions?

Another technique that may be suitable for your problem is backtracking. It is often used for solving puzzles such as 8 queens problem, sudoku, etc.


How to verify a property about a certain order of events in TCTL / UPPAAL? I'd like to check if a certain order of events happens if another property holds true using UPPAAL and TCTL.

If A==true then eventually (B==true and eventually (C==true and eventually (D==true)))

But since "In contrast to TCTL, Uppaal does not allow nesting of path formulae." I'm not sure how to do this.

What I'v got so far is only something like:

E$\diamond$ (A && B)

E$\diamond$ (A && C)

E$\diamond$ (A && D)

Under the assumption that your property can be interpreted in an intuitive way, as it is written, it seems that you can formulate it both in LTL, as:

a => F(b && F(c && F d))

and in CTL, which in the given example is equivalent to TCTL, due to lack of timing constraints (you may assume they are of form [0, inf) and consider a TCTL formula as a CTL formula), as:

a => AF(b && AF(c && AF d))

but not in the logic supported in UPPAAL. Your property requires nested quantifiers, which are not supported in UPPAAL (as you suggested).

In general, it is not possible to model properties like a => F b ("whenever a is true, b should be true eventually") directly in UPPAAL. A workaround that might work is to consider all states in which a holds as the initial states and then formulate and check AF b. Of course, since you have multiple of such nested formulas, this does not seem possible in your case.
Note that such properties require that for all reachable states X where a is true, there should be a state y (reachable from X), such that b is true in y (which does not fall into category of supported classes of properties in UPPAAL such as "liveness" and "safety").

Since you are trying to express a property that requires a nested CTL formula, UPPAAL is not suitable to formulate and model-check it. You should try SPIN or other tools that support full CTL.


Order Notation - Why can't $c$ be in terms of $n$? For $f(n)$ to be in $O(g(n))$, there must exist a $c > 0$ and $n_0 > 0$ such that

$$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\,.$$

I found a solution to a question where my $c$ is in terms of $n$, but my friend says you can't have that. I'd like to understand why.
My thought process is: if I am given an $n$, I can pick a distinct $c$ that will satisfy the requirements above by using the $c$ in terms of $n$ relationship.

Thank you.

Suppose we define $f(x) = O'(g(x))$ to mean that there is a function $c(x)$ such that $f(x)\leq c(x)g(x)$ for all sufficiently large $x$. Then $f(x) = O'(g(x))$ for almost every pair of functions $f$ and $g$, just by taking $c(x)=f(x)$. So, this definition just isn't a useful way to compare functions.

(I say "almost every pair" because there are issues if we have infinitely many values of $x$ for which $g(x)=0$ and $f(x)\neq 0$ but I don't think it's worth pinning down exactly what functions work and what don't.)


What is the name two mutually idempotent functions? To clarify, in haskell, there is an ord function that gives the byte integer of a character (i.e. ord 'a' yields 97); and there is a char function that takes the byte integer of a character and returns the character (i.e. char 97 yelds 'a'.

What is the name of a collection of such functions? I'm not very mathematically literate (I'm working on it), but I found semirings on wikipedia. Do semirings provide an appropriate description?

These are known as inverse functions. For example, the mappings $x \mapsto 2x$ and $x \mapsto x/2$ are inverses of each other, as are $\exp$ and $\log$ (restricted to positive numbers), or $\sin$ (restricted to the interval $[-\pi/2,\pi/2]$) and $\arcsin$.


Why is Knapsack and ILP NP-complete I have a question concerning several NP-hard problems and why they are (or are not NP-complete).

I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and also in NP (we can verify its solution in polynomial time).

I know that Traveling Salesman (TSP) is NP-hard but isn't NP-complete (NPC), because in order to verify its solution, we would need to check that no better solution exists and hence solve it in polynomial time (so its not in NP).

However, problems like Knapsack or ILP (Integer Linear Programming) are said to be in NPC. Why is that? Isn't there the same analogy as with TSP? If someone gives us a solution and claims it is optimal, we would need to verify that no better solution exists and therefor solve these problems to obtain it in polynomial time.

Why is ILP and Knapsack in NPC and not just NP-hard? I hope my question is not too confusing, I will try to rephrase it if so.

As discussed in the comments, this question hinges around subtleties of the definitions. NP is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" is automatically excluded. Natural problems come in a number of variants and it's sometimes important to distinguish between them.

To a complexity theorist, the travelling salesman problem (TSP) is exactly the following problem:

Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities, and a target distance $d$.
Question: Is it possible to start at one of the cities, visit every other city exactly once and return to the starting city while travelling total distance at most $d$?  (Equivalently, does the shortest such route have total length at most $d$?)

Then there is the following optimization problem, MIN-TSP:

Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities.
Question: What is the shortest distance it is possible to travel in order to start at some city, visit each of the others exactly once and return to the start city?

There are also other variants:  F-TSP (function-TSP) has the same input as TSP but the output is a route of length at most $d$, if one exists, and "no", otherwise, rather than just yes or no; F-MIN-TSP is the analogous version of MIN-TSP.

These problems are all inter-related but they're not the same problem. In particular, only TSP is a decision problem: MIN-TSP is an optimization problem and the F- problems are function problems.  TSP itself is NP-complete. If you can solve MIN-TSP, you can clearly solve TSP by computing the minimum and comparing it against $d$, so MIN-TSP is NP-hard (but can't be complete because it's not a decision problem so it's not in NP).  Conversely, if you can solve TSP and you're allowed to make multiple TSP queries, then you can solve MIN-TSP by binary search.

For the function versions, being able to solve F-TSP clearly allows you to solve TSP: if F-TSP gives you a route, say "yes"; otherwise, say "no". Similarly for F-MIN-TSP.  On the other hand, it's not clear that being able to solve TSP helps you solve F-TSP: being told that it's possible to visit the capitals of the 48 contiguous states and Washington, D.C., while travelling a total of less than 11,000 miles doesn't seem to give you much of a hint as to what the route would be.

Your other two examples have the same families of variants. The standard Knapsack problem has a tarvet value $v$ and asks if your knapsack can carry items of total value at least $v$; OPT-Knapsack asks what is the greatest value you can carry. ILP asks if the linear inequations have an integer solution; OPT-ILP asks for the maximum solution.  In both cases, the decision version of the problem is NP-complete and the optimization version is NP-hard.


Recursive Algorithm Copying Array vs. Time Complexity If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$.
However, what will occur if the array is NOT passed by referenced and rather by value.
This means that the recursive call will have to first copy the elements of the array (half the original items).
Does this mean that the resulting time complexity for a pass-by-value binary search using an array is $O(\log(n)\cdot\log(n))$ or $O(\log(n)^2)$?

The first point is that as in the most binary search implementations we are passing an array with their sub-indices each time, and in the common programming languages, arrays are passed by reference this problem cannot happen.

However, if this copy happened each time this would be $n+\frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^{\log(n)}} = \Theta(n)$.
Hence, time complexity of this algorithm which copies half of the passed array would be $\Theta(n)$.

Moreover, if the implementation passed the whole of the array each time and control the search using sub-indices, the time complexity would be worse and it would be $\Theta(n\log(n))$, as each time ($\log(n)$) copy the whole of the array with size $n$.


Are probabilistic search data structures useful? A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these bounds only hold as long as the structure of the SkipList is sufficiently "balanced". In particular, with probability $1/n^c$ for some constant $c>0$, the balanced structure might be lost after inserting an element.

Let's say I want to use a skip list as a storage backend in a web application that potentially runs forever. So after some polynomial number of operations, the balanced structure of the SkipList is very likely to be lost.

Is my reasoning correct? Do such probabilistic search/storage data structures have practical applications and if so, how is the above problem avoided?

Edit: I'm aware that there are deterministic variants of the SkipList, which, are much more complicated to implement in comparison to the (classic) randomized SkipList.

I don't think there is a polynomial probability for losing 'balance'. After you insert an element in a skip list, you build a tower of copies above it by flipping a coin until it comes up heads.

So you have layers with fewer and fewer elements as you reach the top. Since a tower has height $k$ with probability $2^{-k}$, there is an element at height $k$ with probability (union bound) of less than $n/2^k$. Hence having an element at level $c\log n$ has probalitiy less than $1/n^c$. Towers of height $\omega(\log n)$ have subpolynomial probability. Let $M$ be the maximum level, then we have

$$E[M] = \sum_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum_{k\le \log(n)} n/2^k = \log(n) + 2.$$

Furthermore, on level $k$ there are $n/2^k$ elements with very high probability, as this is the sum of $n$ independent random variables and you can use Chernov's bound.

Since you can also show that you only do a constant number of steps per level (with very high probability!), search costs are logarithmic.

So you would have to be very unlucky indeed to end up with an unbalanced list. Note that 'luck' here is independent of your data, unlike for example in unbalanced search trees. Coin flips in Skip Lists are always random.

As far as I know, skip lists are of great practical interest, because it is relatively easy to implement them as lock-free search structures, with the obvious benefits. B-trees on the other hand are rather difficult to make performant under concurrent accesses.


Algorithm to find most nodes in distinct cycles I am trying to design a program where people trade objects within a fixed set of objects.   They offer a single product, and designate a set of products they are willing to accept for that product.  The job of the program is to involve as many people in a trade as possible.

To do this, I create a directed graph, where each edge points from a person who will give a product to a person who wants that product.

I want to find the distinct cycles (they don't share a node) that cover the largest subset.

How would I do that?

Your problem is NP-complete (formulated as a decision problem), by reduction from SAT. For simplicity, I describe a reduction that uses self-loops, but they can easily be avoided.

Given an instance of SAT, create nodes for each variables and each clause. For each assignment of each variables, add directed cycles connecting the variable node with clause nodes satisfied by this assignment, for all possible such subsets (the empty subset corresponds to a self-loop). Since there are no parallel edges, we can also think of these cycles as resulting from a single cycle going through all satisfied clauses by taking all possible shortcuts not avoiding the variable node.

In the resulting graph, it is possible to cover all nodes of and only if the formula is satisfiable, completing the proof.

In practice, it might be possible to find good solutions heuristically, but that could depend on the nature of your instances.


Find ellipsoid that contains intersection of an ellipsoid and a hyperplane I have an $n$-dimensional ellipsoid $E$ and a hyperplane $H$. This hyperplane cuts $E$ into two parts: $E_1$ and $E_2$ (whose disjoint union is $E$). I want to find another ellipsoid $E'$ that has minimal hyper-volume and contains $E_1$.  Is there an efficient algorithm to do this?

My first thought was to formulate it as an optimization problem, but I am having difficulty with formulating it, as I don't know how to formulate the containment ($E_1 \subseteq E'$) constraint.

An approximation for the minimal hyper-volume ellipsoid is also good for my needs.

Your are describing the basic step in the ellipsoid algorithm. Your question might be answered in lecture notes on the algorithm, such as these ones by Goemans.

More generally, given a convex body $K$, the minimum volume ellipsoid containing it is called the Löwner–John ellipsoid. The same name is also given to the maximum volume ellipsoid contained in $K$. See for example these lecture notes of Boyd and Vandenberghe.


Bounded Quadratic Congruence Problem Variant (for square Residue) This is a follow up to the following question: Bounded Quadratic Congruence Problem Variant (for some specific Residue)

As indicated that for square residue the problem is solvable in polynomial time. Let us consider a modified version of the same problem:

Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x<L$ such that $(M*x)^2≡a(mod\ b)$?

where $M$ is some positive integer constant, $a$ is a residue that is also a square.

Can the same approach be used to solve this slightly modified problem easily? It seems so but I am not sure.

The problem is NP-complete.  Let $d = \gcd(M,b)$.  If $a$ is not a multiple of $d$, then there is no solution.  Otherwise, let $a' = a/d$ and $B = b/d$ and $c = M/d$ and $A \equiv a' c^{-2} \pmod B$.  Then the original equation has a solution if and only if $x^2 \equiv A \pmod B$ has a solution with $x<L$.  As you previously noted, the latter problem is NP-complete.


Combinator equivalent to eta conversion In lambda calculus, one can prove that two expressions compute the same function if they are equivalent under both beta reduction and eta conversion, where eta conversion consists of eta reduction,
$$
(\lambda x.A x) \to A \qquad\text{if $x$ is not free in $A$}
$$
and eta expansion,
$$
A \to (\lambda x.Ax) \qquad\text{where $x$ is not free in $A$.}
$$
Thus, while one cannot computationally check whether two expressions compute the same function, one can computationally verify a proof that they do, if someone produces a sequence of beta reductions and eta conversions that takes one expression to the other. The reason that determining equality between expressions is undecidable has to do with the need to use eta expansions as well as contractions, so you have to backtrack to search for a proof.

My first question is: is the above characterisation correct? It seems to be from what I've read, but I haven't seen it explained in exactly that way and I might have misunderstood.

My second question is, does eta conversion exist in the combinator calculus, or is there an equivalent? In other words, is there a set of formal manipulations on combinator expressions that can be used to show that two are equivalent to one another?

As a simple example, the expressions $S\,K\,K$ and $S\,K\,S$ are equivalent. (They are both the identity function.) I can show this by explicitly evaluating both of them:
$$
(S\,K\,K)\,x = (K\,x)\,(K\,x) = x,
$$
whereas
$$
(S\,K\,S)\,x = (K\,x)\,(S\,x) = x.
$$
But this involves introducing variables (i.e. moving away from "pure" SK combinator expressions), and it doesn't proceed by starting from one expression and manipulating it to convert it into the other. Is there a set of syntactic moves that can be used to show this equivalence, analogously to eta conversions in lambda calculus?

From the Barendregt lambda calculus book, we can find theory $CL$ (combinatory logic) defined as follows

$$
    K P Q = P \qquad
    S P Q R = P R (Q R)
$$

where $K,S$ are constant symbols (for the well known combinators), while $P,Q,R$ range over all the possible $CL$ terms (built from $K,S$, variables and application). The relation $=$ is postulated to be a congruence.

The $CL$ theory can be extended with the following $A_\beta$ axioms:

$$
\begin{array}{ll}
A.1 & K = S(S(KS)(S(KK)K))(K(SKK)) \\
A.2 & S = S(S(KS)(S(K(S(KS)))(S(K(S(KK)))S)))(K(K(SKK))) \\
A.3 & S(S(KS)(S(KK)(S(KS)K)))(KK)=S(KK) \\
A.4 & S(KS)(S(KK)) = \\
    & \qquad S(KK)(S(S(KS)(S(KK)(SKK)))(K(SKK))) \\
A.5 & S(K(S(KS)))(S(KS)(S(KS))) = \\
    & \qquad S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))S))))(KS)
\end{array}
$$

(I have double checked these, but I can't swear I got them right.)

Corollary 7.3.15 states that $CL\ +\ A_\beta$ is equivalent to $\lambda$ (the theory of the $\lambda$ calculus with $\beta$ conversion, but no $\eta$ or extensionality).

Hence, in principle one can use "only" the above laws to prove $SKK=SKS$.

The convenience of the above laws is self-evident, I think.

A similar set of axioms is found in the same book for $\lambda\eta = \lambda + \bf ext$. These are $A.3,A.4,A.5$ (hence no $A.1,A.2$) and

$$
\begin{array}{ll}
A.6 & S(S(KS)K)(K(SKK)) = SKK
\end{array}
$$


Shortest path with odd weight Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.

We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph.

If possible, describe one algorithm that is reduction-based (that is, make some modification to the graph so that application of Floyd-Warshall, or any other "known" algorithm, and then deciphering the answer will give the result, see http://en.wikipedia.org/wiki/Reduction_(complexity)) and one that is "direct" (that is, make some modification to Floyd-Warshall in order for it to solve this problem).

Homework? I start with hints. Integer values assumed.

Reduction. Make two copies of the vertices in the graph (odd and even) and rewire the graph such that each odd length edge of the graph is between the even and odd copies.

Direct. The algorithm keeps two values (for each pair of vertices): the length of the even length and odd length shortest paths. You can adapt Floyd if you realize that odd+odd = even (etc).


CPU pipelining stages I have read that in some pipelined architectures, memory access requires more than just one clock cycle. In that case how does processor handles the next instruction if the next instruction tries to access something the previous memory instruction has yet to write to its register files?

There are many ways this kind of situation be handled.

Clever compilers

If you are are writing the contents of, lets say register 5 to the memory location 0x12345, and the next instruction is reading from the memory location 0x12345 and the variable allocated at memory location 0x12345 is not "volatile", compiler will optimize your code so that the next instruction will use the contents of register 5, instead of reading data from the memory.

Instruction reordering

Ordering of the instructions are changed so that the next instruction is pushed down, as far as required without compromising the outcome of the program. This way, more non-dependent instruction can be executed until the memory write is complete.

Multiple threads

When the scheduler detects that there is a read after write dependency, it can pick another thread for thread for the IF stage. That way, the current thread will stay inactive until the memory write is complete. Once completed it becomes active again, and will get picked up by the scheduler when a similar situation arises for the current thread.

Bubbles

And of course, you can have many bubbles in the pipeline, until the write is complete :-). BTW, this is a bad idea.


What is the advantage of heaps over sorted arrays? I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default.

And a follow up: what is the advantage of dealing with the complexity of inserting into a heap given an algorithm like quick sort handles sorting very well?

Context: I'm working through CLRS / MIT 6.006 in python and have only seen integer representations of leaf values. Is this more applicable in a language like C where each leaf contains a struct that can't easily be sorted?

$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ respectively if you implement a min/max-heap by a binary tree.

Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). $\small \texttt{find-min}$ and $\small \texttt{delete-min}$ are of $\small \mathcal{O}(1)$ complexity if $\small \texttt{insert}$ is not required in your application, since you can maintain a pointer $\small p$ that always points to the minimum element in your array. When the minimum element is removed, you just need to move $\small p$ one step to the next element in the array.

Dealing with insertion in a sorted array is not trivial. Given a new element $\small e$, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be $\small \mathcal{O}(n)$) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires $\small \mathcal{O}(n\log n)$ time however.

The last point, how you implement a data structure really depends on your application. NO single implementation is best for all cases. Analyze your application, find out the most frequent operations, and then decide the appropriate implementation.


calculate lower bound of busy beaver Let $m$ be the number of states (without the halting-state) of a deterministic turing-machine with $\Sigma$ = {} and $\Gamma$ = {$\square$, 0, 1}. Let $G(m)$ be the maximum number of ones, which can be generated by a deterministic turing-machine, before going into the halting-state. Prove that $G(m)$ $\in$ $\Omega(2^m)$. (This is about the so called "busy beaver" problem, with the mathematical rado-function $\Sigma(N)$ or $bb(N)$.) Who can me help with that?

All you need to do is show that a machine with $m$ states can halt with $\Omega(2^m)$ 1's on the tape.

There are many ways to prove this. This is just one suggestion, and it may be sub-optimal.

Let $T$ be a machine that on a word of the form $0^i1^j$, when the head is in the leftmost $0$, halts with $0^i1^{2j}$ on the tape and the head at the leftmost $0$.

$T$ is a fixed machine, and thus has $t$ states, for a constant $t$.

We now construct the machine $M_i$ as follows: first, $M_i$ writes $0^i1$ on the tape, using $i+1$ states. It then moves the head to the left most cell, using another single state.
Then, if the leftmost cell is $0$, it erases it and passes control to $T$ (this requires $t+1$ states).
If the leftmost cell is $1$, it halts.

$M_i$ has $i+2+t$ states, and after it halts the tape contains exactly $2^i$ 1's (since in every call to $T$ we double the number of 1's, and we call $T$ $i$-times).

Thus, if $M_i$ has $m$ states, it halts with $\frac{2^m}{t+2}\in\Omega(2^m)$ 1's, and we are done.