Task Manager Performance tab in windows I do not understand the following options in windows. Could any one explain

CPU Usage is how much your processor is running; of the available cycles to compute, how many are actually being used. On the left it shows the current value, and on the right it shows your history. The two graphs are because you have two CPUs (well, two cores in one CPU.)

Page File is something used when your RAM is filled up. All the data in your computer, while it's being used by a program, has to be "kept alive" somewhere, and this is what RAM is built for. When that's full, though, Windows will start using your hard drive instead. This is much, much slower to access than RAM, and will wear out your hard drive somewhat more quickly. I might recommend adding more RAM or closing unneeded processes.

In "Totals" you see:
- Handles, which is resources that a program is using - for instance, a program might have on handle to keep track of a file, one handle to check your registry for settings, and many many others.
- Threads, which is one part of a program that can run by itself. For instance, a simple video game will usually contain at least one thread for running the game, one thread for drawing graphics, and one thread to pay attention to mouse clicks or button presses.
- Processes, which is generally speaking "programs". Some programs, like Google Chrome or Metasploit, will keep many processes open at a time. Each process corresponds to one .exe file, although several instances of the same file could be loaded as separate processes. If you change tabs in Task Manager, you can see a list of all processes, and how much they're each using up resources on your computer.

The other three boxes, "Physical Memory", "Commit Charge", and "Kernel Memory", refer to different parts of RAM & Page File.
- Physical Memory refers to actual RAM (not page file!) being used by anything; right now you have 1.52GB out of 3.14GB of RAM available.
- Commit Charge refers to Physical Memory and Page File, collectively. Right now you are using 1.77GB, out of a total possible of 5.07GB.
- Kernel Memory refers to memory being used by Windows itself, and not by any particular process. Unlike closing a program, which frees its memory, kernel memory is almost impossible to free up.


Expected length of a random walk on a line I am given the following randomized algorithm for SAT,

Input: A satisfiable CNF-formula $\varphi$.
Output: An assignment $\rho$, such that $\rho \models \varphi$.

The algorithm works as follow:

Choose an arbitrary assignment $\rho$.
As long as $\rho \not \models \varphi$

Choose a clause in $\varphi$ not satisfied by $\rho$ uniformly at random.
Choose a variable $x\in_{u.a.r}\operatorname{VAR}(C)$.
Flip the value of $\rho(x)$ (set $\rho(x) = \overline{\rho(x)}$).

We have to prove that for a 2-CNF Formula, the algorithm has polynomial expected running time.

I have proven that for a fixed assignment $\alpha$, such taht $\alpha \models \varphi$, with probability $p \geq 1/2$, after each iteration the number of variables that are assigned different values in $\alpha$ and $\rho$ decrease by one. With probability $1-p$, the assignments $\rho$ and $\alpha$ differ at one extra variable.

Now I have to prove, that the algorithm finished in expected polynomial number of steps. I was able to add one more step of abstraction. Let $X_i$ be the random variable that indicates the number of steps needed to make $\rho = \alpha$, when $\rho$ and $\alpha$ differ by exactly $i$ variables. Then it holds that
$$E[X_i] = 1 + p E[X_{i-1}] + (1-p) E[X_{i+1}],$$
and $X_i \leq X_{i+1}$ for all $i$ and $E[X_0]$ is equal to 0. We need to find a polynomial bound for $E[X_i]$.

Since $p\geq 1/2$ and $X_i \leq X_{i+1}$, the following must hold
$$E[X_i] \leq 1 + \frac{E[X_{i-1}] + E[X_{i-1}]}{2}$$

Now this can bee seen as walking on the integer line, in each step we move either one step to the left or one step to the right and the probability of moving to the left is at least one half. We have to prove that in expected polynomial many steps (polynomial in the starting position), we reach the number $0$ on the line.

Any help on this problem is very appreciated :)

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated.

Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move right of the origin is $\frac{\binom{2n}{n}}{n+1}$ (these are the Catalan numbers), and so the probability that you move right of the origin at the first time after exactly $2n+1$ steps is
$$
q_{2n+1} = \frac{1}{2^{2n+1}} \frac{\binom{2n}{n}}{n+1} = \Theta\left(\frac{1}{n^{3/2}}\right).
$$
Therefore the expected number of steps until you first move right of the origin is
$$
\sum_{n=0}^\infty (2n+1) q_{2n+1} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty.
$$
On the other hand, the number of visits to the origin is
$$
\sum_{n=0}^\infty \frac{\binom{2n}{n}}{2^{2n}} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty,
$$
so you will move right of the origin infinitely many times.

The conclusion is that a random walk started at $i > 0$ will hit the origin almost surely, but the expected time to reach the origin is infinite.

Your case is, however, different, since you "bounce" at $i = n$: when at position $n$, you always move to $n-1$. You can think of the situation in the following way. Although the actual set of positions is $0,\ldots,n$, we imagine reflecting this set along the point $n$, adding $n-1$ new positions $n+1,\ldots,2n$. Here position $n+k$ really plays the role of position $n-k$. We can run the random walk as usual, declaring victory upon reaching either position $0$ or position $2n$.

After $t$ steps, the displacement from the initial position has binomial distribution $\mathrm{Bin}(t,1/2)$, which is close to a normal distribution $N(t/2,t/4)$. Therefore after $t$ steps, we expect to be at a distance of about $\Theta(\sqrt{t})$ from where we started (this can be shown formally by considering the squared displacement and using Chebyshev's inequality, which requires an estimate of the fourth moment of a binomial random variable). In your case, we start at some position $i \in \{1,\ldots,n\}$. After $\Theta(n^2)$ steps, we expect to be about $\Theta(n)$ far from where we started, and so, hit either $0$ or $2n$. Therefore the process should converge in $O(n^2)$ steps.

We can also solve the recurrence directly when $p = 1/2$. Recall that the recurrence is
$$
E[X_i] = 1 + \frac{E[X_{i-1}] + E[X_{i+1}]}{2},
$$
with initial conditions $E[X_0] = E[X_{2n}] = 0$.

Let $N_i = E[X_i] + i^2$. Then
$$
N_i = 1 + \frac{N_{i-1} + N_{i+1} - (i-1)^2 - (i+1)^2}{2} + i^2 = \frac{N_{i-1}+N_{i+1}}{2},
$$
with initial conditions $N_0 = 0$ and $N_{2n} = 4n^2$.

Let $M_i = N_i - 2ni$. Then $M_i$ satisfies the same recurrence as $N_i$, with initial conditions $M_0 = M_{2n} = 0$. It is easy to check that the minimum and maximum of the sequence $M_0,\ldots,M_{2n}$ must be attained at the endpoints (since $\max(M_{i-1},M_{i+1}) \geq M_i$ and $\min(M_{i-1},M_{i+1}) \leq M_i$), and so $M_i \equiv 0$. Therefore $N_i = 2ni$, and so
$$
E[X_i] = i(2n-i) = n^2 - (n-i)^2.
$$


Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted? Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
That is, each node in the topological graph should be visited once at least (instead of exactly).

Is it still NP-complete or reduced to a P problem?
How would this modification affect classical methods for solving the original TSP such as dynamic programming, mixed integer programming, meta-heuristics and maybe branch-and-cut/bound/price?

What I have tried:

I believe this variant might be easier to solve, but after a sketchy thought about the MIP model, I found it is hard to write the sub-tour elimination constraints.

I have checked TSP Where Vertices Can be Visited Multiple Times but it is asking for a working solution which could be a heuristic that does not guarantee the optimality and computational time. This is not what I want.

No, it doesn't become easier. Metric TSP (the version where the distances obey the triangle inequality) is still NP-complete but, in this scenario, the shortest tour always visits every city exactly once. The triangle inequality guarantees that going directly to a new city is always faster than going there via somewhere you've already been.


Shortest paths when edge weight depends on previous edge I have a directed graph with non-negative weights on the edges.
I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300).
I want to collect all the shortest paths from x in X to y in Y.

The weight of the edges depend on the previous edge in the path I am currently on.

Testing the possible paths between x1 and y1, e4 has same attribute "B" as the preceding edge e3, so its weight will be reduced (I want to favour paths with same properties).

How do I actually find the shortest among the paths among x1 and y1 in this scenario?

Let your graph be $G=(V,E)$.  Build a new graph $G'=(V',E')$, where each vertex in $G'$ corresponds to a pair $(u,v)$ of vertices in $G$.  Add an edge $(u,v) \to (v,w)$ in $G'$ iff there is an edge $v \to w$ in $G$.  The intended meaning of the vertex $(u,v)$ is that you are currently at vertex $v$ in $G$, and previously were at vertex $u$.  Thus, you can now figure out what weight to put on the edge $(u,v) \to (v,w)$ -- namely, whatever weight you want to put on the edge $v \to w$ assuming you previously traversed the edge $u \to v$.

Let $X' = \{(x,u) \in E : x \in X, u \in V\}$ and $Y' = \{(u,y) \in E : u \in V, y \in Y\}$.  Now, the find the shortest path in $G'$ from each vertex in $X'$ to each vertex in $Y'$, using an all-pairs shortest paths algorithm.  From this you can infer the length of the shortest path in $G$ from some vertex in $X$ to some vertex in $Y$, while taking into account the fact that edges switch weights.

If you use the Floyd-Warshall algorithm, the running time will be $O(|V'|^3)$, which is at most $O(|V|^6)$.  As an optimization, the vertex set $V'$ can be taken to be $V' = \{(u,v) : u,v \in V, (u,v) \in E\}$.  Then the running time of Floyd-Warshall in $G'$  will be at most $O(|E|^3)$.  Given that your original graph $G$ is fairly small, this might already be feasible without further optimizations.

If you want further optimizations, here's one more.  You can add to $G'$ a special vertex  $x^*$ for each $x \in X$, with an edge $x^* \to (x,u)$ in $G'$ for each $(x,u) \in E$ with the same weight as the edge $x \to u$ in $G$; and similarly add $y^*$ for each $y \in Y$, with edge $(u,y) \to y^*$ of weight 0.  Now find the shortest path from each $x^*$ to each $y^*$.  This can be done by applying Dijkstra's algorithm $|X|$ times, once for each $x \in X$, to find the distance from $x^*$ to each other node in the graph.  The total running time will be $O(|X| \cdot |E'| \log |V'|)$, which is $O(|X| \cdot |V| \cdot |E| \log |V|)$.  You can also achieve running time $O(|Y| \cdot |V| \cdot |E| \log |V|)$ by searching backwards (e.g., reversing the graph).  Given that you have $|Y| \approx 300$, $|V| \approx 2000$, and $|E| \le |V|^2 = 4000000$, this might complete rapidly.


If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$? I tried to solve it as the following:
$$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$
I'll show that $\overline{L}\not\in RE$ by reduction from $$\overline{A_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ rejects } w \big\}$$
I begin by assuming that $\overline{L}$ is recognized by some TM $M'$.

Next, I construct a machine $M_{\overline{A_{TM}}}$ that will use $M'$ to recognize $\overline{A_{TM}}$.

TM $M'$ on input $\langle M, w\rangle$:

Build TM $M_1,M_2$
Simulate $M_1,M_2$ on all $x\in\Sigma^*$, Any simulation will be at most $|x|$ steps.
If $M_1$ and $M_2$ reject the same $x$, then $M'$ will accept $\langle M, w\rangle$.
If $M_1$ or $M_2$ accept some $x$, then $M'$ will reject $\langle M, w\rangle$.

Therefore, $\langle M, w \rangle\in\overline{A_{TM}}$ exactly when $\langle M_1,M_2\rangle\in\overline{L}$.

Because $\overline{A_{TM}}\not\in RE$ so is $\overline{L}$, then $L\not\in co-RE$

Is it true and can I use similar approach to show that $L\not\in RE$?

Thanks.

Your proof is not very clear to me. In your description of $M'$ I don't understand what $M_1$ and $M_2$ are, or why they have the properties you claim they do.

A typical reduction proof looks like:

You have some language $L$ which you wish to prove is, say, not $RE$.
You have a language $L'$ which you know is not $RE$.
Suppose there exists a TM $D$ which recognizes $L$
Construct a TM $D'$ to recognize $L'$. Usually $D'$ will take some input $x$ and transform it into an input $y$ for $D$, such that $D'$ accepts $x$ if and only if $D$ accepts $y$

So let's do the same thing for this problem. We'll reduce $TOTAL$ (which is neither $RE$ nor $co-RE$) to $L$.

Suppose $D$ recognizes $L$. Let $D'$ be the TM:

TM $D'$ on input $\langle M \rangle$:

Let $M'$ be the TM that acts as $M$ but inverts the output
Run $D$ on $\langle M, M' \rangle$
Accept if $D$ accepts, reject if $D$ rejects.

Now we want to prove that $D'$ recognizes $TOTAL$. This is straightforward. $\langle M, M' \rangle$ is in $L$ if and only if $L(M) \cup L(M') = \Sigma^*$. But $L(M') = \overline{L(M)}$. So $D'$ accepts $M$ if and only if $M$ either accepts or rejects every input, which is precisely what it means for $M$ to be in $TOTAL$!

So we have shown that no TM can recognize $L$, so $L$ isn't $RE$.

To show that it's not $co-RE$ either we take $D$ to recognize $\bar{L}$ instead, and define $D'$ just as above. So now $D'$ accepts $M$ if and only if $\langle M, M' \rangle$ is not in $L$. The same argument above shows us this is exactly true when $M$ is not in $TOTAL$.


Algorithm to find exactly two sets of numbers that have the same sum I am searching for the most efficent implementation of a specific algorithm:

Assume you have a set of positive integers, for example:

X = [1,1,2,3,3,6,8]

The aim is to find exactly two sets (containing together all elements of X), so that the sum of all elements of the one is equal to the sum of the other.

So for example a solution would be (there can be more than one solution of course, or no solution):
A = [1,2,3,6]
B = [1,3,8]

(Sorry if my wording is wrong, just a curious developer and no computer scientist)

This is called the Partition Problem, and it's NP-complete, meaning that it's very unlikely that any algorithm can solve every instance of the problem quickly. On the bright side, if there are $n$ numbers and their total sum is $t$, there is a fairly simple $O(nt)$-time dynamic programming algorithm (see section "Pseudo-polynomial time algorithm" on that webpage), and this is fast enough to solve many practical instances.


Complexity of finding a perfect matching in directed graphs To the best of my knowledge, finding a perfect matching in an undirected graph is NP-hard. But is this also the case for directed and possibly cyclic graphs?

I guess there are two possibilities to define whether two edges are incident to each other, which would also result in two possibilities to define what is allowed in a perfect matching:

Allowed in the perfect matching are only edges that do not share a common start or end point, i.e. antiparallel edges are not allowed in the perfect matching.
Antiparallel edge are allowed in the perfect matching, i.e. selecting edge $v_i\rightarrow v_j$ does not exclude selecting $v_ j\rightarrow v_i$.

What I've read sofar, option 1 is the typical generalization for directed graphs, but is finding a perfect matching NP-hard for both cases?

You can find the maximum matching in all three cases in polynomial time.  It follows that it's possible to check whether there exists a perfect matching and, if so, to find one.

Finding a maximum matching in an undirected graph can be done in polynomial time.  It is not known (or likely) to be NP-hard.  See https://en.wikipedia.org/wiki/Matching_(graph_theory)#Algorithms_and_computational_complexity.

If you define the problem according to option 1, then finding a maximum matching in an undirected graph $G$ is equivalent to finding a perfect matching in the corresponding undirected graph (where you just ignore the edge directions) -- and thus can also be done in polynomial time.

If you use option 2, then the following algorithm can be used to find a maximum matching in polynomial time:

Given a directed graph $G=(V,E)$, construct a weighted undirected graph $G'=(V,E')$ with edge set defined as follows:

If $G$ has an edge $v \to w$ but not its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 1.
If $G$ has an edge $v \to w$ and also its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 2.

Find the maximum-weight matching in $G'$, i.e., the matching whose weight is maximized.
Now turn this into a set of edges in the original directed graph.  If this process selected an edge $(v,w)$ and $G$ contains both $v\to w$ and $w\to v$, add both to the matching in $G$.  If it selected an edge $(v,w)$ and $G$ contains only one of $v \to w$, $w\to v$ but not the other, add the one you can.

This runs in polynomial time and finds the maximum matching in $G$.

A simpler way to check whether $G$ has a perfect matching (i.e., one that covers all the vertices) is to construct the undirected graph $G'$ (you can ignore the weights) and check whether $G'$ has a perfect matching.


Tree with alternating types of nodes Suppose that I have a tree where each node is either of type A or type B.

Nodes of type A have outgoing edges only to nodes of type B and vice versa.

Is there a name/term for this kind of a tree?

A concrete example of such a tree would be the state tree of a 2 player game (like tic-tac-toe) which has alternating levels of states where it's X's turn or Y's turn.

Such a tree would be 2-colored.

Note that all trees are 2-colorable; a 2-colored tree is just one where the coloring's already happened.


Does the language of Regular Expressions need a push down automata to parse it? I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular expresssions?

I assume it must be a push down automaton because the presense of brackets means the need to count and a DFA/NFA cannot perform arbitrary counting. Is this assumption correct? For example, the expression a(bc*)d would require a PDA so that the sub-expression in brackets is handled correctly.

You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques.

One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma on $(^p)^p$.

That said, you probably do not want to code a PDA by hand. Consider using a parser generator like ANTLR or byacc. If, on the other hand, you want to investigate the parsing of languages by programming parsers yourself, you should continue with other basic parsing algorithms such as CYK, Earley, recursive descent and LR.


How to improve the binomial algorithm? Good evening!

I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form:

$$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$$

Then, tried to estimate the number of recursive calls that would be used by the method call binomial1(100, 50, .25)

public class Binomial {

    public static double binomial1(int N, int k, double p) {
        if (N == 0 && k == 0) return 1.0;
        if (N < 0 || k < 0) return 0.0;
        return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        double p = Double.parseDouble(args[2]);
        StdOut.println(binomial1(N, k, p));
        StdOut.println(binomial2(N, k, p));
    }

}

I think I have $2^N$ recursive calls of binomial1, that is to say 10000 calls with our exemple. Because of this line:

return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);

I would like to explain it better... I think my answer is too intuitive: each time I call the algorithm, I call it twice until N reach 0.

How to improve with an implementation that would be based on saving computed values in an array?

The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

For completeness, here are the formula and the recursion:
$$
\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}.
$$

There are many ways to use memoization here. One natural way is to loop on n, and compute all values of binomial1 in sequence. This only requires knowing the values of binomial1 on n-1, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given k.

I'll let you come up with matching code and runtime analysis.


Sensor Cover Problem We are given an interval $I$ and several points $p_1,p_2,...,p_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within the interval can be monitored by the corresponding sensor. The sensors may not have the equal range.

Given the current positions of points and sensors, some (or maybe none) points in $I$ may not be monitored by any sensor. We would like to ask the following question:

  Given a distance $\delta$, is it possible to shift each sensor (to the left or to the right) by a distance at most $\delta$, such that every point in $I$ can be covered by some sensor?

PS: I tried to solve this by greedy algorithm. But there is always an exception to any greedy paradigm I came up with. If we want to cover the whole interval with the sensors, I am sure it can be solved by greedy algorithm. But if we only want to "monitor" finite discrete points, is there an efficient algorithm?

Just observations that do not fit on the comments:

I made a little research, and here are what I found + some of my observations:
1) You can use exhaustive search to find whether a solution exist. [so it is decidable]
2) In case $\delta$ is not restricted, all you need to check is the sum of all ranges and compare it to the distance between the farthest two points. If greater or equal, then there exist a solution.
3) In case $\delta$ is restricted, then you are trying to restrict the distance traveled by sensors to at most $n \delta$. In case the sensing ranges are not equal, then this problem is still open [1].

I would suggest you look in the same reference for a solution for the case of equal sensing ranges. So I think a greedy solution exist.

[1] On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment. J. Czyzowicz , E. Kranakis , D. Krizanc , I. Lambadaris , L. Narayanan , J. Opatrny , L. Stacho , J. Urrutia, and M. Yazdani.


How to prove that a bounded pushdown automaton is regular? I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain how we can prove it ?

Thank you in advance!

If the stack has bounded height then there are only finitely many possibilities for its contents. Therefore a regular automaton can “remember” the entire contents of the stack. In other words, you can convert the PDA into an equivalent regular automaton in which each state stores both the state of the PDA and the contents of its stack.


Inductive vs. recursive definition When should I call a definition recursive and when should I call it inductive?

I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like natural numbers, lists, trees, etc. as inductive whereas we refer to definitions of operations over objects like $+$ or $head$ or $leftchild$ as recursive.

Is this the correct way to distinguish these in programming languages theory?

Are there examples where using either would make sense?

An inductive definition takes some elementary objects of the structure to be defined and combines those to obtain new elements of said structure.

Example: Definition of the syntax of many logics.

On the contrary, a recursive definition is a rule how to obtain a specific object based on somehow "smaller" objects of the same structure.

To see the difference more clearly, consider the following:
To define the valid arithmetical expressions, you would state something like

Any real number is a valid arithmetical expression
When $\varphi$ and $\psi$ are valid arithmetical expressions, so are $(\varphi + \psi)$, $(\varphi - \psi)$, etc.

This is an inductive definition of arithmetic expressions, as you build up the class of valid expressions from the bottom (base cases) upwards.
Recursion, on the other hand, works from the top to the bottom. In this case, you would recursively check whether an arbitrary string is a valid expression or not.

When you define an object recursively, the object is determined by easier to compose objects of the same structure, like the Fibonacci numbers. You can only get the value of $\text{Fib}(n)$ by knowing $\text{Fib}(n-1)$ and $\text{Fib}(n-2)$.


Is this variant of set cover NP-complete? Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\{S_1,\ldots,S_m\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ or less", then this is NP-complete.

Now suppose that I add the following:

$|S_1| \gt |S_2| \gt \ldots \gt |S_m|$.

Is this still NP-complete?

I guess that, given 1., we know that the sets $S_i$ are all distinct and then the only cover for $U$ is $S$ but I am not sure about this.

As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S_1$. Then add subsets of $S_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S_1$, and otherwise it just has to be a solution to the original problem.

This is of course not a formal reduction - this is left to the reader.


Find the minimum range Given a list of numbers as L, how do you find the minimum value m such that L can be made into a strictly ascending list by adding or subtracting values from [0,m] from each element of L except the last? (Strictly ascending means the new list can't have any duplicates.)

Example #1:

for L = [5, 4, 3, 2, 8] the minimum value for `m` is 3.
5 - 3 = 2 # subtract by 3
4 - 1 = 3 # subtract by 1
3 + 1 = 4 # add by 1
2 + 3 = 5 # add by 3
8 untouched # nothing

result = [2, 3, 4, 5, 8]

Example #2:

for L = [5, 4, 3, 0, 8], minimum value for `m` is 4

NOTE: I'm not looking for a complete solution just give me few thoughts and clue.

Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. Please check it.

Problem Definition:

The algorithm $\mathcal{A}$ of @norbertpy is for a variant of the original problem:

  To find the minimum positive number $2m$ such that for each item in the array, adding a number from $[0, 2m]$ can lead to a strictly ascending array?

The solutions to these two problems can be reduced to each other (by $\pm m$).
Note that I have ignored the "except the last" part.

A lemma for the property of the algorithm $\mathcal{A}$:

Let $L'[n]$ be the last element of the resulting strictly ascending list of any feasible solution to $L[1 \ldots n]$. We first claim that:

  Lemma: $\mathcal{A}$ gives the smallest value of $L'[n]$ among all the feasible solutions to $L[1 \ldots n]$.

This lemma can be proved by mathematical induction on the length $n$ of $L$.

Now we prove that $\mathcal{A}$ always gives the optimal solution.

Base case: $n = 1$ and $n = 2$ are trivial.

Inductive Hypothesis: Suppose that for any $L[1 \cdots n-1]$ of length $n-1$, the algorithm $\mathcal{A}$ gives us the optimal solution $m$.

Inductive Step: Consider the $n$-th iteration of the greedy algorithm $\mathcal{A}$: it compare a = head + 1 - L[n] with $m$, and take $M = \max(m,a)$ as the feasible solution to $L[1 \cdots n]$.

We aim to prove that

  $M$ is the optimal solution to $L[1 \cdots n]$.

Suppose, by contradiction, that there is another feasible solution to $L[1 \cdots n]$, denoted by $M' < M$.

First, $m < M'$: otherwise, $M'$ is a smaller feasible solution to $L[1 \cdots n-1]$, which contradicts the assumption.

Thus we have $m < M' < M$. Because $M = \max(m,a)$, we obtain $m < M' < M = a$.

By the lemma above, $L'[n-1]$ in the solution corresponding to $M'$ is not less than that in the solution corresponding to $m$. However, $L'[n]$ (for $M'$) is less than that for $M$ (because $M' < a$). According to the way how $a$ is chosen in $\mathcal{A}$, the resulting array (for $M'$) is not strictly ascending. Thus $M'$ cannot be a solution. Contradication.


Which combinations of pre-, post- and in-order sequentialisation are unique? We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

First, I'll assume that all elements are distinct. No amount of sequentialisations is going to tell you the shape of a tree with elements [3,3,3,3,3]. It is possible to reconstruct some trees with duplicate elements, of course; I don't know what nice sufficient conditions exist.

Continuing on the negative results, you can't fully rebuild a binary tree from its pre-order and post-order sequentializations alone. [1,2] preorder, [2,1] post-order has to have 1 at the root, but 2 can be either the left child or the right child. If you don't care about this ambiguity, you can reconstruct the tree with the following algorithm:

Let $[x_1,\dots,x_n]$ be the pre-order traversal and $[y_n,\ldots,y_1]$ be the post-order traversal. We must have $x_1=y_1$, and this is the root of the tree.
$x_2$ is the leftmost child of the root, and $y_2$ is the rightmost child. If $x_2 = y_2$, the root node is unary; recurse over $[x_2,\ldots,x_n]$ and $[y_n,\ldots,y_2]$ to build the single subtree.
Otherwise, let $i$ and $j$ be the indices such that $x_2 = y_i$ and $y_2 = x_j$. $[x_2,\ldots,x_{j-1}]$ is the pre-order traversal of the left subtree, $[x_j,\ldots,x_n]$ that of the right subtree, and similarly for the post-order traversals. The left subtree has $j-2=n-i+1$ elements, and the right subtree has $i-2=n-j+1$ elements. Recurse once for each subtree.
By the way, this method generalizes to trees with arbitrary branching. With arbitrary branching, find out the extent of the left subtree and cut off its $j-2$ elements from both lists, then repeat to cut off the second subtree from the left, and so on.

As stated, the running time is $O(n^2)$ with $\Theta(n^2)$ worst case (in the case with two children, we search each list lineraly). You can turn that into $O(n\,\mathrm{lg}(n))$ if you preprocess the lists to build an $n\,\mathrm{lg}(n)$ finite map structure from element values to positions in the input lists. Also use an array or finite map to go from indices to values; stick to global indices, so that recursive calls will receive the whole maps and take a range as argument to know what to act on.

With the pre-order traversal $[x_1,\ldots,x_n]$ and the in-order traversal $[z_1,\ldots,z_n]$, you can rebuild the tree as follows:

The root is the head of the pre-order traversal $x_1$.
Let $k$ be the index such that $z_k = x_1$. Then $[z_1,\ldots,z_{k-1}]$ is the in-order traversal of the left child and $[z_{k+1},\ldots,z_n]$ is the in-order traversal of the right child. Going by the number of elements, $[x_2,\ldots,x_k]$ is the pre-order traversal of the left child and $[x_{k+1},\ldots,x_n]$ that of the right child. Recurse to build the left and right subtrees.

Again, this algorithm is $O(n^2)$ as stated, and can be performed in $O(n\,\mathrm{lg}(n))$ if the list is preprocessed into a finite map from values to positions.

Post-order plus in-order is of course symmetric.


maximum matching number decreases when vertices collapse? It seems that the maximum matching number decreases when some independent (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true.
Would maximum matching number increases when two vertices are connected to form a new edge?

Any proof? Thanks!

Definitions:
Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

A maximum matching (also known as maximum-cardinality matching1) is a matching that contains the largest possible number of edges.

Try to find a proof that it can't happen! Keep trying.  Hint:

   Suppose you have a maximum matching for the collapsed graph.  Can you use that to find a matching for the original graph?  How many edges does it have?  What does that imply about your question?

If you're really stuck, try to write a program to enumerate all graphs with at most 6 vertices (say) and see if the matching number can ever increase after collapsing an edge.  That should enable you to form a reasonable conjecture, which you can then try to prove, or should give you a counterexample.


What to consider while proving NP-completeness? Suppose that a problem $P$ is known to be NP-hard.
The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m < n$ pairwise distances among the points.
The goal is to place each point on one of $k$ lines, satisfying the given pairwise distances.
Disclaimer This problem might not be an NP-hard problem, but for the sake of simplicity, suppose that it is.

Since the problem is assumed to be NP-hard, having a polynomial time solution checking algorithm is sufficient to show NP-completeness.

At first sight, it seems trivial
Step 1: check whether the pairwise distances are satisfied [takes $O(m)$ time].
Step 2: check for each point whether the point is on a given line. [takes $O(n*k)$ time].

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?

The length of the solution/certificate must be polynomial in the size of the original instance. Therefore, if the certificate/solution can be exponential in the size of the input (due to the numbers needing exponential representation) then you do not have a valid proof of membership in $NP$. The problem might be $\exists \mathbb{R}$-hard.


Multi-prompt delimited continuations in terms of single-prompt delimited continuations Let's call the two languages in question (untyped lambda calculus with single or multiple prompt delimited continuations) L_delim and L_prompt.

  Is it possible to express multi-prompt delimited continuations in terms of single-prompt delimited continuations

By express I mean the macro-expressible sense (to provide some kind of translation that doesn't involve interpreter overhead), of course it's possible to write an interpreter for multi-prompt delimited continuations even in pure lambda calculus.

I expected a negative result for this, that it's not possible but I don't know how that would be shown. Thanks for any input on this.

So, it turns out, the paper describing the construction I mentioned in the comments answers in the affirmative:

  Our technique of removing a dynamic prompt is rather general and thus can be used for the design of many other delimited control operators, which permit capturing the continuation up to an arbitrary (not necessarily the closest one) enclosing delimiter.  It becomes entirely up to the user which delimiters to skip and how the captured frames are to be composed or used separately.

If you look at their method, it seems like the idea would be to tag the H and HV values with tokens that specify the different prompts involved, and have the h and h' functions compare those tokens to decide what to do. This isn't terribly surprising, because the multi-prompt implementation I'm familiar with uses (representations of) stacks with frames tagged with the prompt, and their technique uses 'static' shift/reset (and macros) to hide explicit manipulation of the stack implementation of e.g. control/prompt, more or less.


How to find the minimal description for an array? The following array occupies 10000 slots in memory:

a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]

But one could easily represent the same array as:

a = {len:10000, get: λ idx -> idx}

Which is much more compact. Similarly, there are several arrays that can be represented compactly:

a = {a:1000, get: λ idx -> idx * 2}
Is a description for [0,2,4,6,8,10,...,2000]

a = {a:1000, get λ idx -> idx ^ 2}
Is a description for [0,1,2,4,9,...1000000]

And so on...

Providing so many arrays can be represented in much shorter ways than storing each element on memory, I ask:

Is there a name for this phenomena?
Is there a way to find the minimal representation for a specific array?
Considering this probably depends on the language of description (in this case, I used an imaginary programming language with functions, objects and math operators). Is there a specific language that is optimal for finding that kind of minimal description for objects?

The phenomenon you're describing is Kolmogorov complexity.  Essentially, if you fix a programming language (or, more formally, a coding of Turing machines) then the Kolmogorov complexity $K(s)$ of a string $s$ is the length of the shortest program that outputs $s$ when started with no input. It turns out that, within reason, it doesn't matter what programming language you use, since using a different language makes at most a constant additive difference to $K(s)$. If you want to define Kolmogorov complexity with respect to some whacko language, I can just use that language to write an interpreter for a sensible language, so the Kolmogorov complexity of a string with respect to your language cannot be worse than the complexity in my language plus the fixed, constant overhead of the interpreter.

Like all interesting properties of Turing machines, the Kolmogorov complexity of a string is undecidable. However, this doesn't stop it being a useful concept and there's been a large amount of research on the subject.


Sub-linear-time ordered set (!= sorted set) implementation? Does there exist any data structure that efficiently (linearithmic-or-similar in-order traversal, sublinear time insertion/search/removal) implements an ordered set (i.e. a set that allows for enumerating the items in insertion order)?

If so, what data structure is it/how does it do this?

Another pretty simple solution is a balanced binary search tree with threading (an overlaid linked list passing through all the nodes of the tree in order of their original insertion). Then insertion/search/removal are all O(log n), and iteration is O(n). You just update insert/remove to either append to the linked list or remove the node from it.


Output of well-known algorithms for the Subset sum problem According to Wikipedia:

  In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.

What is the output of the known algorithms which resolve exactly the subset sum problem?

For example:

The algorithm which take $O(2^N*N)$ time.
The algorithme which take $O(2^{N/2})$ time.

Is it just Yes / No or do they also give the extraction of solution?

Example:

$A = \{1, 3, 4, 5\}$

$k = 8$ (The search item)

Output : YES
Output : {1,3,4}, {5,3} (where 1+3+4=8 and 5+3=8)

The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that when an algorithm answers YES, it can also naturally give you a certificate that proves it. Moreover, when this happens, you typically get a one valid solution. (This was just a clarification because your example outputs 2 valid solutions. Listing all solutions is a different thing).

Both algorithms you mention explicitly step through certain subsets, and so it is easy for them to also output the subset whose elements sum up to $t$. Whether you care about that extra information is up to you then.


Decidability of checking an antiderivative? Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether

$$F(x) = \int G(x)dx.$$

Let's suppose that my functions are composed of elementary functions (polynomials, exponentials, logs, and trigonometric functions), but not, say, Taylor series.

Is this problem decidable? If not, it is it semidecidable?

(I'm asking because I'm teaching a class on computability and a student asked me if a TM could help you integrate a function whose integral was not currently known. I suspect that the functions we don't know how to integrate are more properly functions whose integral can't be expressed as a combination of the above elementary functions rather than functions for which we don't actually know the integral, but that got me thinking about whether the general problem of checking integrals was decidable.)

The short answer to your question is "no". Richardson's theorem and its later extensions basically state that as soon as you include the elementary trigonometric functions, the problem of deciding if $f(x) = 0$ (and hence if $f(x) = g(x)$, since this is the same as $f(x) - g(x) = 0$) is unsolvable.

What's interesting about this is that the first-order theory of real closed fields is decidable. Intuitively, the reason why adding trigonometric functions makes the first-order system undecidable is because you can construct the integers via $\{ x \in R : \sin(\pi x) = 0 \}$, and the theory of the integers is undecidable.

Whether or not the theory of real closed fields with $e^x$ is decidable is a fairly famous open problem.

Even more interesting that this is that if you had an oracle which "solved" the constant problem (i.e. an oracle which can tell you if $f(x) = 0$ or not), then integration of elementary functions in finite terms is decidable, and a practical algorithm is known. So given $G(x)$, we could find $F(x)$ or know that there is no elementary integral of $G$ in finite terms.


Regular language concatenation with superset Let $A$ be some alphabet.

$A$ itself is a regular language.

$E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible string from symbols of $A$.

Now let $L$ be some regular language over $A$.

What is $\tilde{L} = L \cdot E$ ? More specifically, how $\tilde{L}$ and $E$ relate to each other? Are they equal? Is one subset of the other? Something else?

Source of the confusion is the following reasoning: closure under concatenation says that $\tilde{L}$ is a regular language and therefore $\tilde{L} \subseteq E$  (according to the above). On the other hand $\tilde{L}$ seems to contain strings $E$ does not, i.e. those that are formed by concatenating non-empty string from both languages.

Obviously this is wrong. What is going on here?

Simply put, this statement of yours:

  On the other hand $\tilde{L}$ seems to contain strings E does not, i.e. those
  that are formed by concatenating non-empty string from both languages.

is wrong.

As you say, $E$ contains every string containing only symbols from $A$. Since $L$ also only contains strings with symbols from $A$, $\tilde{L}$ must as well. Concatenating strings that have symbols only from $A$ will just get you another string whose symbols only come from $A$.

Your statement is flipped; it is $E$ that contains strings that $\tilde{L}$ may not.


a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph Suppose I have a set of small subgraphs $A=\{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i| \ll |G|$, which together span the original graph

$$
G= \bigcup_i G_i
$$
My question is if I take a arbitrary subset of these graphs $A′ \subset A$, and a single subgraph from this graph, $ a \in A′$, is there a simple way (or known algorithm) of reassembling the subgraph $G′ \subset G$ given by that portion of the union of $A′$ connected to $a$?

In words, this is rather like a jigsaw problem where $A$ is the total collection of pieces that originally came in the box, $A′$ is the subset left after half of them got lost and $a \in A′$ the random selected piece you put down the start the puzzle off. The question is then what is the largest connected graph (connected subset of pieces $x \in A'$) that you can lay down all on the board.

The actual application arises where each subgraph $G_i$ of A represents a rule and (e.g. $x \wedge y \Rightarrow z$) and the objective is to find the largest rule implied transitively from an initial seed rule $a \in A′$ and the remaining rules contained in thinned out subset $A′ \subset A$.

I suspect I maybe able to do something by brute force here but would be most interested in knowing if there is any area or known application of this problem elsewhere.
 I think similar things are possible in declarative language such as Prolog but I suspect that Prolog can actually do any more. Any good up-to-date reference on declarative programming languages would also be very useful.

I originally posted a version of this question on the Computational Science site but was advised that this forum could be better.

One unclear point about the question is the meaning of "connected". If we interpret it as weakly connected, then the orientation of the DAG is no longer important, and we could have worked with an undirected graphs in the first place. We should also not interpret it as strongly connected, since a DAG has no strongly connected subsets.

So we are probably interested in the subgraph reachable from a node in $a$. I looks like we can just work with the set of edges contained the graphs from $A'$. But then we end up with a problem which belongs to both 2-SAT and HORNSAT, and the unit-propagation algorithm for HORNSAT will solve it in linear time. As the problems also belongs to 2-SAT, we know that it is not P-complete.


Finding a subset in bipartite graph violating Hall's condition We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are conected to some of the vertices from $U$. If for every choice of $U$ we have $|U| \leq |V|$ (Hall's condition) then there exists a perfect matching (Hall's theorem).

But in our graph we know there is no such matching. That means there exists some set of vertices $U$ violating Hall's condition, and I'd like to find it with complexity around $O(n^3)$ - hints instead of full solutions are most welcome.

What I already tried was finding the maximum matching first, and then searching for our subset, but I couldn't figure out how to do this. Also, I thought of ways of reducing this problem to some max-flow (as you do with the maximum matching) but it also seemed to me like a dead end.

Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices reachable from $U$ in $G'$. Then $|N(S \cap X)| = |S \cap X| - (n-|M|)$.

For the proof, let us first notice that $|N(S \cap X)| \geq |S \cap X| - (n-|M|)$, since otherwise each matching would have to miss more than $n-|M|$ vertices of $S \cap X$. It remains to show that $|N(S \cap X)| \leq |S \cap X| - (n-|M|)$. The idea is to show that $|X \setminus S| + |S \cap Y| \leq |M|$. Given this, note that by definition $N(S \cap X) = S \cap Y$, and so
$$ |N(S \cap X)| = |S \cap Y| \leq |M| - |X \setminus S| = |M| - (n-|S \cap X|) = |S \cap X| - (n-|M|). $$

To finish the proof, we show that $|X \setminus S| + |S \cap Y| \leq |M|$. We do this by showing that each vertex in both of these sets belongs to $M$. For each $(x,y) \in M$, if $y \in S$ then $x \in S$, showing that at most one vertex is counted in $|X \setminus S| + |S \cap Y|$ for each edge in the matching, proving the inequality. It is clear that each vertex in $X \setminus S$ belongs to $M$, since by definition unmatched vertices belong to $S$. The crux of the proof is showing that each vertex in $S \cap Y$ belongs to $M$. Indeed, if some $y \in S \cap Y$ didn't belong to $M$, then the path proving that $y \in S$ is an augmenting path for the matching: if we remove all edges going from $Y$ to $X$ on the path and replace them by all edges going from $X$ to $Y$ on the path then we obtain a matching with one more edge than before. Since we assumed that $M$ is a maximum matching, this is impossible, completing the proof.


Issue understanding the reduction of SAT to 3-SAT in poly time Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way,

Suppose $C_1$ is $\{x_1, x_2, x_3, x_4\}$. It's equivalent representation in 3-literal clauses is,

$C_{3-SAT} = \{\{x_1, x_2, y_1\},\{\bar{y_1}, x_3,x_4\}\}$

The issue lies here. Assume for $C_1$, all the literals are $False$ except for $x_2$.
For $C_{3-SAT}$, the first clause would indeed be $True$, but the boolean value for the second clause depends on the choice of $y_1$. What if we chose $y_1 = True$? then, $C_{3-SAT}$ will be $False$, yet $C_1$ is $True$, realizing a false reduction.

The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses."

All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least one assignment to the variables $y_i$ that makes the new formula true and it doesn't matter that there are also choices for the $y_i$ that make it false. Conversely, if the original formula was unsatisfiable, no choice of the $y_i$ will make the new formula true.

Formally, there doesn't even have to be any relationship between the values of the variables in the two assignments. In theory, you could map all satisfiable formulas to "$x$" and all unsatisfiable formulas to "$x\wedge \neg x$".  (But we don't know of an efficient way to do that.)


Memory Hierarchy and storing data in caches Question: How many 32 bit integers can be stored in a 16 bit cache line.
Answer: 4

can somebody please explain for me why the answer is 4 i did not understand the reason and i think they should give us more given like the number of blocks in the cache..

There's probably a typo there: it's not 16 bits but rather 16 bytes. Each 32 bit integer takes 4 bytes, so 16/4 = 4.


Are there automatic transformation of grammar algorithms? From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, despite the fact that the rewritten grammar is obviously equivalent and accepts exactly the same language.

Are there some automatic transformations of the grammar to avoid conflict? Something (just an analogy) as left recursion elimination in LL parsers?

For example, here is a trivial example of two grammars:

...
deco_symbol -> anon_symbol | named_symbol;
...

and

...
symbol -> anon_symbol | named_symbol;
deco_symbol -> symbol;
...

For LR(1) parser such indirection can be crucial and second form can introduce conflicts (it did in real life).

Since I asked this question I wrote automatic removal of identity production and it helped, so this would be the first type of transformation I know it is helpful. Now I am testing wrapper production removal and empty productions as well.

If you are willing to implement an lr(k) algorithm then yes, there are transformations that you should do in order to obtain a correct parser:
first of all, you have to build an augmented grammar adding production S'->S, making S' the new axiom. This is actually not always necessary, but it allows you have a standardized procedure for all the productions so let's pretend it is for now. After that, you should also eliminate useless symbols from the grammar with the apposite algorithm.

If you execute lr(k) parsing under these hypothesis for the grammar, you should not have conflicts.

----- EDIT ----- I hope this will be of some help :)

An lr(k) parser builds a parsing table over a given grammar G. These parsers are able to recognize words generated from grammars which are deterministic context free and in lr(k) form. If a conflict occurs, then the language generated by the given grammar cannot be parsed using that table and the grammar is not a lr(k) grammar.

However, one can show that a language L is deterministic context free iff there exists k >= 1 such that L is generated by an lr(k) grammar.

I might be wrong but what I concluded from these notions is that if the grammar is lr(k) no conflicts should occur, and one of the definitions of a lr(k) grammar is:

The definition of lr(k) grammars states that the axiom must not occurr on the right hand side of any production, and should this is not be respected one needs contruct the augmented grammar first, using S' as new axiom and adding the only production S'->S. For further definitions of lr(k) grammars or a clarification of what I wrote, I advise to read The Theory of Parsing, Translation and Compiling (around page 370), since I fear I don't have the preparation to answer all questions.


Human computing power: Can humans decide the halting problem on Turing Machines? We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines or general purpose computers?

Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.

So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?

Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?

It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.

You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.

After taking propositional and then predicate calculus  I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."

There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.

Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines
http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments


Are linear languages always unambiguous? Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?

The linear language $\{ a^ib^jc^k \mid i=j \text{ or } j=k\}$ is inherently ambiguous.


Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding? With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is the same as Huffman coding. However, I'm not sure how to prove that arithmetic coding with this restriction is optimal for integer code lengths.

You can't prove it because it's not true.

Arithmetic coding "degrades" to Huffman coding if all of the probabilities are of the form $2^{-k}$. Or, to put it another way, when the Kraft-McMillan inequality is an equality.


Solve longest common subsequence in a non dynamic programming way? I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I understand.

public class LCS
{
    public static String lcs(String a, String b )
    {
    String lcs = lcs(a, b, "", 0, 0);
    return lcs;
    }
    private static String lcs(String a, String b, String lcs, int i , int j)
    {
    int length_a = a.length();
    int length_b = b.length();
    if (i == length_a || j == length_b) return lcs;
    if (a.charAt(i) == b.charAt(j))
        {
        lcs += a.charAt(i);
        i++;
        j++;
        }
    else
        {
        String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
        String lcs_j_plus = lcs(a, b , lcs ,i, j+1);
        if  ( lcs_i_plus.length() > lcs_j_plus.length())
            i++;
        else
            j++;
        }
    return lcs(a, b, lcs , i, j) ;
    }
    public static void main(String[] args)
    {
    //client
    String a = "GGCACCACG";
    String b = "ACGGCGGATACG";
    String lcs = lcs(a, b);
    StdOut.println(lcs);
    }
}

In contrast, the book I studied offered another solution which was claimed to solve the LCS problem via dynamic programming. The code looks as follows.

 public class LongestCommonSubsequence
 {
    public static String lcs(String s, String t)
    {  // Compute length of LCS for all subproblems.
    int m = s.length(), n = t.length();
    int[][] opt = new int[m+1][n+1];
    for (int i = m-1; i >= 0; i--)
       for (int j = n-1; j >= 0; j--)
       if (s.charAt(i) == t.charAt(j))
          opt[i][j] = opt[i+1][j+1] + 1;
       else
          opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
    // Recover LCS itself.
    String lcs = "";
    int i = 0, j = 0;
    while(i < m && j < n)
    {
       if (s.charAt(i) == t.charAt(j))
       {
          lcs += s.charAt(i);
          i++;
          j++;
       }
       else if (opt[i+1][j] >= opt[i][j+1]) i++;
       else                                 j++;
    }
       return lcs;
    }
    public static void main(String[] args)
    {  StdOut.println(lcs(args[0], args[1]));  }
}

I have tested both implementations and they produced the same results. My questions are:

1.Is my approach correct?

2.If my approach is correct, what are the time complexity of these two approaches?

Your approach is correct in the sense that you produce the correct results.

The book's approach has a time complexity of $O(mn)$. Since your solution doesn't use memoization and recomputes the same results repeatedly, the time complexity is much worse. In fact, your approach is functionally equivalent to the brute force method, which has a time complexity of $O(2^n)$.

Note that with

String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);

You recompute a subset of the problem on every single iteration without saving any of the results. The purpose of memoization is to save the results of the sub problems (so you don't have to recompute them) and then use those results to construct a solution to your original problem.


What will be big O complexity for this loop? I am not able to understand time complexity of this for loop.
While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?

public void function(n) {
                    for(int i = 1; i< n; i++) {
                        for(int j =     1; j <= n;  j += i) {
                                System.out.println("*")
                        }
                    }
                }

The inner loopnever stopped for $n \geq 1$ as for the first time i = 0 and j += i never increased the value of j. If we suppose i will be started from 1, for i = 1 the inner loop will be iterated $n$ times. for i = 2 as value of j is increased by step size 2, the number of iterations of the inner loop is $\frac{n}{2}$. Hence, the computation cost of the program is $\sum_{i = 1}^{n-1}\frac{n}{i} = n \sum_{i = 1}^{n-1}\frac{1}{i} = \Theta(n\log(n))$.


Counterexample to big-O claim looks wrong Let $T_1(n) = O(f(n))$ and $T_2(n) = O(f(n))$.
Then $T_1(n) / T_2(n) = O(1)$ is a false statement. A counterexample is $T_1(n) = n^2$, $T_2(n) = n$, and $f(n) = n^2$.

I don't get this counterexample, if $T_2(n) = n$, then $T_2$ is $O(n)$ and not $O(n^2)$. (As indicated by $T_2 = O(f(n))$ and $f(n) = n^2)$. Therefore, this doesn't look like a valid counterexample to me. Am I wrong?

The counterexample is fine. Any function that is $O(n)$ is also $O(n^2)$ – if a function's "smaller than" $n$, it's also "smaller than" $n^2$.

And note that even weaker statements are false.  In fact, there is no function $g$ such that $T_1,T_2=O(f)$ implies that $T_1(n)/T_2(n)=O(g(n))$.  For example, take $T_1(n)=1$ and $T_2(n)=1/g(n)^2$. So, now, $T_1(n)/T_2(n) = g(n)^2\neq O(g(n))$.


Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular) Gradient descent sometimes works better than simulated annealing and vice versa.

Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one of these is optimal for solving an optimization problem?

I am particularly interested in those two examples, but in general interested in this question for metaheuristics for search and optimization problems.

(The no free lunch theorems show that (for certain problem statements) this is not possible in general, since for a uniform diatribution on problems, there usually isnt an optimal algorithm. However it might hold for special cases.)

In general, we definitely don't know this. In fact, it's practically always so that a-priori, we don't know how well a particular metaheuristic performs (let alone proving optimality) on a given instance (or family of instances) until we try.

It should also be noted that we usually go for metaheuristics only when the problem is so hard it seems unlikely it admits an algorithm that is always fast and correct (i.e., the problem is NP-hard). Put differently, when a problem is solvable in polynomial-time with some other methods, we don't even bother considering metaheuristics.

So if a metaheuristic is always optimal (and assuming it always runs in polynomial time), then the problem must be in P (assuming that P is not equal to NP). Of course, no one is stopping you from taking a problem that is known to be in P and applying a metaheuristic on that, but that's probably not that useful anymore.


If graph isomorphism yields a polynomial time algorihtm Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes.

If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible implication it has or what can we possibly deduce?

Thanks for any explanation

Nothing bad is known to happen if Graph Isomorphism can be solved in polynomial time; see this question on cstheory. On the other hand, problems in the complexity class GI will all have polynomial time algorithms.


Seeking nontrivial small SAT/UNSAT instances I need SAT instances, involving 9 to 20 variables. They need to be hard to solve for humans. Both SAT and UNSAT instances are needed.

I tried random-SAT generators on the web, but the results were not satisfactory because they are trivial. A good example of what I'm looking for is the following 4-variable instance from The Art of Computer Programming: $$12\bar3, 23\bar4, 134, \bar124, \bar1\bar23, \bar2\bar34, \bar1\bar3\bar4, 1\bar2\bar4.$$

To build a satisfiable instance, start by picking an assignment to the variables that will be a solution.  Then, randomly generate clauses that are satisfied by this assignment.  Add as many clauses as desired.  If you add enough clauses, then with high probability your chosen solution will be the only one, and the problem will be non-trivial.

For instance, suppose your assignment is $x_1=\text{True}$, $x_2=\text{False}$.  Then you could add any subset of the clauses $x_1 \lor x_2$, $x_1 \lor \neg x_2$, or $\neg x_1 \lor \neg x_2$.  For example, one random formula you could generate might be $(x_1 \lor x_2) \land (\neg x_1 \lor \neg x_2)$.

To build an unsatisfiable instance, proceed as above; then add one more clause that is violated by the solution you chose in advance.  If you added enough clauses, it is likely that there will be no other solution, so the problem will be unsatisfiable.  Check with a SAT solver just to be sure.


Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties Given a language $L$ over $\Sigma=\{a,b\}$ let us define
$L'=\{uv : u \in L  \; \land v \in L^R \; \land |u|=|v|\}$

Prove: if $L$ is regular, then $L'$ is a context free language.

I know how to solve it by building a push down automaton and proving it acceps $L'$, but I'm trying to solve it by using closure properties of context free languages (e.g closure under homomorphism, intersection with a regular languae, etc.) but I couldn't think of such solution. Any ideas?

Let $\tilde\Sigma = \{\tilde a,\tilde b\}$. It is well-known that the language $X = \{a^n b^n : n \geq 0\}$ is context-free. Let $h \colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $h(a) = h(b) = a$ and $h(\tilde a) = h(\tilde b) = b$. The following language is context-free:
$$ h^{-1}(X) = \{uv : u \in \Sigma^*, v \in \tilde\Sigma^*, |u| = |v| \}. $$
Let $t\colon \Sigma \to \tilde\Sigma$ be the homomorphism defined by $t(a) = \tilde a$, $t(b) = \tilde b$. The following language is regular:
$$
Lt(L)^R = \{ uv : u \in L, v \in t(L)^R \}.
$$
Since the context-free languages are closed under regular intersection, it follows that the following language is context-free:
$$
h^{-1}(X) \cap Lt(L)^R = \{ uv : u \in L, v \in t(L)^R, |u| = |v| \}.
$$
Finally, let $s\colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $s(a) = s(\tilde a) = a$, $s(b) = s(\tilde b) = b$. The following language is context-free:
$$
s(h^{-1}(X) \cap Lt(L)^R) = \{ uv : u \in L, v \in L^R, |u| = |v| \}.
$$
This is the language you're interested in.


Not sure if my solution to following recurrence is correct I have a recurrence relation, it is like the following:

$T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm.

To solve this and find a $\Theta$ bound, I tried the following: I put $k=e^n$, and the equation transforms into:

$$T(k)=2T(k/e)+k$$

Then, I try to use the Master Theorem. According to Master Theorem, $a=2$, $b=e\gt 2$ and $f(k)=k$. So, we have the case where $f(k)=\Omega(n^{\log_b a+ε})$ for some $ε\gt 0$, thus we have $T(k)=\Theta(f(k))=\Theta(k)$. Then put $k=n$, we have $T(n)=\Theta(n)$. Does my solution have any mistakes?

$c=1\gt \ln 2\approx0.7$. That's case 3 of the master theorem. It follows that:

$$T(n)=\Theta(n)$$

Your solution is fine.


LET REC recursive expression static typing rule I'm taking a programming languages course and had a question regarding the typing rules for a recursive let rec expression in a static typing system.

To be more specific, we're using the textbook Essentials of Programming Languages (3e) - Friedman & Wand.

To give some rough background, here's how the author describes the typing rule for a normal let binding expression:

To briefly describe it for anybody unfamiliar with the notation, type-of is a function used to evaluate the type of the given expression.

According to the typing rule, we evaluate exp1 first, which would give us type $t_1$. Then we extend our current environment so $var$ is mapped to $t_1$. Using this new environment, we evaluate the $body$ of the expression which gives us our final type.

Here's a typical let binding example in the OCaml programming language:

let func (x) = x + 1 in (func 3);; (* Outputs -: int=4 *)

let func = fun (x -> x + 1) in (func 3);;
(* Equivalent but better aligned with given typing rule. *)

Here's how a let-rec recursive binding's typing rule is defined:

The main problem that I'm having is how to understand the order of evaluation. According to the typing rule, it seems as though we're extending the environment first with $var$ and $p$, but where are we getting the types to map them to from?

It seems you discovered the difference between a set of typing rules and an algorithm for type inference.

Typing rules only define a relation among 1) a type environment, 2) a term, and 3) a type. Their purpose is only to precisely define a mathematical relation $\Gamma \vdash t: \tau$.

Once we have such definition, we do not automatically get a type checking algorithm. That is, in general, there is no algorithm described by the rules which, given $\Gamma,t,\tau$, is able to test whether $\Gamma \vdash t: \tau$ holds. (In some cases, such an algorithm could even fail to exist!)

Similarly, we do not automatically obtain a type inference algorithm, which given $\Gamma,t$ is able to find a related $\tau$ (when it exists).

The type checking/type inference algorithm must be devised independently.

Now, it is true that in many cases the algorithms can follow the rules quite closely. The rule for non-recursive LET you mention is one nice example, since it is clear how to turn it into an algorithm. For recursive LETs, we are not that lucky.

A typical strategy to type check/infer recursive LETs is to introduce a fresh type variable in the environment, and then perform type checking on the body while generating a set of constraints. For instance, consider this example

let-rec f (x: int) = 1 + f(x) in f(0)

We discover immediately that f : int -> ???. Let's introduce a fresh type variable R for the result, and say f : int -> R.

We then type check 1 + f(x) assuming the environment f: int -> R , x: int.
Here + is applied to arguments 1: int and f(x): R. Assuming + requires its arguments to be of the same type, this forces the constraint int = R.
If + also returns the same type, we obtain another constraint int = R (redundant, in this case).

Finally, we solve the constraints, discovering R = int.

Note that in the general case we might be less lucky, since more complex types could be involved.

let-rec f(x: int) = (2, fst(f(x-1)))

Here, we discover f: int -> R, then we see that R must be a pair type R = A*B, then A=int (because of the 2). Moreover, we get f(x-1):R so fst(f(x-1)): A, hence B=A. We conclude f: int->(int*int).

It is not trivial to generate these constraints, or to solve them (usually through a unification algorithm). In the scientific literature we can find several algorithms which perform this, but they are not obvious at first.


Quickly obtaining sums of sets of numbers We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$.  We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For example:

$$s_k = a_3 + a_5 + a_{17} + a_{22} + a_{35}$$

There is more structure to the sums, however.  The sums are split into $m / \alpha$ groups, where each sum is in only one group.  For example, and to make things easier, sums $s_1$, $s_2$,...,$s_{\alpha}$ are in group 1, sums $s_{ \alpha + 1}$,...,$s_{2\alpha}$ are in group 2, and so on.  Then we know that each bit will occur exactly once in each group.

So for example, the bit $a_1$ will appear in each group, the bit $a_2$ will appear once in each group, and so on...

QUESTION

How fast can we calculate all of the sums?

MY IDEAS

If we assume that there are $\alpha$ sums in each group, then there are at most $2^\alpha$ combinations of bits.  For example, if there are two sums, we know that there are four combinations of bits:

(0)  Bits that are not in either sum

(1)  Bits that are in sum 1 ($s_1$), but not in sum 2 ($s_2$)

(2)  Bits that are not in sum 1 ($s_1$), but are in sum 2 ($s_2$)

(3)  Bits that are in both sums.

Thus we need at most $n$ additions to calculate the sums of each of the $m / \alpha$ groups.  So our total time is at most $n(m/\alpha)$ additions, since there are $m/\alpha$ groups.

However, I believe that we can do better!  I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.

I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a_1$, $a_2$, $\dots$, $a_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above).  Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a_1$, $a_2$, $\dots$, $a_{\beta}$.  The second collection consists of the second $\beta$ bits $a_{\beta+1}$, $a_{\beta+2}$, $\dots$, $a_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$.  We then calculate each of these sums exactly.  If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach.  Again, I believe that we can do better.


Convex Hull on a Spherical Surface Is there any convex hull algorithm that can be extended to non-euclidean metric, such as the geodesic distance on the surface of a sphere?

I'm not sure what metrics have to do with it: convexity is about barycentric coordinates rather than distance.

The surface of the sphere is nasty because of antipodes. Roughly speaking, if there is an open hemisphere which contains all of the input points, you can work in that hemisphere without problems. Otherwise, the convex hull is going to be the entire surface.

Supposing that there is an open hemisphere containing the points, essentially any 3D convex hull algorithm will work by the addition of an extra point at infinity. But it's probably more elegant to take the centroid in $\mathbb{R}^3$, project to the surface, and use it as a centre around which to apply your favourite wrapping algorithm.


Proving the Bubblesort actually sorts Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$.
To prove that Bubblesort works, we have to prove that it always terminates and that
$$A'[0]\leq A'[1] \leq \dots \leq A'[N-1].$$
Is there anything else that needs to be proven to show that Bubblesort actually sorts?

(I have found this question in a textbook about algorithms.)

Here is an algorithm which satisfies your conditions:

for i in 0,...,n-1:
   A'[i] = 0

Clearly your conditions are lacking.

Correction of a sorting program, like any other program, is a combination of two condition: termination and partial correction. Termination just states that if the preconditions are satisfied then the program always terminates (in your course the phrase used is evidently "outputs after finite time", but halts or terminates is shorter). Partial correctness means that if the preconditions are satisfied and the program halts, then the postconditions are satisfied. What is left here is to come up with preconditions and postconditions. Since you're not working within a formal model, it is not clear how exactly to state the precondition, but it's probably something like that:

Precondition: The input $A$ is an array of length $N \geq 1$ of numbers.

(More generally, it is an array of some linearly ordered set, but we can think of "numbers" (whatever that means) as an important special case.)

Stating the postcondition is harder. It is not enough to ask that the output be sorted, as my example above shows. The semantics are subtler. Here is one way of stating the postcondition:

Postcondition:
(1) The output array $A'$ is an array of length $N$ of numbers.

(2) The output array $A'$ is nondecreasing, i.e., $A'[0] \leq \dots \leq A'[n-1]$.

(3) The multisets $\{A[0],\ldots,A[n-1]\}$ and $\{A'[0],\ldots,A'[n-1]\}$ are equal, i.e., for each number $x$, the number of elements in $A$ equal to $x$ is the same as the number of elements in $A'$ equal to $x$.

The way that you prove postcondition (3) for bubble sort (and, more generally, for comparison sorts) is by showing that the swapping operation preserves the multiset of elements (the fast implementation of quicksort might need more care). So it might seem that you can replace (3) with the following postcondition:

(3') The array $A'$ is obtained from $A$ by a sequence of swaps.

There are two problems with this postcondition. First, it is not semantic — it doesn't describe what sorting accomplishes, only how sorting is done. Second, it is too restrictive. There are sorting algorithms which use operations beyond swapping. A particularly useful example is counting sort. Suppose the sorted numbers come from a very small domain, say $\{0,\dots,m-1\}$. We compute a histogram of the input array (using an integer array of length $m$), and then go over the histogram, producing a sorted version of the input.


Difference between Row Major Order and Column Major order Let take a multi-dimensional array: $a[2][3][4]$

Here $a$ is a three-dimensional array, which means that it is a collection of two-dimensional array's.

Therefore sizeof(a) = No.of 2D arrays * Size of each 2D array = $2*(3*4) = 24$ elements.

Now my observations are:

If Row Major Order is taken, then we have 2 arrays of a[3][4] so each array has $12$ elements.
If we take Column Major Order, then we have 4 arrays of a[2][3]; that is we have only $6$ elements per array.

Is this  approach of calculation right?

The only difference between Row Major Order and Column Major Order in the case of ANSI C is that the memory access patterns are different.

Suppose we have an array $a[i][j]$ which is stored in Row Major Order and we decide to iterate by columns, then the CPU would take more time to process this set of instruction as compared to the case where we decide to iterate by rows. Using the correct access pattern helps the Operating System use caches more effectively.

However this has no bearing on the running time complexity of the code and for all arrays which occupy space below a certain threshold, the difference would be hardly noticeable.

One final note:

If Row Major Order is taken, then we have $2$ arrays of $a[3][4]$ so each array has $12$ elements. Total no.of elements $= 2*12 = 24$ elements.
If Column Major Order is taken, then we have $4$ arrays of $a[2][3]$ so each array has $6$ elements. Total no.of elements $= 4*6 = 24$ elements.


Positional number representation There is a definition of integer representation:

  A positional representation for integers that uses the binary digits 0
  and 1, in which the values represented by successive bits are
  additive, begin with 1, and are multiplied by successive integral
  power of 2, except perhaps for the bit with the highest position.
  (Adapted from the American National Dictionary for Information
  Processing Systems.)

It is not clear to me. Could you give an example reflects that definition? In general, I don't understand what is the successive integral power of 2 and what is the succesive bits?

This appears to be nothing more than a description of the standard binary notation. List the bits in the string and below them, starting with 1 at the rightmost position and multiplying by 2 at each position to the left:
$$\begin{array}{lccccc}
\mathbf{bits:} & 1 & 1 & 0 & 1 & 0\\
\mathbf{powers\ of\ 2:} & 16 & 8 & 4 & 2 & 1\\
\mathbf{product:} & 16 & 8 & 0 & 2 & 0
\end{array}$$
then add the resulting products: $16 + 8 + 0 + 2 + 0=26$, as it should be, since $\mathtt{11010}_2=26$.

The successive integral powers of 2 are just those that appear in the second line, right to left, and similarly successive bits are those in the first line, again reading from right to left. I must confess to being confused by the phrase except perhaps for the bit in highest position.


algorithm for list display I'm working on a website which gets a list of objects like this:

Object { model: "modelhandler.comment", pk: 5, fields: Object }

where the field objects contains this:

Object { user: "TestUser",id: 6, video: 7, description: "test new video comment lol", reply_to: 5, uploaded: "2018-01-12T09:14:24.281Z", updated: "2018-01-12T09:14:24.281Z", indent: 0}

The goal of the site is to find all comments which have reply_to set to a number (not null) and increment it's indent value and all it's children's indent value.

for example consider this list of comments:

comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 0, reply_to: 1)
comment 4 (id: 4, indent: 0, reply_to: 3)
comment 5 (id: 5, indent: 0, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

Now I want to run trough the list and set all indent values according to the reply_to value. so the list becomes:

comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 1, reply_to: 1)
comment 4 (id: 4, indent: 2, reply_to: 3)
comment 5 (id: 5, indent: 1, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

Now this has to happen inside a for loop which allready runs trough the list once:

for(var i = 0; i < array.length; i++) {
    //do stuff here
    //set the indent value here
    if(reply_to)
        indent++;

    //do more stuff here
}

this was my idea for achieving this but it will only increment indent once as it travels trough the list only once. is there a better way to do this?

Assuming the replies are guaranteed to be below the lines they're replying to, you can do this.

if (reply_to != 0)
{
    array[i].indent = array[reply_to].indent + 1;
}


Subintervals during backward search of a BWT A Burrows-Wheeler Transform (BWT) can be used to find the suffix array intervals for a pattern $P$ by issuing $p=|P|$ paired $rank$ queries
\begin{align}
s^\prime &= C[P[i]] + rank(s-1, P[i]) + 1 \\
e^\prime &= C[P[i]] + rank(e, P[i])
\end{align}
where $s$ denotes the start of the search range and $e$ is the end of the range. Initially $s=1$ and $e=|BWT|$. $C$ is a lookup table containing the count of all alphabet symbols in the BWT that sort lexicographically before $P[i]$.
The search proceeds backwards through the search pattern, so it starts at $i=|P|$ and finishes at $i=1$. For example, given the BWT for string $\text{mississippi\\\$}$ and pattern $P=\text{iss}$, the backward search will first identify the interval $[9,12]$ for $\text{s}$, then $[11,12]$ for $\text{ss}$, and lastly $[4,5]$ for $\text{iss}$.
See [1] for a more complete description of backward search and a walk through the example.
My question is during backward search is it possible to determine which subinterval of the previous character's interval lead to the current character's interval?
For example, given the BWT for string $\text{mississippi\\\$}$ and pattern $P=\text{issi}$, the backward search will first identify the interval $[2,5]$ for $\text{i}$ and then $[9,10]$ for $\text{si}$. What I want to know is what subinterval of $[2,5]$ for $\text{i}$ lead to the $[9,10]$ for $\text{si}$. For this toy example I can see the answer is the subinterval $[3,4]$ of $[2,5]$ for $\text{i}$, but I want to know if/how this can be computed during the paired rank queries described above.
The literature suggests that this could be achieved by utilizing a forward search, but this would require a bidirection representation of the BWT, which seems excessive given that we already know the intervals that contain the subintervals.
Any insight would be greatly appreciated!

The answer is deceptively simple. After a paired $rank$ query for a character $P[i]$ you can compute the positions of $P[i]$ in the BWT by performing a paired $select$ query with the ranks from the paired $rank$ query. As seen in the image below taken from the linked example in the question, the character at position $i$ in a BWT is the left extension of the suffix at position $i$ in the corresponding suffix array. This means the positions of $P[i]$ in the BWT found by the paired $select$ query are also the subinterval of $P[i+1]$'s interval that lead to $P[i]$'s interval.

In other words, the subinterval can be computed during the paired $rank$ query with a complimentary paired $select$ query as follows
\begin{align}
r_s &= rank(s-1, P[i]) + 1 \\
r_e &= rank(e, P[i]) \\
s^\prime &= C[P[i]] + r_s \\
e^\prime &= C[P[i]] + r_e \\
s^{\prime\prime} &= select(r_s, P[i]) \\
e^{\prime\prime} &= select(r_e, P[i])
\end{align}
where $s^{\prime\prime}$ and $e^{\prime\prime}$ denote the subinterval of $s$ and $e$ that lead to the $P[i]$ interval $s^\prime$ and $e^\prime$. As previously described, $s^{\prime\prime}$ and $e^{\prime\prime}$ are also the positions of $P[i]$ in the BWT.


Why are NP-complete problems so different in terms of their approximation? I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory.

One thing that I've noticed is that while many problems are NP-complete, when extended to optimization problems, some are far more difficult to approximate than others.

A good example is TSP. Although all kinds of TSP are NP-complete, the corresponding optimization problems get easier and easier to approximate with successive simplifications. The general case is NPO-complete, the metric case is APX-complete, and the Euclidean case actually has a PTAS.

This seems counter-intuitive to me, and I'm wondering whether there is a reason for this.

One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete:

$\Pi$ is in NP, and
For every other problem $\Xi$ in NP, we can turn an instance $x$ of $\Xi$ into an instance $y$ of $\Pi$ in polynomial time such that $y$ is a yes-instance of $\Pi$ if and only if $x$ is a yes-instance of $\Xi$.

Consider condition 2: all that is required is that we can take $x$ and turn it into some $y$ that preserves the "single-bit" yes/no answer. There's no conditions about, for example, the relative size of the witnesses to the yes or no (that is, the size of the solution in the optimization context). So the only measure that's used is the total size of the input which only gives a very weak condition on the size of the solution. So it's pretty "easy" to turn a $\Xi$ into a $\Pi$.

We can see the difference in various NP-complete problems by looking at the complexity of the some simple algorithms. $k$-Coloring has a brute force $O(k^{n})$ (where $n$ is the input size). For $k$-Dominating Set, a brute force approach take $O(n^{k})$. These are, in essence the best exact algorithms we have. $k$-Vertex Cover however has a very simple $O(2^{k}n^{c})$ algorithm (pick an edge, branch on which endpoint to include, mark all covered, keep going until you have no edges unmarked or you hit your budget of $k$ and bactrack). Under polynomial-time many-one reductions (Karp reductions, i.e. what we're doing in condition 2 above), these problems are equivalent.

When we start to approach complexity with even slightly more delicate tools (approximation complexity, parameterized complexity, any others I can't think of), the reductions we use become more strict, or rather, more sensitive to the structure of the solution, and the differences start to appear; $k$-Vertex Cover (as Yuval mentioned) has a simple 2-approximation (but doesn't have an FPTAS unless some complexity classes collapse), $k$-Dominating Set has a $(1+\log n)$-approximation algorithm (but no $(c\log n)$-approximation for some $c>0$), and approximation doesn't really make sense at all for the straight forward version of $k$-Coloring.


Can we push and pop both at a single transition in a PDA? Let say I have a pda :

δ(q1,a,Z)=(q2,aZ)

δ(q2,a,aZ)=(q2,bZ)

Is this allowed....

you can see that in δ(q2,a,aZ)=(q2,bZ), we are basically popping 'a' and pushing 'b' for a single transition...

Is this allowed for PDA ??

(Previously a comment)

Depends on how you define PDAs. The definition I consider canonical certainly does allow you to exactly this: it is assumed that each transition pops the top-most symbol, and pushes an arbitrary string. To represent not changing the stack, you'd push the same symbol you just popped; to pop one symbol, you'd push the empty string; to put $w$ on top of the stack, you'd push $wa$ (where $a$ is the top-most symbol); and to replace $a$ with $b$, you'd push $b$.


I have trouble translating Turing machine language, can you help me break down language notation to English? My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing machine to recognize the language {0n1n | n ≥ 0}.

I have found this guide on a similar problem however I cannot grasp what is going on and what is required from the language statement. Any help in regards to how to read the specified language effectively would be appreciated.

When $s$ is a symbol and $n$ is a natural number, "$s^n$" means "$s$ repeated $n$ times".  So you're being asked to recognize the language of all strings that consist of $n$ zeros followed by $n$ ones, for any possible value of $n\geq 0$.  That is, $\{\epsilon, 01, 0011, 000111, 00001111, \dots\}$, where $\epsilon$ denotes the empty string (some people write $\lambda$ for the empty string, instead).


Dijkstra with max instead of sum Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of finding the shortest paths where the length of the path is measured as the maximum of its edge weights?

Yes, it is true.

Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{ is edges of a path from } s \text{ to } v \}$ i.e. the shortest path between $s$ and $v$.

Let's prove by induction on the step of Dijkstra's algorithm that it does indeed find the shortest paths. Let $S \subseteq V(G)$ be the set of vertices that have been already processed by the algorithm. Then Dijkstra's algorithm finds $p'(v) = \min\{\max\{p(u),w(uv)\} \mid u \in S\}$ for every $v \in V(G) \setminus S$. Then it is sufficient to prove that there exists $v_0$ such that $p(v_0) = \min p'(v)$ the equality $p(v_0) = p'(v_0)$ holds. Let $e_1, \ldots, e_k$ be the edges of the shortest path from $s$ to $v_0$. $e_k = u v_0$ then $p(u) \le p(v_0)$. If $u \in S$ the statement is proved. Otherwise pick $v_0 := u$ instead (this reduction is finite since we can choose a vertex closer to $s$ in terms of the smallest number of edges in a path between them).

So essentially nothing changes comparing to the algorithm and the proof.

But there is another solution that uses Disjoint Set Union (DSU) data structure. Initialize DSU with sets $\{v_1\}, \{v_2\}, \ldots, \{v_n\}$. Then add edges in the increasing order of $w$ and when an edge $uv$ is added unite the sets containing $u$ and $v$ in the DSU. If at some step an edge with a weight $x$ has been added last then all the vertices in the set containing $s$ have distance to it at most $x$. So if you unite sets $A \ni s$ and $B$ put $p(v) = x$ for $v \in B$.


How does software detect if an interrupt has occurred if it cannot set it's own interrupt handlers? I'm currently working on designing a relatively simple processor using a custom ISA .
It will use interrupts for I/O .

From what i know , once the interrupt controller issues an interrupt , the processor acknowledges it and set it's PC to the IVT , from where it executes the relevant interrupt handler , which specifies what the CPU does .

These interrupt handlers are set by the OS and cannot be modified by the user-mode process.

My question is this : how does the process know when an interrupt has occurred ? the cpu might execute the handler and place the acquired controller data in a memory location , but how is the application notified ? what are the common methods of doing this ?

For example , say i have a platform game ; when i press the assigned jump key , the cpu will acquire the keyboard data , but how does it go from there to actually making the sprite jump in a video game ? does the app still have to check for controller input at regular intervals ?

The interrupt handler adds the new data to an input queue.  Typically the user level process will have a thread waiting for input to appear, or will poll periodically to see if new input is available.  If your process does neither, it would never notice the new data.


Proving following problem NP Hard using known NP Hard partition problem Least cost travel by intermixing different airline routes having linear discount functions:

Lowest air fare route chosen by mixing different routes provided by different airline having different discount functions (like some airline can give 25% discount if fare crosses $5k) so that total cost of travel is minimized after intermixing of different airline routes

This is a graph problem. Let $E(k)$ be the set of edges/routes
flown by $k$-th airline, also given cost of travel associated with
each edge.

For $n$ airlines we have $n$ sets of edges i.e $E(k)=\{\mbox{some edges}\}$ for
all $k=1.. n$. We need to find the route from given source $s$ to given destination $t$
such that we end up paying least fare among all possible
routes. There is no restriction on number of edges in a route.

This is an NP-hard problem. How can I prove it?

Assuming that an "airport" cannot be visited more than once, you can reduce HAMILTONIAN PATH to your problem: given a graph $G = (V,E)$, $|V|=n$; suppose that there are two airlines such that $E(1)=E(2)=E$ (i.e. both airlines cover all edges). Then set the price of each edge = $1$. One of the two companies gives no discount, the other gives a (big) discount $d$% (such that $n - \frac{n * d}{100} < 1$) if the cost of the travel is $\geq n$.

Then $G$ has an Hamiltonian path from $s$ to $t$ if and only if the minimum cost of the travel is $< 1$ (i.e. the airline which gives the discount is more convenient).

Note: if an airport can be visited more than once I think that the problem is no more NP-hard (but  I didn't think of it too much). In this case a modified version of a shortest path algorithm should work: just augment the shortest path traversing multiple times an edge of each airline and check if the total cost decreases after reaching the discount treshold.