Why is particular token missing in LALR lookahead set? I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:

S' ::= S
S ::= L = R | R
L ::= * R | id
R ::= L

The items associated with state 0 given in the Automaton View are as follows:

S ::= ⋅S, EOF
S ::= ⋅L = R, EOF
S ::= ⋅R, EOF
L ::= ⋅* R, {=, EOF}
L ::= ⋅id, {=, EOF}
R ::= ⋅L, EOF

Shouldn't the last item's lookahead set be {=, EOF}? This item could be derived from S ::= ⋅R (in which case the lookahead set is {EOF}) or from L ::= ⋅* R (in which case the lookahead set is {=, EOF}).

In state 0, R ::= ⋅L can only be generated by S ::= ⋅R. In L ::= ⋅* R, the dot precedes *, not R, so no further items are generated by it.

The dragon book uses this grammar as an example of the inadequacy of SLR, and the correct computation of the lookahead in this case is an instance; the SLR algorithm bases lookahead decisions on the FOLLOW set rather than actual lookahead possibilities in the state, which will eventually lead to a shift/reduce conflict on lookahead symbol =.


Asymptotic bounds of the following operations I have a very simple question about the best possible big-O bounds for the following data structure:
It starts out empty When you add an element, it is inserted, and the index it was at is associated with it. So if it was the first item inserted, it's index would be zero:
14 12 19 <- items
 0  1  2 <- associated indices

Now if I delete 12 in this instance, the indexes for the other items are updated like so:
14 19
 0  1

Adding another element, like 10:
14 19 10
 0  1  2

If I were to delete 14, the 19 and 10 have their indices decreased by one.
In addition to adding and removing elements, you must also be able to search for a specific element and it should tell you what the index of that element is.
What is the tightest possible asymptotic bounds for these methods? Obviously I could do O(n) for removing elements and make search and add O(1). However, I was able to use a Fenwick tree to get O(log(n)) on add, search, and remove. Is it possible to do better than this?

If you could do all three operations faster than $O(\log n)$ time, then you would obtain a sorting algorithm whose running time is faster than $O(n \log n)$ time.  That's known to be impossible for comparison-based algorithms.
So, you probably can't do better than $O(\log n)$ time for all three operations.  In particular, you definitely can't do better using a comparison-based algorithm (one that only compares items but has no other knowledge about the values of items).
The reduction works as follows.  First, scan through the list of $n$ numbers and insert each into your data structure.  Second, scan through the list again; for each number $x$, look up its index, and then write it into an output array at that index.  This does $2n$ operations on your data structure, so if your data structure can support insert and lookup in $O(\log n)$ time, the total running time will be $O(n \log n)$.


Machine epsilon vs least positive number What is the difference between machine epsilon and least positive number in floating point representation?

If I try to show the floating point number on a number line .Is the gap between exact 0 and the first positive (number which floating point can represent) ,and the gap between two successive numbers, different?

which one is generally  smaller?
and on which factor these two values depends(mantisa or exponent)?

Machine epsilon is the relative error (the error independent of what exponent you are currently using.)

It tells you the maximum error in the mantissa after a given operation.  For example take sqrt(2.0) and sqrt(2048.0) = sqrt(2.0)*32.0.  In IEEE 754 double precision (53-bit mantissa) the maximum error in the mantissa for this result will be $2^{-53} \approx 1.11\times10^{-16}$.

Put another way, to quote Wikipedia, the machine epsilon is

  the maximum spacing between a normalised floating point number, $x$, and an adjacent normalised number is $2 \epsilon \times |x|$.

The least positive number in a floating point system includes the exponent.  In double precision IEEE 754 the smallest normalized number is $2^{-1022} \approx 2.225 \times 10^{-308}$.  The smallest denormalized number is $2^{-52}\times 2^{-1022}=2^{-1074}\approx 4.941\times 10^{-324}$.


If two languages together cover all words and one is regular, is the other one as well? If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ necessarily regular?

I think that the answer is yes, but I'm not sure on my proof.

The reason that I think that $L_2$ is regular is because surely $L_2$ just accepts all the words in the language that $L_1$ doesn't? So, to me, that suggests that $L_2$ must be regular as well, I just don't know where to begin on a formal proof.

Any guidance would be appreciated.

In fact, the answer is no.

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ is not necessarily regular.

We can prove this through counter-example.

If we let $L_1$ = $\Sigma^*$, then we can choose any non-regular language in $\Sigma$  for $L_2$.

If we take $\Sigma$ = {a,b} and then let $L_2$ = $a^n$$b^n$ (A non-regular language) then  $L_1$$\cup$ $L_2$ = $\Sigma^*$ and $L_2$ is non-regular as required.


A "triangular" data structure for commutative relationships A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, the same is true for any table that represents a commutative relationship. Is there a data structure that can take advantage of commutativity to avoid storing redundant values?

Some languages, such as C, support ragged arrays: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.


What are the different types of databases? Is there is a study or classification available on different types of databases? (Examples include structured, unstructured, semi structured relational, object oriented, folksonomies, etc.)

Wikipedia has a list of database models: http://en.wikipedia.org/wiki/Database_model


How to prove the equivalence of two CFG for balanced parentheses? Given two CFGs for balanced parentheses.

$S \rightarrow  SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$

How do I show that they are equivalent?

I have been able to show $ L(2) \subset L(1) $ as follows

$$ S \Rightarrow SS \Rightarrow SSSS \leadsto S(S)S $$

Thus, $ S \leadsto S(S)S $. Keeping production rule $ S \rightarrow \epsilon $, we get $ L(2) \subset L(1) $.

But I can't prove the reverse i.e. $ L(1) \subset L(2) $. Any help would be appreciated.

But I can't prove the reverse i.e. $(1)\subseteq (2)$.

Indeed, that direction of inclusion is somewhat harder to prove.

Let us prove all following 3 context-free grammars are equivalent

$G_1$: $S \rightarrow  SS \mid (S) \mid \epsilon$
$G_2$: $S \rightarrow S(S)S \mid \epsilon$
$G_3$: $S \rightarrow  (S)S \mid \epsilon$

Proof.

$L(G_1)\supseteq L(G_2)$:
$S\Rightarrow_{G_1}SS\Rightarrow_{G_1}SSS\Rightarrow_{G_1}S(S)S\,.$
$L(G_2)\supseteq L(G_3)$:
$S\Rightarrow_{G_2}S(S)S\Rightarrow_{G_2}(S)S\,.$
$L(G_3)\supseteq L(G_1)$:

Let $B$ be the language of balanced parentheses, i.e.,
$$\{x\in\{(,)\}^*\}:|x||_(= ||x||_) \text { and, }\text{if } f\text{ is a prefix of } x,\,|f||_(\ge ||f||_)\}\,.$$ It is immediate to see that $L(G_1)\subseteq B$ by structural induction.

Let $P(n)$ be the proposition that all words in $B$ not longer than $2n$ are in $L(G_3)$.

$P(0)$ is true since the only word not longer than 0 is $\epsilon$.
Assume $P(k)$ is true. Let $w\in B$ with length $2(k+1)$. $w$ must start with left parenthesis, "(". If we count the number of "("s and the number of ")" in $w$ starting from the beginning "(", there will be a time the number of ")"s catches up with the number of "("s. Consider the first time that happens, which must at a ")" in $w$. So $$w=(w_1)w_2$$ for some $w_1,w_2\in B$. By IH, $S\leadsto_{G_3}w_1$ and $S\leadsto_{G_3}w_2$. Hence
$$S\Rightarrow_{G_3}(S)S\leadsto_{G_3}(w_1)w_2=w$$
which shows $P(k+1)$ is true, completing mathematical induction.

All $P(n)$ tell that $L(G_3)\supseteq B$.

Exercise.  Let $G_4$ be the grammar $S \rightarrow  S(S)\mid \epsilon$. Show that $G_4$ also generates the language of balanced parentheses.


How will broadcast behave with a certain capacity? I wanted to confirm something and will appreciate your help. Suppose we have three nodes called A,B and C. All are connected to a switch whose port supports 1 Gbps. Now suppose, Node's A network card is 100 Mbps while the the remaining have a 1 Gbps. Following are the constraints;

A can send B only with a maximum of 100 Mbps.
A can send C only with a maximum of 80 Mbps.

Now if I were to broadcast a 2 GB file;

It would reach B after approx 2.73 minutes.
It would reach C after approx 3.41 minutes.

Now even if I replace node A's network card with 1 Gbps with the same constraints, I would still get the same results. Have I got it right?

I assume you want to broadcast from A.

The fastest is probably to broadcast at 80 Mbps and the end of the broadcast is then at 200 seconds (3.33 minutes) for both B and C.

Broadcasting at 100 Mbps will prevent C for receiving your file, since your switch can't store the exceeding 400 MB.

But I don't understand where do your constraints come from? Would it be possible to make C and B communicate? Also I don't quite understand how you did your calculations.


Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford algorithm can work with and detect -negative edge cycles.

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node $a$ in following graph:

My shortest path tree after running Dijkstra came like this:

Then why texts say that Dijkstra need all non negative edge weights?
I feel that it should be no -ve edge weight cycle reachable from source node.
Am I correct with this? or am I missing something here?

Then why texts say that Dijkstra need all non negative edge weights?

Because it has to work for all cases, not only a few examples.

  I feel that it should be no -ve edge weight cycle reachable from source node.

Try proving that claim and see where it leads. If you're successful, great; if not, trying to prove the opposite will fix your intuition.

See also here for a high-level argument.

   The smallest example where Dijsktra fails has four nodes, no (directed) cycle at all, and no negative-value cycle:


How do you swap consecutive boxes on a Turing Machine tape? I can't figure out how to swap boxes on a Turing Machine tape.

So for example, I have a tape that says

a 1 0 1 1 1 0
^

And I want to move that a over so that it is in the middle. (but my end goal is not important here)

How do I get the Turing Machine to do

1 a 0 1 1 1 0
  ^

1 0 a 1 1 1 0
    ^

etc...

Here is a possible set of transition to do one move, as you request.
Note that $x$ is to be replaced by $0$ and by $1$, so that each
transition with $x$ is actually a pattern to be replaced by 2
transitions, one with $0$ and the other with $1$, instead of $x$ (so you really have 5 transitions below)
And of course $q_{2,x}$ stands for two states: $q_{2,0}$ and
$q_{2,1}$.

I present things that way so that you know what to do if you can have
more than two disctinct symbols to deal with.

The $*$ is just a wild card, indicating that the content of the tape
does not matter.

This will do the required  exchange, with $0$ or $1$. You end up in
state $q_2$, still pointing to the $a$

$\begin{align}
q_1, a&\to q_{1,a},a,R\\
q_{1,a},x&\to q_{2,x},a,L\\
q_{2,x},*&\to q_2,x,R
\end{align}$

I hope this is clear.

What it does is to note $a$ in the finite state control, by going in state $q_{1,a}$, and then moving Right. There it notes in the finite state control whatever $x$ is found there, a $0$ or a $1$, thus going in state $q_{2,x}$, and write down the $a$ (so it can forget it), and moves back Left.
Back on the left square, there is still an $a$, it does not matter, it can write down the $x$ it memorized in the finite state control, and move Right again, in state $q_2$, so that it is pointing to the $a$ that was moved.

Note that the $*$ could be replaced by $a$. The $*$ is a convenient notation to say that it does not matter, as you could have several symbols other than $a$ to be moved in this way.

$q_2$ is whatever state you need to be in after performing one such permutation.


Regular expression over a monoid I'm looking for the name of the following concept.

Given a monoid $(M,\oplus)$, and a finite set of generators $x_1,\ldots,x_n$. The generators are the alphabets.

We define the regular expression on the words formed by the generators. We treat those words just like strings.

For words $x$ and $y$, we write $x\equiv y$ if $x$ and $y$ represent the same element in $M$.

If $R$ is a regular expression, we define $L(R)$ to be the set of strings matched by $R$ and $L_M(R)$ as

$$L_M(R) = \{w'|w'\equiv w,w\in L(R)\}$$.

I'm interested to know if there exist known literature on $L_M(R)$.

Many problems related to $L_M(R)$ are undecidable, because the word problem on $M$ might be undecidable. I wonder if $M$ has a decidable word problem, does it imply we can decide if $L_M(R)=L_M(R')$ for 2 regular expressions $R$ and $R'$.

The sets that can be defined this way are called rational.
As an example, the pairs of input-output strings $(u,v) \in \Sigma^*\times\Delta^*$ of accepted computations in finite state automata on two tapes define rational subsets in $\Sigma^*\times\Delta^*$ (with pair-wise concatenation as monoid operation). The word problem in $\Sigma^*\times\Delta^*$ is trivially decidable, but equality for their rational languages (of pairs of words) is not.

A special collection of monoids that were extensively studied for their rational language decision problems are the so-called trace monoids (or free partially commutative monoids). A special case of these monoids is $\Sigma^*\times\Delta^*$.

An overview of the literature in that area is given by Sakarovich, in his paper "The "last" decision problem for rational trace languages".


Proof that PDA's with different definitions have same expressive power Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$,
where

$Q$ is the set of states,
$\Sigma$ is the input alphabet
$\Gamma$ is the stack alphabet
$\delta$ is the transition function with signature $Q\times(\Sigma\cup\{\epsilon\})\times(\Gamma\cup\{\epsilon\})\to\mathcal{P}(Q\times(\Gamma\cup\{\epsilon\}))$
$q_s$ is the initial state
$F$ is the set of acceptable states.

We suppose that at every transition at 1 symbol of the input string is read, 1 symbol of the stack is popped, 1 symbol is pushed and we can change our state. A general (informal) definition of the acceptance of a string is: we accept the string when we end in an acceptable state with an empty string (whatever the stack contains).

However, there are other possible definitions of the acceptance of a string by $P$. Some possibilities:

The string is accepted when both the string and stack are empty (even when the current state would not be an acceptable state).
The string is accepted when both the string and stack are empty and we are in an acceptable state.

One could also change the definition of the PDA as follows:

One can push more than 1 symbol to the stack in 1 transition.

My question is, how can 1 (both formally and informally) proof that the power of the PDA does not change by using another definition? Alternatively, one could say that the languages determined by the different PDA's are the same.

You prove it the same way you prove that any two models of computation are equivalent: you show that, for every machine of type A, the language accepted by that machine is accepted by some machine of type B, and vice-versa. Sometimes, this is trivial, for example if A is just a restricted version of B (e.g., proving that every language accepted by a DFA is accepted by an NFA). In other cases, it involves simulating the features or acceptance criteria of A using B (e.g., proving that every language accepted by an NFA is accepted by a DFA by using the subset construction).

If you're looking for details of how to prove all the equivalences mentioned in your question, then I think your question is too broad. You should be able to find some of them in any good textbook that covers PDAs, and you'll probably find the rest as exercises because the specific proofs probably use the same general principles.


What techniques can I use to hand-write a parser for an ambiguous grammar? I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a statically typed language, and my desired syntax for a function type renders the grammar temporarily* ambiguous until resolved. I'd rather not use a parser generator, though I know that Elkhound would be an option. I know I can alter the grammar to make it parse within a fixed number of steps, but I'm more interested in how to implement this by hand.

I've made a number of attempts at figuring out the high-level control flow, but every time I do this I end up forgetting a dimension of complexity, and my parser becomes impossible to use and maintain.

There are two layers of ambiguity: a statement can be an expression, a variable definition, or a function declaration, and the function declaration can have a complex return type.

Grammar subset, demonstrating the ambiguity:

basetype
  : TYPE
  | IDENTIFIER
  ;

type
  : basetype
  | basetype parameter_list
  ;

arguments
  : arraytype IDENTIFIER
  | arraytype IDENTIFIER COMMA arguments
  ;

argument_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN arguments CLOSE_PAREN
  ;

parameters
  : arraytype
  | arraytype COMMA parameters
  ;

parameter_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN parameters CLOSE_PAREN
  ;

expressions
  : expression
  | expression COMMA expressions
  ;

expression_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN expressions CLOSE_PAREN
  ;

// just a type that can be an array (this language does not support
// multidimensional arrays)
arraytype:
  : type
  | type OPEN_BRACKET CLOSE_BRACKET
  ;

block
  : OPEN_BRACE CLOSE_BRACE
  | OPEN_BRACE statements CLOSE_BRACE
  ;

function_expression
  : arraytype argument_list block
  | arraytype IDENTIFIER argument_list block
  ;

call_expression
  : expression expressions
  ;

index_expression
  : expression OPEN_BRACKET expression CLOSE_BRACKET
  ;

expression
  : function_expression
  | call_expression
  | index_expression
  | OPEN_PAREN expression CLOSE_PAREN
  ;

function_statement
  : arraytype IDENTIFIER argument_list block
  ;

define_clause
  : IDENTIFIER
  | IDENTIFIER ASSIGN expression
  ;

define_chain
  : define_clause
  | define_clause COMMA define_chain
  ;

define_statement
  : arraytype define_chain
  ;

statement
  : function_statement
  | define_statement SEMICOLON
  | expression SEMICOLON
  ;

statements
  :
  | statement statements
  ;

Example parses:

// function 'fn' returns a reference to a void, parameterless function
void() fn() {}
// the parser doesn't know which of these are types and which are variables,
// so it doesn't know until the end that this is a call_expression
Object(var, var, var, var)
// the parser only finds out at the end that this is a function declaration
Object(var, var, var, var) fn2() {}
(Object(var, var, var, var) ())
(Object(var, var, var, var) () {})
// the parser could possibly detect the "string" type and figure out that
// this has to be a define statement or a function declaration, but it's
// still ambiguous to the end
Object(Object(string, Object), string[]) fn3() {}
Object(Object(string, Object), string[]) fn4 = fn3;

My basic approach has been to write functions that could parse the unambiguous components of this subset of the grammar, and then flatten the more complex control flow into individual functional blocks to capture state in function calls. This has proved unsuccessful, what techniques can one use to solve this kind of problem?

*There is likely a better word for this

I did not read in detail your grammar which is far too large for my
available time, and short of an example that you should provide (since you
assert it is ambiguous) I will not not attempt to check whether it is,
which is in general undecidable.

This said, as already remarked by user rici there are general
context-free (GCF) parsers that will parse any CF grammar, whether
ambiguous ot not. (I am ignoring very old depth first, recursive
decent parser). GCF parsing takes in general a time $O(n^3)$ where
$n$ is the size of the input sentence. However, it will be only
$O(n^2)$ for unambiguous, but possibly non-deterministic grammars.
And they are usually linear for many grammars, or for a significant
subset of the language defined by the grammars (see below).

I think it would be abusive to qualify these parsers as using unbounded
lookahead. Actually they try simultaneously all parsing possibilities
in parallel, and abandon some when further information from the input
becomes incompatible with the attempted parse. This is not the same as
not attempting a parse using some known facts about the rest of the
string, which is what lookahead is about. Indeed, several of these
algorithm may try not to attempt some parses, based on bounded
lookahead information: this is true of Earley's, GLL and GLR.
Furthermore, the concept of lookahead is meaningful for on-line algorithms, which is not really the case for GCF parsers.

The best way to survey this technology is probably a fast historical overview.

The (almost) oldest of GCF parser is the well known CYK algorithm. It
is pure dynamic programming constructed directly on the grammar. It is
extremely simple, but not best in performance.

The next one is Earley's algorithm (1968). Contrary to what is often said, it
is not simple, at least in its general form, and there is no standard
reference that I know regarding the format of the produced parse-trees
(parse-forest). It is not clear that its performances are the best one
might expect.  Earley's algorithm is actually derived in a somewhat ad hoc
fashion from Knuth's LR(k) parser construction. This of course diminishes in no way the importance of its contribution to introducing new parsing concepts.

This was generalized by Lang (1974), who proposed a general dynamic
programming interpretation of any PDA, that could be combined with any
PDA construction technique, such as LR, LL or precedence, giving
techniques known as GLR or GLL parsing. When the technique an yield a
derterministic automaton, the GCF parser works in linear time.

Tomita realized the first implementation of this technique, applied to
LR(k) PDA construction in 1984, thus implementing the first GLR parser. Then it was also used for LL(k) PDA
construction, in this millenium.

Regarding performance, people have often tried to improve it by using
sophisticated PDA construction techniques that have been designed to
increase the number of grammars that can be parsed
deterministically. This folk wisdom is apparently ill-advised, as
analyzed by Billot and Lang (1989). That suggests that efficient GCF parsers can have a fairly simple structure.

All of these parser can work fast enough on modern computers. They
produce all possible parse-trees, in a condensed form called
parse-forest. One issue may be the representation of the
parse-forest which may be more or less convenient depending on the
implementation. Of course, if the CF grammar is unambiguous, there is
only a single parse-tree, which may do away with this parse-forest problem.

A major difference with traditional deterministic parsers is that the
production of the parses is online for deterministic parsers,
producing the left part of the parse-tree in synchronization with
the reading of the corresponding left part of the sentene being
parsed. With the GCF parsers, it is more an offline behavior, as  you may have to wait the very end of the
parsing process before you know what parsing structure is relevant.

Another issue is that I do not know how well parsing errors can be
handled by current implementation. I do know that some very
interesting work has been done on that by the Natural Language
community.

Regarding your own grammar, I think that trying to use these
techniques in a hand written parser is just looking for trouble.  You
woud have to have an excellent mastery of the technology.  There is
just nothing to be gained. But, given the way you state your question, if you want a simple implementation
that you can master, for testing purposes, you may try the CYK
algorithm. It main advantage is that, like Earley's algorithm, it works directly on the grammar, which you may find more intuitive.

Many parser generation system now propose some form of GCF parsing,
but I have no personnal experience with any of them, thus no
recommendations.


Bounded Quadratic Congruence Problem Variant (for some specific Residue) Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x<L$ such that $x^2≡ a(mod\ b)$?

The above problem is NPComplete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Is there some specific value of $a$ (say $a_0$) such that, if we limit the original problem (the residue) to only $a_0$, the problem ceases to be NPComplete (and much easily solvable than the generic case) ?

My guess is for any/each specific $a_0$ the problem still remains NPComplete but I am not certain. Anyone please ?

Yes.  If $a=1$, the problem is no longer NP-complete; the answer to the problem is always "yes, there is such a positive integer".


Does a Non-Deterministic Turing Machine solve all problems in P in constant time? If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?

A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.


Is SGD used in machine learning libraries? SGD (Stochastic Gradient Descent) is used in most libraries of different programming languages. Is it also used in machine learning libraries?

Big yes.

In fact, gradient descent is one of the fundamental tools used by many supervised learning models.

You can check out a very nice docs page about how it is used in scikit-learn.


Deleting vertices so that largest connected component has at most $n/2$ vertices I have a question regarding a graph algorithm which is as follows:

Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such that deleting vertices $1$ through $k$ results in a graph whose largest connected component has at most $n/2$ vertices (when we delete a vertex we also delete all edges incident to that vertex). Give an $O(m \log^* n)$ algorithm that determines $k$.

The graph at the beginning could be disconnected, nor at the end need it be connected.
Since $O(m \log^*n)$ is almost linear, $\log^*n$ grows very very slowly like in union-find data structure so this algorithm is almost linear time like union-find. I am trying to solve it through union find but it seems I am doing something wrong. Now I think that I should use union-find as a black box, but I ca'nt figure it out.

This is a practice problem, not homework.

Hint: Try working backwards, adding vertices to the graph in reverse order $n,\dots,1$.


proving that $P\ne NP$ under an assumption Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$.

What I did:

Suppose that $P=NP$. Then, $P = coP = NP = coNP$.

We know that $P^P = P$.

Then, by assumption: $P^{NP} = NP = coNP$

Since $SAT$ is $NP$-complete we get: $P^{SAT} = coNP$ in contradiction to the assumption.

So $P\ne NP$.

I've been told that my proof is false, but I don't understand why.

Here is a more direct proof. Suppose that $P=NP$. In particular, SAT can be solved in polynomial time. Therefore $P^{SAT} \subseteq P^P = P \subseteq coNP$.


Time series probability and mutual information There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the program just outputs probability of $1$'s and $0$'s. The following are the questions:

How to find probability or correct my code so that it outputs probablities when number of symbols size > 2?
How to calculate entropy annd mutual information for this case. I don't know although I have read Matlab's entropy calculation Mutual Information & Entropy but alas cannot follow how to apply in this case.

Entropy is, in your case

probs = [p_0 p_1 p_2];
logProb = log(probs);
entropy = -1 * dot(probs, logProb);

You'll have to let us know what two random variables you want to calculate the mutual information of, but with your library it looks like you just need to call mutualinfo(vec1,vec2).


why & how are BFS nodes goal tested when they are generated? In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?

The question makes sense as is and it, indeed, stands for a very important difference in how search algorithms are implemented.

Before moving further, let us refer to basic concepts that were certainly defined in your course material:

Definition 1 [Generation of a node] A node $n$ is generated when a data structure representing its contents is created, i.e., when it is allocated in main memory.

Definition 2 [Expansion of a node] A node $n$ is expanded when all its children are generated.

In general, all brute-force search algorithms (or uninformed as they are usually termed in modern literature) "goal test" nodes when they are generated. There is no reason to modify this decision as it suffices for preserving the main properties of search algorithms. Since you mention Breadth-First Search (BFS), let us review its main properties:

Lemma 1 [Completeness of BFS] Breadth-First Search is complete, i.e., it is guaranteed to find a solution, provided that any exists.

The proof is very simple. It just suffices to observe that by storing nodes in a queue, nodes at depth $d$ are expanded only if all nodes at depth $(d-1)$ have been expanded. Conversely, nodes at depth $d$ will surely be expanded, immediately after all nodes at depth $(d-1)$ have been expanded. Hence, it does not matter where the solution node hides, it will be certainly found even if the graph is infinite (but not locally infinite, i.e., solutions might not be found if there are nodes with an infinite number of descendants).

Lemma 2 [Admissibility of BFS] Breadth-First Search is admissible, i.e., it is guaranteed to find optimal solutions provided that any exist.

This is true if edge costs are neglected. Thus, cost of a solution path equals its depth. Since BFS only expands nodes at depth $d$ after expanding all nodes at the preceding depths, once a solution is found, it can be guaranteed to be optimal since we already tested all paths of shorter lengths (or, equivalently, costs).

There's the trick! If edge costs are neglected, then there is a correspondence between path cost and path length.

Now, what about searching in graphs with arbitrary costs? Best-First Search algorithms (termed also as BFS, but I will not to avoid confusion with the preceding algorithm) are devised to handle this case specifically. Dijkstra is one among many algorithms in the family of Best-First Search algorithms.

In this case (i.e., with arbitrary costs), there is not a correspondence anymore between path length and path cost. Hence, an algorithm can not stop once a goal has been generated if admissibility if desired (i.e., the property that guarantees that solutions found are also optimal). Instead, we keep on generating nodes and inserting them in ascending order of cost. This way, once a goal is about to be expanded (and only when it is about to be expanded!) we can certainly ensure that it is an optimal solution, because: (1) all the other nodes in open have a cost which is larger or equal; (2) path cost is assumed to grow monotonically (i.e., negative edge costs are not allowed).

As I said at the beginning, the stopping condition (whether to stop when the goal is generated, or when it is about to be expanded) is critical for the good behaviour of search algorithms. Indeed, many people believe that A$^*$ (which is also a Best-First Search algorithm) with a null heuristic ($h(n)=0, \forall n$) is equivalent to Breadth-First Search. This is not true as there is a critical difference in the stopping condition.

For more details about this, I would recommend you to look at Robert C. Holte. Common Misconceptions Concerning Heuristic Search. Proceedings  of  the Third Annual Symposium on Combinatorial Search (SoCS-2010), pp. 46-51 and, specifically, to page 49.

Hope this helps,


How to solve this big O notation of a fraction I want to estimate with big O the following expressions:

$$
\begin{align*}
f_1(x) &= \frac{x^4 + x^2 + 1}{x^4 + 1}, \\
f_2(x) &= \frac{x^3 + 5 \log x}{x^4 + 1}.
\end{align*}
$$

How do you eliminate the constant on the bottom of the fraction? How would you work to solve these types of problems?

The idea is that $x^4 + x^2 + 1 = \Theta(x^4)$, and similarly $x^4 + 1 = \Theta(x^4)$. So the first expression is $\Theta(x^4)/\Theta(x^4) = \Theta(1)$. The second expression can be estimated similarly.

This sort of calculation shows the advantage of asymptotic notation - irrelevant details disappear and calculations become manageable.


What does pre-, post- and in-order walk mean for a n-ary tree? The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and right child. If it can be used for n-ary trees, how?

An n-ary tree has 1 parent and n children at any given node. Where n can be any whole number for each node.

Please use the figure below to explain this, if you need one.

No, it's not limited to binary trees.  Yes, pre-order and post-order can be used for $n$-ary trees.  You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function".  We assume that the for-loop will iterate through the children in the order they are found in the data-structure: typically, in left-to-right order, for a diagram such as you have shown.

In fact, this is already described in the Wikipedia article on tree traversals: see https://en.wikipedia.org/wiki/Tree_traversal#Generic_tree, which describes exactly how to generalize this to $n$-ary trees.  Pre-order traversal is one where the pre-order operation is "Display the current node" and the post-order operation is "Do nothing".  Post-order traversal is one where the pre-order operation is  "Do nothing"  and the post-order operation is "Display the current node".

In-order traversal is a special case.  It probably only makes sense for binary trees.  While there are several different possible ways that one could define in-order traversal for $n$-ary trees, each of those feels a bit odd and unnatural and probably not terribly useful in practice.  So, it's probably best to think of in-order traversal as being specific to binary trees; if you want to do something akin in-order traversal for a $n$-ary tree, you'll need to decide exactly what you mean by that, as there's no standard meaning for that.


Jamming signal useless in CSMA / CD? I'm looking at collision detection in communication protocols, in particular Carrier sense multiple access with collision detection (CSMA/CD). According to what I've read on Wikipedia, a collision seems to cause the wave of the outgoing signal and the wave of the incoming signal to overlap. Thus, the signal has values with more amplitude than allowed for a "1-bit". This could be used as a working collision detection algorithm.

However, what's the use of the "Jam signal", as explained in the same Wikipedia article, then? It says that the CRC has to be faulted, but we already have a collision detection algorithm.

Wave overlaps need not cause just 1-bits with a too high amplitude. They could also flip bits around, or nullify each other. Thus error correction is not as easy as you describe and one actually has to use some kind of checksumming like CRC to detect errors reliably.


How to show that hard-to-compute Boolean functions exist? How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute?

This problem was originally stated in Exercise 3.16 of Nielsen & Chuang's Quantum Computation and Quantum Information.

There are only so many circuits using at most $m$ gates, say $f(m)$. If all Boolean functions on $n$ inputs could be computed using at most $m$ gates, then $f(m) \geq 2^{2^n}$, since there are $2^{2^n}$ Boolean functions on $n$ inputs. Hence if $f(m) < 2^{2^n}$ then there must be a function on $n$ inputs which cannot be computed using at most $m$ gates.

A Boolean circuit with $m$ unbounded fan-in gates can be simulated using at most $m^2$ binary gates. We can describe each binary gate by satisfying its inputs and its type (AND, OR, NOT), for a total of $O(m^4)$ possibilities per gate. This leads to a rough bound $f(m) = O(m)^{4m}$. If $m = C 2^n/n$ then
$$
f(m) = \exp O(m\log m) = \exp O(C 2^n),
$$
and so for an appropriate choice of $C$, we would get $f(m) < 2^{2^n}$. This shows that there are some Boolean functions which require at least $C 2^n/n$ gates to compute. It turns out that (up to the choice of $C$) this bound is tight. (So what you wrote in your post is actually wrong.)


Floyd–Warshall algorithm on an undirected graph contains negative weight edges According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances to all vertices in a negative cycle, as well as the distances to the vertices reachable from this cycle,  are not defined. So in the all-pairs shortest path problem, can we say the Floyd–Warshall algorithm also doesn't work on an undirected graph contains negative weight edges for the same reason?

Perhaps it is useful to be more precise about what is meant by "doesn't work".  If the directed graph contains a cycle of negative weight, then the notion of shortest path is not well-defined.  Therefore, it makes no sense to run a shortest-path algorithm on such a graph.   There's no hope for any algorithm to output the shortest path in such a graph, because there is no shortest path.

If you have an undirected graph with negative-weight edges, and you convert it to a directed graph in the obvious way, you'll end up with a directed graph that contains negative-weight cycles.  Consequently, no shortest path algorithm has any hope of success at finding shortest paths: there is no directed path (in the directed graph).  It doesn't matter what algorithm you are considering using.

Basically, the conversion from undirected graph to directed graph, in shortest path problems, is only correct if all weights are non-negative.  If all edge weights are non-negative, then the shortest path in the undirected graph corresponds to the shortest path in the directed graph you obtain in this way.  However, if the undirected graph has negative-weight edges, then there is no longer any such correspondence, so the conversion is not useful.


challenge: Closing hash, linear probing, probe length 1 The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element,
it discards it directly (that is, it does not try to place it in positions 0, 1, 2 ... as it would be correct)

In a hash table using closed hash, linear probing, probe length 1.

What is the probability that with this test we discover that the implementation n has a bug, if N = 27 and K = 42?

Example K=2, N=2:
The only case is if both hashes are 1. In this case, the first element in array [ 1 ] is first saved.
Then, the next element does not have space in array [ 1 ] and since it is the last position of the array, will discard it

I made a script to bruteforce all combinations and find the probability for the firsts N / K

The pseudocode is:

function bruteforce(array):
  hashtable=
        {0="" , 1="" , ..., ..., k-1=""}
  for element in array:
      canStoreThisCombination=False
      for j in range (element,len(hashtable)):
          if (empty(hashtable[j])):
              hashtable[j]="used"
              canStoreThisCombination=True
              break
  if not canStoreThisCombination:
      tot=tot+1

for each combination of N elements:
  bruteforce(actualCombination)

print tot/(k^n)

and got the following results:

table

Combinations for K=3

Combinations for K=4

Combinations for K=5

I'm looking for probability as an irreducible fraction

This problem was formulated and solved in 1962 by Donald Knuth; apparently, it was his first exercise in algorithmic analysis. It's often referred to as the "parking problem".

Knuth's analysis is beautifully simple. (Note: Knuth, and I think most computer scientists, used $n$ as the size of the hash table, and $k$ as the number of items inserted. So do I, even though the question is expressed differently.)

Let's start with the set $A$ of hash values of $k$ items, consisting of all sequences $\langle a_1, \ldots, a_k \rangle$, where $0 \le a_i < n$. Clearly there are $n^k$ possible sequences.

Now, suppose we have a bug-free hash table of size $n+1$, and look the set $B$ of all possible hash sequences for $k$ items,  $\langle b_1, \ldots, b_k \rangle$ with $0 \le b_i < n+1$. There are $(n+1)^k$ such sequences.

Of those sequences, we select the subset $B'$ for which the last table entry ($n$) is empty at the end of the insertion. Since once a slot is occupied, it remains occupied at the end, we know that for every sequence in $B'$, every $b_i < n$. Therefore, every sequence in $B'$ is also in $A$.

Moreover, we know that in the course of the insertion, no probe passes through position $n$. In other words, every sequence in this subset of $B$ is a sequence in $A$ in which there is no wrap-around, which are precisely the sequences in $A$ which do not trigger the bug.

So it will only remains to count these sequences. But that's trivial, because all of the slots in the (bug-free) hash table are identical. So the probability that a particular slot will be unoccupied after inserting $k$ items is $1 - {k \over {n+1}}$, with the result that there are $(n+1-k)(n+1)^{k-1}$ such sequences.

Thus, the probability that a random sequence of $k$ insertions into the buggy hash table will trigger the bug is $1 - {(n+1-k)(n+1)^{k-1}\over n^k}$.

By the way, the output of the program you paste-binned is not correct.  For example, it lists $4, 4, 4$ twice in the list for three insertions into a table of size 5.


Is there a problem in this BN form language? I am working on a simple text query language.  I am using the SLY parser, which itself is an LR parser/shift-reduce parser.  I am running into problems with the following language specification, but I don't understand why.  All I'm trying to do is appropriately group logical statements involving the operators AND and OR (in which AND gets precedence over OR and the statements are left associative) and "words", which is basically anything other than "AND" or "OR".  The language is below.  What is the problem?

LOGICAL ::= <WORD> <OPERATOR> <WORD>
        | <WORD> <OPERATOR> <LOGICAL>
        | <LOGICAL> <OPERATOR> <WORD>
        | <LOGICAL> <OPERATOR> <WORD>

OPERATOR ::= "AND"
            | "OR"

WORD ::= any string other than "AND" or "OR"

Also, for the record I don't know how to express "WORD" in a more formal way, so I'd appreciate any input.

That grammar has two problems.

It's ambiguous. You say that you want to give AND precedence over OR and make both operators left-associative, but your grammar does not reflect that goal since it does not distinguish AND from OR and it explicitly accepts both left- and right-associative parses:

<WORD> <OPERATOR> <LOGICAL>    (* right associative *)
<LOGICAL> <OPERATOR> <WORD>    (* left associative *)

On a more minor level, probably a typo, your third and fourth productions are identical.

It's possible that you have tried to fix the issue by using precedence declarations in your parser generator tool. Precedence declarations are not part of BNF, and incorrect precedence declarations are really a programming error, rather than an issue in parser theory.

If you have such a problem, you should probably ask a question on a programming site, such as StackOverflow, and comply with the usual rules of including a complete reproducible example. However, in the usual approach to using precedence to resolve parser ambiguity, it is important that you don't have explicit parser ambiguity, as above. Thus, a "traditional" precedence-augmented BNF grammar (as per the Dragon book) would look like this:

%left <OR>
%left <AND>

<LOGICAL> ::= <WORD>
          |   <LOGICAL> <OR> <LOGICAL>
          |   <LOGICAL> <AND> <LOGICAL>


Fastest mode of data transfer Which of the following modes of data transfer is the fastest?

a. DMA

b. Interrupt-based

c. Polling

d. All are equally fast

I do not have the answer, so I cannot check, that's why I am posting here.

I think the answer is D. All are equally fast. In all data transfer cases the speed of data transfer is same, but in case of DMA we save CPU time by that we improve the efficiency of CPU since data transfer job is done by DMA. Is my understanding correct ?

First, "fastest" is an ambiguous term--it can refer to latency or throughput/bandwidth.

Second, DMA is orthogonal to interrupts and polling.  I.e., the completion of the DMA can trigger an interrupt or be determined by polling an I/O register (or the memory that is being written in some cases).  (Explicit processor copying to/from memory is the alternative to DMA.)

Third, the tradeoffs between polling and interrupts will vary depending on the hardware.  In general, because an interrupt involves saving and restoring processor state, it has higher latency (saving and restoring state takes time).  When I/O events are extremely frequent and of a limited number of types, the overhead of repeatedly reading an limited number of I/O registers will be less than the overhead of context switching.  (Obviously, increasing the number of events polled--in terms of unique I/O registers or memory accesses--decreases the relative disadvantage of interrupts.)

With polling, the polling thread is taking up processor resources that could otherwise be used to run other code and the reading of an I/O device register (or ordinary memory location) when the polled event has not happened (the probed value has not changed) uses bandwidth that could otherwise be used for productive purposes.  Excessive polling could also reduce the availability of buffers between processors and I/O devices, delaying fast I/O communication behind slow communication (and in some cases the I/O bus is optimized for larger packets so small read responses [which do not communicate any new information] would waste bandwidth).

However, hardware can optimize interrupts in several ways.  It can coalesce interrupts at the I/O device or at an intermediate point between I/O devices and the processor.  At the processor, it is possible to fold interrupts together so that instead of immediately returning from an interrupt (with the overhead of restoring state) a pending interrupt is handled.  Some processors also have shadow registers that are used to avoid the need to save and restore state on interrupts.  (Software can also combine the use of interrupts and polling by performing some polling while in the interrupt handler.  This can reduce the number of interrupts.)

In theory, hardware could also reduce the overhead of polling with multithreading and throttling the execution of a polling thread that is not performing useful work.  (Even with efficient polling--where every read indicates an I/O has completed--multithreading can allow work to be done while waiting for the read of the I/O device register to be completed--this tends to have relatively high latency.)

In a very theoretical sense, I/O device register values could be pushed into cache when they change (a variant on DMA).  Such could reduce the wait time for reading such values (helping both interrupt handlers and polling) and facilitate hardware thread throttling (because the processor could quickly determine that no change had occurred).  However, such is incompatible with how most ISAs are defined and with how I/O devices are implemented, and such would greatly increase the complexity of the system.


When describing a CS paper, can it be assumed that the meaning of "tick" is known? I thinkt this question fits better here than on english.stackexchange.

When describing a figure in a computer science paper, is it safe to use "tick" meaning "tick mark"?

Examples:
... (see the thick line right of tick "17")  meaning tick mark "17"
or ... increase at tick "1e+02" ... increase at tick mark "1e+02".

I've never heard those marks on the axes referred to as "ticks", though Wikipedia agrees with your usage.  Since Dave Clarke also didn't realise that's what you're talking about, I suspect that at least a sizeable minority of people aren't familiar with the term.

Why do you need to talk about the marks on the axes at all? Instead of saying "increase at tick mark '1e+02'" just say "increase at $x=100$" or whatever the variable is on that axis.  (Also, it's silly to use the notation "1e+02" for such a simple concept as 100.)  Your writing will be easier to understand if you talk about the data, rather than talking about the precise details of how you chose to represent it.


Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other? Consider 2 DFAs both determining a language $L$. Both DFAs have the same number of states $n$. Can I then conclude that these two DFAs are isomorphic?

I think the answer is yes, because if I'd make an $MN(L)$ relation with $n$ equivalence classes and map it to a $DFA$, there'd only be one result (at least I believe so). Thus both of the DFAs map to the same $MN(L)$ relation.

Is this reasoning correct?

Let $M$ be a DFA for the language $L$ and let $M_1$ and $M_2$ be $M$ with two different collections of some number $m$ of unreachable states added. $M_1$ and $M_2$ both have the same number of states and both accept $L$, but they need not be isomorphic.

For a less trivial example, consider the following two DFAs:

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 1
2 -a-> 3   2 -b-> 2
3 -a-> 4   3 -b-> 3
4 -a-> 1   4 -b-> 4

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 3
2 -a-> 3   2 -b-> 4
3 -a-> 4   3 -b-> 1
4 -a-> 1   4 -b-> 2

These two 4-state DFAs are non-isomorphic, but both accept the same language, namely the language of all strings over the alphabet $\{a, b\}$ which have an odd number of $a$s.

Note that if two DFAs accepting the same language have the same number of nodes, and that number is minimal among DFAs accepting that language, then the two DFAs must be isomorphic. See DFA minimization.


Find the k length path that maximize a node associate metric Let's say I have :

a Graph g
v vertices. Each vertex is associated to a cost c.
A special vertex called the starter vertex or vs.

I want to find the path p of length 10 (for example), that start from vs and that maximize the sum of the 10 seens nodes costs. I need to tell you that my graph represent a road network which means it has a big diamater, and the degree of each node is never above 6 or 7. Here is an example of the kind of a graph that I have. Obviously, I got way more nodes.

A brute-force approach is to do a backtracking search starting from $s$.  Something like:
Search($s$, $n$, $S$):

If $n=1$, yield $S \cup \{s\}$ and return.  Otherwise:

For each vertex $v$ that is adjacent to $s$, do:
a. Call Search($v$, $n-1$, $S \cup \{s\}$).

If you invoke Search($vs$, $10$, $\emptyset$), this will generate all possible sets of vertices that can arise from a path of length 10; now calculate the cost of each such subset, and keep the largest one.
$6^{10}$ is about 60 million, so this might complete within a few seconds on most graphs.


Propositional Logic: Entailment Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct?
A ∧ ¬A |= B
How can something and not something equate to true?
I am stuck trying to work out how true and false can still entail true, actually how can A and ¬A occur at the same time?
Thanks.

It's not easy to give a full explanation without knowing your axioms and rules, however, $A \land \neg A$ is a contradiction, and it is by exploiting that, that you can prove whatever you like.
First, let $\top = A \lor \neg A$.
We know that "true or whatever else" must be true.  Since $\top$ is a tautology, then $\top \lor B$ must be true.
But since $A \land \neg A = \neg (A \lor \neg A) = \neg \top$ is assumed to be true we conclude the following:

from $\top \lor B$ and $\neg \top$
$B$

It all hinges on the fact that $A \lor \neg A$ is a tautology and that you assume that the negation of a tautology is true.
So to answer your question "actually how can $A$ and $\neg A$ occur at the same time?" It cannot, unless you have a contradiction.  When you assume a contradiction, you can prove anything.


How do you compute the time complexity of distributed algorithms? How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(1)$ time due to the unreliability in the time it takes to pass messages. Since this approach is not practical at all, I am assuming that I have not understood it properly. Could someone please explain?

By impractical, I mean that I can simply solve any NP-Hard problem in distributed computing trivially in $\mathcal{O}(n^2)$ time by passing information throughout the network and then brute-forcing for the solution in $\mathcal{O}(1)$ time and this obviously seems stupid since in real life message passing shouldn't take more time than a brute-force solution over the search space.

Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the total number of operations will be higher.

Because of the high variability, and the overall time taken, often distributed algorithms are measured in terms of the number of messages sent. So in your example, you'd only solve it in $O(n^2)$ time if you assume that there is no cost to sending messages. If you're sending each possibility to a node, a good model will incorporate that cost, and you won't get magically fast solutions to $NP$-hard problems.

Also, for parallel computing, you model (approximately) how many nodes you have. It's a safe-bet to assume that you don't have more than $O(\log n)$ nodes for an input of size $n$. You certainly won't be able to scale your nodes exponentially, so brute-forcing doesn't always work.

Often, the computation done in distributed algorithms is minimal, or the computational content itself is intense, but orthogonal to the distributed nature of the algorithm (i.e. the algorithm is written over some abstract, computationally intensive task). In these cases, you usually only care about the messages sent or some other cost metric, since you might never know how many steps your computation takes.


NLP Classification: rule-based approach providing high precision but low recall In NLP, rule-based/linguistic approaches are usually said to provide relatively high precision but low recall compared to for example machine learning approaches. I think this is often true for almost any classification task in NLP. However, I couldn't find a paper which specifically examines this phenomena. Can someone please name one? Alternatively, I'd be interested in a paper which generally compares different approaches in NLP classification tasks.

I did quite some googling but all I found is a very vague statement in here: http://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-15-285

I dont have enough reputation to add this as comment. Maybe this survey of text classification algorithms (including rule-based approach) could help you http://www.time.mk/trajkovski/thesis/text-class.pdf


How would a Turing Machine recognize n consecutive characters I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters of type a in the string. The formal definition for the input language is:

$$ L=\{ \{w,n\}\in\{a,b\}^*\times \mathbb{N} \mid n\neq 0, \exists \alpha,\beta\in\{a,b\} \text{ s.t. }w=\alpha a^n\beta\}. $$

What I do not understand is how could I hold the count since I need to have exactly n characters.

What answer I came up with would be this. We would use a TM with 2 tapes, t1, t2 and 2 headers h1, h2.

P0. Scan the first tape with the input, if a character ∉ {a, b}
REJECT.
P1. Write "#" and n character of "1" on t2, the head remaining
in the right extremity.
P2. Read characters on t1 and while they are "a" repeat P3, P4.
P3. Move h1 to the right
P4. Read the character on t2 and if it's "1" move h2 to the left, if it's "#" move h2 to the right extremity.
P5. If the read character on t1 is "b" repeat P6
P6. Read the character on t2, if it's "1" move h2 to the right extremity, if it's "#" ACCEPT
P7. Getting at the end and not accepting means we REJECT

I had no example so I am not sure this is 100% correct but it's what I came up with after few hours of thinking. Hope it helps someone and please correct me if it's wrong.


Regular expression (ab U a)* to NFA with two states (Sipser)? In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA.
And then the text ends with: "In this example, the procedure gives an NFA with eight states, but the smallest equivalent NFA has only two states. Can you find it?"
Nope. I can't.
After a good deal of head scratching, I've convinced myself that it's not doable. But being a novice, I'm probably wrong.
Can anyone help? Thanks!

Mouse-over the yellow box to see an NFA that accepts the language.


Proving $L = \{a^iba^j|i\ge2j\ge0\}$ isn't regular I need to prove the following language is not regular, I think I need to use the pumping lemma. The trouble I am having is that there is multiple variables and I am not used to that.
Could someone tell me if the pumping lemma is the correct proof by contradiction of
$$L = \{a^iba^j|i\ge2j\ge0\}$$

I took $xyz = a^{2p+1}ba^p $
so
$|xy| = 2p+2$ which is greater than $p$ and must be false.
Is this solution correct?

As noted, you need to be careful making assertions about $xy$. Recall that the pumping lemma says that if $L$ is a regular language, then there is a positive integer $p$ such that any string $s\in L$ can be written as $s=xyz$ where

$|xy| \le p$,
$|y| > 0$,
$xy^iz\in L$ for all $i=0,1,\dotsc$.

so in your example all you know is that $|xy|\le p$. You certainly can't assert that $|xy|=2p+2$.

All is not lost, though. If you assume that $L$ is regular and let $s=a^{2p}ba^p$ (notice that I chose a different string to pump), then since $|xy|\le p$, you know that $xy$ "lives" among the first group of $a$'s, and so $xy=a^k$, for some $k\le p$. Hence $y=a^t$ for some $0<t\le p$ and so the PL assures us that $xy^iz\in L$ and we have $xy^iz=a^{2p+(i-1)t}ba^p$. [Do you see why?] Now all you have to do is pick some $i$ so that $xy^iz\notin L$ to establish a contradiction and thus show that $L$ isn't regular.

I'll leave the rest for you: what $i$ can you use to show that $xy^iz\notin L$?


Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN} Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable.

$\text{EVEN} = \text{binary strings with even length}$

$Let\;A = \{(M) | \,M\; \text{is a DFA such that L(M) is not the same as EVEN}$

$\text{Show that A is Turing-recognizable}$
$\text{Show that A is decidable}$

So, at first glance it seems we need to just find a word that M accepts that is an odd length binary string. I'm a bit lost at where to start though.

I believe I'd start by using the TM from Theorem 4.1 of Sipser's Introduction to Theory of Computation which states if a DFA is a decidable language we can use Turing machine T to test if it's decidable:

$\text{T = "On input (B,w) where B is a DFA and w is a string:}$

$\text{Simulate B on input w}$
$\text{If the simulation ends in an accept state - accept, otherwise reject"}$

The language is clearly recognizable: given a DFA $M$, simulate it, in minlex order, on every word, and see if there is a word $w$ such that $|w|$ is odd, and $w$ is accepted by $M$, or if there exists a word $w$ such that $|w|$ is even, and $w$ is not accepted by $M$. In both cases - accept.

However, this machine doesn't show the decidability of the language.

In order to decide the language, it is easier to proceed as follows: Let $A$ be a DFA that accepts the language EVEN. Fix such a DFA.

Now, given $M$, we need to decide whether $L(M)=L(A)$. If you feel comfortable with automata, you can just say that this is decidable, and that's it.

If you're not that comfortable yet, consider the following:
Given two DFAs $B,C$, it is easy to construct a DFA $D$ such that $L(D)=L(B)\cap \overline{L(C)}$, and it is also easy (well, decidable in NLOGSPACE) whether $L(D)=\emptyset$. The latter test is equivalent to deciding whether $L(B)\subseteq L(C)$. Thus, you can decide whether $L(M)\subseteq L(A)$ and $L(A)\subseteq L(M)$, which amounts to deciding whether $L(A)=L(M)$, and you are done.


Hidden Markov Model in Tagging Problem I try to understand the details regarding using Hidden Markov Model in Tagging Problem.

The best concise description that I found is the Course notes by Michal Collins.

The goal is to find a function $f(x)=arg max_{y \in Y} p(y|x)$, where $y$ is the tag set for sentence $x$.

Question 1. It's suggested to use a generative model and to estimate joint probability $p(x,y)$ from the trainig examples, however what the the reason to use generative model and increase the number of computation why not directly to estimate $p(y|x)$, I think it's possible to estimate the conditional probability straightforward from the training data.

Addendum. Do you know the reason why at all we should try to use a generative model in this case (POS tagging). As I  understand if we can estimate $p(x,y)$ that exactly with  the same success we can estimate $p(y|x)$  and directly find the answer to the question, what is the best tagging - $\hat{y}$ without weak assumption of generative model. There is the reason to use generative model, and I don't see it yet. Can you explain me what the reason?

Question 2. Assume we decided to use a generative model and made estimation to $p(x,y)$ why we decide to decompose it as follows $p(x,y)=p(y)p(x|y)$ and not  $p(x,y)=p(x)p(y|x)$?

Addendum. I do understand that it's very logical to use the decomposition $p(y)p(x|y)$ just because by doing it we approach $p(y|x)$, so mathematically it seems very reasonable, however according to the task I don't see what the problem to decompose it like $p(x,y)=p(x)p(y|x)$, there should be sore reason why we can not decompose it so and I don't understand why.

I appreciate your help.

Answer 1

You can try to directly fit the function $\Pr[y | x]$. This is called a discriminative classification. This is typically solved via some regression mechanism such as ordinary least squares, or lasso, or ridge depending on certain assumptions of the model.

Answer 2

The reason we want to factor $\Pr[x, y] = \Pr[x | y] \Pr[y]$ is because we are interested in the class conditional density $\Pr[x | y]$. That is, what is the probability of observing data $x$ given the label $y$?

There are various pros and cons to both discriminative and generative classification. For example, generative models tend to be easier to fit [naive Bayes is maximized simply by counting, whereas discriminative requires solving some convex optimization problem]. However, discriminative models typically faire better under independence assumptions when fitting data.


What's the difference between a calculus and a programming language? I think I'm pretty confused about what's called a calculus and what's called a programming language.

I tend to think, and might have been told, that a calculus is a formal system for reasoning about the equivalence of programs. Programs have an operational semantics specified by a machine, that should (I think?) be deterministic. In this way, a (correct) calculus for a language $L$ is a proof method for program equivalence.

This seems like a reasonable split to me, but is this the commonly accepted meaning? Or maybe it's even wrong?

Related, why are some operational semantics nondeterministic (assume it is confluent)? What is gained from leaving the choice of strategy open?

I'd really appreciate some clarification on these; and concrete references even more! Thanks!

The meaning of the words is not fixed, but I can give you my interpretation.

A calculus is something that we calculate with in the sense of juggling equations (think manipulation of Taylor series or computation of integrals in analysis). A calculus tells us what the rules of manipulation are, but not which ones we should used in a given situation.

A programming language is something that tells us how to calculate. It tells us precisely how to use the rules. We typically let the computer use the rules, as it is much faster. The rules may be non-deterministic, and there may be very good reasons for them being non-deterministic. It may be in the nature of the calculus that it is non-deterministc (think concurrent communicating processes), or fixing a particular strategy may be detrimental to implementation techniques and optimization.

For example, the $\lambda$-calculus is an equational theory. There are expressions and equations telling us when expressions are equal. The equations do not tell us how to apply them, although people usually have hidden agendas and they present the equations so that later on they can derive useful evaluation strategies from them. But in its essence $\lambda$-calculus is a bunch of equations. It is not a programming language.

In contrast, Standard ML is a programming language. It  is given in terms of operational semantics, i.e., rules of computation. There are derived notions of equality (contextual equivalence, observational equivalence, etc.) which we can put on top of it to think of it as a kind of calculus.

Of course, there are often useful connecitons between a calculus and its manifestation as a programming language. Confluent normalization is just one way of passing from the calculus to the programming language (although sadly some people have made it into a religion of sorts). The interplay between calculi and programming languages is important: the programming languages can actually be used, but the calculi explain what the programs are about.

Just to annoy people, let me also state that pretending that there is no difference between a calculus and its operational manifestation sometimes leads to skewed views of programming and mini-religions within the programming community. You may try to guess which language I have in mind. (It's a very cool language!)


Getting minimum DFA for regular expression (11)*+(111)* (sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too)

The language corresponding to given regex seems to accepts all strings of 1's with length in multiple of 2 or 3 (i.e.4,6,8,9,10,12,...)

I prepared following NFA first:

Figure 1

Then I followed steps given here to prepare DFA.
First I prepared below table to get equivalent DFA steps:

Figure 2

Then I prepared below DFA, which seems to be quite correct.

Figure 3

Next to get equivalent states I followed table filling algorithm as explained [here]
(http://books.google.co.in/books?id=tzttuN4gsVgC&lpg=PP1&pg=PA144#v=onepage&q&f=false)
and formed below:

(cross between every intersecting column and row indicates two intersecting states are distinguishable / not equivalent)

Figure 4

But I dont get from above table how can I get below minimized DFA as given in the book solution:

Figure 5

So in the solution of the textbook, their is one less state (total 6) than my dfa in figure 3 (which has 7 states). I should be able to derive the same (equivalent 6-state dfa) from above triangular table.

The problem is that you did not make state $A$ accepting during $\epsilon$ transition elimination. Since it has $\epsilon$ transitions to accepting states, you should have done so. As a result, the automaton you obtain doesn't accept the empty word as it should. If you fix this, minimization then merges $A$ with $B,D$.


integer factoring using Fermat's method Reading an article on integer factorization I implemented the following -  rather inefficient - factorization method:

  Every odd
  composite can be factored as a difference of
  squares: $$ ab = \left[\tfrac{1}{2}(a+b)\right]^2 -
 \left[\tfrac{1}{2}(a-b)\right]^2$$
  We can look at values of $f(x) = x^2 - n$ until we find a perfect square and factor.

Here's my implementation in Python.

def fermat(n):
    x = int(np.sqrt(n))+1
    y = int(np.sqrt(abs(y*y - n)))

    while( n - x*x + y*y != 0):
        x += 1
        y = int(np.sqrt(abs(x*x - n)))

    return x, y

How expensive are the square root calculations here?  Are they necessary?
In order to check I have a perfect square, I compute $\lfloor \sqrt{x^2-n}\rfloor$ many times.

Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing floating-point square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and moreover the range of floating-point numbers is limited. Use a bignum package instead.


Check whether all elements are different Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer between $1$ and $n$ and which can be calculate in $O(1)$ time. Let $m := \{(i,j) : a_j  \neq a_i \text{ and } h(a_j) = h(a_i)\}.$

How can i check if all $n$ elements are different in $O(n+ |m|)$ time and $O(n)$ memory?

1) The naive approach would be to check all $n$ elements if there is another element with the same value, which requires $O(n^2)$ time.

2) A better way would be if i sort the elements, which needs $O(n \cdot \log(n))$ time and then check each adjacent pair of elements. In total it would be $O(n \cdot \log(n))$.

But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how.

This sounds like an assignment, so I'll just give you a few things to think about:

Using a hash table/hash map allows you to access elements in near $O(1)$ time. The only reason it's not exactly $O(1)$ is because of the collisions, $m$.
Given two elements $a_i$ and $a_j$, if $h(a_i) = h(a_j)$, the two elements may or may not be equal. The hash table has to handle this collision in some way; you may then have to go back and check for actual duplicates.
On the other hand, if $h(a_i) \neq h(a_j)$, it's necessarily true that the elements are NOT equal. $a_i$ and $a_j$ are stored in separate locations in the hash table.
Think about the worst case test case; what would happen as you build up the hash table?


Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2? The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the title, please tell me in your answer then I will try to make the title much clearer.
Suppose we have a list of integers $x_1, x_2,\ldots,x_n$, what we want to find is the smallest integer $y$ such that all the given integers can be found through the process of dividing $y$ by 2 (on the division tree). More specifically, the results of dividing $y$ by 2 are 2 integers: $⌊y/2⌋$ and $⌈y/2⌉$.
Example: for integers 1, 1 and 3, it is easy to prove that the lower bound of y is the sum of them, 5. As for 5, we can get all the integers we want by dividing itself: dividing 5 we get 2 and 3, where 3 is an integer we want; dividing 2 we get 1 and 1, all of which are expected results. Therefore, all the integers we want can be found in the process, 5 is the smallest integer $y$ we want.
Another example: for integers 2, 2 and 6, the lower bound of y is 2+2+6=10, but 10 is not a suitable candidate for y since 10÷2=5<6, it cannot generate 6 in the process. However, if we plus 1, then 11 is the dream y we want. An illustrational graph is shown in the link:
Notice that once we get an integer we want on the division
tree (i.e. for the 2nd example above, get 6 in a branch of 11), we should accept it as a part of the result, stop dividing it and concentrate on results on the other branch. There also could be some redundant integers generated (i.e. 1 for the 2nd example above), and we just leave them alone.
In all examples above, the smallest integer $y$ is found by trials, not a systematical algorithm. I just cannot come out with an algorithm to find $y$ systematically, and my question is how to find the algorithm.

$x_1=5, x_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.


Why are computers so reliable? In any complicated system, there is always some scope for error. When I program on my computer, the system computes perfectly each time. 1+1 always turns out to be 2. We take reliability of the computer almost for granted. What gives modern computers it's reliability? Are there no errors in computation, or errors, if any, are corrected by some means?

Computers rely on physics. Transistors have some known characteristics, given some assumptions on making process. Parts that does not meet the exepected characteristics are just trashed (or sold with lower expectations, usually lower max frequency).

This ensure that computations are correct while complying operation conditions (stable power supply, EMC, ...). The whole systems are built to meet those requirements. When you use very cheap equipment (often a cheap power supply), you may face some computer crashes, as you do not meet system requirements (power supply stability) anymore.

Sometimes, external conditions make expectations unreachable. In aeronautic and aerospace, systems have to cope with cosmic rays that may disturb their behavior. In such case, several similar systems are used in parallel, to be able to maintain operation when one system has errors.

Also, some transmissions and storages are known to be unreliable, and Error Correction Codes are used to fix the data after reception.

So systems are designed to prevent errors to happen in almost every cases, using a broad range of dedicated methods. Working in consumer electronics, I have some failure rates on the hardware around 10 faulty parts per million in the first year of use. This is much better than the mechanical parts or the software, but not perfect (even if it's too good for the consumer market. Average return rate on consumer products is around 1%, 100 faulty parts per million would be acceptable on this market).


Sampling among constrained partitions I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones.

Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ and would like to sample among reflexive, symmetric and transitive relations $R \in O \times O$ such that samples satisfy a set of must-link/cannot-link constraints. More specifically, I do have for some pairs $o_i,o_j$ either that $(o_i,o_j) \in R$ or $(o_i,o_j) \not\in R$. Alternatively, I could see it as the problem of sampling graphs that are disjoint cliques with pre-specified arcs or absences or arcs.

Reject sampling is likely to not work in practice, as the number of rejection would quickly be prohibitive as n and the set of constraints get high enough (something we can expect).

Do any of you know if this problem has been treated, or any easy way to solve it? Uniformity within the set of samples is desirable, but not absolutely necessary.

Thanks.

A reflexive, symmetric and transitive relation $R$ on $O$ is the same as a partition of $O$. If $(o_i,o_j) \in R$ then $o_i,o_j$ are in the same partition, and so can be merged. If $(o_i,o_j) \notin R$ then $o_i,o_j$ are not allowed to be in the same partition. After merging, we reach the following problem:

  Given a graph, partition the set of vertices so that each partition is an independent set.

Equivalently (up to a permutation of colors):

  Given a graph, find a proper coloring.

Intuitively, it seems that a random partition will have many parts, so you can try to generate a random sample in the following way. Greedily sample a "small" independent set whose size you choose in advance as a Poisson random variable with constant expectation, remove it from the graph, and repeat. Of course, this won't be a uniform sample. You can gather statistics in some small cases to see what is a good choice of parameters in this procedure, and whether the results are good enough for your purposes.


How to show that all 2-terminal SP-graphs are O(log n)-outer-planar I am trying to show that every 2-terminal SP-graph is $O(\log(n))$-outer-planar for a challenge question on my assignment. In particular, I am trying to prove this by induction on the number of combinations (either a series or a parallel combination). This is what I have so far.

The base case on $0$ combinations is that we just have some edge $(s, t)$. Clearly this is outer-planar and so $O(\log(n))$-outer-planar as well (in this case, $\log(2) = 1$, so this does hold).

Now we do the inductive step. Given some 2-terminal outer-planar graph $G = (V, E)$, we will show that it is $O(\log(n))$-outer-planar, where $|V| = n$. Since $G$ is a 2-terminal outer-planar graph, it was either the result of combining two graphs $G_1$ on $n_1$ vertices and $G_2$ on $n_2$ vertices by series or by parallel. So we have two cases two consider.

The first case is when $G_1$ and $G_2$ were combined by series. By induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. Since $G$ was combined by series, it has $n = n_1 + n_2 - 1$ vertices, where $n_1, n_2 \ge 2$. Let $n_0 = \max(n_1, n_2)$. Then $G$ is $O(\log(n_0))$-outer-planar since we have not added any layers to $G_1$ or $G_2$ by combining them. It follows that $G$ is $O(\log(n))$-outer-planar since $n_0 \le n$.

In the second case, $G_1$ and $G_2$ are combined in parallel, meaning that $G$ has $n = n_1 + n_2 - 2$ vertices. Again by induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. However, this time we cannot conclude that the number of layers around $G$ is the same.

This is where I am stuck. I understand that we are at-most doubling the amount of vertices in $G$ by combining them in parallel, but I don't know how to use that to argue that the number of layers in $G$ is $O(\log(n))$. Any help would be appreciated since I've been stuck on this for several days now.

EDIT: Now that the deadline has passed for my assignment, I would love to have a solution so that I can prepare for my midterm exam (solutions to bonus/challenge problems are never posted).

Terminology

Series-parallel graphs (SP-graphs) are constructed in the following way. A two-terminal graph is a graph with two distinguished nodes $s,t$. A single edge connecting $s$ and $t$ is an SP-graph. If $(G_1,s_1,t_1)$ and $(G_2,s_2,t_2)$ are two SP-graphs, then their serial composition is an SP-graph, and their parallel composition is an SP-graph. The serial composition is obtained by identifying $t_1$ with $s_2$; the new terminals are $s_1$ and $t_2$. The parallel composition is obtained by identifying $s_1$ and $s_2$, and $t_1$ and $t_2$; the new terminals are $s_1=s_2$ and $t_1=t_2$. SP-graphs are the minimal class of graphs generated by these operations. See Wikipedia for more on this class.

$k$-outerplanar graphs: A planar embedding (i.e. an embedding without crossings) is $1$-outerplanar if all of the vertices belong to the unbounded face. For $k \gt 1$, a planar embedding is said to be $k$-outerplanar if removing the vertices on the outer face results in a $(k − 1)$-outerplanar embedding. A graph is $k$-outerplanar if it has a $k$-outerplanar embedding.

The idea of the proof is to come up with a parameter of graphs $f(G)$ satisfying the following properties:

The outerplanarity of $G$ is $O(f(G))$.
If $G$ is the (serial or parallel) composition of two graphs $G_1,G_2$, then
$$ f(G) \leq \begin{cases} \max(f(G_1),f(G_2)) & \text{if } f(G_1) \neq f(G_2), \\
\max(f(G_1),f(G_2)) + O(1) & \text{if } f(G_1) = f(G_2). \end{cases} $$

If we are able to construct such a parameter, then your result follows (exercise). It could be that outerplanarity itself satisfies these axioms, but this is not clear. I was able to construct another parameter $f(G)$ which does satisfy these properties, and is very similar to the outerplanarity of $G$. Can you?

Here is my solution. For a two-terminal graph $G$, let $F(G)$ be the result of adding an extra edge connecting both terminals, and define $f(G)$ to be the outerplanarity of $F(G)$, when the extra edge is forced to be on the outer face. Clearly the outerplanarity of $G$ is at most $f(G)$.

It is easy to see that if $G$ is the serial composition of $G_1,G_2$ then $f(G) = \max(f(G_1),f(G_2))$. Now suppose that $G$ is the parallel composition of $G_1,G_2$. It is easy to see that $f(G) \leq \max(f(G_1),f(G_2)) + 1$. This is not good enough, however: we need to show that when $f(G_1) < f(G_2)$, then $f(G) = f(G_2)$ (without the $+1$). To that end, take a "good" planar embedding of $F(G_2)$ (with outerplanarity $f(G_2)$), and replace the extra edge with a copy of a "good" planar embedding of $F(G_1)$ (with outerplanarity $f(G_1)$). The result is a planar embedding of $F(G)$ with outerplanarity $f(G_2)$.


Question about simple perceptron code I'm reading through Sebastian Raschka's Python Machine Learning, and I see something confusing that is not explained in the text.
In the code on this page:
https://github.com/rasbt/python-machine-learning-book/blob/master/code/ch02/ch02.ipynb
Implementing a perceptron learning algorithm in Python
In the training process, in addition to updating weights, I see this happening:
 self.w_[0] += update

Then later on, during "prediction," when weights are applied to input, I see self.w_[0] being used:
def net_input(self, X):
    """Calculate net input"""
    return np.dot(X, self.w_[1:]) + self.w_[0]

It looks like this is a bias being added into the perceptron, but the book says that net_input is simply calcuating "weights transpose dot x" and mentions nothing about this + self.w_[0] part...
Can anyone take a look at the linked code and make sense of what's going on with the self.w_[0] part? Or has anyone else got this book that might explain why that's there?

I suspect the book's English explanation is probably a simplification (or maybe it has adopted the standard convention of adding an extra dimension to x that holds a constant value $1$).  It seems like most likely you've already given the explanation; it's adding the bias value.


Are there any proofs that BQP is not in P? Are there any proofs that BQP is not in P?  In laymen's terms, I am asking if there is any formal proof separating the complexity class that quantum computers are presently assumed to solve efficiently from the complexity class that non-quantum computers are presently known to solve efficiently.

Obviously I'm not talking here about black box/oracle proofs that show they are nonequivalent if we have access to some theoretical oracle.  Just talking about regular, normal equivalence.

This is a famous open problem, so you won't find a proof anywhere at this time. We don't even know how to prove that $\mathsf{P\neq PSPACE}$, so finer separation of complexity classes such as $\mathsf{P\neq BQP}$ is also not known. Note that $\mathsf{BQP\subseteq PSPACE}$ is not trivial, you can find a proof in Quantum complexity theory, by Bernstein & Vazirani.

It is suspected that they are different, with the ability of quantum computers to factor integers in polynomial time being a strong witness.


restricted sub-permutations check I am solving the following problem, motived by combinatorial optimization sampling proces.

I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) at permutations. For example: 4x4 case (4 position permutations)

 1     1     1     0
 1     1     0     1
 1     0     1     1
 0     1     1     1

So, on position 4 (4th row at restriction matrix) is not allowed items 1, for example.

This restrictions produce the following list of possible permutations (earch row is one possible permutation):

 1     2     3     4
 1     2     4     3
 1     4     3     2
 2     1     3     4
 2     1     4     3
 2     4     1     3
 3     1     4     2
 3     2     1     4
 3     4     1     2

I am looking for algorithm to check if any sub-permutation, which is represented by first N < 4 positions, may correspond to any of possible permutation or not, without need to avaluate all possible permutations.

For example sub-permutation [1 2 3] is OK, but sub-permutation [3 4 2] is not.

A sub-permutation (not necessarily initial) corresponds to the removal of rows and columns in your restriction matrix. So your problem can be reduced to the case $N = 0$ (you also have to check that your sub-permutation conforms to the restriction matrix). In order to determine whether a restriction matrix admits any permutation, treat it as an $n \times n$ bipartite graph, and check whether the graph has a perfect matching.

Here is an example. Consider your restriction matrix
$$
\begin{matrix}
1&1&1&0 \\
1&1&0&1 \\
1&0&1&1 \\
0&1&1&1
\end{matrix}
$$
Choosing the first three elements to be $1,2,3$ is the same as deleting the first three rows and columns. We get $\begin{matrix} 1 \end{matrix}$, which has a perfect matching as a $1\times 1$ bipartite graph.

In contrast, choosing the first three elements to be $3,4,2$ is the same as deleting the first three rows (say) and columns $3,4,2$ (rows and columns might be switched depending on the representation). We get $\begin{matrix} 0 \end{matrix}$, which doesn't have a perfect matching.


Hex Bit Pattern to IEEE 754 standard Floating Point Number The question asks for the decimal number that 0x0C000000 represents if it is a floating number. I'm not too sure on how to approach this, but here's my thought process:

0x0C000000 = 0000 1100 0000 0000 0000 0000 0000 0000

The first digit is 0, so it's positive. The exponent is
 0x0C = 12 - 127 = -116.
 The mantissa is 0x0C0000 = 12 * 16 ^ -2 = 0.046875, so the final answer is 1.046874 * 2 ^ -116. While my book has similar examples that I tried to follow along with, none were exactly of this type, so I highly suspect I'm doing something wrong. Any tips, hints, or strategies would be greatly appreciated.

A good start is to expand the hex representation into binary like how you did it.

  0000 1100 0000 0000 0000 0000 0000 0000

Then parse the word:

the left-most bit is the sign bit
the next 8 bits represent the biased-exponent
the last bits represent the fractional part with the "hidden one"

  0 | 00011000 | 00000000000000000000000

Then, follow:

s represents the sign bit
evaluate the binary representation of the exponent to decimal
subtract the bias from the exponent (bias for single-precision is 127 and 1023 for double-precision)
evaluate the normalized form to decimal and you have your floating point decimal number

I hope this helps. It took me a while to understand encoding and decoding using IEEE-754. Slow and steady wins the race.


Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment.
Say that for a students' weekly schedule, there are class times and events that must be attended. With the remaining time slots in the week, how can I assign times to work on each assignment so that the recommended assignment time is fulfilled before the due date.
This is very similar to single-machine scheduling problems, and usually a greedy algorithm of closest-due-date-first would work, but I want to implement constraints based on human factors. For example: don't work on one assignment for more than 2 hours in a row, don't schedule a study time right after a class, etc.
How would I go about including these human factor constraints within my algorithm?

A pragmatic solution might be to use methods from operations research, e.g., formulate this as an integer linear program or an instance of SAT, and use an off-the-shelf solver.  It's hard to say exactly what the best solution might be without knowing the specific constraints, but these approaches will be the most flexible in accommodating a wide range of possible constraints.


Time complexity for FPT algorithm I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen
here on slide 60.
The problem summary is given a graph G and variable k, are there k disjoint triangles in the graph.
There are two methods, I want to focus on one of them. (Method 1)
First I randomly color the graph in 3k colors and then go over each permutation of colors and check whether there are k triangles with distinct colors.
What I fail to understand is what the time complexity of such examination (going over all the possible permutations) and how exactly can it be done?

Suppose that you have a graph and each vertex is colored with one of three colors, and let the set of different-colored vertices be $A, B, C$.
Now, try to find a triangle with one vertex from each partition.  For each vertex $a \in A$, try let $B_a$ and $C_a$ be $a$'s neighborhood in $B$ and $C$, respectively.  Now you only need to check if there is an edge from $B_a$ to $C_a$.  If there is one, you have your triangle, otherwise, you try another vertex from $A$.
Let us call this subroutine colorful_triangle(G, A, B, C).  Observe that it is not necessary that $A \cup B \cup C = V(G)$.

Let $G$ be the graph, $\chi$ the coloring and  $\pi$ a permutation of colors.
Let $\chi(i)$ be the set of vertices that received color $i$.
Now let $A = \chi(\pi(1))$, $B = \chi(\pi(2))$, $C = \chi(\pi(3))$.  Run the subrouting colorful_triangle(G, A, B, C).  If successful, continue with
$A = \chi(\pi(4))$, $B = \chi(\pi(5))$, $C = \chi(\pi(6))$, and so on.
If you at some point are unsuccessful, move on to the next permutation.


Period of sum of two periodic sequences I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ using Vigenere?

From what I understand, each time it is encrypted, each character shifts using the first key and then using the second one, so I believe that for each pair there's an equivalent shifting. but if the two keys have a different length, how can I find the shortest possible key?

I think it has to be something with lowest common denominator, but I am not sure. how can this be shown mathematically?

my previous edit was a mistake and i deeply sorry for it. i read the book wrong and didn't interpret what's written well. very sorry for it. yuval explained to me well and i continue to research it using his given information

If you sum a sequence with period $a$ and a sequence with period $b$, then you get a sequence which is $\mathsf{LCM}(a,b)$-periodic. But the new sequence might have a smaller period, as the following example demonstrates (addition is modulo 10):

022441133502244113350224411335
000772999611888000772999611888
022113022113022113022113022113

The first sequence has period 10 (0224411335), the second sequence as period 15 (000772999611888), and the sum sequence has period 6 (022113), although the LCM is 30.

More generally, the sum of a sequence of period $i$ and a sequence of period $j$ could have period exactly $k$ iff $\mathsf{LCM}(i,j) = \mathsf{LCM}(i,k) = \mathsf{LCM}(j,k)$. See Restrepo and Chacon, On the period of sums of discrete periodic signals.


Definition of NP-hardness for non-decision problems As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-hardness for such problems? The standard definition:

The problem is NP-hard when any problem from NP is polynomial-time reducible to this problem

doesn't make much sense, because of how the reduction is defined:

Language $A$ is polynomial-time reducible to $B$ if there exists a poly-time computable function $f$, such that $x \in A$ iff $f(x) \in B$.

The problem is that $B$ (e.g. our search problem) doesn't define a language (there may be other equivalent definitions, such as $A(x) \in \{true, false\}$, but they'll lead to the same problems).
My friend suggested that we can define a second poly-time computable function $g^{-1}$, which converts an "answer" for $B$ to answer for $A$: $x \in A$ iff $g^{-1}(B(f(x)))$ is $true$, where $B(y)$ is any correct answer for $y$. This makes sense, but I've never seen that.
So, what's the standard definition? For an answer, I would also ask for an appropriate citation (not to Wikipedia or random slides).

There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual reductions in this context, however the natural way to go about saying $L$ reduces to computing $f$ is to say that there exists a polynomial time oracle machine $M^f$ with access to $f$ that decides $L$.
See also the zoo on the class FNP. The fact that "function NP" problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.


MapReduce Pseudocode Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents:

map(String key, String value)
// key: document name
// value: document contents
 for each word w in value
   EmitIntermediate(w, "1")

reduce(String key, Iterator values):
// key: word
// values: a list of counts
  for each v in values:
    result += ParseInt(v);
    Emit(AsString(result));

So the map step gets each word as a key and output its frequency in a document. Does the reduce step sum the counts of each word?

MapReduce groups everything by key, in this case the word. So the reducer gets the word, followed by a list of 1's. The length of that list is the number of times this word occurs in the text. The reducers sums up the ones to count the word.


What additional expressivity does polyvariance give in pushdown CFA? I'm reading through Pushdown Control-Flow Analysis of Higher-Order Programs, which presents a synthesis of the Abstracting Abstract Machines technique and pushdown automata to get static analysis which perfectly matches call and return sites. The paper presents a monovariant and two polyvariant forms of the system.

I can't seem to get my head around what additional expressive power polyvariance (e.g. 1CFA) grants when return-flow merging is already eliminated in the monovariant case by the pushdown methods.

Could someone provide an example program in which polyvariance helps?

After playing with an implementation (found here), I believe I've figured it out.

Although 0PDCFA technically entirely eliminates return-flow merging, this isn't a very strong result in the absence of any polyvariance: if the same function is called in two different contexts, the analysis must end up merging flows within the body of the function, since multiple values are bound to the same variable and the variable's abstract address is identified with its name. 1PDCFA provides a different set of addresses to each syntactically distinct call of each function (I might be either under- or over-selling here), eliminating much of the merging.