Travelling plan between two places There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$.

At each step $i$ there are two choices: stay where you are or change. Whatever you choose you pay a cost $A_i$ or $B_i$ depending on where you are, anyway if you change you pay also an addition that is usually a constant value.

For example, in Kleinberg's problem 6.4 you have two cities (New York and San Francisco), a set of $n$ months, a moving cost $M$ and two sequences of operating costs: $N_1 \ldots N_n$ and $S_1 \ldots S_n$. A plan is a sequence of $n$ locations, such that the $i$-th location indicates the city in which you will be based in the $i$-th month. The cost of a plan is the sum of the operating cost of each of the $n$ months, plus a moving cost of $M$ for each time you switch cities. You have to find a plan of minimum cost.

You eventually approach such problems using two variables. For example defining $OPT(i,j)$ with $i \in \left\{1\ldots n\right\}$ and $j\in \left\{N,S\right\}$ as the cost ending up in month $i$ at $j$ city .
$$
OPT(i,N) = \min\left(N_i + OPT(i-1,N), N_i + OPT(i-1,S) + M \right)
$$
$$
OPT(i,S) = \min\left(S_i + OPT(i-1,S), S_i + OPT(i-1,N) + M \right)
$$

At the end of the process, solution is given by $\min\left\{ OPT(n,N), OPT(n,S) \right\}$.

This is pretty straightforward, but i perceive it as a pragmatic way. How may we prove that two variables are strictly required here? Is there any particular property related to this class of problems?

I'd like to know also if there is a way for solving it with a different recurrence with a variable only, or why if it is not possible.

Before proving a lower bound you have to formalize your computational model. This can be done in several ways for dynamic programming. The pioneer here is Allan Borodin, who came up with priority branching trees. Buresh-Oppenheim et al. extended this to the strong model of priority branching programs. Jukna considered incremental dynamic programming algorithms,tropical circuits and tropical switching networks. The last model is particularly simple, and Jukna proves some tight results for it, so you may be able to prove that your algorithm is optimal for that model.


In a kernel, what are "global constructors"? I am a beginner developing kernels (though I have developed several Hello World programs in C and C++). I frequently see reference being made to global constructors (e.g., osdev https://wiki.osdev.org/Calling_Global_Constructors), but I have not been able to find a clear definition or in it.

Could someone please guide me to the correct definition? I know they are called before the kernel, but I am having trouble understanding why.

The kernel of which I take the example, is this:
  https://github.com/AlgorithMan-de/wyoos/commit/7eb9f8a1d5089cf7587e553e601c42db34dc94a2

in the linker.ld file, have this code:

  .data  :
  {
  start_ctors = .;
  KEEP(*( .init_array ));
  KEEP(*(SORT_BY_INIT_PRIORITY( .init_array.* )));
  end_ctors = .;

  *(.data)
  }

in the kernel.c file, have this code:

typedef void (*constructor)();
extern "C" constructor start_ctors;
extern "C" constructor end_ctors;
extern "C" void callConstructors()
{
  for(constructor* i = &start_ctors; i != &end_ctors; i++)
     (*i)();
}

The link you provided has a clear definition:

  This tutorial discusses how to correctly invoke global constructors, such as those on global C++ objects. These are supposed to have run before your main function, which is why the program entry point is normally a function called _start.

In most OSs, there is a step where the process' memory is filled with its initial values.  For C code, that is typically sufficient.  However, sometimes you want to execute some code before main(), which is your official entry point.  For example, in C++, you need to be able to call the constructor of all global objects before main() is invoked.

To resolve this, and any other run-time activities which must be done before main(), each system provides some way to execute a function before main.  The article mentions that some treat it as a simple array of function pointers, but some compilers will obscure it and hide it.

The key takeaway is that these are handled before the entry point of your program.


NPDA transitions to different states by taking same input and popping same top element of a stack Suppose i have some NPDA and there is some transition functions defined as:

$\delta(q_{1},a,A) = (q_{2}, A)$

$\delta(q_{1},a,A) = (q_{3}, Z)$

Is it allowed?
I understand, that since the NPDA is nondetermenistic, it's possible to have transitions to different states with the same input character, but what about same element at the top of stack?
Thanks.

This is very well possible, the automaton nondeterministically chooses which transition is taken. So it may choose between $\lambda$-transitions and transitions reading input, all with the same symbol on top of the stack.

Sometimes this is written as
$\delta(q_1,a,A)=\{ (q_2,A), (q_3,Z)\}$,
where $\delta$ is considered as a function from $Q\times(\Sigma\cup\{\lambda\})\times\Gamma$ into finite subsets of $Q\times\Gamma^*$.

Alternatively $\delta$ can be seen as a finite relation in $Q\times(\Sigma\cup\{\lambda\})\times\Gamma\times Q\times\Gamma^*$, and we write $(q_1,a,A,q_2,A), (q_1,a,A,q_3,Z)\in\delta$.


Time complexity of DFS and recurrence relation Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?

For an implicit graph  the recurrence can be written as follows:

Let $b$ be the number of branches of every node (assumed to be constant)

let $d$ the depth of the graph

For depth 1 there are $b$ branches:

$T(b,1) = b$

For the next levels it can be written as

$T(b,d) = b + b*T(b,d-1)$

where $b$ are the nodes at this level, and are the $b*T(b,d-1)$ nodes at next level.

If you substitute the definition for $T(b,d-1)$ you get

$b * (1 + b*(1+T(b,d-2)) = b + b^2(1+T(b,d-2))$

If you further substitute the definition of $T(b,d-2)$ you get

$b + b^2(1+b+b*T(b,d-3)) = b + b^2 + b^3 + b^3*T(b,d-3)$

If you continue to expand you get

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*T(b,1)$

Since we know that $T(b,1) = b$, we can substitute

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*b$

Thus

$T(b,d) =  b + b^2 +b^3 +... + b^d$

Using Big-O Notation. $O(b^d)$

For explicit graphs with $V$ vertex and $E$ edges

We assume you have an adjacent list. That is for every $V$ you have a list of adjacent edges. You can think of a Table of $E$ edges (columns) x $V$ vertex (rows).

We can write our recurrent relation based on the navigation of that table.

$T(V,E) = 1 + e_0 + T(V-e_0,E-e_0)$

We count $1$ for visiting the first row, and $e_0$ for the number of edges adjacent to that first vertex.  For the next rows we use the recurrent relation except this time we have $V-e_0$ vertex and $E-e_0$ edges to visit.

If we substitute our definition for the 3rd. element in our relation we get:

$T(V,E) =  1 + e_0 + 1 + e_1 + T(V-e_1,E-e_1)$

if you keep expanding you get

$T(V,E) =  1 + 1 + .. + 1 + e_0 +e_1 + .. + e_V$

1 for every row visited and a certain number of edges for a given vertex.  In total the number of edges is $E =e_0 + e_1 + .. e_V$.

$T(V,E) =  V + E$

in Big-O Notation $O(V+E)$.


Are functions that are equal to a constant as you take a limit to infinty O(1)? The below function converges to a constant as you take n to infinity.
$f(n)=(1 + \frac{1}{n})^n$
$\lim \limits_{n \to \infty}(1 + \frac{1}{n})^n = e$
Would this imply that it is O(1) since you can just upper bound it with a constant?

By definition of $O$ notation, if you can find a constant $c$ and $n_0$ such that $f(n) < c g(n)$ for all $n > n_0$, we can say $f(n) = O(g(n))$. In this case, suppose $n_0 = 1000$ and $c = 3$ and $g(n) = 1$. You can show that as $f(n)$ is increasing function and $\lim_{n\to\infty}f(n) = e$, it is true $f(n) < 3 g(n)$ for all $n > 1000$. Therefore, $f(n) = O(1)$.


Does the amount of symbols a turing machine has affect what computations it can perform? Do additonal symbols on a turing machine actually change what is computationally possible on a machine, or do they just make them easier to work with? For example is there anything a 3 symbol turing machine could compute that a 2 symbol turing machine could not? (Assuming each machine can have any number of states).

Hint: can you express more integers by writing them in a bigger base?

I'll go with the definition where the blank is counted as a symbol. A Turing machine must have at least one non-blank symbol, i.e. at least two symbols. With 0 symbols there's no way to build a tape, and with only the blank symbol there's a single possible tape so the machine is effectively a finite automaton.

Any $n$-symbol Turing machine can be translated to a Turing machine with the symbols $\{0,1\}$ where $0$ is the blank symbol. Let $k$ be an integer such as $2^k \ge n$, and number the symbols from $0$ to $n-1$, with the blank symbol numbered $0$. Translate the tape by mapping each symbol to the sequence of $k$ symbols that is the representation of its number in base $2$.

The state set increases. For each original state $q$, we define several types of states in the new machine:

Forward read states $(\mathsf{R},q,i,x)$ where $0 \le i \le k-2$ and $x \le 2^i$: read the bits that represent one original input symbol, remembering the position $i$ and the partial accumulated number. These states have a right transition to either $(\mathsf{R},q,i+1,2x)$ or $(\mathsf{R},q,i+1,2x+1)$ depending on the symbol read from the new tape.
Decision states $(\mathsf{R},q,k-1,x)$: if there is a transition $\delta(q,x) = (q',x',d)$ in the original machine, then transition to a write state $(\mathsf{W},q',d,k-1,x')$. If the state $q$ is final in the original machine, this state is final in the new machine.
Write states $(\mathsf{W},q',d,i,x')$ where $1 \le i \le k-1$ and $x' \le 2^i$: write the low-order bit of $x'$ to the tape and move left to $(\mathsf{W},q',d,i-1,\lfloor x'/2 \rfloor)$.
Last-bit write states $(\mathsf{W},q',d,0,x')$ where $x' \in \{0,1\}$: write $x'$ to the tape, and move to a fast-forward state or a fast-backward state depending on $d$.
Fast-forward and fast-backward states $(\mathsf{F},q',d,i)$ where $0 \le i \le k-1$: keep moving in the same direction and decrement $i$ until it reaches $0$, at which point, switch to the corresponding forward read state. These states are used to either skip forward to the beginning of the part of the tape that represents the next original symbol after a right transition in the original tape, or to skip backward to the beginning of the part of the tape that represents the previous original symbol after a left transition in the original tape.

In summary, we make three passes over each symbol: one to read it, one to write the new symbol, and one to reposition the tape.

The details are tedious but not difficult.


Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try:
I know that context-free languages are closed under union operation. Also I know how to make a PDA for union. So I tried to decompose the given language to some parts. For example, the language of the strings starting by $b$, the language of strings ending with $a$, the language of strings containing $bab$ as a substring.
I made a context-free grammar for these languages. Then I made PDAs based on each grammar and I combined them to get a PDA for the union of them.
But I know that the union of these languages does not cover all strings in the given language. Could you help me find what I'm missing and how to make a context-free grammar for that?

If a word is not of the form $(a^nb)^n$ for $n > 0$, then one of the following must happen:

The word is not of the form $(a^*b)^+$, i.e., it is either empty or ends in $a$.
The word is of the form $a^ib(a^*b)^*a^jb(a^*b)^*$ for some $i \neq j$.
The word is of the form $a^nb (a^*b)^k$, where $n \neq k+1$.

Each of these can be checked by a PDA or generated by a CFG. It might help to break a condition of the form $i \neq j$ into two alternatives, $i > j$ and $i < j$.
To see why this case distinction holds, let us assume that the word is of the form $(a^*b)^+$. We can write it as
$$
a^{i_1} b a^{i_2} b \cdots a^{i_m} b.
$$
The word is of the form $(a^nb)^n$ if $i_1 = \cdots = i_m = m$, which is equivalent to
$$
i_1 = i_2 \text{ and } i_1 = i_3 \text{ and } \cdots \text{ and } i_1 = i_m \text{ and } i_1 = m.
$$
Hence the word is not of the form $(a^nb)^n$ if
$$
i_1 \neq i_2 \text{ or } i_1 \neq i_3 \text{ or } \cdots \text{ or } i_1 \neq i_m \text{ or } i_1 \neq m.
$$
The case $i_1 \neq i_j$ is handled by the second bullet above, and the case $i_1 \neq m$ is handled by the third bullet.
(Thank you to Hendrik Jan for help with simplifying the cases.)


What is "σ" in a context free grammar? I have a grammar like this:

A → BAB | B | ε
B → 00σ | ε

What is the meaning of σ in the second rule?

Most probably, it means “for each letter $\sigma$ from alphabet $\Sigma$”.

If $\Sigma = \{ 0, 1 \}$, then B → 000 | 001 | ε.


Why is it important to solve a problem in Polynomial time, In cryptography? I have just started to learn Cryptography.

I am trying to learn "Merkle-Hellman Knapsack Cryptosystem".

So, right at the beginning of the discussion, a question came in my mind:

Why is it important to solve a problem in Polynomial time?

The concept of polynomial time is a theoretical concept that is supposed to capture what kinds of problems are possible to solve "in practice". In practical cryptography, the goal one is interested in is that no government body can break the system in less than a 100 years (say). However, this concept is hard to reason about, for many reasons. One reason is that the set of problems that can be solved in a 100 years depend on your hardware, budget, and so on. Moreover, even given a specific algorithm for a problem, it is hard to estimate how much time exactly it will require to run. To circumvent these difficulties, cryptography theory suggests the following idea:

  Consider a cryptosystem which depends on a parameter $n$ tending to infinity. Analyze the security of the cryptosystem in terms of the asymptotic complexity of breaking it.

The asymptotic complexity doesn't depend too much on the exact hardware (as long as it's not a quantum computer); if next year a new CPU is revealed running 10 times as fast, a system that requires $O(2^n)$ time for breaking will still require $O(2^n)$ time for breaking. Moreover, we make the following assumption:

  An algorithm runs "fast" if it runs in polynomial time (in $n$).

Polynomial time is a natural class for many reasons, the reason here being that it is the smallest class which is closed under function composition and contains superlinear functions. Putting both ideas together, we get:

  A cryptosystem depending on a parameter $n$ is secure if it cannot be broken in time polynomial in $n$.

Here $n$ should be a reasonable parameter. One way of enforcing it is to require the encryption procedure to run in polynomial time in $n$.

This definition has led to a beautiful theory of theoretical cryptography. However, in practice polynomial time is not such a good notion, especially in cryptography, for two reasons:

Polynomial time could be very slow in practical. For example, an encryption procedure running in time $O(n^{10})$ or $10^{10} n$ is not practical.
Super-polynomial time could be practical, depending on the value of $n$. For example, $2^{n/2}$ is very practical for $n = 64$.

In applied cryptography, therefore, one tries to give running time estimates for a particular system (a particular setting of $n$) which is not asymptotic. Usually one calculates the number of "basic operations", a concept which is not defined precisely but is a better proxy than asymptotic complexity. When possible, actual simulations are run to show that the cryptosystem can be broken with weakened parameters, and to extrapolate the time it takes to break the full cryptosystem.

One problem with this approach is that it is going to be very difficult to prove that a system is secure. While this is true even for theoretical cryptography (we cannot prove the security of any cryptosystem), here it is seems that the best one can do is try to break the system and fail; proving a meaningful lower bound is probably too much to ask for.

One way to circumvent this difficulty in some situations is to use oracle (or black box) models. Suppose that a cryptosystem relies on some cryptographic primitive which we trust. We can imagine replacing this primitive by an idealized component. In this case, sometimes lower bounds on the number of queries to the black box can be proved. This allows us to gauge the security of the model, making the implicit assumption that the algorithm implementing the black box is completely opaque.

This is the approach taken by theoretical cryptography – assuming the existence of some secure cryptographic primitive (which we can't prove at the moment), it constructs cryptosystems and proves their security. However, this doesn't necessarily have practical implications, since in reality the parameter $n$ is fixed rather than tending to infinity. Even in cases in which we can rigorously prove that some cryptosystem requires $T(n)$ time to break (given some assumptions on the cryptographic primitives), usually the guarantees are very weak, and in order to get reasonably large $T(n)$, an impractically large $n$ is required.

For more information, check this classic paper on concrete security and this notorious article debunking theoretical cryptography.


The maximum number of statements that could be true at the same time I've come across a programming question. I can't solve it but I can write the question in mathematical form as follow:

  Receive k equations,and for each equation receive 3 variables a, b, and c in the following form:

  ax + by + cz >= 0

  This is an example input of k = 4:

  1) 2x + 1y + 0z >= 0

  2) 1x - 2y + 0z >= 0

  3) 3x + 3y - 50z >= 0

  4) -1x + 2y - 50z >= 0

  You should find the maximum number of statements that could be true at the same time given that x, y, and z are positive real numbers and x >= y >= z. As for the following example, the answer is 3.

Please help me with the idea or the design paradigm I should use to solve this problem. The algorithm should be relatively fast. It should be able to compute k = 1,000 in 1 seconds.

There is a $O(k^4)$ time algorithm that works by considering all possible subsets of three out of the $k$ inequalities, looking at the "intersection point" of those 3 inequalities, and counting how many of the inequalities that intersection point satisfies.

In more detail:

This can be solved if you are familiar with some basic facts from linear programming and the simplex method.  Let $S$ be a set of $m$ linear inequalities in $n$ variables.  $S$ defines a $n$-dimensional polytope.  Then the following fact is useful:

Fact: If $S$ has a feasible solution, then it has a feasible solution that is one of the vertices of the corresponding polytope.

(Recall that a vertex is a single point that is a "corner" of the polytope.  Each vertex can be obtained by taking a subset of $n$ independent linear inequalities from $S$, converting them to equalities by changing $\ge$ to $=$, and solving to find the unique point at their intersection.)

For linear programming, a useful consequence of this fact is that, to find the optimal value of the objective function, it suffices to enumerate only the vertices of the polytope and compute the objective function for each such point.  Here we have no objective function and care only about feasibility, but this basic fact is still useful.

In particular, in your problem we have $n=3$ variables ($x,y,z$) and we want to find the largest possible subset of the inequalities, say $j$ of them, that are all consistent.  Any such subset of $j$ of the given inequalities corresponds to a set $S$ of $m=j+5$ inequalities: namely, the subset of $j$ inequalities, plus the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$.  In this way we get a set $S$ of $m=j+5$ inequalities on $n=3$ variables.  Now if there is a feasible solution to $S$, then one of the vertices of $S$ must be a feasible solution.

Essentially, this means that we can restrict our attention to only the vertices; we can ignore all other points in the polytope.

Of course, we don't know what $S$ is, so we don't know what the polytope is.  Nonetheless, we can still use this fact.  This fact means that we can restrict our attention to only the "possible vertices", where a "possible vertex" is a point that is a vertex of one such polytope.  In other words, consider all possible polytopes obtained by taking some subset of the given inequalities and adding the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$; take the union of the vertices of all of these polytopes.  Then it suffices to look only at these possible vertices -- we don't need to consider any other possible value of $x,y,z$.

How many possible vertices are there?  Well, each vertex is determined by choosing $n=3$ of the inequalities, converting them to equalities, and looking at their intersection.  So, there are only ${k+5 \choose 3} = O(k^3)$ possible vertices.  For each possible vertex, we can count how many of the $k$ inequalities it satisfies, and see which one satisfies the largest number of inequalities.  That one will be the optimal solution to your problem.


Algorithm to find a subgraph such that all of its edges has an anti edge Let $G=(V,E)$ be a directed graph. The "invertible" part of $G$ is the subgraph $H=(V,E_2)$ such that $(u,v)\in E_2 \iff (u,v)\in E \land  (v,u)\in E$.
Find an algorithm that generate $H$ from $G$ in a linear time, where $G$ is represented with an adjacency list. Non linear memory is allowed.

Obviously the brute force approach won't be linear, and I thought to use an adjacency matrix but that would be at least $\Omega (n^2)$.
I also thought maybe it's possible to create a forest of DFS trees and then, checking each edge if it has an anti edge would be a lot more easier, but I'm not sure if it would be possible to keep all the information from the original graph...
Another way is to generate the anti graph of $G$, then intersect it with $G$ and then subtract the intersection from $G$, we'll be left with all edges that didn't have an anti edge, it sounds too complicated too work in linear time though and I'm not sure how to implement this algorithm..
Am I on the right track? Is there another way?

Here is one approach, which assumes that the adjacency lists are sorted. First, compute the reversed graph (your anti graph) in linear time. Then, compute the intersection by first merging the adjacency lists from both the original graph and the reversed graph, and then looking for edges which appear twice. This takes linear time since the lists are sorted.


How to determine time complexity with a simple way? I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−n} + 8 \sin(2πn/256). $$

Is there a simple way how a I can determine which one of this is the true one? Because this look much more complicated then the ones we did in our class.

$f(n) =o(n\log_2n)$
$f(n) =o(2^n)$
$f(n) =o(n^4)$
$f(n) =O(n\log_2 n^n)$
$f(n) =O(2n + 1)$

Asymptotic notation satisfies the following two useful properties:
$$
\Theta(f(n)) + \Theta(g(n)) = \Theta(\max(f(n),g(n)) \\
\Theta(f(n)) \Theta(g(n)) = \Theta(f(n)g(n))
$$
Using these, you can determine that $f(n) = \Theta(4n^2\log^2 n)$.

Now you can check each of 1.-5. individually, using the fact that $n^a\log^bn = O(n^c\log^dn)$ iff $a < c$ or $a=c$ and $b \leq d$.


No of Actions in if statement i am new to analysis of algorithm . i am having an if condition.

If (I !=j AND A[i]==A[j])

i am counting the operations as

i) accessing element from Array A[]
ii)compairing i!=j

iii) compairing a[i]==a[j]

according to me this statement is performing 3 Actions. is it so ? if not than please clarify... thanks

Counting "actions" in this way is completely arbitrary. In order to accurately count basic actions, you need to first come up with a list of basic actions, and then to compile your statement to a list of basic actions. This is exactly what compilers do – they compile your problem to assembly language or, in some cases, to bytecode.

Since you are not specifying your assembly language, it is truly impossible to say anything. It could be that there is one instruction that is equivalent to your if, or it could be that your assembly language is very weak, and your if requires 100 instructions. Even if you did specify your assembly language, it is still not clear how to compile the statement to assembly, since in general there is no canonical way to do so.

The way out is to realize that (under certain conditions) whatever assembly language is used, the statement would compile to a constant number of instructions, whose exact number depends on the assembly language. Therefore we can say that the number of instructions is $O(1)$, where the hidden constant depends on the assembly language and the compiler. In contrast, a loop summing an array would execute $\Theta(n)$ instructions. The difference between $O(1)$ and $\Theta(n)$ exists irrespective of the assembly language and compiler used.


Every vertex cover is a dominating set Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set.

Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)$ is a subset $S$ subset of $V$ such that every vertex is either in $S$ or has a neighbor in $S$.

I know that a vertex cover is always going to be a dominating set because a vertex cover set is such that every edge has a vertex in the set, which means that a vertex not in the set (so on the other end of the edge) must have a neighbor in the set in order for all edges to be covered...

I just don't know how to write this as a proof.

Here is a correct version of your result:

If a graph contains no isolated vertices, then every vertex cover is a dominating set.

For the proof, let $G$ be a graph with no isolated vertices, and let $S$ be a vertex cover. In order to show that $S$ is a dominating set, we need to show that every vertex not in $S$ has a neighbor in $S$. Suppose therefore that $v \notin S$. Since $G$ has no isolated vertices, $v$ has some neighbor $u$. Since $S$ is a vertex cover, it must contain one of $v,u$. Since $v \notin S$, necessarily $u \in S$. Therefore $v$ has a neighbor $u \in S$.
A stronger version of this result states that the condition of having no isolated vertices is tight.

Let us call a graph good if every vertex cover is a dominating set.
A graph is good iff it contains no isolated vertices.

We already saw one direction. Now suppose $G$ is a graph containing some isolated vertex $v$. Take an arbitrary vertex cover $S$. Since $v$ is isolated, $S \setminus \{v\}$ is also a vertex cover, but it is not a dominating set, since $S \setminus \{v\}$ doesn't contain $v$ or any of its neighbors (since it has none!).


Undecidability of the language of PDAs that accept some ww I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation,
"Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$. Use the computation history method to show that this problem is undecidable."
I have an attempt at a solution but somehow I just feel kind of foggy on whether it's correct and would appreciate anyone finding flaws in the solution.

For reference, I'm trying to mimic or adapt the solution given earlier in the chapter to
$$ ALL_{CFG}=\{\langle G\rangle | G \text{ is a CFG and } L(G)=\Sigma^*\}$$
Theorem: $ALL_{CFG}$ is undecidable.
The proof given there reduces from $A_{TM}$ the decision problem of checking whether a TM called $M$ accepts a string called $w$.  It does so by, for any fixed $M,w$, constructing a CFG $G$ which produces all possible strings if and only if $M$ accepts $w$.  In particular $G$ is the CFG which generates all the strings that are NOT accepting histories for $M$ on $w$.
It then proceeds to show how to build such a $G$.  For the purposes of the problem I'm asking about, I can just accept that this is possible.

Also for reference, there is this answer to a similar question on here: https://cs.stackexchange.com/q/6629
I particularly want to follow the textbook's guidance in order to practice this method of using a computation history, so I'm ignoring the first answer to the problem. However, I don't understand the answer given for computation histories.  The CFG that he gives (or equivalent PDA) doesn't seem to generate strings with at least one $v!v$ if and only if $M$ accepts $w$.  Supposing $M$ accepts $w$ I don't see a reason why $C_0\#...\#m(C_{2n})\#C_f = C_1'\#...\#m(C_n')$.

My solution is, like in the book's solution for $ALL_{CFG}$, to try to use $M$ and $w$ to build a CFG such that $M$ accepts $w$ if and only if $G$ generates some string of the form $vv$.  In particular $G$ is the grammar defined by the PDA $D$ which on input $x$ checks the first half to see if it's an accepting history of $M$ for $w$, and then checks the second half to see if it equals the first half.  I believe each of these are things any PDA can do, and once built, $G$ will have the properties promised earlier.  Am I making any mistake here?

Your proposed idea doesn't work, because after you have checked the first half of the input with your PDA, you have popped them all so you cannot reaccess them for comparing with the second half.
The correct idea should be making a PDA that checks if odd number configurations leads to even numbered configurations in the first half and vice versa in the second half. Also, make sure the PDA handles the start and accepting state. Then convert the PDA to CFG and pass it to the decider for the language $\{ww\}$. Accepts if it accept and rejects otherwise.
This will work as you can show that the PDA as constructed above will recognize string of form $ww$ iff $M$ accepts $w$. This is because the parity checks of configurations only gives incomplete information, but when supplied with the fact that you have two equal computation history in some string, it tells you each half of that string is actually an accepting computation history of $M$ on $w$.


An online algorithm to find the Pareto frontier elements I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements).

For instance. Given the following inputs, the retained Pareto frontier set would evolved as follows:

(3,7)

insert element b/c it's the first element
pareto set now includes {(3,7)}

(7,3)

insert element b/c it's not dominated in the first
pareto set now includes {(3,7), (7,3)}

(8,4)

insert element b/c it's not dominated; remove (7,3) which it is dominated in both dimensions
pareto set now includes {(3,7), (8,4)}

(1,1)

do not insert because it's dominate in both dimensions
pareto set now includes {(3,7), (8,4)}

(9,9)

insert element b/c it's not dominated; remove all other elements because this dominates them in both dimensions
pareto set now includes {(9,9)}

In my example I'm using 2-tuples, but I'm looking for an algorithm that could handle N-tuples for "small" N (say <10).

The naive solution is to just to compare each element with all elements currently in the set. In practice the naive approach might not be so bad (e.g. sub $O(n^2)$) because elements will regularly be expelled by the comparison set. But I was wondering if there was a known efficient algorithm for this. I'm interested in efficiency in memory and in computational complexity. (Ha! And as a matter of fact, I'm looking for the set of algorithms that are Pareto optimal with respect to memory and computational complexity.)

My current application of this is in building a Lucene search-document Collector that doesn't collect the most relevant documents (the typical use case for a search engine), but collects the Pareto optimal documents along specified dimensions.

In two dimensions, each update can be done in $O(\lg n)$ time, by using a balanced binary tree data structure.  But when you are working in a high-dimensional space, I don't know of any efficient solution.

Let me describe an efficient algorithm for the 2D case.  Let $F$ denote the set of points in the Pareto frontier.  Store $F$ in a balanced binary tree, using the $x$-coordinate of each point as its key.  Note that when you sort $F$ by increasing $x$-coordinate, they'll also be sorted by decreasing $y$-coordinate.

Now, given a new point $(x_q,y_q)$, you can check efficiently whether it is Pareto-dominated by any element of $F$.  Find the first element of $F$ to the right of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \ge x_q$ and $x$ is minimal); then checking whether it dominates $(x_q,y_q)$.

Also, given a new point $(x_q,y_q)$, you can efficiently find whether it Pareto-dominates any element of $F$.  In particular, you can find indices $i,j$ such that the points $(x_i,y_i),(x_{i+1},y_{i+1}),\dots,(x_j,y_j)$ of $F$ are all Pareto-dominated by $(x_q,y_q)$ (assuming that the points of $F$ have been ordered by $x$-coordinate, Pareto-dominated points will be in a consecutive interval).  Here's how.  Find the first element of $F$ to the left of $(x_q,y_q)$ (i.e., the element $(x_j,y_j) \in F$ such that $x_j \le x_q$ and $x_j$ is as large as possible), and check whether $(x_q,y_q)$ dominates it.  If yes, find the smallest index $i$ such that $i<j$ (so $x_i<x_j$) and $y_i \le y_q$.  Both of these steps can be done in $O(\lg n)$ time.  (Finding $i$ can be done in $O(\lg n)$ time by treating the tree as branching on the $y$-coordinate of points, and taking advantage of the fact that the points of $F$ are sorted by decreasing $y$-coordinate.)

Now this tell us what to do.  If $(x_q,y_q)$ is dominated by some point of $F$, then don't add it to $F$; you're done.  Alternatively, if $(x_q,y_q)$ dominate points $i..j$ of $F$, then you need to delete those points from $F$ and add $(x_q,y_q)$ into $F$.  This can be done in $O(\lg n)$ time, by noting that any interval of consecutive indices can be expressed as the union of $O(\lg n)$ subtrees of the binary tree (roughly speaking, you work with the siblings of the nodes along the path from $i$ to the root, and the same for the path from $j$ to the root); you can delete each subtree in $O(1)$ time.  This lets us delete an entire range of consecutive points in $F$ in $O(\lg n)$ time, no matter how large the range is.  For details, see Delete a consecutive range of leaves from a binary tree.

All of this can be done in $O(\lg n)$ time, using a balanced binary tree data structure.

This works in 2 dimensions (i.e., 2-tuples).  In higher dimensions, the problem gets much harder.  You can find references to the literature, with techniques for higher dimensions, at How to find a subset of potentially maximal vectors (of numbers) in a set of vectors; but I'm afraid that in high dimensions, all the known algorithms are likely to be fairly slow (they have a factor that is something like $O((\lg n)^{d-1})$ where $d$ is the number of dimensions).


Time complexity for the 'Restore IP Addresses' problem There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns ["255.255.11.135", "255.255.111.35"].

My solution basically breaks up the string (upto 3 chars at a time) and moves to the remaining part of the string. This way we build a list of valid ip addresses using recursion. I've pasted my solution below.

If the input is number of characters (n) what would the time complexity of this solution be (with an explanation)? Also, would memoization help in this case?

/**
 * @param {string} s
 * @return {string[]}
 */

function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}

function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];

  let ret = [];

  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);
  }

  return ret;

}

var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};

The time complexity here is exponential in s or parts, whichever is smaller.

You have a recursive function, and it calls itself three times (after removing 1, 2, or 3 characters from the beginning). Thus, if $n$ is the size of $s$ and $k$ is the number of parts, your time complexity $T(n, k)$ satisfies
$$
T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1)
$$
We can roughly replace this by $T(n, k) = 3 T(n-3, k-1)$ (a lower bound) which leads to
$$
T(n, k) = \min(3^{n/3}, 3^{k}).
$$

For IP addresses, this exponential time complexity is likely not a huge problem. It's exponential in the number of parts, but the number of parts is only $4$, so that is not huge.

However, conceptually, your solution is pretty inefficient. Notice that you are duplicating a lot of work: you might call your breakString function on the tail of the same string several times, in different recursive calls.

To get a more efficient algorithm, try dynamic programming instead of recursion. For instance, can you keep track of, for each prefix and possible # of parts, whether it is a valid IP address or not? What complexity would that give?

NOTE: In the above idea to try dynamic programming, I assumed that the goal was just to return one valid IP address, not return all of them. When we have to return all of them, the time complexity changes somewhat, because the time complexity is now at least the time it takes to output all the answers, and there could be exponentially many answers.

Specifically, the time complexity in the worst case is bounded below by the number of decompositions of s in the following example: let s be a string of length $4n$ 1s, and let parts $= 2n$. Then there are at least $3^n$ decompositions: this is the number of decompositions where there is a . after every block of $4$ characters.

Here is an example: for $n = 2$, 11111111 into $4$ parts has the following $3^2 = 9$ decompositions:

1.111.1.111
1.111.11.11
1.111.111.1
11.11.1.111
11.11.11.11
11.11.111.1
111.1.1.111
111.1.11.11
111.1.111.1

Again, this includes only those decompositions with a . after every block of $4$ characters, so there are actually more than $3^n$ total. But maybe you get the idea of why it blows up exponentially.


$\lambda$-calculus, is there encoding of for or while? In $\lambda$-calculus, we can encode arithmetic, numbers, booleans, and even compute factorials of numbers, as shown here.

Is there encoding of "for" or "while"?

Sure! Let me show how to encode FOR using an example.

Suppose we want to translate a simple factorial FOR program

x := 1
for i := 1 to N do
   x := x * i

We rewrite it as

x := 1
i := 1
repeat N times
   x := x*i
   i := i+1

then we put all the variables we use in a tuple (a pair suffices, here)

(x,i) := (1,1)
repeat N times
   (x,i) := (x*i, i+1)

This effectively applies the function $\lambda\langle x,i \rangle. \langle x*i , i+1 \rangle$ to the initial pair $\langle 1,1 \rangle$ for $N$ times.

Since $N$ can be represented as a Church numeral, we get

$$
N (\lambda\langle x,i \rangle. \langle x*i , i+1 \rangle) \langle 1,1 \rangle
$$

The above syntax uses a few things beyond the plain lambda calculus. Numbers and arithmetic can be made precise using Church numerals. Pairs also have their own Church encoding:

$$
\langle x,y \rangle \equiv \lambda k.kxy
\qquad
\lambda \langle x,y \rangle . M \equiv \lambda z. M\{zT/x, zF/y\}
$$
where $z$ is a fresh variable, $T = \lambda ab.a$ and $F = \lambda ab.b$.

If you have more than two variables, you can generalize the above encoding to tuples, or simply represent tuples as nested pairs.

WHILE is best dealt with using recursion: instead of

while p(x,i) do
   (x,i) := f(x,i)

where p is a predicate and f is some (partial) function, we can use something like

def recFun(x,i):
   if p(x,i):
      return recFun(f(x,i))
   else:
      return (x,i)

In the lambda calculus, recursion is obtained using a fixed point combinator, e.g. Church's $Y$ or Turing's $\Theta$. We get something like

$$
Y (\lambda r . \lambda \langle x,i \rangle . {\sf if}\ p x i\ {\sf then }\ r(f \langle x,i \rangle)\ {\sf else}\ \langle x,i \rangle)
$$

where ${\sf if}\ b\ {\sf then }\ t\ {\sf else}\ e \equiv b t e$ assuming booleans are Church encoded.

Also note that WHILE is (strictly) more powerful than FOR. Every FOR can be encoded as a WHILE, so this encoding technique can also be used for FOR.


Which graph algorithm should I use? I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time complexity the most important.
I think BFS is the solution. But am not sure.

What I am doing is mapping database tables into a graph data structure. And I need the shortest path for querying the tables with joins. Am storing information in the edges related to the nature of the relationship between the tables, like foreign key field and type of relation (one2many, one2one, etc).

Do you have any sort of distance-heuristic?  If not, then yes, BFS is likely your best choice.


Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$? I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe formula, there is a spigot algorithm for quickly computing in terms of any natural number $n$ expressed in binary the $n^{th}$ binary digit of $\pi$ after the decimal place in polynomial time. Combining information from the Wikipedia articles Computational complexity of mathematical operations and Fürer's algorithm, I figured out that there exists an algorithm that computes every digit of $\pi$ in order within the time $O(n (log(n))^2 2^{(2 log * n)})$ where $log*n$ is the super root of $n$ to the base 10. I also think that according to this answer, there is an algorithm that for any natural number $n$ computes with the binary notation of $n$ as input, the $n^{th}$ binary digit of $\pi$ after the decimal place in time $O(n^3(log(n))^3)$ of the number of binary digits of $n$.

I believe both of those algorithms have a decimal analogue. If so, it seems that using the Spigot algorithm for each decimal digit of $\pi$ one at a time is slower than doing other algorithm for computing all of the digits. You might be wondering how it's possible to compute it faster than can be done by using any Spigot algorithm on each digit one at a time. Because the faster method of computation keeps some of the statements it previously computed and uses it to shorten the length of time it takes to compute the next digit to less time than it would have taken using the spigot algorithm. My question is not "Is the asymptotically fastest way to compute all the decimal digits of $\pi$ in order faster than the method of computing all its decimal digits by using the asymptotically fastest spigot algorithm for $\pi$ for each digit one at a time in order?" The reason is because I haven't thought of a proof that an asymptotically fastest algorithm for either task even exists. Here are my 2 questions:

Is there an algorithm for computing all the decimal digits of $\pi$ that's asymptotically faster than every method by finding a spigot algorithm for a single decimal digit of $\pi$ and using it on every digit one at a time in order?
If not, then is the fastest way to grow a copy of all the decimal digits of $\pi$ up to a certain point bigger and bigger on Earth to use such a spigot algorithm.

In the real world, computers are a certain size so the spigot algorithm might save memory so it might be faster to do it using the spigot algorithm for that reason. On the other hand, the faster method might only require an amount of memory that varies as the log of the number of digits that have so far been computed.

The real meaning of question 2 is quite complex and depends on what people consider feasible to build so I can't figure out a way to explain really clearly what I mean by it, but I believe that even after showing that the answer to question 1 is no, it's still not easy to figure out whether the answer to question 2 is yes or no.

There is no known method to calculate individual decimal digits of pi quickly. And fast methods for calculating the first n digits of pi in base b are considerably faster than using a method to calculate the k-th digit n times.


Dividing 2 integers with some constraints This a problem i came across while practicing binary search. Here is the problem:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store
      integers within the 32-bit signed integer range: [−2^31,  2^31 − 1]. For
      the purpose of this problem, assume that your function returns 2^31 − 1
      when the division result overflows.

A Brute force Solution is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error.

How to solve the problem efficiently or using Binary Search ??

Also provide the time complexity as well.

Here is a strategy (I will only consider positive numbers):
Let $d$ be the dividend and $x$ be the divisor. Generate all values $x_i = 2^i x$, up to some some $x_k$ such that $x_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x_{0} = x$ and, for $i \ge 1$, $x_i = x_{i-1} + x_{i-1}$.
Similarly, generate all values $b_i = 2^i$ for $i=0, \dots, k$.

Let $r$ be a variable that will hold the result. Initially $r=0$. For $i=k$ down to $0$ do the following:

Check whether $x_i$ is bigger than $d$;
If that is the case, then you know that, by subtracting $x_i$ from $d$, you are effectively subtracting $x$ from $d$ a total of $b_i = 2^i$ times. Update $d = d- x_i$, and $r = r + b_i$.

Finally, return $r$.

This strategy requires only a logarithmic number of operations w.r.t. $d/x$ (up to multiplicative and additive constants). Since this is at most $2^{31}$, the time needed is always upper bounded by a constant.

As an example, let's divide $62$ by $3$.
The sequences of values $x_i$ will be:
$x_0 = 3, x_1 = 6, x_2 = 12, x_3 = 24, x_4 = x_k = 48$, since $x_5 = 96 > 62$.
The corresponding values $b_i$ are: $b_0 = 1, b_1=2, b_2=4, b_3=8, b_4=16$.

Initially $d=62$, $x=3$, $r=0$.
In the fist iteration ($i=k=4$) we have  $62 = d \ge  48 = x_4 $, and we update: $d = 62 - x_4 = 62-48 = 14$, and $r = 0 + b_4 = 0 + 16 = 16$.
In the second iteration ($i=3$) we do nothing since $d = 14 \not\ge 24 = x_3$.
In the third iteration ($i=2$) we have $d = 14 \ge 12 = x_2$, and we update $d = 14 - x_2 = 14 - 12 = 2$, and $r = 16 + b_2 = 16 + 4 = 20$.
In the forth iteration ($i=1$) we do nothing since $d = 2 \not\ge 6 = x_1$.
In the fifth and final iteration ($i=0$) we do nothing since $d = 2 \not\ge 3 = x_0$.

In the end we have $r=20$ and $d=2$. Indeed: $62 = 3 \cdot 20 + 2$.


How does selection sort sort? I've found the following algorithm for selection sort on the internet.

program SelectionSort(input,output);
var
  A : Array[1..80] of Integer;
  n, i, j, k, m, loc, temp : Integer;
begin
  writeln('size of the array?');
  read(n);

  for i := 1 to n do
   read(A[i]);

  for k := 1 to n - 1 do
   begin
    m := A[k];
    loc := k;
     for j := k + 1 to n do
      begin
       if m > A[j] then
        begin
         m := A[j];
         loc := A[j];
         loc := j;
        end;
      end;
     temp := A[k];
     A[k] := A[loc];
     A[loc] := temp;
   end;

  for i := 1 to n do
   begin
    writeln(A[i] : 3);
   end;

  readln();
  readln();
end.

I'd like to gain a better understanding of how it actually does the sorting. Could someone please help me with this?

Neither the code you have nor the Wikipedia article highlight the concept of selection sort. Therefore, consider this (functional) pseudocode:

def selection-sort []         = []
|   selection-sort x::xs as l =
      let m = min l
      in
        m::(selection-sort (delete m l))
      end;

Here the idea is more clear

    $\ \ $1. Select the minimum from the list and delete it.
  $\ \ $2. Sort the remainder recursively.
  $\ \ $3. Prepend the minimum.

 The same works the other way around with the maximum, obviously.

Iterative code on arrays works slightly differently -- but the idea remains the same.


DNF to CNF conversion: Easy or Hard In relation to the thread Proving that the conversion from CNF to DNF is NP-Hard (and a related Math thread):

How about the other direction, from DNF to CNF?  Is it easy or hard?

On Page 2 of this paper, they seem to hint that both directions are equally hard when they say "We are interested in the maximal blow-up of size when switching from the CNF representation to the DNF representation (or vice versa)".

But DNF-SAT is in P and CNF-SAT is NP-complete.  So given a DNF expression $\phi_1$, there should be an equisatisfiable CNF expression $\phi_2$ whose length is polynomial in the length of $\phi_1$. And the $\phi_1 \to \phi_2$ conversion can be done in poly time.  Is this correct?

Edit: Changed equivalent to equisatisfiable (that is, additional variables are allowed in $\phi_2$).

If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform.  The resulting CNF formula will be equisatisfiable with the original DNF formula: the CNF formula will be satisfiable if and only if the original DNF formula was satisfiable.  See also https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF.

If you don't want to allow introduction of additional variables, converting from DNF to CNF form is co-NP-hard.  In particular, testing whether a DNF formula is a tautology is co-NP-hard.  However, testing whether a CNF formula is a tautology can be done in polynomial time (you just check separately whether every clause is a tautology, which is easy as each clause is a disjunction of literals).  Therefore, if you could convert from DNF form to CNF form in polynomial time, without introducing new variables, then you would obtain a polynomial-time algorithm for testing whether a DNF formula is a tautology -- something which seems unlikely, given that we expect P is not equal to co-NP.  Or, to put it another way, converting from DNF to CNF form without introducing additional variables is co-NP-hard.

This is the difference between equivalence vs equisatisfiability.  Equivalence requires the two formulas to have the same set of solutions (and thus does not allow introducing additional variables).  Equisatisfiability only requires that either both formulas are satisfiable or both are unsatisfiable (and thus does allow introducing additional variables).


When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$ Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges."  and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$".  Then why do even use $ |E| = \Theta (|V|^2)$?, understand that $\Theta$ is the correct(tightest) bound in asymptomatic notation.  It seems to me that $|E| = \Theta (|V|^2)$ can never happen, so why do we use it?

You're absolutely right that $\Theta$ is the tightest asymptotic bound. But it's still asymptotic, and that means that we don't care about constant factors or terms of lower degree: when $n$ (or $v$ or whatever) gets big enough, the smaller terms become negligible.

In this case, $\frac{v(v-1)}{2} = \frac{1}{2} v^2 + \frac{-1}{2} v$. So removing the constant factors and lower terms leaves us with $v^2$.


Why are some programming languages Turing complete but lack some abilities of other languages? I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that calls 'printf' with the exact same arguments that it got, and instead has to call an alternate version that take a variadic object. This is very problematic since I want to be able to make an object that hold an anonymous hook.

So, I thought that this was weird since Forth, JavaScript, and perhaps a plethora of other languages can do this very easily without having to resort to assembly language/machine code. Since other languages can do this so easily, does that mean that the class of problems that each programming language can solve actually varies by language, even though these languages are all Turing complete?

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it.

This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features commonly found in modern languages.

Turing completeness tells nothing about having types, built in arrays/integers/dictionaries, input/output capabilities, network access, multithreading, dynamic allocation, ...

Just because Java does not have feature X (say, macros, higher-rank types, or dependent types), it does not suddenly stop being Turing complete.

Turing completeness and language expressiveness are two different notions.


What do we do instead of DFS on directed graphs? All the example of DFS I've seen so far are for undirected graph.
In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable.

The algorithm I'm talking about :
https://en.wikipedia.org/wiki/Depth-first_search

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

Example :

So let's say I start with '1' I will never access 4,5,6 with this algorithm.

For directed graph it looks like we have to know all the vertex and iterate through them.

And so we cannot use a DFS for directed graph ?

Is there a DFS variant or another algorithm ?

DFS suffers from the same problem in undirected graphs: if your graph is not connected, then starting DFS with an initial vertex $v$ will only explore the connected component of $v$. In a similar fashion, if the graph is directed, then DFS will only explore the vertices reachable from $v$.

The solution is the same in both cases: loop over all vertices, and start DFS with each of the vertices functioning as the initial vertex. If you skip vertices which you have already discovered, then the resulting algorithm will still run in linear time.


Proof that $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT Consider the Independent Dominating Set problem with a directed graph $G=(V,E)$ as instance and the properties that:

$\forall (u,v) \in E, \{u,v\}\nsubseteq S$
$\forall v \in V: v \in S \lor \exists (u,v) \in E: u \in S$

then consider the function $f$ which is a many-one reduction from IDS to SAT for $G$:
$$f(G)= \bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v) \land \bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$$

Theorem: $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

Proof:

"$\Leftarrow$": Assume that $f(G)$ is a yes-instance of SAT:

Consider the propositional atoms $x_u$ and $x_v$ which represent the vertices of an edge. $x$ is $true$ iff is is in $S$. To proof a CNF-formula true we have to proof all conjuncted subformulas true.

Now consider since $\bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v)$ holds and tells us that only one of the vertices $u,v$ is allowed to be in $S$ at the same time, this implies $\forall (u,v) \in E, \{u,v\}\nsubseteq S$.

For the second part we know that $\bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$ only evaluates to true if either $v \in S$ or any $u \in S$ which is connected by an edge to $v$. This implies $\forall v\in V: v \in S \lor \exists(u,v) \in E: u \in S$.

Therefore we are done.

Is my proof for "$\Leftarrow$" of the theorem correct?

Assumption: The proof is correct and the reduction is valid:

Now we know that IDS is NP-hard, for completeness of IDS we still have to show NP-membership of IDS, right? Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

Yes, your proof of $\Rightarrow$ is correct, but note that you still have to prove the second direction to complete the reduction.

  Now we know that IDS is NP-hard

Unfortunately, we don't. We'd need a reduction from SAT to IDS and not the other way around.
To convince yourself of why it makes sense, a reduction from $A$ to $B$ means that if we had an algorithm that solves $B$, we could use it to trivially solve $A$. So, in your case - if we had an algorithm that solves SAT we would be able to solve IDS, but that's not what we want to show. We want to claim that if we could solve IDS then we could solve SAT, which means IDS is "at least as hard as SAT".

Also, notice that you need a karp reduction and not just a  many-one reduction. That is, a many-one reduction which can be computed in polynomial time (your reduction achieves that)

  Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

Correct.
Assuming we have provided a karp reduction from SAT to IDS, or equivalently - we proved that $\text{SAT}\le_p \text{IDS}$, then all we know is that IDS is NP-hard, and we need to prove that $\text{IDS} \in \text{NP}$ to get that IDS is NP-complete.


How to maximize the profit In CLRS , under the section "Maximum sub array problem", there is a problem to maximize the profit in the stock exchange. The problem is.. given an array A[1..n] and we have to find i and j such that i < j and A[j] - A[i] should be maximum. the solution given is O(n^2) . But I have a solution which does it in O(n) . I know it should be wrong , But I cant find a single counter example to my solution.

My solution :

(i) Find the maximun and minimum in A[1..n] . Let A[x] be the maximum and A[y] be the minimum.

(ii) And find minimum in A[1..x] . Let that be A[u].

(iii)Find maximum in A[y..n] . Let that be A[v].

(iV) Answer = Max{(A[x]-A[u]),(A[v]-A[y])}

What am I doing wrong?

Counter example

Consider the array $A=[5,2,3,4,1]$, where $n=5$.

(i) Then $A[1]=5$ is the maximum and $x=1$, $A[5]=1$ is the minimum and $y=5$.

(ii) And find minimum in $A[1 .. x] = A[1 .. 1]=A[1]$ which is $5$. So, $u=1$.

(iii) Find maximum in $A[y..n] = A[5..5]= A[5]$ which is $1$. So, $v=5$.

(iv)  Answer is $$\max(A[x]-A[u]),(A[v]-A[y]) = \max(A[1]-A[1], A[5]- A[5])= \max(0,0)=0$$

But the maximum profit is $A[4] - A[2] = 2$.

$O(n)$ solution

The idea is to start with two pointers $i=1$ and $j=2$ and at each step increase $j$ by one. At each step check if the difference $A[j] - A[j]$ is greater than the maximum profit. If it is then update the maximum profit. But if $A[i] > A[j]$ (in which case $A[j] - A[j]$ is negative and max profit is not updated) then we make $i$ point to the same location $j$ points to, since if for some $k > j$, $A[k] - A[i]$ is greater than the current maximum profit then $A[k] - A[j] > A[k] - A[i] > maxprofit$.

Set $i=1$, $j=2$, $maxprofit=0$
If $A[j] - A[i] > maxprofit$ then set $maxprofit = A[j] - A[i]$
If $A[i] > A[j]$ then set $i = j$
$j = j + 1$
If $j>n$ return $maxprofit$
Goto 2


Create an order from several incomplete orders Here is the motivation and how it should behave, but I need a help how to implement it.

I have several (typically) incomplete orders given as ordered values, for ex.:
1. A, C, D
2. D, E
3. X, B
4. B, C
5. C, F
6. C, A

and the resulting order should be:
A, X, B, C, D, E, F or A, X, B, C, F, D, E or A, X, B, C, D, F, E

The idea behind it is sort the result based on first seen order. I will try explain it on the example in steps:
order A, C, D
D, E - D seen, so add E after D, so order A, C, D, E
X, B - no value seen yet, so we can not determine the order now, so create 2nd temporary order X, B
B, C - C already seen, so order A, B, C, D, E
and 2nd order can be merged via B, so A, X, B, C, D, E
C, F - C see, so order A, X, B, C, D, E, F
C, A - ignore, both values are part of already defined order (by first incomplete order A, C, D)

But what if an additional incomplete order F, D or F, E will be part (added to the end) of the input? The step-by-step mental algorithm will fail - F was already placed.

How can the idea be implemented, any idea?

I will answer the following question:

  Given a list of partial orders, how can we find a total order compatible with all of them, if any?

Form a directed graph on the ground set by putting an edge $a \to b$ if $a$ immediately precedes $b$ in one of the partial orders. If this graph contains any directed cycles, then there is no solution. Otherwise, we can find a solution by performing a topological sort.


Do quantum logic gates work differently than traditional logic gates? In a traditional computer calculations are done with logic gates that check inputs with AND gates etc. But in a quantum computer, are calculations performed differently since the qubit can be in states other than 1 or 0?
I understand that qubits can have values other than 1 and 0, however, before it is used as input into a logic gate, does the qubit need to be observed and defined as either a 1 or a 0? Or is the logic gates used in a quantum computer fundamentally different from a traditional computer?

In layman's terms, the answer is yes: quantum gates are quite different from classical gates.

One reason is that quantum gates must be reversible. This practically means that AND gates don't even exist in the quantum world (at least, not in the same sense of a classical AND gate). Instead, there is a different set of gates (e.g., CNOT, TOFFOLI, FREDKIN, etc.) that allow to do all that is possible by quantum computing, without breaking the reversibility condition.

The other issue is what you hint in your question. Qubits can be "both in 0 and 1", and the quantum gate must take care of this. But this is not a problem, it just means that the output must be a superposition of 0 and 1.
For instance, let's take a simple NOT gate. If the input is a "superposition" of 30% 0 and 70% 1, then the output becomes 70% of 0 and 30% of 1. Of course this is a very superficial explanation, and quite inaccurate, but the idea is exactly that.

Finally, no measurement is done in gates, unless the gate is a measurement gate (also, measurement is not reversible, so it cannot happen in "standard" gates)

For more information, check

https://en.wikipedia.org/wiki/Quantum_gate
https://en.wikipedia.org/wiki/Reversible_computing


Best sort method for median: median heap or insertion sort on a vector I'm trying to decide between two methods of calculating a median, that will optimize the following operations:

Add integer to data structure (insert)
Get the median of all integer (getMedian)

The program will add a random number of integers (no limit on how many, but generally going to be relatively small amount) to the data structure before trying to access the median, and then repeat this process an indefinite amount of times.

With the median heap method, insert will take O(log(n)) on average and getMedian will be O(1).

What I'm wondering is what would happen if instead I simply used a vector. Insert would be amortized O(1). Then when getMedian is called, the vector is sorted with insertion sort, followed by simply accessing the middle element, O(1).

Would this be faster in the long run? There will almost always be more calls to insert than getMedian in the program, but I'm not sure if the insertion sort will be faster. I believe it is a relatively fast sort, O(n), on a partially sorted array, but I'm not sure.

For instance, if I had a vector with 100 million integers that were sorted followed by 4 unsorted elements, would insertion sort be O(n)? What if I had 50 million unsorted elements (very unlikely in the program, but possible)? And at how many unsorted elements would it be better to use another sort, like quicksort?

You are asking many questions, and I will only answer two of them. If you have a sorted vector of length $n$ followed by $m$ unsorted elements, the best way to sort the entire vector is to use an $O(m\log m)$ sorting algorithm on the tail, and then merge the two sorted lists in $O(n+m)$. The total running time is $O(n+m\log m)$, which is $O(n)$ if $m = O(n/\log n)$. If $m = \omega(n/\log n)$ then the problem is more complicated; asymptotically optimal bounds are known in the decision tree model, but I'm not sure they can be implemented efficiently enough (see for example Kahn ad Kim, Entropy and Sorting).

Another question, which you haven't actually asked, is about lower bounds. Suppose that you have a data structure in which insert takes (amortized) time $\alpha(n)$ and median takes (amortized) time $\beta(n)$, where $n$ is the number of elements in the structure. Suppose further that $\alpha(O(n)) = O(\alpha(n))$ and $\beta(O(n)) = O(\beta(n))$, and that $\alpha,\beta$ are monotone (this is the case for functions of the type $\Theta(n^s\log^t n)$). Then $\alpha(n) + \beta(n) = \Omega(\log n)$, assuming the operations are implemented using the comparison model (two datums can be compared, but are otherwise completely opaque).

For the proof, here is how to sort a list of length $n$. First insert the list. Then, extract the median, add $-\infty$ (or the minimum value) twice, and repeat. You recover the sorted lower half of the list. Now add enough copies of $+\infty$ (or the maximum value), and recover similarly the upper half of the list. This requires at most $O(n\alpha(O(n)) + n\beta(O(n))) = O(n(\alpha(n)+\beta(n)))$. In the comparison model, there is a lower bound of $\Omega(n\log n)$, so $\alpha(n) + \beta(n) = \Omega(\log n)$.


Machine Learning: Identify Patterns in Time-Series Data I work in renewable energy. My company gathers a lot of data from equipment. This typically includes process data (such as transformer temperature, line voltages, currents, etc.) and discrete alarms (e.g. breaker trip, inverter alarm values, transformer over temperature alarm). This is a rough example of what our data looks like (to be read as lines of csv):

timestamp, tag, value
5/25/2016 14:30:01, INVERTER_1.VOLTAGE_DC,
249.5
5/25/2016 14:30:06, INVERTER_1.VOLTAGE_DC, 250.1
5/25/2016 14:45:02, TRANSFORMER_1.TEMP_ALARM, 0
5/25/2016 14:45:15, TRANSFORMER_1.TEMP_ALARM, 1

I'd like to start performing some pattern analysis on this data at rest, not real-time (at least for now). I believe what I'd like to attempt is unsupervised feature learning, but I'm not entirely sure. It would be nice (I think) to apply machine learning to 1) identify any patterns that aren't obvious and 2) allow an algorithm to identify signatures of patterns in the data (e.g. all inverters on a single feeder lose communications when a breaker is open).

My initial question: Is this considered time-series data? In my research so far it seems that time-series data is referencing data that is a function of time. For most of my data, as a domain expert, I don't believe that defining functions for my data is useful for this analysis. Also, in my research, it seems as though time-series data refers to real-valued values and not discrete.

Any comments or relevant references would be helpful.

Yes, your data is "time-series data", since it's a sequence of measurements of the same variable collected over time. Time-series data can be collected continuously or at discrete intervals.

Your sample data can be expressed as a function of time - maybe it helps to think of the "function" as the process that produces the measured output, the input to the function is the date/time stamp, and the output is the value of that parameter at that time:

$\text{INVERTER_1.VOLTAGE_DC}( \text{5/25/2016 14:30:01} ) = 249.5$

You don't necessarily need to define the (general) function(s) that produce your data to perform time-series analysis - it's enough to know the value of the function at your measurement times. The range of time-series data can be continuous & real-valued, discrete, or even non-numeric.

It's certainly possible to use machine learning techniques on time-series data, e.g. for forecasting, anomaly detection, or pattern identification.

Neural nets might be a good choice if you're interested in predictive modeling. One possible setup is to use the current parameter measurements as input to the neural net, and the output is the predicted future value or "state of the system" (e.g., whether a breaker is open or not).

WEKA is a good open-source machine-learning toolkit that contains implementations of many different ML algorithms.


For any non-trivial $A,B$, finding a language which both are polynomially reducible to Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct:
a. There is a language $C$ such that $A\leq_pC$ and $B\leq_pC$.
[..]
c. There is a language $C$ such that $C\leq_pA$ and $C\leq_pB$.

According to two different sources I've seen the correct answer seems to be (a), which is exactly why I'm trying to understand two things:

Why is (a) a correct answer? Taking two languages in $EXP$, for example, I do not see why it's obvious they are polynomially reducible to each other.

Why is (c) not a correct answer? Taking a language $C\in P$ since $A$ and $B$ are not trivial there are some $a\in A, a'\notin A$ and $b\in B, b'\notin B$, and therefore given a polynomial TM $M$ deciding $C$ I can define a reduction $f$ to $A$ by $f(x)=a$ if  $M(x)$ accepts and $f(x)=a'$ otherwise and similarly for $B$, so it seems to me that (c) is a correct answer.

Part (a) is correct since you can take the language
$$ C = \{ 0x : x \in A \} \cup \{ 1y : y \in B \}. $$
Here $0x$ is the concatenation of the strings 0 and $x$. This part works even when $A,B$ are trivial.

Part (c) is correct by taking $C = \emptyset$ and using $A,B \neq \Sigma^*$, for example.


How do modern Operating Systems detect process starvation? So first off do the modern operating systems like windows and linux have a method for detecting starvation? if not, why? and if they do, then how are they going to detect starvation of a process? (this was a question in our exam)

my take was this so correct me if this is not good or not possible:

i said we should implement a linked list of waiting processes (that are waiting for a resource or etc) then we periodically run a function(using interrupts) which checks this list and we have a variable for each process and we increase that everytime, when it reaches certain point then we would know its starving(but i still dont know how to know this "certain point")

so is this correct? if so then how can we know this "certain point"? ( I suppose one way is just look at the statistic of average waiting time of processes and do a little math?)

if not, what is your solution?

Inline with @chi 's comment;  lets say process "x" gets starved in linux or windows, then for example if we are in the windows, wouldn't we get an error message saying the process "x" is not responding? Approximately no.

Now let's assume we want to detect process "x",before starvation nor aging;we have to read it's  arrival time, burst time,process id, priority from the text file and calculate the average waiting time and show the central processing unit utilization of each cycle,for instance;

Time 1 process X arrives

Time 2 process X runs

Time  3 process B arrives

Time 4 process X finishes..........,randomly.

Hope this can give you a little bit of insight.


Grammar still ambigous after removing left recursion LL(1) I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion:

S -> a b S
S -> S a b
S -> c d
S -> a d

in production number 2  there is left recursion which I removed and I got:

S -> a b S F
S -> c d F
S -> a d F
F -> a b F | EPSILON

But it is still ambigous?

Removing left-recursion from a grammar does not make it unambiguous. That's not the intent of removing left-recursion, and an ambiguous grammar is likely to still be ambiguous after left-recursion is removed.

In the case of your grammar, you have two productions which are inevitably ambiguous:

S → a b S
S → S a b

The first production allows an S to start with a sequence of a b, while the second production allows an S to end with such a sequence. However, nothing in the grammar specifies which of these two things takes priority. Since the order of grammar rules is unspecified, there are an exponential number of possible parses; although you might consider all the parses to be semantically equal, the parser needs to produce a single unique parse tree.

The solution, therefore, is to be clear about which parse tree to produce, which can be done fairly simply by creating a new outer production which handles one or the other of the alternatives. So, depending on your preference about associativity, you might use:

S' → S' a b
S' → S
S → a b S

or

S' → a b S'
S' → S
S → S a b

Alternatively, you could define a new non-terminal which just represents a sequence of a b:

S' → A S A
A → A a b
A → ε

In all cases, you should only consider removing left-recursion if you propose to use an LL parser. And if you plan on using an LL parser with only one token of lookahead, you'll have to deal with the prediction conflict resulting from the other rule for S which begins with a (by left-factoring, for example).


How do Context Sensitive Grammar systems work? The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result such as 'aaaaabbbbbccccc'.
What I (think I) understand so far:

CDG == CSG (context sensitive grammar)
Linear bounded automata are a form of Turing machine
Pushdown automata are related in function to a computing stack
CSG uses linear bounded automata to find and replace portions of text or language
The above automata result in stacks that should be worked through sort of like code
Steps in the stack are called productions
A production is basically a substitution rule
Productions go opposite the expected direction, pasting the text after the arrow in place of the text before the arrow
The automata apparently iterate through until the first step is met, and then works through the automata stack until it is done

What I know I do NOT understand:
(I don't expect these questions to be answered - they are only included for detail why I can't seem to solve The Quest)

Is the stack iterated over to produce multiple repetitions?
For example, having some programming experience I expect that to produce a result for The Quest I could start with abc and end with aaaabbbbcccc by creating [if ... then] style statements like:
 a → aa
 b → bb
 c → cc

If starting with {abc} then the above might produce {aabbcc}, iterated again to produce {aaabbbccc}, and again to produce {aaaabbbbcccc}

Can production replacements happen while skipping above productions? In the above attempted solution, I would not expect to skip a step or do them out of order, but steps 3 and 4 on the wiki appear to be doing exactly that.

Can infinite loops result? In comparing the above example to the wiki example, it would seem to me that completing the first step would cause an infinite loop in which 'a' repeats indefinitely because the first 'a' is converted to 'aa', then the second 'a' that now exists needs the rule to be applied and so on resulting in a → aaaaa∞.

I have been researching for hours, and all searches thus far have resulted in only complicated answers that assume I already have a deep understanding of language processing. I find it ironic that Chomsky's system for describing how language works is apparently so difficult to communicate.
In short, I need programmer syntax to explain how automata stacks should be laid out in order to solve The Quest. Thank you for reading.

Your understanding of Linear Bounded Automata is incorrect.  These automata are NOT derived from Pushdown Automata - there is no 'stack' in them.  A closer understanding would be that LBA are a special, 'truncated' form of Turing Machine, in which the size of the tape is restricted to being linearly-proportional to the size of the input string (actually, with a large enough alphabet, the tape space can be limited to -just- the space taken by the input string).
Also, the grammar-expansion behavior described in (1) is more closely analogous to a Lindenmyer System, which is not quite the same as a CSG (in which only one substitution takes place at any one step, so (3) isn't a concern).


Is there a clear line between algorithmic problem and an algorithmic problem instance? E.g. the algorithmic problem of sorting:
 input: sequence of some objects;
output: reordering of sequences such that some relation works for each next element of a sequence.

Right? So what's the instance of a problem?

So instance could be:
 input type: integers; relation in the output: $\geq$.

or instance is some specific input:
like $\{1, 2, 3\}$; plus some relation, e.g. $\geq$.

It looks like there is a problem, then like instance, and then kind of sub-instance.

Also, for example, sorting such that relation is $\ge$ vs $\le$ is it two different algorithmic problems? Or two different instances of the same algorithmic problem?

Also if input data is numbers vs input data is strings, is it two different algorithmic problems or two instance of the same algorithmic problem?

Yes, there is a clear distinction. A problem is a general computational task; an instance is an input to that task.

The confusion in your examples is because you need to make a decision about what the task is and, correspondingly, what the input is. For any fixed domain $D$ and fixed comparison relation $\sqsubseteq$ on that domain, sorting elements of $D$ according to $\sqsubseteq$ is a problem. The instances of this problem are sequences of elements of $D$. For example, the problem of sorting natural numbers according to $\leq$ is a problem, whose instances are sequences of natural numbers. The problem of sorting natural numbers according to $\geq$ is a different problem, though its instances are also sequences of natural numbers.

Alternatively, one could make the comparison operator a part of the input. Now, the problem is to sort elements of some fixed domain $D$ using the given comparison operator, and an instance consists of a sequence of elements of $D$ and a comparison operator. However, it's not clear how you'd specify the comparison operator, which is a binary relation on $D$, which could be an infinite amount of data. One option might be to have a list of allowed choices so, e.g., choice 1 means sort according to $\leq$, choice 2 means sort according to $\geq$, etc.


Euler cycles in biconnected components If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?

Yes.  If you start with a Euler cycle for the graph and restrict to a biconnected component, then what you have is still a cycle on the biconnected component (basically, if the euler cycle leaves vertex v in the biconnected component, then you know it must return to the biconnected component through v, otherwise we could enlarge our biconnected component - contradicting its maximality).


Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation? I am following CLRS for studying Amortized analysis with potential function and there I came through the following :

Let a data structure go through states : $D_0 $ $D_1$ $D_2$ $ ....$ $D_n$ while applying operations  $O_1$ $O_2$ $O_3$ $....$ $O_{n-1}$

$\therefore$ the amortized cost can be written as :

$\hat c(O_i) =  c(O_i) + \phi (D_{i+1}) - \phi (D_{i})$ .

My doubt is that if the state of data structure changes from $D_{i}$  to $ D_{i+1}$ that will be due to that cost of $i^{th} $operation which must be equal to the change in potential of the data structure.

So isn't  $c(O_i) = \phi (D_{i+1}) - \phi (D_{i})$ ? If not, they why are they not equal ?

Is the potential difference between two states, the overwork (credit) we are doing? If this  statement is true, is it the reason for the answer for my doubt to be false?

The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is $C$, and that we want to show that the amortized cost is only $\hat{C}$. What we do is define quantities $\phi(D_i)$ that satisfy the following axioms:

$\phi(D_0) = 0$.
$\phi(D_n) \geq 0$ for all $n \geq 0$.
$\hat{c}(O_i) := c(O_i) + \phi(D_{i+1}) - \phi(D_i) \leq \hat{C}$.

We then have, for all $n \geq 0$,
$$
\begin{align*}
n \hat{C} &\geq \hat{c}(O_1) + \cdots + \hat{c}(O_n) \\ &= c(O_1) + \cdots + c(O_n) + \phi(D_{n+1}) - \phi(D_0) \\ &\geq c(O_1) + \cdots + c(O_n) \, .
\end{align*}
$$
In other words, the amortized cost of each operation is at most $\hat{C}$.

If we define $\phi$ via $c(O_i) = \phi(D_{i+1}) - \phi(D_i)$, then we are really defining some other fictitious quantity. A better choice from the point of view of the analysis above would actually be $\phi(D_i) = 0$, which allows us to recover the bound $C$. The general idea is that we want the fictitious potential function $\phi$ to generally be "small", but sometimes we allow it to grow (we "borrow") so that we can later on take the cost of a costly operation.

Here is a very simple example. Consider a data structure with a single operation in which operation $2^i$ costs $2^i$, and other operations cost $1$. A priori, the worst-case cost is infinite. However, suppose that we define $\phi(D_n) = 2n - 2^k$, where $2^{k-1} < n \leq 2^k$, that is, $2^k$ is the smallest power of $2$ above or at $n$ (and $\phi(D_0) = 0$). Since $n > 2^{k-1}$, when $n > 0$ we indeed have $\phi(D_n) = 2(n-2^{k-1}) > 0$.

When $2^{j-1} < i < 2^j$, we have
$$
\hat{c}(O_i) = 1 + [2(i+1) - 2^j] - [2i - 2^j] = 3.
$$
In this case we are "borrowing", since $\hat{c}(O_i) > c(O_i)$.

When $i = 1$, we get $\hat{c}(O_1) = 1 + [2 - 1] - [4 - 2] = 0$.

When $i = 2^j > 1$, we have
$$
\hat{c}(O_{2^j}) = 2^j + [2(2^j+1)-2^{j+1}] - [2(2^j)-2^j] = 2.
$$
In this case the potential collapses from $2(2^j) - 2^j = 2^j$ to $2(2^j+1) - 2^{j+1} = 2$, allowing us to "pay" for the costly operation $2^j$.

We conclude that the amortized cost per operation is at most $3$.


In control flow graphs, what is the difference between a path and a branch? I'm studying for an exam on software testing and in my notes I found this:

Many more paths than branches. A pragmatic compromise will be needed

I cannot understand the difference between paths and branches; each time I work out the paths and branches of a graph I end up with the same number. Thanks!

I do not know the exact definitions used by your class, so I am saying this with caution. A branch normally correspnds to a graph edge that allows control to pass from one node to another in the graph. A path is a succession of edges connected to each other, with possible repetition and representing the successive parts traversed by the control. So a branch will be a element of the program structure, a static entity. The path represent a fragment of computation.

If you say more about what you understood, I may be able to tell you whether it makes sense.


What is an array that can be iterated circularly an infinite amount of times called? I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.

The answer is circular buffer.
Such structure could be implemented using array or linked list, but you cannot call explicit array-based circular buffer as linked-list.

FSA cannot be "executed" infinitely (type 3 machine only uses fixed input and reads it ones), unless your FSA definition covers Turing Machines.


Is address bus size same as physical address size and is that the same as word size? I am having some confusion between address bus size, physical address size and word size however (I do understand that unit of memory access is word and when word size is one byte then it's known as byte-addressable).

Is address bus size same as physical address size

No, not necessarily. Especially with modern 64 bit address bus sizes, it is quite common that CPUs do not actually support 64 bit physical addresses.
For example, the first AMD64 CPUs had 40 bit physical addresses, the current ones have 48 bit. In fact, due to the Page Table Entry format, physical addresses cannot be larger than 52 bit.

and is that the same as word size?

No, not necessarily. It makes stuff easier, but there have been architectures where the bus was half the word size, and you had to transmit a word in two bus cycles. Conversely, it is also possible to have the bus width be an integer multiple of the word size, making it possible to transmit multiple words per bus cycle.
Just as an example: the IBM 704, one of the most famous computers of all time (both FORTRAN and LISP were first implemented for the IBM 704, the trajectory data for Gemini and Apollo was computed on one) has 36 bit words but 15 bit addresses.


Compiler - Why is the grammar not suitable for shift-reduce Consider this example:

stmt => if (expr) stmt | if (expr) stmt else stmt | other

Why can't we use shift-reduce on this?

This is a compiler homework and I really need to answer it.

The grammar is ambiguous, so no deterministic parsing technique will be able to handle it. The parsing techniques called "shift-reduce" are all deterministic.


Can data be compressed to size smaller than Shannon data compression limit? I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of this method is to encode the file as the characters presented in the file, their frequencies and the index of these characters permutation represented by the file.

These documents may help explaining this method:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

However, in the first document I've read that by using this method they could compress some text to less than the Shannon limit (They didn't consider the space needed to save the frequency of the characters and the space needed to save the meta data of the file). I thought about it and I found that this method won't be very efficient for very small files but on the other hand it may work well with large files. Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by $log_2$ of the reciprocal of the probability.

So I have some questions:

Does this compression method really compresses files to smaller than the Shannon limit?
Is there any compression algorithm that compresses files to less than the Shannon limit (the answer to this question as far as I know is no)?
Can a compression method that compresses files to smaller than the Shannon limit ever exist?
If combinatorial encoding really compresses files beyond the Shannon limit, isn't it possible to compress the file again and again until we reach the file size we want?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability.

Herein lies the crux. The Shannon limit is not some universal property of a string of text. It is the property of a string of text plus a model that provides (possibly context-dependent) probabilities of symbols. It tells us how well that model could compress the text, assuming the model is accurate.

If you use one model to compute the Shannon limit and then a different model to compress, if the second model is more accurate you can beat the original Shannon limit you had computed, but that's not really relevant.


Shortest path in a weighted graph with coloured edges I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of different colour I have to pay an additional fee equal to $K$. Given two vertices $A$ and $B$, I want to find the shortest path between them.

For example, given a multigraph with 3 vertices, $K = 5$, and 3 edges: ($1\rightarrow 2$ of weight 3 and colour 1), ($1\rightarrow 2$ of weight 5 and colour 2), ($2\rightarrow 3$ of weight 2 and colour 2), weight of the shortest path is 12.

I would like to design an algorithm that would solve this problem in reasonable time. My first idea was to use Dijkstra's algorithm and for every vertex store an information about the edge from which I went into that vertex, but that strategy won't work for the example given above. So I don't have any other idea than brute-force search.

Constraints:

$N \leq 10^5$
$M \leq 10^5$
$K \leq 10^5$

Replace each vertex $x$ by $C$ vertices $(x,c)$, where $C$ is the number of colors (actually you only need the colors that appear in edges adjacent to $x$), and connect these vertices by edges of weight $K$. Replace an edge $(x,y)$ of weight $w$ and color $c$ by an edge $((x,c),(y,c))$ of weight $w$.

You can now solve your problem by running Dijkstra's algorithm on the new graph $C^2$ times. You can optimize this approach so that you only need to run Dijkstra's algorithm once by adding two new vertices $A,B$ and connecting $A$ to the vertices $(A,c)$ with directed edges, and similarly connecting the vertices $(B,c)$ to $B$ with directed edges.


Why is it so difficult to eliminate dead loops? I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the code revealed that it would obviously terminate.

Investigating this further, I found it was extremely easy to write very short programs for which basically every major compiler will emit a bunch of dead code. (Side note - it's worse when using a C++ compiler - AFAIU 'forward progress' is guaranteed so even infinite loops should be able to be removed!)

// when m <= 0 this will never enter the loop, so will terminate
// when n >= m, j will be incremented each time through the loop until
// j == m, so the loop will terminate
void naught(int n, int m) {
    int i = 0, j = 0;
    while(j < m) {
        if (i < n) {
            i++;
            j++;
        }
    }
}

// each two loop iterations the value of i gets incremented by 3, and
// then decremented by 1. eventually it will be greater than or equal
// to the value of n and so the loop will terminate. We can ignore
// overflow since it is undefined; a language with unbounded integer
// types would also terminate.
void zip(int n) {
    int i=0;
    while (i < n) {
        if (i % 2 == 0)
            i += 3;
        else
            i--;
    }
}

// each time through the loop the value of i is increased; so it will
// terminate. same comments about undefined behaviour / unbounded types
// apply here
void nothing(int n) {
    int i=2;
    while (i < n) {
        i *= i;
    }
}

// on the first iteration through the loop i becomes equal to n + 1,
// so it will terminate. ditto on undef / unbounded
void zilch(int n) {
    int i=0;
    while (i < n) {
        i += (n / (i + 1)) + 1;
    }
}

// if i <= 0 we never enter the loop. otherwise, on the first iteration,
// i gets divided by i + 1 which equals zero from rounding.
// ditto on undef / unbounded
void nada(int n) {
    int i=n;
    while (i > 0) {
        i /= i + 1;
    }
}

Is there some fundamental reason that compilers fail in these simple cases? This lack of optimization does not seem to be compiler-specific, or language specific, so I thought it might be because of lack of research (hence posting here). Has there been much research in this area? When a compiler sees the snippets above, what are the obstacles in its way that prevent it from removing the code?

To my human brain, the "obvious" thing to do would be to work out where the loops terminate and where not, and replace the entire thing with a simple if statement. If optimizing for C++, I would immediately remove all the loops since forward progress is guaranteed. Why can't the compiler do the same?

Edit:

Maybe I should have been more clear in my question; I am aware that the problem is undecidable in general, but to me these seem like relatively "easy" examples (especially in a C++ compiler, where AFAIU they should all be able to be removed). Optimization in general is an undecidable problem but it has not stopped optimizers from being written. I am interested whether there has been any research in this area.

The conceptual problem here is that dead code elimination is not computable. That is, we know that there is no algorithm that can remove all instances of dead code.

Of course, tools can be created that recognize some instances of dead code and remove them. Which patterns to look for is a matter of taste and skill of the tool creator; it's better to be conservative and err on the site of not breaking things. Language semantics play a huge role as well. I don't think there are overarching conceptual issues there, but I could be wrong.

There may be language-specific subtleties at work that prevent elimination of apparently dead code. For instance, a Java compiler can never remove a private method that is never called from within the class -- it can be executed using reflection. Such special cases are beyond the scope of this site, and best discussed one by one on Stack Overflow.

In the end, I expect there to be trade-offs (as there always are): how much time do you spend on developing the optimizer, how much time do you spend during compilation, for what gain? Maybe an optimization that often creates more efficient code occasionally creates some dead code, which you are willing to accept.


Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$? Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined.

The question is definitely aiming towards a Min-heap/AVL tree solution, which can in fact achieve $O(n\log(k))$ time complexity.

However i'm wondering if there exists a different approach, like a merge variant which can achieve the same result.

The closest I've seen is to merge all the arrays into one array which disregards their given ascending order, than doing comparison-based sort which takes $O(n\log(n))$ but not quite $O(n\log(k))$.

Is there an algorithm variant which can achieve this result? Or a different data-structure?

For the sake of avoiding dealing with rounding in the analysis, assume for simplicity that $k$ is a power of $2$ (if it is not, you can add $d \le k-1$ dummy arrays with one $+\infty$ element each, and ignore the last $d$ elements in the final sorted vector).

You can merge your arrays two by two in a binary-tree fashion: the algorithm works in $\log k$ phases. In phase $i=0, \dots , \log k - 1$ there are $k/2^i$ sorted arrays, where the arrays of phase $0$ are the $k$ input arrays. These arrays are arbitrarily grouped into $k/2^{i+1}$ pairs and each pair is merged. The resulting arrays are moved to the next phase.
At the end of the $(\log k - 1)$-th phase there is only one sorted array $A$ remaining. Return $A$.

The total amount of work on each phase (a level of the tree) is $O(n)$, and the number of phases (i.e., levels) is $O(\log k)$.


MIS complexity in cubic triangle-free graphs The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the question Independent set on cubic triangle-free graphs, it is claimed that a more general problem - maximum independent set in triangle-free cubic graphs (not necessarily planar) - is NP-complete. Could you please provide a reference to the paper for that result?
(Note that the answer to the first of the mentioned questions provides a paper where MIS is shown to be NP-hard in triangle-free planar graphs with vertices of degree <= 3, and I am asking for 3-regular graphs.)
Update: There has appeared a new answer in there since, and it addresses this question as well. The note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.

The paper "The Vertex-Disjoint Triangles Problem" (http://link.springer.com/chapter/10.1007/10692760_3) by Guruswami et al. has the proof of its NP-completeness as Theorem 3.
Update: As stated in a more recent answer to Complexity of Independent Set on Triangle-Free Planar Cubic Graphs, there is a note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara that contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.