Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $w_v : V \to \mathbb{N}$.  Let $\lambda$ be a known constant.
We need to find an exact cover $C \subseteq \mathbb{P}(V)$ of $V$ (with $\iota : V \to C$ being the associated injection) such that each $p \in C$ is a contiguous subset (interval) in $\mathbb{N}$ and
$$\lambda \left( \sum_{\iota(i) \neq \iota(j)} w_e(i, j) \right) + (1 - \lambda) \left( \max_{p \in C} \sum_{v \in p} w_v(v) \right)$$
is minimized.
In other words, we are trying to minimize a convex combination of the sum of the edge weights of the cut edges and the maximum total node weight for each part.
Is there an efficient algorithm for this problem? An approximation algorithm?

I suggest using dynamic programming.  Because your graph forms a path, we can use dynamic programming (considering all prefixes of the path), solving once for each candidate for the maximum total weight of the parts.  Details below.
Let $S$ denote the sum of the weights of the cut edges (i.e., the first part of your objective function) and $M$ the maximum total weight of the parts (i.e., the second part of your objective function), so that your goal is to minimize $\lambda S + (1-\lambda) M$.  Define $f(m)$ to be the minimum possible value of $S$, for all covers with $M \le m$.  I'll show below how to  calculate $f(m)$ for any desired $m$.  This  then is sufficient to compute the minimum possible value of $\lambda S + (1-\lambda) M$,  by enumerating all $m$ and  checking  which gives the lowest value  of $\lambda   f(m) + (1-\lambda) m$.
So, let's fix $m$ from here on.  For any $k$ that ends a consecutive interval in $C$, i.e., where $\iota(k) \ne \iota(k+1)$, define $S_*$ by
$$S_* = \sum_{i\le k, \iota(i)\ne \iota(i+1)}   w_e(i,i+1).$$
We will let $A[k]$ denote the minimum possible value of $S_*$, taken over all exact covers that contain an interval that ends at $k$ (i.e., where $\iota(k)\ne \iota(k+1)$) and such that $M\le m$ for this cover.  Note that this depends on only how vertices $0,1,2,\dots,k$ are partitioned by $C$, and doesn't depend on what is done with vertices $k+1,\dots,n-1$.
Now we can write a recurrence relation for $A[k]$:
$$A[k] = \min_t A[t] + w_e(k,k+1),$$
where $t$ ranges over $0 \le t < k$ such that $\sum_{i=t+1}^k w_v(i) \le m$.  Thus, for each $m$, you can fill in the array $A[\cdot]$ in $O(n^2)$ time using dynamic programming.  It's possible to get this down to $O(n \log n)$ time by pre-computing prefix sums for $w_v(\cdot)$ and binary search to find the range of allowable $t$'s, and storing $A[\cdot]$ in a balanced binary tree augmented with minimums stored in each tree node to quickly find the minimum of $A[\cdot]$ over a range of indices.   To get the total running time, we must multiply this by the number of values of $m$ we iterate through.  A trivial upper bound on $M$ is the sum of all vertex weights.
In this way, we obtain an algorithm whose running time is $O(Tn \log n)$ where $T=\sum_v w_v(v)$ is the total of all vertex weights.  In practice, often the running time will be less, as we can iterate through $m$ in increasing order, and once we find a solution whose objective function has value $v$, then there is no need to consider values of $m$ larger than $v/(1-\lambda)$.  As @j_random_hacker points out, we can replace $T$ with $O(n^2)$, if that helps: we only need to consider values of $m$ that are equal to the sum of vertex weights along some interval, and there are only $O(n^2)$ such intervals.
If you want an approximation algorithm, scale all of the vertex weights down by a factor of $c$, and then round to the nearest integer.  This will speed up the algorithm by a factor of $c$, and should approximate the optimal solution to within $\pm (1-\lambda)cn$ (probably better than that in practice).


How to determine enumerability after applying Rice's theorem? To my knowledge, lots of languages can be classified as undecidable after applying Rice's theorem, for example {"M" | L(M) is regular}.

But what I am not sure is, how to determine if a language is enumerable after applying Rice's theorem? I reckon we can examine that whether the M halt on some specific input, i.e. test if L(M) is an empty set. Am I right? Is there any principled way to determine a language's(composed of lots of Turing machines) enumerability?

You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to determine whether an undecidable language is enumerable or not, you can try to construct an enumerator for the language or its complement.


Algorithm in O(logn) I have a project where I should write the following algorithm :

  Let an integer function $f\colon\{1,2,3,\ldots,n\} \to \mathbb{Z}$ be monotone and suppose that $f(1) > 0$ and $f(n) < 0$. We would like to find the smallest integer $i$ with $f(i) < 0$. Design an algorithm for this purpose that run in time $O(\log n)4.

I tried to search in the middle ($\frac{n+1}2$) and then go in the right half or in the left half (like binary search) but the input is not sorted. Could someone give me an idea of how I can continue?

This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$.

As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$, it can be concluded that $f(i)$ is a decreasing function, which tells us that the array is sorted in decreasing order.

Here, we are looking for the smallest index $i$ such that $f(i)\lt 0$. We need to find a particular value of $i$ such that $f(i-1)\ge 0$ and $f(i)\lt 0$. Such an $i$ must be unique because for all indices greater than $i$, $f$ must be negative and for all indices less than $i-1$, $f$ must be non negative. Such an $i$ must exist as it is given that for at least one value each, $f$ takes positive and negative values. The index $i$ can be found by binary search as you suggested.


Why does TSP require no repetition of cities? It seems odd to me that the TSP denies the possibility of repeated cities.  The goal of this traveling salesman is to go as fast as possible and visit all of the cities, right?  So what if it is faster to travel through a city you have already been to?

It doesn't matter exactly how you define it because it's just a way of modelling a real-world problem. In TSP, you just have a set of cities and the cost of travelling between each pair of them. That doesn't exclude the possibility that, in the real world situation you're modelling, the best route between B and C might go through A. If that was the case then, yes, the route that is modeled as ABCA in TSP may very well really involve driving through A an extra time on the way from B to C but such detail is abstracted away in the TSP model.


Any suggestions about a known NP-complete problem that can be reduced to the following problem? Given an undirected graph $G$, where nodes represent towns and edges represent roads, and given a positive integer $k$, is there a way to build $k$ McDonald's at $k$ different towns so that every town either has its own McDonald's, or is connected by a (direct) road to a town that does have a McDonald's?

I believe that this problem is NP-complete. I am trying to find a well-known NP-complete problem, so I can use it to prove that this problem is NP-complete, too. Any suggestions?

This problem is called Dominating Set, and as pointed out by Raphael in the comments it's a special case of Set Cover (for each vertex, create a set for it and its neighbours).  It's NP-hard.


Split array into contiguous subarrays of approximately same sums My question is similar to this splitting question, but my objective function is different.

Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty subarrays ($N<n$) of approximately same sums:

$$
\min_{\text{splits}} \,(\max_j S_j - \min_j S_j),
$$
where $S_j$ is sum of numbers in $j$-th subarray $(j=1,\ldots,N)$.

E.g., best splitting of $100, 1, 1, 103, 90$ into three subarrays is $100,1,1|103|90$.

Typically $n\approx~10^6-10^8$, $N\approx 10-100$.

I suspect it would be some greedy approach...

This is a polynomial time algorithm:

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$).

Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as:
$$
\begin{cases}
 \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\
+\infty & \mbox{ otherwise.}
\end{cases}
$$

Let $OPT_{m^*}[i,k]$ the cost to split the array consisting of the first $i$ input elements into $k$  contiguous (non-empty) subarrays, and let $x_i$ be the $i$-th input element.
Then, for $i,k \ge 1$,
$$
OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1}
\begin{cases}
\displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt]
+\infty & \mbox{otherwise}
\end{cases}.
$$

Where $OPT_{m^*}[0][0] = 0$ and $OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$ for all $i,k > 0$.

The measure of an optimal solution to the original problem will be $OPT_{m^*}[n][N] - m^*$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $j$ chosen for each entry $OPT_{m^*}[i][k]$).


Prove that every CFL has at least one infinite equivalence class If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?

The language of palindromes over $\{0,1\}$ is context-free, but every Myhill–Nerode class is a singleton. So your claim is wrong for context-free languages (unless the alphabet is unary). In contrast, regular languages have a finite number of Myhill–Nerode classes, so at least one of them has to be infinite. The same is true for context-free languages over a unary alphabet, since all of them are regular.


Definition of uniform boolean circuit Definition
  A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log
  space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/Boolean_circuit#Uniform_Boolean_Circuits)

Can anyone exlain this? I know what boolean circuits are, so only explanation needed is what  and transducer exactly are.

Uniformity definition means that there is a deterministic Turing machine running in logarithmic space $\mathsf{L}$ that generates the description of the $n$th circuit from the unary encoding of $n$.

To have a better idea of what this is talking about, assume that we have a Turing machine $M$ in $\mathsf{P}$. Then for every input size $n$ we can generate a circuit of size $poly(n)$ that compute $M$ on inputs of size $n$. So we obtain a family of circuits $\{C_n\}_{n \in\mathbb{N}}$. However these circuits are not arbitrary independent circuits but coming from a single machine $M$.

The definition is good for large classes like $\mathsf{P}$ but it doesn't work for small complexity classes. For those classes we use deterministic logarithmic time $\mathsf{DLogTime}$ in place of $\mathsf{L}$. In place of printing the whole circuit we just require it to compute any given bit of the description of the $n$th circuit in logarithmic time.


True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable Question: Is the following statement true or false?

If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

I thought that since every language is automatically of type 0, it follows that $A \in RE$, and since RE is closed under the Kleene star operator, it follows that $A^* \in RE$ and therefore semi-decidable.

However the solution says it's not true and uses the following counterexample:

If $A = \{1^n0 | 1^n \not\in H'\}$, where H' is the unaryly coded halting problem. Since $\overline{H} \leq A$, A is not semi-decidable. If $A^*$ were semi-decidable then so would be $A^* \cap \{1\}^* = A$, since $\{1\}^*0$ is semi-decidable and RE is closed under intersection, which is a contradiction.

Since I don't fully understand that line of reasoning, could someone please tell me what's wrong with my argumentation?

It is not true that every language is recursively enumerable ("type 0").

Proof 1. Every RE language is semi-decided by some Turing machine. There are only countably many Turing machines (each one can be coded as a finite string, or an integer) but there are uncountably many languages.  Therefore, there are uncountably many languages that are not RE.

Proof 2. If a language and its complement are both semi-decidable, they are, in fact, both decidable.  The halting problem is semi-decidable. If the complement of the halting problem were semi-decidable then both it and the halting problem would be decidable. But we know that the halting problem is not decidable. Therefore, the complement of the halting problem is not semi-decidable.


Understanding Property Testing with a toy example I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example.

I did not understand the first step of the test in the following slide. Why is the first step $S= 2/\epsilon$?

Could someone please explain me in more detail (i.e. with a concrete example)? I would appreciate with that.

The problem is, given a string of length $n$ over $\{0,1\}$, to distinguish the following two cases:

The string is entirely 0.
The string is $\epsilon$-far from being entirely 0, i.e., has at least an $\epsilon$-fraction of 1s.

The proposed algorithm tests $S = 2/\epsilon$ positions, and returns (1) if all positions were 0. If the original string consisted of 0s then this algorithm always returns (1) correctly, and otherwise it makes a mistake with probability $(1-\epsilon)^S \leq e^{-2}$.

We choose $S = 2/\epsilon$ in the first step so that the error probability is constant, in particular less than $1/3$. If you want a different error probability, you'll choose a different value of $S$.


How do analogue computers perform logical operations? My idea of analogue computers had been that they were the discrete version of digital computers, with fuzzy logic operations returning values in the interval [0, 1] instead of Boolean operations.

However looking at schematics, they seem to be built for directly computing differential equations.

I'm struggling to connect this to dicrete computation. How do analogue computers perform simple logical operations?

As you point out, electronic analog computers were designed to compute differential equations, not simple logical operations.  You can model an arbitrary linear differential equation with a circuit made of op-amps, resistors, and capacitors, where the variables in your equation are represented by voltages and currents in your circuit.

For non-linearities you can add a diode.  The Shockley diode equation gives a good approximation for the behavior of a diode:

$$I = I_s ( e^{\frac{V}{nV_T}} - 1 )$$

(where $V$ is the voltage across the diode terminals, $I$ is the current, and $I_s$ and $n V_T$ are constants that depend on the construction of the diode.)  So now we can implement exponentials and logarithms.

So now to actually answer your question: logic circuits in modern digital computers are non-linear analog circuits where some circuit voltage or current is taken to represent the boolean value.  For example, we might say that a voltage greater than 5V represents true and a voltage less than 1V represents false.  (Any voltage between 1V and 5V is assumed to be an error).

In the 1950s this was sometimes implemented using diode logic.  For example the Wikipedia page shows this diagram of an or gate:

When this is followed by an inverting amplifier we get both a logical not operation, and restoration of any voltage levels that have degraded away from 0V or 6V.  For example a common emitter amplifier has this characteristic,

The point of all this is not that you have to use diodes and transistors to implement logic, but rather that any analog physical system with non-linearities and amplification can emulate boolean logic.  Hydraulic pumps, for example would have done just as well as diodes and transistors.


Parsing Dice Notation The syntax of dice notation follows the following grammar:

$$ Roll \rightarrow Dice | Dice'x'Int | More \quad Mod \quad More $$
$$ Dice \rightarrow Int_{1}'d'Int_2$$
$$ Mod \rightarrow '+'|'-'$$
$$ More \rightarrow Int | Roll$$
$$ Int \rightarrow <integer>$$

Give a leftmost derivation for the sample string:
$3d8 + 2d4x3 + 1d12 + 567$

I was able to parse the two first operands $3d8 + 2d4x3$ but I couldn't find a reasonable derivation for the rest.

My solution is like:

E -> More Mod More
E -> Roll Mod More
E -> Dice Mod More
E -> Int1’d’Int2 Mod More
E -> <integer>’d’Int2 Mod More
...
...
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + More Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Roll Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Dice Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Int1’d’Int2 Mod More

I was thinking that the given string is not a valid string for this grammar.

Does any have any idea for this problem. I'm newbie in Compiler Design :-)

Hint: Your string is of the form Dice+Dice+Dice+Int. Figure out how to obtain this from Roll using only the first, third and fourth rule.


How do I get and/or verify a formal Grammar for a given formal Language? I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language.
After some trying and fiddling I found one that I think works. The question is how do I verify it? On paper it looks fine, but are there some tools check this for me? Also are there easier methods than trying out by hand or brute force?

The Grammar I found is as follows:

$S\rightarrow aB_{1}A_{2}B_{2}|aB_{1}PA_{2}B_{2}$

$P\rightarrow A_{1}B_{1}A_{2}B_{2}|A_{1}B_{1}PA_{2}B_{2}$

$B_{1}A_{1}\rightarrow X_{A1}A_{1}$

$X_{A1}A_{1}\rightarrow X_{A1}X_{B1}$

$X_{A1}X_{B1}\rightarrow A_{1}X_{B1}$

$A_{1}X_{B1}\rightarrow A_{1}B_{1}$

$B_{2}A_{2}\rightarrow X_{A2}A_{2}$

$X_{A2}A_{2}\rightarrow X_{A2}X_{B2}$

$X_{A2}X_{B2}\rightarrow A_{2}X_{B2}$

$A_{2}X_{B2}\rightarrow A_{2}B_{2}$

$aA_{1}\rightarrow aa$

$aB_{1}\rightarrow ab$

$bB_{1}\rightarrow bb$

$bA_{2}\rightarrow ba$

$aA_{2}\rightarrow aa$

$aB_{2}\rightarrow ab$

$bB_{2}\rightarrow bb$

You don't really need the various $X$ nonterminals, just use rules $B_iA_i\to A_iB_i$ instead.

For correctness, use induction to show (1) that you can reach $aB_1(A_1B_1)^k(A_2B_2)^{k+1}$, and from there $a^{k+1}b^{k+1}a^{k+1}b^{k+1}$, for all $k\ge 0$, and (2) that all generated words have the required form. For the second part, try to find some auxiliary conditions (e.g. numbers of $A_i,B_j$ match; if a factor $B_1A_1$ is not rewritten to $A_1B_1$ before the $B_i$ is replaced by $b$, the derivation gets stuck; etc).


How to Specify the Behavior of Automata for Verification I am wondering what it takes to "verify" or "prove" that an automaton is correct. What the components are that are required. It seems that an automaton would be an easier thing to formally verify as sound than say an arbitrary function. Not sure though what needs to be verified in an automaton, which is what brings up the question.

Thank you!

It feels to me like this has already been explained before (1, 2).  To prove that an automaton is correct, you first must define what correctness means to you.  Usually that is done by writing a specification of what it means to be correct.  Then, you prove that an automaton meets the specification.

If you're interested in knowing how to do that, that's a broad subject that people have written entire books about.  I suggest reading a textbook on model checking (particularly of finite-state systems).

How do you know what the specification should be?  Well, you have to figure out what correctness means, or the requirements are.  That's not really a question about computer science but rather a question about your application or your business domain and what problem you are trying to solve or what you're trying to do with the automaton.

If you're asking "what to verify", we can't answer that, because that's something you have to decide: you have to decide what properties you want to prove.  It's like asking 'how do I prove the natural numbers?'  You can't.  You have to decide what theorem you want to prove, before you can ask how to prove it.  If you ask a mathematician how to know what theorems to prove, the answer will probably be something like "well, you have to figure out what you want to know or what is interesting to know".


Is there a way to find path length to a node from root in a binary tree? I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in an array. That is, an array stores the parent values from one node to the root and the same is done to the second node and finally the arrays are compared to find the first mutual parent.

I got stuck when finding the time complexity of this algorithm. I have a feeling that, it depends on the path length of a node to the root. Is there a generalised equation for the path length of a binary tree? If not, how can I compute the time complexity of this algorithm?

PS-I want to find the time complexity wrt to n=number of nodes/elements

Node findLCA(BT tree, Node N1, Node N2){
    Array parentsN1;
    Array parentsN2;
    while(N1.parent != null){
        parentsN1.append(N1.parent)
        N1=N1.parent;
    }
    while(N2.parent != null){
        parentsN2.append(N2.parent)
        N2=N2.parent;
    }
    for(i in parentsN1){
        for(j in parentsN2){
            if (i==j) return i;{
                return null;
            }
        }
    }

}

The worst case scenario for the algorithm is when you pick two nodes, N1 and N2 that have the longest path to the root node. In your example, two nodes whose common ancestor is J.
Say the length of the path of N1 and N2 is n and m.
Then the first while is O(n), the second one O(m) and finally the nested loop is O(nm).
So O(n) + O(m) + O(nm) = O(n*m).


A problem about master theorem and recursion Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.
I think that the statement is false.
Do you know any counterexamples?

Taking $n=2^k$, we have
$$T(n)=2T\left(\frac{n}{2}\right)+f(n)=\\=2\left[2T\left(\frac{n}{2^2}\right) +f(n)\right]+f(n)=2^2T\left(\frac{n}{2^2}\right)+2f(n)+f(n)=\\=2^3T\left(\frac{n}{2^3}\right)+2^2f(n)+2f(n)+f(n)=\cdots=2^kT(1)+f(n)[2^{k-1}+\cdots+1]=\\=2^kT(1)+f(n)(2^k-1) = nT(1)+f(n)(n-1)$$
Now we have 2 cases: 1. $T,f$ are defined only for $2$s powers and 2. $T,f$ are defined on $\mathbb{N}$.

Considering non negative functions, condition $T \in O(f)$    gives
$$ f(n)(n-1) \leqslant T(n) \leqslant C f(n)$$
which is impossible for any below boundedness for $f$.

If we demand $T$ defined on $\mathbb{N}$, then we come to necessity to define $T\left(\frac{n}{2}\right)$ which can be filled by OP.


Assuming NP≠coNP, do we have a similar theorem to Ladner's? We have that $\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$.

So by assuming that $\mathrm{NP\neq coNP}$, can we prove the existence of intermediate problem between $\mathrm{NP}$-complete and $\mathrm{NP\cap coNP}$?

Yes.

Before answering your question, let me make it clear that the reasoning provided in the link Filmus suggests above will not work for $\mathrm{NP\cap coNP}$, since this nasty class refuses to be efficiently enumerated. Also, it is very unclear to talk about $\mathrm{FP^{NP\cap coNP}}$-reductions, not to mention how to enumerate them. Very faint an idea to do complexity theory that way.

By Ladner's splitting theorem for $p$-degrees, every non-zero $p$-degrees splits into two lesser incomparable $p$-degrees.

Now, by the assumption that $NP\neq NP\cap coNP$, the $NP$-complete degree is separated from $P$ (zero $p$-degree). Applying the splitting theorem and downward closure for $p$-m-reduction of $NP$, we have that the complete degree $\mathcal{C}$ splits to two lesser degrees $\mathcal{A}$ and $\mathcal{B}$.

Whenever $\mathcal{C}$ splits into $\mathcal{A}$ and $\mathcal{B}$, we have that $\mathcal{C\subseteq P^{A, B}}$. And, we know that $\mathrm{P^{NP\cap coNP}=NP\cap coNP}$.

So, at least $\mathcal{A}$ or $\mathcal{B}$ must be outside of $NP\cap coNP$. That is the intermediate degree you are seeking.


Min-entropy of a random pre-image of a random function I am facing hard time understanding min-entropy.

Fix $v \in \{0,1\}^{n/2}$, let $F\colon \{0,1\}^n \to \{0,1\}^{n/2}$ be chosen randomly, and let $X_v$ be a string chosen uniformly at random among $F^{(-1)}(v)$ (or a special string $\epsilon$ if $F^{(-1)}(v) = \emptyset$). We want to compute the probability that $H_\infty(X_v) \leq n/4$ (over the choice of $F$), where $H_\infty(X_v)=-\log(\max_{x}\{\Pr[X_v=x]\})$ is the min-entropy of $X_v$.

It's not obvious what approach is needed to solve such things! It would be helpful if one could explain where to start...

Since $X_v$ is a random variable which is uniformly distributed over its support $F^{-1}(v)$, its min-entropy depends only on the size of the support (and it equals the entropy). The min-entropy is at most $n/4$ if and only if $|F^{-1}(v)| \leq 2^{n/4}$. Now $|F^{-1}(v)|$ is binomially distributed $\mathrm{Bin}(2^n,2^{-n/2})$, since for each string $x \in \{0,1\}^n$, the probability that $F(x) = v$ is $2^{-n/2}$. Therefore you are interested in bounding
$$
\Pr[\mathrm{Bin}(2^n,2^{-n/2}) \leq 2^{n/4}].
$$
You can obtain a good bound on this event, which is rather unlikely, using Chernoff's bound or Hoeffding's bound. Let us know if you encounter any difficulties.


Unambiguity of Reverse Polish Notation Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation:

$G=({E},{a,+,*},P,E)$
$P={ E \rightarrow EE+ | EE* | a }$

I know this grammar is unambiguous.

What I do not understand is how I can prove this.

I already searched a lot to in google, etc. but everyone only says, that reverse polish notation are unambiguous, but not WHY.

Can you give me any hints?

To show that a grammar is unambiguous, it is enough to show that for any expression E, there is only one "last step" possible in any derivation of E. It is the case here : the last rule is given by the last symbol of the expression (either +, *, or a terminal a), and the parentheses will prevent any ambiguity.
Of course you can not write "$abc+$" in your grammar, it has to be $(ab)c+$ or $a(bc)+$, but this is implicit when you define a grammar.

For instance, $a(bc+)*(bc)*+$ is not ambiguous : the last rule is given by the last symbol +, and so on... the expression it represents is $(a*(b+c))+(b*c)$


Can any computably enumerable set be generated by a prefix-free set? Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the prefix-free set is equal to the first set).  I don't understand why this would be so.
Specifically, in a proof that a sequence is Martin-Löf random iff is there is no c.e. martingale on the sequence that produces infinite profit, on page 236, D&H assume that for each class $U_n$ that makes up a Martin-Löf test, there is a "prefix-free generator" $R_n$ (which I take to be what I described above, cf. p. 4).  D&H's definition of Martin-Löf test is on 231: the sequence of $U_n$ is merely required to be uniformly c.e. s.t. $\mu(U_n)\leq 2^{-n}$.
I don't understand why such a generator must always exist.
For example, let $U_n$ be$\{00000\ldots\}$ for all $n$.  Then each $U_n$ is null with respect to the uniform measure, so this is a Martin-Löf test.  However, any finite sequence of zeros that would include a sequence of all zeros as an extension, would also have extensions such as $01\ldots$, $001\ldots$, etc., which are not in $U_n$.   So there is no generator of $U_n$.
Clearly I am misunderstanding something (or have not noticed some constraint on Martin-Löf tests?).

After a lot of thinking and reading, and getting a helpful answer and comments from Andrej Bauer to another question that my investigation prompted, I can answer my own question.  I post an answer for the benefit of anyone who may find the question to be similar to one of their own.  I expect no upvotes for answering my own question.
Downey and Hirschfeldt prove (2.19.2, p. 74) that every $\Sigma^0_1$ set of infinite sequences is one that can be generated by a c.e. set of finite strings.  Moreover, they define Martin-Löf randomness in terms of a sequence of $\Sigma^0_1$ sets $U_n$ of infinite sequences.  This is why they have the right to assume that every such $U_n$ can be generated by such a set of finite strings.
In my gloss of D&H's description of a Martin-Löf test, I stated the requirement that the test sets be $\Sigma^0_1$ as a requirement that they be computably enumerable.  One can see the equivalence of $\Sigma^0_1$ and c.e. as implied by D&H's proposition 2.19.2, but it's proved directly by, for example, Nies, 1.4.12, p. 22.  So the way that I characterized D&H's description of Martin-Löf tests was correct.
While it's true that $U_n=\{000\ldots\}$ can't be generated by finite strings, my mistake was thinking that such a $U_n$ is computably enumerable.  It was surprising to me to realize that such a trivially simple set is not c.e.  After all, the set has only one element, and a Turing machine that generates it or checks for it is trivial.  The crucial point, though, is that that machine cannot halt on $000\ldots$, since the sequence of zeros is infinite.  No program can ever successfully list or accept even (the) one member of this set.  Thus my sequence of sets $U_n$ do not form a Martin-Löf test.
(It is possible to define a Martin-Löf test that excludes only $000\ldots$ from the random sequences, but that test has to consist of sets such as, for example, $U_n=\{x:$ the first $n$ digits of $x$ are 0$\}$.  Each such set contains an uncountably infinite number of infinite sequences, but each is a subset of previous sets $U_1, U_2, \ldots, U_{n-1}$. The one sequence contained in each of them is $000\ldots$ .)


Why are primitive types stored in a stack in systems level software? Firstly 2 disclaimers, I am very new to the concept of a stack at a low level. I've only encountered it because I'm learning rust and the docs mention it. Secondly, I am aware of another similar question on this site, but it doesn't address a very specific concern.

My understanding of a stack is that it follows First In Last Off and cannot be searched, this confuses me if I do this.

variable a = 22;
variable b = 33;
variable c = 44;

Then my understanding is that c will be on top of the stack. So if I want to do something with a and b, will the system have to pop c and dig deeper for a and b? This seems inefficient. And an indexed array seems better.

You've probably encountered the simplest definition of a stack, which is a data structure with two operations push and pop, and some basic properties:

If you call push on a value and then pop, the value you get from the pop is the value passed to push, and the stack is returned to its original state.
pop is invalid on a stack where there has never been a push (empty stack).
These properties also apply if the stack is modified in the middle, as long as these modifications return the stack to its state before the modifications.

There are many equivalent formulations of these axioms. The point here is that with this definition, push and pop are the only things you're allowed to do on a stack.

With the metaphor of a stack as being like a stack of plates, you can't “peek” at a value that isn't at the top of the stack (the most recently pushed value). (Note that I'm describing a stack that grows upwards. Unfortunately there's no standard for that: some stacks are described as growing down. But even with downward-growing stacks, the word “top” usually means the most recently pushed value.) But when a stack is a data structure, it's often possible to access values anywhere in the stack.

The same word “stack” can mean any variant of the basic data structure, supporting other operations apart from push and pop. There's no completely universal limit for what can be called “stack”, but generally, if a data structure is called a “stack”, it means that it's a collection of values where the only way to add an item is push and the only way to remove an item is pop. Other operations may be supported, such as:

Reading the stack size.
Peeking, i.e. reading any of the values on the stack (not just the top one).
Modifying a value on the stack.

Let's look at programming languages now. Almost every programming language has a concept of function (or procedure, subroutine, method, etc. — the distinction is not relevant here). Function calls have certain properties:

If the code in function f calls a function g and then g returns, you're back to f, in the same context as before (“context” here means the values of local variables).
You can't return from the top level of the program that's not inside a function. (Depending on the programming language, this may not even be a thing: the program may start directly by calling a certain function, so that there's no way to have code outside of any function. Or a ”return“ statement outside of any function may exit the program instead.)
These properties also apply if there are additional sequences of function calls involved that return back to the original function.

Looks familiar? Yep, the function calls form a stack. (Many programming languages have ways to break the stack structure, such as exceptions which can pop many values from the function call stack in a single statement, or even more complex things that I won't go into.)

The way the function call stack is implemented on a processor is usually through a stack of return addresses. Each function call does a push of the current value of the instruction pointer before jumping to the code of the called function, and returning from a function is a pop in that stack and a jump to the popped address.

Each time a function is called, its local variables come into existence. So the variables, in turn, form a stack. Calling a function pushes a new entry on the variable stack for this function's variables, and returning from a function pops an entry from the variable stack. (You can model this either with a single entry for all of a function's variables and a single push/pop per call/return, or with one entry per variable and as many push/pop per call/return as the function has variables.)

Note that variables are associated with a function call, not just with a function. When a function is called recursively, or more generally as part of a chain of calls of mutually recursive functions, each function call has its own variables, even if they happen to be calls to the same function. Conversely, local variables of a function don't “exist” while the function isn't being called. (Some of the very first programming languages had one storage area per routine, which existed all the time. These languages did not permit recursive calls. No modern programming language works that way, but some hardware description languages do.)

In a language with dynamic scoping, if a function f calls a function g, the code of g can access the variables of f by name. This is an example of a stack with extra operations: the code of g can read and modify the variables of f. The code of g can't create new variables of f or destroy variables of f, so this is still a stack. In a language with [lexical scoping]9https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping), the code of g can't access the variables of f by name, but it may nonetheless be able to access and modify their value if it can see a pointer or reference to a variable of f.

So far I've described how almost every programming language works. The specifics of what “the variables of a function call” means depends on the programming language. There's the association between the variable name and its value, and there's the value itself. Most programming languages have three classes of storage: global (exists for the whole lifetime of the program), stack (lasts as long as a function call), and heap (can be created and destroyed arbitrarily). But how apparent this is depends heavily on the language. In most higher-level languages, these classes of storage are a detail of how the compiler or runtime environment works, because storage allocation and destruction is automatic. Variables have a scope (the parts of the program where a certain name refers to that variable). Storage usually doesn't have an explicit scope in higher-level languages, but it does in lower-level languages.

In Rust, the scope of storage is explicit. A variable's storage lives as long as the variable lives, i.e. until the function returns. It lives longer if the value is returned from the function. Heap storage requires explicitly boxed values.

Now that I've described what a stack is as an abstract data structure, and how it arises when describing the theory of programming languages, I'm finally read to discuss how it works in the implementation of a programming language. Here, I'm going to describe how most implementations of most programming languages work when compiled to native code. (Languages compiled to byte code are typically fairly similar, but may be a bit further from this simplified description.) It's possible to do things differently, but unusual. I'm also going to keep things simple and not go into details that aren't important to understand the basic concept, such as registers, function parameters, return values, block scope, etc.

The typical way to implement a function call stack is to store the return addresses and the local (unboxed) storage for its variables in a single memory area. This specific method of implementing the stack abstract data structure is also called a “stack”. The stack of memory management for function calls works this way:

There's an array of memory which is reserved for the stack.
Pushing means copying a value to the top of the stack and incrementing the stack pointer, which is an index into the array of memory.
Popping means reading the value at the top of the stack, then decrementing the stack pointer.
To call a function, push the current value of the instruction pointer, then push enough storage for the function's local variables. The set of things pushed at this stage constitute a stack frame.
To return from a function, pop the stack frame and jump to the return address.

As long as a function call is in progress, its variables are in its stack frame. To access them, you need to know their address. To access a variable of the current function, all you need to know is its position in the stack frame. And the address of the stack frame of the current function is the top of the stack minus the frame size. So for example, let's imagine a simple (unoptimized) compiler for a simple programming language and the following program fragment in a function:

variable a = 22;
variable b = 33;
variable c = 2 * a;

This is compiled as:
* Allocate a frame with room for three variables.
* Write 22 to the address sp - 3 where sp is the stack pointer. (For simplicity, in this example, I assume that all variables have the size 1. Having differently-sized variables just requires keeping track of their sizes and doing additions at compile time.)
* Write 33 to the address sp - 2.
* Read a value from the address sp - 3, multiply the value by 2, and write the result to the address sp - 1.

As you can see, accessing a variable doesn't require popping to it. This is because computer memory itself is not a stack, but random-access memory. The stack that contains the local variables is a stack only because it grows and shrinks according to a stack pattern, not because it's impossible to access elements that are not at the top.

Accessing a variable of a function which isn't the current one doesn't require popping to it either. It does require knowing the address of that variable. If a variable has access to another function's variable, this can be either because the variable was passed as a parameter, or because the current function has access to a reference (pointer) to that variable. In either case, what happens under the hood is that the address of the variable is stored somewhere where the called function can access it.


Why does taking advantage of locality matter in multithreaded systems? As we all know, when a given thread/process reaches a memory address it does not have cached, the execution will (for the most part) freeze up until said data is fetched from memory. What I don't understand, is why in multithreaded systems, we can't save ourselves the headache of data-oriented design. Why can't the processor/OS simply do work elsewhere on a different thread until the data is received?
I couldn't find a good post on this exact question, and this may just be obvious to others. I only know so much about the pipeline and such so there could be a very obvious reason for this, I simply don't know why.

Ask yourself: How long does it take to load data from memory, and how long does it take to stop one thread from running and start another thread? Starting another thread would usually take a lot longer, plus a new thread would have the exact same problem, having to wait for data to be ready.
An exception is hyperthreading cores. A hyperthreading core can officially run two threads simultaneously, but doesn’t actually have twice the processing power of a normal core, so it cannot actually perform twice as many instructions or anywhere near that. Such a core can however process operations of the second thread immediately when the first thread cannot proceed for any reason.
Now it’s debatable if hyperthreading is actually a win, especially since it gives hackers ways that operations in one thread can very subtly affect operations in another thread, leading to massive security problems. As a result, many high-performance ARM processors don’t implement hyperthreading at all.


0/1 Knapsack problem with real-valued weights Is there a known solution for the 0/1 knapsack problem that allows the weights of the objects to be real numbers? The only algorithm I can think of is a brute force search. I have tried searching for a solution but couldn't come across any. When weights are natural numbers, the most common solution uses dynamic programming by caching solutions $V[i,w]$ to the subproblems in an $N\times W$ table, where $N$ and $W$ are the number of objects and weight limit of the knapsack. When the weights are real numbers, the dynamic programming solution breaks down: how do you define the table now? Granted there will be $N$ rows, but what about the columns?

Sort the items by density such that $p_1/w_1\geq p_2/w_2\geq\cdots\geq p_n/w_n$ for profits $p$ and weights $w$. Let $W(k)=\sum_{1\leq i\leq k} w_i$ be the total weight of the first $k$ items in this order. Then for capacity $c$ an optimal fractional solution is to choose items $1,\ldots,i^*$ where $i^*$ is the largest number s.t. $W(i^*)\leq c$ , and additionally a fraction of $(c-W(i^*))/w_{i+1}$ of item $i^*+1$.

Update: I misread your question. For solving the $0$/$1$ version with real-valued weights you can either round them, or apply branch-and-bound algorithms that were designed for real values, e.g. Martello and Toth's MT1R.


Find subset with minimal sum under constraints Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function.

Now find $C' \subset C$ with the following constraints:

$$
\bigcup C' = M \\
\forall x,y \in C': x \cap y = \emptyset \\
\sum_{x \in C'}w(x) \text{ minimal}
$$

In words: Find a subset $C'$ of pair-wise disjunctive pairs over $M$ that covers $M$, with the sum of these pairs being minimal. Any element of $M$ must appear in exactly one pair.

I could not find an efficient algorithmic solution, and I also fail to relate this to any other known (optimization) problem. I was thinking of the subset sum problem, but I don't see any relation.

So the questions is: Can you find an efficient algorithm to find $C'$? A good approximation might also be sufficient. If not, can you reduce this to any other known computer science problem?

Your problem is known as minimum-weight perfect matching, and can be solved in polynomial time using several different algorithms. One algorithm that can be used is Edmonds' Blossom algorithm. See also Cook and Rohe, who discuss how to implement Blossom.


Looking for clarity on step in fractional knapsack problem proof I'm reading through the proof for the fractional knapsack problem presented here: https://www.cs.rice.edu/~nakhleh/COMP182/Knapsack.pdf
I follow the proof until the definition of the new set $Q = \langle q_1, q_2, ..., q_n \rangle$

for every $1 \leq i<j: q_{i}=o_{i} ($also $q_{i}=y_{i})$ which is constructed as follows:
$q_j=y_j$
For $i=j+1$ to $n$

\begin{array}{l}
- d^{\prime} \leftarrow \min \left(q_{i}, d\right) \\
- q_{i} \leftarrow q_{i}-d^{\prime} \\
- d \leftarrow d-d^{\prime}
\end{array}
I don't understand where the $q_{j+1...n}$ elements come from. We only fill $Q$ up to $q_j$, but to fill $q_{j+1}$ we reference $q_i$ which is undefined — should it be 0? What am I missing?

All appearances of $q_i$ on the RHS are errors -- they should be replaced with $o_i$. I imagine the author was thinking of "initialising" $Q$ to be equal to $O$, and then updating its elements in-place.
Another minor issue I have is with the line "After this procedure is done, the total value of the solution $Q$ is equal to the total value of $O$ (make sure youunderstand why!)". This is true, but as this is the key part of an introductory proof, I think it would have been better to break it into its two parts:

For any $k > j$, moving positive weight from $o_k$ to $o_j$ results in a solution with value $\ge$ the original solution.
The original solution $O$ was assumed optimal, so the $\ge$ becomes a $=$.


Making 5-tuples out of their respective 4-tuples Let's take integer numbers from [1..36]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five distinct (unique) numbers. Each such five-number-combination always contains 5 four-number-combinations (like (1,3,12,7), etc.). All 376992 different (unique) five-number-combinations have 58905 different (unique) four-number-combinations. All these four-number-combinations also have all (four) distinct numbers - being a subset of a set with unique numbers.

Five-number-combinations and four-number-combinations (tuple-4) always have 5 or 4 distinct (unique) numbers respectively. This is prohibited: (1,1,2,3,4) or (2,3,5,2)

Then I take at random approximately half of those 58905 different four-number-combinations - let's call them "unused 4-tuples".

Finally I need to generate all possible five-number-combinations each being such that it always consists of 5 unused four-number-combinations. That is all five four-number-combinations within such five-number-combination are from the "unused 4-tuples" set.

Direct (brute-force) algorithm is like this: I take a set of n=28000 unused 4-tuples, generate all combinations from that set by k=5 (binomial(n,k)) and then check that all five 4-tuples in such combination give exactly five numbers from [1..36] (say, I add individual numbers from every 4-tuple [out of every five 4-tuples] into a set and then check if the set contains exactly five numbers). Having checked all possible combinations (of five 4-tuples) I have solved my task.

The only problem is that binomial(30000,5) = 143368518402340005600  :)))

Could you think of some math trick to somehow sieve and shortcut that process, or maybe a tip to a more clever algorithm?

Go over all $\binom{36}{5}$ possible five-number combinations. For each one, calculate the five four-number combinations, and check whether all of them are unused.

In order to check whether a given four-number combination is unused, you can use a table. This will allow each such test to proceed very quickly. You can either use an array of size $36^4$ using the trivial encoding, or a slightly more sophisticated one of size $\binom{36}{4}$.


Practicality of compressing data with hashing algorithms I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string.

I realize it's impossible to represent $2^{128}$ possible strings with inputs less than 128 bits long, even if MD5 had no collisions. However, a percentage of 128 bit strings could still be compressed using this concept.

Maybe another hash algorithm could be made with this application in mind. It does not need to be secure, irreversible, or computationally difficult. It just needs to represent the largest number of output strings given a string who's length is smaller than the output.

Multiple hashing algorithms could be used to increase the number of possible strings that could be compressed.

Is this idea practical? Could this idea be applied to compress large chunks of arbitrary data such as a file?

This idea is not practical, because there are some serious problems:

You have to calculate all interesting hashes (less than hash length, here 128 bits), which is infeasible.
There must be a way to tell apart compressed and not compressed strings, so some kind of terminator or escape sequence must be introduced.
Since hash functions are designed with avalanche effect (small change in the input should yield huge difference in the output) there are no shortcuts for computations.
The preimage resistance prevents from fast reversing, given hash calculate the input, this also gives another problem, once the data is compressed, the decompression also requires full hash -> input mapping.
The hash signature is quite specific, there are almost none naturally occuring natural texts with such substrings.
If you want to use them in cascade it will be greedy approach, optimal one would require to calculate all cases to given depth and choose the smallest
Multiple hashing algorithms enhance the additional description sequence, now the simple one bit (compressed or not) is not enough, it should also encode which algorithm was used.
With collisions, the number of available hashes of given length decreases. The guarantee of better hash increases the complexity (both time and code).

The idea itself may be tempting, but it is not practical enough to be used in the common compression software, this tells quite a lot.

Please see also Compression with PRNG and Collision free hashes to compress and the compression of random data


Is it possible to obtain a total function by composition of partial functions? This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis:

  If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $g_k$ by composition then $h$ is (partially) computable.

What I understand from this theorem is if there is at least one partial function among the composed function then $h$ is partial function. Am I right?

Here is an example, the functions $x$ and $x+y$ and $x.y$ are total but  $x-y$ is a partial function. it is possible to obtain $4x^2-2x$ by composition of these functions in the following way, this function is total but it is obtained from an non-total function ($x-y$).

$2x = x+x$

$4x^2 = (2x)(2x)$

$4x^2-2x$          composition of $x-y$

This is an example from the book, is this example a contradiction of the theorem?

The theorem should be read as "If you compose computable functions, you get a computable function; if you compose partial computable functions, you get a partial computable function."

Note that, perhaps confusingly, partial computable is a larger class of functions: every computable function is partial computable.  One could reduce the confusion at the cost of verbiage by calling them total computable functions and partial-or-total computable functions.  If you compose total computable functions, the result is a total computable function.  If you compose partial-or-total computable functions, the result is a partial-or-total computable function.

Your example in the question shows that it's possible to combine a total function and a non-total function to get a total function. Notice that both examples actually only apply total functions directly to the inputs and at least one of the inputs to the non-total function is the output of a total function. In those circumstances, it's still possible to get a total function as the result of the composition.  Conversely, if you apply a non-total function directly to your inputs (and none of its inputs is the output of some total function), your composition is guaranteed to be non-total.


Finding the (probable) maximum of a large set of integers *without* iterating over all of the values As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers.  Importantly, I do not have direct access to the full list of integers, but I do have a function $f(n)$ which returns true/false if $n$ is in the set.  The function $f(n)$ is expensive and I would like to minimize the number of calls I must make to it.

The integers might or might not be consecutive, or have large gaps between them (i.e. might be sparse or dense).  There is no prior-known upper bound on the largest integer in the set, which can go off to infinity in theory.

Is there a well-trodden algorithm for doing this?  My inkling is to do some kind of random sample to determine the density, and then try to find the upper bound within some certainty.  I'm not sure how to bound my initial sample properly then though, or which distribution I might assume the integers have based on that sample.

Thanks.

Tricky.

As an approximation, assume that the number n is in the set with a probability p (n), and the sum of p (n) over all integers n is finite, so we may guess that the set is finite.

You'd have to check enough values n to make some reasonable assumptions about p (n), and then based on those assumptions make a reasonable guess about the upper bound.

But let's say that p (n) = $1 / n^2$. The probability that there is any element n ≥ N is about 1/N. So 10 is an upper bound with probability 90%, 100 is an upper bound with probability 99% and so on. On the other hand, your checks will likely show that 1 is an element and find no others. p (n) could be any of a gazillion of possible probabilities.

Your chances are much better if you have some knowledge about the distribution.


Complexity of Special Case Problems Often I see a sentence like this while reading texts on Computational Complexity:

"For this special case of $\text{TSP}$" or

"This is a special case of $\text{SAT}$" or

"$k$-$\text{PARTITION}$ is the following special case of $\text{BIN PACKING}$" or

"$\text{SUBSET SUM}$ is a special case of $\text{KNAPSACK}$" ad nauseam.

What I find missing is the criterium to claim one problem is a special case of another.
What is the necessity of classifying one problem as a special case of another?  Does a special case always carry the complexity class as its  'unspecial' case?

Often this is simply stated with no proof of relation between these problems.

What requirements must be met for a problem to be a special case of another?

How can I prove a new Language for a problem is a special case of an already existing problem?

When we say that a problem $B$ is a special case of a problem $A$, we mean that $B$ is the same problem as $A$, with the exception that not all problem instances of $A$ are problem instances for $B$. If $B$ is a special case of $A$, we say that $A$ is a generalization of $B$.

Two examples: the addition of positive whole numbers (say $5 + 3$) is a special case of addition of whole numbers (say $5 + (-3)$), and sorting of integers in the range $\{ 1, 2, \dots, k \}$ for fixed $k$ is a special case of sorting of arbitrary integers.

Any solution to $A$ is also a solution to $B$, and any hardness results for $B$ (for example, it is $NP$-hard or needs $\Omega(n^2)$ time to be solved) immediately transfer to $A$. However, we usually consider special cases because we can sometimes find better algorithms for them compared to the general case.

Examples: the $\Theta(n \log n)$ sorting algorithm works just as well on integers in the range $\{ 1, 2, \dots, k \}$, but CountingSort works on the special case (not on the general) in $O(n + k)$, which is usually faster if $k$ is small. $SAT$ is $NP$-hard, $3SAT$ is a special case of $SAT$ that is still $NP$-hard (which therefore implies that $SAT$ is $NP$-hard), but $2SAT$ is in $P$.

Note that the above definition is sometimes stretched (abused) to say that you can encode any instance of $B$ as an instance of $A$, and that this encoding is extremely simple. In that case, the above usually still holds, but is less rigorous.


Must a min weight subset of edges connecting all vertices form a tree? Got this question in an exam.

In a graph where all edge weights are positive, if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree?

True or false?

This seems to be the definition of a MST, but since it doesn't state anything about cycles I'm not 100% sure.

Claim : if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree

True. It is the definition of MST on weighted (positive) graphs. Subset $S$ can't form a cycle due to minimum total weight condition.

You can prove this by contradiction, assume $S$ is a MST and forms a cycle, as all weights are positive, you can still remove a one edge $e$ from a cycle. $S -e $ is still going to be connect all the vertices of graph, but subset $S - e$ has total weight strictly less than the total weight of $S$, this is a contradiction to our assumption.


How do I solve a search problem on an infinite graph? I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \times V$ is an undirected set of edges connecting vertices. Both $V$ and $E$ can be infinite. Each edge has an associated cost $c: E \rightarrow \mathbb{R}$ and the cost of a path (an ordered set of edges) between adjacent vertices that leads from the start to the goal is the sum of the cost of all of its edges. My goal is to find the path with minimal cost (assume it exists).
From my understanding, because this graph could possibly have an infinite branching factor, A* is not guaranteed to return a solution (or terminate). Are there any viable alternative algorithms that are designed for handling graphs with large or infinite state and action spaces? I'm not looking for guaranteed termination or optimality, just some names of algorithms that might be used in these sorts of problems as my search for "heuristic search infinite state space" doesn't turn much up.

I believe you can use any algorithm for heuristic search.  On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.


Algorithm to build a "hand" calculation for riichi mahjong game I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game.

I will simplify terms to focus on the algorithm and not on the game specific terms.

Let's imagine that we have a card deck with three suits. Each suit contains cards from 1 to 9 and each card has four copies.

So card deck looks like this:

111122223333444455556666777788889999a (a is a first suit)
111122223333444455556666777788889999b (b is a second suit)
111122223333444455556666777788889999c (c is a third suit)

Each player has 14 cards in his hand and hand should contains four sets and one pair to be able win. Set can be built from three consecutive cards (123a) or from three same cards (444a).

Input data: 14 cards.

Output data: all possible variants of 4 sets and one pair.

Examples:

Input: 123678a234678b44c

Output: [123a 678a 234b 678b 44c]

Input: 233445a 44556677b

Output: [123a 345a 456b 456b 77b], [123a 345a 567b 567b 44b]

Also, it can be cases with 5-10 possible variants of the hand.

I tried to build it with recursion, but I wasn't successful. The main question how to determine that we don't have remaining variants?

Thanks for your help in advance.

Pretty much any approach will be fine.  The trick is to focus on generating all possible ways to partition the hand into groups of size 4+4+4+2, then test each candidate to see whether it is valid.  If you've enumerated all possible ways in the first step, then you'll know you've found all possible variants/solutions.

Even a totally dumb, unoptimized brute-force approach will probably be fast enough: enumerate all partitions of the 14 cards into groups of size 4+4+4+2, and for each, check whether it's valid.  There are

$${14 \choose 4} \times {10 \choose 4} \times {6 \times 4} /6 = 525,525$$

different such partitions.  Therefore, you should be able to enumerate all partitions and for each check whether it satisfies the rules.

Of course there are likely much faster algorithms.  For instance, you can enumerate all possibilities for the first card in the first "set", then enumerate all ways to complete the first "set" (usually there won't be that many, given the restrictions on a valid "set"), then enumerate all possibilities for the first card in the second "set" out of the remaining cards, then enumerate all ways to complete the second "set", and so on.  In practice this will probably be even faster.

It's easy to find all variants with this kind of approach.  You just test each possible partition/grouping, and output each one that is valid.

As another optimization, it's easy to figure out the suit that you must use for the "pair".  Count the number of cards you have in each suit. For there to exist a valid combination, two of these numbers must be $0 \bmod 3$ and one must be $2 \bmod 3$.  The latter is the suit that the pair must come from.  Try all possibilities for how to choose the pair (from that set) -- there usually won't be that many possibilities, as there usually won't be many repeated cards in that suit.  For each such possibility, try all ways to divide the remaining 12 cards into 3 "sets".

As another optimization, after you've chosen and removed the pair, if you have a suit that contains exactly 3 cards, you know that if there is any valid combination, those 3 cards must be placed together in a set -- you have no choice (it's forced).  This further cuts down on the number of possible combinations you must examine.  If there's a suit that contains exactly 6 cards, there are only ${6 \choose 3} = 20$ ways to divide it into two groups of 3; you can check each candidate division to see which ones are comprised of two valid "sets".  These two cases will cover most hands.  The only difficult case is where there's a single suit that contains exactly 9 or 12 cards (after removing the pair), and you can fall back to enumerating all partitions for those (rare) hands, or devise alternative strategies for handling those specific cases.


Multi modal learning from separate modal datasets Let's say I'm trying to learn emotion given multi-modal sources. In this case, video and audio. However, I only have one dataset for video emotions and one dataset for audio. Is it possible to train a Deep Learning classifier on each dataset separately? One way I can imagine doing this is creating some sort of shared hidden units, similar to the figure below:

However, in the publication this is taken from, these weights are trained simultaneously.

Are there examples of this type of multi-modal learning in the literature? I'm not sure what to look up and all I can come up with myself is "something-something Deep Belief Network".

Back in 2012, this was accomplished by Srivastava and Salakhutdinov in "Learning Representations for Multimodal Data with Deep Belief
Nets" where they mixed textual and visual features using the following Deep Belief network architecture:

Note the specially defined hidden layer that can be trained independently.

More recently in 2015, this was accomplished by Huang, Y.; Wang, W. and Wang, L. in "Unconstrained Multimodal Multi-Label Learning" where they use a conditional Restricted Boltzmann Machine applied to creating text labels for images:

Note that each observed variable, t for tags and m for images are connected to h, but there is the built in assumption that m is more frequently available than t.

One problem with both of these approaches is I'm unclear on how well they're going to scale.


Why is there readonly (const) in C++, but not writeonly (sink)? C++ initially had "readonly" and "writeonly" qualifiers, before "readonly" was renamed to "const", and "writeonly" removed. My question is: What are the problems with "writeonly" (or a "sink" qualifier)?

There are (non-object oriented) programming languages with "in", "out" and "inout" qualifier for functions arguments. In that context, the meaning of "out" is pretty clear. Writing "result_p = result_p+1" is not allowed if "out int& result_p", and the question whether "result_p += 1" is allowed doesn't arise, because these languages don't have "+=" and similar constructs.

Now "sink" in C++ would be a type qualifier, not just a function argument qualifier. The meaning of "sink" is clear on a semantic level. Information is only allowed to flow into a "sink" qualified object, but no information is allowed to leave a "sink" qualified object. So writing "result_p += 1" would be allowed if "sink int& result_p", but what about "result_p = result_p+1"? Its semantic is fine, but there seem to be no general way to check this based on simple syntax or typing rules. But so what, does anything bad happens if "result_p = result_p+1" is not allowed?

I can only hypothesize, so maybe this should only be a comment, but it's too long for the comment box.

In general Stroustrup tries extremely hard to avoid adding new keywords to the language, so if he discovered that there was another way to get whatever "expressivity" writeonly might provide he would remove the keyword.

My guess is that he actually couldn't find much use for writeonly.  Stroustrup came from an Operating Systems background, and (according to [1]) a lot of the stuff about const and friend originally derived from analogies to O.S. access rights.  (For const, think read/write/execute permissions on files in Unix, and for friend think of one program granting access permissions to another program.)

The analogy apparently only goes so far though.  The usefulness of a writeonly parameter would seem to be that it allows you to return more than one value (but you can return a pair or a struct in C++, and you can "return" an error code by throwing an exception, and perhaps one return value plus an error code is the common case.)  Declaring a non-parameter variable as writeonly makes no sense, because then you would need to do a cast in order to do anything with the value.  A writeonly function is a constructor, and C++ already has those using a different syntax (that doesn't require a new keyword.)  An append operation for vectors most certainly can not be writeonly, because it must increment the length of the vector (i.e., length = length+1.)

[1] Bjarne Stroustrup, The Design and Evolution of C++, Addison-Wesley, 1994.


What is the best solution to find whether the sum of an array is even or odd I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really interested in the actual sum, I just want to know whether it's even or odd.

Or how do I prove that it cannot be done better than $O(n)$?

By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.

The adversary argument tells that in theory you have to check each element. By the way, it does not mean you have to sum them up. You can simply count the numbers of even numbers and odd numbers (or go through the array by +1 for even and -1 for odd).


Solving Hidoku problem using reduction to Hamilton path It seems like people have discussed this reduction here:

Is Hidoku NP complete?

But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an hamilton path/cycle exists), what about extracting the solution itself from this reduction?

Can someone see how it is possible?

Best regards,
Tal

For any NP-complete problem where the question is, "Can you complete this partial solution?" you can extract a solution from the decision problem just by filling in components of the solution one at a time and asking if there's still a solution.
Is there a solution with $1$ in the top-left corner? No. With $2$ in the top-left? No. With $3$? Yes. OK, let's fix the top-left to be $3$: we know this can be extended to a solution. Is there a solution with $3$ in the top-left corner and $1$ in the square next to it? And so on.  (In fact, you can be a bit more efficient by using the fact that two of the neighbours of the square labeled $i$ must be $i-1$ and $i+1$.)
This is a specific case of the concept of "self-reducibility": a problem is self-reducible if you can find the answer given an oracle for smaller instances of the decision problem. (In the case of Hidoku, the instances the oracle is called on are smaller in the sense that they have fewer blank squares.)  Some other examples of self-reducible problems are:

SAT. Suppose you want to know whether a formula in variables $X_1, \dots, X_n$ is satisfiable. If it's satisfiable, then either there's a satisfying assignment with $X_n=t$, or there's one with $X_n=f$, or both. So replace $X_n$ with $t$ and ask if the resulting formula in $n-1$ variables is satisfiable.  If so, recurse; if not, set $X_n=f$ and recurse.

$3$-colourability. Suppose you want to know whether a graph $G$ is $3$-colourable. If it is $3$-colourable and it has more than three vertices, then two of the vertices must receive the same colour. So, pick two non-adjacent vertices $x$ and $y$ and merge them (delete $y$ and make every vertex that was adjacent to it be adjacent to $x$). If the resulting graph is $3$-colourable, then $G$ has a $3$-colouring in which $x$ and $y$ have the same colour, so recurse. If they don't, then any $3$-colouring must assign different colours to $x$ and $y$, so we can add an edge between them and try a different pair of non-adjacent vertices.
If this process ever gives a graph that contains a $4$-clique –which we can test in polynomial time – then $G$ is not $3$-colourable. Otherwise, we eventually reduce the graph down to a $3$-clique, which is $3$-colourable. We can recover the $3$-colouring by tracking which vertices got merged into the different vertices of the $3$-clique.

Independent set. Suppose we wish to know if a graph $G$ has an independent set of size at least $k$. Pick a vertex $v$ and ask if $G-v$ contains a $k$-independent set. If so, $G$ has a $k$-independent set that doesn't include $v$, so recurse on $G-v$ to find out what it does contain. Otherwise, any $k$-independent set must contain $v$, so it can't contain any of $v$'s neighbours. So ask if $G-v-\Gamma(v)$ contains a $(k-1)$-independent set. If it does, recurse. If it doesn't, $G$ has no $k$-independent set.


Solving Exact2IS using IS i encountered the following problem:

Exact2IS ={G has exactly 2 independent sets}

Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.

(i can check if a graph contains independent set in O(1) and also find some independent set in O(1))

I was thinking on find some independent set(if there is any) of size k and then remove one vertex from the set and check if the graph still has independent set of size k
-after i check i return the vertex to the graph exactly as it was.

The problem my idea check only if a graph G contains at least 2 independent sets and not exactly.

Anyone have an idea how can i check if a graph has exactly 2 independent sets(in polynomial time and given the fact that find and check if there is independent set is O(1))?

Any clues or ideas will be appreciated :)
Thanks

First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all independent sets of size $k$ contain $v$. Accordingly, remove $v$ and all its neighbors, and find an independent set of size $k-1$ in the remaining graph. In this way, you can recover an independent set of size $k$.

Second, how to check whether a graph contains at least two independent sets of size $k$, assuming $k \geq 2$. First, you determine whether in contains at least one. Suppose that it does, say $I$. If $J$ is any other independent set, then $I \setminus J$ and $J \setminus I$ are both nonempty (since $|I| = |J|$). In particular, if $x \in I \setminus J$ and $y$ is any other vertex in $I$, then even after adding the edge $(x,y)$, the set $J$ will constitute an independent set.

This leads to the following algorithm: for each pair of vertices $x,y \in I$, check whether $G + (x,y)$ contains an independent set of size $k$. If so, this independent set is necessarily different from $I$. Conversely, if an independent set of size $k$ different than $I$ exists, then necessarily it will be an independent set in $G + (x,y)$ for some $x,y \in I$.

Third, how to check whether a graph contains exactly two independent sets of size $k$. This is the same as checking whether a graph contains at least three independent sets. I think that at this point, it's better if you try to generalize the above argument from two to three independent sets. You might get stuck, but you won't know until you try.


Construct a digraph given its in-degree and out-degree distribution Could anyone help me with this algorithmic problem:

Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph can allow self loops but not parallel edges.

Here's an example:

Vertex A: in=1 out=1
Vertex B: int=2 out=2

For which we can construct this graph:

A => B
B => A
B => B

Here's another example:

Vertex A: in=0 out=1
Vertex B: in=1 out=1

Here, we obviously cannot construct such graph.

I have been scratching my head around this problem.
For an undirected graph, there exist a simple algorithm to solve this problem but I cannot find any way to derive a solution for directed graphs.

I have the intuition that we could find a matching algorithm in the bipartite graph representing the in and out edges of the graph and where each out-edge would be matched to an in-edge.

However the usual approach can produce a graph with parallel edges.

For example 1, a valid solution could be:

A- A+: A => A
B- B+: B => B
B- B+: B => B

Which is not a valid graph.

Also, please note that I am more interested in determining if a valid solution exists. It's not necessary to provide or construct such solution.

The following remarks are taken from a paper by Berger. I assume that you don't allow parallel loops.

The idea is to frame the problem on bipartite graphs. One side of the bipartition consists of the "inside" of vertices, the other of the "outside". Each vertex $v$ has two copies $v_-,v_+$, and we want $d(v_-)$ to be the indegree of $v$, $d(v_+)$ to be the outdegree of $v$. The existence of such a bipartite graph is the the focus of the Gale–Ryser theorem, which gives an efficient algorithm.

A similar criterion for the case in which loops are forbidden also exists, see Berger's paper quoted above.


Compute 'permutation' like problem with modulo Say, I have some permutation or combination formula like this,
$$\frac{n!}{(n-r)!r!},$$
and I want to $\bmod$ the result with some big prime ($10^9+7$ for example).

I already tried with modular operation and multiplicative inverse but failed (I don't quite understand them). Can someone give me some example in code so I can grasp the idea? (I prefer C).

The idea is that $(a + b) \pmod{p} = ((a \pmod{p}) + (b \pmod{p})) \pmod{p}$ and $(ab) \pmod{p} = ((a\pmod{p})(b\pmod{p})\pmod{p}$. In C code, computing $a + bc \pmod{p}$ is accomplished by

  t = (b*c) % p;
  return (a + t) % p;

Regarding inverses, when $p$ is prime and $1 \leq a \leq p-1$ there is an element $1 \leq b \leq p-1$ satisfying $ab = 1 \pmod{p}$, and so $(x/a) \pmod{p} = (xb) \pmod{p}$. To find $b$ use the extended GCD algorithm to find $b,c$ such that $ab + cp = 1$.


How can I find spans where the distance between two poly-lines is more or less than some threshold? I have two poly-lines. I would like to find segments of these lines where the minimum distance between them is higher (or lower) than some threshold.

I.e. I want to find the parts of the lines highlighted in squiggly pink here:

My best attempt is to split each line into some equally sized segments, and then use dynamic programming to find the closest corresponding points on each line. This is efficient, and works, but will of course be off by some amount from the real points where the minimum distance is reached. Making the segments smaller will make the solution better (but slower), but I have a feeling a continuous and exact solution is possible?

Given a point $P$ and a polyline $L$, you can compute the distance from $P$ to $L$ (i.e., the distance from $P$ to the nearest point on $L$).

Now take the union of all of the following points:

The endpoints of the line segments in the blue polyline
For each endpoint of each line segment in the red polyline, the closest point on the blue polyline
All intersection points where the blue polyline intersects the red polyline

This set can be computed efficiently, and its size is linear in the size of the input.  Let $P_1,P_2,\dots,P_n$ denote these points, in the order they appear on the blue polyline.  Let $Q_i$ be the point on the red polyline that is closest to $P_i$.

Now consider any pair of consecutive points $P_i,P_{i+1}$.  As we move along the blue polyline from $P_i$ to $P_{i+1}$, the distance to the red polyline will either increase monotonically or decrease monotonically.  Thus, if it crosses the threshold (e.g., starts below the threshold and increases to something larger than the threshold), you can use binary search to find the point where it crosses the threshold.

In fact, we can say more.  Consider a point $P = \alpha P_1 + (1-\alpha) P_{i+1}$, as $\alpha$ increases from $0$ to $1$,  and let $Q$ be the nearest point on the red polyline to $P$.  As $\alpha$ increases from $0$ to $1$, $P$ be moving along a straight-line path, i.e., along a single line segment of the blue polyline.  Similarly, $Q$ will also e moving along a straight-line path, i.e., along a single line segment of the red polyline.  Consequently, there's a simple formula for the distance between the two as a function of $\alpha$, and we can solve for the $\alpha$ that makes this distance equal to the threshold.  Thus, this will let us precisely identify the point where the minimum distance between the two polylines is exactly equal to the threshold.

Now doing a linear scan over all consecutive pairs $P_i,P_{i+1}$ will enable you to find all places where the minimum distance is higher than some threshold, exactly.


Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard? Suppose $\Pi$ is a decidable decision problem.

  Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?

Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?

If you assume that $\mathsf{NP}\neq\mathsf{coNP}$ then any coNP-complete problem gives a counterexample. I would guess that one can refute your conjecture unconditionally.


Need introductory guide to cellular automata for geographic automata systems I would like to work on urbanisation and I've read that cellular automata has potential use on model urban sprawl. However I need some kind of introductory to cellular automata in order to tackle an academic paper I have found.

I have a fair background in Computer Science. Moreover I am looking for any tools from CS applied to cities.

This here might help you as an introduction to cellular automata, written by Joel L. Schiff: INTRODUCTION

Furthermore, there is a copy of "Modelling Urban Development with Geographical Information Systems and Cellular Automata" by Yan Liu online. I do not know whether I can link it here, but you can easily search for it.


what is halting problem? i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure would stop that program,or an code will be processed by the input to decide if the program will be executed or will be halted after that.So what is the halting problem actually?

Consider the set of all possible pairs $ \langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may not.

Basically, the Halting problem asks to create a Turing machine that takes a pair $ \langle M, w \rangle$ as input, and eventually halts with answer "YES" if $M(w)$ halts, and "NO" if $M(w)$ does not halt.

If you are familiar with programming you could interpret this problem as following. The Halting problem asks you to write a C++ program which reads another target program together with its input written in C/C++, and always stops and prints "YES" if the target program eventually stops on the input,  and prints "NO" otherwise. Note that your program must work for any finite size of target program and any finite size of input.

As for its history, this is one of famous David Hilbert's 23 questions posed in 1900 at the Second International Congress of Mathematicians in Paris, and later in 1936 was solved by Alan Turing to show that such algorithm deciding on all possible pairs $ \langle M, w \rangle$  cannot exist.

This Wikipedia article provides a formal definition of the problem and sketch of proof.


First-time and second-time seen edges in DFS on undirected graphs Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on the same page, define a discovered vertex x as one that has been visited but descendants of it are still being processed, i.e., we have not yet returned back to x. Define, a processed vertex x as one that we have returned to after we have recursed into all of its descendants and we mark it as such upon return.
Let us define the following edge types on that tree

Tree edges: direct parent/child edges: the parent is the one to first discover the child.
Back edges: edge from a descendant to an ancestor at least 2 levels up on the tree: the descendant sees an already discovered vertex.

Those are the only two types of edges one can have on undirected graph DFS. Now, I have been reading The Algorithm Design Manual (page 173) which discusses the following:

Given an undirected graph DFS and an edge (x,y) as seen from x how can we tell whether we have seen this edge before from the side of y?

I can understand the cases when y is undiscovered or discovered but not yet processed.
However, the book says that if y is processed then we can say that it's the 2nd time (i.e., we have seen the edge (x,y) from y before); this is because we should have seen all edges coming out of y before marking it as processed. The part I don't understand is when such a case can occur. How can we see y again after we have marked it processed? Can you give me an example of such a graph?

Here is the simplest example.
Let the graph contain two vertices, $x$ and $y$ with one edge $\{x,y\}$. Here is a run of the algorithm.

$x$ and $y$ are marked as "undiscovered".
$y$ is marked as "discovered" and enqueued.
$y$ is dequeued.

Since $x$ is adjacent to $y$ and $x$ is "undiscovered", $x$ is marked as "discovered" and enqueued.
All vertices adjacent to $y$ have been "discovered", so $y$ is marked as
"processed".

$x$ is dequeued.

$y$ is adjacent to $x$ but $y$ is not "undiscovered", do nothing.
All vertices adjacent to $x$ have been "discovered", so $x$ is marked as "processed".

The queue is empty. Done.

You can note that, at step 4.1 when $y$ has been marked as "processed", we are seeing y again by the same edge $\{x, y\}$.

Here is an exercise that characterizes such occasions.
Exercise. Suppose we are given a BFS or DFS of a connected undirected graph with more than one vertices.  Let $y$ be a vertex. Show the following two propositions are equivalent.

There is a time that $y$ was seen again when $y$ had been marked as "processed".
$y$ is not a leaf of the search tree.


Why are regular expressions defined with union, concatenation and star operations? A regular expresssion is defined recursively as

$a$ for some $a \in \Sigma$ is a regular expression,
$\varepsilon$ is a regular expression,
$\emptyset$ is a regular expression,
$(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
$(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
$(R_1)^*$ where $R_1$ is a regular expression is a regular expression.

This definition is taken from page 64 of

  Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.

Now, I have the following questions.

Why do not the definition contain the intersection, complement or reverse operations?
If we change the 4th item to $R_1 \cap R_2$, do we get an equivalent definition, i.e. for each regular language, there is a modified regular expression and vice versa?
I know that this definition is complete and well-defined, but why is it preferred to other equivalent, well defined and complete definitions?

1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other operations are not mentioned is the goal of keeping the definition as simple as possible, so that (inductive) proofs do not have to take care of to many cases. Another cause might be that if we allow certain operations, but others not, in some cases very distinct (subregular) language classes result, for example if we consider extended regular expression without the star operator, then we get a proper subclass of the regular ones, the so called star-free or aperiodic languages, see wikipedia:star-free language.

2) If we keep items 1. - 6. but just alter item 4. in using intersection instead of union, we get a proper subclass of the regular languages. For example we could no longer describe the language $L = \{a,b\}$ as it would involve the union of $\{a\}$ and $\{b\}$ (see proof below). If we allow complementation, things change as we have union back by DeMorgan's laws.

3) This was partly answered by me in 1), but what you mean when you say that this definition is preferred? I know definitions where 2. is omitted (as we have by 6. that $L(\emptyset^{\ast}) = \{\varepsilon\}$), or 3. is omitted (as we have $\emptyset = L(\overline{ X^{\ast} }$)), or both are omitted; so this one is not the minimal possible definition (it gives us also some syntactic sugar as we have extra symbols to describe $\{\varepsilon\}$ and $\emptyset$).

EDIT: My first mentioned comment in 2) was wrong, languages in the inductive closure under $\circ$, $^{\ast}$ and $\cap$ do not neccessarily are subsets of $x^{\ast}$ for some $x \in X$, for example consider $L(a\circ b) = \{ab\}$. Nevertheless we have that $L = \{a,b\}$ could not be describes by such an expression. I will give a proof, namely I proof that
if $L = L(R)$ for some expression with the modified 4th item, then if $X = \{a,b\}$ (and hence $a\ne b$)
$$
 \{a,b\} \subseteq L \Rightarrow ab \in L.
$$
The proof goes by induction on the expression $R$. For the base case it holds vacuously, now suppose it holds for $L(R_1), L(R_2)$.
If $L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$ and $\{a,b\} \subseteq L$,
then $\{a,b\} \subseteq L(R_i), i = 1,2$ hence by induction hypothesis we have $ab \in L(R_1) \cap L(R_2)$. If $\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$ then as $a = a\cdot \varepsilon = \varepsilon\cdot a$ we must have $a\in L(R_1)$ and $\varepsilon \in L(R_2)$ or vice versa. Suppose the first case. If $b \in L(R_1)$, then $ab \in L(R_1)$ by induction hypothesis, hence $ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$. Now suppose $b \in L(R_2)$, then we have $a\cdot b \in L(R_2)L(R_2)$ by definition of $L(R_1)L(R_2)$. Lastly if $a,b \in L(R_1^{\ast})$, then $a \in L(R_1)^n$
and $b \in L(R_2)^m$ for some $n,m > 0$. If $n = m = 1$ we find $ab \in L(R_1)$ by induction hypothesis, so suppose $n > 1$, but this gives $a \in L(R_1)$, similar either $m = 1$ or $m > 1$ gives $b \in L(R_1)$ and the induction hypothesis gives $ab \in L(R_1) \subseteq L(R_1^{\ast})$. $\square$

Remark: One commonly used conclusion: If $a = uw$, then $u = a$ or $w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.


What is the purpose of using NIL for representing null nodes? In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for example a child of a node (in a tree) that does not exist.

Once, during a lecture, instead of saying NIL, my classmate said null, and the professor corrected him, and I don't understand why professors emphasise this word.

Is there a reason why people use the word NIL instead of null, or none, or any other word? Does NIL have some particular meaning that the others do not have? Is there some historical reason?

Note that I have seen also a few places around the web where, e.g., the word null was used instead of NIL, but usually this last one is used.

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming languages implement this differently, and some languages might not have any such concept. In languages with pointers, it's a null pointer. In many object-oriented languages, null is not an object: calling any method on it is an error. To give a few examples:

In Lisp, nil is commonly used to stand for the absence of a value. Unlike most other languages, nil has structure — it's a symbol whose name is "NIL". It's also the empty list (because a list should be a cons cell, but sometimes there is no cons cell because the list is empty). Whether it's implemented by a null pointer under the hood, or as a symbol like any other, is implementation-dependent.
In Pascal, nil is a pointer value (valid in any pointer type) that may not be dereferenced.
In C and C++, any pointer type includes a NULL value which is distinct from any pointer to a valid object.
In Smalltalk, nil is an object with no method defined.
In Java and in C#, null is a value of any object type. Any attempt to access a field or method of null triggers an exception.
In Perl, undef is distinct from any other scalar value and used throughout the language and library to indicate the absence of a “real” value.
In Python, None is distinct from any other value and used throughout the language and library to indicate the absence of a “real” value.
In ML (SML, OCaml), None is a value of the any type in the type scheme 'a option, which contains None and Some x for any x of type 'a.
In Haskell, the similar concept uses the names Nothing and Just x for the values and Maybe a for the type.

In algorithm presentations, which name is used tends to stem from the background of the presenter or the language that is used in code examples.

In semantics presentations, different names may be used to refer to e.g. the NULL identifier which denotes a pointer constant in the language, and the $\mathsf{nil}$ value in the semantics. I don't think there's any standard naming scheme, and some presentations leave it up to a font difference, or don't go into concrete syntax at all.

It's possible that your lecturer wants to use the word null for a null pointer constant in the programming language used in the course (Java or C#?), and NIL to denote the absence of a node in some data structures, which may or may not be implemented as a null pointer constant (for example, as seen above, in Lisp, NIL is often not implemented as a null pointer). This distinction would be relevant when discussing implementation techniques for data structures. When discussing the data structures themselves, the null-pointer-constant concept is irrelevant, only the not-equal-to-any-other-value concept matters.

There is no standard naming scheme. Another lecturer or textbook could use different names.


How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space? Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$

Prove that MULT $\in L$

How do I show that this language, MULT, is computable in Logarithmic space?

Let us assume a#b#c is on the input tape, we now need away of multiplying a with b and checking if the product is c, while using only $log(n)$ space while n is the length of the input.

In high-school multiplication, you multiply $a$ by $b$ by summing shifted copies of $b$, some of them zeroed out (according to $a$). You can implement this algorithm in logspace by calculating the result from LSB to MSB, keeping track of the carry. The crucial point is that the carry is only $O(\log n)$ bits long.


Notation for average case complexity of an algorithm I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis.

For example, I have tested my algorithm and fitted the results to the curve $f(n)=2.65\times 10^{-15}\cdot(2.17^{n})$ and in my report right now I'm saying something like:

  the average case complexity was found to be $\approx 2.65\times 10^{-15}\cdot(2.17^{n})$,

but I would rather say something like

  the average case complexity is $\in \Theta(2.17^{n})$.

But I'm not sure if this is technically correct because the result hasn't been theoretically proven, only empirically tested and fitted to the curve.

The notation $\Theta(f(n))$ isn't reserved for worst-case complexity, it's asymptotic notation applicable to functions in general. So you can state that the average case complexity is $\Theta(2.17^n)$, and it means exactly what you think it does. (Regardless of whether this has been proved or not.)


Pruning: Outlier Candidate Selection I am using method 3.3 described in Outlier Detection using Isolation Forest and Local Outlier
Factor .
It states:
Specify a dataset: $={_1, _2, ..., _}$.
Here,  is the sample number of . $_$ is an attribute in $$, and $_={_1,
_2, ..., _}.$ $_$
is a certain data value of the attribute $_$
.
The outlier coefficient of the attribute is defined as:

Here, $\bar{}$ is the mean of the attribute $_$ and $_$
is used to
measure the degree of dispersion of the attribute $_$
. Calculate
the outlier coefficient of each attribute in the dataset, and
get the outlier coefficient vector $_$ of the dataset, which is
recorded as:
$_ = _1, _2, ..., _n$
However, I do not understand what value to select for $x_j$.  What does a 'certain data value' mean in this case?

I suspect this paper has typos (see e.g., line 2 of Algorithm 1).  If so, you're going to have to guess from context what they might have meant.
It's possible that they might have meant to write
$$fd_i = \frac{\sqrt{\frac{\sum_j (x_j - \bar{x})^2}{n}}}{\bar{x}}$$
In other words: the ratio between the standard deviation and the mean of that attribute.
Who knows; this is just a guess.  You might try contacting the authors.


Quantum computer memory size Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers).

Does it also hold for memory size? Are QC going to have exponentially increased memory?

No, quantum computers are not going to have an enormous number of operations per second, in fact they are probably going to be much slower in the foreseeable future. The situation with memory seems even bleaker – so far only a handful of bits.

The big advantage of quantum computers is that they can run quantum algorithms, which work rather differently from classical algorithms. Very informally, they provide a way of going through many possibilities at the same time. This gives an exponential speed up for some tasks, and a polynomial speedup for others – in terms of the number of operations. Even though each individual operation is going to be slower, since you need to run drastically fewer, the overall algorithm would run much faster.