Is busy beaver the fastest growing function known to man? I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver?

We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.

Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.

At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)

The busy beaver function grows faster than any computable function. However, it can be computed by a Turing machine which has been given access to an oracle for solving the halting problem. You can then define a "second order" busy beaver function, that grows faster than any function that can be computed even by any Turing machine with an oracle for the halting problem. You can keep doing this forever, building up a hierarchy of ever faster growing busy beaver functions.

See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.


Solving the min edge cover using the maximum matching algorithm To solve an instance of an edge cover, we can use the maximum matching algorithm.
Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set [from Wikipedia].
Maximum matching: a matching or independent edge set in a graph is a set of edges without common vertices [from Wikipedia].
For example to find the min edge cover of the example below, we can:
1- Find a maximum matching.
2- Extending it greedily so that all vertices are covered.
The image below present this solution:

My question is why this reduction works, is there a proof for that result? or at least an intuition to help me undestand!
How can be sure that the final solution is the min edge cover of the graph and there is no other edge cover with size less than the founded solution.

Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a minimum edge cover. Before we do that, it can be benifical to make some simple observations. First, both edge cover and matching are set of edges, and the subset of an edge cover can be a matching. Given a minimal edge cover $C$(not necessarily the minimum), we denote by $M_C \subseteq C$ the maximum matching containing in $C$ . Note that $M_C$ is the matching of maximum size whose edges are all in $C$. We call any edge in $M_C$ the matched edge. We use $V(M_C)$ to denote the vertices of edges in $M_C$
Observation 1 Every vertex in $V\setminus V(M_C)$ must be covered by an edge which is incident to an edge in $M_{C}$. Otherwise we could find a larger matching in $C$.
Observation 2 Every edge in $C$ covers 1 or 2 vertices. Specifically, an edge in $M_C$ covers two vertices, an edge in $C\setminus M_C$ covers 1 vertex.
Theorem 1 $|V|=|C|+|M_C|$
Proof $\;$  By observation 2 and the definition of edge cover, we have $2|M_C|+|C-M_C|=|V|$.
By observation 1 we have that algorithm $\mathcal{A}$ outputs a minimal edge cover. Then he correctness of algorithm $\mathcal{A}$ is obvious from theorem 1:  when $|M_C|$ is maximized, $|C|$ is minimized since they sum to a fixed number $|V|$. In such situation, theorem 1 is called Gallai’s theorem


Red-black tree. Adding a red child to a red node with a black sibling According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black trees with different values to try to get to this situation, but I never seem to get to the situation where I have a red node with a black sibling, and where the value to be inserted will be inserted below the red node. I'm starting to ask myself if this situation could ever happen in a red-black tree?

Assume we have a black node $N$ with black child $L$ and red child $R$. Thus we have a red and black sibling. Recall that in a red-black tree all paths from root to leaf must have the same number of black nodes. The path $N-L$ contains two black nodes, the path $N-R$ just one. That means that both children of $R$ must be present, and must be black. So indeed, we can not add a new red child to $R$ because it already has black children. However, what can happen is that one of these black children turns red as consequence of a flag-flip. We then are in the situation you describe.


Why are Python 2 and 3 so incompatible with each other? Every software should have backward compatibility (at least some sense of it), this ensures old codes can run in the future updated systems without any problems in most situations. But why did the Python team decide to make the v3 a new language? The community has to split up into two and every computer has to install both v2 and v3 in order to run every python code. This is a huge mess. Is there a computer science reason behind this decision?

The saying goes, "In C++11, 11 is the number of legs the stapled onto the dog to make a better octopus".

As with basically everything in Computer Science, this is all about tradeoffs.

If you focus on backwards compatibility, you have potentially conflicting features interacting with each other. You're stuck with the design choices that were initially made, when you didn't have the knowledge and data that years of production use provide.

Breaking changes, conversely, have the disadvantage of breaking old code, though with Python 2, usually files could be converted mechanically.

Now, there are also questions of "what makes a language?"

From a semantics point of view, every time you add a new feature to a language, you have effectively defined a new language with different semantics. There are nice formalisms for dealing with this: for example, some extensions to languages are conservative, meaning you're only expressing features that the start language could express.

Python 2 to 3 was not an extension, let alone a conservative one. So from a theory point of view, they're different languages, that happen to share a name, most syntax, and a real-life community.

Java broke backwards compatability when they decided to be a different language from C++ or SmallTalk or Eiffel. At the end of the day, the lines between languages and dialects and versions can be blurry, and the decision will come down to what is viewed as the most pragmatic for developers.


Calculating the Time complexity using Radix sort Im trying to determine what is the time complexity of sorting numbers with a specific range and base.
I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n.
I have tried to calculate it using log equations but im getting to a linear result, I dont know wether im right or wrong.
Thank you very much.

You are correct.  We have $(n/\log n)^{20} \le n^{10}$ for all $n\ge 1$, so each number can be expressed using at most $d=20$ "digits".  The running time of radix sort is $O(dn)$, and $O(20n)$ is $O(n)$, so the running time is linear in $n$.


Prof Knuth's MIX computer - Card Reader and illegal characters I'm reading through Knuth's "The Art of Computer Programming" volume 1 (3rd edition), with the goal of understanding the complete workings of his hypothetical MIX computer in order to implement MIX in software.  Needless to say this is a long term project!  (I'm not in college or anything, just an amateur CS enthusiast doing this for fun, I have no Professors to ask!)

In Section 1.3.1 (onwards) of "The Art of Computer Programming" Prof Knuth describes in detail his MIX computer and its IO devices such as Tape, Drum and Card Readers.  The main Text does not describe the "bootstrapping" process for this machine, but Exercice 26 does.

There is one particularly onerous limitation of the Card Reader described in Exercise 26 -- that is certain characters are not allowed to be written to or read from Cards.

To me this is an important point because if this "illegal characters" limitation does apply to the MIX proper, then I cannot see any easy way to write a MIX program by hand without constantly stumbling over illegal characters.  The CMPx operators are explicitly forbidden by Ex 26 for instance.

If I was to attempt to implement MIX myself in software I would find it very convenient to ignore this "illegal characters" limit and just indiscriminately accept all characters without error.  Although in my mind this gives me some doubt as to whether my implementation would be "compliant" with Prof Knuth's MIX spec.  Accepting "illegal" characters would also make creating a MIXAL assembler a lot easier.

Questions:

Am I to understand that concepts discussed in the Exercises are not formally part of the MIX specification?
It seems arbitrary to add such a tricky obstacle, is this rather severe limitation only supposed to be true within the scope of Exercise 26 or should it be understood that it applies to the formal specification of the MIX computer throughout the entire TAOCP book set?

I imagine the concepts developed in the Exercises are meant to be formally part of the MIX specification, but there will also be some degree of arbitrariness.

For example, the MIX character set of $56$ characters supports only upper case text, but also includes three Greek characters ($\Delta$, $\Sigma$, $\Pi$) and an arbitrary selection of punctuation characters (no '%', '?', '!' or '^'; '/' but no '\').

Similarly, the restriction on allowed characters in the card reader is probably just to make the point that not all input devices will support the full character set. Knuth may have regarded the typewriter terminal (which presumably does support the full character set) as the main input for program instructions, and may have seen the card reader as primarily for data input.

I think you can make your MIX implementation a completely faithful implementation or a looser interpretation of the original specification - it is your choice.


Protocols for "almost equality" with one-sided error In the well-known communication task EQUALITY, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is a probabilistic protocol which uses 2 bits, is always correct when $x = y$, and is correct with constant probability when $x \neq y$ (in fact, with probability 1/2).

The following generalization came up in a recent question. In the task $k$-HAMMING (where $k$ is a constant parameter), Alice and Bob hold strings $x,y$ of length $n$ bits, and their task is to determine whether the Hamming distance between $x$ and $y$ is at most $k$. EQUALITY is the case $k=0$.

When $k = 1$, we have the following nice protocol, which uses 5 bits, is always correct in the Yes case, and is wrong in the No case with probability at most 5/8. Alice and Bob agree on two random strings $z,w \in GF(3)^n$. Alice and Bob each compute the inner product of $z,w$ with their input, and compare the values. If both are equal or both are different, they output Yes, and otherwise they output No.

If the Hamming distance between $x$ and $y$ is $d$ then the probability $p_d$ that $\langle z,x-y \rangle = 0$ is $1/3 + (2/3)(-1/2)^d$. We have $p_0 = 1$, $p_1 = 0$, and $1/4 \leq p_d \leq 1/2$ for $d \geq 2$. This shows that the error probability when $d \geq 2$ is at most $p_d^2 + (1-p_d)^2 \leq (1/4)^2 + (3/4)^2 = 5/8$.

When $k > 1$, a similar protocol works since using enough samples we can estimate $p_d$ to any required accuracy. However, the resulting protocol no longer has one-sided error. One-sidedness can be recovered in many ways at the cost of using $O(\log n)$ bits of communication.

  Is there a one-sided error protocol for $k$-HAMMING for $k \geq 2$ using $O(1)$ communication?

Here are two solutions. In both cases, the inputs are $x,y \in \{0,1\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not.

Solution 1 (D.W.):

The two parties decide on a random string $z \in \mathbb{Z}_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if $\alpha - \beta \notin \{k+1,k+2\}$.

If the Hamming distance between $x$ and $y$ is $d$, then $\alpha - \beta$ is distributed as the sum of $d$ many $\pm 1$ random values. When $d \leq k$, clearly $\alpha - \beta \notin \{k+1,k+2\}$. Conversely, when $d > k$, the probability that $\alpha - \beta \in \{k+1,k+2\}$ is $\Omega(2^{-k})$.

Solution 2 (Sa'ar Zehavi):

The two parties decide on a random partition of $\{1,\ldots,n\}$ into $k+1$ parts, and run the one-bit equality protocol on each of them. They accept if the equality protocol succeeds (declares "equal") on at least one of them.

If the Hamming distance between $x$ and $y$ is at most $k$, then clearly the parties always accept. Otherwise, with probability $\Omega(e^{-k})$ all the $k+1$ parts will be different, and so the equality protocol will fail on all of them with probability $\Omega(2^{-k})$.


Turing machine with an oracle for a proper subset of a known undecidable language Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $L$. Is it possible to define such an $L$ so that $T$ does not decide $E_{TM}$ (the language of descriptions of Turing machines whose languages are empty)?

Intuitively, it seems the problem is that when the oracle answers "No", $T$ is unable to distinguish whether the string it fed to the oracle to receive this response belongs to $A_{TM} - L$ or $\overline{A_{TM}}$. But this doesn't really prove that $T$ can't decide $E_{TM}$.

It seems you're working towards the notion of Turing reducibility. For example, adding a nontriviality assumption you're roughly asking here:

  Is there a set which is not computable but also does not compute the halting problem?

This is an excellent question, and the answer is far from obvious - but ultimately yes in a very strong sense (although a subsequent follow-up question is still open and generally believed to have a negative answer). These were some of the first serious results in computability theory:

Kleene and Post in $1945$ showed that the answer to your question is yes in a strong way: there is in fact some $A$ which is strictly intermediate between the computable sets and the halting problem with respect to Turing reducibility. Their argument also showed that we can find an $A$ which is incomparable with the halting problem with respect to Turing reducibility, so we get a strong affirmative answer.
This wasn't the end of the story, though. One year earlier, Post had posed a separate question: is there a computably enumerable set which is noncomputable but does not compute the halting problem? (Such a set would necessarily be strictly weaker than the halting problem as opposed to incomparable.) This was answered affirmatively about ten years later by Friedberg and by Muchnik independently; this required a new idea, the priority argument (although later priority-free proofs were discovered). The priority argument subsequently became one of the most, if not the most, important technique in computability theory, and was rapidly advanced far beyond the point of the Friedberg/Muchnik argument (some relevant results here include Sacks' density theorem and Lachlan's monster theorem).
However, the Kleene/Post and Friedberg/Muchnik degrees were all fairly artificial. Their arguments showed that the interval between the computable sets and the halting problem is extremely rich, and subsequent results would point towards them being "maximally" rich in some senses, but did not construct examples of such sets which are interesting on their own. Indeed, it is still the case that every natural Turing degree is basically just an iterate of the Turing jump (basically, something of the same "flavor" as the halting problem itself). The question of whether there is a natural intermediate Turing degree is still wildly open; there are some not-too-implausible candidates, but also results pointing towards a negative answer (and I think almost everybody believes that the answer is negative). Certainly the discover of any natural degree which isn't an iterate of the Turing jump would be one of the most important results in computability theory.


Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd prefer the one with the minimum element count.

Examples:

1)

Given values: [500, 1000, 2000, 5000]

Target: 7000

Result: [2000,5000]

2)

Given values: [500, 1000, 2000, 5000]

Target: 7990

Result: [500, 2000, 5000]

3)

Given values: [222,333]

Target: 444

Result: [222,222]

4)

Given values: [222,333]

Target: 777

Result: [222,222,333]

Later on I would like to implement this algorithm in JavaScript, and make it run in a browser. I have tried:

-Knapsack algorithm

-Generating all combination of the numbers and find one with the minimum difference

but both are very slow when implemented, and used with big numbers.

This problem is NP-hard by a reduction from partition.
Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the instance is trivial).
Assume that each $x_i$ is positive and let $\ell = \lceil \log 2M \rceil$.

I will now construct some values based on $X$. I will denote a generic value by a tuple $v$ of $n+2$ entries $(v^{*}, v^{(0)}, v^{(1)}, \dots, v^{(n)})$, where all entries $v^{(i)}$, $i=0,\dots,n$ are between $0$ and $2^\ell - 1$.
The tuple $v$ will actually correspond to integer whose binary representation is obtained by encoding $v^{*}$ in binary (using a variable number of bits), each of $v^{(0)}, \dots, v^{(n)}$ using $\ell$-bits, and finally concatenating the resulting bitstrings, in order.
An example of the tuple $v=(5, 2, 7, 9)$ with $\ell = 4$ is as follows:
$$
(\underbrace{101}_{v^*}
\underbrace{0010}_{v^{(0)}}
\underbrace{0111}_{v^{(1)}}
\underbrace{1001}_{v^{(2)}})_2 = (21113)_{10}
$$

Notice that the value obtained in this way has an encoding of polynomial length w.r.t. the length of the encoding of the original partition instance, as long as $v^{(*)}$ is small enough (as will be the case). The sum of two tuples is the tuple whose integer value equals the sum of the integer values of the summands.

Let then $y_i = (1, x_i, 0, \dots, 0, 1, 0, \dots, 0)$, where the second entry set to $1$ is $y_i^{(i)}$.
Similarly, let $z_i = (1, 0, 0, \dots, 0,1,0, \dots, 0)$, where $z_i^{(i)} = 1$.

The instance of the problem in the question consists of the set of numbers $S = \{y_i  : x_i \in X\} \cup \{z_i  :  x_i \in X\}$ and of the target value $T=(n,M,1, \dots, 1)$.

Given a solution $X' \subseteq X$ to the partition problem, it is easy to construct a solution $S' \subseteq S$ for our problem such that $\sum_{x \in S'} x = T$. Simply select $S' = \{ y_i : x_i \in X'\} \cup \{ z_i : x_i \in X \setminus X' \}$ (notice that it suffices for $S'$ to be a set rather than a multi-set).

I will now argue that if a (multi-)set $S' \subseteq S$ such that $\sum_{x \in S'} x = T$ exists, then the partition instance $X$ has answer "yes".
From now on let $S'$ be such a set and notice that, by our choice of $T$, the overall multiplicity of all the elements of $S'$ cannot be larger than $n$ (as otherwise $T^{(*)}$ would be exceeded).

Claim: Let $m(x)$ be multiplicity in $S'$ of $x \in S$.
$\forall i=1,\dots,n$ we have $m(y_i) + m(z_i) = 1$.

Proof:
If $m(y_i) + m(z_i) = 0$ then, since $T^{(i)}=1$, $S'$ must contain at least $2^\ell \ge 2M > n$ elements $y_j$ or $z_j$ such that $j > i$, contradicting $\sum_{x \in S'} m(x) \le n$.

Assume then that $m(y_i) + m(z_i) > 1$, and consider the tuple $h$ corresponding to the sum of exactly 2 copies of $y_i$ and/or $z_i$ in $S'$.
We have $h^{(i)}=2$ and, since $T^{(i)}=1$, we conclude that there must be at least $2^\ell - 2$ other copies of some $y_j$ or $z_j$ for $j \ge i$ in $S'$.
The total multiplicity of the elements in $S'$ is therefore at least $2 + 2^\ell - 2 > n$, a contradiction. $\;\; \square$

Let $X' = \{x_i : y_i \in S' \}$ and call $h = \sum_{x \in S'} x$. Since there can be at most one copy of each $z_i$ in $S'$ (see the above Claim), the only way to affect $h^{(0)}$ is through the values $y_i \in S'$. Since there can be at most one copy of each $y_i$ in $S'$ (see the above Claim), we must have $\sum_{x_i \in X'} x_i = \sum_{y_i \in S'} y_i^{(0)} = h^{(0)} = T^{(0)} = M$.


Efficient search for solving a Jigsaw Puzzle? I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice.

Let's assume the puzzle pieces are encoded as 4-vectors of integers representing the four sides. A negative integer indicates an indentation that must be matched with corresponding positive integer representing an extrusion. Zero represents a smooth edge (i.e., a border piece.) Rotations then correspond to cyclic shift (assuming the indentations/extrusions are rotationally symmetric.)

My heuristic for an efficient solution is to try to tile the puzzle in an inward spiral starting from the borders. What is the best strategy for building a chain of fitting pieces that avoids exhaustively trying all combinations/rotations?

I found some related SE questions that are relevant:

https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
https://stackoverflow.com/questions/15121903/algorithm-for-solving-tiling-jigsaw-puzzle
Partially filled jigsaw puzzle with six types of tiles

Seems like your heuristic needs to incorporate the distribution of the edge types to be optimal. Here's an idea:

Form a matrix the size of the puzzle's dimensions. Each cell indicates the proportion of remaining pieces that can be fit there on the next iteration without conflicting. At the beginning, the corners of the matrix will be $4$ (only four corner pieces), edges $2(w+h-4)$, and interior $wh-2(w+h-4)$. You can indicate filled cells with a large value, like infinity. Select the set of cells with minimum values as candidates for the next piece. Of these cells, select the piece that decreases the adjacent, unassigned cells by the most amount (use "min" of adjacent cells for the score).

This will ensure you explore the paths that have highest probability of conflicting first. If the first piece you place is incorrect, you want to find if it is incorrect as soon as possible. Likewise, you want to select the first piece to be the one with the least number of choices.

When the min value of the matrix is zero, you know there was an incorrect piece lain somewhere. In that case backtrack, decrease the proportion for the backtracked cell (since now we have eliminated one choice), and begin the iteration again. The backtracked cell will have the minimum value still, of course; so you will simply go on to trying the next piece in the candidate list.

Tentatively, I'd say on average the algorithm would propagate out from the four corners in a spiraling fashion, until two of the corner blocks connect. Then I suspect it would favor building off the connecting block. It will factor in the candidate probabilities, so for specific puzzles the paths it takes will vary.

(You'll need a specialized data structure to store the best candidates list. Could experiment with a blacklist instead. Or could try simply keeping a counter for how many conflicting pieces you tried for a cell, and then recreate the sorted list each time you need to backtrack)


Recovering a point embedding from a graph with edges weighted by point distance Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.
Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.
In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.
On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.
Which raises the questions:

How expensive is it to find a solution?
How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
What sorts of conditions make the problem trivial?
If I don't promise the edge weights actually correspond to point distances in 3d, how expensive is it to determine if an embedding is possible at all?

One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape.

Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, but this costs energy).  We now want to solve for a set of positions that minimize the total energy.  Suppose each vertex $v$ is placed at point $x_v \in \mathbb{R}^3$.  Then the total energy of this arrangement will be

$$E(x) = \sum_{(v,w) \in E} (\text{distance}(x_v,x_w) - d_{v,w})^2.$$

Here the $d_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x_v$'s (they are the coordinates of the points).

We can solve for an arrangement $x$ that minimizes this total energy.  This arrangement then provides a reasonable candidate for the positions of the points.  This is an optimization problem, and there are standard techniques for solving this kind of optimization problem.  See, e.g., the article Network Solutions by Erica Klarreich.

I don't think there any guarantee this will provide the correct desired solution.  It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for.  However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.

Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances.  Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.

Finally, there's a lot of work on embedding graphs into $\ell_2$ space, while minimizing the distortion of the embedding.  That's very related; you are basically asking for a zero-distortion embedding into $\ell_2$.  Thus, the techniques developed in that context might be useful for your problem, too.  Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem.  However, it's possible that their techniques might be effective in your situation as well.  It's worth a try.


Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time Ok, so I got this for homework and been struggling for a while now.
The full assignment requires this:

While N = number of elements in given array and n = number of different elements,

init(S,A[1...N]) - accept an array A as input and initialize S data structure in O(Nlogn) time

insert(S,x) - insert the key x to S in $O(\log n)$ time

freq(S,x) - return the number of appearances of x in S, in O(logn) time

mostFreq(S) - return the most frequent element in S, in O(1) time

I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.

So it's clear I'm pretty lost :) any suggestions?

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

That's exactly the solution I would go for.

Store a mapping of $\langle x, freq_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes

if x is in BST then
    replace <x, freq> with <x, freq+1> in bst
    if freq+1 > max_freq then
        max_freq := freq+1
        max_x := x
    endif
else
    insert <x, 1> into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif

You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.


How many possible policies in a Markov Decision Process? If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \{Hot, Mild, Cold\}$,  $A = \{East, West\}$, has 8 possible policies? Isn't it 6 if there are 2 possible action for every state?

Looks like you are a bit confused by the notion of MDP policy. There's a detailed discussion with lots of examples in this question.

A policy is any possible strategy in a given environment. Example: "go $East$ in any state" is a valid strategy in your MDP (though maybe not optimal), as well as "go $West$ in any state".

So there are 3 states and 2 possible actions per each, hence $2^3=8$ possible strategies: $EEE$, $EEW$, ..., $WWW$.


Loop invariance insertion sort algorithm I have the following pseudo code for a insertion sort algorithm
INSERTION-SORT

1 for j = 2 to A.length
2    key = A[j]
3    // Insert A[j] into the sorted sequence A[1..j-1]
4    i = j -1
5    while i > 0 and A[i] > key
6        A[i+1] = A[i]
7         i = i -1
8    A[i+1] = key

I am trying to convert it into executable code written in Python
def main():
    A = [5,2,4,6,1,3]
    for j in range(1,len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
        print A[0:j+1]
    return A

main()

is this a correct translation? I'm not sure if I messed something up with the indexes because it seems as though I'm not getting the end index with range. Furthermore I'm going to be testing correctness with initialization, maintenance and termination.
I added the line print A[0:j] to show initialization and maintenance but I'm not sure if it should be print A[0:j-1].
Any help is greatly appreciated!

Python arrays have 0-based indexing, like in C, and unlike Fortran, which uses 1-based indexing. You can check Wikipedia for information about other languages.
A python array $A$ of length $n$ consists of the elements $A[0],\ldots,A[n-1]$. The python function range(n) goes over the indices $0,\ldots,n-1$, and your range(1,n) goes over the indices $1,\ldots,n-1$.
In insertion sort, we go over all prefixes of the array inductively, and make sure that they are sorted. If $A[0],\ldots,A[j-1]$ is already sorted, in order to make $A[0],\ldots,A[j]$ sorted, we just need to more the current $A[j]$ into its proper location. Since $A[0]$ is automatically sorted, we only need to go over $j=1,j=2,\ldots,j=n-1$, at which point the entire array $A[0],\ldots,A[n-1]$ is sorted. This is why the loop goes over range(1,n).
Is your implementation correct? Practically speaking, the best way to find out is to test it on many inputs. While such a test cannot verify that the algorithm is correct, and could miss some corner cases, it is also likely to catch off-by-one errors, especially in a language like python with bounds checking. Since insertion sort is such a simple algorithm, you are likely to catch any implementation errors by sorting small random arrays.


Equivalence of minimum cost circulation problem and minimum cost max flow problem In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow:

  ...

  The second part of the proof is showing that min-cost circulation
  reduces to min-cost max-flow.

  Consider a network G for which we want to find a min-cost circulation.
  Add a source s and a sink t to the network, without any edges to
  the rest of the network. The maximum flow in this network is 0,
  therefore the min-cost max-flow is actually a min-cost circulation.

In theory, I don't understand how this works. If we add disconnected source and sink nodes, the maximum flow is trivially 0 as claimed. Does that mean the minimum circulation problem has zero flow on every edge of the original network? This seems to violate the lower bound requirement on the edges of min-cost circulation networks.

In practice, I don't know how to implement a min-cost circulation solver using a min-cost max-flow solver such as the one in Boost Graph Library (BGL) here :

#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>

#include "../test/min_cost_max_flow_utils.hpp"

int main() {
    boost::SampleGraph::vertex_descriptor s,t;
    boost::SampleGraph::Graph g;
    boost::SampleGraph::getSampleGraph(g, s, t);

    boost::edmonds_karp_max_flow(g, s, t);
    boost::cycle_canceling(g);

    int cost = boost::find_flow_cost(g);
    assert(cost == 29);
    return 0;
}

The above BGL example solves a small min-cost max-flow problem. I can't figure out how to change the network to include lower bounds of edges as required in the min-circulation problem. Simply adding additional, disconnected dummy source and sink node gives zero flows on all edges (as expected) and solves nothing.

My questions are:

Am I missing something in the above proof?

How should I adapt the BGL min-cost max-flow solver above to solve min-circulation problems?

I'd really appreciate a concrete example with cycle canceling (or another algorithm) in BGL to verify and illustrate the reduction.

Does that mean the minimum circulation problem has zero flow on every edge of the original network?

No, it does not means that, unless the lower bound capacity of every edge is equal to zero.

You need to remove the lower bound capacity. You can use the transformation done in Ahuja, page 39.


Does a time quantum affect priority non preemptive scheduling? I am given a list of processes with their arrival time, CPU, time and Priority. The time quantum is given as 2 seconds. A lower priority number translates to a higher priority.

(process #, arrival time, CPU time, Priority)

-P0: 0, 8, 5

-P1: 2, 2, 4

-P2: 4, 1, 6

-P3: 6, 3, 3

So the priority ranks P3,P1,P0, P4.

would my scheduling look like this using the priority non preemptive scheduling algorithm:

P0 P0 P0 P0 P0 P0 P0 P0 P3 P3 P3 P1 P1 P2

I wasn't able to figure this question out on my homework and I wasn't given the solution either. I wasn't sure if the time quantum would affect my scheduling or if I even am understanding the priority non-preemptive scheduling algorithm either.

In non-preemptive scheduling the time quantum is not important for determining scheduling. The time quantum is only important when processes can preempt the CPU and 'cut' the line, such as in Round Robin scheduling. If you were given a time quantum for this problem I have a feeling it was stuck there to try to trip you up.

Your answer is correct though and it sounds like you understand the concept. Priority non-preemtptive scheduling can be visualized as a priority queue. If the queue is empty you can have the CPU, if not you get into line based on your priority and wait until whomever has the CPU releases it (on their own).


If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts? The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the things running them are Turing-complete.

Since all computers have a finite amount of memory and are therefor not Turing-complete, does that mean that the halting problem does not apply to a program run on a machine with finite memory?

You can take a look at:
https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls

One can realize that a program is not halting by seing that it's repeating its behavior.
"A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state"

It also says that even computers are finite state machine, it's more useful to model them as infinite state machines, just because the number of states it's huge.
"Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least $2^{1,000,000}$ possible states"


What were the shortcomings of Robinson's resolution procedure? Paulson et alii. From LCF to Isabelle/HOL say:

Resolution for first-order logic, complete in principle but frequently disappointing in practice.

I think complete means they can proof any true formula in first-order logic correct. In the Handbook of Automated Reasoning I find:

Resolution is a refutationally complete theorem proving method: a contradiction (i.e., the empty clause) can be deduced from any unsatisfiable set of clauses.

From Wikipedia:

Attempting to prove a satisfiable first-order formula as unsatisfiable may result in a nonterminating computation

Why is that disappointing?

While "disappointing in practice" is certainly not definable formally, unlike "complete" (which does indeed mean "can eventually prove every true formula"), it's pretty easy to find examples where naive resolution is not even remotely adequate, i.e. examples which should be easy to prove but which resolution is extremely slow on.
A famous example is an encoding of the pigeon hole principle for $n$ holes in propositional logic (which is the statement "$n+1$ pigeons cannot fit in $n$ holes without duplicates). There is no proof of this statement using only resolution in time sub-exponential in $n$.
Things are even worse in predicate logic, where it is very easy to find statements without any fast resolution proofs.
Note that any implementation of resolution must implement a strategy for picking the resolvents, which is already a very difficult problem, and an active area of research, since most practical algorithms for theorem proving are enhancements of naive resolution, e.g. hyper-resolution.


Advantages of amortized analysis I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?

What I understood:

Let say we have 3 three operations a,b,c used 1,2 and 3 times to achieve d. Based on aggregate analysis a,b and c are used 2 times each. Is this correct?

I am trying to understand the advantages of this in CLRS but I am completely lost. For example in dynamic programming we save the answers to sub problems in tables which helps us reduce the running time(lets say from exponential to polynomial). But I am unable to get a complete picture of amortized analysis.

Amortised analysis is a tool to get more useful results than "naive" worst-case analysis. Especially in the realm of advanced data structures, operations can be cheap most of the time but expensive in rare cases; worst-cases analysis yields only the latter case as characteristic of the data structure. Dynamic arrays, splay trees and some flavors of hash tables are among the more popular examples.

For many purposes, that is too pessimistic. We don't actually need that every operation is fast¹; we execute lots and lots of operations (e.g. during an algorithm) and we want the total runtime to be small. That is what amortised analysis looks at.

Be careful not to confuse amortised analysis with average-case analysis. The former is still considering the worst case; it only sums over time and spreads the cost evenly; you get for one operation its share of the worst-case total cost. On the other hand, average-case assumes a probability distribution over inputs and/or the sequence of operations, and yields the expected time per operation, which is (by definition) its share of the expected total cost.

Real-time applications are a notable exception.


Finding a minimum weight path with certain restrictions I have a directed weighted multigraph whose vertices are sets of URLs.

We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are vertices of the graph.

Now having a set of source vertices and destination vertices, I need to find the minimum weight path (or several paths, if there are several such paths of the same weight) from a source to a destination of nonzero length and having at least one edge not of the form $i\to j$ where $i\subset j$.

Also it is desirable that the paths do not have adjanced edges of the form $i\to j$ where $i\subset j$.

I am currently working with Python and NetworkX.

I think (but not sure), that we can assume that the set of source vertices is disjoint with the set of destination vertices.

You can solve this in $O(|E| \log |V|)$ time, if all weights are non-negative.  Basically, you'll build a larger graph, of twice the size, then do a shortest-paths query in this graph.

I will call the edges of the original multigraph regular and added edges of the form $i\to j$ for $i\subset j$ as irregular.

For each set $i$, you have two vertices $i^-,i^+$ in the new graph, where $i^-$ represents a step along the path that visits set $i$ before visiting any regular edge; and $i^+$ represents a step along the path after visiting a regular edge. It is easy to work out the edges in this graph (if you have an irregular edge $i \to j$ in the original graph, you have $i^- \to j^-$ and $i^+ \to j^+$; if $i \to j$ is a regular in the original graph, you have $i^- \to j^+$ and $i^+ \to j^+$).

Add a source node $s$ to this large graph, with an edge $s \to i^-$ for each $i$ in your set of source vertices; and similarly add a sink node $t$ with an edge $i^+ \to t$ for each sink vertex $i$.

Finally, find the shortest path from $s$ to $t$ in this bigger graph using any standard algorithm  for shortest paths (e.g., Dijkstra's algorithm).

You can accommodate the restriction about adjacent edges by doubling the size of the graph again.  I'll let you work out the details.  Basically, each vertex in the bigger graph represents a vertex in the original graph, plus a little bit of state summarizing everything you need to know about what comes before this on the path.


Equality of cardinality of maximum matching and minimum vertex cover in general I'm preparing for exam and I came across this problem:

  We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time algorithm deciding if a graph is König's graph.

I'm stuck. I know that in bipartite graphs this always holds. I also know that we can find maximum matching in every graph in polynomial time. But I don't know how to connect this with minimum vertex cover problem which in general is NP-complete.

Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if there's a vertex cover consisting of one vertex out of each edge of $M$.

Denote the edges of $M$ by $e_1 = (x_1,y_1),\ldots,e_m = (x_m,y_m)$, where $m = |M|$. Let $v_i$ be a Boolean variable which determines which of $x_i,y_i$ we pick. We can express the constraint that an edge not in $M$ is covered as a disjunction of two literals. Hence we can express the existence of a vertex cover of size $M$ as a 2CNF. Since 2SAT is solvable in polynomial time, we can determine whether such a vertex cover exists.


What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice? In parallel computing, I know the speed up equation is

$$ \frac{1}{ s + \frac{1-s}{p} } $$

But what is meant by superlinear speed up? Is it something theoritical? Could you explain it with equations?

With equation: not really.

Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the bottleneck).

For example, you have serial algorithm that takes $1t$ to execute. You have $1024$ cores, so naive speedup is $1024x$, or it takes $t/1024$, but it should be calculated like in your equation taking into account memory transfer, slight modifications to the algorithm, parallelisation time.

So speedup should be lower than 1024x, but sometimes it happens that speedup is bigger, then we call it $superlinear$.

Where it comes from?
From several places: cache usage (what fits into registers, main memory or mass storage, where very often more processing units gives overall more registers per subtask), memory hit patterns, simply better (or a slightly different) algorithm, flaws in the serial code.
For example, a random process that searches space for a result is now divided into $1024$ searchers covering more space at once so finding the solution faster is more probable.
There are byproducts (if you swap elements like in bubble sort and switch into GPU it swaps all pairs at once, while serial only up to point).

On the distributed system communication is even more costly, so programs are changed to make memory usage local (which also changes memory access, divides problem differently than in sequential application).

And the most important, the sequential program is not ideally the same as the parallel version - different technology, environment, algorithm, etc. so it is hard to compare them.

Excerpt from "Introduction to Parallel Computing" Second edition by Ananth Grama, 2003

  Theoretically speedup can never exceed the number of processing elements $p$.
  If the best sequential algorithm takes $T_s$ units of time to solve a given problem on a single processing element, then a speedup of $p$ can be obtained on $p$ processing elements if none of them spends more than time $T_s/p$.
  A speedup greater than $p$ is possible only if each processing element spends less than time $T_s/p$ solving the problem.
  In this case, a single processing element could emulate the $p$ processing elements and solve the problem in fewer than $T_s$ units of time.
  This is a contradiction because speedup, by definition is computed with respect to the best sequential algorithm.

So the name "superlinear" in this context comes from the definition of speedup.


Finding a (Small-Big-Medium) subsequence Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{i_3}<x_{i_2}$. Only a yes-no answer is required.

The statement also suggest to use the "divide & conquer" strategy.

My try was the following:

I read the vector left to right

If the list changes from increasing to decreasing, then it is clear that the last read number is lower than the maximum of the currently read list. So if it is greater than the minimum of the current list we can stop. This comparation can be done in $\mathcal{O}(1)$ if we keep track of the minimum of the currently read list.
If the list changes from decreasing to increasing, then I look for the first number $m$ in the list which is a local minimum and it is lower than the last read number $c$. And then I look for a local maximum appearing after $m$ which is greater than $c$. If both searches are successful we can end. This searches can be done in $\mathcal{O}(\log n)$ time if we keep track of the local maximums and local minimums currently found (binary search).
If the list keeps increasing we do the same as in the previous step.
If the list keeps decreasing do nothing.

So the complexity is $\mathcal{O}(n\log n)$. I think the strategy is good, but an online judge rejected it. I don't know if it is due to a silly bug or because the strategy is indeed wrong.

Anyway, seeing the stats of the people who solved the problem, my solution is so memory consumming, so I really think it can be done better.

Any idea?

Your algorithm is wrong in the detail of finding a local maximum after $m$ as pointed out in the comments.

Divide-and-conquer can be used to solve this problem. If such $i_1,i_2,i_3$ exist, there are four cases:

$i_1,i_2,i_3\le n/2$, or
$i_1,i_2\le n/2$ and $i_3>n/2$, or
$i_1\le n/2$ and $i_2,i_3>n/2$, or
$i_1,i_2,i_3> n/2$.

Cases 1 and 4 can be checked by solving the sub-problems on $(x_1,\ldots,x_{n/2})$ and $(x_{n/2+1},\ldots,x_n)$. For other cases, numbers less than $\min_{i\le n/2} x_i$ are useless, so we can filter them in $O(n)$ time first. In the following analysis, we assume all numbers are no less than $\min_{i\le n/2} x_i$.

For case 3, $i_1$ can be adjusted to $\arg\min_{i\le n/2} x_i$, then $i_2$ and $i_3$ exist if and only if $x_{n/2+1}<\cdots<x_{n/2}$ does not hold. Therefore we can also check this case in $O(n)$ time.

For case 2, since we have passed case 3, we can assume $x_{n/2+1}<\cdots<x_{n/2}$. Let $r_1=n/2$, and $r_{i+1}$ be the largest index smaller than $r_i$ such that $x_{r_{i+1}}>x_{r_i}$. Similarly let $l_1=1$, and $l_{i+1}$ be the smallest index larger than $l_i$ such that $x_{l_{i+1}}<x_{l_i}$. We mark each element with which sequence its index belongs to. This can be done in $O(n)$ time and space. Easy to see $i_1$ and $i_2$ can be adjusted to $l_s$ and $r_t$ respectively for some $s$ and $t$. Furthermore, we can adjust them such that no $l_j$ or $r_j$ lies between $l_s$ and $r_t$. So we can scan from $x_1$ to $x_{n/2}$ once to get all possible $(i_1,i_2)$ pairs in $O(n)$ time.

For example, suppose $(x_1,\ldots,x_{n/2})=(40,60,30,10,50,20)$, then
$\{r_i\}$: $6,5,2$, and $\{l_i\}$: $1,3,4$. We mark these elements as $40_l,60_r,30_l,10_l,50_r,20_r$. Possible $(i_1,i_2)$ pairs are $(40,60)$ and $(10,50)$.

Every possible $(i_1,i_2)$ pair is an open interval. We need to determine whether any of $x_{n/2+1},\ldots,x_n$ falls into these intervals. Note $x_{n/2+1},\ldots,x_n$ are sorted and so are these intervals, we can determine it in $O(n)$ time.

Now checking for case 2 and 3 costs $O(n)$ time and space, so this algorithm costs $O(n\log n)$ time and space in total.


Is it admited to give the complexity of a function regarding the resulting data structure? Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$.

The time complexity of $f$ is $O(n_{_{old}})$ = $O(\log\ n_{_{new}})$,
is it admited to say that $f$ is a $O(\log n)$ function ?

The running time of a function is usually measured with respect to the length of the input, which is represented by the parameter $n$. In your case, if the input is the integer $m$ then the input length is $n = \log m$ and the running time is $O(m) = O(2^n)$.

For functions whose output is much larger than the input, it makes sense to measure the complexity with respect to the size of the output. In your case, the function runs in linear time with respect to the size of the output.

In other cases it might be meaningful to use other parameters to measure the running time of a function. For example, functions on graphs are sometimes measured with respect to the number of vertices and the number of edges. The end goal is usually to analyze the running time of some function in terms of its input length, but on the way it is OK to measure the running time of subroutines in terms of other parameters.


Grid covering by rectangles We have a $N_1 \times N_2$ grid.
We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those rectangles.

Is the decision version of this set cover problem NP-complete ?

Input : Collection $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ of rectangles on the grid (input size: $N_1N_2L$), and $K \in \mathbb{N}^+$
Output : Subset $\mathcal{S}\subset\mathcal{C}$ with $|\mathcal{S}|\leq K$ and $\mathcal{S}$ containing for each cell at least one rectangle covering it.

I found that the 1D case ($N_2=1$) can be solved in polynomial time by dynamic programming: any optimal cover is going to be the union of

an optimal cover for some subproblem of covering the first $N_1-n_1$ cells.
a 1D rectangle, i.e. an interval, covering the remaining $n_1$ cells.

I don't think however DP can work for the 2D problem: for the 1D problem, you have a $N_1$ subproblems to solve, but for 2D you have $\binom{N_1+N_2}{N_2}$ subproblems (number of North-East lattice paths on the grid).

I think the problem might be NP, but I am not sure (though it seems harder than P), and I have not succeed in finding a polynomial reduction from an NP-complete problem (3-SAT, Vertex Cover,...)

Any help or hint is welcome.

Thanks to j_random_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem:

We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered as columns $\{v_1,\dots,v_{N_1}\}$ and edges ordered as rows $\{e_1,\dots,e_{N_2}\}$.
We'll construct rectangles on this grid (the drawing below will help a lot understanding the different rectangles used)

For each vertex, we create a rectangle of type 1, which covers the central column of the column of blocks corresponding to that vertex, so we have $|V|$ rectangles of type 1.

Each block correspond to a unique couple $(e_i,v_j)$, with $e_i=(v_a,v_b)$ for each block we add a rectangle of type 2 :

if $j<a$ or $b<j$, this is a 3-by-3 rectangle covering the entire block.
if $j=a$ (resp. $j=b$), this is a 3-by-1 rectangle covering of the left (resp. right) column of the block.
if $a<j<b$, this is a 1-by-3 rectangle covering the top row of the block.

So we have $|E||V|$ rectangles of type 2, those rectangles will be obligatory to choose, as each will be the only cover for the top-left (or top-right) corner of the block it's in.

As we have said, each edge correspond to a row, with two blocks (let's call them endblocks) corresponding to the endpoints of the vertices $(e_i,v_a)$ and $(e_i,v_b)$, now we have rectangles of type 3:

for endblock $(e_i,v_a)$ (resp. $(e_i,v_b)$), we have a 1-by-2 rectangle covering the top-right (resp. top-left) corner of the endblock.

We have $2|E|$ rectangles of type 3, and again, they're obligatory as each will be the only cover for the top-right corner (if it's the first endblock) or the top-left corner (if it's the second endblock) it's in.

Now, for each edge we construct rectangles of type 4, between the endblocks, we have two rectangles for the second row :

One going from the central square of the first block to the central-left square of the second block.
One going from the central-right square of the first block to the central square of the second block.
And the same two rectangles for the third row.

We have $4|E|$ rectangles of type 4, those are not all obligatory however.

So now, to cover the grid:

$|E|(|V|+2)$ rectangles (type 2 and 3) are obligatory and $|V|+4|E|$ (type 1 and 4) are optionnal.

To cover, for a given edge, the part between the edge endblocks not yet covered (second and third rows of the row of blocks), we can either use:

the four rectangle of type 4.
one rectangle of type 1 and two rectangles of type 4.

Note that in any case, we need at least two rectangles of type 4.

So here the cost function will be : $|E|(|V|+4) + k$

If their is a valid vertex cover with less than k vertex:  we use the $|E|(|V|+2)$ obligatory rectangles, then for the optionnal rectangles, we can use the rectangles of type 1 corresponding of the vertex cover, and for every row, we need only 2 rectangles of type 4 (we already have a rectangle of type 1). So if the graph has a valid vertex cover, the grid has a valid set cover.
If we have a valid set cover for the grid (with less than $|E|(|V|+4) + k$) rectangles, then for each edge, either we already have a rectangle of type 1 (and the edge is "covered") or four rectangle of type 4, in which case, we can replace two of them by one rectangle of type 1, and we still have a valid cover with $|E|(|V|+4) + k$ rectangles. By iterating this process, we reach a valid solution with no row using four rectangle of type 4, from which we can obtain a valid vertex cover.

So the vertex cover can be reduced to the grid cover. And the grid problem instance can be encoded by $|E|(|V|+6) + |V|$ covers on a grid with $9|V||E|$ elements, so the reduction is polynomial and the grid problem is NPC.

PS :
I noticed after writing this answer that a lot of rectangles are actually useless and much simpler reduction can be made using a $|E|$-by-$3|V|$ grid with $|V|+4|E|$ covers, using cost function $3|E|+k$


Weakening and Contraction Wikipedia says that weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). However, I can't seem to get the terms yet. There are even these symbols that looks like a T turned counterclockwise.

In simple terms, what are weakening and contraction? Can they even be described without the symbol that looks like a T turned counterclockwise?

I can't comment about the programming language aspect, but here is the logical aspect. A sequent is an expression of the form
$$ A_1,\ldots,A_n \vdash B_1,\ldots,B_m $$
whose meaning is "if $A_1,\ldots,A_n$ hold then one of $B_1,\ldots,B_m$ holds", that is
$$ (A_1 \land \cdots \land A_n) \to (B_1 \lor \cdots \lor B_m). $$
Sequent calculus is nice since its laws enjoy a certain symmetry between the two sides that reflects the de Morgan symmetry between AND and OR.

Weakening is the law that states that you can a formula to either side of a sequent. That is, if a sequent $\Gamma \vdash \Delta$ is true (where $\Gamma,\Delta$ are sequences of propositions), then for every formula $X$, both sequents $\Gamma,X \vdash \Delta$ and $\Gamma \vdash \Delta,X$ also hold.

Contraction states that if a formula appears twice one of the sides, then an equivalent sequent is obtained by removing the duplicate. That is, if $\Gamma,X,X \vdash \Delta$ then also $\Gamma,X \vdash \Delta$, and similarly for duplicates on the other side.

One more structural rule, permutation, allows us to reorder formulas: if $\Gamma,X,Y,\Delta \vdash E$ then also $\Gamma,Y,X,\Delta \vdash E$, and the same for the other side.


Acceptance problem for CFGs is not regular Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars.

It is easy to show that $ACFG$ is decidable. Parsing algorithms like CKY are proofs of this fact.

Is $ACFG$ also regular? Is it also context-free? I would guess nay to both, but how would one formally show these facts?

Let's prove a more general result:

  Let $\phi\colon \{0,1\}^* \to 2^{\{0,1\}^*}$ be an arbitrary function mapping binary strings to languages over the binary alphabet. Suppose that the range of $\phi$ is infinite. Then the language $L_\phi = \{(x,y) : y \in \phi(x)\}$ is not regular.

(The language is over the alphabet consisting of $0,1$ as well as parentheses and comma.)

For the proof, we use Myhill—Nerode theory. Let $(x_n)_{n \in \mathbb{N}}$ be encodings of languages such that $\phi(x_i) \neq \phi(x_j)$ for $i \neq j$. Then the words $(x_i,$ and $(x_j,$ are inequivalent modulo $L_\phi$: taking any word $y \in \phi(x_i) \Delta \phi(x_j)$, the word $y)$ separates the words $(x_i,$ and $(x_j,$.

Interestingly, $L_\phi$ could be context-free. Let $\phi(0^n) = \{1^n\}$ and $\phi(w) = \emptyset$ if $w$ contains $1$. Then $L_\phi = \{(0^n,1^n) : n \in \mathbb{N}\}$, which is context-free.


Big-O Notation: Runtime Analysis I have a problem with an exercise, I have to analyze the following
For-Loops

Then I have to write down the explicit notation, my problem is that I don't know how to get the right m.
I tried this
but now I have no idea how to get the m, because I thought that m defines the diffrence between i and j and so I became m = n + 2 but that was wrong.
(This is the form in which it has to be)

I would really appreciate your help thx for your efforts in advance.

Kind Regards

Just for convenience, I'll write out the code first.

for(int i = 0; i <= 4 * n;  i = i + 4) {
    for(int j = 0; j <= i + 1; j++) {
        meth();
    }
}

and meth() runs in constant time $O(1)$.

Right away we can use that the outer loop runs $n+1$ times (assuming $n$ is a non-negative integer) since we are doing $0$ to $4n$ inclusive in increments of 4. The inner loop runs $i+2$ times for each iteration of the outer loop since it goes from 0 to $i+1$ inclusive in increments of 1. So we can write the total number of times the inner loop runs as

$$\sum_{i=0}^{n} (4i+2) = \sum_{i=0}^n4i + \sum_{i=0}^n2 = 4\sum_{i=0}^ni + 2(n+1) = 4\frac{n(n+1)}{2}+2(n+1) = 2(n+1)^2$$

In the arithmetic, we first break up the sum into two parts. Then we factor out the 4 in the first term and use that that we added 2 $(n+1)$ times, aka 2(n+1). Next, we use the formula $\sum_{i=0}^n i = \frac{n(n+1)}{2}$ and then finally simplify.


Is Equational Reasoning an application of Referential Transparency? In various discussions of the merits of functional programming, the phrase referential transparency or equational reasoning is often listed.

My question is - are these roughly the same thing? (One being the concept, and the second being the process of applying the concept?

Referential transparency is an operational notion: it describes what happens when you evaluate a same piece of code (typically a function) several times, namely, the return value is the same. In particular, the evaluation context can generally be ignored when considering the operational semantics of a referentially transparent language.

Equational reasoning is, well, a way to reason about code: it allows you to replace pieces of code with others without worrying about things like evaluation order or current state. This is usually valid because of referential transparency; in general the value of a given code block is dependent on it's context which prevents replacing a piece of code by another regardless of it's position within another block.

In conclusion, referential transparency is a property of the evaluation semantics and the ability to do equational reasoning is a benefit of this property.


Algorithm to translate a deterministic Büchi automaton to LTL (when possible) Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express $FGa$, and LTL cannot express "at least each odd letter is 'a'". But sometimes it is interesting to know whether the language of a DBA can be expressed in LTL.

I need an algorithm that decides whether a language of a given DBA is describable in LTL. Do you know algorithms for that?

You may find the algorithm in Diekert and Gastin's paper, Section 12. It works for both NBW and DBW (provided that you have the $\omega$-expression), and this can be decided in polynomial time.


How many sequences in a prefix code can be compressed by m bits? I have a little understanding problem with Appendix A ("Universal Codes") in the paper "Shannon Information and Kolmogorov complexity" by Gründwald and Vitanyi (Link).

At the end of page 50, they say something corresponding to:

  For each Prefix-code, the fraction of sequences of length $n$ that can be compressed by more than $m$ bits is less than $2^{-m}$.

Either this is a writing mistake or I should make a break from reading.

It is easy to see, that the number of strings with length $n$ and compression length smaller than $m$ is smaller $2^{m-n}$ for a prefix-code because there are simple not enough "shorter" words.. Did they mean this information?

It is also easy to understand, that the Kraft-Inequality $\sum_{x\in X}2^{-l(x)}\leq1$ holds for a prefix code  with source word set $X$ and the compression length $l(x)$ for strings $x\in X$.

Is that only a writing mistake? Respectively can you tell me an explanation?

There is no problem with the statement. An encoding $f$ of the set of strings of length $n$ is a map from $\{0,1\}^n$ to $\{0,1\}^*$ which is injective (one-to-one). Such a mapping compresses a string $x$ by more than $m$ if $|f(x)| < |x| - m$. In our case, all the strings have length $n$, so a string $x \in \{0,1\}^n$ is compressed by more than $m$ if $|f(x)| < n-m$. There are $\sum_{i=0}^{n-m-1} 2^i = 2^{n-m}-1 < 2^{n-m}$ such strings, and since $f$ is injective, the fraction of strings compressed by more than $m$ is less than $2^{n-m}/2^n = 2^{-m}$.


Generalized data structure Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and to perform at satisfying complexity.

However, despite the additional features of data structures (e.g. organization, like in trees storing entries according to less-like relation), all that data structures do is keeping information unchanged between algorithm's actions. Can this generic feature of data structures be izolated and defined in abstract way?

Notice that a data structure stores more than just it's accessible elements. This is probably what mean by additional feature, but I would consider it the essential feature. Take for example a binary search tree. This tree stores information on the order of its elements. In particular, by a traversal you can output the sorted sequence of elements stored in the tree in linear time. There are roughly $\Theta(4^n)$ different full binary trees with $n$ leaves. Thus the  data structure stores roughly $2n$ additional bits in this case.

Maybe this view helps. Some algorithmic problems are one-shot problems. So you take the input, process it, and then (hopefully) output the solution. Other problems, however, are trying to solve several problems for which part of the input is mostly the same. Here it might pay off to preprocess the static input (the data), such that further requests are easier to answer. The result of the preprocessing is stored (often in form of a labeled graph). This is what you do, when you store data in a data structure.

The above paragraph explained how static data structure behave. Usually data structures are dynamic, allowing you to alter the represented data and its associated information.


Simplifying sum of falling factorials I wrote the worst algorithm in the world.
Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute.
So I concluded that the equation for the number of operations is as follows:

$$n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots + n!\,.$$

Can we fold this sequence to some nice equation which will give us exact number of operations needed to complete this algorithm?

You gave the closed form for the number of operations:
$$
\sum_{m=1}^n n(n-1)\cdots(n-m+1) = \sum_{m=1}^n \frac{n!}{(n-m)!} = n! \sum_{m=0}^{n-1} \frac{1}{m!}.
$$
We can estimate this sum as follows:
$$
n! \sum_{m=0}^{n-1} \frac{1}{m!} =
n! \left(e - \sum_{m=n}^\infty \frac{1}{m!}\right) =
en! - 1 - \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} - \cdots = \\
en! - 1 - O\left(\frac{1}{n}\right).
$$


Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$ For the purpose of proving that they are not regular, what closure properties can I use to transform the languages

$L_a = \{ a^*cw \mid  w \in \{a,b \}^* \land  |w|_a = |w|_b \}$ and
$L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid  i_j∈\mathbb N \land \exists j∈[1,n]  \ i_j \not= j \}$

to  $L := \{ a^nb^n \mid n\in \mathbb N \}$, respectively?

I tried:

$L_a = \{ a^*cw \mid w \in \{a,b \}^* \land  |w|_a = |w|_b \}$

$L_a' = \{ \{a,d\}^*cw \mid w \in \{a,b,d \}^* \land  |w|_a + |w|_d = |w|_b \}$ (union?)

$L_a'' = \{ d^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$
(concatenation?)

$L_a''' = \{ w \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$
(homomorphism?)
$L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\exists j∈[1,n] \ i_j \not= j \}$

$L_b' = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$  (complement?)

$L_b'' = \{ac^{i_1}ac^{i_2}\ldots ac^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$ (homomorphism?)

Regular languages are closed under intersection. This often allows to cut away all parts of a language that are not needed to show non-regularity. Complementation serves a similar purpose: if the original language is "complicated", the complement may be simpler so work with (in terms of other closure properties).

Hints:

   For $L_a$, the part right of $c$ is sufficient; try to intersect with a regular expression that gets rid of the clutter. Note that the part right of $c$ is close to $L$. Maybe another regular expression can help?
 For $L_b$, note that we get $n$ times $a$ and $b$ (in the last block), respectively, if we replace $\exists \dots i_j \neq j$ with $\forall \dots i_j=j$.

Complete solution for $L_a$:

   Let $L_a' := L_a \cap \mathcal{L}(ca^*b^*) = \{ ca^nb^n \mid n \in \mathbb{N} \}$. Then, with homomorphism $\phi : \{a,b,c\} \to \{a,b\}^*$ defined by

 $\qquad \displaystyle \phi(w) = \begin{cases} \varepsilon &, w = c \\ w &, \text{ else} \end{cases}$

 we have $\phi(L_a') = L$.

Complete solution for $L_b$:

   In order to get rid of the pesky $\exists$, we can complement. That introduces lots of words we do not want, i.e. such that don't have the $(ab^*)^*$ structure, so we can intersect with exactly that regular expression to get structure back:

 $\qquad \displaystyle L_b' := \overline{L_b} \cap \mathcal{L}((ab^*)^*) = \{ abab^2ab^3\dots ab^n \mid n \in \mathbb{N} \}$.

 Note that words in $L_b'$ contain exactly $n$ times the symbol $a$; if we can get rid of all blocks of $b$ but the last, we have $L$. This is possible by (nondeterministic) finite state transduction which $\mathsf{REG}$ is closed under. The transducer removes all $b$ until it decides on an $a$ that is was the last one. After that it emits the input and accepts if no further $a$ is encountered.

 Note that if we reverse $L_b'$, we can cut away the excess $b$ with a deterministic transducer and reverse again to obtain $L$.


Equal partition up to one integer In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" requirement is replaced with the following:

  The difference $|\sum_A - \sum_B|$ should be at most the largest integer in the set with the larger sum.

A solution always exists, and can be found using the following algorithm:

Order the integers by descending value.
Put the largest integer in subset A, the second in subset B, the third in subset A, etc.

The sum in subset A is always at least as large as the sum in subset B, but if we remove the largest integer from subset A, then the sum in subset B is at least as large as the remainder. Hence, the partition is equal up to one integer.

MY QUESTION IS: what happens when there are cardinality constraints on the subsets? Formally, the task is to partition $n$ given integers into two subsets $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. The algorithm above does not work, and indeed an equal partition up-to-one-integer may not exist. What is an algorithm to decide whether such a partition exists?

There is an $O(n \log n)$ algorithm for this problem.

To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\sum_A - \sum_B| \le M$.

Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum_A < \sum_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum_B - M \le \sum_A \le \sum_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum_B + M < \sum_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum_A - \sum_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum_B + M < \sum_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum_A$ will become smaller than $\sum_B$ by repeating this operation.
This can be implemented in $O(n \log n)$ with sorting and two pointers.


Comparing random access and sequential access Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases :

We read (or write) sequentially from part $1$ to part $k$.
We read (or write) the part indexed $N_1$, then the part indexed $N_2$, ..., and the part indexed $N_k$.

Have these two cases the same complexity in the RAM model?

In which model these two cases don't have the same complexity?

The answer critically depends on the model in use, specifically whether or not the memory is cached, and how the cache is being used. In the following I'll explore the two main architectures: with and without a cache.
Throughout, we assume the file consists of $k$ parts: $f_1, \ldots, f_k$ where $f_i$ is 4 bytes (32bits).
A. The simple case: a single-layered RAM.
In this case, we assume that we have a large memory $M$, where each address contains 32 bits of data.  Accessing an address in the memory takes $t_M$ time, and fetches the 32bits stored in that address.
We can assume that the file is stored sequentially in the memory, (although it doesn't matter), that is, $M[i]=f_i$ for $i\le k$ and $M[i]=0$ otherwise.
In this case, accessing the file in any order will take the same time, namely $k \cdot t_M$.
bottom line: RAM allows random-access with the same access time as sequential access. (this is why it is called a Random-Access Memory, RAM).
B. A more realistic case: a cached memory
In the more interesting case, the memory is layered. There is a small fast cache we denote $C$ that contains small amount of addresses, say 1024. Each address contains 32bits of data.
When accessing an address $i$ in the memory, the process is the following:

if $M[i]$ exists in the cache, say $C[j]=M[i]$, then the access time is $t_c$. (this is called a cache hit)
Otherwise, the slow memory is being accessed, and the data is fetched in time $t_C+t_M$. Additionally, $M[i]$ is now stored in the cache as well. (this is called a cache miss)

It is assumed that $t_C \ll t_M$. In case of a miss, if the cache is already full, we assume that the new value brought to the cache replaces the oldest item in the cache (the one that was last accessed the earliest)
B.1 A Single Access
Assume that at the beginning the cache is empty.
If the file is being accessed only a single time, then, each address we access is a miss, and it will take us $k(t_C+t_M)$ to access the entire file, regardless of the order.
B.2 Multiple Access
Now, assume we need to access the file twice. At the first time the cache is empty and so it will take us $k(t_C+t_M)$ to fetch the file, as above.
On the second time, things are a bit different.
If $k<1024$, then in the next access, the entire file is in the cache, and it will take us $k t_C$ time to access it again, regardless of the access order.
If $k>1024$ (say $k = 2048$), then in the second access the times slightly change:

if we access the file sequentially, then we will always have a miss, since the cache will hold the 1024 parts we have most recently accessed, and will never hold the next one that we need. The time is $k(t_C+t_M)$,
if we access it in a random order (that is independent of the order in the first time we accessed the file), then the first part will be there with probability $1/2= 1024/2048$, the second with probability $1023/2047$ and so on (the last 1024 parts will always cause a miss). This gives a slightly better access time.

B.3 Blocked cache
Realistic caches don't work byte-by-byte, but rather they work in blocks.
Let's say the block size is 256 words (that is, the 1024-cells cache holds 4 blocks of 256$\times$32bits each). Now, when you access an address $i$ in the memory, the following process happens:

if $M[i]$ exists in the cache, then the access time is $t_c$.
Otherwise, the slow memory is being accessed, and the entire block that contains $M[i]$ is brought into the cache. This takes time $t_C + 256t_M$.
We assume we always work in aligned blocks of 256 words: so if you access any address between 0 and 255, the same block $M[0],\ldots, M[255]$ is fetched into the cache.

Now, if you access the file in sequential order, once you access $M[0]$ you get a miss, and the first block gets into the cache. This takes time $t_C + 256t_M$. The next 255 access will be a hit. The total time will be about $k(t_C + t_M)$.
However, if you access the file randomly, every part has a probability of about $1024/k$ to already be in the cache (this is not exactly correct, but close enough). Thus the time will be (approximately)
$k \cdot (1024/k \cdot t_c + (1-1024/k)(t_C + 256t_M))$. This may be substantially worse than in the sequential case.
bottom line: if the cache is blocked, you get advantage accessing sequentially. Otherwise, it shouldn't matter that much.
C. The (even more) realistic case
Finally, I must add that there are more parameters that affect the analysis.
First, usually the memory has several cache layers, e.g., L1--L3 cache, and a main memory. Each level has more memory but is slower than the layer beneath it.
In order to give a precise analysis, a full description of the memory and the access pattern should be given, since many parameters might have a dramatic effect on the total access time.


Randomly generating graph based off number of connections on each node I'm trying to generate a graph based off some data I have.
This graph should have N nodes where the number of edges each node has is equal to a random number P(k), where k is the "index" of the node (mostly arbitrary).
My question is, is there an actual way to do this? I'm thinking that I need more data that either determines the density or another degree of connections out (N1->N2->N3), but I'm not entirely sure.

You essentially want to generate a graph with some degree sequence (which you want to be random, but this is not relevant); this is called the graph realization problem which is solved e.g. by the Havel-Hakimi algorithm in the sense that the algorithm will return a (simple) graph with the desired degree sequence if that is possible (such sequences are called graphic). Note that not all finite sequences over $\mathbb N$ are graphic as e.g. any sequence whose members sum to an odd number cannot be graphic by the handshake lemma (which states that the sum of all degrees in a graph is equal to 2 times the number of edges in a graph and thus even).
Further, the solutions will in general not be unique: The degree sequence $(2, 2, 2, 2, 2, 2)$ for example can be realized by the cycle graph $C_6$ of size $6$ or the disjoint union $C_3 \mathop{\dot\cup} C_3$ of two cycle graphs $C_3$ of size $3$ each.
Many graph libraries for programming languages have implementations of algorithms for this problem, for example the Python library networkx.


Model Checking: hardware vs software In short: What is the basic difference that allows model checking for hardware to be "easily" solvable, but makes it undecidable for software?

I guess it has to boil down to the difference between hardware being finite automata and software having the expressiveness of a Turing machine, which would basically mean that its the infinite amount of (randomly accessible, vs. that of a push-down automaton) memory that the Turing machine has available -- is this correct?

The statespace explosion problem.

More specifically, software often uses unbounded loops, pointers into complex data structures on the heap, and dynamic allocation.  Each of these can cause rapid statespace explosion: the number of states increases rapidly, or becomes infinite.  Model checking has difficulty with that.  These constructs tend to be more common in software than in hardware, explaining why model checking tends to be more effective on hardware than on software (as a general rule, though there are of course exceptions).


What does the term "top-most" mean in the context of formal grammars? I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here:

$$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \mid ( \mathit{Sum} )$$

I think I understand the intuition that in a string like:

$$ 0+1+0 $$

we want the 1 to be an argument to the left plus, so we put some sort of wall so that the symbol + cannot be right next to the 1. So something like this:

\begin{align}
\mathit{Sum} &::= \mathit{Ntp} \mid \mathit{Ntp} + \mathit{Sum}\\
\mathit{Ntp} &::= 0 \mid 1 \mid ( \mathit{Sum} )\end{align}

From my understanding this always enforces to put a parenthesis on the left side of any sum. Thus, putting a wall literally using the symbol (.

However, what I don't understand is that the 2nd rule is supposed to mean:

  Not top-most plus.

But I don't understand what "top-most" is supposed to mean. What does that mean?

Also, can someone give me a clearer argument to why the above grammar is indeed left associative? I feel my argument is a little to hand wavy or unclear to really be convincing.

Cross posted:

https://www.quora.com/unanswered/What-does-the-term-top-most-mean-in-the-context-of-formal-grammars

In the context of context-free languages, "top-most" refers to the root of a parse tree. Your rules guarantee that a sum of the form $1+1+1$ is parsed as $1+(1+1)$ rather than the opposite, since the nonterminal Ntp ("not top-most") doesn't allow + to be the top-most operator (you should imagine a parse tree in which + labels the root).
Consider the following two parse trees: (generated using Syntax Tree Generator)

On the left, the left child of the root has + as the top-most operator.
On the right, the right child of the root has + as the top-most operator.
Your grammar only allows the second parse tree, since the left child of + must not have + as the top-most operator.


Cashier Scanning Algorithm Problem I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.

A cashier only has x time to scan a person's goods. The goods come 1
item per time step in a conveyor belt. In one time step, the cashier
can either scan an item or bag the item (so when bagging, the cashier
misses the item on the conveyor belt for that time step). The place to
hold scanned, unbagged goods has a max capacity of c, where each
good takes 1 unit space. However, once the cashier starts to bag
scanned items, the cashier must bag all unbagged scanned items. The
cashier also wants to ensure he makes the most money possible. How
would the cashier go about choosing the goods such that he maximizes
the amount of money the buyer spends. What is the maximum amount of
money the cashier can make?

This seems to be a modification of the 0-1 knapsack problem, where the max capacity c is the max capacity of the knapsack, the price of the item is its value in the knapsack, and all items have a 1 unit space. I am, however, confused about how I would incorporate the "conveyor belt" of missing items and the moving of items out of c into the algorithm. I imagine this could still be run in $O(nc)$ time with $O(c)$ space complexity (in fact the original problem statement says it should be possible in these bounds). How would I go about modifying the 0-1 knapsack problem for this?

Let the $i$th item have profit $p_i$, and assume there are $n$ items passing by.
We can construct a graph where the nodes are pairs $(k, b)$ where $k$ is the number of timesteps, and $b$ is the number of items in our bagging area. We have $0 \leq k \leq x$ and $0 \leq b \leq c$.
Then, avoiding invalid nodes and/or nonsensical self-edges,

Add edges from $(i-1, b)$ to $(i, b + 1)$ with weight $-p_i$. These represent scanning an item.

Add edges from $(i, b)$ to $(i + 1, b)$ with weight $0$ for all $i$. These represent skipping an item.

Add edges from $(i, b)$ to $(i + b, 0)$. These represent bagging all scanned items.

Now we have a directed weighted acyclic graph, in which we can find the longest path in linear time. And the longest path between $(0, 0)$ and $(x, 0)$ precisely gives us the maximum profit (and following the path also gives us the steps used).
There are $O(cn)$ edges, and thus that is our complexity.


Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n)) Suppose I have an algorithm whose running time is
 $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$

And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\frac{n}{f(n)}\right)\right)$, i.e. I can get an algorithm whose running time is $O(g(n)) = O\left(\frac{\log\frac{n}{\frac{\log n}{\log\log n}}} {\log\log\frac{n}{\frac{\log n}{\log\log n}}}\right) = O\left(\frac{\log\frac{n\log\log n}{\log n}} {\log\log\frac{n\log\log n}{\log n}}\right)$.

I'm pretty sure that $g(n) < f(n)$ for big enough $n$ (by using wolfram alpha) but wasn't able to prove it.

My questions are:

Is $g(n) < f(n)$ in fact true (starting from some n)?
Is $g(n)$ asymptotically better the $f(n)$, i.e. is $g(n) = o(f(n))$
Assuming this is asymptotically better, I can do this step again and further improve the running time of the algorithm. Meaning that in 1 more step I can make my algorithm run in time of $O\left(\frac{n}{f\left(\frac{n}{f(n)}\right)}\right)$, and I can repeat this process as many times as I want. How many times should the process be repeated to get the best asymptotically running times and what will it be? obviously repeating it $O(f(n))$ times will already have a running time of $O(f(n))$ only for the repetition of this process and will not improve the overall algorithm complexity.

Here are the functions.
$$f(n) = \frac{\log(n)}{\log\log(n)}$$
$$h(n)=\frac n{f(n)}=\frac{n\log\log(n)}{\log(n)}$$
$$g(n)=f(h(n))=\frac{\log(\frac{n\log\log(n)}{\log(n)})} {\log\log(\frac{n\log\log(n)}{\log(n)})}$$

  Is $g(n) < f(n)$ in fact true (starting from some $n$)?

Yes, here is a proof.

Let us compute the derivative of $f(x)$ with respect to $x$ as a real variable.

$$\frac{df}{dx}
=\frac{\frac{\log\log x}{x}-\frac{\log x}{x\log x}}{(\log\log x)^2}
=\frac{\log\log x-1}{x\ (\log\log x)^2}$$

So $\frac{df}{dx}\gt0$ when $e^e <x$. That means, $f(x)$ is strictly increasing once $e^e\lt x$.

If $n$ is large enough, $e^e\lt h(n) \lt n$, which implies $f(h(n)) < f(n)$, i.e., $g(n) < f(n)$.

If we want to be specific, we can show that $e^e\lt h(n) \lt n$ when $n > e^{e+2}$.

  Is $g(n)$ asymptotically better the $f(n)$, i.e. is $g(n) = o(f(n))$?

No, $g(n) = \Theta(f(n))$. In fact, $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$

  Assuming this is asymptotically better, I can do ...

Well, that assumption is invalid.

Here are two exercises.

Exercise 1. Show that $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$ using the following hint or steps.

Recall that $\log(n) < n^\epsilon$ for any constant $\epsilon>0$ when $n$ is large enough.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log(\frac{n\log\log(n)}{\log(n)})}{\log(n)}=1$.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log\log(\frac{n\log\log(n)}{\log(n)})}{\log\log(n)}=1$.

Exercise 2. Show that $g(n)−f(n)=O(1)$. (This exercise might be hard.)


Approximate a smooth f(x,y) function with a polynomial function I have a discrete function of two real variables defined as a set of point in a rectangular domain. The function is smooth. I need to approximate it with a polynomial function of the 2nd degree with the error as little as possible. What algorithm can I use to find out the constants for the polynomial?

Wikipedia:

  In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable $x$ and the dependent variable $y$ is modelled as an $n^{th}$ degree polynomial in $x$.

One possible solution is the polynomial regression, that is, curve fitting method. Given a set of points $Y$ you may use one of two algorithms: closed form solution or gradient descent. When number of points is very large then the gradient descent is  faster than closed form solution. Also note that we measure error using residual sum of squares (RSS). Both algorithms finds coefficients by minimizing the RSS. This post may help as well.


Is the language $\{a^n b^m : 1000|nm \}$ regular? We have a language  $$ L = \{a^n b^m \mid 1000|nm \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say  $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$ and 1000|nm
if I say i = 0 , $L =a^{n-t}b^m$ and 1000|(n-h)*m and I can't prove (n-h)*m isn't dividable by 1000.
if I say i = 2  $L =a^{n+t}b^m$ and 1000|(n+h)*m I can't prove this too because I'm not sure about h value.
I think it didn't work. any idea?
I would appreciate it if you helped me with this.

Notice that $1000 = 2^3 5^3$. Then $1000 | nm$ iff for some $0 \le i,j \le 3$,
$n$ is multiple of $2^i 5^j$ and $m$ is a multiple of $2^{3-i} 5^{3-j}$ (notice that there are only finitely many choices for $i$ and $j$).
Then $L$ can be obtained as the union of the languages $L_{i,j} = \{a^n b^m : 2^i 5^j|n \;\mbox{ and }\; 2^{3-i} 5^{3-j}|m\}$.
Each of these languages  $L_{i,j}$ is the concatenation of $L'_{i,j} = \{ a^n : 2^i 5^j|n\}$ with $L''_{i,j} = \{b^m : 2^{3-i}5^{3-j}|m\}$.
It is easy to see that each $L'_{i,j}$ and each $L''_{i,j}$ is regular. By the closure properties of regular languages $L$ is regular.


Double hashing constraints For double hashing, we have some constraints on $h'(k)$

(1) It should never evaluate to 0

(2) It should be relatively prime to m

How to show that all slots in an open addressing table will be included in a probe sequence.

In double hashing, we have (for a specific $k$) the series $h(k) + nh'(k) \mod m$
Since we have that $gcd(h'(k), m) = 1$ (they are relatively prime), then from Bézout's identity there exists two integers a,b such that $ah'(k) + bm = 1$. since $h'(k)$ is not 0, we can conclude that b is not 0 and thus also a is not 0.
We have $ah'(k) = 1 \mod m$, which means that a is the inverse of h'(k) in modulo m.
Now, let $0 \leq i \leq m$ be an integer. by choosing $n = ia$, we have $( h(k) + nh'(k) ) \mod m = ( h(k) + iah'(k) ) \mod m = ( h(k) + i ) \mod m$.
This concludes the proof (think why).
I hope i managed to help!


Why doesn't everyone use distributed operating systems? As requested by a moderator, this question as been separated from my question about microkernel-based operating systems.

In the 1980's, the team that developed C and Unix developed a distributed operating system Plan 9 from Bell Labs. Its descendant Inferno is still with us. Given its impeccable pedigree, the fact that Unix's own creators agree it is better, and the fact that the are accustomed to ideas such as that of a virtual machine today, one would have expected such operating systems to have replaced Linux, Windows, and so on. But this hasn't happened.

Wikipedia cites several opinions as to the probably reasons for the failure of Plan 9, including Eric Raymond's:

  It looks like Plan 9 failed simply because it fell short of being a compelling enough improvement on Unix to displace its ancestor. Compared to Plan 9, Unix creaks and clanks and has obvious rust spots, but it gets the job done well enough to hold its position. There is a lesson here for ambitious system architects: the most dangerous enemy of a better solution is an existing codebase that is just good enough.

However, to choose one pet example, in another domain, platforms such as lichess prove that a new upstart platform (in lichess's case a chess platform) can displace established platforms if it offers a compelling enough advantage in terms of a user-friendly experience.

So I would like to ask, why has the world not switched over to Inferno? What, in fact, prevents the world from migrating to distributed OS's, particularly given that virtual machines, multiple CPUs, etc. are commonplace? Is there a "hard barrier" that Inferno has not crossed in terms of its capabilities?

This is part of an answer.  Others will probably be able to add other points.

A chess platform has to do a limited number of things, while an OS has to be able to do everything that OSes do, which is unlimited.  You need lots of utilities, lots of apps written, and to get those, lots of compilers and coders' tools, etc.  It's a much harder thing to get off the ground, and doing so is as much a social endeavor as a technical one.  It's quite interesting that Linux took off as it did, but there were other competing projects at the time such as FreeBSD and GNU (which was supposed to be an OS, and not just Linux's utility suite) that have fallen by the wayside.  This has a lot to do with choices that Linus Torvalds and others made early on in the process that gradually led to more and more people hacking on Linux and using it, I believe.  Some of the choices were reflected in the code itself, but some of them had to do with social factors.  Part of it is probably just chance, though.  It didn't happen overnight with Linux, either.  It took several years before it started to get popular enough that it might have had a chance to grow into the popularity it has now.

The point is that being better isn't enough.


Why does Prim's algorithm keep track of a node's parent? There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of  a node's parent.  In Dijkstra's algorithm, the parent of the node needs to be tracked in order to follow the chain back to the original node to determine the distance from the source, however since Prim's algorithm only requires knowledge of the distance from the minimal spanning tree, rather than a specific node, there would be no reason to track the parent.

Please refer to the following pseudocode as reference:

PRIM(V, E, w, r )
  Q ← { }
  for each u in V do
    key[u] ← ∞
    π[u] ← NIL
    INSERT(Q, u)
  DECREASE-KEY(Q, r, 0)    ▷ key[r ] ← 0
  while Q is not empty do
    u ← EXTRACT-MIN(Q)
    for each v in Adj[u] do
      if v in Q and w(u, v) < key[v] then
        π[v] ← u
        DECREASE-KEY(Q, v, w(u, v))

Keeping the parent of each vertex is not a requirement to get the minimum spanning tree. For example, the algorithm as described on Wikipedia does not do this.

However, it's worth noting that there is more than one representation of an MST. In certain applications, it might be useful to quickly find the parent of a particular vertex.