Simpler proof of Rabin's Compression Theorem? I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to.

Rabin's Compression Theorem states that every reasonable complexity class has a problem that can be solved optimally in it.  The proof is a little involved, but not horribly difficult.

The audience member proposed a much simpler proof.  For the given complexity class, calculate the target volume of computation from the input length.  Then write that many hashes to the output.

Does this really prove the same result?

Also, I have had a lot of trouble finding Rabin's original paper.  Does anyone know how to get it?

A formal version of the argument would be:
Given a constructible function $f$, find a program that is optimal for $O(f(x))$ time, where $x$ is the length of the input.

def program(input):
    x = len(input)          # takes O(x) to read input of length x
    target = f(x)           # f is constructable, computing f(x) takes at most O(f(x))
    for _ in range(target): # takes exactly O(f(x)) to loop f(x) times
        print('1')          # assume we can append to the output in O(1)

The runtime of the algorithm is clearly $O(f(x))$.

The algorithm is optimal:
Any program that prints $f(x)$ "1"s requires at least $f(x)$ steps.

As far as I can tell, this proof seems to work. It almost certainly proves something similar. However, I can't understand why the original proof would be so complicated, if this simpler proof works.  This makes me worry that maybe I misunderstood something: e.g., about why the original statement is important/interesting, or about whether this simpler proof is correct and proves what it needs to prove.  Can anyone help clear this up for me?

It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book Complexity Theory and Cryptology: An Introduction to Cryptocomplexity by Jörg Rothe, page 63:

  For each time constructible function $t(n)$ there exists a decidable set $D_t$ such that each deterministic Turing machine $M$ deciding $D_t$ must run in time larger than $t(n)$ for all large enough $n$.

Granted, this is not exactly your statement (it might be a different theorem proven in the same technical report of Rabin from 1960, or perhaps a different publication of Rabin from the same year), and it also differs from the rather unclear statement in Levin's lecture notes, which is closer to your statement but also seems to mention a predicate (though Levin's proof doesn't result in a predicate).

Both statements are somewhat different than your informal statement that every complexity class has a problem that can be solved optimally in it. They also seem to mention that the problem can be chosen to be a predicate.

In order to make progress, I suggest that you update your question with a complete formal statement of Rabin's compression theorem as you understand it, explaining no longer standard notions such as volume. Then try to formally prove the theorem along the lines you mention. If you succeed, include the proof. If you fail, you have answered your own question.

It is likely that there is some easy version of the theorem that does follow from your argument, but the actual theorem is harder, requiring either a delicate priority argument (like in the book) or a Kolmogorov complexity argument (like in Levin's notes). This may be due to one of two features of Rabin's theorem:

It gives a predicate rather than an arbitrary function.
The actual guarantee is a bit different. For example, in Levin's version you should be able to compute the function in all volumes which are asymptotically larger than the optimal complexity.

Also, depending on your computation model, your own function might not be computable in your own time bound (though multitape machines seem fine here).

Why am I so sure that there is something wrong with your argument? Your argument is very simple, and I find it hard that it was missed by both Rabin and Levin. It is much more probable that it just doesn't work, or that it proves a weaker version of the theorem.


When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed? The depth-first and breadth-first algorithms for traversing graphs use a flag (or  color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. When the traversal is complete all the nodes in the graph are black.

None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.

Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?

Your question is, essentiall, "How is this stuff implemented?", to which the answer is "However the implemnter chooses."

Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress.  In a concurrent environment, it would also limit you to doing only one search at a time.  Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A* search. This data structure will simply be deallocated when the search is complete.

If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.


How to prove "The power set of a countable set must be uncountable"? I'm not sure if this statement is correct, but my friend said so.

The problem arose from this T/F question:
Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $2^F$ (Power set of $F$) is uncountable.

And its answer is True. The set of primitive recursive functions is countable, and I would like to know the proof to the statement above...I believe I've seen it somewhere in the book but can't find it now.

Thank you for your time.

This is Cantor's diagonalization lemma:

Let $S$ be a countable set and suppose that there is a bijective function $\phi: S \to 2^S$.  Let $U = \{x \in S \mid x \notin \phi(x)\}$.  (Notice that our only assumption is the existence of the bijective function.)

Since $U \in 2^S$, and $\phi$ is bijective, there must be a $u \in S$ s.t. $\phi(u) = U$.

Now I ask you:  Is $u \in U$?

If you answer that question, you have the answer: $\phi$ cannot exist!  Hence $2^S$ cannot be countable.  You should also show that there is an injective function $\psi: S \to 2^S$, but this is trivial: $\psi(x) = \{x\}$, so $|S| \leq |2^S|$.

To complete the argument you must also show that there cannot be a bijective function from $\mathbb{N}$ to $2^S$ but this is immediate since there is one from $\mathbb{N}$ to $S$.


Tightening application rules for STLC The syntax STLC is usually written:

$e ::= x |\lambda x : \tau . e|(e \space e)|c$

However, the application rule appears to accept all expressions on the left hand side. Shouldn't the application rule be written:

$(\lambda x : \tau . e \space e : \tau)$ ?

The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression. All other cases would be:

$(x \space e)$ makes no sense. By the time application can take place x will be substituted with its bound expression. By this logic it will be either an abstraction, as labeled okay above or something else, discussed below

$(c \space e)$ again, you can't apply to a value.

$((e \space e) \space e)$ this is not an issue because applications resolve to an expression, and following that recursive logic it will resolve to one of the aforementioned cases.

Shouldn't the application rule be written:
$(\lambda x : \tau . e \space e : \tau)$ ?

No, there are at least three problems with this formulation:

First, it is important that the first time can be a variable. For example, we want to allow the term
$$
x \; y
$$
Why do we want to allow this? Well we want to be able to apply a function to an argument. For example, the following lambda term is a function which applies $x$ to $y$:
$$
\lambda x: \tau_1 \to \tau_2. \lambda y: \tau_1. (x \; y)
$$

Second you are assuming the first term has already been reduced. This is not generally true. Although once reduced, the term $e_1$ in $(e_1 \; e_2)$ should usually be a lambda expression (or a variable), this may not hold before it has been evaluated.

The third problem is really a misunderstanding, not a concrete issue with your formulation: in STLC, we allow terms that are not well-typed. For example, if there are base types including numbers and Booleans, then we can write nonsense like
$$
\text{true} \; 3
$$
and this is a valid lambda term, just not a well-typed one. So your question seems to want to make sure that the application rules is well-typed, but that will be part of the typing rules, not part of the definition of a lambda term itself.

The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression.

That is correct, and this is going to be the motivation for the typing rules. In fact, the typing rule will say this exactly: the term $e_1 \; e_2$ will be well-typed only if $e_1$ is a function $\tau_1 \to \tau_2$ and $e_2$ is a value of type $\tau_1$. But for the reasons above, it is important that these restrictions be on the typing level, not baked into the syntax.

$(x \space e)$ makes no sense.

It does make sense: but only in a context where $x$ is a variable of a function type. Think of a variable that may be assigned to a value; if it is assigned to a value which is a function, then this makes sense.

$(c \space e)$ again, you can't apply to a value.

It's true that this makes no sense, but we allow it anyway; we just don't say that it is well-typed.

$((e \space e) \space e)$

As you said this case may resolve to one of the other cases, but we are defining the syntax here, not the semantics. So it doesn't imply that we should rule it out just because resolves to the other cases; it is still a valid lambda term, just one that is not fully reduced.


Can you increase data rate by increasing number of bits? My question is on data rate and baud rate.

data rate = baud rate * n

The question is, can you keep on increasing the data rate by increasing baud rate or number of bits.

I believe it can be increased by increasing the baud rate but what about the latter part?

Theoretically you can, but in reality you can not. The problem in raising the number of bits one symbol represents is that you have to space the symbol levels closer and closer together. Therefore even small amounts of random noise lead to misinterpreted symbols. A first attempt at calculating the maximum data rate is Nyquist's formula:

maximum data rate [bit/s] = $2H\cdot log_{2}(V)$

Where $H$ is the bandwidth in $Hz$ and $V$ is the number of symbol values.

This formula indicates that unlimited data rate can be achieved when enough symbol levels are used, but, as we have already seen, that is not possible because of random noise. Shannon's formula takes that into account:

maximum data rate [bit/s] = $H\cdot log_{2}(1 + S/N)$

Where $S$ is the signal strength and $N$ is the noise level.


Phrase generation approaches In generating reports, sometimes there is a need to produce quite involved phrases in one of natural languages given numerical or boolean parameters.

To get a feel of it, it is enough to take a look at convert integers into words or time ago algorithms.

These solutions use (procedural/OO/functional) programming and Turing-complete computations, but the question is, whether there is some declarative approach, or hybrid approach, which can be more generic for this class of algorithms? By hybrid I understand decomposed into preparation phase (calculating or defining all necessary units, tuples and conditions), and phrase generation phase, which works with declarative definitions (some kind of domain-specific language)?

The current approach I see in Open Source projects is like the above-mentioned questions: conditional statements interspersed with string interpolations or concatenations. I guess, there are more optimal ones.

What I am searching for is some right term for the problem. I am sure there is a lot of research on the topic, but I have so far failed to come with good keywords to find suitable theory. This is something in between of constant phrases and arbitrary text generation. Ideally, the declarative part should be something easy for domain experts, like a grammar.

In practice, there is also table-driven approach, but what about theories?

Also found this oldish work A flexible shallow approach to text generation by S. Busemann and H.Horacek, but it goes too fast into too specific cases.

I've found a survey on natural-language generation approaches by Albert Gatt, Emiel Krahmer, 2018. According to that, my question is about linguistic realization. And the paper mentions three most common ones:

human-crafted templates
human-crafted grammar-based systems
statistical approaches

If I remember correctly, there may also be rules-based NLG systems, which may be overlapping with the grammar-based in the above classification.

And I am sure there may be more approaches.


How can i prove this asymptotic comparison? This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:

Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$

Clearly this is correct, because the dominant term ($\sqrt{n}$) is present in both sides. But i wasn't able to give a mathematic explanation why it's correct.

When it comes to instances like this, I prefer to think about conceptually "promoting" and "demoting" lower order terms.

For instance, if we wanted to upper bound:

$$f(n) = 32 + 11 \log_2 n + 5 n + 2 n^2$$

We know (by intuition or limits) that $n^2$ is the fastest growing term here. Thus, we should be able to bound $f(n)$ by $n^2$. By this, I mean we can find some constant $c$ such that $f(n) \leq c n^2$ for all $n \geq n_0$ (where $n_0$ is some initial starting value for $n$ where this inequality holds true). Note, that this is preciesly the definition of Big O.

  Promoting lower order terms of $f(n)$ - Consider we can represent each lower order term by a constant $c_0$ times some function $h_0$ of $n$ (e.g. $c_0 \cdot h_0(n) = 11 \cdot \log_2 n$). For each lower order term, we will promote $h_0(n)$ to the highest order function of $n$, call it $h^*(n)$ and leave the constant the same.

Consider the lower order terms of our example: $\{32,\ 11 \log_2 n,\ 5n\}$ and the highest order term $2 n^2$. The promotions will go as follows:

$$\begin{align*}
32 & \mapsto 32 \cdot n^2\\
11 \cdot \log_2 n & \mapsto 11 \cdot n^2\\
5 \cdot n & \mapsto 5 \cdot n^2
\end{align*}$$

Let's assume $n_0$ is the first value of $n$ for which all lower order functions of $n$ are less than or equal to the highest order function of $n$. In our example we have:

$$\begin{align*}
1 & \leq n^2 & \forall n \geq 1\\
\log_2 n & \leq n^2 & \forall n \geq 1\\
n & \leq n^2 & \forall n \geq 1
\end{align*}$$

Thus we have found our $n_0 = 1$. Now we can replace the lower order terms in $f(n)$ with their promoted counterparts to get:

$$\begin{align*}
f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\
& \leq 32 n^2 + 11 n^2 + 5 n^2 + 2n^2
& = 50 n^2
\end{align*}$$

With this he have found our $c = 50$. Thus we can conclude:

$$f(n) \leq 50 n^2 \quad \forall n \geq 1 \quad \implies f(n) = O(n^2)$$

  For demoting lower order terms we simply remove them from the equation to get:

$$\begin{align*}
f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\
& \geq 2n^2\\
&  = 2n^2
\end{align*}$$

Thus we can conclude:

$$f(n) \geq 2 n^2 \quad \forall n \geq 1 \quad \implies f(n) = \Omega(n^2)$$

Then we clearly get:

$$f(n) = O(n^2) \land f(n) = \Omega(n^2) \implies f(n) = \Theta(n^2)$$

Typically, most of these operations are simple enough to just conclude $f(n) = \Theta(n^2)$ in one fatal sweep, though it does always help to determine $c$ and $n_0$ explicitly when you need to. Clearly, the $c$ we find here is a loose upper bound and you could usually restrict it further if you needed to.

At this point I am assuming you have a summation of functions that are monotone non-decreasing. You must be a bit more careful when you have decreasing lower order terms, but these are usually not a big problem.


Constraint on Universal set of hash functions I was reading hashing from CLRS. In it author says:

  Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be universal if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

So basically in universal set of hash functions, the number of hash functions a finite collection of hash functions is said to be universal if number of hash functions $h$ for which $h(k)=h(l)$ is at most $\frac{\text{number of hash functions}}{\text{size of hash table}}=\frac{|\mathscr{H}|}{m}$

However next the author says:

  In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$.

I didnt get the last part "$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$". How $|\mathscr{H}|=$[$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$]

Let's plug real numbers into the passage:

$|\mathscr{H}|$ = 10;

$m$ (size of hash table) = 100

In the first statement:

$\frac{|\mathscr{H}|}{m}$ = $\frac{10}{100}$ = 0.1 = the maximum number of hash functions that will cause a collision. (Assuming the count of functions in $\mathscr{H}$ can be represented as decimals for sake of argument.)

The important thing to note here is that the chance of selecting a collision causing hash function is: $\frac{0.1}{|\mathscr{H}|}$ = $\frac{0.1}{10}$ = 1%.

In the second statement:

The argument being made is that the chance of collision "is no more than..":

$\frac{1}{m}$ = $\frac{1}{100}$ = 1% = the chance of generating a hash value $h(key)$ from the set {0, 1..., 99}. AKA the chance of selecting a specific value from 100 values.

Conclusion:

So, from our example, a collection of 10 hash functions that map a given universe of keys into the range {0, 1..., 100 - 1} is said to be a universal collection if: by randomly choosing a hash function, the chance of collision between distinct keys is no more than 1%.


Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$ I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\{x\in(a,b), \#_a(x) = 2\#_b(x)\}$, where $x$ is the input string and $\#_a(x),\#_b(x)$ the number that $a$ or $b$ appears in the $x$ string.

That means that the following sequences should all be accepted:

  aab
  aba
  bbaabaaaa
  baabaa
  abbaaa

My problem: I've found examples of PDAs being constructed for $a^nb^n$ and even $a^{2n}b^n$ which is pretty close to what I'm looking for, but these languages all have a predetermined sequence of the $a$s coming first, then the $b$s.

I've been trying for literally hours to build a PDA that circles between how many $a$s and $b$s it has, and how many it still needs, but every attempted solution has been wrong (situations where consequent same letters cause pops on empty stacks, halting the PDA).

Any information or methodical approaches on constructing a PDA out of a language like that? I'm at my wit's end.

GPDA$\to$PDA Approach

See you have got a solution from chat. But the first thing popped my mind is a Generalized_pushdown_automaton(GPDA), which can be constructed pretty straight forward.

GPDA construction

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

$(q_0,a,Z)\to(q_0,aZ)$
$(q_0,b,Z)\to(q_0,AAZ)$
$(q_0,a,a)\to(q_0,aa)$
$(q_0,b,A)\to(q_0,AAA)$
$(q_0,a,A)\to(q_0,\epsilon)$
$(q_0,b,aa)\to(q_0,\epsilon)$
$(q_0,b,aZ)\to(q_0,AZ)$
$(q_0,\epsilon,Z)\to(q_f,\epsilon)$

GPDA$\to$PDA convertion

Using the algorithm provided on Wikipedia, we can convert it to PDA easily. Only 6. and 7. need to convert:

6.1 $(q_0,b,a)\to(p_0,\epsilon)$

6.2 $(p_0,\epsilon,a)\to(q_0,\epsilon)$

7.2 $(p_0,\epsilon,Z)\to(q_0,AZ)$

Resulting PDA is $M=(Q',\Sigma,\Gamma,\delta',q_0,Z,\{q_f\})$ where $Q'=\{q_0,p_0,q_f\}$ and $\delta'=(\delta\setminus\{6,7\})\cup\{6.1,6.2,7.2\}$. The constructed PDA is non-deterministic.

Convert to DPDA

To convert to DPDA, the only affected transitions are 1. 2. and 8 in above rules:

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,p_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

$\mathbf{(q_0,\epsilon,Z)\to(q_f,Z)}$
$(q_0,a,a)\to(q_0,aa)$
$(q_0,b,A)\to(q_0,AAA)$
$(q_0,a,A)\to(q_0,\epsilon)$
$(q_0,b,a)\to(p_0,\epsilon)$
$(p_0,\epsilon,a)\to(q_0,\epsilon)$
$(p_0,\epsilon,Z)\to(q_0,AZ)$
$\mathbf{(q_f,a,Z)\to(q_0,aZ)}$
$\mathbf{(q_f,b,Z)\to(q_0,AAZ)}$


Is there a fast solution for this set reduction problem? Let there be a set $S$ and denote by $P=2^S$ the power set of $S$. We are given a finite subset $L = \{p_0, \ldots, p_{n-1}\}$ of $P$ and we are allowed to transform the set as follows: if two sets $p_i$ and $p_j$ share some elements, i.e. $p_i \cap p_j \neq \emptyset$, remove both $p_i$ and $p_j$ from $L$ but add their union $p_i \cup p_j$ to $L$.

What is the algorithmically fastest way to reach a state where there is no further (or almost no further) transformation of $L$ possible?

One simple way to achieve that goal is to compare all elements with each other and perform a transformation if possible, repeat until no changes are possible.

Pseudo C++-code using std::vector:

vector<Set> L = ...;
int n = L.size();

bool hasChanged = true;
while (hasChanged) {
    hasChanged = false;

    for(int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (!isDisjoint(L[i], L[j])) {
                // remove L[i] and L[j]
                swap(L.back(), L[i]);
                L.pop_back();
                swap(L.back(), L[j]);
                L.pop_back();

                // add their union
                L.push_back(getUnion(L[i], L[j]));

                hasChanged = true;
                i -= 1; // we don't want to skip the swapped element
                break;
            }
        }
    }
}

This algorithm takes $\frac{n^2-n}{2}$ comparisions in the best case and $\sum_{k=1}^n \frac{k^2-k}{2}$ comparions in the worst case. Naturally the number of comparisons needed depends on the ordering of the elements in the vector.

To provide some less abstract context: I have a set of line segments which i want to reduce. So the idea is to connect lines which are "close" to each other. A connected line does not necessarily share start or endpoints with its original lines but it can be connected to other lines in the set. How do I connect all the lines until there is no further improvement possible in the fastest way possible?

This rewriting system is confluent, so if you just repeatedly pick a legal transformation and apply it, over and over again, until  you can't any longer ... you will always end at the same state.

In other words, there is a unique end state from which no further transformations are possible, and you can reach it by any sequence of legal transformations.  Define a state to be a final state if no further transformations are possible from it.  Then there is a unique final state, so you can reach it by following any legal sequence of transformations and continuing until you can't continue any further.  (This will terminate, since each step reduces the size of $L$.  By definition, once you can't continue, you are in a final state.  Since the final state is unique, this terminates at the unique final state.)

You can even find the shortest such sequence, relatively efficiently.  Build an undirected graph with one vertex for each $p_i$, and with an edge $(p_i, p_j)$ if $p_i \cap p_j \ne \emptyset$.  Compute the connected components of this graph.  Then the final state will have one subset per connected component in the graph; it will be a subset containing the union of all of the vertices of the connected component.  You can get to that connected component by repeatedly picking some pair of vertices $p_i,p_j$ that are joined by an edge, merging those two vertices into a new vertex $p'$, and then updating the edges ($p'$ gets an edge to each vertex that had an edge to either $p_i$ or $p_j$; but remove all self-loops).  If there are $n$ vertices originally and $c$ connected components, this will terminate after $n-c+1$ steps.

In fact, looking at it a bit longer, you can discover that any legal sequence of valid transformations that ends at a final state is equally good -- all such sequences have the same length.  You start with $L$ containing $n$ subsets; you end with $L$ containing $c$ subsets; each transformation reduces the length of $L$ by one; so any such sequence must contain exactly $n-c+1$ steps.  All the legal sequences end at the same final state, so all sequences are equally good.

TL;DR: At each step, apply any valid transformation.  Eventually you will terminate.  It doesn't matter which pair of subsets you choose to merge at each step; you'll eventually end at the same ending point, and the total number of steps will be the same regardless of the choices you make at each step.

This is the most wonderful kind of algorithm: at each step, do anything that's not illegal, and you'll eventually end up a winner.  You can't lose!


Proof that class of languages accepted by DPDA by empty stack is not closed under union My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):
$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d : i,j \ge 0 \}$$
So their union would be:
$ L = L_1 \cup L_2 = \{ a^i b^i c^k d : i=j \lor j=k \} $
Then to prove $L$ not even being DCFL (e.g. in similar way as Example 10.1 from "Introduction to Automata Theory, Languages, and Computation" by Hopcroft & Ullman).
Big inconvenience would be the need to include in the proof also the proofs of all other properties (assuming this class is - just as "regular" DCFL - closed under complement etc.)

But I was told that precisely because the question is about DCFL being accepted by empty stack, the proof is actually trivial and could be expressed in just few sentences.

Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences.
Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are prefix-free: if the accepted language contains a string $x$ then it will not contain any string $xy$ with $y\neq \varepsilon$.
Now the language $\{a,aa\}$ is an easy counterexample.


How do we determine how much time a multi-tape DTM saves over a one-tape DTM? Note: This is a part of a homework question

Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}

Then it says "Discuss how much time your machines saves over a one-tape DTM using the same algorithm"
Any hint?

Here's my algorithm:

(1) Cut-and-paste c's to tape 3

(2) Cut-and-paste b's to tape 2

(3) Cross out each triplets, accept if last round cuts all three, reject if there's leftover

Which seems like it has a time complexity of $O(n+n+3n)=O(5n)$
Then how do we determine the time complexity for the one-tape version?

As this is homework, I'll go for the gentle hint approach. Firstly, it's a bit odd to talk about a TM using an algorithm - a TM is an algorithm, so my interpretation of the question is:

Given a multitape TM, you want to produce a single tape TM that does the same job (i.e. has the same language), and you want to know how much slower the single tape version is (in the worst case).

To put it another, hint laden way, how much slower is it to simulate a multitape machine with a single tape machine?

There's a rather important result regarding this (i.e. there's a way to do it that guarantees an upper bound on the slowdown factor), a little searching should get you that at least.


Time units required for Interrupt Cycle I am reading William Stallings Computer Organization & Architecture to understand about control unit & micro-operations.

Stallings explain that interrupt cycle requires 3 time units to complete :

t1 : MBR <- (PC)
t2 : MAR <- Save_Address
     PC <- Routine_Address
t3 : Memory <- (MBR)

t1 : Save the current PC value to MBR

t2 : Save_Address provides the memory location where the value of PC has to be stored. It is saved in MAR.

Routine_Address gives the address for Interrupt Service Routine

t3 : The MBR (which has old value of PC) is stored to memory location (whose address provided by MAR)

But this is how I am thinking, the above operations can be completed in only 2 time units.

t1 : MBR <- (PC)
     MAR <- Save_Address
t2 : PC <- Routine_Address
     Memory <- (MBR)

I checked twice & I find no dependency among micro-operations performed in time unit t1 & t2.

So, is my approach correct ?

Your approach will work.  There are no hard and fast rules in micro-op scheduling.  The number of micro-ops that can be executed in parallel depends on the internal organization of the CPU. Clearly, we cannot reload the program counter (PC) until we save its contents, but there is nothing stopping us from saving its contents on the leading of the clock signal and loading new contents on the trailing edge.


NPC problem with sets Let us have a finite set $S$ and a finite set of its subsets $S_1, S_2 \dots S_k$. For any $S_i$ we have two numbers: $l_i$ and $h_i$. We need to figure out if there is such a subset $T$ of $S$, that for any $i$ we have $l_i \leq |T \cap S_i| \leq h_i$.

Prove that this problem is in NP & NP-complete by reducing 3SAT to it.

I will prove it is NP-hard leaving the proof that it is in NP to you.

Let $\phi = c_1\land c_2\dots\land c_m$ be a 3SAT formula. Define
$$S = \{l \mid l \text { is a literal of  } \phi \}$$
$$S_i = \{l \mid l \text { is a literal of } c_i\}$$

Since each clause has to have at least one literal with TRUE value we have the following constraints
$$l_i=1 \leq |T \cap S_i|\leq 3 = h_i$$
Finally, we have to make sure that $T$ contains no variable $x$ (of $\phi$) and its negation at the same time
$$S_{x} = \{x,\overline{x} \} $$
$$l_x=0\leq |T \cap S_x| \leq 1=h_x$$

So, if $\phi$ indeed has a solution then $T$ consists of those literals whose true-value is TRUE. Then it is trivial that all constraints satisfy since $T$ may not have a variable and its negation at the same time and each clause has at least one TRUE literal.

On the other hand, if we have a set $T$ satisfying the above-described constraints then $\phi$ can be constructed by ORing each literal in $S_i$ (by ORing with arbitrary variables if $|S_i| < 3$) and ANDing all clauses corresponding to $S_i$. This formula is satisfiable since may make each clause TRUE by making true each literal in $S_i$ and since not $x$ and $\overline{x}$ are in $T$.


Program to check whether a string is accepted by an unrestricted grammar How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?

Unfortunately, you cannot.

Nobody can since the membership problem for unrestricted grammar is undecidable. Here is a reference in Wikipedia.

On the other hand, the membership problem for context-sensitive grammar or, what is equivalent, noncontracting grammar is decidable. 1

Just in case it is not clear to you, a collection of decision problems (a.k.a, yes/no questions) is decidable if there is a program which will solve any given one of them correctly within finitely many steps. It is undecidable if there is not such a program.
The existence of undecidable problems could be the best technical backdrop for this story.

You will learn its formal definition in your study of computer science (or you might have). There will be lots of undecidable problems coming to you; so if you suspect one, you should probably wait until you have studied the chapter about undecidability and somewhat more before you raise a similar question. Or you could just search around using the keyword "decidable" or "undecidable"


Turing Completeness + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions? Assume we are working in a Turing-complete, referentially-transparent, higher-order language that supports arbitrary dataflow unification.  Shouldn't it then be possible to construct the following function (using Haskell-like syntax, because that's what I'm most familiar with)?

-- Takes an arbitrary pure function and constructs its inverse.
-- If the passed-in function is recursive, the result is not guaranteed to terminate
invert :: (a -> b) -> b -> a
invert f r = declare a in let r =|= f a in a

(if =|= is the dataflow unification operator).

Is this indeed possible in such a language?  If so, why haven't people leapt at this before?  If not, where did my reasoning go wrong?

Dataflow unification behaves as you expect on first-order data (numbers, booleans, lists, trees, etc.) but can fail for higher-order data such as functions. In general, unifying functions requires using full higher-order unification, which has terrible performance, up to and including frequent failure to terminate (as it must, since otherwise it would solve the halting problem).

Higher-order logic languages such as $\lambda$-Prolog and Curry typically use restricted forms of higher-order unification, to get better efficiency at the price of completeness.


Can properties such as memory usage of a function be expressed in a dependently typed language? Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this be done through dependent typing and effects systems?

Yes, it can.  While conceptually it's not that difficult, it hasn't been studied all that much.  One aspect of the field is cost semantics such as the research done by Guy Blelloch.

In the vein of the video Anton mentioned is Daniellson's work in Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures.  This does indeed use a monad to carry around a cost per operation.  A similar monad, at the semantic level, is used in Denotational cost semantics for functional languages with inductive types.  Here's a 2016 paper doing something similar in Coq, A Coq Library For Internal Verification of Running-Times.

The NuPRL people have also long been interested in doing things like this.  In Expressing Computational Complexity in Contstructive Type Theory, which basically amounts to calculating over a structured operational semantics.  Where it gets a bit more interesting is that you can reflect the language semantics into the language.  The example in the final section, section 12, of Naive Computational Type Theory illustrates and discusses this sort of thing.


Which matrix of Q values is being used here? This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task

In section 2.1, equations (5) and (6), I am wondering which Q values are being used to adjust the weights of the restricted boltzmann machine:

Option 1: the Q values generated by the original MDP

Option 2: the approximate Q values obtained by calculating the (negative of the) free energy of the RBM

Follow up question: When considering states $(s^t, a^t)$ and $(s^{t+1}, a^{t+1})$, how do we determine which values of $a^t$ and $a^{t+1}$ to use? Are these the optimal actions from the original MDP, or are these to be obtained through the alternating Gibbs sampling mentioned later on...(which doesn't make sense, since we would not have weights required for this CD)

Thanks for your help

Reinforcement learning works by bootstrapping, which means that Q values are updated based on previous estimates. Also, MDP's don't generate Q values, just rewards (Q values are long-term estimates of accumulated future rewards). So the answer is option 2: the Q values are obtained by calculating the (negative of the) free energy of the RBM. You use the RBM to calculate the current Q value and use it together with the value from the previous step to update your estimate.
The paper uses the Sarsa algorithm, which means it is on-policy. In other words, it uses only actual performed actions. It means that the values are updated only on the next step $t+1$, where you chose your action $a^{t+1}$. In summary, you use Gibbs sampling to select actions and, on time $t+1$ you update the weights using $s^t, a^t, s^{t+1}$ and $a^{t+1}$.


Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked with $\dagger$

Theorem: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $d[v] = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $\pi[v]$ followed by the edge $(\pi[v], v)$.
$\left[ \delta(s,v) \rightarrow \text{Length of the shortest path from s to v}\\ d[v]\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\pi[v]\rightarrow \text{Predecessor of $v$ in the path from $s$ to $v$ in the BFS}\right]$

Proof:
Assume, for the purpose of contradiction, that some vertex receives a $d$ value not equal to its shortest path distance. Let $v$ be the vertex with minimum $\delta(s, v)$ that receives such an incorrect $d$ value; clearly $v \neq s$. We know $d[v] \geq \delta(s, v)$, and thus we have that $d[v] > \delta(s, v)$. Vertex $v$ must be reachable from $s$, for if it is not, then $\delta(s, v) = \infty \geq d[v]$. Let $u$ be the vertex immediately preceding $v$ on a shortest path from $s$ to $v$, so that $\delta(s, v) = \delta(s, u) + 1$. Because $\delta(s, u) < \delta(s, v)$, and because of how we chose $v$ , we have $d[u] = \delta(s, u)$$^\dagger$. Putting these properties together, we have
$d[v] > \delta(s, v) = \delta(s, u) + 1 = d[u] + 1 $
(The proof then continues, but I do not include the rest here...)

I could not understand the reasoning behind the statement marked with $\dagger$, $\text{"because of how we chose $v$ , we have $d[u] = \delta(s, u)$"}$

It is perhaps more illuminating to reformulate this proof by contradiction as a proof by induction. We prove that $d[v] = \delta(s,v)$ by induction on the latter (the case $\delta(s,v) = \infty$ should be taken care of separately). If $\delta(s,v) = 0$ then $v = s$, and indeed $d[s] = 0$. Now suppose that the result holds for all vertices at distance $i$ from $s$, and consider a vertex $v$ at distance $i+1$ from $s$. Let $u$ be a neighbor of $v$ at distance $i$ from $s$. By induction, $d[u] = \delta(s,u)$, and so once $u$ is processed, $d[v] \leq \delta(s,u) + 1 = \delta(s,v)$. Since $d[v] \geq \delta(s,v)$, it follows that $d[v] = \delta(s,v)$, as needed.
How do the two proofs relate? Let $U$ be the set of vertices such that $d[v] = \delta(s,v)$; clearly $s \in U$. Let $v \neq s$ be an arbitrary vertex reachable from $s$, and let $u$ be a predecessor of $v$, that is, a neighbor of $v$ such that $\delta(s,v) = \delta(s,u) + 1$. The proof shows that if $u \in U$ then also $v \in U$. You can now proceed in two different ways:

Proof by contradiction: choose $v \in U$ minimizing $\delta(s,v)$. By definition, the predecessor of $v$ does lie in $U$, and so we reach a contradiction.
Proof by induction: we show that all vertices reachable from $s$ are in $U$, by induction on their distance from $s$.

The two proofs are equivalent. I prefer the second.


Finding interesting anagrams Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length.  An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ for each $i$.

There might be more than one anagramming for the same pair of strings.  For example, If $a=$`abcab` and $b=$cabab we have $p_1[1,2,3,4,5]\to[4,5,1,2,3]$ and $p_2[1,2,3,4,5] \to [2,5,1,4,3]$, among others.

We'll say that the weight $w(p)$ of an anagramming $p$ is the number of cuts one must make in the first string to get chunks that can be rearranged to obtain the second string. Formally, this the number of values of $i\in[1\ldots n-1]$ for which $p(i)+1\ne p(i+1)$. That is, it is the number of points at which $p$ does not increase by exactly 1.For example, $w(p_1) = 1$ and $w(p_2) = 4$, because $p_1$ cuts 12345 once, into the chunks 123 and 45, and $p_2$ cuts 12345 four times, into five chunks.

Suppose there exists an anagramming for two strings $a$ and $b$. Then at least one  anagramming must have least weight. Let's say this this one is lightest. (There might be multiple lightest anagrammings; I don't care because I am interested only in the weights.)

Question

I want an algorithm which, given two strings for which an anagramming exists, efficiently yields the exact weight of the lightest anagramming of the two strings. It is all right if the algorithm also yields a lightest anagramming, but it need not.

It is a fairly simple matter to generate all anagrammings and weigh them, but there may be many, so I would prefer a method that finds light anagrammings directly.

Motivation

The reason this problem is of interest is as follows.  It is very easy to make the computer search the dictionary and find anagrams, pairs of words that contain exactly the same letters.  But many of the anagrams produced are uninteresting.  For instance, the longest examples to be found in Webster's Second International Dictionary are:

  cholecystoduodenostomy
  duodenocholecystostomy

The problem should be clear: these are uninteresting because they admit a very light anagramming that simply exchanges the cholecysto, duedeno, and stomy sections, for a weight of 2. On the other hand, this much shorter example is much more surprising and interesting:

  coastline
  sectional

Here the lightest anagramming has weight 8.

I have a program that uses this method to locate interesting anagrams, namely those for which all anagrammings are of high weight. But it does this by generating and weighing all possible anagrammings, which is slow.

This problem is known as the “minimum common string partition problem.”  (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.)  Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng [GKZ05].  This means that no polynomial-time algorithm exists unless P=NP.  (Of course, if each letter occurs at most once, then the problem is trivial because there is only one anagramming.)

On the positive side, the same authors [GKZ05] give a polynomial-time 1.1037-approximation algorithm under the same restriction.  (A “1.1037-approximation algorithm” means an algorithm which may not output the correct answer A but is guaranteed to output a value B such that A ≤ B ≤ 1.1037A.)  They also give a linear-time 4-approximation algorithm under the weaker restriction that each letter occurs at most three times in each of the input strings.

[GKZ05] Avraham Goldstein, Petr Kolman, and Jie Zheng.  Minimum common string partition problem: Hardness and approximations.  Electronic Journal of Combinatorics, 12, article R50, 2005.  http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50


Reducing 3SAT to MAX-3SAT I have the following problem:

  Consider the MAX-3-SAT problem: given a Boolean function in
  Conjunctive Normal Form (CNF) determine the maximum number of clauses
  that can be satisfied. Prove that this problem is NP-hard.

I know that I'd have to reduce 3-SAT to MAX-3SAT, but I'm pretty lost on how that would work. The related decision problem I figured would be, given clauses and a number k, is there an assignment satisfying at least k of the clauses?

Hint: You have a 3SAT formula $\varphi$ in CNF with $n$ clauses and a maximal $m \le n$ number of clauses can be satisfied. What happens if $m < n$? And what about $m = n$?


ML functions from polymorphic lists to polymorphic lists I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples:

let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = function [] -> []
                                   | l -> loop_if_not_empty l

What I can't figure out is how to make a function that does something other than return the empty list or loop (without using any library function). Can this be done? Is there a way to return non-empty lists?

Edit: Yes, if I have a function of type 'a -> 'b, then I can make another one, or a function of type 'a list -> 'b list, but what I'm wondering here is how to make the first one.

Well, something known as parametricity tells us that if we consider the pure subset of ML (that is, no infinite recursion, ref and all that weird stuff), there is no way to define a function with this type other than the one returning the empty list.

This all started with Wadler's paper “Theorems for free!”. This paper, basically, tells us two things:

If we consider programming languages that satisfy certain conditions, we can deduce some cool theorems just by looking at the type signature of a polymorphic function (this is called the Parametricity Theorem).
ML (without infinite recursion, ref and all that weird stuff) satisfies those conditions.

From the Parametricity Theorem we know that if we have a function f : 'a list -> 'b list, then for all 'a, 'b, 'c, 'd and for all functions g : 'a -> 'c, h : 'b -> 'd we have:

map h ∘ f = f ∘ map g

(Note, f on the left has type 'a list -> 'b list and f on the right is 'c list -> 'd list.)

We are free to choose whatever g we like, so let 'a = 'c and g = id. Now since map id = id (easy to prove by induction on the definition of map), we have:

map h ∘ f = f

Now let 'b = 'd = bool and h = not. Let's assume for some zs : bool list it happens that f zs ≠ [] : bool list. It is clear that map not ∘ f = f does not hold, because

(map not ∘ f) zs ≠ f zs

If the first element of the list on the right is true, then on the left the first element is false and vice versa!

This means, our assumption is wrong and f zs = []. Are we done? No.

We assumed that 'b is bool. We've shown that when f is invoked with type f : 'a list -> bool list for any 'a, f must always return the empty list. Can it be that when we call f as f : 'a list -> unit list it returns something different? Our intuition tells us that this is nonsense: we just can't write in pure ML a function that always returns the empty list when we want it to give us a list of booleans and might return a non-empty list otherwise! But this is not a proof.

What we want to say is that f is uniform: if it always returns the empty list for bool list, then it has to return the empty list for unit list and, in general, any 'a list. This is exactly what the second point in the bullet list in the beginning of my answer is about.

The paper tells us that in ML f must take related values to related ones. I'm not going into details about relations, it is enough to say that lists are related if and only if they have equal lengths and their elements are pair-wise related (that is, [x_1, x_2, ..., x_m] and [y_1, y_2, ..., y_n] are related if and only if m = n and x_1 is related to y_1 and x_2 is related to y_2 and so on). And the fun part is, in our case, since f is polymorphic, we can define any relation on the elements of lists!

Let's pick any 'a, 'b and look at f : 'a list -> 'b list. Now look at f : 'a list -> bool list; we've already shown that in this case f always returns the empty list. We now postulate that all the elements of 'a are related to themselves (remember, we can choose any relation we want), this implies that any zs : 'a list is related to itself. As we know, f takes related values to related ones, this means that f zs : 'b list is related to f zs : bool list, but the second list has length equal to zero, and since the first one is related to it, it is also empty.

For completeness, I'll mention that there is a section on impact of general recursion (possible non-termination) in the Wadler's original paper, and there is also a paper exploring free theorems in the presence of seq.


Decidable non-context-sensitive languages It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable.

Between these two types are the recursive non-context-sensitive languages. Wikipedia gives one example here:

An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

So the question: What others problems exists that are decidable but yet non-context-sensitive? Is this class of problems the same as decidable EXPSPACE-hard?

CSL is the same as $\mathsf{NSpace}(n)$ (non-deterministic linear space). Any language which is outside $\mathsf{NSpace}(n)$ is not CSL.

To get a feeling of the situation, remember that $SAT \in \mathsf{NSpace}(n)$ and even TQBF.

  What others problems exists that are decidable but yet non-context-sensitive?

The are many problems. Any problem that is complete for a complexity class larger than $\mathsf{PSpace}$ will do (we need $\mathsf{PSpace}$ because problems like TQBF in $\mathsf{NSpace}(n)$ that are complete for $\mathsf{PSpace}$ because a (polynomial time) reduction can blow up the size of an input by a polynomial). Giving an example will mean proving a lowerbound for the complexity class containing the problem and that is very very difficult task. The only major way we know so far to do this is diagonalization which intuitively means that the larger class should be able to simulate the smaller class.

So $\mathsf{ExpSpace\text{-}hard}$ seems a natural place to start to look for natural examples of language which are not CSL.

  Is this class of problems the same as decidable EXPSPACE-hard?

No. By the space hierarchy theorem, there are languages which are in $\mathsf{NSpace}(n^2)$ which are not in $\mathsf{NSpace}(n)$. If you are asking for nice examples, that is going to be difficult because the theorem works using diagonalization and therefore the language it proves to satisfy these conditions is very artificial.

I suggest that you ask a separate question for a natural problem that separates $\mathsf{NSpace}(n^2)$ from $\mathsf{NSpace}(n)$.


Number of submatrices, of a base matrix derived from an array, with a particular sum Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its elements is K.

Example:

$A = \begin{Bmatrix}1&-1\end{Bmatrix}$
$K = 0$

Thus:
$M = \begin{Bmatrix}1 & -1\\-1 & 1\\\end{Bmatrix}$

So, there are 5 submatrices where the sum of its elements is 0:
$ M_{00}...M_{01} = 1 + (-1) = 0$
$ M_{10}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{10} = 1 + (-1) = 0$
$ M_{01}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{11} = (-1) + 1 + (-1) + 1 = 0$

Brute force is obvious and it costs $O(n^4)$, but I'm looking for a less naive solution. The first thing that comes to mind (at least mine) is two pointer algorithm, but it works only when there are no negative members, which is not the case. If it were it would make this question a duplicate of this one.

I believe there is a smarter way to solve this because of the correlation between M and A, but I can't figure out how.

Try writing a small example (e.g., where $N=3$), then pick a submatrix (say, $2 \times 2$) and write an expression for the sum of the elements of that submatrix in terms of the entries of $A$.  By doing some algebraic manipulations, you should be able to get a nice expression for this sum.

This will then let you characterize which submatrices sum to $K$, in terms of the entries of $A$.  Working on this a bit, you should be able to get a $O(N^2)$ time algorithm [assuming a submatrix is defined by a consecutive range of rows and a consecutive range of columns].

Since this is your exercise/programming contest problem, I'll let you work out the details.


A path modification problem in directed graphs We start with a given finite directed graph. It could represent transitive relations such as:

data transfer paths in social networks,
transportation connections, etc.

Let us use the notation

A->B to denote a directed edge from node A to node B and
A=>B to denote a path from A to B.

Example 1: Social networks. An edge A->B can mean: A can send data to B. So if we have edges A->B and B->C  we have a path A=>C and data can be sent from A to C.

Example 2: Rail connections. An edge A->B can mean: there exists a rail connection from A to B. So if we have edges A->B and B->C  we have a path A=>C and there is a rail connection from A to C.

We would like to locally modify the graph, in order to add or remove directed paths (not just edges). For example, we may wish to add or delete data paths or rail connections. We may wish to make it possible or impossible for C to receive data, directly or indirectly, from A. Or we may wish to make it possible or impossible to go by rail from A to C. We may have several (possibly conflicting) requirements such as these.
Local modifications are rarely possible without implying other changes, some of which can be unwanted.

Adding paths.  Adding a path X=>Y, is simple because it is
sufficient to add an edge X->Y. However by doing this we will also
add paths from all Z such that Z=>X to all W such that Y=>W. Some of
these paths may be unwanted. Is the addition of the new path
important enough to justify the addition of some unwanted paths? Or:
how can the new path be added with a minimal effect on the rest of
the graph?
Removing paths. For example, if we want to remove a path A=>C such
as A->B->C we must remove either A->B or B->C. The removal of either
edge may imply the removal of other paths that contains this edge.
Hence the need of removing certain paths may force the removal of
others, some of which can be wanted. Is the removal of the unwanted
path important enough to justify the removal of the others? If there
is a choice of paths to be removed, which ones to remove? Or: how
can a path be removed with a minimal effect on the rest of the
graph?

So in general, locally adding or removing paths can have ripple effects that can involve other paths, possibly the whole graph. After adding some paths, others should perhaps be removed and after removing some, others should perhaps be added. This becomes messy. If several path constraints are present, the problem may be infeasible. This could perhaps be seen as an optimization problem, where we must weigh the relative importance of paths: of those we explicitly want to add or remove and of those whose addition-removal may result.

This seems an interesting practical problem. How can this problem be formulated in a way that may lead to a solution? Has this problem, or similar ones, already been studied? I have found some literature on the problem of adding-removing nodes, but I have not found any on the problem of adding-removing edges. In any case, this problem is different, as we want to add-remove paths.

I am assuming you are using some lists of node pointers at the source nodes for keeping record of outgoing edges and paths.i.e. if you have a source node A which has directed edges towards the nodes B,C and D then you have a list containing pointers to B,C and D which is called $edges$  stored in node A

edges=[B,C,D];

and if some other edges lets say E ,F and G have a directed path towards them then you have a list of paths called $paths$

paths=[E,F,G];

Now let's say you want to delete the paths towards E and F from A then you should remove E and F from paths but still keep it in another list called $forbiddenPaths$.

forbiddenPaths=[];// this list will initially be empty

Here's how the lists will be updated after you have removed E and F from $paths$

edges=[B,C,D];
paths=[G];
forbiddenPaths=[E,F];

This way all you need to do before transmitting data is check if the destination node exists in the $paths$ list.If it does then transmit otherwise don't.You can also keep a $forbiddenEdges$ list in the same manner for avoiding some edges of your choice.


Why are mathematical proofs so hard? I am an electrical engineer and trying to make a transition into machine learning.  I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about mathematical proofs.  I started studying it on my own using the material available on MIT's OCW, while I did grasp the concepts of induction and well ordering etc..
I've been struggling with the exercises for a very long time and it's really frustrating.  I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them).  My problems start when I face an unusual question.  I feel like I am memorizing the proofs rather than learn how to prove.
Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

I feel like i am memorizing the proofs rather than learn how to prove

You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you have to invent a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and never succeed.

I can easily deal with any type of proofs that i saw before ( eg. once i saw the proof of a recurrence question i became pretty good at prooving them). My problems start when i face an unusual question.

That is normal. Any mathematics "proofs" course isn't designed to teach you how to take an arbitrary problem you've never seen before and be able to solve it (since nobody, not even the best mathematics professors can do that). Rather, your learning goals are

Learn how to "read" proofs and judge their correctness

Learn how to "write" down a proof in the right mathematical language

Learn about known proof "techniques" and how to apply them

If you are working on a new, unknown problem, it is normal that you might not be able to solve it. However, knowing and having memorized other proof techniques may help you. Often proofs involve combining a new idea with existing known proof techniques. The more, and the more varied the proofs you already know are, the better your chance of being able to solve the given problem.
You are on the right track. You should simply keep studying proof techniques. The exercises you are doing are good. Don't worry if you get stuck. As you get more experienced and your "toolbox" of techniques grows, you will be able to solve exercises that are less "alike" the previous ones you have seen.


Bayes theorem probaility doesn't make sense I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following:

my calculations were:

$$P(B/A) = 0.8\times A$$
$$P(B) = (Bx*0,55)+((1-Bx)*(0,55))$$
$$P(A/B) = (Ax*Bx)/Cx$$

The probability gets above 1. What am I doing wrong?

The problem is your data! For example, the last row shows that $\mathbb{P}(A) = 1$ and $\mathbb{P}(B|A) = 0.8$. If $\mathbb{P}(A) = 1$ means $A$ is equivalent to all possiblities of event world. Hence, $\mathbb{P}(B|A)$ couldn't be anything except 1.


Can there be a perfect chess algorithm? Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game. An algorithm that has all the possible paths that opponent can take at any given moment depending on the players moves. Can there ever be a perfect chess algorithm that will never lose? Or maybe an algorithm that will always win?
I mean in theory someone who can predict all the possible moves must be able to find a way to defeat each and every one of them or simply choose a different path if a certain one will effeminately lead him to defeat.....

edit--
What my question really is. Let's say we have the computing power for a perfect algorithm that can play optimally. What happens when the opponent plays with the same optimal algorithm? That also will apply in all 2 player games with finite number (very large or not) of moves. Can there ever be an optimal algorithm that always wins?

Personal definition: An optimal algorithm is a perfect algorithm that always wins... (not one that never loses, but one that always wins

First of all, I believe that chess algorithms look more than 2 plies down, although they don't consider all different possibilities; pruning the search tree is very important to avoid the combinatorial explosion in the number of possible moves.

For a game like chess, there are three possibilities as to the identity of the winner: either player 1 has a winning strategy, or player 2 has a winning strategy, or both players draw under optimal play. It is not known which is the case for the game of chess. However, since chess is a finite game, there is a computer algorithm, consisting of a very large table, which plays chess optimally.

Of course, such an algorithm wouldn't be practical. But for some simpler games, the "value" of the game (which player wins, if any) has been determined, and an optimal algorithm has been devised. Such a game is known as a solved game.

The mathematical subject that deals with (what are known as) combinatorial games is combinatorial game theory. Mathematicians have developed a recursive method to determine the value of a game given the graph of the game, which includes all the allowed positions and moves. You should be able to find a description of this algorithm in the Wikipedia entry or any lecture notes on the subject.


When is the concatenation of two regular languages unambiguous? Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous otherwise. (I don't know if there's an established term for this property—hard thing to search for!) As a trivial example, the concatenation of $\{\varepsilon, \mathrm{a}\}$ with itself is ambiguous ($w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$), but the concatenation of $\{\mathrm{a}\}$ with itself is unambiguous.

Is there an algorithm for deciding whether the concatenation of two regular languages is unambiguous?

Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by joining DFAs for $A$ and $B$ with $\epsilon$ transitions), ensuring that the switch from $A$ to $B$ happens at two different points.


Are LR(k) languages and DCFLs equivalent? In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ (denoted as LR(k) languages) is the set of deterministic context-free languages (denoted as DCFL).

My question is also about the relation of those two sets, but in the broader field of all context-free languages. Specifically, are LR(k) languages and DCFLs equivalent? And, in which book can I find a proof?

For now, I just have some surrounding facts as followed. Also in the book, the author proved that LR(0) languages strictly belong to DCFLs, and LR(k) languages belong to DCFLs for all $k \in \mathbb{N} \setminus \{0\}$. In addition, it's obvious that LR(a) languages belong to LR(b) languages for all $0 \le a < b$. Recently, I've got an unchecked fact from here: LR(1) languages and DCFLs are equivalent.

According to Wikipedia:

For every fixed $k \geq 1$: A language has an LR($k$) grammar iff it is DCFL.
A language has an LR(0) grammar iff it is DCFL and has the prefix property (no word is a prefix of another word).

The first property is proved in Knuth's original paper, in Section V on page 628.


Is the shadow ray in a Whitted ray tracer occluded by transparent objects? In a Whitted ray tracer, each ray-object intersection spawns a transmitted ray (if the object was translucent), a reflected ray and a shadow ray. The shadow ray contributes the direct lighting component.

But what happens if the shadow ray intersects a transparent object? Is the direct lighting component ignored? How will diffuse objects submerged in water be lit if they don't get any direct light contributions from the shadow ray?

You should first refer to Rendering Equation. It is the general equation to describe the physically transmitting of light in the view of computer science.

Whitted model is just an approximation of the surface integration of the Rendering Equation. It only calculates three light rays(shadow ray, reflected ray, and refracted ray). In a more sophisticated ray tracer, you should use Monte-Carlo ray tracing, where at every intersection point on the object, you will use thousands of rays sampling according to BRDF. Such backward algorithms actually work not good at caustic scene, which is the scene you say. You can use Photon Mapping plus Monte-Carlo Ray Tracing to get a better visualization.

If you just want to use Whitted model, you can multiply the lighting of shadow ray by a factor defined by the occluded transparent object.


How to evaluate dynamical conditioning/pseudo code I am having a hard time even to formulate my question, so here it is:

I have an application that the user can go in and define on a webpage the logic one wants to evaluate for the student to comply with:

  Student must take classes (MATH111 OR (MATH101 AND MATH103))

I have an array of all its enrolled classes like:

  [MATH101,MATH102,MATH123,MATH444]

How do I evaluate my array on that expression to check if the students satisfies the AND/OR clause?

First, your terminology is unusual. I wouldn't speak about "evaluating an array on an expression", but rather about "evaluating an expression using a variable assignment". Your array is, essentially, a variable assignment stating which boolean variables are true and which are false.

You can represent the expression as a syntax tree, having AND/OR internal nodes, and variable names MATH101 as leaves.

Then, you can evaluate the expression simply visiting the tree. In pseudocode:

boolean function eval(tree, array):

    if tree is a leaf X:
       return the boolean answering (X in array?)
    else if tree is OR(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 || b2)
    else tree must be AND(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 && b2)

If you want, you can even implement short-circuit evaluation to save some time. If your expressions are short it won't make any difference w.r.t. performance, though.


NP-Complete problem proof I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I need help with to understand how to prove it's NP-complete. Any help will be much appreciated!

[Background] A directed graph is consisting of people, with an edge from person A to person B if person A is a follower of person B. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself.

The answer of the algorithm is YES if there exists a set S of at most k people reaching at least m people, and NO otherwise.

Prove that this is a NP-complete problem by reducing a known NP-hard problem.

So the first step is to prove that the problem is a NP problem and if I understand correctly I can prove that by finding a cefrtificate that is proved as a solution of the probem in polynomial time. However, I have problems in picking a known NP-hard problem and reducing.

Consider an instance $G=(V,E)$ of vertex cover with $n=|V|$ and $m=|E|$, and build a directed graph $G' = (V', E')$ in which:

$V' = V \cup ( E \times \{0, 1, \dots, n\} )$.
For each $e = (u,v) \in E$, $E'$ contains all edges $(u,e')$ and $(v,e')$ for $e' \in \{e\} \times \{0, 1, \dots, n\}$.

Claim: If there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$, then there is a vertex cover of size at most $k$ in $G$.

Proof:
The existence of a set a set of $k$ observers that reaches at least $(n+1)m$ people in $G'$
implies the existence of a set $S \subseteq V$ of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

For every edge $e=(u,v) \in E$,  $\{u,v\} \cap S \neq \emptyset$.
Indeed, if $\{u,v\} \cap S = \emptyset$, then none of the vertices in $e \times \{0, \dots, n\}$ is reached by $S$ in $G'$, showing that $S$ reaches at most $(n+1)m+n - (n+1) = (n+1)m-1$ people in $G'$.
Therefore $S$ is a vertex cover for $G$. $\square$

Claim: If there is a vertex cover $C$ of size at most $k$ in $G$, then there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

Proof:
For each edge $e = (u,v) \in E$, let $x \in \{u,v\} \cap S$. All vertices $\{e\} \times \{0, \dots, n\}$ in $G'$ are reached by $x$ and hence by $C$.
Therefore $C$ reaches at least $m \cdot (n+1)$ people in $G$. $\square$

This shows that your problem is NP-hard.


Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$ What is the asymptotic rate of growth of the following recurrence relation?
$$
f(x) = \begin{cases}
8f(x/2) + Θ(1) & \text{ if } x^2 > M, \\
M &  \text{ if } x^2 \leq M.
\end{cases}
$$
Here $M$ is a constant.
I'm not sure how to do it with the condition on $x^2$.

The case $x^2 \le M$ has no effect on the asymptotic growth rate of $f$ since it is essentially telling you that $f(x) = \Theta(1)$ whenever $x$ is (at most) a constant.
Then you can use standard methods (e.g., the Master theorem) to show that $f(x) = \Theta(x^3)$.
Perhaps the following transformation will make this more evident.
Define $g(x) = \frac{f(\sqrt{M}x)}{M}$, then:
$$
\begin{align*}
g(x) &= \frac{f(\sqrt{M}x)}{M} = \begin{cases} \frac{8}{M} f(\sqrt{M}x/2) + \Theta(1) & \mbox{if }Mx^2 > M \\
1 & \mbox{if } Mx^2 \le M
\end{cases} \\
&=
\begin{cases} 8g(x/2) + \Theta(1) & \mbox{if }x > 1 \\
1 & \mbox{if } x \le 1
\end{cases}.
\end{align*}
$$
Since $g(x) = \Theta(x^3)$, you have $f(x) = Mg(\frac{x}{\sqrt{M}}) = \Theta(M \frac{x^3}{M^{3/2}} ) = \Theta(x^3)$.


Whether equivalence of different types of automata is of P-type? I came across following problem:

  Which of the following problems is/are P-problems?
  (I) Equivalence of DFA's
  (II) Equivalence of NFA
  (III) Equivalence of regular expressions

Now I know I there exist neat algorithm to find whether given two DFAs are equivalent or not. So (I) must be P-problem. I am doubtful about (II) and (III). There is a procedure to convert every NFA to DFA. So to check whether equivalence of two NFAs, we can first covert them into DFAs and then check their equivalence in P-time. But seems that we cannot convert NFA to DFA in P-time, hence equivalence of NFA seems not a P-problem. Same for (III). Am I correct with this?

The short answer to your question is that 1 is in P, and for 2 and 3 we don't know, but we strongly suspect that they are not in P.

In more detail, as you point out, checking whether two DFAs are equivalent can be done in P (by observing that DFAs are closed under complementation and intersection, and that $A\subseteq B$ is equivalent to $A\cap \overline{B}=\emptyset$).

As for checking equivalence of NFAs, we know that the equivalence problem is PSPACE-complete (by a simple reduction from universality of NFAs). This means that if the problem was in P, we would get P=PSPACE, which would be a huge and unlikely surprise.

Same goes for checking equivalence of regular expressions - the problem is PSPACE-complete. This post has more details on this


Why every finite language is polynomial? I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$

Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in constant time.


Is “A -> aAA” convertible to regular grammar? I have a simple grammar as below and wonder if it is convertible to regular grammar?
If yes, what is the conversion sequence? If no, how can we prove it?
S -> A
A -> aAA | b | c

In which S is the start symbol; A is non-terminal; a b c are terminals.
Any help or suggestion is appreciated.

You can prove inductively that any word $w$ generated by your grammar satisfies $$\#_b(w) + \#_c(w) = \#_a(w) + 1.$$
Also, you can prove inductively that for every $n$, your grammar generates a word having $a^n$ as a prefix.
You can now use the pumping lemma to show that the language generated by your grammar isn't regular.
Variant: intersect the language generated by your grammar with $a^*b^*$ to get an explicit language which is not regular.


How do i tell if a grammar is regular or not? I know that a regular grammar has a definition

$$\begin{align}S &\to aS\\
S &\to \lambda
\end{align}$$

But I dont really know how to apply this information to check whether or not a grammar is regular...

So for example I have a grammar
$$\begin{align}S &\to aSbSb\\
S &\to \lambda
\end{align}$$

If I compare it to the definition of a regular grammar this is not a regular grammar right? Which also means that I can't turn this into a regex.

Also could you please give me an example of a regular grammar and a non-regular grammar hopefully that will solidify my understanding.

It's important to distinguish between regular grammars and regular languages.

Your first grammar is regular.

A regular grammar is either a right-regular grammar or a left-regular grammar. In a right-regular grammar, every production's right-hand side has at most one non-terminal, and that non-terminal is the last symbol in the right-hand side. A left-regular grammar is the same except that all the non-terminals are at the beginning of their respective right-hand sides.

As you observe, your second grammar is not a regular grammar, since there is a right-hand side with more than one non-terminal.

A regular language is a language for which a regular grammar exists. That's a much trickier criterion, since the fact that a particular grammar is not regular does not in any way prove anything about the regularity of the language generated by that grammar. The language might or might not be regular, and there is no algorithm which will even tell you for sure.

So your statement "Which also means that I can't turn this into a regex." does not follow. As it happens, your second grammar does not generate a regular language, but many non-regular grammars do recognise regular languages. Here's a simple example:

$$\begin{align}S &\to aS\\
S &\to Sb\\
S &\to \lambda
\end{align}$$

That grammar generates the language $a^*b^*$, which is certainly a regular language. But this particular grammar is not regular because one production is left recursive and the other production is right recursive; in a regular grammar, either all productions with a non-terminal are left-regular, or all productions with a non-terminal are right-regular.


Multiple production rules for expressions of the same type? I often see syntax like

expression = term | expression, "+" , term;
term       = factor | term, "*" , factor;
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z";

You see, all the rules produce an arithmetic value. Each can replace the other. Why not just declare

aexpr = var | num | (expr + expr) | expr * expr;

?

Certainly I need different production for expression of different type

statements = "if (" bexpr ") body | "while (" bexpr ")" body | a_variable "=" aexpr
bexpr = (bexpr "|" bexpr) | bexpr "&" bexpr | aexpr ">" aexpr

Here, I introduce a new production rule (a line per rule) only when I get a new type of expression and see no reason to split them.

I just started to generate random sentences and see that expressions are naturally grouped according their result type (e.g. arithmetic and boolean are different) and that is all. If you need an arithmetic expression, you draw (rewrite) it from arigthmetic pool, if boolean form the boolean pool. Why to split the pools into further groups?

In one word - ambiguity.

Sometime you don't want your grammar to be ambiugous.

For example, for parsing. Ambigous grammar can't have a $LR(K)$ grammar (you can think of ambiguity as non determinism). $LR(K)$ parser handle determinstic grammars.

Example for the ambiguity of your grammar:

The sentence a * b + c can be derived in two different ways.


Effiecient Repeat Evaluation of Large Multivariable Expressions I am working with a professor to implement an optimization algorithm for determining the maximum and minimum of large (100+ variable) multi-variable expressions (not restricted to polynomials). Part of this process involves picking random values for all variables and then evaluating the expression for near "neighbors" (slight variations in all sub-sets of the variables).

Simplified Example:

f(x,y,z) = x^2 + sin(y/x)/log2(3z)

Start at random point (1,1,1)
Test all neighbors by altering each variable by +/- 0.1:

{1,1,1.1}, {1,1.1,1}, {1, 1.1, 1.1}, {1.1,1,1}, {1.1,1,1.1}, {1.1,1.1,1], ...

Over the course of the optimization the same expression will be evaluated many millions of times. It seems like there must be an efficient way to prevent reevaluating portions of the expression that have already be evaluated, or at least recently evaluated. I am struggling to come up with an efficient way of doing this. I understand that computers are smoking fast at math calculations so maybe attempting this optimization is unwarranted even with large expression size, however expression evaluation is the bottleneck in the process at the moment. Thanks for you time and thoughts on this!

In symbolic computation, hash consing is a technique that consists of systematically remembering the result of function calls in a cache. The cache is indexed by functions and their parameters. Before performing an operation, you look up the call in the cache, and if you find it, you don't perform the function call. Function calls include data constructors, so there is only a single copy of any data structure in memory, and data structures can be compared by physical address. If the computation is highly repetitive, involving many identical parts, this can be a huge performance and memory benefit as it removes any redundancy in computation and memory. If the computation involves little repetition then it's just wasted time doing failed cache lookups and wasted memory for a cache that isn't used.

The same technique can be applied to numerical computations: store all intermediate results in a cache indexed by function calls. I don't know how effective it could be in practice.

As floating point is involved, you need to decide what it means for values to be equal. The most straightforward approach is to use floating point equality; assuming consistent compilation, the same mathematical operation on the same parameters always yields the same result, but you will miss equalities resulting from obtaining the same result in two different ways that are mathematically equivalent (e.g. you may not get the same result for f(x,y) and f(y,x) even if f is mathematically symmetric).


Doubt regarding Chomsky Hierarchy, CFG and CSG I was following a discussion on a website, where a fellow scholar claims that
this grammar

  S→ aAa | bAb | ϵ

  A→aA | bA |ϵ

is not CSG, so it should also NOT be a CFG. But this grammar properly satisfies the rules of CFG according me, on the other hand it fails to satisfy the conditions of CSG, which states that--

  In addition, a rule of the form

S → λ

  where λ represents the empty string and S does not appear on the
  right-hand side of any rule is permitted

So the given grammar is definitely not in CSG. But According to chomsky hierarchy

A CFG should be contained in CSG, so why this rule is NOT being satisfied for this case?

Note that the Chomsky Hierarchy is nowsadays considered as a hierarchy of language families. For each of the levels we both have suitable grammars and automata to generate and accept the languages in the family. Usually there is a relation between the devices for the different levels, but in some cases we have to be careful about the details.

You are right. The given grammar is context-free, but it is not context-sensitive. The reason is that with CSG we have to restrict the possibility for variables to generate the empty string. Technically the reason for this is that the context-sensitive languages are not closed uner erasing (deleting some letters).

So, any CFG that does not have $\varepsilon$-rules is also a CSG. Usually a CSG is not allowed to have $\epsilon$-rules. Of course that would mean that CSL do not contain the empty string. Well, the empty string can be handles separately if we need it. The same is true for, say, CFG in Chomsky normal form. Strict ChNF does not allow the empty string, but that is not a real restriction. Either we deal with the language without $\varepsilon$, or we have some complicated formulation that will allow generating $\varepsilon$ only in the first step of the derivation.


Show that the union of Θ and o is not O Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$

I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would have to just show that $o(n \log n) \neq O(n \log n) $  Which would be easier I think. But I don't know how to go about this formally..

An obvious function is
$$
f(n) = \begin{cases}
n \log n & \text{if $n$ is even}, \\
0 & \text{if $n$ is odd}.
\end{cases}
$$

It's in $O (n \log n)$, it's not in $o (n \log n)$ and not in $\Theta(n \log n)$.

By the way: Every function in $\Theta(f(n)))$ is in $O(f(n))$, just take the larger constant from the $\Theta$ definition. And every function in $o(f(n))$ is also in $O(f(n))$, choose $c = 1$ and make $n$ large enough. But not the other way around.

$O(f(n))$ contains functions that have infinitely many values between $c_1 f(n)$ and $c_2 f(n)$, but also infinitely many small values. So a function $g(n) = f(n)$ for infinitely many $n$, and $g(n) = 0$ for infinitely many $n$ where $f(n) \ne 0$ is in $O (f(n))$, but not in $\Theta(f(n))$ and not in $o (f(n))$.


Uniformly Random Nested Subset Pairs Main Question

We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example

A B C D E F
1 0 0 1 0 1
1 0 0 0 0 1

is a nested subset, where the first mask tells us inclusion in the first set and the second mask tells us inclusion in the first. In this case the first set is {A,D,F} and its subset is {A,F}. I am trying to uniformly generate such subset pairs.

Some Thoughts

One could try naively to generate two random masks, use the first for the union, then the second for the intersection where it overlaps. However, this would generate subsets uniform in the initial subset, and not the pair.

Mathematically speaking this can be done by weighting each mask by the number of possible subsets it has (2^n where n is the size of the subset), randomly drawing a subset, then randomly drawing an intersection from it. However this is very challenging/inefficient to implement in practice

My first idea was to find some (efficient) hash function from integers into subset pairs, however I have not had much success with this.  I am wondering if there is a superior way to do this. I don't need code (I don't have implementation issues); I am looking a conceptual approach. Any advice?

For the sake of simplicity, I will assume that: 1) empty sets are allowed, 2) we count a set as a subset of itself (i.e.: both the big set and small set can represent the same set). If these assumptions don't hold, the math gets a little messier but the basic principles still hold.

First, we observe that there are $2^i{n\choose i}$ pairs of subsets where the bigger subset has cardinality $i$ and that there are a total of $\sum_i 2^i{n\choose i} = 3^n$ such pairs.

We proceed as follows:

1) We choose $k$ (between $0$ and $n$), the size of the bigger subset. This will not be a uniformly random choice but our initial observation lets us know the correct probabilities, i.e.: $P(k = i) = 2^i{n\choose i} / 3^n$.

2) We choose uniformly among the ${n \choose k}$ subsets of cardinality $k$ to be our bigger subset. Reservoir sampling should do the trick.

3) We choose uniformly among the $2^k$ subsets of the bigger subset to be the smaller subset. Simply choosing a random number from $0$ to $2^k-1$ and using the natural correspondence between sets and binary representations of integers should suffice.

EDITED TO ADD:

I just realized an even slicker way to do this but it depends heavily on the first two assumptions I stated. Unlike my originally provided method, I don't see an obvious way to adapt it if either of those assumptions fails to hold.

Recall that we deduced that the total number of eligible subset pairs was $3^n$. We can identify a bijection between each subset pair and $\{0,1,2\}^n$, i.e.: vectors of length $n$ with entries in $\{0,1,2\}$. Let $v$ be such a vector. If the $i^{th}$ entry of $v$ is $2$, then put $i$ in both sets; if it's $1$, then put it only in the bigger set; if it's $0$, ignore it.

So, the problem reduces to generating a number between $0$ and $3^n-1$ and examining its ternary representation.


Number of rounds in interactive proofs - Arora & Barak In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the prover sending a message. In other sources on the matter, it seems to me that a round consists of both the verifier and the prover sending a message. Could someone clarify which of the definitions is the one that is usually used?

It could be that both definitions are used by different authors. Whenever you use the concept of rounds, make sure to tell the reader what you mean by a round. In any case, the two concepts differ by a factor of $2$.


Prove a language $A_{PTM}$ is not BPP-Complete I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer science professors about the problem and he proposed the following proof sketch:

Proof (sketch):

We know $A_{TM} \le_m A_{PTM}$.

Construct a decider $D$ that given a Probabilistic Turing Machine $M$ and a string $x$, $D$ accepts if $M$ accepts $x$, and rejects otherwise. As $A_{TM} \le_m A_{PTM}$, a solution to $A_{PTM}$ would yield a solution to $A_{TM}$. However, $A_{TM}$ is not decidable, so therefore, $D$ cannot exist.

End of Proof

Where I am confused is how does this show $A_{PTM}$ is not BPP-Complete? As an acceptance problem, I would think $A_{PTM}$ is BPP-Hard, but I don't see how this shows it is not in BPP.

To show that a language is not BPP-complete, it suffices to do one of the following:

Show that the language is not in BPP.
Show that the language is not BPP-hard.

Your language seems to be undecidable, and so in particular, not in BPP.


Improving copy cost of a bit array by using big-endian Patricia Trees (or similar) I have an algorithm that on each iteration generates a copy of an object containing a bit array and modifies it (the modification is limited to just 1 element per copy)

While doing the time analysis I cannot neglect the copy cost as this bit array is encoding information about the input set, so for a very large number of elements I have to account for it..

I has been said that effective data structures exists, like big-endian Patricia trees, that can achieve a $O(log(n))$ when copying an instance, and I confirmed there are implementations using them like Data.IntSet from haskell that provides a very good TC for certain operations that I can use to refactor this part of the algorithm ($O(min(n,W))$ W=word size)

I have seen another post in Stack Exchange explaining that is possible to achieve a similar copy cost with AVL persitent trees.

I'm looking for confirmation about this or any other specialized structure that can achieve the reported time complexity for copy.

Yes, you can use standard techniques for persistent data structures to make a version of Patricia trees that has the properties you want.  See also What classes of data structures can be made persistent? and persistent-data-structure on this site.


Formal definition of loss surface of multi-layered networks Let $\mathcal{L}$ be a loss function associated with a multi-layered neural network.  So it seems almost everyone in AI/ML community is interested in  the Hessian $H=\partial^2 \mathcal{L}$ of $\mathcal{L}$. So if you read [1] on page 193 the left colum you find the following text

"An important question concerns the distribution of critical points (maxima, minima, and saddle points) of such functions. Results from random matrix the- ory applied to spherical spin glasses have shown that these functions have a combinatorially large number of saddle points. Loss surfaces for large neural nets have many local minima that are essentially equivalent from the point of view of the test error, and these minima tend to be highly degenerate, with many eigenvalues of the Hessian near zero.
"
Could anyone in the community shed some light on how formally the authors define (perhaps assuming some accepted definition in the community) the loss surface associated with either neural network or the loss function of the neural network?

My guess is that it is the level set of the loss function attaining one of its critical values (of the loss function). I would appreciate if someone would share any knowledge on the nature of the formal definition of the loss surface or any accepted common knowledge definition.
Many thanks.

[1] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192–204, 2015.

In the empirical risk minimization framework, we let $w$ denote the weights of the neural network (which we are trying to learn) and define $L(w)$ to be the total loss (across the entire training set) if you use weights $w$.  Then, the optimization problem is to find $w$ that minimizes $L(w)$.

This is the function that the quote is talking about.

"Loss surface" refers to the graph of this function.  $L$ is multidimensional so we obtain a graph in some high-dimensional space.


Find minimum set of vertices that are reachable from all other vertices I have a DAG and I wish to find the minimal set of vertices that have a path to all other vertices.

My solution was to simply find all the vertices that their incoming degree is 0.
However, if there are two vertices in the DAG that have an indegree of 0 and that point to a common vertex then one of the two vertices is surplus.

Any help appreciated.

Your algorithm is correct, provided that the following is a formal definition of your problem:

  Given a DAG $D = (V, A)$, find a minimum set $C \subseteq V$ such that for every vertex $v \in V$, either $v \in C$ or there exists a vertex $c \in C$ such that $v$ is reachable from $c$.

Let's call a vertex with indegree 0 a source and any vertex set that satisfies the reachability part a cover.

Claim.  The optimal solution is $C = \{v \in V \mid v \text{ is a source}\}$.

Claim 1.  $C$ is a solution.  Trivial since $D$ is a DAG.

Claim 2.  Every vertex $c \in C$ is in every cover.  Since it has indegree 0 it cannot be reached by any other vertex.


3-SAT with negative-literals in each clause Does a 3-SAT problem, where in each clause there is at least a negative-literal, always has a solution?

After looking at it, seems to me that the answer is yes, but maybe there is something I am not seeing.

Consider the all-zeroes assignment, $x_1=x_2=\cdots=x_n=0$.

What if all clauses have a positive literal?


Book for algorithms beyond Cormen I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations?

NOTE: I asked this on stackoverflow but wasn't all too happy with the answer.

NOTE: Looking at most of the comments I think ideally I would like to find a book that would cover the material of the the 787 course in this course description.

As others have noted, books about (advanced) algorithms are best selected by topic. A good but heavy-weight general reference with rigorous analysis is probably The Art of Computer Programming by Knuth.

As for analysis techniques, you may be interested in An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, and Algorithmic Combinatorics by Flajolet and Sedgewick for more theory in the same direction.

For approaches on tackling hard problems, see Algorithmics for Hard Problems by Hromkovič.


Bellman Ford Source & Negative Cycles I’m having some troubles with Bellman Ford Algorithm in the following exercise
My guess is that at the end the algorithm should detect the negative cycle BD DF FG GB since B is decreasing at Vth (i.e. 7th) iteration. However changing the distance of the source does not make much sense to me. Is the source to be considered at fixed distance 0 or it can change as well as all the other vertices? Or is it correct to assume, as I did, that the algorithm will detect a negative cycle in the end?
Moreover, assuming to proceed with the computations, it is not clear to me the order I should follow. Being Vertex A not connected, should I go on relaxing from C (I guess not since it is not directly connected to B)? Or should I go on from D, which is the first vertex in alphabetic order directly connected to B?
Thank you

The source distance does not need to be treated specially. It can change like any other vertex. In this scenario, it'll be updated to -1 by the end of the fourth round. The weights into and out of B will never become quiescent: either B's distance will be more than 2 greater than G's distance, or (say) A's distance will be more than 5 greater than B's distance. So the cycle will still be detected.
Now, if you ever find yourself reducing the source distance below zero, you immediately know that there's a negative cost cycle, and can terminate early. But there's no need to do so for the algorithm to work.


Building heaps and heapsort using linked list I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.

One of the answers here (https://stackoverflow.com/a/14584517/5841727) says that heap sort can be done in O(nlogn) using linked list which is same as with arrays.

For building a heap, I think that heapify operation would cost  O(n) time in linked list and we would need (n/2) heapify operations leading to time complexity of O(n^2). Is it correct?

Also, can someone please tell how to achieve O(nlogn) complexity (for heap sort ) using linked list ?

doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list.
merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.


Rotations in splay trees I am having some difficulties splaying the element 4 to the root.
Considering the following splay tree.

0
 \
  1
   \
    2
     \
      3
       \
        4

Could anyone show me the steps how to get the 4 to the root?

Just follow the algorithm. First you have to do a zag-zag-rotation, which gives you

0
 \
  1
   \
    4
   /
  3
 /
2

Then you have to do another zag-zag-rotation and you obtain as the result of splay(4) the tree

    4
   /
  1
 / \
0   3
   /
  2