Is Rice-Shapiro theorem bidirectional? Rice-Shapiro theorem states that

  version A

  Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$ is c.e, then for all $x$, $x \in I$ if and only if there is $y \in I$ such that $W_y$ is a finite subset of $W_x$.

  Or equivalently

  $I$ is c.e $\Rightarrow$

  $~~~~(1):~ \forall x,y ~ (x \in I \land W_x \subseteq W_y \rightarrow y \in I)$

  $\land ~~(2):~ \forall x ~ (x \in I \rightarrow \exists y~(y \in I \land W_y ~\text{is finite} \land W_y \subseteq W_x))$

My question is if it's converse is also true, that is, if (1) and (2) hold, then $I$ is c.e.

So I found another (weaker) formulation of the theorem in H. Rogers Theory of Recursive Functions and Effective Computability p. 324, which states:

  version B

  $I$ is c.e $\iff ~(3):~ \forall x ( x \in I \leftrightarrow \exists u (D_{f(u)} \subseteq W_x))$ for some totally computable function $f$

where $D$ is the canonical enumeration of the finite sets (see definition 2.4).

(3) implies that $I$ is c.e, for it is just a $\Sigma_1$ representation of $I$.
On the other hand, if $I$ is c.e, by s-m-n theorem take the totally computable function $g$ to be defined such that $W_{g(x)} = D_x$. Now the set $g^{-1}(I) = \{ x : \exists y (g(x) = y \land y \in I)\}$ is also c.e, thus there must be a totally computable function $f$ such that $Range(f) = g^{-1}(I)$. So by version A of the theorem, we also have (1) and (2), which imply that this $f$ is the function that satisfies (3).

I also found these two answers which state the theorem in bidirectional form, but with an additional condition:

  version C

  $I$ is c.e $\iff (1) \land (2)$

  $~~~~~~~~~~~~~~~~\land (4):~ \{ e : D_e \in \Gamma \}$ is c.e

Now this set in (4) is just the $g^{-1}(I)$ defined above, where we just saw that it is indeed c.e. by the sole fact that $I$ is c.e. So my primitive guess is that (4) is the ingredient for proving the other direction.

Considering all the observations above, my question is whether the right to left direction holds generally, i.e. does (1) and (2) imply $I$ is c.e? And is there a counterexample if that fails? Assuming (4), can we deduce that $I$ is c.e? And does that mean the wanted counterexample should refute (4)?

No, the converse direction does not hold:

Pick some non-c.e. set $B \subseteq \mathbb{N}$. Now consider $\Gamma = \{A \ c.e. \mid A \cap B \neq \emptyset\}$. By construction, $\Gamma$ satisfies the conclusion of Rice-Shapiro (it suffices to consider singleton sets rather than all finite sets). However, for the resulting index set $I$ we find that $B \leq_m I$, so $I$ cannot be c.e..

Essentially, Rice-Shapiro says that the Markov-effectively open subsets of the subspace of ce subsets of $P(\omega)$ (with the Scott topology) are open, but for already for cardinality reasons alone, not all open subsets can be Markov-effectively open.


Coin flipping problem on an $n \times m$ grid There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly:

Flipping a row of coins;
Flipping a colomn of coins;
Flipping a diagonal line of coins;
Flipping a counter-diagonal line of coins.

The problem is to check whether we can finally let all coins facing up.

As we can see, there are $3n+3m-2$ kinds of transformations in total ($n$ rows, $m$ colomns, $n+m-1$ diagonals, and $n+m-1$ counter-diagonals). However, these transformations are not independent. For example, flipping all rows and then all colomns except the first colomn is equivalent to flipping the first colomn.

By trying some examples $n,m\ge 3$, I find that there are $3n+3m-9$ kinds of independent transformations in total. Other 7 transformations can be done by combining the $3n+3m-9$ kinds of independent transformations. Using Xor-Gaussian elimination we can check the correctness of the proposition.

If we can prove the above proposition, we can solve the problem in this way:

In the following image, there are $3n+3m-9$ shaded lattices. For any state of coins of these lattices (facing up or facing down), we can always use the above transformations to face up all coins of these shaded lattices (according to the order in the image to face them up). Also, for other unshaded lattices, their state will be uniquely determined. Then we can check whether we can finally let all coins facing up in $O(nm)$ time.

But it seems difficult to prove the independent proposition. Does anybody have some ideas on it? Thank you!

This is just linear algebra. Let $x$ be the vector over $\mathbb{Z}_2$ representing the initial state of the board, and let $y$ be the goal state of the board. Let $v_i$ be the vectors corresponding to the allowed flips (flipping corresponds to adding some $v_i$). Then we want to check whether $x+y$ is in the span of the $v_i$.


Highly colored vertices in greedy coloring imply existence of subtrees I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. (It is easy to see that this might not be the optimal coloring possible)

So after the coloring, we see that a vertex has color $k$ which is the highest assigned color in the graph (other vertices might have color $k$ but no vertex has color more than $k$). I would like to say that given any tree on $k$ vertices I can find that tree as a sub-graph of $G$.

My ideas : I observed that the $k$ vertex tree can be found in the graph with one vertex being the one colored $k$ (as one might expect). Moreover I think that if someone mentions any $k$ vertex tree and any node, $v$, in that tree we can find the tree in $G$ with the vertex colored $k$ acting as the node $v$. This is what I tried to induct on but couldn't succeed.

Let us prove the following claim by induction.

Let $T$ be a colored rooted tree in which each color appears at most once, and the colors of the children of a node are smaller than the color of the node.
Let $G$ be a greedily colored graph, and let $v$ be a vertex whose color is the same as the color of the root of $T$. Then we can embed $T$ into $G$ in such a way that the root gets mapped to $v$ and the colors of all nodes match.

If $T$ consists of a single node, this is clear. Otherwise, let $T_1,\ldots,T_m$ be the subtrees rooted at the children of the root of $T$. Since the colors of the roots of $T_1,\ldots,T_m$ are distinct and smaller than the color of the root of $T$, the node $v$ must have distinct neighbors $v_1,\ldots,v_m$ whose colors match the colors of the roots of $T_1,\ldots,T_m$. Inductively, we can embed $T_1,\ldots,T_m$ into $G$. Since all colors in $T$ are distinct, the embeddings are disjoint, and so can be put together to construct the desired embedding of $T$.
To derive your claim from this one, you need to show that every tree of size $k$ can be colored according to the prescriptions of this claim. You can use BFS to accomplish that.


Time Complexity of a Union Find algorithm I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows:
input: data: array of sorted n integers
input: n: size of data
input: c:a positive integer between 1 and n-1

delta = Array(n-1)
map=HashMap()

for I =1 to n-1 do:
delta[i] = data[i+1] - data[i]
map.Insert(delta[I],i)
end

heap=MinHeap(delta)
uf = UnionFind(n)

for I =1 to c do:
t=heap.deleteMin()
x=map.Search()
uf.Union(x,x+1)
end
return uf

To my knowledge
the first for loop runs in O(n) time, building the heap takes O(n), and the second for loop would run at O(n^2) times dominating the other complexities.

Figured this out. Since uf.Union is an inverse ackermann it grows so slowly that it could be considered constant. thus the second loop would run O(clgn) giving and expected output of O(n + clg n))


Polynomial Time reducible explanation Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct?

  If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in P$ is false

I think this means that since $Y$ is not polynomial time solvable, and it is reducible to $X$, then X is not polynomial time reducible. This makes sense to me, but the statement ends with a false, how is that?

  If  $Y \leq_p X$ and $X$ is solvable in constant time, then $Y$ is
  solvable in constant time as well

Seems pretty intuitive, if you can reduce to $Y$ using a polynomial reducer, then it should also be solvable in constant time. But I have the nagging feeling that it wouldn't be constant time since polynomial time > constant time.

  Say you have $SORT$ which checks if the list of ints is sorted, then
  for all $X$ we have $SORT \leq_p X$

I don't get this at all, how can the $SORT$ algorithm be reducible to all $X$, isn't that a bit too farfetched?

  Assume $Y \leq_p X$, if $Y$ doesn't have a polynomial time algorithm
  to solve it, then there isn't one for $X$ either

I think this implies that since $Y$ is not solvable in polynomial time then neither is $X$, but isn't that false? Isn't the whole purpose of us using reductions is to show that we can reduce one to another that already has a solution, thus translating the solution?

What is polynomial-time reduction?
Let us recall the definition of polynomial-time reduction (function) as presented in section 34.3, NP-completeness and reducibility
CLRS, third edition.

Let $\Sigma=\{0,1\}$. A language $L_1$ over $\Sigma$ is polynomial-time reducible to a language $L_2$ over $\Sigma$, written $L_1 \le_p L_2$, if there exists a polynomial-time computable function $$f: \{0, 1\}^*\to\{0,1\}^*$$ such that for all $x\in \{0,1\}^*$,
$$x\in L_1\Longleftrightarrow f(x)\in L_2.$$ We call the function $f$ the reduction (function), and a polynomial-time algorithm $F$ that computes $f$ is a reduction (algorithm).

Examples

[FALSE]$\ \ $ If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.

What is $O(2^n)$? It is not $\Omega(2^n)$! For example, a constant function is in $O(2^n)$. If set $Y$ can be solved in constant time and $Y \leq_p X$ then $X$ can be in $\bf{P}$. For example, we can let $X=Y$.

[FALSE]$\ \ $ If $Y\le_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well.

You cannot ignore the time spent in the reduction step. $Y\le_p X$ tells us that it takes no more than polynomial time to map (a.k.a. reduce) an instance (a.k.a a word) of $Y$ to an instance of $X$. That polynomial time, as you suspected, is significant.
In fact, the complexity class $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$ for some $X$ that is solvable by constant time.

[ALMOST TRUE]$\ \ $ Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq_p X.$

There is a polynomial-time computable function $f$ that maps a word in $\{0,1\}^*$ that encodes a sorted list of ints to 1. Basically, we can use an algorithm that checks each int in the list is not greater than than the next int in the list. This algorithm is, in fact, linear-time.
Suppose word $x_0\not\in X$ and $x_1\in X$. Let $g$ be a function that maps 0 to $x_0$ and 1 to $x_1$. $g$ can be computed by a constant-time algorithm, since both $x_0$ and $x_1$ are fixed sequences of 0s and 1s. $g\odot f$ is a polynomial reduction from $SORT$ to $X$.
As long as $X$ is not the empty set nor the set of all words over $\Sigma$, $SORT \leq_p X.$
If $X$ is empty set, there is no reduction of any kind. If $X$ is the set of all words, then any map to $X$ will map any instance, including a "no" instance to a "yes" instance of $X$. Because of these two exceptions, we can say the proposition is false.

[TRUE]$\ \ $ Assume $Y \leq_p X$, if $Y$ doesn't have a polynomial time algorithm to solve it, then there isn't one for $X$ either

$Y \leq_p X$ implies
$\quad X$ is solvable in polynomial time $\Longrightarrow$ $Y$ is solvable in polynomial time.
Note that contrapositive of that implication is exactly
$\quad Y$ is not solvable in polynomial time $\Longrightarrow$ $X$ is not solvable in polynomial time.
Exercises
Check whether the following propositions are true.
Proposition 1.  If set $Y$ can be solved in $\Omega(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.
Proposition 2.  If set $X$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $Y \not\in \bf{P}$.
Proposition 3.  If set $X$ is solvable by polynomial time, then $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$.


Context Free Grammar $L = \{a^i(b+c)^jd^k | i0\}$ I'm trying to design a CFG that accept the words of the following language:

$$L = \{a^i(b+c)^jd^k  \mid  i<j+k; \quad  i,j,k>0\}$$

My first approximation would be to do $i = j+k$ as something like:

$S\to aSd \mid X$

$X\to aXY \mid aY $

$Y\to b \mid c$

But then I don't know how to make the jump to the $<$.

Whenever you see a condition $i<j+k$, you can translate that to the condition $i+\ell=j+k$ where $\ell>0$, then use the methods you know for handling $=$ instead of $<$.

See our reference question on this subject for more systematic answers.


Why is Turing completeness right? I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can perform any possible computation.

Of course, calculating machines of one kind or another go back to antiquity. People have built machines which for performing addition and subtraction (e.g., an abacus), multiplication and division (e.g., the slide rule), and more domain-specific machines such as calculators for the positions of the planets.

The striking thing about a computer is that it can perform any computation. Any computation at all. And all without having to rewire the machine. Today everybody takes this idea for granted, but if you stop and think about it, it's kind of amazing that such a device is possible.

I have two actual questions:

When did mankind figure out that such a machine was possible? Has there ever been any serious doubt about whether it can be done? When was this settled? (In particular, was it settled before or after the first actual implementation?)
How did mathematicians prove that a Turing-complete machine really can compute everything?

That second one is fiddly. Every formalism seems to have some things that cannot be computed. Currently "computable function" is defined as "anything a Turing-machine can compute". But how do we know there isn't some slightly more powerful machine that can compute more stuff? How do we know that Turing-machines are the correct abstraction?

Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the Entscheidungsproblem.

Although Church's paper was published slightly earlier, Turing was unaware of it when he developed his ideas, and Turing's approach proved to be more useful for the design of real-world machines. This was because he showed how to design a Universal Turing Machine that could be programmed to run any computation. This universal machine, with a concrete architecture based on the work of John von Neumann is the basic idea behind the machine on which you are reading my answer.

As you noted, computable is defined as "computable on a Turing machine" and all other reasonable models of computation have proven to be equivalent in their power. The belief that all reasonable models of computation are equivalent in what decision problems they can solve is known as the Church-Turing thesis. In its original form, it is almost completely believed by the learned community. In fact it is not completely clear what it would mean to prove/disprove the Church-Turing thesis; in a lot of ways it becomes an empirical question.

However, there is still the extended Church-Turing thesis which asks the slightly more subtle question of: what can be computed efficiently?. Many classical models, such as $\lambda$-calculus, Turing Machines, tag-based systems, cellular automata, etc are equivalent under the extended thesis as well. However, the recent development of quantum computing casts doubt on the extended thesis. Although most people who work on quantum computers (including me) believe they are more efficient that classical ones, the matter is subject to scholarly debate. Note that in terms of the coarse notion of what is computable (as opposed to efficiently computable) quantum computing is still equivalent to Turing's model.


Sorting n element using Fibonacci Heap How can I design a sorting algorithm of n elements using a Fibonacci Heap?

Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap?

Your help is appreciated

Designing a sorting algorithm based on the Fibonacci Heap is the same as the Heap Sort; Build the Fibonacci-Heap, Extract Minimum.

From the Wikipedia;

  Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

The data size should be very long to achieve better than the heap sort, but this time you may turn into external sort.

And, remember, for comparison based sorting algorithm, we have $\Omega(n \log n)$ as lower bound.


Justify the following running time The book "Cracking the Coding Interview , 6th ed." describes the following method to sum the values of all nodes in a balanced binary search tree, and also claims that this method runs in O(n) time.

int sum(Node node) {
    if (node == null) {
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

It seems to me that this method iterates through every node in the tree exactly once, plus one null reference for each leaf in the tree. I would say that n is the number of nodes in the tree, and we visit O(n+b) nodes (where b is the number of leaf nodes, is the number of null nodes traversed) and do constant work there.

How can n be an upper bound if we visit (or attempt to visit) more than n nodes? You might argue that b is constant and so we drop it, but b grows proportionally to n.

Please don't mark this as a duplicate just to get your internet points. Specific questions have specific answers.

The book is correct, because $b\leq 2n$, so you visit no more than $3n$ nodes, which is $O(n)$, and $b\leq 2n$ because no node has more than two leaves. You correctly say that $b$ grows proportional to $n$, which is exactly the key.

Just for clarity, Big-Oh notation means "grows proportional to, ignoring constant factors" (roughly), which is why we say that $3n\in O(n)$, even though one is a multiple of the other, and $6n^2+3n+42\in O(n^2)$ and $42e^n\in O(e^n)$, for example.

(actually, $O(n)$ means, "is not more than $cn$". For "is proportional to $n$", use $\Theta(n)$ instead of $O(n)$).


Does a language stay regular if you re-encode the input? $\tau$ be a transformation that, applied to a word of $\Sigma_a^\star$, replaces each character with a word from a possibly different $\Sigma_b^\star$ and concatenates the resulting words. For instance, given a $\tau$ with the following translation table:

A -> AA
B -> AB
C -> BA
D -> BB

$\tau(ABC)=AAABBA$ and $\tau(DACB)=BBAABAAB$. Note that the words may not all have the same length. A translation table such as

A -> FOO
B -> BAR
C -> BAZ
D -> QUUX

is also valid.

Now, is $\{w'|w\in L\land w'=\tau(w)\}$ regular iff $L$ is a regular language as well?

The answer is yes. This is generally called homomorphism, and regular languages are closed under homomorphism. Moreover, regular languages are closed under inverse homomorphism also. More precisely,
if $\tau$ is a homomorphism from alphabet $\Sigma$ to alphabet $\Delta$ and $L$ is a regular language over $\Delta$, then $\tau^{-1}(L)$ is also a regular language.

You can take a look here for more details, or the best is to take a look at this book, which contains proofs about basic properties of regular languages.


Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable? This question was made during a class of Computer Theory in Rome, Italy.

Let $G$ be a regular grammar, $\Sigma$ its alphabet and $L(G)$ the language generated by $G$

  Given a regular grammar $G$, is $L(G) = \Sigma^*$ a decidable property?

My approach

I can design a Finite State Automaton that recognize the strings in the language $G$. Because regular languages are closed under the iteration operation, the FSA recognize also string in $\Sigma^*$ alphabet

By the "iteration operation" you probably mean the Kleene closure of the language. In the case of the language is $\Sigma^*$ its Kleene closure is clearly equal itself. But you do not provide detailed explanation about how to use this fact to decide whether $L(G) = \Sigma^*$. However, you could solve the problem as following:

Solution 1: Convert the regular grammar into the corresponding DFA and take the complement of the DFA. The complement of a DFA accepting all strings has not accept state. So you can decide by checking whether or not it has an accept state.

Solution 2:  Convert the regular grammar into the corresponding DFA and minimize it. If this DFA accepts $\Sigma^*$ then the minimal DFA has only one state which is the accept-state. So you can decide by checking if the minimal DFA has only one state which is accept-state .


When does a type generalise another type? In languages like Haskell, with a Hindley-Milner type system, when does a type $t$ generalise a type $u$? I use the definition: $t$ generalises $u$ iff $\forall\ v: v \text{ unifies with } u \rightarrow v \text{ unifies with } t$.

I have an algorithm that given these types returns a unifier if one exist. The unifier is an ordered list of assignments $v_1 \mapsto t_1, v_2 \mapsto t_2, \dots, v_n \mapsto t_n$ such that applying $v_i := t_i$ to both types for ascending $i$ results in two identical types.

For instance, the types $(a,a)$ and $(p,q)$ unify with the unifier $a \mapsto p, p \mapsto q$: after applying these assignments both types are $(q,q)$.

It should be possible to use the unifier to see if a type generalises another type, but I can't figure it out at the moment. I couldn't find an existing algorithm either.

Note: if there is an easier way, without using the unifier, that would be appreciated as well.

A pretty easy way to see if $t$ generalizes $u$ if $u$ matches $t$:

replace all variables in $u$ by (fresh) constants, written $u_c$, and check if $u_c$ unifies with $t$.

If so, then there is a substitution $\sigma$ such that $t\sigma\equiv u$ which means by definition that $t$ is more general than $u$.

As mentioned in the comments, if $\mathrm{mgu}(t,u)$ succeeds and returns a substitution $\tau$, then $u$ matches $t$ iff $u\tau\equiv u$ up to variable renaming.

Note: Pattern matching is usually best implemented independently from unification, as it is simpler in general. In particular it isn't necessary to actually replace variables with constants in $u$. Beware of non-linearities in $t$ though: $\alpha\rightarrow \alpha$ does not match $\mathrm{int}\rightarrow\mathrm{bool}$!


Traveling Salesman -- number of qubits required? I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In there, they give an example of how you could use quantum computers to solve the Traveling Salesman problem, for 4 cities. I may have missed the explanation somewhere in the notebook, but they use 9 qubits to address the problem -- can someone explain why 9? It is a hardcoded value in the actual code, which indicates to me that you could use different numbers...so what would be the tradeoffs with using more or fewer qubits, and how would that scale with the number of cities?

I understand that I can run the notebook and change the value to see how the results change, but I'd like to get a better theoretical grasp of why.

Thanks!

The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a Hamiltonian, and so solved by a quantum computer. The number of qubits needed is the dimension of the Hamiltonian, which is also the number of bits in the encoding.

In TSP, the optimization is over permutations. The notebook suggests encoding a permutation by encoding its permutation matrix, which is an $n\times n$ binary matrix. Since the rows and columns sum to 1, we can deduce the final row and column from the rest of the entry, and so need to keep only $(n-1)^2$ variables. In your example, $n = 4$ and so $(n-1)^2 = 9$.


Efficient queriable data structure to represent a screen with windows on it (this is related to my other question, see here)

Imagine a screen, with 3 windows on it:

I'd like to find an efficient data structure to represent this, while supporting these actions:

return a list of coordinates where a given window can be positioned without overlapping with others

for the above example, if we want to insert a window of size 2x2, possible positions will be (8, 6), (8, 7), ..

resizing a window on the screen without overlapping other windows while maintaining aspect ratio
insert window at position x, y (assuming it doesn't overlap)

Right now my naive approach is keeping an array of windows and going over all points on the screen, checking for each one if it's in any of the windows. This is $O(n\cdot m\cdot w)$ where $n, m$ are the width, height of the screen and $w$ is the number of windows in it. Note that in general $w$ will be small (say < 10) where each window is taking a lot of space.

An easy optimization to the naive algorithm is to skip some points when you check one covered by a window. Say you scan left-to-right, top-to-bottom. If you encounter an $(x, y)$ in window $w = (l, r, w, h)$, you can jump from $x$ to $l + w + 1$ and continue. If windows are big and don't overlap, off the cuff, I'd wildly conjecture that would give you an $O(p)$ algorithm, where $p$ is the number of points in the set you return.

In fact, it could be beneficial to see whether the windows are generally wider or taller. For tall windows, it would be better to scan top-to-bottom, left-to-right; for wide windows, the method discussed above should win out. You might be able to take the idea and do scan/skip diagonally to get balanced performance across the board.

In fact, scanning left-to-right, top-to-bottom, you can remember for subsequent $h$ rows (values of $y$) that you will need to skip at the same $x$ value to the same $l + w + 1$ value, if you reach the $x$ (you might not if there's another window that overlaps). This would make top-to-bottom, left-to-right and diagonal scanning unnecessary to get equivalently good performance.

More generally, you now have two data structures: one with $O(1)$ preprocessing/construction overhead and $O(w)$ lookups, and one with $O(p)$ (possibly; maybe you can do better, or maybe my optimization doesn't really achieve this) preprocessing/construction and possibly $O(1)$ (hash/lookup table) or $O(\log p)$ (BST). So there are already two alternatives, both of which are pretty good, really...


Finding independent sets so that all nodes are hit frequently I have a problem, and I appreciate it if you could share your thoughts.

Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in each iteration. Then, I will increase a counter for those vertices that are in the selected IS. Initially, the counter for all vertices of the graph are zero.

With an integer programming formulation, we can choose one independent set (provided that we know the set of all ISs) in every iteration, so that the counter of each vertex $i$ in the graph is at least $r_i$ over $k$ iterations (clearly $r_i \leq k$)? In other words, we can make a plan, with IP, so that each vertex $i$ has been selected $r_i$ times over $k$ iterations. Also, with simple modification, minimum value for $k$ can be included in IP formulation. I aim at finding the minimum $k$ by which all $r_i$'s are satisfied.

Now the main concern is that the above formulation need the set of all ISs as an input. Finding this set, however, is an NP-hard problem. So, I was wondering if there there is any way to bypass the need for having all ISs? For sure, many heuristic algorithms can be developed (one example is proposed in comments below). However, I am interested to find an algorithm for which I can say something analytically, e.g. convergence proof, optimality gap, etc.

Approach 1: Use ILP

If you want an algorithm that might work in practice as long as the graph is not too large, one approach is to formulate this as an integer linear problem.

That's pretty straightforward in this case.  We'll have $k|V|$ integer variables.  In particular, $x_{v,i}$ will be $1$ if the vertex $v$ is included in the independent set in the $i$th iteration and $0$ otherwise.

First, let's encode the constraint that the $x_{\cdot,i}$ have to encode an independent set in each iteration.  We get $0 \le x_{v,i} \le 1$ and

$$x_{v,i} + x_{w,i} \le 1 \quad \forall (v,w) \in E.$$

Next, note that $x_{v,1} + x_{v,2} + \dots + x_{v,k}$ counts how many times each vertex is covered across the $k$ iterations.  We want this to be at least $r_v$, so we get the constraint

$$x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v \quad \forall v \in V.$$

Now throw an integer linear solver at the problem, and hope that it finds a solution.  The worst-case running time is exponential, but integer linear solvers sometimes work a lot better than you'd expect, so as long as the graph is not too large, it might just work.

If you want to find the smallest $k$ such that this can be solved, use binary search or linear search on $k$.

You can also formulate a similar version that works using SAT, and then throw a SAT solver at it.  It's a little more complex because you'll need to encode the constraint $x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v$ in SAT, but it can be done (e.g., by building a circuit for a small adder and then translating it to SAT using the Tseitin transform).

Approach #2: A greedy heuristic

Here is an alternative approach, that might work even on larger graphs.  It won't find the optimal solution, but it might find a solution that is not too much worse than the optimal solution.

The problem reminds me of a set cover problem: in each iteration you select one set, and you want the union of the sets to cover the universe.  One natural approach to set-cover-like problems is to try to apply the greedy algorithm for set cover: in each iteration, choose an independent set that gives you as much progress as possible.

Let me start by assuming $r_v=1$ for all vertices $v$, for simplicity.  Then you could use the following algorithm:

Initially all vertices are uncovered.  Set $i=1$.
Find an independent set $I$ that covers as many of the uncovered vertices as possible.  Choose that one, and output it as the independent set $I$ as the one to use in the $i$th iteration.  Increment $i$ and go back to step 2.

You can now plug in any algorithm you like for finding independent sets, including a heuristic or approximation algorithm.  There's lots written on that subject so you might be able to re-purpose any of a number of different algorithms.

What about the general case where the $r_v$'s are arbitrary?  Well, in any given iteration, you can evaluate each candidate independent set by how much incremental coverage it adds, where now the coverage is given by the sum of the counters on all of the vertices.  So, in each iteration, choose the independent set with the largest incremental coverage that you can find.  This might give a reasonable approximation algorithm for your initial problem.


What operation is the algorithm performing? unsigned int input = 0xC116D9B5709FED85 unsigned int output = 0
while (input > 0 )
{
if (( input mod 2) == 1)
{
output += 1
}
input = floor(input / 2)
 }
 return output

I understand how the algorithm is working and using mod to break the input and then counting the number of times input is modded by 2 where it resulted 1. Basically checking if the number is odd. My question in the first place is howcome we can even store a huge hex like the one in question in an unsigned int. Doesn't it exceed the size limit of unsigned int. Secondly, if someone can help me understand the question would help alot.

The algorithms counts the number of $1$s in the binary expansion of the input. The code as written seems a little weird because it’s not a function that can be applied to an input, it’s being specifically applied to the defined number. I certainly couldn’t tell you why it’s being applied to that number without a lot more context.


What are applications of alphabetic trees? Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as

  Alphabetic trees are Huffman trees with the additional constraint on
  order, or, equivalently, search trees with the modification that all
  elements are stored in the leaves. Faster algorithms exist for optimal
  alphabetic binary trees (OABTs).

From this, I understand that an alphabetic binary tree will produce shorter paths from root to element for elements that have been inserted into the tree more times than elements that haven't, and the alphabetic property would be described the same way for a ternary tree.

I haven't been able to find a lot of discussion about applications for the alphabetic property outside of Huffman coding but it is not a requirement to implement the algorithm.  Are there any applications where the alphabetic property would be a requirement, and if not, are there any benefits to guaranteeing the alphabetic property that justifies increased implementation complexity?

You use alphabetic trees when you need nodes to keep their input order in the resulting code. Huffman trees are used for coding purposes, and alphabetic trees for storing data and for allowing quick search and edit.

One example application is storing textual data in alphabetic order. The complete works of Shakespeare were stored in an OAT (optimal alphabetic tree), which was constructed using the Hu-Tucker algorithm. See here for another $O(n \log n)$ algorithm for constructing OATs.


Towers of Hanoi Algorithm "Using Auxiliary" Peg I'm trying to fully understand how the recursive Towers of Hanoi Algorithm works and to implement it in code.

Something that keeps throwing me of is the use of phrases like "move n-1 discs from A to B using C."

I understand that the peg which is referred to is as being "used" is the auxiliary or spare peg, but the language seems misleading because if n-1 has a value of more than 1, then more than one peg is used to perform the move. So the phrase "using C" or "using B" or "using A" doesn't seem accurate and is hindering me from thinking clearly about the problem.

Am I missing something, or can I substitute the phrase "with C as the spare/auxiliary peg" for "using C" without loss of meaning?

I've seen one video where for the n=2 problem, the first move is described as "move a disc from A to B using C" - in this case C isn't involved at all!

I wonder if anyone who has managed to fully grasp the algorithm can advise if it would be helpful to adopt the "using A/B/C" language or if there is another alternative that you have found more helpful, such as my suggestion above - "with C as the spare/auxiliary peg"?

In mathematics, the literal meaning of a phrase is of little importance. What is important is that both author and reader know what a phrase means, and this can come about in two ways. Either the phrase is well-known, or the phrase is defined in the article. In your case, the phrase "move $n$ pegs from $A$ to $B$ using $C$" means "call the function Hanoi with parameters $n,A,B,C$" - no more, no less. The author could have chosen a completely different phrase, for example "jump from $A$ to $B$ doing $n$ flips above the midpoint $C$", as long as they make it clear that it means "call the function Hanoi with parameters $n,A,B,C$".

Another point that you raise is that when $n=1$, you can move the disc directly from $A$ to $B$, without involving $C$ at all, which you feel contradicts the phrase "using $C$", since $C$ isn't actually used. However, in mathematics such phrases are usually inclusive rather than exclusive — it is not obligatory to actually use $C$. This highlights the fact that mathematical terms often differ in meaning from their common use. For example, when mathematicians say "$p$ or $q$", they are also allowing the possibility "both $p$ and $q$", although common knowledge precludes it.


Iterative and/or tail-recursive implementations of merge sort? I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented in an iterative style?

In general how can a recursive algorithm converted into an iterative and tail-recursive algorithm? What are the possible pros and cons of this conversion?

An iterative implementation is easy: you just introduce an explicit stack (instead of using the call stack as the implicit stack).  You can always convert any recursive algorithm to be in iterative form by using an explicit stack; each recursive call is translated into pushing something onto the stack.

However, I don't know of any reason why you'd want to do that, in this case; the resulting algorithm just becomes harder to understand.  The amount of stack space used by merge-sort is $O(\lg n)$, where $n$ is the length of the list, so you're not going to exhaust the size of the available stack.

Merge-sort is not purely tail-recursive.  First of all, the result of a call to merge-sort is not the result of either recursive call; the results of the two recursive calls must be further processed (by merging the sorted sublists).  Second of all, merge-sort contains two recursive calls, so even if there were some way to convert the last call to a tail-call (there isn't), you'd still be left with one other recursive call inside the body of the function.  So, no, merge-sort is not tail-recursive.  And there's little or no benefit to try to rewrite it in a form that is tail-recursive.

(Technically speaking, just as any algorithm can be transformed to be iterative,
anything can be transformed to be tail-recursive form by using continuation-passing style.  This includes merge-sort.  Nonetheless, in this case there is no reason why anyone would want to do that.  It's unlikely to make the code noticeably faster, and it's sure to make the code harder to understand.  Therefore, this is a technicality that can be safely ignored.  If you don't know what continuation-passing style is, don't worry about it, you can just pretend that merge-sort cannot be made tail-recursive, and that'll be close enough.)


Constructing non intersecting segments from distinct sets of points Given 2 sets of points in the plane, $A$ and $B$, each of size $n$,
I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect.

The coordinates are comparable signed reals (no constraints here about that) and no 3 points are on the same line. There can be no segments sharing an end point because we need to construct $n$ pairs of points from $2n$ points, and there are no duplicate points.

I tried to sort each of the sets according to $x$ or $y$, and pair the appropriate points from each of the sorted sets, but I found a counterexample for that:
a set of points whose sorted $x$ order was $(a_1,b_1,a_2,b_2)$ and sorted $y$ order was $(a_2,a_1,b_1,b_2)$.

Here is a quote from

  Kaneko, Atsushi, and Mikio Kano. "Discrete Geometry on Red and Blue Points in the Plane—A Survey." Discrete and Computational Geometry. Springer Berlin Heidelberg, 2003. 551-570.


Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties? I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding shortest path. I am reading about A* search starting page 71 of the UK GCE Computing textbook, Rouse to find shortest path. I have also read the Wikipedia entry - but to no avail. Two things do not makes sense to me.

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

(ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important? Surely all the intermediate distances before the completion of the A* algorithm are "over-estimates".

Regards,

Clive

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

When you decide to use A* to solve a problem, you need to design an appropriate heuristic. Designing a heuristic is a creative act, so one can't really give advice on how to do it. Ideally, though, the heuristic should give a good estimate of the true cost.

The purpose of the heuristic is to guide the search and a search that receives accurate guidance will terminate faster than one that receives poor guidance.  There is, however, a trade-off. If your heuristic is perfect, then it will guide the search so well that the optimal route is the first one it examines. But, of course, if you could compute this perfect heuristic, you wouldn't need to be using search in the first place! Having a better heuristic means you spend less time searching, but you need to balance that against the fact that you'll probably spend more time computing this better heuristic.

  (ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important?

You know it because you figured it out and you designed the heuristic to achieve that. The classic example is using straight-line distance as a heuristic for navigation. You know that the straight-line distance is the shortest possible distance between two points, so it cannot overestimate the distance you'd have to travel on the road network.

I wrote an answer a while ago about why it's important that you don't overestimate. Essentially, if you say "every route via X is long", the algorithm will first look at routes via other places, and potentially find one. When it finds an answer, it will stop. But it never considered routes via X so, if it turns out that the shortest route was via X, you missed it because your heuristic overestimated.

  Surely all the intermediate distances before the completion of the A* algorithm are "over-estimates".

No. A*'s use of the heuristic means that, any time you expand a node in the search, you've found the shortest possible path to that node. So, every time you expand a node, you've found the optimal path to that node, plus an underestimating heuristic to the goal: all your intermediate states that get expanded are underestimates. There might be over-estimates in the frontier (i.e., suboptimal routes to intermediate goals) but they'll never get expanded.


Lower-bounding the Membership Problem in the Bitprobe Model I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound.

In particular, they are trying to show that $s_A(2, m, 2) \in \Omega(m^{4/7})$. That is, the goal is to store a set $S$ of $2$ elements from a universe $U$ of size $m$ such that a query of the form "is $x \in S$" can be answered using only $2$ bit probes. The $s_A(2, m, 2)$ indicates the minimum number of bits required to answer such queries, and in particular, the scheme is allowed to be adaptive (the second probe can depend on the first one).

They begin by saying that such a scheme can be defined by three functions $a, b, c\colon [m] \to [s]$, where the query "is $x \in S$" is answered by first probing location $a(x)$ then probing locations $b(x)$ or $c(x)$ depending on the outcome of the first probe. They then go on to explain that this can be viewed as a bipartite multigraph where $G = (B = [s], C = [s], E = \{\langle b(x), c(x)\rangle : x \in [m]\})$. Lastly, they state that $E$ is naturally partitioned into sets $E_1, E_2, \ldots E_s$, where $$E_i = \{\langle b(x), c(x)\rangle : x \in [m], a(x) = i \}$$.

Now, my questions are as follows. First they make the assumption that "Each $E_i$ is a matching $\ldots$ Details Omitted". Why can this assumption be made? I can't for the life of me figure out why this needs to be the case.

My second (and more important question) is this. They provide the following example:
They state that edges with the same type of label (i.e $x$ and $x'$) belong to the same matching. In their caption, they state that if such a scheme were to exist, then there are some pairs that cannot be stored (such as $x$ and $y$ on the left). This is what I don't understand. They do not provide an explanation beyond the "If it were to exist in our graph, then the underlying scheme cannot store all sets of size two. In particular, it is easy to verify that if this configuration exists, there is no way to store the set $\{x, y\}$".

I am just getting myself familiar in this area, so some of the "obvious" things may not be so obvious to me right away.

First, the reason why the authors had to omit so many details is that the paper was published in a conference (SOCG) with a strict page limit. When you publish your paper, please provide a full version on your website with all the proofs. In my area usually the full details are in an appendix which is not available from the conference website since back in the day, the proceedings were printed and so a strict page limit had to be enforced. Nowadays many proceedings are online only and then there is no page limit, but it seems that your paper dates from before that period.

I'll only address your main question. Consider the structure for storing $\{x,y\}$. When you query $x$, you get either "left" or "right" at the first probe. Say you got "right". Then the right endpoint of the edge $x$ must be 1 (we use the convention that the output is the last bit read, see the paper). When querying $x'$, we read the same first bit, and so the right endpoint of the edge $x'$ must be 0. This means that the left endpoint of $y$ must be 1. This means that when querying $w'$, the first bit read must be "right". But then when we query $w$, we read the right endpoint of the edge $w$ which is 1.

Suppose now that you got "left" in the first probe of $x$. Then the left endpoint must be 1, and so the first probe of $y'$ must be "right". Therefore the right endpoint of $y$ must be 1, and so the first probe of $z'$ must be "left". But then when we query $z$, we answer the left endpoint of $z$ which is 1. In both cases we have reached a contradiction.


State complexity of difference of two languages Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, recognizing the language $L(A_1)\setminus L(A_2)=L(A_1) \cap(\Sigma^*\setminus L(A_2))$.
What I thought of: evaluate the state complexity of $\Sigma^*\setminus L(A_2)$ (hypothesis: $2^m$). Why? Because an upper bound of $2^m$ can be obtained for a DFA to accept the language of $A_2$. It's also known that the state complexity of the completion $\Sigma^*\setminus L(A_{min})$ is $k$, where $A_{min}$ is an arbitrary minimal $DFA$ with $k$ states. Therefore we can evaluate the upper bound of the minimal DFA, recognizing $L(A_1) \cap(\Sigma^*\setminus L(A_2))$ as $n2^m$ (the state complexity of the intersection is simply the product of states).

This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ and any $m$.
It is an interesting question whether the bound is tight for all $n$. This is likely the case if we take for $L(A_1)$ the language $(\Sigma^n)^*$.


How to use structural induction to prove law on lists I want to prove that the following equation holds using structural induction on (finite) lists

subs (map f xs) = map (map f) (subs xs)

where subs [] = [[]]                                          (subs.1)
      subs (x:xs) = subs (xs) ++ map (x:) (subs xs)           (subs.2)

      map f [] = []                                           (map.1)
      map f (x:xs) = f x : map f xs                           (map.2)

: is the cons operator and ++ the join operator on lists.

I'm using structural induction on xs, the base step for [] is easy to prove but I hit a wall when trying to solve the inductive step for (x:xs)

subs (map f) (x:xs)                                             (map.2)
subs (f x : map f xs)                                           (subs.2)
subs (map f xs) ++ map ((f x):) (subs (map f xs))               (hyp)
(map (map f) (subs xs)) ++ map ((f x):) (map (map f)(subs xs))

From here I couldn't find a way to proceed so I moved to the right-hand side of the equation and I kind of found a way to find a "proof" but something tells me that it's bogus

map (map f) (subs (x:xs))                     (subs.2)
map (map f) (subs xs ++ map (x:) (subs xs))   (generalise term)
map (map f) ys                                (hyp)
subs (map f ys)                               ???
subs (map f (y:ys))
□

My reasoning here is: (x:xs) is a list with at least length 1, it should be legal to generalise subs xs ++ map (x:) (subs xs) as either (y:ys) or ys (because (x:xs) is not empty) so I chose the latter first to be able to use the induction hypothesis and after that I rewritten ys as (y:ys) to establish the case.

Does this make any sense at all? If not, could anybody show me the right approach to tackle this proof?

You'll want a helper lemma to make this endeavor more digestible.

Notations for map and subs:

I'm going to condense the map notation a bit so that we can express it as the binary operator $f \diamond l = \mathrm{map} ~ f ~ l$. Similarly, we will express the subs as a unary operation $\lfloor\!\!\lfloor l \rfloor\!\!\rfloor = \mathrm{subs} ~ l$.

This might seem terse at the moment, but it's useful to visually capture a "commutativity" property we will illustrate in a moment that sits at the core of the proof of this extensional equation.

Reformulation of the problem:

We want to show that
$$
\lfloor\!\!\lfloor f \diamond l \rfloor\!\!\rfloor = (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor
$$

which basically states that if we try to hoist the $f$ outside of the brackets, then we have to turn it into a map.

Now, if we follow your original blueprint, your inductive hypothesis establishes that
$$
\lfloor\!\!\lfloor f \diamond x ::l \rfloor\!\!\rfloor = (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor)
$$

In order for this proof to proceed, you need to tame the term on the righthand side of the concatenation. But what would you want it to look like?

Well, recall that maps distribute into concatenations:
$$
(f \diamond l_1) +\!\!\!+ ~(f \diamond l_2) = f \diamond (l_1 +\!\!\!+~ l_2)
$$

which suggests that we might be able to get our equation into an amenable form if we can rewrite the second term so that it is of the form $(f \diamond) \diamond \cdot$.

Here's where our helper lemma comes in to save the day:

Lemma ("Commutativity"):You have to use finger quotes when you read the name of this lemma out loud.
$$
(f ~x ::) \diamond ((f \diamond) \diamond l) = (f \diamond) \diamond ((x ::) \diamond l)
$$
Proof: Structural induction on $l$. This is actually a pretty easy proof, so I'll leave it to the reader™. However, the core of this proof is essentially showing that
\begin{align*}
(f~x ::) \diamond ((f \diamond) \diamond a :: [...]) &= (f~x ::) \diamond ((f \diamond a) :: \underbrace{((f \diamond) \diamond [...])}_{\text{induction hypothesis}}) \\
&= \underbrace{(f~x :: f \diamond a)}_{\text{map distributivity}} :: (f~x ::) \diamond((f \diamond) \diamond [...])) \\
&= (f \diamond (x :: a)) :: (f~x ::) \diamond((f \diamond) \diamond [...])) \\
& \text{discharge the induction hypothesis} \\
&= (f \diamond (x :: a)) :: (f \diamond) \diamond ((x ::) \diamond [...]) \\
& \text{distributivity} \\
&= (f \diamond) \diamond ((x :: a) :: ((x ::) \diamond [...])) \\
& \text{distributivity} \\
&= (f \diamond) \diamond ((x ::) \diamond (a :: [...]))
\end{align*}
which concludes the proof of the lemma. $\square$

Finishing your inductive proof:

Once we have this gem, we can continue your structural induction proof.

\begin{align*}
\lfloor\!\!\lfloor f \diamond x ::l \rfloor\!\!\rfloor &= (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by the lemma} \\
&= (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f\diamond) \diamond ((x ::) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by distributivity of map} \\
&= (f \diamond) \diamond (\lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~ (x::) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by the definiton of } \lfloor\!\!\lfloor x :: l \rfloor\!\!\rfloor \\
&= (f \diamond) \diamond \lfloor\!\!\lfloor x :: l \rfloor\!\!\rfloor
\end{align*}

which satisfies your goal.

The equational acrobatics we've just performed seems a bit excessive, which is why I'm willing to bet that there's some elegant fusion law, recursion scheme, or some other representation (probably some categorical law given the nature of the problem) that nicely unwraps this proof. Unfortunately, AFAIK, I'm not aware of more elegant approaches. While this is a valid proof, it's somewhat unsatisfying. It is as much of a proof of this theorem as my performances of Taylor Swift is considered entertainment: it is technically correct, just not in the way that I intend it to be.


Genetic Algorithm Neural Network- Inputs for evolving creatures I made a GANN program for evolving creatures. The genes that get put into the GA for each ind are the weights that go into the neural net for each creature. The NN is a basic 1 hidden layer NN with bias neurons and it uses TANH so the weights are from -1 to 1. The GA uses .8 crossover rate (.3 elitism) and .003 mutation chance per gene/weight. Ranked selection is used and 1 point crossover.

The creatures go after food that spawns in a random location after pickup and there are also traps to avoid that done move. A food raises the fitness by 1 and the trap makes it lose 1 fitness point. They start at 1 fitness (health) and if they hit to many traps and get to 0 they die and their genes aren't used in the next evolution. But not many die anyway only like 5 to 10/50 per gen. There are 20 of both traps and food and 50 creatures. There are two sensors on the creatures. One on the left side about 30 degrees from the center face and one on the right. The inputs are each sensors dis from the closest food and from the closest trap.The outputs are 2 numbers. I pick which is highest get the abs value and multiply it by a max angle of 15 degrees and the creature rotates by that amount either right or left depending on which output neuron was the highest.

Before I added in the traps the creatures were very good at getting to food quickly and accurately. And they learned how to do it relatively quickly per test (after like 15 gens they were very good). Then I added in traps and just added the inputs that were the distances from the sensors to these traps just like with the food. With both inputs to food and traps they no longer learn. They just kind of make circles or do random stuff. They aren't dying that often (their fitness starts at 1 but if they hit food before they hit a trap they wont die just lose a fitness) but they aren't learning anymore. I tried normalizing (dividing by the env square side length) but didnt change anything. So is the issue with the inputs or something else?

If I understand well, your neural net have 4 inputs. But let's take this example :

The black circle is your creature
Grey circles are your sensors
Green circle is food
Red circle is a trap

Does the left sensor "see" the trap closer than the food ?

If yes, you're doing it wrong

A better way to do it would be to "simulate" real eyes, like this, where each sensor can only see what is in its field of view

Your neural net can take 2 inputs per sensor, as you did, with the distance to the closest food/trap it can see.

A second thing to try would be to only take in account the closest item for each sensor.

Another interesting thing to do would be to decrease the fitness over time, avoiding passive bots


Mimimum spanning tree with a constraint on number of certain types of edges I have the the following problem.

Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning tree such that we minimize total weight but also we can only use a maximum of $c$ edges in $B$.

I feel like this is just Prim/Kruskal with an additional condition in the main if condition, but is that correct? I think we can still use a greedy algorithm but do not know how to show correctness.

Let us take Kruskal's algorithm for an example. Apparently, OP refers to the adjusted version such that when we choose among edges of equal weight, we will pick the ones in $A$ before the ones in $B$ as long as at least one edge in $A$ is left available. If the MST we arrive in the end has no more than $c$ edges in $B$, then that MST is the output. Otherwise, the output is empty, indicating no such MST has been found. Let us name this algorithm $A$-favoured Kruskal's algorithm.

To prove that $A$-favoured Kruskal's algorithm will find a satisfying MST whenever there is one is, in fact, not trivial even if we have been enlightened with or especially when we are distracted by the  general techniques on how to prove greedy algorithm is correct.

Here goes my proof. Let us fix the weighted graph $G$ so that we will often be referring to $G$ implicitly. Let $R$ be a particular run of Kruskal's algorithm that produces $m$, an MST. Let $RA$ be a particular run of $A$-favoured Kruskal's algorithm that produce $ma$, another MST. ($RA$ may or may not be the same as $A$ and $ma$ may or may not be the same as $m$). Suppose $w_1\lt w_2\lt\cdots$ is the increasing sequence of all distinct edge weights. Break up the while loop of $R$ into smaller loops $R_1\lt R_2\lt\cdots$. For each $i$, $R_i$ iterates over all edges of weight $w_i$. For each such edge, $R_i$ adds it to the growing forest if it connects two different trees and ignores it otherwise. Let $F_i$ be the forest obtained at the end of $R_i$. Let $E_0=G$. For $i\gt0$, let graph $E_i$ has the same vertices as $G$  and all edges of $G$ except the edges of weights greater than $w_i$.

Using induction on $i > 0$, we can see that each connected component of $F_i$ (, which is a tree) is its corresponding connected component of $E_i$ minus some edges (the edges that were discarded because they did not connect different connected components(trees)). Let $g_i$ be the number of edges in $A$ of weight $w_i$ that are selected into $m$ during $R_i$. We can see that $g_i$ cannot bigger than $h_i$, the largest number of edges in $A$ of weight $w_i$ that can be added to $H_{i-1}$ without causing a cycle. In fact, $h_i$ is the decrease from the number of connected components in $E_{i-1}$ to the number of connected components in $E_{i-1}$ with all edges in $A$ of weight $w_i$ added. So $h_i$ depends only on $G$, $A$ and $i$. Note that $g_i$ will be $h_i$ if $R$ is actually a run of $A$-favoured Kruskal's algorithm, such as $RA$. So
$$\#\{\text{edges in } A \text{ and } m\} = \sum_{i}g_i
\leq \sum_{i}h_i = \#\{\text{edges in } A \text{ and } ma\}$$

Note that all MSTs can be found by Kruskal's algorithm. For a proof, you can check any MST is reachable by any MST algorithm with some minor exceptions. So we have shown that of all MSTs, $ma$ has the most edges in $A$. Since the number of edges in $ma$ is the same, $ma$ has the least edges in $B$. Proof is completed.

Indeed, we have proved more. Any run of $A$-favoured Kruskal's algorithm will produce an MST with the same number of edges with any given weight in $A$ and in $B$.


Why is the running time for BFS $O(b^{d+1})$? In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as being: $O(b^{d+1})$ with the following explanation:

Normally (or at least in my experience thus far in Algorithms) I've seen the running time of BFS to be $O(V+E)$ so why is it different here. Is this a special case?

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve.

The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits everything in the graph.  We measure the number of vertices ($V$) and the number of edges ($E)$, and the running time is measured in terms of these two parameters.  Also, the algorithms community usually analyzes the case where we run BFS until every vertex in the graph has been visited.  If this is the goal, and those are the parameters we care about, the running time to visit every vertex is indeed $O(V+E)$.

The artificial community typically considers a different scenario: we have an infinite or very large graph, and we're not going to visit all of it; we're going to visit only a tiny fraction of the graph, only as much as necessary until we can find one node with a particular property (a target node / goal node).  Think of the state space of a game like chess, or the 15-puzzle, or something like that.  In addition, in the cases that typically arise in artificial intelligence, usually the portion of the graph that we're going to visit looks sorta like a tree: each vertex has on average about $b$ edges leading out of it.  So in this situation, a bound like $O(V+E)$ is not helpful: it is a valid upper bound, but it is extremely loose -- the number of states (vertices) you actually need to visit might be much smaller than the total number of states (vertices) that exist.  So, in AI applications, we usually want a better estimate of the number of states visited.  That's what leads to the $O(b^d)$ estimate.

Both upper bounds are valid, in the situation where they apply.  But the two situations they're focused on are very different.  It's the same algorithm (BFS), applied in two different contexts... and because of some differences in the characteristics, it makes sense to measure its running time differently in the two settings.


Using a 2nd neural network to predict 1st neural network prediction error So for example, we are trying to predict the amount of rainfall in the afternoon base on continuous features such as humidity and temperature in the morning.

1st neural network: Regression neural network on features to give one output label which is a continuous value for predicted rainfall in the afternoon.

2nd neural network: Features will be the same as the 1st neural network. But now, the label will be the absolute difference between the 1st neural network predicted rainfall and the actual rainfall.

From this, we can train the 2nd neural network to recognise what particular set of features will result in the 1st neural network giving a 'bad' prediction and be more wary of that 'bad' prediction. In a way, this is like using another neural network to give the confidence level of the first neural network, solely based on the same features (the humidity and temperature in the morning).

I could not find much literature on this subject and am wondering if this idea makes sense in the first place? Perhaps stacking neural networks over each other is a bad idea because it compounds the error from one network to another?

I tried this with some data except my 2nd neural network is a classifier which classifies if the error is above a certain threshold (bad prediction) or below a certain threshold (good prediction).

However, from a few different model runs, it seems that my 2nd neural network usually gives a matthew's correlation coefficient of about 0. This means my 2nd neural network is as good as guessing whether the 1st neural network prediction is good or bad.

So I am not sure if the problem is the idea itself or that my model hyperparameters are bad.

More details: I used 10 fold cross-validation for the 1st model to get a predicted rainfall for all the data. Then I used another separate 10 fold cross-validation and a siamese neural network for the 2nd model to predict whether the 1st neural network prediction is good or bad.

It's not an unreasonable approach, but I suspect you'd need to define a custom loss function to make it work well.

I can also suggest two different, more sophisticated approaches: the bootstrap, or a variational neural network.

In the bootstrap, you train many classifiers (say, 100 of them); each is trained on a different random sample of the training set, and then you look at the distribution of outputs from these classifiers when you feed in the input $x$ to each of them.

In a variational network, instead of outputting a single number $y$ for the prediction in response to the input $x$, the network outputs two parameters $(\mu,\sigma)$, with the idea that the network is predicting a Gaussian distribution $\mathcal{N}(\mu,\sigma^2)$ as an approximation for $p(y|x)$.  Then you can use this to get a sort of confidence interval for the prediction, e.g., $[\mu-2\sigma,\mu+\sigma]$.  I'm not an expert on this, but I think a variational network is actually very close to what you suggested; we can think of it as two networks, one that outputs $\mu$ (your first network) and one that outputs $\sigma$ (your second network).  However, variational networks are trained with a special loss function.  In particular, if we have an instance $(x_i,y_i)$ in the training set, the loss for the network is the log likelihood $-\log p(y_i)$ where here $p(y_i)$ represents the probability of getting the output $y_i$ from a Gaussian distribution with parameters $\mathcal{N}(\mu,\sigma^2)$, where $\mu,\sigma$ are the two outputs from the network.  Since the Gaussian distribution has probability density function

$$p(y_i) = c e^{-(y_i-\mu)/2\sigma}$$

where $c$ is a constant.  Therefore, the loss function is

$$-\log p(y_i) = (y_i-\mu)/2\sigma + c'$$

where $c'$ is a constant that can be ignored.  Thus, I think you can think of the variational approach as being equivalent to your approach, but with a custom loss function chosen to be appropriate for what you're trying to achieve.


Chord protocol - How should I go about mapping nodes to placeholders on the ring? In the real world, how is a node mapped to the position on the ring,
Each nodes's IP address is hashed using SHA-1 hashing algorithm which will produce this hash - 73.128.154.69 hashed into 60CBFB98C9052A425D684A2C3D8D8D38424129A3.
This should have been in the range of 0 to (2^m) - 1 where m is the number of bits. I have the following questions -

How should I convert this hashed value into a number?
Will the IP address after leaving and re-joining the ring get the same  placeholder position?
Are placeholders or node positions ordered numbers at all?

Take the last m bits of the hash.  View it as a number in binary.  That's how you convert the hashed value into a number.  The position is a number.  That should answer your questions 1 & 3.

Now that you know how it works, you should be able to answer question 2 yourself.  If not, go back and read the original paper (especially Section IV.B), which should make this clear.


Visual programming tools, why don’t they work with the AST directly? I've found several open source visual programing tools like Blockly and friends, and other projects hosted at Github, but could't find any that work directly with the abstract syntax tree.

Why is that?

I'm asking because once I discovered that every compiler out there has a phase in the compilation process where it parses the source code to an AST, it was obvious to me that some visual programing tools could take advantage of this to give the programer ways to edit the AST directly in a visual way, and also to do the round trip from source to node-graph and then back again to source when needed.

For instance one could think that from the JavaScript AST Visualizer to an actual JavaSript visual programming tool there isn’t too much of a difference.

So, what am I missing?

Many of these tools do work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages and editors like it (Scratch, Pencil Code/Droplet, Snap!, GP, Tiled Grace, and so on).

Those systems don't show a traditional vertex-and-edge graph representation, for reasons explained elsewhere (space, and also interaction difficulty), but they are directly representing a tree. One node, or block, is a child of another if it is directly, physically inside the parent.

I built one of these systems (Tiled Grace, paper, paper). I can assure you, it is very much working with the AST directly: what you see on the screen is an exact representation of the syntax tree, as nested DOM elements (so, a tree!).

This is the AST of some code. The root is a method call node "for ... do". That node has some children, starting with "_ .. _", which itself has two children, a "1" node and a "10" node. What comes up on screen is exactly what the compiler backend spits out in the middle of the process - that's fundamentally how the system works.

If you like, you can think of it as a standard tree layout with the edges pointing out of the screen towards you (and occluded by the block in front of them), but nesting is as valid a way of showing a tree as a vertex diagram.

It will also "do the round trip from source to node-graph and then back again to source when needed". In fact, you can see that happen when you click "Code View" at the bottom. If you modify the text, it'll be re-parsed and the resulting tree rendered for you to edit again, and if you modify the blocks, the same thing happens with the source.

Pencil Code does essentially the same thing with, at this point, a better interface. The blocks it uses are a graphical view of the CoffeeScript AST. So do the other block- or tile-based systems, by and large, although some of them don't make the nesting aspect quite as clear in the visual representation, and many don't have an actual textual language behind them so the "syntax tree" can be a bit illusive, but the principle is there.

What you're missing, then, is that these systems really are working directly with the abstract syntax tree. What you see and manipulate is a space-efficient rendering of a tree, in many cases literally the AST a compiler or parser produces.


Question involving regular expressions I've been playing around with converting regular languages to regular expressions and was wondering if my thinking is correct for this one.

Question:

The set of all strings that begin or end with a doubled digit, either 11 or 00.  (In all cases assume the alphabet is {0,1}).

So far, I have: $((11+00) + (1 + 0)^*) + ((1+0)^*(11 + 00))$.

My thinking is that we want to take the union of:  the set of strings that start with 11 or 00 followed by any sequence of 1's and 0's AND the set of strings that end with 11 or 00 preceded by any sequence of 1's and 0's.

Sorry for the somewhat clunky writing.....still trying to get the hang of styling my questions.

You are thinking correctly but a small error is there in writing the regular expression. The regular expression is $r = ((00+11)(0+1)^*)+((0+1)^*(00+11))$.


The use of multiset ordering in proving termination Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?

As I understand the paper (and I was not familiar with it before) to prove termination of a program using the method of Floyd it is enough to find a function $\tau$ that maps the states of the program into some well-founded set $(S,\prec)$ such that this function is consistent with the program steps. Here consistency means that if a state $s$ follows $s^\prime$, then $\tau(s^\prime)\prec \tau(s)$.

Prior to Manna and Dershowitz the method of Floyd was used by mapping the states into the set of natural numbers or into the set of $n$-tuples thereof with lexicographic ordering (both sets are well-founded). The authors suggest a new source of well-founded sets for the Floyd method, that is the set of multisets of finite structures with multiset ordering and show how this can simplify termination proofs.

Note also that contrary to the sets of natural numbers and lexicographically ordered $n$-tuples, multisets ordering is only a partial ordering.


Bounds for Akra-Bazzi versus Master theorem I had my final exam today in an advanced algorithms course. In it there were two recurrence relations and I used the Akra-Bazzi theorem to solve them. After the examination I was discussing the problem with one of my colleagues and they apparently got a different bound using Master theorem. My question is which of this two bounds are tighter?

The recurrences were:

$1)\quad T(n) = 8T\left(\frac{(2n-1)}{4}\right)+n^3+n\log n$

$2)\quad T(n) = 3T(n/2)+n\log^2 n $

Now, correct me if I'm wrong but Akra-Bazzi gives 1) as $\Theta(n^3\log n )$ and 2) as $\Theta(n\log^2 n )$
Can somebody please verify 2) by Akra-Bazzi? I checked and regularilty condition doesn't hold for 2) .

Both methods give $\Theta$ type estimates. That is, the master theorem gives some estimate $T = \Theta(f)$, and the Akra–Bazzi theorem gives some estimate $T = \Theta(g)$. From the definition of $\Theta$ it immediately follows that $f = \Theta(g)$ and $g = \Theta(f)$, that is, the estimates are equivalent. I suspect either one of you was mistaken, or both bounds that you got, while seemingly different, are in fact equivalent.


What complexity does this 'how many ways to climb' algorithm have? I have a solution to the following problem:

  Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the
  time ($1 \leq m \leq n$), return all the ways you can climb the stairway.

  E.g. for $n = 3$, $m = 2$, the possible ways to climb are $[2,1], [1,2], [1,1,1]$

// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
  // store unfinished tracks; start with an initial track
  let iter = [{ val: [], sum: 0 }];
  let count = 0;

  // take the next track until there are none
  for (let i of iter) {
    for (let s = 1; s <= max; s++) {
      // append step value to the current track
      // assume constant complexity
      let val = [...i.val, s];
      let sum = i.sum + s;

      count++;

      if (sum === total) {
        // we've reached the top;
        // do not expand current track further
        out(val);
        break;
      }

      // add an unfinished track and start over
      iter.push({ val, sum });
    }
  }

  return count;
}

Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $m$ and $n$. For $m = 1$ the number of iterations is $n$, for $m = n$ it's $2^n - 1$.

Also, is there a canonical solution to this problem?

The solution is the recursive formula:

$S[k] = \sum_{i=1}^mS[k-i]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S[k-i]$


Find shortest path in undirected graph that goes through all vertices and returns to starting vertex I have an undirected weighted graph like this one

My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex without repeating a vertex.

Graph
1 3 time 5
3 2 time 5
2 4 time 5
4 1 time 5
4 3 time 4
1 2 time 5

Starting vertex 3
Path 1: 3->1->4->2->3
Path 2: 3->2->1->4->3
Time 1 and 2: 5+5+5+5=20

Path 3: 3->1->2->4->3
Path 4: 3->4->2->1->3
Time 3 and 4: 5+5+5+4=19 -> fastest

Is there a fastest way than DFS to solve the problem?

Travelling salesman problem looks almost the same but I can't repeat a visited vertex.

Going from vertex 3 to vertex 5 I can't do that
3 -> 2 -> 3 -> 1 -> 3-> 4 -> 3

A solution is: 3->1->2->4->3

That's my function:

private static List<HashMap<Integer,Integer>> graph = new ArrayList<>();

public static void dfs(int currentVertex,Stack<Integer> visited,long currentTime) {
    if(visited.size() == graph.size()-1) {
        if(!graph.get(currentVertex).containsKey(targetVertex)) {
            return;
        }

        currentTime += graph.get(currentVertex).get(targetVertex);
        if(currentTime < fastestTime) {
            fastestTime = currentTime;
        }
        return;
    }

    for (Map.Entry<Integer,Integer> vertex: graph.get(currentVertex).entrySet()) {
        if(!visited.contains(vertex.getKey())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}


Recursion Time Complexity (Half n' Half) This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:

Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
For each symbol $s_i$, check whether it appears less than $k$ times in $s$
If all symbols appeared at least $k$ times, return $n$
Otherwise, let $i$ be the first index such that $s_i$ appears less than $k$ times
Call the procedure recursively on $s_1,\ldots,s_{i-1}$ and on $s_{i+1},\ldots,s_n$, and output the maximum

Here is a C++ implementation:

int longestSubstring(string s, int k) {
        for (int i = 0; i < s.length(); i++) {
            if (count(s.begin(), s.end(), s[i]) < k) {
                string left = s.substr(0,i);
                string right = s.substr(i+1,s.size()-1);
                return max(longestSubstring(left,k),longestSubstring(right,k));
            }
        }
        return s.length();
    }

The count method runs in $O(n)$.

I'm new to asymptotic complexity, but from what I understand, "half n' half" recursion has time $T(n) = 2T(n/2)+f(n)$ where $f(n)$ is the time the rest of the execution takes. At this point, we'd induct, and get a general pattern. Then, given that we usually know $T(0)$ and $T(1)$, we can get an expression in $n$, which would be our time complexity.

Now, my problem is that my implementation doesn't split the string into exact halves (in the same way a BST traversal splits the input in halves, for example), so I can't really write $T(n/2)$, correct? Are $T(0)$ and $T(1)$, $O(1)$ and $O(n)$ respectively?

Is there, perhaps, a faster way to solve this problem? Leetcode says it runs in 0ms, but I find that dubious. It takes a longer time to execute than one of the highest upvoted Python implementations, which is supposedly $O(n)$.

I can offer one simple optimizations to your code.

At the moment your code will take $\Omega(n^2)$ time even on a string in which each symbol appears at least $k$ times. This can be avoided using counting sort: using a single pass, you can compute how many times each letter appears. If every letter appears either 0 or at least $k$ times, then the current string is good. This takes linear time.

(This uses the fact that it is known that all letters of the string are lowercase letters. If the letters are arbitrary, you can still speed this up by sorting the array.)

Even after this optimization, your code suffers from a problem. Suppose that $k = n/2 + 1$, and let the string consist of $n/2$ copies of a followed by $n/2$ copies of b (as an aside, you can immediately return 0 in this case – a further optimization). Your code will recurse on the substring $s_2,\ldots,s_n$, the on the substring $s_3,\ldots,s_n$, and so on, not giving up at any point. Therefore it will take time $\Theta(n^2)$ (or, without the first optimization mentioned above, $\Theta(n^3)$).

In order to avoid this, suppose that you found out that $s_i$ appears fewer than $k$ times. Find all occurrences of $s_i$, partition the string accordingly, and recurse on each such substring. This will guarantee that each substring won't have the letter $s_i$. Each time you recurse, you have one fewer letter appearing, and so the depth of the recursion tree is at most 26. Therefore the algorithm will run in linear time.


Language of decimal encodings of cubes is not regular Prove that the language that consists of cube numbers as strings is not regular.

I wanted to use pumping lemma but couldn't
$$0, 1, 8, 27, 64, 125, 216, \dots$$

Denote your language by $L$.
Suppose that the pumping length is $p$. Consider
$$
N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1,
$$
whose decimal encoding is
$$
w = 1 0^p 3 0^p 3 0^p 1 \in L.
$$
According to the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xz \in L$. Since $|xy| \leq p$, the part $xy$ lies within the prefix $10^{p-1}$. If $y$ contains $1$ then $xz$ has a leading zero, which is impossible (if you allow leading zeroes, consider $L \cap (1+9)(0+9)^*$ instead), so $y$ consists only of zeroes. Hence
$$
xz = 10^q 30^p 30^p 1,
$$
for some $q < p$,
which encodes the number
$$
n = 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1.
$$
If $xz \in L$ then $n$ is a cube. Since $n$ ends with $1$, necessarily $n = 10m + 1$ (you can check this directly by considering $0^3,1^3,\dots,9^3$), and so
$$
10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1 =
1000 m^3 + 300 m^2 + 30m + 1,
$$
which implies that
$$
(10^{p+q+2} + 3 \cdot 10^{p+1} + 3) 10^p =
(100 m^2 + 30 m + 3) m.
$$
Clearly $100m^2 + 30m + 3$ is divisible by neither $2$ nor $5$ (its units digit is $3$), and so $10^p$ must divide $m$. In particular, $m \geq m_0 := 10^p$. However, this is impossible, since $N = (10m_0 + 1)^3$, and $n < N$.


Negative cycle detection using Bellman-Ford and its correctness I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.

I have 2 doubts about the correctness of the algorithm:

Why are we relaxing (num of vertices - 1) times all the edges? Why not some finite number of times till earlier values and new values remain same?
The second for loop (lines 5,6,7 in algo image) is for detecting negative edge cycles. Then I have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction (if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative - page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]

But I am not able to visualise such an edge if I have some negative edge cycle from source vertex s. Please help me: how can such an edge exist?

If there are no negative cycles then you can indeed perform the relaxation until all values remain the same.
In the $i$-th round of relaxation you are ensured to have correctly computed all finite distances towards all vertices whose hop-distance from $s$ is at most $i$ (the hop distance is the number of edges in a shortest path).

Therefore stopping after the $(n-1)$-th iteration ensures that:

All finite distances have been correctly computed
The algorithm terminates on graphs with negative cycles.

Notice that there are graphs where all $(n-1)$ iterations are needed to properly compute the distances. E.g., a path.

Regarding 2), your question is not completely clear to me. In the proof there is no particular edge to visualize. The proof just shows that if it impossible for these two conditions to be simultaneously true:

There is some  negative weight cycle $C$.
No relaxation happens, i.e., $v.d \le u.d + w(u,v)$  for all vertices $v$ of the cycle. This is used in the second centered inequality.


Why selection sort will require $O(N)$ time As per the example given in this MIT OCW link URL  https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/

Why selection sort requires $O(N)$ time since the number of exchanges is at most N. Pls give example algorithm that prove this fact. Below is excerpt taken from same MIT OCW URL for reference

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires $O(N^2)$ comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, selection sort requires $O(N)$ time since the number of exchanges is at most $N$.

It is simpler and more correct to say: selection sort requires $O(n)$ exchanges (and this is optimal in the worst case).

That doesn't imply $O(n)$ time, unless the other operations take negligible time.
But from a theoretical standpoint, $O(n^2)$ is never negligible compared to $O(n)$.

In practice if a comparisons and related overhead takes $s$ seconds and an exchange and related overhead takes $e$ seconds, the total time will be

$$\frac{sn^2}2+cn=\left(\frac{sn}2+c\right)n.$$

This can be considered a linear behavior as long as $sn\ll c$. That could be true if the records are stored on a slow disk while the keys are cached in RAM.

This course plays a dangerous game with the Big-$O$ notation.


How are useless states created NFA to DFA So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA without creating any useless states?

Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $a$. If we make it determinsitic using the standard construction half of the states will be unreachable.
You ask, why does this happen? Look at the initial state $0$ of the original automaton. It has a loop for both $a$ and $b$. That means that in the powerset construction all next states will always contain state $0$ because the deterministic automaton collects the states of all paths from the original automaton. As a consequence all states without $0$ are uneachable.

It is possible "by hand" to avoid those unreachable states, by a step by step construction. Only consider staes that are reached and continue form those to the next possible states. A kind of depth-first construction will work.


Show the problem of a machine visiting infinitely many tape cells on some input is undecidable I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?

I am considering a reduction from the halting problem. Is this the right approach?

Based on my comments, I might as well make this an answer, and let the community decide whether it's right or not.

Suppose you could decide whether a TM visits an infinite number of cells on an input. Here's how to solve the Halting problem given this information:

Halts(TM, input)
1. if the TM visits an infinite number of cells for the input then return false
2. configurations = {}
3. while(true)
4.     configurations.add(non-blank tape area, TM head position, state)
5.     let the TM execute one step
6.     if state is halt accept or halt reject, return true
7.     if configurations.contains(non-blank tape area, TM head position, state) then return false
8. loop

This works because, if the TM doesn't visit an infinite number of cells, it visits some finite number of cells, $n$. The number of distinct configurations is therefore $|\Sigma|^n \times n \times |Q|$, and configurations.size() will never be bigger than this. By the pigeonhole principle, we must satisfy at least condition #7 in a finite number of moves. If none of the reached configurations enters a halting state, we never will; so we have to halt before we see the same configuration twice.


largest samples of set of random variables Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF.

We know that max of two independent random variables is: if $Z = max(X,Y)$

$pr(Z = k) = pr(X = k) pr(Y < k) + pr(X < k) pr(Y = k) + pr(X = k) pr(Y=k)$

Where in the above figure pr(Z=3) for instance is pr(X=3)*pr(Y=3)+ pr(X<3)pr(Y=3)+ pr(X=3)pr(Y<3) so (1)(1) + (1+1)(1) + (1)(1+1+1) =7.

My question how this operation has O(nm) timing complexity where n and m are the sample size of X and Y receptively or O(n^2) when both has n samples?

According to my calculations there is only 2 multiplications and n sums involve to generate each sample, so it should be o(n), right?

Yes, you are right; the PDF of $Z=\max(X,Y)$ can be computed from the PDFs for $X,Y$ in $O(n+m)$ time, using the approach you described.

In particular, it takes $O(n)$ time to compute $P(X<x)$ for each $x$ ($n$ sums), $O(m)$ time to compute $P(Y<y)$ for each $y$ ($m$ sums), and $O(n+m)$ time to then compute $P(Z=z)$ for each $z$ (3 products and 2 sums for each of the possible values of $z$).

Perhaps that paper was using a sub-optimal algorithm, or maybe it was just a mistake, or maybe the author didn't care about the difference between $O(n+m)$ vs $O(nm)$ and used an overly loose bound.


Potential function for stack problem Consider the follow operations on a stack of size at most $k$.

Push - insert element in the stack - actual cost 1

Pop - remove top element from the stack - actual cost 1

Copy - copy whole stack (but maintain the number of elements) - actual cost is the number of elements in the stack

Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.

What would be a suitable potential function for this problem?

A reasonable potential function here would be $C\ell$ or $C(k-\ell)$, where $\ell$ is the number of elements on the stack.

However, I don't think that the amortized cost can be bounded. Consider $k$ push operations followed by $M$ copy operations. The total cost is $k(M+1)$. If the amortized cost of push is $a$ and of copy is $b$, then $ka + Mb \geq k(M+1)$. Dividing by $M$ and letting $M\to\infty$, we obtain $b \geq k$.


Edit distance (Levenshtein-Distance) algorithm explanation I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo».

According to this site we'll get the result matrix:

What I don't understand is: In case of comparison the last «o» from «solo» with the first «o» of «oslo» will see the submatrix:

3 2
4 3

As far as I understand, in order to calculate the bottom right value, which is equal in this example to 3 of this submatrix, we'll get the min(3, 2, 4) + (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to 3 and not to 2?

You got the recursive definition wrong. It's

$\qquad\displaystyle d_{ij} =
  \min \begin{cases}
         d_{i-1, j}  + c_\mathrm{del}(b_{i}) \\
         d_{i,j-1}   + c_\mathrm{ins}(a_{j}) \\
         d_{i-1,j-1} + [a_j \neq b_i] \cdot c_\mathrm{sub}(a_{j}, b_{i}) \end{cases}$

where the $c_{\mathrm{op}}$ are fixed costs for the respective operations, all of which are $1$ here. You'll note that for alternatives one and two, insertion and deletion (which correspond to a vertical resp. horizontal step in the matrix), don't care if the current symbol matches any other -- you introduce a gap symbol, anyway!

Following this definition, clearly $2+1$ (insertion of $o$) results in the entry you highlight. Note that the alignment computed (implicitly) up until this point is

$\qquad\begin{array}{cccc}
  - & o & - & - \\
  s & o & l & o
\end{array}$


How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$? I am given an oracle $A$ that takes input samples from two distributions $\chi_1$  and $\chi_2$.

Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where $p_1 \neq p_2$.

In general, how can we use $A$ to construct a distinguisher to determine whether the input samples are from $\chi_1$ or $\chi_2$? And how good is the running time of such distinguisher?

Thank you very much! :)

Hint: Run $A$ on lots of samples $x_1,\ldots,x_n$ and compute the average $(A(x_1)+\cdots+A(x_n))/n$.


Is ecological bin packing NP-hard? The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as:

  Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, minimizing the number of bottle movements.

Specifically, we wish to decide on an allocation of colors to bins so that moving from the initial position to the "sorted" position requires the least number of bottle moves.  The bins are assumed to have infinite capacity.

For the problem as stated, one can brute-force check all $3! = 6$ permutations to see which has the fewest number of bottle movements.  However, for $N > 3$ colors of glass, $N!$ grows very large. Is there a way to solve this problem for general $N$ that runs in polynomial time?

Yes, this can be solved in polynomial time, for arbitrary $N$.  This is an instance of the assignment problem, for which polynomial-time algorithms are known.

You want to assign a color of glass to each bin, such that each bin gets exactly one color, and each color is assigned to exactly one bin.  The cost of assigning bin $b$ to color $c$ is the number of bottle moves needed to move all bottles of color $c$ that aren't currently in bin $b$, into bin $b$.  Therefore, this is an assignment problem.

(You can compute this cost function more efficiently as follows: the cost of assigning bin $b$ to color $c$ is the number of moves needed to move all bottles that aren't colour $c$ out of bin $b$.  Thanks to @David Richerby for this insight.)

The assignment problem can be solved using standard methods, e.g., the Hungarian algorithm or algorithms for min cost max flow.


Bottom-up Mergesort vs Natural Merge Sort I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort
However, I can't find much information regarding:

The algorithm(s) to achieve natural mergesort, and the pros and cons of each method
How natural mergesort compares to bottom-up mergesort (pros and cons of each w.r.t the other)

In short, I'm looking for resources that would teach me algorithms to do natural mergesort, and how to weigh it against the usual bottom-up mergesort

Natural Mergesort usually refers to Timsort. In terms of comparison to bottom-up mergesort, Timsort has $O(n)$ best-case running time where as bottom-up mergesort is at least $O(n\log n)$ on any input.
However, analysis of the worst-case running time of Timsort proves to be more tricky; an 2018 paper [1] establishes that its worst-case time complexity is $O(n\log \rho)$, where $\rho$ is the number of maximal monotonic sequences in the input array.
[1]: Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau, "On the Worst-Case Complexity of TimSort"