What is beta equivalence? In the script I am currently reading on the lambda calculus, beta equivalence is defined as this:

  The $\beta$-equivalence $\equiv_\beta$ is the smallest equivalence that contains $\rightarrow_\beta$.

I have no idea what that means. Can someone explain it in simpler terms? Maybe with an example?

I need it for a lemma following from the Church-Russer theorem, saying

  If M $\equiv_\beta$ N then there is a L with M $\twoheadrightarrow_\beta$ L and N $\twoheadrightarrow_\beta$ L.

$\to_\beta$ is the one-step relation between terms in the $\lambda$-calculus. This relation is neither reflexive, symmetric, or transitive. The equivalence relation $\equiv_\beta$ is the reflexive, symmetric, transitive closure of $\to_\beta$. This means

If $M\to_\beta M'$ then $M\equiv_\beta M'$.
For all terms $M$, $M\equiv_\beta M$ holds.
If $M\equiv_\beta M'$, then $M'\equiv_\beta M$.
If $M\equiv_\beta M'$ and $M'\equiv_\beta M''$, then $M\equiv_\beta M''$.
$\equiv_\beta$ is the smallest relation satisfying conditions 1-4.

More constructively, first apply rules 1 and 2, then
repeat rules $3$ and $4$ over and over until they add no new elements to the relation.


Given a vertex, find a path between it and each other vertex that minimizes the maximum weight in the path I'm revising for an upcoming exam and was wondering if someone could help me with a practice problem:

  We model a set of cities and highways as an undirected weighted graph $G = (V,E,l)$, where the vertices $V$ represent cities, edges $E$ represent highways connecting cities, and for every undirected edge $e = \{v, w\}\in E$ the number $\ell[e]$ denotes the number of litres of fuel that your motorcycle needs in order to ride the distance between cities $v$ and $w$.
  There are fuel stations in every city but none on the highways between the cities. Therefore, if the capacity of your motorcycle's fuel tank is $L$ litres, then you can only follow a path (a sequence of adjacent highways), if for every highway $e$ on this path, we have $L\geq \ell[e]$, because you can only refuel in the cities.

  Design an algorithm with a running of time of $O(m\log n)$ that, given an undirected weighted graph $G=(V,E,\ell)$ modelling a setting of cities and highways, and a city $s \in V$ as inputs, computes for every other city $v \in V$, the smallest fuel tank capacity $M[v]$ that your motorcycle needs in order to be able to reach city $v$ from city $s$.

I'm not sure how to solve this problem, but I do have a few ideas. I thought of possibly running Kruskal's algorithm since that would give me the MST of the graph. I'm not sure how I would then efficiently get the answer I need to produce.

Alternatively, I was thinking of using dynamic programming in some way since that's one of the things that we use a lot in the course, but I'm not really sure how to go about it.

Let $T = \{s\}$, and let $Q$ be a new empty priority queue. Insert each edge incident on $s$ in $Q$. While there are still nodes with $d$ from $s$ yet to be computed, extract and remove the minimum from $Q$.

If such edge connects a node $u$ in $T$ with a node $v$ not in $T$, add each edge incident on $v$ that still isn't in $Q$ to $Q$, then set $M[v]$ to $\max\{M[u], w(u, v)\}$.

Otherwise, disregard the extracted edge and extract more edges until you find a suitable one.

The overall complexity is $O(|E| \log |E|) = O(|E| \log |V|^2) = O(|E| \log |V|)$.

To informally prove correctness, we can observe that whenever we set $M[v]$ to a certain value $x$, we can certainly reach $v$ from $s$ with a path in which each edge weighs at most $x$. On the other hand, no better path exists, because we already gave each edge lighter than $x$ a chance to connect to $s$.


Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem? I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.

  Halting function: The Halt function takes an input a pair $<\alpha, x>$ and outputs 1 if and only if the TM $M_{\alpha}$ represented by $\alpha$ halts on input $x$ within a finite number of steps.

The undecidability of Halting function is proved by reduction from another undecidable function $UC$, which is defined as follows Book by Arora and Barak.

  $UC$: For every $\alpha \in \lbrace 0,1 \rbrace^{\ast}$, if $M_{\alpha}(\alpha) = 1$, then $UC(\alpha) = 0$; otherwise (if $M_{\alpha}(\alpha)$ outputs a different value or enters an infinite loop), $UC(\alpha) = 1$.

The undecidability of $UC$ is proved by the also well-known "diagonalization" technique. I can understand the technique. However, I am puzzling over a more basic problem involving the definition of $UC$.

  My Problem: The definition of $UC$ is based on the value of $M_{\alpha}(\alpha)$. Especially, it seem to be based on whether a Turing Machine halts on an input. However, the latter is undecidable (Worse still, it is undecidable due to the undecidability of $UC$!). In this sense, is the $UC$ function well-defined?

What is wrong with my opinion? How should I understand the definition of $UC$ and the relation between $UC$ and Halting Problem?

Thank for your help.

In classical logic it is possible to define a function which is not computable, and $UC$ is such a function. What probably confuses you is that you think that a function must always be given in a symbolic form, or as a set of instructions on how to compute it, or some such. But this is not necessary. Officially a function $f : A \to B$ is the same thing as a subset $F \subseteq A \times B$ satisfying the functionality condition:

  For every $x \in A$ there is exactly one $y \in B$ such that $(x,y) \in F$.

We may apply this to our situation to define $UC$ as the set of pairs
$$UC = \lbrace
((\alpha, x), d) \mid
(\text{$M_\alpha$ halts on $x$ and $d = 1$})
\lor
(\text{$M_\alpha$ does not halt on $x$ and $d = 0$})
\rbrace.$$
Even though nobody told us how to discover the output $d$ for a given input $(a, x)$, it is still the case that for every $(a,x)$ there is exactly one $d$. Indeed, if there were more than one then we would have a machine $M_\alpha$ which both halts and does not halt on input $x$. And if there were no such $d$, that would mean we have a machine $M_\alpha$ which neither halts nor not halts on input $x$.

In constructive logic one cannot define a non-computable function. And neither can one show that all functions are computable. So there $UC$ would not satisfy the functionality condition, and it would only define a partial function. But we could still talk about the fact that the Hlating problem is not decidable because the same classical argument still applies (we just avoid talking about $UC$). Assume there is a Turing machine $H$ such that:

$H$ halts on every input.
If $M_\alpha$ halts on $x$ then $H$ on input $(\alpha, x)$ outputs $1$.
If $M_\alpha$ does not halt on $x$ then $H$ on input $(\alpha, x)$ outputs $0$.

We now proceed with the usual diagonalization argument and construct a machine $B$ with a code $\beta$ such that $B(\beta)$ halts if, and only if, $H(\beta, \beta)$ outputs $0$. Everything here is perfectly constructive. I only took care never to assume that every machine either halts or not (such an assumption is implicit in the definition of $UC$).

So perhaps you should stick to constructive mathematics, and there will be fewer surprises for you.


Maximum Value Contiguous Subsequence I have stumbled upon this problem online:

  Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is maximized.

Now my solution is so:
I assume that the sequence is stored in an array.
We need 2 arrays under the original array, one is a flag array A and the other is a real number array B.

Take the first element as the subsequence we are searching for, put a 1 under it in A, and put the value of the element in it's index in B (which is right under it's index in A).
Go to the next element.
If it isn't negative, put a 1 under it in A, and put the sum of that element and the element before him in B.
If it's negative, put a 0 under it in A, and go to the next element, starting a new subsequence.

The complexity is O(n) time because I run on the whole sequence once.

Example:

Sequence: 4 33 -24 3 4 2 -5 6 19 -11 32 40 -30 5 6
Array A:  1  1   0 1 1 1  0 1  1   0  1  1   0 1 1
Array B:  4 37  13 3 7 9  4 6 19   8 32 70  40 5 11

My question is: is that the wanted solution? and does it really run in O(n) time?

Your algorithm does not yield the solution. An extension of your algorithm that follows will provide a solution.
You need to mark the extremes of consecutive 1's in the flag array (an obvious observation ). For example, the flag array is 1111101111 then you need to mark 0,5,9 indices (zero based) and for every pair of extremes you need to find the difference computed in prefix sum array. The number of marker indices are of the order of n. So number of pairs are of the order n^2.


Why do Computers use Hex Number System at assembly language? Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? Why it looked so beneficial to them?

Computers don't use the hexadecimal number system for assembly language. Assembly language, or rather machine code, uses base 256 (typically): instructions are encoded in units of bytes. When displaying machine code, it is customary to use octal or hexadecimal. The reason is that in many cases, the byte is further subdivided into bitstrings, and identifying these bitstrings is easier when using a base which is a power of 2. Hexdecimal is particularly compact since each byte can be encoded using exactly two hexadecimal digits.


What was Robert Floyd's algorithm for inserting brackets? In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other things, being discoverer of a simple program that would insert the brackets properly [into an arithmetic expression]."

What was this algorithm?

Based on the page for Floyd's award, it looks like the algorithm can be found in this paper.

The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today.
The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm used to parse Algol-60, commonly referred to as the "Shunting Yard Algorithm". Floyd's contribution was to formalise and extend the idea, making it into a practical general-purpose parsing technique.
Floyd's approach to parsing was highly influential on another young parsing investigator of the time, Donald Knuth, whose 1965 paper "On the Translation of Languages from Left to Right" introduced the LR(k) parsing algorithm, capable of parsing a much larger set of languages than operator precedence parsing. However, it was not until 1969 when Frank deRemer invented the computationally manageable LALR(1) algorithm described in "Practical Translators for LR(k) languages" that Knuth's discovery moved out of the theoretical realm and into practical compiler construction.
Floyd's 1961 paper "An algorithm for coding efficient arithmetic operations", cited in the OP, was not about parsing ("inserting brackets properly") but rather about efficiently ordering the computation of the parsed expression so as to maximize the use of scarce CPU resources, based on the very limited CPU architectures common at the time. Modern CPU architectures demand different algorithms, but parts of Floyd's 1961 algorithm can be found in simple optimizations for minimising the stack size in stack-based virtual machines (or, equivalently, the number of temporaries required in three-address-code).

For reference, a quick summary of Floyd's operator precedence algorithm. The algorithm takes as input a precedence grammar $G$, which is a context-free grammar with the property that no right-hand side contains two consecutive non-terminals. (This definition allows unit productions and null productions; in practice, these would usually be removed before proceeding since they do not participate in the parsing algorithm.)
As usual, we will write $G = \langle N, T, P, S\rangle$, where $N$ is the set of nonterminal symbols, $T$ the set of terminal symbols, $P \subset N \times (N \cup T)^*$ the set of productions and $S \in N$ the target (start) symbol. We will use uppercase letters to represent symbols in $N$, lowercase letters to represent symbols in $T$ and Greek letters to represent sentences which are elements of $(N\cup T)^*$. We write $\alpha \Rightarrow \beta$ if $\alpha$ derives $\beta$ (that is, $\alpha = \alpha_1 A \alpha_3$ and $\beta = \alpha_1\alpha_2\alpha_3$, where $A\rightarrow\alpha_2 \in P$). Also, we write $\Rightarrow^+$ and $\Rightarrow^*$ for the transitive closure and reflexive transitive closure of $\Rightarrow$.
Then we define three precedence relations over $T$: $\lessdot$, $\doteq$ and $\gtrdot$ , defined as follows:
$a \lessdot b \text{ if } A\rightarrow\alpha a B \beta \in P \text{ and either } B\Rightarrow^+b\gamma \text{ or } B\Rightarrow^+Cb\gamma$
$a \gtrdot b \text{ if } A\rightarrow\alpha B b \beta \in P \text{ and either } B\Rightarrow^+\gamma a \text{ or } B\Rightarrow^+\gamma aC$
$a \doteq b \text{ if either } A\rightarrow\alpha a b \beta \in P \text{ or } A\rightarrow\alpha a C b \beta \in P $
For an intuition about these symbols, think of a derivation being written with $\langle$ and $\rangle$ surrounding the strings replacing each nonterminal. Then $a\lessdot b$ holds if there is such a derivation where $b$ follows $a$ after a sequence of $\langle$s possibly followed by a single nonterminal. (Note that the operator property guarantees that there could not be two consecutive nonterminals.) In other words, ignoring nonterminals, $b$ is the first terminal in a reduction following $a$. $\gtrdot$ is analogous: $b$ is the first terminal following a reduction whose last terminal was $a$. (Again, the operator property guarantees that $b$ is not preceded by a nonterminal, since a nonterminal cannot follow a reduction.) $a\doteq b$ holds if $a$ and $b$ are consecutive terminals in a production, possibly separated by a (single) nonterminal.
Now, if the three precedence relations $\lessdot$, $\gtrdot$ and $\doteq$ are disjoint, we call $G$ an operator precedence grammar.
For simplicity, we will parse the augmented grammar
$$G' = \langle N\cup\{S'\}, T\cup\{\#\},P\cup S'\rightarrow S\#, S'\rangle$$
where $\#$ is some symbol not in $T$. It's easy to verify that $a\lessdot \#$ for every $a \in T$ and that there is no other precedence relation involving $\#$. We also add a $\#$ to the end of the input. Then we can parse the input as follows:

Create a parser stack $S$ consisting only of the symbol $\#$.

For each input symbol $b$ in turn, from left to right:

While $TOP(S) \gtrdot b: \;POP(S)$
If $b = \#$ and $top(S) = \#$, $ACCEPT$ the input
If $TOP(S) \lessdot b \text{ or } TOP(S) \doteq b: \;PUSH(S, b)$. Otherwise, $REJECT$ the input.

In practice, we'll actually want to record the derivations discovered by this algorithm. If we $POP$ the stack in step 2.1, the popped symbols (both terminals and nonterminals) are accumulated into $X$, and just before we continue with step 2.2, we find the production in $P$ whose right-hand side is $X$, and output that production as a derivation step. If there is more than one such production, then we need some auxiliary algorithm to decide which one to use; usually, we sidestep the problem by requiring that the right-hand sides be unique. (This is also why it's common to eliminate unit and null productions, because the Floyd algorithm provides no clue whatsoever about when to insert their derivation steps.)

Like many others, I think Floyd's contribution to parsing theory was fundamental. But it is important not to be seduced by the beautiful simplicity of his algorithm. As Floyd himself noted, it suffers from two important issues:

It is not sufficient to parse many programming languages, whose grammars cannot conveniently be written as operator grammars with unique right-hand sides or do not yield disjoint precedence relations.

The fact that a string is accepted by the algorithm does not guarantee that the string is accepted by the grammar. Many syntactically invalid strings are accepted and must be filtered out using other algorithms.

Floyd's later work, including his investigation into bounded-context grammars, sought to overcome these shortcomings.


What does it mean to be "closed" under beta reduction? I am reading the paper Compiling with Continuations, Continued, and in section 2.4, Comparison with ANF, the author draws attention to the fact that ANF is not closed under beta reduction. The snippet of text in question follows:

  As Flanagan et al. (1993) suggest, the “back end of an A-normal form
  compiler can employ the same code generation techniques that a CPS
  compiler uses”. However, as we mentioned in the Introduction, it is
  not so apparent whether ANF is ideally suited to optimization. After
  all, it is not even closed under the usual rule for β reduction (λx.A)
  v → A[v/x].

What does the author mean by this last sentence?
(My guess is that he means ANF beta reduction can introduce new, unbound variables into the reduced term. If that is the case, I am having a hard time visualizing when this would occur and would appreciate outside confirmation that my interpretation is correct.)

The claim is that after applying β-reduction to an expression in A-normal form you can be left with an expression no longer in A-normal form.

The only explicit definition I can find of A-normal form is not consistent with the definition Kennedy seems to be (implicitly) using in this paper.  Wikipedia defines A-normal form as the subset of lambda calculus expressions where only constants, $\lambda$-terms, and variables can be arguments of function applications, and then (vaguely) says that results of non-trivial expressions must be captured by let-bound variables.

That is: f(g(x)) is not in A-normal form because the argument to the application of f is another application (g(x)) rather than a constant, $\lambda$-term, or variable.  This expression in A-normal form would be something like let y=g(x) in f(y).

Kennedy uses the vague "definition"

  a let construct assigns names to every intermediate computation. (Section 1.1.ANF).

But then in Section 1.2 he gives an example of an A-normal form not being preserved under β-reduction

  Consider the ANF term let x = (λy.let z = a b in c) d in e.  Now naïve β-reduction produces let x = (let z = a b in c) in e which is not in normal form.  The ‘fix’ is to define a more complex
  notion of β-reduction that re-normalizes let constructs (Sabry and
  Wadler 1997), in this case producing the normal form let z = a b in (let x = c in e).

So apparently Kennedy's variant of A-normal form places some kind of restriction on what can be in the assignment part of a let clause, but I can't figure out what (or why) that restriction is.  In addition to Kennedy's paper you linked, I looked in several of his references:

  Amr Sabry; Philip Wadler: A reflection on call-by-value. ACM T. Prog. Lang. and Sys. (TOPLAS), 19(6):916-941, 1997.

  Amr Sabry; Matthias Felleisen: Reasoning about Programs in Continuation-Passing Style. Lisp and Symbolic Computation 6(3-4):289-360, 1993.

  Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.; Felleisen, Matthias: The Essence of Compiling with Continuations. Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation, (PLDI):237-247, 1993.


How to state that a complexity bound does not depend on a given parameter size? I am often ill at ease with Landau (Big O) notation, because it seems
often to be abusing mathematical notation. The best example is the use
of the equal sign to express a set membership. And this can be
misleading.

I have an algorithm that is dependent on two parameters $n$ and $m$,
which are the respective sizes of the two pieces of data it works on,
like (for example) in the case of a substring search, where you have
the size $n$ of the string being searched and the size $m$ of the
pattern to be found.

I want to express that the algorithm is $O(n)$, but with a constant
that is independent of the value of $m$.

A simple example is the recognition of a regular set, which is linear
in the size of the input string, independently of the size of the
regular expression defining the regular set, provided it has been
compiled into a DFA (which is supposed to be amortized on many
recognitions). This is usually implicit, but can I make it explicit when it is less obvious, or less well known.

The problem seems to be that people will often write $f(n)\in O(g(n))$
to mean that ultimately $|f(n)|\leq k\cdot |g(n)|$ even when $k$
actually depends on $m$. I realize that this depends on how you look
at the problem, and whether you consider that the parameter of size
$m$ is part of the data.

But then, how can one state unambiguously and clearly, but without
being too verbose, that, though the size $m$ parameter is part of the
data, the algorithm is $O(g(n))$ independently of $m$, i.e. the same
constant $k$ can be used even though $m$ may grow arbitrarily? Is there a notation or terminology for it?

Is there a better way recommended by HABON (the High Authority on Big
O Notation)?

The usual convention is to state upfront that your big O notations are with respect to $n$, and that whenever the constant depends on some parameter $m$, then you write $O_m(\cdot)$.

If in another paper you are fine with allowing the constant to also depend on the parameter $m$, then instead you state upfront that your big O notations are with respect to $n$, and the underlying constant could depend on $m$. Then you can use Luke Matheison's suggestions that if in some case your big O doesn't depend on $m$, then you mention that in that case the underlying constant doesn't depend on $m$; but that could be more confusing than the convention in the preceding paragraph.


What are some applications of binary finite fields in CS? I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F_2}$, are used in CS in some places such as circuit theory [1].

  What are some key applications of finite fields in CS?

I am also looking for uses of $\mathbb{F_{2}^n}$ which Mathworld shows can be represented as binary vectors.

[1] Noga Alon and Gil Cohen. On Rigid Matrices and Subspace Polynomials. Electronic Colloquium on Computational Complexity, Report No. 133 (2012).

Finite fields come up in many places. Here are just a few examples:

The Razborov-Smolensky polynomial method.
Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication.
List decoding - codes like Reed-Muller are algebraic codes.
Algebraization, the method used to prove IP=PSPACE.
Elliptic curves over finite fields are used in cryptography.


What is a conventional format for presenting algorithms? I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format.

I've been searching all over the web for the conventional structure of an algorithm with little luck. Can someone tell me the conventional format of an algorithm or any specification from IEEE for writing algorithms?

There is no such thing as  the "format" for algorithms. A general agreement¹ is to use pseudocode, i.e. code that abstracts from the particulars of specific programming languages, machines and/or libraries.

The most important thing is to be consistent.
If you want to follow a specific style, I recommend you pick up some textbooks on algorithms and/or data structures and follow the style you like best.

Some kinds of pseudocode have specific package support in LaTeX, e.g. clrscode, algorithms or pseudocode. For help with these go to tex.SE.

As long as you publish about algorithms as scientist. Articles featuring concrete technology frequently use real code, for better or worse.


Characterisation of Turing completeness? I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language.

For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). That gives an easy way to say if a language is Turing complete, as soon as we've found out that it is imperative.

Hence my question is there any similar, characterization of Turing completeness which would work for any language?

It seems very unlikely that there is any useful characterization other than the definition. Any such characterization would have to deal with all kinds of programming languages (imperative, functional, declarative and everything else) along with, assuming the claims from the Wikipedia article you link are correct, Minesweeper, Conway's game of Life and Magic the Gathering.

If you did have a characterization, it would probably be no easier to apply that characterization than to just apply the definition.


Is this a well founded inductive type? Can I express this in Coq? the standard List type in Coq can be expressed as:

Inductive List (A:Set) : Set :=
  nil : List A
| cons : A -> List A -> List A.

as I understand, W-type express a well-founded tree of elements of this type. so, what if nil is not qualified by A? i.e. we have:

  for all A: Set nil : List A

instead of

  for all A: Set nil A: List A

is this a correct W-type? can I express this in Coq?

You have misunderstood why A stands there in the definition of list.

Let us first look at how we might define lists of booleans:

Inductive ListBool : Set :=
  | nilBool : ListBool
  | consBool : bool -> ListBool -> ListBool.

And here is how we might define lists of natural numbers:

Inductive ListNat : Set :=
  | nilNat : ListNat
  | consNat : nat -> ListNat -> ListNat.

As you can see the nilBool and nilNat are constants that do not depend on any parameters. It is boring to define lists of booleans, lists of natural numbers, lists of lists of booleans, etc. Coq allows a parametrized definition of lists in which the List type itself takes a parameter A as input, to give lists of elements of type A. This is defined as you wrote:

Inductive List (A : Set) : Set :=
  | nil : List A
  | cons : A -> List A -> List A.

In the nil clause we have List A. Here A is the argument to List, it is not an argument to nil. If we wrote just List then Coq would ask "list of what"? For a similar reason the cons constructor has two occurences of List A.

Let me put it another way. The type of ListNat is Set. The type of List is Set -> Set. So we have to apply List to a set before we get a list.


Are these production rules for a formal grammar? I have a question on if production rules of a formal grammar are being specified correctly.  Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states each rule has the form:
$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*} \implies (\Sigma \cup N)^{*}$
How can each rule have this form when each rule is a subset of the above arguments to the implication symbol?  Should quantification and the $\in$ symbol be used to specify each rule?  Thanks

The use of notation in that statement might be confusing.  A grammar is a rule of the form "something $\to$ something", where the something on the left is a string of symbols containing at least one non-terminal symbol, and the something on the right is a string of symbols.
For instance, $A \to BcD$ would be a valid rule, as would $AB \to BDeeF$, or $aAcE \to b$.
If you read the very next sentence after the one you quoted, it explains the meaning of the part you didn't understand, in different words.  It says "That is, [...]" (you can read the rest yourself).  If you don't understand one sentence, in the future I suggest you keep reading a little further to see if you can work it out from context.


Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n)) I  have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? I'm lost..

Let $d(n) = 2n$ and $e(n) = n$. Then
$$d(n)-e(n) = n.$$
Since $d(n) = O(n)$ and $e(n) = O(n)$, we have that $$f(n) = g(n) = n,$$
so
$$O(f(n)-g(n)) = O(n-n) = O(1),$$
and clearly $$n \neq O(1).$$


Is there a bound on possible Dead state in a minimized DFA I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?
Intuitively, I am thinking that it is at most one, because if other state is there from where accept state is not reachable, the minimization would merge the states, because it is serving no more purpose than the other dead state.
Is my intuition true?

If you allow the DFA to be trimmed, then you can delete ALL dead states. If you want the DFA to be complete, then the minimized DFA will indeed have at most one dead state.
The reason is that minimizing leads you to merge nondistinguishable states, that is equivalent states in the Myhill-Nerode equivalence relation (here the definition is given for words and languages, but it can be extended to automata).
Two states $q_1, q_2$ are distinguishable if there exists a word $u$ such that $\delta^*(q_1, u)$ is final and $\delta^*(q_2, u)$ is not (or the converse). If $q_1, q_2$ are two dead states, then $\delta^*(q_1, u)$ can never be final (and same for $q_2$), so $q_1, q_2$ will never be distinguishable.


Counting restricted partitions Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$:
$$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq \frac{N}{2} $$

Two partitions are considered distinct if any of the summands has distinct values in them. For example, if $N = 4$ and $S = 3$ then there are 6 possible partitions:
$$(1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2, 0), (2, 0, 2), (0, 2, 2)$$

I've derived a dynamic programming solution. Let $d_{ns}$ be the number of above defined partitions of number $n$ with $s$ summands (each not greater than $\frac{N}{2}$). Then
$$ d_{0s} = 1, ~~~ s \geq 0 $$
$$ d_{n0} = 0, ~~~ n > 0 $$
$$ d_{ns} = \sum_{k = 0}^{\max \left(n, \frac{N}{2} \right)}d_{n-k,s-1}, ~~~ sn > 0 $$

It works fine but i consider this approach to be too slow from algorithmic point of view. It requires roughly $O(N^2 S)$ operations.

So here's my question. Can this computation be done faster? Perhaps via some other recurrence or some smarter way to fill the dynamic programming table for recurrence described above.

First, let us note that the number of ways to write $N$ as a sum of $S$ non-negative integers is exactly $\binom{N+S-1}{N}$. Indeed, the partition $N=x_1+\cdots+x_S$ corresponds to the string $\ast^{x_1}|\ast^{x_2}|\cdots|\ast^{x_S}$ (where $\ast^x$ means $x$ many stars), which contains $N$ stars and $S-1$ bars, and conversely any such string corresponds to a partition.

In your case you have the additional constraint that all $x_i$s are at most $N/2$. Note that at most one $x_i$ can be more than $N/2$. If $x_i > N/2$, then the number of ways to fill the rest of the $x_j$s is exactly $\binom{N-x_i+S-2}{S-1}$. Therefore the number of ways to write $N$ as a sum of $S$ non-negative integers which are at most $N/2$ is
$$
\binom{N+S-1}{S-1} - S\sum_{x=\left\lceil \frac{N+1}{2} \right\rceil}^N \binom{N-x+S-2}{S-2} =
\binom{N+S-1}{S-1} - S\sum_{y=0}^{\left\lfloor \frac{N-1}{2} \right\rfloor} \binom{y+S-2}{S-2} =
\binom{N+S-1}{S-1} - S \binom{\left\lfloor \frac{N-1}{2} \right\rfloor+S-1}{S-1}.
$$
You can calculate this closed form using $O(S)$ arithmetic operations.


Conditions for applying Case 3 of Master theorem In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this.
$a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $T$ is $T(n) = a T(n/b) + f(n)$ for $n=b^i$, $i>0$.

For the third case, we have $f(n) = \Omega(n^{\log_ba +\epsilon})$ for some fixed $\epsilon>0$ and that $ af(n/b)\leq cf(n)$ for fixed $c<1$ and for all sufficiently large $n$. In this case, $T(n) =\Theta(f(n))$ since $f(n) = \Omega(n^{\log_ba +\epsilon})$.

I was wondering if the condition that $f(n) = \Omega(n^{\log_ba +\epsilon})$ is unnecessary since the regularity condition $ af(n/b)\leq cf(n)$ for all $n>n_0$ for fixed $c<1$ and for some $n_0$ implies that
$$
\begin{align*}
f(n)&\geq m\left(\frac{a}{c}\right)^{\log_b(n/n_0)} \text{ where } m=\min_{1\leq x\leq n_0}{f(x)}\\&\ge\left(\frac{n}{n_0}\right)^{\log_b(a/c)}=\Theta(n^{\log_ba +\log_b(c^{-1})})=\Theta(n^{\log_ba +\epsilon}).
\end{align*}
$$
This will hold as long as $f(n)$ is non-zero. Hence $f(n)=\Omega(n^{\log_ba +\epsilon})$.
Therefore we merely need to add the condition that $f(n)$ is positive for all but finitely many values of $n$ for case 3. Am I correct about this?

Yes, your sharp observation is completely correct.

To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$.
(Regularity implies lower-bounded by a greater-exponent polynomial.) Let $a\geq1$, $b>1$ and $f$ be a nonnegative function defined on exact powers of $b$. Suppose $af(\frac nb)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.
Proof. There exists some $n_0>0$ such that $af(\frac nb)\leq cf(n)$ and $0 < f(n)$ for all $n\ge n_0$. We can assume $n_0$ is an exact power of $b$ since, otherwise, we can replace $n_0$ by $b^{\lceil\log_b{n_0}\rceil}$.
Let $n\ge n_0$ be an exact power of $b$. So $n = n_0b^m$, where $m=\log_b\frac n{n_0}$ is an integer since both $n$ and $n_0$ are exact powers of $b$.
Applying $af(k/b)\leq cf(k)$ multiple times, we get
$$f(n) \ge \frac acf(\frac nb) \ge (\frac ac)^2f(\frac n{b^2})\ge \cdots \ge (\frac ac)^mf(\frac n{b^m})=(\frac ac)^mf(n_0)$$
Since
$$(\frac ac)^m=(\frac ac)^{\log_b\frac n{n_0}} =(\frac n{n_0})^{\log_b\frac ac}=(\frac n{n_0})^{\log_ba-\log_bc}=c_0n^{log_ba+\epsilon}$$
where $\epsilon=-\log_bc > 0$ and $c_0=(\frac1{n_0})^{log_ba +\epsilon}$ are two constants, we have
$$f(n) \ge c_0f(n_0)n^{log_ba +\epsilon}.$$
So,
$$f(n)=\Omega(n^{log_ba +\epsilon}).\quad \checkmark$$

What happens if $n$ is not necessarily an exact power of b?  The same result will hold if we replace $\frac nb$ by $\lfloor \frac nb\rfloor$ or $\lceil \frac nb\rceil$.  The following is a version when $\lfloor \frac nb\rfloor$ is used.
Let $a\ge1$, $b>1$ and $f$ be a nonnegative function defined on positive integers. Suppose $af(\lfloor \frac nb\rfloor)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.


Is $\{\Theta(f)|f:\mathbb{N}\rightarrow\mathbb{N}\}$ Dedekind-complete? Let $\Theta$ and $o$ be defined as usual (Landau-notation).
For two equivalence classes defined by $\Theta$ we define
$$\Theta(f) <_o \Theta(g) :\Leftrightarrow f \in o(g)\qquad.$$
Let $$\mathbb{F}:= \{\Theta(f)\mid f:\mathbb{N}\rightarrow\mathbb{N}\}$$

My question:
Is $\langle \mathbb{F},<_o\rangle$ Dedekind-complete, i.e. given a set $F\subseteq \mathbb{F}$ with an upper bound $f_u,\forall f \in Ff\in o(f_u)$ are there $f_\inf$ and $f_\sup$ s.t.
$$\forall \Theta(f)\in F: \Theta(f_\inf) <_o \Theta(f) \qquad{(1)}$$
$$\forall g: (g\text{ fulfills (1)} \Rightarrow g \in o(f_\inf))$$

($f_\sup$ is defined analogously)?

Note: We don't need to assume a lower bound, since there is no infinite strictly decreasing series of $n \in \mathbb{N}$, i.e. $\Theta(0)$ is always a lower bound.

Background: I'd like to consider $\inf \{f \mid L \in N/DTIME/SPACE(f)\}$ for some Language $L$, but that only makes sense if such a (class of) function(s) exist(s).

Let $F$ be the set of all functions $f(n)$ such that $\sum_n f(n)$ diverges. Then $F$ is bounded from below by $f(n) = 1/n^2$ (for example), but there is no infimum: for every divergent sequence, you can find a sequence which diverges more slowly. This is a classical result of Hausdorff.

Similarly, if $F$ is the set of all functions $f(n)$ such that $\sum_n 1/f(n)$ converges, then $F$ is bounded from above by $f(n) = n$, but there is no supremum since for every convergent sequence you can find a convergent sequence which grows much faster.

Edit: This paper (among others) provides a proof of these claims.


How Does Populating Pastry's Routing Table Work? I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify.

Disclaimer: I'm not a computer science student. I've taken precisely two computer science courses in my life, and neither dealt with anything remotely complex. I've worked with software for years, so I feel I'm up to the implementation task, if I could just wrap my head around the ideas. So I may just be missing something obvious.

I've read the paper that the authors published [1], and I've made some good progress, but I keep getting hung up on this one particular point in how the routing table works:

The paper claims that

  A node’s routing table, $R$, is organized into $\lceil \log_{2^b} N\rceil$
  rows with $2^b - 1$ entries each. The $2^b - 1$ entries at
  row $n$ of the routing table each refer to a node whose nodeId shares
  the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th
  digit has one of the $2^b - 1$ possible values other than the $n + 1$th
  digit in the present node’s id.

The $b$ stands for an application-specific variable, usually $4$. Let's use $b=4$, for simplicity's sake. So the above is

  A node’s routing table, $R$, is organized into  $\lceil \log_{16} N\rceil$ rows
  with $15$ entries each. The $15$ entries at
  row $n$ of the routing table each refer to a node whose nodeId shares
  the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th
  digit has one of the $2^b - 1$ possible values other than the $n + 1$th
  digit in the present node’s id.

I understand that much. Further, $N$ is the number of servers in the cluster. I get that, too.

My question is, if the row an entry is placed into depends on the shared length of the key, why the seemingly random limit on the number of rows? Each nodeId has 32 digits, when $b=4$ (128 bit nodeIds divided into digits of b bits). So what happens when $N$ gets high enough that $\lceil\log_{16} N\rceil > 32$? I realise it would take 340,282,366,920,938,463,463,374,607,431,768,211,457 (if my math is right) servers to hit this scenario, but it just seems like an odd inclusion, and the correlation is never explained.

Furthermore, what happens if you have a small number of servers? If I have fewer than 16 servers, I only have one row in the table. Further, under no circumstances would every entry in the row have a corresponding server. Should entries be left empty? I realise that I'd be able to find the server in the leaf set no matter what, given that few servers, but the same quandary is raised for the second row--what if I don't have a server that has a nodeId such that I can fill every possible permutation of the nth digit? Finally, if I have, say, four servers, and I have two nodes that share, say, 20 of their 32 digits, by some random fluke... should I populate 20 rows of the table for that node, even though that is far more rows than I could even come close to filling?

Here's what I've come up with, trying to reason my way through this:

Entries are to be set to a null value if there is not a node that matches that prefix precisely.
Empty rows are to be added until enough rows exist to match the shared length of the nodeIds.
If, and only if, there is no matching entry for a desired message ID, fall back on a search of the routing table for a nodeId whose shared length is greater than or equal to the current nodeId's and whose entry is mathematically closer than the current nodeId's to the desired ID.
If no suitable node can be found in #3, assume this is the destination and deliver the message.

Do all four of these assumptions hold up? Is there somewhere else I should be looking for information on this?

Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems by A. Rowstrong and P. Druschel (2001) -- download here

The idea of a routing table in Pastry (and all structured P2P networks) is to minimize its size, while guaranteeing a quicker routing.

The routing algorithm of Pastry goes as follows:

Step A. A node u searches for an object A by firstly looking it up in its leaf set.
Step B. If it was not available, then the query is forwarded to a known node that shares "a number of prefixes with $A$ that is at least larger than what node u shares with A".
Step C. If such a record is not found, then the query is forwarded to a node in the leaf set that is numerically closest to $A$.

This is why a node $u$ stores addresses of nodes organizes its table as follows:

1.Each record in row $i$ of the routing table of node $u$ is a node identifier that shares $i$ prefix bits with the identifier of $u$.

2.The $(i + 1)^{th}$ bit of the records of a row $i$ is unique and is taken from the set $\{0, …, 2^{b} – 1\}$.

Example in  a typical scenario:
if u address is 1111 and object $A$ has identifier 4324: then here is what will happen: (we assume that it is of the base of 4. (i.e. addresses are from [1-4][1-4][1-4][1-4]).

Node $u$ shares 0 prefix with object $A$. Therefore, it looks in row 0.
According to rule 2 above, node $u$ stores addresses of nodes 1XXX, 2XXX, 3XXX, 4XXX, where X is a "dont-care" value. The closest among these nodes to $A$ is 4XXX. - Let's say this 4XXX is actually 4013. Then $u$ forwards to $u _1$ with address 4013. Now you are going to repeat the same thing again at node $u _1$ with address 4013.

To make it simpler, here is again an example of how it will go in 4013. $u _1$ will first look for the size common prefix between 4013 and 4324 which is 1. So it goes to row 1, which contain values such that 41XX, 42XX, 43XX, 44XX. The closes among them to $A$ is 43XX. - if this was 4331 then it will be forwards toward it.

The maximum number of hops here in is 4 hops (XXXX) ! in Pastry terms, it is $log_{2^b}$. So it is reduced as $b$ increases. But the size of the rows which are $2^b$ will increases ! -- so the authors said that $b$ = 4 is a good balance !

Practical scenarios are usually not typical as that. There may be situations in which there are not many nodes in the network. this is why we follow step C above. - However, what you need to guarantee to make this algorithm correct is that each node be connected to the closest two nodes to it (in term of identifiers). This will form a ring of ordered nodes [e.g. 1->3->4->9->10->11->1]


Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search? Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a depth of $2$, then $F$ has a depth of $3$). The beginning vertex has a depth of $0$. I need to show that every vertex must have a depth $\le \lfloor \frac{n}{2} \rfloor$.

I know that because the graph is only a cycle, every vertex must have a degree of $2$. And when performing a breadth first search, each vertex (except for the beginning vertex) will only have one vertex to choose, as the other connected vertex would be its parent. This would create a kind of "tree" shape where every node except the root has one child, and would mean that the maximum depth is $\le \lfloor \frac{n}{2} \rfloor$. I'm not sure how to phrase this as a proof, though.

There may be other ways to prove your claim, the simplest seems to me is by induction on $n$.

Base case : $n=3$, that means input graph is a triangle and it is easy to see that in this case maximum depth is $\le \lfloor \frac{n}{2}\rfloor$

Inductive case:  Suppose that depth of every vertex is $\le  \lfloor \frac{k}{2}\rfloor$ in $k$ cycle graph want to prove that depth of every vertex is $\le  \lfloor \frac{k+1}{2}\rfloor$  for $k+1$ cycle graph.

Hint for Inductive case: Going from $k$ cycle to $k+1$ cycle means we have added one vertex to any one of the edge ( as we know its both endpoints have depth  $\le  \lfloor \frac{k}{2}\rfloor$ (due to induction ) ) of the $k$ cycle graph it means depth of both endpoints in $k+1$ cycle will be    $\le  \lfloor \frac{k+1}{2}\rfloor$.


Finding a kernel for d-Bounded degree deletion In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum vertex degree of the graph to at most $d$.
The question is to how to find a polynomial kernel (in $k$ and $d$) for this problem.
I seem to be able to get the only reduction rule that if any vertex has degree $ > k+d$, it has to be there in the deletion set (if the answer to instance is yes). Because if it isn't, then at least $k+1$ of its neighbors have to be in deletion set. I can't seem to move beyond this point.
The exercise is from this book (exercise $2.9$).
I am also aware that we can remove edges between vertices with degree $< d$, and find solution in the modified graph (hint from the book). But I am not sure how it will be useful, in getting a bound over number of vertices/edges in $k$ and $d$.
I would appreciate only hints if possible (something maybe beyond the book hints).
PS: for $d=0$ this reduces to vertex cover problem.

Reduction Rule 1. Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($\le d$ as $d \ge 0$). And if $I$ is a yes instance so is $I^{'}$, as $G-V$ is a sub-graph of $G$, and $k$ and $d$ remain same across the two instances.
Reduction Rule 2. If a vertex $v$ has degree $\ge k+d+1$ then it has to be kept in the deletion set. Otherwise $k+1$ of its neighbours have to be kept in the deletion set. Which cannot be done, as maximum size of deletion set is $k$. Thus after this reduction all vertices will have degree $\le k+d$.
Reduction Rule 3 If there are two vertices $v$ and $w$, such that degree of both of them is $\le d$. Then the edge $vw$ can be removed converting the instance from $I = (G, k,d)$ to $I^{'} = (G-\{vw\}, k,d)$. If $I$ is a yes instance so is $I^{'}$ as $G-\{vw\}$ is a sub-graph of $G$, with $k$ and $d$ remaining same across the instances. And if $I^{'}$ is a yes instance so is $I$, as adding back $vw$ can make the degree of $v$ and $w$ at most $d$ (as they initially had degree $\le d$).
Rule $1$ might be applied after applying Rule $3$ as well.
Now considering a graph where vertices with degree $\le d$ don't share an edge, no vertex is isolated and and all vertices have degree $\le k+d$ (ie. none of the above rules applied). Let $A$ be the set of vertices with degree $\le d$ and let $B$ be the set of vertices with degree $> d$. We can argue that $|B| \le k(k+d) +k$, otherwise the output is no. Because if $|B| > k(k+d) +k$, then as most $k$ elements will be chose from $B$ for the deletion set, and  $ > k(k+d)$ elements will be left (in $B$). And as each of them has degree $> d$, they each have at least one edge going into the deletion set. But the deletion set can only accommodate $k(k+d)$ edges. Also as each vertex in $A$ has at least one neighbor (and all of them in $B$), the maximum number of vertices in $A$, will be bounded as $|A| \le |B|(k+d)  \le (k(k+d)+k)(k+d) = k(k+d)(k+d+1)$.
So $|A| + |B| \le k(k+d) + k(k+d)(k+d+1) = k(k+d)(k+d+2)$.


Complexity of generating power sets Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a function $f$ to them and check something.
I understand that generating a power set is $O(2^n)$, but what complexity class does this belong to, and how do I prove it?

Complexity time $O(2^n)$ is called $\text{DTIME}(O(2^n))$ and is a sub-complexity class of E which is in turn a sub-complexity class of EXPTIME.
To prove you can do it within $O(2^n)$ time, you have to provide an algorithm for that and show the algorithm runs in no more than $O(2^n)$.


Inexact cover, or cover with gaps Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem.

In the Knuth's research papaer, linked above it is shown how Polymino problem (that is covering a given shape with given sets of Polymino) is translated to exact cover problem, so that dancing links can be used to solve it.

Exact Cover problem goes like this:

  Given a matrix of 0s and 1s, find a subset of rows with exactly one 1 in each column.

For example the matrix

is solved by choosing rows 1, 4 and 5.

Knuth explains in the paper, how the Polymino problem can be translated into exact cover problem on example of the famous case of Polymino problem where we are trying to cover chess board (8x8) with 12 pentominoes. The 12 pentominoes occupy 60 squares in total, so 4 spaces on the 64 squares chessboard are left unaccounted.

Here is Knuth's explanation, of how the problems are translated into each other:

  Imagine a matrix that has 72 columns, one for each of the 12 pentominoes and one for each of the 60 cells of the chessboard-minus-its-center. Construct all possible rows representing a way to place a pentomino on the board; each row contains a 1 in the column identifying the piece, and five 1s in the columns identifying its positions. (There are exactly 1568 such rows.)

If this is not very clear please refer to the original paper for further details.

This makes sense. Latter in the paper Knuth uses a 2x2 tetromino to account for the 4 squares mentioned earlier. This also makes sense.

Now imagine that you have a different shape of the board. This is easy. You still translate each square into a matrix column as explained above.

What I'm having problems though is when I need to find solution for "inexact" cover, or cover with gaps.

In the chessboard problem above, imagine, that you do not want to settle for nicely defined 2x2 tetromino in the centre, like Knuth does. Instead you want to find all solutions no matter where the four "missing" squares go onto the board.

My initial idea was model this with 4 separate "monomino" one square each. Unfortunately this does not work so well. There are over 6 millions combinations of how 4 squares can be selected from 64 square keyboard.

If we assume that for a particular solution the monominoes occupy square A, B, C and D, then there are 4! of indentical solutions that the algorithm need to wade through, where monomino 1 goes to square A, monomino 2 goes to square B, etc or monomino 1, goes to square B , monomino 2 goes to square A, etc and all other possible combinations of fitting these 4 pieces into these 4 squares.

If we have a problem when we have more than 4 gaps, this becomes even worse. We are getting more and more identical solutions where only placement of monomino order is different, and the squares they occupy are the same.

This makes the algorithm orders of magnitudes slower, since in needs to enumerate all these identical solutions.

I cannot figure out how to efficiently model the problem of covering a shape with polymino pieces when there are many gaps as explained above.

Are there better ways to model it?

I'd propose this idea:

Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.

This will eventually run until a solution is found, in which 4 cells will be left unassigned.

By allowing 4 option-less columns, you place no required knowledge on which columns (cells) should be left unoccupied. The matrix is kept small and tidy as before.

Performance: The search tree probably does not grow too vast, as most of the "stupid" piece placements will trigger the limit within 1 or 2 iterations. Accordingly, the tree should only be about one order of magnitude larger than usual.


0 and 1 Queries in tables of N*N cells There is a square table composed of N*N Cells. Initially all cell is filled with a number 0.
Two types of Operations can be performed on the table.

R i k: All the numbers in the cells on ith row has been changed to k.

C i k: All the numbers in the cells on ith column has been changed to k.

Please Note : k ∈ {0, 1} (ie k = 0 or 1).

At any time ,Alice is interested to know  the total number of 0's on some row or total number of 0's on some column.

Our task is to answer Alice Query.

Input

First line contains a single integer N as described above.Next line contains a single integer Q representing the total operations and queries from Alice.
Then Followed Q lines , containing operations or queries in following format:

R i k: All the numbers in the cells ith row has been changed to k.

C i k: All the numbers in the cells ith column has been changed to k.

qc i :How many 0's are there in ith row?

qr i:How many cols are there in ith col?

Examples:
Input:

3

6

qr 1

C 1 1

qr 1

qc 1

R 1 0

qc 1

Output:

3

2

0

1

I tried a Naive solution.But it got time out. The constraint is quite large and the time limit is just 0.55 Seconds.

**1 ≤ N, Q ≤ 500000 (6 * 10^5)

How can i solve this problem within the given time-limit?

P.S: This is not a homework.

My solution uses 2 arrays (R and C) to store the zero-counts and a 1D array (Grid) to represent the grid of zeros and ones as a sequence of numbers. All 3 arrays are of size $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likewise for the i'th row). Here is a Python implementation and a test case (yours):

N = 3
R = []
C = []
Grid = []

for k in range(N):
    R.append(N)
    C.append(N)
    Grid.append(0)

def qr(k):
    print R[k - 1]

def qc(k):
    print C[k - 1]

def r(i, k):
    R[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[i - 1] & (1 << l) >> l)
        if bit != k:
            if k == 0:
                C[l] = C[l] + 1
            else:
                C[l] = C[l] - 1
        Grid[i - 1] = Grid[i - 1] | (k << l)

def c(i, k):
    C[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[l] & (1 << (i - 1))) >> (i - 1))
        if bit != k:
            if k == 0:
                R[l] = R[l] + 1
            else:
                R[l] = R[l] - 1
        Grid[l] = Grid[l] | (k << (i - 1))

qr(1)
c(1, 1)
qr(1)
qc(1)
r(1, 0)
qc(1)

You have to complete this with code that parses the input file and interprets the commands.


If you naively generate a parse tree from

$$\begin{align}T\to& FT'\\
T'\to& *FT' \\
\mid&\; /FT' \\
\mid&\; \epsilon\\
\end{align}$$

then you're going to end up with something like this:

         T
        / \
       /   \
      /     \
     F       T'
     |      /|\
     6     / | \
          /  |  \
         *   F   T'
             |  /|\
             3 / | \
              /  |  \
             ÷   F   T'
                 |   |
                 2   ε

What you really want is this:

         T
        /|\
       / | \
      /  |  \
     T   ÷   F
    /|\      |
   / | \     2
  /  |  \
 T   *   F
 |       |
 F       3
 |
 2

But that belongs to a different, left-recursive grammar:

$$\begin{align}T\to& T * F\\
\mid&\; T / F\\
\mid&\; F
\end{align}$$

To use the second grammar, you'd need to use a different parsing technique (not the end of the world :-). To get the second parse tree, you need to do a little surgery while constructing it (or in a post-parse tree-walk, but that seems like overkill).

Because LL grammars cannot deal with left-recursive grammars, they cannot directly represent left-associative operators (which is most operators). Without left-recursion, you only have one way to represent a repetition, which means you have to use the same style to represent both left-associative and right-associative operators. That's not an issue in practice -- you certainly know the associativity of all operators in your language -- but you might find it annoying that you need to annotate the parser in order to get the right parse. If you use a bottom-up parsing technique, this annoyance vanishes.


Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...

The question shows several misconceptions. I'll try to clarify the key aspects.

If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it must halt in infinitely many cases.

A TM halting on infinitely many cases does not imply that the recognized language is decidable. (I'm unsure about why you think this would be the case, it would make the halting problem decidable, for instance.)

There is no such a thing as an uncountable language, at least in a conventional setting where the alphabet is countable, and words have finite length. Hence, a TM can never halt on "uncountably many" words.


Why doesn't a time cutoff convert NP problems into co-NP? Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations.

You make a tweak to the verifier program, so that if it takes more than $f(n)$ operations, it unconditionally rejects. Then you place it into an NP machine and run it on all possible certificates for some instance of the problem where you're not sure if it has a solution. The unconditional reject after $f(n)$ operations ensures the computation terminates within $f(n)$ operations, even when rejecting. So this NP machine can solve the co-NP dual of the NP problem, where you want to reject in polynomial time when there is no solution.

Except that can't be right, because it seems to imply $\mathsf{NP}=\mathsf{coNP}$ and that's not believed to be true. I have an incorrect assumption or inference somewhere. What is it? Why can't I avoid NP's "negatives might run for a long time or even forever" with algorithm-specific time cutoffs?

A concrete example: suppose you have a 3-SAT verifier that takes no more than $42 n^2$ operations to check a solution to an $n$-clause problem (involving up to $3n$ variables). You then make an NP program like "non-deterministically choose a variable assignment, run verifier for up to $42 n^2$ steps, return its result else reject if it didn't finish". So within $42 n^2$ operations we'll have an answer, and flipping it gives the "is there no satisfying assignment" answer. Why is this not an NP algorithm for the co-NP problem of determining if there is no satisfying assignment to a 3-SAT problem?

The mistake I made was in the very last step: flipping the result. Doing that requires more than an $\mathsf{NP}$ machine, because I'm recombining the massively parallel computation then doing something else. $\mathsf{NP}$ machines finish with the merging, they can't continue on.

To run my algorithm I'd need a machine with the ability to query an $\mathsf{NP}$ machine then continue. A $\mathsf{P^{NP}}$ machine can do that... but it makes sense that $\mathsf{P^{NP}}$ would contain $\mathsf{coNP}$.

See also: Oracle Machines (Complexity Classes), and the Polynomial Hierarchy.


A context-free grammar for all strings that end in b and have an even number of bs I'm trying to find CFG's that generate a regular language over the alphabet {a b}

I believe I got this one right: All strings that end in b and have an even number of b's in total:

$\qquad S \to SS \\
\qquad S \to YbYb \mid \varepsilon \\
\qquad Y \to aY \mid \varepsilon$

However, Im not sure how to accomplish this with an odd number of b's.

So for example, how could I find a CFG that generates all strings that end in b and have an odd number of b's in total: So far I have this,

$\qquad S \to SS \\
 \qquad S \to YYb \mid \varepsilon \\
 \qquad Y \to abY \mid baY \mid \varepsilon$

But this can generate abababb so it's incorrect and Im stumped at this point.

There is an easy and very natural way how to derive a context-free grammar $G=(V,\Sigma,R,S)$ from a DEA $M=(Q,\Sigma,\delta,q_0,F)$. We set

$V=Q$
$S= q_0$
$R$ consists of the following rules:

for all $X\in Q$ and $a\in \Sigma$ with $Y=\delta(X,a)$ we add the rule $X \to aY$
for all $X\in F$  we add the rule $X \to \varepsilon$
there are no other rules in $R$

It's an easy exercise to show that $L(G)=L(M)$. With this technique you can now build your automaton first (which is an easy two-state example in your case), and then apply this construction.


Uniform sampling from a simplex I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should lie within the triangle:

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

Ideally I want each point within the area to have equal probability. If it's too hard, I can drop the requirement. Thanks.

Let us first assume that you want to sample within

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

This doesn't make quite a difference, since the sample point will still lie in your requested area with high probability.

Now you are left with sampling a point from a simplex. In the 3d example you get a 2d simplex (triangle) realized in 3d.

How to pick a point uniformly at random was discussed in this blog post (see the comments).

For your problem it would mean that you take $n-1$ random numbers from the interval $(0,1)$, then you add a $0$ and $1$ to get a list of $n+1$ numbers. You sort the list and then you record the differences between two consecutive elements. This gives you a list of $n$ number that will sum up to $1$. Moreover this sampling is uniform. This idea can be found in Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134.

For example  ($n=4$)  you have the three random numbers 0.4  0.2 0.1 then you obtain the sorted sequence 0 0.1 0.2 0.4 1 and this gives the differences 0.1 0.1 0.2 0.6, and by construction these four numbers sum up to 1.

Another approach is the following: first sample from the hypercube (that is you forget about x+y+z=1) and then normalize the sample point. The normalization is a projection from the $d$-hypercube to the $d-1$-simplex. It should be intuitively clear that the points at the center of the simplex have more "pre-image-points" than at the outside. Hence, if you sample uniformly from the hypercube, this wont give you a uniform sampling in the simplex. However, if you sample from the hypercube with an appropriate Exponential Distribution, than this effect cancels out. The Figure gives you an idea how both methods will sample. However, I prefer the "sorting" method due to its simple form. It's also easier to implement.


Is there an approximation algorithm for Minimum Test Collection Problem? The problem is defined as follows:

Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J≤|C|$.

Question: Is there a subcollection $C′⊆ C$ with $|C′|≤ J$ such that, for every pair $a_{i},a_{j}$ of possible diagnoses from $A$, there is some test $c∈C′$ for which $|{a_{i},a_{j}}|∩ c|=1$ (that is, a test $c$ that "distinguishes" between $a_{i}$ and $a_{j}$)?

And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey & Johnson's book.

Thanks.

Yes, there are approximation algorithms for this problem.

If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&context=tepper
constructed a $O(\log{k})$-approximation algorithm
Another approximation algorithm of the same complexity is derived here:
https://link.springer.com/chapter/10.1007/3-540-44676-1_13

Hope that helps!


How to compare the efficiency of two encoding schemes or hypothesis languages? My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have the right terminology and just need a starting point so I can help myself.)

I'm trying to interpret the vector inputs to a black-box controller (which I can model as finite-state machine). I can see them and they look like a series of symbols but it is too variable (stochastic) to easily define an "alphabet" based on repetition and it isn't clear how the symbols are grouped. In other words it isn't clear whether they use something like block coding where each symbol is the same number of vectors in a sequence, or convolutional coding where symbols can have different numbers of vectors.

The controller operates a linear actuator (it just goes up and down) and the inputs are large vectors from a CNN. It's essentially a pong playing robot. I make predictions by modeling the controller as binary decision tree that maps each putative symbol to an exact position of the actuator. This is very similar to a language induction problem for a finite-state machine. Recall that a finite automaton can be a representation of a regular language. Also recall that finite automaton can characterized in terms of its memory requirements and computational complexity, hence a regular language can too.

I know that the controller is optimal. There is no controller which has both less memory and less computational complexity. If I have two guesses at coding schemes and each are able to predict actuator position equally well then I want to pick the coding scheme which implies the least complexity and memory. So how does one go about evaluating the resource requirements of a coding scheme (raw inputs-> symbols) and grammar (rules about symbols) in combination?
I need to keep in mind that I might be wrong that it digitizes its inputs into symbols at all. So what are the signs that it is not digital? (such as, if I divide the symbols into smaller symbols and it still works just as well, ad infinitum, that probably means the symbols are meaningless).

If you don't think I've given enough information keep in mind that I don't expect a detailed answer (but I'm happy to offer more). An acceptable answer is something of the form "I think you need to look into ____.", "This sounds like ____ in which case we often use ____.", "This sounds like a paper I read, see ____.", or "The ____ metric compares the level of the difficulty of a task to the number of symbols in the language required to perform that task and tells you how efficient a language is at that task."

The answer was just tree depth. What I needed to do was learn about evaluating the complexity of finite automata and how we can use a decision-tree model (decision-tree complexity) to put bounds on the complexity of an automata (analysis of algorithms). So I take my two coding schemes (call them A and B) and I make binary decision tree to predict the output of my system based on the inputs provided by the coding schemes. If both coding schemes A and B are equally useful for predicting the outputs but A requires a tree depth of 15 while B requires a tree depth of 54 then A is "better".  This is because our decision-tree model of the system is simpler when using A than when using B and as stated before we strongly believe that our system is as simple as possible.

Of course I also need to include the complexity of the coding scheme itself but that just goes with alphabet size since it is a Nearest Neighbor search.

So it was under my nose, I just needed some context.


Division by a constant After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time?

Additionally, what about division with a constant numerator, ie. "division of a constant"?

Division by a constant can always be recast as multiplication by a constant followed by a shift.  The relevant papers are:

Robert Alverson, "Integer Division Using Reciprocals," IEEE Int'l Symp Comp Arithmetic, (ISCA-10):186-190, 1991.

Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," ACM Conf on Prog Lang Dsgn and Impl, (PLDI-1994):61-72.

Daniel J. Magenheimer, Liz Peters, Karl W. Peters, and Dan Zuras, "Integer Multiplication and Division on the HP Precision Architecture," IEEE T. Comp., 37(8):980-990, August 1988.


On the computable function of a problem that halts Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ is a computable function?

In general, is it true that the behavior of program $G(P)$ with the input $F(i)$ identical to the behavior of P with input i? (Both $G$ and $F$ are computable.)

No, it is not.

In general, to help you think about this kind of problem, I recommend you work through some examples.  Keep them as simple as possible.

Here is an example that illustrates why the answer is no.  Suppose $P$ is the following program: "if the input is 1, then halt immediately; otherwise enter an infinite loop".  Suppose $F(1)=2$.  Then $P$ halts on the input $i=1$, but it does not halt on the input $F(i)=F(1)=2$.  So, the behavior of the program $P$ on one input tells you nothing about its behavior on a different input.


Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1}  = app \quad \& \quad r(j) \leq p $ and (3) $t_{i-1} = app \quad \& \quad r(j) > p$. However, for two of them I can go to two directions.

To explain more, suppose I have job $−1$ scheduled. Then, if $_{−1}=$, I can schedule the next job (job $$) with two conditions: (1): start it immediately after job $−1$ is finished, i.e. at point $_{−1}$ or (2): start it two time slots earlier than job $−1$ is finished, i.e. at $_{−1}−2$. Both directions should be checked in the DP.

The formula is shown in the following, that is simplified to avoid misleading. In fact, cases 1 and 2 are the same, but can go into two directions ''app'' and ''int''. The same is for cases 3 and 4. But case 5 has only one option that is ''app''. I think the current format of the formula is missing something since the condition for cases 1 and 2, and for cases 3 and 4, is the same. What is the correct form of interpreting this formula?

\begin{equation}
z_i = \begin{cases}
z_{i-1} + p + (app) & \text{if $t_{i-1} = int$}\\
z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$}\\
z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\
z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\
z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p \\
\end{cases}
\end{equation}

One thing that comes to my mind is to write it with two $\min$ functions. Since from the three conditions with $(app)$ (i.e. conditions 1, 3 and 5) one with lower objective function will be remained, and the same for the two with $(int)$ option (i.e. conditions 2 and 4). How about writing with two $\min$ functions with distinct condition for each?! For example:
\begin{equation}
z_i = \begin{cases}
\min\begin{cases} z_{i-1} + p + (app) & \text{if $t_{i-1} = int$} \\ z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \\ z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p\end{cases} \\
\min\begin{cases}z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$} \\
z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \end{cases}\\
\end{cases}
\end{equation}

If you want to have two values for each stage, one for $t_{i - 1} = app$ and one for $t_{i - 1} = int$, which are derived from three or two cases respectivelly then you will need to store two dynamic programming values for each stage. Let's name these values for the $i$-th stage $z_{app, i}$ and $z_{int, i}$ respectively. $z_{app, i}$ is the minimum additive value of your objective function for stages up to the $i$-th one if you used (app) in the $i$-th stage, while $z_{int, i}$ has a similar definition. Now let's see what the format of the dp recursion will look like:

$
z_{app, i} = min
\begin{cases}
z_{int, i - 1} + p + (app), & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (app), & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j) + (app), & \text{if } t_{i - 1} = app \wedge r(j) > p
\end{cases}
$

$
z_{int, i} = min
\begin{cases}
z_{int, i - 1} + p + (int), & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (int), & \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

Note that that $t_{i - 1} = int$ dictates the use of $z_{int, i - 1}$ which is the optimal value of the previous stage when (int) was used. The case when $t_{i - 1} = app$ is faced similarly by using $z_{app, i - 1}$. We have represented the optimal values of each stage using mutual recursion. Equivalently you can use the following recursion:

$
z_{app, i} = (app) + min
\begin{cases}
z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j), & \text{if } t_{i - 1} = app \wedge r(j) > p
\end{cases}
$

$
z_{int, i} = (int) + min
\begin{cases}
z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

This way the dynamic programming calculations will speed up by a constant factor.


Unrestricted grammar to generate $a^{n^2}$ I have been asked to find a grammar that will generate the language $\{a^{n^2}:n \ge0\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn't work. Any idea on how to setup such grammar? Any help will be appreciated.

Set aside $n$ of the $n^2$ characters, and use that $(n+1)^2 = n^2 + 2n +1$.

So at any moment we have (say) $n^2-n$ symbols $A$ and $n$ symbols $B$.
We also need endmarkers. $L,R$ count as A$.

$S\to LBBR$

In one linear phase we visit all symbols, and each symbol $B$ will generate two extra $A$'s. Finally we add a $B$.

$L \to LX$; $XA\to AX$; $XB\to AABX$; $XR\to BR$

Nondeterministically end, transforming all symbols into $a$.


What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end? Here are some sequences:

'0.66666'
[3,0,1,2,2,2,0,1]
'banana'
'bandana'
'11221122'

I would like to find the index and length of the substring in each which is repeated (even if partially) for the most terms and which repeats until the end.

I wrote a function in JavaScript that successfully returns the
expected output:

'0.66666'           After occurring at index 2, '6' repeats for 4 terms.
[3,0,1,2,2,2,0,1]   After occurring at index 1, [0,1,2,2,2] repeats for 2 terms.
'banana'            After occurring at index 1, 'an' repeats for 3 terms.
'bandana'           After occurring at index 4, 'an' repeats for 1 terms.
'11221122'          After occurring at index 0, '1122' repeats for 4 terms.

Explanation:

[3,0,1,2,2,2,0,1] is a sequence with 8 terms. [0,1,2,2,2] is the longest substring which repeats at least partially to the end of the sequence, because after its first occurrence it repeats directly after for another 2 terms. Then the sequence terminates.
If we were to input [3,0,2,2,2,0], you might think the substring [2] wins because it repeats for 2 terms following its first occurrence, but it doesn't repeat to the end so the substring [0,2,2,2] wins as the term that follows the only occurrence of this substring (0) is also the first term in the substring meaning that it repeats for 1 term following the first occurance.

Repetition must continue to the end so for the second example [2,2,2] is not valid though it also repeats for two terms

Here's the function (JS Bin):

function longestRepeatedSuffix(sequence) {
    var repeatStart;
    var blockLength;
    var maxRepeatLength = 0;

    // Go through each suffix from length 1 to the length of the sequence - 1.
    suffixLoop: for (var suffixI = sequence.length - 1; suffixI > 0; suffixI--) {
        var len = sequence.length - suffixI;
        var repeatLength = 0;

        // Go right to left through adjacent substrings the length of suffix.
        // substringI may be negative on the last iteration.
        for (var substringI = suffixI - len; substringI >= 1 - len; substringI -= len) {

            // Go right to left through characters in the suffix and current substring.
            for (var charI = len - 1; charI >= 0 && substringI + charI >= 0; charI--) {

                // See how many characters match.
                if (sequence[substringI + charI] === sequence[suffixI + charI]) {
                    repeatLength++;
                    if (repeatLength > maxRepeatLength) {
                        maxRepeatLength = repeatLength;
                        repeatStart = substringI + charI;
                        blockLength = len;
                    }
                } else {
                    continue suffixLoop;
                }
            }
        }
    }
    return 'After occurring at index ' + repeatStart + ', "' +
        sequence.slice(repeatStart, repeatStart + blockLength) +
        '" repeats for ' + maxRepeatLength + ' terms.';
}

I believe this is an O(n^2) implementation even though I used 3 nested for-loops. So my question is: how can I use something like a suffix-tree to get even better time complexity?

Similar algorithm:

Longest repeated substring: This is different, as it includes repetitions which overlap and those which are not adjacent (not just consecutive repetitions) and it doesn't require repetition to continue to the end.

This can be solved with a prefix function in linear time.

Prefix function of a string $S$ is an array $p$ of length $s$, where $p_i$ is the length of the longest border of a string $s_1 \dots s_i$. The $border$ of a string is its longest proper prefix which is also a suffix. E.g. the border of $abacaba$ is $aba$, the border of $ababa$ is $aba$, the border of $banana$ is empty. The prefix function can be computed in linear time (see this Coursera lecture, for example).

For simplicity I reverse the string and now look for a recurring prefix, not suffix. Let $p_i$ be the prefix function of the string. Then the length of the shortest recurring substring of the $i$-th prefix of the string is $i - p_i$:

s: a b a c a b a c a b a
p: 0 0 1 0 1 2 3 4 5 6 7
   -------------
           -------------
   + + + +

With hyphens I denote the matching prefix-suffix pair found by prefix function, and with pluses the generating prefix itself. It is easy to see that it ends exactly where the matching suffix begins, that is, at the position $i - p_i$.

Having the length, the answer is trivially computed as $i - (i - p_i) = p_i$. Isn't it the nice observation? ;) So what you actually want to do is to take the maximum value of the prefix function of the reversed string.


why the big-oh of a linear function is n^2? I know the definitions and differences of big-theta, big-oh, and big-omega in finding time complexity of algorithms. what I can't understand is that why the big-oh of a linear function cannot be O(n).

$0 \le an + b \le cn \Rightarrow  c = a + \frac b {n_0}$

so we could find a value for constant $c$. as a result, the big-oh of a linear function can also be $n$. am I right??

Note: I have read all the previous answers and questions in this commission and others. but I didn't understand. that's why asked a new question

A function does not have a unique big-oh. $O(f(n))$ denotes a class of functions that are big-oh of $f(n)$. Big-oh is used to give upper bounds.

For example, $f(n)=3n+5$ is $O(n)$, but it is also $O(n^2)$ and also $O(n^3)$ and also $O(2^{2^{2^n}})$. However, $f(n)$ is (in this example) not $O(\log n)$.

In set theory notation, we have $O(n)\subset O(n^2)$, i.e. any function that is $O(n)$ is also $O(n^2)$. However, if we had a function that is $O(n)$ and you gave $O(n^2)$ as an upper bound, that would not be incorrect, but it would be a weaker result than saying it is $O(n)$.

$\Omega$ works the other way around (i.e., it is used for lower bounds). A function that is $\Omega(n^2)$ is also $\Omega(n)$. $\Theta$ is used to give "tight" bounds: a function that is $\Theta(n^2)$ is neither $\Theta(n)$ nor $\Theta(n^3)$.


Two Generals problem - what if we set boundary conditions, and then layer redundant messages once they've been met? apologies if this is in wrong place (very new to CS). I know there must be some flaw in my reasoning here, but I can't quite see it. Here's how I've stated the problem.

There are two generals, A and B. Messages start from A with a request M and B replies with an agreement N. Thereafter, the generals must exchange acknowledgements An and Bn of message reception. That is, after receiving N, A will send A1; upon receiving A1, B will send B1; and so on.

M reads:

  Attack at time X. Once I receive your reply, we will begin exchanging the acknowledgments An and Bn. As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

M goes through. N is sent, agreeing to M.
A1 is sent, acknowledging M and N. B1 is sent, acknowledging M, N and A1.
A2 is sent, acknowledging M, N, A1 and B1. B2 is sent, acknowledging M, N, A1, B1, and A2.
So on for An and Bn

By the time Bn is sent, B knows the following:
I've told A that I received A1 n times, and I know he heard me n-1 times. So he knows I received A1.
At this same time, A knows the following:
I've told B that I received B1 n-1 times, and I know he heard me n-2 times. So he knows I received B1.
Recall that the boundary conditions for the attack were:
As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

If we set n = 3, these conditions seem to be met. If we set n arbitrarily higher than that, it works.

As I understand it, the point of the Two Generals problem is that is that neither party is willing to proceed while the chance of the other proceeding is less than 100%. I also know that classically, each additional message increases the chance of a general proceeding asymptotically towards 100%. But if we set boundary conditions such as these, and then add some layers of redundant messages, there is some shared knowledge between the two generals, and the possibility that either one will not attack falls to 0? Have we not established that both generals know that the attack criteria have been met with 100% certainty?

I know this problem's unsolvable, so I must've made a mistake somewhere. I just can't see it.

Realize first that if General $X$ doesn't receive message $X_k$, then General $X$ must assume that General $Y$ didn't receive message $Y_{k-1}$.

Suppose that General $B$ does not receive the final message $B_n$.  An important question is: Why is that?

In General $B$s mind, General $A$ didn't necessarily receive $A_{n-1}$.  And that would be bad.

Suppose in this hypothetical scenario that $B$ believes that $A$ didn't receive $A_{n-1}$.  That could be due to $B$ not receiving $B_{n-2}$.  But why didn't $B$ in this scenario receive $B_{n-2}$.  Well, possibly because $A$ didn't receive $A_{n-3}$.

That means that if $B$ doesn't receive $B_n$, $B$ must assume that $A$ assumes that $B$ assumes that $A$ didn't receive $A_{n-3}$ ... ad infinitum.

The problem here is that after $A$ and $B$ split, there is no more new common knowledge.  A nice way of modeling this situation is with the use of possible worlds.


How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem Task:
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, the 1/2 hamiltion path problem (1/2-HPP) asks for a path that visits exactly half of the nodes.
Show that: $HPP \le_{P} 1/2-HPP$

Question: Can anyone give me a hint on how to prove $HPP \le_{P} 1/2-HPP$

Double the graph size: make two clones of the input $G_1,G_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G_1,G_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G_1$ or all $G_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.


PRNG bad seeding and von Neumann unbiasing Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is useful in production).  For example, Marsaglia talked about seeding methods in his May 2003 Communications of the ACM article [1].  It feels like a chicken/egg situation.  You need a source of high-quality random bits in order to seed your generator, so you can create a source of high-quality random bits.

I was wondering:

Is von Neumann unbiasing a legitimate way to defend against poor seeding of large-period PRNGs?   In other words, if I apply von Neumann unbiasing to the bitstream output of Mersenne Twister, does the quality of the stream still depend on how I seeded it?

[1] George Marsaglia, "Seeds for random number generators." Communications of the ACM, 46(5):90–93, 2003 (ACM page.)

Von Neumann unbiasing only works if the random source consists of independent samples. Otherwise it is not guaranteed to produce random bits. More generally, in theoretical computer science there exist objects called (randomness) extractors whose job is to extract random bits out of imperfect random sources. Usually they need access to a small number of "high quality" random bits.

In practice, seeding a PRNG is not difficult. There are many legitimate sources of randomness, and using an extractor such as a hash function, you can take a decently sized sample and extract a decently random seed. Once you have a handful of high quality random bits, you can use a PRNG to quickly extract many more seemingly random bits.


Is λ allowed in Deterministic CFG? I have a non-deterministic CFG that says

  S-> aS | aB | bB | λ;
  B-> bB | λ

And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it contains

  S-> aS | aB | [...]

But I think what I'm confused is why in my book does it say that A->λ productions are not allowed? I can't think of any other way to keep the solution a deterministic CFG if λ is not allowed.

[EDIT]
The book defines deterministic CFG

  "To recognize the full set of context-free languages, we require a non-deterministic stack automaton. We saw that any NFA could be replaced by an equivalent DFA but we cannot do this in the case of non-deterministic stack automaton. It is our good fortune that practical programming languages can be adequately described by deterministic CFG"

  "We said that in Type 1 grammars, the nonterminal on the left-hand side could be replaced by ε. Since these restrictions are cumulative as we go from one level of the hierarchy to the next, this implies that Type 2 grammars may not have productions of the form A-> ε. In fact, we will see many CFGs have such productions, we must allow such productions as exceptions to the Type-1 restriction."
  - Introduction to Compiler Construction by Thomas W. Parsons

Oh. That's a disappointing explanation in the book.  I suggest that you don't rely on that explanation for precise details about deterministic CFGs; it looks like it is trying to give intuition, but it is not the place to look for formal definitions, rigor, or precision.  I'd suggest looking at a well-regarded automata theory textbook.  (Hopcroft, Motwani, and Ullman's book is well-regarded, though I haven't checked specifically whether it has a definition of deterministic CFG.  Sipser is also good.)

As Yuval says, the definition of a deterministic CFG is not completely standard.  I think I've seen multiple slightly different definitions.  Here are the basic concepts:

The definition of a deterministic pushdown automaton is standard.  (There are two variants, acceptance by final state and acceptance by empty stack; normally we use acceptance by final state, unless otherwise specified.)
The definition of a deterministic context-free language is standard: $L$ is a deterministic context-free language if it is accepted by any deterministic pushdown automaton.
The definition of a deterministic context-free grammar is not completely standard.  If I remember correctly, I think it can be defined in a few slightly different ways.  The one thing everyone agrees on is that, no matter what definition of deterministic CFGs you pick, the languages that can be accepted by such grammars should be exactly the deterministic context-free languages.  But there are a few different ways to place restrictions on a CFG, while achieving this property.  In particular, you can define deterministic CFGs in a way that allows it to include $A \to \lambda$ rule.  Perhaps there is another definition that doesn't allow such rules, and perhaps your textbook has that definition in mind.  Since your book doesn't state a precise definition, one can only guess.  Perhaps the author decided that the exact specifics aren't too important, for the book's purposes.

The bottom line is: your question seems perfectly reasonable.  I don't think the problem is that you lack understanding of something important.  I think the problem is that the textbook is just written in a confusing way, on this particular point.


On computing the factor-free basis of a regular language The problem is as follows.

Background: Given an alphabet $\varSigma$. If $u,v,w,x \in \varSigma^*$ and $w=uxv$ then $x$ is a factor (substring or infix) of $w$. A language $L$ is factor-free if, for all distinct words $x, y \in \varSigma^*$, $x \in L$ and $y \in L$ imply that $x$ and $y$ are not factors of each other. Given a regular language $L$, we define $basis(L)$ as $L' \subseteq L$ such that $L'$ is factor-free and for every word $x \in L$ there exists a word $y \in L'$ such that $y$ is a factor of $x$.

Question: Is $basis(L)$ efficiently computable, given (say) a DFA for $L$? If so, do you have any ideas about the algorithm that computes it?

Example: Consider the language $L=\{ab,abab,ababab,abababab,\ldots\}=\{(ab)^i|i>0\}$. Then, $basis(L)=\{ab\}$.

Let me give you my insights on the subject, it may help.

It has been proven that checking factor-freeness is tractable for regular languages1.

Also, in a trivial way, $L=basis(L)$ if $L$ is factor-free. This leads to the fact that $basis(L)$ is not always finite. Because for an infinite factor-free language the basis is also infinite. Here is an example from the Handbook of Formal Language Theory (vol. 1, p. 19): $L=\{ba^ib | i > 0\}$.

For finite languages, it seems that a basis always exists because a language $L$ is either factor-free thus $basis(L)=L$ or not factor-free. The latter necessarily means that $L$ contains a sublanguage $L'$ for which some words are factors of each others, consequently $basis(L)=basis(L') \cup (L \setminus L')$.

1 Han YS, Wang, YJ , Wood, D. Infix-free regular expressions and languages.  International journal of foundations of computer science. 2006.

A language $L$ is infix-free if
$$ L \cap (\Sigma^+L\Sigma^* \cup \Sigma^*L\Sigma^+) = \emptyset. $$
(This deep observation, which I made independently, appears in reference [1] to the paper you cite.) This gives a simple algorithm for deciding whether a regular language $L$ (given as a DFA, NFA, or regular expression) is infix-free.

Similarly, the basis of $L$ is
$$ L \setminus (\Sigma^+L\Sigma^* \cup \Sigma^*L\Sigma^+). $$
This gives a simple algorithm for computing the basis of a regular language (as a DFA, NFA, or regular expression).


Defining a "repeat until"-construct in Denotational semantics My Problem is: to define a "repeat until"-construct in terms of Denotational semantics. I made an attempt and now i need to know if i made it right.

The Conditions are: i used the language "While" as specified in "Semantics with Applications" by Nielson & Nielson (1992) (pdf) (WorldCat). I do not want to use the help of the While-construct.

In denotational semantics, we are interested in the effect of a program, rather than in "how" it is executed. Thats why semantic functions are defined compositionally. The corresponding definitions for the Denotational semantics (or "direct style semantics") can be found on page 86 in the Book from Nielson & Nielson (they made it avaible over the Internet).

My Approach is:
$$\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = \text{FIX }F\\ \text{where }F\ g = \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ\text{cond}(\mathcal{B}\lbrack\lbrack b\rbrack\rbrack , \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ g, id)$$

As you might see, my approach is quite similar to the definition of while, but i cannot see a mistake in it.

post scriptum: Bounty given, and second edit: yes, i meant $$\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$$ .. typo corrected.

Presumably you mean $\lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$, which you can easily define using $\text{while}$ as follows.

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
\mathcal{S}_{\text{ds}} \lbrack\lbrack S ; \text{while } \lnot b \text{ do } S\rbrack\rbrack
$$

Note that typically, a $\text{repeat}$ construct loops while the condition is false; your definition keeps the condition positive.

Building on the above equation and expanding the right-hand side using the table on page 86, you get:

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
(\text{FIX }F)\circ \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\\ \text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack , g\circ\mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack, id)
$$

You can transform the above to the following.

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
\text{FIX }F\\
\text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack, g, id)\circ \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack
$$

Your version is not correct in this regard, it would be equivalent to $\lbrack\lbrack \text{while } b \text{ do } S;S\rbrack\rbrack$, which evaluates the condition before rather than after the first execution of $S$.


Seeking popular science book on bioinformatics or computational genomics An intelligent 15-year-old I know is interested in both computer science and genetics.  I told her that these fields make an excellent combination.  I'd like to give her a book on bioinformatics or computational genomics.  I'm looking for a fun book, not a textbook.  Specifically, it should inspire people to want to study the field, not aim to provide in-depth knowledge itself.  I am not interested in books on genetic algorithms.  Any suggestions?

this is a very broad question so am going to answer it with decent lists found across the internet most of which are sorted by some criteria (eg bestsellers, top review counts, etc). also there are so many bioinformatics books now and one strategy might be to simply go with your favorite publisher. there are some that come up often in CS areas eg O'Reilly. also, even the "x for Dummies" book series has a bioinformatics title which might be of interest to those who like that publisher. another option is to narrow it down by your algorithmic angle eg there is one based on Python and there are others that emphasize other statistical packages, etc.;

as for your tricky criteria of "inspirational" it may make sense to look for biographies of scientists in the field or stories about successful startups, and if the student is into CS, then programming exercises might verge on "inspirational".

goodreads bioinformatics books ranked by review count & ratings listed
O'Reilly bioinformatics top sellers
Amazon best sellers Bioinformatics
best book on bioinformatics for a computer scientist stackoverflow
suitable book on bioinformatics for cs student biology.se
recommend your favorite bioinformatics books biostars thread