Sampling numbers from a weighted set that sum to constant value So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to weights $W$ such that the sampled numbers sum to a given constant positive integer $k$.

The naive way to do it, as I understand it, is to find out all combinations of numbers from $S$ that sum to $k$ and add their weights and choose one of the combinations according to the sum of weights. But doing that is $O(|S|^k)$, which is unacceptably large.

What I'm doing right now is do a weighted shuffle of $S$ according to weights $W$, and picking number in the obtained order until the requirement is fulfilled. If, for example, the order obtained is $3, 2, 3, 2, 1$ and $k = 4$, then I'll pick $3$, ignore $2$ (as picking it will exceed $k = 4$) and pick $1$. This approach turns out to be $O(n\log\ n)$.

Does anyone have a better idea for doing this sampling in a way that is faster than exponential but more robust than what I'm currently doing now?

There's a close connection between counting the number of solutions and randomly sampling from the set of solutions.  Any time you need to randomly sample, it's often helpful to ask yourself how you'd count the number of solutions, and then you can often turn that into a way to randomly sample.

So, one approach is to use dynamic programming to count the number ways to select numbers from $S$ that sum to $k$ (weighted by their weights $W$), then use that to help you sample from this space.  Let me spell out the details more.

Define

$$f(S,W,k) = \sum_I \prod_{i \in I} w_i,$$

where $I$ ranges over all sets of indices such that $\sum_{i \in I} n_i = k$.  Notice that if all the weights were 1, then $f(S,W,k)$ would count the number of ways to select these numbers; in general, with arbitrary weights, you can think of $f(S,W,k)$ as a weighted count, where you sum up the weights of each candidate combination, and the weight of a combination is the product of the weights of the numbers selected.  You can compute $f(S,W,k)$ using dynamic programming, using the recurrence

$$f(\{n_1,\dots,n_j\},W,k) = f(\{n_1,\dots,n_{j-1}\},W,k) + w_j f(\{n_1,\dots,n_{j-1}\},W,k-n_j).$$

Now you want to sample a set $I$ with probability proportional to $\prod_{i \in I} w_i$.  This can be done, using your algorithm for computing $f(S,W,k)$.  In particular, if $S=\{n_1,\dots,n_m\}$, then flip a coin with heads probability

$${f(\{n_1,\dots,n_{m-1}\},W,k) \over f(\{n_1,\dots,n_m\},W,k)}.$$

If it is heads, then don't include $n_m$ in the solution: instead, recursively sample some numbers from $\{n_1,\dots,n_{m-1}\}$ that sum to $k$, and output that as the random sample.  If it is tails, then do include $n_m$ in the solution: recursively sample some numbers from $\{n_1,\dots,n_{m-1}\}$ that sum to $k-n_m$, then add $n_m$ to that combination, and output that as the random sample.  You can see that this induces the correct probability distribution on samples.

Overall, the running time will be comparable to the time to compute $f(S,W,k)$, or in other words, the running time will be $O(|S| \cdot k)$.  This is much better than the $O(|S|^k)$ naive solution.  It can still be very slow if $k$ is enormous, but if $k$ is not too big, it might be perfectly satisfactory.


How do you classify properties as Trivial and Non-trivial? I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone help me understand this better, maybe with some good examples?

A property $P$ is a set of Turing machines. The property is trivial if it contains every TM, or if it is empty.

Essentially, in order to check if a property is trivial, just check if there is a TM that satisfies it and if there is a TM that does not satisfy it. If both kinds exist, then the property is nontrivial. Otherwise it is trivial.

However, deciding this can be difficult...

For example, consider the property $\{M: L(M)=\emptyset\}$. This is a non-trivial property, since there are TMs with an empty language, and there are TMs with a nonempty language.

A trickier example is $\{M: L(M)\in RE\}$. Initially, this may seem like a nontrivial property. But recall that every TM recognizes its own language. So $L(M)$ is in RE for every $M$. Thus, this property is simply the collection of every TM. So it is trivial.


How to find the minimum number of states required by a DFA Given a language $L = \left\{ a^{nk+1} | n > 0 \right\}$ and $k$ is an integer constant.

How to show that a DFA for this language must have $k+2$ states or more states using minimum state lemma.

By minimum state lemma I mean the number of minimum state a DFA has is the number of pairewise distinguishable states. I have constructed a set of pairewise distinguishable string ${a, aa, aaa, ... a^{k+2}}$ with respect to L and found that I can not add anymore strings to it. But I don't know how to prove this string has the maximum number of pairewise distinguishable strings.

You can prove that your set is maximal in (at least) two different ways:

Show that every string is equivalent to one of the strings in your set.
Construct a DFA for the language having the same number of states as are strings in your set.

In your case both approaches are not too difficult.

Note, however, that the question only asks you to show that every DFA for the language must contain at least $k+2$ states. For this there is no need to show that your collection is maximal. If you find $k+2$ pairwise inequivalent strings, then it follows that every DFA for the language must contain at least $k+2$ states. If the collection is not maximal, all it means is that your bound isn't tight.


Are there strongly-polynomial algorithms that take more than polynomial time? In [1] strongly-polynomial is defined as either:

The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

Why do they restrict to polynomial TM space as opposed to polynomial TM time? (this came up here)

It seems strange for an algorithm that takes a number of TM steps unboundable by a polynomial to still be considered strongly-polynomial (provided it takes polynomial space and a number of arithmetic operations polynomial in the number of numbers in the input). Can it be shown that such an algorithm does not exist? Perhaps based on this argument: the number of arithmetic operations would not be polynomial, since under the arithmetic model every operation is an arithmetic operation (?).

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

No, any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model. That is the whole point of strongly-polynomial vs weakly-polynomial.

When you've analysed algorithms in the past, you've probably assumed that your arithmetic operations (addition, multiplication, etc.) take unit time. This is the arithmetic model of computation, where a step is defined as one arithmetic operation and input size is the number of integers. In the TM model, this isn't true, as a step is defined as moving the head and input size is defined as the number of bits used to represent the input. Thus arithmetic operations take time proportional to the number of bits used to represent them.

The definition restricts to TM space because that's the only condition you need to convert a polynomial time algorithm in the arithmetic model to a polynomial time algorithm in the TM model. The algorithm is already polynomial time in the arithmetic model, so as long as it's space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

In the case where you can't bound the space of your algorithm, you can't guarantee anything about the time when converting between the two models. There exist algorithms that take polynomial time in the arithmetic model but not in the TM model, and vice versa. Drawing examples from wikipedia let's elaborate on this.

An algorithm that is polynomial in the arithmetic model but not the TM model
Suppose given the integer $2^n$ we wish to compute $2^{2^n}$ by repeated squaring. The integer $2^n$ takes space proportional to $n$ (i.e. the bits used to represent it). However $2^{2^n}$ takes space proportional to $2^n$, which is exponential in the size of the input. In the arithmetic model this algorithm is clearly polynomial since we perform $O(n)$ multiplications assuming each takes unit time which is polynomial in the input size. However the resulting value is exponential in the size of the input, so in the TM model this would take exponential time simply to write the bits necessary to store the result. Note that if we could bound the space of the algorithm, then we can guarantee that it is polynomial in the TM model as well.

An algorithm that is polynomial in the TM model but not the arithmetic model
The standard GCD algorithm is one such example. Given two integers $a,b$ computing $gcd(a,b)$ takes $O((\log(a)+\log(b))^2)$ steps which is polynomial in the size of the input $\log(a)+\log(b)$. However in the arithmetic model the size of the input is just two integers and we can't bound the number of steps of the algorithm since it depends on the magnitude of $a$ and $b$.

Notice that the last example does not contradict the definition of strongly-polynomial. Strongly-polynomial doesn't say anything about algorithms that are polynomial in the TM model, it's only defined in the arithmetic model. If an algorithm is polynomial time in the arithmetic model and also happens to use space bounded in the size of input in the TM model, then it is strongly-polynomial.


Perfect matching in a bipartite regular graph in linear time Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.

It is easy to show that there is a perfect matching for the graph, by using flow and showing a flow of size $|V|/2$.

Using flow networks, we can also use Dinic's algorithm to find the max-flow which is equal to the perfect matching (thus, deriving a perfect matching) in $O(|E|\cdot\sqrt{|V|})=O(|V|^{3/2})$ (Since $E=O(|V|)$).

Can we find a perfect matching in linear time?

Thanks!

There is a classical linear time algorithm of Gabow and Kariv.

The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, you find another vertex which has unused edges, and start a new walk from there. Eventually, you will have decomposed all edges into cycles. If you're careful, you can implement this algorithm in $O(n)$; see Wikipedia for hints.

Since the graph is bipartite, all cycles have even length. Remove from each cycle every other edge to obtain a bipartite 2-regular graph. Now repeat the same process to obtain a perfect matching.

This algorithm works more generally for $d$-regular graphs whenever $d$ is a power of 2. It runs in time $O(m)$ even for non-constant $d$ (here $m$ is the number of edges). Cole, Ost, and Shirra devised an $O(m)$ time algorithm for any value of $d$, Alon devised a simple $\tilde{O}(m)$ algorithm for the same problem, and Goel, Kapralov and Khanna gave a randomized $\tilde{O}(n)$ algorithm in the same setting.


What are the primal and dual planes in the context of the point-line duality? In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact definition of the primal and dual planes is often not given in the literature. It's a little bit confusing which one is which. What are exactly the primal and dual planes in this context?

In short, the original $(x, y)$-plane is the primal plane and the new $(a, b)$-plane the dual plane.

More specifically, in a $(x, y)$-plane (or coordinate system)1, a non-vertical line can be represented as $\ell \colon y = ax - b$, where $a \in \mathbb{R}$ is the slope and $b \in \mathbb{R}$ the $y$-intercept. Hence, to describe a line, we just need to scalars, $a$ and $b$. We can state that a line has two degrees of freedom.

The idea of the duality between lines and points is that lines in the $(x, y)$-plane can be thought of or represented as points in a new $2$-dimensional space (or coordinate system), in which the coordinate axes are labeled $(a, b)$, rather than $(x, y)$. This new plane is denoted or labeled as $(a, b)$ to emphasize the fact that the values that $a$ and $b$ may assume respectively refer to the slope and $y$-intercept of the line $\ell$ in the original $(x, y)$-plane.

For example, the line $\ell : y = 2x + 1$, in the $(x, y)$-plane, corresponds to the point $\ell^* = (2, −1)$ in this new $(a, b)$-space 2, 3; that is, $\ell^*$ is a $2$-dimensional point with $2$ as the value of the $a$-coordinate and $-1$ as the value of this $b$-coordinate. A point $p=(5, 2)$ in the $(x, y)$-plane corresponds to the line $p^* \colon b = 5 a - 2$ in the $(a, b)$-plane 4. Similarly, a point $q = (1, 6)$ in the $(a, b)$-space, corresponds to a non-vertical line, $q^* \colon y = 1x − 6$ in the "original" plane $(x, y)$. And a line $t \colon \frac{1}{2} a - 5$ in the $(a, b)$-plane corresponds to the point $t^*=(\frac{1}{2}, 5)$ in the $(x, y)$-plane.

A convention is to call the original $(x, y)$-plane the primal plane, and the new (a, b)-plane the dual plane.

Why is $(x, y)$ the "original plane"? What's "original" about it? It's simply the plane where our initial problem is formulated. For example, we may have a problem where we are given a set of points. Then, we say that those points are given in the primal plane. We may convert our points to lines in the dual plane, because maybe we can formulate our problem in terms of lines, and the new problem is easier to solve.

Of course, we could have labeled the "original" plane with other letters, e.g. $(g, h)$, but we often label it $(x, y)$, so the new system is labeled differently, e.g. $(a, b)$. We could have labeled the new plane or coordinate system $(o, z)$: it really does not matter, i.e. it's just notation!

Here's a picture which summarizes all these words

Notes

Note that we label this plane $(x, y)$, but could have labeled it $(u, v)$ or any other tuple of two letters: it does not matter (as long as we are consistent).
Note the $-$ (i.e. the minus) in front of the $1$ in the point $\ell^*$.
We use an asteristik, $*$, to denote the dual of some object. For example, $u^*$ is the dual (in the dual plane) of $u$ (in the $(x, y)$ or primal plane). $u$ can either be a line or a point. If $u$ is a line, then $u^*$ is a point. If $u$ is a point, then $u^*$ is a line.
Note the $-$ (i.e. the minus) in front of the $-2$ in the equation of the line $p^*$.


Understanding how convolution of images work in cnn I'd like to understand convolutional neural network.
Consider this quote from Stanford CS notes on Convolutional Neural Networks for Visual Recognition (CNNs/ConvNets):

  Example Architecture: Overview. We will go into more details below, but a simple ConvNet for CIFAR-10 classification could have the architecture [INPUT - CONV - RELU - POOL - FC]. In more detail:

  INPUT [32×32×3] will hold the raw pixel values of the image, in this case an image of width 32, height 32, and with three color channels R,G,B.
  CONV layer will compute the output of neurons that are connected to local regions in the input, each computing a dot product between their weights and a small region they are connected to in the input volume. This may result in volume such as [32×32×12] if we decided to use 12 filters.
  RELU layer will apply an elementwise activation function, such as the $\max(0,x)$ thresholding at zero. This leaves the size of the volume unchanged ([32×32×12]).
  POOL layer will perform a downsampling operation along the spatial dimensions (width, height), resulting in volume such as [16×16×12].
  FC (i.e. fully-connected) layer will compute the class scores, resulting in volume of size [1×1×10], where each of the 10 numbers correspond to a class score, such as among the 10 categories of CIFAR-10. As with ordinary Neural Networks and as the name implies, each neuron in this layer will be connected to all the numbers in the previous volume.

I don't understand why the result of applying convolution to the 32by32by3 input image is not of size 32 by 32 by 3 by 12?  From what I understand, we there are 12 filters and we apply each filter to each of the 3 channels of the image to get 3 new images for each filter.

Suppose the result of the first convolution is really 32 by 32 by 12, I don't understand how you get them.

Also, what happen when we do a second convolution? Say we do a second full convolution with 5 filters, then the result of the second convolution is 32 by 32 by 3 by 12 by 5?

We apply one filter to 32x32x3 image and output 32x32x1 image.And we stack all these twelve 32X32X1 images,which gives 32x32x12 volume.

check this image.In here we apply 5x5x3 kernal to 32x32x3 image with zero padding and stride 1.which gives you 28x28x1 output.if we use 12 filters like this,we get 28x28x12 volume.


Recurrence Question:T(n) = T(n − √ n) + T( √ n) + θ(n) I need help to solve the recurrence T(n) = T(n−√n) + T(√n) + θ(n)

The solution is $T(n) = \Theta(n^{3/2})$.

For the lower bound, note that $T(n) \geq T(n-\sqrt{n}) + \Theta(n)$. Iterating this for $\sqrt{n}/2$ steps, the value of the parameter never drops below $n/2$, for a total contribution of $\Omega(n^{3/2})$.

For the upper bound, let us notice first that
$$(n-\sqrt{n})^{3/2} \approx n^{3/2} - \sqrt{n} \frac{d}{dn} n^{3/2} = n^{3/2} - \Theta(n). $$
This allows us to prove the upper bound $T(n) = O(n^{3/2})$ by induction.


Is every NP-hard problem computable? Is it required that a NP-hard problem must be computable?

I don't think so, but I am not sure.

There appears to be some considerable confusion in this community regarding this question. I'll give a detailed answer in the hope of clearing up the water and illuminating the relationship between computability and NP-hardness.
First, I believe that being clear and explicit about the various definitions involved will resolve a lot of the confusion.

A string is a finite sequence of characters from some fixed finite alphabet.
A decision problem is a set of strings. (This set is typically infinite.) Think of the decision problem as testing strings for some property: the strings with the property are in the set, and the strings without the property are not.
Assume we have two decision problems, $A$ and $B$. Say $A$ is polynomial-time reducible to $B$ if there is some polynomial $p(x)$ and algorithm some algorithm $M$ such that, for all strings $s$,

If you provide $M$ with input $s$, $M$ halts in fewer than $p(|s|)$ steps (where $|s|$ is the length of the string $s$) and outputs a string $M(s)$.
$s$ is in $A$ if and only if $M(s)$ is in $B$.

A decision problem $B$ is NP-hard if, for every NP decision problem $A$, $A$ is polynomial-time reducible to $B$.
A decision problem is computable if there is an algorithm $M$, that, for all strings $s$,

If you provide $M$ with input $s$, $M$ halts and outputs either "yes" or "no".
The output is "yes" if $s$ is in $A$ and "no" otherwise.

With the above definitions, we can immediately clarify what I think might be the root confusion in your question: nothing in the definitions of decision problem, reductions, or NP-hardness requires the decision problems to be computable. The definitions make perfect sense thinking of decisions problems as arbitrary sets of strings, and these sets can be very nasty indeed.

That leaves two questions on the table:

The definitions leave open the possibility that non-computable functions might be NP-hard. Are there actually non-computable, NP-hard functions?
There is an intuition that saying a problem is NP-hard is saying that it is hard to solve. Saying that it is non-computable is like saying it's "really hard" to solve. So, are all non-computable problems NP-hard?

Question 1 is easier to answer. There are two particularly important ways to find non-computable decision problems that are NP-hard. The first is the halting problem: the halting problem, $H$, has the property that every computable decision problem is polynomial-time reducible to $H$. Since NP problems are computable, every NP problem is polynomial-time reducible to $H$, so $H$ is NP-hard.
The other important way to build a non-computable, NP-hard problem is to observe that we can combine any known NP-hard problem with any known non-computable problem. Let $A$ be NP-hard and $B$ be non-computable. Form the decision problem $A \oplus B$ as follows: $A \oplus B$ contains those strings of the form "0, followed by a string in $A$" and those of the form "1, followed by a string in $B$". $A \oplus B$ is NP-hard because we can turn any reduction (of any problem) to $A$ into a reduction to $A \oplus B$: just tweak the algorithm to output an extra "0" at the front of its output string. $A \oplus B$ is non-computable, since computing $A \oplus B$ requires deciding which strings that start with "1" are in the set; this is impossible, since $B$ is non-computable.

Question 2 is considerably tricker, but in fact there are non-computable decision problems that are not NP-hard (assuming P $\neq$ NP). Yuval's fine answer constructs such a decision problem explicitly. (For any computability theorists in the room, any "Cohen $\Pi^0_1$-generic" will do the trick, as well.) I'll break down why the intuition that "NP-hard problems are hard, non-computable problems are harder" is wrong.
NP-hardness and non-computability both say that a problem is "hard" in a very general sense, but they are very different and shouldn't be lumped together as the same kind of phenomenon. Specifically, NP-hardness is a "positive" property: an NP-hard problem $A$ is hard in the sense that, given access to a cheat sheet for $A$, you can solve a hard class of problems. On the other hand, non-computability is a "negative" property: a non-computable problem $A$ hard in the sense that you cannot solve $A$ with a given class of resources.
("Forcing," by the way, is the technique used to produce the "Cohen $\Pi^0_1$ generic" that I mentioned. To be very very vague, forcing is a general way to produce things that are "generic" in that they have no positive properties and every negative property. That's why forcing can directly produce a problem that's neither computable nor NP-hard.)


Fast ways to compute the smallest prime with a given substring? So, I've got this problem:

  Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0.

What I'm asking is a fast algorithm for the problem?

This answer only shows that every string actually appears in some prime. Without loss of generality, $\omega$ doesn't start with zero (otherwise, consider $1\omega$ instead). Consider all digits in the range $\omega \times 10^N$ to $\omega \times 10^N + 9 (10^{N-1} + \cdots + 10^0)$, an interval of length $10^N$. Let $M = \omega \times 10^N$. According to the prime number theorem, there are roughly $(M+10^N)/\log M - M/\log M \approx 10^N/\log M$ prime numbers in this interval. Since $10^N/\log M \to \infty$, for large enough $M$ there will be a prime number in the interval, and its most significant digits would be exactly $\omega$.

I don't expect there to be an algorithm much faster than going over all primes in sequence. If you expect the answer to be one of the first few primes (here few can be a rather large number, say $10^9$), then you can probably do some preprocessing to be able to handle such queries fast.


How do you find out if the polygon lies to the right of a regular vertex? In section 3.2 of the book Computational Geometry: Algorithms and Applications (by Berg et al.), the authors describe a procedure to make a polygon y-monotone. The algorithm distinguishes vertices into $5$ different types: "start", "end", "regular", "split" and "merge" vertices.

A regular vertex is a vertex which has one of its neighboring vertices above it, and the other neighbor below it. A regular vertex can be on the left or right chain of the polygon.

Given a regular vertex $v$, how do I find out if the polygon lies to the right or left of $v$?

The polygon is stored in a doubly-connected edge list. The vertices have coordinates and are stored in a normal DCEL data structure along with the half-edges and polygons. It seems reasonable to expect an elegant solution that uses the DCEL.

I'm going to assume that your DCEL is counter-clockwise (ccw) oriented, meaning that if we traverse the list of half-edges incident the polygon's interior in order we make a counter-clockwise walk of the polygon. (This is standard.)

Let $v_i$ be your vertex, from the DCEL you can easily obtain $v_{i-1}$ and $v_{i+1}$, the vertices immediately preceding and following (resp.) $v_i$ in the ccw walk of the polygon. (The DCEL will have an edge $e_{i-1}$ with target $v_i$ and an edge $e_{i}$ with source $v_i$ both incident to the polygon $P$, and that $source(e_{i-1}) = v_{i-1}$ and $target(e_i) = v_{i+1}$.)

If $v_{i-1}$ is below $v_i$ (and $v_{i+1}$ is above $v_i$) then $P$ is to the left of $v_i$. Otherwise it is to the right. You can see this by drawing out the two possible cases. The point is that locally as you travel from $v_{i-1}$ to $v_{i+1}$ the polygon is on your left, so if you are traveling from a vertex above $v_i$ to a vertex below it, in your view the polygon is on your left, but in the "global" view, the polygon is on the right. However, if you are traveling from a vertex below $v_i$ to a vertex above it, then your view and the local view both have the polygon on the left. And by the definition of a regular vertex, those are the only two things we need to check.

Of course since you already know that one of $v_{i-1}$, $v_{i+1}$ is above and the other is below you only need to check for one. Something like, if $v_{i-1,x} < v_{i,x}$ then $P$ is left, otherwise right.

Here is a sketch:

I saw the code base you are using in your other posting on DCELs, so here is the code version:

First you will need to augment your vertex data structure to have fields for x and y:

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
    double x, y;
};

bool polygon_isleftof(half_edge *he) {
  return he->next->tail->y > he->tail->y;
}

By the way, when dealing with DCELs I have found that for many applications it is best to work with half-edges directly rather than vertices (in other words, if you want to pass a vertex to a function, just pass one of the half-edges for which it is a tail/source). That way you get two pieces of information: 1.) the vertex you are interested in and 2.) the face your are interested in. So in the code above my polygon_isleftof tells you whether the vertex which is the tail of he is to the right of the face which is incident to he. If I instead passed a vertex and a face the code would be much slower:

bool polygon_isleftof_slow(vertex *v, face *f) {
    //first we need to find a half-edge incident both f and v
    half_edge *walk = v->rep;
    //loop over all half-edges with tail equal to v:
    do {
        if (walk->left == f) break; //exit the loop if we find a half-edge incident f
        walk = walk->twin->next;
    } while (walk != v->rep);

    //If we didn't find a half-edge incident f and v, then return false:
    if (walk->left != f) {
        return false;
    } else {
        return walk->next->tail->y > walk->tail->y;
    }
}

Notice that in the first case, polygon_isleftof is $O(1)$ whereas in the second case polygon_isleftof_slow is $O(n)$. And since you are probably traversing the polygon using half-edges anyway, there is no reason not to just operate on half-edges and only access the vertices as needed in functions.


What does it mean for a function to be decidable? (homework) Note: This is part of a homework exercise. I am asking for clarifications, not a solution!

Given: Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a strictly monotone function, i.e., $\forall n\in \mathbb{N}: g(n)  < g(n+1)$.

Prove that $g(\mathbb{N})$ is decidable.

Clarification of the assignment:
I am not sure I understand the exercise correctly. What does it mean that a function is decidable? I assume that it's a decision problem of the form "For $x \in \mathbb{N}$, is $x\in range(g)$? For a function $g$ to be decidable, we can then define a decision procedure that returns $yes$ or $no$ for any $x$.

Is this correct? Or am I on the wrong track?

They are not asking to prove that the function $g$ is decidable, but the image $g(\mathbb{N})$ is decidable. The image is a subset of $\mathbb{N}$, namely
$$g(\mathbb{N}) = \{ k \in \mathbb{N} \mid \exists n \in \mathbb{N} . g(n) = k \}.$$
The question reduces to showing decidability of "given $k$, does there exist $n \in \mathbb{N}$ such that $g(n) = k$?".


In a DFA, does the restriction for a total transition function apply to accepting states? I recently discovered the idea of a total transition function in Automata Theory. To my understanding this means that every state has at least one outgoing state.

My question is whether this restriction applies to accepting states, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.

Thanks in advance for any answers.

Unfortunately there seem to be several different definitions of DFAs in the literature. Here is the classical definition:

A DFA is a quintuple $\langle \Sigma,Q,q_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.
We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.
The language accepted by the DFA is $\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F \}$.

Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.
Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.
It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in state complexity (the number of states needed to accept a given language).


Why the alphabet of the digital information is composed of 2 elements? please don't offer an answer about "it's an electronic thing" or something like that, just keep reading.

I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the entire digital world.

My point is about the fact that information is entropy, things that are predictable or just don't vary over time don't carry any information, so if you want information you want entropy, and if you want entropy why you stick with just 2 elements for your alphabet ? It's like the minimum before making the thing completely "flat" and meaningless like an array full of 0 or Z, an array of 0 and 1 it's just the next step after that .

But the main reason why I don't accept the answers with "electronics in them" is that this kind of studies were based on math and theoretical stuff, Boole wasn't even a regular student, He was a self taught mathematician, and chances are that he was trying to solve or study a practical problem without even caring about electronic devices given the times he was in .

If you also consider the information as a bingo where you can call numbers from 1 to 100, and you can call 1 number for each session, you have 1% of probability to call any number in the range, and this probability doesn't change between sessions . But this doesn't grant you any entropy, it's just probability .

For example if you consider a single char a number in the Bingo and the fact that every char is contributing to a word with its positional value, the fact that the hello word is composed over time by

h
he
hel
hell
hello

with each char having the same probability this consideration, on its own, doesn't give you any entropy.

Things change when you introduce a dictionary of a given language and you associate it with the pool of chars you are fishing from. If you have that dictionary the word hello becomes predictable, and thus with less entropy and more order, by the time you write hel or h or he depending on the context and semantics .

So I guess the answer is that we use binary because no one speaks binary and there is no dictionary of words in binary and the binary is not sensitive to the context and thus retains more entropy ? Because the context plays a big role in lowering the entropy and let things appear more ordered then what they really are, and entropy can be also taught as just something "random" with less order because you don't know what to expect because there is no semantic. And I don't think that the positional value can be considered as a giveaway for semantic, you have the same probability of picking either 0 or 1 in your next cell of information, positional value doesn't change anything.

I'm probably terribly confused and confusing, but why we use binary ?

You are really asking three different questions:

Why are computers based on binary?
Why did Boole use a binary system?
What does all of this have to do with entropy?

The answer to the first question, as you suspect, relies on implementation details; see for example this question. In other circumstances, such as wired or wireless communication, information is transmitted in larger chunks, what is known as modulation.

The answer to the second question is simpler: Boole was formulating the laws of thought, that is logic, in which each statement is either true or false. That's your binary distinction.

Finally, I can't really follow your third question. According to Shannon's source coding theorem, you can optimally compress information using any channel. Text is usually stored as text since it's easier to process that way, but we can compress it to reduce its size to roughly the entropy. In some sense, text is stored using an alphabet of size roughly 64, including lower and uppercase letters, digits and punctuation marks. Other data is stored in bytes, which is an alphabet of size 256. All of this has nothing to do with entropy, rather it's ease of processing. These are just some thoughts, since I can't really understand this question.


How to find the closest N to the power of X to the given number? Let's say we have number 4920 and we want to find the closest $n^x$ to 4920

2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920

The question is, how do we find the closest $n^x$, where $n$ and $x$ are less than 2 digits long? (because $4913^1$ is not what I want)

Here is a general solution for the following problem:

  Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$.

Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b > m$ then there is no point to check any $b_0 > b$, hence we only need to check $O(\log m) = O(n)$ many different values of $b$ (we can find the maximal $b$ by comparing $2^b$ to $m$). For each value of $b$, we can find the best value of $a$ using binary search; this takes polynomial time for each $b$, and so polynomial time overall. Finally, we choose the optimal solution among the $O(\log m)$ possibilities.


change turing machine to RAM How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into a set of instructions (load/add etc).
For example, here's a TM:
M = ({q 0 , q 1 , q accept , q reject }, {0, 1}, {0, 1, t}, δ, q 0 , q accept , q reject )

having a transition function as follows:

Now, how can I formulate a set of RAM instructions from this?
Sample Solution:

You can implement, on a RAM machine, an interpreter that simulates the behavior of an arbitrary Turing machine (that's just a matter of programming, and there's nothing conceptually interesting or difficult about it); then use it on this particular Turing machine.  That's much easier to do, but might not lead to nice code for the RAM machine.
Or, you can understand/reverse-engineer the algorithm the Turing machine is using (this could be difficult), and then figure out how to implement that algorithm on a RAM machine (which is just a matter of programming once you understand the algorithm).
Asking "how do I write code on a RAM machine?" is not very different from "how do I write code in assembly language?"; you just do it, and there's not a lot of deep scientific or conceptual ideas needed, once you know what algorithms you are using.


Does this language have a context-free grammar? Here is a question that I encountered in one of my exams:

  Find one context-free grammar that recognizes the language:
  $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $

Can you find such a grammar? I even doubt its existence, but I have not been able to prove that.

No, this language is not context-free. This is because the language requires to iterate $b^mc^m$ with the same number $m$ each time. Even if we restrict to $n=0$ and $p=2$ then the resulting language $\{b^mc^mb^mc^m \mid m\ge 0\}$ is easily recognized as non-context-free. Formally this restriction is obtained by intersecting with a regular language, a known closure property of context-free languages. To prove a language formally non-context-free one might use the pumping lemma discussed elsewhere in this forum.

Perhaps that is a mistake in its specification. If for each iteration the number $m$ can be different, the resulting language is context-free. That language would be $L_1 = \{ a^n w d^n \mid n\ge 0, w\in \{\; b^mc^m \mid m\ge 0\}^*  \;\}$. As an example, $bbbcccbc$ is an element of $L_1$, but not of $L$.

How to find a grammar (for $L_1$)? Observe the nesting structure. Context-free grammars are good in nesting, and iteration. For instance the part $\{\; b^mc^m \mid m\ge 0\}^*$ is generated by $T\to AT, T\to A, A\to bAc, A\to\lambda$, starting with $T$. Now add a matching number of $a$'s and $d$'s on both sides by nesting: $S \to aSd, S\to T$.


Does converting algorithms into elementary recursive form preserve runtime bounds? There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class?

For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity?

By converting into elementary recursive form, I mean:

Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form.

By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else".

Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $x$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity).

This depends highly on the encoding.  If you consider bounded summation, the number of summations done is the value of the first argument of the function.

If the "encoding" (whatever that means) of the input is unary, this takes linear time, otherwise it takes exponential time in the size of the input. It is not obvious that it makes sense to assume input to be unary.

Elementary recursive functions are over natural numbers and do not speak of their encoding: is $s(0)$ encoded as $1$ or as $s0$?


How to understand the CRC Algorithm from the CAN specification? I am trying to understand how the cyclic redundancy check (CRC) algorithm from the Controller Area Network (CAN) specification works. Here is the pseudocode.

CRC_RG = 0;                         // initialize shift register
REPEAT
CRCNXT = NXTBIT EXOR CRC_RG(14);
CRC_RG(14:1) = CRC_RG(13:0);        // shift left by
CRC_RG(0) = 0;                      // 1 position
IF CRCNXT THEN
   CRC_RG(14:0) = CRC_RG(14:0) EXOR (4599hex);
ENDIF
UNTIL (CRC SEQUENCE starts or there is an ERROR condition)

I do understand the standard algorithms but not the CAN algorithm. I have calculated it by hand and programmed it and it works fine. I just don't understand why/how it works.

CRC(x) is remainder of polynomial division of x by some fixed polynomial. Here bits of x, as well as bits of result, represents polynomial with binary coefficients, f.e. 0b101 may represent polynomial 1*x^2 + 0*x + 1.

So, the algorithm you have cited, is the most straightforward one - if q(x) = p(x) mod f(x), then p(x)*x mod f(x) is either just q(x)*x (if it doesn't contain x^N where N is order of f(x) polynomial), or q(x)*x - x^N + (x^N mod f(x)). As you may note, the last sum component is some fixed polynomial for given f(x).

So, each step of this cycle do the following:

shift result by 1 bit left - equivalent to multiplication by x
if result contains x^N then xor result by x^N mod f(x)

Oh, well, there are some more details. Please read a painless guide to CRC error detection algorithms for real explanation.


How do you search a graph? An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one.  Got the first one but not the second.

What is the modern standard way to search a graph (assume undirected) given no other context? I've a notion that it might have something to do with Dijkstra's algorithm but IDK what. It makes sense that one way is to simply traverse the graph until you find the item you are looking for but it sure doesn't seem optimal.

Interviewer was probably fishing for words like: preorder, inorder, postorder traversal and depth-first versus breadth-first.  I am thinking of traversal as simply having an iterator over the graph that returns some vertices and edges in some particular order.  As Richerby says, you could fill books with all the various ways that this could happen.

As for searching graphs, if they didn't mean traversal; then they probably meant searching for subsets efficiently: If a graph is known to have implicit structure (ie: find all edges in: 192.168.4.0/24 -> 10.0.3.2/24 by hour, etc), then various kinds of searches over src/dst/time are often possible.  Facebook/Twitter, etc are utterly gigantic graphs of "at time T, A says X to B".


Does the write through cache copies the whole block or just the byte which is updated? Just a basic question to ask

Does the write through cache copies the whole block or just the byte which is updated?

I went through the following question

Array A contains 256 elements of 4 bytes each. Its first element is stored at physical address 4096.
Array B contains 512 elements of 4 bytes each. Its first element is stored at physical address 8192. Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct mapped, 2K-byte cache with an 8 byte block size. The following loop is the executed

for(i=0; i<256; i++)
A[i] = A[i] + B[2*i];

How many bytes will be written to memory if the cache has a write-through policy?

I calculated it as follows:

The cache can store the whole array with 2 elements per block (block size = 8bytes, element size = 4bytes). For every write, the whole block will be copied. For $0^{th}$ element, the block containing $0^{th}$ and $1^{st}$ element would be written. The same would be done for $1^{st}$ element as well.

So, for every iteration the 2 elements would be written. This makes the number of bytes as $256*2* (4bytes / element) = 2048bytes$.

But in the solution, they have just calculated the number of loop iterations ($256$) multiplied by the element size ($4byte$) which makes the answer $1024bytes$.
If this is true, then the cache would update only the updated byte (not the whole block).

Which is correct?

I would say that write-through cache always knows which addressable units need to be written, so there is absolutely no reason why it should write the rest of the block. Therefore it does not.

I am intentionally saying "addressable units", because (though I am not sure) it would generally be aligned units of the same width as the bus, i.e. usually 4-byte. But that has no effect here when the elements are 4-byte.

In contrast write-back cache is likely to only keep per-block modified status. However a write-back cache would be delaying the writes and since the consecutive passes through the loop end up overwriting whole blocks, it would still write just 1024 bytes.


How to understand the recurrence relation and time-complexity of StoogeSort? I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the values of $x$ and $y$.

Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[0...m−1])
        StoogeSort(A[n−m ...n−1])
        StoogeSort(A[0...m−1])
    end
end

The problem demands the following:

Show that the algorithm correctly orders the array A of n elements.
Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.
Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.
Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)
Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement. But how do I show this?

I have the following help:
For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n−1$ or fewer items, then it also works for n items. For the 3rd & 4th bullets, $c_1=0$, $c_2=1$ and $c_n=3c_m$. For the final bullet, show that any pair of items is never swapped more than once.

How should I interpret the help for bullets 4 and 5? Thanks in advance.

Here are some more hints:

The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
When $n=4$, the algorithm sorts $a_1,a_2$, then $a_3,a_4$, then $a_1,a_2$. You can easily give an example showing that this doesn't work.
You should be able to solve this yourself.
The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.
For a permutation $\pi$, the number of inversions is the number of pairs $i<j$ such that $\pi(j)<\pi(i)$. A permutation can have at most $\binom{n}{2}$ inversions (this is the number of pairs $i < j$). Each swap operation reduces the number of inversions by 1.


Algorithm to minimize an expression If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize
$$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$$
 if all of the $x_i$ are given?

One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.

For $n=2$ there is a solution:

Minimize $f(y) = x_1/y_1 + x_2/(k-y_1)$, it is convex for $y_1 >0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.

For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y_i = k \cdot \frac{\sqrt{x_i}}{\sum\limits_i {\sqrt{x_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.

UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y_i$ where the difference $ \frac{x_i}{y_i} - \frac{x_i}{y_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.


What is the difference between expected cost and average cost of an algorithm? While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.

In short, the average is the expected value of the uniform distribution.

If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is

$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$

given some random distribution for random variable $X$.

Average runtime is more specific and corresponds to

$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$

or, in other words, the expected runtime given a uniform distribution over inputs of the same size.

Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.


Lexing and parsing a language with juxtaposition as an operator Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for example, supposed to be included in the language Fortress (now a dead project).

Lexing and parsing such a language seems to me like it would be difficult within the usual lexer-parser framework. In a computer language, unlike human math notation, we want to have variable names that are more than one letter. So if we need to lex the string xyz, we have a problem, because this could, e.g., mean x*yz if x and yz are variables, but it could also mean xy*z if xy and z are variables. The lexer normally wouldn't have this type of information available, so it would have no way of resolving the ambiguity.

Are there ways of reducing this problem to a more standard form that can be handled by a traditional lexer-parser pair, or does it require qualitatively different techniques?

Juxtaposition is used in mathematics because most mathematical texts
use single character variables (possibly with diacritic signs,
subscripts, superscripts, etc...) so that there is no ambiguity.

A mathematician might write $2x$ to multiply $2$ and $x$. It would be
quite unusual to write $x2$ to multiply $x$ by $2$. Actually, as much
as I can see (but I am open to contrary examples) a numerical factor
always comes first in the product. This unstated rule implies that one
never has two numerical factors in succession, which would make it
difficult to interpret $22$, which could be $2\times 2$ or the single
number $22$.  Of course, if two numerical factors in a row were to be
acceptable, they would be separated by a space to avoid ambiguity.

Regarding variables, the same has to be true. Several variables can be
factors of a product (well, a sequence of products). Either you have a
rule that all variables are 1 letter (a constraint that cannot be
imposed on numbers), or you maust have a way to separate the
variables, either by a space, or by a $\times$ sign.

First I would point out that this is a pure lexer problem: how do I
determine what variables are juxtaposed as the factors of a product.
The fact that the operator are omitted is not really an issue for the
parser (though it may call for some appropriate techniques depending
on other syntactic aspects of the language, and the way they interact
with the feature we are discussing).

Of course, you can start playing games, like the following which you seem to be actually suggesting. Since all
variables are supposed to be declared (that is also true in
mathematics), you could juxtapose variables arbitrarily, without
spaces, to form a product, and rely on the lexer to determine how to
cut the string so that each cut out substring is a declared variable.
Of course, depending on what variables you have declared, this can
have an ambiguous result (as you suggest in your question), and produce a lattice of variables instead of a
sequence of variables.

I created the expression "lattice of variables" after the expression "word
lattice" used in speech recognition for exactly the same problem in a
different setting. For example, given that you have declared the seven
variables: a b c d ab bc cd. Then the string abcd can be cut into
several sequences of variables, that can be represented by a loopless
finite state automaton like the following (which is what is called a
word lattice in speech processing).

     /--- ab ---\
    /            \
    --- a --- b --\--cd --------\
-- /     \                       > -----
   \      \-- bc ------/--- d --/
    \                 /
     \-- ab --- c ---/

Creating this lattice is not difficult, using finite state techniques,
when the available variables are known. It would however probably
require some changes in standard lexers, as they usually identify
lexical element with simpler techniques, simpler use of context.

One way to do it is for the lexer to first identify the string as an
expression. It could then call a routine that would access the current
symbol table to find relevant identifiers and organise them as a trie
to cut the string into existing identifiers. Assuming no ambiguity,
the lexer could then give the successive identifiers to the parser,
interspersed with $\times$ symbols.  So it is rather easy to integrate
into existing architectures.

To limit the ambiguity, one can first eliminates by type checking all
variables with a type incompatible with use as factor in a product.
Or possibly, if there are different kinds of products requiring
compatible types, this can be used to eliminate inconsistant sequences
of variables.

Remaining ambiguities would probably no be a major problem for the
parser (possibly depending on parsing techniques, typing ...). But of
course, the ambiguity has to be resolved at some point, if the
language is supposed to convey only one meaning.

One way to do it could be to notify an error whenever such an
ambiguity is found, with some details about the ambiguity, thus
requesting the user to disambiguate by adding a space or a $\times$
symbol.

Though this can be handled technically, I do not think I would
recommend it in a language. Even if unambiguous, this is not extremely
readable, notwithstanding the fact that the ancient languages such as
Latin and Greek used to be written that way.

An alternative could be to accept this kind of notation only with the
usual constraints (in mathematics) that I stated above: number must be
first and variables must have a single letter for implicit product. But ambiguity could
remain between a single variable $xx$ and the product $x\times x$
written without the $\times$ symbol. I guess it would not be very
hard, with standard technology.

I think I have exhausted my imagination on this topic. It is not
technically difficult, for what I can see.
But why would all this be worth the trouble?


Significance of parameters in Tiny Mersenne Twister algorithm I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned integers "mat1", "mat2", "tmat", and an array called "status" which is four 32-bit unsigned integers wide.

I am relatively new to the subject of random number generation; however, I have been able to teach myself a lot about the subject over the past couple of weeks. I know what the purpose of a seed is, different methods such as linear congruent, LSFR, GFSR, etc. So I've been doing my "homework" and researching the topic to the best of my ability (contrary to what the guys at Stack Overflow think). Unfortunately, the Mersenne Twister in general is extremely poorly documented and very few documents exist to explain the code and math side-by-side. The TinyMT's documentation is even worse, it's virtually non-existent! So developing accurate Doxygen comments for this part of the API is going to be tricky.

With that said, hopefully somebody more qualified than I can help me out here. What is the significance of the aforementioned parameters? What do they do, what do they mean, what do they stand for, etc? My guess would be as follows:

mat1 - Matrix 1
mat2 - Matrix 2
tmat - Tempering Matrix
status - 127 bit wide "seed" (where the last bit goes, I'm not sure)

Given that the user provides values for "mat1", "mat2", and "tmat," are there any precautions they need to take before supplying values for them? Again, this is for an API and its documentation, so I would like to be able to give the customers a good idea of what they need to use the RNG and hopefully make the lives of other fellow programmers easier. Thanks!

You can generate parameters for the PRNG using the provided program tinymt32dc. You should generate these parameters once and for all for each application. Each time you call the PRNG, you use the same parameters but a different seed. The reason that you don't want to vary the parameters is that generating them is (apparently) time consuming, while initializing the PRNG from just the seed is designed to be quick.

There might be some constraints on these parameters, but since you're not the designer of TinyMT, you're not aware of them. Instead, you should just use the provided program that generates legal parameters.


Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization problems in weighted graphs:

Consider the following pairs of minimization-maximization problems in weighted graphs:
(a) - MINIMUM SPANNING TREE and MAXIMUM SPANNING TREE (we seek the heaviest connecting tree).
(b) - SHORTEST PATH (recall Problem 1.4.15) and LONGEST PATH (we seek the longest path with no repeating nodes; this is sometimes called the TAXICAB RIPOFF problem).
(c) - MIN CUT between $s$ and $t$, and MAX CUT between $s$ and $t$.
(d) - MAX WEIGHT COMPLETE MATCHING (in a bipartite graph with edge weights), and MIN WEIGHT COMPLETE MATCHING.
(e) - TSP, and the version in which the longest tour must be found.
Which of these pairs are polynomially equivalent and which are not? Why?

Let's denote an edge $e \in E$ that connects vertex $u$ and $v$ and has weight $w_e$ as $e = (u, v, w_e)$. Let $M = max(|w_e|) + 1$. I was able to solve some of them by using the following reduction: given a graph $G = (V, E)$ construct the graph $G' = (V, E')$ where you construct the set $E'$ as follows: for each edge $e = (u, v, w_e) \in E$ add the edge $e' = (u, v, M - w_e)$ to $E'$. For some of the mentioned problems, the minimization version in graph $G$ is equivalent to the maximization version in graph $G'$.
I was able to solve itens (a), (d) and (e) using this trick. I am not sure if this trick applies to (c), and I think it does not work for (b).
Can anyone tell me if my attempt at itens (a), (d) and (e) are correct? Also, how do I solve itens (b) and (c)? Thanks in advance.

For item (b), the reduction does not work. To understand why, imagine a graph with all edges having the same weight. Then, the reduction has no effect: $G = G'$. Finding the shortest path from $u$ to $v$ consists in finding the path with fewer intermediate nodes, while finding the longest path, consists in finding the path with the highest number of intermediate nodes. The problems are not polynomially equivalent because the shortest path is in $P$ while longest path is in $NP$ (see here).
For item (c), the optimization problem for MAX CUT is NP-hard while for MIN CUT is polynomial. However, when you consider the version of these problems that allows both positive and negative weights they can be trivially converted to each other by flipping the sign in all weights.


Deterministic vs. Non-Deterministic PDA? The following is an example of language $a^nb^n$ where $n \geq 1$

From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, the definition was: "If a PDA has more than one paths going accept state then it is non-deterministic PDA" but what about epsilons?

So, Is this an example of Non-deterministic or Deterministic PDA? How to recognize NPDAs from DPDAs? Can I create both NPDA and DPDA for this language as above?

Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.

Your example is deterministic. Check:

From state $q_0$ with $Z_0$ on the stack, on reading $a$ there is one possibility. In the same case there is no alternative on input $\epsilon$
Similarly, from $q_0$ with stack $a$, only one option. No $\epsilon$ alternative
In $q_0$, with $a$ on the stack and inputs $a$ and $b$, again one move only. No $\epsilon$ alternative

You can complete the analysis for the other possible combinations of state, stack symbol, an possible input, making sure there is one option for a given input symbol, and if $\epsilon$ input is allowed, no "real" symbol alternative is available (e.g. in $q_1$ with $Z_0$ on the stack, only $\epsilon$ can be read).


Is there an algorithm for reducing CNFs further I have a boolean formula in conjunctive normal form (CNF):
$(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$
I know that this can be simplified to:
$(a\vee b)\wedge (x \vee y)$.
a) Is there an algorithm to decide if a CNF is already in the reduced form or not?
b) Is there an algorithm that can do this reduction in an manner more efficient than comparing each pair of clauses to see if any pairing can be reduced? I wish to automate this reducing for any CNF and am looking for any algorithms that I can borrow/implement.

CNF minimization is hard; see https://cstheory.stackexchange.com/q/9839/5038.  It is certainly NP-hard, and there is a sense in which it is "even harder".
One way to get some intuition why it is hard is that if the CNF is not satisfiable, then its reduced form is "False", whereas if it is satisfiable, its reduced form is something else.  So, if you had an efficient way to find a reduced form, that would immediately give you a way to tell whether the CNF is satisfiable -- a task that we know is NP-hard.
See https://cstheory.stackexchange.com/q/9839/5038 and https://en.wikipedia.org/wiki/Logic_optimization#Circuit_minimization_in_Boolean_algebra for some points into the literature on algorithms for this task.


Generating all strings that a regular expressions describe I'm having trouble generating the set of strings, which a regular expressions describe.
A typical regular expression can look like this:

[atom_0] atom_1 (atom_2 | atorm_3 | ... | atom_n-1) <var> [atom_n]

Or any other combination of the following:

[], means, that the atom inside of it can be omitted
(), one of the atoms (seperated by | (stands for OR)) inside the braces can be chosen
<>, variable.
atom, it can be thought as a constant, which is hard coded.

For example:

The [yellow] (dog | cat) named <animalName>

This expression describes the following set of strings:

The yellow dog named <animalName>;
The yellow cat named <animalName>;
The dog named <animalName>;
The cat named <animal Name>;

The strings can vary, depending on the variable <animalName>, but say, we have two names for <variableName> : Petsy and Rony, then w'll have:

The yellow dog named Petsy;
The yellow cat named Petsy;
The dog named Petsy;
The cat named Petsy;
The yellow dog named Rony;
The yellow cat named Rony;
The dog named Rony;
The cat named Rony;

Right now, I'm thinking that I could build a tree (or graph) from the expression and then a DFS or BFS can do the job.

Any comments or document/article references would be helpful to me.

There is a standard construction for converting regular expressions into finite automata (check here or any textbook on formal languages). Once you have such an automaton in hand (either NFA or DFA) you can enumerate all accepted strings with a breadth-first search from the initial state looking for finite states (ordered by length).

Be careful, though: in general, regular expressions specify infinite languages. You can easily specify a length limit, though.


Can someone explain this conclusion for Finite State Machines? PS It isn't a homework problem..
(But the results seems to be working for me when I checked manually a couple of values of m and n)

Let's say I have two FSM's(calling them A and B)

A is the the machine for checking divisibility by any +ve number (calling it m)
B is the the machine for checking divisibility by any +ve number (calling it n)
(m and n aren't equal)

Now we have a third machine (C) for which we need to find the number of states it will have if the goal of that machine is A machine(FSM) which will accept Divisibility of both $n$ and $m$)

So here are the claims for the count of states for $C$,

if $GCD (m,n)$ equivalent to $1$, then the number of states in C is $m*n$
if $GCD (m,n)$ isn't equivalent to $1$, then number of states in C is $LCM(m,n)$

(EDIT 1- Both are technically the  same thing, check the comments and the answer)

(Edit -2  I meant this, if we have strings given to us over {0,1}, and the machines will then calculate the divisibility by the given number and with result in either of the (let's say the number we are dividing with is n) n-1 states as we can have n-1 modulo values possible)

I have checked the results for few m and m manually and they seem to be correct for them..

But why it's so?(I know that A and B will have m and n as count of states respectively for minimal DFA)

In both cases, the number of states is the LCM. This is because a number is divisible by $m$ and $n$ if, and only if, it is divisible by $\mathrm{lcm}(m,n)$ and, for any positive integer $d$, you can check that the input length is divisible by $d$ by having states $\{0, \dots, d-1\}$ such that the automaton is in state $i$ when the number of characters read is congruent to $i$, modulo $d$.


CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm I'm trying to better understand Question 24.3-4 From CLRS below:

  Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm.
  The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$. Give an
  $O(V + E)$ algorithm to check the output of the professor’s program. It should
  determine whether the $d$ and $\pi$ attributes match those of some shortest-paths tree.
  You may assume that all edge weights are non-negative.

I have the answer from the Solutions manual, but simply do not understand how this answer actually works: (bottom of pg. 5/19, Exercise 24.3-4 didn't want to overload the question with a long solution):
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch24.pdf

Basically, the solution says we have to check every edge $(u, v)$ for all $v \neq s$. I understand that we only need to ensure that $s.d = 0$ and $s.\pi = NIL$ since the $\delta(s, s) = 0$ and $s$ should not have a predecessor, as it is the first vertex in the graph. The solution goes on to mention that:

  "Check that $v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$, and that $v.d = v.π.d + w(v.π, v)$. If this is ever false, return false"

So I understand that for any $v \neq s$ that $v.\pi.d < v.d$ by the fact that $v.d = v.\pi.d + w(v.pi, v)$ so the distance of any node's predecessor must always be less than that of the node by the simple property.

How do we manage to check though that: "$v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$?"

Since say we pick some random vertex in the graph that is a neighbor of $s$, call this node $v$. So $\delta(s, v)$ could potentially be calculated by traversing half of the graph then coming back to $v$ through some other node, $u$ if the $w(s, v)$ is extremely large. How does the algorithm verify cases like this? Does it ensure that it starts only at the neighbors of $s$ first, verify those distances, and essentially inductively proceed to verify the remaining predecessors and distances?

It seems that for $v \in V - {s}$ that if $v.\pi$ is correct, then all that remains is to verify $v.d$? I just don't really understand how the algorithm can correctly do this.. Is it traversing the graph, or iterating over the adjacency list/set of edges for each node, such that for a node, $v$ we check all edges $(u, v)$ somehow and then come up with an understanding of whether the node $v$ has the proper $v.\pi$?

Could someone please help/explain how this solution works? Have been struggling for a few hours now on this, and stepped through the algorithm with written examples but am not seeing the pattern here. Thank you.

Edit I've seen some answers mentioning creating a tree (since Dijkstra's algorithm is supposed to output a shorted path tree from the src node, $s$).

Regarding this: Would we create a shortest path tree using all of the $v.\pi$ values for each $v \in V - \{s\}$, since $s.\pi = NIL$? This takes time $O(V + E)$ to create an adjacency list we would need to traverse using BFS/DFS. Then, we begin a DFS on the tree created by the $v.\pi$ attributes and modify the DFS to check $v.d = v.\pi.d + w(v.\pi.d + v)$ or something along these lines?

So I'm going to go out on a limb with this one and attempt to answer my own question. It seems that when running the algorithm given in the solution, say that there are many vertices for which $v.\pi$ and $v.d$ is incorrect (call this set of vertices, $V_i$ and $V_i \subseteq V$).

When we run the algorithm, if there are at least some vertices for which $v.\pi$ and $v.d$ is correct (call this set of vertices $V_c$ and $V_c \subseteq V$), the algorithm is guaranteed to detect at some point that there is an incorrect vertex $u$, such that $u \in V_i$.

But, it may return a false positive for some vertex, $u$ (again such that $u \in V_i$) if all of the parents of $u$, WLOG say a parent($u$), is called $p$, so $p$ also has incorrect distance and predecessor values, thus $p.\pi$ and $p.d$ is incorrect for a parent, $p$ of $u$ therefore $p \in V_i$ but eventually we will come across some vertex $u \in V_i$ such that when we look at the incoming edges to $u$, we will find that $u.\pi$ is incorrect, since at least $1$ of the parents of $u$, call it $p' \in V_c$ has correct distance and predecessor values, and we would return false/something that indicates we have found the vertex $u$ such that $u.\pi$ and $u.d$ are incorrect.

In the case of all $v \in V$ outputted by the Professor's program are incorrect, we'd easily find a $v$ such that $s \xrightarrow{} v$ and see that $v.\pi$ or $v.d$ is incorrect.

I believe this explains how the algorithm works... Someone please correct me where/if I'm wrong. Thanks.


Undecidable problem intersection of two DCFL languages is DCFL? We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an intersection of the languages of A and B. This problem is known to be undecidable. But I can't find a proof for it.

Problem statement

We have two deterministic pushdown automatas (DPDA) $D_1$ and $D_2$. The problem is to decide whether there exists a DPDA $D$ such that $L(D) = L(D_1) \cap L(D_2)$.

Post correspondence problem

The proof is based on the fact that Post correspondence problem (PCP) is undecidable. Suppose we have a PCP problem with two input lists $\alpha = (\alpha_1, ..., \alpha_n)$ and $\beta = (\beta_1, ..., \beta_n)$

Define languages

Let $$L = \{i_1...i_k\#j_m...j_1\$\beta_{j_1}...\beta_{j_m}\$\alpha_{i_k}^R...\alpha_{i_1}^R | \;1 \leq i_l \leq n, 1 \leq j_l \leq n \}$$
One can constructively show that there exists a DPDA $D_1$ that accepts $L$.
From the other hand, the language with words $u\$u^R\#v\$v^R$ also has DPDA $D_2$. Let's call this language $L_{rev}$.

Let intersection language be $L_{\cap} = L \cap L_{rev} $

Emptiness of $L_{\cap}$ is equivalent to PCP decidability

Consider a word from $L_{\cap}$. It is like $i_1...i_k\#j_m...j_1\$\beta_{j_1}...\beta_{j_m}\$\alpha_{i_k}^R...\alpha_{i_1}^R$ and like $u\$u^R\#v\$v^R$. So $\alpha_{i_1} = \beta_{i_1},..., \alpha_{i_k} = \beta_{i_k}.$

Since then, if $L_{\cap} \neq \varnothing$ then there is a solution for PCP. Otherwise, there is no solution.

Emptiness of $L_{\cap}$ is equivalent to existing of $D$

Furthermore if $L_{\cap} = \varnothing$ then $L_{\cap}$ has DPDA because it is empty.
Using pumping lemma, one can show that if $L_{\cap}$ is not empty then this language is not context-free. Since languages of DPDAs are subset of context-free languages then $D$ does not exist.

Conclusion

Assume we can decide if $D$ exists. Let's take our PCP, construct our languages and answer if $D$ exists. If it does exist, then the intersection language is empty and the PCP doesn't have a solution. Otherwise, it has. This way, we decide whether a solution for PCP exists. But this problem is known to be undecidable. We have come to a contradiction. Consequently, the assumption is wrong and the problem of deciding whether $D$ exists is undecidable.


How good (or bad) is my makeshift PRNG? Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I pass it (or get a high score) I can write up a paper to announce a new state-of-the-art PRNG to the world. Yeah I know that's unlikely, but by saying this I mean I expect a really "strict" test.

I did some searching and Wikipedia points me to TestU01, which is said to be state-of-the-art, but its latest release is in 2009, or nearly ten years ago. I suppose a lot of things have happened since then.

There is no such test.  All automated tests for examining the randomness of a PRNG have limitations.  If you read some papers in the literature that propose PRNGs, you might notice that they do more than just run an automated test against their scheme.

Of course you can always write up anything at any time.  For the research community to find it interesting, or for practitioners to find it useful, it will probably take more than just passing an automated test.   Getting a paper to be accepted at a quality peer-reviewed conference will probably require the reviewers to find it novel and interesting.  For your PRNG to be adopted in practice, your PRNG will probably need to be better than existing ones in some relevant respect (perhaps it is faster and the quality of the pseudorandomness is "as good" in some sense as existing schemes; or better in some other way that implementors care about).


Is it possible to modify dijkstra algorithm in order to get the longest path? Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?.

  My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the same as finding the shortest path on a graph with negative weights. However, Dijkstra’s algorithm requires that the weights are positive, so it cannot be modified to calculate the longest path. A better algorithm to use could be: http://en.wikipedia.org/wiki/Longest_path_problem

Any idea of how to modify it?

Longest path is basically the Hamiltonian Cycle problem or the Traveling Salesman Problem, and it is NP-hard. So no, and if you find a way, then ${\rm \mathbf{P=NP}}$.

The existence or non-existence of an algorithm to find the largest path, in polynomial time, is essentially part of the largest open problem in all of CS (and probably in math).

Incidentally, the Bellman–Ford algorithm can handle negative weights, so long as they don't form a cycle; in which case, if it encounters one (ie. if the cycle is reachable from the source), it would run forever, running 'round and 'round the cycle, accumulating a "shorter" and "shorter" path. Of course, it can detect this, and terminate, and is thus useful for detecting such cycles.


Is it possible that low-resource Turing Machines can always "usually" agree with high-resource Turing Machines Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs.

It is known that there are problems in $TIME(n^{3})$ that are not in $TIME(n^2)$.  But is it possible that, for every language $L \in TIME(n^{3})$, there is a $.99$ approximation in $TIME(n^2)$?

I'm also curious about this question with respect to other computational resources: Nondeterminstic Time, Space, and Randomness (although I'm not even sure if there is a BPTIME hierarchy theorem, so it might be hard to answer for randomness).

Okay, I realized there's an uninteresting answer to this question via a "slow" diagonalization argument.  Let ${M_k}$ be an enumeration of the machines that run in $TIME(n^2)$.  Define $\bar{M}$ to be the machine that does the opposite of $M_k$ on all inputs of length $k$.  Then $\bar{M}$ is in $TIME(n^{2 + \epsilon})$, but there is no machine in $TIME(n^2)$ that is a $0.001$ approximation of $\bar{M}$, because there is some input length on which the two machines disagree everywhere.

I don't feel like this really captures the spirit of the question, though, and I'm going to try to think about how to re-formalize it.  Maybe I want to say something about circuits?  Like: is it possible that for all circuits on $n$ input wires, $SIZE(c)$ has a $.99$ approximation of $SIZE(c+1)$?


Do all algorithms aim to solve decision problems? An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more abstractly considered decision problems? Is the ultimate reason for a calculation, data processing or automated reasoning to solve a higher decision problem?

Thank you and forgive my ignorance.

There is a class of problems called decision problems that have an yes/no answer. These problems can be further be classified in decidable, where we have a way to solve them, or undecidable, for which there cannot be or has not been yet discovered a way to solve them.

However, there is another set of problems where we are not interested in a yes/no answer, but rather in a more specific solution. For example, there are optimisation problems, where we are searching for the best value according to some parameters, or counting problems, where we are interested in counting the number of instances where certain property occurs.

To sum it up, decision problems are a specific class of problems, a subset of which can be solved by algorithms. However, algorithms can be used to solve problems in other classes.

Now, given an algorithm for a specific problem, one can solve multiple problems equivalent to the original one (there are ways of "translating" a problem in the terms of another one, and having a solution to one problem means having a solution for all such problems).


unambiguous grammar but it's not LR(1) I have following grammar:

$$A \to a A a \mid \varepsilon$$

This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a shift-reduce conflict in LR(1) on this grammar.

Why does there exist an conflict even though it is not ambiguous grammar?

All $LR(1)$ grammars -- indeed, all $LR(k)$ grammars -- are unambiguous, by definition.  But the converse is not true: the fact that a grammar is unambiguous does not say anything about whether it can be parsed with an $LR(k)$ parser.

The grammar you present is not $LR(1)$, although the language itself is. (In fact, the language is regular: $(aa)^*$.) But that's not true for the language of even-length palindromes which has a rather similar unambiguous CFG:

$$\begin{align}
  S &\to \epsilon \\
  S &\to a S a \\
  S &\to b S b
\end{align}$$

Intuitively, the problem with parsing palindromes deterministically is that you have to start popping the stack at the middle of the sentence. But you can't tell where the middle of the sentence is until you reach the end, and since there is no limit on the length of a sentence, the end could be arbitrarily distant from the middle. So no finite lookahead is sufficient to make the decision.

A context-free language is $LR(k)$ precisely if it is deterministic. For the outline of a proof of the non-determinism of the language of even-length palindromes, see: prove no DPDA accepts language of even-lengthed palindromes


Does Bellman–Ford algorithm can handle zero-weight cycles? According to my understanding, the Bellman–Ford algorithm can handle cyclic graphs with negative weights. but it cannot have negative cycles. But can it handle zero weight cycles?

Yes.  Bellman-Ford can handle graphs with zero-weight cycles; they aren't a problem.

Intuitively, negative-weight cycles are problematic because they can make the notion of "shortest path" ill-defined: there is no shortest path.  For instance, suppose we have a cycle from A to A with weight -5, and an edge from A to B with weight 10.  Then there is no shortest path from A to B.  There's a path with length 10 (go straight there), a path with length 5 (traverse the cycle once, then go there), a path with length 0 (traverse the cycle twice, then go there), a path with length -5, a path with length -10, and so on.

Zero-weight cycles don't cause this problem.


Tools for practicing problem solving and expression of algorithms I'm involved in a university course which is a crash course in the basics of problem solving and common concepts in computer science. The course contains a number of practical assignments and ends with a group project (~30 hours) in which at least two students solve a problem given to them. Lately we have focused on assigning problems to be solved by use of some computer program and/or device. Examples include visualizing algorithms in a virtual world by use of Alice and Scratch, as well as programming pre constructed Lego Mindstorms robots to perform specific tasks. We think those kinds of environments are suitable because of the low pre-requisites needed and because of the quick feedback that the students are given. As a bonus, the presentations tend to not be boring.

We are currently searching for additional tools to use in the course, which is why I ask you users of Stack Exchange Computer Science this:

What kinds of tools have you come across that could be used to practice problem solving and expression of algorithms? Feedback does not have to be visual -- we are investigating sound/song generation as a possible assignment. What is important is that basically any pair of students should be able to solve our assignments (with guidance if needed) in ~30 hours. That is, the students should not need any pre existing knowledge other than possibly basic mathematics. Whatever tool is required must be available for free.

Problem solving is best done (in my opinion) on pencil and paper. However, some other useful tools for helping solving problems is Wolfram|Alpha. If you need to, Python is a fairly good scripting language for solving problems. Of course, this all depends on what kind of problem you are working on (for example, a geometry problem would be very difficult to solve using Python).


How does RAID-5 algorithm locate the right device? Please consider the following diagram of a RAID-5 array (Ignore the gray background):

Now, given a logical address, how can one return the device number (0-3)?

For example, DeviceByLogicalSector(50) = 0, DeviceByLogicalSector(31)=2.

I've need to implement DeviceByLogicalSector method. I can use space if that's required.

Now, I've noticed the following:
Let's observe only the first $4$ rows; If we have a sector which is above the $P$-diagonal then the formula is: $\frac{(\text{logical_addr} \mod 12)}{4}$. And if the sector is below the diagonal then we need to add $1$.

Thanks

Extracted from: HERE

// Assume all indexes are zero-based.
// Algorithm = Left-Asym

ChunkIndex = LogicalSector / SectorsPerChunk
StripeIndex = ChunkIndex / (DiskCount - 1)

ParityDisk = (DiskCount - 1) - ((StripeIndex / ParityDelay) % DiskCount)

DataDisk = (LogicalSector % (SectorsPerChunk * (DiskCount - 1))) / SectorsPerChunk
If ParityDisk <= DataDisk:
    DataDisk = DataDisk + 1

PhysicalSector = (LogicalSector / SectorsPerChunk) * (DiskCount - 1)
PhysicalSector = PhysicalSector * SectorsPerChunk
PhysicalSector = PhysicalSector + (LogicalSector % SectorsPerChunk)


Example of a non-regular language that is a subset of a regular language? How can this be? I don't think it is actually possible for a non-regular language to be a subset of a regular language. What examples are there where this is true?

Every language over an alphabet $\Sigma$ is, by definition, a subset of $\Sigma^*$, which is regular. If you want a less trivial example,

$$\{a^nb^n\mid n\geq 0\}\subseteq L(a^*b^*)\,.$$


prove that there is a complete language in $L \cup \{A_{TM}\}$ $A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$

$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space

Given the language $L \cup \{A_{TM}\}$,

we will say that $A$ is complete in $L \cup \{A_{TM}\}$ if:

$A \in L\cup\{A_{TM}\}$
For every $B\in L \cup \{A_{TM}\} \implies B\le_LA$

Is there a complete language in $L \cup \{A_{TM}\}$?

We will show that $A_{TM}$ is complete for your class.

In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$.

First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$.

Now, if $A\in L$, we need to work slightly harder. We need to show that $A\le_L A_{TM}$. In order to do that, we construct a reduction from $A$ to $A_{TM}$, as follows: let $M$ be a deterministic TM that decides $A$ in logspace (why does there exist such a machine?).

Now, the reduction works as follows: given input $x$, the reduction uses $M$ to check whether $x\in A$. If $x\in A$, the reduction outputs $\langle\epsilon, T_1\rangle$, where $T_1$ is a TM that accepts every input immediately. If $x\notin A$ the reduction outputs $\langle\epsilon, T_2\rangle$, where $T_2$ is a TM that rejects every input immediately. Note that $T_1,T_2$ are fixed, i.e. they are hard-coded in the reduction.

Try to prove that this reduction is correct, and that it is indeed in logspace.


Are dictionaries and associative arrays the same thing? With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?

As far as I can tell, associative array is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the dictionary but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation).

Citing from theory-leaning [1, p281] (bold emphasis mine):

  The dictionary, symbol table, or simply search problem is a fundamental one in computer science: a set of distinct keys is to be organized so that client queries whether or not a given key is in the set can be efficiently answered.
  More generally, with distinct keys, we can use binary search trees to implement an associative array, where we associate information with each key and can use the kry to store or retrieve such information.

CLRS [2, p229] make no mention of associative arrays but define dictionaries:

  We call a dynamic set that supports [insertion, deletion and membership test] a dictionary.

In the more practically inclined [3, p361 ff], the term symbol table is used as a synonym for dictionary but defined in a slightly different way:

  A symbol table is a data structure for key-value pairs that supports two operations: insert (put) a new pair into the table and search for (get) the value associated with a given key.

Later, they write:

  [The conventions "no duplicate keys" and "put on an existing key replaces the old value"] define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.

Summarising this small literature research (which is not without contradictions) and from a theoretical viewpoint, I'd state the following:

A dictionary is a data structure that implements a (dynamic) set with insertion, deletion and membership test.

Mathematically speaking, a dictionary over universe $X$ represents an element of the power set $2^X$ of $X$.
An associative array is a data structure that implements a (dynamic) mapping with insertion/update, deletion and retrieval.

Mathematically speaking, an associative array over key universe $X$ and value universe $Y$ represents an element of the set of functions $X \to Y$.

One can thus view a dictionary over universe $X$ as associative array over $(X,\{0,1\})$; this closely resembles the indicator function of sets.

I think this fits programmers' reality quite well, but terms may be used differently over there.

Important: The usage of the term "array" may suggest $O(1)$ accesses. This can, in general, not be expected to be true; at least not in the worst-case and without amortisation arguments. Implementations using hash tables come closest; see here for a discussion about what to expect w.r.t. performance.

An Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd ed, 2013)
Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (3rd ed, 2009)
Algorithms by R. Sedgewick and K. Wayne (4th ed, 2011)


Explanation of the Gelfond Lifschitz reduct Can someone explain with a hands on example how the Gelfond Lifschitz reduct works in order to check stable model semantics?

edit

a simple example here - at least as far as I understand the thing. So far grounding is clear to me - but the the application of the reduct is not. My goal in the end is to check stable model semantics of a program P and a supplied model M

Let i, j be constant symbols and X, Y be variables. Consider

d(X,Y,Z) :- a(X), b(Y), c(Z).
c(X) :- a(X), not b(X).
a(i).
b(j).

Decide using the Gelfond-Lifschitz reduct whether the interpretation I = {a(i), b(j), c(i), d(i, j, i)}
is a stable model of P.
Then the grounding looks like:

a(i).
b(j).
c(i):- a(i), not b(i).
c(j):- a(j), not b(j).
d(i,i,i) :- a(i), b(i), c(i).
d(i,i,j) :- a(i), b(i), c(j).
d(i,j,j) :- a(i), b(j), c(j).
d(j,j,j) :- a(j), b(j), c(j).
d(j,j,i) :- a(j), b(j), c(i).
d(j,i,i) :- a(j), b(i), c(i).
d(j,i,j) :- a(j), b(i), c(j).
d(i,j,i) :- a(i), b(j), c(i).

Now I start to apply the reduct. To me only the simple bits are clear:

P = {a(i), b(i), ... unclear part}

What is lacking & unclear to me:
- removal of default negations
- removal of not applicable formulas

Due to b(j)., c(j):- a(j), not b(j). is not applicable and needs to be removed.
As all negated literals are deleted, c(i):- a(i), not b(i). is converted to c(i):- a(i).
Therefore, as I = {a(i), b(j), c(i), d(i, j, i)} is minimal representation of the remaining P, it is also stable.


Time complexity of a problem in probabilistic inference on a Bayesian network Suppose we have a simple Bayesian network with two rows of nodes:  $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$.  Each node $x_k$ takes a state of either 0 or 1 with equal probability.  Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

We would like to find the probability of the joint event $E$ that both (i) all $y_k$ are 1 and (ii) the total assignment of states on the network has a probability above $\epsilon$.

Is exponential time required to compute the probability of $E$, and if so (or not), how do we prove this?

In case it is helpful, let me give a low-$n$ example:

Suppose $n = 3$.  If we just want to compute the probability of (i), then this is
$$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0}p_{2,0}p_{3,0} + p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,0} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,0}p_{3,1} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$
We can factor the right-hand side so that rather than a sum of $2^3$ terms we just have a product of $3$ factors:
$$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0} + p_{1,1})(p_{2,0} + p_{2,1})(p_{3,0} + p_{3,1}).$$
This reduces our computational time from $O(2^n)$ to $O(n)$ (as shown here for arbitrary $n$).

However, now consider the case that the terms $p_{1,0}p_{2,0}p_{3,0}$, $p_{1,0}p_{2,1}p_{3,0}$, and $p_{1,1}p_{2,0}p_{3,1}$ are quite small -- each less than $\epsilon$ -- and we would like our overall probability to 'ignore' such small terms.  Then we want to compute:
$$\Pr(E) = 2^{-3}(p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$

Of course, no generalizable factorization seems possible for the right-hand side.  This motivates the above question:  how can we prove (or disprove) that computing $\Pr(E)$ in the case of arbitrary $n$, $p_{k,0}$, $p_{k,1}$, and $\epsilon$ is indeed $\Omega(2^n)$?

Your problem is equivalent to:

Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$
Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $\sum_i a_i x_i \ge t$.

I think this problem is #P-complete, so you shouldn't expect any polynomial-time algorithm for computing it exactly.

Let me explain why.
Let $\ell(x,y)$ denote the likelihood of the states $x,y$, $\ell(x) = \ell(x,1^n)$, and $L(x) = \log \ell(x)$ its log-likelihood.  Then $L(x)$ has the form

$$L(x) = -n \log 2 + \sum_i \log p_{i,x_i}.$$

An assignment $x,1^n$ satisfies $E$ iff $L(x) \ge \log \epsilon$.  Note that

$$\log p_{i,x_i} = \log p_{i,0} + x_i (\log p_{i,1} - \log p_{i,0}).$$

Letting $a_i = \log p_{i,1} - \log p_{i,0}$, we have

$$\sum_i \log p_{i,x_i} = \sum_i \log p_{i,0} + \sum_i a_i x_i.$$

If we now let $t = \log \epsilon + n \log 2 - \sum_i \log p_{i,0}$, we find that $x$ satisfies $E$ iff $\sum_i a_i x_i \ge t$.  So, given $t$, we want to compute the probability that a random chosen $x$ satisfies $\sum_i a_i x_i \ge t$.  This is equivalent to counting the number of $x$'s that satisfy $\sum_i a_i x_i \ge t$.

According to https://cstheory.stackexchange.com/q/19758/5038, this problem is #P-complete, so you shouldn't expect to find any polynomial time algorithm to compute the answer exactly.

However, there are techniques for approximating it: for instance, you could use algorithms for estimating the number of lattice points in a convex polytope (see, e.g., https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf) or computing them exactly in super-polynomial time (https://cstheory.stackexchange.com/q/22280/5038, https://cstheory.stackexchange.com/a/6464/5038).