Is the following intuition valid for understanding $k$-wise independent hash functions? I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable working with these families of hash functions as black boxes (that is, I understand the relevant definitions and how the algorithms and data structures rely on those definitions), but when I look at specific examples of families of $k$-wise independent families of hash functions, I often have a really hard time understanding why they work. I assume that a lot of this is due to the fact that I don't have a super solid grasp of number theory or finite fields.

One trend I've noticed is that to form a $k$-wise independent family of hash functions whose domain and codomain is a set $\{0, 1, 2, 3, \dots, p-1 \}$, where $p$ is a prime, you can choose a random $(k+1)$-degree polynomial by choosing $k+1$ random elements out of $\{0, 1, 2, \dots, p-1\}$, then to have the hash function be "evaluate the polynomial on the given input value." (I assume that this is equivalent to choosing a random $(k+1)$-degree polynomial over $\mathbb{F}_p$, though I may be mistaken about this.)

My intuition behind why this approach works is that, just like a degree-$(k+1)$ polynomial over the reals cannot be determined by $k$ or fewer points, a degree-$(k+1)$ polynomial over $\mathbb{F}_p$ cannot be determined by $k$ or fewer points. As a result, these polynomials work well as hash functions because, with random coefficients, if you see $k-1$ outputs of the hash function, it's impossible to predict any $k$th output of the hash function better than a random guess because you can't determine what the polynomial is.

My questions are the following:

Is this a correct intuition for why these families of hash functions work correctly?
I teach undergraduate courses on algorithms and data structures that do not have number theory or abstract algebra as prerequisites. If this intuition is correct, would it be inappropriate / misleading to use this intuition to explain these families of hash functions?

Thanks!

Your intuition is exactly right.  Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$.  The reason why it works is exactly the interpolation theorem for finite fields.

$k$-wise independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as correlations between up to $k$ different hash values appear"; and the interpolation theorem then ensures that this level of perfection is achieved for the construction you outline.

It can be a bit tricky to explain this intuition to students who aren't familiar with anything from number theory, group theory, or finite fields.  One approach is to explain the intuition of the interpolation theorem over the real numbers, and then just give a statement that "something similar happens when you work modulo $p$ a prime", without trying to prove it.  That's not perfect, though.

Another approach is to not try to teach this topic, at this point in their education.  While I was taught universal hashing in my undergraduate algorithms course, I've gradually come to the opinion that the topic is better to omit from the course: it's not important enough, and it relies too much on mathematical background and intuition that students don't have.  Why isn't it important?  Well, most students won't become theorists.  For students who will eventually become practitioners, they probably won't ever need universal hash functions.  Instead, ordinary hash functions are often so good that as a first approximation you can just model them as if they were universal (as a heuristic), without making a big deal about it, and do your probability calculations from there.  This is enough to let you analyze uses of hash functions in a way that's accurate enough for practical/engineering purposes.  And, given that, it's not clear that we need to show them constructions that provably achieve something that ordinary hash functions already heuristically achieve pretty well.  That's just a personal opinion, though.


Is it decidable if a TM takes at least 2016 steps on all inputs? $$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$

Is this language decidable?

I will write my way of understanding it. Please answer it in the way I understand & tell if my understanding is wrong.

It means L1 is a language, which includes all such Turing machines, which takes at least 2016 steps on all inputs. So we need to say it is decidable or not...

We are talking about which machine? We are talking about that machine whose language is L1. Other TMs are input to the new turing machine as encoding of 0 &1. We need to say for all inputs (for all Turing machine encodings) the new turing machine halts or not. When it will halt? When the new turing machine can either say..."Yes, the turing machine I am considering took at least 2016 steps but still it is on progress"...it also can say "No, the turing machine you gave me went to final state before 2016 steps" If it will say either of this, then the new turing machine, language L1 is decidable.

When it will be undecidable? When the new turing machine is still on progress unable to say yes or no. So solution is run new Turing machine for 2016 steps only. If it is saying "yes, the other turing machine halted...or the other turing machine did not halt."... then for both answer our new turing machine will halt... It is simple to understand that the new turing machine will always halt... bcz it's task is just to check the other turing machine halted or not within 2016 steps.

A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This gives an algorithm for deciding $L_1$: run the input machine $M$ on all inputs of length at most 2015, and check whether any of them stops within 2015 steps. If so, reject. Otherwise, accept.


Union of infinitely many regular languages I need to prove or disprove the following statement.

  If  $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.

I know that if two languages are regular, then the union of the languages is also regular. I don't think that really applies to this problem, because it's the union of every $n \in \mathbb N$. Also, to help with my understanding with the definitions, is $A_n$ a language or an alphabet, since it's a subset of $\Sigma^*$?

Is $A_n$ a language or an alphabet, since it's a subset of $\Sigma^*$?

A member of the alphabet, $\Sigma$ is called a symbol or a letter.
A member of $\Sigma^*$ is called a string or a word, which is a finite sequence of symbols or letters.
A subset of $\Sigma^*$ is called a language.

  If $A_n\subseteq \Sigma^*$ is regular for each $n\in\Bbb N$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.

As you suspected, this is not true. For example, let $A_n=\{a^nb^n\}$. Then $\bigcup\limits_{n=0}^{\infty} A_n$ is the well-known non-regular language of words with equal number of $a$'s and $b$'s. Infinity should indeed be treated carefully.

Exercise 1. Give an example of a non-regular language $L$ over unary alphabet such that $L=\bigcup\limits_{n=0}^{\infty} A_n$ where $A_n$ is a regular language for all $n$.

Exercise 2. Let $L$ be any language. Then $L=\bigcup\limits_{n=0}^{\infty} A_n$ for some regular language $A_n$.


Is FKS hashing really linear space? In FKS hashing, I wonder if the size of the table $G[1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability of a hash function $g_i$ is higher than 0.5, I can see that it will mostly hold small values (assuming we start with $g_0$, and if that doesn't work, try $g_1$ and so on). But I think for $n$ to $\infty$ there will be larger values as well, so that the number of bits for each entry is $log^*(n)$ and not fixed. Right?

The reason I ask is that many minimal perfect hash functions, such as the CHD algorithm, rely on a similar mechanism, and those algorithms claim to be strict $O(n)$ space.

Space is counted in machine words rather than in bits. A machine word is allowed to contain a member of the universe $U$, and so is $O(\log |U|)$ bits wide. The array $G$ stores hash functions, via their index inside some collection of universal hash functions. The lecture notes don't mention this, but there are collections of universal hash functions of size $O(|U|^2)$. If you use one of these collections, each entry of $G$ takes $O(\log (|U|^2)) = O(\log |U|)$ bits to store, and so $O(1)$ machine words.

Why is it meaningful to count space in machine words? First of all, even if you store your set as an array (with logarithmic access time, using binary search), the number of bits is $O(n \log |U|)$ rather than $O(n)$. If we want such an array to be considered taking up linear space, we need to "divide" by $\log |U|$, and the simplest way to accomplish this is to allow each memory cell to contain $O(\log |U|)$ bits (the exact constant doesn't matter).

Another reason we would like to allow cells to contain an unbounded number of bits is so that they can store indices. When you implement binary search, or any other algorithm, you have variables which store indices in the array. These variables take $O(\log n)$ bits to store. When discussing algorithms, however, we often think of an index as taking $O(1)$ space. Again, the way to accomplish this is to allow each memory cell to contain at least $\log n$ bits.

On the other hand, if we allow memory cells to be of arbitrary size, then the space measure becomes trivial, since anything can be done in $O(1)$ space (though depending on the exact computation model, you might have to pay in terms of running time). The usual convention in algorithms is to allow each memory cell to contain $O(\log n)$ bits, where $n$ is the input size (in bits). In this particular case, it is more meaningful to allow a machine word to contain $O(\max(\log n, \log |U|))$ bits, and this is the way we measure the space consumption of the algorithm.


Are most machine learning problems the same problem? (NP-hard) I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.
Reasoning for Question:

Most problems in Machine Learning are NP-hard.

2/3. All NP-Hard problems are the same problem - per reduction unto each-other in trivial poly-time.

Thus, it is the case that most Machine Learning problems are actually just the same problem in a different disguises. Is this true?
Timestamped: https://youtu.be/YX40hbAHx3s?t=406
An estimate on what percent of Machine Learning algorithms are NP-hard would be helpful. For example, regression is not NP-hard, but I was told that the fact that a closed form solution exists for that particular problem is a "miracle". I use the term most loosely. Many will also work.

I don't find this a useful or accurate perspective.
It's not true that all NP-hard problems are identical, not even under polynomial-time reductions.  All NP-complete problems can be reduced to each other in polynomial time, but NP-complete is different from NP-hard.
When you see someone say something like "all NP-complete problems are the same problem", that is an informal slogan that should not be taken too seriously; you need to look at the technical statement behind that and see whether it is relevant to what you care about.  In the context of machine learning, I don't think it's very relevant or useful.
Machine learning is about average-case behavior, not worse-case behavior.  NP-hardness is about worst-case behavior.
In machine learning we focus more on behavior on typical problem cases, rather than worst-case problems.  For example, the no-free-lunch theorem demonstrates that no ML algorithm will work well on all problems.
In machine learning typically we are more interested in understanding their accuracy rather than their running time, and usually we are concerned with concrete performance on concrete tasks and empirical results rather than asymptotic running time or provable guarantees.
For these reasons, the tools built up for NP-completeness and NP-hardness may not add a lot of insight about machine learning.


Do deterministic context free grammars always have corresponding deterministic push down automata? A language $L$ is deterministic context-free if and only if there is a
  deterministic push-down automaton M such that $L = L(M)$.

According to the answer key of this quiz, the above statement is false. Which is odd to me, if a context free language is one that can be defined by a pushdown automata, would a deterministic context free language not also be defined by a deterministic pushdown automata? Perhaps it's the "if and only if" that is at issue here.

I'm also referencing information from this post
Are there inherently ambiguous and deterministic context-free languages?, which does imply that the above statement should be true.

I would agree with you, but local definitions may differ.

One point might be the definition of $L(M)$. What is the acceptance type of the PDA? That might be "empty stack" or "final state". For deterministic PDA the two modes of acceptance are not equivalent. But also here wikipedia agrees that $L$ indicates final state, which is commonly used for DCFL.


Does any CPU not contain an ALU? Is there any kind of CPU which doesn't contain an ALU ?

If the CPU (Central Processing Unit) does any processing, it will do either Arithmetic or Logic operations... in a sense, some form of ALU is the core of the CPU.


What does "AF AX p" mean in CTL? Both Logic in Computer Science (Huth and Ryan, 2004) and Branching vs. Linear Time: Final Showdown (Vardi, 2002), state something to this effect (paraphrased):

  In LTL, X F p and F X p are equivalent, meaning "p is eventually true in some state that is not the current state". In CTL, AX AF p and AF AX p are not equivalent. AX AF p does mean the same as the above LTL formulas, but AF AX p means something different, which we leave as an exercise to the reader.

Both works emphasize that the meaning of AF AX p is something very strange.

From what I understand of CTL, AF AX p would mean "all paths from this state eventually reach a state where p is true in all next states", but that doesn't seem particularly strange. Am I correct in that understanding?

Your understanding of $AF AX p$ is correct (in my opinion). But whether it seems particularly strange or hard to understand is rather subjective. The argument you quote compares the expressiveness or usability of LTL and CTL, and tries to convince readers that LTL is easier to understand (especially for engineers in practice).

In my experience, it indeed takes more time for me to figure out and confirm the meaning of $AF\,AX\,p$ than that of $AX\,AF\,p$, which is in turn more than that of $X\,F\,p$ or $F\,X\,p$. By the way, if $AF\,AX\,p$ were easier to understand than the other three formulas, you  would probably not bother asking for confirmations here.


Irregularity of $\{a^iba^j : i \neq j\}$ using pumping lemma Proving the language $L=\{ a^i b a^j |\ i<j,\text{ or }i>j;\ i,j>0 \} $ is not regular, I am trying to use the pumping lemma for regular languages:

pumping length $:= m$

case 1: $i<j; j=m$

$w_1 = a^i b a^m = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

$a$s only
$a$s + $b$
just $b$

However, this leads to $xy^hz\ \not \in L\ \forall h,\ h>0$.

case 2: $i>j; i=m$

$w_2 = a^m b a^j = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

$a$s only

Pumping with this $y$:
 $xy^hz\ \in L\ \forall h$ holds true.

As this answer does not seem to even consider the second case, is the first case sufficient to proof the language is not regular?
However, taking a look at this answer I think I'd have to considere the second case as well, in order to cover all possible $xyz$ combinations.

Here is the contrapositive form of the pumping lemma, which is what we use to prove that a language is not regular:

  Let $L$ be a language. Suppose that for all $p \geq 1$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

Using the pumping lemma directly for the language $L$ in the question is a bit tricky. Given $p \geq 1$, let $w = a^p b a^{p+p!} \in L$; note that $|w| \geq p$. We have to show that for every decomposition $w = xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Consider any such decomposition. It is easy to check that $y = a^\ell$ for some $1 \leq \ell \leq p$, and that $xy^ij = a^{p+(i-1)\ell}ba^{p+p!}$. For $i = p!/\ell+1$ (which is an integer!), $xy^ij = a^{p+p!}ba^{p+p!} \notin L$. Thus the condition in the pumping lemma is satisfied, and we conclude that $L$ is not regular.


Is there a name for this graph search strategy? The standard implementation of breadth-first search looks like

queue = [root]
while queue:
    node = queue.pop()
    visit(node)
    for_each child in node.children:
        queue.push(child)

Just by switching the queue to a stack:

stack = [root]
while stack:
    node = stack.pop()
    visit(node)
    for_each child in node.children:
        stack.push(child)

we get depth-first search.

There is another way to write breadth-first search:

visit(root)
queue = [root]
while queue:
    node = queue.pop()
    for_each child in node.children:
        visit(child)
        queue.push(child)

But when you switch this one from a queue to a stack:

visit(root)
stack = [root]
while stack:
    node = stack.pop()
    for_each child in node.children:
        visit(child)
        stack.push(child)

You do not get a traditional depth-first search.  Instead, you get a variant where all a node's immediate children are visited first, then its other ancestors in a depth-first way.  For example, on this tree:

     F
   /   \
  B     G
 / \     \
A   D     I
   / \   /
  C   E H

Depth-first search gives the order

  [F, G, I, H, B, D, E, C, A]

The last algorithm gives the order

  [F, B, G, I, H, A, D, C, E]

which is not exactly depth-first because B and G are both visited before I.  Does this algorithm have a name?

I don't think it has any standard name, but you might arguably call it a depth-first search with one level of lookahead.


Is this variation of set-cover NP-hard to approximate? The classic set-cover problem is described as follows:

  Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1,
 ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The
  objective is to find some cover $C \subset \Lambda $ such that
  $\cup_{A\in C}A = S$ and $|C|$ is minimized. That is, find the minimum
  number of $A$'s needed to cover every element of $S$.

The variation we will consider has two key alterations:

Rather than finding some cover $C$ such that $|C|$ is minimized, we want to cover as much of $S$ as possible, given some budget $k$. That is, let $F\subset S$ be the elements that are covered by $C$, our objective is to maximize
$$\big|F \cap S\big|$$
such that $|C| \leq k$.
Rather than considering an element $s \in S$ covered when $s$ appears in at least one $A\in C$, we require that $s$ show up in 2 distinct $A$'s to be considered covered. (Any multiple is also interesting, even heterogeneous ones for each $s\in S$, but for now 2 is good enough).

So far I can show that it is an NP optimization (reduction from set-cover), and that a $n-$approximation exists by simply looking any element $s$ that appears in some $A_i$ and $A_j$ and then selecting $C = \{A_i, A_j\}$, but this is a rather unsatisfying approximation.

Is this variation NP-hard to approximate to a constant factor?

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP).

Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the optimal solution for the new instance (of your problem) is either $M$ or $M+1$. (You can also add $S \cup \{x\},\{x\}$, where $x$ is a new element, to make the optimal solution of the new instance exactly $M+2$.) Hence your problem inherits the $\ln n$-hardness of set cover. In the other direction, the greedy algorithm likely gives an $O(\log n)$ approximation for your problem.


Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$? I'm working with this definition for one-way functions:

  We call $f$ a (strong) one-way function if

  it is computable in polynomial time
  for any polynomial time randomized algorithm $B$ and any constant $c$
  $$
\mathbb{P}\big(f(B(f(x))) = f(x)\big) = o(n^{-c})
$$
  where $x\in\{0,1\}^n.$

And this defintion for hard-core bits:

  Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$,
  $$
\mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\,.
$$

And I'm asking myself whether, if $f$ is one-way and finding $x$ from $f(x)$ is polynomial time reducible to finding $b(x)$ from $f(x)$, $b$ must be hard-core. One way to structure this argument is like so:
$$
\text{finding $x$ reduces to finding $b(x)$} \implies \big(f\text{ is one-way} \implies b\text{ is hard-core}\big)
$$
Or by contrapositive:
$$
\text{finding $x$ reduces to finding $b(x)$} \implies \big(b\text{ isn't hard-core} \implies f\text{ isn't one-way}\big)
$$

So suppose finding $x$ reduces to finding $b(x)$ and $b$ isn't hard-core. Then the obvious strategy is to go through the reduction but instead of computing $b(x)$ deterministically, we make a good guess using some algorithm $B$ which must exist because $b$ isn't hard-core. Since we have a non-negligible chance of success to guess $b(x)$ correctly, we end up with a non-negligible chance to guess $x$ correctly and so $f$ isn't one-way.
But there's a point here where trouble comes in. That is, the reduction might involve computing $b(x)$ multiple times for various values of $x$. While we know the probability of computing a single $b(x)$ for a random $x$ correctly, I don't have any handle on the probability of success for a sequence of calls $b(x_i)$ where the $x_i$ are arbitrarily correlated.

Before addressing your question, we should note that there are some subtleties when defining "inverting $f(x)$ reduces to finding $h(x)$". Suppose we aim towards something along the lines of a standard Turing reduction, then what does our oracle do? When feeding the oracle some string $y\in\{0,1\}^*$, where the only promise about $y$ is that it lies in the image of $f$, then what do you expect it to return? If $f$ is a permutation, then this is easy. However, when $f$ is not one to one, it isn't clear what to expect. One possibility is to require that the oracle returns $h(x)$ for some $x\in f^{-1}(y)$, though it might make the oracle pretty much useless (I'd guess that there exists a one way function $f$ and a hardcore predicate $h$ for $f$ such that any function in $2^{\{0,1\}^*}$ is an $h$-oracle for $f$ under this definition).

Back to your original question. Suppose $f$ is a one way permutation and define $g(x,i,j)=(f(x),i,j,x_i)$. Inverting $f$ reduces to (under the above definition) evaluating $h(x,i,j)=x_j$, since you can feed the oracle different values of $j$. However, $h$ is not hardcore for $g$, since for a uniformly chosen triplet $(x,i,j)$ where $x\in\{0,1\}^n$ and $i,j\in [n]$, with probability $\frac{1}{n}$ it holds that $i=j$ and you can recover $x_j$.


High Level Programming Languages vs Block Programming Environments I am looking for the opinions of more experienced programmers as to the effectiveness of writing programs in Block Programming Environments such as Scratch or App Inventor as opposed to High Level Languages such as C++, Python or Java.
I have already done some research and here are some examples of links that have been helpful.

Programming : High Level Languages
An Overview of Programs and Programming Languages

I am just looking for a few other peoples opinions.

Questions that I would really appreciate if you could answer include:

Do you find using high level code easier or more difficult than using blocks?

Have you experienced any limitations of either High Level Languages or Block programming?

What advantages and disadvantages have you experienced when using the two?

Any helpful answers would really be appreciated

A Block programming environment is higher in the abstraction levels as compare to high level programming languages which basically mean that Block programming environment is easy to work with and there is less conceptual burden to carry BUT you can do "less stuff" (as it is very abstracted) where as in high level programming languages you can do "more stuff" but the conceptual burden at this level is much high.

This is how abstraction principle works. More abstract = less things to worry about BUT less ability. Less abstract = More things to worry about BUT more ability.

It is usually advised that you start at the top abstraction layer so that you can start learning things without freaking out with way too much details and as you get more and more experience you start to look at bottom abstraction layers to gain more insights and get more done.


The border between P and NP for some problems A problem is defined to be in NP when it can be reduced to another NP problem in polynomial time.

In Karp's 21 NP-complete problems, the most famous ones are presented. However, I wonder (and could not find a reference) for some of them, what happens if we "relax" the objective function.

For instance, say Hamiltonian path problem: given a graph $G$ with $n$ vertices, is there a simple path $P$ of length $n$? (i.e. passes through all vertices). This problem is NP-complete.

But what if I ask for a path $P$ whose length is $n-k$? At which value of $k$ the problem becomes tractable?

Similarly, 3-coloring problem: color the vertices of a graph with three colors such that no two adjacent vertices have the same color.
What if I allow $k$ pairs of adjacent vertices to be the same color?

Is this descripton the very same thing with approximation algorithms? Or is this a different concept?

Approximation algorithms are most often encountered in the context of optimization problems. Consider the problem of minimizing some function $f$ subject to constraints $C$. An $\alpha$ approximation algorithm (where $\alpha$ can depend on some parameters of the instance, such as the number of vertices in a graph) is a (usually) polynomial time algorithm which produces a feasible solution (that is, one satisfying the constraints $C$) whose value is at most $\alpha$ times the optimum.

In some cases, bicriteria approximation algorithms are considered. These are algorithms as above, with the only difference being that the solution doesn't satisfy the constraints $C$ but rather some weaker version of them $C'$. See this question for some examples.

In the case of 3-coloring, your notion is very similar to the following optimization version of 3-coloring: given a graph, find a 3-coloring which violates the least number of constraints. There are several hardness results that show that it is difficult to approximate the optimum, even if you are allowed to use more colors (in the spirit of bicriteria optimization problems). For example, Guruswami and Khanna, in their paper On the hardness of 4-coloring a 3-colorable graph, show that it is NP-hard to distinguish between the following two classes of graphs: (i) 3-colorable graphs, (ii) graphs in which every 4-coloring has an $\epsilon_0$-fraction of monochromatic edges (for some constant $\epsilon_0$).

Similarly, your relaxation of the Hamiltonian path problem can be rephrased as an optimization problem: the longest path problem. It is NP-hard for any constant $k$, and even for much larger $k$; see the paper mentioned in Wikipedia, On approximating the longest path in a graph by Karger, Motwani and Ramkumar.


Regular Grammar and Regular Language My doubt is based on the relation between regular grammar and regular languges

$S \to Sa\ |\ a$ produces the regular language $a^+$ but this grammar is not type-3 grammar of Chomsky classification. So am I correct in stating that this is not a regular grammar even when it produces regular language?

Let me quote the wikipedia entry for linear grammar:

  Two special types of linear grammars are the following:

  the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends
  the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

  Collectively, these two special types of linear grammars are known as
  the regular grammars; both can describe exactly the regular languages.

As you can see, your grammar is a left-linear grammar, and it generates a regular language. Type-3 grammars of the Chomsky hierarchy can be defined as right-linear grammars or as left-linear grammars, as you prefer.


Randomized and Deterministic Communication Complexity of a function I have a problem I'm trying to answer for my homework. The question is:

Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $⌈log2p⌉$ bits and B has input $y∈GF(p)$ encoded with $⌈log2p⌉$ bits. Let $f:GF(p)×GF(p)→\{0,1\}$ be the function defined as
$$
f(x,y)=
\begin{cases}
0& \text{if}& x+y+xy=0\\
1& \text{if}& x+y+xy≠0
\end{cases}
$$
for all $x,y∈GF(p)$. Show that the randomized communication complexity of $f$ is $O(log\text{ } log\text{ } p)$ bits. Can you prove a lower bound on the deterministic communication complexity of $f$?

I've been thinking about using a random element $r∈GF(p)$ and make A calculate $f$ using $x$ and $r$ and sending the answer $r$ to B, but this doesn't seem to work as there are no general trend using such an protocol. For example that when A and B get the same answer, the function is $0$ or if they get different answers, the function is $1$.

Anyone have any idea how this protocol can look like? For example what kind of random input should be used?

Hint: The condition $x + y + xy = 0$ is equivalent to the condition $1 + x + y + xy = 1$, i.e. $(1 + x)(1 + y) = 1$, or in other words,
$$
(1+x)^{-1} = 1+y.
$$


How to reduce from subset-sum problem? I have this problem which is described as follows:

Input:
    You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$.
    $M = {(x_1,y_1), (x_2,y_2), ..., (x_n,y_n)}$.
    Each $x$ and $y$ is an integer $>= 0$.
    $P$ in an integer $>= 0$.
    $T$ is an integer $> 0$.

Question:
    Is there a subset $G$ of $M$, such that the sum of every $x$ value of $G$ is $> P$ and the sum of every $y$ value of $G$ is $< T$?
    (Note: You are basically taking from $M$. For example: if $M$ has two $(1,1)$'s then $G$ can contain at most two $(1, 1)$'s)

I want to reduce it to from the subset sum problem, but I am not sure how because there's two conditions to solve for...

Can anyone help with this problem?


Solving constants in the recursive term with master theorem We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the problems were in the form of $aT(\frac{n}{b}) + f(n)$ where applying the Master Theorem is no sweat, but we're given this recurrence relation wherein there is a constant inside the recursive term, I am not sure anymore if Master Theorem would still work, or is there another way?
\begin{align*}
T(n) = 3T\left(\frac{n}{3}-2\right) + \frac{n}{2}
\end{align*}
This one has a constant 2 inside the term, and I don't know how to show that this recurrence relation is upper bounded by $ O (n \log n) $.

If you are just interested in an upper bound you can notice that $T(n) \le S(n)$ where $S(n) = 3 S(n/3) + \frac{n}{2}$ and has solution $S(n) = O(n \log n)$.
Alternatively there is always induction. You can show that, for $n \ge 2$,  $T(n) \le c n \log n$.
For $2 \le n < 7$, $T(n)$ is a constant and $n \log n \ge 1$. Therefore the claim is true for a sufficiently large (constant) value $c^*$ of $c$.
For $n \ge 7$ you have:
$$
T(n) = 3T\left(\frac{n}{3} - 2\right) + \frac{n}{2} \le 3 c \frac{n}{3} \log \frac{n}{3} + \frac{n}{2}
= cn \log n - cn \log 3 + \frac{n}{2},
$$
which is at most $cn \log n$ when $c n \log 3 \ge \frac{n}{2}$ or, equivalently, $c \ge \frac{1}{2 \log 3}$.
Simply pick $c = \max\{c^*, \frac{1}{2 \log 3} \}$.


Find cycles with specific weights in complete graph (this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=[4,7,6]$).
Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$
Here is a poorly-drawn example:
.

Welcome to CS.SE.
I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.
A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?
This leads to the following python 2.7 code, that does not make the assumption that the graph is complete. Its core is the find function, everything else is for playing and testing.
import random
random.seed()

min_weight,max_weight=1,20
c_length=30

# build the graph (complete in this case)
V = ['A','B','C','D','E']
N = {u:[v for v in V if v!=u] for u in V}
weight = {}
for (u,v) in [(u,v) for u in V for v in N[u] if u<v]:
        weight[(u,v)] = weight[(v,u)] = random.randint(min_weight,max_weight)
for (u,v) in sorted(weight):
        print u+'--'+str(weight[(u,v)])+"--"+v

# build a correct sequence of weights
c = []
u = random.choice(V)
while len(c)<c_length:
        v = random.choice(N[u])
        c.append(weight[(u,v)])
        u = v
print c

# search all paths corresponding to the weight sequence in the graph
def find(c,S):
        if len(c)==0:
                return(S)
        return set([u+r for u in S for r in find(c[1:],[v for v in N[u] if weight[(u,v)]==c[0]])])

result = find(c,V)
print result

# check results
def check(x):
        if len(x) != len(c)+1:
                return(False)
        for i in xrange(len(x)-1):
                if weight[(x[i],x[i+1])] != c[i]:
                        return(False)
        return(True)
for x in result:
        assert(check(x))

Is it correct? It is far from optimal, of course.


Mapping Reductions to Complement of A$_{TM}$ I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$

where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\}$

which is great for proving undecidability. But say I want to prove unrecognizability instead. That is, I want to use the corollary that given $A \le_{m} B$, if $A$ is unrecognizable then $B$ is unrecognizable.

So for any arbitrary unrecognizable language $C$ which can be reduced to $\overline{A_{TM}}$ (any example language would suffice for sake of example), how can I reduce $\overline{A_{TM}} \le_{m} C$?

For simplicity, suffice to merely consider TM in $\overline{A_{TM}}$.

EDIT

For clarification, $\overline{A_{TM}} = \{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \}$

Let's take $L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$, that is, all the machines that accept no word (i.e., whose language is empty).

Now we show the reduction $\overline{A_{TM}} \le L_\emptyset$. The reduction is done by taking an input $(\langle M \rangle,w)$ of $\overline{A_{TM}}$ and converting it into an input ${\langle \tilde M \rangle}$ for $L_\emptyset$ such that

$$(\langle M \rangle,w) \in \overline{A_{TM}} \quad\text{  iff  }\quad \langle \tilde M \rangle \in L_{\emptyset}$$

Given $(\langle M \rangle,w)$ we can construct $\tilde M$ in th following way. $\tilde M$ on input y does the following:

deletes the tape
writes $w$ on the tape
runs $M$ on $w$, and performs the same (if $M$ accepts, $\tilde M$ accepts as well).

Convince yourself it is possible to construct the coding of $\tilde M$ from the coding of $M$ and from $w$. Now let's verify that this reduction is valid:

If $(\langle M \rangle,w) \in \overline{A_{TM}}$ then $M$ either rejects or doesn't halt. If so, then also $\tilde M$ doesn't accept $y$, for any input $y$. This means $L(\tilde M) = \emptyset$ thus $\langle \tilde M \rangle \in L_{\emptyset}$.
If $(\langle M \rangle,w) \notin \overline{A_{TM}}$ then $M$ accepts $w$, thus $\tilde M$ accepts $y$ (for every $y$). It follows that $L(\tilde M)=\Sigma^*$ which implies that $\langle \tilde M \rangle \notin L_{\emptyset}$.

The "iff" condition holds and we successfully mapped an input of $\overline{A_{TM}}$ into an input of $L_\emptyset$. In this case we say we reduced $\overline{A_{TM}}$ to $L_\emptyset$. That is, if we can solve $L_\emptyset$, we can also solve $\overline{A_{TM}}$ by first converting the input and then running the algorithm that solves $L_\emptyset$ on the converted input.


Is FNP = FEXPTIME if and only if NP = EXPTIME? It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia).

Is it also true that if $\sf FNP=FEXPTIME$ then also $\sf NP=EXPTIME$?  (See the exponential time conjecture.)  I did find a paper constructing real functions that are in $\sf FEXPTIME$.

Yes, vacuously, since it is trivial that $\operatorname{FNP} \neq \operatorname{FEXPTIME}$, because it takes an exponentially long amount of time to give an exponentially long output.


Show that the following algorithm takes $O(n)$ time You are given a linked list of size $n$.
An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed is at index $i$ and it belongs to a list of size $n$. Once an index $i$ is accessed, the list is broken into two lists. One list contains the first $i$ elements and the second list contains the rest of the elements. It has something to do with cartesian trees, but I am not clear how to proceed with this chain of thought.

Show that the total cost incurred to access all the elements is any arbitrary order is $O(n)$.

Can't be done.

Consider the following sequence of access: $$\tfrac{1}{2}n, \tfrac{1}{4}n, \tfrac{3}{4}n, \tfrac{1}{8}n, \tfrac{3}{8}n, \tfrac{5}{8}n, \tfrac{7}{8}n, \ldots$$

The first access costs $\tfrac{1}{2}n$. The next two cost $\tfrac{1}{4}n$ each, for a total of $\tfrac{1}{2}n$. The next four also cost a total of $\tfrac{1}{2}n$. Overall we get a cost of $\tfrac{1}{2}n \lg n$.


Why are strings immutable in some languages? String is an immutable class in Java. An immutable class is simply a class whose instances cannot be modified.  Why does the Java programming language choose to make objects of class String immutable?

This issue is strongly connected to the notion of what it means to be an instance of a class. In strict Object-Oriented terms, a class has an associated invariant: a predicate which always holds true on exit from a (public) method of the class. Such a notion is central in ensuring that inheritance is well-defined, for example (it's part of the Liskov Substitution Principle).

One of the most pernicious issues with Java is that it is difficult to prevent client code from breaking class invariants.

For example, consider the following 'ZipCode' class:

class ZipCode {
    private String zipCode;

    public ZipCode(String value){
        if(!isValidZipCode(value))
            throw new IllegalArgumentException();
        zipCode = value;
        assert(invariant());
    }

    public String get() { return zipCode; }

    public boolean invariant() {
        return isValidZipCode( zipCode );
    }
}

If String were not immutable, it would be possible for a user of ZipCode to call 'get' and change the characters at any subsequent time, thereby breaking the invariant and destroying the conceptual integrity offered by the encapsulation  of the ZipCode concept.

Since this kind of integrity is essential to ensuring that large systems are valid, this answer to your question really begs the wider one of:

"Why doesn't Java support an analog of C++ const, or at least offer immutable versions of more of it's library classes?"


Pumping Lemma: Is language with equal number of "aa" and "bb" regular? Given alphabet $\Sigma=\{a,b\}$, is the language
$$L = \{ w \mid w\text{ contains an equal number of substrings }aa\text{ and }bb \}$$
regular?
 My initial though was no, because the language $L' = \{a^nb^n\mid n\ge0\}$, is not regular, and is of the same general form as $L$. However, I am confused about how $aa$ and $bb$ being substrings affects the proof, via pumping lemma. Is it proper to select a "specific" $s$ for the pumping lemma, such as

$$s = a^p(aa)^pb^p(bb)^p\,?$$

Is there a better $s$ I could choose? In general, how would I pick an $s$ when I am dealing with a language written based upon substrings, like $L$?

Your intuition is correct: regular languages can't count.  Indeed, a quick way to prove that $L$ isn't regular is to observe that $L\cap \{a^mb^n\mid m,n\geq 0\} = L'\cup\{a,b\}$. Since the intersection of any two regular langauges is regular, and $\{a^mb^n\mid m,n\geq 0\}$ is certainly regular, it must be that $L$ is not – because if it was regular, then its intersection with $\{a^mb^n\mid m,n\geq 0\}$ would have to be regular, and it isn't.

To prove with the pumping lemma, you need to show that, for every $p>0$, there is a string $s$ of length at least $p$ such that every way of writing $s=xyz$ with $|y|\geq 1$ and $|xy|\leq p$ has $xy^nz\notin L$ for some $n\geq 0$. (I originally wrote "just need to show" but deleted "just" because the statement that follows is such a mouthful!)

Your string $s$ works just fine.  If we rewrite it in the required form $s=xyz$, the fact that $|xy|\leq p$ means that $x=a^k$, $y=a^\ell$, with $1\leq\ell\leq p$ and $0\leq k\leq p-\ell$.  And $z$ is the rest of the string.  But, now, for any $n\neq 1$, we have
\begin{align*}
  xy^nz &= a^ka^{n\ell}a^{p-k-\ell}(aa)^pb^p(bb)^p\\
        &= a^{3p+(n-1)\ell}b^{3p}\,,
\end{align*}
and this string is not in $L$, since the number of $a$s at the front is different from the number of $b$s at the back, so the number of $aa$ substrings is different from the number of $bb$s.

Insofar as that proof works, there's no problem with your choice of $s$.  But, if you read through the proof, you'll see that there would have been a bit less writing if you'd just chosen $a^pb^p$. The point is that, when something in the $a^p$ part gets "pumped", it breaks the required property of having the same number of $aa$s as $bb$s.

It's hard to give general advice, because proof is a creative act and you can't just follow recipes. The general scheme is to pick a string where repeating any sequence of characters from the first $p$ will break the property that defines the language.


Turing machine that converts decimal to binary I'm a beginner in Turing machine computation and want to design two TMs; one that converts decimal number to binary, and other one that converts binary to decimal.

Could anyone help me design these Turing machines? How can I start?

Thanks.

You can play around and try your ideas with this simulator.

Under examples, you can find decimal to binary converter. Furthermore, you can learn about TMs in tutorial section.


Why does RAID-5 require an additional disk for parity blocks? I know that RAID-5 consists of block-level striping across multiple disks, but using an additional parity-check block on each disk .. and that at least two disks are required for striping.

And it's obvious that each parity block is specific to each disk it belongs to (and so there is no need for allocating an additional disk).

Image from Wikipedia.

However I've been unable to understand why in fact there is an additional disk required for parity checks, as I found on this article:

  The minimum number of disks in a RAID 5 set is three (two for data and
  one for parity).

Any idea?

I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery from a failed disc.

Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and  $1$ are data and disc $2$ is parity. "Parity" means that the $b$th block of disc $2$ is the xor of the $b$th blocks of discs $0$ and $1$. The point is that, if any single disc fails, we can recover its data because the $b$th block of any disc is the xor of the $b$th block on the other two discs. For this to work, it's crucial that the parity data is on a separate discs. If you only had two discs and put the parity data on those discs (e.g., each disc was two-thirds data blocks and one-third parity blocks) then the failure of a single drive would destroy some blocks and their corresponding parity data, so you'd be unable to recover the data using just what was left on the remaining disc.

RAID-5 is the same idea except that, instead of putting all the parity data on the last disc, it's spread across all the discs. So, for a three-disc set-up, a third of the blocks would have parity data on disc $2$, a third on disc $1$ and a third on disc $0$.

The point of using RAID-5 rather than RAID-4 is that every time you write data, the corresponding parity block must be updated. If all parity data is on the same disc, that disc will be written to much more than the other discs ($k$ times as much, in a $k$-disc sytem), so it will fail faster. Spreading the parity data across the discs evens out the wear on them.


K Perfect Subgraph Algorithm I have a problem that goes as follows:

Problem. Suppose we have undirected graph $G$. We denote a $k$-perfect graph as a graph such that $\forall v \in G, degree(v) = k$. Present an algorithm that constructs a subgraph $H$ such that $H$ is $k$-perfect, for $k$ maximized. Do this in $\theta(|V| + |E|)$ time.

I was thinking that perhaps we could borrow techniques from a BFS based topological sort, to work on the "fringe" vertices and continuously cut inwards. Formally, we would identify vertices with small degree and cut them out, but I don't know how to make sure that this doesn't accidentally take out a vertex that would create a $k$ perfect graph of larger $k$, and how to do this without the check for if we're done costing $\theta(V)$.

Have you got any ideas?

Note that we define a subgraph here as: $H = (V', E')$ is a subgraph of $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$. Basically we are allowed to remove both edges and vertices.

This problem is NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance in polynomial (let alone linear!) time.  I'll show this by reducing the NP-hard problem Clique to this problem.  In Clique, we are given an undirected graph $F$ and a number $K$, and the task is to determine whether or not $F$ contains a clique (complete subgraph) with at least $K$ vertices.  The strategy will be to add universal vertices to $F$ -- that is, new vertices that are connected to all existing vertices -- and show that doing so grows the size of cliques in $F$, but does not grow the size of any other regular subgraphs in $F$.

Let there be $n$ vertices in $F$.  We will construct an instance $(G, k)$ of your problem from the given instance $(F, K)$ of the Clique problem:

$G$ is formed by adding $n+1$ new vertices to $F$ that are adjacent to each other and to every vertex in $F$.
$k = K + n$.

First we show that if there is a clique in $F$ of size at least $K$, then there is a regular subgraph with degree at least $K+n$ in $G$.  Clearly a clique of $K+n+1$ vertices can be formed by including the $K$ clique vertices in $F$ and all $n+1$ new vertices.  A clique containing $i$ vertices is regular with degree $i-1$, so this clique is regular of degree at least $K+n$.  Thus a YES answer to the given Clique problem implies a YES answer to the constructed instance of your problem.

Now we show that if there is a regular subgraph $H$ with degree at least $K+n$ in $G$, then there is a clique of size at least $K$ in $F$.  First observe that this $H$ must include at least one of the $n+1$ newly added universal vertices, since the largest degree obtainable using just the original $n$ vertices of $F$ is $n-1 < n+K$.  The following lemma is key:

  Lemma: If a regular graph $I$ contains a universal vertex, then it must be a clique.

  Proof: Let $c \ge 1$ be the number of universal vertices in $I$, and let $a$ be the number of other vertices.  Since $I$ is regular, it
  must be that every non-universal vertex has the same degree $c+d$ for
  some $d$ -- that is, removing the $c$ universal vertices from $I$ must
  leave a $d$-regular subgraph, which I'll call $I'$.  Again, since $I$
  is regular, we must have that the degree $c-1+a$ of each universal
  vertex in $I$ is equal to the degree $c+d$ of the other vertices.  But
  this implies $a-1=d$, i.e., $I'$ is a clique of $a$ vertices, and thus
  $I$ is a clique of $c+a$ vertices.

Since $H$ contains at least one universal vertex, by the above lemma, it must be a clique of size at least $K+n+1$.  Since we only added $n+1$ universal vertices to $G$, at least $K$ of the vertices in $H$ must have come from the original graph $F$, where they also form a clique since every induced subgraph of a clique is a clique.  Thus a YES answer to the constructed instance of your problem implies a YES answer to the given Clique problem.

Since a YES answer to one problem instance implies a YES answer to the other, it follows that a NO answer to one problem instance also implies a NO answer to the other.  Thus any algorithm that could solve your problem could also solve Clique.  Since constructing the instance of your problem requires only polynomial time, a polynomial-time algorithm that could solve your problem could also solve Clique in polynomial time.


Interval Scheduling Problem with Three Resources So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources.  Consider this example interval scheduling problem.

Say there are n requests for a lecture hall and three lecture halls are available to satisfy these requests. Each request has a starting time and an ending time.
Create an algorithm to get a maximal scheduling.

I am familiar with the process and I know how the ISP would work if I had only one resource.  But how would I apply it in this scenario if I had two, three, or a predefined set of resources.

Any input will be appreciated.

The greedy scheduling with a first fit resource selection is actually not correct.
Consider the case where the intervals are:

${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$,

for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. Although, a more optimal assignment would have been assigning all 4 of them 1, 2, 2, 1 in the following order.

So another greedy choice has to be made which is the selection of the resource to host the interval. The greedy choice would be selecting the compatible resource with the latest finish time. That way resources which are good (i.e. support more intervals) are kept free.

Intuition to the correctness of the algorithm:

There are 2 claims:
1) Intervals with early finishing time are always better to schedule first.

This is proven by an exchange argument, assume we would leave an interval with early finish time unscheduled to take a later interval, future intervals will definitely have a harder job finding a free room.

2) When an interval is compatible, it is always better to select the worst compatible room.

Since by claim 1, the interval will be taken anyway, the state of the rooms will have a room with $nextFreeTime = endTime_{cur}$ leaving 2 rooms with their previous $nextFreeTime$. Selecting the room with a larger $nextFreeTime$ will leave the better rooms for worse intervals.

Note: The problem can be solved with a less efficient but more obviously correct algorithm using a 3D dynamic programming approach. The state of the dp would indicate the last taken resource in each of the rooms, and the transitions are for each current interval, try selecting all of the compatible rooms updating their states. The intervals are still taken in order of finish time (Claim 1 still holds). The complexity becomes $O(n^3)$, however this is not scalable for k resources unlike the greedy algorithm.


Can a turing machine calculate word's length? I want to understand how a turing machine that will accept only words of length bigger than 100 will look like.
My idea: it will copy a word and move to the right 100 times.
If non of the cells was empty it will accept.
Furthermore if it is true I can also conclude that it is decidable .

If there is no problem with my assertions so far, how will a turing machine that prints the number of letters in a word will look like? is it possible as well?

Replace every character in the input string with a $1$; you then have the length of the string in unary notation. Then convert the unary representation to your favorite base $b$ by successive division by $b$.


DFA for binary language with constraints on triplets I need to create a deterministic finite automata whose language consists of words over $\{0,1\}$ of any length, satisfying the following constraint:

  Among any subsequent 3 numbers, there needs to be exactly two 1s, and exactly one 0.

I've spent a couple hours studying DFAs, but I can only find solutions like the one I need to one of these issues. Meaning that among the 3, there can be at most 1 of something, or there needs to be at least 2 of something. I'm pretty much lost in how I'm supposed to combine these into a single DFA.

Imagine writing a program on any high-level language for checking if string corresponds the given restriction. You would probably iterate symbols one by one and check if appending next symbol breaks the restriction.

Now note that you need only two last symbols to do it,  and there are finite number of two-symbols combinations (namely $--, -0,-1,00,01,10,11$, where "$-$" stands for absence of preceding symbol at the very beginning of the string).

Why wouldn't we use these combinations as automata states? You are left only to add transitions, which are pretty straightforward (e.g. appending $0$ to $11$ transits to $10$, appending $1$ to $00$ transits to the dead state, and so on). Can you finish it now?


What is the definition of a problem In computation theory, when talking about the computability and complexity of a
problem, what is the definition of a problem?

How specific should a problem be? For example, can the followings
all be function evaluation problems?

evaluate $f$, where $f(x)=x^2, x \in \mathbb R$
evaluate any function in $\mathbb R^{\mathbb R}$.
evaluate any function in $Y^X$, where $X$ and $Y$ are any two sets.

Without restriction to the computability and complexity of a problem (or
even without restriction to computation theory), how is a problem defined?

Can the above examples in 1 all  be  function evaluation problems?

Thanks.

A problem is anything you're trying to solve computationally. Problems typically specify an input and a desired output which, for most models of computation, will both be finite. Any statement of the form, "Given $X$, compute/evaluate/find/determine/decide whether/..." is a problem.

So, yes, all the things you describe in the question are problems. (Though, in the case where the input is the uncountable set $\mathbb{R}$, you need to be careful about how you specify what the input is.)


Prove that the TM which would go over the leftmost position is not decidable Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the left.

Show that the language

$ LEFT_{TM} = \{<M,w> | $ M is a TM of the type above $\}$

is not decidable.

How can I show that such a language is not decidable?

I was thinking about using the TM $A$ which accepts any input and reduce it to $LEFT_{TM}$, but I'm not sure how. I would appreciate a nudge in the right direction.

You can reduce the halting problem to your problem. Roughly speaking, the reduction goes along the following lines:

  Given a Turing machine $T$, construct a Turing machine $T'$ which simulates $T$ but never ventures to the left of the starting symbol. If $T$ halts, it then proceeds to go all the way to the left, until it goes beyond the starting symbol.

If you can do this, then you will have shown that LEFT is undecidable.

So how do you construct the machine $T'$? The difficult part is to somehow arrange that it never goes to the left of the starting symbol. Fortunately, this is essentially equivalent to showing that Turing machines with a one-sided infinite tape are equivalent to Turing machines with a two-sided infinite tape. You can look this up in many sources, or come up with a simulation of your own. There are many different ways to do it. Be creative!

One thing which might be unclear is what it means to simulate $T$ without going to the left of the starting symbol. What if $T$ wants to go to the left of the starting symbol? We are not looking for a literal simulation. Rather, we want to simulate each step of $T$ using a series of steps in $T'$, in such a way that the state of $T$ can be read from the state of $T'$. As a simple example, you can think of a Turing machine over the tape alphabet $\{0,1\}$ which simulates a Turing machine with tape alphabet $\{00,01,10,11\}$ by using two cells to store each symbol. We are looking for something similar: simulating a two-sided infinite tape using a one-sided infinite tape.


Intuition behind the Master Theorem The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following:

  For a recurrence of the form $T(n) = aT(\frac{n}{b})+f(n)$
  with constants $a \ge 1$ and $b>1$,

  Case 1: if $f(n) = O(n^{\log_b(a-\varepsilon)})$ for some $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b(a)})$

  Case 2: if $f(n) = \Theta(n^{\log_b(a)})$, then $T(n) = \Theta(\log n \cdot n^{\log _b(a)})$

  Case 3: if $f(n) = \Omega(n^{log_b(a+\varepsilon)})$ for some $\varepsilon > 0$, and if $a f(\frac{n}{b}) \le c f(n)$ for some
  constant $c<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

I have seen proofs of this theorem which go through the algebraic derivation of these results and I understand how to apply it but I don't have a very strong intuitive understanding of why it works. Here's what I understand so far, using these explanations of the Master Theorem on Quora as a starting point:

The first answer frames the three cases in terms of the relative amount of work done at each level (either increasing geometrically, staying the same, or decreasing geometrically). At a high level, I understand this intuition and if the Master Theorem were given to me I could explain it using this reasoning, but I'm unconvinced that I could take this idea of geometric growth/decay and then derive the theorem.
I think the second answer is closer to the kind of intuition I'm looking for. It explains the $aT(\frac{n}{b})$ term and the $f(n)$ term as opposing forces of replication and merging, respectively. However, I'm having trouble understanding how the intuitive cases (the replication step winning, the merging step winning, and the forces being equal) actually translate into the three different cases of the Master Theorem.

This explanation also follows a similar argument and simplifies the Master Theorem in the following way:

  If $T(n) = aT(\frac{n}{b})+f(n)$ then compare $n^{\log_b a}$ with $f(n)$

  If $f(n) < n^{\log_b a}$, then $T(n)=n^{\log_b a}$
  If they are equal, then $T(n)=f(n)\log n$
  If $f(n) > n^{\log_b a}$, then $T(n)=f(n)$

While I see the connection with the Master Theorem cases here, there isn't an intuitive explanation for where the $n^{\log_b(a)}$ term comes from. That is, if I were just looking at the recurrence relation $T(n) = aT(\frac{n}{b})+f(n)$, how would I know to compare $f(n)$ with $n^{\log_b(a)}$? Perhaps there is some connection between $n^{\log_b(a)}$ and $aT(\frac{n}{b})$ that I'm missing?

In summary, I'm looking for something of the form "here is a high level concept/understanding (eg. geometric growth/decay, competing forces), and now here is how you can derive the Master Theorem from that idea." I would be satisfied with an explanation of how to get from the replication and merging intuition posed in the second bullet point above to the three different cases of the Master Theorem but I'm also interested in any other more intuitive perspectives.

You can use repeated substitution to obtain
$$
T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots
$$
Now suppose that $f(n) = n^\gamma$. Then
$$
\begin{align*}
T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/b^2)^\gamma + \cdots \\ &=
n^\gamma \left[ 1 + \frac{a}{b^\gamma} + \left(\frac{a}{b^\gamma}\right)^2 + \cdots \right].
\end{align*}
$$

Let us assume that $n$ is a power of $b$, and that there is a base case $T(n) = C$ for some $C>0$.

There are three different cases to consider:

If $a < b^\gamma$ then the stuff in the brackets is a converging geometric series, and so $T(n) = \Theta(n^\gamma)$.
If $a = b^\gamma$ then all terms are the same. Since there are $\log_b n+1$ of them, $T(n) = \Theta(n^\gamma \log n)$.
If $a > b^\gamma$ then the terms keeps increasing, and so we can approximate $T(n)$ by the last term, which is $a^{\log_b n} C = \Theta(n^{\log_b a})$.

The condition $a \lesseqqgtr b^\gamma$ is the same as $\log_b a \lesseqqgtr \gamma$, which is how the theorem is usually presented.

The actual theorem has some extra conditions that are needed in some of the cases when $f(n)$ is not a function of the exact form $n^\gamma$, but these are just technicalities.


Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11 I got that I can get (1) followed by not (1) like this
$$ (0+2)^*1(0+2)^* $$
From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ambiguous (where I can get the same word different ways from regex) and quite long. Is there more elegant and right way to write this expression? Thanks!

Well, we know our word contains a $0$, so let's start with that:

$$0$$

Now let's assume that that $0$ is the first $0$ in the word. Then there may be arbitrary $1$s and $2$s before it, but $11$ is not allowed, thus $1$ must be followed by either a $2$ or by our zero:

$$(2 + 12)^*(10 + 0)$$

Now at the end we can have arbitrary characters, except for $11$. Thus each $1$ must be followed by a $0$ or $2$, or be at the end of the word:

$$(2 + 12)^*(10 + 0)(0 + 2 + 10 + 12)^*(1 + \lambda)$$

Here $\lambda$ is the empty string. If that isn't acceptable, we can distribute over the concatenation:

$$(2 + 12)^*(10 + 0)((0 + 2 + 10 + 12)^*1 + (0 + 2 + 10 + 12)^*)$$

Or alternatively we turn our logic around:

$$(2 + 12)^*(10 + 0)(1 + \lambda)(0 + 2 + 01 + 21)^*$$

And then distribute over the earlier concatenation:

$$(2 + 12)^*(101 + 01 + 10 + 0)(0 + 2 + 01 + 21)^*$$

These are all unambiguous, by the trick of recognizing a first zero, rather than the existence of an arbitrary one.


Where can we put primitive recursive functions in Chomsky hierarchy? I am currently studying recursion theory, but I cannot really understand where to put the Primitive Recursive functions in the Chomsky hierarchy.

In my understanding, Primitive Recursive functions contain all finite languages but are not contained in Regular expressions.
For instance, I think that $\{a^nb^n | n \in \mathbb{N}\}$ can be computed by a partial recursive function but not by a DFA. But DFA can express the always undefined function, while the primitive recursive function cannot, because they are total.

Am I completely wrong?

The Chomsky hierarchy concerns languages. Languages are total functions from $\Sigma^*$ to $\{0,1\}$, where $\Sigma$ is some non-empty finite set.

A language can be computed by a primitive recursive function if it can be computed by a total Turing machine which has a primitive recursive time upper bound. In particular, every language accepted by an LBA is primitive recursive, since we can simulate an LBA by a deterministic Turing machine running in double exponential time, and $2^{2^n}$ is primitive recursive.

In contrast, it is known that the Ackermann $A(n)$ function is decidable but not primitive recursive. Hence the language $\{ \langle n, A(n) \rangle : n \in \mathbb{N} \}$ is decidable but not primitive recursive.

Consequently, we find that primitive recursive languages sit between Type 0 and Type 1. In other words, every Type 1 language is primitive recursive, and every primitive recursive language is Type 0. Moreover, there are primitive recursive languages which are not Type 1 (for example, any EXPSPACE-complete language), and there are Type 0 languages which are not primitive recursive (for example, the graph of the Ackermann function).


How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? How to prove if P = NP if problem Π ϵ  NP-complete and Problem complement Πc ϵ NP?
OR
P = NP if NPC intersects with Co-NPC

Proving $NP=co-NP$ doesn't necessarily mean that $P=NP$. Although, the other way around is correct:
Assume $P=NP$, then $co-NP=co-P=P=NP$.


Why finding the difference between the adjacent elements of the array to find the maximum difference? I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum array but I don't get the following solution which first find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. The  problems turns into finding the maximum sum subarray of this difference array.

Here is a working example plus my comments showing where I especially don't understand the algorithm.

// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;

/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1.
    // The array will hold the difference
    // of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];

    // Now find the maximum sum
    // subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1]; // I especially don't get why we add differences
        if (max_diff < diff[i])
            max_diff = diff[i]; // and why we update the max_diff as the sum of differences
    }
    return max_diff;
}

/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr[0]);

// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);

return 0;
}

Suppose that the original array is $a_1,\ldots,a_n$. The new array is $b_i = a_{i+1} - a_i$ for $1 \leq i \leq n-1$. Note that
$$
a_j - a_i = b_i + \cdots + b_{j-1}.
$$
Hence
$$
\max_{\substack{i < j \\ a_i < a_j}} |a_j-a_i| = \max_{i<j} (a_j-a_i) = \max_{i<j} b_i + \cdots + b_{j-1}.
$$


Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular Are there any closure properties which I can use to come up with a contradiction?

$L_1 = \{a^ib^jc^k: i,j,k \ge0\} = a^*b^*c^*$ is regular.

Assume that $L = \{a^ib^jc^k: (i=1) \Rightarrow (j=k)\}$ is also regular.

Then $L_2 = \{ab^jc^k: j\neq k\} = L_1 - L$. By closure properties (difference of regular sets is regular) $L_2$ is regular. But using Pumping lemma it is not difficult to prove that $L_2$ is not regular. So we have a contradiction.

In fact we could prove that $L$ is not regular directly using Pumping lemma.


Can the same machine word sometimes be data and sometimes be code? I have a question about machine words. We have data and a code segment in the memory which is addressed. If we take a word from it and let's say it is a code (instruction), and another one is some data. Can we have a situation that some word is sometimes code and sometimes data?

If your question is "can one and the same sequence of bits sometimes represent a machine instruction and sometimes represent data" then the answer is definitely yes.

If your question is "can one and the same location in memory sometimes hold a machine instruction and sometimes hold data" then the answer is it depends on the machine architecture. The Harvard architecture strictly segregates instruction memory and data memory into physically separate parts of the computer memory, with separate data buses. However, the Von Neumann has a single common memory which can hold either instructions or data at any location.

If your question is "can one and the same location in memory be treated sometimes as an instruction and sometimes as data by one and the same program" then the answer in a Von Neumann architecture is yes, in principle. However, this leads to the possibility of writing self-modifying code, which is considered undesirable because such code is difficult to maintain and is a security risk. Therefore all modern operating systems make sure that the programs they are running have a strict segregation between data and instructions, and cannot modify their own code. This is usually implemented within the operating system itself rather than at the physcial memory level.

Note, however, that the distinction between data and code still depends on context - what is data to one program may be code for another program. For example, the output of an assembler, which the assembler treats as data, will be treated as machine instructions when the assembled program is actually being run.


How can two maps be compared? The scenario is the creation of street maps. For example, two people at Open Street map edit the same part of the map at the same time. Now the one that submits the data later should see a diff. Assume they both started with no vertex, but they had the same aerial image as a basis to create the digital map.

Let's define a street map $M$ as a set of vertices and edges $M := (V, E)$ with

\begin{align}
V &\subseteq \mathbb{R}^2\\
E &\subseteq V \times V
\end{align}

I want to compare two maps $M_1$ and $M_2$, where $M_1$ was there first. Think of two teams creatings a map from satellite images on Open Street Maps (OSM).

What I want to understand is:

How many roads (edges) are new?
How many roads (edges) were removed?
How many roads (edges) were changed?

I only could think of Dynamic Time Warping to get a score how much things have changed. But very likely no single vertex will be exactly the same, but most will be close.

What is a change?

A "change" is fuzzy in this context. If it is only about a single vertex, I would say if the geo-positions of that vertex only changed by < 10cm, it is for sure only a change. Likely also if it is less than 1m due to the lack of precision in GPS (and likely also the aerial image).

It is more complicated for streets which consist of multiple line segments and not necessarily the same number of line segments. If one knows which line segments should belong together, I would use the Douglas-Peucker algorithm to reduce the street with more line segments to have an equal amount of line segments as the second street. Then one can check if a single vertex is over the threshold to determine if a segment is different. In this case different would mean there is a "removed" and "new" segment.

But when we cannot have such a mapping I only see the possibility to check everything for change. And this does not cover the case of a change in between.

For example, obviously street (a) and street (b) have quite a bit in common, besides only point (a). They have the whole line segment AY in common.

a: A---------------------------------X

b: A---------------------Y
                          \
                           \---------Z

As a map is a geometric object, you can use from the concept of map matching in computational geometry. Also, some measures like Frechet Distance could help you to compare two maps on the plane.


Complexity of Hamilton path in directed complete bipartite graphs Finding a Hamiltonian path in a directed bipartite graph is NP-complete.

  Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete bipartite? Is this known? (In other words, what is the complexity if the digraph is semicomplete bipartite, not just any bipartite digraph)

There is a variant of the problem we wish to consider

  Problem 2 What is the complexity of the problem if the underlying graph is complete bipartite (that is, the digraph is semicomplete bipartite), and we specify the starting and ending vertex of the path?

These problems can be solved efficiently.

For Problem 2, both [1] and [2] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices.

For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see [3]) that a Hamiltonian path is found in polynomial-time via bipartite matching.

There's a good amount of research on these type of problems on tournaments and other digraphs. You will find more general results by looking at papers that cite the ones I mentioned.

[1]  J. Bang-Jensen, Y. Manoussakis, Weakly hamiltonian-connected vertices in bipartite tournaments, J. Combin. Theory B 63 (1995) 261–280.

[2] J. Bang-Jensen, G. Gutin, J. Huang, Weekly hamiltonian-connected ordinary multipartite tournaments, Discrete Math. 138 (1995) 63–74.

[3] J. Bang-Jensen, M. El Haddad, Y. Manoussakis, T. Przytycka, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Algorithmica 17 (1997) 67–87.


Why is max{n,k}= Ө(n+k) I saw this relationship in my exercise.
    max{n,k}= Ө(n+k)
Could somebody prove it?

Assuming n and k to be non-negative,
$n\leq n+k$ and $k\leq n+k$. Hence,$\max(n, k) \in \mathcal{O}(n+k)$.
Next, $n+k≤2\max(n,k)$. Hence, $\max(n,k)\in\mathcal{\Omega}(n+k)$.
Hence, we get that $\max(n,k)\in \mathcal{\Theta}(n+k)$.


How to transform an Abstract Syntax Tree (AST) to an Abstract Binding Tree (ABT)? (for machine learning fo theorem proving) I was reading the HOList paper that applies Graph Neural Networks (GNNs) to the HOL Light (HOList) data set and benchmark for ML for theorem proving. They describe their results etc but there is no code I can find or even pseudocde (algorithmic description) of how to transform an AST -> ABT. How does one do this?
This seemed like a solved problem obviously so I wanted to avoid re-inventing the wheel - especially if something already existed that is probably optimized or takes care of nuanced of the process.

References:

paper https://arxiv.org/abs/1905.10006
zulip chat about it: https://leanprover.zulipchat.com/#narrow/stream/219941-Machine-Learning.20for.20Theorem.20Proving/topic/HOList
cross post on quora: https://qr.ae/pGroph
reddit DL: https://www.reddit.com/r/deeplearning/comments/nfdkbg/how_to_transform_an_abstract_syntax_tree_ast_to/
reddit FM: https://www.reddit.com/r/formalmethods/comments/nfdqwl/how_to_transform_an_abstract_syntax_tree_ast_to/

Your referenced paper doesn't define the term "abstract binding trees"; where did you get that phrase? (I did not look at your other references; this paper was interesting enough by itself).
The paper does define a variety of transformations on ASTs by examples, but IMHO those examples are sufficient to define or least lookup the necessary algorithms.
What I interpret the paper as saying is,  "(for our GNN-based theorem prover), you can use pure ASTs, or you can use a variety of variants which perform better because they take context into account".
If you work on compiling code, you already know the value of (semantic) context over a pure context-free parsing in validating program source text (and logical formulas are just a kind of programming text).   I make this point brutally obvious here: Life After Parsing
They seem to define context in three different ways:

bidirectional links between parent and child nodes.   Having links going both directions allows context to be computed bottom up, and to have context flow from some children of a node, to be passed as context to other children.  This sounds like the value one obtains by having an attribute grammar, which has synthesized properties and inherited properties.   I didn't read the paper carefully enough to understand what information was being propagated up, or what was being propagated down, or even how their GNN accomplished this effect.   Implementing this is rather trivial: one needs child links and parent links in the nodes.

joining nodes in the AST that represent the same variable.  What this is doing is taking into account scoping rules in the language, and amounts to replacing variable names by symbol table references.  They argue that the type information associated with the symbols should be included, which you get for  "free" if your symbol table includes type information, which any serious symbol table does.  Implementing this requires that your AST processing machinery be augmented with symbol tables, and that the AST is processed to replace identifier nodes with symbol table entries (well, with the content of the appropriate symbol table entry).   This is hard to do if your langauge is complex (e.g, symbol tables for C++ will make your head explode) you need an extremely organized attack to build/use these; this is part of the reason that building compiler front ends is hard.  But for the HOL representations being used by the authors, the "symbol" tables are pretty simple and you can probably do this in an ad hoc way with a tree-scanning procedure.

Merging common subtrees honoring variable type information into single trees.  This is classically what common sub-expression elimination does.   Its apparent value in this paper is that it can dramatically shrink the size of the tree and therefore the implied amount of work it takes to process the tree. (You can get an overly compressed tree for free if you use a GLR parser which produces maximally shared subforests which happen to also include expression trees, but  you have to split out shared subtrees based on type information after the fact).  I note this looks to me not so much as context usage but "merely" size reduction.

TLDR:  The authors appear to implementing classic compiler front end building techniques and algorithms to convert ASTs into what amounts to Directed Acyclic Graphs that encode type information for different variables.
[FWIW, a generalized AST-processing engine I build called DMS has: a) bidirectional links between parent and child nodes, b) shared subtrees via GLR parsing c) symbol table definition methods, d) attribute-grammar definition/execution which is easily used to scan  ASTs to link leaves to symbol table entries. AFAICT, DMS sort of does everything this paper suggests doing.  This is because you pretty much always need at least the results of all this to process any kind of AST in a semantically sensible way].
HTH.


A particular complexity Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?

It is quasi-polynomial time. See it under examples http://en.wikipedia.org/wiki/Time_complexity


Number of addresses in a memory region So I am looking at some Operating Systems exercises and we have

  A swapping system eliminates holes by compaction. Assuming a
             random distribution of many holes and many data segments and a
             time to read or write a 32-bit memory word of 10 nsec, about how
             long does it take to compact 128 MB? For simplicity, assume that
             word 0 is part of a hole and that the highest word in memory
             contains valid data.

  The solution is : 128 x 2^20 / 4 = 2^25 memory address

      compaction time = (read + write) * # of memory access
                      = 2 x 10 x 10 ^ -9 x 2^25
                      = 671 ms

Problem is I dont understand the 128 x 2^20 / 4 = 2^25 memory address part ? How did we get 2^20 in this case? I gues the 4 is 4 bytes =32 bits so I kinda understand that.

Now in 2 x 10 x 10 ^ -9 x 2^25 what is 2 here?

A megabyte is $2^{20}$ bytes.

The factor of $2$ is because we need to count both reads and writes.


Graphs in space efficient representation Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph $G$, I want to answer whether $(u,v) \in E$. If the input graph is given by adjacency representation then I can answer whether $(u,v) \in E$ in $O(\log |V|)$ time with space complexity $O(|V| \log |V|)$.

Space complexity refers to the space taken by input in words. One word means $O(\log |V|)$ bits.

Question: Does there exists a representation of graph $G$ such that I can answer whether $(u,v) \in E$ in $o(\log |V|)$ time with space complexity $O(|V|)$?

Farzan and Monroe, Succinct Representations of Arbitrary Graphs, give such a representation with constant query time. See their Theorem 8.


What does ⊢ mean in operational semantics? I have been reading a couple of texts on operational semantics.

In [1], the evaluation of expressions is done as in this rule:

$\frac{<e_1,s>\;\Rightarrow \;n_1\;\;\;<e_2,s>\;\Rightarrow \;n_2}
{<e_1+e_2,s> \;\Rightarrow \; n_3}$,

where $n_3 = n_1+n_2$.

That is, the state $s$ is represented in a tuple with the expression to be evaluated.

But in [2] a rule for evaluation of a function as this:

$\frac{\rho\; \vdash\; e \;\Rightarrow\; v, \;\;\;\;\rho[v'/x]\;\vdash\;e \;\Rightarrow\; v}
{\rho\; \vdash \;F(e) \Rightarrow v}$

I am confused: why in the first case, the state $s$ was passed along with the expression as a pair, and in the second case, the environment $\rho$ was not (it was to the left of $\vdash$). Does $\vdash$ here have the same meaning as in formal logic? Are the two notations that I have shown (using a pair/tuple and using $\vdash$) interchangeable in operational semantics?

In this text ([2]), the author writes, before the first time he uses $\vdash$,

  In a given environment an expression will evaluate to a numeral. We will write this as $\rho \; \vdash\; e \;\Rightarrow \;v$

But he doesn't explain why, and in another text ([1]) the same author uses the pair notation for the same purpose.

[1] Matthew Hennessy, "Semantics of Programming Languages (CS3017), course notes"
[2] Matthew Hennessy, "The Semantics of Programming Languages: an elementary introduction using structural operational semantics"

This is something that I think is not explicitly pointed out or not pointed out with enough emphasis in many, even introductory, CS/type theory/logic texts.

$\vdash$ doesn't mean anything.

Instead, in this example, the three place relation $- \vdash - \Rightarrow -$ is what has meaning.

Except that was a lie. It doesn't a priori have meaning either.  That relation is what is being defined.  $- \vdash - \Rightarrow -$ is just a (mixfix) name.  It does, of course, have some informal meaning we are hoping to capture with this definition, and after it is defined it does have meaning.

In most cases, such relationships are being inductively defined which makes them identical to inductive families in a dependently typed language.  For example, here are the rules for the arithmetic language fragment from figure 3.2 in section 3.1:
$$
\frac{}{\langle n,s \rangle \Downarrow n} \qquad
\frac{\langle e_1, s\rangle \Downarrow n_1 \qquad \langle e_2, s\rangle \Downarrow n_2}{\langle e_1 + e_2, s \rangle \Downarrow n_1+n_2} \qquad
\frac{}{\langle \mathtt{L}, s \rangle \Downarrow s(\mathtt{L})}
$$

and here's Agda code for this fragment:

data Expr : Set where
    Num : Nat -> Expr
    Add : Expr -> Expr -> Expr
    Lookup : Label -> Expr

data Eval : (e : Expr) (s : Label -> Nat) (n : Nat) -> Set where
    EvalNat : {n : Nat}{s : Label -> Nat}
        -> Eval (Num n) s n
    EvalAdd : {e1 e2 : Expr}{n1 n2 : Nat}{s : Label -> Nat}
        -> Eval e1 s n1
        -> Eval e2 s n2
        -> Eval (Add e1 e2) s (n1+n2)
    EvalLookup : {l : Label}{s : Label -> Nat}
        -> Eval (Lookup l) s (s l)

A proof of a statement like $\langle 3+4,s \rangle \Downarrow 7$ looks like:

threePlusFourIsSeven : {s : Label -> Nat} -> Eval (Add (Num 3) (Num 4)) s 7
threePlusFourIsSeven = EvalAdd EvalNum EvalNum

Rule induction, which is the topic of section 2.3, is induction over data types like this.

I hope at this point that you can see that the answer to:

  Are the two notations that I have shown (using a pair/tuple and using ⊢) interchangeable in operational semantics?

is "yes, but only because whenever you see such notation it is being or has been defined, and we can use whatever notation we want to mean whatever we want if we define it."  In other words, nothing is stopping us from having used the syntax $s \vdash e \Rightarrow n$ instead of $\langle e, s\rangle \Rightarrow n$. We'd just be defining a relation named $- \vdash - \Rightarrow -$ instead of being named $\langle -,- \rangle \Rightarrow -$.

That said, there are (unwritten) conventions – naming conventions no less – that are commonly abided by.  So $\vdash$ is normally used to separate some "context" or "environment" from "terms".  The tuple notation is often used for state components because we (denotationally) model state as a function from the old state to the output plus the new state.  If we also have input, this results in a function (Input, State) -> (Output, State).  This intuition gets reflected in the naming of the operational semantics, as in, for example, figure 3.6 which includes rules like $\langle \mathtt{skip};C_2, s\rangle \rightarrow \langle C_2, s\rangle$.  Nothing stops us from writing that $s \vdash \mathtt{skip};C_2 \rightarrow s \vdash C_2$, but I think you can agree that that is harder to read.

I got around to posting a blog article that goes into this notation in more detail.


Complexity of a knapsack variant Consider the following traditional integer knapsack problem:

$\max \sum_{i=1}^k p_i \cdot x_i\\
\text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\
x_i \in \{0,\ldots,k_i\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\{1,\ldots,k\}$ such that for each pair $I_1,I_2 \in \mathcal{I}$ it either holds that $I_1 \subseteq I_2$ or $I_1 \supseteq I_2$ or $I_1 \cap I_2 = \emptyset$. For each of these subsets $I_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum_{i \in I_j} x_i \leq \mu_j$

for some number $\mu_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k_i$ are still not polynomially bounded).
Accordingly, if the maximum amounts $k_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?

It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T[p,i]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I_j$ are consecutive. Since $I_j$ are disjoint, when dealing with $x_i$, we only need to consider  how many items in $I_j$ can be picked. Thus, for each $p$ and $i$, let $D[p,i,q]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.


Can CYK Parsing algorithm generate the parsing tree in O(n^3)? I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free Grammar in $O(n^3)$.

But this does not make sense because I cannot see how NonDeterministic Context Free grammar can be parsed in $O(n^3)$. Then, while reading Hopcroft and Ullman (2006) pages 304 I found:

  In $O(n^3)$ time the algorithm constructs a table that tells whether w is in L $\in$ Note that when computing this running time the grammar itself is considered fixed and its size contributes only a constant factor to the running time which is measured in terms of the length of the string w whose membership in L is being tested.

So, the correct affirmation is: There is no way a NonDeterministic Context Free Grammar parsing tree can be built in $O(n^3)$ time, only its word membership can be determined in $O(n^3)$ time by the CYK algorithm. NonDeterministic Context-Free Grammars Parsing Trees can only be built in Exponential Time (worst case)?

Related:

Chomsky Hierarchy and P vs NP
What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

It depends what you mean by build a parse tree.

You can build a parse forest in $O(n^3)$ time and space. The forest represents all parse trees, even an infinite number of parse trees, because it is a graph, not a tree. From a parse forest, it is possible to produce a single parse tree in time linear to the size of the forest, and it is possible to iterate through all possible parses.

So if you either consider that "build a parse tree" means "find one of the possible parses" or if you consider that it means "build a datastructure which represents all possible parses", then you can certainly do that with a CYK grammar in $O(n^3)$.

If, on the other hand, you intend "build a parse tree" to mean "build all parse trees for a sentence", then it is not limited to exponential time; it is easy to write a grammar with an infinite number of possible parses for certain sentences.


Prove that two different concatenations of relations are equivalent I've had this question on my exam today and I couldn't figure it out, I would like to know the answer.
The question:

Given relations $R$, $S$ on a set $U$.
$R$ is transitive, $S$ is reflexive.
Prove that $(R;S;R)^2$ is a subset of $(R;S)^3$.

Partial answer of mine:

By using associativity you get an equivalent question of:
Prove that $R;S;R;R;S;R \subseteq R;S;R;S;R;S$.
By monotonicity you have that $R;S;R \subseteq S;R;S$.
Then I took $(x, y) \in R;S;R$, so there exist $a, b \in U$ such that $xRa \land aSb \land bRy$.
Now I need to conclude that $xSa \land aRb \land bSy$.

Here I am stuck, nowhere I see how I should be using that $R$ is transitive and $S$ is reflexive, and I know they are obvious hints. I tried using them directly, proving by contradiction, but I am just stuck.

This is best carried out using notations from algebra of relations.

You're asked to prove $RSRRSR \leq RSRSRS$. That $R$ is transitive means $RR\leq R$, so  $RSRRSR \leq RSRSR$ by monotonicity of composition. That $S$ is reflexive means $I\leq S$, where $I$, the identity relation, is neutral element for composition: $I\leq S$ entails $(RSRSR)I\leq (RSRSR)S$ (monotonicity of composition again). Finally, you have

$(RSR)^2 = RSRRSR \leq RSRSR = RSRSRI \leq RSRSRS = (RS)^3$

as required.


Which implementation for the Maclaurin Series for the cosine function is better? First, sorry if this post is off-topic. I consider it too analytic for stack overflow.

  In Numerical Analysis subject I must explain which one is better (has less error).
  The recursive implementation seems to be better with the inputs I have used, but I don't know the reason.

  Can someone explain to me which one is better and why? Having in mind round-off error and loss of significance using doubles.

Iterative implementation:

$$\cos{x} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ ... \ + (-1)^n\frac{x^{2n}}{(2n)!}$$

Recursive implementation:

$$y_{n+1} = (-1)^n$$
$$y_{k} = \frac{y_{k+1}x^2}{(2k)(2k-1)} + (-1)^{k-1}, \  \text{for} \  k=n,\ n-1,\ n-2,\ ... \ 1$$

The main problem with the iterative approach is that the terms of the series get smaller and smaller with increasing index, so if you sum terms from 1 up, you eventually end up adding values of very small magnitude to accumulated sums of much larger magnitude.  When done using floating-point arithmetic, that's pretty much the same as simply discarding terms after some point.  The recursive approach sums the same terms, but in reverse order, so all the small terms get a chance to accumulate into larger sums before the larger terms get added; this lets the smaller terms actually contribute to the final sum.

I suspect that the way the recursive approach builds up the larger factorials in small steps also helps produce more accurate sums.


Language of Turing machines that loop on all inputs, recognizable? Prove that the language Loop Turning Machine =  {  < M > | M is a TM that loops on all inputs}  is recognizable.

I feel like $M$ would never halt.  To make $M$ recognizable it needs to accept or reject.  Do I need to establish a decider?

EDIT:

Can I say that a halting Turing Machine $M$ is a machine for which  exists a word $w$ such that $M$ halts on $w$?
This makes the language recognizable but the machine may go on forever if executed.

$L$ isn't recognizable. We'll first establish a couple of preliminary results

I. $\overline{L}$ is recognizable

The complement of $L$,
$$
\overline{L}=\{\langle M\rangle\mid M \text{ halts on at least one input}\}
$$
is recognizable. Define a recognizer TM as follows:

R(<M>) =
   for n = 1, 2, 3, ...
      for each x in {x_1, x_2, ... , x_n}   // in some canonical order
         run M on x for one move
         if M halts
            return accept

It should be clear that $R$ accepts all and only those $\langle M \rangle$ for which $\langle M \rangle\in \overline{L}$ and so $\overline{L}$ is recognizable. Now if $L$ were also recognizable, then we could use the two recognizers to make decider for $L$, which brings us to our second result.

II. L is undecidable

If $L$ were decidable, then $\overline{L}$ would also be, and conversely. If that were the case, we could define a reduction from the known undecidable language
$$
HALT = \{(\langle M\rangle \mid M \text{ halts on input }w\}
$$
to $\overline{L}$ by the mapping
$$
(\langle M\rangle, w)\rightarrow M_w
$$
where, as babou has already noted,

M_w(y) =
   erase the input y
   write w on the input tape
   simulate M on w

Now observe that $M$ halts on $w$ $\Longleftrightarrow$ $M_w$ halts (on every input $y$, in fact) $\Longleftrightarrow$ $M_w\in \overline{L}$. In summary, if $L$ were decidable, then we could $L$'s decider (reversing the roles of accept and reject) to decide the halting problem, a contradiction.

Now we can show that $L$ is not recognizable. If it were, then, using (I) we could conclude that $L$ was decidable, a contradiction to result (II).