How hard is it to factorize sum of two numbers Say I have numbers with known factorizations $n = \prod \limits _i p_i ^{n_i}$ and  $m = \prod \limits _i p_i ^{m_i}$ (where $p_i$ is the $i$th prime).

How hard is it to factorize $m+n$? Is there a more intelligent algorithm than if factorizations of $m$ and $n$ were not known? Assume $n$ and $m$ coprime as it is trivial to make them so.

The fact that $m+n$ will share no factors with $n$ or $m$ seems very helpful for small numbers, but I doubt it offers much for large ones.

There is currently no known (asymptotical) more intelligent algorithm (and it is also not expected that there should be one) than if factorizations of $m$ and $n$ were not known (assuming $m$ and $n$ to be coprime). Even the case where $2$ is a prime factor doesn't count, because checking some of the smallest prime numbers can be done without much effort anyway.


Prove correctness of recursive Fibonacci algorithm, using proof by induction I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction.

Here is my recursive version of an algorithm to compute Fibonacci numbers:

Fibonacci(n):
    if n = 0 then     // base case
        return 0
    elseif n = 1 then // base case
        return 1
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    endif

How can I prove the correctness of this algorithm by induction?

(Seems like it may be a duplicate, but the "Related" questions don't seem to be too close, with the possible exception of "this one)

The proof is by induction on $n$. Consider the cases $n = 0$ and $n = 1$. In these cases, the algorithm presented returns $0$ and $1$, which may as well be the 0th and 1st Fibonacci numbers (assuming a reasonable definition of Fibonacci numbers for which these values are correct).

Now, assume that the algorithm returns the correct Fibonacci number for all $n$ (i.e., the nth Fibonacci number) for all $n \leq k$ where $k \geq 1$.

We must show that the algorithm returns the correct value for $k+1$, i.e., the (k+1)th Fibonacci number. By the induction hypothesis, $k \geq 1$, so we are in the else case. We return Fibonacci(k) + Fibonacci(k-1) in this case. By the induction hypothesis, we know that Fibonacci(k) will evaluate to the kth Fibonacci number, and Fibonacci(k-1) will evaluate to the (k-1)th Fibonacci number. By definition, the (k+1)th Fibonacci number equals the sum of the kth and (k-1)th Fibonacci numbers, so we have that the algorithm returns the (k+1)th Fibonacci number on input $k+1$.

The proof of the claim follows by induction on $n$.


Graph Families that are easy to color What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter.

Examples would be:

Kneser graphs
Chordal graphs

Do you know any other families?

Motivation:

We are looking for interesting classes on which we can test a proper coloring heuristic. This is why we wanted some graphs that are not so easy to color but in the same time have a known chromatic number so we can evaluate the quality of the heuristic.

Whenever you are interested in a (well-known) graph invariant, it's a good idea to check out ISGCI first. Have a look at graphs that have bounded chromatic number, or graphs for which computing the number is doable in polynomial time.

To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded treewidth.


A Question about a Question related to Graph Theory and Maximum Flow The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at
most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum
flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob

It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow.  Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird.  Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow).  Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.


if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free I am having a hard time understanding if this would be true or false, can someone point me in the right direction?

One way to deal with this kind of problems is to check some easy and extreme cases. Also, you would like to have a few concrete instances of the concepts involved. You should try to construct simple counterexamples with the instances. If you have found just one counterexample, great, you have found the answer. If you cannot found counterexamples by various constructions, you might have gained some understanding why it might be correct. You may have to repeat a few times.

What are some instances of non-context-free languages? Here is one. $\{0^{n^2}\mid n\ge1\}$. Or another one $\{1^{n^2}\mid n\ge 1\}$. Or another one $\{0^{n^2+1}\mid n\ge1\}$. How about their intersections?

In general, a condition that stipulates the type of the intersection of two languages is a very weak restriction to each of the languages. There are a lot of room for each of them to vary without changing their intersection.

Interested readers can enjoy the following simple exercises. $L_1$ and $L_2$ are are assumed to be over the same alphabet for all exercises.

Exercise 1. If $L_1 \cap L_2$ is finite, must at least one of them be finite?

Exercise 2. If $L_1 \cap L_2$ is regular, must at least one of them be regular?

Exercise 3. If $L_1 \cap L_2$ is context sensitive, must at least one of them be context sensitive?

Exercise 4. If $L_1 \cap L_2$ is decidable, must at least one of them be decidable?

Exercise 5. Raise a similar question.


Mapping an address to a cache block A cache with 64 blocks(block0 to block63) and each block of size 16 bytes (or 4 words).
This is what I think of the address arrangement, if it is byte addressable.

block0 has addresses: 0,  64,  64*2,  64*3, ....,  64*15

block1: 1,  64+1,  64*2 + 1,  64*3 + 1, ....  64*15 + 1

block2:

...

...

...

...

block63: 63,  64*1 + 63,  64*2 + 63,  64*3 + 63, ...  64*15 + 63

But in the problem given in the figure, the addresses are suggested to be present in a serial order (see the last line saying "maps all addresses between 1200 and 1215") like:

block0: 0,1,2,3,4....15

block1: 16,17,... 31

block2:

...

...

...

...

block63: 1008, 1009,...1023

A cache is a copy of a "chunk" of main memory of a given size that is held in a faster ram closer to the CPU.

In the example given each cache block holds a chunk that is 16 bytes in size and there are a total of 64 blocks available.   When a CPU accesses an address if it's not already in cache, the data is copied from main memory into the cache in 16 byte chunks.  When the cache load selects a cache block, it ignores the lower 4 bits of the address (for a 16 byte block) then it uses the next 6 bits of the address (for 64 locations) to determine which block to use and the remaining bits of the address are used as a TAG to keep track of the addresses currently cached.  It fills the block with the 16 bytes starting at the accessed address with the lower 4 bits zeroed.

The math used in the explanation is based on the physical processes...  Dividing by 16 ignores the lower 4 bits.  Using the modulo of 64 on the result uses the next 6 bits as an index into the cache.  The explanation didn't deal with tagging, but that wasn't really part of the question which was "Which cache block is it using?".

So consider the CPU accesses address 1205 (Using an address that doesn't start at the beginning of a cache block for a little more clarity.):

A 16 bit address 1205 in binary is 0000010010110101.

Ignoring the lower 4 bits, the memory's block address is 1001011

Since the cache is 64 blocks it uses the next 6 bits to select which cache block to use.  In this case 001011 is used.  This is block number 11.

The remaining bits, 000001, are used in a tag to indicate which memory block is in the cache.

The data is then loaded from the cache into the CPU using the lower 4 bits 0101 as an index (or the 6th byte of the block).

If a subsequent access is for address 1210, or binary 0000010010111010, the tag will match and the cache system won't have to access main memory for the data.  It's already in cache and can be used quickly, the CPU just has to use the lower 4 bits of the address 1010 to load the 11th byte from the cache block...

If, however a future access is for address 9403, or binary 0010010010111011, this address also selects cache block 11 so the previous data is overwritten with 16 bytes of data from main memory beginning at 9392 (lower 4 bits zeroed), the new tag for the block is 001001, and the CPU loads the byte from 1011 in the cache block.


What are the rudimentary types of information connectivity i.e. model types? I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level)
I remember seeing a list of ways in which you can connect or categorise information elements. basically the types were as follows:

Lists - constitute a list of information elements

Hierarchies- visualise information in a parent-child relationship (ie organisational chart)

Flows - connect elements in a logical (lateral) flow (ie process model)
Have you seen any reference to these types, or can you elaborate on the full list of "model types"

Model theory, branch of mathematical logic, is based on three things: atoms, functions, and relations. With these you can define pretty much anything. In fact, functions are subsumed by relations, so you only need two.

What is a list but a next relation? What is a hierarchy but a parent-child relation?

Of course these satisfy axioms, and these can readily be expressed in first order logic.


Why is the distinction between linear and context-free grammars useful? The linear grammar is a grammar that's either left, right or left and right linear.

The context-free grammar can contain any kind of productions of non-terminals and terminals.

All linear grammars are context-free grammars.

But what is useful about distinguishing linear and context-free separately?

Let $\cal F$ and $\cal G$ be two classes of grammars, or what ever language defining devices you want. We assume that $L({\cal F}) \subset L({\cal G})$, the languages defined by the first class are included in those of the second.

Why consider both ${\cal F}$ and $\cal G$?

The most obvious reason is that the "models" in $\cal F$ are usually easier to handle to those in $\cal G$. That means it is in general easier to understand, write and analyse grammars in $\cal F$ than those in $\cal G$.  So whenever it is possible to work in the smaller class we might work there.

Sometimes we want to study and understand what makes a certain type of grammar hard to handle. We know that it is undecidable whether two context-free grammars generate the same word. For regular languages (given by right-linear grammars or finite automata) it is simple to construct the intersection and decide its emptiness. Now it is a matter of curiosity to know what happens in between: what about emptyness of intersection of linear languages?

Things are not always that straightforward. Deterministic pushdown automata are strictly less powerful than the general family (which generates context-free languages). They even allow a decidable equality test which is interesting for modellers. On the other hand, except for closure under complement, they have little closure properties.


Palindrome of fixed length We know that general palindromes cannot be decided by a DFA.

Howeve if you restrict to case of even length palindromes, does a DFA need exactly $2^{2k}$ states where $2k$ is length of palindrome the language needs to accept?

I get this as lower bound from Myhill Nerode aplication.

From answers below, my lower bound is wrong. What is the correct bound from Myhill Nerode?

How do you show the upper bound?

Imagine we build the DFA from top to bottom to recognize palindromes of length $2k$. As usual, we'll use the states to "remember" the input seen so far. The DFA will consist of three parts:

The states needed to represent the $2^k$ possible choices for the first $k$ characters. This will be a complete binary tree of depth $k$ with $2^k$ leaves and so will need $2^{k+1}-1$ nodes in total.
The states needed to process the remaining $k$ inputs. This will consist of $k-1$ layers, each of which contains $2^k$ nodes for a total of $(k-1)2^k$ nodes. For example, suppose we had $k=3$ and after part (1) we were in state $q_{011}$, i.e., having seen input $\mathtt{011}$. Then on input $\mathtt{0}$ we would transition to the fail state, since $\mathtt{0110}$ could not be part of a 6-character palindrome. If, on the other hand, we saw $\mathtt{1}$ we would change to a state on the next level, since the current input $\mathtt{0111}$ could be part of a palindrome.
Finally, we add an accept state and a reject state, with the appropriate transitions from the accept state to the reject state on either 0 or 1 and similarly from the reject state to itself on a 0 or a 1.

We will have $2^{k+1}-1$ states in stage (1), $(k-1)2^k$ states in stage (2) and the two states in stage (3) for a total of $(2^{k+1}-1)+(k-1)2^k+2=(k+1)2^k+1$ states.

It's not hard to use a Myhill-Nerode argument to show that the states are pairwise distinguishable and so this DFA is minimal.


What are the steps/tricks/tips to construct a Büchi automaton from a given language? Let's say I have this language: $(a + bc)^∗((b + c)a^ω + (abb^∗)^ω)$

It seems pretty complicated, where should I begin with if I were to construct a Büchi automaton?

I've been doing it the following way with smaller language sets:

a $^*$ operator is usually a path coming from a node to the same node.
a $+$ draws 2 branches

how would $^ω$ be represented? there are other operators, which I have not seen yet, what are they and how would they also be represented?

Pardon me if this is a silly question, but I'd rather ask than not knowing the answer ever.

Any help is greatly appreciated.
Thang

You can construct an NBA for an $\omega$-regular expression $r$ by induction on the generating sequence of $r$, using the constructive closure properties of NBAs.

You can see some examples here


Is javascript scripting? This one goes both ways at this point in my computer science studies... Is it scripting in the same sense as a Python script (for example)?

Are they the same?

I'm learning Javascript at the moment as part of a Web design textbook but at the very start of my programming lessons I got quite far in programming with Python and would like to finish it IF it is conducive to Web design.

Many thanks in advance to anyone who can help me here and I'll be sure to vote up the best answer for reputation.

JavaScript and Python are both interpretive languages (as opposed to compiled languages like Java) with JavaScript being (mostly) a client-side language and Python a server-side language.

You would do well to learn them both, especially JavaScript.


How to reduce Untyped λ-Calculus to Normal Form? I have an assignment to do which involves reducing an Untyped λ-Calculus expression to Normal Form. I am struggling to come to terms with Lambda Calculus though.

For example, one small part of the expression is:

((λ n f x . n f (f x)) (λ f x . x))

Does this mean that we substitute (λ f x . x) in for every n, f and x? Giving us the following:

((λ n f x . (λ f x . x) (λ f x . x) ((λ f x . x) (λ f x . x))))

If so, can this be reduced further? I know I am probably way off with this, but I just do not understand it; any help would be appreciated.

EDIT: Thanks to @ljedrz Comment.

  Before doing the reduction is worth noting that:
  $$ (\lambda n f x . n ~ f (f ~ x)) = (\lambda n f x .((n f) (f ~ x))) $$
  This is a convention, the parenthesis always associate to the left

It can be reduced further, but I advise you to change the second expression to an $\alpha$-equivalent one.

$$ \Big(\big(\lambda n f x . (n ~ f) (f ~ x) \big) ~ (\lambda h y . y) \Big) $$

This might not be necessary in this specific problem, but might also save you some headache later trying to keep track if some free variables got captured.

\begin{align*}
\Big(\big(\lambda \color{red}{n} f x . \color{red}{n} ~ f (f ~ x)\big) ~ \color{red}{(\lambda h y . y)} \Big) &\rightarrow_\beta \big[n ~ / ~(\lambda h y . y)\big] \big(\lambda f x . n ~ f (f ~ x)\big)\\
 &\rightarrow_{\alpha} \big( \lambda f x. (\lambda h y. y) ~ f ~ (f~x) \big)\\
\Big( \lambda f x. \big((\lambda \color{red}{h} y. y) ~ \color{red}{f}\big) ~ (f~x) \Big) &\rightarrow_{\beta} \Big(\lambda f x.\big[h ~ / ~ f \big]\big(\lambda y.y\big) ~ (f ~ x) \Big)\\
\Big( \lambda f x. ((\lambda y. y)) ~ (f~x) \Big) &\rightarrow_{\beta} \Big(\lambda f x.\big[y ~ / ~ (f ~ x)\big]y\Big)\\
 &\rightarrow_{\alpha} \Big(\lambda f x. (f ~ x) \Big)
\end{align*}

Which cannot be reduced further.


Why "reduce to", not the other way around? This action confuses me for a while. As you know, once we come up with a problem and we want to know how hard it is, we will do the "reduction". Intuitively, if we prove problem B is as hard as problem A, we can know the complexity boundary of B. But if problem B is harder than A, why we call the reduction process -- reduce problem A to problem B, not reduce problem B to A?

There are several different types of reduction, but generally, if we say we reduce problem A to problem B, it means something like:  if we had a way to solve B, we could use that to solve A.  Some reductions may allow to use B as a black box.  Others might require that "yes" instances of A map to "yes" instances of B, and that "no" instances map as well.  Or, it may be something simpler, like "hey, I already have a great solution to problem B, and now with just a simple transform, I can use it to solve problem A."
In all forms, it implies something related to "we could solve A if we had solutions to B".

What that means has something to do with what is known.  If B is an easy problem to solve, then A reducing to B tells us that solving A is no harder than solving B, plus doing the reduction from A to B.  In that case, an easy reduction, to an easy problem, proves that A is easy.

On the other hand, especially in the context of hardness results, we would usually reduce a known difficult problem (A here) to B, and that would show that, because A is hard, but transforming an instance of A into B is easy, B must also be hard, because if B were easy, it would give a solution to the known A problem.

So basically, for an easy reduction from A to B, it proves 2 things:  A is not harder than B, and B is not easier than A.  Yes, those are the same thing, but usually, you only care about one of them, depending on whether you know A to be difficult, or B to be easy.


Time complexity of a problem inspired by palindromes This was inspired by Bradshaw's question originally posted on Math.SatckExchange.

EVEN PALINDROME:

Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number.

Question: Is there a permutation $\sigma$ such that $w=v_{\sigma(1)}v_{\sigma(2)}... v_{\sigma(n)}$ $\in \{uu^R \in \Sigma^* \}$.

  Is it NP-complete to determine if a given set of strings can be ordered to form a palindrome (of even length as defined above)? If yes, Is it still NP-complete for $|\Sigma|=2$?

EDIT: Marzio has given an elegant reduction which shows that Even Palindrome is NP-complete for binary alphabets.

After a wrong polynomial-time attempt, this is a more robust idea to prove that the problem is indeed NP-complete.

The reduction is from the 3-PARTITION problem which is strongly NP-complete; i.e. it is still NP-complete even if the numbers are represented in unary.

The problem is to decide whether a given multiset $S = \{a_1,a_2,...,a_n\}$ of $n = 3 m$ positive integers, can $S$ be partitioned into $m$ triplets $S_1, S_2, ..., S_m$ such that the sum of the numbers in each subset is equal?

Let $p = (\sum_i a_i) / m$

Note that the problem remains strongly NP-complete even if $p/4 < a_i < p/2$ (which forces each $S_i$ to contain at exactly three elements); see the original definition of 3-PARTITION in Garey&Johnson, Computers and Intractability.

We can build an equivalent EVEN PALINDROME instance in this way:

We add the long string:

$$w = 1 \, 0^p \, 111 \, 0^p 11111 \, 0^p \, ... \, 0^p \, 1^{2m+1}$$

Then we add $n$ more strings:

$$v_i = 0^{a_i}\; , \;i = 1...n$$

and $1 + 3 + 5 + (2m+1) = \sum_{j=1}^{m+1} (2j-1)$ strings of length 1:

$$r_k = 1 \; , \; k = 1...\sum_{j=1}^{m+1} (2j-1)$$

Note that $|w| = \sum_{i=1}^n |v_i| + \sum_k |r_k|$

Proof:

By construction the $w$ contains substrings of odd increasing length $(1,111,11111, ...)$, so it cannot be "placed" in the middle of $u u^R$; but it must be placed entirely in $u$ or entirely in $u^R$ (without loss of generality suppose that it is placed in $u$.

Now the others $v_i$ must be arranged in the opposite part $u^R$ and in such a way that every $p$ zeroes (that can be "totalized" using the $v_i$) an odd number of the $r_k$ can be placed (to reflect the corresponding $1^{2j+1}$ substring of $w$). Furthermore all elements must be placed, so exactly 3 $v_i$ must be picked to reflect each of the $0^p$ substring of $w$. So if an EVEN PALINDROME can be found it induces a valid 3-partition of the $a_i$ of the original problem.

The opposite direction (a 3-partition exists $\Rightarrow$ there is an EVEN PALINDROME is immediate by construction).

Example:

3-Partition instance: $S = \{1, 1, 1, 2, 2, 3 \}$, strongly NP-complete; so we can also represent the numbers in unary: $S' = \{ 1_1, 1_1, 1_1, 11_1, 11_1, 111_1 \}$

EVEN PALINDROME reduction:

$w = 1000001110000011111$

$v_i = \{ 0, 0, 0, 00, 00, 000 \}$

$r_k = \{ 1,\quad 1,1,1,\quad 1,1,1,1,1 \}$

Solution of EVEN PALINDROME:

$$uu^R = 1000001110000011111 \quad 11111 \; 0 \; 00 \; 00 \; 111 \; 000 \; 0\; 0\; 1\}$$

which corresponds to the 3-partition:

$S_1 = \{ 1, 2, 2 \}, S_2 = \{ 3, 1, 1 \}$


How to avoid column wise access in matrix multiplication? I know when we access elements  in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise.
In GPUs with CUDA/OpenCL I could resolve this issue by explicitly copying both matrices row-wise into user-managed shared(cache)-memory (or local memory in OpenCL), and then can access data for matrix multiplication in anyway- no penalty for column access.

My question is how do I avoid such column access if I am implementing Matrix-multiplication on CPU, where I do not have any access to such shared memory as in GPU?

I'm assuming you don't want to store a copy of the second matrix in column-wise order and then multiply. In this case maybe the best way is to take the most advantage of cache hierarchy in modern CPUs. There are many complexity results for such setting.

For matrix multiplication there is a cache-oblivious algorithm based on Strassen's algorithm. Here you can find it in details. Notice that their aim is to optimize I/O access, so it may not fully match your requirement.


Show that the inequality holds for all positive integers $a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n>=3$
Show $a_n<3^n$ for all positive integers n
Base case: $a_3 = 2*9+3*2 = 24<=3^3$ is true
Hypothesis: $a_k<=3^k$ for $k\epsilon\mathbb{N}$, show $a_{k+1}<=3^{k+1}$
Begin:
$a_k<=3^k$ implies $3a_k<=3^{k+1}$
by definition: $a_{k+1} = 2a_k+3a_{k-1}$
$2a_k + 3a_{k-1} <= 2a_k + a_k = 3a_k <= 3^{k+1}$
Because $3a_{k-1} = 2a_{k-1} + a_{k-1} = 2a_{k-1}+2a_{k-2}+3a_{k-3}$
$3a_{k-1}$ will always be smaller than $a_k$ because $2a_{k-2}+3a_{k-3}$ is always smaller than $3a_{k-2}$
So because $a_{k+1} <= 3a_k$ and $3a_k<=3^{k+1}$ then $a_{k+1}<=3^{k+1}$ which proves $a_n<=3^n$ for all n
Is my proof legit?

We are not going to prove that $a_k\geq 3a_{k-1}$ because it is not true: $$a_3=2a_2+3a_1=2\cdot 9+3\cdot 2=24<3\cdot 9=3a_2$$

We also don't have $a_k<3^k$ for all $k$, since $a_2=9=3^2$. That's probably a typo.

Let's prove, by induction, that for all natural $k$ we have $a_k\leq 3^k$.
We have that $a_1=2\leq 3=3^1$.
Assume that $a_{k-2}\leq 3^{k-2}$ and $a_{k-1}\leq 3^{k-1}$. Or you can assume that $a_t\leq 3^t$ for all $t<k$.
Then
$$\begin{align}
a_k&=2a_{k-1}+3a_{k-2}\\
&\leq 2\cdot 3^{k-1}+3\cdot 3^{k-2}\\
&=3\cdot 3^{k-1}\\
&=3^{k}
\end{align}$$
Therefore, $a_{k}\leq 3^{k}$.
By induction, for all natural $k$ we have that $a_{k}\leq 3^k$.


Does XNOR of three variable equals XOR of same three variables I came across following excerpt:

  $(x'y'+xy)'z'+(x'y'+xy)z=x\oplus y\oplus z$

What I see is left hand side is XNOR of $x,y$ and on right, $z$ and I get XOR of of $x,y$ and $z$ !!!
In other word,

  $XNOR(XNOR(x,y),z)=XOR(XOR(x,y),z)$

Somehow I am surprised by the result, as I didnt came across this earlier, no text stated this explicitly and was unexpected.
It was unexpected because, I knew some other equalities and inequalities stated below, so was never thought of existence of above equality.

  $XNOR(x,y)=NOT(XOR(x,y))$
  $NAND(NAND(x,y),z)\neq AND(AND(x,y),z)$
  $NOR(NOR(x,y),z)\neq AND(OR(x,y),z)$

Q1. Am I interpreting it correct as XNORs of three variables equals XOR of same three variables?
Q2. If yes, can someone shed more light about why such relationship is not true for other gates? Is just that their definition does not permit such relationship? Or Is it beacause ExOR is not basic gate, while AND and OR are?

PS: Sorry for naive, possibly stupid question.

The full excerpt:

  $(x'y'+xy)'z'+(x'y'+xy)z$
  $(x'y')'(xy)'z'+x'y'z+xyz$
  $(x+y)(x'+y')z'+x'y'z+xyz$
  $xy'z'+x'yz'+x'y'z+xyz$
  $=x\oplus y\oplus z$

XOR is addition modulo 2, and XNOR computes the sum modulo 2 of its inputs and 1. Since
$$ (x+y+1)+z+1 \equiv x+y+z \pmod{2}, $$
We see that XORing three variables is the same as XNORing them. The same holds for any odd number of variables. When XNORing an even number of variables, you get the negation of their XOR.

Nothing of this sort happens for AND or OR. There isn't any particular reason. You should think of it the other way around: XOR satisfies this surprising property, but other gates do not. XOR is special. It has absolutely nothing to do with AND and OR being "basic gates", whatever that means (mathematically, probably not much).


When can I use dynamic programming to reduce the time complexity of my recursive algorithm? Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that if satisfied by a recursive algorithm would imply that using dynamic programming will reduce the time complexity of the algorithm? When should I use dynamic programming?

Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is called on a set of inputs which were already used, the results are just fetched from the table. This reduces recursive Fibonacci to iterative Fibonacci.

Dynamic programming can be even smarter, applying more specific optimizations. For example, sometimes there is no need to store the entire table in memory at any given time.


How to get Algorithm complexty based on another 2 algorithms? I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively.
Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (The input for $A_3$ is the input for $A_1$.)
Give a worst-case time bound for $A_3$.

How could I calculate the worst case based on the given info?

The total running time of $_3$ will be bounded by $()+()$ where $$ is the size of the input to $_1 $and $$ is the size of the output of $1$. Now time complexity is usually written in terms of the size of the input of the algorithm and nothing else, so if $=()$ then the running time of $_3$ will be $\mathcal{O}(p(x)+q(f(x)))$


Master Theorem and rounding up to the nearest integer For the master theorem for recurrences of the form

$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$

what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/b$? My guess is that this would only allow splits that are natural numbers, and obviously you can't split into a non-integer number, but I can't see anything beyond that.

Yes, this is generally valid.  Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid?  Let me give three explanations, in order of decreasing amount of hand-waving:

Informally, it probably won't make much difference, and probably not enough to change the asymptotics.  Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).
Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$.  Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$.  What about other values of $n$ that aren't a power of $b$?  Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$.  Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$.  Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.
A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.


How can I download a streaming file without the file's specific address? I want to download a streaming file, but I don't know the real address of that file, only the address where the stream is.
How can I download that file? Is it possible to know the address of the file by sniffing the connection?

What do you suppose happens in the back-end when you request a download of a file from a given location? The file gets converted to some encoding (in the most basic/general case: binary) and streamed over a network connection to you as a receiver.

Really for all practical purposes you wouldn't be able to distinguish downloading a 'real' file from download/receiving an active (bit)stream of that file as they're generally the same thing: bits being pushed across a connection.


Computing $n$th lexicographically smallest permutation of length up to $k$ I wonder how to tackle such problem, to be more specific:

  Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say that the permutation is valid if its length is up to $k$ (inclusive).

Here's an example: $S$ = {a, b, c}, $k$ = 4, $n$ = 15

a aa aaa aaaa aaab aaac aab aaba aabb aabc aac aaca aacb aacc ab

Output should be: "ab" as it's the n-th lexicographically smallest permutation of length up to k of this set.

How to do this efficiently?

Your kind of problem reduces to the problem of enumeration. For example, suppose that you wanted to know the first letter of the $n$th lexicographically smallest non-empty string of length at most $k$ over the alphabet $S$. You could easily solve that if you could calculate the number of strings of length at most $k$ that start with a given letter.

More generally, the enumeration problem you have to solve in your case is:

  How many strings of length up to $k$ over the alphabet $S$ start with the prefix $w$?

This is not such a hard problem, and I'll let you solve it on your own. I'll also let you figure out how to use the result in order to solve your problem.


Definition of deterministic pushdown automaton Wikipedia Pushdown automaton (as of aug 16, 2013) states:

  In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations. If only one computation exists for all accepted strings, the result is a deterministic pushdown automaton (DPDA)

My professor gave this as an example that we shouldn't trust Wikipedia but rather consult a textbook. Is he right?

Yes, this is an example of an informal explanation that is not quite true.

A PDA is deterministic if (at any moment) it can make at most one legal computational step. This is a local property, a condition on a single step, and not on a computation.

The statement "If only one computation exists for all accepted strings" is a global property, a statement on all computations on a given string.

Let me give an example where the two concepts differ. The language of all (even length) palindromes over $\{a,b\}$ is context-free. It is accepted by a PDA in the obvious way. Start copying the input to the stack, guess the middle, then check whether the rest of the input matches the first part read (in reverse), finally accept on the empty stack. This automaton has only one accepting computation on each palindrome, but certainly is not deterministic.

But here I have argued that "only one accepting computation" is not the correct statement, where Wikipedia does only insist on a single computation (without the condition of acceptance). So is Wikipedia right after all? Unfortunately, no. The problem is in the $\varepsilon$-transitions. It is quite legal for a deterministic PDA to have the possibility of making several $\varepsilon$-moves before and after acceptance, it may even loop. That means many accepting computations on a fine deterministic PDA. It is also the reason that some proofs on PDA need just some extra care.

You may now edit Wikipedia to correct this mistake!


Height of a 2-3-4 tree Consider the following 2-3-4 tree.

Does this have a height of 3 or 2 ?
Code for searching a min heap

If I count from the external nodes ie. the ones with the square boxes then height should be 3.
Not sure if they are to be included in the height as they are represented as NIL.
If they are not to be included then the height of the tree = 2
Any clarification on this.
Also looking to understand the following algorithm for searching in heaps -

https://tinyurl.com/w9yzwx9w

Citing from Wikipedia (https://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree)

Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.

Thus, since the squares in the bottom row do not hold data elements, they are not nodes of the 2-3-4 tree.
Then, using the definition of height from https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height the height of your tree is 2.


How is β-reduction a 2-morphism in Category theory? According to Categorifying CCCs: Computation as a Process, computation or β-reduction process in untyped-lambda calculus is in fact a 2-morphism in category theory.

Can someone please describe me how is it so and elaborate on it?

P.S. I understand that category theory is a mathematical concept but since this specific question is about β-reduction and lambda calculus I have posted it in computer science section.

Here is a new paper that covers a similar topic. The idea is that by doing algebra in enriched categories (2-categories are like categories enriched in categories), you can talk about more fine grained semantic structure on the algebra. (I haven't read through the whole paper myself, but I know enough to see some of the ideas behind it.)

The way it relates to your question is thus: ordinary categories are, "set enriched," meaning the homs are sets. When giving a categorical semantics of a type theory (say), the (open) terms are interpreted as arrows, the idea being that the domain of an arrow is the context, and the codomain is the type of the open term.

$$ Γ ⊢ e : T \ \ \ \ \ \Longleftrightarrow\ \ \ \ \  e \in Hom(Γ, T)$$

The important thing is that both the terms in the language and the semantics of those terms will form (enriched) categories, and the interpretation of those terms into the semantics will be functors that must preserve the structure of the hom collections. For sets, the structure is just equality of elements. So, equal terms must be assigned equal semantic values.

However, this means set enrichment isn't very good at letting us have structured semantic requirements. If we have β equivalent terms:

$$
(λ x → (x, x))\  e\\
(e,e)
$$

then with set enrichment, we have two choices:

They are not equal, so the semantic values assigned can be totally unrelated.
They are equal, so the semantic values must be the same.

However, option 2 basically means that our syntactic category has arrows that are β equivalence classes of terms (or whatever equivalence you wish to require of the semantics). We have pre-quotiented the syntax by all the reductions that hold.

Instead, think about poset enrichment (which is like a 2-category in which there is at most one 2-morphism between any two 1-morphisms). Now there is an additional partial order $\prec$ on elements of the sets, and the semantic assignment must respect that partial order. Now we have a third option, which is to say these two terms are not equal, but they are related:

$$(λ x → (x, x))\ e \prec (e, e)$$

And the semantics can no longer assign them completely unrelated values, they must assign them values that are 'connected' in the semantics.

With posets we are basically only able to represent whether or not a term is reducible to another. With enrichment in a category (like a 2-category), we are able (I think) to keep track of multiple potentially different ways in which reductions can occur, and how to compose them. Vertical composition is like:

$$ e_1 \rightsquigarrow e_2 ∧ e_2 \rightsquigarrow e_3 ⇒ e_1 \rightsquigarrow e_3$$

And horizontal composition is rather like:

$$f_1 \rightsquigarrow f_2 ∧ x_1 \rightsquigarrow x_2 ⇒ f_1 x_1 \rightsquigarrow f_2 x_2$$

Although you should take that with a grain of salt, because that gets into the part of the paper I haven't really read yet.

So, by using 2-categories or enriched categories, we can explicitly represent richer structure on our terms, and talk about semantics that preserves that structure.


Pattern matching on function application Suppose we have a function f :: a -> b and a function g :: b -> a such that f . g = id. You might say that g is the "inverse" of f (and vice versa). Could we then pattern match on something like f x on the left hand side by replacing occurences of x with g x on the right hand side? For example:

-- Here, (- 3) is the "inverse" of (+ 3), or more generally, (- n) is the "inverse" of (+ n)

subtractThree (x + 3) = x
subtractThree x = (x - 3)

This just randomly came to my mind and I'm wondering if there is something fundamentally wrong with this.

Edit: This is my first post here and I'm unsure whether this is the right kind of question for this community. Please don't hesitate to close this if this doesn't belong here.

If you are given that $g(f(x))=x$ for all $x$ and $f,g$ are pure functions, then your proposed transformation works.  However, the condition $f(g(x))=x$ is not sufficient: consider $f,g:\mathbb{N} \to \mathbb{N}$ given by $g(x)=2x$, $f(x)=\lfloor x/2 \rfloor$.  (I'm not sure which your g . f notation was intended to capture.)


Nodes reached with exactly $k$ steps in an undirected graph? Given an undirected graph $G$ of $N$ nodes and a starting node $s$, I want to build, with dynamic programming, a table whose $(k, n)$-th entry is $1$ if node $n$ is reachable with exactly $k$ steps from node $s$.

Specifically, for the first row of the table, I set $(1, n)$ to 1 if node $n$ is connected to node $s$. Then for the second row, I set $(2, n)$ to 1 if node $n$ is connected to any of the nodes who have value $1$ in the first row. I can stop the construction whenever I have a repeated row. In other words, I want to build the table to the point where more rows will be redundant, as there are already exact copies of them up in the table. So $k$ should be expressed in terms of $N$.

I want to check if this table construction can be done in polynomial time.  I think it boils down to whether the number of rows is polynomially bounded. Is it so?

My intuition is yes, because in the worst case, where the $N$ nodes are serially connected one next to another, and starting node $s$ is at one end, I can still reach the other end with $N-1$ steps.

There is an easier way than dynamic programming. You can compute the adjacency matrix to the power of $k \in \mathbb{N}$. Let $m$ be your adjacency matrix. Then $m^k$ contains also paths of the length $k$. All other entries would be zero.

The runtime would be (because of only matrix multiplication): $\mathcal{O}(n^3)$


Use dynamic programming to find a subset of numbers whose sum is closest to given number M Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying to find a subset $A′$ of $A$ such that the absolute value $|M - \sum_{a∈A′}a|$ is minimized. I only need to return the sum of the elements of the solution subset $A′$ without reporting the actual subset $A′$.

For example, if we have $A$ as $\{1, 4, 7, 12\}$ and $M = 15$, then the solution subset is $A′ = \{4, 12\}$, and thus the algorithm only needs to return $4 + 12 = 16$ as the answer.

The dynamic programming algorithm for the problem should run in $O(nK)$ time in the worst case, where $K$ is the sum of all numbers of $A$.

Hint: Use the classical dynamic programming algorithm to find all sums of subsets, and from that information deduce the sum closest to $M$.

You can actually improve this algorithm in two ways. First, you can improve the running time to $O(n\min(K,M))$, using the fact that the optimal sum is at most $2M$ (why?). Second, you can also find the optimal set $A'$ itself within the same time bound: just use the very same technique used to accomplish that for the usual SUBSET-SUM.


How to sort $N$ fractions from finite set We have $10^5$ fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$.
  Find (fast) algorithm which sorts them.

I ask you to look at my proposition and tell me your ideas. $\frac{p}{q}$ is represented as the ordered pair $(p, q)$.

On input we have an array a.

My idea:

for i = 1 to n
do t[i] = a[i].first * 2^(10)
countsort (t)
bring results from t to a (remember about / 2^10)

II Idea:

for i = 1 to n do
   t[i] = a[i].first * 2^(10)
{ now we have only integer numbers }
sort t by counting (as bucket use bits)
for i = 1 to n do
   a[i] = t/2^10

In this way we have O(n + log (10 * 1024)n) = O(14n).
What about this solution ?

You can sort all $11^2$ possible fractions, and create a table mapping $p/2^q$ to its position in this ordering, and another table going the other way. Then you can use counting sort to handle $N$ fractions in time $O(11^2 + N)$. (Here the underlying constant is universal, not depending on the size of the domain.)


A visitor at a political convention with n delegates So I have been asked to specifically construct a divide and conquer algorithm for the question:
"You  are  a  visitor  at  a  political  convention  with n delegates;  each  delegate  is  a  member  of exactly one political party.  It is impossible to tell which political party any delegate belongs to;  in  particular,  you  will  be  summarily  ejected  from  the  convention  if  you  ask.   However,you can determine whether any pair of delegates belong to the same party or not simply by introducing  them  to  each  other—members  of  the  same  party  always  greet  each  other  with smiles  and  friendly  handshakes;  members  of  different  parties  always  greet  each  other  with angry stares and insults.
Suppose more than half of the delegates belong to the same political party.  Describe an  efficient  algorithm  that  identifies  all  members  of  this  majority  party.   How  many introductions do you need?
So I came up with the pseudocode:
AMajorityPolitician(set of politicians S):

 if |S| == 1 :
  return S
 L = AMajorityPolitician(half of S)
 R = AMajorityPolitician(other half of S)

 if party[first item in L] == party[first item in R]:
  return L U R
 else
  return max(|L|,|R|)

AllMajorityPolititians(set S of n politicians):

 M = AMajorityPolitician(S)

 first = first item of M

 ans = {first}
 for each p in S:
   if first smiles to p:
     ans = ans U {p}

 return ans

But I don't think this works because if I have a list of politicians parties such as: 2,2,1,1,1 and it is split s.t. L=2,2,1 and R=1,1 then majority of L is party 2 of size 2 and majority of R is party 1 of size 2 so algorithm could pick 2 as the majority.
But I don't really know where to go from here to fix it. Do you guys have any suggestions?

You need to make sure what is returned from AMajorityPolitician(set of politicians S) is indeed a politician from the majority in S if there is a majority.
To ensure majority, we need to count the number of politicians who are in the same party as the chosen one. Here is the simple routine.
def number_of_friendly_politicians(person, all_people):
    count = 0
    for p in all_people:
        if smiles_between(person, p):
            count ++;
    return count

Now refactor AMajorityPolitician to the following function, which returns a majority politician in politicians whenever there is a majority.
def a_majority_politician(politicians):
    if size(politician) is 1:
        return that person

    L = a_majority_politician(half of politicians)
    R = a_majority_politician(other half of politicians)

    if number_of_friendly_politicians(L, politicians) * 2 > size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.


Latin-1 Supplement Unicode Characters The unicode characters under the "Basic Latin" unicode block from U+0020 to U+007F are the characters that characters we use in English. However, the "Latin-1 Supplement" block from U+00A0 to U+00FF is an extension of the "Basic Latin" block and includes characters that are used in some languages. For example, the Spanish language use all the characters from U+00A0 to U+00BF as well as the letter "Ñ/ñ" (U+00D1 and U+00F1), which is pronounced like the "ny" in "canyón". So, how did some languages get the characters under the Latin-1 supplement block?

The Latin-1 supplement was taken unaltered from the upper half of an existing standard, ISO 8859-1, which in turn was based on a standard published by the European Computer Manufacturers Association (ECMA) in the early 1980s as ECMA-94.
ECMA-94 was based on an actual hardware encoding, developed by Digital Equipment Corporation (DEC) for its popular VT-220 video display terminal, presumably on the basis of what they perceived as customer demand. But the various national standards associations negotiated some adjustments which, as is often the case, were hammered out in interminable meetings attended by well-meaning people with a lot if enthusiasm but without much expertise in designing character sets.
In the end, ISO 8859 was extended to a series of 8-bit encodings, ISO 8859-1 through ISO 8859-15, providing support for national languages which had not been well-served by the original encoding.
By then it was obvious that 256 codes were not enough for all the alphabets in use at the time, but there was still some reluctance to switch to a wider encoding for languages which could be shoe-horned into eight bits. Many manufacturers were quite prepared to sacrifice the possibility of representing multilingual documents (unless, of course, one of the languages was English), and the relatively simple Unicode proposal was countered within the ISO by a byzantine collection of unworkable multibyte shift encodings. Fortunately Unicode did eventually prevail, but the provisions for context-dependent shift encodings continue to complicate multilingual APIs.
For another view of this history and some interesting links, you can check out the Wikipedia entry on ISO 8859-1.


Enumerating all partial permutations of given length in lexicographic order I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }  .
For each chosen tuple, all of its permutations need to be present in the output. For example, for k = 2, the chosen tuple (0, 1) needs to have both (0, 1) and (1, 0) in the output. The output overall needs to be in lexicographic order, which in turn implies that lexicographic ordering of permutations within a given chosen combination is not enough.
I'm following along with
https://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html
which offers a simple recursive algorithm to generate combinations. Their recommendation to do this:

Note that you can get all permutations of n things taken k at a time by simply calling perm (v, maxk, 0); at the base case of combinations. This generates all k! permutations of each of the n C k combinations, taking O(k! n (n C k)) = O((n+1)!/(n-k)!) time.

gets me 90% of the way there, but yields result tuples in an order that is not useful to me. For k=2 it yields
[0, 1]
[1, 0]
[0, 2]
[2, 0]
...

where I would want it to yield
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[0, 5]
[0, 6]
[0, 7]
[0, 8]
[0, 9]
[1, 0]
[1, 2]
...

Is there a modification to this algorithm - or a different one - that will do this? I hope it doesn't require putting everything in memory and then applying an in-place sort.

Here is a simple iterative solution. We maintain two arrays, an output array $L$, and a Boolean array $A$, which keeps track of the elements currently in $L$. We update $A$ as we add and remove elements from $L$.
We initialize $L$ with $0,\ldots,k-1$, which is also our first output. Now we repeatedly try to "increment" $L$. If successful, we output the incremented $L$, and try to increment $L$ again. If unsuccessful, we have gone through all combinations, and can terminate.
In order to increment $L$, we start by trying to increment position $k-1$ (this is the rightmost position). We do so by scanning the array $A$ starting at $L[k-1] + 1$, until we find an element $x$ which is not in $L$. If this search is successful, we replace $L[k-1]$ with $x$. Otherwise, we try to do the same for $L[k-2],\ldots,L[0]$, until successful; if all of these fail, we declare failure (and terminate).
Suppose that we have successfully replaced $L[j]$. If $j = k-1$, we're done. Otherwise, we have to update $L[j+1],\ldots,L[k-1]$, which we do by scanning $A$ starting at $0$, inserting the first $k-j-1$ elements not already in $L$.
Here is a Python implementation:
def gen(n, k):
    A = [True] * k + [False] * (n-k)
    L = list(range(k))
    yield tuple(L)
    while True:
        j = k - 1
        while j >= 0:
            A[L[j]] = False
            t = L[j] + 1
            while t < n and A[t]:
                t += 1
            if t < n:
                A[t] = True
                L[j] = t
                r = 0
                j += 1
                while j < k:
                    while A[r]:
                        r += 1
                    A[r] = True
                    L[j] = r
                    j += 1
                yield tuple(L)
                break
            else:
                j -= 1
        if j == -1:
            break

An even simpler recursive solution simply iterates over all possible choices of the first element; within these, iterates over all possible choices of the second element; and so on.
Here is a Python implementation:
def gen_rec(n, k, L=[]):
    if len(L) == k:
        yield tuple(L)
    for i in range(n):
        if i not in L:
            yield from gen_rec(n, k, L + [i])


Grammar for all words other than $wq,qw$ I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$.
My grammar:
\begin{align}
&S \to qSw \mid wSq \mid qXq \mid wXw\\
&S \to qYw \mid wYq \mid q \mid w\\
&X \to qX \mid wX  \mid qXw \mid wXq \mid ε \\
&Y \to qw \mid wq \\
\end{align}

How about
\begin{align*}
S&\to q\mid w\mid qqB \mid wwB \mid qwA\mid wqA\mid \varepsilon \\
A&\to qB\mid wB \\
B&\to qB\mid wB\mid \varepsilon
\end{align*}
We can just explicitly include strings of length 0, 1 or 2 that are allowed, but add another non-terminal after the length two strings which are not allowed to force us to add at least one more terminal, then make sure after that we can add any letters we want in any order.


Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable? This is text of an exercise I am working on:

Given a binary encoding scheme for the set of the  deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: \{0,1\}^* \rightarrow \{0,1\}^*$, prove that the language
$$L=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}$$ is recursively enumerable and undecidable.

I don't know how to prove it, and I don't know where to start.

Using formal notations rather than words would make your life easier. Since you have a
binary encoding of  Turing Machines (TM), you should use a formal
notation for it.

For example you can give it a name, say $g$. Then an encoding $x$ of a
TM $M$ can be written $x=g(M)$, or if you want to use the common angle
bracket notation: $x=\langle_g M\rangle_g$. Note that I keep $g$ as a
subscript of the angle brackets, so that I can distinguish different
binary encodings of Turing Machines.

Now, if $g$ is a binary encoding scheme for TMs, then its composition
$h=f\circ g$ with a bijective and computable function $f$ (from binary
numbers to binary numbers) is also a binary encoding scheme for TMs,
such that (using the various possible notations) $h(M)=f(g(M))=\langle_h M\rangle_h=f(\langle_g M\rangle_g)$.

Now you can rewrite the definition of $L$ using this new binary
encoding scheme:
.$$\begin{align}
L&=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}\\
&=\{f(x)\mid \mbox{$x=\langle_g M\rangle_g$ and $M$ accepts $f(\langle_g M\rangle_g)$}\} \\
&=\{f(\langle_g M\rangle_g)\mid \mbox{$M$ accepts $f(\langle_g M\rangle_g)$}\}\\
&=\{\langle_h M\rangle_h\mid \mbox{$M$ accepts $\langle_h M\rangle_h$}\}
\end{align}$$

It is now easy to see that L is recursively enumerable, since for any
value $x$, we can test whether it is in $L$ by running the machine $M$
such that $x=\langle_h M\rangle_h$ with input $x$, which does
terminate when $x\in L$.

However, $L$ is not decidable. The proof goes by contradiction.
We first suppose that $L$ is decidable. Thus its complement $\overline
L$ is also decidable, and is recognized by a Turing machine $\overline
M$

If $\overline M$ accepts $\langle_h \overline M\rangle_h$, then
$\langle_h \overline M\rangle_h$ is in $\overline L$, the language
that $\overline M$ recognizes by definition. But this implies, by definition of
$\overline L$ that $\overline M$ does not accept $\langle_h \overline
M\rangle_h$.

But if $\overline M$ does not accept $\langle_h \overline M\rangle_h$,
then $\langle_h\overline M\rangle_h\notin L$ by definition of $L$. Thus $\langle_h\overline
M\rangle_h\in\overline L$. Hence since $\overline M$ recognizes
$\overline L$,  $\overline M$ must accept $\langle_h \overline
M\rangle_h$.

In both cases we have a contradiction. So the hypothesis that $L$ is
decidable cannot hold.


How many algorithms solve the same problem? Its kind of a weird question to ask but I have been asking myself this: Is there a limit to number of ways to find a solution to a particular problem.

Take the simplest problem: sorting a sequence of numbers.

Now there are a lot of algorithms to sort. Is there a limit to such algorithms? Technically, you can always flip a bit and back again, so there are infinite number of ways.

But still, simple problem as sorting, surely there must be finite number of ways to solve it.

In computer science we have computability theory which tells us whether a problem is solvable, complexity theory which tells us time and space to solve the problem. Similarly, is there something which can tell us the number of ways we can solve a particular problem?

Motivation for this question is that I'm amazed how many sorting algorithms we have. Such a simple problem and there are so many solutions!

Note: I asked this on stackoverflow. It seems that we need to precisely define how we would differentiate between two algorithms. Let's say we do it by somehow recognizing steps that are useless. That way we can say if two algorithms are doing the same thing.
What after that?
Lets take the example of sorting. All you can do is move one number from one index to other. With just this operation, surely there must be finite number of algorithms to solve the sorting problem

As far as I can see, there are always infinitely many ways of doing something, even if you try to define and disallow redundant steps.  Let's take the example of sorting.  Even if you restrict to the operations of comparing and swapping numbers, there are infinitely many ways of sorting a list: quicksort the list; swap the first two numbers and then quicksort; swap the first two numbers twice and then quicksort; ...; swap the first two numbers $n$ times, then quicksort; ...

OK, so you try to disallow that as "wasting time". But then there are still infinitely many ways: quicksort; mergesort if the list has length two, otherwise quicksort; mergesort if the list has length three, otherwise quicksort; ...

OK, so you try to disallow that on grounds that quicksort and mergesort will always produce the same answer so the test on the length of the list is redundant. But this is too coarse a notion of equivalence, since now there's exactly one algorithm for every problem – every correct sorting algorithm produces the same answer by definition.


Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time? I'm following an online course which has the following (multiple-choice) quiz question:

  Which of the following statements cannot be true, given the current
  state of knowledge?

  Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
  There is an NP-complete problem that is polynomial-time solvable.
  There is an NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.
  There is no NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.

It seems to me that (1) and (2) are false since it has not been proven that any NP-complete problem is polynomial-time solvable. So I'm vacillating between (3) and (4).

In particular, I'm a bit nonplussed where the $O(n^{\log n})$ comes from; I haven't seen this expression in any of the lecture notes. However, I do know about the traveling salesman problem which can be solved in $O(n^2 2^n)$ time using the Held-Karp algorithm. It would seem to me like this function grows less faster asymptotically than $O(n^{\log n})$, since it is usually the expression in the exponent that matters the most, in which case the answer would be (3).

Is this correct? Also, how would I show this formally?

The accepted answer is incorrect. I've taken the same course, and option 1 is correct. They didn't say why, but I have the following argument.
Quoting Wikipedia:

polynomial time: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $ T(n) = O(n^k) $ for some positive constant $ k $.
exponential time: An algorithm is said to be exponential time, if $ T(n) $ is upper bounded by $ 2^{poly(n)} $, where $ poly(n) $ is some polynomial in $ n $. More formally, an algorithm is exponential time if $ T(n) $ is bounded by $ O(2^{n^k}) $ for some constant $ k $.

We don't know $ P \neq NP $, so option 2 can't be ruled out.
For all we know, the running time required to solve NP-complete problems could be anywhere between polynomial and exponential (note that $ n^{\log n} $ is more than polynomial but less than exponential). Thus, options 3 and 4 can't be ruled out.
That only leaves option 1. The claim in option 1 is incorrect because if there's a polynomial-time algorithm for any NP-complete problem X, then every other NP problem has a polynomial-time algorithm by reduction to X.


How to practically construct regular expander graphs? I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.

What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is proven to be a.a.s. an expander?

I also read about Margulis constructions and Ramanujan graphs that are expanders and a construction using a zig-zag product. Wikipedia gives a nice but very short overview: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10
But which method do I choose in practice?

For me, these methods seem all very complicated to implement and in particular to understand and maybe quite specific.
Aren't there easier methods, maybe based on permutations or so, to practically generate a sequence of d-regular expander graphs?

Is it maybe easier to construct d-regular bipartite expander graphs?

I also have another question: What about families of bad d-regular expanders? Does such a notion make sense? Can one construct a family of d-regular graphs (that are of course connected) that is as bad as possible in the sense of an expander?

Thanks in advance.

If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular.

Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$.
For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$.
Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$.

As an example, the 7-vertex graph in the family is a 7-cycle with vertices numbered sequentially around the cycle; there are self-loops on $6$, $0$, and $1$; finally, there are chords joining $3$ and $5$, and $2$ and $4$.

See https://mathoverflow.net/questions/124708/an-expander-graph  for further discussion and references.  There are lots of more detailed pointers by searching on "expander" at CSTheory, Math.SE, and MO.

As Yuval Filmus points out, the random construction is likely to give better results in general, but of course may not yield an expander (especially for small graphs).


What is the field studying the search and generation of computer programs? This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that integer sequence. I was trying to approach the same idea using lambda-calculus instead of a stack-based language, but I was stuck on the enumeration of valid programs on LC's grammar.

Anyway, what is the field studying that kind of idea and how can I grasp the current state-of-art?

What you are describing is a Kolmogorov complexity approach. The Kolmogorov complexity of an integer sequence (or a string) is the size of the minimal program computing it (in some fixed Turing-complete language). Here we're looking for the minimal program which generates $n+1$ numbers, the first $n$ of which are the given sequence.

Kolmogorov complexity is not computable - that is, one cannot compute the size of a minimal program computing a given sequence. The implementation you mention computes a restricted version of Kolmogorov complexity in which the programs are very simple (and always halt).

Another (non-computable) approach is the universal probability distribution in which a given integer sequence of complexity $x$ is given a probability in proportion to $2^{-x}$. By conditioning on the first $n$ numbers produced, we can construct a probability distribution on the next number. By restricting the set of programs, we can make this distribution computable (though perhaps not efficiently).


Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms? If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit.
Can any randomized Algorithm be seen as a probability distribution over the set of deterministic Algorithms? And if yes, why?

You can think of a randomized algorithm as having access to a random variable $\mathbf{r}$, which informs its random decisions. For any fixing of $\mathbf{r}$, you get a deterministic algorithm, and in this way you can view the original randomized algorithm as a distribution over deterministic algorithms.
As an example, consider the randomized algorithm for solving MAX-3SAT. The algorithm chooses a random assignment. You can think of this assignment as specified by $\mathbf{r}$. Any particular assignment corresponds to a deterministic algorithm, and the original randomized algorithm is just the uniform distribution over these deterministic algorithms.


Characterization about Kleene Closure, when is a language $L=L^*$? I'm trying to find a characterization of when $L=L^*$.
I think I have one, but maybe is trivial, but I don't know if the proof is correct.
Claim: $L=L^* \Leftrightarrow L=LL$.
Proof:
If $L=L^*$ then is easy to see $LL \subseteq  L$ so $L=LL$.
The other implication is in which I have doubts, I used a simple chain of equalities
$$L=LL=\cdots=L^n=\cdots= \bigcup_{i\geq 0}L^i=L^*.$$
I would like to know if there is something wrong and specially if there's another characterization which is less trivial.

What your argument actually shows is
$$
L = L^* \Rightarrow L=L^2 \Rightarrow L = L^+.
$$
Indeed, suppose that $L = L^*$. On the one hand, $L^2 \subseteq L^* = L$. On the other hand, since $\epsilon \in L$, we have $L = \epsilon L \subseteq L^2$.
Next, suppose that $L = L^2$. Inductively, $L = L^n$. In particular, if $w \in L^+$ then $w \in L^n$ for some $n$, and so $w \in L$, showing that $L^+ \subseteq L$; and $L \subseteq L^+$ trivially holds.
If $L = L^+$ then we cannot conclude that $L = L^2$. For example, $a^+ = (a^+)^+$ but $a^+ \neq a^+a^+$.
If $L = L^2$ then we cannot conclude that $L = L^*$. For example, $\emptyset = \emptyset^2$ but $\emptyset \neq \emptyset^*$.
However, it is possible to prove the following:

If $L = L^+$ and $\epsilon \in L$ then $L = L^2$. This shows that if $\epsilon \in L$, then $L = L^+ \Leftrightarrow L = L^2$.
If $L \neq \emptyset$ then $L = L^2 \Rightarrow L = L^*$. This shows that if $L \neq \emptyset$, then $L = L^* \Leftrightarrow L = L^2$.

Indeed, if $L = L^+$ and $\epsilon \in L$ then $L^2 \subseteq L^+ = L$, and $L \subseteq \epsilon L \subseteq L^2$.
Next, if $L \neq \emptyset$ and $L = L^2$ then let $w$ be a word of smallest length in $L$. Since $L = L^2$, we can write $w = xy$, where $x,y \in L$. By assumption, $|x|=|y|=|w|$, and so $|w| = 2|w|$, implying that $w = \epsilon$. Together with $L^+ \subseteq L$, this shows that $L^* \subseteq L$, and so $L = L^*$.

Another nice characterization is:
$$ L = L^* \Leftrightarrow L = M^* \text{ for some language } M. $$
One implication is trivial. In the other direction, if $L = M^*$ then $L^* = (M^*)^* = M^* = L$.
This characterization remains true if we impose restrictions on $M$, for example $M \cap M^2 = \emptyset$. Indeed, suppose that $L = L^*$, let $\tilde L = L \setminus \{\epsilon\}$, and let $M = \tilde L \setminus \tilde L^2$. Note that $M^2 \subseteq \tilde L^2$, and so $M \cap M^2 = \emptyset$. Also, clearly $M^* \subseteq \tilde L^* = L$. On the other hand, we can prove inductively that $L \subseteq M^*$.
Indeed, let $w \in L$. If $w = \epsilon$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L$. If $w \in M$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L^2$, that is, $w = xy$, where $|x|,|y| < |w|$. By induction, $x,y \in M^*$, and so $w = xy \in M^*$.


Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search? I came across the chalk-and-string labyrinth analogy for depth-first search in Algorithms by Dasgupta et al.  I have seen the code for the depth first search.

Everybody knows that all you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk prevents looping, by marking the junctions you have already visited. The string always takes you back to the starting place, enabling you to return to passages that you previously saw but did not yet investigate.

How a computer does it in code makes sense, but as a human, I think that the string is sufficient. why would I need the chalk, wouldn't see the string indicate that I have already passed a junction?

First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs.
Now graphs can be directed, which would correspond to having a labyrinth with junctions/rooms and one-way pathways between them.
Then it is possible for you to be in some room $r_0$ and to travel to some other room $r_1 \neq r_0$ as a part of your labyrinth exploration.
Maybe all paths from $r_1$ lead to a dead end, so you backtrack to $r_0$. From there you continue to explore until you reach a third room $r_2 \not\in \{r_0, r_1\}$.
The problem arises if $r_2$ has a pathway to $r_1$: without any record that you already visited $r_1$, you'd visit it again.
To stick with your analogy, you don't need strings if the floor plan of your labyrinth can be represented as a tree (rather than a general graph). Indeed, if you have a tree and some (arbitrary) order among the edges from a vertex to their children (as it is usually the case in actual implementations), you can implement a DFS without keeping any information other than the current and previous vertices of the search (i.e., an edge of the tree).


Prove $n! = o(n^n)$ without limits I've already proven the statement using the limit definition of $o(g(n))$ and Stirling's approximation, but how do I prove it using the main definition for $o$ notation provided in CLRS instead?
Definition: $f(n) = o(g(n))$ if for all $c > 0$ there is $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n > n_0$.
I've tried substituting Stirling's approximation again, but I am unaware of any analytic means of determining $n_0$ as a function of $c$ due to the presence of the $n$ term as both a base and exponent in the resulting inequality.

You do not need anything as fancy as Stirling. It is easy to see that $n!\cdot n < n^n$ for all $n>2$ (just compare the first two terms of $n!=1\cdot 2\cdot\ldots$ witht those of $n^n=n\cdot n\cdot\ldots$).


Is it possible for a graph to have two different minimum spanning tree I am suppose to create a minimum spanning tree from this graph below

I got this answer

However this is my textbook answer

Based on what i have learnt , I think my answer and the textbook answer would both be acceptable however I would like assurance from the community that both the answers are acceptable and I did not miss anything out

Thanks

It is possible to have different minimum spanning trees for a graph.
Consider a simple example: a cycle graph with all weights equal. Removing any edge from the graph produces a minimum spanning tree for the cycle graph.


Finding all vertices on negative cycles Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a way to do it faster than Floyd-Warshall's $O(|V|^3)$?

If you don't constrain yourself to simple cycles, you can actually use the Bellman-Ford algorithm to find all the relevant vertices.

Start by running a DFS on the graph to find its strongly connected components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ iterations where $V_i$ is the vertices in $G_i$), add $V_i$ to your list of vertices that belong to a negative (not necessarily simple) cycle.

If one of the strongly connected components contain a negative cycle, then because $G_i$ is finite and so are the weights, you can loop through the negative cycle as much as you need, and then add go in a cycle through all the vertices in $G_i$. You only need to loop an amount that will guarantee a total negative cycle.

It is easy to show that there are no cycles between any $G_i,G_j$ and therefore there are no negative cycles other than inside the strongly connected components.

Since you run BF on each subgraph seperately, you keep the time complexity of BF which is $O(|V|\cdot|E|)$.


Dynamic programming approach for finding perfect square subsequence Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,\ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,\ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 \cdot a_2 \cdots a_i$. The subsequence $a_i,\ldots,a_j$ multiplies to a perfect square iff $b_j/b_{i-1}$ is a perfect square, which happens if the vectors corresponding to $b_{i-1}$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,\ldots,c_\ell$. The answer is then $\sum_i \binom{c_i}{2}$.


Get mathematical relation of node IDs of a subtree based on a given tree (I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.)

Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning from 0. The ID counting is taking place in breadth-first order.

Now I want to pick out a part of the graph A. The information of the subtree is given by a node ID in the original tree A.

Example

Let's say the new tree starts with the node ID 3 of the original tree. For this example, the tree depth has an offset of 1 (because 3 is in depth 1 of the original node). The result is the following

You might have noticed that the new tree have the same structure than the old tree. The unique ID of each node in the new tree, will also be counted up in breadth-first order. In the brackets, you can see the link to the original node tree A.

Background

The reason, why I need this node link is the fact that I need to copy some node properties from the original tree node to the new tree node.

Question

What is the mathematical relation between the unique node IDs of the new tree and the node IDs of the original tree? I want to compute the ID's of the old tree, based on the ID's of the new tree.

Thanks for any help.

I don't think there is any "mathematical relationship". Observe that if you change the tree around the extracted subtree, the original IDs change arbitrarily.

You should copy properties while creating the copy of the tree you want to extract. Perform a tree traversal on the subtree in question and do everything in one pass.

You can also link new nodes to the old ones in case you need the relationship later.


Solving a recurrence Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution....
I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) + n$ and then substituting $n = 2^{m}$ but things gets really messy !

any idea?

Assuming that the end goal is to get an asymptotic bound on the time or space complexity of the algorithm that this recurrence relation represents, then start with $n = 4k^2$ s.t. $k > 1$ and notice the following:

$T(4k^2) = T(2k^2 + 2k) + 4k^2$

$T(2k^2 + 2k) = T( k^2 + k + \sqrt{ 2k(k + 1) } ) + 2k^2 + 2k$

$T(k^2 + k + \sqrt{ 2k(k + 1) }) = T(\ldots) + k^2 + k + \sqrt{ 2k(k + 1) }$

Substituting backward

$T(4k^2) = 7k^2  + 3k + \sqrt{ 2k^2 +2k } + T(\ldots)$

Substituting the original value of $n$

$T(n) = \frac{7}{4} n + \frac{3}{2} \sqrt{n} + \sqrt{\frac{1}{2}n + \sqrt{n}} + T(...) $

Each successive term is an order smaller than the one prior and as we look at the asymptotic behavior, those smaller terms will vanish and the linear term will dominate, thus $\mathcal{O}(n)$.


What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth? Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands from me. This vessel has to reach, say, the island of Hainan at the earliest possible moment.

What are the deterministic algorithms for finding a maritime route on a globe?
What is their time and memory complexity?
Can I, for instance, use A* after transforming the map of the globe into a diagram with connected polygons (i.e. Delaunay triangulation on a sphere/ellipsoid) and what are other feasible approaches?

Answers should ideally provide references to papers with discussion of the above-mentioned questions.

As pointed out by Rob Lang, the algorithms must fit the usual criteria: in the absence of time constraints, lead to the shortest path between any two points on Earth's oceans and seas, or indicate pathfinding failure otherwise.

There are interesting sub-topics here (trading pre-computation time/storage for online computations, providing slightly suboptimal routes before a deadline kicks in etc.), but these are ancillary to the main issue.

The deterministic requirement isn't all that constraining. That just implies your vehicle is certain of the state it's in. That being said, you'll probably want to plan paths in a way that allows you to avoid obstacles. The best way I've seen this done is with sampling-based planners. Steven LaValle wrote the central academic resource on this topic: Planning Algorithms.

The RRT* algorithm is among the planners he describes. This algorithm generates the state space tree with random samples and a few heuristics to ensure feasibility (e.g. obstacle avoidance) and optimality. Details on RRT* can be found in LaValle's book, or at Sertac Karaman's website. The asymptotic time and memory characteristics are described as O(nlogn) to process, and O(n) for queries. The algorithm is linear, O(n), in space complexity too.


Pattern bonding problem Let $\Sigma  = {1,2,3,4}$  . We say that symbol $\sigma $ bonds with
  symbol $\tau$  if $\sigma = \tau$ of $\sigma = \tau +1$ for even
  $\sigma$ and $\sigma = \tau -1$ for odd $\sigma$ . In other words  , 1
  and 2 bond  , and 3 and 4 bond (in addition to every number bonding
  with itself ) .

  The  Pattern bonding problem is defined as follows:

  INPUT :  Text $ T = t_{1}  , ..., t_{n}$  and pattern $ P = p_{1}  ,
 ..., p_{m}$ over alphabet  $\Sigma  $ .

  OUTPUT :  All locations $i$ in the text that bond with the pattern ,
  i.e  , where $t_{i+j-1}$ bonds with $p_{j}$ $j=1,...,m$ .

Can someone supply an algorithm for the pattern bonding problem (the faster the better   complexity can)  ?  , I thought about "Less then matching" .

Edit: (Answer)

Map $ (1,2) \rightarrow \alpha , (3,4)\rightarrow  \beta$ then the text and the pattern is on $\Sigma = {\alpha , \beta}$ and then we know to solve it in $O(n)$ using witness or KMP .

Hint: map $1,2$ to $a$ and $3,4$ to $b$.


Relations between deciding languages and computing functions in advice machines I'm trying to understand implications of translating between functions and languages for P/Poly complexity.  I'm not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts.  (I have a project in which I want to discuss Hava Siegelmann's analog recurrent neural nets, which recognize languages in P/Poly, but I'd like to understand and be able to explain to others implications this has for computing functions.)
Suppose I want to use an advice Turing machine $T_1$ to calculate a function from binary strings to binary strings $f: \{0,1\}^* \rightarrow \{0,1\}^*$.  $T_1$ will be a machine that can compute $f$ in polynomial time given advice that is polynomial-size on the length of arguments $s$ to $f$, i.e. $f$ is in P/Poly.  (Can I say this?  I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)
Next suppose I want to treat $f$ as defining a language $L(f)$, by encoding its arguments and corresponding values into strings, where $L(f) =  \{\langle s,f(s)\rangle\}$ and $\langle\cdot,\cdot\rangle$ encodes $s$ and $f(s)$ into a single string.
For an advice machine $T_2$ that decides this language, the inputs are of length $n = |\langle s,f(s)\rangle|$, so the relevant advice for such an input will be the advice for $n$.

Question 1: If $T_1$ can return the result $f(s)$ in polynomial time, must there be a machine $T_2$ that decides $\{\langle s,f(s)\rangle\}$ in polynomial time?  I think the answer is yes.  $T_2$ can extract $s$ from $\{\langle s,f(s)\rangle\}$, and then use $T_1$ to calculate $f(s)$, and then encode $s$ with $f(s)$ and compare it with the original encoded string.  Is that correct?

Question 2 (my real question): If we are given a machine $T_2$ that can decide $\{\langle s,f(s)\rangle\}$ in polynomial time, must there be a way to embed $T_2$ in a machine $T_3$ so that $T_3$ can return $f(s)$ in polynomial time?
I suppose that if $T_2$ must include $T_1$, then the answer is of course yes.  $T_3$ just uses the capabilities of $T_1$ embedded in $T_2$ to calculate $f(s)$.  But what if $T_2$ decides $L(f)$ some other way?  Is that possible?
If we are given $s$, we know its length, but not the length of $f(s)$.  So in order to use $T_2$ to find $f(s)$, it seems there must be a sequential search through all strings $s_f = \{\langle s,r\rangle\}$ for arbitrary $r$. (I'm assuming that $f(s)$ is unbounded, but that $f$ has a value for every $s$.  So the search can take an arbitrary length of time, but $f(s)$ will ultimately be found.)
One thought I have is that the search for a string $s_f$ that encodes $s$ with $f(s)$ has time complexity that depends on the length of the result $f(s)$ (plus $|s|$, but that would be swamped when $f(s)$ is long).
So now the time complexity does not have to do with the length of the input, but only the length of $f(s)$.  Maybe $L(f)$ is in P/Poly if $f$ is in P?  (Still confused here.)
Thinking about these questions in terms of Boolean circuits has not helped.

I think the answer to Question 2 is "no", as far as we know.  For instance, let $f$ be the function that parses its input $s$ as a 3CNF formula $\varphi$ and then returns the lexicographically earliest satisfying assignment to $\varphi$, or $\bot$ if none exists.  Then it is easy to decide $L(f) = \{\langle s,f(s) \rangle\}$ in polynomial time, but (assuming P $\ne$ NP), you cannot compute $f$ in polynomial time (and assuming P/poly $\ne$ NP, advice doesn't help).
The following might be a better way to translate between functions and languages.  Let $L'(f) = \{\langle s,i,b \rangle : f(s)_i=b\}$, where $y_i$ denotes the $i$th bit of $y$. (I assume that if $y$ has fewer than $i$ symbols, then $y_i=\bot$.)  Then if you can compute $f$ in polynomial time, you can decide $L'$ in polynomial time; and if you can decide $L'(f)$ in polynomial time and the length of $f(s)$ is polynomial in the length of $s$, then you can decide $L'(f)$ in polynomial time.


How many inputs does the Hadamard gate have? Look at the diagram in the middle of page 6-3 here,
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf

I am confused as to how should one think of the Hadamard gate.

As per the mathematics shown below it seems that the Hadamard gate, $H$ acts on tensor products of states as follows,

$$H( \otimes ^n | 0 \rangle) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$

But then the above interpretation and the diagram and the text have a few apparent discrepancies between them,

In the diagram there is no step which looks like $\otimes ^n ( H | 0 \rangle ) $. It seem that all the wires carrying $H|0\rangle$ are straight away sent to the $f$ oracle without this tensoring between them.
In terms of circuit complexity is this to be thought of as a "single" Hadamard gate or as $n$ Hadamard gates?
Lastly how does the gate $H$ know about the state $|1\rangle$ ? It only sees the $|0\rangle$ states.
And the last step is totally unclear: on which state is the $i$th Hadamard gate acting to get $ |s_i\rangle$? It doesn't seem to be there in the equations below.

Can someone help clarify this?

The $n$-ary Hadamard gate acts on $n$ qubits. The state of the $n$ qubits is a unit norm vector of dimension $2^n$. You can take as basis the vectors $|x\rangle$ for $x \in \{0,1\}^n$.

As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that the $n$-dimensional Hadamard transform is the tensor product of $n$ one-dimensional Hadamard transforms.

The usual convention in circuit complexity is that gates have bounded fan-in. Otherwise you can compute any function using a large gate!

Consider the case $n=1$:
$$
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix} 1 \\ 0 \end{bmatrix} =
\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \, .
$$
This is where $|1\rangle$ comes from.

The entire circuit involves initializing $n$ qubits at the state $|0\rangle$, applying $n$ unary Hadamard gates on the $n$ qubits, applying the black box function $f$, and then applying the Hadamard gates again on the $n$ qubits. The final state of the $i$th qubit turns out to be $|s_i\rangle$.


Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$? From Wikipedia

  A hash function is any algorithm or subroutine that maps large data
  sets of variable length, called keys, to smaller data sets of a
  fixed length. For example, a person's name, having a variable
  length, could be hashed to a single integer. The values returned
  by a hash function are called hash values, hash codes, hash sums,
  checksums or simply hashes.

I wonder if the range/codomain of a hash function is always the set of natural numbers or integers, because their function values seem to be always used as indices to some array?

Range of any hash function is a sub-set of natural numbers (this is how we think of it, exactly for access to the arrays, that could lie behind). The actual output of common hash-functions (MD5, SHAX...) is $n$ bits, where $n$ is $128$ for MD5 and $512$ for SHA2 with 80 rounds.

These bits can then be interpreted as natural numbers from interval $[0, 2^n-1]$. They can also be interpreted as integer from $[-2^{n-1},2^{n-1}]$. They can also be interpreted as "strings", although in essence they are only bits. What @Arani is talking about (I think) is probably conversion of this binary number to the hexadecimal format, and viewing it as string.


How does a compiler give an immediate compilation error? I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? What am I not understanding? I thought the whole difference between an interpreter and a compiler is that the former translates code line by line and the latter translates your source program as a whole in one go.

I'll talk about relatively simple (for the sake of analysis) languages, like C#/Java. There may be different approaches aside from want I describe here.
What IDE does during analysis is not compilation
The primary goal of IDE is not compilation, it's to assist you with code writing/analysis. For example, IDE helps you with auto-completion, refactorings (renames, indentation, dead code removal, simplifying the code), navigation (go to definition, find usages), code generation (overriding equals()/hashCode(), creating constructors, properties generation), and many, many other tasks. On the other hand, it doesn't care about resulting code efficiency, linking, and other compilation-related stuff, but e.g. it cares about preserving comments and spaces (compilers can simply throw them away). It means that IDE can (and will) use completely different structures to work with.
Code analysis
The code analysis can usually be split into three steps, in this order (for C++ these steps are mixed, which makes it a hard language):

Lexical analysis: the input is split into a sequence of tokens. E.g. a + b becomes [IDENT(a), PLUS, IDENT(b)].
Syntax analysis (or parsing; they are not exactly the same, but doesn't matter now): builds a syntax tree. E.g. a + b can be parsed as PlusExpr(left=IDENT(a), PLUS, right=IDENT(b)). c = a + b; can be parsed as AssignmentStatement(left=IDENT(c), EQ, right=PlusExpr(...), SEMICOLON).
Semantic analysis. Surely a huge field, with a lot of tasks, but for now let's only care about name resolution (finding declarations) and type checking.

Error detection
Errors types detected by IDE correspond to code analysis steps outlined above.

Lexical errors: e.g. you use some invalid token (e.g. 0gda) or you didn't close a string literal (e.g. "abc<EOF>). Usually, lexical analysis is lightning fast, and such errors are trivial to detect. To continue lexical analysis (to detect more errors and allow syntax analysis), bad literals can be ignored or fixed (e.g. the analysis can treat "abc as "abc").
Syntax errors: e.g. you forgot a semicolon c = a+b<EOF>, closing parenthesis c = (a+b;, etc. Detecting the errors is simple. A tricky part is to recover from the errors. E.g. in c = (a+b; you can assume that there should be ) before ;, report error, and continue parsing. Anyway, while error recovering is nontrivial (and often requires manual handling), it's usually performed reasonably well.
Semantic errors. I'll talk about errors like "Undefined identifier" and "wrong type" next.

Name/Type errors
In Java, there are no identifiers that come from nowhere (this is one of the reasons why Java is a relatively simple language for analysis). The sources are (as I recall):

import statements.
Identifiers declared in the same scope. E.g. when you define class A at the top level of the file, this class can be used anywhere in the file; when you write for (int i; ..., i can be used in the body of the loop.
With qualifiers. E.g. if you have an object a, which has a method b, you can write a.b.

These lead to the following structures:

For import statements, you have a global structure that analyses all source files and all linked libraries. This structure is a trie which represents a global name hierarchy. So if you've written import java.util.*, it follows the path <root>->java->util and includes all identifiers in the found node into the current file scope.

For scopes. Consider an example:
class A {
    int f() {
        if () {
            print(a);
        }
    }
}

In this example, when we try to resolve a, we try to find a declaration (in this order): 1) inside if-block, 2) inside f(), 3) inside class A, 4) in the file scope (i.e. because of imports). When the name is found, the search is done.
Therefore, for scopes, it suffices to maintain a stack-like structure: each level of the stack represents a scope and has all the names defined in this scope. When trying to find a declaration, you process the stack layer-by-layer.

For qualifiers: for a.b, when resolving b, you assume that you've already resolved a (using the above rules). Moreover, you assume that you know the type of a; it means that the above structures should maintain the types of all identifiers (which is easy to do by looking at the type at the declaration; this is another aspect that makes Java simple). Now, you simply check whether the type has a member b and which type it has.

With the above analysis, the type analysis is simple: for each identifier you know its type, and you know which type you expect: e.g. in f(x,y), if you know (after resolution) that f is a function (int, int) -> int, you know that x and y should have type int.
Why it can be done fast
All these structures can be maintained on-the-fly. In the hierarchy trie, the only modified nodes are the nodes corresponding to the current file. The scope stack and access with qualified correspond only to the current file (so you simply need to re-analyze the file).
Also, some optimizations may be used to re-analyze only a portion of the file (e.g., if you make edits inside some function, there is a chance that you need to re-analyse only this function).
Actually, the slowest operations are the following:

Building the hierarchy when the project is first opened.
Loading the hierarchy when the project is reopened. This is indeed an issue, and a lot of efforts may be required to make this efficient.
Rebuilding the hierarchy when a lot of files change simultaneously (e.g. because of git pull).

Solution-wide analysis
I was talking about finding errors in the current file.
However, editing the current file may break something else: e.g. if you remove a method from a class, all files using this method will break (the above structures can't detect it unless you open the affected file). This requires a Solution-wide analysis, which, well, analyses your entire project in real-time.
This analysis requires much more resources though (at the very least, you need to track all usages of all identifiers, and I believe there is a lot of other stuff going on there), not every machine can handle it on a large project, and it may take some time (few seconds, as I recall) for errors to be detected.


Are tiny point-symmetric grids of two Pentominos impossible to solve? The game of Pentomino is a tiling puzzle game played on a grid. A Pentomino piece is a two dimensional shape of five non-diagonally connected tiles. There are exactly 12 unique pieces (ignoring rotation/reflection). The goal of the game is to fill the board with the available pieces without overlapping.

This question concerns point-symmetric boards (not necessarily rectangular) of 10 spaces, i.e. with room for exactly two pieces.

Filling such a board is, of course, trivial when using the same piece twice.

Using the Y-piece twice on a point-symmetric hourglass board:
####
 O#
OOOO

However, it seems impossible to do when using two different pieces. Is this true? How could this be proved?

This is not the case for larger boards or larger pieces (more than 5 tiles). Of course, the standard 6x10 board using 12 Pentomino pieces is also a counter example when using more than two pieces. Small counter examples:

Three 5-tile Pentomino pieces (V, P and L pieces) on a 3x5 grid:
vvvpp
vLppp
vLLLL

The 5-tile pieces P, T and F on an oval-shaped point-symmetric grid.
 ppTF
pppTFFF
  TTTF

Two 8-tile pieces on a 4x4 grid:
####
#OOO
#OOO
##OO

Let's see what happens after you rotate the partition around the board's center. The region in which one part maps onto the other part is point symmetric around the board's center. Therefore, the region in which one part is mapped onto the same part is:

also point symmetric with the same center
itself partitioned into two point symmetric regions with the same center and
those two regions have the same area

The smallest non-empty such region has an area of 4. There are three possible configurations (I tetromino, S/Z tetromino, O tetromino). To connect the outer partition of the I tetromino or the S/Z tetromino into a single polyomino you need four extra tiles. For the O tetromino you need five extra, and furthemore you can't connect both regions at once.

Therefore, there is no partition of a 10-tile point symmetric board into a pair of incongruent pentominoes, and only two partitions of 12-tile point symmetric boards into a pair of incongruent hexominoes, up to symmetry:

I:   S/Z:
@@@@ @@@.
.@@. @...
.... @@..