Is Dominosa NP-Hard? Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$
  grid. Before the game begins, the domino bones  $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$
  are placed on the grid (constituting a perfect tiling). In the next step, the domino bones are hidden, leaving only the numbers revealed. The purpose of the game is to recover the original arrangement of the domino bones.
You can play the game here: http://www.puzzle-dominosa.com/:

Rules:

  The rules are simple. You have to find the location of all the dominoes on the grid. A domino is a pair of numbers. You can only have one of each pair.

I have some polynomial algorithms that solve a relatively small part of the puzzle. I could also show that typical Dominosa grids have at least $2^{\frac{n}{2}+o\left(n\right)}$ solutions.

Is Dominosa NP-Hard?

${\rm D{\small OMINOSA}}$ is NP-hard

Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is:

  Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

Obviously, the optimization problem, the problem of actually finding a solution to the game is at least as hard, or harder, than the decision problem.

We will convert a $1\text{-}3\text{-in-}{\rm S{\small AT}}$ formula to a corresponding grid, that will only be coverable iff there is a satisfiable assignment to the formula. Furthermore, the covering can actually be used to recover the satisfying assignment.

Therefore, if the construction presented is correct, and one could solve a game in polynomial time on a DTM, then it would imply ${\rm P=NP}$. This implies ${\rm D {\small OMINOSA}}$ is NP-hard.

Reduction from $1\text{-}3\text{-in-}{\rm S{\small AT}}$ to ${\rm D {\small OMINOSA}}$

Introduction

Most of the $3\text{-}{\rm S{\small AT}}$ problems/variants have a pretty good correspondence to ${\rm C{\small IRCUIT}S{\small AT}}$. It can be important to think of the problems in parallel; as they are related to each-other, almost anything in one problem can be related to in the other.

${\rm C{\small IRCUIT}S{\small AT}}$ has a planar variant, to which it reduces, called ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$. This conversion is very elegant, and basically allows you to take any planar embedding, find the remaining crossing wires, and use a "gadget" to let the wires cross via a planar "gate" (collection of gadgets, with input and output wires).

Conveniently, most of the $3\text{-}{\rm S{\small AT}}$ variants also have reductions to planar variants, which parallel ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, and are very related; easily reducible from one to another, and easy to reason about. So whenever I come to a planar problem that might be NP-hard, I think in terms of the planar variants of $3\text{-}{\rm S{\small AT}}$, and their parallels in ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$.

The planar variants are important to know, because they make help make reductions to planar/geometric problems, like Euclidean TSP (incidentally a pretty rare reduction to find and learn). Thus, there is ${\rm P{\small LANAR}}\text{-}3\text{-}{\rm S{\small AT}}$, and a parellel, ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, to aid in such reductions.

Other $3\text{-}{\rm S{\small AT}}$ variants are important to know because some of them are weaker; that is, seemingly "easier", yet still NP-complete. They seem easier to solve at first glance - and they are much simpler - yet are still NP-complete. NP-complete, but simpler; and therefore easier to make reductions to, in many cases.

For example, there is $1\text{-in-}3\text{-}{\rm S{\small AT}}$. For some problems, you can easily make an exactly $1\text{-in-}3$ gadget, while making "at least 1 in 3", like the standard $3\text{-}{\rm S{\small AT}}$ uses, would be non-obvious and make for huge constructions.

Another example is ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$. Monotone makes things a lot simpler when you have a construction that can't easily negate values.

Even more amazing is that ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ has a planar variant: ${\rm P{\small LANAR}}\text{-}{\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$! So this makes things a lot easier; you don't have to cross "wires" (remember, there are parallels in ${\rm C{\small IRCUIT}S{\small AT}}$ to these), and trust me, while crossing gadgets are fun to make, they tend to be very non-obvious and difficult.

$$
\begin{array}{c|c|c|ccc}
&&&&\hspace{1em}&\hline\\
{\rm\mathbf{P{\small ROBLEM}}}
  &\scriptsize{{\rm\mathbf{MONOTONE}}}
  &\scriptsize{{\rm\mathbf{PLANAR}}}
  &\scriptsize{{\rm\mathbf{1\text{-in-}3}}}
  &&{\rm\mathbf{NP\text{-}hard}}
  \\
\hline\\
{\rm\mathbf{3\text{-} S{\small AT}}}
  & \text{No} & \text{No} & \text{No}
  && \text{Yes}\\
\hline\\
{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}
  & \text{Yes} & \text{No} & \text{No}
  && {\text{No}}^1\\
{\rm\mathbf{P{\small LANAR}\text{-}3\text{-} S{\small AT}}}
  & \text{No} & \text{Yes} & \text{No}
  && {\text{Yes}}^2\\
{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}
  & \text{No} & \text{No} & \text{Yes}
  &&
          {\text{Yes}}^3\\
\hline\\
\genfrac{}{}{0}{1}
  {\rm\mathbf{P{\small LANAR}}}
  {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}
  & \text{No} & \text{Yes} & \text{Yes}
  &&
          {\text{Yes}}^4\\\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{M{\small ONOTONE}\text{-} }}}
  {{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}}
  & \text{Yes} & \text{No} & \text{Yes}
  &&
          {\text{Yes}}^5\\\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{P{\small LANAR}\text{-}}}}
  {{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}}
  & \text{Yes} & \text{Yes} & \text{No}
  && {\text{Yes!}}^6\\
\hline\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{P{\small LANAR}\text{-}M{\small ONOTONE}\text{-} }}}
  {{\rm\mathbf{1\text{-in-}3\text{-}S{\small AT}}}}
  & \text{Yes} & \text{Yes} & \text{Yes} && {\text{Yes}}^7\\
\end{array}
$$

Pure literal elimination
Schaefer's dichotomy theorem
The Problem of Compatible Representatives
Minimum Weight Triangulation is NP-Hard
Schaefer's dichotomy theorem
Finding Perfect Auto-Partitions is NP-hard
Optimal Binary Space Partitions in the Plane

One way to start with a reduction, is to try to find "gadgets" that resemble wires, and a gadget that resembles a clause of one of the $3\text{-}{\rm S{\small AT}}$ variants. As a bonus, many of the variants are planar, we can probably get away without crossing wires.

What is a "gadget"? A gadget is some construction in the problem, that is helpful as a building block to build gates/wires/clauses. Some gadgets will have a restricted set of states; for example, a gadget with two states can be used as a variable; one state is "true" and the other is "false". A gadget with two states, that can be "long", can bend, and split, is useful as a wire - if it can interact with a variable, and become constrained to extend the state of the variable to another location. A gadget with exactly three states can perhaps be used as a clause; if it can be used to constrain "one of three" wires via each one of its three states. Similarly, one might want all sorts of logic gates, like a not-gadget, an or-gadget, an xor-gadget etc; where you can have some sort of constraint via the gadget that relates 2 or 3 wires in such a way.

A Building-block

First, let's reserve a number, for example, $\mathbf 1$, on the board. We will make $\mathbf 1$ a building block for everything else.
We will use a corner to make sure that $\mathbf 1$ can never connect to another $\mathbf 1$, except in this corner, where it must.
Below (in the three figures) is the corner, and how we place the $\mathbf 1$s there.
We will use the $\star$ to indicate unique values in all the grid, in all the diagrams.
In fact, we will cover our grid with $\star$ values before overlaying them with important values; therefore, by default cover everything with $\star$ values.

As you can see, by placing the $3$   $\mathbf{1}$s the pair $\mathbf{(1,1)}$ must be used up in this configuration; it must use one of the dashed-tiles. Now $\mathbf{(1,1)}$ can never happen elsewhere in the board, which is what we need.

There are alternate ways of reserving a number, either against the wall with $4$ of them, or in the middle of nowhere, with $5$ of them in a cross. Any way is fine, as long as $\mathbf{(1,1)}$ is forced.

A Wall

Now, it would be very useful to be able to make "walls" and "corners" all over the place, not just at the sides of the grid. Look what happens if we line up pairs of ones in a line; the one's have no choice but to pair with their neighbors, making a "wall" of width $4$.

Images below, from left to right:

A line of pairs of $\mathbf 1$s.
The only possible tiling of that $\mathbf 1$-square.
The only possible tiling of (almost) all the $\mathbf 1$s in the line.
The wall line, drawn for emphasis.

An initial attempt at a wire

Now, by placing two "walls" opposite each-other, and leaving a space of $\mathbf 1$ between the walls, perhaps we can come up with a "wire"-like gadget.

Showing only the wall-borders, this is what we get in the figures below (left to right):

Placing two walls opposite each-other.
Putting unique numbers inside.
Rightmost two: Two possible states of the wire.

How it works:

  There cannot be any holes in the tube/wire, therefore, if the the tiles are shifted up, then they all must be shifted up, all along the tube; if they are shifted down, it will "suck" down all of them. Thus, we can send a "signal" from one side of the wire to the other; in other words, propagate a value.

Thus, now we can propagate a value across long distances!

Remaining limitations are:

We cannot bend a wire,
We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Bending a Wire, Part 1: Wall Below

Next problem is, we need to be able to bend a wire, not just go straight ...

So. We will break the bending part down into two parts; the upper part and the lower part. First the lower part. Ignore the upper part of the bend, we will do that later.

The figures below show a bit of a problem with bending; the top of the wire is "loose", it seems difficult to make a wall that turns a sharp 90 degrees.

Left to right:

The top of a wire is "loose".
What happens if we try to bend it; we want to wire to be in between the blue lines. Again, Ignore the upper part of the bend, we will do that later.
As you can see, the top $\mathbf 1$s are loose, they can tile along the wall, or through the wire! This is no good.

One solution is as follows:

Pick a $\mathbf{(x,1)}$ pair near the bend. Take the value of that $\mathbf x$ square, let us name it $\mathbf{ q \star}$; this means the number is unique in the entire grid, just like $\mathbf \star$, and is reused once, here in this bend only. Because this $\mathbf x$ is paired with a $\mathbf 1$, it cannot be paired with a $\mathbf 1$ again. Therefore, we place it right on top of the rightmost-topmost $\mathbf 1$. Now, we can clearly see, the only option remaining to pair for that $\mathbf 1$ is to its right, and thus it will solidify the wall.

Illustration below, description from left to right:

The situation with the problem.
Pick a square, let $\mathbf{q \star}$ be the square value of any square in the bend (of course not $\mathbf 1$s though).
The two togglings of the rightmost-topmost $\mathbf 1$ tilings; this time, only one of them is valid.

However, how can we be sure this $\mathbf {{q}{\star}}$ won't ruin the wire? Below you can see the states of the wire, and that the $\mathbf {{q}{\star}}$ will not hamper with it.

From left to right:

The current construction.
Two rightmost figures: The states of the wire; empirically, they are not hampered by the introduction of $\mathbf {{q}{\star}}$.

Now we still have a loose $\mathbf 1$ on top; the leftmost-topmost-$\mathbf 1$.

We will do the same thing; pick a pair $\mathbf{({r}{\star},1)}$ that is already paired in the bend-tiles, and place $\mathbf{r}{\star}$ on top of the leftmost-topmost-$\mathbf 1$.

Illustration below, left to right:

Our current construction.
The problem: leftmost-topmost-$\mathbf 1$ can pair with a number in the wire, or with the wall; we want it to only pair with the wall.
Choosing an $\mathbf{r}{\star}$, and using the same number on top of the leftmost-topmost-$\mathbf 1$.

And we finally get our lower bend. Illustration below, descriptions, from left to right:

Left: Our final construction for a bend.
Right: How to continue the wire to the left.

Bending a Wire, Part 2: Wall Above

The walls to make the top corner of the bend are much simpler. You simple align a vertical wall with a horizontal wall. Illustration below, description from left to right:

The wire-bend we want to make.
Place the vertical section of the wall squares down.
Tiling the  squares of the vertical-wall.
Placement and tiling of the horizontal wall; it can meet the vertical wall, and form a corner.

Now you should be convinced that we can place and bend wires. We still can't split or cross wires though, more on that later.

Remaining limitations are:

We cannot bend a wire,
We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

A Valued Wire

Now we have wires, it would be nice to have a valued-wire, where we can see the value of a wire, like an LED on a circuit board. So what we do, is take a wire, say of length $7$, and introduced a named $\star$ square, we'll call it ${\mathcal T}{\star}$, and another named square, we'll call it ${\mathcal F}{\star}$. These are both unique to each valued wire section, ie. only twice, and they will only get reused within a single valued wire. They are placed in pairs, the two ${\mathcal T}{\star}$ squares right next to each-other, and the two ${\mathcal F}{\star}$ squares next to each-other, with a single $\star$ square separating them. Illustrated below, description from left to right:

Left: A wire.
Right: The square-configuration.

So how do we tell if a wire is true or false? Well, a wire has two states. In each of these states, one of ${\mathcal T}{\star}$ or ${\mathcal F}{\star}$ will be paired in the same tile; the value that is paired is the value of the wire. Illustration below, desciption from left to right:

Left, right: The two states of the valued wire;
Left: Wire is valued trued, as the ${\mathcal T}{\star}$ squares share a single tile
Right: Wire is valued false as the ${\mathcal F}{\star}$ squares share a single tile.

We can now have named variable that we can use, to place our ${\rm 3\text{-}S{\small AT}}$ variables down on the grid. We can connect two valued wires and force them to have the same value, or if we connect them with an odd-length, force them to have different values; and using wires, we can do this long-distance, across the grid. Using wires, we can propagate the values of the named variables all over the place.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Not-gate

A not-gate is unnecessary as it is implicit: simply using an off-by-one wire length we can negate the value of the wire.

A Clause Gate

Now I can demonstrate a simple clause gadget; it will connect to $3$ wires, and force one of them to be "pulled" state, and force the other two to be in the "pushed" state. We can use this, this is an exactly one-in-three relationship; we set the odd-wire-state to mean "true", and the other two wire-states to mean "false", and we are set.

Illustrations below, descriptions from left to right:

The wire-layout of the clause gadget. It makes a "plus" sign; the joining of 3 wires in one spot.
Fill the wire with unique $\star$ squares.
The three states of the center square. Each of these states "pulls" exactly one wire into the center, the essential point of the gate; to act like a ${\rm 1\text{-in-}3\text{-}S{\small AT}}$ clause.

Now let's take a look at the different states. Illustration below, description from left to right:

The left wire is pulled into the center; the other two are pushed out.
The bottom wire is pulled into the center; the other two are pushed out.
The bottom-right wire is pulled into the center; the other two are pushed out.

Now, if you attach wires with the right length-parity (even or odd length) to the end of this gate, only one of them could be true, the other two false (depending if you attach them oddly, you can generalize this a bit). Thus we can connect $3$ values into a $1\text{-in-}3$ CNF clause.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Splitting a Wire

To split a wire, we first line up two wires next to each-other. Next, as a visual aid, we label each of the wires with two ${\mathcal T}{\star}$ squares, one next to the other. This will allow us to see when the wire is "true": when the two ${\mathcal T}{\star}$ squares of a wire in a single tile, then it will be true, otherwise false. Each wire should get its own pair of ${\mathcal T}{\star}$ pairs, so we'll name one pair ${\mathcal T}_1{\star}$ and the other ${\mathcal T_2}{\star}$. Then we introduce three new named-unique $\star$ values, $a{\star},b{\star},c{\star}$. We will place these three next to each-other, once on each wire. However, on one wire, keep a single $\star$ squares between the $a{\star},b{\star},c{\star}$ squares and the ${\mathcal T}{\star}$ pair. On the other wire, put two $\star$ squares between the $a{\star},b{\star},c{\star}$ squares.

Illustration below, description from left to right:

Wire layout. Note the walls are a bit thick, so the wires are drawn closer together for illustration purposes; in reality, they are a bit farther apart.
The square-values; the ${\mathcal T}{\star}$ values on top, and the split-connectors $a{\star},b{\star},c{\star}$ beneath.

What this does is force the wires not to be different; if $a{\star},b{\star}$ is tiled on one wire, then the second wire cannot be off-by-one, because then that would imply $a{\star},b{\star}$ is tiled on the second wire, and thus $a{\star},b{\star}$ would be tiled twice. Illustration below, description from left to right:

Example state of the left wire, valued as true.
Bad state of the second wire; it tries to be differently valued, but then it gets a duplicate pair.
Good state of the second wire, now they are the same value, and there are no duplicate pairs.

If you play around with the other two possible states, you will see this extends to those as well, and it works both ways. Thus these two wires are now the same; we have successfully split a wire. We can split the wire as many times as we like, each time using a new set of $a{\star},b{\star},c{\star}$.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

A Cordless Wire!

Well, to my delight, splitting a wire turned out to be cordless! That is, in the illustrations above, I lay the wires next to each-other, but there is no reason to! We can place the wires anywhere on the grid, and they'd still be "entangled" so-to-speak. This saves us a lot of trouble:

We don't even have to worry about crossing wires. This lets us reduce from non-planar variants of ${\rm\mathbf{3\text{-} S{\small AT}}}$
We have to do any annoying layout, getting the wires to their locations, it is easy! Like a cordless phone! Freedom!
We don't have to worry about wire-length parity/off-by-one layout.
We can make pretty minimally sized reduction; the variables will each get a single set of long wire strips, with a lot of cordless connections along the wires. These connections will be to clause-gates, which will reside in its own location on the grid. The clause will now only consist of the clause gadget and three cordless wires sticking out of it.

Remaining limitations are:

We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

The Reduction, first attempt

Let $\Phi(\mathbf x)= \bigwedge_i C_i$ be a $1\text{-in-}3\text{-}{\rm S{\small AT}}$ boolean formula.

For each $x_j \in \mathbf x$, lay-out a single long wire, in rows, near the bottom of the grid.
For each $C_i \in \Phi(\mathbf x)$, make a clause-gate at the top of the grid; you can lay them out however you like; best fill it up in a square area, but you can lay it out in a single long row as well.
For each $x_j$ variable participating in a clause $C_i$, place a cordless-wire at one of the $3$ wire-pins of the clause gate; place the other $a{\star},b{\star},c{\star}$ of each connection onto the corresponding variable wire/row. Negated terms should just place the cordless connection to the clause a distance of one farther away, changing the wire-length-parity, and negating the value.

What it might look like:

Figure: A clause, directly connected to cordless wires. "Hotspots" are the way we symbolize the $a{\star},b{\star},c{\star}$ from here on. These hotpots will each be connected to the variables in the grid.

And here is what the grid might look like:

Figure: The resulting game-board. The variables are lined up in rows on the bottom. The clauses are spread out across the top. This layout gives quadratic blowup; a smarter layout can avoid quadratic blowup.

Last Minute Details

Recall the decision problem:

  Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But our reduction requires a lot of unique variables, much more than $\mathcal O(n)$. There are several ways to solve this issue.

One way, is to square the size of the grid in both axes. So now our $\mathcal O\left(|\mathbf x|\times \left|\Phi(\mathbf x)\right|\right)$ grid is merely $\in \mathcal O\left(n\right)$, which means all of our unique numbers can be bounded by $n$. Then, we must fill up the rest of the grid, reusing our unique numbers, but being very careful not to place any numbers that our adjacent to each-other in our grid, adjacent to each-other in the filler-space of the rest of the grid. There are several creative ways to do this, I'll leave that as an exercise. This method induces an additional quadratic blowup, obviously.
Another, more succinct, more complex way, is to diversify the $\mathbf 1$ block. Instead of just one building block, we can use $\mathcal O(n)$ building blocks, and then we can reuse the numbers they pair with. This method allows us to avoid quadtratic blowup.

Graph sources

Dominosa.Part.I.tex (writelatex)
Dominosa.Part.II.tex (writelatex)
Dominosa.Part.III.tex (writelatex)
Dominosa.Part.IV.tex (writelatex)


Is there a way to check if a path in a graph is infinite? Edit: Maybe this is not the best title, so few free to change it.

So I'm trying to prove the following statement:

  A finitely branching tree $T$ with infinitely many vertices must have an infinite path.

My proof is loosely like this:

$P = \emptyset$
Start at the root $v_0$
Since there are infinitely many vertices, there must be some vertice
with infinitely successors.

Order the successors of $v_0$ (there is a finite number of them), with the vertices with infinite successors to the left.

$P = P \cup \{v_0\}$

Select $v_1$ as the new root and repeat (3).

What bothers me the most is that I didn't manage to find a deterministic way to do step (3), at first I though BFS would work, since it's complete it would eventually visit all vertices at height $n$ and I could use this to construct an arbitrarily long path $P_n$, however arbitrarily long and infinite are two different things.

You will not find an algorithm to do what you want. As you indirectly suggest, an algorithm can only check a finite prefix of any path.  You can't even use the process of elimination as there may be multiple infinite paths. (If there was only one, you could eventually rule out all the other finite paths.)

As you are probably aware, this is (a corollary of) König's lemma.  What you are asking for is essentially a constructive proof of it which doesn't exist.  The typical (classical) proof repeatedly uses double negation elimination in the form: if no child has an infinite (simple) path then the subtree has a finite number of vertices, this is a contradiction thus there must be some vertex that has an infinite number of descendants. There is not, in general, a computable function to pick out this vertex though.  Knowing that it must "exist" doesn't mean we have any way of calculating it.


Discrepancy between heads and tails Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show that $E[H_i]=\Theta ( \sqrt{i} )$ and $E[H]=\Theta( \sqrt{n} )$.

This problem appears in the first chapter of `Randomized algorithms' by Raghavan and Motwani, so perhaps there is an elementary proof of the above statement. I'm unable to solve it, so I would appreciate any help.

Your coin flips form a one-dimensional random walk $X_0,X_1,\ldots$ starting at $X_0 = 0$, with $X_{i+1} = X_i \pm 1$, each of the options with probability $1/2$. Now $H_i = |X_i|$ and so $H_i^2 = X_i^2$. It is easy to calculate $E[X_i^2] = i$ (this is just the variance), and so $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ from convexity. We also know that $X_i$ is distributed roughly normal with zero mean and variance $i$, and so you can calculate $E[H_i] \approx \sqrt{(2/\pi)i}$.

As for $E[\max_{i \leq n} H_i]$, we have the law of the iterated logarithm, which (perhaps) leads us to expect something slightly larger than $\sqrt{n}$. If you are good with an upper bound of $\tilde{O}(\sqrt{n})$, you can use a large deviation bound for each $X_i$ and then the union bound, though that ignores the fact that the $X_i$ are related.

Edit: As it happens, $\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$ due to the reflection principle, see this question. So
$$
\begin{align*}
E[\max_{i \leq n} X_i] &= \sum_{k \geq 0} k(\Pr[X_n = k] + \Pr[X_n = k+1]) \\
&= \sum_{k \geq 1} (2k-1) \Pr[X_n = k] \\ &=
\sum_{k \geq 1} 2k \Pr[X_n = k] - \frac{1}{2} + \frac{1}{2}\Pr[X_n = 0] \\ &= E[H_n] + \Theta(1),
\end{align*}
$$
since $\Pr[H_n = k] = \Pr[X_n = k] + \Pr[X_n = -k] = 2\Pr[X_n = k]$. Now
$$ \frac{\max_{i \leq n} X_i + \max_{i \leq n} (-X_i)}{2} \leq \max_{i \leq n} H_i \leq \max_{i \leq n} X_i + \max_{i \leq n} (-X_i), $$
and therefore $E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$. The other direction is similar.


is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$ $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$

Alphabet = { a , b }*

Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a machine or grammar which accepts this?

This is a classical example of a context-free language whose complement is not context-free. It is context-free since every word in $w$ has the form
$$ \Sigma^i a \Sigma^j \Sigma^i b \Sigma^j = \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j $$
or the similar form with the locations of $a$ and $b$ switched.


The operator $A(L)= \{w \mid ww \in L\}$ Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ wouldn't be CFL.

Does anyone have an idea for such a language?

As an amplification of sdcvvc's hint:  You can find a context-free language $L$ such that $A(L) = \{a^m b^m c^m \mid m\geq 0\}$, which as you probably know is not context-free.

So we want to find $L$ such that if $ww\in L$, then $w$ has the form $a^m b^m c^m$.  We might as well have $L$ be a sublanguage of $a^*b^*c^*a^*b^*c^*$.  Now we just need to put enough restrictions on the words in $L$ so that words of the form $ww$ in $L$ will have the form we require, while ensuring $L$ is still context-free.

Partial spoiler:

  A word $a^{m_1} b^{m_2} c^{m_3} a^{m_4} b^{m_5} c^{m_6}$ has the form $ww$ if and only if $m_1 = m_4$, $m_2 = m_5$ and $m_3 = m_6$.  Now we can add some restrictions on the $m_i$ for words in $L$ to force them to all be equal in words of the form $ww$.  (Hint: we can require $m_1 = m_2$, but then we can't require $m_1 = m_3$ or $m_2 = m_3$, because then $L$ wouldn't be context-free anymore.  This isn't a problem though, because we can make use of some of the equalities we already have between the $m_i$.)


Maximize distance between k nodes in a graph I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance.  In other words they have to be spread around the graph as possible.

Let $d(u,v)$ be the length of a shortest path between $u$ and $v$ in $G$.  Now, for a set of vertices $X \subseteq V(G)$, define
$$d(X) = \sum_{\{u,v\} \subseteq X}d(u,v).$$

Let the problem SCATTERED SET be the problem which on input $G,k$ asks to find a set of $k$ vertices $X$ maximizing $d(X)$.

  Is there an efficient algorithm solving SCATTERED SET?

No, the problem is NP-complete.

Let $(G,k)$ be an instance of INDEPENDENT SET.  Construct $G'$ by adding a universal vertex $u$ to $G$.  The crucial observation is that the distance between two vertices in $G$ is 1 in $G'$ if and only if they are adjacent in $G$, and 2 otherwise.

Now, the optimal solution of SCATTERED SET on input $(G',k)$ is $2\binom{k}{2}$ if and only if $G$ has an independent set of size $k$.


Clustered Regions by Each Neuron in Self Organizing Map (SOM) I was given a question about SOM.

There is a SOM which have 4x4 neurons and each neuron's x1 and x2 values (coordinates) given. Also neighborhood function and weight update rule given. How can i find and show the regions which are clustered by each neuron?

Thanks for answers.

Regards...

When clustering an input, one should calculate the Euclidean distance to all neurons, then the input is assign to the cluster of the nearest neuron.

In other words, for an input $v$ and a set of neurons $N$ (in your case $|N| = 16$ ) the cluster is:

$\text{Cluster}(v)=\arg \min_{i\in A}(||w_i-v||_2)$


How to solve recurrences with transcendental terms? Problem:

  A number is said to be a magic number, if the sum of its digits, taken again and again till it becomes a single digit number, is 1.
  Example: $289 => 19 => 10 => 1 => 289$ is a magic number
  but, $20 => 2 =>$ not a magic number.

So the simple algorithm is to keep doing the digit sums till we reach a single digit number. I tried to calculate the time complexity of this algorithm, and came up with the following recurrence:

$$T(n) = T(lg\ n) + O(1)$$

Let us say we have a number $N$ to test for magic number. The number of digits in this number is $O(lg\ n)$, so the sum of its digits is at most $9*lg\ n$ which is $O(lg\ n)$. So we have one smaller subproblem of size $lg\ n$ and some constant work to return data.

How do I solve this recurrence? The answer would be, ostensibly, the number of times I have to take $log $ of a number to get to 1. Is there a direct equation for this?

The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant.

(Confusingly, in information theory the same notation is used for the function $\log + \log\log + \log\log\log + \cdots$.)


Raptor Algorithm: Differences between trip and route I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). In this algorithm, there are some definitions that I don't understand:

About trip:

  trip represents a sequence of stops a specific vehicle (train, bus,
  subway, . . . ) visits along a line

About route:

  Each route consists of the trips that share the same sequence of
  stops.

So, if I understand, trip means a "bus route" and a route is collection of trips to make a path? If my guess is true, why does it state:

  Typically there are more routes than trips

And if a route is just a collection of trips, how can I build all routes?

Trip represents a sequence of stops plus associated arrival and departure times on each stop.

Group all trips by their sequence of stops, ignoring the time information, then each group of trips sharing the same sequence of stops forms a route.

eg. for air traveling, each flight is a trip, while each airline is a route, grouping all flights flying on the same airline.

What I saw in the paper is

  Typically, there are many more trips than routes.

Which is obvious since there is an one-to-many mapping between route and trips.


Get count of longest zigzag sub-sequences I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to obtain that?

Extending the well-known dynamic programming algorithm for Longest Common Subsesequence, we have a poly-time algorithm for Longest Zig-zag Subsequence.

When DPing, just also add another parameter: $\mathrm{A}[\mathrm{i}][\mathrm{j}]$ is the length of the longest zig-zag sequence ending at position $i$ and it is increasing when it ends at $i$ if $j = 0$ and otherwise, decreasing when it ends at $i$ if $j = 1$. So, at a position $i$, you scan from $1$ to $i-1$ and update $\mathrm{A}[\mathrm{i}][\mathrm{0}]$ and $\mathrm{A}[\mathrm{i}][\mathrm{1}]$ gradually. Note that you need to make the $\mathrm{j}$-index alternate while updating.


Master theorem not applicable? Given the following recursive equation

$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that

$$ n^{\log_2(2)} = n.$$

Now we check the first two cases for $\varepsilon > 0$, that is whether

$n\log n \in O(n^{1-\varepsilon})$ or
$n\log n \in \Theta(n)$.

The two cases are not satisfied. So we have to check the third case, that is whether

$n\log n \in \Omega(n^{1+\varepsilon})$ .

I think the third condition is not satisfied either. But why? And what would be a good explanation for why the Master theorem cannot be applied in this case?

The three cases of the Master Theorem that you refer to are proved in the Introduction to Algorithms by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).

It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\varepsilon}$ for any $\varepsilon > 0$.

However the theorem can be generalized to cover this recurrence. Consider

Case 2A:
Consider $f(n) = \Theta (n^{\log_b a }\log_b^k n)$ for some $k\geq 0$.

This case reduces to Case 2 when $k = 0$. It is intuitively clear that along each branch of the recurrence tree $f(x)$ is being added $\Theta (\log_b n)$ times. A sketch of a more formal proof can be found below. The final result is that

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$.

In the Introduction to algorithms this statement is left as an exercise.

Applying this statement to the recurrence in question we finally get

$$
    T(n) = \Theta(n \cdot \log^2 n).
$$

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

$$
   \lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}
$$

for any functions $f(x)$ and $g(x)$ differentiable in the vicinity of $c$. Applying this to $f(n) = n \log n$ and $g(n) = n^{1+\varepsilon}$ one can show that $\log n \not\in \Theta (n^{1+\varepsilon}).$

Sketch of the Proof of the Master Theorem for Case 2A.

This is a reproduction of parts of the proof from Introduction to Algorithms with the necessary modifications.

First we prove the following Lemma.

Lemma A:

Consider a function

$$
 g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)
$$

where $h(n) = n^{\log_b a} \log_b^k n.$ Then
$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Proof:
Substituting the $h(n)$ into the expression for $g(n)$ one can get
$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}}  \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

If $n$ is an exact power of $b$ given a recurrence

$$
 T(n) = a T(n/b) + f(n),\quad  T(1) = \Theta(1)
$$

one can rewrite it as

$$
 T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j f(n/b^j).
$$

Substituting $f(n)$ with $\Theta(n^{\log_b a} \log_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.


Are there any algorithms that run in (2 ↑ ↑ n)? I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation.

Required: Use more than one up-arrow for time complexity.

Bonus points:

Have the algorithm be useful.
Have the algorithm be useful and optimized

Yes! A simple automaton-based algorithm for answering first-order queries in Presburger arithmetic (and some extensions) has worst-case running time about $2 \uparrow\uparrow n$, where $n$ is the number of quantifier alternations in the query.   Despite this formidable worst-case running time the algorithm has been implemented and gives useful results (see Hamoon Mousavi's implementation here).


Number of final states in a minimal DFA Is the number of final states in a DFA at least the number of final states in its minimal DFA?

Is the answer even yes? Any help would be appreciated.

Yes, the number of final states in a DFA is at least the number of final states in its minimal DFA. Your proof is correct at some level of formality.

Intuitively, as you have noticed, any DFA for $L$ can be reduced to the minimal DFA for $L$ by merging states, which must merge any final states to a final state.

Here is how to make your proof mathematically more formal. Let $L$ be a language over $\Sigma$ and $D=(Q,\Sigma,\delta,s,F)$ be a DFA that accepts $L$. Let $M$ be the set of Myhill-Nerode equivalence classes with respect to $L$.

Define a map $m:Q\to M$ such that $m(q)=[w]$, where $w$ is any input that will drive $D$ to state $q$ and $[w]$ is the Myhill-Nerode equivalence class that contains $w$. We can verify that $m$ is well-defined, i.e., $[w_1]=[w_2]$ if both $w_1$ and $w_2$ drive $D$ to $q$.

We can verify or recall the following claims, thus completing this proof.

$m$ maps a final state in $D$ to a Myhill-Nerode equivalence class that contains a word in $L$.
all final states in the minimal DFA of $L$ are in one-to-one correspondence to all Myhill-Nerode equivalence classes that contain a word in $L$.

Here is a simple related exercise.

Exercise. The number of non-final states in a DFA is at least the number of non-final states in its minimal DFA.


log(n) complexity. Difficulty understanding example So, I am revisiting complexity analysis.

Here's the example: the instructor reduced an algorithm to:

n*(1 + 1/2 + 1/3 + ... + 1/n), and I can't seem to grasp why the part in parentheses is log(n).

Do you know the Harmonic series (wiki)?

$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = 1 + \sum_{i=2}^{n} \frac{1}{i} \le 1 + \int_{1}^{n} \frac{1}{x} \text{d}x = 1 + \ln n = \Theta(\log n).$$

Similarly, we also have
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum_{i=1}^{n} \frac{1}{i} \ge \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Theta(\log n).$$

The formula above follows from

$$\int_{a}^{b+1} f(x) \text{d}x \le \sum_{i=a}^{b} f(i) \le \int_{a-1}^{b} f(x) \text{d}x$$

when $f(x)$ is non-increasing.


Recognizably turing machine question (reject / loop) The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?

Give a deterministic TM D that recognizes L such that if $w \in L$ then D accepts w. Or if $w \notin L$, then D does not accept $w$. I realized this definition states on whether D accepts a $w$ like

$A_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ accepts some string that ends with 111$\}$, which is recognizable and easy to prove through dovetailing.

Now how about

$R_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ reject some string that ends with 111$\}$?  Is this also recognizable and would the proof be the same as the one above ? I think this will work but what about

$L_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ loops on some string that ends with 111$\}$?

How do you check if something loops?

As commented by dkaeae, there is no way to verify whether a general Turing machine (TM) loops forever on some input. No matter how many operations has been run by an algorithm that simulates the TM on that input, that algorithm cannot be sure the TM will loop forever. The TM may or may not stop at the next moment.

The intuition is pretty simple. The only way to know the behavior of a TM on some input is to run it, unless there are some extra information or restriction about the TM that we can take advantage of, such as only finitely many cells are used.

We can recognize all Turing machines that accepts some string that ends with 111 since we can list all such strings and we can use an universal TM to simulate all Turing machines on all such strings sort of in parallel, thanks to dovetailing. Ditto with the case of rejecting.

However, a simulation cannot be finished if the TM keeps running. There is no point of time that an algorithm can be sure that the Turing machine (TM) under inspection will loop forever. Even if it looks like the simulated TM will never stop, it might halt at the next moment. The very fact that it keeps running prevents us from making a foolproof decision on whether it will eventually halt or loop forever. So we should believe that $L_{*111}$ is not recognizable. In fact, we should believe the simpler language $L_{111} = \{\langle M \rangle \mid M$ is a TM that loop on $111\}$ is not recognizable either.

Of course, we still need a rigorous proof that shows neither $L_{*111}$ nor $L_{111}$ is recognizable. We can make a reduction from the known unrecognizable language $\overline{HALT}=\{\langle M \rangle \mid M$ is a TM that does not halt on the empty string$\}$ to both of them.


Understanding x64 and x86 OS with 64bit cpu Kinda stupid question, but makes me a bit confused. If my OS (Win 7) is 64-bit type system and my CPU is 64-bit, why Program Files directory is marked (x86), x86 stands for 32-bit OS?

You should notice there are two directories for your program files. For the directory with the suffix x86 it contains the programs which are based on 32-bit addresses. Any program which is made to produce 32-bit addresses is compatible with 64-bit architecture but not vice-versa. The OS installs the programs based on 32-bit addresses in the x86 directory.


Is the program in secondary memory can be a process? Let us consider the following scenario,

The cpu started executing a program, which is in secondary memory with n lines of code, so, it brings m ( <  n ) lines of code in to main memory and started executing.

We can call the m lines of code, which are in main memory as process.

But my doubt is that, what about the remaining n-m lines of code that are in secondary memory, which are not yet reached main memory, can we call them process? or just program? The remaining n-m lines may execute by the CPU in future. But what now the n-m lines of code are?

A process is a technical term that has a well-defined meaning.  You can't just re-define standard terms that have an accepted meaning... or if you do, you should expect it to cause confusion.  My advice is to stick with the standard meaning of this term, and read an operating system textbook to learn what is the accepted notion of a "process".

Wikipedia defines a process as "an instance of a computer program that is being executed".  A process is not some set of lines of code.  A program contains a bunch of machine-level instructions.  (Those machine-level instructions are typically obtained by compiling some source code.)  A process is then a running instance of a program.  The process typically is comprised of multiple resources: some memory (in particular, a region of virtual memory), one or more threads of execution, and some operating system state that is specific to the particular process.

So, no, you can't call "the set of lines of code in secondary memory" a process -- that's not what a process is.  Similarly, when you write "We can call the m lines of code, which are in main memory as process.", my reaction is: no, you can't -- that's not what a process is.


How do we construct reductions for NP-Completeness I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the independent set problem is NP-complete.

In this case, do we start with an instance of the vertex cover problem and show how we can transform this instance into an instance of the independent set problem? Or, do we start with an instance of the independent set problem and transform it into an instance of the vertex cover problem?

I understand the relationship between vertex cover and independent set, however, I am confused on the direction of reduction.

You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a subroutine of Independent set to solve Vertex cover. This does not say anything, as there might be a better way to solve vertex cover and does not show anything.


What is $Prop$ in the calculus of constructions? I'm looking at the Calculus of Constructions and its place in the Lambda Cube.

If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the simply-typed calculus, $\lambda_\to$. The first axis adds type-to-term operators, the second type-to-type operators, and the third dependent typing, or term-to-type operators. The CoC has all three.

However, the CoC introduces a term $Prop$, and states that $Prop : Type$ by the inference rules,
but is otherwise not used.
I understand that it is for the eponymous propositions, but the logical propositions are not defined in terms of it.

Could you explain to me what $Prop$ is for, where/when it appears, and explain it in terms of the cube's axes (if indeed it is possible to do so)?

In traditional Martin-Löf type theory there is no distinction between types and propositions. This goes under the slogan "propositions as types". But there are sometimes reasons for distinguishing them. CoC does precisely that.

There are many variants of CoC, but most would have
$$\mathsf{Prop} : \mathsf{Type}$$
but not $\mathsf{Type} : \mathsf{Prop}$. Another difference shows up when we have infinitely many type universes and make $\mathsf{Prop}$ impredicative (this is what Coq does). Concretely, consider a variant of CoC where we have $\mathsf{Prop}$ and infinitely many type universes $\mathsf{Type}_1$, $\mathsf{Type}_2$, $\mathsf{Type}_3$ with
\begin{align*}
\mathsf{Prop} &: \mathsf{Type}_1 \\
\mathsf{Type}_1 &: \mathsf{Type}_2 \\
\mathsf{Type}_2 &: \mathsf{Type}_3 \\
&\vdots
\end{align*}
The formation rule for $\prod$ has to explain how to form $\prod_{x : A} B(x)$ when $A$ is either a proposition or a type, and $B(x)$ is either a proposition or a type. There are four combinations:

$$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
$$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Type}_i}
     {\prod_{x : A} B(x) : \mathsf{Type}_i}$$
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Type}_j}
     {\prod_{x : A} B(x) : \mathsf{Type}_{\max(i,j)}}$$

The most interesting is the difference between the second and the fourth case. The fourth rules says that if $A$ is in the $i$-th universe and $B(x)$ is in the $j$-th universe, then the product is in the $\max(i,j)$-th universe. But the second rule is telling us that $\mathsf{Prop}$ is not just "one more universe at the bottom", because $\prod_{x : A} B(x)$ lands in $\mathsf{Prop}$ as soon as $B(x)$ does, no matter how big $A$ is. This is impredicative because it allows us to define elements of $\mathsf{Prop}$ by quantifying over $\mathsf{Prop}$ itself.

A concrete example would be
$$\prod_{A : \mathsf{Type}_1} A \to A$$
versus
$$\prod_{A : \mathsf{Prop}} A \to A$$
The first product lives in $\mathsf{Type}_2$, but the second one is in $\mathsf{Prop}$ (and not in $\mathsf{Type}_1$, even though we are quantifying over an element of $\mathsf{Type}_1$). In particular, this means that one of the possible values for $A$ is $\prod_{A : \mathsf{Prop}} A \to A$ itself.


Determine deadline for periodic task that enter ready queue in RTOS I am currently trying to optimise the scheduler of FreeRTOS and in general Real-Time Operating Systems as a Project.

In FreeRTOS, and I suspect other RTOS as well, we don't specify the deadline for the tasks, not to mention the tasks would mostly be periodic.

How can we, if possible, generate the deadline for them?

Maybe a constant added to the time task reached the ready queue? Where the constant depends on the priority.

How should I go about it? Looking for suggestions...

In short, how can we implement something like Earliest Deadline First?

I am actually trying to implement Ant Colony Optimisation.

Edit: In FreeRTOS the API of OS doesn't need deadline to create Task, only Priority can be set.

You can't generate a deadline from nothing. That doesn't make sense.

Some tasks must be completed by a certain time, or they are useless.  Only the programmer who writes the task knows whether this is the case, and if so, knows when they have to be completed by.  That's not something that the OS can infer, because it depends on what the task is doing and why.

For instance, a task that adjust the jet engine's power level in response to pilot commands might need to respond rapidly to make sure that safety requirements are met.  However, a task that displays frames of a movie on the passenger's entertainment system is probably less critical; if the next frame of video doesn't get displayed or is delayed, there's no great harm done.  The OS cannot distinguish those two cases.  Only the software developer can.

Therefore, in a real-time OS that tries to meet task deadlines, the deadlines come from the software developer.

For periodic tasks, we might not have a fixed deadline, but we might have requirements on how often they run (e.g., must occur at least two times per second).


Optimizing hash table for common subset of keys? Are there variants of hash tables that take advantage of the likely distribution of key values? For example, if I'm using utf-8 encoded unicode strings as identifiers in a compiler but expect the majority of them to fit into ASCII, can I optimize for that use case?

Yes, it's sometimes possible to optimize hash tables based on expected key values (i.e. make certain classes of keys at the expense of other classes). But I don't see how there could be one in your case.

There are two ways to potentially make hash tables faster: use a hash function with fewer collisions, and use a hash functions that's faster to calculate. But they pull in opposite directions: you can either make the hash function faster or better, not both.

Hash functions are designed to spread out likely key values in the first place. So if you have “typical” input, there's nothing to be gained here.

For example, if you're making exact string comparisons, then the fact that the strings are encoded in UTF-8 doesn't affect the way the hashes are calculated. The hash function looks at all the bytes of the string anyway, and has a low probability of collisions except for specially-crafted data. A hash function specialized to pure-ASCII strings won't be faster to calculate (operations are on bytes anyway, even on words, not on individual bits) nor have more collisions (repeated bit patterns like “all upper bits are 0” is something typical hash functions are designed to cope with).

An example where you can gain performance for typical cases is when the key for the hash table is a large data structure, such that there's a gain to be made by hashing only part of the data structure. Say the key consists of both a name and some large extra data, and most keys have different names, but occasionally there are distinct keys with the same name. Then you might use a two-level table: first hash on the key, and then, only in buckets where there is more than one entry, calculate the hash of the extra data.

In the case of a string, the closest thing would be to hash only a prefix. But that typically gives bad results in practice; for example, in a compiler, it's very common to have large sets of identifiers with a common prefix.

Another case where a simpler, partial hash function can be useful is when equality between keys is hard to test. This may be the case with Unicode strings if you need to treat different representations of the same text as equal, e.g. treat combining characters as equivalent to non-canonical forms. In this case, you may want to avoid doing the work of normalizing each string. However that wouldn't help for the pure-ASCII case, since normalizing a pure-ASCII string is easy. It might help with typical “tame” uses of Unicode (sticking to characters that are common in one language).

A hash table is not necessarily the best structure to represent a mapping from keys to values. Search trees or tries have many advantages. Balanced search trees have guaranteed $O(\lg(n))$ behavior, whereas hash tables are harder to protect against deliberately-crafted key sets (not so much an issue in compilers, but it can be an issue when interpreting code from an untrusted source, e.g. a web browser running Javascript code from some random website). Hash tables are pretty much impossible to share intelligently — you have to copy the whole table. With trees, on the other hand, sharing comes naturally. Sharing is very often useful in compilers, between scopes that differ only on a few identifiers.


What sort of theoretical machine would be needed to solve the tiling problem? So theoretically, what sort of machine would we need to solve the tiling problem?

(Given a set of tiles, decide if they will tile the plane or not.)

I know we could have a Turing machine plus a "tiling oracle", but do we know what, specifically a Turing machine isn't able to do that keeps us from being able to compute the answer?

According to Wikipedia, the halting problem reduces to the tiling problem. This means that one thing that prevents Turing machines from solving the tiling problem is their inability of deciding whether a given procedure ever halts. The tiling problem might be even more difficult that the halting problem, but unfortunately I wasn't able to confirm or disprove this.


Predicate variant of Assignment Problem Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that
\begin{align}
\forall p \in P \; p(f(p))
\end{align}
It seems like a special case of having a weight matrix $W$ where $w_{ij}=0$ if $P_i(T_j)$ and otherwise $1$, and then solving the general Assignment Problem.
For practical reasons calculating such a weight matrix up front is not desirable, as evaluating $p$ is not necessarily cheap.
I have also thought about whether it could be formulated as some variant of Stable Marriage Problem, where the men have a predicate that needs to satisfied instead of a ranked preference list over all women.
I don't think the proposed problem sounds very exotic, so I might just be looking in a wrong direction.

Your problem is known as bipartite perfect matching. Unfortunately, the query complexity of your problem is $n^2$ (where $n = |P| = |E|$), that is, in the worst case you might need to make a lot of queries of the form $p(e)$. The complexity remains $n^2$ even if you are allowed XOR queries, and remains $\Omega(n^2)$ even if you are allowed AND queries, or if you are allowed OR queries. See Gal Beniamini and Noam Nisan, Bipartite Perfect Matching as a Real Polynomial.


A query about Complexity Class $NC$ Given a polynomial circuit consisting of only $AND$ and $OR$ gates. Is it true that any such circuit is easily parallelizable i.e. it belongs to the complexity class $NC$?

I think this is the case but I can't find a source confirming it.

The complexity class $\mathsf{NC}$ is a uniform class. There are constant size circuits which don't belong to $\mathsf{NC}$.

What does that mean? Most circuit complexity classes don't really make sense for individual circuits. A single circuit can't have polynomial size, or rather, this doesn't mean anything (every circuit has size at most $n^k$ for some $k$). Instead, when talking about a circuit belong to a complexity class, we are really talking about sequences of circuits. These sequences can be uniform – that is, can be generated by a Turing machine – or arbitrary. (In the uniform case, you can get different complexity classes by constraining the strength of the Turing machine.)

The complexity class $\mathsf{NC}$ consists of uniform circuits of polynomial size and polylogarithmic depth. Consider the following sequence of circuits: $C_n$ (with $n$ inputs) is either the constant 0 or the constant 1, depending on whether the $n$th Turing machine halts on the empty input. This sequence doesn't belong to $\mathsf{NC}$ (since it's not even computable), but all circuits have constant size.

In order to compare $\mathsf{NC}$ and polynomial size circuits, you have two options. Either you compare $\mathsf{NC}$ to $\mathsf{P}$, which is the uniform analog of polynomial size circuits, or you compare non-uniform $\mathsf{NC}$ to polynomial size circuits (a complexity class known as $\mathsf{P/poly}$). In both cases, it is conjectured that the two classes are different, but this hasn't been proved yet.

One way of separating $\mathsf{NC}$ from $\mathsf{P}$ would be to separate non-uniform $\mathsf{NC}$ from $\mathsf{P}$, that is, to give an example of a problem in $\mathsf{P}$ (say, some $\mathsf{P}$-complete problem) that cannot be solved using $\mathsf{NC}$-circuits. In the same way, you could prove that $\mathsf{P} \neq \mathsf{NP}$ by showing that $\mathsf{SAT}$ doesn't have polynomial size circuits. In both cases, you are actually trying to prove stronger claims, which are believed to hold.


Exercise: Sliding window protocol: Bits for sequence number This is a task in a lecture on computer networks:

"Suppose you are designing a sliding window protocol for a 1-Mbps point-to-point link to the moon, which has a one-way latency of 1.25 seconds. Assuming that each frame carries 1 KB of data, what is the minimum number of bits you need for the sequence number?"

R = 1-Mbps = 125KBps

d_prop = 1.25 sec  so I assume RTT = 2.5 sec

The solution I was given ignores the transmission delay but I calculated it to be

d_trans = 1KB/125KBps = 0.008s

Within one second you can put 125 frames into the link if you allow full utilization.
I assume the task ignores the size of the acknowledgements as well as the processing and transmission delay of the receiver for simplicity.
Nothing else is said about the links properties.

Since within 1 second you could send 125 frames, within 2.5 seconds you could send. 312.5 frames. If we include the senders d_trans then within 2.508 seconds we could send frames 313.5 frames until the acknowledgement for the first frame should be received. If you complete the LastFrameSent then I think you should need a send_window_size(SWS) of 314 to acknowledge each frame individually.
In this case you would need Ceil(log2(314)) = 9 bits for the sequence numbers.

The solution given by the tutor says that you need at least 10 bits and part of the explanation I noted down is that (ignoring d_trans) you can send 312 frames until the first frame is received. And then you can supposedly send another 312 frames until you receive the first ACK back, so you'd need a SWS of 624.

So did I misunderstand anything about the task or did the tutor make an error by doubling the one-way-latency (which I assume to be the same as d_prop) twice?
Can additionals assumptions be made regarding the properties of the link?

I saw a similar question where the link was considered the be a full-duplex link (which wasn't explained in the lecture iirc). But even if you'd consider a full-duplex link which means only the half of the bandwidth may be used then you could only send ~156 frames until you get the ACK and then you'd need 8 bits instead of 10, right?

Thank you for your help.

Assuming SWS(sender window size) = RWS(receiver window size)

In this case Assume a scenario where SWS = RWS = 3 so MaxSeqNum = SWS - 1 = 2

LAF(Last Acknowledged frame)
LFS(Last Frame Sent)

Sender = { [ 0, 1, 2 ], 0, 1, 2, 0, 1, 2}

Note:
Sequence of packets waiting on the queue.
Square bracket represent the window

Receiver = {0, 1, 2, [0, 1, 2], 0, 1, 2}

Here the packets 0, 1, 2 are obtained and window is moved further acks sent by the receiver.

but acks are lost in traffic.

So the sender didnt got the acks thinks that the packets have lost and sends the
first window packets with sequence numbers 0, 1, 2. In this case the packets received are actually not distinguished by the receiver.


Order of growth definition from Reynolds & Tymann I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines).

The second chapter introduces algorithms with an example of a sequential search which simply iterates through a list of names and returns TRUE if a given name is found in the list.

The author goes on to say (page 17):

  We say that the "order of growth" of the sequential search algorithm
  is n. The notation for this is T(n). We also say that an algorithm whose order of growth is within some constant factor
  of T(n) has a theta of NL say. "The sequential search has a theta of
  n." The size of the problem is n, the length of the list being
  searched.

I find this really hard to follow. The book is riddled with errors, so I am not sure if I am missing something or if the there is a typo in the paragraph above. In general English I rarely see any sentence end with "...say".

I am very confused.

What does T stand for? The book does not explain. Is it for Time or for Theta?

If "a theta of NL" means "The sequential search has a theta of n." What does L stand for? 'Linear' or 'length'?

I have written to the publishers asking for an explanation. They said they would forward my message to authors. They have not replied. I have also tried looking at other sources but I still get the naggling feeling that I am misunderstanding something - so cannot rest until I have decoded this paragraph.

If anyone has a copy of that book, and has understood that paragraph. Then, I'd appreciate if you could let me know if that paragraph is accurate or explain it in other words. Thanks.

The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book.

  We say that the "order of growth" of the sequential search algorithm is n. The notation for this is $T(n)$.

No. $T(n)$ is the notation for a function called $T$, which takes an argument called $n$. That function could be used to mean anything whatsoever. There is something of a tradition of writing recurrence relations for the running time of programs in the form, e.g.,
$$\begin{align*}
T(1)&=k\\
T(n)&=T(n-1)+\log n \quad\text{for }n>1
\end{align*}$$
But $T$ is not an "order of growth", here: it is a specific function defined through a recurrence relation. And you cannot just write "$T(n)=\text{blah}$" and expect people to read your mind and know that the function $T$ denotes the running time of some algorithm.  $T$ here stands for time.

  We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of NL say. "The sequential search has a theta of $n$."

This has obviously been mangled. I think the authors intended to write something like,

  We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of $\boldsymbol{n}$ and we say, "The sequential search has a theta of $n$."

But, please, we do not say "has a theta of $n$," just as, if $h$ is your notation for height, you wouldn't say "John has an $h$ of 180cm." It's just not a correct form of words. We actually say, "The running time of the algorithm is theta $n$ (or theta of $n$)." Note in particular, that $\Theta$ is a tool for talking about mathematical functions, not algorithms. Theta doesn't mean that the running time is something; rather, it's something you can use to talk about the running time.

"NL", by the way, denotes the complexity class nondeterministic logspace, which makes no sense at all in the position it appeared in the original quote.


Is C++ considered a language with high or low orthogonality? I'm looking to make a comparison of regularity in languages - specifically orthogonality.
If I were to say Java is weak in terms of orthogonality and Haskell stronger, where would C++ sit and why?

By many standards, Java would not be considered weak in this respect. Java was not one of the first-generation languages. By the time it was developed, quite a few things were known about language design, and the lessons learned do show. For instance, it's pretty easy to parse.
C++ is quite a bit older, as it shares a history with C. As a result, C++ has the a preprocessor language that is quite distinct from the rest of the language. But unlike C, C++ has effectively added a third language. The C++ template system is Turing-complete, and effectively a language of its own. (Although recent C++ versions have reduced this gap).
The result? This bit of valid C++ code:
#define A 0
enum { b = 1};
const int c = 2;
constexpr int d = 3;

But note that this process is a result of the success. The most orthogonal languages are those defined as a theoretical exercise, never used, and therefore never adapted to be useful for a wide range of tasks.


Naive Bayes Intuition I have some difficulties in understanding the intuition behind Naive Bayes Classification.

In general, I do understand every argument of the definition, however I don't understand why it's correct and why any other argument is incorrect.

Start from the beginning:

Goal: $v_{MAP} = argmax_{v_i} p(v_i|a_1...a_n)$

the goal is simply to find the maximum aposteriori of the value of the target function given the set of features Note,  here we don't mention the hypothesis, because we are not interested in hypothesis.

After developing the formula with Bayes formula, we get

$argmax_{v_i} p(v_i)p(a_1...a_n|v_i)$

Now, the trick goes $p(a_1...a_n|v_i)=\prod_{j} p(a_j|v_i)$

The question is why in the very begging, having the formula of

$v_{MAP} = argmax_{v_i} p(v_i|a_1...a_n)$

I cannot apply the trick $p(v_i|a_1...a_n)=\prod_{j} p(v_i|a_j)$

It's just a reverse direction, in addition we don't have to calculate the prior probability of $p(v_i)$, so for me it looks like the better way to go.

What's wrong with my reasoning.

Because in general $p(v_i \mid a_1 \dots a_n) \ne \prod_j p(v_i | a_j)$.  There is no reason to expect that equation to hold with equality.  You can't just write down an equation and hope that it is true; you have to be able to justify it from the axioms of probability, and you can't justify the equation you want to hold.

Remember that $p(A \mid B)$ is not the same as $p(B \mid A)$.  The two probabilities can be very different.  Be careful not to confuse them, or you will definitely get very mixed up.

In general, if $A,B,C$ are events, then $p(A \mid B,C)$ is not necessarily equal to $p(A \mid B) \times p(A \mid C)$.  It is easy to come up with a counter-example.  For instance, suppose I toss a fair die, and define the following events: $A$ = "the die came up 5", $B$ = "the die is showing an odd number", $C$ = "the die is showing a prime number".  Then $p(A \mid B,C) = 1/2$, $p(A \mid B) = 1/3$, $p(A \mid C) = 1/3$, and $1/2 \ne 1/3 \times 1/3$.

The reason why you can write $p(a_1 \dots a_n \mid v_i) = \prod_j p(a_j \mid v_i)$ is because $a_1,a_2,\dots,a_n$ conditionally independent on $v_i$: once $v_i$ is fixed, then $a_1,a_2,\dots,a_n$ become independent.  In general, if $A,B$ are conditionally independent on $C$, then $p(A,B \mid C) = p(A \mid C) \times p(B \mid C)$ -- this is in fact the definition of conditional independence.  That's why $p(a_1 \dots a_n \mid v_i) = \prod_j p(a_j \mid v_i)$ is justified.  (However, no such justification is available for $p(v_i \mid a_1 \dots a_n) \ne \prod_j p(v_i | a_j)$.)

If you are not familiar with the concepts of independence and conditional independence, I suggest reviewing a standard probability textbook, where you can find more on that subject to help you practice and become proficient with those concepts.


PAC learning of axis-aligned rectangles I've been reading the proof that axis-aligned rectangles are PAC learnable from the book Foundations of Machine Learning by Mohri (Proof pt. 1, Proof pt. 2), and a small technical detail stuck out to me.

The proof goes through dividing the target rectangle $R$ to four rectangular regions $r_i$ (Fig 2.3), each having probability at least $\frac{\epsilon}{4}$. It is then claimed that:

If the tightest sample-consistent rectangle $R_S$ (Fig 2.2) meets any of these regions, then the mass of the possible erroneous region $R\setminus R_S$ is bounded by epsilon, which in turn bounds the error probability.
If $R_S$ misses at least one of those rectangles, then we reduce to upper bounding the probability that the number of trials in a geometric random variable with probability $\ge\frac{\epsilon}{4}$ exceeds $m$.

It seems that for the first point, we need to pick $r_i$ such that $\Pr[r_i]\le\frac{\epsilon}{4}$, which means that we must pick the $r_i$'s such that $\Pr[R_i]$ equals exactly $\frac{\epsilon}{4}$. Is this reasoning correct? If so, how can you ensure that $\Pr[r_i] = \epsilon/4$, without assuming something like absolute continuity of our distribution on $\mathbb{R}^2$?

Good question! The proof given in Mohri's book indeed assumes continuity of the distribution, but this can be avoided with a finer definition of the $r_i$'s. Such a correction appears in these lecture notes who cite this paper.

Recall that you want the rectangles to be small enough, such that if $R_S$ intersects all of them, then $R\setminus R_s$ is small enough. Simultaneously, you want the rectangles to have large enough mass such that with high probability you do not miss a rectangle (here you use a simple bound on a geometric random variable as stated in the second point).

Suppose $R=[a,b]\times [c,d]$, and let us focus on $r_1$, the subrectangle having $[a,b]$ as an edge (if we are able to satisfy the above constraints for $r_1$, you can apply a similar construction for the rest of the rectangles). Define $r_1=[a,b]\times[c,c+h]$, where:

$h=\inf\big\{h'\big|\Pr\left[[a,b]\times[c,c+h']\right]\ge \frac{\epsilon}{4}\big\}$.

Note that $\Pr[r_1]\ge\frac{\epsilon}{4}$. To see why, let us assume that $\Pr[R]\ge\epsilon$ (otherwise we are done) and let $[a,b]\times[c,c+h']$ be some rectangle with mass $\ge \epsilon/4$. Now define the sequence of events
$x_i=[a,b]\times[c,c+h+2^{-i}\Delta]$, where $\Delta=h'-h$, and identify the rectangle $x_i$ with the event that a point drawn from our distribution lies inside the rectangle. Now we have:

$\Pr\left[r_1\right]=\Pr\left[\bigcap\limits_{n=1}^\infty x_n\right]=\Pr\left[\lim\limits_{n\rightarrow\infty}x_n\right]=\lim\limits_{n\rightarrow\infty}\Pr[x_n]\ge \frac{\epsilon}{4}$.

To see why the last inequality holds note that the series converges, since it is decreasing and lower bounded by $\frac{\epsilon}{4}$ (by our choice of $h$). See this question for a discussion on the probability of limit events. This shows that you are covered on the second point, and can upper bound the probability that at least one of the rectangles is missed.

It remains to show what we should do in the case that $r_i\cap R_s\neq\emptyset$ for all $i$. We can no longer immediately claim that $\Pr\left[\bigcup\limits_{i}r_i\right]\le\epsilon$, but a more sensitive approach would do the trick. Let us define $r_i'$ to be the interior of the rectangle $r_i$ along with its corresponding edge from $R$. Note that if $R_S\cap r_i\neq\emptyset$ then $R\setminus R_S\subseteq\bigcup\limits_{i}r_i'$ (geometric argument). We can now conclude the proof by showing that $\Pr[r_i']\le\epsilon/4$. You can prove this by a similar approach, define a sequence of events converging to $r_1'$, and use the fact the the probability for each event in the sequence is upper bounded by $\epsilon/4$.


Decision vs Optimization version for Problems of two Parameters Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.

Now the corresponding decision problem $foo(M)$ would be:  Is there a solution to foo with quality at least $M$ of size $k$.

For problems on one parameter (for example vertex cover) it is obvious that solving the optimization problem sovles the decision problem.

But here I do not see such a correspondance between the $k$-foo optimization problem and the $foo(M)$ decision problem. How does for example showing that $foo(M)$ is NP-hard implies that $k$-foo is NP-hard?

The $k$-center problem is an example of such a problem where the decision version takes the radius as input and asks wether a solution of size $k$ exists.

Having more than one input doesn't change anything:

Consider an optimization problem $MinQ$:

  Input: $x, k$
  Output: find $y$ satisfying $Q(x,k,y)$ which minimizes $f(x,k,y)$:
  $$g(x,k) = \min_{y : Q(x,k,y)} f(x,k,y)$$

The corresponding decision problem $Q$ is:

  Input: $x, k, l$
  Query: is there a $y$ satisfying $Q(x,k,l)$ such that $f(x,k,y) \leq l$?

To solve the decision problem,
we can solve the optimization problem,
then check if the output is less than $l$.
I.e. there is a very easy reduction from $Q$ to $MinQ$:

  input: $x,k,l$
  1. $m = MinQ(x,k)$
  2. return $m \leq k$


I need help with virtual memory problem • Given the above virtual to physical address mapping,

1 What is the page size?

2 How many virtual pages can we have in maximum?

3 How many physical pages can we have in maximum?

Approach:

1 For the page size I would say I don't know because we have no information that gives us a clue about page size.

2 I think that we can have as many as the number of physical frames in memory

3 As many as we want, but since we have to constrain the number pages to the number of bits in the address then I would say 2^15 pages.

Can you give me some insight to get to the right idea to solve this problem?

A quick search reveals that

POFS is page offset.
VPN is virtual page number.
PFN is page frame number.

Since the page offset is 13 bits long, assuming that the page is byte-addressed, the conclusion is that page size is $2^{13}$ bytes.

I trust that you can solve the other parts in a similar way, especially having been taught these concepts in class.


Questions about Turing Machine Below I will list a concrete example and the confusion it causes.

Let's first say we have a decision problem, which is:

"Is X <= 400?"

We define the alphabet as the set of natural numbers.

The language formed by this problem is $L = \{ w | w <= 400 \}$

We define a Turing machine, M, over the alphabet, that halts in an accepting state on any word that is in L. Ie the Turing machine recognises L.

$L(M) = \{ w |$ M halts in an accepting state on input w$\}$

Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?
Since this is a decision problem, the language realised from it, will always b finite?
Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.
How would the Language be for the problem: "Is X <= Y?"
For a decision problem, the elements in the Language realised are the solutions?

I left out the notion of an algorithm, in my explanation, Is it not needed as it is implicit in the Turing machine halting on any input of L? Which means it implements some algorithm that can solve the problem?

We define the alphabet as the set of natural numbers.

No you don't. The alphabet must be finite.

  Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?

If all you know is that the TM recognizes the language then you're correct: it could loop forever on some inputs.

  Since this is a decision problem, the language realised from it, will always b finite?

That doesn't follow from being a decision problem. This language is finite because there are only finitely many natural numbers less than 400. But, for example, the language of even numbers is infinite, but it's still a decision problem.

  Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.

Yes, you could produce a Turing machine that decides the language $\{x,y\mid x,y\leq 400\}$.

  How would the Language be for the problem: "Is X <= Y?"

It would be the set of all strings with that property.

  For a decision problem, the elements in the Language realised are the solutions?

I'm not sure what you mean by "realised". (You wrote it before but the exact meaning wasn't so important, then.) A decision problem is any problem of the form "Does the input string have property X?" and it's naturally associated with the language of strings that do have that property.


For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink? I am stumped on the following question:
For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also contains a sink?
I know that the sink has the highest post-order number, so I am inclined to say False, but I do not know if that reasoning is accurate.

The statement is false. Consider the directed graph $G=(V,E)$ where $V=\{1,2\}$ and $E=\{(1,2), (2,1)\}$.
The graph only contains a single strongly connected component, namely $G$ itself. However no vertex in $V$ is a sink.


About graphs whose edge set decomposes into perfect matchings Is there a characterization of graphs whose edge set decomposes into a disjoint union of perfect matchings?

One trivial class of such graphs are $d$-regular $(n,n)$-bipartite graphs. Their edge set will decompose into $d$ disjoint perfect matchings.

Yes: we call such graphs 1-factorable (a 1-factor is also known as a perfect matching). All such graphs are regular, but the converse is not true. In fact, a $d$-regular graph $G$ is 1-factorable if and only if it is of class one, that is, $\chi'(G) = d$, where $\chi'(G)$ is the chromatic index of $G$.

Deciding if a $d$-regular graph is of class 1 is NP-complete (see e.g. [1]), so you likely cannot test this efficiently.

[1] Leven, Daniel, and Zvi Galil. "NP completeness of finding the chromatic index of regular graphs." Journal of Algorithms 4.1 (1983): 35-44.


Shortest Path in Layerwise Complete Graph Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. There are directed edges from the $s$ to all vertices in partition $0$. There are directed edges from all vertices in partition $k$,, ie, the last partition to $t$. $G$ is layerwise complete that is, in addition to the above, there is a directed edge from all vertices in partition $i$ to all vertices in partition $i+1$, ie, adjacent partitions form complete bipartite graphs. An edge between any two nodes is labeled with a negative integer value or with $0$.

There could also be directed edges between nodes in partitions $m$ and $n$ where $1 \leq m, n \leq k, m \lt n,  n \neq (m+1)$, and  labeled with a negative value. This is depicted in the following figure where there are two edges between partition $1$ and partition $3$ indicated with dashed lines. Non adjacent partitions do not form complete bipartite graphs. They only comprise edges as indicated. In the figure, the edge labels are shown with negative values, wherever edges are not labeled with values, they are labeled with $0$ by default.

Consider all paths from $s$ to $t$. The length of this path would be calculated as the addition of all the integer labels of the nodes on this path and the addition of the edge labels if there is an edge between any pair of vertices in this path. For example, the length of the path taking the first vertex from each partition would thus be $0 + 50 + 30 + 50 + 0 -8$, where the negative value of $-8$ corresponds to the edge between nodes labeled with $50$ and $50$. Similarly, if we took the first vertex from partition $1$, the last vertex from partition $2$ and the first vertex from partition $3$, the length of this path would be $0 + 50 + 40 + 50 + 0 - 6$, where the $-6$ value corresponds to the edge between the first vertex in partition $1$ and partition $2$. The $0$ values correspond to the source and sink vertices.

Find the shortest path from $s$ to $t$ taking exactly one vertex from each $k$-partition where the length would be calculated as described.

Attempt : I converted the node weights for a pair $(a, b)$ into edge weights where each edge weight would be the sum of the node value of $b$ deducting the edge cost between $a$ and $b$. This works for edges between successive partitions and produces the correct shortest path in cases where the edges are only between such. However, if I use the same approach for edges between different non successive layers it doesn't work. What would be an algorithm to find the shortest path and the transformation?

Your problem is NP-hard, by reduction from clique. Given a graph $G=(V,E)$ and a number $k$, we construct a graph with $k$ internal layers, each containing $|V|$ vertices. All vertices in a layer are connected to all vertices in the following layer. The weight of an edge is $0$ if the corresponding edge is not in $G$, and $-1$ otherwise. We also add shortcut edges corresponding to edges in $G$ with weight $-1$. The graph $G$ has a $k$-clique iff the shortest path in the new graph has length $-k(k-1)/2$.


An example of something you can formally verify with proofs in Software Development I have been working on understanding formal verification of software. Formal methods include things like modeling your software with Petri Nets, Automata, or State-Transition Graphs. Other techniques for formal verification include using type systems, model checking, automated theorem proving, proofs, and doing program derivation. Finally, there is testing, but I wont go into that here.

I have asked several questions regarding these topics:

What to prove and how to prove it
What you want to "prove" in algorithms
High-level requirements for a Proof of "Saving to the Database"
How to prove a function returns a value
How proofs can be applied to a simple logging function
How to prove a side effect in a function
How to prove $c = a + b$ using Program Verification Techniques
How to use Hoare Logic to Prove this Assertion
How to apply Hoare Logic to this function
How to apply Operational Semantics to this function

The gist of the answers is essentially, you can't apply formal proofs to realistic software applications. This is a bit disappointing to hear, especially when there are projects such as CompCert, the "formally verified" C compiler. My first question is, what exactly they mean (in CompCert) by "formally verified". Wondering which of the following (or something different) this includes:

Model Checking
Formal Proofs (e.g. Hoare Logic)
Type Theory
Transition Systems
Operational Semantics / Denotational Semantics

My second question is, what is a realistic application of proofs to formally verify software (i.e. a web application example, not a textbook example). After asking these questions, I am discouraged that there are no applications of formal proofs to practical software development.

At first I thought that using Coq I could somehow write "formal proofs" for my code, and walk away with a sense of confidence that my code was "formally verified". But now I don't know if that has any practical or realistic meaning. That was what I was getting at in How to prove a function returns a value, High-level requirements for a Proof of “Saving to the Database”, and How proofs can be applied to a simple logging function.

Then I imagined that perhaps Operational Semantics or Hoare Logic could help in "formally proving" the behavior of functions. But the gist of the answers was "it's too hard" or "it's impractical". Nevertheless, it seems that CompCert accomplished it (but not sure if they used Hoare Logic, Operational Semantics, or others), or maybe I am missing something. So what my sense is is there is no use in Hoare Logic or Operational Semantics in practical software development. I would like to be proven wrong on that.

I realize that Model Checking is a good candidate for matching a program model with a specification. But the question still remains, how you know that your model is correct in the first place. That is where it seems formal proofs or some other formal verification technique could shine somehow (which is what this question is about). Wondering how in practice you can apply formal proofs to software development. How to verify that your Model Checking model is correct. It seems the only answer is "formal proofs". But then the question is how. How to apply formal proofs to your model to verify it is correct. I've tried asking questions about it but have had no luck.

Look into tools like Frama-C, SPARK, Astrée, etc...
They have their use in very specific cases, notably software verification of small to medium sized embedded safety critical software (e.g. inside aircrafts, per DO-178C, or nuclear power plants, etc...). Such software have a few dozen thousands lines (or perhaps two hundred thousands at most of C or Ada code), but a bug inside them could crash a plane. So the industry is ready (and required by external regulations) to spend a lot of money and efforts on such small critical software. There are also many severe coding rules (e.g. dynamic allocation, recursive functions, dead code are forbidden).
Proving software, even with these tools, is very costly. A typical safety-critical software costs about a hundred or a thousand times more to develop than a usual software (like your phone applet or some Unix command line tool) of equivalent size, because formal methods (but not only them) are involved. The teams developing them should have formal methods experts working together with aircraft software experts. Sometimes, a small routine has to be rewritten and annotated to be processable by code provers.
There are several research projects around such tools and their use. For a recent example look into VESSEDIA (but you could find many others). One of its results might include a simple proof of a small subpart of the Contiki OS. From an outside view, the results are related to simple subsystems of it (e.g. some simply-linked-list module). In practice the proof requires a lot of formal annotations (so the developer has to provide annotations in ACSL about half as long as the simple C code that is specified by these annotations).
The L4 microkernel has also a variant, called seL4, which uses formal methods (the code size which is formally proved is a few dozen thousands of C code). AFAIU that variant (with its proof) is open-source.
But formal methods don't scale well. It is very unlikely that they would scale -in the next 20 or 30 years- (for present-day programming languages and code) to software as big as the Qt toolkit or the Linux kernel (because formally specifying the intended behavior of Qt or of Linux kernel is practically impossible). For example, C heap allocation is easy to code (that is, a lot of C code uses malloc & free), but difficult to formalize and prove (because current shape analysis techniques don't scale well to large programs). That internal complexity and difficult of formal methods hinders its uses in real-world programs (whose size is growing a lot: a source code editor today is much more complex and bigger than what vi was in the 1980s).
I was part of several research grant submissions mixing more or less formal methods and other approaches (e.g. machine learning techniques on large amount of code, natural language processing techniques), but such funding is hard to get (e.g. there is probably no more any H2020 or FP9 calls dedicated to software engineering before my retirement; the last one was ICT-16 to which I was part of a submission -and waiting (in june 2018) for its evaluation; but only a few percents of submitted proposals get funding). See also this answer to another (but indirectly related) question. BTW, I might be interested in joining some European consortia in 2019 for HPC software tooling using such ideas.
To summarize: There is No silver bullet, so I agree with you:

there is no use in Hoare Logic or Operational Semantics in practical software development

(because even if you have proven your code w.r.t. some explicit formal specifications, there could be - and there still is some - "bugs" or incompleteness in the formal specifications; specifying "correctly" what a real-life software such as a word processor or some web application should do is practically impossible, since you want that specification to be "complete" and cover all the practical cases).
However, notice that recent practical programming languages (e.g. Rust, Ocaml, and also monsters like C++20 or C++17 which became so complex that only a dozen of people understands them fully) have been inspired by formal proof techniques. And academic curiosities like Agda uses even more them. Also, static source code analyzers like clang-analyzer (and even some optimization passes of GCC) use techniques related to formal proofs.
Regarding CompCert, you could download its source code (and proof) and study its code, but you are not allowed to use that source code for non-academic purposes (so CompCert is not free software but its source code is downloadable and you are allowed to study and experiment it. However the resulting binary has license restrictions).
See also this draft report (and the references there).


Is this program O(n^2logn) or O(nlog^2(n))? I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely.

for(int i=0;i<n;i++)
    for(int j=i; j>0; j/=2)
        for(int k=j; k>0; k--)
            printf("Hello, World!\n");

I mean, the innermost loop is for sure $O(n)$ but maybe it could have a tighter asymptotic upper bound? It executes a number of times that is dependent on a logarithmically decreasing value (j), so I'm not really sure how would I have to think about such a scenario.

The complexity is $O(n^2)$. The reason is that the two inner loops take $O(n)$ time. The first iteration takes $i$ operations, then $i/2$, then $i/4$ until it's 0. So we need to compute the sum of $i+i/2+i/4+...+1$ operations which its upper bounded to $2i$. Finally because your outer loop is clearly $O(n)$ the total complexity is $O(n^2)$.


solving large nonlinear systems in parallel I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations.  Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to solve the linear system to get the update increment.  I am  solving the system on a single 24 core, 64GB  workstation with a NVIDIA Quadro K4000 GPU. However as the number of unknowns exceeds 1e5 and/or the Jacobian matrix gets more dense, there is not enough memory on the GPU to fit the compressed Jacobian matrix on the device.  Using the CPU cores allows the Jacobian matrix to fit into memory, however the compute time is very long.

I would like to use a cluster of the above mentioned workstations to solve either the nonlinear system or the linear update increment system, however I am not sure how to go about decomposing the system of equations into pieces that can be tackled via a distributed memory approach.  The equations include radiative transfer, and therefore it is not easy to decompose the domain geometrically as the Jacobian matrix is dense.

Does anyone know about distributed memory approaches to solving large dense linear equation systems?

All help is greatly appreciated!

PS I have looked into the parallelised nonlinear solvers implemented in PETSc, however this is a clunky c library and one must write there entire problem in terms of the PETSc interface which I would like to avoid if possible.  I would be more interested in understanding the details as to how a distributed memory parallelised nonlinear or linear solver works...

The main point of Krylov-Newton is that it does not require computing and storing the whole Jacobian matrix. It only requires the ability to apply the matrix to a vector.

The stardard approach is to do a little bit of pencil and paper work to figure out how to express the action of the derivative without actually computing and storing the whole matrix. If this is not possible, one can try to figure out a compressed representation of the matrix.

For problems where the matrices are dense, but the long range interactions are low rank (I think many radiative transfer problems would fall in this category..?), fast multipole or H-matrix type methods tend to be very effective.

It's difficult to give further advice without knowing more specifics of the problem.


CoNP and NPhard intersection Can a problem be both NP-Hard and CoNP?

Can a problem be both NP and CoNP-Hard?

There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have  coNP ⊆ NP. This means NP = coNP.

The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.


Inferring Shannon Capacity of pentagon Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? That is does $\alpha(C_5 \boxtimes C_5)=5$ and $\alpha(C_5 \boxtimes C_5\boxtimes C_5 \boxtimes C_5)=25$ imply $\theta(C_5)=\sqrt{5}$? Why? Or why not then?

Here $C_5$ is pengtagon, $\alpha(G)$ is independence number of graph $G$, $\boxtimes$ is strong product and $\theta(G)$  is Shannon capacity of graph $G$.

From the givens you can only deduce that the Shannon capacity is at least $\sqrt{5}$. For example, it could be that $\alpha(C_5^8)^{1/8} > \sqrt{5}$, which doesn't contradict your data.

As an aside, the Shannon capacity is usually denoted by $\Theta$, whereas $\theta$ is the Lovász function, which is an upper bound on the Shannon capacity. From the givens you can only deduce that $\theta(C_5) \geq \sqrt{5}$.


Proof Check: The class L is closed under concatenation I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $L_1L_2$, simply look at all possible $n+1$ ways to slice the word into 2 parts and check if the first part belongs to $L_1$ and if the second belongs to $L_2$.

Because both of the languages can be decided in logarithmic space, checking one after the other can also be done in logarithmic space.

Is my idea correct? Thanks.

The idea is correct, but the proof is not finished. It lacks an implementation on the Turing Machine, and sometimes that can be quite tricky. Given a "slice" how are the halves "marked" as belonging to the first and second part, so we can run the two subroutines for $L_1$ and $L_2$? How are the consecutive slices generated?