Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$ I was told that exponential time always beats polynomial time but doesn't this not work for:
$n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$?
If we take $log_2$ on both of them we get:
$\frac{1}{2}log \,n > \sqrt{log \,n}$
which seems that what I was told is incorrect.

Did I not hear the caveats?
Have I mislabelled exponential and polynomial functions?
If this view is wrong. What's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \,n}}$? How would you show it?

"exponential time always beats polynomial" we understand as for $a>1$ and any $k\in \mathbb{R}$ we have $n^k \in O(a^n), n\to \infty$.
But if you consider substitution of $n$ with some arbitrary function, then, of course, generally,   $n^{f(n)} \in O(a^{g(n)})$ will be wrong.  We can even reverse functions with appropriate substitution: $n^{f(n)}=n^{\log_na^n} = a^n $ and $a^{g(n)} = a^{\log_a n^k} = n^k$.
Your example $\sqrt{n}$ vs $2^{\sqrt{\log_2 n}}$ is not polynomial vs exponential, but polynomial vs some elementary function.
Addition.
Now let's compare $\sqrt{n}=2^{\log_2 \sqrt{n}}$ and $2^{\sqrt{\log_2 n}}$. As exponential with base $2$ is strictly increasing, then it is equivalence to compare $\log_2 \sqrt{n}$ and $\sqrt{\log_2 n}$. Considering function $f(x)=\log_2 \sqrt{x} - \sqrt{\log_2 x}$, for $x>1$, we have $$f'(x)=\frac{1}{2x\ln 2}-\frac{1}{2x\ln 2\sqrt{\log_2 x}} = \frac{\sqrt{\log_2 x}-1}{2x\ln 2\sqrt{\log_2 x}}$$
So $f$ is decreasing on $(1,2)$ and increasing on $(2,+\infty)$. As it easy to see, that $f(1)=f(16)=0$, then we can conclude that on $(1,16)$ function is negative and on $(16,+\infty)$ function $f$ is positive, so $$\sqrt{n}=2^{\log_2 \sqrt{n}} \gt 2^{\sqrt{\log_2 n}}$$ for $n \gt 16$. This gives $2^{\sqrt{\log_2 n}} \in O(\sqrt{n})$.
Additionally, if we consider $g(x)=\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}$, then
$$\lim\limits_{x \to +\infty}\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}= \lim\limits_{x \to +\infty}\sqrt{\log_2 x}=+\infty$$
which gives $2^{\sqrt{\log_2 n}} \in o(\sqrt{n})$.


From Whence the Randomization in Randomized Quicksort Cormen talks briefly about the advantages of picking a random pivot in quicksort.  However as pointed out here(4th to the last paragraph):

  Using a random number generator to choose the positions is relatively
  expensive

So how is picking a random pivot actually implemented in practice, and how random is it?  It can't be too expensive, since from what I understand one of quicksort's main advantages over other $\cal{O}(n \lg n)$ sorts is the small constant factors, and spending allot of cycles picking pivots would undermine that advantage.

EDIT

As an example, the C code from "Three Beautiful Quicksorts" actually calls the C library rand function:

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

While the pivot picking code here is clearly $\cal{O}(1)$, it would seem that the hidden $c$ here is relatively high.

Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the reason behind randomizing. Quicksort behaves very badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to make sense, it has to be random (if I know how you pick pivots deterministically, I can cook up an array that forces you to go into $O(n^2)$ behaviour, see the paper mentioned for details). But a fancy RNG is costlier than, say, taking 3 or another smallish odd number of elements, and pick the median of those as pivot, which is another way to counteract bad behaviour. So if you choose randomization, use a fast RNG seeded appropiately (probably a linear congruential scheme will be enough).

Algorithms can (and should) be compared by $O(\cdot)$, but if you are talking about different implementations of the same algorithm one must switch to more detailed analysis. In fact, Sedgewick and Flajolet in "An introduction to the analysis of algorithms" argue that one shouldn't use $T(n) = O(f(n))$ at all, but should strive to get $T(n) \sim f(n)$ type asymptotics.


A condition ensuring that a bipartite graph have a perfect matching There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From this, how can I prove there is matching which covers all of $A$?

Hint: Use Hall's criterion.

In more detail, suppose that Hall's criterion didn't hold. Choose a set $X$ of minimal size satisfying $|N(X)| < |X|$. Show that $X$ is not empty, and let $Y = X \setminus \{x\}$ for some arbitrary $x \in X$. Show that $Y$ has a perfect matching with $N(Y)$, and prove that $N(N(Y))=Y$ by counting the edges connecting $Y$ and $N(Y)$ in two ways. Show that $\emptyset \neq N(x) \subseteq N(Y)$, and reach a contradiction.


Detecting isthmuses on digital curves Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them.

I want to find the isthmuses, i.e. sections of the curve that are close to each other (within a fixed threshold), though the indexes ("curvilinear" abscissa) differ by a large amount. For a curve of length $L$, there are $O(L^2)$ inter-pixel differences, but the size of the answer does not exceed $O(L)$.

Can you advise an efficient procedure ?

Update:

I believe that the following approach might be effective: we can sort the points on their $x$ abscissa using histogram sort, in time $\Theta(L)$, while keeping the corresponding index with them. Then for any point $(x_0,y_0)$, the possible close neighbors are found in the range $x_0-D\le x\le x_0+D$.

Assuming that a vertical line hits the curve $I$ times on average (for ordinary curves, $I$ will be a little more than $2$), the total effort will be at worse $O(LDI)$. Given that the intersections are found on the curves and change little from column to column, I suspect that by some incremental process, the dependency on $D$ could be lowered. Maybe also an auxiliary sort on $y$ can help.

Divide the image up into evenly sized grid cells.  Have one hash bucket per grid cell, and hash each point on the curve into the grid cell it falls in.  Sort all of the elements in each grid cell / bucket by the order of their abscissa.  Then, you can iterate over all of the non-empty grid cells, and for each, iterate over their sorted list to look for an instance of a large gap.  Each isthmus will correspond to a pair of adjacent elements in the sorted list that have a large difference in their abscissa.

You should probably do this do this four times: once with the original grid; again with that grid moved by one-half to the right; again with it moved one-half down; and again with it moved one-half to the right and one-half down.  If you use grid cells of side length $2D$, then this ensures that if the distance of the isthmus is $\le D$, it will be detected during one of these four iterations.


How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression? I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression.

Now there is a theorem for the last structure above:

  The complexity of any sequence of m operations of Makeset, Union and Find, n of which are of Makeset, on a Quick Union by rank and path compression is in the worst case equal to $O(m\,\, G(n))$. Where $G(n)$ is the inverse of the  Ackerman function

And this one is the Kruskal algorithm in pseudocode. Let $G=(V,E)$ be an undirected, connected and weighted graph, where $V$ is the set of vertices and $E$ the set of edges, then the following algorithm returns a Set $A$ that contains the edges of the Minimum Spanning Tree.

Kruskal(Graph G) {
    Set A

    For every vertex v in V {
         Makeset(v)
    }

    Order the edges in E in ascending order by weight

    For every edge (u,v) {
        If find(u) != find(v) {
            union(u,v)
            A = A + (u,v)
        }
    }

    Return A
}

Let's go back to my problem.
I understand that the second loop is executed at the worst $m$ times (the number of edges). Hence the number of operations of union and find is $m$, while the number of makeset is $n$ (the number of vertices).

The book where I'm studying, after making similar observations says that the complexity of the above operations equals to $O((m+n)\,\,G(n))$ and I don't get why.
Of course, the other complexity to order the edges is $O(m\,\, log\, m)$ so the final one is:
$O(m\,\, log\, m) + O((m+n)\,\,G(n))$
But $m>n-1$ then
$=O(m\,\, log\, m) + O((m)\,\,G(n))$
However $m<n^2 \implies log\, m < 2log\, n \implies log(m)=O(log n)$, so
$=O(m\,\, log\, n) + O((m)\,\,G(n))$
$=O(m\,\, log\, n)$

Can you explain to me how to get the $O((m+n)\,\,G(n))$ complexity from the algorithm?

You are absolutely right.  There is nothing wrong with your reasoning.

The running time of Kruskal's algorithm, when implemented in the way you describe, is $O(m \log m)$, or equivalently, $O(m \log n)$.  If the book says its running time is $O((m+n) G(n))$, the book is wrong; that doesn't take into account the time to sort the edges by weight.

If you look at other sources I think you'll find that they correctly report the running time of Kruskal's algorithm.


Lower bound on the covering radius of a code Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$.

Could you give me a hint how we could show this?

The idea is to use a sphere packing argument, only for covering. Let $V_q(\rho)$ be the volume of a Hamming ball of radius $\rho$. The Hamming balls around all codewords cover the entire space, so $V_q(\rho) q^k \geq q^n$, or $V_q(\rho) \geq q^{n-k}$. To deduce the bound, use an approximation for $V_q(\rho)$.


Converting a regular expression to a context-free grammar Does this conversion look right? I am learning conversion from RE to CFG.
RE:
$$(a \cup b)^* \cup ab(a \cup b)^*$$
CFG:
Terminals:
$$ S_1 \to a \\ S_2 \to b $$
This is for the first $(a + b)^*$:
\begin{align}
&S_3 \to S_1 \mid S_2 && (a \cup b) \\
&S_4 \to S_3S_4 \mid \epsilon && (a \cup b)^*
\end{align}
This is for the $ab$ in the middle:
$$ S_5 \to a \\ S_6 \to b $$
This is for the second $(a \cup b)$ and $(ab)$ in the middle:
\begin{align}
&S_7 \to S_1 \mid S_2 && (a \cup b) \\
&S_8 \to S_7S_8 \mid \epsilon && (a \cup b)^* \\
&S_9 \to S_5 S_6 && (ab)
\end{align}
Concatenated $ab$ with the second $(a \cup b)^*$:
\begin{align}
&S_{10} \to S_8 S_9 && (ab(a \cup b)^*)
\end{align}
This the final CFG:
\begin{align}
&S_{11} \to S_4 \mid S_{10} && (a \cup b)^* \cup ab(a \cup b)^*
\end{align}

This CFG is indeed correct, but can be greatly simplified.

First, there is no need to create a new variable that would derive only a terminal value, that is - $s_1,s_2,s_5,s_6$ are not required.
For a similar reason, we don't need $s_9$.
Another simplification is that $(a\cup b)^*$ was already generated by $s_4$. There is no need to create $s_7$ and $s_8$ for this usage

Considering those things, the CFG will be reduced to:

$S\rightarrow A\space|\space abA$
$A \rightarrow AB\space|\space\epsilon$
$B \rightarrow a\space |\space b$

Notice also that $L(ab(a\cup b)^*)\subseteq L((a\cup b)^*)$, and thus:
$L((a\cup b)^*\cup ab(a\cup b)^*) = L((a\cup b)^*) \cup L(ab(a\cup b)^*) = L((a\cup b)^*)$
And thus an even smaller CFG will be:

$S \rightarrow A$
$A \rightarrow AB \space | \space \epsilon$
$B \rightarrow a\space | \space b$

Essentially we removed one unnecessary derivation rule. This can be simplified a bit further, go ahead and give it a try :)


Generalized operators for programming languages After asking this question on stackoverflow, it has changed slightly.  Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that vector space?

I'm interested in the parallels between mathematical operators (like the Hamiltonian, ladder operators, momentum operators, etc) and programming languages.  The operators that I'm talking about can be thought of as transformation matrices that act on (potentially) infinite vectors.  It seems like a good place to start might be a tree algebra?

An alternative would be to force the program into some sort of allowed bitwise representation, and then perform transforms on it.  Is such a thing possible?

You might be interested in the citations provided in the following post on CSTheory.StackExchange: https://cstheory.stackexchange.com/q/19091/5038  They get at something roughly similar to what you are asking for.

See also the algebraic theory of parsing, e.g., https://cstheory.stackexchange.com/q/9000/5038  It seems like it too might be in the space that you are interested in.


Linear programming maximizes the minimum distance problem I have a problem with creating an equation for linear programming solver.

Company wants to open stores in k cities. For the purpose of even coverage of the entire area, these cities should be selected from the available n candidates in such a way that it maximizes the minimum distance between any pair of selected cities.

I don't know how to define maximizes the minimum problem in graph in linear equation.
Can any one give me some hints?

Thank you very much.

Let's first define some variables.

$$x_i \in \{0, 1\}$$
$$w_i \in \mathbb{Z}^+$$

Where $x_i=1\iff $ location $i$ is selected and $w_i$ equals the minimum distance from node $i$ to any selected city if $x_i=1$ and $\infty$ otherwise. We will use $D$ to represent $\infty$ and in practice $D$ can just be the diameter of the graph. We can constrain these variables below.

$$
\begin{align}
\sum_{i=1}^nx_i &= k\\
w_i & \leq \texttt{distance}(i,j) + D(2 - x_i - x_j)& \forall j\neq i
\end{align}$$

It remains to find the minimum across all $w_i$. We will let this minimum be $y$. We constrain $y$ as follows
$$y \leq w_i \;\; \forall i$$

Now the objective function is clear, we want to find the largest $y$ that satisfies our constraints
$$\text{maximize }{y}$$

Our first constraint verifies that we select $k$ locations. The second gives us the minimum distance from a selected point to any other selected point. The third ensures that we find the minimum across these distances. Unfortunately, this is not a linear program but a mixed integer program.


Find a maximum sum in matrix, subject to special constraint I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in the $i$-th row from interval $[a, b]$, then I have to also take the interval $[\max(1, a - 1), \min(b + 1, M)]$ in the $i + 1$-th row.  In other words, if I use all of $A[i][a], \dots, A[i][b]$, then I also have to use the elements $A[i+1][\max (1, a-1)],\dots ,A[i+1][\min (b+1, M)]$.

I can't think of any algorithm for this.  I don't even have any idea how to brute-force it. Could someone please help me solve that? I think the optimal solution should have $O(N \cdot M)$ complexity or something like that.

Example input: $N=4$, $M=7$, and
$$A =
\left(\begin{matrix}
&-1 &4 &-6 &-1 &-2 &-5 &10 \\
&5 &-7 &2 &1 &-9 &-13 &2 \\
&2 &4 &-10 &3 &1 &2 &6 \\
&3 &2 &7 &1 &-7 &4 &5
\end{matrix}\right).
$$

For this problem instance, the maximal sum is $40$. This can be achieved by taking the 5 in the first column, the 3 in the fourth column, the 1 in the fifth column and the 2 in the last column as the summits of the triangles.

This can be solved in $O(NM)$ time using dynamic programming.

Given any solution, let $s$ denote the smallest index $s$ such that $a[s][1]$ is selected.  (It follows that $a[1][1],\dots,a[s-1][1]$ are not selected and that $a[s][1],\dots,a[N][1]$ are selected.)  This partitions solutions based on the value of $s$, i.e., based on which entries from the first column are selected in that solution.  There are only $N$ possible values for $s$.

Now define $f(s,t)$ to be the largest sum that is possible by selecting some entries from the submatrix $a[1..N][t..M]$, subject to the restriction that you choose all of $a[s..N][t]$ and don't choose any of $a[1..s-1][t]$.  You can easily find a recurrence relation that expresses $f(s,t)$ in terms of a few values of the form $f(s',t+1)$.  This immediately yields a simple dynamic programming algorithm with running time $O(NM)$.


Measuring the Probability of Error for a Potential BPP Algorithm Problem

Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space into four regions then selects three of those regions due to some condition. From there it selects at random one of the three spaces as the next space to check for the answer. If this algorithm produces a value it is 100% the correct solution, else it states it cannot find the solution which is always wrong because the item being searched is always there. Therein, the theory is to run it a bunch of times until it produces the solution.

Question

I created this algorithm which is to be utilized as an experiment to create a BPP algorithm for a data analysis problem. But, I am uncertain if it qualifies as a BPP algorithm. From my understanding it is not, because it has a one in three chance of selecting the correct partition at each time it partitions the space. This means the probability of selecting the correct solution is $(1/3)^{klogN}$ making the probability of selecting the incorrect solution one minus the probability of the correct solution.

So, my question is A) Is my interpretation correct for measuring the probability? B) Does this algorithm qualify as a BPP algorithm or some other class?

The class BPP (and related classes such as RP, coRP, and ZPP) deal with decision problems. This means the algorithms corresponding to these classes may only produce "yes" or "no" answers. This notion does not quite match your algorithm, which is actually solving a search problem (i.e., the solution set is a subset of some arbitrary set of outputs).

At any rate, what you are actually trying to refer to as a "BPP algorithm" is a randomized algorithm with two-sided error. Such an algorithm produces correct and incorrect answers for both instances that have and do not have a solution, and, usually, it is also required that the algorithm be correct "most of the time" (where this is defined by bounding the error by some probability constant).

However, your algorithm has not actually two-sided nor one-sided error. This is because your problem instances all have solutions (and your algorithm does not claim otherwise). Thus, your algorithm only really fails to find solutions with some probability, which makes it have zero-sided error, that is, it always outputs correct answers, but may also output a "could not find" or "don't know" answer (with some bounded probability). As a result, what you have is a Las Vegas algorithm, which is a type of probabilistic algorithm with applications well beyond complexity theory. Incidentally, the alternative definition for a Las Vegas algorithm (i.e., a probabilistic algorithm with expected polynomial time complexity) is quite consistent with your remark that you need to run your algorithm "a bunch of times until it produces the solution."

On a side note, the complexity class associated with decision problems solvable with zero-sided error probabilistic TMs is the class ZPP (though this is only tangential to your question since, as I have explained above, you are not working in the realm of decision problems anyway).


Find longest subsequence in array with given condition I am given an array $A$ having $n$ elements and an integer $k$.

I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition:

for all $i < j$: $|A[i] - A[j]| \leq k$.

Example: $n= 4$, $k = 5$, $A = [1, 2, 50, 6]$

Answer: the longest valid subsequence, $[1, 2, 6]$, has length $3$.
Note that the first element is always to be included in the sequence.

I think this can be solved with Dynamic Programming. But I can't form a recursive equation for Dynamic Programming.

In the following answer, I show how to solve in $O(n\log n)$ the following similar question:

  Given an array $A$ and a number $k$, find the longest contiguous subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Using this, it is easy to solve in $O(n \log n)$ the following question, closer to yours:

  Given an array $A$ and a number $k$, find the longest subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Indeed, sort $A$ and then find the longest contiguous subsequence satisfying the condition.

Finally, to solve your actual question, filter $A$ by removing all elements at distance more than $k$ from the first element. The longest subsequence is now guaranteed to contain the first element (since it can always be added), so we can run the preceding algorithm to solve your question in $O(n\log n)$.


An intuitive explanation for LR grammars? With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR grammars however such an explanation seems to be difficult. Of course you could go through the entire construction of the DFA and so on. But is there a general principle or a few of them, that can give an intuitive understanding of LR grammars as a whole?? What is the intuition behind the item sets??

A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively easy (hah!) to grasp. In particular, it explains why $LR$ grammars are a much richer set than the $LL$ ones.

In practice, it is probably much more relevant to be able to understand the format in which your preferred LR parser generator spits out item sets when tickled the right way, and in particular how to track down the origin of conflicts and alternative ways to solve them (and their consecuences). I like the bison manual a lot in this regard.


Variant of interval scheduling (multiple machines with given availability) I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks cannot be performed at the same time by the same machine. I am trying to maximize the number of scheduled tasks.

More formally, we are given $m$ intervals $[B_i, E_i]$ (the machines) and $t$ tasks $[b_i, e_i]$. We must output $m$ lists $[i_1, i_2, ..., i_{k_j}]$ such that for each $1 \leq j \leq m$, $B_j \leq b_{i_1} \leq e_{i_1} \leq b_{i_2} \leq ... \leq e_{i_{k_j}} \leq E_j$, all the elements of the lists are distinct and $\sum_{j = 1}^m k_j$ is maximal (ideally t).

I thought about the greedy algorithm consisting on scheduling first the task that finishes the earliest, on the compatible machine whose last task finishes the latest (we consider every machine has at first a task finishing at the beginning of its working interval). However, this idea doesn't work, how we can see considering the instance of the problem where we have two machines, working on the intervals (0, 3) and (1, 4), with the tasks (1, 3) and (2, 4).
This way of selecting the machine on which we schedule the task is however not so stupid, and prevents other problems (the algorithm works if we are allowed to exchange the end of the working interval of the machines).

Is there a fast algorithm to solve this or is it a hard problem ?

Let us call $n$ the number of intervals and $m$ the number of available machines.

There is an algorithm by Brucker and Nordmann running in time essentially $O(n^{m-1})$. Thus for any constant $m$, the problem admits a polynomial time algorithm. The authors claim that the algorithm is practical up to $m=5$ machines.

When $m$ is not constant, the problem appears to be hard, however I do not know whether the version you stated is NP-hard. In this case, Faigle, Kern and Nawijn show that by a simple greedy algorithm you can schedule at least half of the intervals scheduled in an optimal solution. This is the overview of their algorithm, that they call $G$ (the jobs are denoted by $I_1,I_2,\ldots,I_n$,  and are considered ordered by their left endpoints):

  $G$ places $I_t$ on a free feasible machine if such a machine is
  available. Otherwise $G$ tries to replace a job $I_v$ by $I_t$ on a
  feasible machine with the goal to reduce the maximal remaining
  processing time. If neither action is possible, $G$ discards $I_t$.


Why is the CPU Involved During Keyboard Echo? I'm currently studying for a computer science exam, and I've come across a concept that has me somewhat stumped.

  When one types a key on the keyboard, an ASCII character is transmitted to the CPU. Upon reception of this character, the CPU outputs the same character to the screen. This process is called echoing. Instead of having the CPU involved, why don’t we simply have this echoing process done within the keyboard/screen unit so that the CPU is free to do other useful work?

Now, intuitively, I feel like this is because there is no defined keyboard/screen unit, and the CPU is the device which is responsible for communicating between the screen and the keyboard, through the interconnection network. However, I feel like the fact that a keyboard/screen unit is mentioned may mean I'm missing an important concept. Is this the case? Why do we involve the CPU in the echo process?

Letting the computer see each character as it is typed allows programmers to make the user interface more dynamic.

Back when a serious computer was the size of several upright refrigerators and computers operated on user input a line at a time, terminal input was handled as you described.  You typed a line of text on a terminal which displayed it locally (often on paper).  Only when you pressed the ENTER or RETURN key was the text sent to the mainframe or minicomputer to be processed.

But even back then, the advantage of letting the computer see the user input early was realized by the engineers of the time.  Command completion, where you type the first few letters of a command and the computer fills in the rest, was invented in the mid 1960's.  This feature was copied and improved through the years to where it stands today, available in all modern UNIX shells and under Windows as well.

Allowing the CPU to see each character as it is typed also allows shells to offer command line editing and history features well beyond what a dumb terminal could provide.  A key can allow you to step back through a list of commands you've previously typed, choose one, and then edit it slightly before pressing RETURN to have it executed.  Text can be cut and pasted between command lines, possible because the CPU has access to previous commands while the terminal does not.  Filenames as well as commands can be completed based on partial input, again possible because the CPU has access to the names of files in the filesystem and the terminal does not.


What exactly is the difference between a Balanced Binary Search Tree and an AVL tree? I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <= 1.
But then what about the Balanced Binary Search Tree? What's the difference here?
Let's take an example:
I have a sorted array X = {1,2,3,4,5} and if I insert each of the values in X into a Balanced Binary Search Tree, I get the PreOrder output as 3 1 2 4 5. However, if I insert each of the values of X in an AVL tree, I get the PreOrder output as 2 1 4 3 5.
I notice that an AVL is always self-balancing, but it seems that a balanced BST is not necessarily an AVL.
I am quite confused about this. Is there something I am missing here?

There are some implementations of Balanced Binary Search Trees, also known as Self-balancing Binary Search Trees. One of the aspects that can be considered when balancing a tree is it's subtrees height difference. This height aspect aims to keep the tree as flat as possible. The more flat the tree is, the less levels it will have and the search will be faster.
The implementation that you mentioned reconstructs the entire tree when a new node is inserted, from the root to the leaves. The AVL tree will reorganize (balance) only the subtrees needed to meet its invariant, i.e., the height difference less or equal to one, when a new node is inserted or a existing node is removed.
The pre-order traversal will be different, since these two BBSTs have different implementations! If you test, maybe a red-black tree (another BBST), the preorder will be different too!
The main thing to keep in mind is that the reason of the BBSTs to exist is that they will keep them more flat as possible to speed up the search for nodes. The only traversal that will be equal among them (if they are search trees) is the in-order traversal, that can be also used to sort data.


Non Recursively Enumerable Languages Can someone give me an example of Non Recursively Enumerable language... i.e.  A language which no Turing machine can accept ?  What makes a language non recursively enumerable ?

Every undecidable yet semi-decidable language provides an example: its complement.

That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.

You should know at least one such language from class.

   The Halting language, and probably numerous others from exercise problems.


How does an admissible heuristic ensure an optimal solution? When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves).

How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.

If you  want you can explain using the Manhattan distance heuristic of the 8-puzzle.

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal.

Look at this simple example.

Let $A$ and $G$ be respectively the starting and goal nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X_{i})$ be the step cost function from node $N$ to its neighbour $X_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).

Let the heuristics be

$h(B) = 3$
$h(C) = 4$

This heuristics function $H$ is not admissible, because $$h(C) = 4 > c(C, G) = 2$$

If the $A^*$ algorithm starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there.
And the path will be  $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$  with cost $3$. If the heuristic function was admissible this would not have happened.


Minimum number of edges for $n$ vertex graph to be connected I was reading about connectedness of a graph where I came across following points:

  The $n$ vertex graph with the maximal number of edges that is still disconnected is $K_{n-1}$ (complete graph with $n-1$ vertices) with an additional vertex, which has $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ edges.
  Adding any additional edge must connect the graph. So the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$.

I am ok with the first point but not with the second point. The minimum number of edges for $n$ vertex graph to be connected should be $n-1$. Then how does that second point makes sense? How does the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$? Was the text trying to say something else? Is $\frac{(n-1)(n-2)}{2}+1$ number characterizes/pertains to some other condition on the graph?

Likely they mean that if a graph has as at least $f(n) = {n-1 \choose 2}+1$ edges, then it is connected. For instance, $f(5) = 7$, and any 5-vertex graph is connected with 7 edges. However, as you observe, it would also be connected with a smaller number of edges (that is, with $n-1 = 5-1 = 4$ edges).


If M is recognizing L in polynomial time, is it also deciding it in polynomial time? Assume that a given turing machine $M$ accepts words in the language
  in $n^k$ or less steps, but words that aren't in the language
  are rejected in unknown number of steps (the machine might even loop).

  $k$ is unknown.

  Is $L(M)\in P$?

Well, obviously $L(M)$ is recognized in polynomial time. The question is whether it's possible to decide $L(M)$ in polynomial time.

It seems to me that the answer is no, but I can't figure a way to prove it.

It is indeed possible. Simulate $M$ for $n^k$ steps. If it has accepted so far, accept. Otherwise, reject. You can simulate $M$ for $n^k$ steps in polynomial time (perhaps $O(n^{2k})$), hence this is a polynomial time algorithm.


Which is better ? Iterations or Recursions? I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa.

But which type of repetition is preferable for minimum amount of computational effort and resource consumption ? Iteration or Recursion ?

A straightforward answer would be "iteration", since recursion consumes stack memory and imposes computational overhead for calling functions.

However, in practice both implementations can be equivalent at machine code level due to compiler optimizations (such as tail call optimization). In general, you shouldn't really be concerned about these matters unless you have strong reasons to believe they are relevant in your particular case.

As a rule of thumb, you should concentrate on clarity and efficiency of your algorithm, and use constructions that look natural for the logic of your method. This recommendation is repeated virtually in all books on the subject, so please follow it.

P.S. You should also consider that certain algorithms require you to store certain local values on each iteration. Recursion gives you this capability "for free", so you should also consider that iterative procedures may need additional data structures comparing to their recursive equivalents.


Is CFL closed against exchanging complementation and reversal? Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?

Hint: Show that they are the same language.


What are the treatises on how to build mechanical computers? I've just watched this replica of the Antikythera mechanism. I've heard also about Babagge's analytical machine and the Curta calculator. I got curious: What did they use to build computers made of gears? We have nowadays some treatises to make logic gates with transistors, how did they manage to build logic gates or to do whatever was needed for building their computers?

I'm not sure if this question really fits this forum, but it was the nearest one I could think about.

This is a very broad question, with a different answer for each kind of device.
The computers before modern times did NOT use logic gates.

For example the January 2004 Scientific American article "The Curious History of the First Pocket Calculator" covers how Curta calculators work, in addition to the history.

The Antikythera mechanism used gear reductions (gears with differing teeth counts) to implement the ratios of times of various periodic events to predict positions. Given the [known even then] frequencies, it is straightforward to compute the required gear ratios. http://www.cs.virginia.edu/~robins/Decoding_an_Ancient_Computer.pdf

In addition (as mentioned in a comment above) there were many many different flavors of analog computers, that a quick google search should be able to find explanations for many of them.


Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...

  Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$

So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f \geq 0.5$.

I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $\frac{1}{4}$... and I can expand that solution to any $p$ where $p = \frac{1}{2^x}$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...

I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?

Suppose $p=\sum\limits_{n=1}^\infty \frac{1}{2^n}p_n$, where $p_n\in\{0,1\}$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i \neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^{-(k-1)}\frac{p_k}{2}$, thus the probability of generating heads is $\sum\limits_{k=1}^{\infty}2^{-k}p_k =p$. The expected number of iterations is $2$.

Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.


Given n standard C++ STL maps, can I merge them? I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick.

For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}}

Then the resultant map will be : {{1,2},{2,4},{3,6},{4,8}}

If not achieveable by DSU, is there any other algorithm to achieve this in O(logn) complexity?

Here n is the number of maps and the sum of the sizes of all maps is 10^5.
n can range from 1-10^5.

STL maps are stored in a data structure which is effectively sorted by key, typically some kind of binary search tree. BSTs have the property that finding the smallest key and finding the next larger key are both amortised O(1) (assuming you can find a node's children in constant time).

So doing your merge is similar to merging n sorted arrays, which has complexity $N log n$, where $N$ is the total number of elements in all the arrays. (Sorting the concatenation of all the arrays is $O(N log N)$, which is both practically and theoretically slower.

A simple $O(N log n)$ algorithm is to repeatedly do the following until only one array is left:

Divide the arrays into two $n/2$ pairs. If there is an odd number of arrays, one array is treated as though it were paired with an empty array.
Merge each pair into a single array using the standard merge algorithm, which involves iterating through both arrays in parallel.

The total number of elements scanned in each iteration is at most $N$. (It will be slightly less because the merge procedure combines two elements with the same key, so that the next iteration will involve fewer elements. But $O(N)$ is an acceptable estimate.)

Since the number of trees is halved each time, it will take $\lceil log_2 n\rceil$ iterations to reduce the number of groups to one. So the he total time is the product of the number of iterationss and the total number of elements scanned, which is $O(N log n)$.


how to solve simultaneous equation with O(n) Does someone know how to solve the below?

Assume that the array $A$ is already sorted.
And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that

$A[i] + 4A[j] = A[i] + 5A[k] = 0$.

I came up with an algorithm that uses two double for-loop for each i, j and i,k. But the complexity will be $O(n^2)$..

As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$.

We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ again that are bigger than our current $j, k$ since $A$ is sorted, thus our $j, k$ can only ever decrease giving $O(n)$ instead of $O(n^2)$.

In Python:

i = 0
j = k = len(A) - 1

while i < len(A):
   while j >= 0 and -A[i] < 4*A[j]:
       j -= 1

   while k >= 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None


Closest-point heuristic approximation problem I have an Approximation Algorithm problem and its answer but I am having a hard time to clearly understand.
The problem is as follows:

  Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex $u$ that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest $u$ is vertex $v$. Extend the cycle to include $u$ by inserting $u$ just after $v$. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

The answer is (I apoligize for including an image but I couldn´t get the  some special characters displayed correctly)

What I do not understand is the part surrounded by the red rectangle. I will very much appreciate if you help me to get the idea behind it. I am studying for an exam and I am stuck with this problem.

Respectfully,
Jorge Maldonado

I think there's some problem with the LaTeX formula. It should look like this:
$c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$
Let's say initially it was $u\to x$. Then you add $v$ directly after $u$, forming $u\to v\to x$. This increases the total distance by $c(u,v)+c(v,x)-c(u,x)$. From the triangle inequality, we have $c(u,v) + c(u,x) \geq c(v,x)$ and thus $2c(u,v)\geq c(u,v)+c(v,x)-c(u,x)$, hence $c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$.
The next paragraph should make more sense now.


Counting the number of permutations of string with given repeated interwoven subsequence Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence.

Example. $S=abc$. There are 5 permutations: $abcabc$, $abacbc$, $ababcc$, $aabcbc$, $aabbcc$.

If each character of $S$ appears only once, the problem becomes easier. Consider all binary strings of length $2n$ with $n$ zeros and $n$ ones. Zeros represent the first subsequence and ones represent the second subsequence. Whenever there is a binary string with some prefix that contains more ones than zeros, we may repaint the binary string in a way that both the original binary string and the repainted binary string represent the same permutation, and that no prefix of the repainted binary string has more ones than zeros.

Therefore we may restrict ourselves to the binary strings where for each prefix the number of zeros equals or is greater than the number of ones. Because each character of $S$ appears only once, each such binary string represent a distinct permutation. There is a simple recursive method to generate such binary strings, and by applying dynamic programming it is possible to calculate $P_n$ in $O(n^2)$ time. Apparently for this special case $P_n$ eqals the n'th Catalan number $C_n$, so it should be possible to get it done with $O(n)$ multiplications.

When some characters of $S$ appear more than once, or there are common substrings, $P_n<C_n$. For $S=aaa$ the number is 1, for $S=aab$ it is 3, and for $S=aba$ it is 4. So now my questions are:

How to find $P_n$ in a way that is faster than generating all $C_n$ permutations and counting the unique ones?
The general case. Given $S$,$n$,$k$, count the number of distinct permutations of a string of length $kn$ such that each of them contains $S$ $k$ times as an interwoven subsequence. How to do this faster than generating all the plausible permutations and counting the unique ones?

It's possible to count the number of such strings in something like $O(2^{n})$ time.  This is faster than generating all permutations (as $n! \sim 2^{n \log n + O(n)}$), but it's still not polynomial time.  I don't know if the number of such strings can be counted in polynomial time.
Here's how to do it.  You can build a NFA that accepts all such strings of length $2n$, and only such strings.  The NFA will have $O(n^2)$ states and be acyclic: it has $2n$ levels, and each level has $\le n$ states in it, and each transition goes from one level to the next level.  Each state in the NFA is of the form $(i,j)$, representing that we've already consumed the first $i$ characters of the first copy of $S$ and the first $j$ characters of the second copy of $S$.
So now the task reduces to counting the number of strings accepted by this (acyclic) NFA.  Unfortunately, counting the number of strings accepted by an (acyclic) NFA is #P-complete in the general case, so there's no polynomial-time algorithm that works for all (acyclic) NFAs.  (This doesn't rule out the possibility of a specialized algorithm that somehow takes advantage of the special structure of this particular NFA, but personally, I don't see any way to construct such an algorithm.)
That said, there are two techniques that are available here:

We can count the number of strings accepted by this NFA in exponential time.  First, convert the NFA to a DFA via the product construction.  You obtain an acyclic DFA with at most $2n \times 2^n$ states.  Since this DFA is acyclic, you can then count the number of words accepted by it in time linear in the number of states using dynamic programming.  Therefore, the total running time will be something like $O(n \cdot 2^n)$.
See also https://cstheory.stackexchange.com/q/8200/5038.

Alternatively, you can compute an approximation to the number of such strings, much more efficiently -- but the approximation will be rather inexact.  See Counting the number of words accepted by an acyclic NFA for details of how to do that.

I don't know if there are better techniques for your problem, or if there's any method to solve your problem in polynomial time.


Unknown representation of number as bits I am self taught in CS and came across this while looking at binary search applied to multiplication. I don't understand this part:
OK, we have some x that has binary representation $10110010(1*2 + 1*2^4 + 1*2^5 + 1^7$) ...I understand this, but don't know what following means $x = 2^4(1011) + 0010$. What is name of second notation, where can I find more about this?

Thanks!

They've split an 8-bit byte into two four-bit nibbles (sometimes spelled "nybble").  The brackets denote multiplication; it's just saying that
$$10110010 = 10000\times 1011 + 0010\,,$$
(written all in binary to avoid having two different bases in the same expression).  This is just like saying, in decimal, that
$$837\,487 = 1000\times837+487\,.$$
There isn't really anything to find out.


What is the difference between a TM accepting and deciding a language? Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language $L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$.  I know that any binary string ending with $00$ is divisible by 4, so $\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ is the language that this TM accepts.

But on the topic of (un)decidability:  I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language — and that same TM rejects all strings and only strings not in that language.

Which leads to the question:  What is the difference between a Turing machine accepting and deciding a language?

There is major difference. A turing machine "accepts" a language, if it enters an accepting state for any input from the langue, while it "decides" the language if it "accepts" it and enters a rejecting state for any input not in the language.

These are different, because there is a third thing that a Turing machine can do: never stop. Such Turing machine accepts the language, but does not decide it.

See also this other question and definition of decidable language on WP.


Does Assembly Language depend on an Assembler or the family of processor? From what I understand, the x86 family of processors understands the same instruction set and x86-32, x86-16 machine code can be executed by an x-86-64 processor because of backwards compatibility.

Now since Machine Code is usually produced from Assembly Language and we use an assembler for that purpose, does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

Let's say I have an Assembly Code like this which is assembled by MASM for an 80386 processor:

MOV AX, 5
ADD AX, 10

Now assume that this another Assembly Code which is assembled by another hypothetical assembler (lets say HASM) for the same 80386 processor:

MOV 5
ADD 10

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)

Q0: > does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

It's not the processor/family that defines the detailed syntax of the assembly language for a particular CPU - the Assembler program is what defines the assembly language it accepts. You can have two different/incompatible assembly languages for the same processor/family.

Of course the CPU itself will determine what concepts are needed in the assembly language - e.g. 16 registers or 8, of different sizes, etc.

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Yes. "right assembler"=>"corresponding assembler"

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

No, because the machine code is processor-/family-specific and you are copying between different processor/family

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)

At a low level the generated binary code of e.g. an instruction to move a constant into a register is obviously compatible between these two PCs because it is aimed at the same processor/family.

HOWEVER even if it isn't obvious in the assembly code you write, when turned into a binary this is inevitably tightly related to the Operating System - all useful executable programs rely on many Operating System services and these are not the same between your two PCs, so the program won't run in any meaningful way. Maybe it might be possible for the ultra pedantic to come up with a raw binary which could be run on any operating system, but if it's independent of the operating system then it couldn't do anything useful like input or output which is provided by the OS, so while it might prove a point, that point wouldn't actually be very useful.


What is the purpose of learning propositional logic I am in an AI class where we have extensively learned about propositional logic.
I am wondering what the point of learning this is? Are there any uses for propositional logic? Beyond basic logic gates I can't think of any.

Briefly, one can't learn AI without it.
Some of the main content areas of AI are based on logic: knowledge representation, planning, natural language semantics and reasoning. Have a look at the leading AI textbook to see this in detail. A lot of this uses first-order logic, but first-order logic and many of the other major forms of logic are built on propositional logic.
AI has either used or created several other kinds of logic: non-monotonic logic, temporal logic, fuzzy logic, intuitionistic logic, and modal logic. Check out this 5-volume set about logic in AI.
Back to propositional logic: in the 90's it was realized that SAT solvers (programs which could find satisfying assignments to most propositional logic formulas) could solve formerly intractable problems in AI planning. This has been an active research field ever since.
Propositional logic also has a number of very desirable properties: it is consistent, complete, sound, and decidable. Not all forms of logic have all these properties. For example, decidability breaks down in first order logic.
Finally, it's worth knowing that a lot of other stuff in computer science is based on propositional logic. Consider one of the fundamental theorems of complexity theory: the Cook-Levin theorem, which provides a theoretical basis of complexity theory by showing that bounded computations in a Turing machine can be modeled with propositional logic.


Is there a paradigm for composing "incremental update" functions in a pure dataflow style? I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.

Background, just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's mistake is to forget to update a cached value after changing one of its upstream sources/precedents. But the dataflow or FRP programming paradigm is immune to such mistakes. If we have a number of pure functions, and connect them together in a directed dependency graph, then nodes can have their output value cached and re-used until any of the function's inputs change. This system architecture is described in the paper Caching In Dataflow-Based Environments and in an imperative language it's more or less analogous to memoization.

Problem: When one of the inputs to a function do change, we still have to execute the function as a whole, throwing away its cached output and re-calculating from scratch. In many cases, this seems wasteful to me. Consider a simple example that generates a "top 5 whatever" list. The input data is an unsorted list of whatever. It's passed as input to a function that outputs a sorted list. Which in turn is input to a function that takes the first 5 items only. In pseudocode:

input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

The complexity of the sort function is O(N log N). But consider that this flow is used in an application where the input only changes a little bit at a time, by adding 1 element. Rather than re-sorting from scratch every time, it would be faster, in fact O(N), to use a function which updates the old cached sorted list by inserting the new element in the correct position. This is just one example - many "from scratch" functions have such "incremental update" counterparts. Also, maybe the newly added element won't even appear in the final_output because it's after the 5th position.

My intuition suggests it might be possible to somehow add such "incremental update" functions to a dataflow system, side by side with the existing "from scratch" functions. Of course, re-calculating everything from scratch must always give the same result as a doing bunch of incremental updates. The system should have the property that if each of the individual primitive FromScratch-Incremental pairs always give the same result, then the larger composite functions built from them should also automatically give the same result.

Question: Is it possible to have a system/architecture/paradigm/meta-algorithm which can support both FromScratch functions and their Incremental counterparts, cooperating for efficiency, and composed into large flows? If not, why? If someone has researched this paradigm already and published it, what is it called, and can I get a short summary of how it works?

This field has been invented many times, and goes under many names, such as:

Online algorithms.
Streaming algorithms, stream queries, continuous queries.
Dynamic data structures.
Self-adjusting computation (as per Andrej).

(And possibly more.) Those are not the same, but related.

Paraphrasing  Cai et al (1): There are two core ways of implementing online algorithms generically (i.e. without reference to any specific algorithmic problem):

Static incrementalisation. Static approaches analyse a program at compile-time and produce an incremental version that efficiently updates the output of the original program according to changing inputs. Static approaches have the potential to be more efficient than dynamic approaches, because no bookkeeping at runtime is required. Also, the computed incremental versions can often be optimised using standard compiler techniques such as constant folding or inlining. This is the approach investigated in (1).
Dynamic incrementalisation. Dynamic approaches create dynamic dependency graphs while the program runs and propagate changes along these graphs. The most well-know approach is Acar's self-adjusting computation. The key idea is simple: programs execute on the original input in an enhanced runtime environment that tracks the dependencies between values in a dynamic dependence graph; intermediate results are cached. (As you might imagine, this tends to use a lot of memory, and much research in this field is about how to limit memory usage.)  Later, changes to the input propagate through dependency graphs from changed inputs to results, updating both intermediate and final results; this processing is often more efficient than recomputation. However, creating dynamic dependence graphs imposes a large constant-factor overhead during runtime, ranging from 2 to 30 in reported experiments.

In addition, one can always  try and come up 'by hand' with an online version of a given algorithm. This can be difficult.

(1) Y. Cai, P. G. Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for Higher-Order Languages: Incrementalizing λ-Calculi by Static Differentiation.


Is this NP-completeness proof correct? I want to prove that a problem $P_1$ is NP-complete. Let say that I want to do a reduction from SAT problem.

If the instance of problem $P_1$ depends on $M$ and $N$, can I specify the sturcture of the instance of the SAT problem?

More precisely, can I say that, for example, the instance of SAT problem is composed of $M\times N +1$ clauses and every clause has $M+N$ literals ?

Based on this structure of the instance of SAT problem, I construct an instance of $P_1$. Is this proof correct?

In your specific case, what other constraints do you have on $M$ and $N$? For example, if it is possible that $M=N=1$, then each of your clauses will have 2 literals, and your SAT problem actually seems to become the 2-SAT problem which is in P.

So if $P_1$ depends on $M$ and $N$, maybe you should consider an NP-complete SAT variant that somehow takes them into account. In general, if you want to add some additional constraints on SAT (or any other problem you reduce from), make sure the problem still remains NP-complete.


Arithmetic code: from interval to code value I've not clear how to pass from final interval to code value, for example:

Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source S={2,1,0,0,1,3};

After the encoding process we'll have an interval $[ 0.7426, 0.7428 ) $.

Now the final step is to find the shortest representation to transmit and in the book the chosen value is 0.10111110001 = 0.74267578125.

  How is it possible to calculate the shortest representation and the code value to transmit having the final interval?

You transmit the bit pattern of the left(smaller) end, until you either run out of bits or you find a difference of the left and the right (bigger) number.  The first difference will have a 0 on the left side, and a 1 on the right side.  If this 1 is not the last bit on the right side, you transmit this 1 and you are done, you transmitted the shorted number from within the interval.

a=0011001100
b=0011010010
->001101

If this 1 is the last bit you cannot transmit it directly, because then you would send exactly the right end which is not within the interval.  In this case you have to continue sending bits from the left side, until you hit the next 0.  Here you transmit a 1, and you are done.

a=00110010101
b=00110011000
->0011001011


Connection between CPU address bus and max amount of RAM So, i'm stack on the following question > "A system has a 12 bit address bus. What is the maximum amount of RAM that can be installed on the system?"

First of all, is this question correct? If so, can you explain to me way and how to determine the answer?

Thanks in advance.

A 12 bit address bus means the computer can access $2^{12}$ unique blocks of memory.  Unstated in the problem is the size of each block, and without that information you cannot determine the maximum amount of ram.

Bulat also points out that there are other tricks that could be played, such as multiplexing the address bus.  If the address was sent in 2 cycles rather than 1, then $2^{24}$ blocks could be addressed.

Lacking any other information, and recognizing that this is a homework/test question we can make a few assumptions.  The first is that we're not doing anything exotic like multiplexing the address bus.  In a test-question setting, it is highly likely that they would call a multiplexed 12 bit bus a "24 bit bus" instead unless you were on a chapter specifically dedicated to clever address bus tricks.

The second assumption we have to make is the size of the block.  Since it isn't specified, there are two common assumptions we could make.  The first is that it is byte addressable, meaning each byte can be addressed individually as its own block.  In that case, there's a maximum of $2^{12}$ bytes of memory addressable.  The other common assumption is that they are addressable by machine word.  If you are working in a chapter on 16-bit machines, it might be 16-bit blocks (2 byte), so there'd be a maximum of $2^{12}\cdot 2 = 2^{13}$ bytes.

Given it is a test question, and your teacher is not evil, I would assume the simplest answer is likely correct.  I'd assume 1 byte blocks, and no exotic trickery, yielding a best answer of $2^{12}$ bytes.  If I was facing this in an industry setting, I'd find the datasheets on the processor to determine the exact answer.


Construct a grammar for the language How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must be in each string somewhere, and each string must start with a bb. For example, the strings bbababbbaa, bbbaaaababaa, and bbbab are in the language, while a, aabb, baaa, and bbba are not.

The string much start with $ bb $ .
There should at least one occurrence of the sub-string $ bab $

Hence, the structure of the regular expression must be something like this:
$$ bb[some \: string]bab[some \: string] $$

and, we can define $ [some \: string] $ something like this:

$$ (a + b)^* $$

which means, there can be any number (including 0) of either a's or b's.
Therefore, the final regex for the word is,
$$ bb(a+b)^*bab(a+b)^* $$


Regular Languages in $ \mathsf{\text{}NC^1}$ Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.

To prove the theorem stated above we need some theorems and definitions given below :

Barrington Theorem : A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in $\mathsf{\text{}NC^1}$.

Proof Idea of Barrington Theorem is like small depth boolean circuit implies small group program and small group program implies small branching program.

Monoid : In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I google and find out a research paper but not able to understand much (some of the things that I have understood I have written above). A high level proof idea or an resource to prove the theorem stated above will be helpful.

Let $L$ be a regular language. Take some DFA $\langle q_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $q \mapsto \delta(q,\sigma)$. In other words, if $Q = \{q_1,\ldots,q_m\}$, then in input $\sigma$, the circuit computes the sequence $\delta(q_1,\sigma), \ldots, \delta(q_m,\sigma)$.

There is another constant size circuit whose inputs are two functions $f,g\colon Q \to Q$ (such as the outputs of the circuit above), and whose output is their composition $q \mapsto f(g(q))$. As before, we encode the inputs and outputs as sequences of $m$ states.

Given $n$, construct a circuit that computes whether a given input word $\sigma_1 \ldots \sigma_n$ belongs to $L$ as follows. Assume by simplicity that $n = 2^t$.

Compute the functions $q \mapsto \delta(q,\sigma_1), \ldots, q \mapsto \delta(q,\sigma_n)$ using the constant size circuit from the first paragraph.
Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2), \ldots, q \mapsto \delta(q,\sigma_{n-1}\sigma_n)$ using the constant size composition circuit from the second paragraph.
Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2\sigma_3\sigma_4), \ldots, q \mapsto \delta(q,\sigma_{n-3} \sigma_{n-2} \sigma_{n-1} \sigma_n)$ using the constant size composition circuit.
Continue in the same way for $t-2$ more levels, until you compute the function $\varphi$ given by $q \mapsto \delta(q, \sigma_1\ldots\sigma_n)$.
Using a constant size circuit, determine whether $\varphi(q_0) \in F$.

This circuit has depth $O(\log n)$ and size $O(n)$, and moreover it is uniform in $n$. This shows that $L \in \mathsf{NC^1}$.


Reduction of the Y combinator The  Y combinator expression is as follows:
$$ Y \equiv \lambda  f .(\lambda  x .f(xx) )) .(\lambda  x .f(xx)  ) $$

Now , if I am not wrong , then this expression can be reduced by seeing this as the argument:
$ .(\lambda  x .f(xx))$ hence would lead to the consumption of first bound variable giving:
$$ (\lambda  x .\lambda  x .f(xx) (xx))$$

which is equivalent to $ \lambda  xx .f(xx)  (xx)$

which will yield $ f(xx) $.

But in my book I don't find the Y combinator being reduced to this and it made me feel that something is fishy with the reduction that I am doing .

Is there any mistake in this?

You've misread the definition of $Y$. $(\lambda x.f(xx))) (\lambda x.f(xx))$ is the body of the function. You can put an additional pair of parentheses in the definition:
$$ Y = \lambda f. \color{red}{\mathbf{(}} (\lambda x.f(xx))) (\lambda x.f(xx)) \color{red}{\mathbf{)}}$$
Beware that different authors use different conventions for parentheses. But under the most common convention, $\lambda$ has lower precedence than application, so the body of a lambda goes until the next enclosing closing parenthesis. If a text uses a different convention, make sure to put parentheses accordingly.

You can reduce $Y$, but the argument $(\lambda x.f(xx)))$ is applied to $(\lambda x.f(xx))$. The $\lambda f. \ldots$ doesn't change since it isn't applied to anything.
$$\begin{align}
Y \;\; = \; & \lambda f. (\lambda \color{magenta}{x}.f(\color{magenta}{x}\color{magenta}{x}))) \color{magenta}{(\lambda x.f(xx)))} \\
\rightarrow_\beta \; & \lambda f. f \left( (\lambda x.f(xx))) (\lambda x.f(xx))) \right) \\
\end{align}$$
Let $\Omega_f = (\lambda x.f(xx)) (\lambda x.f(xx))$, so that $Y = \lambda f. \Omega_f$. The reduction above is $\lambda f. \Omega_f \rightarrow_\beta \lambda f. f \Omega_f$. That's $\Omega_f \rightarrow_\beta f \Omega_f$ under the context $\lambda f. []$. There's an infinite chain of reductions
$$
Y = \lambda f. \Omega_f
\rightarrow_\beta \lambda f. f \Omega_f
\rightarrow_\beta \lambda f. f (f \Omega_f)
\rightarrow_\beta \lambda f. f (f (f \Omega_f))
\rightarrow_\beta \ldots
$$
This is how the recursion combinator works. But this won't do anything “useful” until $f$ is replaced by a lambda so that the $f \Omega_f$ part can be reduced.

If you apply $Y$ to a function $g$, a redex appears at the top level.
$$ \begin{align}
Y g \;\; = \;\; & \left( \color{green}{\lambda f}. (\lambda x.\color{green}{f}(xx))) (\lambda x.\color{green}{f}(xx)) \right) \color{green}{g} \\
\rightarrow_\beta \; & (\color{darkblue}{\lambda x}. g(\color{darkblue}{x} \color{darkblue}{x})) \color{darkblue}{(\lambda x. g(x x))} \\
\rightarrow_\beta \; & g \left( (\lambda x. g(x x)) (\lambda x. g(x x)) \right) \\
\leftarrow_\beta \; & g \left( \left( \color{brown}{\lambda f}. (\lambda x. \color{brown}{f}(x x)) (\lambda x. \color{brown}{f}(x x)) \right) \color{brown}{g} \right) \\
= \; & g (Y g)
\end{align}$$


Overlap between computer science and analytic geometry? I would like to know if there are some topics that could be covered in an undergraduate first-term course about analytic geometry, but related to Computer Science.

I know that, for example, the simple equation for the line can be used for explaining linear regression or other topics in elliptic cryptography (too advanced for an initial course).

Any suggestion of topics?

Computer graphics is applied analytic geometry, and showing how games do their computations might be exactly the kind of motivating subject matter you are looking for.


Until quantifier of Computation Tree Logic It's quite a short question: Refering to this Wikipedia article p U q means, that p has to hold at least until at some point q holds.

So, does it mean:

On each path starting from the current state p has to hold in each state until a state is reached in which q holds.
On each path starting from the current state p has to hold in any state before a state is reached in which q holds.

Example: Suppose p holds in s3 and q holds in s5. Let s0 be the starting state and the set of edges given by { (s0,s1),(s1,s2),(s2,s3),(s3,s4),(s4,s5) }. Let's assume p and q don't hold in all the other states. Is p U q satisfied, starting from s0?

$pUq$, as is, is not a well-formulated CTL (or more generally - CTL*) formula. A CTL* formula is a state formula, which starts with has a path quantifier ($A$ or $E$).

$pUq$ is a path formula, which means it refers to a single (linear) computation. A computation satisfies $pUq$ if $p$ holds in every state until $q$ holds (and $q$ must hold at some state).

Translating to CTL, you can talk about two different formulas: $ApUq$ and $EpUq$. The former is true in a state if every path starting from this state satisfies $pUq$. The latter is true in a state if there exists such a path starting from that state.

Does that clear things up?


blockchain database - why so redundant I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database.

Why can't distributed blockchain database be 'distributed' to reside partly on many computers to achieve say fixed 10 times redundancy, not times number of users redundancy? Will speed be times slower or other reason it's not done?

See https://en.wikipedia.org/wiki/Blockchain_(database)#Decentralization, which states that "Every node in a decentralized system has a copy of the blockchain. This avoids the need to have a centralized database managed by a trusted third party."

This is as true of 10 computers as it is of one.  It's not about redundancy from this perspective, though that is certainly a motivating factor.  It's about having zero centralized authorities,  and the only way to do that is to allow everyone to have a copy of the blockchain.


Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable I came across following facts:

  Set of finite languages over a finite alphabet is countable.
  Set of languages over finite alphabet is uncountable.
  I believe proof of this will be similar to below fact number 3.
  Set of languages over {0,1} is uncountable.

I came across proof of fact 1 here and of fact 3 here.

Summary of fact 1 proof:

  Let your finite alphabet be $Σ={a_1,…,a_ℓ}$ and let $\#$ be some character not in $Σ$. Let $L={w_1,…,w_n}$ be a finite language over $Σ$. Then the string $\#w_1\#w_2\#…\#w_n$ maps different $L$ to different integer.

Summary of fact 3 proof:

  Let $L$ be set of all finite length strings over $\{0,1\}$. We can generate a one-to-one mapping from $L$ to $\mathbb{N}$ : just add a 1 in front of each string in W and interpret the resulting strings as binary numbers. So $L$ is countable. Now let $L_{\{0,1\}}$  is countable, where $L\{0,1\}=\{L_1,L_2,L_3,…\}$ with each $L_i$ being a language over $\{0,1\}$. Given that each $L_i$ is a set whose elements are strings from $L$, and since $L$ is countable, we can build a table whose row indices are language indices and whose column indices are string indices as follows: for each table cell with row index $i$ and column index $j$, write 1 if the language $L_i$ contains the string $s_j$ or 0 otherwise.

  We flip the value of every diagonal cell on the table above, then collect all strings $s_j$ such that the diagonal cell on the column of $s_j$ has a 1 after flipping:

  Lets call it $L_{diag}={s_2,s_3,...}$.
  $L_{diag}$ is a language with a special property: it is different from every language $L_i∈L_{\{0,1\}}$. This implies $L_{diag}≠L_i$ for all $L_i∈L${{0,1}} and therefore $L_{diag}∉L_{\{0,1\}}$. However, since $L$ is a set of strings which are in $L$, $L_{diag}$ is a language over {0,1} and therefore $L_{diag}∈L_{\{0,1\}}$, a contradiction. Hence $L_{\{0,1\}}$ cannot be countable.

Doubts

I get both the proofs, but I dont get why approaches followed in each of them cannot be used to prove other fact incorrect. That is:

Why I cant use fact 1 proof approach to prove fact 3 is incorrect, that is "set of languages over {0,1} is countable".
Cant I form similar string string $\#w_1\#w_2\#…\#w_n$ for different languages to map them to different integers?
Why I cant use fact 3 proof approach to prove fact 1 is incorrect, that is "set of finite languages over a finite alphabet is uncountable"?

Cant I form similar table for finite languages and then form $L_{diag}$ which wont belong to the set of finite languages?

If the language is infinite, the word $\# w_1 \# w_2 \ldots$ would be infinite, and so doesn't map to an integer in any meaningful way.
Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.


Computing FOLLOW sets for LL(1) grammar. Stuck on question Calculate the FOLLOW sets for all the non terminals:

  $S \rightarrow bEx \mid Db \mid b \mid F$

  $D \rightarrow EDc \mid Y$

  $E \rightarrow dED \mid dDY$

  $Y \rightarrow ab \mid aDx \mid \varepsilon$

So I know that:

FOLLOW($S$) = $\{\$\}$ since it doesn't appear anywhere

FOLLOW($D$) = $\{b, a, x, c\}$, since it is followed by terminal $b$ in $S$, $c$ in $D$, FIRST($Y$) in $E$ which is $\{a\}$ ($\varepsilon$ not included), and $x$ in $Y$

FOLLOW($E$) = $\{x, c, a, d\}$, since it is followed by terminal $x$ in $S$, FIRST($D$) in $D$ which is $\{a, d, c\}$

but how do I calculate FOLLOW($Y$)? It isn't followed by anything. I'm guessing since it's at the end of $D$ and $E$ its the union of their follow sets including $\$$ since there's an $\varepsilon$?

Have been stuck on this for a while, any help is HIGHLY appreciated. Thanks in advance for any input

$FOLLOW\ (Y) = FOLLOW\ (D)$

  $FOLLOW\ (Y) = FOLLOW\ (E)$

A general Rule of thumb is, for any grammar

S -> XAB
A -> BC
X -> Bt

$
Follow (B) = Follow (S)  $
(Since there isn't anything after B in Production-1)

$Follow (B) = First (C) $ (Since C follows B in Production-2 and is a non-terminal)

$Follow (B) = t $ (since it follows B in Production-3 and is a terminal)


Checking whether a node is expandable I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable.  A node is said to be expandable if it has a child node that hasn't already been visited.
How can I test whether a given node is expandable?
I know you could always try out every play possible given a node, and test whether each generated node is already a node in the tree, but that seems inefficient.  Is there a more efficient algorithm?
The rules of Quoridor are (quoting from Wikipedia):

Quoridor is played on a game board of 81 square spaces (9x9). Each player is represented by a pawn which begins at the center space of one edge of the board (in a two-player game, the pawns begin opposite each other). The objective is to be the first player to move their pawn to any space on the opposite side of the gameboard from which it begins.
The distinguishing characteristic of Quoridor is its twenty walls. Walls are flat two-space-wide pieces which can be placed in the groove that runs between the spaces. Walls block the path of all pawns, which must go around them. The walls are divided equally among the players at the start of the game, and once placed, cannot be moved or removed. On a turn, a player may either move their pawn, or, if possible, place a wall.
Pawns can be moved to an adjacent space (not diagonally), or, if adjacent to another pawn, jump over that pawn. If an adjacent pawn has a third pawn or a wall on the other side of it, the player may move to any space that is immediately adjacent to other adjacent pawns. The official rules are ambiguous concerning the edge of the board.
Walls can be placed directly between two spaces, in any groove not already occupied by a wall. However, a wall may not be placed which cuts off the only remaining path of any pawn to the side of the board it must reach.

I'm using the Monte Carlo Tree Search algorithm, which follows these steps:

Selection: Using a tree policy, like UCT1, nodes are selected while traversing down the tree
Expansion: From the node selected by the tree policy, create a random child node
Simulation: Either use a random simulation from the node or a system with a weighing of moves
Backpropagation: If the simulation is victorious for the computer, add say each node "won" all the way up the tree. If it lost, then each node "lost" up the tree.

During the Selection step, one cannot select a node that is fully expanded. Is there a better way to check whether a node is expandable than just trying out every possible move from that node, and check if it is already in the tree? What algorithms exist for this (if any?)

You keep track of your work so far. As you say, a node is expandable if it has a child node which you haven't visited so far. In your program, every time you reach a new node in the expansion phase, you calculate all its children (you can also do this dynamically, but let's keep things simple). As time goes on, you mark each child which has been visited. In order to know whether a node is expandable, you just check whether all its children have been marked.

Of course, you don't really need to check all children. You can keep a counter at each node that counts the number of unvisited children. The next question would be – how do I find an unvisited child. It's a nice elementary exercise finding a way to achieve this efficiently.


Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy? In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$).

Why do we have these conditions?

A concise answer would be: To have enough time (resp. space) to do the diagonalization jobs.

Remember that both of these separation results are just using diagonalization techniques. In particular, to separate bigger time/space bound apart smaller time/space bound, one use the bigger bound (by just ONE machine) to diagonalize over all the possible smaller time/space-bounded machines.

And to do that, one needs to know when to finish (on each input) in case of time hierarchy, or where to prohibit the crossing (on each input) in case of space hirachy. This is possible only when the bigger bound is constructible. For time, constructibility at least requires $\geq n$. For space, constructibility at least requires $\geq log(n)$.

For full constructibility, it is not necessary to require any thing. But note that while constant functions are fully constructible (in time and space), functions in between like $log log(n)$, $log log log(n)$ (for space), $\sqrt{(n)}$, $n^{2/3}$ (for time) are not so. Informally, the spectrum of full constructibility is not continuous.

Lastly, one can even separate the notions of time constructibility by reasonable conjectures.


CFL and inverse homomorphism I found a proof that shows CFL is closed under inverse homomorphism.

First of all the Definition of an homomorphism and its inverse:

$h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in L\}$

$h^{-1}: \Delta^{*} \rightarrow \Sigma^{*} \ \ \ h^{-1}(L) = \{w | h(w) \in L\}$

The proof I found works as follows:

Let $L = L(A)$ for some PDA $A$.
Construct PDA $A’$ to accept $h^{-1}(L)$.
$A’$ simulates $A$, but keeps, as one
component of a two-component state a
buffer that holds the result of applying
$h$ to one input symbol.

I really can't get my head around that intuition.
My approach was to create an example:

Let $L=\{a^{n}b^{n} | n \in \mathbb N\}$ and $h: \{a,b\}^{*} \rightarrow \{0,1\}^{*} | \ \ h(a) = 01, h(b) = 1$

$\Rightarrow h(L)= \{(01)^{n}1^{n} | n \in \mathbb N\}$

I would then create an PDA $A$ that accepts my $h(L)$ and PDA $A'$ (because I already know how my inverse image looks like) that accepts $L$.

And that is the point I got stuck. I know that I need a different PDA for $A'$ with some sort of buffer but I don't know how to realise that.

My Question: Can someone explain the proof a little bit more detailed. And what it means that $A'$ simulates $A$?

Suppose that $A=(Q,\Delta, \Gamma, \delta, q_0, \gamma_0, F)$.

Define $\operatorname{Prefs}(u)$ to be the set $\{v|\exists w, u = vw\}$ of prefixes of $u$.

Define $A':=(Q',\Sigma, \Gamma, \delta', q_0', \gamma_0, F')$ by:

$\displaystyle Q':= \left(Q\times \left(\bigcup_{a\in \Sigma}\operatorname{Prefs}(h(a))\right)\right) \sqcup \left(Q\times \Sigma \right)$. A state $(q,u)$ with $u\in\operatorname{Prefs}(h(a))$ will mean "I'm in state $q$ in $A$, I've read $u$ and am waiting for the rest of $h(a)$ and then I'll go to $(q,a)$" while a state $(q,a)$ means "I've read $h(a)$ and will now simulate a transition reading $a$ in state $q$ in $A$ to arrive to some state $(q',\varepsilon)$".
Transitions are (where if a transition doesn't mention the stack, it means it doesn't change it):

$(q,u)\overset{b}{\to}(q,ub)$ whenever the destination state exists (i.e. if you can read the letter while remaining a prefix of some $h(a)$, you can just keep reading)
$(q,h(a))\overset{\varepsilon}{\to}(q,a)$ (i.e. at any point, if the word I've read is the image of a letter by $h$, I can replace it by its preimage)
$(q,a)\overset{\varepsilon,...}{\to}(q',\varepsilon)$ whenever $q\overset{a,...}{\to}q'$ in $A$ (where both $...$ are the same thing) (i.e. if I just read the image of $a$, simulate reading $a$ in $A$)

$q_0':=(q_0,\varepsilon)$
$F':=F\times \{\varepsilon\}$

Then (I think that) $L(A')=h^{-1}(L(A))$.

What you call "buffer" would be the right component of the states used to remember the prefix of $h(a)$ you've read.


How hard is counting the number of simple paths between two nodes in a directed graph? There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).

However it seems that, surprisingly, the problem gets much harder if instead of testing for the existence we want want to count the number of paths.

If we allow paths to reuse vertices then there is a dynamic programming solution to find the number of paths from s to t with n edges. However, if we only allow simple paths, that don't reuse vertices, the only solution I can think of is brute force enumeration of the paths, something that has exponential time complexity.

So I ask,

Is counting the number of simple paths between two vertices hard?
If so, is it kind of NP-complete? (I say kind of because it is technically not a decision problem...)
Are there other problems in P that have a hard counting versions like that too?**

The most common complexity class associated to counting problems is #P. Deciding if there a simple path from a given node to another is clearly in NP. Counting them is then in #P.

About the NP-completeness: even if that's not a decision problem, it would hardly fit in NP: there may be $n!$ paths, and non-determinism does not help you about that (you'd still need to check them all)

The answer to your two first two question is: yes, it is hard, it is #P-complete (ref).

The Wikipedia article gives pertinent facts: 1) probabilistic algorithms are useful to approximate #P-complete functions, and that's the kind of algorithm used for the approximation in the previous article. 2) There are other easy problems with hard (#P-complete) counting versions:

finding (linear) vs. counting all assignments satisfying a DNF formula or an instance of 2-SAT
finding (linear) vs. counting topological sortings
finding (O(VE)) vs. counting perfect matching in bipartite graphs

You already know that if you remove the constraint "simple path" the problem falls into P (well you have to bound the length of the paths by a polynomial of the size of the graph or give the bound in unary)


Questions on shortest path and minimum spanning tree T/F Questions

Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
Solution - False

I think this should be True, as Dijkstra's Algorithm sums the paths from source to each vertex. If every edge weight is increased by a constant, then nothing should be changed if all edges are positive. If some edges are negatives, then I don't know if Dijkstra's Algorithm still applies here.

Adding a constant to every edge weight does not change the solution to the MST problem. (I don't have the solution for this)

I think this is True for the same reason above.

Can someone confirm on this?

You are wrong on the first one and right on the second one (but for the wrong reason).

To see that (1) is false, just observe that there exists a constant $c$ such that adding $c$ to all weights turns the weighted minimum distance problem into the unweighted one.

On the other hand, (2) is true because every spanning tree contains has exactly $|V|-1$ edges, therefore adding $c$ to all weights adds $c(|V|-1)$ to the total cost of each spanning tree.


Build a scheduler, to simulate parallel game flow I am building a strategy game where units can interact with each other.

As input I am getting a list of actions. I need to output a scheduler, that will tell when to start each action. The goal is to find the shortest time combination of all the actions.

Action is defined as interaction between two users or user with him self, it build from 4 parts:

performing unit - the unit that performs the action
receiving unit(optional) - the unit on witch the action is applied
supported actions - A list of actions that the receiving unit can perform while applying this action on him.
action time - how long does it takes to execute the action

Rules:

Units can only perform one action in a time
Units may have to perform more than one action

The best solution will be: Is to run all those actions in parallel. There are two things that stops me from doing it.

If more than one action have the same performing unit, they cannot start simultaneously as units can perform only one action in a time.(Rull 1)

The other problem is actions with receiving unit. I need to make sure that the receiving unit is currently performing one of the supported actions(defined in action part 4), if it's not, this actions cannot be started.

In case of actions without receiving unit, they can all be started simultaneously. How ever I need to make sure that I am not left with action that have a receiving unit, that cannot be started as the receiving unit already performed all his actions.(So supported action will never be started)

Your set of rules is self-conflicting. You require

  Same unit cannot perform two actions in parallel

but also

  When unit perform attack, the interacting unit must perform take damage [...] during the attack-action time of the performing unit.

and

  Multiple units can attack single unit at once

In other words, you require that multiple take damage actions be performed simultaneously while demanding that that may not happen.


How does increasing the page size affect the number of page faults? If we let the physical memory size remain constant,

What effect does the size of the page have on the number of frames?
What effect does the number of frames have on the number of page faults?

Also, please provide reference strings as an example.

Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames.

Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice.  Imagine a system with four frames with the reference history of 0, 4, 3, 1.  On a page fault, LRU would victimize frame 0.  With a doubling of page size the reference history becomes 0a, 1b, 1a, 0b; so the LRU victim would be 1 (corresponding to small page frames 3 and 4) when one would prefer to victimize 0a (the first half of 0).

Large pages will also waste more space with internal fragmentation.  If a typical process has three sections (text, heap, stack), on average about half a page per section is unused so 1.5 pages worth of memory are unused per process.  If page size is doubled, this waste is doubled.

On the other hand, using larger pages will draw in more memory per fault, so the number of faults may decrease if there is limited contention and/or reasonably high spatial locality at the scale of page size (e.g., references to the high half of a double-size page occurring near in time to references to the low half would make replacement of a double-size page a close approximation of the replacement for the two smaller pages of which it is composed).  (If memory is abundant, first reference [a.k.a. compulsory] page faults will tend to dominate, so larger pages will reduce the number of page faults.)  Of course, the OS can use prefetching to accomplish the same reduction in faults with the benefit of being able to throttle prefetching under heavy memory pressure or poor prefetch behavior while avoiding the above mentioned disadvantages of large pages.

Of course, larger pages do reduce the number of TLB misses (sometimes called minor page faults), and an OS can support multiple page sizes and aggregate smaller pages to form larger pages (for reducing TLB misses) and deaggregate larger pages to from smaller pages (to reduce the volume of memory swapped and to reduce the above negative effects of larger pages).