Are number of states in a NFA same as Pumping length? So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? Are NFA's able to give us minimum pumping length?

For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?

Here is a counterexample. Consider the language $L = 1^* + 0^*1^n$. The minimal NFA for $L$ has $n+C$ states for some constant $C$, but every word can be pumped, so the pumping length is 1.


Hamming Weight to find the sum of 1 bits in the range between A and B inclusive I am trying to find the sum of 1 bits in the range between A and B inclusive,

where -2^31 <= A <= B <= 2^31 - 1

Input Format:

The first line contains the number of test cases T (<=1000). Each of the next T lines contains two integers A and B.

I have used Hamming Weight algorithm to solve this problem. Though I have used memoization version of Hammnig Weight algorithm, it runs out of time.

mf = [-1 for i in range(65536)]

def count_1s(x):
    """It counts the number of 1 bits in an given 32 bit integer"""
    if (x > 65535):
        return count_1s(x&0xFFFF) + count_1s(x>>16)
    elif (mf[x] != -1):
        return mf[x]
    else:
        count = 0
        while(x > 0):
            x &= (x-1)
            count += 1
        mf[x] = count
        return mf[x]

t = int(input())

for i in range(t):
    a = [int(number) for number in input().split()]
    count = 0

    for j in range(a[0], a[1]+1):
        if (j < 0):
            count += 32 - count_1s(-j-1)
        else:
            count += count_1s(j)

    print(count)

So I am in a need of improving this algorithm. Are there any ways to improve this algorithm? or I should use some other algorithm to solve this problem?

Link for Input:

https://hr-testcases.s3.amazonaws.com/56/input02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339544&Signature=5bf736TpbPUWcQZ%2FbGijtBHbVeM%3D&response-content-type=text%2Fplain

Required Output:

https://hr-testcases.s3.amazonaws.com/56/output02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339722&Signature=NUwWGdUVsvttRWx0janzsxncDtY%3D&response-content-type=text%2Fplain

The basic idea is not to manually go over all numbers from $A$ to $B$. For example, suppose $A = 0$ and $B = 2^n-1$. The $k$th bit of a number in $\{0,\ldots,2^n-1\}$ is $1$ exactly half the time, so the total number of $1$s is $n2^{n-1}$. Similarly, if $A = x2^n$ and $B = x2^n + 2^n-1$ then the number of $1$s is $n2^{n-1} + 2^nH(x)$, where $H(x)$ is the Hamming weight of $x$. In the general case, you have to decompose the range $[A,B]$ into a small number of ranges of the form just described. You should be able to do this with at most $2n$ or so ranges, where $n$ is the length of $B$ in bits.


Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap? In the solution to problem 2 of this exercise sheet:

  The height of $n$-node Binomial  Heap  is  always $O(\log{n})$. Show
  that this  is  not  the  case for Fibonacci Heaps by exhibiting, for
  any positive integer $n$ a sequence of Fibonacci-heap operations that
  creates a Fibonacci heap consisting of just one tree that is a linear
  chain of $n$ nodes.

it is stated that

  We obtain a chain with two elements where $x$ is the root,
  having degree $1$. Thus the chain of height two and the chain of height $k$ are consolidated.

However, in this presentation, it is stated that:

  Delete $\min$.

  Delete $\min$; meld its children into root list; update $\min$.
  Consolidate trees so that no two roots have same rank

which is not the case with $2$ and $k$.

So why are they consolidated?

Page 8 defines rank:

  rank(x) = number of children of node x

So rank is not the height of the tree. With that, each chain, regardless of its length, has rank 1 and will be consolidated with any other chain.

But in most cases, rank defines the height, so why is it different here? The Reason is, it is simpler to implement. For the number of children, you just need the size of the direct children of a node, in many cases just some array.size, often already saved in a field.

But for the height you'd need additional calculations and fields, which can get complicated, especially for functions like decrease-key (which would make it not O(1) anymore).


What does tilde mean, in big-O notation? I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.

I have searched the internet and wikipedia, but I can't find what this tilde signifies in big-O/Landau notation. In the paper itself I have also found no clue about this.  What does $\tilde{O}(\cdot)$ mean?

It's a variant of the big-O that “ignores” logarithmic factors:

$$f(n) \in \tilde O(h(n))$$

is equivalent to:

$$ \exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right) $$

From Wikipedia:

  Essentially, it is big-$O$ notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the “nitpicking” within growth-rates that are stated as too tightly bounded for the matters at hand (since $\log^k n$ is always $o(n^\varepsilon)$ for any constant $k$ and any $\varepsilon > 0$).


Expectation of $\langle s,x \rangle^2$ I'm studying dimensionality reduction (SVD in particular), and I saw the following question:

  Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ ,  where
  $s$ is a $d$-dimensional random vector with entries drawn uniformly
  independently from $[-1,1]$.

What is the value of $\mathbb E[F(x)^2]$?

I'm starting now from zero, so I need to study more. The exercise asks for a formal proof, but I wish to just understand the philosophy.

I see many questions in which valued are drawn uniformly and independently from $[-1,1]$. Is this distribution used due to its symmetrical range? Is the expectation in this range often $1/2$?

Let us assume that each entry of $s$ is drawn independently from some distribution $\mathcal{D}$ whose expectation is $0$. Then
$$
\mathbb{E}\left[\left(\sum_{i=1}^d s_i x_i\right)^2\right] =
\sum_{i=1}^d x_i^2 \mathbb{E}[s_i^2] + \sum_{i \neq j} x_i x_j \mathbb{E}[s_i s_j] = \|x\|^2 \mathbb{V}[\mathcal{D}],
$$
since $\mathbb{E}[s_is_j] = \mathbb{E}[s_i]\mathbb{E}[s_j] = 0$ due to independence.

In your particular case, $\mathcal{D}$ is the uniform distribution over $[-1,1]$, whose variance is
$$
\frac{1}{2} \int_{-1}^1 x^2 \, \mathrm{d}x = \left. \frac{x^3}{6} \right|_{-1}^1 = \frac{1}{3}.
$$


Time complexity to find Median of Medians I recently wrote my Grad school Admission test few days back and the following question appeared in the test.
There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ..., An contains 'n' distinct elements. There are no common elements between any two arrays. The worst case time complexity of computing the median of medians of A1, A2, ..., An is:

O(n)
O(n log(n))
O(n^2)
Ω(n^2 log(n))

Approach 1: Compute the median using Counting Sort for all arrays and then store the median values in a separate array. Once again apply Counting Sort on the newly created array having median values and compute the median.
Time Complexity = O(n^2)
Space Complexity = O(n)

Approach 2: Instead of Counting sort, use any other algorithm with constant space complexity, thereby yielding a total Time complexity of O(n^2 log(n)).

  According to space-time trade-off, a problem or calculation can either
  be solved in less time by using more storage space (or memory), or by
  in very little space by spending a long time.

Approach 1 favours time and Approach 2 favours space. I believe that space should be favoured as the size of Array will be very high on performing Counting sort when the range of values is high. Thus I marked Ω(n^2 log(n)) in test. However, my mentor and one my acquaintances say time should be favoured and O(n^2) is the correct answer. So, my question is whether to favour time or space?

The running time of counting sort isn't $O(n)$, in general.  If you are guaranteed that every element of the array is an integer in the range $1..n$, then the running time of counting sort is $O(n)$; but if you aren't guaranteed that, in general the running time could be much worse.

Since the question doesn't make any guarantees that the elements of the array will be in a specified range, you can't claim that counting sort will have $O(n)$ running time, and your analysis of Approach #1 is not correct.

Approach #2 does indeed provide an algorithm with running time $O(n^2 \log n)$.  However, that's not the best algorithm.  There are better algorithms, which can find the median in $O(n)$ time.  So, the correct answer is $O(n^2)$ ... but not for any of the reasons listed in your question.  See https://en.wikipedia.org/wiki/Selection_algorithm and Find median of unsorted array in $O(n)$ time.


NP-Hard problems that are not in NP but decidable I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable?

For example, the halting problem is NP-Hard, not NP-Complete, but is undecidable.

I believe that this means that it is a problem that a solution for can be verified but not in polynomial time. (Please, correct this statement if this is not the case).

By the nondeterministic version of the time-hierarchy theorem, we have $\mathsf{NP} \subsetneq \mathsf{NEXP}$, where $\mathsf{NEXP}$ is the class of problems solvable in non-deterministic exponential-time. Thus it suffices to consider any problem which is $\mathsf{NP}$-hard and in $\mathsf{NEXP}$, but not in $\mathsf{NP}$. For instance, we may consider any $\mathsf{NEXP}$-complete problem, such as

3-colourability of graphs described by succinct circuits — or any other NP-complete problem on graphs — where a "succinct circuit" is a format for representing very large graphs at the input: instead of explicit representation of a graph e.g. by adjacency lists, we instead provide a circuit computing some function $f: \{0,1\}^{n} \times \{0,1\}^n \to \{0,1\}$ which computes the coefficients of a $2^n \times 2^n$ adjacency matrix.
(Non-)equivalence of two regular expressions, where the Kleene star is replaced by squaring (repeating a sub-pattern exactly twice, rather than zero or more times), and where we ask whether two such regular expressions represent different sets of strings.

Note that in the latter case, if we take regular expressions as we are used to considering, including the Kleene star, the resulting problem is $\mathsf{EXPSPACE}$-complete: because we have the containments $\mathsf{NP} \subset \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}$, this is still a decidable problem which is $\mathsf{NP}$-hard, and not in $\mathsf{NP}$.


Parser theory: How to systematically compute FOLLOW sets? Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have computed the FIRST sets.

For the following grammar:

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' |  ε
F -> (E) | id

I found that the FIRST sets are:

FIRST(E) = { (, id }
FIRST(E') = { + ,  ε }
FIRST(T) = { (, id }
FIRST(T') = { *,  ε }
FIRST(F) = { (, id }

When it comes to computing the FOLLOW sets, I am trying to use the following rules:

1. $ goes into the set FOLLOW(S) where S is the start symbol.
2. If A -> aBb, then (FIRST(b) - { ε }) is in FOLLOW(B).
3. If A -> aB then everything in FOLLOW(A) is in FOLLOW(B)
4. If A -> aBb and ε is in FIRST(b), then everything in FOLLOW(A) is in FOLLOW(B).

Obviously, the step I am most certain here is that

FOLLOW(E) contains $, based on rule 1. But everything after that, I seem to have a hard time following a pattern on how to systematically compute the FOLLOW sets. For example, to compute FOLLOW(E), how are we supposed to approach this?

E -> TE', looks like A -> aB , so everything in FOLLOW(E) is in FOLLOW(E'). Where to go from here? Do I compute FOLLOW(E')? Then going to FOLLOW(E'):

E' -> + TE'... looks  like A -> aBb. Then that means FIRST(E') - {  ε } is in FOLLOW(T). So I do know that { + } is in FOLLOW(T).

As you can see, with the way I have interpreted this, I am going around all over the place computing the FOLLOW of another production. Ultimately, I end up losing track on what terminal symbols go into which follow set. :(

I am for sure misunderstanding something here.

What is the right approach/ordering to compute the FOLLOW sets?

The simple way to do it is the same as the simple way to compute FIRST sets, using a least fixed-point algorithm in which a set of inclusion rules are applied repeatedly until a fixed-point is reached:

Initialise all the sets to empty.
For every production in order, use the rules to add elements into the sets.
(As a slight efficiency, rule 2 only needs to be applied on the first pass. I didn't apply that to the trace below.)
If any set was modified during step 2, do it again.

So, here are the productions in order (I added the missing $*$ to $T'$, and inserted an augmented start rule $S$, which avoids the need for your special case rule 1):

$$\begin{align}
S &\to E\; $ \\
E &\to TE' \\
E' &\to +TE' \mid \epsilon \\
T &\to FT' \\
T' &\to *FT' \mid \epsilon \\
F &\to (E) \mid id
\end{align}$$

Set all the $FOLLOW$ sets to $\{\}$
First pass. I left out productions like $F\to id$ which don't match any of the rules.
$$ \begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &FOLLOW(E) = \{ \$ \}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &FOLLOW(E') = \{ \$ \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + \$ \}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * \}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &FOLLOW(T') = \{ + \$ \}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * + \$\}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &FOLLOW(E) = \{ ) \$\}\\
\end{array} $$
There were various changes, so we repeat step 2.
(Step 2, second pass)
$$\begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &\text{no change}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &FOLLOW(E') = \{ )\$ \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + )\$ \}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &FOLLOW(T') = \{ + ) \$ \}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * + ) \$\}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &\text{no change}\\
\end{array} $$
(step 3, second pass) There were some more changes. Once again.
(Step 2, third pass)
$$\begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &\text{no change}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &\text{no change}\\
\end{array} $$

So the $FOLLOW$ sets are:
$$\begin{align}
FOLLOW(S) &= \{\}\\
FOLLOW(E) &= \{ )$ \}\\
FOLLOW(E') &= \{ )$\}\\
FOLLOW(T) &= \{ + ) $\}\\
FOLLOW(T') &= \{ + ) $\}\\
FOLLOW(F) &= \{ * + ) $ \}
\end{align} $$

That's a very simple grammar, of course. You might want to try it out with a more complicated one, although it is typical that it terminates after very few iterations and that many of the steps are obvious no-ops.


The purpose of grey node in graph depth-first search In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (discovered and all its neighbours was visited). What is the purpose of this distinction? It seems that DFS algorithm will never visit a visited vertex regardless of whether it's grey or black.

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to explicitly make these distinctions for better understanding.

Of course, there are actual uses of these colors. Consider a directed graph $G$. Suppose you want to check $G$ for the existence of cycles. In an undirected graph, if the node under consideration has a black or grey neighbor, it indicates a cycle (and the DFS does not visit it as you mention). However, in case of a directed graph, a black neighbor does not mean a cycle. For example, consider a graph with 3 vertices - $A, B,$ and $C$, with directed edges as $A \to B$, $B \to C$, $A \to C$. Suppose the DFS starts at $A$, then visits $B$, then $C$. When it has returned to $A$, it then checks that $C$ has already been visited and is black. But there is no cycle in the graph.

In a directed graph, a cycle is present if and only if a node is seen again before all its descendants have been visited. In other words, if a node has a neighbor which is grey, then there is a cycle (and not when the neighbor is black). A grey node means we are currently exploring its descendants - and if one such descendant has an edge to this grey node, then there is a cycle. So, for cycle detection in directed graphs, you need to have 3 colors. There could be other examples too, but you should get the idea.


Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$ So, I'm refreshing my undecidablility knowledge, and I came across this statement reading about Post's Correspondence Problem on Wikipedia:

  A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.

I'm a little confused about how to parse this sentence formally.

Let $POST(n) = \\ \{((a_1, b_1),\ldots, (a_n, b_n) \mid a_i, b_i \in \{0,1\}^*, \\ \exists j_1 \ldots j_m \ldotp a_{j_1} \cdots a_{j_m} = b_{j_1} \cdots b_{j_m}  \}$

Which of the following is true?

$\forall n \ldotp n \geq 5 \implies POST(n)$ is undecidable
$\bigcup_{n \geq 5} POST(n)$ is undecidable

i.e. if I'm showing that a problem is undecidable, can I show that that problem can be used to solve any 5-tile PCP instance? Or am I not allowed to make such assumptions on the number of tiles?

It is the first version: $\forall n,\,n\geq 5\Rightarrow\,POST(n)$ is undecidable. The reason for the number $5$ is explained in the article of Turlough Neary cited in wikipedia page. The case $n=2$ is proven in

A. EHXENFEUCHT, J. KARHUMAKI, G. ROZENBERG, "THE (GENERALIZED) POST CORRESPONDENCE PROBLEM WITH LISTS CONSISTING OF TWO WORDS IS DECIDABLE",
Theoretical Computer Science 21 (1982) 119-144.


Can I use ellipses in first order logic I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is:

$$ \forall x \; \exists y_1, y_2, \dots , y_{n-1} \; (x \neq y_1) \land (x \neq  y_2) \land \dots  \land (x \neq y_{n-1})$$

I'm not sure if this is a valid first-order logic sentence or not.

Strictly speaking, your statement is invalid because $\ldots$ is not part of the syntax of first-order logic. However, your statement is an abbreviation of a statement in first-order logic. For example, when $n = 3$, your statement is an abbreviation of the bona fide statement
$$ \forall x, \exists y_1, y_2 (x \neq y_1) \land (x \neq y_2). $$
As long as you understand this difference, you can use the statement. Your statement is stated in the metalanguage, and it corresponds to a bona fide statement of the language.

Here is a similar example. The following defines a number, for every integer $n \geq 1$:
$$
\overbrace{11\cdots 1}^{\text{$n$ times}}
$$
For example, when $n = 5$, this number is $11111$. While the notation above, which belongs to the metalanguage, is not in itself a valid number, for every specific $n$ it satisfies a valid number. You can think of it as a pattern, a number scheme (in your case, a statement scheme), or a function that takes $n$ and outputs a number (in your case, a statement).

That said, your statement (for every $n > 1$) states that there are at least two different objects in the universe. So while it is a valid statement, it doesn't state what you intended it to.


What is the $\mathcal O$ of subtraction-based GCD algorithm? Subtraction-based algorithm for finding the greatest common divisor works like this:

For two integers a and b (a > 0, b > 0),
if a > b, then gcd(a, b) = gcd(a-b, b)
else if b > a, then gcd(a, b) = gcd(a, b-a).
else if a = b gcd(a, b) = a

What is the $\mathcal O$ of this algorithm?

Suppose that $a,b$ are the two input numbers. At each step of the algorithm, the sum $a+b$ decreases, since (assuming $a > b$), the new numbers are $a'=a-b,b'=b$, and $a'+b'=a < a+b$ (since we stop when $b=0$). Thus the algorithm terminates in at most $a+b$ steps. This is almost tight: if $b = 1$, then the algorithm terminates in $a$ steps.

Summarizing, on inputs $a,b$, the number of steps (or arithmetic operations) is at most $a+b$, and could be as bad as $a$. In terms of the length $n$ of the input (number of bits needed to represent it), the number of operations is at most $O(2^n)$ (since $a,b \leq 2^n$), and could be as bad as $\Omega(2^n)$ (when $a = 2^n,b=1$). Thus the worst-case running time (as measured by number of steps) is $\Theta(2^n)$, where $n$ is the input length.


Is vmlinux a virtual machine? From Wikipedia,

On Linux systems, vmlinux is a statically linked executable file that contains the Linux kernel

Does that mean vmlinux is a virtual machine that runs Linux? I am really confused.

vmlinux is the executable file that is generated when building the Linux kernel. This isn't a normal executable file that would be generated as a result of compiling a program using, say, gcc.
As Wikipedia suggests, this executable needs to be further processed to be made bootable, but this is the essentially the executable image of the kernel.

Does that mean vmlinux is a virtual machine that runs Linux?

No, the 'vm' here stands for 'virtual memory'. From Wikipedia,

With the development of virtual memory, kernels that supported this feature were given the vm- prefix to differentiate them. The name vmlinux is a mutation of vmunix.

What is this vmlinux executable good for? Well, for starters, it can be made bootable and then booted on a physical computer.
You can also use this executable to run a virtual machine using qemu. Then, you can debug the kernel that is running in the virtual machine using gdb.


Why is non-determinism a useful concept? An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state.

When we are trying to model real systems, why include nondeterminism in Automata theory?

Yes, you are correct computers are deterministic automate. Non-deterministic models are more useful for theoretical purpose, sometime the deterministic solution is not as obvious to the definition(or say problem statement) and so little hard to find solution. Then one approach is that first design a non-deterministic model that may be comparatively easy to design and then try to convert it into a deterministic one. Below, I have tried to demonstrate what I mean with an example. Consider regular expression:

(01)*01(0 + 1)*

Now suppose, if you are asked to draw DFA for the language generated by above RE.

With my knowledge of designing FAs, I know that (1) when a * present in regular expression indicated I need corresponding  loop in  FA  (2) concatenate operations like a.b means something like: (q0)─a→(q1)─b→(q2).

So, at my fist attempt I would draw an NFA like:

Thought this is not a deterministic solution but looks very simple FA that can be easily designed using the given regular expression.  My kind-of-analogy to show similarity between the above regular expression and my NFA is as below:

The loop at state  q0 should be for (01)*
01 (after (01)*) gives (q0)─0→(q1)─1→(q2)
(0 + 1)*  gives a self loop at state q2 for label 0, 1

According to my analogy I think the FA I drawn above is comparatively simple to draw from given RE. And luckily in class of finite automata every Non-deterministic model can be converted into an equivalent deterministic one. We have algorithmic method to convert an NFA into DFA. So I can easily convert above NFA into a DFA:

Other part is unfortunately this is not always possible to convert a non-deterministic model into deterministic one, for example class for deterministic push down automate is subset of class of deterministic push-down automate "check venn diagram" and you can't always convert an NPDA into a PDA.

Usually when it is not possible to convert a non-deterministic solution into deterministic one then with the help of non-deterministic solution we define deterministic solution in sub-domain (or say partial domain) instead of complete domain. Or we define solution in some other ways (e.g. greedy approach) that of-course may not give you an optimal solution.

Sometimes non-determinism is an effective mechanism for describing some complicated problem/solution precisely and effectively, for an example non-deterministic machines can serve as model of search-and-backtrack algorithm (read: How string process in non-deterministic model using backtrack). Oppositely deterministic models better represents efficient, minimized and less-redundant solutions.

Here I would also like to quote from Wikipedia Use of Nondeterministic algorithm:

  In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.

  A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.

As @keshlam also mentioned in his comment: "Nondeterminism" is in practice used to refer to any unpredictability in the outcome of some process. For an example, Concurrent programs exhibit non-deterministic behaviour - two executions of the same program with the same input can produce different results (if concurrency control mechanism are not applied ). Read more about this in "Usefulness Of Non Determinism".

I would also suggest you to read following links:
1.  What is the difference between non-determinism and randomness?
2. 9.2.2 Nondeterministic vs. Probabilistic Models: (a). Nondeterministic: I have no idea what nature will do. (b). Probabilistic: I have been observing nature and gathering statistics.
3. Nondeterministic programming


Description and semantics of program graphs I'm working on a question which gives me a program graph and tells me to give a mathematical description of it. I'm aware that a program graph PG is a tuple

$(Loc, Act, Effect, \rightarrow, Loc_0, g_0)$

This is the question I'm trying to answer:

So far for $PG_1$ (one of the 2 transition systems) I have:

$Loc = \{k_1, k_2, k_3\},$ with  $Loc_0 = \{k_1\}$

$Act = \{\alpha_1, \beta_1, \gamma_1\}$

$Effects = \{Effect(\alpha_1, \eta) = \eta[x := x + 1]$,
$Effect(\beta_1, \eta) = \eta[y := y - 1]$,
$Effect(\gamma_1, \eta = \eta[y := y + 2]\}$

$\rightarrow = \{(k_1, \alpha_1, k_2), (k_2, \beta_1, k_3), (k_3, \gamma_1, k_1)\}$

$g_0 = $ ?

I'm aware that $g_0$ is the starting condition, but I'm not sure what it is in this case? Also for $\rightarrow$ I assumed this was done the same was it is in Transition Systems, if somebody could clarify whether or not this is the correct way to do it I would be really grateful.

Thanks in advance for any help.

Definitions

From "Principle of Model Checking" By Joost-Pieter Katoen and Christel baier:

  A program graph over a set Var of typed variables is a tuple $(Loc, Act, >Effect, \rightarrow, Loc_0, g_0)$ where:

  $Loc$ is a set of locations
  $Effect: Act \times Eval(Var) \to Eval(Var)$ is the effect function
  $\rightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the condition transition relation
  $Loc_0 \subseteq Loc$ is a set of initial locations
  $g_0 \in Cond(Var)$ is the initial condition

It is further noted that:

  $Eval(Var)$
  denote the set of (variable) evaluations that assign values to variables

  $Cond(Var)$ is the
  set of Boolean conditions over Var

Given these definitions, your definitions of $Loc$, $Act$ and $Effect$ are correct

Transitions

So, according to these definition the conditional transition relation must be:

$\rightarrow =\{(k1,α1, ? ,k2),(k2,β1, ?, k3),(k3,γ1, ?, k1)\}$

where each questionmark is a tautology, ie something always true (as there are no conditions in the figure). As the authors note,

  If the guard is a tautology ... we simply write $(l, \alpha, l') \in \rightarrow$.

So in conclusion your definition of $\rightarrow$ is correct

Furthermore, $Cond(Var)$ must consist of tautologies.

Initial Condition

To me it seems that there are no given initial conditions on the variables $x,y$ so $g_0$ must simply be a tautology as $g_0 \in Cond(Var)$. It seems undefined what specific tautology $g_0$ must be, but any tautology will do, if you apply the Structural Operational Semantics given in the book, as any location satisfies any tautology.

Execution and Traces

Both concepts are defined in the context of Transition Systems.

Executions:

  Executions  are alternating sequences consisting of states
  and actions

And traces:

  Thus, rather
  than having an execution of the form $s_0
\rightarrow^{a_0} s_1
\rightarrow^{a_1} s2$ . . . we consider sequences of the
  form $L(s_0)L(s_1)L(s_2)$ . . . that register the (set of) atomic propositions that are valid along
  the execution. Such sequences are called traces.

For reasoning about executions and traces you thus need to look at the transition system induced from the program graph (by the structural operational semantics given in the book).


Less used data (1 byte) in memory address holding 4 bytes I need to store two distinct variables of 1 byte size in memory.

My memory system stores 4 bytes at one address; therefore, you cannot address byte 3 directly, and you have to logically access it after all 4 bytes are fetched of that address (correct me if I'm wrong please).

So, if I assign the following two variables: char var1 = "a" and char var2 = "b",

Will my system store them in memory at two different addresses?

Will 3 bytes in each of those addresses be useless (i.e., will the two variables occupy 8 bytes of memory)?

So your computer has 32 bits as the smallest addressable unit.

Your compiler has two choices: It can store var1 and var2 in two different sets of 8 bits in the same 32 bit unit, or it can store var1 and var2 in to different 32 bit units. The former produces likely more code, the latter uses more memory. It's up the compiler to decide.

If your programming language supports "pointer to char" as a type, then a pointer to var1 and a pointer to var2 will be different. Even if both are stored in the same 32 bit unit. A "pointer to char" will not be an address as it is used by the computer, but a combination of an address, plus some indication which of the four bytes of a 32 bit unit to access. Cray built machines that worked that way.

In the end, the compiler for your programming language is responsible to make everything work the way it is supposed to work according to the definition of the programming language, no matter how the underlying hardware works.

PS. The compiler also has the option to make char = 32 bit.


Do polynomial reduction functions work both ways? For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem:

Theorem- Formula F is satisfiable IFF graph has an independent set.

If I have to prove it this way does this also mean that Independent Set ≤p 3-Sat as well since the theorem goes both ways?

The statement

  Formula $F$ is satisfiable $\iff$ graph has an independent set

is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:

  There is a polynomial-time function $\mathcal{G}$ from formulas to graphs such that, for all formulas $F$, $F$ is satisfiable $\iff$ $\mathcal{G}(F)$ has an independent set

Note that, once properly written like this, the statement is no longer symmetric: the reduction function goes in one way (formulas to graphs), and not the other way around. So, proving the above does not also prove the converse reduction.

The converse reduction (from independent set to 3-SAT) holds, but to prove that we need another reduction function $\mathcal{F}(G)$ mapping graphs into formulas.


Find maximal clique consisting of at least half of the vertices Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority of the vertices will belong to this clique. This clique may or may not be maximal; however, given these assumptions it will definitely be a subgraph of the maximum clique of $G$.
My goal is to find the most efficient algorithm to find the maximum clique of the graph. If the maximum clique is not unique, finding one of them is fine.
In general, $G$ won't be planar or perfect graph and to the best of my knowledge there is no exponential or linear-time algorithm to solve this problem.
I thought that, one way is to do an exhaustive search of all $n\choose c$ induced subgraphs until I find a clique $C$. Then, one can keep adding vertices to $C$ such that they connect to all vertices currently in $C$ until this clique cannot be enlarged anymore. Then, $C$ will be one maximum clique.
Assuming that $n$ is not too large, maybe $n < 50$, do you think that this is a reasonable method given that $n\choose c$ is large? Is there a more efficient algorithm?
One small optimization is to exclude all vertices with degree $< c-1$ from consideration.

Each time you remove a vertex $v$ with degree $<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $<c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a degree $\geq c−1$. The maximum clique will be a subset of such core.
Besides that, $c$ is just a lower bound on the maximum clique size, which doesn't change the fact your problem is NP-hard but over a much tinier graph (if you are minimally lucky).
Also, given the maximal $d$ such as the $d$-core exists (the degeneracy of the graph), $d+1$ is an upper bound to the maximum clique size.
With $c$ and $d+1$ as bounds, your maximal clique will probably be found very efficiently by the algoritm introduced in this paper, where all of the above is explained very well (there are a link to github with the implementation in C++): http://www.optimization-online.org/DB_FILE/2018/07/6710.pdf
If you have remove enough vertices, maybe your $c$, which is at least a 50% in the original graph, becomes even higher after the previous erosion of the graph, so you could start looking for algorithm variants specialized for dense graphs.


Regularity of infinite concatenation It is well-known that an infinite union of regular languages is not necessarily regular, since every language can be written as a union of singletons. What about infinite concatenations?

Let $\{ L_z : z \in \mathbb{Z} \}$ be a family of languages, cofinitely many of which contain $\epsilon$. We can define the infinite concatenation of the family as the collection of all words of the form $w_{i_1} \ldots w_{i_n}$, where $i_1 < \cdots < i_n$ and $w_{i_j} \in L_{i_j}$. (The definition makes sense if we replace $\mathbb{Z}$ with any linear order.)

  Is the infinite concatenation of a family of regular languages necessarily regular?

The answer is negative. Let $L_n = \{\epsilon, a^{3^n}\}$ for $n \geq 0$, and let $L_n = \{\epsilon\}$ for $n < 0$. The infinite concatenation of the collection $\{ L_n : n \in \mathbb{Z} \}$ is
$$
L = \{ a^m : \text{$m$ is the sum of distinct powers of $3$} \}.
$$
Since $L$ is unary, in order to show that $L$ is not regular, we need to show that the set $S = \{ m : \text{$m$ is the sum of distinct powers of $3$} \}$ is not eventually periodic. We can see this in many ways. For example, $S$ is infinite but has density $0$ in the limit.


Converting physical address to logical In 8-bit address space there are 16 pages and the page table stores:

68792EA51BD3CF04 (hex)

The physical address is 39h, what is the corresponding logical address?

I have literally no idea what to do, tried to look on different sites and work with formulas but nothing seems to work. I don't think it was ever covered on the lectures but it might show up at the exam.

I'd appreciate any form of help, thank you and sorry for taking your time.

You need to provide a linking page table which links the page number (logical address) to the frame number (physical address) and vice versa.


How to read 'max min' and 'min max'? Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.
Now, we'll let $P*$ be the set of $s-t$ paths in the graph, and let $C*$ be the set of $s-t$ cuts -- meaning, $C*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.
Demonstrate that the following equality is true:
$\max_{P\in P*} \min_{e \in P}c_e = \min_{C \in C*}\max_{e \in C}c_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.
Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have nesting here:

$\max_{X \in \mathcal{X}}\ ( \min_{x \in X} x)$

is the largest minimum of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \{ \{1,2\}, \{3,4\} \}$. Then, the following equalities hold:

$\min_{X \in \mathcal{X}} \min_{x \in X} x = 1$.
$\min_{X \in \mathcal{X}} \max_{x \in X} x = 2$.
$\max_{X \in \mathcal{X}} \min_{x \in X} x = 3$.
$\max_{X \in \mathcal{X}} \max_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

Xs.map { X => X.max }.min


Prove that NP is closed under karp reduction? A complexity class $\mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B \in \mathbb{C}$ $\implies$ $A \in \mathbb{C}$

How would you go about proving this if $\mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B \in NP$ $\implies$ $A \in NP$

I was able to figure it out. In case anyone (mans in ECE 406) was wondering:

$B \in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where $i$ is the input to $B$.

$A$ karp reducing to $B \implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and same for false case),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

Take input $i$ and apply $m$ to yield $m(i)$
Apply $b$ with input $m(i)$

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.


Bucket Priority Queues with large integers for $O(1)$ insert and extract~min? I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively close).

After thinking about it a bit I stated "I could probably make it $O(1)$ by using buckets" and approximating the minimum (to bucket size precision). I was politely told that I was wrong. Not taking no for an answer, I later went to Google and found the ample literature on the subject, which seemed to confirm I was wrong :-|

Note that the closely related question, Unique integer priority queue with both $O(1)$ insert and extract-min?, does not allow for approximation, so the answers don't apply to my question.

I was told the standard solution to this problem is to use a queue where keys are appended to the end in $O(1)$ and read from the head in $O(1)$ and which is then periodically sorted in $O(\log N)$ or whatever sorting algorithm you can find.

Assuming 64-bit integers as keys, and a precision of $ \pm 127$ (a 56-bit bucket)... Can't you just hold the buckets in a sparse array (so as not to require $2^{56}$ words of memory)... problem solved?

Your proposed data structure is simply a hash table with some rounding to reduce the number of buckets. Effectively, all this does is divide the problem complexity by some constant factor (128 in your example).

You have no hierarchy in your design, so there is no way to have O(1) access to the smallest/largest non-empty bucket. To achieve this feature efficiently, you're already pretty much bound to some type of priority queue. This class of data structures is well studied, and has various implementations with typically very low bounds on complexity.


Expected number of vertices with degree 2 A simple graph with $n$ vertices is constructed by randomly and independently placing an edge between every two vertices with probability $p$. What is the expected number of nodes with degree two?

I was only able to find the probability of any vertex having degree 2. Let me explain what I tried. For any vertex we can have n-1 edges connecting it(since its a simple graph), so for it to have degree = 2, two of these n-1 edges should be there, and rest not.

This gives: $\binom{n−2}{2}p^2(1−p)^{n−3}$.

Hint:

   Indicator random variables.

If that's not enough and you need a second hint:

   Use linearity of expectation.


What kind of language uses an infinite alphabet? Kind of what it says on the tin. Let's say I have a countably infinite alphabet $A$ and a "language" $L = \{s_1s_2 | s_1,s_2 \in A\}$ (i.e. all possible strings of length 2). Now, my question is this: does it even make sense to think of this in terms of formal languages? Is there some construct akin to a state machine that I can use to model such a thing? And do any of the above answers change if $A$ is uncountable?

The definition of formal language doesn't depend on the alphabet - it remains exactly the same. Things start getting a bit more complicated when you are interested in certain classes of languages. For example, let us consider regular languages. If your alphabet is infinite, the restriction of having only finitely many states seems a bit restrictive. Instead, it makes sense to allow any number of states whose cardinal is strictly less than that of the alphabet (if you allow a cardinal at least as large, every language would be regular). The corresponding notion of regular languages isn't too exciting perhaps, but at least it is a genuine subclass of all languages, which shares some properties with regular languages over finite alphabets.


numerically stable log1pexp calculation What are good approximations for computing log1pexp for single precision and double precision floating point numbers?

Note: log1pexp(x) is log(1 + exp(x))

I have found few implementations of log1pexp for double precision but they don't provide an explanation on how they arrived at the approximations. Hence, I am not able to implement log1exp for single precision numbers (without converting to double precision intermediates of course).

Reference implementation: https://github.com/davisking/dlib/blob/master/dlib/dnn/utilities.h#L16-L29

Let $0 < \varepsilon \lll 1$ be the relative error bound of the floating-point system—$2^{-53}$ in IEEE 754 binary64 arithmetic.

First, the naive formula log1p(exp(x)) always gives a good approximation unless exp(x) overflows:  If exp(x) computes $(1 + \delta_1) e^x$, and if log1p(y) computes $(1 + \delta_2) \log(1 + y)$, where $|\delta_1|, |\delta_2| \leq \varepsilon$, then log1p(exp(x)) yields

\begin{equation}
  (1 + \delta_2) \log\bigl[1 + (1 + \delta_1) e^x\bigr]
  = (1 + \delta_2) (1 + \delta_1') \log(1 + e^x)
\end{equation}

where $|\delta_1'|$ is bounded by a constant multiple of $\delta_1$ since $(1 + \delta_1) e^x$ is positive and $y \mapsto \log(1 + y)$ has small condition number on the positive real axis.  Thus the relative error is bounded by $|\delta_2| + |\delta_1'| + |\delta_2 \delta_1'|$ which in turn is bounded by small polynomial function of $\varepsilon$.

  Exercise: Compute a bound on $|\delta_1'/\delta_1|$.

But you can do better, with less computation (only one transcendental evaluation, not two), in some special cases:

If $x \lll 0$, then $e^x$ is near 0 so $\log(1 + e^x) \approx e^x$.  Specifically, $0 < e^x < 1$, so:

$\log(1 + e^x) \geq e^x/2$, since $y \mapsto \log(1 + y)$ is a concave function with derivative $y \mapsto 1/(1 + y)$ bounded below by $1/2$ for $y < 1$; and
the Taylor expansion of $y \mapsto \log(1 + y)$ converges absolutely at $e^x$.

Thus the relative error of $e^x$ from $\log(1 + e^x)$ is:

\begin{align}
     \frac{|e^x - \log(1 + e^x)|}{\left|\log(1 + e^x)\right|}
     &\leq 2 e^{-x} |e^x - \log(1 + e^x)| \\
     &= 2 e^{-x} |e^x - (e^x - e^{2x}/2 + e^{3x}/3 - \cdots)| \\
     &= 2 e^{-x} |e^{2x}/2 - e^{3x}/3 + e^{4x}/4 - \cdots| \\
     &= 2 |e^x/2 - e^{2x}/3 + e^{3x}/4 - \cdots| \\
     &< 2 |e^x/2| \\
     &= e^x.
   \end{align}

For $x \leq \log \varepsilon$, this relative error is bounded by $\varepsilon$, which justifies the formula exp(x).

In IEEE 754 binary64 arithmetic, $\log \varepsilon \approx -37$.
If $x \gg 0$, we can use the identity

\begin{equation}
     \log(1 + e^x) = \log\bigl[e^x (1 + e^{-x})\bigr] = x + \log(1 + e^{-x})
   \end{equation}

to rewrite $\log(1 + e^x)$ in terms of $\log(1 + y)$ for $0 < y < 1$, with $y = e^{-x}$, as in case (1).  The value of $\log(1 + e^x)$ lies between $x + e^{-x}$ and $x + e^{-x} - e^{-2x}/2$, so the relative error of $x + e^{-x}$ from $\log(1 + e^x)$ is below the relative error of $x + e^{-x}$ from $x + e^{-x} - e^{-2x}/2$, which is

\begin{equation}
     \frac{|x + e^{-x} - (x + e^{-x} - e^{-2x}/2)|}{|x + e^{-x} - e^{-2x}/2|}
      = \frac{e^{-2x}/2}{|x + e^{-x} - e^{-2x}/2|}
      \leq e^{-2x}/2.
   \end{equation}

For $x \geq \log(1/\sqrt{2\varepsilon})$, this is bounded by $\varepsilon$, which justifies the formula x + exp(-x).

In IEEE 754 binary64 arithmetic, $\log(1/\sqrt{2\varepsilon}) \approx 18$.
If $x \ggg 0$, then $x + \log(1 + e^{-x})$ may simply be rounded to $x$.  Specifically, the relative error of $x$ from $\log(1 + e^x) = x + \log(1 + e^{-x})$ is

\begin{equation}
     \frac{\bigl|x - \bigl[x + \log(1 + e^{-x})\bigr]\bigr|}{\left|\log(1 + e^x)\right|}
     = \frac{\log(1 + e^{-x})}{\log(1 + e^x)}
     < \log(1 + e^{-x}),
   \end{equation}

as long as $e^x \geq e - 1$ so that the denominator $\log(1 + e^x)$ is at least $1$.

For $x \geq \log[1/(e^\varepsilon - 1)]$, then this error is below $\varepsilon$, which justifies the formula x.

In IEEE 754 binary64 arithmetic, $\log[1/(e^\varepsilon - 1)] \approx 37$.

  Exercise: Find a nice formula for a bound on $x$ that corresponds to the cutoff $33.3$ in the source you cited, by taking the denominator $\log(1 + e^x)$ into account.


Random walk increasing distance I'm wondering why if I increase the number of step in a set of simulation of a random walk on a grid the distance from the origin is higher.

If I can move on the grid in 4 directions, there are 0.5 chance of getting closer to origin and 0.5 of getting farther.

This is a simple javascript example (well, here maybe I made some other errors because the points ends always with a negative x and a positive y, or maybe I just cannot rely on javascript random function in this case)

var steps = 100; //number of steps for each simulation (initially)
var simulations = 100; //number of total simulation
var points = Array.from({length:simulations}, () => ({x:0,y:0})); // init the array of points from the origin

//the 4 possible moves
var moves = [{x:0,y:1},{x:1,y:0},{x:0,y:-1},{x:-1,y:0}];
//ranom util function
var random = (max) => parseInt(Math.random() * max)

for (var s=0;s < simulations;s++) {
    //note the steps are increasing: 100,200,300,...,1000
    for (var i=1;i <= steps * s;i++) {
        let move = moves[random(4)];
        //console.log(move)
        points[s].x += move.x
        points[s].y += move.y
        //console.log(s, move)
    }
    console.log(`simulation n.${s} total steps: ${steps*s}`, points[s].x, points[s].y, `distance: ${Math.abs(points[s].x) + Math.abs(points[s].y)}` )

}

EDIT: thanks to @GASSA I fixed my code, but watching the results I'm still in doubt: the distance actually is not increased (see the graph below). Not sure what's the problem..

It's easiest to understand with a one-dimensional random walk.  After $n$ steps, the typical value for the distance from the origin is proportional to $\sqrt{n}$.  Thus, the more steps you take, the greater the typical distance from the origin.  For an analysis and explanation, see https://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk.  The math is well-developed in many standard places, so I'm not going to repeat it here.


Which fixpoint is Haskell list type? Let's say that lists are defined as

List a = Nil | Cons a (List a)

Then, in Haskell is List x the greatest or least fixpoint? I'm asking because the lfp should exclude infinite lists (but you can build them in Haskell), whereas the gfp should exclude finite ones.

It's the greatest fixed point, or the final coalgebra, depending on how you set things up. In Haskell it is impossible to define the datatype of finite lists because Haskell does not have inductive types, only the coinductive ones. Many people are in denial about this particular issue.


Using existential quantifier within implication I had used an existential quantifier within an implication, as below:

$$\exists ~ \sigma_{opt}~~~ \wedge~~~ n \in R^{+}~  ,~0<n<1 \rightarrow ~~ \sigma_{opt} = n$$

I've, recently, found that it is illegal to do that and just universal quantifier could be used in this situation. Could anybody explain the reason?

Your statement attempts to be express in formal logic the following sentence:

  There exist $\sigma_{opt}$ and $n$ in $R^+$ such that if $0 < n < 1$ then $\sigma_{opt} = n$.

The attempt at translation goes about by replacing English words by mathematical symbols, while keeping English syntax. Unfortunately, that is not how this sort of translation works. Just as when translating between human languages the syntax needs to be changed, here as well you have to conform to the syntax of statements in predicate logic. Your statement is, unfortunately, ungrammatical (more formally, it is not well-formed, that is, it is not a wff).

The syntax of sentences in predicate logic is described in many sources, so let me just mention that the following sentence is valid:
$$
\exists \sigma_{opt} \in R^+ \exists n \in R^+ \; (0 < n \land n < 1) \to \sigma_{opt} = n.
$$
We often allow shortcuts to be used, and so consider the following statement to be valid as well (standing for the former statement):
$$
\exists \sigma_{opt},n \in R^+ \; 0 < n < 1 \to \sigma_{opt} = n.
$$
You are using a different shortcut for folding the two existential quantifiers, but your convention is not standard; it's better to use standard conventions, unless there's a good reason to deviate from standard practice.

Finally, I'm not sure what your statement is supposed to express, but it probably doesn't express what you were hoping for: it doesn't depend on any parameter (this is why it's a statement rather than just a formula), which was probably not your original intention.


Solving recurrence relation with square root I am trying to solve the following recurrence relation :-

$T(n) = T(\sqrt{n}) + n$ using masters theorem.

We can substitute $n = 2 ^ m$

$T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$

Now we can rewrite it as

$S(m) = S(\frac{m}{2}) + m$

The big $O$-notation for $S(m)$ will be $O(m)$.

Hence, $T(n) = T(2^m) = S(m) = O(m)$.

So we can say that $T(n) =O(\log n)$ as $n=2^m$.

But the answer is $O(\log\log n)$ . What is wrong with my approach ?

The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$.

But now to your computation.  Setting $n=2^m$, we obtain as you did
$$ T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m).$$ Then equation $\eqref{eq1}$ should become the following equation,
which is different from $S(m)\,$$= S(\frac{m}{2})\,$$ + m$, the wrong equation in the question.

$$S(m) = S\left(\frac{m}{2}\right) + 2^m.$$

The equation above falls into the third case of the master theorem, therefore $S(m) \in \Theta(2^m)$. And from this follows $T(n) \in \Theta(n)$.


Proving a language is not a regular language but a context free language I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$.

I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is not a regular language I can use the pumping lemma but I'm unsure about the details.

I also want to prove that $L_2$ is a context free language. Do I need a Push Down Automaton that accepts the language to prove that $L_2$ is a context free language? If so, what would this Push-Down Automaton look like?

While it is possible to show that $L_2$ is not regular using the pumping lemma, it is easier to do so by making use of the fact that the regular languages are close under complement, i.e. a language is regular if and only if its complement is regular.

In order to show that $L_2$ is context-free, you can give either an automaton or a context-free grammar for the language. The automaton is presumably the easier way in this case. Hint: $L_2$ is a deterministic context-free language, so there is a deterministic PDA for $L_2$ that can be derived in a straightforward way from the deterministic PDA of $L_2$'s complement.


Problems that provably require quadratic time I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.

The problem needs to have the following properties:

$\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
$O(n^2)$ algorithm, if possible, simple one as well.
Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
(if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.

I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was conjuctured to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.

Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.

If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).

So, can we find a simple (to prove), natural (well known) problem whose runtime is $\Theta(n^2)$?

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound -
probably one of the largest gaps in computer science.


CFG With unambiguous if-else statement I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'.
 The non-ambiguous if-else statement I took from the dragon book, which turns to be ambiguous when I add the braces. To build the parser and test it I am using the Ply library written in Python.

The grammar terminals/nonterminals specification is backwards here - Uppercase strings are the terminals and Lowercase are the non-terminals. Also the grammar below is not ambiguous untill you try to enclose the if-else with {} which is tokenized as LBRACE and RBRACE.

Below is the grammar specification:

Rule 0     S' -> program
Rule 1     program -> function_definition program
Rule 2     program -> empty
Rule 3     function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN block
Rule 4     function_definition_args -> var_list
Rule 5     function_definition_args -> empty
Rule 6     var_list -> var_declaration COMMA var_list
Rule 7     var_list -> var_declaration
Rule 8     var_declaration -> data_type ID
Rule 9     data_type -> VOID
Rule 10    data_type -> INT
Rule 11    data_type -> FLOAT
Rule 12    data_type -> STRING
Rule 13    data_type -> CHAR
Rule 14    block -> LBRACE statements RBRACE
Rule 15    statements -> statement statements
Rule 16    statements -> empty
Rule 17    statement -> matched_statement
Rule 18    statement -> unmatched_statement
Rule 19    matched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE matched_statement RBRACE
Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE
Rule 23    logical_expression -> logical_term OR logical_term
Rule 24    logical_expression -> logical_term
Rule 25    logical_term -> logical_factor AND logical_factor
Rule 26    logical_term -> logical_factor
Rule 27    logical_factor -> boolean_statement
Rule 28    logical_factor -> NOT logical_factor
Rule 29    logical_factor -> LPAREN logical_expression RPAREN
Rule 30    boolean_statement -> value comparison_op value
Rule 31    boolean_statement -> value
Rule 32    value -> ID
Rule 33    value -> NUMBER
Rule 34    comparison_op -> LESS_THAN
Rule 35    comparison_op -> LESS_EQUAL
Rule 36    comparison_op -> GREATER_THAN
Rule 37    comparison_op -> GREATER_EQUAL
Rule 38    comparison_op -> EQUAL
Rule 39    command -> compound_statement
Rule 40    command -> simple_statement
Rule 41    compound_statement -> WHILE LPAREN logical_expression RPAREN block
Rule 42    simple_statement -> expression
Rule 43    expression -> expression PLUS term
Rule 44    expression -> expression MINUS term
Rule 45    expression -> term
Rule 46    term -> term TIMES factor
Rule 47    term -> term DIVIDE factor
Rule 48    term -> factor
Rule 49    factor -> NUMBER
Rule 50    factor -> ID
Rule 51    factor -> LPAREN expression RPAREN
Rule 52    uminus_expression -> MINUS LPAREN expression RPAREN
Rule 53    empty -> <empty>
Rule 54    function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN error

The following change bellow is the one which causes the shif/reduce conflicts

Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE

If you insist that the alternatives in a conditional statement be blocks, then the dangling-else ambiguity vanishes.

The dangling else ambiguity is something like this, where the else could be attached to either if:

if (a > 3) if (b > 4) do_something else do_something_else

However, if the statements in the conditional must be surrounded by braces, that is a syntax error. You would have to write either:

if (a > 3) { if (b > 4) { do_something } else { do_something_else } }

or

if (a > 3) { if (b > 4) { do_something } } else { do_something_else }

and both of those are quite explicit about which if the else belongs to.

In effect, a braced statement list (or block, as you refer to it in the context of a while statement) is a matched_statement, and you could just add it to the set of possibilities for that non-terminal. But that's only necessary if you want the braces to be optional; if you're going to require them, then you can scrap all that matched- and unmatched- statement stuff, and just use block in your if statement, just as with your while statement.

In any case, the problem is

Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE

Since matched_statement -> command (rule 20), the RBRACE in rule 21 induces a shift-reduce conflict. Assuming a command has just been reduced, the parser has to decide whether rule 20 should be applied (a reduce), which is necessary if the input is the start of rule 22, or whether the RBRACE should just be shifted, necessary if the input is the start of rule 21. And it can't know that by just looking at the RBRACE, since that is the same in both rules.

However, as I said, it doesn't matter. You don't need two different non-terminals for a block, and just using block will avoid the problem.


Making random sources uniformly distributed How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities $prob(a)$ and $prob(b) = 1 - prob(a)$ that are unknown to us.

How do I state an algorithm that does the job and that does not consume more than an expected number of
$(prob(a) \cdot prob(b))^{-1}$ symbols of $S$ between two output bits and prove its correcteness?

Consider this: get two elements $x_0$ and $x_1$ from $S$. If $x_0x_1$ is $aa$ or $bb$ then discard them and repeat. Otherwise return $0$ for $ab$ and $1$ for $ba$, events that occur with the same probability $p_ap_b$.

This will use $2n$ elements from $S$, $n$ the number of performed steps. The probability of stopping at each step is $p=1-2p_ap_b$. The expected value of $2n$ is therefore $$2p\sum_{n=1}^∞{n(1-p)^{n-1}}=\frac{2p}{(1-(1-p))^2}=\frac{1}{p_ap_b}\enspace.$$


Booth bit-pair recoding technique In Booth's bit-pair recording technique how to multiply a multiplicand with -2 or 2? For example while multiplying 01101(+13, multiplicand) and 11010(-6, multiplier), we get 01101 x 0-1-2.

How to multiply the multiplicand using -2?

In bit recoding multiplication, e.g.   01101 times 0, -1, or -2.

For multiplying with -1:
Take 2's complement of 01101 i.e: 10011
For multiplying with -2:
Add 2's complement of 01101 i.e: 10011 + 10011= 100110


Using Generalized Rice's Theorem to Prove Decidability I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to determine if L(M) is decidable, semi-decidable (computably enumerable) or undecidable.

Using Rice's Theorem, I believe I can prove that L(M) is not decidable:

  P is the property of a language where the language has infinitely many strings that start with one symbol and finitely many strings that start with another symbol. P is non-trivial and is a property of languages of TMs. Therefore, according to Rice's Theorem, M = {⟨M⟩∣L(M) has has infinitely many strings that start with 1 and finitely many strings that start with 2 and Σ = {1,2}} is undecidable.

But I'm struggling to prove whether it's semi-decidable or completely undecidable. This post mentions using an Generalized Rice's Theorem to prove that a language is recursively enumerable (aka semi-decidable) but I'm having trouble understanding their approach.

Can anyone shed some light on this approach and/or if I'm heading down the right path? Many thanks in advance.

I'm going to ignore the second half of your post, and answer the question that appears at the first half. If this is not what you meant - post another question or edit as necessary.

Given a machine $M$ we define $L(M)$ to be the language recognized by that machine. In other words, $L(M)$ is the set of all the words $w\in \Sigma^*$ such that $M$ accepts $w$.

Thus, by its definition $L(M)$ is at least semi-decidable (because $M$ is accepting it!!)

To clarify whether $L(M)$ is decidable or semi-decidable(but not fully decidable), we need more information on $M$.

For instance, it can be that $M$ is the trivial machine that immediately go to the accepting state. In that case $L(M)=\Sigma^*$ (all the possible words), and $L(M)$ is decidable.

On the other hand it can be that $M$ does the following:

1. it ignores the first symbol of the input
2. it runs HP on the rest of the input

where HP is the machine that accepts the Halting Problem language. It is not too difficult to see that in this case $L(M)$ cannot be fully decidable (or otherwise the halting problem will be decidable), but, as said above, it is semi-decidable by definition (that is, it is in $RE\setminus R$).

Now, if you don't care about a specific machine $M$, but instead about all the machines that accept infinitely many words that begin with 1 and infinitely many words that begin with 2, the language that contain all such machines cannot be decidable due to Rice's theorem.

Just to be clear on the statement: let $S \subset RE$ be all the languages that contain infinitely many words that start with 1 as well as infinitely words that start with 2, then

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}$$ cannot be decidable, $L_S\notin R$. Note that $L_S$ contains all the (encodings of) machines that satisfy the property $S$  defined in your question.


In Data Mining, what does it mean to be greedy? I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory.

For example, with Hierarchical Clustering the decision to merge clusters is described as greedy. However, a filter attribute selection method where we select a subset of the attributes which possess the highest Information Gain is also described as greedy because it does not cope well with the interaction of attributes.

What does the term greedy mean in terms of Data Mining?

I'm not a Data Mining expert, but from what I understand, it means the same thing as it does outside of data mining: to improving the solution in a locally optimal way, rather than one that is guaranteed globally optimal. (And, as Raphael comments, to not backtrack on that decision).

For example, if you are training a graphical model, the process of repeatedly adding the edge that improves your model's fit the most, until no changes improve the model, is a greedy process. at each stage, you've taken the action which has the most incremental improvement over your current model, but the result may not be globally optimal.

Likewise, in the clustering example, to say that the clusters are merged greedily means that they are merged in the way that provides the best incremental improvement over other merges, but may not lead to the optimal clustering at the end.


Approximating the Kolmogorov complexity I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group documents by their similarity).

In that case, data compressors were used to approximate the Kolmogorov complexity, since the data compressor could be used as a Turing Machine.

Besides data compression and programming languages (in which you would write some kind of compressor), what else could be used to approximate the Kolmogorov complexity? Are there any other approaches that could be used?

I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of $s$:

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Where $|G|$ is the length of the program that computes $G(s)$ (often quite short, as for linear generators).

Note that in practice, random number generator attacks are not as described: they may fail or produce incomplete results. In that case, you may adapt the algorithm so that it returns $|s|$ when the result of the attack is unsatisfactory. The same remark goes for compression algorithms.

The caveat to this approach as opposed to compression algorithms is that compression algorithms are in general much more suited to computing KC as they are tailored to work on any string, whereas an attack can work only if $s$ happens to be in the image of $G$ (very unlikely).


Time complexity of the fastest algorithm for this case An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $2≤i≤n−1$, either $A[i] > max \{A [i-1], A[i+1]\}$, or$A[i] < min \{A[i-1], A[i+1]\}$.  What is the time-complexity of the fastest algorithm that takes as input a sorted array $A$ with $n$ distinct elements, and un-sorts $A$?

A.$O(nlogn)$ but not $O(n)$
B.$O(n)$ but not $O(\sqrt{n})$
C.$O(\sqrt{n})$ but not $O(logn)$
D.$O(logn)$ but not $O(1)$
E.$ O(1)$

My approach:
1.Pair wise swapping can be done which will result in $O(n)$
2.Starting from the left every even position from the start will be swapped with the even position from the right
1 2 3 4 5 6 7 8 -- 2 will be swapped with 7 similarly 4 and 5
odd length can be also listed which is taking $n/4$ steps
So i want to confirm whether only $O(n)$ is the max can best algorithm can be achieved or better can be achieved.

I think it's not optimal but here's a lower bound: you have to move at least $\lfloor\frac{n}{3}\rfloor$ elements.

Split $A$ into blocks of $3$: {$A[1],A[2],A[3]$}, {$A[4],A[5],A[6]$}, ...

The claim is you have to move at least one element from each block. Otherwise, assume the block {$A[k],A[k+1],A[k+2]$} is kept unchanged. Since $A$ is sorted, $\min(A[k],A[k+2])<A[k+1]<\max(A[k],A[k+2])$, which violates your constraint. So the problem takes $\Omega(n)$. Combine this with your $O(n)$ approach we get $\Theta(n)$.


DAG Hamiltonian Path NP-complete The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG.
But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two vertices ${s,t}$ which will make the graph acyclic and then ask for $s\rightarrow t$ hamiltonian path in that DAG. These two problems are equivalent. Then why is one NP-complete and other is not ?

Your proposed approach doesn't work.  For some directed graphs there is no single vertex you can split to turn it into a DAG.  An algorithm only qualifies as a solution to the Hamiltonian Cycle problem if it solves the problem for all graphs.  It's not enough to solve the problem for a subset of "easy" graphs.


Proving OP(L) is regular I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints.
So, I am currently working on a proof to show that if $L$ is regular then $OP(L)$ is also regular without the use of pumping lemma. For the sake of this question, I am using $\{0,1\}$ as alphabet.

$$OP(L) = \{w \mid wz ∉ L \text{ for every } z ∈ \{0,1\}^+ \}.$$

At the moment, I have a hard time starting the proof. What I understand is that, if $L$ is regular then we can define a DFA that can decide $L$. And then we can define another machine for $OP(L)$ with every transition from $M$ along with $\epsilon$-transitions.

Am I on the right track? I could really use some hints.

Hint: Consider a DFA for $L$, and some word $w$. Suppose that upon reading $w$, the DFA reaches some state $q$. Is knowing $q$ enough for deciding whether $w \in OP(L)$?


How are REGEXP implemented in programming languages? Is there a good general paper about the interpretation or compilation
of REGEXP in programming languages for pattern matching, with or
without variables? I am not looking for a quick explanation about the
construction of DFAs, but for a real paper on how it is actually done
in programming languages implementation, and what is considered simple
or difficult. I expect differences between languages may have an
inpact. A formal paper on how REGEXP implementation should be done is
useful too :-)

I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata.  The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM, 11(6):419-422, June 1968.  But that paper is a little hard to read, since he was compiling to machine code.

My favorite tutorial on regular expression implementation is this series of blog posts by Russ Cox, the author of the RE2 regular expression library.  He gives lots of historical discussion.  He argues that the most efficient approach to simulating the NFA is to convert to DFA on the fly with caching of just the DFA states that you actually reach.  (In contrast to, for example, the implementation of regular expressions in Perl, which use backtracking.)  There are cases (e.g., when you get an extended regular expressions with backreferences) where you need to use backtracking, but Cox suggests that you should only use backtracking when you need to.

The other place you might look is Henry Spencer's regular expression library.  According to that web site this was described in the book: Dale Schumacher (ed), Software Solutions In C, Academic Press, 1994.


Why not use Right Recursion to avoid Left Recursion? I am reading about Representative Grammars from book, where I encountered the following grammar:

$$ E \rightarrow E + T \ | \ T $$
$$ T \rightarrow T * F \ | \ F $$
$$ F \rightarrow (E) \ | \ id$$

The above grammar is left-recursive, which is bad. So in order to eliminate left recursion, they changed it to the following:

$$ E \rightarrow TE' $$
$$ E' \rightarrow +TE' \ | \ \epsilon $$
$$ T \rightarrow FT' $$
$$ T' \rightarrow *FT' \ | \ \epsilon $$
$$ F \rightarrow (E) \ | \ id $$

But why bother so much? Why not simply use a right recursion instead, like the following:

$$ E \rightarrow T + E \ | \ T$$
$$ T \rightarrow F * T \ | \ F$$
$$ F \rightarrow (E) \ | \ id$$

So I am confused about whether the Right Recursive Grammar I thought of is same as the original grammar or not?
If not, what's the difference?
If they are same, why don't we write all grammars as Right Recursion?

The left recursive and the right recursive grammars describe the same language. But grammars do more than give the set of allowed strings in the language, they also give a structure to such strings and that structure is sometimes meaningful. Consider a+b+c; the structure implied by the left recursive grammar is {a+b}+c (I'm using braces and not parenthesis to show the structure to avoid confusion with the common mathematical meaning of parenthesis) the structure implied by the right recursive grammar is a+{b+c}.  If mathematically both are equivalent for addition, it is not the case for all operations. Consider subtraction a-{b-c} is not equal to {a-b}-c and that is the later that we usually consider the value of a-b-c.

The version with left-recursion removed is also right-recursive.  But its structure is different, and easier to map to the desired structure.  With a-b-c-d we have {{a-b}-c}-d for the left-recursive structure, a-{b-{c-d}} for the right-recursive and a{-b{-c{-d}}} for the result of left-recursion removal; that structure allow more easily than the right recursive one to get the intended meaning.


Efficiently finding duplicates in lists of numbers I decided to try my hand at solving the knapsack problem.

My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the objects to fit into the knapsack. The $i$ tables will then be sorted. Then for each of the $k$ numbers to be tested, I'll run a binary search on the sorted arrays.

I realised that there may be sums which repeat. I feel like recording them will be unnecessary waste of space.

So I want to determine if for any new number $k$ to be added to the list, if $k$ is a duplicate of any number in the list. It is trivial to just search the list, but this is too inefficient, and takes $O(n^2)$ operations, making the trade off with space complexity a bad deal.

I wanted a linear time algorithm for solving this problem. I thought of a function, which takes in inputs, and the function is such that if any new input is the same as a previous input, the function will provide a certain known output. This function should work in constant time or at worst, logarithmic time.

I have tried several means of constructing the function but they failed.

Use any efficient set data structure, based e.g. on hashtables or balanced search trees.

Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will come up with.

That said, you may want to check out pseudo-polynomial algorithms for Knapsack, and problem variants that have polynomial-time algorithms.


Partitioning connected graphs in the plane This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

Long edges are not guaranteed to be in the correct partition.
The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines

I'm looking to minimize the amount of line segments required, but optimality is not required.

This is not a full answer to your question, but at least you'll have something working.

Step 1. Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

Step 2. Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

Step 3. Repeat the Step 2 recursively for each box, which contains more than one component.

Step 4. After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

Step 5. Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - I don't know how to do that regularly for now.


Construct initial marking for marked graph so that the graph is live and safe I am learning something about P/T petri nets from the book from Wolfgang-Reisig authors and on the seventh chapter's end there is an exercise I can not really work out.

It asks me to construct initial marking such that the following marked graph is live and safe. Note that yellow highlighted place is for the latter part of the question and does not bear any other special significance.

Right after this exercise, there is following task, which asks me to do this: Show that the initial marking of each marked graph can be modified such that live and safe marked graph is obtained.

Based on that, I assume that it must be possible for any marked graph to have initial marking such that the graph is live and safe. But still I was not able to construct such initial marking. Is there an algorithmic approach to the task? And if I were to remove the highlighted part of the marked graph, would it still be possible to construct such graph?

Why can't you find a live and safe marking?

Number the transitions from left to right $t_1,t_2,t_3,t_4,t_5$ and the places from left to right $p_1, \ldots, p_{12}$,

We need to find a firing sequence that is possible, fires all transitions at least once, has net effect zero, and never produces an unsafe marking.

It doesn't matter where we start: if the net is live, we can "cycle" any such firing sequence by moving its starting transition to the end or vice versa.

So we may as well start with the "thick" transition in the middle, $t_2$. For it to be enabled, its input places must be marked. For the firing sequence we'll construct to be safe, its output places must be empty. So let's fire it. Now, its input places are empty, and its output places are marked. We must now be able to fire $t_3,t_4,t_5$. This is possible iff exactly one of $p_9,p_{10},p_{12}$ was (and is) marked. We can then fire all three in a row. So let's pick $p_9$ as the one that was set. Then, after firing $t_2$, $t_3$ will be able to fire; firing it will enable $t_5$; firing that will enable $t_4$; firing that will put the token back into $p_9$.

After firing $t_3$, $p_4$ will be set, enabling $t_1$. The firing of $t_1$ and of $t_3,t_5,t_6$ are independent: they don't influence each other.

Having fired both $t_1$ and $t_3,t_5,t_6$, we're back at our initial marking. The net doesn't actually give us a choice: we must fire $t_3$ first, and then both $t_1$ and the sequence $t_5,t_6$ to enable $t_2$, and no alternative firing sequences exist.

So with the initial marking $p_2,p_6,p_8,p_9$, the only possible firing sequences of this net are given by the regular language $(t_2t_3(t_1|t_5t_4))^* = (t_2t_3(t_1t_5t_4 \cup t_5t_1t_4 \cup t_5t_4t_1))^*$. All of the reachable markings are safe.

By the way the example is drawn, there appears to be theory behind this example. This marked graph is special in that it is composed from three plain cycles (the ovals) by fusing some of their transitions. I'll bet Reisig's book proves that all marked graphs constructed in such a way are live and safe.

Your second question: what if we remove the place marked in yellow? Well, this only removes a constraint on the firing sequences: all existing firing sequences will continue to exist, but new ones may arise.

Indeed: after $t_4$  has fired, or in the initial marking above, $t_3$ can now already fire before $t_2$. However, this is merely a relaxing of the order in which transitions are fired, and it doesn't produce any unsafe or unlive markings.
So the net remains live and safe. I suppose you'll have to prove this.

I'll guess there is another lemma in the book proving that this is true in general: that removing places from a live and safe marked graph always leaves it live and safe. I haven't read the book, so I'm not sure.


How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$ This almost makes sense to me, but I feel like I'm missing something.

I know that for a decidable language, there must exist some total computable function $f$ that can take in any $x \in \sum^{*}$ and tell us whether or not $x$ is accepted (while my textbook is unclear, I would infer from this that decidable languages and computable functions are equivalent?)

So I can see that $L$ is decidable if and only if some computable function can determine if $x \in L$ or not, which implies the existence of a function $f(x)$ that outputs $x$ if $x \in L$, and nothing otherwise (this makes sense in my head at least...correct me if I'm wrong). How would I use what's given to show that this is true for any recognizable $L$ though? Computable functions have finite steps have to halt, from my understanding, so how that they be used to check if $x$ belongs to a recognizable but undecidable language?

Hints:

If $L$ is recognized by some Turing machine $T$, then consider a Turing machine that on input $(x,n)$, runs $T$ on $x$ for $n$ steps and outputs $x$ if $T$ halts within $n$ steps.
If $L$ is enumerated by some Turing machine $T$, then given $x$, accept it if it appears in the list generated by $T$.


Connected but not adjacent vertex Are there specific terms or adjectives in graph theory to name these two situations?

Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-common vertices or edges).
Two connected non-adjacent vertices (the shortest path or paths connecting them have a lenght $> 1$).

You've exactly described the first situation, i.e. we indeed say that $u$ and $v$ are non-adjacent. For the second we do the same, but we want to also specify they are in the same component of $G$ which contains them if $G$ is not connected.

These are already simple and well-understood descriptions and there's nothing "more standard". However, you are also free to use your own definitions in your actual use case if it's worth it.


Is there an efficient algorithm for solving tiling puzzles? As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

  Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with
  hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right
  trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how
  to place two copies of T and two copies of P inside R with no overlap.

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).

Tiling figures of the plane with two bars shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.


Finding all unique paths from a source to a sink in a specially-formed DAG Let $G$ be a directed, acyclic graph of order $n$, such that:

$G$ has exactly one source vertex $s$;
$G$ has exactly two sink vertices $t_1, t_2$;
The out-degree of any non-sink vertex in $G$ is exactly 2; and
The longest path from $s$ to either of $t_1,t_2$ has length $k$.

What is the most efficient way of finding all unique paths from $s$ to $t_1$ (or $t_2$, doesn't really matter in this case) in $G$? What would the time complexity of this algorithm be? It is acceptable to use $k$ as a parameter if that would produce a better analysis.

If you are interested enumerating all the unique paths, then a recursion would be suitable since it is a dag. Observe that suppose v is a non source vertex and has incoming arcs from X1,...,Xn then every path from the source through v needs to pass through X1,...,Xn. . So if you enumerated all the paths from the source to each of these vertices you simply need to append v to them to compute all the paths through v originating from the source. This computation can be done very efficiently via dynamic programming. The reason DP will work is precisely because none of the paths from source to X1,...,Xn would have contained v since it is a dag.You should be able to work out the time complexity for the algorithm i described easily since it has a standard dp structure.


Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear? Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) that given three points returns true if they are non collinear and false otherwise. Is there an efficient algorithm to generate a list of random points such that no 3 points in the list are collinear? The points coordinates x y are integers, the amount of points is N and the grid size is RxC, I know that there is a restriction between N and R C, so I am fine if the algorithm relies in some assumption (e.g RxC is way bigger than N)

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.

Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose is $2N$.

Now consider the set of points $\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$.

For any set of 3 points to be collinear (Lets call them $(x_1,y_1),(x_2,y_2),(x_3,y_3) , x_1 < x_2 < x_3$ ) we must have $\frac{y_3 - y_2}{x_3 - x_2} = \frac{y_2 - y_1}{x_2 - x_1}$ , putting in $y_i = x_i^2\ mod\ n$ , we obtain $x_3 + x_2 \equiv x_2 + x_1 \mod n$ and this is only possible when $x_1 = x_3$.

Hence we have a set of $N$ points where no 3 points are collinear and it is the best we can obtain upto a constant factor.

Since this is a deterministic construction , to get a random family of points , instead of choosing $i^2$ , we can take any random quadratic polynomial $p$ and take the set of points $\{(i , p(i)) \ mod\ n \ |\ 0 \leq i \leq n-1 \}$.


How to interpret the execution of distributed computation from time-space diagram? I'm following a course on Distributed Systems

http://www.ict.kth.se/courses/ID2203/index.html

and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram of an execution with the symbolic definition of the execution as a sequence of configurations and events.

In the model, an execution is defined as a sequence of configurations interleaved with events. As in:

<C,E,C,E,C,E...>

Where the C's are configurations (states of the nodes, including their buffers) and the E's are events, which in this model, are either Computation or Delivery events.

A computation event, comp(i), takes place at a single node, indexed by i, and modifies the buffers of node_i and the internal state of node_i and nothing else. A delivery event, del(i,j,m), removes message m from the output buffer of node_i and adds it to the input buffer of node_j.

A time space diagram of a particular execution is given in Slide 11 in this particular lecture: http://www.ict.kth.se/courses/ID2203/material/Lecture_2._Unit_3._Computation_theorem_and_causality.pdf

The arcs on a single timeline are comp(i) events at a particular node. The arcs between timelines are del(i,j,m) events between nodes i and j.

I'd like to interpret this diagram into a sequence of comp and del events, but it seems ambiguous. Specifically, a delivery is initiated from node 1 to node 2 -- del(1,2,m) -- and during the delivery a computation event at node 3 -- comp(3) --  takes place and completes before the delivery event completes.

Since the events in an execution are, by definition, totally ordered, I'm not sure if the comp(3) should precede the del(1,2,m) or vice versa.

Yes, it is ambiguous, and it is ok. A single space-time diagram can be linearized (collapsed into a compatible sequence of configurations and events) in many ways, potentially an exponential number of ways. E.g. imagine that you have 1000 nodes, and each of them performs a local operation. Obviously there's 1000! different ways to linearize this, because there are no inherent causality constraints in this situation.

It is not true that events in an execution are totally ordered. They are only partially ordered, using the partial order given by causality constraints (most of which are "a message is sent BEFORE it is received"). There are many total orders compatible with this partial order.