How to represent zero as floating point number? For the floating-point number, we have the form
$\pm d_0.d_1d_2···d_{P-1}\times\beta^E$

$\pm$ --------------------------- sign
$d_0.d_1d_2···d_{p-1}$ --------- significant
$\beta$ ---------------------------- base (int)
$0\le d_i\lt \beta$ are the significant digits
$P$ ---------------------------- precision (int)
specifies number of digits carried -> controls accuracy
$E$ ---------------------------- exponent (int)
$L\le E\le U$

$L$ -- lower
$U$ -- upper

For example, suppose $F(10,3,-10,10)$
$4.00\times10^5$ represents the number $400000$
But how are we going to represent $0$ in such case?
Are we going to give $0$ directly or $0.00\times10^0$?

Note: In the interest of making this somewhat self-contained, I am using terminology from the most recent versions of the IEEE-754 standard. Prior to 2008, "subnormal numbers" were called "denormal numbers", and "binary32" was called "single precision". Some textbooks/papers/etc may use the old terms.
The representation that you are talking about here is called, in IEEE-754, normal numbers. A normal number is one which has a single nonzero digit on the left-hand side of the radix point (i.e. decimal point or binary point) of its mantissa.
The representation for zero uses a slightly different representation, namely, subnormal numbers.
Taking binary32 as our example, there are three fields:

The sign bit, which is 1 bit in size.
The exponent field, which is 8 bits in size.
The significand field, which is 23 bits in size.

The sign bit is 0 if the number is positive, and 1 if it is negative.
There are 8 bits reserved for the exponent field, so we can store a number between 0 and 255. We encode the exponent with with a bias of 127, using only the range of -126 to 127 for normal exponents.
The significand field is used to store the mantissa. In binary, the only nonzero digit is 1, so it is not stored explicitly in the IEEE-754 representation of normal numbers. So, for example, to represent the number $3$, we first express it in normal form:
$$+1.1_2 \times 2^1$$
The sign bit is 0 (because the number is positive). The exponent field is $1 + 127$, the true exponent plus the bias, which is 10000000 stored as a bit field.
The mantissa is $1.10000000000000000000000_2$. In normal form, the digit before the binary point is always $1$, so we don't store it, giving 10000000000000000000000 for the significand field.
The reason for the distinction between "mantissa" and "significand" is because the mantissa is the true mathematical mantissa of the number, but the "significand" is only the bits that we need to store.
Using this biased representation for the exponent gives us two bit patterns that we didn't use: 00000000 and 11111111.
The "all ones" pattern is used for values that are not finite numbers: infinity and NaN ("not a number"). I won't talk further about these here.
The "all zeroes" pattern is used for subnormal numbers. What it means is that the mantissa is the significand field with an implicit zero before the binary point, and the exponent is fixed to be -126. So, for example, if the sign bit is zero (positive), the exponent field is all zeroes, and the significand field is 10000000000000000000000, then this represents the number:
$$+ 0.10000000000000000000000_2 \times 2^{-126} = 2^{-127}$$
By setting the sign bit, the exponent field and the significand field to all zeroes, this gives us a representation for zero. Plus, it's the most desirable representation as far as programmers are concerned: if you have zeroed-out memory (all of the bits are set to zero) and read it as a floating-point number, it means zero.
There is also a representation here for negative zero. This is by design, but the reasoning behind it is beyond the scope.
Now this is all binary, and you are asking about decimal. IEEE-754 also defines a decimal floating point format, with two different binary encodings. While the exponent is always base-10, the mantissa/significand field can be either binary or densely packed decimal. The idea is still the same. One exponent value is reserved, and zero is represented using that special value.


How to find efficiently the minimum modification to avoid close consecutive numbers? I have an array of sorted numbers:

arr = [-0.1, 0.0, 0.5, 0.8, 1.2]

I want the difference (dist below) between consecutive numbers for that array to be above or equal a given threshold. For example, if threshold is 0.25:

dist = [0.1, 0.5, 0.3, 0.4] # must be >=0.25 for all elements

arr[0] and arr[1] are too close to each other, so one of them must be modified. In this case the desired array would be:

valid_array = [-0.25, 0.0, 0.5, 0.8, 1.2] # all elements distance >= threshold

In order to obtain valid_array, I want to modify the minimum amount of elements in arr. So I substract 0.15 from arr[0] rather than, say, substract 0.1 from arr[0] and add 0.05 to arr[1]:

[-0.2, 0.05, 0.5, 0.8, 1.2]

Previous array is also valid, but we have modified 2 elements rather than one.
In order to obtain valid_array, I already have a brute force solution which works fine, but it is quite slow for large arrays. My questions are:

What is the time complexity of that brute force solution?

Does a more efficient algorithm even exist?

Edit

First, I need to clarify what I mean by difference, which I define the same way as in here, so out[n] = a[n+1] - a[n].
The fact that all elements in that difference must be above (or equal) threshold implies that valid_array is also sorted.

Second, the number of modifications (which must be minimized) is obtained by comparing elementwise the original arr and valid_array

Here is an algorithm that returns the minimum amount of elements that need to be modified. It is about as simple as possible and as fast as possible. Its time complexity is $O(n)$, where $n$ is the size of input array.

def minimize(arr, threshold):
    size = len(arr)

    # keep[i] or modify[i] is the minimal number of modification
    # needed on arr[0:(i+1)], keeping or modifying the i-th
    # element respectively, so that any two consecutive numbers
    # in arr[0:(i+1)] are greater than `threshold` apart.
    keep = [0] * size
    modify = [0] * size

    for i in range(1, size):
        modify[i] = min(keep[i - 1], modify[i - 1]) + 1

        if abs(arr[i] - arr[i - 1]) >= threshold:
            keep[i] = min(keep[i - 1], modify[i - 1])
        else:
            keep[i] = modify[i - 1]

    return min(keep[-1], modify[-1])

The criticall observation is that if a number at a certain index has been modified, we can consider it has been modified so wildly it will be more than threshold away from any of its neighbours, whether those neighbours will be modified or not.


How can i find $Ω(f(n))$ and $O(f(n))$? Given the following function,
$$f(n)=\prod_2^n \log i. $$
How can I find $f(n)=\Omega (?)$ and $f(n)=O(?)$ ?

I tried to do it, but I have no idea how to do it ..

It will be easier to analyze $S(n) = \log f(n)$, which is given by the formula
$$ S(n) = \sum_{i=2}^n \log\log i. $$
According to the Euler–Maclaurin formula,
$$
S(n) = \int_2^n \log\log x \, dx + \frac{\log\log 2 + \log\log n}{2} + \sum_{k=1}^s \frac{B_{2k}}{(2k)!} [(\log \log)^{(2k-1)}(n) - (\log\log)^{(2k-1)}(2)] + R,
$$
where the remainder satisfies
$$
|R| = O_s \left(\int_2^n (\log\log)^{(2s+1)}(x) \, dx\right).
$$
Here $(\log\log)^{(r)}$ is the $r$th derivative of $\log\log$ and $B_{2k}$ are Bernoulli numbers.

In order to get big O asymptotics, it suffices for the error to be of order 1. The first few derivatives of $\log\log x$ are
$$
\log \log x, \frac{1}{x\log x}, -\frac{\log x + 1}{x^2\log^2 x}, \frac{2\log^2 x + 3\log x + 2}{x^3\log^3 x}.
$$
The third derivative has constant sign (for $x$ larger than some constant), and so when $s=1$, the growth rate of the remainder term can be bounded by the second derivative evaluated at $n$, which is $o(1)$. So it suffices to choose $s=1$. We obtain
$$
\begin{align*}
S(n) &= \int_2^n \log\log x \, dx + \frac{\log\log 2 + \log\log n}{2} + \frac{\frac{1}{n\log n} - \frac{1}{2\log 2}}{12} + o(1) \\ &=
x\log\log x - Ei(\log x) \bigr|_2^n + \frac{\log \log n}{2} + O(1) \\ &=
n\log\log n - Ei(\log n) + \frac{\log \log n}{2} + O(1),
\end{align*}
$$
where $Ei(x)$ is the exponential integral. The exponential integral doesn't really reduce to any known function, but it is known that $E_i(x) = (e^x/x)(1 + O(1/x))$. Therefore
$$
S(n) = n\log\log n - \frac{n}{\log n} + O\left(\frac{n}{\log^2 n}\right).
$$
This gives the value of $f(n)$ up to a factor of $e^{O(n/\log^2 n)}$. In the same way, we can get an explicit expression with error $e^{O(n/\log^k n)}$ for any constant $k$, using the divergent series for $Ei(x)$. If we want an expression with $O(1)$ multiplicative error, then the best we can get is
$$
f(n) = \Theta(e^{n\log\log n - Ei(\log n)}\sqrt{\log n}).
$$
With a bit of effort we can also find the hidden constant.


What is the name of the domain or theoretical problem of transmitting game states in an online game For example, in chess (or any online game), you broadcast the game state to other players at certain times (every n-milliseconds or after a move is made). Thereupon, a player's game client renders the game state in a format suitable for human interaction.

I want to do additional research on the design/transmission of multiplayer video game states, but my ignorance of the terminology is frustrating my research efforts.

What role or documented theoretical problem describes this specific piece of game system architecture?

I'm not sure there is a single "name" for this non-trivial situation -- not every situation you will run into will have a single "name" or terminology for that situation -- but there are multiple topics and concepts that seem relevant:

As Draconis mentions, serialization or pickling are relevant for how to convert a complex data structure in memory into a sequence of bits that can be sent to another party.
Data synchronization and file synchronization may also be relevant; there are techniques that may be useful if the data structure representing game state changes slowly, as then it may be more efficient to send only the changes to the other parties without having to repeatedly send the current state.  You might enjoy reading about rsync and mosh.
Video games may use various methods for lag compensation that are worth knowing about.

Stack Exchange has an entire site for game development.  I suggest spending some quality time there perusing questions that seem related, to get a taste of some of the methods, concepts, and techniques that are relevant.


Sort a $d$-sorted array An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array.
I need to write an algorithm that get a $d$-sorted array of length $n$ and sort it in the following running times:

$\Theta(n)$ if $d$ is constant
$\Theta(n\log\log n)$ if $d = \Theta(\log n)$.

My attempt:
I wrote the following pseudo-code:
Sort_d_array(A[],d)
 min-heap-size <- d
 for i <- 1 to n
    BUILD-MIN-HEAP(min-heap,heap-size)
      if min-heap not empty
        then EXTRACT-MIN <- A[i]
          if i+d<=n
            then heap-insert-min(min-heap,A[i+d])

But in terms of runtime, all I get is $O(n\log\log d)$.
My method: I initialize $i \gets 1$ and then I build a min-heap that contains the first $d$ elements.
As long as the heap is not empty, I use EXTRACT-MIN and put the element at index $i$ in the array. If $i+d \le n$, then I add the element at index $i+d$ to the min-heap.
Any help?

Since your heap contains $d$ elements, every operation takes take $O(\log d)$, for a total running time of $O(n\log d)$.
When $d$ is constant, this is $O(n)$, and when $d = O(\log n)$, this is $O(n\log\log n)$.
For a matching $\Omega(n\log d)$ lower bound, see this question.


Using the pumping lemma for a proof by contradiction I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata.  I can explain why it cannot be accepted intuitively, but I'm having trouble with the proof.  Our symbols are {a, b}.

I allowed L = $\{(ab)^{*{\frac{n}{2} - 1}} aa (ab)^{*{\frac{n}{2} - 1}}\}$.  I know the format of the language is wonky, and will be talking to my professor about it tomorrow.  For the proof, I allowed $\frac{n}{2} - 1$ to be the combination of symbols before and after the two elements.  So, using the Pumping Lemma's condition that |uv|≤ n, I allowed $u = \frac{n}{2} -1$  and $v = n^2$ (for aa); this is obviously greater than n, but I'm having trouble understanding how to choose $u$ and $v$.  Is my assignment for these parameters correct?

$u$ and $v$ are supposed to be strings such that $uv$ is a prefix of a
string in the language longer than $p$ symbols, $p$ being the pumping length. Furthermore, you do not
get to choose them. All you know is that their total length does not
exceed $p$ and they are prefix of a word $x$ in  the regular language, of length $n$.

You do not get to choose them because they are existentially
quantified in the statement of the pumping lemma ... you could choose
them if they were universally quantified. If you do not understand
this last remark, just ignore it.

What you can choose is the value of $n$ and the string $x=uvw$ of size $n$
that will be used for pumping.  You choose $n$ in relation to the
pumping length $p$ which depends only on the regular language.

I would suggest to choose $n$ quite big, so that you make sure $uv$ is
in the first half of the string $x$, since $| uv| ≤ p$.

I would also choose my string $x$ with an appropriate pattern of a and
b  ... and then check what happens when I pump. It may seem odd, but
you have to get even with that problem.


Increasing every starting edge by a constant, then the shortest path tree remains the same? Consider a directed graph G = (V,E) with non-negative costs on each edge.
  With s being a starting vertex. Prove that by adding a constant k to each edge
  (s,u) ∈ E such as u ∈ V, the shortest path tree starting from s will remain the same.

In an attempt to solve the above question (with a proof)
I thought that if we add the same constant factor to every edge the relative order of path weights is preserved.
  However, I am not sure how to state the proof correctly.

I have searched a lot, any help would be greatly appreciated.

I think you can prove it by counter-example.

Assume your SPT (shortest path tree) from the original graph is no longer a valid SPT in the new graph.  That means there's a node $f$ s.t. the path $(s, n_1, n_2, ..., f)$ in your SPT is no longer a shortest path, meaning some other path $(s, v_1, v_2, ..., f)$ (whose length wasn't shorter before) now has a shorter length.

Now show that's impossible by calculating how much the lengths of those two paths have increased.


Could someone suggest me a good introductory book or an article on graph clustering? For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the book on graph clustering as it often more self contained but articles are fine too. Back in the days I used to work in the field of numerical linear algebra so I'd also prefer algebraical view on things (so books which view graph as a matrix with specific properties are more accessible to me).

p.s. I've tried scholar.google.com but was overwhelmed by vast number of results.

The book The Elements of Statistical Learning by Trevor Hastie,
Robert Tibshirani and
Jerome Friedman covers a lot of learning and clustering algorithms including various graph clustering algorithms. Algorithms such as Spectral Clustering are phrased algebraically, as is much of the book. The good thing is that a pdf of the book is available from the authors' website, linked above. It has an extensive bibliography to help you beyond what is presented in the book.

There's also an implementation of Spectral Clustering in R which works quite well and has lots of options.


Get every possible (connected) subgraph containing x number of nodes If I had a graph representing the USA with each node representing a state, and each edge linking adjoining states, is there a graph algorithm that would give me every possible unique group of 4 states that are linked (order of states is not important)?

By 'linked' I mean that all states in valid group should be reachable from every other state in the group either because they are adjoining (direct neighbours) or connected via another state in the group, eg :

One valid group is Kansas, Nebraska, Iowa, Missouri (since Nebraska, Iowa, Missouri are direct neighbours of Kansas)

But also Kansas, Colorado, Utah, Nevada is valid since Kansas is a neighbour of Colorado which is a neighbour of Utah which is a neighbour of Nevada (even though Kansas and Nevada are not direct neighbours)

It seems to make sense to me to represent this data in a graph or adjacency matrix since 'connectivity' is the key qualifier. Generating every combination of 4 states, then testing for connectivity seems wasteful and even more so if I wanted every combination of 5,6,7... states.

I don't have much knowledge in this area, but I thought this may be suited to a graph theory type problem, but cannot find anything that matches this type of problem, so I am probably looking in the wrong area.

Can anyone give any advice, areas for me to read up on ?

A standard brute-force method should suffice: enumerate all ${50 \choose 4}$ ways to choose 4 out of the 50 states, and for each such combination, check whether it meets your requirements.  There are only about 230,000 combinations to check, so this should run in a fraction of a second on a computer.

If you wanted to optimize it, there are various methods, such as choosing a state $u$, then choosing another state $v$ that is a neighbor of $u$, then choosing another state $w$ that is a neighbor of $u$ or $v$, then finally one more state $x$ that is a neighbor of one of $u,v,w$, and then checking whether that meets your conditions.  This would be faster.  But why bother?  It's hardly worth spending an extra hour or two programming a complicated algorithm to spend a fraction of a second of CPU time.


Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language? In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]

  In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is surprisingly complex.

How to prove that?

In contrast, is there a language that is accepted by some DPDA but can't be accepted by any non-deterministic one counter machines?

Reference

[1]: John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley. P359.

The conclusion is: the languages recognized by DOCA(deterministic one counter automata) is a proper subset of the languages recognized by DPDA(deterministic pushdown automata).

The reason why Hopcroft said the proof is complex is that in his definition, the input string of DOCA is appended with an endmarker  \$ [1:P356]. So, the actual difficulty is to prove that: for any language $L$, there exists DPDA $P$ s.t. $L = L(P)$ $\Leftrightarrow$ there exists DPDA $P$ s.t. $L\$ = L(P)$.

This is shown in Exercise 8.5.2 [1:P362] .But I failed to prove the exercise by Hopcroft's hint. I find a detailed proof here by Hendrik Jan Hoogeboom and Joost Engelfriet [2, see remark end of Section 1.6].

Since, we can prove that the languages of DOCA is a subset of the languages of DPDA.

In contrast, $\{ a^n b^m a^m b^m | n, m \ge 1 \}$ is a language that can be recognized by some DPDA but can't be recognized by any DOCA. (Thanks to @Vor in his answer)

References

[1] John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley.

[2] H.J. Hoogeboom, J. Engelfriet (2004). Pushdown Automata.
Chapter in: Formal Languages and Applications, C. Martín-Vide, V. Mitrana, G. Paun, eds. Springer.


Can such an operation be done with two stacks? Assume a Forth-like environment with two stacks, a main one and an auxiliary one.
The following operations can be done on the main stack: DUP (duplicate the top element), SWAP (swap the top two elements), DROP (drop the top value), PUSH (move the top value to the auxiliary stack) and PULL (move the top value of the auxiliary stack to the primary one).

If the main stack is organized like this (top-bottom): x <x elements> y <y elements> z <z elements>, where x, y and z are integers preceding the corresponding number of arbitrary elements, is it possible to re-arrange it like this: x <x elements> z <z elements> y <y elements> using only the operations described above?

If not, what operations can be added to satisfy this condition?

You do not need more operations. In fact, you do not need DUP and DROP, either. All you need are SWAP, PUSH and PULL.

The list of states of main stack below shows how the initial state 1 a 3 p q r 2 x y is changed to 1 a 2 x y 3 p q r. The auxiliary stack is at left hand side growing to the right from its bottom at the very left. The main stack is at right hand side growing to the left from it bottom at the very right. <- means PUSHing to the auxiliary stack and -> mean PULLing from the auxiliary stack.

   <- 1 a 3 p q r 2 x y  //initial state
 1  <-  a 3 p q r 2 x y
 1 a  <-  3 p q r 2 x y
 1 a 3  <-  p q r 2 x y
 1 a 3 p  <-  q r 2 x y
 1 a 3 p q      r 2 x y  //then SWAP
 1 a 3 p q  ->  2 r x y
 1 a 3 p      q 2 r x y  //then SWAP
 1 a 3 p  ->  2 q r x y
 1 a 3      p 2 q r x y  //then SWAP
 1 a 3  ->  2 p q r x y
 1 a      3 2 p q r x y  //then SWAP
 1 a  <-  2 3 p q r x y
 1 a 2  <-  3 p q r x y
 1 a 2 3  <-  p q r x y
 1 a 2 3 p  <-  q r x y
 1 a 2 3 p q      r x y  //then SWAP
 1 a 2 3 p q  ->  x r y
 1 a 2 3 p      q x r y  //then SWAP
 1 a 2 3 p  ->  x q r y
 1 a 2 3      p x q r y  //then SWAP
 1 a 2 3  ->  x p q r y
 1 a 2      3 x p q r y  //then SWAP
 1 a 2  <-  x 3 p q r y
 1 a 2 x  <-  3 p q r y
 1 a 2 x 3  <-  p q r y
 1 a 2 x 3 p  <-  q r y
 1 a 2 x 3 p q      r y  //then SWAP
 1 a 2 x 3 p q  ->  y r
 1 a 2 x 3 p      q y r  //then SWAP
 1 a 2 x 3 p  ->  y q r
 1 a 2 x 3      p y q r  //then SWAP
 1 a 2 x 3  ->  y p q r
 1 a 2 x      3 y p q r  //then SWAP
 1 a 2 x  ->  y 3 p q r
 1 a 2  ->  x y 3 p q r
 1 a  ->  2 x y 3 p q r
 1  ->  a 2 x y 3 p q r
      1 a 2 x y 3 p q r  //final state

Once you have checked the above procedure, you will understand how to proceed in the general situations. In fact, what have been shown above is, basically, the well-known fact that if you can swap any two adjacent elements in an array, you can sort all elements in the array into any permutation you wanted.


Is learned RNN still universal? I know it has been shown that RNNs are Turing complete. So for any Turing machine, there exists a configuration of a RNN that is equivalent to it.

But I'm wondering, is all those configuration reachable through learning/training? i.e. For any Turing machine, does there exist a data set and a training process, which will finish in finite time and generate an equivalent RNN?

The RNN construction of the paper is independent of training, because the weights are fixed and no learning occurs. The proof is based on how the encoding of the input output mechanism should be translated into an RNN so that it behaves the same as a Turing machine given the same input. They construct an RNN equivalent to a two-stack push-down automata, which can simulate any Turing machine. They also end up with a Turing complete universal processor net with 1058 units.

Training process is an approximation for a function, thus accuracy is always a parameter to decide on the computation time. Theoretically speaking, for a network with finite number of processors, and with weights and states represented with rational numbers (computable numbers), which is also a translation of a computable function (i.e. not a real random number generator for each sample), it should converge. Thus, the answer is yes.


Reachable state space of an 8-puzzle I've just began studying Artificial Intelligence and am wondering why the reachable state space of an 8-puzzle is $9!/2$. I see that the number of permutations of the tiles is $9!$ but it is not immediately obvious why half the possible states of the puzzle are unreachable at any given state. Can anyone elaborate?

An image of an 8-puzzle for reference with a random configuration on the left and the goal state on the right:

This is an expansion of this presentation.

Because the state graph consists of two disconnected components of equal size.
Without loss of generality we can  assume that the target state is $1\;2\;3\;...\;15\;\Box$.

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  *

Given a state $S$ a permutation inversion is a tile $T_i$ that is placed after $T_j$ but $i < j$; this happens when (a) $T_i$ is in the same row of $T_j$, but on its right, or (b) $T_i$ is in a lower row:

 .  .  .  .      .  .  .  .
 3  .  .  1      .  7  .  .
 .  .  .  .      .  5  .  .
 .  .  .  .      .  .  .  .
    (a)             (b)

We define $N_j$ as the number of tiles $T_i$, $i < j$ that appears after $T_j$.
For example, in the state:

 1  2  3  4
 5 10  7  8
 9  6 11 12
13 14 15  *

we have that after $T_{7}$ there is one tile ($T_6$) that should be before it, so $N_7=1$; after $T_{10}$ there are four tiles ($T_7, T_8, T_9, T_6$) that should be before it, so $N_{10}=4$.

Let $N$ be the sum of all $N_i$ and the row number of the empty tile $T_{\Box}$

$$N = \sum_{i=1}^{15} N_i + row(T_{\Box})$$

In the example above we have: $N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

We can notice that when the empty tile is moved horizontally $N$ doesn't change; if we move the empty tile vertically $N$ changes by an even quantity.

For example:

 .  .  .  .      .  .  .  .
 .  .  2  3      .  .  *  3
 4  5  *  .      4  5  2  .
 .  .  .  .      .  .  .  .

$N' = N + 3 \mbox{ (2 is placed after 3,4,5)} - 1 \mbox{ (empty tile is moved up)} = N + 2$

 .  .  .  .      .  .  .  .
 .  .  *  4      .  .  3  4
 2  5  3  .      2  5  *  .
 .  .  .  .      .  .  .  .

$N' = N + 1 \mbox{ (2 is placed after 3)} - 2 \mbox{ (4,5 are placed after 3)} + 1 \mbox{ (empty tile is moved down)} = N$

So $N \bmod 2$ is invariant under any legal move of the empty tile.

We can conclude that the state space is split in two disconnected halves, one having $N \bmod = 0$ and the other having $N \mod 2 = 1$.

For example the following two states are not connected:

 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15  *    13 15 14  *
    N = 4         N = 5


D flip flop : How does it work in depth I'm coming to you today because I have some trouble to understand how works D flip flop in depth. Two weeks ago we started at school learning sequential logic and so register and everything that come with. We saw how to build a D flip flop using RS Asynchronous flip flop like this one :

Then we made a synchronous version of this one using two AND logic gate (one per input) and a clock input. The D flip flop we made is only a RS Asynchronous using only one input linked to S, and the NOT linked to R. Just like this :

And as I wrote it works on HIGH LEVEL. So to make any shift register based on this it is impossible. So I decided to go my own way and I ended with something like this :

I was conviced that it's the good way. It works on falling edge so it's perfect for shift register. And then my teacher told me that we couldn't use any gate on clock (in my case I use a NOT gate). But he can't tell me clearly how to do a D flip flop working on rising or falling edge. Even if Logisim (the software I use to simulate circuits) there is a D flip flop where you can make it working on Rising, falling edge or even at high or low level.
So my main question is : What is the good way to make a D flip flop working or RISING or FALLING edge if we can't use a single gate on clock ? And why can't we use gate on clock ?

Here's a big hint, and then I'll let you work out the rest for yourself. Because we want cs.SE to be a collection of questions and answers, please post your solution as an answer.

Edge-triggered D flip flops are generally done using the "two RS flip flop" design that you have. You got that right. Reading from left to right, I'm going to call these RS flip flops "stage 1" and "stage 2".

Before the transition "happens", stage 1 should load the data. The effect of the transition is to make stage 1 hold its data and make stage 2 load its data from the output of stage 1.

So to create a D flip flop that is triggered on the rising edge:

When the clock is low, stage 1 should load its data and stage 2 should hold its data.
When the the clock is high, and stage 2 should load its data and stage 1 should hold its data.

The effect of this is that the transition from low to high shifts the result from stage 1 to stage 2.

Conversely, to create a D flip flop that is triggered on the falling edge, stage 1 should load when the clock is high, and stage 2 should load when the clock is low.

Now can you implement that?

Incidentally, I don't understand your teacher's requirement "we couldn't use any gate on clock". When you realise digital circuits in CMOS or NMOS, clock fanout is a large practical issue. Besides, you only get inverting gates, so putting gates on clock lines is normal and expected.

Nonetheless, perhaps they meant you to use de Morgan's laws to reduce the gate count?


Books on finite languages and automata theory with examples, problems and solutions Can you suggest me a good book with illustrative examples and problems with solutions for finite languages and automata theory?

I tried Hopcroft's but it has mostly theory and not many problems with solutions.

Thanks! :)

Try this question to get an idea. I think the classical ones at universities are the one from Sipser and Hopcroft's one. For Hopcroft I would really look for the old version if you are mathematically inclined. They removed a lot of proofs in new versions.

For specific examples of problems you'll get solutions here and there over the Internet. It is good not to have a straight look to the solution and having the solution very near can be very tempting at times.

While looking for books to get an idea of what's on them I like this Internet library. Then you can always buy the book on paper or borrow it from your University library.

Hope this helps.

Some books with solutions: (under construction)

Hopcroft's et alii. solutions to their book.

Apparently, Sipser's book contains solutions after each chapter.


C++ : N line segment Intersection I need to find intersection of N line segments (given by coordinates of start and end points) which are either vertical or horizontal.So I read that Sweep Line Algorithm is a good way to solve this.

But I can't seem to find it's implementation in C++ anywhere on Internet. Can someone provide me it's code in C++ ?

Depending on how long the lines are and what the likelihood of intersections is, you could also use a spatial join. I.e. you treat all all lines as rectangles, put them in a spatial index and search for each line with which other lines it overlaps. You can use a standard R-Tree or Quadtree, but I would actually suggest a PH-Tree here, for example this one, because they are very fast for window queries with small result sets (for example if you expect usually only 1 intersection). For all results, you would have to manually calculate whether the lines actually intersect or not, because overlapping rectangles is an indicator for overlap, but obviously not a guarantee.

Also 'Sweep Line' is more of a general approach of tackling a problem, a bit like 'divide and conquer'. It is not an algorithm in itself, you would have to be more specific how you would use it to solve your intersection problem.


Two criteria for an edge to belong to all MSTs Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1:

  The edge $e_1$ appears in any MST of $G$ iff $e_1$ is a light edge in any cut $C$ that it crosses.

Is it equivalent to the following Lemma 2?

  An edge $ = (, )$ appears in all MSTs of $$ iff every cycle including $$ has an edge $′$ with $() < (')$.

The latest is clearly a negation of the red rule for MSTs.
I think they are equivalent but can't prove it.

There is a serious typo/mistake in the OP's (original) question. The title say "Two criteria for an edge to belong to all MSTs". However, the lemma 1 talks about "appears in any MST". To be consistent with the title and with lemma 2, let us modify the lemma 1 as:

An edge $e$ appears in all MSTs iff $e$ is the unique lightest edge in the cut-set of some cut which $e$ crosses.

According to the title of the question, we may assume the OP's intention is to prove the two criteria for an edge to belong to all MSTs is equivalent without any reference to MST. (If reference to MST is allowed, both criteria are equivalent to the statement, the edge belongs to all MSTs. Hence both criteria are equivalent to each other as well.)
Let us state the equivalence of the two criteria clearly.

Let $G$ be a weighted connected undirected graph and $e$ an edge in $G$. The following two properties of $e$ are equivalent.

(unique-cut-lightest) there is a cut of $G$ such that $e$ is the unique lightest edge that crosses the cut.
(non-cycle-heaviest) every cycle containing $e$ contains an edge heavier than $e$.

It turns out we do have a simple proof of the above equivalence.
Unique-cut-lightest $\Rightarrow$ non-cycle-heaviest: Let $c$ be a cycle that contains $e$. As a cycle, $c$ must contains another edge in that cut-set. Name that edge $e'$. Since $e$ is the unique lightest edge in that cut-set, $e'$ is heavier than $e$.
Unique-cut-lightest $\Leftarrow$ non-cycle-heaviest: Let the vertices of $e$ be $u$ and $v$. Let us remove $e$ and all edges that is heavier than $e$ in all cycles that contains $e$ from $G$ (keeping all the vertices, however), obtaining a new graph $G'$ that share the same vertices as $G$ but with less edges. There is no path from $u$ and $v$ in $G'$; otherwise, any such path together with $e$ is a cycle in $G$ that contains no edge that is heavier than $e$, which contradicts the assumption. So $u$ and $v$ are in different connected components of $G'$. Divide the vertices of $G'$ into two sets, the vertices in the connected component of $u$ and all the other vertices. These two sets of vertices is a cut of $G$ as well. $e$ crosses that cut since $u$ is in the connected component of $u$ and $v$ is not. Since all edges other than $e$ crossing that cut is one of the removed edges, $e$ is the unique lightest edge crossing that cut.


A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard? The multiple choice knapsack problem (MCKP) can be defined as follows:

MCKP is known to be NP-hard in general. I have a special case of MCKP for which

$N_i=\{1,2,\cdots,|N_i|\}$, for all $1\leqslant i\leqslant k$ ;
$p_{ij}=j$, for all $1\leqslant i\leqslant k$ and for all $1\leqslant j\leqslant|N_i|$; and
$w_{i1}<w_{i2}<\cdots<w_{i|N_i|}$, for all $1\leqslant i\leqslant k$.

My question is: Can we solve this special case of MCKP in polytime? (Or, is this special case of MCKP NP-hard?)

There is a dynamic programming solution.

Let $f(i, V)$ be the minimum weight to achieve value $V$ while only the first $i$ classes (i.e. $N_1,\ldots,N_i$) are considered, then according to the item to be chosen in $N_{i+1}$, we have

$$
f(i+1,V)=\min_{0\le j\le |N_i|}w_{ij}+f(i,V-j),
$$

where $w_{i0}$ is defined to be 0. Now you can compute $f(n,1),\ldots,f(n,\sum_{i=1}^n |N_i|)$ to get the first $j$ such that $f(n,j)\le W$, then this $j$ is an optimal value for your original problem.

This algorithm runs in
$$
O\left(\left(\sum_{i=1}^n |N_i|\right)^2\right).
$$

This is polytime because the input length is $\Theta\left(\sum_{i=1}^n |N_i|\right)$.


On propositional formula satisfiablitiy I know that there is no algorithm for converting any logical formula to DNF so even though we have an efficient algorithm to solve DNFSAT we can't solve formulaSAT in deterministic polynomial time.
But what makes the finding of an efficient CNF algorithm solve formulaSAT in polynomial time?
Because I'm guessing that the complexity of converting a logical formula to a DNF would be the same as the complexity of converting a formula to CNF so even if we find an efficient algorithm for CNFSAT we won't be able to convert any formula into CNF and therefore we can't solve formulaSAT also! Or am I wrong and the problem of formulaSAT is not in NP?!
An example of what I mean by a formula: (¬A∨B)∧¬((A∧¬C∧(B∨D))∨(C∧D))

When converting an arbitrary formula into a CNF, you are introducing extension variables. These are new variables that represent subformulas of your formula.

Let us take the following simple formula as an example:

$$ A \lor (B \land C). $$

In order to convert this into a CNF, we need to replace $B \land C$ with an extension variable $\alpha$ which has the same truth value of $B \land C$. We can easily express "$\alpha = B \land C$" as a CNF (or as a DNF). After replacing $B \land C$ with $\alpha$, we obtain the formula
$$
 (A \lor \alpha) \land \text{"$\alpha = B \land C$"}.
$$
(You need to replace "$\alpha = B \land C$" with a CNF.) This formula is equisatisfiable with the original formula: the original formula is satisfiable iff the new formula is satisfiable. Therefore if we are interested in knowing whether the original formula is satisfiable, we can instead ask whether the new one is.

In the transformation outlined above, we used the fact that the class of CNFs is closed under conjunction. That is, we could express add the condition "$\alpha = B \land C$" to our formula while retaining its CNF form. The same is not the case for DNFs, which are closed under disjunction but not under conjunction.

Indeed, consider the opposite situation, in which we want to convert $A \land (B \lor C)$ into an equisatisfiable DNF. We can easily express $\alpha = B \lor C$ as a DNF; the problem is that $(A \land \alpha) \land \text{"$\alpha = B \lor C$"}$ is not a DNF, since we joined $A \land \alpha$ and $\alpha = B \lor C$ with the wrong connective.


Time complexity of this while loop So, i would like to know the time complexity of the following codes:

x = (float) rand() / rand();   // T(4)

while (x >= 0.01)   // T(?)
{
    x *= 0.8;  // T(?) x T(2)
}

Assuming that all the basic operations are perfomed once, is the best case T(1) - constant time? Since, that might only happen when the random x generated is <= 0.01.

What about the average case? Is it T(?) x T(1) / 2?

Thanks a lot!

Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In that case, the loop will run forever.

If you changed your code to exclude that case, and exclude the case that rand () might return a 128 bit integer, then for any implementation the size of x is limited, so the number of multiplications by 0.8 is limited, so the runtime is O (1).


Matrix Chain Multiplication Greedy Approach In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic Programming but I have found a greedy approach to this problem.

For example a chain of Matrices of the size of:

   A        B       C       D
40 * 20  20 * 30 30 * 10 10 * 30

First list all of the possible consecutive pairs, and the 2 different dimensions of the pair:

        X
AB:  40 * 30
BC:  20 * 10 <----
CD:  30 * 30

Then multiply the pair that has the lowest product in the X column and the list will turn into:

   A       BC      D
40 * 20 20 * 10 10 * 30

Repeat the first 2 steps until all of the matrices are multiplied together:

          X
A(BC): 40 * 10 <----
(BC)D: 20 * 30

  ABC      D
40 * 10 10 * 30

             X
(A(BC))D: 40 * 30 <----

This have a time complexity of $O(2n^2 + 2n\log n)$.

I have tested a Java implementation on smaller test cases and it runs fine.

Does this method work, or is there a something I have overlooked?

You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $24$. In contrast, the other option has complexity $10 + 10 = 20$.

According to Wikipedia, Hu and Shing came up with an $O(n\log n)$ algorithm, which is more efficient than your algorithm, and moreover is provably correct.


Finding the largest linear combination that is not possible Regarding the problem:

What is the largest bet that cannot be made with chips worth $\$7.00 $
and $\$9.00$? Verify that your answer is correct with both forms of
induction.

I need to find an algorithmic approach, but till now my approach is to try all possible combinations with 0,1,2,3,4,5,6,7,8 (9) as the column headings and then the next row having the values as 9,10,... and so on, till able to get all values that can be generated.
All this requires an iterative approach that progressively increases the data set size, till at least 9 consecutive values can be generated.
I have found that 47 is the largest value that cannot be generated.

But, first of all this is no programmable algorithm. Second, due to first reason, I cannot prove it by induction of any type.

I feel that the algorithmic approach should consider the values that are originating from the initial set of those values that cannot be generated by any linear combination of values; i.e. 1,2,3,4,5,6,8; and then checking out which value will be the last one that can be generated from them and is not a linear combination of $9x + 7y$ (with $x,y > 0$).

If there were an approach that takes all further points that are not reachable by all the initial set of non-reachable (not having a value given by the linear combination of 9x + 7y, (x,y >0)) points (1, 2, 3, 4, 5, 6, 8); then I would be very happy to get any hint for the same.

First of all, there is a known formula that gives the correct answer in this case: if $a,b$ are relatively prime, then the maximal element which cannot be written as a non-negative combination of $a,b$ is $(a-1)(b-1)-1$. (Extending this to the case where $a,b$ are not relatively prime is a nice exercise.)

Second, suppose you don't know this formula, and want to prove that 47 is the largest value that cannot be generated. You have to prove two things:

47 cannot be generated.
Any larger number can be generated.

To show that 47 cannot be generated, note that if $47 = 9x + 7y$ with $x,y \geq 0$ then $x < 7$ and $y < 9$. This means that it suffices checking all $x \in \{0,\ldots,6\}$ and $y \in \{0,\ldots,8\}$.

To show that any larger number can be generated, you first show that $48,49,50,51,52,53,54$ can be generated, by giving the appropriate values of $x,y$ (for example, $48 = 3 \cdot 9 + 3 \cdot 7$). You then complete the proof by induction (how?).


Lazily computing a random permutation of the positive integers Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)?

What I mean is this:

An algorithm that, given a source of randomness and a positive integer range (for simplicity it could be restricted to starting at 0 and ending at n), can be asked to produce the next value in that range. This can be repeated n times, and a different number is provided by the algorithm each time.

If the caller were to push all of the values retrieved from the algorithm into a queue the resulting ordering would be just as random as if the result had been generated with the Fisher–Yates shuffle.

The naïve implementation would be to pick a random number in the range, check to see if it has already been selected, and choose again if so. This algorithm starts efficient enough, but has increasing complexity for subsequent calls -- too expensive for real-world applications.
To really be useful it would have to be O(1) for each trial, though a good logarithmic time might be applicable.

It has to be lazy because with large ranges (such as a 64 bit unsigned integer) it would take Exabytes of storage to precompute the whole permutation, and it is unlikely that a real-world application is going to actually need all of the range; merely it needs that the entire range was considered in values it is actually going to use.

Essentially the problem is just lazily generating a mapping between the integers in a range and a random permutation of those same integers, though being able to access the mapping at arbitrary points instead of just sequentially is but a bonus.

Yes.  Use a block cipher with a small block size.  This is extremely efficient and requires extremely little state.

A block cipher is a map $E : K \times X \to X$ such that, for every $k \in K$, $E(k,\cdot)$ is a permutation on $X$ (a bijective function $X\to X$).  Moreover, if $k$ is chosen uniformly at random, then $E(k,\cdot)$ acts in a way that is computationally indistinguishable from a function chosen uniformly at random from all permutations on $X$.

Thus, a simple solution is to let $X$ be the set of possible values of an unsigned integer, e.g., $X=\{0,1,2,\dots,2^{64}-1\}$, let $x$ denote a counter ($x \in X$) and $k$ a random key.  The state of your pseudorandom generator is $x$ and $k$.  When you want a new random number, you output $E(k,x)$ and then increment $x$.  This requires very little memory, is extremely efficient, and is provably good (if the block cipher is secure, which is a reasonable assumption given the state of modern cryptography).

You can find information on how to build a block cipher with a small block size here:

Format Preserving Encryption (on Wikipedia)
Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize? (on crypto.SE)
Is it possible to generate a secure permutation F over 32-bit integers even if F(0) … F(n) is public knowledge? (on crypto.SE)
Can I create a fixed length output from a fixed length input? (on crypto.SE)


How do garbage collectors avoid stack overflow? So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they are traversing a linked list or a balanced tree or whatever. They also can't use up too much memory in their search. One possible way, and the only way I can think to traverse ALL structures, might be just to traverse them all recursively the way you would a binary tree. This however would give a stack overflow on a linked list or even just a poorly balanced binary tree. But all the garbage collected languages that I have ever used seem to have no problem dealing with such cases.

In the dragon book it uses a "Unscanned" queue of sorts. Basically rather than traversing the structure recursively it just adds things that need to be marked too a queue and then for each thing not marked at the end it is deleted. But wouldn't this queue get very large?

So, how do garbage collectors traverse arbitrary structures? How does this traversal technique avoid overflow?

Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques.

An unscanned queue is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of the garbage collection thread.

Once all but one of the children of a node have been scanned, the node can be removed from the unscanned queue. This is basically a tail call optimization. Garbage collectors can include heuristics to attempt to scan the deepest child of a node last; for example a GC for Lisp should scan the car of a cons before the cdr.

One way to avoid keeping an unscanned queue is to modify pointers in place, making the child temporarily point to the parent. This is a constant-memory tree traversal technique that's used in contexts other than garbage collectors. The downside of this technique is that while the GC is traversing a data structure, the data structure is invalid, so the GC has to stop the world. This isn't a deal breaker: many garbage collectors do include a phase that stops the world, in addition to phases that don't but can miss garbage as a result.


Computer theory/ automata example help Computer Language/Logic Examples?
These are some of the questions i am having within a few chapters of my automata class and would like some help if you could :) Class is online and can be hard to self teach at times, you dont have to answer all or any for that matter, just thought id ask i got a midterm coming up and would like to know how to do these. ¯(ツ)/

Λ is not a word but it’s still used in its language? How do I show that there are other CFGs for these languages that do not use Λ-productions.

(ex i) S → aX | bX
 X → a | b | Λ

(ex ii) S → aX | bS | a | b
 X → aX | a | Λ

(ex iii) S → aS | bX
 X → aX | Λ

(ex iv) S → XaX | bX
 X → XaX | XbX | Λ

How would I convert these CFGs to CNF?
 (ex i) S → SS | a

(ex ii) S → aSa | SSa | a

(ex iii) S → aXX
 X → aS | bS | a

(ex iv) E → E + E
 E → E * E
 E → (E)
 E → 7
 The terminals are + * ( ) 7

How would I make a PDA that accepts the same language (given that a CFG makes L then a PDA makes L)
 S → XaaX
 X → aX | bX | Λ

There are online lecture notes which give algorithms for getting rid of $\epsilon$ productions ($\epsilon$ is another name for $\Lambda$) and for converting arbitrary grammars into Chomsky normal form. Both are reasonably simple. There is also an algorithm for converting a context-free grammar to a non-deterministic PDA, but if I remember correctly you first have to convert your grammar to Greibach normal form, so it might be better to understand what the language is and come up with a PDA for it directly.

Since you're taking this course online, I think it will be advantageous for you to find useful lecture notes online yourself, as part of your general education. Finding stuff over the internet is extremely useful, and if that's the only thing you get out of this course, you've already benefitted a lot.

I can illustrate the algorithms by solving some of your examples. In order to eliminate $\epsilon$-productions from your (i), the idea is that for every production that has $X$ in it, we create another one in which $X$ is missing. So we add productions $S \to a | b$. This works in general, but has to be applied iteratively.

In order to convert your (i) to Chomsky normal form, we only need to "rename" $S$: replace $S \to SS$ with $S \to TT$, and add $T \to TT|a$. Other cases require other operations; for example, if you had $A \to BCD$ then you would replace it with $A \to ED$ and $E \to BC$; and if you had $A \to Bc$ then you would replace it with $A \to BC$ and $C \to c$. This should be enough for you to work out the other parts of this question.


Can I find a clique with more than 2 nodes in a bipartite graph? As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?

A graph is bipartite if and only if it is 2-colorable. A clique of size at least 3 contains a triangle, and a triangle $K_3$ clearly cannot be colored with 2 colors. It follows we can't find a triangle in a bipartite graph, so the corresponding decision problem is very easy for a bipartite graph.


Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:
Simulate the decider of $L$ on the input, if it accepts, go over $L \setminus S$ and check if it is there, if it is, reject. If it isn't accept. If the decider of $L$ rejects - reject.
Another point is if $S \subset L$ is finite then $S$ also must be decidable, this is immediate that every finite language is decidable.
Now we have the last case where $S$ is infinite and $L \setminus S$ is infinite. We know that there must be some subsets $S$ corresponding to this case that are undecidable. This is since there are $\aleph$ such $S$ but only $\aleph_0$ deciders. Denote $D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$
Is it true that for all infinite decidable languages $L$ we have $D(L) \neq \phi$?
If this is true then as a conclusion we will have for all infinite decidable languages $L$ a sequence of decidable languages $L_n$ such that $L_0=L$ and $L_{n+1} \subset L_n$ and $|L_n \setminus L_{n+1}| = \infty$
We will also have a limit-set $L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n  \}$ and can dicuss if it is empty/finite/infinite and decicable or not.
This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions
Thanks for any help

If $L$ has a finite alphabet, then $L$ is recursively enumerable.
Then, from such an enumeration $w_0,w_1,w_2,...$ of the words of $L$ you can take $S=\{w_0,w_2,w_4,...\}$, which will also be decidable. To check if a word $w$ is in $S$ check if it is in $L$. If it is then use the enumeration of $L$ to check if its position is even or not.


Choosing a non-cryptographic hash function for language with no unsigned integers I'm implementing a hash table in pure UnrealScript, which only has support for signed 32-bit integers. This means no 64-bit integers and no unsigned integers. I was in the middle of implementing an FNV hash function, but ran into a potential problem.

  The offset_basis for FNV-1 is dependent on n, the size of the hash:
  32 bit offset_basis = 2166136261

Well, 2166136261 converts to -2128831035 when the bits are turned into an signed integer representation. My question is whether or not this will negatively affect the hash distribution and result in more collisions.

For quick reference, here is the psuedo-code for the FNV hash:

hash = offset_basis
for each octet_of_data to be hashed
    hash = hash * FNV_prime
    hash = hash xor octet_of_data
return hash

Thank you for your time.

The offset is unlikely to matter.  As the FNV web page says:

  almost any offset_basis will serve so long as it is non-zero

The multiplication is potentially more important.  The FNV-1 hash is defined to use unsigned multiplication modulo $2^{32}$, but if UnrealScript only has signed 32-bit integers, presumably you have no way to do that kind of unsigned multiplication.  At that point you're no longer using the official FNV-1 hash; you're using something different.  I suspect it's still fine, though.


Selection over combinatorics that satisfies a distribution I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.

Here is the problem :

Consider a list of M sets that ( M = 10000 )

each set contains integers in range 1... N. (Let's say N=50)
each set has the size of K. ( Let's say K=10)
each element in the set is distinct.

Sample sets are

{ 1,2,3,4,5,6,7,8,9,10}
{ 2,4,5,7,9,11,13,15,20,25}
{ 4,5,8,12,16,30,41,42,45,49}
{ 2,6,11,18,24,27,31,36,39,43}

....

{ 3,5,8,17,19,23,34,37,38,46 }

You should select L sets(Let's say L=1000) from given 10000 sets. This selection must approximately satisfy a distribution table like below

1=> 100 %
2=> 80 %
3=> 100 %
4=> 15 %

...

50=> 20%

It means that 1 should occur in all selections, 2 should occur 80% of the selections and goes on ... I will try to solve the problem by trying a random-walk algorithm that exchanges a set in each iteration.

I'm sorry if I did not express my problem well. It would be great if you could share similar problems with mine or could express your approach to the problem.

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the elements in the ground-set. It is an NP-complete problem and since it is a special case of your problem, your problem is NP-complete as well (it is clearly in NP since an NTM can guess all possible tuples of $l$ subsets and accept if the union of subsets in any of the guessed tuples covers the ground-set). So You should not expect a polynomial answer.

On the other hand, an exponential trivial solution would be to try packing all sets of $l$ subsets which are at most $n \choose l$ and try for each of them if they satisfy all the constraints in $O(l \cdot r)$ where $r$ is the number of the constraints. This totals in an $O(n^{l+1}r)$. There are a lot of improvements on this running time I think but you should not expect something sub-exponential.


Question about the undecidability of $A_{TM}$ You probably know this one (or at least a version of it).
Let $P$ be a program code, and $w$ be an input string.
Define $A_{TM}=\left\{(P,w)| P(w)=1\right\}$.
Meaning: $A_{TM}$ is the set of all ordered pairs $(P,w)$ s.t. $P$ accepts $w$.
$A_{TM}$ is undecidable.

I just read the proof for it, that made me wonder about something.
The brief of the proof (by contradiction) looks something like this:
Suppose there exist $D_{A_{TM}}$ - a computer program that answers 'yes' if $(P,w)\in A_{TM}$, and 'no' if $(P,w)\notin A_{TM}$.
Let us consider the following program:

$Q(w):$
1. run $D_{A_{TM}}$ on $(w,w)$
2. if $D_{A_{TM}}$ returned 'yes', then return 'no'.
if $D_{A_{TM}}$ returned 'no', return 'yes'.

Now running $Q(w);$ with the input $Q$, contradicts the existence of such $D_{A_{TM}}$

This is a brief, since I assume most of you already know this problem (and its proof).

Now what makes me wonder is this: when I looked at $A_{TM}$, and needed to determine if it's decidable or not, the first thing that came to my mind when I tried to imagine a machine that accepts $A_{TM}$, is how can machine like that handle inputs $(P,w)$ s.t. $P$ doesn't halt on $w$?  How can it 'predicts', beforehand, that $P(w)$ goes to an infinite loop, without actually running $P$ on $w$?
That intuition, as it turns out, wasn't wrong.
The thing is: How come the proof, as clever as it is, has nothing to do with that fact?
You'd expect it to lean - and even in the slightest way - on that leverage, but instead, the proof looks like something that was taken from the realm of paradoxes.

Basically, what I'm asking is: why does this proof work?

If you know what the program is doing, you can predict its outcome even without running it. For example, consider the following program.

INPUT: a polynomial P with integer coefficients
n = 0
while P(n) is different from zero:
  n = n + 1

This program halts if the input polynomial $P(x)$ has a non-negative integer root. It turns out that this problem is decidable - there is a clever shortcut that determines the outcome of the program. How can we rule out the existence of such shortcuts in general? The proof you describe is one clever way of doing that.


What does the $\leq_{\mathrm{P}}$ symbol mean? What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?

It should have been defined wherever you've seen it used. It normally stands for polynomial-time reducibility of one kind or another; usually many-one reducibility.


assigning running time I'm trying to assign running times to loops of code to roughly get the upper asymptotic ($O$) running time.

while (j < n2) {                                   # executes n2-1 times
    int k = 0;
    while ((k < n1) && (seq[k] < seq2[j])) {       # executes (n2-1)*n1times
      k = k + 1;
      }
     // we want to insert seq2[j] at seq[k]
     // so we move seq[k] through seq[n1 - 1] to the right
     for (int i = n1; i > k; i = i - 1) {         # some n-k times
        seq[i] = seq[i - 1];
      }
     seq[k] = seq2[j];
     j = j + 1;
     n1 = n1 + 1;
}

I know this is bad but would this algorithm worst running time be something in O(n^2) because there is one main loop and then two separate nested loops inside the main loop?

Thanks

It's hard to say without seeing the preceding code. If seq is initially empty the the run time of the outer loop is $O(n2)$ and the first nested loop is $O(k)$ and the second nested loop is $O(n1-k)$. The total running time would be $O(n2)*(O(k)+O(n1-k))$ which is $O(n^2)$.

However if seq has some initial elements, the worst case running time for the algorithm is $O(\infty)$. The problem is with the nested while loop seq[k]>seq2[j]. If any of the first n elements in seq are > seq2[j] the loop will not increment and run endlessly. Also you may run into array index out of range errors.

For example if seq = 2 , 1 , 0 and seq2 = 1 , 2 , 3. Then seq[0] > seq2[0] would be equivalent to 2 > 1 which i s false and k would never increment.
The solution would be to use

n1 = sizeof(seq)/sizeof(seq[0])  # number of elements in seq
int k = 0;
for(; k < n1 ; k++){             # iterate over seq
    if( seq[k] >= seq2[j] )      # until an we find an element in seq >= seq2[j]
        break;


What is the difference between a lock convoy and lock/thread contention? From wikipedia on lock convoy:

A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same lock. Unlike deadlock and livelock situations, the threads in a lock convoy do progress; however, each time a thread attempts to acquire the lock and fails, it relinquishes the remainder of its scheduling quantum and forces a context switch. The overhead of repeated context switches and underutilization of scheduling quanta degrade overall performance.

From wikipedia on lock/thread contention contention:

lock contention: this occurs whenever one process or thread attempts to acquire a lock held by another process or thread. The more fine-grained the available locks, the less likely one process/thread will request a lock held by the other. (For example, locking a row rather than the entire table, or locking a cell rather than the entire row.);

Could somebody please elaborate a bit further on both of those things? To me it seems like they are essentially the same, or if they are not, then surely lock contention causes a lock convoy. Is that the case or are they separate and independent concepts? Also, I don't understand the sentence "it relinquishes the remainder of its scheduling quantum and forces a context switch".

There are two blocking approaches used in locking algorithms when a lock is busy. spin wait or block (go to sleep, relinquish processor and wait for OS to awake the thread and re-schedule). Lock convoy as mentioned will happen when blocking strategy is used.
OS schedule threads on a core in time-sliced manner. Every thread get the processor for some per-determined time-slice, say 2 ms. OS in a round-robin fashion schedule all the threads in the ready-queue one by one. If say a thread after it get schedule and start its execution, say after 100 us, ask for a lock. If the lock is busy, the thread unable to get the lock, blocks and relinquishes processor. So remaining 1.9ms (2ms-100us) time slice is not used by the thread. Even after it is awaken by the OS when lock is free, the thread has to wait for its turn in the round-robin queue. The number of active threads could be in 100's.
Lock contention causes convoy effect.


Is it possible that the union of two undecidable languages is decidable? I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$.

I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't exist (because otherwise we'll be able to construct a Turing Machine $M_1$ which will decide $L_1$, for instance).

However, I cannot prove that it's impossible in the case $L_1\cap L_2 \in RE \setminus R$, and I can't find such languages.

Take $L_1=\{0\cdot x:x\in \Sigma^*\}\cup \{1\cdot x: x\in A_{TM}\}$ and $L_2=\{1\cdot x:x\in \Sigma^*\}\cup \{0\cdot x: x\in A_{TM}\}$. Clearly both languages are in $RE\setminus R$.

However, their union contains $\{0\cdot x\}\cup \{1\cdot x\}=\Sigma^*\setminus\{\epsilon\}$, so their union is $\Sigma^*$, and is therefore decidable.


Why this pattern matching fails in Agda? Consider function wa'' (need natural number definition, either in stdlib or Agda.Builtin.Nat):

postulate comm : ∀ m n -> m + n ≡ n + m

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with comm n m
...        | refl = { }0

The pattern matching on comm n m with refl fails. But if I add one more match:

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with (n + m) | comm n m
...        | .(m + n) | refl = { }0

This code works. Is there any semantics-level difference between these two code snippets?

First, let's desugar the withs.

First definition:

wa''-aux : ∀ m n -> n + m ≡ m + n -> wa (m + n) ≡ wa (n + m)
wa''-aux m n refl = ?  -- cannot unify n + m with m + n

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (comm n m)

Second definition:

wa''-aux : ∀ m n w -> w ≡ m + n -> wa (m + n) ≡ wa w
wa''-aux m n .(m + n) refl = ?

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (n + m) (comm n m)

When checking that refl is a valid case, we must unify the two sides of the equation it is supposed to be a proof of. Remember that refl : {x : ℕ} → x ≡ x, so we must find a single value x that is βη-equal to both the left-hand side and right-hand side.

In the first case, this means unifying n + m with m + n, and in the second case, this means unifying w with m + n. The latter is obviously possible, where we assign w ↦ m + n and note that we have done this with the dot pattern .(m + n) in w's place. The former is not obvious. How should we unify n + m with m + n? n ↦ m would be wrong: note, for example, that 2 + 3 ≡ 3 + 2, but 2 does not unify with 3.

In general, things are made difficult by the fact that Agda can't show that _+_ is injective. This is for the good reason that it isn't (as our example showed). Agda can show that constructors are injective, justified by the fact that Agda has no quotient types or the like. This is why suc m and suc n will unify. Agda does not try to show that any defined functions are injective, though it in principle could (by getting the user to supply a proof, for example).


Do formulas involving fewer repetitions of variables give higher numerical precision? I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis.

  Exercise 2.15.  Eva Lu Ator, another user, has also noticed the
  different intervals computed by different but algebraically equivalent
  expressions. She says that a formula to compute with intervals using
  Alyssa's system will produce tighter error bounds if it can be written
  in such a form that no variable that represents an uncertain number is
  repeated. Thus, she says, par2 is a "better" program for parallel
  resistances than par1. Is she right? Why?

This question is a little confusing when pulled out of context, so please let me explain. The formula for parallel resistors can be written in two algebraically equivalent ways: $\frac{R_1R_2}{R_1+R_2}$ and $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$. However, it seems that computing parallel resistors with the second formula would always produce higher precision than using the first one.

My question is:

Which formula is better? $\frac{R_1R_2}{R_1+R_2}$ or $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$? Here "better" means provides higher precision.
Why it is better than the other one? Please prove your answer to the first question.

Here is my effort

  After many experiments, $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$ seems to
  be the better formula. I guess that the reason behind can be conclude
  as the fewer time uncertain numbers are repeated, the less
  uncertainty is introduced, and the higher precision we can get.

But that's not enough. I expect a more scientific and more rigorous answer.

First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point.  For example, compensated summation.

On the other hand, it's certainly the case that interval arithmetic can greatly benefit from knowing when two inputs are identical.  As a trivial example, if $X$ is an interval variable, then logically $X - X = 0$ but of course the subtraction algorithm (usually) doesn't know whether it's inputs are logically identical, and so it must assume the worst-case $$X - X = [X^{lo} - X^{hi},X^{hi} - X^{lo}]$$

This is roughly what's going on here and almost certainly view SICP is taking.  If you use naive interval arithmetic operations, repeated uses of a variable will be treated independently, and so it won't be possible to cancel out error and the worst-case must be assumed.  Using the formulas from the interval arithmetic Wikipedia page and assuming $R_1$ and $R_2$ are represented by intervals that are strictly positive, you can simply calculate:
$$\frac{1}{\frac{1}{R_1}+\frac{1}{R_2}} = \left[\frac{1}{\frac{1}{R_1^{lo}}+\frac{1}{R_2^{lo}}},\frac{1}{\frac{1}{R_1^{hi}}+\frac{1}{R_2^{hi}}}\right]$$
while
$$\frac{R_1 R_2}{R_1 + R_2} = \left[\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}},\frac{R_1^{hi}R_2^{hi}}{R_1^{lo}+R_2^{lo}}\right]$$

It's clear that $$\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}} \leq \frac{R_1^{lo}R_2^{lo}}{R_1^{lo}+R_2^{lo}}$$ and symmetrically for the upper bounds, so the latter formula has a looser interval.


Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta So far I've understood that because of the definition of $\Theta$, we have
$c_1n^2 \le f(n) \le c_2n^2$.
I'm not sure how to proceed from there.

Since $f(n) \in \Theta(n^2)$ there exist two constants $n_0$ and $c>0$ such that $f(n) \ge c n^2$ for all $n \ge n_0$.
Suppose then that $f(n) \in O(n)$. For some $n'_0$ and $c'>0$, we have
$f(n) \le c'n$ for all $n \ge n'_0$.
Selecting $n = \max\left\{ n_0, n'_0, 1+\left\lfloor \frac{c'}{c} \right\rfloor \right\}$ leads to the following contradiction:
$$
c' n\ge f(n) \ge c n^2 \ge c \cdot \left(1+\left\lfloor \frac{c'}{c}\right\rfloor\right) \cdot  n > c \cdot \frac{c'}{c} \cdot n = c'n.
$$


Algorithm for coherent motion. Which bus is app user on? I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on.

To achieve this I am working on building a function that consumes a stream of a set of buses and their positions (Stream<Set<Tuple2<BusId, Location>>>), and a stream of phone location, to produce a Stream of bus predictions. The prediction should contain a confidence level.

The function should return the current prediction in real-time, and handle scenarios where the user changes the bus.

How could this be accomplished?

Both streams contain very precise locations at a rate of once every second.

You basically have a table as follows:

Time | Person | Bus1 | Bus2 | ... | BusN  |
=====+========+======+======+=====+=======+
  0  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
  1  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
...

x,y being the coordinates of that Person/Bus at a specific point in time.

You then calculate the distance for each pair of Person/Bus and timepoint and map each Bus-Person-distance column to its rolling average of approx. 20 to 60 seconds (depends on precision and stuff like this).

You can then map the distances for each time-segment to a probability to be in a specific bus (if the location data quality is high, this should be pretty easy).

If you then plot the probabilities over time, for most times a specific bus should be on top. If this probability gets lower and another one rises, the person is likely changing the bus (or the buses are near each other).

PS: If your location API has methods for distance calculations, use those. If you have to do it yourself, there are some formulas to get from latitude and longitude to something for which the Euclidean distance ($D = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$) works (using that with latitude/longitude is wrong in general: see here.

PPS: I am not entirely sure, whether this problem is actually related to Computer Science.


Constant time range sum query I need to come up with a data structure that supports the following interface:

new(time_stamp x, value v): insert a new data v for time stamp x
update(time_stamp x, value v): update the data for time stamp x to v
delete(time_stamp x): delete the data for time stamp x
query(time_stamp x): returns sum of all data whose time stamp is less than or equal to x

The data structure needs to support out of sequence data. I need the query operation to run in O(1) time. While there is no restriction for other provided interfaces, I don't want to end up with O(n) time complexity for any of them.

An AVL tree seems a good candidate, however I'm not aware of any technique (maybe amortized cost analysis) to reduce the O(log n) query complexity for AVL tree to O(1).

I appreciate any suggestion or direction toward implementing such a data structure.

If the timestamps can take $T$ different values, then it is simple to implement the new, update, and delete operations in time $\Theta(T)$ and the query in time $O(1)$, by maintaining two arrays $val[ ]$ and $q[]$ of size $T$. The array $q[]$ is initially filled with zero values.

new(x, v): set $val[x] = v$ and increment each $q[y]$ with $y\ge x$ by $v$;
update(x, v): let $v' = val[x]$; increment each $q[y]$ with $y \ge x$ by $v-v'$, then set $val[x]=v$;
delete(x, v): let $v' = val[x]$; decrement each $q[y]$ with $y \ge x$ by $v'$;
query(x): return $q[x]$.

Note that $n$ (number of data items, that is, the number of total calls to new) is unrelated to $T$ (range of the timestamps). Whenever $T=o(n)$, the above implementation satisfies your requirements. For example, if a timestamp is a day of the year, $T$ will be a constant, even though $n$ can be arbitrarily large (because you can have arbitrarily many new and deletes).

If, on the other hand, $T$ can be larger than $n$, then as D.W. noted in his comment your requirements may be too strict.


Surprising and basic data structures I'm interested in surprising data structures that extend the things people learned in their first algorithm/data structure course. Usually by offering an additional operation at a very low cost.

I learned that one can create a dynamic array with $O(1)$ access and $O(1)$ amortized append a long time ago. I thought there is no way to remove the amortized cost. I saw a data structure only a few months ago that do both operations in $O(1)$ non-amortized time.

What are some other examples?

I would not know what you learned or did not learn, What is surprising depends a lot on who is to be surprised. So your question is pretty much undefined.

All I can do for you (but I am no expert) is to mention one technique that impressed me when I first saw it, the skip lists of William Pugh. And more generally the use of randomness and  probabilistic techniques, actually not just in algorithmics but also in "proving" or in quickly identifying things that can then be formally proved (at high computational cost) to have this or that property.


Finding the largest possible area covered by M rectangle under a given histogram Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem.
In my problem, we have $M$ rectangles instead of one rectangle in the previous problem.

So, my problem is to find the largest area under a histogram by $M$ rectangles which don't have overlap with each other. It should be noted that the bottom edge of all rectangles should be on the vertical axis of the histogram.

Is there any tractable solution for large $N$ (where $N$ is the number of bars in the histogram).

Edit:
@Apass.Jack suggested an approach with the complexity of $\Theta(MN^2)$, but after implementation, it needs some days for running! Is there any faster solution?
For clarification, the value of $N$ is around $10^7$ and the value of $M$ is around $10^3$.

What are the subproblems of this problem when we try dynamic programming? Or what is the table?

The subproblems are finding $dp[m][n]$, the largest area possible by $m$ non-overlapping rectangle

which are under the first $n$ leftmost bars and,
the rightmost of which contains the $n$-th bar.

Let $dp2[m][n]$ be the the largest area possible by $m$ non-overlapping rectangle

which are under the first $n$ leftmost bars and,
the rightmost of which is not to the right of the $n$-th bar.

The answer is the maximum of $dp2[M][n]$, where $M\le n\le N$.

$dp[m][n]$ is the maximum of $dp2[m-1][n-1] + R_{n,1}$, $dp2[m-1][n-2] + R_{n,2}$, $\cdots$, $dp2[m-1][n-i] + R_{n,i}$, $\cdots$, where

$R_{n,1}$ is the area of $n$-th bar
$R_{n,2}$ is the area of the rectangle which expands the $n$-th bar and $(n-1)$-th bar horizontally and which contains $n$-th bar
$\cdots$, where $R_{n,i}$ is the area of the rectangle which expands the $n$-th bar and $(n-i+1)$-th bar horizontally and which contains $n$-th bar.

$dp2[m][n]$ is the larger of $dp2[m][n-1]$ and $dp[m][n]$.

The initial values of the two tables and boundary relations should be easy to determine.

There might be optimization tricks to speed up computation besides the standard memorization. You can check whether this naive dynamic programming is fast enough, whose worst behavior is about $\Theta(MN^2)$, which happens when all bars are becoming shorter and shorter from left to right.


Counting with constant space bounded TMs The problem, coming from an interview question, is:

  You have a stream of incoming numbers in range 0 to 60000 and you have
  a function which will take a number from that range and return the
  count of occurrence of that number till that moment. Give a suitable
  Data structure/algorithm to implement this system.

The stream is infinite, so if fixed size data structures re used, i.e. primitive types in Java or C, they will overflow. So there is the need to use data structures that have a size that grows over time. As pointed by the interviewer, the memory occupied by those data structures will diverge.

The model of computation is a Turing machine with three tapes:

infinite read-only one-way input tape;
constant space bounded read-write two way work tape;
infinite write-only one-way output tape.

The main reason to choose the model above is that in the real world there is virtually no limit to the quantity of input that can be acquired using a keyboard or a network connection. Also, there is virtually no limit to the quantity of information that can be displayed on amonitor over time. But memory is limited and expensive.

I modeled the problem as the problem to recognize the language L of all couples (number,number of occurrences so far).

As a corollary of the Theorem 3.13 in Hopcroft-Ullman I know that every language recognized by a constant space bounded machine is regular.

But, in any given moment, the language L is a finite language, because the number of couples to be recognized is finite: 60001. So I can't use the pumping lemma for regular languages to prove that such language is not regular.

Is there a way I can complete my proof?

The original question is here.

Let me give an explanation which does not differ in content from the accepted answer, but brings the question back to the realm of regular languages.

The language you are dealing with can be defined as follows. Let $s \in \Sigma^{\mathbb{N}}$ be a (countably) infinite string of symbols from some finite alphabet $\Sigma$, and let $s[1:i]$ be the prefix of the first $i$ symbols in $s$. In your case $s$ is the input and and $\Sigma$ is the nonnegative positive integers $\{0, \ldots, 60000\}$. $L(s)$ can be defined as a language of triples $(s[1:i], a, j)$ where $(s[1:i], a, j) \in L(s)$ if and only if there are $j$ occurrences of $a$ in $s[1:i]$. Convince yourself, using the pumping lemma, that for any fixed $s$, $L(s)$ is not regular. Then convince yourself that if a bounded memory Turing machine could solve your problem, it could also recognize the non-regular language $L(s)$. This argument ought to work even if we fix $a$ and define a similar language $L(s, a)$.

These kinds of examples are the reason why our computational model of choice (our = the algorithms community) is the word RAM machine, and we assume that word size grows with input size. This is supposed to model the fact that as the instances we face in reality grow, so does the memory of our computers. Of course, at some point we'll face physical limits of the hardware: there is only so much memory that can be accessed fast by a single/finitely many processors. One way to go beyond these limits is memory hierarchies and the modeling becomes more complicated, but there is some very nice theory as well (see external memory models and cache-oblivious algorithms).


Power of Double - Logarithmic Space I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich.
The goal is to show that the given set $S=\left \{ w_k \mid k \in \mathbb{N} \right \}$, where $w_k$ - concatenation of all $k$-bit long strings separated by *'s is not regular and yet it is decidable in double-logarithmic space. The exercise contains guidelines, and I would like to shed the light on few sentences from guidelines in order to solve the exercise.

In the guidelines it's mentioned that

  we can take advantage of of the *'s (in $w_i$) , the $i$th iteration
  can be implemented in space $O(\log i)$

The $i$th iteration is verifying whether $x = w_i$, which is really can be decided in $O(\log i)$ space, where $\log i$ can be used to note the position in $i$ long string, but the position in $x$ can be included in $O(\log i)$ or not?

  Furthermore, on input $x \notin S$, we halt and reject after at most
  $\log |x|$ iterations.

It means only $\log |x|$ $w$'s from the set S will be compared to $x$. Why it is actually so?

  Actually, it is slightly simpler to handle the related set
  $\left \{w_1**w_2**..**w_k \right \}$

Why it is actually so, and I would call it set, it is rather concatenated string.

Well, the set $\left \{w_1**w_2**..**w_k \right \}$ contains only one single element, but is nevertheless a set. And TM can accept only languages, which are sets of words.

Why is it slightly easier? Hmm, I would say, it is easier since you can simplify the algorithm slightly. You have one counter for $k$, and then you check, whether in the string $\cdots *x*y*\cdots$, you have $\text{bin}(y)=\text{bin}(x)+1$ on every position. You do not have to care about detecting the right $k$. Other than this, the suoer-string is longer, which gives you more space. But this effect vanishes in the big-O.


Is language equality for linear context-free grammars decidable? Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?

In general, this problem is undecidable. However, if both $G_1$ and $G_2$ are left-linear (or right-linear) grammars, then the problem is decidable, because both grammars describe regular languages.

My question is whether or not the same problem is decidable when both grammars are linear. Also, if anybody can point to relevant literature, that will be highly appreciated!

Quoting from Amiram Yehudai, The Decidability of Equivalence for a
Family of Linear Grammars, Information and Control 47, 122-136 (1980), page 1:

  The equivalence problem for various families of languages is of great
  interest in the theory of formal languages. This problem is decidable
  for regular languages (Rabin and Scott, 1959) and undecidable for
  context-free languages (Bar-Hillel et al., 1961). It is also
  undecidable for the family of linear context-free languages, as
  follows from Lemma 1 in (Baker and Book, 1974). The family of uniform
  linear languages is a natural and nontrivial subfamily of the linear
  languages for which equivalence is decidable.

This refers to Baker, B. S. and Book, R. V. (1974), Reversal-bounded multipushdown machines, J. Comput. System Sci. 8, 315-332, which, in the proof of that Lemma 1, presents a subset of linear context-free languages such that deciding whether a member of the set is equal to $\Sigma^*$ is equivalent to deciding the Post Correspondence Problem.


Prove little o with just the definition I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation.

Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am supposed to prove, or disprove, the following statement: $f(n) \in \mathcal{o}(g(n))$.

I am fairly sure that it's true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $\mathcal{O}$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $\mathcal{o}(g(n)) = \{f(n)|\forall C > 0 \exists n_{0} \forall n\geq n_{0}:f(n) < C * g(n)\}$. This means other than with big $\mathcal{O}$, where it suffices to show that there's at least one pair $C$ and a $n_{0}$ so that $f(n) \leq C * g(n)$  $\forall n \geq n_{0}$, I now have to prove that for every $C > 0$, there is such a $n_{0}$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $\mathcal{O}$, because you can prove with induction that $2^{n} < n!, \forall n\geq 4$. Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance!
(It would already help to know how to start. Probably like, let $C$ be greater 0, and then I have to show that for any Value of this $C$, there is... because...
My biggest struggle is to find meaningful estimations to get a chain of inequalities.)


'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges Take the language $L = \{a b^n c^n \; : \; n \geq 0\}$.

It's obvious that $L$ is non-regular because $\{b^n c^n \; : \; n \geq 0\}$ is non-regular, but I don't know a satisfying way to show that to the hypothetical Devil's advocate reading my proof without dragging out a full argument using the pumping lemma.

Is there some property of languages that can allow us to easily deduce that $L$ is non-regular if its accepted as known that $\{b^n c^n \; : \; n \geq 0\}$ is non-regular?

It is known that regular languages are closed under homomorphisms. In particular, if $L$ were regular than so would $h(L) = \{b^nc^n : n \geq 0\}$ be, where $h$ is the homomorphism given by $h(a) = \epsilon$, $h(b) = b$, $h(c) = c$. Since $h(L)$ is not regular, so is $L$ non-regular.

More generally, you can use proof by contradiction together with operations under which regular languages are closed. The idea is to start with your language, perform a bunch of operations, and end up with a non-regular language. If all operations you used preserve regularity, then you can conclude that the original language is not regular.


Numerical stability of linear interpolation Is one of these two functions more numerically stable than the other?

def interpolate_a(x, y, z):
    return y + (z - y) * x

def interpolate_b(x, y, z):
    return y * (1 - x) + z * x

If so, which one is better and why? After testing these functions with several million inputs, they have always returned the same value. My concern is that with certain inputs, they may return different values, and one will be more correct that the other. Is this possible?

"Numerical stability" is a much vaguer term than most people realise. We typically use it when referring to an approximation method, such as some kind of linear analysis, or numeric quadrature, or solving (possibly partial) differential equations. It refers to the property that given some appropriate assumptions (e.g. the inputs are reasonable), the algorithms converges to the ideal solution reasonably, even in the presence of floating-point error.

That's actually not what you're referring to here. However, there is a good answer to the question that you are trying to ask. If x is between 0 and 1 inclusive (and this is an important proviso; it's called "interpolate" but could be used to extrapolate), then interpolate_b is better.

In any sensible system of floating point (e.g. IEEE-754), you can assume several things:

Multiplying a finite number by zero returns a zero.
Multiplying a finite number by one returns that number.
Adding zero to any finite number returns that number.
For any finite number x, x - x returns a zero.

Standard provisos: Inf is not a finite number. NaN is not a number at all. Negative zero is a thing.

The negative zero thing is occasionally relevant, so when I say "returns a zero", or "returns that number" when that number happens to be zero, do be aware that you may get a zero of the opposite sign that you might expect under some circumstances. The exact rules are complicated, and we won't go into them here.

Still, it's more correct to say, for example, that if x is a finite number which is not zero, then x+0 and x+(-0) are both identical to x. If x is zero, then x+0 and x+(-0) may not be identical, and may not be identical to x, but they will differ from x by at most a sign bit.

First, consider the case where x is zero (and neither y nor z are negative zero). Then both interpolate_a and interpolate_b return exactly y. So far, so good.

Now consider the case where x is exactly 1. Then interpolate_a returns y + (z - y), because the multiply by x is a no-op. This may not be exactly equal to z due to round-off error. (Exercise: Find two single-precision IEEE-754 numbers which have this property in the default rounding mode.)

However, if you follow through the logic above, you can see that if x is exactly 1 (and neither y nor z are negative zero) then interpolate_b returns exactly z.

It's almost always considered a desirable property of any interpolate function that they return exact values at the endpoints. It's this property that makes interpolate_b a better choice.


Closure under reversal of regular languages: Proof using Automata I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

Under the topic of Reversal, they have tried to prove that the regular languages are preserved under the reversal of closure. They have stated the following (for a regular language $E$):

  $E = E^{*}_{1}$. Then $E^R = (E^{R}_{1})^*$

I wasn't able to get their justification so I took the following approach:

Tried to take up an example, say $E_{1} = 01^{*}$
Draw an NFA that accepts the regular expression $E_{1}$
Draw AN NFA that accepts the Kleene's closure of $E_{1}$, i.e. $E = E_{1}^*$
Convert the NFA into a DFA, and reverse the DFA into an NFA to get $E^{R}$.
Reduce the NFA of step 4 to a DFA again.

This is my work regarding the same:

Now for the right hand side, i.e. $(E^{R}_{1})^*$,

Created an NFA that accepts $E_{1}$ and reducing it to DFA
Created an NFA that accepts $E_{1}^{R}$ by reversing
Created an NFA that accepts $(E^{R}_{1})^*$ by taking the Kleene Closure, and then reduced it to a DFA.

This is my work for the second half:

However, the two DFAs I get at the end are not similar. Can anyone help me with the error I might be making?

Plus, how can we prove the same in a way other than DFA/NFA construction?

You are asking two questions. I will only answer the second one. Recall that $L^* = \bigcup_{n=0}^\infty L^n$. I will show that $(L^k)^R = (L^R)^k$, and then it easily follows that $(L^*)^R = (L^R)^*$.

To show that $(L^k)^R = (L^R)^k$, notice that:
$$
(L^k)^R = \{ (w_1\ldots w_k)^R : w_1,\ldots,w_k \in L \} = \\
\{w_k^R \ldots w_1^R : w_k,\ldots,w_1 \in L \} = \\ \{z_k \ldots z_1 : z_k,\ldots,z_1 \in L^R \} = (L^R)^k.
$$
If you want to be more formal, you can prove this by induction on $k$. The crucial observation is $(xy)^R = y^R x^R$, which you can also prove by induction if you want to be very formal.


Optimize sorting matrix entries by row and column I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be inserted in the tree. I am defining the ordering of the matrix elements simliar to how C handles a row-major ordered dense matrix. In particular, a matrix element $(i_a,j_a)$ comes before $(i_b,j_b)$ if:
$$
N i_a + j_a < N i_b + j_b
$$
I need to write a routine which returns $-1$ if $(i_a,j_a)$ is less than $(i_b,j_b)$, $+1$ if $(i_a,j_a)$ is greater than $(i_b,j_b)$ and $0$ if they are equal. I want this routine to be as fast as possible since I will be calling it hundreds of millions of times.

I've tried two options so far, which I implement as macros to avoid the overhead of a function call.

Option 1:
Comparing rows first and then compare columns

#define COMPARE(ia,ja,ib,jb) (ia < ib ? -1 : (ia > ib ? 1 : (ja < jb ? -1 : ja > jb)))

The worst case for this option is 4 comparisons between integers.

Option 2: Compare full linear index

#define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)

The worst case for this option is 2 multiplies, 2 adds, and 2 comparisons (assuming the compiler optimizes so that the quantities $N i_a + j_a$ and $N i_b + j_b$ are computed only once).

So far, Option 1 is a clear winner, and runs faster by around 20-30% on tests I have done.

My question is: can anyone suggest a way to optimize this even more, by somehow improving on Option 1, or perhaps suggesting a completely different method of sorting matrix elements in the tree?

Profiling has shown that a significant amount of time is spent in this comparison function, so it is worth it to me to make it as fast as possible.

Another idea I have is to use 2 levels of binary trees. The high-level tree uses only row indices for sorting. Then each node in that tree contains a pointer to another tree which uses the column indices for sorting. This way the comparison function only needs to compare two integers instead of 4. But having 2 levels of tree would make things more complicated. I have not implemented or benchmarked this approach yet.

Option 2: Compare full linear index
  #define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)

Instead of N, use the minimal power of 2 that is not less than N. For example, if N = 10000, use $2^{14}=16348$. So we can have #define COMPARE(ia,ja,ib,jb) ((ia << 14) + ja < (ib << 14) + jb ? -1 : (ia << 14) + ja > (ib << 14) + jb).

Instead of using #define, we can use a function to make sure that long expression is computed only once. forceinline is defined to be the cross-platform forceinline modifier.

#define TWO_EXPONENT 14
forceinline int compare(int ia, int ja, int ib, int jb) {
    int t1 = ((ia - ib) << TWO_EXPONENT) + (ja - jb);
    return (t1 > 0) - (t1 < 0);  //branchless computation
}

You have specified that you need to return 3 values, 1, 0, and -1. That sounds more than enough. You may want to double check if it is enough to use 1 for the case of "not smaller than". That is enough, for example, when we just want to sort an array of numbers.

Just in case you have not noticed, there are a wealth of information on how to store sparse matrix, Google search or Wikipedia entry.


If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)? Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?

No. You can't. As $\lim_{n\to\infty} \frac{n!}{n! \times n} = 0 $. Hence, $n! \times n  = \omega(n!)$ or $n! = o(n\times n!)$ (little-oh).


Polynomial space complexity with exponential size witnesses Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has:

Input tape: Read only, move in both directions.
Witness tape: Read only, move only in one direction.
Work tape: Read-Write, move in both directions.

The machine itself is deterministic (the guesses are the value of the witness tape). The space complexity is the size of the work tape, and is polynomial. We say the machine
accepts an input if and only if there exists a setting for the witness tape, with which the
machine accepts.

Prove: $C = \mathrm{PSPACE}$

Well, it's obvious that $\mathrm{PSPACE} \subset C$ since any TM $M$ can be converted into a TM $M'$ that simply ignores its witness tape and runs in the same space complexity as $M$.

However, I'm struggling with the other direction. The problem is that the witness can be exponential in the input and I can't see how we can enumerate over all witnesses using only polynomial space.

edit: I had a mistake, the witness tape can only be read in one direction.

Hint: Use Savitch's theorem to show that PSPACE=NPSPACE.


Do Karnaugh maps yield the simplest solution possible? I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example:

Truth table (inputs are A B C; output is F):

A   B   C   |   F
0   0   0   |   1
0   0   1   |   0
0   1   0   |   1
1   0   0   |   0
0   1   1   |   1
1   0   1   |   1
1   1   0   |   0
1   1   1   |   1

The Karnaugh map looks like this:

AB
--
C|

    00  01  11  10
    --------------
0|  (1  1)  0   (1)
1|  0   (1  1)  (1)

And this yields $\bar{C}\bar{A}+CB+A\bar{B}$. Is there any simpler way of choosing the 1s from the map and getting a simpler result? Are Karnaugh maps guaranteed to always yield the simplest result possible?

Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html).