Shortest Path using at most k colors I have an edge-colored network, in which edges also  have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the number of colors of edges in a path should not exceed an integer $k$.

It corresponds to finding shortest Paths on a multimodal network, with the only restriction being a limitation in the number of changes of modes allowed (e.g. different bus lines, and no more than three changes of bus).

I am trying to determine the complexity of this problem.

I have found a line of research combining graph theory and formal languages theory [1], which is interested in the more general problem of paths constrained by the fact that the word formed by the labels of a path belongs to a certain formal language. Theorems state that:

The problem is in $P$ if the above language is context-free.
It is $NP$-hard for regular languages.

So alternatively, my question could be stated as follows:

Is a language over a finite alphabet, in which words can be of any length, but have to use a limited number $k$ of different letters, regular or is it context-free?
E.g. the language of words using at most four latin letters. "HELLO" is okay but "HELPS" is not. Is this regular or context-free?

I would appreciate any pointers to literature discussing the problem in either form (but would really prefer a purely graph-theoretic proof of NP-hardness or polynomial algorithm). Otherwise, I guess I will have to invest a few weeks learning about formal languages.

Thank you in advance. The help I have received so far in this forum is outstanding.

[1] Barrett, C. et al. 2000. Formal-language-constrained Path problems. SIAM journal of computing. Vol. 30, No. 3, pp 809-837.

Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, and we will choose $k := n$. The edges are:

From $s$ to $x_1$ there are two edges, colored $x_1$ and $\lnot x_1$.
From $x_{i-1}$ to $x_i$ there are two edges, colored $x_i$ and $\lnot x_i$.
From $x_n$ to $C_1$ there is an edge per literal in $C_1$, colored as the literal.
From $C_{j-1}$ to $C_j$ there is an edge per literal in $C_j$, colored as the literal.

Then $\phi$ is satisfiable iff there is a path from $s$ to $C_m$ which uses at most $n$ different colors.


Algorithm for finding the best “route” of tasks I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x coordinates per second. Every task has:

A coordinate where it can be completed (for example (40/50))
A importance value ranging from  0  to X (for example importance = 5)
A time that is needed to complete this task

Also, some tasks can only be done if a certain other task has already been completed.
Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.

I tried to bruteforce it, but that didn't work out. There are around 11 tasks usually and 4-6 can be done, resulting in up to a million and something possiblities. Also, I had a solution without calculating the time needed to travel between the points which was basically calculating a importance per time value and just doing the tasks based on this value... which won't work for the full problem.

If you have just one person to complete the tasks, this is the (in)famous Travelling Salesman Problem (TSP), which is NP-complete, so an efficient exact algorithm is a very remote possibility. Unless your problem is quite small, you'd have to settle for approximate solutions. There are algorithms that can solve enormous instances of TSP in (somewhat) reasonable time, but I have no pointers at hand.


Computer networks - Can there be an out of order frames in a noiseless channel? In a noiseless channel can frames in the 2 layer of OSI model(Data link layer) reach to the destination out of order?
*I am studying from Computer networks 5 Edition of Andrew S. Tanenbaum

It depends on the channel and the assumptions you are making.  There may well be some communication channels where messages can be re-ordered but will not be dropped or lost or modified in transit.


Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable? I am reading "Introduction to Theory of Computation" by Michael Sipser. One of the exercise problems asks to verify whether  the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

This problem has two parts

K can be infinite (I know how to solve this. If the grammar has any
kind of     loop then it will generate infinite number of strings
thus k=infinite.
K can be finite. I don't know how to solve this. Any Ideas?

As you said, if there is a cycle of variables (non-terminals), the language generated is infinite. If you can also show the converse, that is, if the language is infinite, then there exists a cycle of variables, then you can construct a machine to do the following given a finite $K$:

Given a context-free grammar $G$, check if it has any cycles of non-terminals.
If yes, then $L(G)$ is infinite, so output no; otherwise, $L(G)$ is necessarily finite (using the converse property above, which you need to prove).
Since the grammar generates a finite number of strings, it is safe to try all possible paths of productions starting from the starting variable. Each such path corresponds to a string in $L(G)$. Eventually, all possible paths will be exhausted (as otherwise $L(G)$ would be infinite), at which point you will have generated $L(G)$. If $|L(G)| = K$, output yes, otherwise output no.


Arithmetic expressions grammar transformation In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions:

E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

which is quite bad, because it's ambiguous and left-recursive. So he starts from removing the left recursion from it, and his result is as such:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

But I can't figure out how did he get to this result. When I try to remove the left recursion myself, I'm doing it the following way:

Firs, I group together the productions which doesn't have left recursion in one group, and other (left-recursive) in another group:

E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
Next, I name them and factor for easier manipulations:

E --> E B E  // L-recursive; B stands for "Binary operator"
E --> P  // not L-recursive; P stands for "Primary Expression"
P --> v | "(" E ")" | U E   // U stands for "Unary operator"
B --> "+" | "-" | "*" | "/" | "^"
P --> "-"

Now I need to deal only with the first two productions, which are now easier to deal with.
I rewrite those first two productions by starting from the non-L-recursive production (which is simply P, the Primary expression) and following it by the optional Tail T, which I define as the rest of the original production less the first left-recursive nonterminal (that is, just B E) followed by the Tail T, or which could be empty:

E --> P T
T --> B E T |

(note the empty alternative for the tail).
These two productions I can now rewrite in EBNF like this:

E --> P {B E}

which is nearly what the author get, but I have E instead of P there inside the zero-or-more repetition pattern (the Tail). The other productions I get quite the same as he have got:

P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"

but here too I have E instead of P in the first production for P.

So, my question is: What am I missing? What algebraic transformation on the syntax I need to proceed now to get the same exact form as the autor gets? I tried substitutions for E, but it only leads me into loops. I suspect that I need somehow to substitute P for E, but I don't know any legal transformation to justify it. Maybe you know what's the last missing step?

The missing step:

E --> P T
T --> B E T |

rewrite E in T:

E --> P T
T --> B P T T |

Simplify T:

E --> P T
T --> B P T |

Equivalent to:

E --> P T
T --> {B P}

And there you are.


Largest N squares that fit in a rectangle I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:

Problem: Given N equal-sized squares and a rectangle with width W and height H, find out the maximum size of the squares L such that the squares fit inside the rectangle in such a way that their sides are orthogonal to the rectangle sides.

So far, I think we have a O(sqrt(N)) solution, in which we assume W>H, start by trying to place all squares in a single row, then in two rows and so on, until we get to O(sqrt(N)). For formally, let nRows be a variable from 1 to sqrt(N), nCols = ceil(N/nRows) and then do L = min(H/nRows, W/nCols).

I'm not completely sure the idea above is optimal. I was also wondering if we can solve this problem in O(1)?

I've tried looking for orthogonal square packing, but the problem seems a bit different (or could we easily reduce on to another?)

Let

\begin{align}
C&=\left\lfloor\frac WL\right\rfloor&
R&=\left\lfloor\frac HL\right\rfloor
\end{align}

be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximum $L^*$ such that, when $L=L^*$, we have $CR\ge N$. Let

\begin{align}
L_0&=\sqrt{\frac{WH}N}\\
C_0&=\left\lceil\frac W{L_0}\right\rceil=\left\lceil\sqrt{\frac{WN}H}\right\rceil&
R_0&=\left\lceil\frac H{L_0}\right\rceil=\left\lceil\sqrt{\frac{HN}W}\right\rceil.
\end{align}

Observe that $L\le\min{\{W/C_0,H/R_0\}}$ is sufficient, and $L\le L_0$ is necessary:

\begin{align}
\frac{WH}{L^2}&\ge\left\lfloor\frac WL\right\rfloor\left\lfloor\frac HL\right\rfloor=CR\ge N\\
L&\le\sqrt{\frac{WH}N}=L_0,
\end{align}

with equality only if $W/L_0$ and $H/L_0$ both are integers. As a result, the optimal solution has dimension either $C_0\times\lceil N/C_0\rceil$ or $\lceil N/R_0\rceil\times R_0$.


Cost of shifting a number I was wondering what would be a time complexity of shifting a binary or a decimal number?
For example: 0011, when I shift it left I get 0001.

I was thinking that the time complexity is $\Theta(n)$, because we have to shift every number.

I need it to calculate $m*{b^\frac{n}{2}}$, where $m$ is some number
and $b$ might be 2 (in case of binary) or 10 (decimal).
Therefore instead of multiplication, I just shift to multiply, and therefore complexity is $\Theta(n)$.

Am I correct or is my thinking wrong?

Time complexity is not god-given but is rather defined by the model of computation. To take a simple example, what is the time complexity needed for adding two numbers? In the RAM machine model, this operations takes constant time, as long as the numbers are not "too big". The rationale is that modern hardware implements addition as a fast machine instruction; if the numbers are not "too big" then they fit into single registers. The same reasoning holds for shifts. You have to be careful, however, that the size of the relevant quantities doesn't blow up.


Shortest common supersequence with Genetic Algorithm I'm trying to solve the shortest common supersequence with Genetic Algorithm.
I found it a little bit hard to reduce the size of the chromosomes in each generation.

I know that the maximum size of the chromosome is the total length of the strings.
Even if we create a "naive" genetic algorithm:
Totally random strings (with different length) as initial population, mutation that replace a character, fitness that return how much strings that chromosome contains etc.
How the crossover can reduce the size of the chromosome length?
If we choose n-points crossover, the length of the children cannot be smaller than the shorter parent.

So how genetic algorithm can solve such problems that need the shortest chromosome length? How crossover can reduce the chromosome length?

As is usual, you will really have to think for yourself what makes sense for the
crossover function.  But here is the naive approach (without really knowing your
problem).

Let $s_1$ and $s_2$ be the strings you want to find the shortest common
supersequence for.  Let $\text{superseq}(x, s_1)$ be the number of characters in
$x$ that form a supersequence.

For individuals $x$, $x'$, define

fitness: $f(x) = \text{length}(x) - \text{superseq}(x, s_1) - \text{superseq}(x, s_2)$ (we want to minimize $f$)
mutation: $m(x) = \hat x$, where we obtain $\hat x$ from $x$ by randomly changing, deleting, or adding a character
crossover: $c(x, x') = x[i, j] + x'[i', j']$ for randomly drawn $i \leq j$, $i' \leq j'$.

In other words, the crossover simply picks a random (consecutive) substring of
each of the individuals and concatenates it to make a new.  There are many more
options, you can pick a string smarter (keeping only certain missing
characters), you can interleave the strings, e.g. shuffle the string $\chi =
0^{\text{length(x)}}1^{\text{lenth(x')}}$ and let the result of the crossover be

$$ \left[ x[i] \text{ if } \chi_i = 0 \text{ else } x'[i] \text{ for } i \in \text{range}(\text{length}(\chi) \right]. $$


The halting problem for laymen This line from Wikipedia made me want to ask this question:

  There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans are tasked with the inspection. The theoretical reason for this is the undecidability of the Halting Problem: there cannot exist some algorithm which determines whether any given program stops after finitely many computation steps.

Wondering what this is and what it means. Why is the Halting Problem undecidable. I don't understand, I feel like I could tell if a program terminates or not. Wondering what an example is of a program you can't tell will terminate or not.

How about the Collatz Conjecture:

def f(n):
   if (n % 2 == 0):
      return n/2
   else:
     return 3*n + 1
n = read_input()
while (n != 1):
  n = f(n)

Will this program always halt? Nobody knows! It's an open problem in mathematics. You can run it for specific instances, and if it halts, you know that it halts. But if it doesn't halt, you never know when to quit. You could run it for 1000000 steps, but maybe it halts after 1000001 steps?

We may be able to intuitively determine which programs halt. This is because we write programs in ways that make their halting obvious: we write loops over finite numbers, we try to have recursion over strictly smaller arguments.

It turns out there is a large class of programs which are guaranteed to halt, and almost everything you can think of falls into this class. So most of the time, things you're running across on a daily basis will halt. But not every program is in this class.

The Halting problem says that there is no algorithm which can take any program which halts and return whether it halts or not. It doesn't mean that, given a specific program, we can never know if it halts.


Is the language of all ucv with u ≠ v context-free? Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL?

In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is not a $CFG$.

This is a CFL, but the complement (with equality) is not. Notice that both the language and the complement become CFL when you mirror one of the two words.

To show that this is a CFL, you can design a PDA that guesses the letter at position $i$ that will be different in $w_1$ and $w_2$. It start by reading the first $i$ letters of $w_1$ and pushing $i$ symbols to the stack up to this letter, and remembers the letter $a$ in $w_1$ at position $i$. Then, it waits to read $c$, and pops the $i$ symbols off the stack. It accepts if the current letter (at position $i$ in $w_2$) is not $a$.

You have to also treat the case of different lengths, but it's not hard, I leave it as exercise ;)


Print the number of subarrays of an array having negative sums Problem statement: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $[1,-2, 4, -5, 1]$ there are 9 subarrays whose sum is negative. Subarray means sequential array within an array.

My code: It's complexity is $\theta(n^{2})$ as we can see. I have applied brute force technique. How can I improve my code/pseudocode?

    int sum=0,count=0;
    for(int i=1,k,j;i<=N;i++){
        for(k=1;k<=N-i+1;k++){
            for(j=0;j<i;j++){
                sum += arr[j+k-1];
            }
            if(sum<0)
                count++;
            sum = 0;
        }
    }

An $O(n \log n)$ solution:

Find prefix sums $S[i] = \sum_{k=0}^{i} a[k]$

Set $S[-1] = 0$

Now count the number of inversion pairs in $S[-1], S[0], \dots, S[n-1]$


Finding number of memory locations in chip I was solving some old MCQs and found this question:

A RAM chip has 7 address lines, 8 data lines and 2 chip select lines. Then the number of memory locations is _____.
(A) $2^{12}$ (B) $2^{10}$ (C) $2^{19}$ (D) $2^{13}$

Assuming a word consisting of a byte, this should have
2 chip select lines, meaning total $2^2$ chips.
With 7 address lines, we can address $2^7$ memory locations in a chip.
8 data lines should be used to access only the data in the memory location, and not to specify any location.
That'll make for a total of $2^2\times2^7=2^9$ memory locations. But none of the option matches my answer. What should be the correct answer?

Here is an actual chip! From the '70s :

Motorola MC6810

https://upload.wikimedia.org/wikipedia/commons/f/f8/Motorola_Microcomputer_Components_1978_pg08.jpg

http://www.icpdf.com/MOTOROLA_datasheet/MCM6810_pdf_874837/#view

128 bytes : 128 * 8bits = 1024 bits = $2^{10}$ "memory cells".

I suppose the author considers each bit in a RAM as a "memory location", the way a memory is addressed, the data bus width, doesn't change its capacity : A 1Mega * 8bits RAM has the same capacity as a 512k * 16bits.

On the MC6810, there are 6 chip select inputs, but they are used to ease the selection of different chips connected in parallel, they don't add to the RAM storage capacity.


Error estimates of piecewise-linear curve approximations In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about this functionality:

The FPLOT function begins with a minimum step of size (XMAX-XMIN)*TOL.
The step size is subsequently doubled whenever the relative error
between the linearly predicted value and the actual function value is
less than TOL.

So, if I plot a curve based on some expression and with some predefined tolerance TOL, is the error of the line segment approximation between any two calculated points always lower than TOL? Unfortunately, this is not obvious for me.

If not, how could one achieve a guaranteed (small) error of a piecewise-linear curve approximation (compared with the "exact" curve).

It is impossible to achieve a guaranteed small error for general functions. If the function is given to you as a black box, for all you know it could be the constant zero other than some specific point in $[0,1]$ in which it is very large. If you have bounds on the first two derivatives, however, then you should be able to use Taylor's formula to accomplish your guaranteed approximation.

Matlab's function probably uses some heuristic, which works for reasonable functions. The idea of this heuristic is to empirically estimate the derivative of a function at a point by computing $[f(x+\epsilon)-f(x-\epsilon)]/(2\epsilon)$ for some small $\epsilon > 0$. When the derivative is large, the step size is small, and vice versa. Your worries are justified: in order to get a bound on the distance from the function, you need to have a global bound on the derivative in the entire interval being plotted, and then you can choose the tolerance accordingly. FPLOT is therefore just an optimization, choosing a larger step size when tolerable. From the description you gave it is not clear whether the step size is doubled once or keeps getting doubled — in the first case this optimization saves you at most half the time, and in the second case you could get large errors. (The first interpretation seems more reasonable.)


What are some of these "high-level" instructions found in CISC architectures? The Wikipedia article on complex instruction set computing says

  Before the RISC philosophy became prominent, many computer architects tried to bridge the so-called semantic gap, i.e. to design instruction sets that directly supported high-level programming constructs such as procedure calls, loop control, and complex addressing modes, allowing data structure and array accesses to be combined into single instructions.

What do these "high-level" instructions that can handle loops look like? What does an instruction for a procedure call (strikes me as something of a nebulous term to use here) look like? Can a loop instruction be strung together with multiple instructions for multiple conditions like in a C loop? Does "procedure call" mean something like an instruction that can pass parameters to a function? "High-level" means nothing here without examples.

I know of two main aspects of complex instructions.

addressing modes.  There are two sub-aspects here:

RISC tend to be load/store machines (that this the only instructions which access memory are those whose sole goal is that access), CISC tend to allow operands to be in memory and to be accessible with a variety of addressing modes.  When each operand can have an independent addressing mode like on the VAX, that make the instruction complex.
the addressing modes of CISC tend to be more complex than those of RISC.  When, like the PDP-10, the number of memory access needed to determine the true operand is unbounded, it makes the instruction complex.

the instructions themselves. That's what you are probably thinking about. Setup of complex stack frames with automatic saving of registers, which register to be saved being determined by a bitmap (see VAX) and other complex context switching state mechanism (see 80386 task gate or whatever their name is), polynomial evaluation (see VAX), insertion in a linked list (I don't remember where I've seen that and don't want to dig it out, VAX and PDP-10 are candidates), it is folklore (I don't know how true it is) that some machines in the IBM 360 family had instructions who where designed for the only usage of  improving their Cobol library sorting function.

I think they all can be regrouped with one characteristic: complex instructions are those who need to do a relatively large (and I'd not argue strongly against defining large as being greeter than one), sometimes variable number of memory accesses.  That characteristic brings true nightmare:

you need a relatively complex state machine to handle them, and to decide how to handle interrupts during the time they execute;
you need to be handle multiple page fault (in simple instruction you have two: one for the instruction, one for the data memory) which means that they may be interrupted and resumed for internal reasons several times, making the first issue more important.


Does "serializable" also mean that it's lockable Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "serializable" also means that the schedule is lockable or not. What I mean is.. I understand that for the schedule to be isolated, you have to have non-conflicting reads & writes, but then it also says "if the transactions are not isolated(i.e., serializable).."

By determining if the schedule is isolated, does this include determining if locks(lock-W(x), lock-R(x)) and unlocks can be placed inside the schedule, is "serializable" both isolated and lockable?

lockable - can locks and unlocks be placed inside the schedule at appropriate R/W-intervals.

Here's the question:

  a). Two transactions are shown below. The statements of the transaction are executed from top to bottom. Specify whether the current schedule meets the Isolated property of ACID and why or why not. If the transactions are not isolated (i.e., serializable) specify what concurrency problem may occur with this schedule. Be specific about what statement(s) in what transaction(s) causes the issue.

$$
\begin{array}{}Time&Transaction \, 1&Transaction \, 2
\\1&Read(B)&Read(B)
\\2&\_&Update(C = C + B)
\\3&Read(C)&\_
\\4&\_&COMMIT \, or \, ROLLBACK
\\5&Update(A=B+C)&\_
\\6&COMMIT\, or \, ROLLBACK&\_\end{array}
$$

The definition of serializable schedule is pretty clear. Intuitively, it is a schedule which is equivalent to a serial schedule.

More formally, according to [1] :

  A serializable schedule over a set S of transactions is a schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed transactions in S.

In your example the schedule is definitely serializable, since it is equivalent to running Transaction 2 and then Transaction 1.

I don't know what do you mean by "lockable" and not sure that this term can be applied to a schedule.

[1] R.Ramakrishnan and J.Gehrke, Database Management Systems,  3rd edition


How does one formally show that two lambda functions are $\alpha$ equivalent? I was going through the following slides and I wanted to show the following:

$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$

formally. They define a an $\alpha$-conversion on page 15 as follows:

$$ \lambda x . E = \lambda z.(E[x \leftarrow z])$$

however, I wasn't sure how to formally show the statement I am trying to show. Essentially I guess I don't know how to formally show in a proof that two distinct objects actually belong to this same equivalence class. The intuition and idea is clear, but how do I know if I've shown the statement?

In fact if someone can show me how to do the more complicated one too that would be really helpful too:

$$ \lambda x.x (\lambda y . y) \equiv_{\alpha} \lambda y . y (\lambda x. x)$$

how do I know if I've shown what is being asked?

Actually I think page 16 is the one thats confusing me most:

  Using the equation above, one has now the possibility to prove
  $\lambda$-expressions "equivalent". To capture this provability
  relation formally, we let $E \equiv_{\alpha} E^\prime$ denote the fact
  that the equation $E = E^\prime$ can proved using standard equational
  deduction form the equational axioms above (($\alpha$) plus those for
  substitution).

  Exercise 3 Prove the following equivalences of $\lambda$-expressions:

  $\lambda x.x \equiv_{\alpha} \lambda y.y$,
  $\lambda x.x (\lambda y.y) \equiv_{\alpha} \lambda y.y (\lambda x.x)$,
  $\lambda x.x(\lambda y.y) \equiv_\alpha \lambda y.y(\lambda y.y)$.

what does:

  can be proved using standard equational deduction from the
  equational axioms above

mean?

Since there is already an answer that is not helping (because I don't understand the notation) I will add what I thought was the answer but I'm not sure:

I would have guessed that:

$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$

if and only if there is a variable such that if we plug it into the lambda functions evaluates to the same function with the same variables. i.e.

$$ \lambda x. x \equiv_{\alpha} \lambda y . y \iff \exists z \in Var : \lambda x . x = \lambda z. ( (\lambda y . y)[y \leftarrow z] )$$

if we set $z = x$ we get:

$$\lambda z. ( (\lambda y . y)[y \leftarrow z] )$$
$$\lambda x. ( (\lambda y . y)[y \leftarrow x] )$$
$$\lambda x. (\lambda x .x )$$

which I assume the last line is the same as $\lambda x .x$ but I am not sure. If that were true then I'd show I can transform $\lambda y . y$ to $\lambda x . x$ which is what I assume the equivalence class should look like. Where did I go wrong?

By definition of substitution we have
$$x [x \leftarrow z] = z$$
therefore
$$\lambda z . x [x \leftarrow z] = \lambda z . z \tag{1}$$
because $\lambda$-abstraction is a congruence (it preserves equality). By the definition of $\alpha$-equality we have
$$\lambda x . x = \lambda z . x [x \leftarrow z] \tag{2}.$$
By transitivity of equality we get from (1) and (2) that
$$\lambda x . x = \lambda z . z$$
If you require more details than this, you should use a computer proof assistant to check the details.


Viterbi algorithm recursive justification I have a question regarding recursion in Viterbi algorithm.

Define $\pi(k; u; v)$  which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$.

The base case if obvious $\pi(0,*,*)=1$

The general case.

$\pi(k,u,v) = max_{w \in K_{k-2} } \pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$

The author justifies the recursion as folllows:

  How can we justify this recurrence? Recall that $\pi(k, u, v)$ is the highest probability for any sequence $y_{−1}...y_k$ ending in the bigram $(u, v)$. Any such sequence must have $y_{k−2} = w$ for some state $w$. The highest probability for any sequence of length $k − 1$ ending in the bigram $(w, u)$ is $\pi(k − 1, w, u)$, hence the highest probability for any sequence of length $k$ ending in the trigram $(w, u, v)$ must be $\pi(k − 1,w, u) \cdot q(v|w, u) \cdot e(x_k |v)$

I do not understand why it's actually true, I think it's possible to reach $\pi(n,u, v)$ from any $(n-1,w, u)$ not actually the maximum one $\pi(n-1,w, u)$ just because $q(v|w, u) \cdot e(x_k |v)$ might have a higher influence on the resulting $(n,u, v)$ than any $\pi(n-1,w, u)$.

I would appreciate if anyone could explain me why it's true.

The maximum is over the entire expression $\pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$, for exactly the same reason that is worrying you. Moreover, under your original interpretation, there is no reason to keep $\pi(k-1,w,u)$ for the non-optimal $w$. We are forced to store $\pi(k-1,w,u)$ for all $w$ exactly for the reason you mention.


Branch wrong prediction pipeline Let's say we have a pipeline with 20 stages. If the testing for the jump condition is done at stage 14 and we have a wrong prediction, then the instructions processed in those 14 stages, that shouldn't have been processed due to the wrong prediction made the processor lose 14 cycles. We know that the jump instruction entered the pipeline 14 stages back, therefore from this behaviour I deduced that 14 cycles were lost. Am I correct? If no, why?

It's not correct. The instruction that would determine the result of the condition is read at cycle x. The conditional branch is read at cycle x + k. k can be any value, depending on the code. For example I can have a comparison "compare x and 0", then half a dozen unrelated instructions, then an instruction "branch if the comparison result is 'greater'". You are saying the correct condition is determined at cycle x + 14. You lose 14 - k cycles.

You may find out 14 cycles later that the branch was predicted wrongly, or 8 cycles later, or in the next cycle. What is lost is the cycles between branch prediction and the point where the correct way became known, which is variable. In this situation, compilers will often try to issue the comparison as early as possible before the branch instruction, to minimise the penalty for an incorrect branch.

To clarify: If a compare instruction is read at cycle x, and the result of the comparison is available at cycle x+14, and a conditional branch instruction is read at cycle x + k, then it doesn't matter at which stage in the pipeline the incorrect branch is detected. What matters is the time from the start of the conditional branch, to the time of detection of the incorrect branch, and that time is variable. If the compare instruction is issued early enough then the branch isn't even predicted because the result of the compare instruction is known.


Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion? The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when minimizing the resulting DFA. The most common case is when states are "unreachable" from the corresponding start state.

I am interested in the following question: if we have an NFA with $n$ states and $q$ symbols, is there a $\mathrm{poly}(n, q)$-time algorithm to output the number of states that the standard conversion (and minimizing, if possible) to a DFA would produce? Note that producing the DFA itself can take exponential time.

It is well known that NFA universality (given an NFA, does it accept all words?) is PSPACE-complete. This easily implies that the following problem is PSPACE-complete:

  Given an NFA, is there an equivalent DFA with exactly one state?

To show that the problem is in PSPACE, note that in order to show that an NFA isn't equivalent to a DFA with exactly one space, it suffices to show that its language is not universal (known to be in PSPACE) and non-empty (can be checked in P).

To show that the problem is PSPACE-hard, we reduce from NFA universality. Given an NFA $A$ over the alphabet $\Sigma = \{0,1\}$, we construct an NFA for the language $L = \epsilon + 0\Sigma^* + 1L(A)$; this requires adding a constant number of states. The language $L$ is never empty, and it is universal iff $L(A)$ is, hence $L(A)$ is universal iff $L$ is accepted by a DFA having a single state.


Succinct data structure for "bookkeeping problem" I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array.

Currently I use an each bits of an other array to track it.
Let's say I have a byte array of 8k elements if I want to know if a place is taken (without accessing to the array), I need a 1k byte array (8 bits per byte) to track it. So I have more or less these complexities:

Check: $O(1)$
Change: $O(1)$
Memory: $O(n/8)$

I wanted to know if there's a more memory optimized data structure keep the constant check factor because I have the following properties:

The targetted array has a fixed size known at compile-time
Most of the actions performed are Check (maybe 10k-1k checks for one change)
The array is mostly sparsed (5-25% used)
There are only few space freeing
Sometimes a value take more than one byte but I only need to keep track of the first one.

I'm looking for data-structures name or samples. Thanks.

Let's suppose that there the occupancy rate is 25%. Then given an array of $n$ elements, there are ${ n \choose 0.25n}$ possible bitmaps. The theoretical minimum number of bits per entry that you need is, then:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.25n } \approx 0.81$$

At 5%, the minimum number is:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.05n } \approx 0.29$$

Note that I didn't actually calculate it this way. I used the binomial entropy function:

$$B(p) = -\left(p \log_2 p + (1-p) \log_2 (1-p)\right)$$

Then $B(0.05) \approx 0.29$.

So given a 25% occupancy rate, there is no data structure which compresses better than 80% of the size of the uncompressed bitmap.

Given that it sounds like you have a real problem to solve, does shaving 20% off the size of the bitmap seem like a reasonable benefit, given that the cost is likely to be a much higher-constant-factor data structure?

Besides, 1kB just isn't that big. It's a fraction of a page in size, and likely to be in cache most of the time if this is really your inner loop.

EDIT

OK, if you really need this, I suspect that succinct hashing might be your best bet. There are dynamic bitmap data structures which support the rank operation, but none of them have constant time queries to my knowledge.


Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well) This problem probably falls under some category of algorithms but I don't know which.

  A given restaurant has $b_1..b_n$ branches around the world. A food critic has to travel all of the branches.

  When the critic finishes visit to the branch $1 \le j\le n$ he gets paid $m_j$ money by his employer for the job.
  For branch $j \le n-1$ he takes a flight to the next branch $b_{j+1}$ while the flight costs $c_j$ money. From the last branch $b_n$ a flight goes out to the first branch $b_1$ for the cost of $c_n$.

  It is also given that the total amount of money the critic received equals the total cost of flights so:
  $$
\sum_{j=1}^n m_j=\sum_{j=1}^n c_j
$$
  At any given point the critic can only pay for the next flight out of the money he currently has.

  Lastly, the critic can choose any branch which he will visit first and the first trip will be free.

  Prove that the branch $j$ exists such that the critic will be able to start from $b_j$ and visit all branches and suggest an algorithm which will find such a $j$ in $\Theta(n)$ time.

The hint which was given to us is to use queue data structure.

I thought of the following algorithm:

1) Add all branches to a queue.

2) Check if we can travel to the next branch that is if $m_j \ge c_{j+1}$.

If no, that means we don't have enough money so push the branch to the tail of the queue.
If yes, check if $m_j+m_{j+1} \ge c_{j+1}+c_{j+2}$ that is if the critic does travel to the next branch will he have enough money to continue from that branch?

--If yes then advance one branch in the queue.

--If no push the next branch to the tail of the tail of the queue

After one traversal of the queue we should have branches in such an order that the critic can complete the journey and branch $j$ will be at the head of the queue.

I'm on the right track? I'm not sure this proves formally enough that a $j$ indeed exists so the critic can complete the journey.

The algorithm that you suggested using a queue does not seem to be linear-time with respect to $n$, because you did not prove that each restaurant gets pushed in the queue only once (or at most a constant number of times). I suppose there are cases where a restaurant gets pushed into the queue nearly $n$ times.

However, there is a simple algorithm for this problem and I got the idea based on a similar question in `Introduction to Algorithms' by Cormen et al. The main idea is to start from the first restaurant and fly as much as possible, until we run out of money. If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money. It is easy to see that the next starting point is exact the place where we run out of money (because previous restaurants did not pay enough money for sustaining).

Let $i \gets 1$;
While ($i \leq n$)
$~~~~$ Let $money \gets m_i$;
$~~~~$ Let $starting \gets i$;
$~~~~$ While ($money \geq 0$)
$~~~~~~~~$ Let $money \gets money - c_i$;
$~~~~~~~~$ Let $i \gets i + 1$;
$~~~~$ EndWhile;
EndWhile;
Output $starting$;

The main idea behind the proof is mentioned in my second paragraph. Once you start from a restaurant $b_i$ and run out of your money in a restaurant $b_j$, you can make sure that none of the restaurants $b_i$ to $b_{j-1}$ are not good starting points.

How to prove that such $starting$ exist? It is possible to show that by contradiction. We know that:

$$\sum_{1 \leq i \leq n} m_i = \sum_{1 \leq i \leq n} c_i,$$

which is equivalent to:

$$\sum_{1 \leq i \leq n} m_i - c_i = 0.~~~~(Eq. X)$$

Let us assume that there is no such $starting$ for which the person can start from restaurant $b_{starting}$ and visit all restaurants maintaining a positive amount of money in his pocket. We know that starting from restaurant $b_i$, if we run out of money in restaurant $b_j$, this means that for every restaurant $b_k$ ($i \leq k < j$) there is no way to pass restaurant $b_j$ (because we will definitely run out of money). Given our assumption that no such $starting$ exist, this means that we will have a bunch of pairs $(b_{i_1}, b_{j_1}), \cdots, (b_{i_m}, b_{j_m})$ ($i_{x+1} = j_{x}$) that all result in running out of money. This means that for every pair $(b_{i_x}, b_{j_x})$ we have,

$$\sum_{i_x \leq y \leq j_x} m_{i_y} - c_{i_y} \leq 0,$$

which results in either of the following two cases: (1) The money becomes zero and the critic does not have money to catch up with the next flight and cannot continue flying, (2) The overall summation becomes negative, which is in clear contradiction with our very initial assumption in Eq. (X).


Intuition about decidability Given a language, how do you go about deciding if it's decidable or not? For example:

Given a DFA $A_0$ and a TM $M_0$

$L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$

$L_2 = \{ \langle A \rangle \, | \, A \mbox{ is a DFA and }L(A) = L(M_0) \}$

What's the intuition/process of figuring out if $L_1$, $L_2$ are decidable or not?

This is not homework, $L_1$ is not decidable and $L_2$ is decidable, but I have not idea why, and how to solve this problem and problems similar to it. If you could explain to me the process of doing that you will help a lot.

For the first undecidable language $L_1$ you can apply the Rice's theorem:

Theorem (Rice’s Theorem): Let L be a language of the form

$L = \{ \langle M \rangle | L(M)\mbox{ has some property }P\}$,where

P is non-trivial, i.e. there exist at least one machine M such that $\langle M \rangle \in L$, and at least one machine $M$ such that $\langle M \rangle \notin L$.
P is indeed a property of the language of TMs, i.e. whenever $L(M_1) = L(M_2)$,
we have $\langle M_1 \rangle \in L$ if and only if $\langle M_2 \rangle \in L$.

Then L is undecidable.

You can pick a Turing machine that decides $A_0$ and one that decides $\overline{A_0}$, so $L_1$ asserts a nontrivial property of $\langle M \rangle$, and so it is undecidable.

For the second decidable language $L_2$ the machine $M_0$ is fixed (it is not part of the language).
So $L(M_0)$ is regular or it is not regular. If it is not regular then $L_2 = \emptyset$ (trivially decidable). If $L(M_0)$ is regular then there is a DFA $A_{M_0}$ such that $A_{M_0} = L(M_0)$ and the language $L_2$ becomes:

$L_2 = \{ \langle A \rangle | L(A) = L(A_{M_0}) \}$

but the equivalence of two DFAs is decidable, so $L_2$ is decidable.


Constructing solution to 3SAT formulas using oracle queries I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula true. Note: this does not say what the assignment to the variables is, just that there exists one.

My main question is: can we get the actual solution of the formula in polynomial time, using the oracle?

My first thought was that no, it is impossible because the oracle cannot help you with an assignment (i.e., if I gave an assignment to the variables, the oracle's answer does not change). However, just because this technique does not work does not mean that no techniques will.

I then thought to give an assignment to the first variable $x_1$, and then use that to work on the next variables; however, I don't know how to progress from there without trying all possible combinations (i.e., running in time $O(2^n)$).

You have the right idea. Suppose you have a SAT oracle and an instance $I$ of 3SAT (or whatever SAT-ish class you like) containing $n$ variables, $x_1, x_2, \dotsc x_n$. You could then do this:

send I to the oracle
if the oracle answers "not satisfiable"
   quit
else
   j = 1
   I_0 = I
   repeat
      transform I_{j-1} to I_j by substituting x_j = 1
      send I_j to the oracle
      if the answer is "satisfiable"
         save x_j = 1
      else
         save x_j = 0
         transform I_{j-1} to I_j by substituting x_j = 0
      j = j + 1
  until j = n

When the algorithm terminates, you'll have saved a satisfying collection of values for all the variables. This will be linear in $n$ (times the steps necessary to do the substitutions, which will be polynomial in the length of $I$).


Number of automorphism for clique of 6 vertices minus two non adjacent edges How many automorphism does a clique with 6 vertices have, when we take two edges from it (two edges that don't have the same vertex)?

I thought the answer is 6*(n-2)!
Number of automorphism for a full graph Kn is n!. Clique can be seen as a full graph since all of the vertices must be connected to each other. Since we take away two edges I think it should be (n-2)!. And it has to be multiplied by 6 because there are 6 vertices all together so was still permutate them.

Is this correct? How to find this correctly? What if there are N vertices?

It's not hard to check that $(1\; 2)$, $(1\;3)(2\;4)$, and $(5\;6)$ are all automorphisms of the graph. Considering the degrees of vertices, this shows that the orbits of the automorphism group $G$ are $\{1,2,3,4\}$ and $\{5,6\}$. According to the orbit stabilizer theorem, $|G| = 4|G_1|$. Once again, it's not hard to check that $(3\;4)$ and $(5\;6)$ are automorphisms in $G_1$, and consider degrees and the property of being connected to $1$ shows that the orbits of $G_1$ are $\{3,4\}$ and $\{5,6\}$. It is not hard to check that all 4 permutations respecting these orbits are in $G_1$, and so $|G_1| = 4$. We conclude that $|G| = 16$.

Informally, $1$ can get mapped to any of $1,2,3,4$. Assuming that $1$ gets mapped to itself (without loss of generality), we see that $2$ has to get mapped to itself, $3$ to one of $3,4$, and $5$ to one of $5,6$. These are the only constraints, so in total there are $4\cdot 2\cdot 2 = 16$ automorphisms.


Is there any way to "pre-compute" a huge dataset in order to make *any* arbitrary linear-time computation on it sub-linear? Suppose that you have a huge (terabytes worth) collection of numbers, and you know that you will, in a future, need to run some statistics of it. In order to cut future work, you notice that, by pre-computing some key statistics, you can make other statistics be computable in sub-linear time.  For example, if you store the sum and the length of the collection, you can, in a future, compute the average in linear time. If you also store the variance, you can compute the standard deviation. You can keep adding specific statistics in hope to cover as many "future computations" as you could.

My question is: is there any way to prepare the dataset such that any arbitrary linear-time function could, in a future, be processed in sub-linear time? In other words, is the snippet below possible?

# builds an ideal pre-computation of an arbitrary bit string
precomputed = precompute(arbitrary_bit_string)

# builds a circuit for a "countOnes" function
# could be any other arbitrary linear-time function
countOnes = buildCircuit("... an String->Int algorithm here ...")

# computes the number of ones in sub-linear time
average = execute(precomputed, countOnes)

Multiplying the size of the dataset you have to pre-calculate over does not increase the amount of time it takes to calculate the average when the sum and length are pre-calculated; it will be a constant time operation. Moreover, calculating the sum and length of a dataset in itself is only linear time (doubling the dataset will result in doubling the amount of time it takes to pass over all data and therefore is only linear, the 'addition' operation is constant-time and does not contribute to the time complexity).

However, I think what you meant is the following:

If I had any possible data readily accessible, would that mean I can run a more optimal algorithm over this new dataset than I could over the original dataset?

The answer is no.

Some examples:

The original dataset contains 10 integers. We want to calculate the total when we multiply each number by every other number. This is an O(n^2) algorithm since for each element we have to pass over all other elements.
If we had precalculated the set resulting from multiplying each number by all other numbers it would only take linear time; O(n) since we only have to sum the numbers in the dataset. So for this function the hypothesis holds.
The original dataset contains 10 integers. We want to calculate the sum of the first two numbers. This will take O(1) time, as the size of the dataset does not increase the time it takes to sum the first two numbers. Now assume that we had precalculated this value then it would still be an O(1) algorithm. After all, no (0) time is still considered constant time.
The original dataset contains 10 integers. We want to know the value at the first index. This is obviously a constant time O(1) function and, as a result, one that cannot be done more efficiently regardless of any precalculated data.

P.S. do note that this is only the purest sense that it does not hold for every function; it might very well be that every real-world application can more efficiently be run over a set containing pre-calculated data).


Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to find the connected subgraph (not sure about this terminology) with maximum number of edges, among all the connected subgraph of $C$ that satisfy the following:

includes vertex $v_1$
has exactly $m$ number of vertices (including $v_1$)

By connected subgraph of $C$, I mean a subgraph of $C$, such that each pair of vertices in it are connected by a path.

It's NP-hard (by reduction from clique problem).
Let $G$ be an arbitrary graph, and we want to check if there exists a clique of size $m-1$ in this graph. This problem is NP-hard. By adding $v_1$ to the graph and connecting it to all vertices in $G$, we reduce the clique problem to your problem (since clique, when exists, has the maximum number of edges).


Bottleneck TSP with MST There is a problem I don't know the answer too.
The 3 approximation for the bottleneck TSP that involves first getting the MST.
I have not been able to come up with the right "shortcut" method so far.

To be more specific.

The problem comes from Cormen's Introduction to Algorithms 3rd edition . The problem is

  In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial time approximation algorithm with approximation ratio 3 for this problem. (Hint:Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

I can prove that the MST is also a bottleneck spanning tree, however when I search online and Google scholar for the step where we walk on the bottleneck spanning tree, all of the articles are on much better approximations, and I can't seem to find any reference to this type of argument online.

You need to prove by induction the following claim:

  Let $T$ be a tree rooted at $r$ with at least two vertices. You can list the vertices of $T$ in a sequence such that the distance (in $T$) between two adjacent vertices (including the first and the last) is at most $3$, and furthermore the vertex following $r$ is adjacent to $r$ (in $T$).

(The induction is on the number of vertices.)

Given this, you argue as follows. Suppose that there is a Hamiltonian cycle with heaviest edge having weight $w$. Then there is a spanning tree whose heaviest edge has weight $w$. So the heaviest edge in the bottleneck spanning tree has weight at most $w$. Apply the claim to that tree, and consider the corresponding Hamiltonian cycle. Since the tree distance between adjacent vertices is at most $3$ and thanks to the triangle inequality, the heaviest edge in the resulting cycles weighs at most $3w$.


Maximum matching for general graph I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must recur to the blossom algorithm.
The explanations that I found (1. here, 2. and here) are based on the fact that the direction that I choose to start exploring an odd loop in the Depth First Search (DFS) could make me miss an augmented path.
But it seems to me that this issue can be solved by considering the same vertex distinct during the DFS if I am entering it through a matched edge or an unmatched one, why isn't this enough?
To be more precise, what I mean is that during a DFS, you still avoid loops, so you stop if you enter a node that is already in the path between the root and the current node, but you still explore nodes that you have visited in previous paths if you are entering them from a different type of edge (matched or not matched).

I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be simple). This seems to entail keeping track of all, or at least all minimal (w.r.t. set inclusion) sets of vertices used on the path to each vertex considered in the BFS so far, which in the worst case would multiply time (and possibly space) requirements by a factor exponential in $|V|$.
Why is it not necessary to explicitly keep track of which vertices have been used in the usual Hopcroft-Karp algorithm for maximum matching in bipartite graphs, which considers each vertex only once? Because the BFS step used in that algorithm to find augmenting paths automatically ensures that all paths from the BFS root are shortest paths, and thus that they are all simple.


Relaxing the stack in a push down automata Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol can succeed (i.e. "getting rid" of the stack), we get a non-deterministic finite automata.

If we convert two such PDAs, whose languages recognized are the same, and assuming all states are reachable, to NFAs in this fashion, are the languages recognized by the NFAs still the same?

Here's a simple example.  Consider the language $\{a^n b^n : n \in \mathbb{N}\}$.  Here's one simple PDA for it.  The PDA has two states, $q_0,q_1$.  When it is in state $q_0$ and it reads the symbol $a$ on the input tape, it pushes $A$ on the stack and remains in state $q_0$.  When it reads the symbol $b$ on the input table and the stack is non-empty, it pops whatever is on the stack and moves to state $q_1$.  The PDA accepts if the stack is empty at the end of the input string.  If we convert this PDA to a NFA, we get a NFA with two states $q_0,q_1$ and transitions $q_0 \stackrel{a}{\to} q_0$, $q_0 \stackrel{b}{\to} q_1$, $q_1 \stackrel{b}{\to} q_1$.  This NFA accepts the language $a^* b^*$.  There are other ways to build a PDA for the language $\{a^n b^n : n \in \mathbb{N}\}$; if we apply the same conversion to them, does the corresponding NFA always accept the language $a^* b^*$?

I think the answer is no, even if we disallow unreachable states.

Consider the language $L$ given by the grammar $S ::= \varepsilon \mid abS \mid aSb$.  In this language, every word $w \in L$ has the same number of $a$'s and $b$'s, and every prefix of $w$ has at most as many $b$'s as $a$'s.  Also, if $w \in L$ is not empty, then $w$ starts with $a$ and has length $\ge 2$.

First PDA

Here's one PDA that can recognize that grammar.  It has two states $q_0,q_1$, and the following transitions:

$q_0 \stackrel{a,\epsilon\to \alpha}{\to} q_0$

$q_0 \stackrel{b,\alpha \to \epsilon}{\to} q_0$

$q_0 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_1$.

The state $q_1$ is the accept state, and both states are reachable.

If you convert this to a NFA, then the NFA accepts the language $(a|b)^*$.

Second PDA

Here's another PDA that accepts the language $L$.  It has four states $q_0,q_1,q_2,q_3$, and transitions

$q_0 \stackrel{a,\epsilon \to \alpha}{\to} q_1$

$q_1 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_1 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_2 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_3$

Here $q_0,q_3$ are the accepting states.  All states are reachable.

If you convert this to a NFA, it accepts the language $\varepsilon | a (a|b)^*$.


Is computation independent of hardware? We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is not dependent of how we make our computers, then does the same principle which apply to a computer apply to how brain works?
I want to know if computation is an abstract object which then is realized as computers. In other words, if we visit some alien civilization we expect that our mathematicians and physicists understand the alien physics and math. Is it the same as with the notion or concept of computation?
It seems that in order to consider computation first we need consider a realization of a machine or a model. For example according to the first two lines of this question there are Turing machine, circuits and lambda calculation. How do we know that there is not another way of computation? For example, the way the brain works and does computation might not be describable by the computation which we consider in Turing machine.

To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry.

To answer the title question, yes, computation is independent of hardware. Computation is defined by the transformation of information, not by how it's embedded in the real world. This is easy to see: all the computation models have a mathematical formulation, and you can write mathematics as symbols on paper. In fact, many models of computation, such as the lambda calculus (1936) and Turing machines (1936) were invented before there were general-purpose computing machines (there were numeric calculators and data sorters, but programmable machines didn't exist until the 1940s).

It is possible to model today's computers by mathematical tools. They're just finite-state machines, after all. There are a lot of states, so a complete pen-and-paper representation is not feasible, but if you only model the part that you're interested in, that can be within reach.

As to whether there is only a single notion of computation, we don't know. We think so: that's the Church-Turing thesis. We think so because we've invented a lot of models of computation, and they all turned out to be equivalent. Some of them are easier to work with than others, or more directly applicable to certain problems, or are a closer match for certain computing hardware (e.g. in terms of performance or locality). But they can express the same computations.

Are Turing machines (or any of the equivalent concepts) the last word on the topic? We don't know. We certainly have weaker models of computation, but we think of them as restricted computation. And we have stronger models of computation, but we think of them as “magic“ — we can reason about them, but we have no idea how they could be implemented.

Is the brain a Turing machine? That's a question about the brain, and we don't know. We know that it's at least as powerful as a Turing machine, since it can simulate one. We are very far from being able to accurately simulate a brain with a Turing machine, but we don't know whether that's a matter of scale (a brain has tens of millions of neurons — a PC doesn't have enough memory to even store all the connexions). We do tend to think of brains as being more powerful than computers — when a problem is undecidable (in the Turing computation sense), we offer to solve it by thinking, but that doesn't answer the question. When we solve a problem by thinking, the solution is expressible in Turing machine terms. The problem solving method, however, may or may not be more powerful than Turing machines.

Would aliens have the same notion of computations? We don't know. We think so — mathematics seems universal to us — but that's a question about aliens, and since we don't know anything about aliens except what your imagination tells us, we can't answer it.


Modifies Dijkstra’s Algorithm to find the maximum cost path In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?

This will not work. Consider

(a)-4->(b)
(a)-1->(c)
(b)-2->(d)
(c)-6->(d)

Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.

See here for an alternative based on a topological sort.


What can't guarded fragment of FO express? I have some basic confusions about the definition of the guarded fragment of first-order logic. Hopefully someone can tell me where I'm wrong.

GF in FO is defined by:

Atomic formulas, $x=y$ and $R(x_1,...,x_n)$, are guarded formulas.
If $\phi,\psi$ are guarded formulas, so are $\neg \phi$ and $\phi \wedge \psi$.
For variables $\{x_j,...,x_m\} \subseteq \{x_i,...,x_n\}$ and guarded fomula $\phi$ and atomic formula $A$, $\exists x_j\ A(x_i,...,x_n) \wedge \phi(x_j,...,x_m)$ is a guarded formula.

My reasoning is: for arbitrary FO formula of form $\exists x\ \phi$, I can just pick some relation $T$ that's always true and over all variables, and it's then equivalent to $\exists x \  T \wedge \phi$, a guarded formula. Other forms follow from this. So FO reduces to GF.

But that's obviously not true. I can't figure out where my mistake is. Could someone let me know where I got it wrong?

For example, isn't
$$
\forall x\ \exists y\ \forall z\ \phi
$$
equivalent to
$$
\forall x\ (T \to \exists y\ (T \wedge \forall z\ (T \to \phi)))
$$

You're correct that, if the structure you're working with has a universal relation, then using that relation as a guard is equivalent to having no guard at all. However, you don't get to pick the interpretation of the relation symbols. For example, if you're trying to write a formula that is satisfied by exactly the class of 3-colourable graphs, then you should think in terms of an adversary supplying you with an arbitrary graph and your formula has to give the right answer, without being able to rely on any particular properties of the structure you're given.


Searching the best trading route - algorithm Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount c of good d.

I have made a simple table to point out what I am trying to explain:

In this case there are three different goods: Wood, Sand and Gras.

I also live in the village and noticed that the prices of the traders vary greatly. I have 1 wood and want to increase it by simply trading between the five dealers. But: I must not visit a dealer more than once.

There would be different routes, for example I could do Dave - Adam, which would result in +1 wood for me. A better route would be Earl - Berta - Adam, because it would mean +2 wood.

I think at that point you might already know what I am asking for. I am looking for a technique / algorithm to find the route which maximizes my input. The rules are:

Input good = Output good
Output value > Input value
Each node ("dealer") must not be visited more than once
You do not have to visit all dealers
Each dealer is limited to one trade ("Giving amount a of good b for amount c of good d").
$a\in\mathbb{R}_{>0}$ and $c\in\mathbb{R}_{>0}$
The benefit is calculated at the end by output - input, i.e., by the increase in the quantity of the goods that you're starting with (if you start with 1 wood, then all that matters is the number of woods you end with).
It is important that the input good is the same as the output good ("Input good = Output good"). If I start with wood, I need to end with wood. If I start with sand, I need to end with sand, etc.

I don't even know how such a problem is called. That means that anything like algorithm names to solve it, the general name for this kind of problem, etc. would help me to continue with my research. I have already tried approaching it by converting the table to a graph and then run path-finding algorithms. That did not work, because I wasn't sure how to weight the edges and the Longest-Path-Problem was also in my way, which is NP-Hard for non-DAGs.

The traveling salesman problem (TSP) was already mentioned. I had a look at the Wiki page of the TSP. Quote: "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
I think my problem is very different, because:

I look for the most profitable route, not the shortest.
I don't have to visit every dealer ("city").
I must not return to the origin, because as I said each node ("dealer") must not be visited more than once.

The "village" can get quite big. About 200 different goods and 500 dealers, so the algorithm should be able to perform good in this scenario.

The last possibility would be to brute-force, but I really want to avoid that.

This problem is NP-Complete by reduction from Directed Hamilton Path. I use the method of the linked mathoverflow answer. Let's say $b(v)$ and $s(v)$ is the good that villager $v$ buys and sells, respectively (each villager only buys/sells one good). Then you may ask, what dealers can I visit consequtively? This is the following graph:

$$G = \langle \text{Villagers}, \{ (\sigma, \beta) | s(\sigma)=b(\beta) \rangle $$

This directed graph has an edge from $\sigma$ to $\beta$ iff $\sigma$ sells something that $\beta$ buys (using the letters $\sigma$ and $\beta$ because they sound like 's' and 'b' for seller and buyer). In this graph, you are one node called $y$ and you have a good, $s(y)$, which you want to sell. You can verify that you are looking for a route through $G$. How much profit do you make? If $\$_b(v)$ and $\$_s(v)$ are the buying and selling price of villager $v$'s goods, and you travel some route $v_1\cdots v_k$ through the village, then your profit is: (w.l.o.g. assume that you start with $1$ unit of your good)

$$ \text{Profit}(v_1\cdots v_k) = \prod_{i=1}^{k}\frac{\$_s(v_i)}{\$_b(v_i)}$$

This suffices for a reduction from Directed Hamilton Path: Take a directed graph $H=\langle V, E \rangle$, and say you want to find out whether there is a Hamilton Path starting in vertex $x$. Suppose that the $n$ vertices are villagers. Each villager $v_i$ trades his own good for his own good at a $1/1$ ratio. Now populate the village further as follows. For each edge $(\sigma,\beta)\in E$ in the graph, add a "stockbroker" villager called $\tau_{\sigma,\beta}$ who buys $\sigma$'s goods and sells the goods that $\beta$ buys at a rate of two units of $\beta$ for each unit of $\sigma$. That is, $b(\tau_{\sigma,\beta})=s(\sigma)$ and $s(\tau_{\sigma,\beta})=b(\beta)$ at $\$_b(\tau_{\sigma,\beta})=1$ and $\$_s(\tau_{\sigma,\beta})=2$. In this scenario, you are villager $x$.

If your profit problem were easy, then you could ask 'Is there a route from $x$ which makes  $2^{n-1}$ profit?' Iff there is such a route in the graph I constructed, then there is a Hamilton Path in the graph I constructed it from. $\square$

So this problem is NP-Complete and in fact it is hard even to approximate. Instances of the problem that are not contrived are probably more difficult. You can also make an elegant reduction from Traveling Salesman by assigning to each villager a profit $\varepsilon(v_i)=\log\left(\frac{\$_s(v_i)}{\$_b(v_i)}\right)$, I'll leave the details up to you. If you really mean to solve this problem practically, you can look for some advice in this question here (link) and in the extensive literature on TSP and related problems. Personally, I would use a greedy algorithm which looks ahead some fixed number of steps, say $3$ steps. Or you can use an evolutionary approach, which should work just fine, too.

Here's one heuristic: given a candidate solution $v_1\cdots v_k$ computed by an evolutionary algorithm, you can check the intermediate profits halfway along the route, and quickly find the point at which you should have stopped. Fix only the last part of the path $v_j\cdots v_k$.


Bellman-Ford: shortest path my assumption:
- we have an undirected graph with only positive edges
- the edges are sorted alphabetically:
    e.g A-B, A-C, B-D
    and e.g not C-A, D-B, A-B

I do not understand, why we need the first loop (line 1) here.
I executed the algorithm on paper on 3-4 different undirected graphs.
And everytime the first iteration of line1 ends, the algorithms finishes to find the shortest path and the remaining iterations are doing just garbage check.

Can anyone give a concrete graph example where we need the first loop?
Does the first loop to do something with the negative edges or edge direction perhaps ?

1 for i=1 to vertices.length-1
2    foreach e in edges
3        if e.v2.cost > e.v1.cost + e.weight
4            e.v2.cost := e.v1.cost + e.weight
5            e.v2.pre := e.v1

You're correct that there is always an ordering of the vertices for which this algorithm will converge in one iteration, namely the topological ordering given by the shortest-path spanning tree. However, in general the vertices won't be given to us in that order.

Consider for example a path $(C,A),(A,B)$, where $C$ is the source. The algorithm will go through the edges in the order $(A,B),(C,A)$, and will need two iterations to converge.

Here is another example, in which the source it the first vertex: a path $(A,C),(C,B),(B,D)$, where $A$ is the source. The algorithm will go through the edges in the order $(A,C),(B,D),(C,B)$, and will need two iterations to converge.


Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?

I had the same thoughts when i did Complexity course myself.
Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine.
This is by definition of space complexity analysis.


How do I interpret this formal languages definition? Given the formal language

$L_1 = \{wcw | w\in \{a,b\}^+\} $

Does this definition requires $w$ to be exactly the same before and after the terminal character $c$ or can it be different?

Example:

Are $aabca$ or $abca$ accepted words of $L_1$, or only words like $aabcaab$ or $aca$?

It's the same $w$. You can think of this language in a ``procedural'' way: it is  formed by taking every word $w\in \{a,b\}^+$, and for each such word, adding to the language the word $wcw$.

Typically, sets (and languages in particular) are described as $\{x: \text{condition on } x\}$, which is pretty clear. However, it is sometimes more convenient to ``push'' the condition into the description of an element.

That is, you could describe the same language as:
$$\{x\in \Sigma^*:\ \exists w\in \{a,b\}^+\wedge x=wcw\}$$
Or even worse:
$$\{\sigma_1\cdots \sigma_n: \exists k\ge 1,\ n=2k+1\wedge \sigma_1\cdots\sigma_k=\sigma_{k+2}\cdots\sigma_{2k+1}\wedge \sigma_{k+1}=c\wedge \forall 1\le i\le k,\ \sigma_i\in \{a,b\}\}$$

But obviously this is much more cumbersome than the original description.


Multi-level cache for which inclusion holds For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?

L1 must be a write-through cache.
L2 must be a write-through cache.
The associativity of L2 must be greater than that of L1.
The L2 cache must be at least as large as the L1 cache.

This was a multiple-choice question with the following possible answers:

(A) 4 only
(B) 1 and 4 only
(C) 1, 2 and 4 only
(D) 1, 2, 3 and 4

I think L2 cache must be at least as large as the L1 cache but I am confused what the need for writeback is for this cache.

Correct Answer: 1) and 4) only . For inclusion property to hold, every changes in L1 should be made in L2 also. therefore , L1 should be write-through. It is not necessary fr L2 to be write -back. And 4) is mandatory for the same reason i.e L2 would need to hold the contents as same as L1 and as much as ,or may be greater than L1.


Generalization of Horn clauses in logic programming? As far as I understand, Prolog and related languages are restricted to inference rules of the form
$$ p_1 \land \dots \land p_n \rightarrow q$$
which is equivalent to the Horn clause
$$ \neg p_1 \lor \dots \lor \neg p_n \lor q$$
I'm wondering if there are languages that relax this constraint to allow arbitrary disjuctions as clauses in the knowledgebase, and if so what the downsides of this would be. For example, the rule
$$ p \rightarrow q_1 \lor q_2 \equiv \neg p \lor q_1 \lor q_2$$
is not a Horn clause and is not allowed in Prolog, but it seems to me that it would be possible to run a resolution algorithm for such clauses as well. For example, if $p = \top$, then we can prove $q_1 \lor q_2$ by contradiction: we assume the converse $\neg(q_1 \lor q_2) = \neg q_1 \land \neg q_2$ and resolve
$$ (\neg p \lor q_1 \lor q_2) \land (\neg q_1 \land \neg q_2) = \neg p$$
which then yields a contradiction $p \land \neg p$.

Why should such arbitraty disjuctions not be permitted? Is it somehow related to the satisfiability problem (HORNSAT) ?  Or is it due to the closed world assumption (where the statement $q_1 \lor q_2 = \top$ is paradoxical) ?

p.s. I am a hobbyist in logic programming, so simple informal explanations are appreciated :)

$\lambda$Prolog is a logic programming language based on a much richer logic than Prolog. In particular, the formulas that constitute its language are (higher-order) hereditary Harrop formulas. Horn clauses are a pallid fragment of that. The enabling concept for $\lambda$Prolog is the notion of a uniform proof, and additionally switching to an intuitionistic perspective on the logic. That last paper introduces the notion of an abstract logic programming language based on the notion of uniform proof and shows that classical first-order and higher-order Horn clauses form an abstract logic programming language.

Basically, a uniform proof is one where the rules used can be given an operational interpretation based on goal-directed search. This isn't the actual definition of a uniform proof, but the motivation behind the actual definition. An abstract logic programming language is one where uniform proofs suffice to prove any formula in the language with respect to a given notion notion of provability that is contained by the usual classical one.

Even the class of higher-order hereditary Harrop formulas doesn't allow $P \to Q_1\lor Q_2$ as a program clause. (It is allowable as a goal.) Why not? Obviously, $P, P\to Q_1\lor Q_2 \vdash Q_1\lor Q_2$, that is, if we know $P$ holds, and we know $P \to Q_1 \lor Q_2$ holds, then we can prove $Q_1 \lor Q_2$. However, this proof succeeds without ever specifying which of $Q_1$ or $Q_2$ holds. Indeed, neither $P, P\to Q_1\lor Q_2 \vdash Q_1$ nor $P, P\to Q_1\lor Q_2 \vdash Q_2$ is true. Formally, the proof of $Q_1\lor Q_2$ from $P$ and $P\to Q_1\lor Q_2$ is not a uniform proof. Informally, the operational interpretation we'd like to give to proving $Q_1 \lor Q_2$, is that we search for a proof of $Q_1$ and a proof of $Q_2$, and if either search succeeds we've established $Q_1 \lor Q_2$. Obviously this search approach will fail in the above example since neither $Q_1$ nor $Q_2$ can be individually established.

Finally, why do we need to "retreat" to intuitionistic logic in the hereditary Harrop formula case (we don't for Horn clauses)? This is because $P\lor(P\to Q)$ is a goal in the class of hereditary Harrop formulas, and it's classically true. However, if we again apply our operational interpretation, the search would proceed as follows: First try to prove $P$, this fails. Next, try to prove $P\to Q$ which reduces to proving $Q$ given $P$ which fails. $P\lor(P\to Q)$ isn't true intuitionistically since when $Q$ is false, this is just the law of the excluded middle. Of course, it requires a more involved proof (which is in the paper) to show that there isn't a similar failure with respect to intuitionistic logic for the class of higher-order hereditary Harrop formulas.

Since 1991, the notion of an abstract logic programming language has been extended. The most notable extension is the generalization of uniform proofs to focusing proofs, and the idea has been applied primarily in the context of linear logics.  In many ways disjunction and negation are more tractable in linear logic. However, the idea has also been applied to Disjunctive Logic Programming. The idea was (first?) applied in Uniform Proofs and Disjunctive Logic Programming, but it didn't provide any guidance on how to handle quantifier elimination.  That is, the idealized interpreter of an abstract logic programming language assumes you can "magically" guess the term to use in existential quantifier elimination. Normally this is accomplished with unification, but unification interacts with proof search. For example, higher order unification generates extra backtracking and the universal quantifiers in hereditary Harrop formulas lead to eigenvariables. Unification interacts with disjunction as well. The later paper A New Abstract Logic Programming Language and its Quantifier Elimination Method for Disjunctive Logic Programming gives a story not just for the abstract logic programming part of Disjunctive Logic Programming, but also how unification needs to be modified in this context.

To my knowledge, DLV seems to be the only serious implementation of any form of disjunctive logic programming.


Are run time bounds in P decidable when the problem is promised that an input program must halt? I'm solving Problem 11-10(b) in "what can be computed".

11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as
follows.
The input is a program P, and the solution is “yes” if and
only if there exists some polynomial q(n) such that, for every n, P
halts after at most q(n) steps on all inputs of length ≤ n.
(a) State, with proof, which of the following statements are true: (i) HISP is
undecidable, (ii) HISP ∈ Expo, (iii) HISP ∈ Poly.
(b) Would your answer to a change if we restrict the domain of HISP, so that the
input P is guaranteed to halt on all inputs? (Note: This is an example
of a promise problem, in which the input is promised to have a certain
property, which may itself be undecidable.)

The proof of 11-10(a) is basically same as "Are runtime bounds in P decidable?", which is that HISP reduces to halting problem.
If an input program is promised to halt, however, this reduction does not help us.
Is there any suggestion to solve this problem?

Given a Turing machine $T$, construct a new Turing machine $T'$ which, in input of length $n$, simulates $T$ for up to $n$ steps. If $T$ halts then $T'$ also halts, and otherwise $T$ counts up to $2^n$ and then halts.


Are genetic algorithms special instances of random search done in an unexpectedly short run-time? I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?

Ever since I finished my implementation of a GA , since randomness is present in the mutation function,the initialization part (as well as the reinitialization part) and crossbreeding part as well... other than a encoder which tries to sense of the chromsomes (encoder tailored to make sense of the chromosome in context of the problem) and a fitness function , it feels like genetic algorithms are just random search functions in disguise .

So my question is : are GA implementations just plain old random searches with a shot of memory to make it look like there is some sort of meaningful feedback?

I guess the easiest  way to reason it (this is after thinking about what user:vzn said

  a genetic algorithm exploits the gradient in the fitness function due
  to crossbreeding. if there is no gradient to exploit, it is indeed
  roughly the same as a random search over the search space.

, um that the chromsomes which embedd some sort of a possible solution has a higher chance of being a solution than a randomly generated chromosome.On mutation and crossbreeding it up its chance of being closer to the answer.I do not know random variable theory or stochastic calculus(if it is ver used in such a thing) to prove it but it's feels pretty intuitive now.

ANd if you think carefully about what the fitness function does probabilistically, because it takes the best fits, the best fits have a higher chance of being crossbred and mutated into a better solution than an unfit solution.

As for a random search based searching , it really doesn't this narrowing down part to give an answer in most cases as compared to a GA.


What is the minimal pumping length of this string $(01)^*$ In this answer, it is told that the minimal $p$ value is $1$. One of the conditions of the pumping lemma is that

$|xy| \leq p$

Now if we try to split a string $01^p$, we might do it like this:

$x=\epsilon$, $y=01$, $z=01^{p-1}$

But this decomposition contradicts the above condition. If we arrive at a contradiction, then how $p$ can be equal $1$?

Besides, is there a maximum pumping length? Various sources define $p$ as constant, and if it is a constant, there should be a single value instead of minimum and maximum range.

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$. The pumping length of $(01)^*$ using this definition is $2$. Anybody claiming that the pumping length is $1$ is either wrong or has a different definition in mind (the notion of pumping length isn't completely standard, and my definition is not the only possible one).

In order to show that the pumping length cannot be $1$, you need to show that there exists some word $w \in L$ of length at least $1$ such that for every splitting $w = xyz$ in which $|xy| \leq 1$ and $y \neq \epsilon$ there exists $i$ such that $xy^iz \notin L$. In particular, you don't get to pick the decomposition. You need to show that no decomposition works. In this case, we can take the word $w = 01 \in L$. Since all words in $L$ have even length, if $w = xyz$ and $xz \in L$ then necessarily $y$ has even length. However, this is impossible since on the one hand $|y| \leq |xy| \leq 1$, and on the other hand $y \neq \epsilon$.


Prove Undecidability: TM M enters each of its states on Input W? Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$?

How to prove that the problem is undecidable?

I was trying to prove undecidability by Rice's theorem which states that languages having non-trivial property are undecidable. But how can I adjust the problem to the theorem?

Hint. We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that, if they do halt, they cycle through all their states just before doing so. This gives you a class of TMs that visit every state if and only if they halt.


Graph coloring variation Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?
Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,
$$| \{ w \in N_G(v) \mid \text{color}(v) = \text{color}(w) \} | \leq p?$$

The definition you are looking for is "defective coloring":

A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi _{d}(G)$.


Is there a usable implementation of PBFT? In the original Practical Byzantine Fault Tolerance (PBFT) paper they mention they implemented a fault tolerant NFS service. To do that they made a library for PBFT. Does that exist anywhere?

As that paper is quite old now and was well received, I thought it should not be hard to find implementations. However so far I only found incomplete and abandoned experiments.

RAFT has a list of implementations on their website. I am looking for something like this in the byzantine case.

Not necessarily NFS, but Hyperledger used PBFT for their blockchain platform.

This is a Go implementation: https://github.com/hyperledger-archives/fabric/tree/master/consensus/pbft

That is an old repo, they seem to be currently using a new repo with implementations in other languages as well, however I haven't gone through it in detail:
https://gerrit.hyperledger.org/r/#/admin/projects/

There are more related details in this question: https://stackoverflow.com/questions/41710738/pbft-algorithm-in-hyperledger

Good luck


Emulation, interpreters and parallel execution I'm interested in how software emulators of old game consoles work.  These must consist of an interpreter for the machine language of the emulated processor.

If I have understood correctly an interpreter, for each instruction: reads the instruction and scrolls a huge switch-case (or sequence of if-elseif-...) like structure comparing the instruction with each possible instruction in the architecture of the emulated processor, and then executes the related branch.

Is it possible to distribute the switch-case into severial thread, and give them to a parallel processor (GPGPU, FPGA, ...) ?
In my opinion, this problem is inherently parallel, because if 1 core = 1 opcode, and each core can read the next opcode, then just the right core will execute the instruction. After finishing the execution of the current instruction, then it does the same thing for the next one.

Is it a good idea to create an interpreter (slowest type of emulation, but also the easiest type of emulator and free of problems like self-modifying code) and make it faster using distribute computing?
Each instruction means a different process for a different core
No problem with concurrency, because just one instruction branch is executed.Is this a good idea or there is any problem?

Your understanding of the complexity of a switch or case statement is not correct.  In most languages these statements make a decision based on the value of a single integer variable.  If those integers are densely packed together (as they typically are when an interpreter is decoding an instruction opcode) then the compiler turns this into an $O(1)$ lookup table.

The table is simply an array of addresses.  The control variable for the switch statement is used to determine the offset into the array.  Then the code simply jumps to the address given at that offset in the array.

In the case where the integers are not densely packed together then the compiler builds a logarithmic-height tree of branches each of which divides the remaining range in half, like in the children's "number guessing game."  So, for example, if you have a switch statement over 1000 different cases spread over the numbers 0-1000000000, then you'll be able to determine whether any given input is one of the cases, and which case, in less than 10 comparisons.  (Because $\log_2 1000 < 10$.)


How important is balance of a tree? I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced.

But I am imagining that in situations in which several paths of a tree have to be explored such as in an R-tree, balance might not always be necessarily desired?

Tree balance is usually preferable as the depth of the tree is shortest and the tree itself is most compact. However, there are few situations in which the fact that is unbalanced is what gives it efficiency. Huffman Coding is an example of this, where shorter paths in a binary tree represent frequently used items.


Can a process run if there's not enough space for minimum pages? I'm studying OS and I came up with this scenario where the OS works with a paging scheme and virtual memory, and a process wants to start running, but in memory, there's not enough space to allocate the minimum pages the process needs.

So I was wondering, will the OS try to allocate the process pages and end up thrashing? Or will automatically discard the process and trap indicating there's not enough space?

I know there are techniques to avoid thrashing but I don't really know how they are implemented and what the system considers appropriate to run in the system.

There's no set answer; it will come down to what the OS is implemented to do in that situation.  I suppose if you implement the OS poorly, arbitrarily bad things could happen.

But in practice, with modern OS's, there's no such thing as "minimum pages the process needs".  The way virtual memory works is that the process has no idea what pages are actually mapped into physical memory at any times and which ones aren't; the OS transparently pages in pages as needed.  So, that notion doesn't exist.

Thrashing is not a black-and-white phenomenom.  For instance, thrashing can happen if 98% of the CPU time is spend paging pages in and out of memory, and only 2% on running the process itself.  In that case, forward progress is still being made -- just very slowly.


Closure property of recursively enumerable language I read that recursively enumerable languages are closed under intersection but not under set difference.

We know that, $A \cap B = A - ( A - B)$.

Now for LHS (left-hand side) to be closed under intersection, RHS(right-hand side) should be closed under set difference .

But we know that RHS is not closed under set difference so LHS is also not closed under intersection.

Suppose we assume that R.E is closed under intersection then,

$A \cap B = \overline{(\overline{A} \cup \overline{B})}$.

Now LHS can be closed only if RHS is closed under complement (as R.E languages are already closed under union). But we know R.E is not closed under complement, so again a contradiction.

So, R.E should not be closed under intersection right ?

Basically, "R.e. sets are closed under intersection means that for any two r.e. sets $A \cap B$ is again r.e, but when we say that r.e. are not closed under some set-theoretic operation it means there are at least one pair of r.e sets which results in not-r.e. set under that operation no matter it is set-theoretic difference or complement. In other words,

R.e. sets are closed under a set theoretic operation $\star$ means that for any pair $A$ and $B$, $A\star B$ is r.e.
R.e. sets are NOT closed under a set theoretic operation $\star$ means that NOT for all pair $A$ and $B$, $A\star B$ is r.e. In simple words, there may be sets $A$ and $B$ such that $A\star B$ is r.e., and there exist other sets $C$ and $D$ such that $C \star D$ is not r.e.

For example, the set $N - 2N$ (the set of all odd positive integers is r.e (even recursive), but the set $N - A_{TM}$ is clearly not r.e. ($A_{TM}$ denotes the set of Halting problem).


Characterisation of graphs that are not 3-colorable We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not 3-colorable depending on a single graph property e.g. vertices/edges parity or anything else that can be generalised.

As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs.

However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem states every triangle-free planar graph is 3-colorable. Furthermore, such graphs can be 3-colored in linear time. In a random graph setting, almost all graphs with $2.522n$ edges are not 3-colorable [1].

You can find plenty of graph classes for which 3-coloring is easy on ISGCI.

[1] Achlioptas, D., & Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3-colorable. Electronic Journal of Combinatorics, 6(1), R29.


Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free? I was wondering if this language is context-free:

$L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$

I know that this language is not regular because it fails the pumping lemma for regular languages but that does not necessarily mean it is not context-free. I'm not sure whether to use the pumping lemma for context-free languages to show that this is not context free or to provide context-free grammar to show that it is context free.

I've tried creating a context-free grammar to generate this language but ran into trouble which makes me believe that this language is not context-free, but I am still unsure.

If someone could point me in the right direction that would be greatly appreciated.

Suppose $L$ was context-free. Then $L \cap 0^*$ were also context-free. Since $L \cap 0^*$ is a unary language (a language over a unary alphabet, i.e., an alphabet of size $1$), Parikh's theorem states that it is context-free iff it is regular. As you mention, $L \cap 0^*$ isn't regular, and so $L$ can't be context-free.


How does f(n) < cg(n) specify time? I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:

$O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq c*g(n)$ for all $n > n_0$.

The way I understand it, $c*g(n)$ denotes $c$ multiplied by $g(n)$. If this is the case, then how does the above expression specify time, and not just that $c*g(n)$ is greater than $f(n)$? Or am I incorrect, and this is some notation I don't understand? My understanding of time complexity is very rudimentary, so forgive me if this is just a stupid mistake on my part.

How does f(n) < cg(n) specify time?

It doesn't. Bachmann-Landau notation is simply a handy way to compare the growth-rate of functions. It doesn't say anything about what those functions mean, and we can be pretty sure that Bachmann wasn't thinking about computers when he came up with it in 1894.
What meaning you assign to those functions is up to you. For example, when analyzing comparison-based sorting algorithms, we typically take $n$ to be the number of elements in the collection and $f(n)$ to be the number of comparisons, or the number of swaps, or the number of comparisons and swaps.
Note also that all of this is always relative to a machine model or a cost model.
As a very simple example, if I were to ask you what is the algorithmic worst-case step complexity for copying a list, you would say $O(n)$. But actually, the correct answer would be "I can't tell you that because you haven't specified the machine model". Because, for example, in a Turing machine, copying a list is $O(n^2)$, because for each element being copied, the head of the TM has to drive further and further and further to reach the end of the list to write the next element.