With a grammar, does precedence and associativity change the accepted language? When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "ignored" (defined in some random precedence all associating left, say) in the grammar, and then the AST fixed later based on (possibly dynamic) precedence and associativity conditions?

I am concerned only with LL grammars and their common variants.

Precedence and associativity declarations are common in parser generators, but they are not part of the theory of context-free grammars. And nor are they part of the working of the LL(k) parsing algorithms (or, for that matter, the LR(k) algorithms).  So there is no real way to answer that question in terms of the theory of formal languages.

On a practical level, you could perhaps look at popular parser generators and ask if the precedence and associativity declarations can alter the language recognised by the generated parser. In most cases, the answer will be "yes", but it depends considerably on how the precedence declarations are used to modify the generated parser.

I don't know enough about LL parser generators to answer that question for any of them, but it's quite clear precedence declarations for Yacc-based parser generators which use the mechanism described in the Dragon book can affect the set of recognised sentences. First, most such precedence declarations include the "nonassoc" declaration, which specifies that a particular operator cannot be used in a way which might require associativity. For example, a language in which a < b < c is illegal might declare < to be nonassociative, thereby removing the illegal construct from the language.

But even without "nonassoc", there are certainly cases in which forcing a reduction in a particular context can eliminate valid sentences. If, for example, you invert the precedence order used to resolve the "dangling else" ambiguity, you will make it impossible for the parser to recognize conditionals with "else" clauses.


$k$-SAT completeness proof when $k$ is linear in number of variables I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case?
I tried reducing 3-SAT to it by expanding, but this introduces $2^{k-3}$ extra clauses per original 3-SAT clause, hence the reduction is not polynomial when $k=n/2$.
Any ideas?

Your problem is actually in P. First of all, you can assume that no clause contains both a variable and its negation, since such clauses are always satisfied. Suppose that the instance contains $m$ clauses. Then a random assignment will falsify your formula with probability $m/2^{n/2}$. If $m < 2^{n/2}$, then this means that your formula is satisfiable. Otherwise, the input is of size at least $2^{n/2}$, and so you can go over all $2^n$ truth assignments in polynomial time.


Product of a Transition System and a Finite Automaton Dealing with a question that asks me to compute the product of the following transition system and finite automaton.
Compute the product between the transition system TS and the finite-word automaton A depicted below.

Can't seem to find a good example on how to do this so I sort of just freestyled my answer. The best I found was in Principles of Model Checking but the book didn't really explain how the product was derived (it just provided a TS, FA and product), so I had to "guess" the logic.
Can anybody have a quick look at my solution and see if there are there any obvious mistakes I have made?

Also I can't figure out whether or not I should indicate any terminal states. I know that a TS doesn't have any terminal states, but an FA can - so what about the product?

In Section 4.2.2 of the book "Principles of Model Checking", there is a definition (Definition 4.16; Page 165) of "Product of Transition System and NFA". You are right about the states (i.e., $S \times Q$) of the product but make mistakes about its transition relation. Below I focus on the transition relation.

  Definition 4.16 Product of Transition System $TS = (S, Act, \to, I, AP, L)$ and NFA $\mathcal{A} = (Q, \Sigma, \delta, Q_0, F)$. The transition relation $\to'$ of their product is the smallest relation defined by the rule
  $$\frac{s \to^{\alpha} t \; \land \; q \to^{L(t)} p}{(s,q) \to'^{\alpha} (t,p)}$$

Intuitively, the transition system TS generates atomic propositions and feeds them into the automaton $\mathcal{A}$, driving the automata running. This semantics can be used to verify if the TS satisfies some property expressed by an automaton.

Additionally, the start states of the product is $$I' = \{ (s_0, q) \mid s_0 \in I \land \exists q_0 \in Q_0. q_0 \to^{L(s_0)} q \}.$$ That is, $q_0$ in automaton has moved one step forward, driven by the atomic propositions in $s_0$.

Based on the definition above, I calculate the product as follows (please check it):

For what it concerns the terminal states, please refer to "Remark 4.17" (immediately following the Definition above) in the book.
By the way, the labels for transitions (action denoted by $\alpha$ above) in $TS$ are often ignored (because they are irrelevant).


Karp's reduction strategy One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction):
$$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&(2)\end{array}$$
The usual way to prove NP-Completeness however, is to follow Karp’s strategy which consists in proving that
$$\begin{array}{rr}X\in \textsf{NP} & (3)\\W \leq_p X&(4)\end{array}$$
I am trying to show that $(1)$ and $(3)$ are equivalents, but but I'm not sure where I can start. Can someone help me with how to do this?

$(3)\Rightarrow (1)$ should just be a consequence of the definition of $\textsf{NP}$-completeness.
For $(1)\Rightarrow (3)$, you can use the fact that there exists a function $f$, computable in polynomial time, such that $u\in X \Leftrightarrow f(u) \in Z$. Now to decide if $u\in X$, you can compute $f(u)$, and then decide nondeterministically if $f(u)\in Z$.


Proof of the Bubblesort algorithm I'm studying The Algorithm Design Manual and I was having some difficulty in the proof exercises,
so I asked a question here.
Based on the answer I got in that question(which was not the a complete proof),I came up with a proof.
Prove the correctness of the following sorting algorithm.
    Bubblesort (A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

1.Base case:
    An array of length 1 which is by definition sorted.

2.Inductive hypothesis:
    We'll assume that for all arrays of length (0 <= m) one iteraion of the outer loop with "n" being the length of the array,
    the array gets permutated in such a was  that the last element in the array is the biggest.

3.Inductive step:
    We want to prove that if our assumption is true for lists of length (0 <= m), then it is also true for lists of length (m)

    Let A = a[0], a[1], ..., a[m] (of length m+1)
    After (m-1) iterations of the inner loop based on our assumption, in the list A[0:m-1], a[m-1] is the biggest element.
    At this point,as (j < m),we have one more iteration to perform.
    Before this, j was equal to m-2 and j+1 was equal to m-1. After this loop, j will be equal to m-1 and j+1 will be equal to m.
    If A[m-1] and A[m] satisfy the if statement, that is, A[m-1] > A[m], they will swap.If not, then that would mean that A[m] is
    the biggest element in the list.
    In either case, the last element of the list will be the biggest after one iteration of the outer loop, which was what we were
    trying to prove.  ▮

I'm not really sure of it's correctness,so I would really appreciate if you could review it and tell me whether its correct or not.
Also please note any inadequacies it may have or things I could've done better as I'm quite new to inductive proofs.

Your induction hypothesis is insufficient. In the hypothesis, you are just proving that the last element of the array has the maximum value. However, you have to prove that the resulting array is sorted. Therefore, your induction hypothesis should be the following:
Hypothesis: At the end of 't' iterations of the outer "for" loop, the "n-t" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t+1' to 'n'.
Base case: For 't = 1', the induction hypothesis says that at the end of the first iteration of the outer "for" loop, the algorithm gives the highest element at the index 'n'. And, you can easily prove this statement.
Induction Step: At the end of 't+1' iterations of the outer "for" loop, the "n-t+1" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t' to 'n'. Again, you have to prove this step using the earlier mentioned hypothesis -- for 't' iterations.
This proves the induction hypothesis. And, now you can simply say that at the end of 'n' iterations of the outer "for" loop, all elements of the array are in the sorted order and they occupy the indexes from '1' to 'n'.


Example of a superword w such that v^2 isn't its subword What is an example of an infinite word(superword) w such that if a nonempty word v belongs to L = {1,2,3}*, v^2 isn't a subword of w?

For example if w = 123123123...123 and v = 123, v^2 = 123123 hence it's a subword of w, I can't seem to find a superword that fits the requirement.

There is a dedicated page on "square-free words" on wikipedia here, with references. As you can see, there is an exemple of a square-free word on a three lettre alphabet.


1/r attractive force by cellular automaton Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles?

More specifically, I would like to know whether it is possible, with strictly local update rules, to have two objects (defined within the model) attract each other with a $1/r$ force, where $r$ is the distance separating the objects.  This would in particular entail an acceleration of the object (particles) as they get closer together.

More generally, can long range attractive forces between objects (blobs) be simulated in a cellular automaton setting with strictly local rules?

If by "simulate" you mean something like "generate a picture of what the dynamics would be under such a force," then the answer to your question is yes: there exist universal cellular automata (including Conway's original Game of Life rule set).

If, however, you're asking about whether our universe can be explained in terms of strictly local update rules, then your question is still open.  Konrad Zuse was one of the first to explore this question explicitly in terms of CA; see Wolfram, Schmidhuber, or t'Hooft for more recent work.


Are hash functions really quantum resistant for commitment schemes? It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic speedup.

However, there is active research into, for example, commitments such as https://eprint.iacr.org/2015/361.pdf. These state that in a quantum setting (whatever that means), the old way of doing commitments by requiring collision resistance doesn't work.

My understanding (possibly wrong) is that one cannot implement a hash function with quantum operators and gates because the quantum operators are unitary and therefore the hash function becomes invertible. The classical hash function uses compression to lose information and is hence, non-invertible. Is there then a possibility that if we attempted a quantum implementation of SHA-2, that would end up showing us how to break it?

Consider $x \rightarrow y = H(x)$. If I have an implementation of $H$ with quantum gates, I could take any $y$, put the remaining registers into whatever state I want (corresponding to the lost information) and then invert to obtain a valid $x$. My only assumption here is that I implemented the quantum $H$ but I can't see why this is forbidden, or even difficult.

No.  I can see how that sounds like it could work, but it doesn't actually work.  You're missing an important detail about how we implement classical functions on a quantum computer.  The usual way to implement non-reversible functions with reversible logic is to use ancilla bits (i.e., constant inputs, and junk outputs that are discarded).

For instance, suppose you want to implement the function $f(x,y) = x \land y$ (it computes the boolean AND of its two inputs).  You can make this invertible by instead implementing $g(x,y,z) = ((x \land y) \oplus z, x, y)$ (here $\oplus$ denotes XOR).  Here $g$ is called a Toffoli gate.  Note that $g$ is invertible, even though $f$ is not.  Moreover, we can compute $f$ by noting that $g(x,y,0) = (f(x,y,0),x,y)$, so if you want to compute $f$ in a reversible way, you feed in $x$, $y$, and a constant $0$ to $g$, then discard all but the first bit of output.  Just because you can invert $g$ doesn't mean you can invert $f$.  First, given only $f(x,y)$, we don't know what value to place into the other output bits of $g$.  Second, if we made random guesses at those outputs and then inverted $g$, that won't necessarily give us an inverse of $f$ (try it!).

The same is true for SHA2.  We know how to implement SHA2 on a quantum computer.  It uses ancilla bits.  Those ancilla bits prevent you from inverting SHA2 by trying to reverse the quantum computation.


Can we solve this problem more efficiently than trying all possible combinations Here is the context of the problem I am struggling with.

I have a set of strings, for example:

"my name is john",
"i like cheese",
"what is your name",
"the cheese is in the kitchen",
"john likes cheese"

Let $S$ be union of all words appearing in the previous strings.
my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes

The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :

Words are separated by a comma.
The sum of the lengths of selected words is bounded by a constant number (say 25).
A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.

For example, the combination john,cheese,like,likes,i uses 24 characters and allows to rebuild  both "i like cheese" and "john likes cheese".

Here is what I have tried to implement.

First, I sort every single word by the number of strings it's contained in. In this example:

is      (3)
cheese  (3)
john    (2)
name    (2)
my      (1)
i       (1)
like    (1)
what    (1)
your    (1)
...

So I'm now using this array: [is, cheese, john, name, my, i, like, ...], let us call it initial_array

And here is the idea of the algorithm I amm using.
First, I initialize another array of strings containin of all the strings g the first word from initial_array, let's call it new_array:

[is]

Then, while the total length of all the strings of new_array plus the commas does not exceed the limit of 25 chars, I append them:

[is,cheese] (9)
[is,cheese,john] (14)
[is,cheese,john,name] (19)
[is,cheese,john,name,my] (22)
[is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john"
[is,cheese,john,name,my,i,like] (29) --> up to 25 chars

When I reach a length up to 25 chars, I try to replace the last element of new_array by the following of initial_array:

[is,cheese,john,name,my,i,what] (29) --> up to 25 chars
[is,cheese,john,name,my,i,your] (29) --> up to 25 chars
...

And when I reach the last word of initial_array, I remove it from new_array and replace the previous one by the next one of initial_array:

// if the last word of initial_array is "likes"
[is,cheese,john,name,my,i,likes] --> we reached the last word
[is,cheese,john,name,my,like]
[is,cheese,john,name,my,like,what]
etc...

If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the initial_array, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.

Thank you for your help.

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.


Random Sudoku generator I want to generate a completely random Sudoku.

Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a unique way to complete it to match the Sudoku constraints (each line, column and aligned $3\times3$ square has no repeated element) and it is minimal in that respect (i.e. if you omit any more element the puzzle has multiple solutions).

How can I generate a random Sudoku puzzle, such that all Sudoku puzzles are equiprobable?

Generating the exact uniform distribution of all sudoku puzzles can be done that way: you can just randomly generate a 9x9 grid and then only keep it if it is a correct sudoku grid, otherwise retry.

This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct by $9^{17}$ only by generating a random 8x8 grid and then fill the remaining two lines. This is still a random distribution, but still way too inefficient.

You can also force the first line to be $[1, 2, .. 9]$, then randomly generate the remaining of the grid and then randomly pick a permutation of all digits. You will still pick all the grids with the same probability but $9!$ faster.

Maybe you see where I am going: answering this problem in a clever way will probably lead you to wonder about the underlying symmetries of sudoku grids. A lot of work was done in this direction to prove the fact that 17 is the minimal number of clues to a sudoku (see this article) and you can go here to see this precise enumeration of 5,472,730,538 classes of 3,359,232 similar grids, which uses these symmetries:

Permutations of digits
Permutations of rows (the bands and the rows inside each band)
Same thing for columns
Transposition

With this framework you can pick randomly one of the 5,472,730,538 classes (they can actually be compressed into 6 GB) and then pick one of the representative for each symmetry, respectively one in $9!, 6^4, 6^4, 2$.

EDIT: to adapt this to incomplete puzzles, you can choose randomly a subset of your grid, check if the solution is unique with a sudoku solver and retry if not. This is not a uniform distribution since the number of incomplete puzzles with a unique solution may be different for two grids. (I would be very surprised otherwise)


Skolem constant in existential instantiation for first order logic For any sentence $\alpha$, variable $v$, and constant symbol $k$ that
does NOT appear elsewhere in KB:
$$\dfrac{\exists \nu. \alpha}{\mathsf{subst}(\{ \nu / k \},\alpha)}.$$
E.g., $∃x. \mathrm{Crown}(x) \wedge \mathrm{OnHead}(x, \mathrm{John})$ yields

$\mathrm{Crown}(C_1) \wedge \mathrm{OnHead}(C_1, \mathrm{John})$

Provided $C_1$ is a new constant symbol (aka Skolem
constant)

Can someone clarify the Skolem constant concept?

Perhaps it will help to discuss this in a broader context, so let me explain this concept with regard to the resolution principle, which is used to check if some formula is unsatisfiable.
Resolution for propositional logic's formulae is rather straightforward and is based on the Conjunctive Normal Form.

We want to apply resolution to first-order formulae, i.e. sort of reduce FOL to propositional logic. One way to do that is to convert the original formula via Skolemization into a formula of the form
$$\forall x_1x_2...x_nM,$$
where $M$ (called 'matrix') is a formula without quantifiers and in CNF. To do this conversion we must get rid of existential quantifiers. The rule you provided does that in the special case where the current existential quantifier is not in scope of any universal quantifiers.

The intuition here is if it is known there exists some $\nu$ for which $\alpha$ holds, then why don't we "pretend" we know that $\nu = k$, where $k$ is some fresh constant. It needs to be 'fresh' in order not to introduce any dependencies between unrelated things.
And the reason we are allowed to "pretend" we know $\nu$ is that there is a theorem which claims that Skolemization preserves unsatisfiability.

Note: recall that we only want to check if a formula is satisfiable/unsatisfiable, so the skolemized formula is not necessarily equivalent to the original one.


Figuring out when one algorithm will be slower than another algorithm I'm studying for a computing exam and came past the following question on a past paper and need help with it.

When would algorithm A be slower than algorithm B? Demonstrate your answer with the help of an example. Also what will the value of SUM be at the end of each algorithm if the size is set to $10'000$?

Algorithm A:

SET sum TO 0
FOR i=1 to size
  FOR j=1 to 10000
    sum=sum+1

Algorithm B:

SET sum TO 0
FOR i=1 to size
  FOR j=1 to size
    sum=sum + 1

I came up with this answer but not sure if it is correct:

The algorithm A will be slower than algorithm B when the performance of the algorithm is directly proportional to the cubed or more of the size of the input data set, for example if the Big O notation becomes $O(N^3)$ or $O(N^4)$ or $O(N^5)$ etc. The Big $O$ notation $O(N^3)$ nesting the for loops in two more for loops:

Set Sum TO 0
For i=1 to size
  For k=1 to size
    For l=1 to size
      For j=1 to 10000
sum=sum+1

Algorithm A contains an instruction that is executed $size * 10000$ times.
Algorithm B contains an instruction that is executed $size * size$ times.

It is obvious that the comparison between A and B depends on the variable size.
You can see that if $size < 10000$ then B performs better, and if $size > 10000$ then A performs better.
If $size = 10000$ then A and B can be considered equally fast.

It is easy to calculate the result for $sum$ when $size = 10000$.

I am not sure if it makes sense to answer with big O notation here because the algorithms are different. A computes $size * 10000$ and B computes $size^2$, which are two different algorithms; it does not make sense to compare them with big O notation in my opinion. Usually big O analysis helps in comparing algorithms that solve the same problem, which is not the case here.


Maximum Capacity Path Problem with constraints I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output.
The problem is: Given an undirected graph with two parameters (weight,cost). We need to find the Maximum Capacity path problem from source to destination such that the cost of the path(sum of the edges of path) is within a fixed value specified by the user. In other words, it(sum of cost parameter along the path) is upper bounded by a constant value.
I modified the existing algorithm by adding and extra cost constraint while relaxing the edges but was unable to make it work for all types of graph. I was also wondering if this problem is NP-Complete.

It can be solved in polynomial time. For instance, you can use binary search over the weight.  Given a candidate weight, delete all edges with lower weight, then find the lowest-cost path and test whether its cost is below the lower bound; that tells you whether the weight was too high or too low.  Repeat until binary search converges.


Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not find a solution for a proper NFA after multiple tries.
The solution of my DFA for the language provided above:
My attempts for the NFA are down below. I apologize for my messy handwriting but these were just rough works that I was drawing out on the go.
My first attempt at solving the NFA
My second attempt at solving the NFA
My third attempt at solving the NFA

The question is not clear as formed: if you want an NFA which is not a DFA and matches the language then you could take your DFA and add a new unreachable state with an $\epsilon$-transition to itself, or add other $\epsilon$-transition self-loops or many other things that will not change the language.
If the aim is to use non-determinism to reduce the size of the automaton, then you can omit the garbage state (so that the word would just "fall out of" the NFA at that point). Given that you have already optimised the paths for $ab,abb$ (based on their shared prefix) and $baa$ has no shared prefix or suffix with the other words, it looks like this is the only possible optimisation to be made.


A language in NSPACE(O(n)) and very likely not in DSPACE(O(n)) Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages).
And also the open problem $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ is not so famous as the "analogous" problem: "$\mathbf{P} =^{?} \mathbf{NP}$".

Well, is there really such an analogy:?

Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE(O(n))}$  (like $\mathbf{NP}$ complete languages)?
Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE(O(n))}$ we get that $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$?
(Maybe just a matter of opinion) Are both problems on the same level of difficulty?

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.

The conjecture $\mathsf{L} \neq \mathsf{NL}$ is considered (by some) to be more approachable than the conjecture $\mathsf{P} \neq \mathsf{NP}$. I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$.

The bigger picture here is whether Savitch's theorem, which states that $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$ for reasonable $t(n) \geq \log n$, is tight. While $\mathsf{NPSPACE} = \mathsf{PSPACE}$, I think that most people believe that $\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$. On the other hand, I'm not sure that people believe that $t(n)^2$ is the optimal blowup; perhaps a smaller exponent also works, at least in some cases. See for example a recent arXiv paper, The parameterized space complexity of model-checking bounded variable first-order logic, by Yijia Chen, Michael Elberfeld, and Moritz Müller.


Minimize cost of recursive pairwise sums: how to prove the greedy solution works? The problem is in this other question.

Why does this always work? It's not clear to me how one would use induction.

For $n = 3$, a quick calculation shows it works, however, I don't think it generalizes well.

Each summing approach can be represented by a binary tree: the leaves represent the original elements and each internal node (including the root) represents the result element of the addition of the elements represented by its two children. For example,

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

... can be regarded as the following tree:

      16
     /  \
    9    \
   / \    \
  4   \    \
 / \   \    \
1   3   5    7

Then we rewrite the cost of each addition as the sum of original elements. For example, the costs in the example above are:

4 = 1+3
9 = 4+5 = 1+3+5
16 = 7+9 = 1+3+5+7

Total cost: 4 + 9 + 16 = 29

We can see each number corresponding to a leaf is contributed to the total cost in the additions corresponding to its ascendants. For a leaf $e$, If we denote by $h(e)$ the height of $e$, and by $f(e)$ the number corresponding to $e$, then the total cost is exactly $\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$.

Note each tree represents a prefix code of the leaves. In the example above, the tree represents the prefix code:

1: 000
3: 001
5: 01
7: 1

If we regard $f(e)$ as the frequency of $e$, then $\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$ is the average length of the code, which is optimized by Huffman coding. Note the answer in your link describes exactly how Huffman coding works.


Periodic Pattern recognition In a Sales Log I'm pretty new in this field and I need some advice for my first professional challenge.

I'm trying to create a sort of client segmentation from a my company's sales log which has the peculiarity that the clients has a pretty long-term relationship and a periodic behavior.

Based on when does he has bought (Ex: Twice a month, once a week, once every three months...) determine the frequency of purchase.
I need to figure out the phase of this client, so I can know in what stage of his/her period is.
I would like to know how much does it buys each time purchase amplitude

Once i have his three elements I want to be able to use that info to detect when the client changes his behavior (specially when they have an missing period or they decrease the buying amplitude)

I would like to get a really neat result, because i think that i will use it to a Markovian process.

So far I've tried astropy's lomb-scargle implementation but it seems that is too-precise and needs to many data points.

These are the steps you need to follow.

Model

You need to pick a model that you think explains your data. It can be very simple (e.g. linear regression) or very complex (e.g. a four-layer neural network). You want to pick as simple a model as possible!

Example: Assume sales follow $s(x) = a + b\sin(cx)$.
Train

Using one part of the data, you determine which parameters of the model fit your data best. The method of training depends on your model of choice.

Example: You fit the parameterized sine against the first half of your data with least-squares and find $(a,b,c) = (3,77, 13)$ is "best".
Validate

Inspect how well the model explains the rest of the data. You will have to decide in step 1 how you quantify quality here, and what your acceptance criteria are.

Separately, if that makes sense in your domain, apply the model entirely different data sets that should follow the same model if your hypotheses are correct. Does it predict anything there? What does the answer say about your model and/or your assumptions?

Example: Inspecting the squared error between $3 + 77\sin(13x)$ and the second half of the timeline data, you notice it is far too large.
Iterate

Unless the predictive quality of your model is good, go back to step 1. Sometimes, more training data can be the answer, too; note how that weakens your result, though.


Variant of offline Turing machine Let $M$ be a variant of Turing machine with no working tape but with several heads on input word. Prove that these machines accept exactly the languages in $L$.

Please hint me how to start.

Let $S$ denote the languages accepted by such machines.  The question wants you to prove $S=L$.

When you have a complicated-looking task, it often helps to break it down into pieces.  So, a first helpful hint on how to break it into pieces: try to prove $S \subseteq L$.  Separately, try to prove $L \subseteq S$.  (If you still can't solve it, then you're able to ask a more specific question about one or the other of those.)


MAC protocol with throughput of 1 Consider a MAC protocol (ALOHA, CSMA, TDMA, etc.) that, even for very high loads, always results in a throughput of 1 (normalized with respect to the channel speed).
Why is that not good if the throughput is equal to 1?

There can be many reasons, but one example would be fairness. Suppose you have a modified version of ALOHA where one priority user has transmission probability set to 1 and all others to 0. Assuming the priority user always has a message to send, this scheme has a throughput of 1. However, this is an awful scheme if you care about any of the other users, because they are going to experience infinite delay.
This is why researchers often prefer working with network utility functions as performance metrics to account for the welfare of the network instead of just overall throughput.


An obvious approach to NP = coNP, is there a counterexample? Let's try to solve "co3SAT" with an NTM in polynomial time.  It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction.

We've got a formula in conjunctive normal form, a big AND of OR clauses, each clause with 3 literals.  Let's suppose we adopt the following strategy:  at each stage, we expand two of of the clauses using the distributive law (AND distributes over OR), and simplify the result whenever possible.  In the end, if the formula is unsatisfiable, we should get "false" from this procedure.

Is a lower bound known for this procedure (i.e. is it known whether this necessarily uses exponential time, given that we can use the non-determinism to select the optimal order in which the clauses are expanded)?

I read a little a bit about lower bounds for resolution techniques using the pigeonhole principle, but at first glance this seems like a different problem.

It is not known whether NP=coNP or NP≠coNP, but the latter is strongly suspected. It is not even known whether P≠NP implies NP≠coNP.

It is known that NP≠coNP implies P≠NP, and this approach for proving P≠NP is known as "Cook's program".

Now to your particular proof system. As far as I understand, your proof system maintains a collection of DNFs, which are initially the clauses of the original CNF (so they are trivial DNFs in the sense that all terms have width 1). At each step, you take two DNFs and combine them to a new DNF.

This system is similar to "depth-2 Frege", which is the following system. You start with "axioms" which are the clauses of the original CNF that you are trying to refute. The proof consists of a sequence of "lines" (propositions), each one either an axiom or following from previous lines via one or more derivation rules. In addition, all the lines are constrained to be formulas of depth 2 (CNFs or DNFs). The exact choice of derivation rules doesn't matter - fix any finite set of derivation rules of your choice.

It seems that one can simulate your proof system using depth-2 Frege in such a way that the number of lines in the Frege proof is comparable to the size of your proof. To know for sure, one needs to examine the exact simplification rules that you use, and show how to simulate them using depth-2 Frege. I believe that this should work out.

The pigeonhole principle is hard not only for Resolution, but also for bounded depth Frege. In particular, refuting the pigeonhole principle using depth-2 Frege takes $2^{n^{\Omega(1)}}$ lines, where $n$ can be taken as the size of the formula. See for example Fu and Urquhart.


What exactly is an algorithm? I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, about ways to devise programs other than the ones taught in university.

Consider the factorial function. Typically we define this function like

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

I'd call this an algorithm and have no doubt that this is the right way to do it. Then, i wondered "can i do this in constant time?", which let to the following idea: what if i had an array of integers where array[n] houses the factorial of n? Once this array is filled i could simply define fact as:

 int fact(int n)
 {
 return array[n];
 }

Still i cant seem to cal this an algorithm, even though it provides the correct result and operates in constant time O(1). Can this be called an algorithm? Otherwise, why not? I could argue that filling the array would require an algorithm to have operated at some time, even if it was in our brain in order for us to fill the array, but could this be the criteria? How are these aspects handled formally?

Note that this concept could be extended to any function operating over integers independly of its number of arguments, i would just have to use a matrix if the function had 2 arguments, or 3 if the function had 3 arguments, and so forth. Also, aren't these solutions used simply because of memory consumption?

Also, not that functions may also encompass any program with output, since i could find a way to index every single possible output that a program could provide.

As another exemple, consider the common use of an array: i allocate an array initially of size N, then i add elements to array by storing the value at index n and increasing n by one unit. Then, if i want to look for an elemento, i cant help but to perform a linear search over the array. If instead i created an array of size, for instance, Integer.MAXVALUE, to store integers, initialized with zeroes, i could store an integer by placing 1 at its index. Then i could search for its existence in the array in O(1) time. What if i wanted to be able to place multiple units of the same number? No problema, i'd just increase the value stored at the integer's index.

Sorting would be a bit more complicated, but nonetheless lookup and addition could be performed in O(1) time.

The informal definition of an algorithm in a popular textbook goes something like:

An algorithm is (1) a well defined computational procedure (2) that takes some input and (3) produces some output (4) for a well defined computational problem.

In your first case you have coded an algorithm where:
The problem is to find the factorial (part 4 of definition),
given int n as input (part 2 of definition),
the code describes the computation to be performed (part 1 of definition),
the output is the factorial (part 3 of definition).

In your second case:
The problem is to find the array element at position n (part 4 of definition),
given n as input (part 3 of definition),
the code describes the computation to be performed (part 2 of definition),
the output is the element at position n (part 1 of definition).

You have stored factorials there so it gives you factorials. If you had stored squares or cubes there you'd get squares or cubes, so it cannot be said that the second snippet by itself is an algorithm to compute factorials.

And if you say that an array look up along with an array having f(n) at position n is an algorithm to compute f(n) then you have gone so deep that there is no more computation below. A well defined computational procedure should be a finite piece of information. If an infinite array of factorials is a part of the computational procedure this does not hold. So that wouldn't be an algorithm to compute factorials.


W[1]-hardness of Steiner tree w.r.t. number of non-terminal vertices This is an exercice is Rolf Niedermeier's book "Invitation to fixed-parameter algorithms", Chapter 13.

Show that the following problem is W[1]-hard:
Steiner Tree in Graphs with respect to the parameter "number of non-terminal vertices".

The way I understand it, if there are most $k$ non-terminal vertices, then this doesn't help in solving the Steiner problem in time $f(k)n^c$.

The objective is to find the minimum number of edges connecting terminal vertices (while some vertices are non-terminal).
I can't find a reduction however.  I am convinced that the parameter $k$ being number of included non-terminal vertices in a solution makes it W[2]-hard. But if $k$ is the number of existing non-terminal vertices, I don't know.  Proof ideas or references will be appreciated.

When parameterized by number of non-terminal vertices in the input graph, Steiner Tree is FPT by brute force.  -  Find a minimum-size subset of non-terminal vertices such that [the subgraph induced by the union of [the set of terminal vertices] with [the chosen set of non-terminal vertices]] is connected, and then output any spanning tree of that subgraph.

(If that's not your interpretation of the problem, then clarify your last paragraph.)


matrix multiplication speedup when the matrix elements are 0, 1 and -1 I would like to compute matrix multiplication A * B where A is Nx3 and B is 3x3. We also know that the elements of B only contains 0, 1, and -1. The content of A is arbitrary floats.
Is there any speedup we can do?

Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like
ResultX = ax * c00 + bx * c01 + cx * c02
ResultY = ax * c10 + bx * c11 + cx * c12
ResultZ = ax * c20 + bx * c21 + cx * c22

Use a switch for the 27 possible values of c00, c10 and c20. Then we need just the fma’s and even replace one of them with a plain multiplication in case one of these numbers is zero.


Oracle separation P and BPP I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in real life, it is very easy to construct an oracle $O$ such that $\mathbf{P}^O \neq \mathbf{BPP}^O$. Frankly I don't find this easy at all. Even more so I find it implausible sounding. I will explain my reasoning here.

My understanding from earlier parts of the book is that the reason people believe that $\mathbf{P} = \mathbf{BPP}$ is that we believe in the existence of good pseudo-random generators (i.e. deterministic processes that generate random looking strings) and even have some plausible looking candidate pseudo-random generators. Now whenever we want to run a $\mathbf{BPP}$ algorithm on a $\mathbf{P}$-machine we just run the algorithm as written, but replace every random bit the $\mathbf{BPP}$-machine would use by a pseudo-random bit generated by our pseudo-random generator.

You can see my problem now: we can just apply the same strategy in presence of the oracle. Whenever the $\mathbf{BPP}^O$-algorithm makes an 'ordinary' deterministic step we do the same thing in our $\mathbf{P}^O$ algorithm. Whenever the $\mathbf{BPP}^O$-algorithm queries the oracle, we query the same oracle in our $\mathbf{P}^O$ algorithm and whenever the $\mathbf{BPP}^O$-algorithm uses a random bit we use a bit from our pseudo-randomgenarator. What could go wrong, short of the oracle magically coming to life, taking physical form and smashing our pseudo-random generator with an axe? So my question is:

  What is an example of an oracle $O$ such that $\mathbf{BPP}^O \neq \mathbf{P}^O$ and what problem is in the former but not the latter class?

Update: while typing a link to the following question showed up that is essentially asking the same: Existence of suitable pseudo-random number generators to derandomize BPP to P

However I don't see how the accepted answer answers my question. It seems to say that there are oracles that can distinguish the output of a given pseudo-random-generator from actually random data but

a) I can't think of a problem where having access to truly random data would give an advantage over having access to only outputs of $G$ to solve it and

b) What if the $\mathbf{P}$-machine fools the oracle by using a PRG other than $G$?

I'm not sure what's the simplest way, but you can use diagonalization. We will construct an oracle for the following problem:
$$
L = \{ x : O(y) = 0 \text{ for all } |y|=|x| \},
$$
where $O$ is some oracle that we construct by diagonalization. The same oracle will also be used to solve $L$ in randomized polynomial time, but we will ensure that it doesn't suffice to solve $L$ in deterministic polynomial time.

Let $M_i$ be an enumeration of timed oracle Turing machines running in polytime (that is, $M_i$ runs some other machine $M'_i$ for $p_i$ time steps, where $M'_j,p_k$ go over all oracle machines and polynomials).

We construct $O$ in stages. Initially, $O$ is empty (none of its values are decided).

In stage $i$, we handle $M_i$. We pick some length $n$ on which $O$ is completely empty, and furthermore the running time of $M_i$ on $0^n$ is at most $2^{n-1}$ (this will hold for all large enough $n$), and run $M_i$ on $0^n$. Whenever $M_i$ queries an undecided value of $O$, we set the value to $0$. If the machine $M_i$ says that $0^n \notin L$, then we set all other values of $O$ of length $n$ to $0$. If it says that $0^n \in L$, then we set the other values of $O$ of length $n$ so that exactly half of them are $0$ and half of them are $1$.

Finally, we set all undecided value of $O$ (after going through the entire enumeration) to $0$.

Our construction guarantees the following properties:

$M_i^O$ fails to compute $L$. Consequently, $L \notin \mathsf{P}^O$.
For each length $n$, if we choose a random $y$ of length $n$ then $\Pr[O(y) = 0] \in \{1/2,1\}$. This gives a trivial random sampling algorithm for $L$, showing that $L \in \mathsf{BPP}^O$. (In fact, the algorithm has one-sided error, so $L \in \mathsf{RP}^O$.)


NRU: Page fault on writing? I am trying to understand the concept of NRU from the following link. I have got some problem in understanding the text below:

NRU page replacement Algorithm

  If the hardware does not have these bits, they can be simulated as
  follows. When a process is started up, all of its page table entries
  are marked as not in memory. As soon as any page is referenced, a page
  fault will occur. The operating system then sets the R bit (in its
  internal tables), changes the page table entry to point to the correct
  page, with mode READ ONLY, and restarts the instruction. If the page
  is subsequently written on, another page fault will occur,
  allowing the operating system to set the M bit and change the page's
  mode to READ/WRITE.

I have bolded the text. I have two problems: Page fault occurs if the page is not in memory but the above text says that
(a)the page fault occurs at the time of modifying or writing the page? I can’t understand that.
(b) Also I cant understand the text “, allowing the operating system to set the M bit and change the page's mode to READ/WRITE.” What is meant by READ/WRITE? If we are setting the M bit then it should be WRITE mode only? Why the text says READ/WRITE mode.
Somebody please guide me.

The idea is to mark a read/write page as read-only when loading it into memory (or after writing it out). If it is written to, a fault will occur. When handling the fault, the operating system looks at it's tables, and notices it should be writeable. So it can record it as "written to" (modified) in it's tables, make it read/write, and allow the operation to proceed. Later writes just add insult to injury, no need to keep track of them.


3-SAT where variables occur equally many times as a positive literal and as a negative literal Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$.

Is it NP-complete to decide the satisfiability of such a formula? Assuming it is, I would be interested in knowing if it has a special name. Has it perhaps also been investigated somewhere?

It is NP-complete (but I don't know if it has a name): suppose that a variable $x_i$ appears as a positive literal $n$ more times than as a negative literal.

Then you can "balance" it adding $n$ new 3CNF clauses with $n$ new variables $y_1,...,y_n$:

$-x_i \lor y_1 \lor -y_2$
$-x_i \lor y_2 \lor -y_3$
...
$-x_i \lor y_{n-1} \lor -y_n$
$-x_i \lor y_n \lor -y_1$

If $x_i$ appears more times as a negative literal, apply the same expansion but using $x_i$ in the new 3CNF clauses instead of $-x_i$.

The $y_i$ are balanced and the resulting formula (that can be built in polynomial time) is clearly satisfiable if and only if the original 3CNF formula is satisfiable: whatever is the value of $x_i$ the new clauses can be satisfied setting $y_i = true$, so they don't "interfere" with the satisfiability of the original formula.


Nondeterministic Logarithmic-space in directed graph I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the following problem.

Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem.
To show that the problem is $NL-hard$, start from problem $s; t-connectivity$ and as an intermediate step, create a acyclic graph $G^a$ which is $s’; t’- connected$ if and only if the original graph $G$ is $s; t- connected$.

The author has set as hint: use the length of the paths of a vertex $x$ at a vertex $y$.

To show that the problem is in NL: guess a directed edge $(u,v)$ of the graph that is part of a cycle, and check (using the connectivity algorithm as a black-box, or by guessing each step of a walk) whether $v$ is connected to $u$ in $G$.

To show that the problem is NL-Hard create a new graph $G'$ as follows:

For each  vertex $v$ of $G$ add $n$ vertices $v^{(0)},\dots,v^{(n-1)}$ to $G'$.
For each edge $(u,v)$ of $G$, and for each $i=0,\dots,n-2$, add the edge $(u^{(i)}, v^{(i+1)})$ to $G'$.
For each $i=0,\dots,n-2$, add the edge $(t^{(i)}, t^{(i+1)})$ to $G'$.

It is easy to see that $G'$ is acyclic and that $s^{(0)}$ and $t^{(n-1)}$ are connected in $G'$ iff $s$ and $t$ are connected in $G$.

Now, consider the graph $G''$ obtained by adding the edge $e=(t^{(n-1)}, s^{(0)})$ to $G'$.

If $s^{(0)}$ and $t^{(n-1)}$ were connected by a path $P$ in $G'$, $G''$ contains the cycle $C = P + e$. The opposite direction is also true: if there is a cycle $C$ in $G''$ then $C$ must include $e$ and this means that of $C-e$ is a path between $s^{(0)}$ and $t^{(n-1)}$ in $G'$.


Linear program for min-length pair of edge-disjoint paths problem Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, B)$ of edge-disjoint paths between $s$ and $t$ such that
$$
\sum_{e \in A}l(e) + \sum_{e \in B} l(e) \to \min
$$
How can I formulate this problem in terms of ILP ?

I think this can be solved in polynomial time by finding a minimum-cost maximum flow in the graph, where you set the capacity of each edge to $1$ and the cost of each edge $e$ to $-l(e)$, and add a source node $s_0$ with an edge $s_0 \to s$ of capacity 2 and cost 0.  (You might need to add a "demand" that the edge $s_0 \to s$ has exactly 2 units of flow along it.)
If you must formulate it as an ILP, introduce a zero-or-one variable $x_e$ for each edge, with the intended semantics that $x_e=1$ means that edge $e$ is in the first path.  Add a constraint that, for each vertex $v$ other than the source/sink, $\sum_w x_{(v,w)}$ is 0 or 2; for the source and sink, it must be 1.  This captures the requirement that you have a path from $s$ to $t$.  Add another zero-or-one variable $y_e$ for each edge, with similar constraints to ensure it represents a path from $s$ to $t$.  Finally, enforce the disjointness requirement: $x_e + y_e \le 1$.  The objective function to maximize is $\sum_e l(e) x_e + l(e) y_e$.
You can enforce a constraint that a variable $z$ is 0 or 2 by requiring $z=2t$ where $0\le t \le 1$ is a fresh zero-or-one integer variable.


Acquiring the necessary background for research I'm starting my mater's thesis in computer science. I'm interested in computational Origami (algorithms mainly); I've read a little about the subject and I'm worried because I lack some of the knowledge that I think is necessary to do research in that area. But still I'd like to start and want to ask: which is better an approach: learn the necessary background as I go and wheneve a necessity pops up or learn it first and then start. I have 4 to 5 months to finish my thesis.

In my experience, it is better to learn stuff as you need it. Otherwise, you don't have the motivation to really "get" it, and there is always the risk of getting lost in the forest of interesting stuff out there (that in the end is of no use). Be at the lookout for results that could help you (Google or citeseerx or ..., or even this site, are your friends).

Another piece of advise: Start writing right now. Editing your ramblings into something coherent later on is easy, sitting in front of a blank screen with writer's block when the deadline approaches is extremely painful. Write down what you do right now; if it works out it stays for later, if not it gets erased (and you don't get embarassed by your dumb attempts ;-). That way it doesn't happen to you that you know something is right, but don't remember why... and have to redo lots of work (happened to me!).

Make a short (3-4 line) summary of each paper or other reference that looks relevant, add it to your bibliography. Reading the stuff so you are able to extract what is relevant to you helps understanding the stuff, the summaries help in locating material later. And the collection of summaries will be your chapter on state of the art (after cleanup).

As a final comment, use LaTeX (it looks much nicer, has very good handling of bibliographies ;-), and perhaps asymptote for figures (it is a bit hard to learn, but has C++-like syntax to manipulate points and define lines, and produces excelent results). Put the whole stuff under version control (my favorite is git, but use whatever you are confortable with). That  way you'll be able to have an up-to-date backup (preferrably on some other machine!), and go back if you really mess up (Murphy's lat assures us you will).


Can you pop 2 elements at a time in a PDA My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously

In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and transitions to a new state (possibly non-deterministically, i.e. there could be several or no choices). If you define PDAs according to this definition then you cannot pop two stack symbols in a single transition.

That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.


Decide if binary encoded number is divisible by 3 Let's consider the language over $\{0,1\}$ containing such words $w$ that:
$$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + ..  + m_n \mod 3 = 0$$

($m_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class.

The first problem is:  How to decide whether $m_i$ is divisible by $3$?

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is:
$v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\
2^{2k} \mod 3 = 2$$

Please hint me.

you have to use the fact that $2^n\mod 3 = n\mod 2 + 1$:

2 mod 3 = 2
4 mod 3 = 1
8 mod 3 = 2
16 mod 3 = 1
32 mod 3 = 2

and so on.

The solution then for an $n$ bit number is to use $n$ processors, the $i$th processor will calculate $f_0(i) = i\mod 2 +1 * w[i]$ where w is the little-endian array of bits.

Then, each of the processors can calculate the following: $f_{t+1}(i) <= f_{t}(i) + f_{t}(i+2^t)\mod 3$, for $t \in \{1...log_2(n)\}$ (increasing sequentially of course). $f_{log_2(n)}(0)$ will then contain the sum of the bits mod 3.


SVM Maximizing Margin I am trying to make sense of the following:

Taken from the MIT website.

So I understand that we want to maximize the distance between the planes H0 and H1, where H0 is defined as wx+b=0 and H1 is defined as wx+b=1. I am following with the definition that the distance betweena point (x0,y0) and a line Ax+By+c=0 is |Ax0+By0+c|/sqrt(A^2+B^2).

What I don't understand is... What is wx+b? So I understand w is the weight vector, x is an input and b is the offset, so wx+b gives an indication's of x's class as predicted using the model with weight vector w. But, when we are looking at the distances between H0 and H1, which are both lines, what 'line' and what 'point' are we referring to?

First of all, the formula given for the distance between a point and a line is not a definition, it is a calculation. The distance between a point $p$ and a line $\ell$ is the minimum distance between $p$ and a point on $\ell$.

Similarly, if $\ell,\ell'$ are two lines then the distance between them is the minimum distance between a point on $\ell$ to a point on $\ell'$. This is zero unless the lines are parallel, and if they are, say given by $x \bullet w + b = 0$ and $x \bullet w' + b' = 0$, then the distance is (I believe) $|b/\|w\| - b'/\|w'\||$. Again, this is not a formula but rather a calculation.


Is weighted XOR-SAT NP-hard? Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form
$$f(x_1,\ldots,x_n)=\bigwedge_{i=1}^k\bigoplus_{j=1}^{l_i}x_{r_{ij}}$$
($\oplus$ denoting XOR) with $k\in\mathbb{Z}_{>0}$, integers $1\leq l_i\leq n$ and $1\leq r_{i1}<\cdots<r_{il_i}\leq n$ for all $i=1,\ldots,k$, $j=1,\ldots,l_i$, the problem is to find an assignment of minimum cost for $x_1,\ldots,x_n$ that satisfies $f$, if such an assignment exists. The cost of an assignment is simply given by
$$\sum_{\substack{i\in\{1,\ldots,n\}\\x_i\,\text{true}}}c_i.$$
Is this problem NP-hard, that is to say, is the accompanying decision problem "Is there a satisfying assignment of cost at most some value $K$" NP-hard?

Now, the standard XOR-SAT problem is in P, for it maps directly to the question of solvability of a system of linear equations over $\mathbb{F}_2$ (see, e. g., https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#XOR-satisfiability). The result of this solution (if it exists) is an affine subspace of $\mathbb{F}_2^n$. The problem is thus reduced to pick the element corresponding with minimal cost from that subspace. Alas, that subspace may be quite large, and indeed, rewriting $f$ in binary $k\times n$-matrix form, with a $1$ for each $x_{r_{ij}}$ at the $i$-th row and the $r_{ij}$-th column, and zero otherwise, we get a cost minimization problem subject to
$$Ax=1,$$
where $A$ is said matrix, $x$ is the column vector consisting of the $x_1,\ldots,x_n$ and $1$ is the all-1-vector. This is an instance of a binary linear programming problem, which are known to be NP-hard in general. So the question is, is it NP-hard in this particular instance as well?

A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$.

You can reduce this problem to your problem. The system $Ax = b$ is equivalent to the conjunction of equations of the form $x_{i_1} \oplus \cdots \oplus x_{i_m} = \beta$. If $\beta = 1$, this equation is already of the correct form. If $\beta = 0$ then we XOR an extra variable $y$ to the right-hand side, and then we force this variable to be $1$ by adding an extra equation $y = 1$. We define the weights as follows: $y$ has weight $0$, and the $x_1$ have weight $1$. We have now reached an equivalent formulation of maximum likelihood decoding which is an instance of your problem.


Rolling hash hacking The hash value of a string $s$ is given by

$$
h(s) = \sum^{|s|}_{i = 1} s_i  \cdot p^{|s| - i} \mod m;  \text{ $m$  is prime, $m < 10^{12}$}.
$$

The string $s$, $p$, $m$ is given,
 $|s| \le 14$, alphabet size $= 62$ (letters and digits).

I need to
find a string $s^{\prime}$:

$s^{\prime} \neq s$, but $h(s^{\prime}) = h(s)$

$s^{\prime}$ must meet the same requirements as $s$. The answer is always exist.

I know about Birthday-attack, but $m$ is too large and
if I generate random strings, probability of collision is too small.
Simple brute-force is also not suitable, because the string may be too long (14 characters).

Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6

Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.


Basics of Amortised Analysis I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an example and explain me:

a) What is the difference between worst-case analysis and amortised analysis?

b) What is the difference between average-case analysis and amortised analysis?

c) In plain English(with using minimal notations), how can we provide a complexity(especially I am interested in potential method)

I'll just answer a) and b) because I don't know the potential method.

About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a structure called "dynamic array", which is very similar to an ArrayList in Java. The way that structure operates is that internally it has an array, and it doubles in size once it's full, copying everything into the new array.

Now what's the worst case cost for an insert operation into that structure? The worst that can happen is that you have to double the array that contains $n$ elements, so you get a worst case cost of 1 operation (!) of $\mathcal{O}(n)$. If you insert $n$ elements, this gives you a worst case running time of $\mathcal{O}(n \cdot n) = \mathcal{O}(n^2)$.

Obviously that is far too pessimistic. We know that we only have to double every $2^k$ steps, because with every time we double the size of the array, it'll take twice as long until we need to double it again. Here is where amortized analysis comes into play: you know that there are some expensive operations, but you also know that they happen comparatively rarely, so you try to see whether the "naive" worst case analysis can be improved with a little bookkeeping. In order to do this reasonably, you don't consider a single operation anymore, you consider a sequence of operations, usually of length $n$.

Maybe you have read about the accounting method: you have an account where you can "save up" time, and every operation is allowed to take "time" out of the account, but no more than is in the account. The idea behind this is that the many cheap operations "help pay" for the few expensive ones, and if we distribute the cost that way, we can get a better analysis (that is still a true upper bound, i.e. the actual complexity is still below the amortized complexity in all cases).

How would that work in the case of the dynamic array? Every "cheap" insert is just one write operation to the array, so that costs us $1$ unit of time. Every "expensive" operation costs us $k$ units where $k$ is the number of elements in the array at that time. Now we would like the cheap inserts to share the cost of the expensive one that they help produce. This can be done if every cheap insert, in addition to paying its own $1$ unit of cost, contributes another $2$ units to the account, because this way, the inserted element pays for the copying of itself and a second one that will be copied when we double. This means that for every expensive insert we have, there will be at least $k$ units of time on our account, and we can pay for it using the money in the account only, so the actual cost of the expensive insert goes down to $k-k = 0$ (because it doesn't actually cause work that hasn't already been paid for, it's paid for with the time that was "saved up" by the cheap inserts using the account savings). How does this help us? Now every cheap insert costs us $1+2=3$ units, and every expensive insert costs us $k-k =0$ units, giving both an amortized cost of $\mathcal{O}(1)$. If we want to calculate the amortized cost of inserting $n$ elements now, we get $\mathcal{O}(1 \cdot n) = \mathcal{O}(n)$, and this is still an upper bound on the actual cost that any input can produce.

About b) While amortized analysis still gives you an upper bound on the actual cost of an algorithm, average case analysis doesn't guarantee that; there may be inputs where the actual cost is above the average case cost. But that's not a problem for average case analysis, because it just tells you what the cost of running your algorithm typically is, meaning as an average of the cost of all possible instances of size $n$.


Undecidability of checking whether all words can be generated from a context-free grammar? I know it's undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Let $T$ be a one-tape Turing machine. A snapshot of a Turing machine is the contents of its tape, where the location of the head is preceded by the current state of the machine (encoded using a disjoint set of symbols).

We can encode a halting computation of $T$ on the empty string as a string $s_0 \# s_1^R s_2 \# s_3^R \# \ldots \# s_n$ (or $s_n^R$, according to the parity of $n$), where $s_0,\ldots,s_n$ is the sequence of snapshots encountered during the run of $T$.

We can check that a string does not code a halting computation as follows:

It is of the form $\Sigma^*\# s \# \Sigma^*$, where $s$ doesn't contain $\#$ but doesn't correspond to a valid snapshot. (More accurately, we have two corner cases corresponding to the first and last snapshot, and we might have to count the number of $\#$ in the prefix to determine whether it should be a snapshot or its reverse.)
It is of the form $s_0 \# \Sigma^*$, where $s_0$ doesn't contain $\#$ but doesn't correspond to an initial snapshot.
It is of the form $\Sigma^* \# s_n$ (or $s_n^R$), where $s_n$ doesn't contain $\#$ but doesn't correspond to a final snapshot (i.e., the Turing machine is not in a final state).
It is of the form $\Sigma^* \# s_i \# s_{i+1}^R \# \Sigma^*$ (or $s_i^R \# s_{i+1}$, according to the parity of $\#$ in the prefix), where $s_i,s_{i+1}$ do not contain $\#$ but $s_{i+1}$ is not the snapshot following $s_i$.

With some care, we can express all of these conditions as a context-free grammar. Here it is important that we encode the computation by reversing any other snapshot, since this enables us to ascertain that $s_{i+1}$ doesn't follow $s_i$ in a context-free manner (roughly speaking, this is just the language $w\#w^R$ with small modifications).

This context-free grammar generates $\Sigma^*$ if and only if $T$ doesn't halt on the empty string. It follows that universality of context-free grammars is co-r.e.-hard. It is also co-r.e.: if the context-free grammar is not universal, then there is a witness for it, namely a string not generated by the grammar (recall that the word problem for context-free grammars is decidable). Hence universality of context-free grammars is co-r.e.-complete.


Why update weights and biases after training a Neural Network on whole set of training samples I am reading the book Neural Networks and Deep Learning by Micheal  Nielsen. In the second chapter of his book, he describes the following algorithm for updating weights and biases for a neural network:

In the 2nd step, the algorithm computes the error for a sample and backpropogates it through the layers. This happens for all of the training samples (please correct me if I am wrong because this is what I assume is going on). Then in the 3rd step, the weights and biases are updated. My question is, why does the algorithm wait until the third step to update the weights and biases. That is, why can't it do it after each training sample instead of after a whole set of training samples?
Thank you so much for your help and I appreciate it.

You are right.  While you could backpropagate for all samples and then update the weights, you don't have to.  Alternatively, you can iterate through the samples and, for each sample, backpropagate for just that sample and then update the weights.

The latter turns out to be more effective (empirically).  It is called stochastic gradient descent.  Today, most neural networks are trained using stochastic gradient descent, because it reaches convergence faster than the alternative.  This makes neural networks faster to train.

Anyway, you could do it either way.  Both ways are valid.  The stochastic gradient descent approach seems to be faster in practice, but neither one is wrong.

Why did the book describe it this way?  That's a pedagogical choice.  The author might have considered it more natural or easier to explain this way.


What does an "I/O Task" mean? While reading an article, I noticed the use of term 'I/O Task':

Indeed, suppose the currently running process is performing an I/O
task (which, by definition, does not need the CPU to be accomplished).
Then, the OS may interrupt that process and give the control to one of
the other in-main-memory programs that are ready to execute (i.e.
process context switching).

However, AFAIK a unit of execution (task definition) is either a thread or a process.
So what does an "I/O Task" mean?

Reading / writing from disk.

Reading / waiting for keyboard / mouse input.

Reading / waiting for network data.

Printing a page.

Basically, as the text says, an I/O task is anything which the CPU can't perform on its own, and has to rely on other components. Usually this involves waiting a long time, compared to the CPU speed, so it's better to switch to another task while waiting.

In this way, even if the browser is waiting for the server to respond, the other running tasks can move on (unless they also need to wait for I/O, of course).


DFA containing substring to not containing substring by flipping acceptability of all states? For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$

For $D_1$, I would make $F_1 = \{q_4\}$.
As I tried to design $D_2$ as the complement of $D_1$ which does not have baba as a sub-string, I've found that I can make $D_2$ by inverting all the acceptability of all states, making $F_2 = \{q_0, q_1, q_2, q_3\}$, since instead of accepting, the input string is rejected upon reaching the an acceptance state of its complement $D_1$.
From this, I believe that we can get the complement of any DFA simply by accepting when $D_1$ rejects, and reject when $D_1$ accepts, meaning $F_2$ is the complement of $F_1$.
Is my generalized proof correct?

Shortly, yes. Formally, for every DFA $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, F\rangle$, define the DFA $\overline{\mathcal{A}} = \langle \Sigma, Q, q_0, \delta, F' \rangle$, where $F' = Q\setminus F$. That is, $\overline{\mathcal{A}}$ is obtained by flipping the acceptance of the states in $\mathcal{A}$. We calim the following.
Claim: $\overline{L(\mathcal{A})} = L\left(\overline{\mathcal{A}}\right)$.
Proof:  for every word $w\in \Sigma^*$, we have $$ w\in L(\mathcal{A}) \leftrightarrow\\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\mathcal{A}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin Q\setminus F$} \leftrightarrow \\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin F'$} \leftrightarrow \\ w\notin L\left( \overline{\mathcal{A}}\right)$$
Crucial points in the construction that you should ponder about:

Both automata have the same structure, in particular, they have the same run over the same word $w$: can you tell where we relied on this fact?

The automaton $\mathcal{A}$ is deterministic (in particular, there is a single run of $\mathcal{A}$ on $w$ that determines whether $w$ is accepted or rejected): if $\mathcal{A}$ is nondeterministic, then the construction does not work. Indeed, on input word $w$, there could be two runs of $\mathcal{A}$ on $w$: $r$ which is accepting, and $p$ which is rejecting. After flipping the acceptance of states, we get that $r$ is rejecting and $p$ is accepting, and so $w$ is still accepted.


"The Annotated Turing" on listing all binary numbers between 0 and 1 In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote:

These are binary numbers between 0 and 1, and (judging from the way we
created these numbers) all the binary numbers between 0 and 1, and
hence all the real numbers between 0 and 1.

And then at the bottom of the page there is a note:

It may also seem as if we've stumbled on a method to enumerate all the
real numbers between 0 and 1...

Followed by a brief explanation of why we really have not.
These two sentences contradict each other. The first one says we've made a list of all real numbers and the bottom note says we have not. So I have to questions regarding this:

Is it a mistake or am I getting something wrong?
If we have not listed all the real numbers between 0 and 1, then what have we listed?

You haven't shown the full proof, but it most likely has the form "Assume that the set is countable.  Consider any enumeration.  Then (blah-blah-blah) shows that there is a number not in the enumeration.  That's a contradiction, so our assumption must have been wrong."
If that's the structure of the proof, then pointing out that the proof appears to say two contradictory things is not a surprise; that's entirely the point of the line of reasoning, to show that if you start with a particular assumption, you reach absurd results.
What's actually true?  The truth: that list doesn't actually contain all the real numbers.  Assuming that it does is a faulty assumption.
It's possible that the text could have been written a little more carefully to caveat that the statement about it containing all numbers; but oh well, no one's perfect.  Books written for a popular audience, in particular, aren't always the best source if you want a precise and careful proof of a mathematical theorem.


Is $\lceil\log n\rceil!$ polynomially bounded? Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} > \lceil\log n\rceil!$  for all $n > 1$.  However, the solutions to Introduction To Algorithms (2009) say  that $\lceil\log n\rceil!$ is not polynomially bounded. What's going on?

Don't trust plots.

By Stirling's approximation (and dropping the ceilings to avoid notational overload),

$$\begin{align*}
(\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\
  &= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\
  &= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,,
\end{align*}$$

which grows faster than any polynomial.  But you're not going to see that by plotting versus $n^{100}$ unless you consider values of $n$ big enough that $\log\log n$ is more than about $99$, i.e., roughly $n\geq e^{e^{99}}\approx 10^{10^{42}}$, and you probably didn't consider values of $n$ quite that big, because no plotting software is going to display values like $(10^{10^{42}})^{100}$.


Generating numbers to be averaged efficiently During my research, I had encountered the following issue. Consider the equation
$$\sum_{k=1}^K\alpha_k P_k = P$$

where $\sum_{k=1}^K\alpha_k=1$, $\alpha_k > 0$, $P_k > 0, P>0$.

So you are given $\{\alpha_k\}$, $K$ and $P$. The task is to generate randomly $\{P_k\}$ such that the above equation is satisfied. I am looking for an efficient way to generate these numbers.

My strategy

I have one method. Basically, we generate $K$ distinct uniform numbers between $(0,1)$. Call them $\{b_k\}$. Then we compute $\sum_{k=1}^K\alpha_k b_k = B$. Now the sequence $\{\frac{b_kP}{B}\}$ is the desired sequence.

However, if you observe, using this method, $P_k$ can never exceed $P$ and in my work, I require some of the values to exceed $P$. E.g. if $\alpha_1=0.5, \alpha_2=0.5$, even $(2P,0)$ is a valid solution.

Is there a way to generate these numbers so as to circumvent this issue?

Update:
Given $\{\alpha_k\}$, it follows that $P_k \leq P/\alpha_{\min}$.
Note: The above counter example is not valid. Apparently the algorithm works fine.

A reasonable solution is to first generate a random point in the simplex
$$ x_1 + \cdots + x_K = 1, \qquad x_1,\ldots,x_n \geq 0. $$
Check out this question for several ways to do this. Then take
$$
P_i = \frac{P}{\alpha_i} x_i.
$$
This should give you a uniformly random point in the geometric body you are interested in
$$
\sum_{i=1}^K \alpha_i P_i = P.
$$


What is the difference between distributed representations and factors of variation in deep learning In the field of deep learning, people often talk about factors of variation which, in my understanding (in terms of dimensionality reduction), are the latent variable directions capturing variability in the data. I also often come across the term distributed representations which are basically the features of the input data that are not mutually exclusive.

Sometimes for object recognition, one may wish to extract distributed features of the object that are invariant to small variations (which are a result of combination of many factors of variation).

On the other hand, in case of autoencoder, one needs to extract the factors of variation as completely as possible so as to minimize the reconstruction error.

In the above two cases, factors of variation seem to have two contradicting roles, nevertheless they are both referred to as useful features for intermediate layers of a deep architecture.

So what is the difference between factors of variation and distributed features? I am very confused.

Usually, factors of variation are independent from each other. However, sometimes in feature extraction, some combination of these factors can be helpful to detect better and accurate features to explain the behavior of the observation.

Therefore, factors of variation are used to explain distributed features, and their relation likes the relation between basis of a space and a vector which is defined in the space using these basis or prime factors.

Although, observations change base on the factors of variation and distributed features, distributed features change base on the factors of variation.
In the other words, features of variation are prime factors, and distributed features are defined base on the prime factors.


Minimum Number of Integers From a List that Add up to N (Dynamic Programming) A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:

  Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where each $a_{i+1} > a_i$ and each $a_i > 0$, design an algorithm that finds the minimum number of such $a_i$ that their sum adds up to $N$.
   You can use each $a_i$ an unlimited number of times. You may assume $N$ is a possible sum for any $L$.

  Example: $L = [1, 3, 5]$. $N = 10$. The optimal choice is $5 + 5$. A possibility is using $10$ $1$'s, but that is not optimal.

I thought I found the optimal solution using a greedy algorithm, where we start with $0$ add the largest integer from $L$ without going over.

But my greedy algorithm fails in this case:

  Integers: $[1, 5, 7]$, $N = 10$; greedy algorithm gives $7+1+1+1$, but optimal solution is $5+5$.

The people I've talked to suggested taking a Dynamic Programming approach, but I am not quite comfortable with DP. What suggestions or hints do you have for thinking of a DP approach? I think I should approach this recursively, but in what way? Should I keep breaking it down to halves until I find individual components (kinda like mergesort), and see what numbers these components add up to in $L$?

You start with an array $A$ from 0 to N and initialize every value with $\infty$ (or some very large number).
Then you set $A[0] = 0$.

Then you loop the following until no more changes occur:

For each number $0 \leq n \leq N$ and for each integer $l\in L$ you update $A[n+l] = min(A[n+l],A[n]+1)$ (don't forget to check for array boundary violations)

When finished, the value of $A[n]$ should contain the minimum number of integers from your list that sum up to $n$.

Expected runtime of this is pretty bad (assuming you have a huge $N$ and $L = \{1,N\}$, as you will update values for $n<N$ for quite some time until you've found your solution.

You can optimize it a bit by observing, that in each iteration, the assigned values increase by one and thus, if some value has been assigned it will not be updated anymore. Therefore, as soon as $A[n] \neq \infty$ you can stop as the lowest value has been found.

Also you can keep track of a "frontier", i.e those indices $i$, for which $A[i]$ has been assigned in the last iteration. You can implement this with a queue, where you add $n+l$ to the queue if the minimum is lower than the previously found value and don't iterate over all $n$ but take the first element from the queue, which has been initialized with $Queue.add(0)$.

The resulting runtime should be $\approx\mathcal O (K\cdot r)$ (or something similar, e.g. $\mathcal O (K^2\cdot r)$) where $K$ is the number of integers in your set and $r$ is the result.

You could improve it a little bit if you replace the queue with a priority queue (e.g. a maxheap).

Alternatively you could precompute some multiples of your numbers (e.g. if $N=10^6-1$ and you have 1 and 1000, you would first determine the values for the largest multiple of each number that is below $N$ (999999*1 and 999*1000) and assign those directly).


Does a problem stay NP-hard when an additional constraint is added to it? I have the following problem $(P)'$:

\begin{align*}
 {\rm max}_{x_1,...,x_K}\quad & \sum_{k=1}^Kf(a_k,x_k) \cr & & (P)'\cr {\rm subject\ to}\quad & 0 \le x_k \le A, k=1,\ldots,K.
\end{align*}

This problem is proven NP-hard. An instance of $(P)'$ is given by $(K,a_i,A)$.

I have another problem $(P)$:

\begin{align*}
 {\rm max}_{y_1,...,y_N}\quad & \sum_{n=1}^Nf(b_n, y_n) \cr & & (P)\cr {\rm subject\ to}\quad & 0 \le\sum_{n=1}^Ky_n \le B, \cr \quad & y_n\geq 0, n=1,\ldots,N.
\end{align*}
And an instance of $(P)$ is given by $(N,b_i,B)$.

Can I say that problem $(P)$ is NP-hard?

For general $f$ you can't conclude that $P$ is NP-hard just from the fact that $P'$ is NP-hard. In order to do so, you would need to come up with a reduction from $P'$ to $P$. For such a reduction to work, you would need that for every value of $A$ there be a value of $B$ such that the two systems of constraints are equivalent. Unfortunately this is not the case.


Compact representation of paths in a graph I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$.

What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the selected ones are represented?

Note that I want to use this representation in an algorithm that will iterate through this subset of paths over and over again and that I want to be fairly fast, so for instance, I can't use any standard compression algorithms.

One representation that came to my mind was representing them as a set of trees. I'm guessing though that getting it down to an optimal number of trees is NP-hard? What other representations would be good?

A Trie might do the trick: http://en.wikipedia.org/wiki/Trie

Label each edge of your graph with a letter.  Then add the strings which represent paths through your graph to the trie.  To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something.  A bool, the number of the path under some ordering, etc.

Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation.  (see the linked Wikipedia article.)


What is the min # of moves to sort an array from 1 to n? Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted.
This shows $n-k$ moves is necessary.


Who coined the term "machine learning"? I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as:

  the field of study that gives computers the ability to learn without
  being explicitly programmed

?

You can find many, many references to this definition on the internet, but I haven't been able to track down the source. Some give it as his 1959 paper on checkers, but I don't find any such definition there.

"Programming computers to learn from experience should eventually eliminate the need for much of this detailed programming effort"
Samuel, A. L. (1959), “Some Studies in Machine Learning Using the Game of Checkers” in IBM Journal of Research and Development  (Volume:3, Issue: 3), p. 210


Applications of Lamport's Distributed Mutual Exclusion algorithm I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource without relying on a centralized coordinator.

How can this be useful in practice?  For instance, if the resource is something like a printer, or a shared file system, it can enforce mutual exclusion on its own, so there is no need for a distributed algorithm. I can't think of an example where this wouldn't be the case.  What am I missing?

Lamport introduced his distributed mutual exclusion algorithm as an example in

  Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-565, 1978.

The link leads to Lamport's personal page, where he has an annotated bibliography of all his work, with PDFs of every paper that has an electronic version.

The paper in question is the one that introduced Lamport timestamps and Lamport clocks.  Here's what Lamport has to say about the distributed mutual exclusion algorithm:

  It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system.  A distributed system can be described as a particular sequential state machine that is implemented with a network of processors.  The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.  So, I wrote this paper, which is about how to implement an arbitrary distributed state machine.  As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.

The relevance is not that you would use it to protect some kind of centralized resource.  The relevance is rather to show that when you are implementing a distributed state machine, you can actually get all the participants to agree about something, so you don't need centralized resources.


Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates? Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^O(1) where n denotes the number of points.

Yes.

I suspect that you have not read the paper The Rectilinear
Steiner Tree Problem is NP-complete, by M. R. Garey and D. S. Johnson, SIAM Journal on Applied Mathematics, Vol. 32 (1977), pp. 826-834. Well, if you have, I am sorry. Well, if you have, please indicate that critical information in your question. In fact, whenever your question is based on one big theorem/one paper, it is always a good idea to inform readers here whether you have no access to or have read or are familiar with a proof or proofs of the theorem/that paper. People, or at least I, will then be able to exchange ideas with you more efficiently in a way that suit you better.

I just browsed through the proof by Garey and Johnson. It is clear that, in fact, they build their proof on the rectilinear stree problem with integral coordinates within a square of side length $n^{O(1)}$, where $n$ denotes the number of points.


Combining these two results into one asymptotic notation Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$.

I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\big(N\log\big(\frac{2}{N\epsilon}\big)\big)$ otherwise.

I would like to write it using one notation (possibly with $\max$ or $\min$ operands), but can't get it right.

The problem is that $\log\big(\frac{2}{N\epsilon}\big)$ is negative for large values of $\epsilon$, so it doesn't seem to fit.

Any help will be appreciated :D.

Not that I encourage you to do so, but here's one way:
$$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) $$

For $\epsilon = \omega(N^{-1})$, the $\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor$ expression is $0$, and the left expression is $$\frac{1}{\epsilon+N^{-1}}+\log N = \Theta(\epsilon^{-1} + \log N)$$

For $\epsilon = \Theta(N^{-1})$, the whole expression translates into $\Theta(N)$.

For $\epsilon = o(N^{-1})$ you get:
$$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$


How to bridge theory and implementation for while loops? I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - and from what I understand, unnecessary. But reading through the books I have and google searches, I can't find the elegant solution.

So, the problem is that I'm building off basic lambda calculus as I understand it. I have defined true/false as abstraction terms. I can combine these with functions to do if/then/else sort of behavior. The problem comes with loops. I can define a basic while loop via recursion, but in practice, that causes a stack overflow. As I understand it, the usual solution would be to perform Tail Call Optimization, but I don't see how I can - conditionals are defined in-language. Because of that, the compiler doesn't know that the body of the while loop is in tail position.

The dragon book focuses on implementing the loop assuming there is labels and gotos. I could certainly do that. It looks as though other languages that don't build in looping constructs at least build in conditionals and then do TCO. And I could certainly do that too. But my understanding is that as long as I can apply abstractions and perform reductions, then loops (and everything else) should be able to be built from those basic blocks.

So what am I missing? Or is this one of those cases where "you can model anything once you have X and Y" isn't the same as "you can model anything once you have X and Y on a real computer" and built-ins are necessary for practical purposes?

So I managed to solve this issue today. The code for my while loop:

while (condition: ~>bool) (body: ~>void) => void {
    if condition {
        body;
        while condition body;
    };
}

When I go to build this into CIL (a stack based runtime, important for the psuedocode, not important for the answer) it looks like:

ldarg 0
<build closure from { body; while condition body; }>
call if

The important thing I was missing is that in the while code, the conditional was the thing in tail position. From the compiler's perspective, the block and the while function are two separate functions, with two separate "tails". Each of those are easily evaluated for tail position, making the optimization viable despite the lack of built-in conditionals.


cannot construct the infinite type I am trying to learn haskell and could not configure it out, why following code snippet can not get compiled:

*Uncurry> applyTwice f x = f f x

<interactive>:14:20: error:
    • Occurs check: cannot construct the infinite type:
        t ~ t -> t2 -> t1
    • In the first argument of ‘f’, namely ‘f’
      In the expression: f f x
      In an equation for ‘applyTwice’: applyTwice f x = f f x
    • Relevant bindings include
        x :: t2 (bound at <interactive>:14:14)
        f :: t -> t2 -> t1 (bound at <interactive>:14:12)
        applyTwice :: (t -> t2 -> t1) -> t2 -> t1
          (bound at <interactive>:14:1)

This would be fine:

applyTwice f x = f (f x)

In haskell function application is left associative, the first code snippet would be apply like:

(f f) x

why (f f) x it is wrong?

Okay, let's look at what we know about the type of applyTwice, $\alpha$:

It is given two arguments, so $\alpha = \beta_1 \to \beta_2 \to \gamma$, and $f$ has type $\beta\_1$ and $x$ has type $\beta_2$
$f$ is applied to $f$, so $\beta_1 = \beta_1 \to \gamma_2$
$(f\ f)$ is applied to $x$, so $\gamma_2 = \beta_2 \to \gamma$

The kicker here is the second equation, $\beta_1 = \beta_1 \to \gamma_2$. This equation has no finite solution, because $S \to T$ is structurally larger (uses at least one more type constructor) than either $S$ or $T$.

So the only type that satisfies this equation is infinite recursive type $\mu T\ldotp T \to \gamma_2 = ((\ldots \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2)$. But this type doesn't really have any meaning in Haskell or related type systems, and it's pretty hard represent an infinite type in finite memory in a concrete form.

Remember that $f\ f$ is giving $f$ as an argument to $f$. If you want to apply $f$ twice, you could use function composition (f . f) x, or $(f \circ f)\ x$ in math notation.


Is there a limit on the length of queries for the oracle? Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My question is what is the length of query that the machine can ask the oracle? Is it $O(log(n))$ or can it be polynomial in $n$ (where $n$ is the length of the input)?

It seems that the usual definition, following Ruzzo, Simon and Tompa, is as follows. The oracle tape is write-only but has no space constraints. It is erased after each oracle call. In addition, if the machine model were non-deterministic (which is not your case), then the oracle calling process would have to be deterministic.


Data structure with insert, and delete-min (or max) in $O(1)$? Is it possible to have a data structure that supports both insertion and delete-min  (or max) in $O(1)$?

You can assume the numbers that will be inserted are integers in the range [0,n] and that you will be inserting a maximum of n elements.

No; at least, it seems unlikely.  Such a data structure would contradict the lower bound on comparison-based sorting algorithms and would imply linear-time sorting algorithms (where none is known to exist).

Suppose we want to sort $m$ numbers from the range $1..n$, where $m \ll n$.  If we had your data structure, we could do that in $O(m)$ time.  However, this seems implausible.  The fastest comparison-based algorithm runs in time $\Theta(m \log m)$, which is  larger than $O(m)$.  Counting sort takes $O(m+n)$ time, which is much larger than $O(m)$ when $m \ll n$.  Van Emde Boas sorting takes $O(m \log \log n)$ time, which is still larger than $O(m)$ time. Han & Thorup's sorting algorithm takes $O(m \sqrt{\log \log n})$ time, which is still larger than $O(m)$ time.

So, you should not expect there to be any data structure of the form you list, as that would imply a huge breakthrough in sorting algorithms.

However, there is probably an algorithm where those operations can be done in $O(\log \log n)$ time, or possibly even $O(\sqrt{\log \log n})$ time, by applying Van Emde Boas trees or Han & Thorup.  See also https://en.wikipedia.org/wiki/Integer_sorting#Sorting_versus_integer_priority_queues.