Who first introduced the pushdown automaton? I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble finding a source that first introduces pushdown automata. Who first developed them, and what was the context?

Ginsburg (in his book The Mathematical Theory of Context-Free Languages, McGraw-Hill, 1966) states in the Historical References (Section 2.7, page 81):

  Pushdown acceptors were first formalized by Chomsky [Ch5] and Evey
  [Ev], although the notion of a pushdown tape has been used since 1954.

[Ch5] N.Chomsky, context-free grammars and pushdown storage, MIT Res. Lab. Electron. Quart. Prog. Rept. 65, 1962.

[Ev] R.J.Evey, The theory and applications of pushdown store machines, Mathematical Linguistics and Automatic Translation, Harvard Univ. Computation Lab. Rept. NSF-IO, May, 1963.

The context can be read from the Preface of the same book.

  The concept of a context-free language was first introduced by Chomsky
  in 1959 in an attempt to find a reasonable mathematical model of
  natural language such as English, French, etc. In the period
  1959-1960, several papers developing the theory were written. In the
  late 1960, it was discovered that the "ALGOL-like" languages, that is,
  the languages defined by Backus normal  form (the metalanguage used to
  describe the widely publicized programming language ALGOL-60), where
  identical with the context-free languages.  Since then, there has been
  a flurry of activity in the theoretical development of context-free
  languages. Much of this work has been done by those concerned either
  with natural languages in connection with computers, or with
  programming languages. The remainder has been by mathematicians and
  logicians intrigued by the inherent problems, techniques, and results.
  This activity has been given birth to a number of theoretical results
  of concern to computer science, and especially to programming
  technology. For example, we have the characterization of a
  context-free language in terms of a pushdown acceptor (a device used
  in the parsing aspect of compiling). [...]


Is Loop Invariant Proof a form of Induction? As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a theoretical difference?

Good question. I think yes, a loop invariant proof implies induction. However, it also deals with the termination step which is outside of the scope of induction. So a loop invariant contains an induction proof, but goes beyond that, and so an induction proof does not do all that a loop invariant proof does.

  (1) Here, showing that the invariant holds before the first iteration is like the
  base case, and showing that the invariant holds from iteration to iteration
  is like the inductive step.


Does transforming a CFG to Chomsky normal form make it unambiguous? Does transforming a CFG to Chomsky normal form make it unambiguous?
And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?

There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky normal form, so transforming a CFG to Chomsky normal form doesn't necessarily make it unambiguous. For the same reason there is no technique to convert an arbitrary context-free grammar to one which in unambiguous.

Deciding whether a given context-free grammar is ambiguous, or whether a given context-free grammar generates an inherently ambiguous language, is undecidable. This doesn't necessarily mean that there is no procedure that converts any context-free grammar into an unambiguous one given that the language isn't inherently unambiguous, but it does make the existence of such an algorithm somewhat doubtful.


DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$ How do we find all equivalence classes of $\mathsf{R_L}$ for a language?

Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$.

Here's an example they give us in the book
http://books.google.com/books?id=VEHYzv0GHt8C&pg=PA73&lpg=PA73&dq=ding+du+example+2.51&source=bl&ots=P8gAls0z7f&sig=HIsMb7rcD3hKZHYzi8fYZsyrLQ8&hl=en&sa=X&ei=5N0nUfSoJ6We2gWOv4HYDQ&ved=0CDMQ6AEwAA

ps
The relation $\mathsf{R_L}$ is an equivalent relation.
$\mathsf{R_L}$ on $\Sigma^* as:$
$xRy$ iff $(\forall w)[xw \in \mathsf{L} \Leftrightarrow yw \in \mathsf{L}]$

You may want to look at Sipser's "Theory of Computation" for a full explanation.
Technically, you must first define the problem. What do you mean by "find the equivalence classes"? You probably mean that you want to find a representative of each class, or to find an algorithm that given a word, classifies it to a class.

Probably the easiest way to do so, is to construct a DFA for the language, and then minimize it. By the correctness proof of minimization, the states of the minimal DFA correspond to the equivalence classes.

EDIT: The example in the book doesn't show you how to find the equivalence classes algorithmically. It just shows an example of finding them based on intuition and clever thinking (as you would do with a general mathematical problem). There is no general way to do that.

What the example demonstrates is that if you find these classes, then you can construct a minimal DFA. The interesting point is that the converse is also true.


byte addressing memory and 32 bit bus Say I have total 4 bytes on 1 byte addressable memory, with a 32 bit bus.

If I move value at 0'th address to one of the registers will system grab all 32 bits (all 4 bytes) through bus from memory, reprocess it to extract 0'th address value behind the scenes?

Or will it get exactly one byte through bus?

It really depends on the hardware, the memory type, ...

Usually, for memory accesses, reading extra data have no side effect so a CPU may read 32bits and use a multiplexer to extract the byte from the correct data lane.

There are still some signals that indicates the width of accesses and which byte is actually read, because some addresses may be mapped to I/O ports, and reading an I/O port can have side effects.

It can also be used to optimize access times : Imagine a 32bits CPU connected to a bridge component as an interface to a 8bits NOR FLASH (for example some boot BIOS). The bridge should check which bytes are needed to minimize the number of accesses to the FLASH chip.


How many ways to find a sum totalling n using only certain Integers? Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n?

Clarification: The Integers are arbitrary, positive, and may not include 1.

At first I thought it was the coin changing problem without pennies, but it's not because the order is important so coin changing will always be less.

It's also like Leonardo's Leaps but with arbitrary leap sizes, and again possibly without a leap of 1.

This is NP-hard, by reduction from the partition problem.

Consider the decision problem version of your problem: given $S,n$, is there at least one way to reach a sum of $n$ using the integers from $S$ (possibly multiple times).

Suppose I have a partition instance, a set $T$ where I want to know whether it can be partitioned into $T_1,T_2$ such that the sum of $T_1$ equals the sum of $T_2$.  Let $c$ be a very large constant, and define $S=\{t+c : t \in T\}$ and $n=(m+|T|c)/2$ where $m$ is the sum of all of the numbers in $T$.

Then the answer to the decision problem is yes if and only if the answer to the original partition problem was yes.

You should be able to fill in the details from here (including, in particular, how to choose the constant $c$, based upon $T$).

See also https://cstheory.stackexchange.com/q/19758/5038.

Of course, the problem may still be easy for many $S$; there may even be infinite easy subclasses.  See also Dealing with intractability: NP-complete problems for more on strategies for what to do, when you have a problem that is NP-hard but you still have to solve it.


Proving the language which consists of all strings in some language is the same length as some string in another language is regular So I've been scratching my head over this problem for a couple of days now.  Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose length is equal to some string in $B$ is a regular language.

In equation form:

$$L = \{x \in A \mid \exists y \in B \text{ s.t. } |x| = |y| \}$$

My initial thought was to try and come up with some DFA for both languages $A$ and $B$ and map the two states to each other and hopefully get a 1:1 ratio that way I can generate a new DFA which proves that $L$ is regular.  But then I realized that $A$ and $B$ don't have to be over the same set of symbols.

I think the correct way to solve this is to use the closure properties of regular language, but I'm not sure of how to begin/use the properties for "lengths" of strings instead of strings themselves.

Could someone point me in the right direction?

Remember (or come up with) the proof for

$\qquad \displaystyle L_1, L_2 \in \mathsf{REG} \implies L_1 \cap L_2 \in \mathsf{REG}$.

Do you see how to modify the proof for your setting?

   Abstracting the equality of lengths thing, come up with a construction for an automaton for

 $\qquad \displaystyle L_l = \{ w \in \Sigma^* \mid \exists x \in L.\, |x|=|w|\}$

 for given, arbitrary $L \in \mathsf{REG}$ over $\Sigma$.

Do you see the connection?

   Now note that $L = A \cap B_l$.


Given many partial orders, check them for consistency and report any that are not consistent Inputs. I am given a finite set $S$ of symbols.  I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything.

I am also given a collection of assertions.  Each assertion takes the form $s_1<s_2<\cdots<s_m$, where $s_1,\dots,s_m$ form a subset of the symbols of $S$.  The assertion probably won't mention all of the symbols of $S$, just a subset.  Each assertion will probably cover a different subset.

Warmup problem. The starter problem is: Given $n$ assertions, identify whether they are all internally self-consistent, i.e., whether there exists a total order on $S$ that is consistent with all of the assertions, and if so, output an example of such a total order.

The real problem. In practice, a few assertions might be faulty.  Almost all of them should be correct, though.  So, the real problem is: if the assertions are not all internally self-consistent, find a minimal subset of assertions to label as "probably-erroneous", such that if you remove the probably-erroneous assertions, the remainder are all self-consistent.

What I know. I know how to solve the warmup problem (just compute the transitive closure of the union of the partial orders given by each assertion, and check that the result is antisymmetric; or, in other words, create a graph with $S$ as vertex set and an edge $s\to t$ if $s<t$ appears in any assertion, then check for cycles).  However, I don't know how to solve the real problem.  Any ideas?

Real-world parameters. In the application domain where I've run into this, $S$ might have up to a few hundred symbols, and I might have up to a few thousand assertions, with each assertion typically mentioning dozens of symbols.

This sounds like weighted FAS (Feedback Arc Set).  Find a minimal (weight) feedback arc set in a directed graph and report the assertions that contributed to the wrongly directed arcs.

For each pair of symbols s and t, there is an arc saying how many assertions have s < t and how many assertions have t < s.

This is a known NP-complete problem.

On a different note, your problem is a classic social choice problem where each of the "assertions" are votes.


Usage of master theorem for solving recursions I know that master theorem is used for the recurrence relations of the form:

T(n) = aT(n/b) + f(n)

But in my question, i am supposed to solve the following recurrence relation by using master theorem:

T(n) = 2T(n/7) + 5T(n/8) + n

Can i take f(n)=n and since f(n)=Θ(nlogba), i say T(n) is O(nlogn)? But if i do this, i neglect the fact that the relation must be of the form T(n) = aT(n/b) + f(n). What should i do? Thanks

You may solve this recurrence by using the Akra-Bazzi method, which generalizes the master theorem and allows solving recurrences of the form

$T(n)= \sum\limits_{i = 1}^k {a_i T(n/b_i) + f(n)}$

You need to solve for $p$ the equation

$\sum\limits_{i = 1}^k {a_i b_i^{-p} = 1}$

and the solution to the recurrence can be obtained exactly as in the master theorem, but you must compare $f(n)$ with $n^p$ instead of $n^{\lg_b a}$.

For your recurrence, $p = 0.954101 \quad$ so that $f(n) = n \quad $ dominates $n^p = n^{0.954101}$ and therefore, $T(n) = O(n) \quad$ (you may want to verify that the master theorem regularity condition also holds).

Akra and Bazzi also proved a more general result.


Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.

I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:

$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\
\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$

For already-in-a-superposition qubit, it would be just some linear transformation.

$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$

But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.

  A Hadamard transformation is applied to each bit to obtain the state

Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.

What the equation is doing above appears to indicate that if $n$ is 2, we would get

$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?

[Update]

As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\left|10\right\rangle$. Since we are working with two-state system here I figured out that the 2 and 3 should be converted into binary in this context. And therefore the expression should be interpreted as

$$\frac{1}{\sqrt{2^{3}}} (\left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}(\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} (\left|10\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} (\left|11\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

It appears that things are making a lot more sense now. But as I take a deeper look into the expression above, two questions come to me:

Why do I see so many $\left|0\right\rangle - \left|1\right\rangle$ but not a single $\left|0\right\rangle + \left|1\right\rangle$ ? (Intuitively I expect to see just one $\left|0\right\rangle - \left|1\right\rangle$ since we can only get $\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2}$ when it is in the state of $ \left|1\right\rangle$ and there is only one qubit in $ \left|1\right\rangle$).
Why are there only $2^{n}$ possible states with each having the chance of $(\sqrt{2^{3}})^2$ when the input is $2^n+1$ qubits? Adding four $(\sqrt{2^{3}})^2$ together doesn't give us 1.

After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself).

Apparently, this is how the expression in the Wikipedia page is derived:

$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$

Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.

$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.


Maximum value of arbitrage I'm trying to solve this from The Algorithm Design Manual:

  6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75×2×0.7=1.05 U.S. dollars---a profit of 5%. Suppose that there are n currencies c1,...,cn and an n×n table R of exchange rates, such that one unit of currency ci buys R[i,j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of R[c1,ci1]⋅R[ci1,ci2]⋯R[cik−1,cik]⋅R[cik,c1] Hint: think all-pairs shortest path.

My understanding is this is asking to find the longest simple cycle (LSC) on a directed weighted (complete?) graph. There is a reduction from longest simple path to LSC, so this would be NP-hard. It seems strange that the problem gives a hint, so maybe it's asking something else?.

The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value.

If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the simple cycle with the maximum sum of the logarithms of the weights, which is indeed the NP-hard Longest Simple Cycle problem.

Usually, these arbitrage questions ask to find a cycle with positive return, if one exists. This can be done by negating the logarithms of the weights and checking for negative cycles. This question asks for the best cycle, though.


An O(n log sqrt(n)) sorting algorithm? Skiena TADM 2nd Question 4-28 Skiena writes:

  In one of my research papers [Ski88], I discovered a comparison-based sorting
  algorithm that runs in $O(n\log\sqrt{n})$. Given the existence of an $\Omega(n \log n)$ lower bound for sorting, how can this be possible?

I believe the research paper he is referring to is Encroaching lists as a measure of presortedness, and the $O(n\log\sqrt{n})$ algorithm is Melsort.  I don't have the full text of the article, but the abstract states that melsort has [time] complexity $O(n\log m)$, where $m$ is the number of "encroaching lists" present in the input and $n$ is (presumably) the size of the input.

I suspect that the solution to Skiena's apparent paradox hinges on expected running time vs worst case running time.  He notes in the abstract of the '88 paper that melsort is "linear for well ordered sets and reduces to mergesort and $O(n\log{n})$ in the worst case."  If the expected number of encroaching lists, $m$, is $\sqrt{n}$ (as apparently conjectured by Skiena, according to wolfram's article on encroaching lists), it would follow that melsort's expected runtime is $O(n\log\sqrt{n})$.

But wikipedia states that "A comparison sort must have an average-case lower bound of $\Omega(n \log n)$ comparison operations," citing Cormen et al.  Checking the referenced pages of Introduction to Algorithms, I see only a proof that the worst-case runtime has that bound. Is the Wikipedia article incorrect?

Azzo is correct.  It's very simple:

$n\log \sqrt{n} = n\log n^{\frac{1}{2}} = \frac{1}{2}n\log n = \Omega (n\log n)$

Therefore Skiena's $O(n\log\sqrt{n})$ sorting algorithm does not violate the lower bound on comparison sorts.


How do I normalize a push down automaton? Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does this mean that there must be two separate transitions to push the * and then pop the *? Or is it normalized as is? Is it okay to have multiple transitions from a single state to another, some of which pop, and some of which push?

What do you call a normalized PDA? There are many ways to specify
that. Also, a PDA is defined by its transition fonction. The diagram
is just a convenient graphical way to do that, as long as it is
precise and easily read.

For the example you give, a transition is not represented by a
directed edge, but by a directed edge together with a label. If you
have an edge with two labels, as in your loop on $q_1$, that
represents two transitions. Trying to do it with two separate loop
edges would only make your diagram less readable.

Now, it is possible that your instructor has defined "normalized
diagrams" in some way, and you should try to follow his wishes.  But I
do not remember of any such normalization of PDA diagrams with real
technical importance.

Yes it is OK to have multiple transitions from one state to
another. You could avoid it by introducing new intermediate states,
but that would serve absolutely no purpose other than making your life
miserable.


Shortest even path that goes through a vertex Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \{s,t\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least once) and is of even length (regarding number of edges).

We need to find such a path that is  the shortest in $O(V+E)$ time.

I thought about BFS from $s$ to find a shortest path to $d$, and BFS from $d$ to find shortest path to $t$, but then it wouldn't necessarily be of even length.
Plus, such a path we're looking for is not necessarily simple.

Any hints?

Your remark is true: there might be no simple even path from $s$ to $t$, an even path perhaps includes a cycle of odd length.

The shortest path from $s$ to $t$ via $d$ is the shortest path from $s$ to $d$ plus the shortest path from there to $t$.

To compute even length paths you might consider turning the graph into a bipartite graph using two copies of itself. Double $V$ by adding a copy $V'$. Now duplicate every edge $(x,y)$ into $(x,y')$  and $(x',y)$, where the primes indicate copies in $V'$.
Now the shortest path from $s$ to $t$ will be of even length. (And all paths of even length in the original graph are 'represented' in the new graph.)

Problem: the intermediate node $d$ might be $d'$, its copy in $V'$. Your turn to connect the two requirements 'via $d$' and 'even length'.


Need help trying to figure out DFA Can anyone please help me try to understand what will the state diagram look like for this question:

Let $L = \{x_0y_0z_0x_1y_1z_1\ldots x_{n-1}y_{n-1}z_{n-1} \mid \exists n,x,y,z \, x+y=z \land x=\sum_{j=0}^{n-1} x_j2^j \land y=\sum_{j=0}^{n-1} y_j2^j \land z=\sum_{j=0}^{n-1} z_j2^j \land \forall i \, x_i,y_i,z_i \in \{0,1\}\}.$ Show that $L$ is regular. It is sufficient to draw a state diagram.
Try to design your state diagram in a systematic way. Arrange your states in 3 columns (with 1 exception), such that before reading the $j$th bit you are in column $j$. If at this time, the DFA has to remember 2 bits, you could draw the states in lexicographical order of these 2 bits.

Any help is much appreciated. I've spent more than an hour just trying to understand the question and still could not figure it out.

The alphabet for this language is $\Sigma=\{0,1\}$. We also have that $x_i,y_i,z_i\in\Sigma$. So, notice that
$$\sum_{j=0}^{n-1}x_j2^j$$ is simply the decimal equivalent if we assume that the symbols of $x$ are expressed as a number in binary. Similar can be said for $y$ and $z$.
Using this, one can see that the language is effectively the those strings such that if you take every third symbol and form $x,y,z$, the numerical equivalent adds up.
For this to be true, for every $x_i,y_i$ and carry from the past additions, the corresponding $z_i$ should be the correct symbol. If it were not so, then irrespective of the future symbols, we cannot have $x+y=z$, and the string can never be accepted.
So, at each iteration, the DFA needs to remember the current values of $x_i,y_i$ and the current carry. If the corresponding $z_i$ is correct and the carry is $0$, it can return to the start state and continue, as this is not going to affect future considerations in any way. This is a final state as at any point when the DFA is in this state, the current sets of $x_i$s, $y_i$s, and $z_i$s are such that the string would be accepted.
If the value of $z_i$ is correct but the carry is not $0$, then the DFA goes to a different state corresponding to carry being $1$. This is not a final state as if the carry was $1$ at the end, it would imply that $x+y\ne z$ as $x,y,z$ must have the same number of symbols.
If the value of $z_i$ is incorrect, then the symbol at that "bit" can never be corrected in the future, and the DFA can be sent to a sink state where the string is rejected irrespective of the remaining symbols.
Using the above, the DFA I have drawn (using JFLAP) is as follows:

The first column is when $x_i,y_i,z_i$ have been received. $q_0$ corresponds to a carry of $0$ and is that start and final state. $q_7$ corresponds to a carry of $1$. The second column is the set of states when $x_i$ has been received, and the third is when $y_i$ has been received. Then, when $z_i$ is received, if it matches $z_i=x_i+y_i+\text{carry}$, the DFA goes to state $q_0$ or $q_7$ depending on the carry. Else, it goes to $q_{14}$, which is a sink.


Describing the language formed by a particular grammar G → G B ⏐ G N ⏐ ε
B  → ( E )
E  → E ( E ) ⏐ ε
N  → ( L ]
L  → L E ⏐ L (⏐ ε

For this grammar, the prompt asks to describe in  the language that this grammar describes and builds.

I got to the point of first trying at defining the language each one builds but the recursiveness of this grammar threw me off a bit.

I'm kind of stuck, thus far I tried to start with let's say N and try to describe it as generating a left paren followed by a left paren and right bracket.

I could really use some direction on where to go with this.

There doesn't appear to be a simple description for the language generated by this grammar, but here's what happens.

From $E$ we have the productions $E\rightarrow E(E)\mid\epsilon$. The first few strings generated from $E$ are:
$$\begin{align}
\epsilon &\quad E\Rightarrow\epsilon\\
(\:) &\quad E\Rightarrow E(E)\stackrel{*}{\Rightarrow}(\:)\\
(\:)(\:) &\quad E\Rightarrow E(E)\Rightarrow E(E)(E)\stackrel{*}{\Rightarrow}(\:)(\:)\\
(\:(\:)\:) &\quad E\Rightarrow E(E)\Rightarrow E(E(E))\stackrel{*}{\Rightarrow}(\:(\:)\:)
\end{align}$$
It's not too hard to show inductively that $E$ generates all and only the strings of balanced parentheses, i.e., the strings over $\{(\;,\, )\}$ that could appear in a legal arithmetic expression. Let $\mathcal{B}$ denote this language.
From the production $B\rightarrow (E)$ we see that $B\stackrel{*}{\Rightarrow}(\mathcal{B})$, namely any string of balanced parentheses enclosed in $(\,)$.
From the productions $L\rightarrow LE\mid L\:(\:\mid\epsilon$. It's not too hard to see that $L$ generates all strings over $\{E,\,\,(\,\}$. Call this language $\mathcal{L}$. In simple terms, $L$ generates all strings of balanced parentheses interleaved with an arbitrary number of left parens.
From $N\rightarrow\,(\,L\,]$ we see that, similarly to step (2), we have $N\stackrel{*}{\Rightarrow}(\,\mathcal{L}\,]$
Finally, it's not too hard to see that from the productions $G\rightarrow GB\mid GN\mid\epsilon$, that $G$ generates all strings over $\{B,N\}$, so we have that the language of this grammar will generate all strings made from the concatenation of terms of the form $(\mathcal{B})$ and $\:(\mathcal{L}\:]$ in any order.

For example, a string generated by the grammar is $((\:)(\:)((\:]\,(((\:)(\:)))$, where I've separated the $N$ and $B$ substrings for clarity.

As I said at the start, not pretty.


Does a path exist going through each color only once? I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once.

I think this problem can be formulated using network flow. Somehow a penalty can be placed on nodes of the same color that makes the flow 0 or infinity if a node is repeated.

Thanks!

I understand from your question that you are asking for a polynomial-time algorithm for solving the problem. It is unlikely there is one for the problem.

Taking the hint of @jjohn, this is exactly the same problem as in the Kleinberg-Tardos book, Exercise 8.12. They call the problem evasive path. Here, color classes represent different zones, and you must get from $s$ to $t$ visiting each zone at most once.

There are at least two straightforward reductions. The other one is from directed Hamiltonian path, and the other one from set partitioning, i.e. exact cover. If you still care about solving the problem, you can do it in $O^*(2^k)$-time, where $k$ is the number of colors.


How to tackle different sample size in the training set in SVM I have to train a SVM for a classification problem. I have some strings that are the paths in a deterministic finite automata (DFA). If the alphabet is -01-   then possible strings are 011101110  or 0110 for example. The purpose of classifier (SVM) is the correct prediction (label) of unseen strings like accepting or rejecting(label 1 or label -1, binary classification).
The problem is that the strings have different lenghts. How can I tackle this problem?

A SVM classifier requires a fixed-length feature vector, i.e., all feature vectors must have the same length.  There are multiple solutions:

Pad out the strings to fixed length.
Choose a different set of features, so that there is a fixed number of features.
Pick a fixed number $k$, and look at windows of length $k$ (i.e., substrings of length $k$).  Classify each window of length $k$ using your SVM, then combine those results somehow (e.g., majority vote).
Use a different classifier, such as a recurrent neural network (e.g., LSTM).  See also https://datascience.stackexchange.com/q/16115/8560 for more possibilities.

It's hard to say what will be most appropriate for your particular situation, without knowing more about your learning task.

Based on your subsequent comments, it sounds like you want to learn a DFA.  There's lots written on learning DFAs, using Angluin's algorithm, SAT solvers, or other methods.  Follow the link above for some entry points into the literature on that.  I don't think a SVM  is the right tool for that job -- this sounds like an XY problem.


Is there a generic way to parallelize algorithms? Take:

An algorithm $A$ that is analytically nice in some way, say, for some class of inputs of length $n$ it runs at $O(f(n))$ on some Turing machine.
$k+2$ independent, identical such machines.

Is there a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ for which tapes can be made so that:

$A_{in}$ finishes after $O(k)$ and transforms a length-$n$ input for $A$ into $k$ inputs, each to one of $A_\ell$, $\ell \in \{1,\dots, k\}.$
Each $A_\ell$ runs in $O(f(n)/k)$
$A_{out}$ runs in $O(k)$ and combines the the outputs of the $A_\ell$ into what $A$ would have produced on the input of $A_{in}$

No, there cannot be such a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ with the requested properties. The basic problem is that the requested parallel algorithm only uses a single round. (And allowing $A_{in}$ and $A_{out}$ only $O(k)$ time is very restrictive, they cannot even read length-$n$ input or write a length-$n$ output in that time.)

One simple problem which even has a parallel algorithm (but not of the form stated in the question) is the all-prefix-sums operation. Input is a list of numbers, and output is another list, whose elements are the sum of all previous elements in the original list. See section "3.2 Scans" on page 23 in

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

There are at least two possible criticisms of this answer. (1) The counter-example problem took a list of size $n$ and output a list of size $n$. Maybe the question expected the output to be much shorter than the input, like in a decision problem. (2) No explicit proof is given that the counter-example problem has no parallel algorithm of the form stated in the question.

Regarding (1), an output of length-$n$ is used to get around Barrington's theorem, as explained in a comment below the question. Regarding (2), one might look at the elements from $n/2$ to $n$ of the output. Each of them would require more than $n/2$ additions, if computed in isolation. $A_{out}$ can only output $O(k)$ of them in $O(k)$ time, so most of them must be computed in partial isolation. Hence, the algorithms $A_i$ outputting them will need more than $O(n/2)$ time.


Proof of contention of the wait-free consensus algorithm I know that this is a known theorem but I can't find its proof. The theorem is:

  The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write operations) is $n$.

Can someone link me to a proof or an explanation?

This is the classical "critical-state argument", also called "bivalence argument", used by Fischer, Lynch, and Paterson to prove the impossibility of consensus in an asynchronous message-passing system where one processor may fail.

For (wait-free) binary consensus, the critical-state argument says that there must exist a state S of the system such that both decisions are still possible starting from S, but for every immediate successor S' of S the decision is determined. Thus we can partition the processors into two teams $\Pi_0$ and $\Pi_1$ such that a step of a processor from team $\Pi_0$ from S eventually results in decision 0 while a step of a processor from team $\Pi_1$ from S eventually results in the decision 1.

Now suppose that, in S, the next step of processor $p_0$ is to modify object $O_1$, and the next step of processor $p_1$ is to modify object $O_2\neq O_1$. Wlog we can assume $p_0\in\Pi_0$ and $p_1\in\Pi_1$. Since $O_2\neq O_1$, the steps of $p_0$ and $p_1$ commute and lead to the same state S'' regardless of their order. Moreover, since $p_0\in\Pi_0$, the consensus decision from S'' is 0. However, since $p_1\in\Pi_1$, the consensus decision from S'' is also 1, which is a contradiction.

The case in which some processors are about to perform a pure read operation similarly leads to a contradiction.

We conclude that in state S, all processors are about to modify the same object. Thus in any consensus algorithm there is at least one system state in which all processors are about to modify the same object.


Superscript on complexity class? What does it mean when one complexity class has another complexity class superscript?

For example, sometimes in papers I see $P^P$ or $P^{NP}$.

It's a synthetic notation for complexity classes of oracle machines. Let $\mathcal{A}$ be a class and $L$ be a language. We define:

$$
\mathcal{A}^L
$$

to be the complexity class of the languages decidable by a machine in class $\mathcal{A}$ with access to an oracle for $L$.

If $\mathcal{A}$ and $\mathcal{B}$ are classes, we define:

$$
\mathcal{A}^\mathcal{B} = \bigcup_{L \in \mathcal{B}} \mathcal{A}^L
$$

Therefore, $\mathcal{P}^\mathcal{P}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{P}$, and $\mathcal{P}^\mathcal{NP}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{NP}$.


Why does CLRS refer to the disk parts as pages rather than blocks? I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters:

In order to amortize the time spent waiting for mechanical movements,
disks access not just one item but several at a time. Information is
divided into a number of equal-sized pages of bits that appear
consecutively within tracks, and each disk read or write is of one or
more entire pages. For a typical disk, a page might be $2^{11}$ to $2^{14}$
bytes in length. Once the read/write head is positioned correctly and
the disk has rotated to the beginning of the desired page, reading or
writing a magnetic disk is entirely electronic (aside from the
rotation of the disk), and the disk can quickly read or write large
amounts of data.

I always thought that pages are related to the virtual memory, although including swapping with the disk access. When the talk goes into the discussion of the filesystems in general, then I thought the information is divided into blocks rather than pages. Is he talking about virtual memory here? If I restate the whole paragraph in terms of blocks, would it be still correct, except for the provided sizes of the blocks?

I think you're right to be confused by this.
If their "pages" are sectors (= disk blocks), then they're right to say that pages "appear consecutively within tracks, and each disk read or write is of one or more entire pages", but their size range for pages makes no sense. The overwhelmingly most common sector size in 2009, when this textbook was published, was $2^9$ bytes. Also, I've never heard the term "page" used for a disk sector before.
If their pages are VM pages, then the size range makes more sense. But then they're wrong to suggest that the page size is a property of the disk, and it's not true that a swapped-out VM page will generally appear consecutively in a track. Also, disk reads and writes are only in units of VM pages if they come from the paging subsystem, and you shouldn't expect B-tree nodes to be paged in general (though they can be).
If their pages are clusters (filesystem allocation units), then the size range may be reasonable, but the rest is wrong. Clusters aren't generally read or written as a whole, they are just allocated as a whole. Also, I can't think of any reason to match the B-tree node size to the cluster size unless it's a filesystem B-tree (probably a directory index) and equating them simplifies the design or implementation of the file system.


Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing I'm studying the Knuth Morris Pratt pattern searching algorithm from here. I want to know the order of computing the $lps$ array in this algorithm - that is the array of longest proper prefixes that are also suffix. I studied the Wikipedia page for this algorithm and it says this part is of $O(m)$ - $m$ is the length of the pattern being searched. I just don't understand why.

Can anyone help?

I've copied below the wikipedia algorithm for computing the LPS array (which is usually called the failure function because in the main KMP algorithm you refer to this table whenver there's a failed match). They denote $T[]$ where you use $LPS[]$

  algorithm kmp_table:
      input:
          an array of characters, W (the word to be analyzed)
          an array of integers, T (the table to be filled)
      output:
          nothing (but during operation, it populates the table)

define variables:
    an integer, pos ← 1 (the current position we are computing in T)
    an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)

let T[0] ← -1

while pos < length(W) do
    if W[pos] = W[cnd] then
        let T[pos] ← T[cnd]
    else
        let T[pos] ← cnd
        let cnd ← T[cnd] (to increase performance)
        while cnd >= 0 and W[pos] <> W[cnd] do
            let cnd ← T[cnd]
    let pos ← pos + 1, cnd ← cnd + 1

let T[pos] ← cnd (only need when all word occurrences searched)

The running time will be dictated by how many times "cnd" gets assigned to. The while loop inside the for loop ($pos$) might make you think the algorithm is $O(m^2)$ but as you learned it is $O(m)$.

Inspect how $cnd$ may change during one step of the for loop; it can either increase by +1, or it can decrease inside the while loop. And when it decreases, it decreases by at least 1, since $T[]$ satisfies $T[x]<x$ for all $x$ ("proper" in the definition of LPS). Since $cnd$ can increase only by +1 and there are $m$ steps in the for loop, this means the overall increase is bounded by $+m$.  You might visualize each change to $cnd$ as a stair of integer height, with upstairs and downstairs representing increases and decreases to $cnd$; the upstairs are all height 1, and the downstairs are each height at least 1.  Because the overall height never falls below 0 (that is the termination condition for the while loop), you can bound the total number of stairs by $2m$; there are at most $m$ "up" stairs and there can't be more "down" stairs than up stairs since their height is $\geq 1$.

To put another way, this is basically a twist on the saying "what goes up most come down"; here we have "what comes down must have gone up before"


Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent? I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 .

$n$ : number of nodes in the tree

$Z_{n,k}$ : Indicator random variable that activates when rank of the root  is k

$X_n$ : random variable denoting height of BST

$Y_n$ : random variable denoting $2^{X_n}$

In the video, it is said that $Z_{n,k}$ and $max(Y_{k-1} , Y_{n-k})$ are independent events.

But how they are independent? If we have $k=1$, then the max height can go till n. And when we have $k=n/2$ , max can go till $n/2$ only. Therefore the choice made by $Z_{n,i}$ affects the possibilities for $Y_{k-1}$ and $Y_{n-k}$

I haven't watched the video, but presumably it uses the following model of random BST. You start with one element. Then you insert an element which is smaller than the existing element w.p. 1/2, and larger w.p. 1/2. Then you insert an element which is smaller than both existing elements w.p. 1/3, is between them w.p. 1/3, and larger than both w.p. 1/3. In the $n$th step, you similarly insert the new element in one of the $n$ positions, with equal probability for all.

This means that $Z_{n,k}$, which indicates whether the $n$th element got inserted in the $k$th position, is independent of anything that went on before, and in particular of $Y_1,\ldots,Y_{n-1}$.


Are there any stochastic models of non determinism in the rate of program execution? We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems.  Java & jet engines don't mix, and consequently a lot of study has gone into researching and developing real time operating systems.

Is there any research as to exactly why a traditional operating system and high level garbage collecting language can't be used?  I'm interested in any stochastic modelling that might have been done, rather than lots of words. So as a simple example, is there a mathematical model for the execution rate of say a simple FOR /NEXT loop on something like *nix + Java?  Ideally this should refer to contemporary micro processors with all their associated speculative execution, interrupt handling and other modern optimisations like memory reclamation and parallel processing.

I would also extend this reference request to any models that might try to equate the mensuration of the execution rate of such a FOR /NEXT loop, with the Observer Effect as found in quantum mechanics.

There is work on estimating the worst-case execution time for code (sometimes called WCET analysis).  You can start with the Wikipedia article on the subject and use Google Scholar to find many research papers on that topic.

However, in traditional systems, the problem is not that the running time is random (well, that's one problem, but it's not the most serious one).  The more serious one is that the running time is unpredictable.  We can't even assign a probability distribution to it -- we have no basis for doing that.

For instance, in many garbage-collected languages, response time is unpredictable and real-time operation cannot be guaranteed.  The garbage collector might kick in at any point and pause your program for a very long time.  The point where that happens is not predictable, and the amount of time it will take is also not (usefully) predictable -- we can't even assign a stochastic model to it.

We can't really call the garbage collector random, as it might be triggered by some sequence of events that is in principle deterministic but is in practice too complex to model and thus is for all engineering purposes unpredictable.  You might be tempted to say "treat the time when garbage collection happens as random and uniformly distributed", but that's not valid.  For all we know, the garbage collector might kick in at the worst possible time.  Maybe there is some code that does a bunch of stuff (e.g., creating lots of short-lived objects and then immediately destroying all references to them) that tends to trigger the garbage collector, right before some other code that does something really time-critical (e.g., update flight control surfaces).  If you modelled the time of garbage collection as random, you would fail to recognize that the flight-control code might systematically fail at a higher probability than your stochastic model predicts.  All we can safely do is assume conservatively that the garbage collector might run at the worst possible time, and take essentially forever to do its job.  That renders worst-case execution time analysis impossible or unhelpful.

Similarly comments can be made about many other elements that make running time analysis hard, such as interrupts, caches, speculative execution, and so on.


Generate scale-free networks with power-law degree distributions using Barabasi-Albert I'm trying to reproduce the synthetic networks (graphs) described in some papers.

It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree distributions, $P_A(k) ∝ k^{-λ}$".

$P_A$ is a probability distribution that returns the probability of a node having degree $k$. For instance, $P_A(2)$ indicates the probability of randomly choosing a node from the network and getting a node with degree 2.

The average degree $k$ stroke seems to be 4 in one paper, with a the minimum $k$ of 2. No word about the maximum $k$. In the other paper it is not specified. It does not seem that important to define the network.

Lambda λ values are given, as is the number of nodes $n$.
Combinations are

n = 50000, λ = 3, 2.7, 2.3, with  in a paper
n = 4000 and λ = 2.5, or n = 6000 and λ = 3 in the other paper

I looked for libraries implementing the Barabasi-Albert algorithm and they seem to require different parameters than lambda and the average degree. One is NetworkX, another is GraphStream (implementation here). They work in similar ways and ask for:

n : int - number of nodes
m : int - number of edges to attach from a new node to existing nodes; the number of edges to be added at each step

How can I calculate the settings m to generate a comparable  graph?

Here are some references:

Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
Small Cluster in Cyber Physical Systems, Huang et al. 2014
Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used "generating functions" to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Thanks.

The short answer is that you can't use that software as-is to get what you want. For a fixed $m$, the Barabasi-Albert model always has the degree distribution $P_k \sim k^{-3}$, regardless of $m$. The exact formula for the probability degree of what those pieces of software implement (which is the BA model) is

$$ P_k = \frac{2m(m+1)}{k(k+1)(k+2)}$$

The papers (with $\lambda \neq 3$) are probably talking about some kind of generalized BA model, I presume. It would help to give more details (full citations) on them.

EDIT: OK, I'll have at look at those refs. In the meantime, I've discovered there's R package called igraph that can do what you want. The relevant theory paper/cited used there is:

"Connected Components in Random Graphs with Given Expected Degree Sequences" by Fan Chung, Linyuan Lu.

It has some 400 citations in Google Scholar, so it's probably a widely used method. The later, 2009 paper cited on that R package page clearly says "SF networks contain heterogeneous degrees, and their distribution follows a power law, $P_d(k) \sim k^{-\lambda}$. To construct artificial SF networks, a stochastic model called the Chung and Lu (CL) model is used."

EDIT2: I think you have misread Huang et al. "We build synthetic random, scale-free and small-world networks using Erdos-Renyi model, Barabasi-Albert model and Watts and Strogatz model [9] respectively." It doesn't say anywhere they got BA to do any power other than 3. There's a figure caption which says "We use ‘k-n’ interdependence model to couple two synthetic scale-free networks $G_p$ and $G_c$ with the power law exponents 2.5 and 3 respectively." But that doesn't mean they used BA for those 2.5-degree graphs. There's one later figure which only says "Barabasi-Albert model is used to generate scale-free network with power law exponent 3."

EDIT3: The paper by Buldyrev et al. doesn't say anywhere they've used any BA graphs. "Simulation results for P8 as a function of p for for SF networks with $\lambda$ = 3, 2.7, 2.3". They don't say how they got those graphs. The do cite the BA papers, but only in long list of 10 papers about various random network models. The second paper of this group by Havlin et al. does indeed give on p. 5 the BA model as having an indeterminate/unspecified $\lambda$, citing the 1999 BA paper. I don't really want to call this paper wrong, but the only correct reading of it is $\lambda = 3$. Again it doesn't say how they generated their $\lambda = 2.7$ graphs from their Fig 8. I can see how reading this paper you can conclude that BA can generate such graphs... but it can't.

EDIT4: Yes, I found it now in the actual version published in Nature "For two interdependent scale-free networks2 with power-law degree distributions, $P_A(k) \sim P_B(k) / k^{-\lambda}$, we find that the existence criteria for the giant component are quite different from those in a single network." The citation is indeed misleading in the same way as in the Halvin et al., but they don't say they've used the BA process to generate the graphs. The passage can be interpreted as only a citing BA 1999 reference for what scale-free network means and/or who originated the concept. In any case, trust the math... you can find the derivation for the BA degree formula in numerous places, including BA's own paper or in more detail in a later book[let]. BA obviously understood the generality of what they observed, so they stated a law that is more general (arbitrary $\lambda$) than what their construction provides, i.e. $\lambda = 3$. As I said before, there are other methods (subsequently published by others, e.g. Chung and Lu) to get a different $\lambda$, but they are not using the BA construction, even though their graphs are correctly called scale-free too.


What goes into proving two complicated programs are equivalent? Say I wanted to prove that two programs were equivalent (either rigorously if possible, or informally if not). More specifically, say I have something relatively complex such as an HTTP server implemented in C, and one implemented in Node.js/JavaScript. What can I do in terms of saying "these two are effectively the same"? What are my options? What is possible? What is not possible?

It's been a little while since I've looked into proving program equivalence (I'm currently linked to this, but I can't read it yet haha, and it looks like it's focusing on extremely simple programs like equality checks or basic loops, whereas I'm asking about a robust HTTP server).

Essentially (I'm imagining) I want to say "these two programs in JS and C do the same thing". That "do the same thing" is obviously vague, but at the same time it means something specific. Any observable outcome on either system is generally the same, give or take. So it's like a proof, but without being a perfect proof. It's like it's a partial proof or something.

I would like to be able to say of my programs "these two implementations are equivalent for all intents and purposes". I would probably start by providing measurable guarantees or observations about performance and input/output behavior, and then write some tests, and ... I don't quite remember, somehow make statements about the system. Or should I just be thinking that "a functioning HTTP server in either language is an AXIOM". That would simplify it :) Just assume it does the same thing as one another. But that's sidestepping it feels like.

Wondering what are my options here? How far can I take this in theory? I am not concerned with how long this would take to implement or define, if it takes years, fine. I just would like to know what is possible in terms of making the statement "these two programs in C and JS are equivalent" more rigorous and nailed down. What techniques/theories/research-directions could I look into to make it possible?

Right now I am just assuming they are equal implicitly, allowing my code to call either the C function or the JS function knowing that the ~overall effect~ is the same (nebulous, I know, don't know how to pin it down). I would like to apply some math or model checking or program simulation or something to this so that I can make it more solid, if possible :)

At the other end of the spectrum is proving that 3 > 2 is equivalent in both C and JS. What am I even supposed to do in this simple case? Making that slightly more complex on it's way to a full HTTP server, copying a string in C is very different than in JavaScript, but it's a relatively simple thing. Where do I even begin to prove those "operations" equivalent between the two languages? Or if not "prove", then just "state" that they are equivalent, with some backup evidence or something, I dunno.

Here is not much, but this diagram is what I'm basically trying to do:

At a broader level, the problem seems to be similar to this.... Say I want to get a medallion. I can either go the store and buy one, or I can 3D print one. Both "algorithms" (going to the store, or 3D printing) are way different from each other, but they are effectively the same. There would be no straightforward way to step-wise prove these are equivalent operationally (from what my imagination provides), but visibly the end result is the same. How would you (even here) state this with rigor?

Formal analysis today is usually done on module or unit level. Unfortunately I'm not aware of a common metric which allows to predict if a formal analysis will be possible. Only structurally very simple codes can be formally analysed even with LOC's or cyclomatic complexities of up to a million.

In your case here the code of any of the two programs is clearly too complex for a full formal analysis:

Model-checking will not work.
A complete (bi-) simulation will not work either.

So the best practical solution I know is model-based testing. While it is not a proof still formal methods can be used. It ultimately eliminates the disaster of writing and maintaining manually written test cases.

P.S.:

A short list of steps which can be done in this case:

An abstract model of the two programs is created. This is a third implementation which will omit all unimportant details. The abstraction has the advantage that this model is simple enough again to be formally analysed. The model can be implemented in any language you like if the model analyser will analyse the byte code.
The abstract model can be traversed and e.g. a condition coverage is reached in a test suite. This step is done using a model-based-testing tool.
Finally these test cases are tested on the two programs and it is checked if the abstract model can simulate the two program implementations.
This simulation relation is of course not a proof of the equivalence.
The abstraction is a very clean specification what was taken into account in our tests and what was omitted.
Two model-based testing tools which can be recommended: Microsoft Spec Explorer, Conformiq Designer


Function that is not Space Constructible I'm reading Sipser's Introduction to the Theory of Computation, and I'm reading about space-constructible functions. He gives the following definition:

  A function $f: \mathbb{N} \to \mathbb{N}$ is space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

He follows up by saying,

  All commonly occurring functions that are at least $O(\log n)$ are space constructible, including the functions $\log_2 n$, $n \log_2 n$, and $n^2$.

My question:  What is an example of a function that is $\Omega(\log n)$ that is not space constructible?

Usually such examples are specifically "tailored", using hard problems.
Perhaps the easiest way is to take the halting problem:
$$HALT=\{\langle M\rangle: M\text{ is a TM that halts on }\epsilon\}$$
and consider the encodings of TMs as numbers, in such a way that no two numbers are encoded to the same TM (e.g. by leading 0s). This can be achieved using unary encoding, for example.

Now, consider the function $f:\mathbb{N}\to \mathbb{N}$ defined as follows:
$f(n)=2n$ if $n$ represents a TM in HALT, and $f(n)=2n+1$ otherwise.

This function is $\theta(n)$, but clearly it is not space constructible, since constructing it would enable you to solve the halting problem.

A similar example can be constructed from a problem which is harder than PSPACE (e.g. a problem complete in EXPSPACE).

However, these example are somewhat "ugly". A more elegant example is the busy beaver function, which is non-computable simply because it "grows too fast".


Global relabeling heuristic: Push-relabel maxflow I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues.

I have a specific instance of the problem here to illustrate my questions 1:

a) For this problem instance, the "current preflow" is a state that is reached by my implemented max flow algorithm [[ even without global relabeling heuristic we reach this state ]]. Without applying any heuristics the algorithm proceeds to completion from this state giving the correct result.

b) The distance labels (in green) at this state represent a valid labeling as for every (u, v) \belong to E_{residual} d_u <= d_v + 1

Q1: The distance label (or height) is supposed to be a lower bound on the distance from the sink. However for several nodes in the residual graph (eg: 6, 7) this is not true. Eg. Node 7 has a distance label of 14...but clearly has a distance of 1 from the sink in the residual graph.

Q2: On running the global relabel at this stage, we get a labeling as seen in the extreme right. From this point on (depending on how frequently you do the global update), the algorithm can get stuck [[ deadlock ]] -- eg. nodes 6, 3 keep circulating flow between them as they each get relabeled to a higher height. If you run the global update before the reach the final height, you will reset the heights and the process repeats.

I am reasonably sure I am making a very trivial error but am unable to put my finger on it. Can someone help me with this issue? I am happy to provide a code snippet if that would help.

A couple more points that may be relevant:
-> I am implementing a single phase version of the push-relabel algorithm (ie. do not stop when you have a min. cut, but continue till you obtain a valid flow).
-> I am processing active vertices in FIFO order in the current problem instance. But I have a highest label first [3] implementation as well. I do not think this affects the two questions I have.

Thank You!

[[ This question has also been posted on programmers stackexchange -- I was unsure which forum is better for this question ]]

[2] A new approach to the maximum flow problem; A.Goldberg, R.Tarjan; JACM, Vol 35. Iss 4, 1988

[3] On implementing the push-relabel method for the maximum flow problem; B.V.Cherkassky, A.Goldberg

Q1: The invariant goes the other way around: height[n1] <= height[n2] + 1 for all edges (n1,n2) in the residual graph.

As the sink (10) is not adjacent from (7) in the residual graph, the configuration height[7] == 14, height[10] == 0 is perfectly fine.

The other way around, (7) is adjacent from (10) in the residual graph, and indeed height[10] <= height[7] + 1.


What does it mean to prove that a set of binary integers is regular? I'm not exactly sure what this question is asking me to do:

  Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that recognizes it. Leading 0s are allowed. The empty string should be accepted. Briefly explain your answer.

Is this asking me to construct a DFA where the set of binary integers add up to be divisible or the number of elements is divisible?

I understand that by constructing the DFA I prove that it is regular.

The question asks you to construct a DFA for the language

$$L = \{x \in \{0,1\}^* : x \text{ is the binary representation of an integer that is divisible by three}\}.$$

In other words, the DFA should accept a string if and only if this string is the binary representation of a number that is divisible by three.


Range Query with conditions Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the index range $l$ to $N$ having key as $x$. Also, there can be updates that add a new pair to the end of the array increasing $N$. Succeeding queries consider the updated $N$. There can be multiple queries so I need to answer the query in $O(logN)$ but precomputation is allowed.

I think it might be done with a Segment Tree but I cannot see what to keep in the nodes. Is it even possible to do it with required complexity, because I feel you actually need to go to every element in the array to check it's key. Any help is appreciated.

Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position.

For example in the input array: $$[(3, 1), (2, 3), (2, 5), (1, 6), (3, 3)]$$ you would build the map:

{
    1 : {(4, 6)} // (value 6 at position 4)
    2 : {(2, 3), (3, 5)}
    3 : {(1, 1), (5, 3)}
}

Notice that with this data structure you can solve queries in vector by finding the sum in suffix. First find the corresponding vector in $O(log N)$ (possible in $O(1)$ if used unordered_map instead of map) and use lower_bound (also in $O(log N)$) to determine the target suffix. You should keep cumulative sums of the vector to calculate the sum on a suffix in $O(1)$.

To handle updates of the form add an element of the form (key, value) to the end of the original array you should only extend the vector corresponding with key in the map. You know the new position in the original array, which is greater than all previous position since it is at the end, so add the pair (new_size, value) to the end of the array associated with given key.

Notice that we must keep cumulative sum up to date, but cumulative sum up to the first $n$ values is equal to the cumulative sum up to the first $n-1$ values plus the last value. The new cumulative sum can be computed in $O(1)$.

Notice that in practice we don't need to have on each vector in the map a pair of (position, value), but instead (position, cumulative_sum).


Curry Howard correspondence and Church-Turing thesis Curry-Howard correspondence states the equivalence between logic/deduction and types/programs.

The Church-Turing thesis states the equivalence of some models of computation. Specifically, all computable functions can be written both on a Turing Machine and in Lambda Calculus.

Not all logics are equivalent however. 2nd order logic can quantify over sets whilst 1st order can't.

Can someone explain the dissonance? Can some computable functions be
expressed at a "higher-level" but not at a "simpler-level"?

[CLARIFICATION]

If I define a model for computation off say 2nd order logic whilst the Turing Machine is a model for 1st order logic, then does that mean my hypothetical language can compute "uncomputable" functions? It appears so to me because 2nd order logic is more powerful than 1st order logic. This is clearly nonsense because Haskell is based off a flavor of 2 order logic (system F with extensions) but isn't more powerful than say C: any program achievable in Haskell is achievable in C. The mapping (or equivalence) between logic and computation does not appear to preserve the notion of strength: 2nd order logic is stronger than 1st order logic but programming languages off 2nd and 1st order logic have the same strength. Does that make sense?

The only conclusion I can come to is that the relationship between logic and types is not a straightforward mapping. The Turing Machine is not based off any specific logic and that any logic/deductive system can be mapped to the Turing Machine. Can you confirm?

[CLOSING WORDS]

I think that my mistake is in not realizing that there is a large divide between the colloquial "program" and programs in the context of types.

Haskell which is based on a stronger, more expressive type system does indeed provide stronger, more expressive programs. These programs are stronger in the sense that more can be guaranteed about them (in the same sense as "type safe"). This does not mean that Haskell can "compute" more; it is still merely Turing complete.

I'm not sure where you see the dissonance.

The Church-Turing thesis is a hypothesis stating that Turing Machines (equiv. Lambda Calculus or Recursive Functions) can do anything that we'd think of as computable.

The Curry-Howard correspondence is a much stronger statement that certain types of intuitionistic logic are structurally identical to things kind of like the Lambda Calculus. It doesn't really say which logic it corresponds to, it just shows that you can map the logical constructions in a canonical way to a (typed) computational model and vice versa. If you take different logics, you get different models and vice versa. The models may or may not be Turing-complete, although if we believe the Church-Turing thesis (it does seem to be doing alright so far), if you get a model that's more powerful than a Turing Machine, then you've got something incomputable in there.

Nonetheless, the logic you deal with does limit what you can compute in the corresponding model. For example, the Calculus of Inductive Constructions, which is a type theory and the basis for Coq, only allows types that it can verify have decreasing definitions (i.e. a recursive destruction of the type will terminate), but there are perfectly computable types which it can't verify, so you're locked out of using them.


Round Robin time slice(quantum time) In all books about this topic, I read that there is a rule of thumb is that 80% of the process execution time is lower than time slice. But how do I calculate this value? I looked at every article possible and I found like nothing. Can someone help me understand this topic?

I know that there is a topic with this question click here. I have the exact same problem, but the answer from there isn't clear to me.

Thanks in advance.

The end of a time slice is costly (need to interrupt the running program, switch over to the kernel, stash away the running process context, restarting another process means loading it's context, cache contents of the processor are now useless and have to be reloaded). You want to do this hopefully only when forced (the running program does a system call, which forces a context switch anyway; a high-priority interruption arrives), but on the other hand you don't want any process to just monopolize the system by never yielding. So sometimes (i.e., by time slice end) you will force it. The "80%" rule of thumb is just that, it works (most of the time, for most workloads, and probably makes very little practical difference if it is 60% or 90%).

Take a look at e.g. Pabla's discussion of the Completely fair scheduler in Linux to get a feel of the problems to be solved. The history of Linux' schedulers is quite enlightening (and people have been reported to be sucked into hacking it, never to be seen again...)


Linear Path Optimization with Two Dependent Variables Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.

There are two runners on a line that goes from $x=0$ to $x=100$. The two runners start at $x=50$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $x$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $(40, 70)$, to successfully "complete" that coordinate, runner 1 must go to $x=40$, and runner 2 must go to $x=70$. They can't move on to the next coordinate pair until both have reached their destination.

So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $x=10$, and runner 2 is at $x=90$, it would be inefficient to chose a coordinate pair like $(80,80)$, because runner 2 would only travel $10$ units, and spend a long time waiting while runner 1 is moving $70$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.

Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?

You can consider the 1D-position of the 2 runners as one 2D-position.
X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).

Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the Tchebychev distance (infinite norm). I am pretty sure this is NP-complete.

A simple heuristic approach may be to always run to the next closest point (greedy nearest neighboor). Or you can either look for a more sophisticated one...


Why are different logarithms in the same Θ even thought their difference diverges? As I have read in book and also my prof taught me about the asymptotic notations

The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large value of $n$.

So from here my confusion is-

$2^n=O(3^n)$ and $\log_2 n=\Theta(\log_3 n)$

First relation is clear to me and second relation is confusing me.Though I derived $\log_2 n$ and $\log_3 n$ to same base and noticed that $\log_2 n=\log_{10} n/\log_{10} 2$ and $\log_3 n=\log_{10}n/\log_{10}3$. So In both constant factor can be removed. So second relation is also OK.

Still there remain a doubt that when I see the graph plot of $\log_2 n$ and $\log_3 n$, $\log_2 n$ is always above $\log_3 n$ and grows faster than $log_3 n$ i.e the difference of log values increases as n increases. Then I got more confused when I saw the graph plot of $x_1=y$ and $x_2=2y$ in which again $x_2$ is above $x_1$ and difference is increasing b/w them as $y$ increases.

So now I want to know .How do I distinguish from graph about the asymptotic relations of the function. In what sense they say one function is upper bounded by the other though 2 lines with different slopes also following this.Why don't we say one line is upper bounded by the other.We only say they are related by $\Theta$.

Please help me understand this concept.

You are missing one thing in your definition of asymptotic notation. In addition to only caring about large values of N, we also ignore constant multiplicative factors.

$f$ is $O(g)$ if there exists a large $N$ and a constant $c$ such that
$f(x) < c g(x)$ for all $x \ge N$

In the $\log_3$ vs $\log_2$ case its true that we have $\log_3 x < \log_2 x$ for all big $x$. However, its also true that

$\begin{equation*}
   \log_2 x
      = \frac{\log_3 x}{\log_2 3}
\end{equation*}$

so we can choose some $c$ larger than $\log_2 3$ to end up with:

$\begin{equation*}
    \log_2 x < c \cdot \log_3 x
\end{equation*}$

and thus $\log_2 x$ is $O(\log_3 x)$.

The same reasoning does not apply to $2^n$ and $3^n$. There is no constant multiplicative factor that will make the $2^n$ catch up to $3^n$ for all big $n$.


How does the runtime of the Ukkonen's algorithm depend on the alphabet size? I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.

Here is a citation from the book "Algorithms on strings, trees and sequences" by Dan Gusfield (section 6.5.1):

  "... the Aho-Corasick, Weiner, Ukkonen and McCreight algorithms all either require $\Theta(m|\Sigma|)$ space, or the $O(m)$ time bound should be replaced with the minimum of $O(m \log m)$ and $O(m \log|\Sigma|)$".

  [$m$ is the string length and $\Sigma$ is the size of the alphabet]

I don't understand why that is true.

Space: well, in case we represent branches out of the nodes using arrays of size $\Theta(|\Sigma|)$, then, indeed, we end up with $\Theta(m|\Sigma|)$ space usage. However, as far as I can see, it is also possible to store the branches using hash tables (say, dictionaries in Python). We would then have only $\Theta(m)$ pointers stored in all hash tables altogether (since there are $\Theta(m)$ edges in the tree), while still being able to access the children nodes in $O(1)$ time, as fast as when using arrays.
Time: as mentioned above, using hash tables allows us to access the outgoing branches of any node in $O(1)$ time. Since the Ukkonen's algorithm requires $O(m)$ operations (including accessing children nodes), the overall running time then would be also $O(m)$.

I would be very grateful to you for any hints on why I am wrong in my conclusions and why Gusfield is right about the dependence of the Ukkonen's algorithm on the alphabet.

As @jogojapan mentions in the comments, hasing generally is only amortized $O(1)$, so you would only get amortized bounds for the algorithm. However, I think you do not even get these: In order to get amortized $O(1)$ hashing, the hash tables have to be of size $\Omega(\Sigma)$, so you still have $\Theta(m\Sigma)$ space (and the same time requirement for initialization).

What's more, in practice the time for setting up all these hash tables will be much higher than the time to set up arrays.

You might fare better with using a global hash table that is indexed with (node, character)-pairs, but at least the "only amortized" argument will remain.


Using a rotation matrix to transform/shift a pinhole camera I have a pinhole camera model with the following extrinsic (in Earth Centered, Earth Fixed Coordinate, (ECEF) system) and intrinsic parameters.

focal length (x,y) = 55000 px, optical center = (2400,540)

camera center (x,y,z), (ground coordinates) = -2322996.2171387854 -3875494.0767072071 5183320.6008059494 (ECEF)

Rotation matrix (3x3, camera to ground frame)  =  [[0.88982706839551795,-0.45517069374030594 ,0.032053516353234932], [-0.44472722029994571, -0.84940151315102252, 0.28413864394171567], [-0.10210527838913171, -0.26708932778514777, -0.95824725572701552]]

I need to shift the camera so that it points to the correct position on the ground based on a ECEF transformation matrix (4 X 4), which looks like this:

[[0.99999922456661872, 0.00043965959331068635, -0.0011651461883787318,   7033.5303197340108],
[-0.00044011741039666426, 0.99999982604190574, -0.00039269946235032278     ,814.02427618065849],
[0.0011649733316053631, 0.00039321195895935108, 0.99999924411047925      ,4139.9400998316705], [0, 0, 0, 1]]

The 3 x 3 matrix portion formed by the first three rows and columns are the rotation component, the first three values in the last column is the translation component. My general understanding is that I need to add the translation component to the camera center coordinates, while multiply the camera to ground rotation matrix with the rotation component. Is this sufficient, or would I need to do something extra ?

It looks like you got it, but what's actually going on here is that you are working in homogeneous coordinates.
In this system, a point in space is represented as a 4-tuple, $(x,y,z,1)$. You can multiply this 4-tuple by any non-zero constant and it represents the same point, so this is equivalent to $(wx,wy,wz,w)$ for any $w \ne 0$.
A vector is the difference between two points, and this is represented as a 4-tuple with a zero in the fourth component, $(x,y,z,0)$.
Right-multiplying that 4x4 matrix by a point has the effect of adding the translation component, and right-multiplying by a vector has the effect of not adding the translation component.


Partitioning planar graph cycles based on chords Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that:

No sublist contains two vertices with a chord between them
The last element in each sublist is the first element in the next
Every element in each sublist is adjacent to its neighbors in the original cycle
The difference in size between the sublists is kept minimal, given constraints 1 to 3

Overall I'm not really sure if this is required to be solved using graph structures, or if it's possible to transform it into something more general.

If the original cycle has length $n$, there is a straightforward $O(n^5)$ time algorithm: simply guess which vertex each sublist should start at.

In other words, let the original cycle go through the vertices $v_1,v_2,\dots,v_n,v_1$.  Then you can choose indices $i,j,k,l$ (such that $1 \le i < j < k < l \le n$), where the first sublist contains $v_i,v_{i+1},\dots,v_j$, the second sublist contains $v_j,v_{j+1},\dots,v_k$, and so on (assuming index arithmetic wraps around modulo $n$).  There are only ${n \choose 4} \in O(n^4)$ possible choices for $i,j,k,l$, so you can exhaustively try them all and test each one to see whether it meets all your requirements, and then keep whichever one is best (according to your "difference-in-size" metric).

This proves that the problem can be solved in polynomial time.


Deterministic algorithm to find number of collisions Let $h:U \to[m]=\{0,1,\dots,m\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$

Let $D \subseteq U$ be a subset of size $n.$

I'm looking for a deterministic algorithm, efficient as possible, to find the number of collisions of $h$ on $D$

I thought to start operating $h$ on all elements in $D,$ place the results in an array and work with that, but not sure how to continue.

Any help is appreciated.

You could hash all of the elements of $D$, sort them, and then count duplicates.  Sorting brings all duplicates next to each other, so a linear scan lets you count the number of duplicates.  The running time will be $O(|D| \log |D|)$.

If you don't insist on a deterministic algorithm, you could place elements of $D$ into a hashtable, using $h$ as your hash, and then count the size of each hash bucket.  If the hash function is any good, then there is a sense in which the expected running time is $O(|D|)$ (e.g., if the elements of $D$ are random and the hash function is sufficiently good) -- but the worst case is $O(|D|^2)$.


What needs led to the implementation of ASCII codes? Prior to ASCII existing, we already had at least four number systems, namely

Binary
Decimal
Octal
Hexadecimal

So what were the needs that lead to the implementation of ASCII codes? Why was this code chosen, from a computer architecture perspective?
I have searched online, but I haven't found a satisfactory answer.

Those r "number" systems they represent just numerical values. ASCII is a standard "coding" that include characters

(encode them as digital binary number, for example "A" is represented as 65)

Think of it as a fn that maps each number/character/symbol(enter for ex. has a code that I don't remember now)  to a code number that will be represented to the computer in binary format


Complexity of a SAT related problem Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$.

Question: what is the (theoretical) complexity of this problem? Is it in DP?

Given a propositional formula $\varphi(\vec{x}, \vec{y})$, consider $\psi = \exists \vec{y} \ \forall \vec{x} \ \varphi(\vec{x}, \vec{y})$.

Let
$\Delta =
\{ y_0 \leftrightarrow \top, y_0 \leftrightarrow \bot, \ldots,
y_m \leftrightarrow \top, y_m \leftrightarrow \bot \}$.
Then $\psi$ is true iff there exists $\Gamma \subseteq \Delta$ such that $\Gamma \nvDash \bot$ and $\Gamma \vDash \varphi(\vec{x}, \vec{y})$.

Therefore the problem is $\Sigma^\mathsf{P}_2$-hard.
$\mathsf{DP} \subseteq \Delta^\mathsf{P}_2$, so unless $\mathsf{PH}$ collapses the problem is not in $\mathsf{DP}$.


Is "Query Equivalence" decidable? I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d \in Data:P_1(x) = P_2(x)$). This is easily shown with Rice's theorem.

I was wondering if a similar problem with SQL queries is solvable:

Is it possible to design an algorithm $A_D(x,y)$ which, given a fixed database schema $D$, decides if, for every possible instance of $D$, $Q_1$ and $Q_2$ return the same table $T$?

Appendix

As suggested in the comments, I'll now specify the legal operations for $Q_i$. I am talking about simple queries such as:

Simple queries with SELECT [DISTINCT] ... FROM ... WHERE
Queries with subqueries
Queries with aggregated operators
Queries with GROUP BY and HAVING
CREATE VIEW

Furthermore, let's assume our SQL is not turing complete, so no CTE or RECURSIVE are allowed.
Lastly, I mean only SELECT-like queries, no UPDATEs, INSERT INTOs, etc...

Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support *, +, and = in WHERE clauses.

Fix the schema as $k$ such integer values columns called x_1, ..., x_k.

Query equivalence in this schema is undecidable by a reduction to the satisfiability of Diophantine equations (Hilbert's 10th problem):

A system of Diophantine equations can be described as a multivariate-polynomial with integer coefficients $p(x_1, \dots, x_n) = 0$. Determining whether or not there is any tuple $(x_1, \dots, x_n) \in \mathbb{Z}^n$ that satisfies the equation is known to be an undecidable problem.

This condition can be directly represented as the WHERE clause in the SQL described above: WHERE p(x_1, ..., x_k) = 0 (expanded using * and +).

Determining whether or not SELECT * FROM t WHERE p(x_1, ..., x_k) = 0 is equivalent to SELECT * FROM t WHERE false is determining whether or not p(x_1, ..., x_k) has some assignment of integers $x_1, \dots, x_k$ such that $p(x_1, \dots, p_k) = 0$; thus if we were able to determing the equivalence of SQL queries, we would be able to determine the satisfiability of Diophantine equations.

Because the satisfiability of Diophantine equations is undecidable, so must this query equivalence problem.

The above doesn't rely on any particularly interesting features of SQL -- it certainly doesn't rely on any tricky "Turing complete" features of many SQL implementations -- it relies solely on the embedded ability to evaluate expressions involving integers. That means this is unfortunately rather unenlightening, but it also makes it hard to pare down SQL to something that won't immediately have undecidability creep in.

Like any theoretical result on decidability would, this does require arbitrary precision integers are supported. While I don't know of any popular SQL implementation that truly supports unbounded integers, PostreSQL for one documents arbitrary-precision integers that support at least 1000 digits of precision, which is likely "large enough" to say an abstract model of SQL supports unbounded integers.

It might be worth analyzing a SQL without any support for arithmetic operators like + and *, though I think it might be possible to emulate both + and * using SUM and JOINs; even without SUM I think it may be possible.


How proof of Hoffman algorithm greedy property starts with optimal tree T? In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts with tree T which has b and c at the maximum depth of tree. I can't understand why tree T is called optimal, because if x and y have smallest probabilities, then tree T cannot be optimal because Hoffman algorithm won't build such tree. I think my problem here is with understanding what optimal tree means.

If someone comes from CSLR this is about lemma 16.2 and proof to that.

A code tree is optimal if the average codeword length is minimal. This has nothing to do with Huffman's algorithm. Huffman's algorithm is guaranteed to produce an optimal code tree, but there might be other code trees. In fact, Huffman's algorithm could produce different code trees using different tie-breaking rules. Moreover, not every optimal code tree can be produced using Huffman's algorithm, even with an arbitrary tie-breaking rule.

Here is a formal definition of an optimal code tree. Let $\pi$ be a distribution. The $\pi$-cost of a code tree is the expected length of a codeword, where the expectation is taken with respect to $\pi$. A code tree is optimal for $\pi$ if its $\pi$-cost is equal to the minimum $\pi$-cost of any code tree.


Exactly why the time taken by 'memory reads', is not considered while calculating time complexity of an algorithm? I am sorry if I sound repetitive(I've asked a similar sounding question earlier - Relevance of memory reads while calculating the time complexity of an algorithm). Actually, it didn't answered my intended query. May be I framed the question inappropriately, and in an unnecessarily complex and indirect way.

In the current/present question, I am referring to the magnetic disk memory as it definitely takes much time, but if the primary memory(RAM) also does take much time relative to processing, then it can too serve the purpose here.

Also, I am specially concerned here with the algorithms where number of memory reads are some function of 'n', instead of being nearly constant(because in latter case, this question is not applicable or doesn't make sense anyway).

People don't usually refer to the hard drive as "memory" though the term "external memory" is common in this area of the literature. As far as disk accesses are concerned, they are taken into account in the analysis of algorithms that are explicitly written to access disk. Some of the more popular models are the two-level external memory model, the parallel disk model, and the cache-oblivious model. There are also hierarchical memory models. Algorithms and Data Structures for External Memory particularly chapter 2 describes the parallel disk model in detail, briefly describes other external memory models, and provides pointers into the literature. Some of these ideas and results go back about half a century.


Path in a graph with durations I have the following problem:

given

a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds) is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=[a,b]$ for some $a\in \mathbb{Q}_0^+,b\in \mathbb{Q}_0^+\cup\{+\infty\}$ and $a\leq b$,
two vertices $s,t\in V$ and
an integer $h$ encoded in binary,

we have to decide whether or not there exist

a path in $G$, possibly with repeated vertices and edges, $v_0 \cdot v_1 \cdots v_{n-1}\cdot v_n$, with $v_0=s$ and $v_n=t$ and
a list of values $d_0,\ldots,d_n\in\mathbb{Q}_0^+$,
such that $\sum_{i=0}^n d_i = h$ and for all $i=0,\ldots, n$, $d_i\in d(v_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE.
We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Is this problem in NP?

This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP,
we provide a polynomial-size certificate,
and then we show how to check it in deterministic polynomial time.

The certificate is just the following:
a set of integers $\{x_{u,v}\mid (u,v)\in E\}$.
Intuitively, $x_{u,v}$ is the number of times the solution path
traverses $(u,v)$.

We now describe the
verification algorithm.

We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}>0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.
We check whether

$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover,
$y_s := \sum_{(s,u)\in E'} x_{s,u}$.
We check whether there exist real values $z_v$, for every $v \in V$, such that

$d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
bound of the rational interval $d(v)$), and
$\sum_{v \in V} z_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify
a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4.
form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).


Why should small o notation has to satisfy the equation for all values of the constant Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the following condition exists:

f(n) = o(g(n)) means for all c > 0 there exists some $\text{n}_0$ > 0 such that
0 ≤ f(n) < cg(n) for all n ≥ $\text{n}_0$. The value of $\text{n}_0$ must not depend on n,
but may depend on c.

But for the conditions,

for all c > 0
$\text{n}_0$ may depend on c

we can simply select the value of $\text{n}_0$, based on the value of c,  so that the equation is satisfied. So why should it satisfy for all values of c ?

Consider this also (more?) common definition:

$\qquad\displaystyle f \in o(g) \quad\mathbin{:\!\!\iff}\quad \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Do you see now why we need to get below all factors $c$ in your definition? If not, we would have $f \in \Omega(g)$.


Prove, that $A^+\subseteq A^*$ where $A$ is a formal language Prove, that $A^+\subseteq A^*$, where $A$ is a formal language.

The definition of $A^+$ is $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i$,  which would be $A^1 \cup A^2 \cup \dots \cup A^i$. Likewise, $A^*$ is $\bigcup_{i\in\mathbb{N}}A^i$ and therefore $A^0 \cup A^1 \cup \dots \cup A^i$.

Suppose, $x\in A^+$. By definition $x\in A^+ \land x\in  A^*$ for all $x\neq A^0$, which is the set of the empty word. We can conclude, that $A^1\cup A^2\cup \dots \cup A^i \subseteq A^0\cup A^1\cup \dots \cup A^i$ and $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i \subseteq \bigcup_{i\in\mathbb{N}}A^i$, that's why $A^+\subseteq A^*$.

Is this "proof" ok?

It seems you have hit the reasoning correctly:
A set $S$ is a subset of another set $A$ if $w\in S\implies w\in A$.
Since you are trying to show that $\forall w \in A^+ \implies w \in A^*$, you are proving that $ A^+ \subseteq A^*$.

One more legant way to formally do this is by finding a bijection between the two sets.
Since $|A^*|$ = $|\Bbb N|$ you need to prove that $|A^+|$ is a subset of  $|\Bbb N|$. So you need to find a Bijection (left to you since we dont do Homework for the OP's) from these two sets.
Note that there exists $2^{\aleph_0}$ such functions, so
 you have a large selection space :)


Is it more effective to vote for a woman? A certain political party wants to encourage women to participate in their primary elections, so they decide, that the 4th position is reserved for a woman. That is, if there is no woman in the top 4 positions, then the woman with the largest number of votes will be promoted to the 4th position, and the candidates at positions 4 and below (5, 6, 7...) will be demoted one position (of course, if there is initially a woman in one of the top 4 positions, then no promotion/demotion will take place).

There are two candidates that I support equally, one is a man and the other is a woman. Is it true that, if I vote for the woman, my vote is more effective?

In a more extreme case, where the 1st position is reserved for a woman, it's clear that my vote is most effective when I give it to the woman, because this is my only chance of sending my favorite candidate to the 1st position; voting for the man, in this case, will never bring my favorite candidate to the 1st position.

Intuitively, it seems to be the same with the 4th position reserved, because, if I vote for the man and he enters position <=4, he might be demoted, but if I vote for the woman and she enters position <=4, she might be promoted, so my single vote may be worth a lot.

However, I am looking for a formal proof that this is the case (or maybe a disproof?)

Consider the following cases when you are the marginal voter (i.e. you decide the election):

Two men $m_1$ and $m_2$ have $>n$ votes, two other men $m_3$ and $m_4$ have $n$ votes, and one woman $w_1$ has $<n$ votes. If you support $m_3$ and $w_1$ equally and support $m_4$ less, then you should vote for $m_3$, such that both $m_3$ and $w_1$ will be in the top four.
Three men have $>n+1$ votes, one man $m_x$ has $n$ votes and two women $w_1$ and $w_2$ have $k<n$ votes each. If you support $m_3$ and $w_1$ equally, you should vote for $w_1$ regardless of $x$ because $m_x$ will definitely lose, and $w_1$ will only win with certainty with your vote.
Men $m_3$ and $m_4$ have $n$ votes, two women $w_1$ and $w_2$ have $k<n$ votes. What happens in the case of a tie is unclear, and (given one vote) it will end in a tie either way.

Thus, it seems as though there is no advantage to voting for either a woman or a man over the other.