How to prove that problem is not in P Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?

The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-hardness of HALT), which contradicts the time hierarchy theorem. We conclude that HALT is not in P.

Consider now a different problem, REGEXP-INT, in which given a list of regular expressions, we have to decide whether their intersection is empty. This problem is coPSPACE-hard, and so if it were in P, then P=PSPACE. While we don't know for sure that P is different from PSPACE, this is widely conjectured (and follows from P$\neq$NP), and assuming that, we conclude that REGEXP-INT is not in P. We call this a conditional result. Similarly, SAT is NP-hard, and so unless P=NP, SAT is not in P.

The unconditional results invariably use one of the hierarchy theorems, and so eventually, diagonalization. This technique itself cannot separate P from NP, due to the so-called "relativization" barrier (though non-black-box diagonalization still stands a chance).


efficiently calculate nearest common ancestor in a family tree (each person has two parents) I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent).  Just iterate back to root for each person, then walk back from root tossing off anything common.

In a matriarchal society, for example, this could be used to quickly calculate how any two people are related as long as only the mothers are considered.

But if both parents are considered, eg mother AND father, then the algorithm just described breaks down.

So I wondered is there an algorithm to tell two people how they are related in a family tree where both parents are considered?  For example, see the Icelandic genealogy app (https://www.islendingabok.is/) which does precisely that.  How's it done, algorithmically speaking?

Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately the same number of generations back on each side.

Indeed, this is exactly what you should do on a tree: going all the way back to the root and then discarding all common ancestors after the first takes more time.


Why does the concatenation operation imply the empty string? I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular expressions. He does this by giving regular expressions, breaking them down into simpler regular expressions that represent the constituent pieces of the whole expression, creating a finite automata for each piece of the expression, and finally connecting them with the finite automata at the bottom that accepts the language described by the regular expression.

One of his examples is the sequence of finite automata in the picture attached, meant to illustrate how one might work through creating a finite automata that accepts the regular expression $(a\cup b)^* aba$.

With his definitions of union, concatenation, and star below.

Concatenation: $A+B=\{xy\mid x\in A\wedge y \in B\}$

Star: $A* = \{x_1x_2...x_k \mid k\geq 0 \wedge x_i \in A\}$

Union: $A\cup B = \{x\mid x\in A\vee x\in B\}$

At one point in the book he explains that two characters next to one another with no symbol between can imply concatenation so I am interpreting the "$aba$" piece as $a+b+a$.

I would think a finite automata that accepts $aba$ would have four states, with an "$a$" transition arrow between the first and second states, a "$b$" transition arrow between the second and third states, and an "$a$" transition arrow between the third state and the accept (fourth) state. The diagram instead is similar to what I imagined but adding a state with an empty string transition arrow between each state I described. See the 5th diagram, given for expression $aba $below $(a \cup b)^*aba$ illustrating how one might go about constructing a finite automaton that accepts the language described by that regular expression.">

These states with associated empty string transition arrows appear in both of the regular expression examples with concatenation he gives, so I must be misunderstanding something. There's a section in the book when he introduces nondeterministic finite automata in part of an effort to prove that regular languages are closed under the concatenation operation and mentions that "In general, an NFA may have arrows labeled with members of the alphabet or $\varepsilon$", and I figure the answer must have something to do with that, but I still don't understand why.

An $\varepsilon$ transition (called the empty transition from here on out) from $A$ to $B$ means that if you end up in $A$ after a transition you can go to $B$ for free without consuming a character from the input.

When concatenating $a$ and $b$, $a$ may have multiple end states so it is easier to add an empty transition from every end state of $a$ to the start state of $b$.

You can make the rule so when you concatenate all outgoing transitions of the start state of $b$ is copied to every end state of $a$ and if the start state of $b$ is not an end state then the end states of $a$ are not end states of the concatenated NFA.

This is a much more complicated rule than: every end state of $a$ is no longer an end state and gets a new empty transition to the start state of $b$.

Adding the empty transitions does not change the language being accepted and you can do a minimization/optimization pass after constructing the NFA to eliminate the excess empty transitions.

This is actually a common practice in compilers, the early code generation is dumb and does the obvious, easy and non-optimal but correct thing. Then optimization passes look for patterns that can be simplified or optimized. This means that the pattern can be optimized everywhere even when it wasn't generated by the construct that commonly creates it.


Analysing time complexity Okay so we've been given an algorithm and asked to give an upper bound to its best and worst case
weirdSort(A,r,p)

if r < p

q = (r+p)/2
BubbleSort(A,r,q)
wierdSort(A,q+1,p)
Merge(A,r,q,p)

I'm not quiet sure how to do that.. this is my first time analysing time complexity and I'm quiet lost
I know that an upper bound for BubbleSort is $O(n^{2})$ for worst and $O(n)$ for best, and for Merge is $O(n)$ for both (Merge being the function that merges the arrays in MergeSort)
So for the worst case I have
$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n^{2}\right)+O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n^{2}+c_{2}n$
and for the best case
$T\left(n\right)=T\left(\frac{n}{2}\right)+2O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n$
But now what? how do I handle $T\left(\frac{n}{2}\right)$? What are the steps I need to take in these types of questions? I feel like they've just thrown us in the water without really explaining how to solve stuff..

Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc.
Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the "best case" scenario:
Examples
$T(2) = T(1) + c_1 \cdot 2$
$T(4) = T(2) + c_1 \cdot 4 = T(1) + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (4 + 2)$
$T(8) = T(4) + c_1 \cdot 8 = T(1) + c_1 \cdot 8 + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (8+4+2)$
Opening recursion
And now (try for yourself) you can prove using induction that:
$T(n) = T(1) + c_1 \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{n}{2^k}$
Finding closed form
Notice that $\sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} = \frac{\left(\frac{1}{2}\right)^{\lfloor \log(n) \rfloor} - 1}{\frac{1}{2}-1} = \frac{1 - \frac{1}{n}}{\frac{1}{2}} \le 2$ Since it is the sum of a geometric progression.
Therefore, $T(n) = T(1) + c_1 \cdot n \cdot \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} \le T(1) + c_1 \cdot 2 \cdot n = O(n)$


Artificial intelligence and undecidibility Can artificial intelligence solve problems like Post correspondence problem?

No.  The Post correspondence problem is undecidable.  That means that no computer program can solve it (in all cases).  "Artificial intelligence" is just a computer program. Actually, "artificial intelligence" is a name for something that we're not even sure how to do with a computer program; but even if we knew how to achieve it, it would still be a computer program.  Artificial intelligence isn't magic -- anything that can be done is still constrained by the laws of physics and mathematics.


How probable is a deadlock in the dining philosophers problem I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock:

*Philosophers are represented by black beads. They think when running in small circles and eat when running in bigger circles. Forks are represented by yellow beads. The number of meals are counted.

Might it be the case that for $N=4$ participating philosophers a deadlock must inevitably be reached? Or can a situation be described in which four philosophers can eat for ever and ever?

I am looking for a quantitative model and analysis of the dining philosophers problem.

Let $N$ be the number of philosophers. Let the problem be implemented as an algorithm that takes as inputs the set $T_k$ of partial functions $t: [N] \rightarrow [k]$ with $t(i)$ being the point in time when philosopher $i$ starts trying to pick the fork to his left (maybe never). The algorithm stops when it detects a deadlock or an oscillating state in which a philosopher starves.

I wonder especially about the probability $p_{stop}^{(k,n)}$ that the algorithm will stop, depending on the number $n$ of philosophers that join the diner, $n \leq N$.

$$p_{stop}^{(k,n)} = \frac{|\text{functions $t \in T_k^n$ for which the algorithm stops}|}{|T_k|}$$

with $T_k^n$ the functions $t\in T_k$ with $|\text{dom}(t)| = n$.

the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some literature and there are some performance analyses of its probability of deadlock scenarios. here are some examples of quantitative models and performance analysis and other frameworks on the problem which attempt to consider the probability of deadlocks from theoretical derivations and observed scenarios (simulations etc).

Expected Robustness in Dining Philosophers Algorithms / Galron
Dynamic Lock Dependency Analysis of Concurrent Systems / Schrock
Performance analysis of the dining philosophers
system in dtsPBC / Tarasyuk (Dining Philosophers sec 8.1.3)


Analyzing the Runtime of Shuffling Algorithm The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. Determine the runtime of the following algorithms.
Algorithm 1:
function Shuffle(A)
Split A into two equal pieces A, and B (this takes constant time)
A = Shuffle(A)
B = Shuffle(B)
for i = 0 to len(A)/2 − 1:
        for j = 0 to i − 1 do:
            B[j] = B[j] − A[i] + Random(10)
            A[i] = A[j] − B[i] + Random(10)
B = Shuffle(B)
A = Shuffle(A)
Combine A = A + B (this takes constant time)
return A

Algorithm 2:
function Shuffle1(A)
for i = 0 to len(A) − 1:
    for j = 0 to i − 1:
        for k = 0 to j − 1:
            A[k] = A[k] + A[j] + A[i] + Random(m)
return A

After a good amount of work, I believe that the runtime for Shuffle1$(A)$ to be $O(n^3 \cdot m^2)$ as there are three nested loops. In the innermost loop, the algorithm does the constant time array access and $O(m^2)$ work done. But, I am not quite sure. I am having difficulty tackling the runtime of Shuffle(A). Should I be using the Master Theorem in any way? Any advice and help would be greatly appreciated!

You are right about the running time of the second algorithm, i.e., Shuffle1$(A)$. Its running time is indeed $O(n^{3} \cdot m^2)$.
To analyze the running time of the first algorithm, i.e., Shuffle$(A)$, you can formulate the recurrence relation as follows:
$$T(n) = 4 \cdot T(n/2) + O(n^2)$$
Note that, Random(10) takes time $O(10^2) = O(1)$.
You can indeed solve this recurrence using the Master Theorem. The theorem gives $T(n) = O(n^{2} \log n)$ by applying Case $2$ of the theorem.

You can also solve the recurrence by the expansion method as described below:
$$
\begin{align}
T(n) &= 4 \cdot T(n/2) + O(n^{2}) \\
&= 4 \cdot (4 \cdot T(n/4) + O(n^{2}/4)) + O(n^{2}) \\
&= 4^{3} \cdot T(n/8) + 4^{2} \cdot O(n/4^{2}) + 4 \cdot O(n^{2}/4) + O(n^{2}) \\
& \quad \, \textrm{... on further expansion we get the following relation} \\
&= 4^{t} \cdot T(n/2^{t}) + \sum_{i = 0}^{t} 4^{i} \cdot O(n^{2}/4^{i}) \\
\end{align}
$$
When $t = \log n$, the value $T(n/2^{t})$ becomes $T(1)$. I am assuming that $T(1) = 1$ for the base case of your algorithm. (ttnick is asking the same question in the comment section also). Based on this assumption, we get the following relation:
$$T(n) = (4)^{\log n} \cdot 1 + \sum_{i = 1}^{\log n} O(n^{2}) = n^{2} + \sum_{i = 1}^{\log n} O(n^{2}) = O(n^2 \log n)$$.


Practical communication example for a data rate scenario Having difficulty with the following question.
I can answer parts I and II but having trouble finding a practical example.
Question:

Compute the maximum data rate of the following communication links;
I) 4000Hz bandwidth and a signal to noise ratio(SNR) of 20dB;
II) noiseless channel of 2.4GHz bandwidth with 64 signalling levels;
Provide a practical communication example for each scenario.

Any help would be greatly appreciated.

4kHz bandwidth and 20dB SNR is telephone communication.
2.4GHz with 64 signaling levels is WiFi with 64QAM if I understood correctly. In that case bitrate is 6 * baud.


Select a set of elements from a 2D matrix, such that each element comes from distinct row and column We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that

Each element in the set comes from a unique row and column combination. That is, once you've selected an element (i, j) as a candidate for a set, that set cannot contain any elements from ith row or jth column.
The size of the set is Maximized. The Matrix may contain NaNs, so it may not be possible to find a set of size n.
The sum of elements on this set is minimum over all sets of this size for this Matrix.

For Example, consider following matrix -

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

This is artificially constructed to demonstrate the problem, solution for this Matrix is going to be the diagonal elements

{1, 1, 1, 1}

Any ideas?

Just to be sure, this is not a homework problem. We're trying to solve this for a client. Problem we're trying to solve is in Transport domain, and basically boils  down to problem statement above.

I've tried to think of a polytime solution, but the first condition seems to be problematic. If it was not in place, this would have been a trivial DP problem - create a temporary 2d array, traverse each row of original array, and for each element, try to find element in last row in temporary array that has the smallest cumulative sum. Make this element's value in temp_arr smallest cumulative sum + this element. Find smallest element in last row and you're done.

I'm trying to see if there is a polynomial time solution. In all probability, it will be easier to code, verify, and debug than any graph theory based solutions.

Edit added after some search -
Just realized that what I was looking for was Hungarian Algorithm for Assignment problem - https://en.wikipedia.org/wiki/Hungarian_algorithm

This is maximum matching in a weighted bipartite graph in disguise. (You can easily convert your objective of minimizing the sum of weights into one of maximizing it.)


Are there any established methods for generating random graphs/networks that are both planar and meshlike? There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs.  I am looking for methods to generate random graphs that (1) are planar, and (2) have the quality that they are arranged in a lattice-like or mesh-like pattern, such that all connections are "nearby" connections only, and local loops are ubiquitous.
I suppose one could start with an actual 2-dimensional rectangular lattice, and then start randomly moving or adding edges in ways that preserve the planarity.
Thanks in advance for any thoughts, or references to known methods!

You could take the Delaunay triangulation of a random set of points (or, if you want almost lattices, a perturbation of something regularly defined) and remove some edges if you want.
This won't give you a small-world graph, but no lattice-like thing would. If you want something like this, you'll have to have some fractal properties anyway (if the connections are "nearby", then you'll need a lot of connections to go far).
If you want something scale-free, you can generate a Delaunay triangulation hierarchy instead -- which is a beautiful and useful tool of computationnal geometry so you'll find lots of references. The idea is to have a Delaunay triangulation on a small number of point, and then a Delaunay triangulation inside each triangle, and again, etc.


High-dimensional geometry and P vs. NP Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered at the origin. We perform the following cut-and-color operation $m$ times, each time for a clause.

Let’s say there are $k$ literals in this clause. For the $i$th literal with variable numbered $x$ and sign $s$, we cut the hyper-cube or what is remaining with the hyper-plane perpendicular to $x$th axis and keep the $s$-signed half. After $k$ times cutting, color the remaining part red.

If, after all clauses have been processed this way, the entire hyper-cube is red, announce UNSAT. Otherwise announce SAT.

This is the problem. Basically an uncolored part corresponds to an assignment whose reverse is satisfiable, because no clause covers this assignment or, in other words, this assignment does not contain any clause when both assignments and clauses are viewed as sets.

Phrased this way, SAT is really a geometric representation problem, and the key is to keep track of colored parts with only polynomial-sized storage.

Question: What is known about high-dimensional geometry of a hyper-cube, especially related to this problem? My current difficulty is with visualization.

Difficult example: Consider the following simple CNF formula:
$$(x_1\lor x_2)\land(x_3\lor x_4)\land\cdots\land(x_{2k-1}\lor x_{2k}),$$
or in DIMACS format

1 2
3 4
...
2k-1 2k

where $k>0$. The challenge is to represent the colored parts by (preferably polynomially many) non-overlapping clauses only. Below is the best I can do:

$k=1$:

1 2

$k=2$:

1 2
-1 3 4
1 -2 3 4

$k=3$:

1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6

$k=4$:

1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6
-1 -3 -5 7 8
-1 -3 5 -6 7 8
-1 3 -4 -5 7 8
-1 3 -4 5 -6 7 8
1 -2 -3 -5 7 8
1 -2 -3 5 -6 7 8
1 -2 3 -4 -5 7 8
1 -2 3 -4 5 -6 7 8

As you can see, it's growing exponentially.

Partial question: Do you have a way to do this example (not the general problem) using only polynomially many clauses? This is the difficulty I can't handle right now. It's easy to see that the interactions among the original clauses grow exponentially with $k$. So if you can prove that this example is impossible to do, then this non-overlapping-clauses approach won't work and we need to find something else.

Code: I posted my code here. My approach was implemented but it’s still exponential without the partial problem above solved. You can observe that.

One potential weakness is that any algorithm implementing my idea can actually count the number of satisfying assignments, solving a #P-complete problem. Not only that, it remembers in memory exactly which assignments are not satisfying (one simple way to do this is to just remember the initial clauses) and it can enumerate these without much overhead, because the final clauses are non-overlapping. Is that something enough to prove my idea is always exponential-time?

The answer to the partial question is no. It’s impossible to be so efficient by a counting argument. First, there are $2^n$ cells, each of which is either colored or not. So there are $2^{2^n}$ possible configurations, each of which has to be represented in polynomial space. This is impossible.


Equivalence of Kolmogorov-Complexity definitions There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity functions (defined via different languages or models), then there exists a constant $c$ such that for every string $x$, $|K_1(x) - K_2(x)| < c$. I believe this is because for every Kolmogorov complexity function $K$ and for every $x$ it holds that $K(x) \le |x| +c$, for some constant $c$.

I'm interested in the following definitions for $K$, based on Turing-machines

number of states: Define $K_1(x)$ to be the minimal number $q$ such that a TM with $q$ states outputs $x$ on the empty string.
Length of Program: Define $K_2(x)$ to be the shortest "program" that outputs $x$. Namely, fix a way to encode TMs into binary strings; for a machine $M$ denote its (binary) encoding as $\langle M \rangle$.  $K_2(x) = \min |\langle M \rangle|$ where the minimum is over all $M$'s that output $x$ on empty input.

Are $K_1$ and $K_2$ equivalent? What is the relation between them, and which one grasps better the concept of Kolmogorov complexity, if they are not equivalent.

What especially bugs me is the rate $K_2$ increase with $x$, which seems not to be super-linear (or at least linear with constant $C>1$ such that $K_2 < C|x|$, rather than $|x|+c$).
Consider the most simple TM that outputs $x$ - the one that just encodes $x$ as part of its states and transitions function. it is immediate to see that
$K_1(x) \le |x|+1$. However the encoding of the same machine is much larger, and the trivial bound I get is $K_2(x) \le |x|\log |x|$.

I apologize in advance for that I give way too many details, but I'm about to contradict people.

About $K(x)≤K'(x)+c$

The fact that $K_1(x)≤K_2(x)+c$ usually comes from an interpreter of the description language #2 into the description language #1 and not from a translation from programs of #2 into programs of #1.

For example $K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$ and you get this inequality as simply as this:

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Then your constant $c_\mathtt{py2c}$ will be something like $528+490240688$ where $528$ is the number of bits for this code and $490240688$ bits is the size the official Python interpreter written in C. Of course you only need to interpret what is possible in your description language for Python so you can do better than 69 MB :-)

What is important is that you can write your Python program linearly in your C code. For example, a language where you need to put "BANANA" between every character is not a very good description program and the property is then false. (But if the description language authorizes you to write data in a separate file or in a block, this problem disappear)

Why your $K_1(x)=q$ is flawed

The problem with your definition of $K_1$ is that you may need more than $q$ bits to describe a Turing machine with $q$ states because you need to encode transitions.

So no $K_1$ and $K_2$ are probably not equivalent, but that's mainly $K_1$'s fault. I think that we can prove that for all $a>0$ there is a $c_a$ such that $K_1(x)≤a|x|+c_a$. Of course any $a<1$ is enough to disprove the fact that $K_1$ is not a valid function, since it would mean that we can encode more all $2^n$ possible strings of length $n$ into $an+c_a$ bits.

But the size is an incredibly tight bound when building Turing machines. The idea is that in a block of $b$ states there are $b^{2b}$ ways to find transitions for each state and that's better than the usual $2^b$ ways you can fill $b$ bits. Then you can store in each block $\log_2 b$ bits of information. (not $2\log_2 b$ because you have to go in and out the block one way or another)

So yeah... With blocks of size $2^{1/a}$ you could probably prove $K_1(x)≤a|x|+c_a$. But I already written way too much about why the number of states is not a valid Kolmogorov complexity function. If you want me to elaborate, I will.

Now about $K_2$

The naive descriptive language corresponds roughly to $K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$ (i.e. $\log_2q$ for each next state and details about write and termination).

As you seem to be, I'm convinced that a better/cheater way would be to authorize to encode "data" into Turing machine, maybe by adding a binary tag in the description language that says whether if a state is a data state (that just writes a bit and go to the next state) or if it does something else. That way you could store one bit of your $x$ in one bit of your descriptive language.

However if you keep the same $K_2$ you could use the same technique I used in the previous part to save a few bits, but I seem to be stuck at $K_2(x)≤a|x|\log|x|+c$ (for any $a>0$) .. maybe less than $\log|x|$, even, but obtaining $O(|x|)$ seems hard. (And I expect it should be $|x|$, not even $O(|x|)$.)


what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R? in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows:
the algorithm below uses a data structure containing $P$ nodes to represent the selection tree; the $jth$ node $X[j]$ is assumed to contain $c$ words beginning in $LOC(X[j]) = L_0 + cj$, for $0$ $\le$ $j < P$, and it represents both internal node number $j$ and external node number $P + j$ in Fig.63.

There are several named fields in each node:
$KEY$ = the key stored in this external node;
$RECORD$ = the record stored in this external node (including $KEY$ as a subfield)
$LOSER$ = pointer to the "loser" stored in this internal node;
$RN$ = run number of the record pointed to by $LOSER$;
$PE$ = pointer to internal node above this external node in the tree;
$PI$ = pointer to internal node above this internal node in the tree.
For example, when P = 12, internal node number 5 and external node number 17 of Fig.63 would both be represented in $X[5]$, by the fields $KEY = 170, LOSER = L_0 + 9c$ (the address of external node number 21), $PE = L_0 + 8c, PI = L_0 + 2c $
for $LOC(X[j]) = L_0 + cj$, 4 questions:

I need TAOCP's $MIX$ machine knowledge for understand this formula?

it seems that $LOC(X[j])$ is not meaning of the array or pointer, its goal is to find $X[j]$'s beginning addrss?

$cj$ is equal to $c * j$?

what's the meaning of $L_0$ ?

$LOC(X[5] = L_0 + 5c, LOSER = L_0 + 9c = LOC(X[9]), PE = L_0 + 8c = LOC(X[8]), PI = L_0 + 2c = LOC(X[2]) $,
what's the meanings about them $LOC(X[9]),LOC(X[8]), LOC(X[2])$?

according to $LOSER = L_0 + 9c$ indicates that the address of external node number $21$, so that $PE = L_0 + 8c$ indicates the address of external node number $20$, and $PI$'s address of external node number $14$, but int this case of internal number 5 and external number $17$, $20$ and $14$ are unrelated to them?

The key observation may be each array element of X (regrettably called node by DEK, just as the nodes of fig. 63) representing one internal (round) and one external (rectangular) node of figure 63 with no discernible relation.
1&2) Don't think so, for this formula it should suffice to take LOC(X(j)) as the location in MIX's linear memory of (the first word of) the jth element of array X of records of c words each (see 2nd paragraph above), a natural number from 0 to 3999. (Then, there is en.wikipedia.org/wiki/MIX)
3) yes, $cj$ is consise for $c * j$
4) $L_0$ seems to be the location of the first word of all the consecutive words representing Algoritm R's data structure
5) Those LOC()-expressions denote the locations of X's elements 9, 8, and 2, resp.
6) no relation I can see: $17$ happens to be $5 + P = 5 + 12$, the parent (external, PE) of which is (internal) node 8, coincidentally represented by the same element as (external) node 20, parent (internal, PI, used to be FI(/FE) in 1st ed.) of node 5 is 2, $14 = 2 + P$ happens to share the same element of X.


Suppose that the path consists of edges $e_1,\ldots,e_\ell$. The following answer assumes that by "subpath" you mean a partition of $e_1,\ldots,e_\ell$ into intervals. Go over all possible values of $b_1,\ldots,b_{\ell-1} \in \{T,F\}$. If $b_i = T$ then the edge $e_i$ ends an interval. Otherwise it doesn't. Here is how this looks in your case, $\ell=4$:
$$
\begin{array}{ccc|c}
b_1 & b_2 & b_3 & \text{subpath} \\\hline
F & F & F & e_1e_2e_3e_4 \\
F & F & T & e_1e_2e_3;e_4 \\
F & T & F & e_1e_2;e_3e_4 \\
F & T & T & e_1e_2;e_3;e_4 \\
T & F & F & e_1;e_2e_3e_4 \\
T & F & T & e_1;e_2e_3;e_4 \\
T & T & F & e_1;e_2;e_3e_4 \\
T & T & T & e_1;e_2;e_3;e_4 \\
\end{array}
$$


Turing degree incomparable with any countable-ordinal jump of another Turing degree? Among the Turing degrees are degrees of the form $0^n$, e.g. $0$, $0'$, $0''$, etc.

I'll just prove this quick for completeness' sake.  Hopefully nobody has any qualms with this short proof:

Lemma: Any countable set of sets of natural numbers can be encoded as a single set of natural numbers, such that each original set can be decoded by a Turing machine.

Proof: Let $S$ be our set of sets, so that each $S_n \in S$ is a set of natural numbers.  Define $O = \{k \cdot 2^{n+1} - 2^n | k \in S_n \}$.

Thus, $S_n = \{ k | k \cdot 2^{n+1} - 2^n \in O \}$.  Clearly, for each $S_n$ there is a Turing machine that computes $S_n$ given an oracle for $O$.

Minor Theorem: Any countable set of Turing degrees has an upper bound.

Proof: Let $D$ be our countable set of degrees.  Thus, each $D_n \in D$ is a countable set of sets of natural numbers.  Let $E_n$ be a set of natural numbers that encodes the elements of $D_n$, and let $E$ be a set of natural numbers that encodes all $E_n$.

Any set in any degree $D_n$ can be computed by decoding $E$ twice in succession, so as Turing degrees, $D_n \leq [E]$.  Therefore $[E]$ is an upper bound of $D$.

Let $0^\omega$ be the upper bound of $\{0, 0', 0'', ... \}$ as described just above.  Of course, we can take the Turing jump of $0^\omega$ to obtain $(0^\omega)'$ which we will write $0^{\omega + 1}$, and so on to obtain the countable set of Turing degrees, $0^{\omega + n}$.  Taking the upper bound of these, we obtain $0^{2 \omega}$, and of course, furthermore taking the upper bound of $\{ 0, 0^{\omega}, 0^{2 \omega}, ... \}$ we obtain the Turing degree $0^{\omega^\omega}$.  Generally for any countable ordinal $\beta$, we can define a degree $0^\beta$.

It is known that for every nonzero Turing degree $a$, there is a Turing degree $b$ with which it is incomparable.  However, for any Turing degree $a$ (and I'm particularly interested in $0'$), is there a Turing degree $b$ that is incomparable with $a^\beta$ for all countable ordinals $\beta$?

The answer to your question is a resounding: IT DEPENDS! This takes us into some set theory, which - while interesting - is a bit off the beaten track perhaps for CS; to address this, I've made the first part of my answer strictly about the computability theory, and then added a separate section on the set theory side of things.

Before we can even address your question, it turns out that there is a surprising subtlety here:

  For $\alpha$ an arbitrary countable ordinal, it is not always clear how to define $0^{(\alpha)}$.

This is treated variously at mathoverflow and math.stackexchange; what I've written below should be self-contained, however.

The issue is that of presentations (or, essentially identically, fundamental sequences). In general, suppose $\lambda$ is a limit ordinal, we've defined $0^{(\alpha)}$ for each $\alpha<\lambda$, and we want to define $0^{(\lambda)}$ as the set $$Z_\lambda=\{(i, \alpha):i\in\omega,\alpha<\lambda,  i\in0^{(\alpha)}\}.$$ However, this set isn't a set of natural numbers. Fixing a map $f:\lambda\rightarrow\omega$, we can "interpret" $Z_\lambda$ along $f$ in a natural way: $$Z_\lambda^f=\{(i, j): i\in\omega, j\in ran(f), i\in 0^{(f^{-1}(j))}\}.$$ Here's the problem: what $f$ do we want to use? Different choices of $f$ will yield different sets, and potentially different Turing degrees. This wasn't an issue in cooking up $0^{(\omega)}$, since there was only one obvious thing to do, but when we try to go further the problem rears its head.

As a quick aside, there's an alternate approach here which seems promising at first: simply define $0^{(\lambda)}$ for $\lambda$ a limit ordinal to be the least upper bound of $\{0^{(\alpha)}:\alpha<\lambda\}$! Combined with the clause $0^{(\beta+1)}=(0^{(\beta)})'$, this would seem to give a recursive definition which works for all countable ordinals. However, it turns out that this entire attack is built on a false assumption: $0^{(\omega)}$ is not the least upper bound of $\{0^{(n)}:n<\omega\}$ in the Turing degrees, and in fact nontrivial least upper bounds never exist (this is the "exact pair theorem" of Spector). So we do necessarily have to do some work.

At this point it's a good idea to go back and try to develop a theory of iterated jumps "from scratch" as it were. This is hyperarithmetic theory due to Kleene, and is presented in detail in the beginning of Sacks' book; I'll just give a rapid (and ahistorical) gloss.

The sets $Z_\lambda^f$ defined above are intuitively what we get if we iterate the jump not along a mere ordinal but along an explicit well-ordering of a set of natural numbers (that is, a copy of the ordinal "labelled" appropriately). To make this precise, suppose $R$ is a well-ordering of some set $D$ of natural numbers (note that $R$ determines $D$). It's easy to show that there is a unique set $J_R$ of ordered pairs of natural numbers with the following properties:

$(x,y)\in J_R$ only if $x\in D$.
If $u$ is the $R$-successor of $v$, then $(u, y)\in J_R$ iff $\Phi_y^{J_R[v]}$ halts, where $J_R[v]=\{z: (v, z)\in J_R\}$.
If $u$ is an $R$-limit, then $J_R[u]=\{(v, y): v<_Ru, y\in J_R[v]\}.$

This is what you get, intuitively, if you iterate the jump along $R$ starting with the emptyset (the fact that we started with the emptyset was built in secretly to the last bulletpoint, since if $u$ is the $R$-least element then $J_R[u]$ is forced to be empty; we can relativize by starting with a non-empty column).

If $R$ is "nice," this is extremely well-behaved:

  Suppose $R_0, R_1$ are well-orderings of sets $D_0, D_1$ of natural numbers such that each $R_i$ is computable, their respective successor operations are computable, and their respective sets of limit elements are computable. Then if $R_0$ and $R_1$ have the same ordertype we have $J_{R_0}\equiv_TJ_{R_1}$.

The conditions above are stronger than merely demanding that the orderings be computable, but in fact every computable well-ordering is (non-computably!) order-isomorphic to such a "nice" computable well-ordering. So based on this, it makes sense to define $0^{(\alpha)}$ for $\alpha$ a "computable ordinal" as the unique Turing degree of a "jump sequence" along a "nice presentation" of $\alpha$. More generally, for any Turing degree $d$ it makes sense to talk about the degree $d^{(\alpha)}$ for any ordinal $\alpha$ with an $d$-computable presentation.

The sets computable from $0^{(\alpha)}$ for some computable $\alpha$ are the hyperarithmetic sets; hyperarithmeticity has a number of equivalent characterizations and is one of the fundamental notions of modern computability theory, and is also very important in descriptive set theory. But this only gets us through countably many ordinals; most countable ordinals don't have computable presentations! The supremum of the computable ordinals is denoted "$\omega_1^{CK}$" - it's much bigger than other popular ordinals like $\epsilon_0$, $\Gamma_0$, etc., but still countable, and indeed quite small among countable ordinals from various perspectives within logic. And it's not very hard to cook up two Turing degrees, neither of which is hyperarithmetic relative to the other, since we've only reached "countably high." Can we do better?

To go further, we need to get into set theory, so I'll put a horizontal line here:

Alright, let's talk about set theory. It turns out that we can continue the jump in a natural way past $\omega_1^{CK}$. However, this gets complicated pretty quickly. The idea comes from Godel's constructible universe, the idea being that each additional step in the $L$-hierarchy is like taking $\omega$-many jumps of what you have so far (since you're looking at everything first-order definable in what you have so far). Teasing this out precisely gets us the notion of mastercodes. I won't define them precisely here, but Hodes has an excellent paper on the topic.

Now, mastercodes have many subtle and annoying features,$^*$ but they let us unproblematically(ish) iterate the jump starting with the emptyset all the way up to $\omega_1^L$, the first ordinal which the constructible universe thinks is uncountable. (More generally, given a degree $d$ we can unproblemantically "do mastercodes" up to $\omega_1^{L[d]}$, the first orderinal that the smallest inner model of ZFC containing $d$ thinks is uncountable.)

If the constructible universe happens to be all there is - that is, if V=L - then we're peachy:

  Every real in $L$ is computable from some $0^{(\alpha)}$ - in the sense of mastercodes - for some $\alpha<\omega_1^L$.

More generally, "reachable via mastercodes" just gives us the notion of relative constructibility: $x\le_Ly$ iff $x\in L[y]$ iff $x$ is in every inner model containing $y$ iff $x$ is computable from some $y^{(\alpha)}$ for $\alpha<\omega_1^{L[y]}$.

However, it's quite possible - that is, consistent relative to ZFC - that $V$ is very far from $L$. For example, $\omega_1^L$ might be countable, and indeed the "real" $\omega_1$ could appear to be quite large from the perspective of $L$! Indeed, it turns out that strong set-theoretic hypotheses can prevent us from getting very far at all with this idea:

  Broadly speaking, if large cardinals exist then there are no easily-definable increasing $\omega_1$-sequences of Turing degrees. (This is parameterized: ramp up the large cardinals and we get more and more necessary undefinability.)

Even assuming $\omega_1^L=\omega_1$ and ruling out anything (like large cardinals) that will bump up consistency strength, the $\le_L$-degrees could still be quite wild, via forcing. In particular, if $c_0, c_1$ are mutually Cohen generic (say) over $L$, then $c_0\not\in L[c_1]$ and $c_1\not\in L[c_0]$; we can get Cohen generics without changing $\omega_1$, so in this case neither is reachable from the other via countably many jumps, assuming we buy the "mastercode picture" (and if we don't, we need to cook up another picture!).

$^*$They really only make sense at the level of degrees, not sets of naturals, so in that sense the "presentation issue" hasn't been avoided; see the middle of page 207 of Hodes' paper. More obnoxiously, Theorem 8 (and see the bottom of page 204 for the relevant definition) shows that ... OK, there's just no nice way to say this, and I can't put it off anymore: mastercode-jumps aren't fully monotone. We can have $\alpha<\beta$ but $a^{(\beta)}=0^{(\alpha)}$ for some degree $a$. Aaargh.


For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

[Where $w^R$ is the reverse of $w$]

My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language.
Any hints?

Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$.
It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.

It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.

Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.


Rectangular Automata have a question regarding rectangular automata and their derivatives.

In each location the derivates are defined by a interval, how are the derivates applied on the variables?
Is one value chosen out of the interval and added to the value or do we reset the value to one value in the interval ?

Regards

The derivatives are applied over time in a continuous fashion.

Here is an example:

Assume that we want to find out whom of two runners wins a running tournament. They run for 100 meters each, and the one reaching a goal first wins.

We can model the position of the two runners using two variables $x$ and $y$. We do not quite know the exact speed of the runners, as it depends on how well they feel at the tournament day. But we know some boundaries on their speed, i.e., how $x$ evolves over time. Let's assume we know that
$\dot x \in [9.8,9.9] \ \frac{m}{s}$ and that $\dot y \in [9.7,9.78] \ \frac{m}{s}$

So a rectangular hybrid automaton would have one "running" state in which the variables evolve like this, and then there are two states for the cases that runner $x$ has reached the goal and that runner $y$ has reached the goal. You can see from the numbers above that player $x$ will win, but let's assume that this is not obvious, and we want to use a rectangular hybrid automaton for this:

   | x:=0, y:=0
   V
+- -------------------+    x >= 100       +---------------------+
| 0.98 <= x' <= 0.99  |------------------>| x' = 0              |
| 0.97 <= y' <= 0.978 |                   | 0.97 <= y' <= 0.978 |
| x < 10, y<10        |                   +---------------------+
+---------------------+
   |                       y >= 100       +---------------------+
   +------------------------------------->| 0.98 <= x' <= 0.99  |
                                          | y' = 0              |
                                          +---------------------+

If we always "reset the value to one value in the interval", then the two runners would never reach the 100 meter mark and hence one of the two goal states on the right is never right.

But it is also not the case that "one value chosen out of the interval and added to the value". Because adding is a discrete actions. You could, for example, add x' to x until one of the two conditions have been reached. But then, it takes exactly 11 steps for both runners to reach the goal, and hence, they both win at the same time. But that makes no sense, because time is continuous. Rather, if you plot the evolution of x over time, you would use x' as the steepness of the line, and the positions of the runners are really continously updated as time progresses, as in real life.

In rectangular hybrid automata, it doesn't really matter whether $\dot x$ can change at every moment of time to a different value in the interval or not. The reason is that we use these automata for checking the properties of model. In the example above, this would be whether the bottom-right location is ever reached (which is not the case). And for this analysis, whether the first derivatives has to stay constant (within their defined interval) or not does not matter.


Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise) Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks:

Consider the following factor $2$ approximation algorithm
for the cardinality vertex cover problem. Find a depth first search tree
in the given graph, $G$, and output the set, say S, of all the nonleaf vertices
of this tree. Show that S is indeed a vertex cover for $G$ and $|S| ≤ 2$ · $OPT$.
Hint: Show that $G$ has a matching of size $|S|/2$.

$EDIT$: the hint originally reads as follows: 'Show that G has a matching of size |S|'. A counterexample to this is when G is a path of length $4$ - then the DFS tree $T = D$, and a maximum matching is of size $2$. I took this to be a misprint and assumed that $|S|/2$ is the number the hint meant to refer to. Now after reading fade2black's comment, he also has a counter example in which $S$ is not a cover of $G$. After thinking about this for a while, I now cannot see for what reason $|S|$ should always be a cover of $G$. What I thought was proof of this statement (my attempt at the first part of the question below), is actually proof that $S$ is always a cover of $T$. Any ideas? Am I missing something? Is this a misprint, or is this just a poorly formulated question?

My attempt:

Showing $S$ is a vertex cover of $G$: Assume not. Then there is at least one vertex $v \in G-S$, $s.t.$ $v$ is a leaf and not adjacent to any vertex in $S$. Then either $v$ is disconnected in $G$, or $v$ is adjacent to some other leaf in $G$. If $v$ is adjacent to some other leaf in $G$, this implies that $G = K_2$, in which case $S = \emptyset$ and selecting either of the two vertices on its own gives a vertex cover. Therefore, if $G \neq K_2$ and $G$ is connected, $v$ must be connected to some $w \in S$.

Showing that $|S| \leq 2 \cdot OPT$: Consider a $2$-colouring of the vertices in $S$. At least one of the colours will have been used to colour at least half of the vertices in $S$. Pick that  colour, and for each vertex coloured by it, match exactly one of its incident edges. It follows that $G$ admits a matching of size $|S|/2$.
Let $M$ be a maximal matching in $G$. Then $|S|/2 \leq |M|$. We know that the minimum cardinality vertex cover of $G$ can be bounded from below by $|M|$, i.e. $|M| \leq OPT$. Together this gives $|S|/2 \leq |M| \leq OPT$, which implies that $|S|/2 \leq OPT \implies |S| \leq 2 \cdot OPT$.

Im pretty happy with the logic behind my solution to the second part of the exercise (showing that $|S| \leq 2 \cdot OPT$), but I'm not sure if the first part is quite there - I think the logic needs a bit of work. Any suggestions?

In this exercise, we think of the DFS tree (in fact, DFS forest) as a rooted tree (in fact, forest). We define leaf and nonleaf accordingly. In particular, the root of the tree is not a leaf vertex unless it is an isolated vertex.

In order to prove that the set of nonleaf vertices is a vertex cover, you have to notice that no edge can connect two leaves $x,y$ of the tree, since if $x$ is the vertex reached first, then $y$ will be a descendant of $x$.


Machine Learning algorithms based on "structural risk minimization"? Which machine learning algorithms (besides SVM's) use the principle of structural risk minimization?

The structural risk minimization principle is a principle that is at least partly 'used' in all machine learning methods, since overfitting is often to be taken into account: reducing the complexity of the model is (supposedly and in practice) a good way to limit overfitting.

SVMs explicitly have a parameter for the complexity (the dimension of the feature space, or even the kernel function) and it's necessary because increasing the complexity is a part of the learning algorithm.
Neuronal networks also have a easy indicator of their complexity (number of 'cells') and is part of the associated learning algorithm.
Without this principle grammar inference would be both stupid and perfect grammar is the list of all possible words, so every non-trivial algorithm at least acknowledges this principle.
Decision trees have their own notion of entropy.
Clusters can be simply counted or kind of 'use' the principle intrinsically or have a fixed number of clusters and in that case you apply the principle at a higher level.

To be perfectly honest I don't really know about what happens in genetic programming but they don't have an intrinsic notion of complexity.

I don't know well Inductive logic programming but it doesn't seem to scale very well to this principle.


Combining Runtime Complexity Expressions with respect to Dijkstra If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity statement:

$$
O(\text{my algorithm}) = O(|V|\mathop{log}|V| + |E|\mathop{log}|V|) + O(|V|^2)
$$

Assuming Dijkstra's is implemented with the binary heap.

My problem is that I realized that, worst case, $|E| = |V|^2$, and the statement rewrites as:

$$
O(|V|^2 \mathop{log}|V|) + O(|V|^2) = O(|V|^2\mathop{log}|V|)
$$

But, the rest of the time, the algorithm is $O(|V|^2)$, especially if $|E| < |V|$.

What is the correct runtime in this situation? And what is the reasoning behind the correct runtime statement?  Because it seems like, to me, just listing out Dijkstra's runtime would be incorrect, since it is only true when the graph is dense... (can I add them together, like: $O(|V|^2 + |E|\mathop{log}|V|)$?)

Yes, you can just add them together.  If $|E|=O(|V|^2/\log|V|)$, then $O(|V|^2+|E|\log|V|)$ is the same thing as $O(|V|^2|)$, since the first term dominates.  If $|E|=\Omega(|V|^2/\log|V|)$, then it's the same thing as $O(|E|\log|V|)$, since the second term dominates.

It might help your thinking to bear in mind that $f + g = O(\max\{f,g\})$.


Minimum moves to "stabilize" an array We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the element by adding +1 to some element or by adding -1 to some element, we don't have a limit on how much we can use those operations, but we want to make the array stable in minimum moves.

I started solving the task by writing a dynamic programming relation, described by the state $f(i, j)$ meaning the minimum moves to stabilize the first $i$ elements of the array, such that the last element is equal to $j$.

However it seems that this method is slow for big values of $N$. How would you approach solving this problem?

Let $M=\max_i|A_i|$.

Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.

Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$ elements of the array, such that the last element is in the range $\left[j,j+2^k\right)$. Then we have $f(0,j,0)=0$,
$$f(i,j,0)=|A_i-j|+ \min\left\{f\left(i-1,j-H,\hat{k}\right),f\left(i-1,j+H+1-2^{\hat{k}},\hat{k}\right)\right\}$$
where $2^{\hat{k}}>H$, and
$$f(i,j,k)= \min\left\{f(i,j,k-1),f\left(i,j+2^{k-1},k-1\right)\right\}$$
for $k>0$. Note each entry can be calculated in $O(1)$ time if we calculate them in some proper order.

Note in an optimal solution, the final $A_N$ must be in the range $[-(M+NH),M+NH]$ (otherwise the final elements are all either greater than $M$ or less than $-M$, which is not optimal), so we need to calculate $f(i,j,k)$ for all $i,j,k$ such that $0\le i\le N$, $j\ge -(M+(2N-i)H)$, $k\ge0$ and $j+2^k\le M+(2N-i)H+1$. The time complexity is $O\left(N(M+NH)\log (M+NH)\right)$, while the naive $f(i,j)$ solution takes $O(N(M+NH)H)$ time.

You can further use the range minimum query technique to reduce the time complexity to $O(N(M+NH))$.


Partitioning vertices in a bipartite graph according to minimum vertex covers How to solve this problem?

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.
Consider a set of all minimum vertex covers of a given bipartite graph. Your task is to divide all vertices of the graph into three sets. A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex. A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph. If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

The following idea comes from a Chinese blog.

Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.

We have the following observations:

All vertices not in $M$ must belong to $\mathrm{Never}$.

Proof. Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$.

Proof. Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$.

These observations lead us to the following algorithm:

A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
    i = i + 1
    A[i] = empty set
    for each vertex v in N[i - 1]:
        temp = N(v) \ A
        A[i] = union(A[i], temp)
        A = union(A, temp)

    if A[i] is empty:
        break

    for each vertex v in A[i]:
        add M(v) into N[i]
        add M(v) into N

After the execution of this algorithm, all vertices in A belong to $\mathrm{Always}$ and all vertices in N belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in A forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.


Given a language L what can we say about the decidability of whether this language is regular or not? Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?

As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines.

So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.

Unfortunately, even for context-free grammars it is undecidable whether their language is regular.

Bar-Hillel, Perles, Shamir.  On formal properties of
simple phrase structure grammars. (1961)
doi 10.1524/stuf.1961.14.14.143


Turing machine with a finite tape after the input word ends How can I prove that for a natural number K, a language that accepted by a Turing machine with K cells after the input word ends, belongs to R (which R is the set of languages that there is Turing machine that accept them while for each input the run is finite)?

Given the length of the input $n$, you can come up with a bound $N(n)$ on the number of configurations that the Turing machine can have. If the machine hasn't stopped on an input within $N(n)$ time steps, then it will never stop (why?), and you can use this to complete the proof. Details left to you.


Are the regular languages closed against injecting single letters? Let $L$ an arbitrary regular language and

$\qquad L_2 = \{uav : uv \in L\}$.

Am I correct to say that this language is not regular by saying:

$L$ has an even number of $a$'s. So $u$ and $v$ have an even number of $a$'s. However, $uav$ will have an odd number of $a$'s so $L_2$ is not regular?

This language is regular. Let $M$ be a DFA accepting $L$ and assume it has a single initial and final state. We can construct a NFA accepting $L_2$. We create two copies of $M$: $M_1$ and $M_2$. Let us denote the states of $M_1$ as $q_1, \dots, q_n$ and the states of $M_2$ as $p_1, \dots, p_n$. Note that these two DFA are isomorphic where $q_i$ corresponds to $p_i$. The initial state of the new automaton will be $q_1$, and its accepting state will be the accepting state of $M_2$ (so the accept state of $M_1$ is no longer an accept state, and the initial state of $M_2$ is no longer an initial state; in the new NFA, these are just normal states).  Add new transitions $\delta(q_i, a) = p_i$ for each pair $(q_i,p_i)$. The resulting NFA accepts $L_2$.  You can think over it to prove it accepts $L_2$; effectively, $M_1$ is reading the $u$ part of the input and $M_2$ is reading the $v$ part.


Proof that MAX CLIQUE is NP-Hard My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD?

Remarks:

MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k>0$. Does the graph $G$ contain a maximum clique of size $k$?

I have been looking for a formal proof that MAX CLIQUE is NP-Hard, still I haven't found one. The book of Computers and Intractability (Michael Garey) in the final chapters mentions briefly that the full proof is on the phd thesis of Ernet Legget: http://dl.acm.org/citation.cfm?id=907661 . I couldn't find the copy of the book on the internet nor any survey whit the proof.

There is probably a proof in Karp's original paper. Here is a simple reduction from SAT. Given an instance $\varphi$ of SAT with $m$ clauses, construct an instance of MAX-CLIQUE as follows. For each clause $C$ and each literal $\ell$ appearing in $C$, there is a vertex $(C,\ell)$. Two vertices $(C_1,\ell_1),(C_2,\ell_2)$ are connected if $C_1 \neq C_2$ and $\ell_1 \neq \lnot \ell_2$. This has a clique of size $m$ iff $\varphi$ is satisfiable (exercise).


Why do presenttations of proof systems in logic and automated reasoning not include the algorithm that finds proofs? Is is that a common way to present a proof system in the field of Logic and Automated Reasoning is to present a system of inference rules, without having to formally describe a particular algorithm or procedure to find proofs in this system?

I notice that phenomenon in both textbook as well as conference or journal papers of this field.

This can be seen in classic topics like: the Natural Deduction calculus, Hilbert calculus where only inference rules is presented.

In modern researches, I am studying about Separation Logic, thus, I would like to take some papers from this field to illustrate this observation:

Automated Cyclic Entailment Proofs in Separation Logic

Symbolic Execution with Separation Logic

To simplify a bit, a system of inference rules generally defines a set of sequents, which are simply pairs of a list (or set) of propositions $\Gamma$ and a proposition $\phi$ written

$$ \Gamma \vdash \varphi$$

called the derivable sequents. The rules describe which sequents are derivable, and for any reasonable system, given $\Gamma\vdash\varphi$, and sequents $\Gamma_1\vdash\varphi_1,\ldots,\Gamma_n\vdash\varphi_n$, it is easy to tell whether

$$\frac{\Gamma_1\vdash\varphi_1\ldots \Gamma_n\vdash\varphi_n}{\Gamma\vdash\varphi} $$

is a valid derivation. This usually be done with some obvious algorithm.

Some much more difficult algorithmic questions are this:

Given $\Gamma\vdash\varphi$, is this sequent derivable?
Given $\Gamma$, how can we enumerate the set of $\varphi$ such that $\Gamma\vdash \varphi$ is derivable?

In general, there is no algorithm for answering question 1, and question 2 is quite difficult. In particular, when trying to prove $\Gamma\vdash\varphi$ a natural approach is to try to apply all possible rules until exhaustion. Several issues come up:

What order do we apply rules in?
How do we guess the $\Gamma_i\vdash \varphi_i$? If any variables appear on top that do not appear in the conclusion, you need to guess some instance for that variable.
When do we know if a derivation does not exist?

Because of the complexity of these issues, it's much more natural to separate the system of rules that describe the derivable sequents from the algorithms trying to find actual derivations of a given sequent.


Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$ Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma.

I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is a $p$ such that every $w \in L$ such that $|w| \ge p$ can be represented as $xyz$ with $|y| \ne 0$ and $|xy| \le p$, so that $xy^iz \in L$ for all $i \geq 0$. But I have not been able to choose $w \in L$ that serves me to finish with the lemma, taking into account the restrictions that $L$ has.

Suppose towards a contradiction that $L$ is regular, and let $n \ge 1$ be its pumping length.
Consider the word $a^{2n}b^nc \in L$. By the pumping lemma there is some value of $k \in \{1, \dots, n\}$ such that, for every $i \ge 0$, the word $a^{2n+(i-1)k} b^nc$ also belongs to $L$.
Picking $i=0$ yields the sought contradiction since $a^{2n-k} b^n c \not\in L$. We can then conclude that $L$ is not regular.


Determine if a language is Decidable or semi decidable Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.
We need to determine, without using Rice's Theorem, whether:

$L\in \text{R}$, i.e., $L$ is decidable.
$L \in \text{RE}\setminus \text{R}$, i.e., $L$ is semi-decidable but not decidable
$L \notin \text{RE}$, i.e., $L$ is not semi-decidable.

Any hints or some steps on how to approach this problem would be appreciated.
Also, if $L\notin \text{R}$, can we prove that using Rice's Theorem?

The language $L$ is not in $\text{RE}$. Consider the complement of the halting problem $\overline{Halt_{TM}} = \{ \langle M, w\rangle: \text{ $M$ does not halt on $w$}\}$ which is not in $\text{RE}$. We show that $\overline{Halt_{TM}}$ reduces to $L$ (and therefore, $L \notin \text{RE}$). From this point, I am assuming w.l.o.g that every machine has an input alphabet that contains at least three letters $a, b, $ and $c$.
A mapping reduction from $\overline{Halt_{TM}}$ to $L$ operates as follows. On input $\langle M, w\rangle$ of the reduction, the reduction outputs $\langle K\rangle$, where $K$ is a machine that operates as follows. On input $x$ of $K$, if $x = a$ or $x = b$, $K$ accepts. Otherwise, if $x\notin \{ a, b\}$, then $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$, then $K$ accepts $x$. The reduction is correct. Indeed, if $M$ does not halt on $w$, then $K$ accepts the inputs $x = a$, and $x = b$, and does not halt on any other input. In particular, $K$ accepts at most two single-letter words. Conversely, if $M$ Halts on $w$, then $K$ accepts all inputs $x$, in particular, $K$ accepts at least three single letter words $a, b,$ and $c$.
Since $\text{R}\subseteq \text{RE}$, the above also proves that $L$ is not decidable. Yet, if you want to prove that $L$ is not decidable using Rice's theorem, then you note that the property $\text{P} = \{ M: \text{ $M$ accepts at most two single-letter words} \}$ is a non-trivial semantic property:

$\text{P}$ is nontrivial: it is easy to show that there are machines that accept at most two single-letter words, and there are machines that accept at least three single-letter words. I leave the details to you.

$\text{P}$ is semantic: let $M_1$ and $M_2$ be two machines with $L(M_1) = L(M_2)$. We need to show that both $M_1$ and $M_2$ are in $\text{P}$, or both are not in $\text{P}$. This is also easy as $M_1$ and $M_1$ recognise the same language, in particular, they accept the same single-letter words.


What kind of LTL formula can be represented by DBAs I am looking for the portion of LTL formula that can be expressed by deterministic buchi automata. Is there any classification of this such?

You can define syntactic fragments of LTL that ensure that all properties expressible in these fragments are representable as DBAs. An example is given in the paper "A LTL Fragment for GR(1)-Synthesis". Also, the common fragment of ACTL and LTL only contains properties that are representable as DBAs.

But note that such a fragment will never be complete in the "if a formula is not in the fragment, then it is not representable as a DBA" sense. The reason is that if we have LTL formulas that are not representable as DBAs, then we may be able to combine them to a formula that is representable as DBA. For example, the properties "FG p | GF q" and "FG q | GF p" are both not expressible by DBA, but both their conjunction and their disjunction are.

Note that there are also DBAs that are not representable in LTL. So a fragment of LTL cannot be equiexpressive to DBAs.


Algorithm for optimal spacing in intervals Is there an algorithm to optimally space points within multiple intervals? Optimal in this case means maximizing the smallest distance between any two points so that each pair of points has at least distance X. For example, in the intervals (1,3) and (5,7) you can space out three points with a distance of at least 2 (at 1,5, and 7). But you can't space out three points with a distance of at least 3. Is there an easy way to do this with a program?

Sure.  A simple approach is to use binary search on the separation distance $d$: given $d$, it is easy test whether there is a way to space out $k$ points so that all are at least $d$ apart (I'll let you figure out how; if you can do it for one interval, you should be be able to do it for multiple intervals).  Then use binary search on $d$.


Is this language regular or non-regular: {ww : w ∈ {a,b}* } This is a question from a text book that's giving me some trouble.  The question is:

  Determine whether or not this language is regular. Justify your answer.
  $$L = \{ww : w \in \{a,b\}^* \}$$

I think this language is not regular because $w$ can be of arbitrary length and adheres to no pattern.  So, therefore, it cannot be determined whether $ww$ is part of the language using a finite number of states.  Am I correct in this assumption, and does my explanation make sense?  Thanks for any help you can give me!

My answer, after reading the comments below:

Let $w = ww = (a^p)(b^p)(a^p)(b^p)$.  Then consider the Pumping Lemma.  Since $|xy| \leq p $ and $|y| \geq 1$, then the $y$ part of the string must be a's.  But if we pump up, we'll have more a's in the first part than the second, and $w \neq w \in             ww$.  Hence, the language can't be regular.

Your explanation is correct. To make it more rigorous, assume that L can be recognized by a finite automaton $D$ with $N$ states.

Consider feeding a string $w$ longer than $N$ characters to $D$. Since $D$ has only $N$ states, that means it will go through some state twice. Suppose $w$ can be represented as $w = pqr$, where the state of the DFA is the same before and after $q$.

Then the strings $ww = pqrpqr$ and $pqqq...rpqr$ must be both accepted by $D$, but probably only the first one is in $L$ (some more rigor may be needed to prove that there exists such a string $w$ such that the second string really cannot be in $L$, for some number of repetitions of $q$).

P.S. looks like I unknowingly used the Pumping Lemma.


Computational complexity classes not based on input size? Computational complexity classes, such as $P, NP, PSPACE$, etc, are defined according to the factory by which computational time increases, as the input size $n$ increases.

But this doesn’t allow us to talk about the complexity of a particular problem (i.e. for a particular $n$).

For example, I believe that “generalized chess”, i.e. on an $n\times n$ board, is $NP$-hard. But this only tells us something about how the computational time of generalized chess increases as $n$ goes to infinity. It doesn’t tell us anything about how hard $8\times 8$ chess is.

On the other hand, simply giving a number, denoting the amount of steps required to solve $8\times 8$ chess with a Turing machine, is not very insightful.

Is there a different classification-scheme/framework for analysing the computational complexity of problems, that doesn’t refer to the input size $n$, that allows us to analyse e.g. the complexity of $8\times 8$ chess?

No, not really: there's no framework for this that turns out to be very useful.  There is a reason that in theoretical work we often use asymptotic complexity.

In principle, you could talk about the concrete complexity of the problem of chess on a 8x8 board.  One way to measure that would be to use the worst-case running time of the fastest program to solve chess on a 8x8 board: not the asymptotic running time, but the actual wall-clock time, measured in seconds.  However, this has multiple problems.  One problem is that it is obviously super-specific to a particular computer: if I buy a different computer, the wall-clock time might be very different, even though I haven't changed the algorithm.  So now the running time is no longer a property of the algorithm; it also depends intimately on which computer I run it on.

Or, perhaps we could count the number of instructions executed.  But now that will depend on the particular computer architecture; when we compile to x86, the number of instructions might be different than when we compile to ARM.  So the complexity still depends  on the computer.

Finally, there is the problem that it is very hard to reason about this number through theoretical analysis.  Given some pseudocode, can you analyze how many instructions or how many seconds it will take to run that pseudocode?  That's very hard, since the pseudocode first has to be implemented in some language, then compiled to machine language, then run.  (And good luck reasoning about the effect of caches and the memory architecture on the time it takes to, e.g., perform a single read or write to memory; that's very hard to predict.)  At best, it gets super messy; at worst, it's just not predictable in a reasonable way.

If you read Knuth, you'll find that he tries to do this kind of analysis.  He defines an artificial computer architecture called MIX, which is fully specified.  He then implements his algorithms carefully in MIX machine language, and finally mathematically analyzes the number of MIX instructions the algorithm might take.  If you go through some of his demonstrations you'll see just how painful and messy it is.  He ends up doing this only for some pretty simple algorithms, and the calculations are still ugly; doing that for something as complex as a chess algorithm sounds horrendously painful.

Finally, there's the problem that we don't know what is the optimal program for playing 8x8 chess. That's a famous open problem.

So, yes, in principle, it is possible to reason about running time without relying on asymptotics.  In practice, it usually gets so messy that you drown in details and have a hard time extracting useful insights.


What does the notation $ [ i \neq k ] $ mean? I can't figure out what the notation $[x \neq k ]$ means. Here's a bit of context:
The formula is:
$Pr[A_i^k = 1] = \frac{[i\neq k]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 \text {  if } i = k \\ \frac{1}{i-k+1} \text{ if } i \gt k
 \end{cases}$
and is part of a chapter where the average expected time of operations of a randomised treap are proved.
$A_i^k$ is an indicator variable defined as $[ x_i \text{ is a proper ancestor of }x_k ]$ where $x_n$ is the node with the $n$-th smallest search key.
That probability comes up because $\text{depth}(x_k) = \sum_{i=1}^{n} A_i^k$ and $\mathbf{E}[\text{depth}(x_k)] = \sum_{i=1}^nPr[A_i^k = 1]$.
I have no access to the pages that explain the notation since I'm studying from a pdf of a few pages taken from a book.

It  is used like a boolean where $[i \neq k] = 1$ if $i \neq k$ and $0$ otherwise. Notice that $[i \neq k]$ is equivalent to $i < k$ or $i > k$ for numbers, which is the right part of the equation you wrote.
It is called Iverson bracket and in general $[statement] = 1$ if $statement$ is true and $0$ otherwise.


What kind of operations can we do with bits? I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting ">>"? Could we count this?
Thanks for replying.

If you think about it, there are $2^4 = 16$ possible ways of combining two bits to give a single-bit ouput (AND, OR, NOR, NAND, XOR, ...).  Can you work out what they all are? This is because there are four possible input combinations ($00$, $01$, $10$, $11$) and any subset of those can be mapped to~$1$.  But we could combine more than two bits to give a single bit output – can you work out how many operators there are that take $k$ bits as input and output one bit?

And we're not even restricted to one bit of output: in general, we can have any number of bits of input and any number of bits of output. You mentioned shifts, which map $k$ bits to $k$ bits, as an example of this.

Overall, there are infinitely many ways of combining bits.


Why is it hard to show that the euclidean Steiner tree problem is in NP? I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. [Wikipedia]
Shouldn't the euclidean version obviously be in NP since the metric Steiner tree problem is in NP and a non-deterministic TM that decides the metric Steiner tree problem could also decide the Euclidean Steiner tree problem? Or am I missing something that could make the Euclidean version inherently more difficult/different?

I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP.
The problem is the following: for integers $a_1, \ldots a_n$ and $b_1, \ldots b_m$, is $\sum\sqrt{a_i} < \sum\sqrt{b_j}$?
This is not known to be in NP and is a major barrier in adapting a lot of computational geometry algorithms from the Real-RAM model to Word-RAM.


Example for the analysis of a recursive function l is a matrix of size [1...n, 1...n]

function: rec(i,j)
  if (i*j == 0)
    return 1
  else
    if (l[i,j] == 0)
      l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
    return l[i,j]
end_function

for i=1 to n
  for j=1 to n
    l[i,j] = 0

rec(n,n)

The nested for's are O(n2). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:

if (l[i,j,k] == 0)
  l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)

Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):

T(n) = T(n-1, n2) + T(n, n-12) + T(n-12, n-12)

And i'm stuck here. Besides i don't know if i did right till this point.

Here's the correct recurrence for the running time of rec:
$$
f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\
f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases}
$$
The running time of the entire program is $f(n,n) + O(n^2)$. Now it remains to solve the recurrence for $f$, which I leave to you.


Sort already sorted array - after changing several elements Problem:

Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S_1$ — an array of indexes of changed elements. Design an algorithm that will sort the array in $O(n)$ time.

Additionally, we know that $\text{length of }S_1\le\log_2(\text{length of }S)$.

Example:

$S$ — [3, 5, 7, (20), 15 ,(0) ,16]

$S_1$ — [3, 5]

() - Changed elements

Question:

I have some troubles designing the algorithm. My first idea was to just use Count or Radix sort algorithm, but as the values which are changed can be random I've ruled out count sort as potential candidate.

The second idea is to:

Load the values based on indexes of $S_1$ into new array $S_x$.
Rewrite $S$ without the elements of indexes provided in $S_1$.
Sort $S_x$.
Use "Merge" procedure from Merge Sort on $S_x$ and $S$.

However that still will leave me with $O(n\log n)$ as I'll need to sort $S_x$ array. I'll appreciate any advice on the approach.

Note the length of $S_1$ is no more than $\log_2n$, so the time you need to sort $S_x$ is $O(\log n\log\log n)$, which is $O(n)$.


Devise a backtracking algorithm to allocate $p$ projects to $s$ students There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all students must have a project. I need to compute and display all possible ways of allocating projects to students under these constraints. Here's an example:

Input:

3 students, 2 projects

Output:

   P1      P2
   {1}     {2, 3}
   {2}     {1, 3}
   {3}     {1, 2}
   {1, 2}  {3}
   {1, 3}  {2}
   {2, 3}  {1}

In my attempts, I've thought about this as being related to the problem of partitioning the set of students into non empty subsets and then ignoring those partitions which have unacceptable length. i.e. for my example generate:

{{1}, {2}, {3}}
{{1}, {2, 3}}
{{2}, {1, 3}}
{{3}, {1, 2}}
{{1, 2, 3}}

and ignore the first and last as well as double count the three in the middle as they can be arranged in a two ways (order matters for this problem). I'm not sure however how I would go about generating and filtering these subsets and even whether this is a decent solution for any p or s values.

I didn't get what you're exatly asking for? Backtracking is the solution. Are you looking for an actual implementation or an explanation of backtracking? Or a  better  performing approach in terms of runtime.

Here my pseudo code how I would generate all matching solutions.

state = [];  //array representing the current state, assigns students to projects

S = [..];    //array containing the students
P = [..];    //array with students
func assign(level) {
  if(level == S.length) {
    if is_valid_state() //ensure each project has at least one student
      output(state);
  }
  for(i = 0; i < P.length; i++) {
    state[level] = i;
    assign(level+1);
  }
}

level(0)

Can of course  be optimized by moving the final condition atop, but this would be my first thought of how to solving this the least efficient way (in terms of performance).


Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique? why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire problem .So what is the difference in terminology of sub-problems in divide and conquer and dynamic programming except for the fact that in the latter case we have overlapping sub-problems since both tend to imply that we have some sub-problems which combine to give an optimal solution to entire problem so in case of divide and conquer can we say that each sub-problem also gives us optimal solution ?

The CLRS definition of optimal substructure:

  A problem exhibits optimal substructure if any optimal solution to the
  problem contains within it optimal solutions to subproblems.

This make sense for both methods.

Divide&Conquer is used when subproblems are independent, there is no overlapping subproblems. In this case you just combine solutions to resolve the main problem.

Dynamic Programming is used when subproblems are dependent, there are overlapping subproblems and results are typically stored in some data structure for later reuse.


Bayesian Network - Inference I have the following Bayesian Network and need help with answering the following query.

EDITED:

Here are my solutions to questions a and b:

a)

P(A,B,C,D,E) = P(A) * P(B) * P(C | A, B) * P(D | E) * P(E | C)

b)

P(a, ¬b, c ¬d, e) = P(a) * P(¬b) * P(c | a, b) * P(¬d | ¬b) * P(e | c)

= 0.02 * 0.99 * 0.5 * 0.99 * 0.88 = 0.0086

c)

P(e | a, c, ¬b)

This is my attempt:

a ×  ∑ P(a, ¬b, c, D = d, e) =
     d

 a × ∑  { P(a) * P(¬b) * P(c | a, b) * P(d) * P(e | c) + P(a) * P(¬b) * P(c | a,b)    *P(¬d)
     d                                                                  + P(e | c) }

Note that a is the alpha constant and that a = 1/ P(a,¬b, c)

The problem I have is that I don't know how to compute the constant a that the sum is multiplied by. I would appreciate help because I'm preparing for an exam and have no solutions available to this old exam question.

You're on the right path.  Here's my suggestion.  First, apply the definition of conditional probability:

$$ \Pr[e|a,c,\neg b] = {\Pr[e,a,c,\neg b] \over \Pr[a,c,\neg b]}. $$

So, your job is to compute both $\Pr[e,a,c,\neg b]$ and $\Pr[a,c,\neg b]$.  I suggest that you do each of them separately.

To compute $\Pr[a,\neg b,c,e]$, it is helpful to notice that

$$ \Pr[a,\neg b,c,e] = \Pr[a,\neg b,c,d,e] + \Pr[a,\neg b,c,\neg d,e]. $$

So, if you can compute terms on the right-hand side, then just add them up and you've got  $\Pr[a,\neg b,c,e]$.  You've already computed $\Pr[a,\neg b,c,\neg d,e]$ in part (b).  So, just use the same method to compute $\Pr[a,\neg b,c,d,e]$, and you're golden.

Another way to express the last relation above is to write

$$ \Pr[a,\neg b,c,e] = \sum_d \Pr[a,\neg b,c,D=d,e]. $$

If you think about it, that's exactly the same equation as what I wrote, just using $\sum$ instead of $+$.  You can think about whichever one is easier for you to think about.

Anyway, now you've got $\Pr[e,a,c,\neg b]$.  All that remains is to compute $\Pr[a,c,\neg b]$.  You can do that using exactly the same methods.  I'll let you fill in the details: it is a good exercise.  Finally, plug into the first equation at the top of my answer, and you're done.


Clarification of the proof involving the regularity condition in Master Theorem I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem.

(The Statement of Master theorem) Let $a \geqslant 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be deﬁned on the nonnegative integers by the recurrence( the recursion divides a problem of size $n$ into $a$ problems of size $n/b$ each and takes $f(n)$ for the divide and combine)
$T(n) = aT(n/b)+ f (n)$ ;
where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:

If $f(n)=O (n^{\log_ba - \epsilon})$ for some constant $\epsilon > 0$, then $T(n)=\Theta (n^{\log_ba})$.

If $f(n)=\Theta (n^{\log_ba})$, then $T(n)=\Theta (n^{\log_ba}\lg n)$

If $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

For $n$ as exact powers of $b$ we restrict the domain of T(n) as follows:

$$T(n)= \Theta(1), n=1$$
$$T(n)=aT(n/b)+f(n) ,n=b^i$$

Now in the proof of Master's Theorem with $n$ as exact power of $b$ the expression for $T(n)$ reduces to :
$$T(n)=\Theta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Then the authors assume the following,
$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$
Then for the proof of the 3rd case of the Master's Theorem the authors prove the following lemma,

Lemma 1 : If $a\cdot f(n/b)\leqslant c\cdot f(n)$ for some constant $c<1$ and for all $n\geqslant b$ then $g(n)=\Theta(f(n))$

They say that:
under their assumption that $c<1$ and $n \geqslant b$,they have $a \cdot f(n/b)\leqslant c \cdot f(n) \implies f(n/b)\leqslant (c/a) \cdot f(n)$
then iterating $j$ times yields, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$
I could not quite get the mathematics used behind iterating $j$ times.
Moreover I could not quite get the logic behind the assumption of $n\geqslant b$ for the situation that $n$ should be sufficiently large. (As the third case of the Master's Theorem says.)
The proof of the lemma continues as follows:

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n)$$
So, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$
$$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$
$$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ as $c<1$ we have an infinite geometric series
$$= f(n) \left(\frac{1}{1-c}\right)$$
$$=O(f(n))$$ as $c$ is a constant. (Note that $T(n)=\Omega(f(n))$ from the recursion diagram.)

Then the authors proof the third case of the Masters Theorem for $n$ as exact power of $b$:

Lemma 2: Let $a \geqslant 1$ and $b>1$,  if $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

So $$T(n) = \Theta(n^{\log_ba}) + g(n) = \Theta(n^{\log_ba}) + \Theta(f(n)) =\Theta(f(n))$$ as $f(n)=\Omega (n^{\log_ba + \epsilon})$

Moreover in the similar proof for the third case of the general master theorem (not assuming $n$ as exact powers of $b$) there again the book assumes that $n\geqslant b+b/(b-1)$ to go with the situation of sufficiently large $n$.
I do not quite understand what the specific value has to do and why such is assumed as sufficiently large $n$
(I did not give the details of the second situation as I feel that it shall be something similar to the first situation but however it can be found here)

Let's start with the issue of iteration. Suppose that a function $f$ satisfies
$$ f(n/b) \leq (c/a)f(n). $$
Then it also satisfies
$$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$
You can prove by induction that for all integer $t \geq 0$,
$$ f(n/b^t) \leq (c/a)^t f(n). $$
As for your second question, about assuming that $n$ is large enough: the proof is just sloppy. You cannot assume that $f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n$ is a power of $b$.
They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for $n \ge b + b/(b-1)$. Using the idea of the proof of the special case where $n$ is a power of $b$, you can complete the proof of the general case. I would, however, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and you can trust the authors that it works out. Nothing interesting is hidden under the rug.


Proving a binary heap has $\lceil n/2 \rceil$ leaves I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:

Each new node is inserted via percolate up. This means that each new node must be created at the next available child. What I mean by this is that children are filled level-down, and left to right. For example, the following heap:

    0
   / \
  1   2

would have to have been built in this order: 0, 1, 2. (The numbers are just indexes, they give no indication of the actual data held in that node.)

This has two important implications:

There can exist no node on level $k+1$ without level $k$ being completely filled
Because children are built left to right, there can be no "empty spaces" between the nodes on level $k+1$, or situations like the following:

    0
   / \
  1   2
 / \   \
3  4    6

(This would be an illegal heap by my definition.) Thus, a good way to think of this heap is an array implementation of a heap, where there can't be any "jumps" in indeces of the array.

So, I was thinking induction would probably be a good way to do this... Perhaps something having to deal with even an odd cases for n. For example, some induction using the fact that even heaps built in this fashion must have an internal node with one child for an even n, and no such nodes for an odd n. Ideas?

Here's a simpler logical proof.

Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.

Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.


What is meant by a single-threaded kernel? I was looking at this course but I cannot seem to understand what is meant by the term "single-threaded kernel".
Does it mean that:

only a single kernel thread is made available by the OS?
only a single kernel thread can be executed at one time?

or is there some other interpretation?

I will be adding to nir shahar's answer.
A single-threaded kernel is essentially a kernel that processes only one thread at a time. We can have multiple kernel threads, but only one can get executed at any given point in time. This can be achieved by some scheduling procedure on the kernel threads.
But is this the same thing as having only one kernel thread (and using the many-to-one model) as even multiple threads have to be executed sequentially?
NO! A blocking call made on a many-to-one model blocks all other processes mapped to that kernel thread. Having a one-to-one model will allow for other processes to run even if one process executes a blocking call.
This does come at a cost. The overheads of creating and managing multiple kernel threads are somewhat expensive, but it all depends on your usage.


Determining initial and final states from FA diagram I am new to automata. And learning to find concatenation of two FAs. But this one has confused me

I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final state or does it mean both initial and final state because it is on the start?? Just clear me on this that what is initial state and what is final state in FA 1? Then I'll take it from here and will be able to do concatenation.

P.S I know that +- in a state mean both initial and final state but I don't know about double circle form. Kindly help me on this.

In your diagrams, a triangle points at the initial state, and double circles indicate final states. Inside the circles you can find the state names, such as x1.


What all can be said when you say that the CPU is 32 bit? When someone tells a computer scientist that a CPU is, say, 32 bits, what all does he/she infer from this information?

I know that it means that the physical address has 32 bits. This meas that the physical memory can't hold more that 2^32 bytes of RAM. This also means that the word size is 32 bit or 4 bytes. Please correct me if I am wrong and also tell me what more we can infer from this.

I have searched over the internet only to get websites answering the above question to layman. Can anyone answer it from the technical point of view?

An $n$-bit processor is a processor for which the preferred integer size is $n$ bits.  That's usually the size of the integer or general purpose registers (a processor may not have exposed registers in its ISA, a processor may have some other kind of registers of different width, a processor may provide instructions to do some integer operations on different -- smaller or wider -- width, the width of buses used in the ISA implementation do not define its architectural width: there may be several implementations using buses of several sizes).

Data of that size is usually called a word, but when an ISA exist as a family and is extended to provide wider registers, the term word tend to continue to refer to data of the width adequate for the first member of the family (thus the continued use of word to refer to 16-bit quantities in the x86 world which has grow now to a 64-bit ISA).

The address space size is determined by the ISA width only if the ISA is using the same registers for address computation as for integer one.  That's a very common property of later architectures, but it has not always be the case (the 8086 used 24-bit addresses but its word size was 16 bits, Cray had 64-bit data register but its address registers were 24 bits IIRC).  Even when the registers used are the same, the amount of addressable memory may be different, either because some bits are not used for addresses (the 68000 for instance, and programmers making use of that caused issues for their followers when all of the bits were token into consideration), or because virtual memory allows for a process $n$-bit addressable space to be mapped into a wider physical address space (you could consider the 24-bit address of the 8086 a special case of that).


Number of compatible trees with an ancestry matrix Suppose you are given an ancestry matrix $M$ which means that $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. If $M$ represents no cycles (treated as an adjacency matrix) the corresponding graph is a tree (or a forest). My question is what is the number of trees where their ancestry matrix is $M$.

Is this question any simpler than counting number of directed graphs which are compatible to a general ancestry matrix?

As hinted in the comments by @j_random_hacker, ancestry matrix, if valid, characterizes a unique rooted tree. A simple algorithm would be to create the tree from leaves to the root or vice versa.


Data Science vs Operations Research The general question, as the title suggests, is:

What is the difference between DS and OR/optimization.

On a conceptual level I understand that DS tries to extract knowledge from the available data and uses mostly Statistical, Machine Learning techniques. On the other hand, OR uses the data in order to make decisions based on the data, for example by optimizing some objective function (criterion) over the data (input).

I wonder, how these two paradigms compare.

Is one subset of the other?
Are they consider complementary fields?
Are there examples that one field complements the other or they are used in conjuction?

In particular, I am interested in the following:

  Is there any example where OR techniques are used to solve a Data Science question/problem?

While both Operations Research and Data Science both cover a large amount of topics and areas, I'll try to give my perspective on what I see as the most representative and mainstream parts of each.

As others have pointed out, the bulk of Operations Research is primarily concerned with making decisions. While there are many different ways to determine how to make decisions, the most mainstream parts of OR (in my opinion) are focused on modelling decision problems in a mathematical programming framework. In these kinds of frameworks, you typically have a set of decision variables, constraints over these variables, and an objective function dependent on your decision variables that you are trying to minimize or maximize. When the decision variables can take values in $\mathbb{R}$, the constraints are linear inequalities over your decisions variables, and the objective function is a linear function of the decision variables, then you have a linear program -- the main workhorse of OR for the past sixty years. If you have other kinds of objective functions or constraints, you find yourself in the realm of integer programming, quadratic programming, semi-definite programming, etc...

Data Science, on the other hand, is mostly concerned with making inferences. Here, you're typically starting with a big pile of data and you'd like to infer something about data you haven't seen yet in your big pile. The typical sorts of things you see here are: 1) the big pile of data represents the past results of two different options and you'd like to know which option will yield the best results, 2) the big pile of data represents a time series and you'd like to know how that time series will extend into the future, 3) the big pile of data represents a labelled set of observations and you'd like infer labels for new, unlabelled observations. The first two examples fall squarely into classical statistical areas (hypothesis testing and time-series forecasting, respectively) while the third example I think is more closely associated with modern machine learning topics (classification). Fun trivia: I believe that for a long time, the job title at Google for people doing what we now call Data Science was (is?) "Statistician".

So, in my opinion, Operations Research and Data Science are mostly orthogonal disciplines, although there is some overlap. In particular, I think that time-series forecasting appears in a non-trivial amount in OR; it's one of the more significant, non-math programming-based parts of OR. Operations Research is where you turn if you have a known relationship between inputs and outputs; Data Science is where you turn if you're trying to determine that relationship (for some definition of input and output).