Null Characters and Splitting the String in the Pumping Lemma So I'm really struggling with the pumping lemma.  I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question.  Here is an example, take the problem prove that $L = \{w | w$ contains more $0$'s than $1$'s over the language $\{0,1\} \}$ is not regular via the pumping lemma.

So I choose the string $01^{p}0^{p}$.  Since this is a regular language pumping lemma problem I know that:

for each $i > 0, xy^{i}z \in A$,
$|y^{i}| > 0$, and
$|xy| < p$

I am little uncertain about other possibilites though, such as if $x$, or $z$ can be null (obviously $y$ can't by condition 2).  I assume that this isn't possible since I don't think the preceding or trailing whitespace is considered part of the string, but I'm not sure.  Is it possible for $x$ or $z$ to be null?

Yes, it is possible for $x$ or $z$ to be 'null', if by 'null' you mean the empty string. The empty string, $\epsilon$, is the string of length zero.

If the loop in the automaton (which is ultimately what the pumping lemma refers to) starts at the initial state and the initial state is also an accepting state, then strings of the form $y^i$ will be accepted, where $y$ is some string that will take you around the loop.

Whitespace plays no role in this theorem. Formal languages are defined over a given alphabet, in your case $\{0,1\}$. This is the only alphabet relevant for the question.  There is no preceding or trailing whitespace when talking about the pumping lemma. Spaces, tabs, return characters play absolutely no role.


lexicographic depth-first search complexity class It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be P-complete. However, I want to talk about complexity of DFS, not it's decision problem. What complexity class should I say DFS belongs to?

The formal name for a problem where you want to actually produce the solution as the output (not just say yes or no to whether one exists) is a Function Problem if every input has an associated output, or a Search Problem if some inputs might not have any solution (of course a function problem is just a special case of a search problem).

In this case, every graph has a lexicographic depth first ordering, so for any graph there is some output that can be produced, and you have a function problem. The class of function problems that can be computed in deterministic polynomial time is (cunningly) called FP.

Going out on a limb (with regards to my knowledge, someone else might be able to confirm this), I suspect that the obvious relationship1 between P and FP holds for complete problems too, so your problem should also be FP-complete.

Note that this relationship normally relies on Turing reductions, but seeing as P=co-P there shouldn't be too much of a problem here.


Understanding of SPACE in non deterministic Turing Machines Let's consider the following situation.
We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$.
I am trying to solve some problem and I am going to:

Generate every word using non-deterministic Turing Machine. And, for every generated word make a computation $C$. that uses only constant space and linear time. So, it seems that we have to remember (for a moment) generated word. I mean the situation that we have to generate word $w$ and then make a computation $C$ on $w$.

The scheme of Turing machine looks like:

The question is: Is my Turing machine NPSPACE? I have a problem with thinking about space complexity when it comes to nondterministic TM.

A nondeterministic Turing machine is a Turing machine that has a "guessing" mechanism. It accepts an input if there is a sequences of guesses that leads it to an accepting state. It rejects an input if all guesses lead it to a rejecting state.

The time complexity and space complexity of the Turing machine are defined in exactly the same way as for deterministic Turing machines:

The time complexity on inputs of size $n$ is the maximum number of steps that the machine executes before halting over all inputs of size $n$ and all guesses.
The space complexity on inputs of size $n$ is the maximum number of tape cells that the machine uses over all inputs of size $n$ and all guesses.

If your machine always uses only a polynomial amount of space, then it is is NPSPACE. Note that NPSPACE=PSPACE, a consequence of Savitch's theorem, and so you can convert it to a deterministic machine using polynomial space (the amount of space used could increase).


Sandwiching Languages I am studying for my algorithms final and came across the following problem:

Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are undecidable.

I am having trouble coming up with an example of three such languages. My first thought was to use a form of the halting problem for both $L_1$ and $L_3$ since that is pretty much the only undecidable language I know and am familiar with. I was thinking of perhaps coming up with something of the form
\begin{align*}
L_1 &= \{M \mid \text{$M$ is a Turing machine that starts with 00 and halts}\}\\
L_2 &= \{M \mid \text{$M$ is a Turing machine that starts with a 00}\}\\
L_3 &= ?
\end{align*}
but this doesn't seem to be working.  Any ideas are appreciated!

Hint: Your approach can be completed and you need to change only one word in the description of $L_1$ to get a description for $L_3$ that works.


Streaming digit-to-digit conversion from decimal to hexadecimal I am looking for a streaming algorithm for converting a decimal number to a hexadecimal number.  I am assuming the input is a string represention of a decimal number (i.e., each character is a decimal digit) in digit-reversed order, and I'd like the output to be a string represention of a hexadecimal number (i.e., each character is a hex digit) in digit-reversed order.

By streaming, I mean that I'd like the algorithm to start producing hexadecimal digits without having to look at the entire decimal-string input first (i.e. up to some fixed number of digits of input can be looked at before producing digits of output); and ideally with only a constant amount of memory.

Is there a way to do this?

I know one can convert from hexadecimal to binary in a streaming way.  For single-digit numbers, we can use the following table:

hex -> bin
0 -> 0000
1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000
9 -> 1001
a -> 1010
b -> 1011
c -> 1100
d -> 1101
e -> 1110
f -> 1111

For multiple-digit numbers, we can do the same by applying the mapping above to each hexadecimal digit individually.

1234 -> 1, 2, 3, 4 -> 0001, 0010, 0011, 0100 -> 0001001000110100

Is there a way to do something like this, converting from decimal to hexadecimal?

I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to fairly-low-order bits:

10011000100101101000000
10110111000110110000000

It doesn't change the very lowest bits: Since $10 = 5\times 2$, the digit in position $k$ in a decimal number is a multiple of $10^{k-1} = (5\times 2)^{k-1} = 5^{k-1}2^{k-1}$, so changing it will never change the lowest $k-1$ bits of the binary representation. But it can change the $k$-th bit, and bits in positions up to $\log_2(9\times 10^{k-1}) = (\log_2 10)(k-1) + \log_2 9 \approx 3.322(k-1) + 3.170$. This is true for any $k$, so the range of affected digits grows indefinitely as $k$ increases.

If you were, say, trying to convert between base 4 and base 8, you could group each block of 3 base-4 digits into a base-64 "superdigit", which you could then convert back down to 2 base-8 digits since 8^2 = 64.

But there is no "right" superdigit base for the bases 10 and 2, since 10 contains 5 as a factor and 2 does not: every positive integer power of 10 contains 5 as a prime factor, and no positive integer power of 2 does, so by the uniqueness of prime factorisations there is no integer that is a power of both 2 and 10.


What would an exponential reduction from an NP-complete problem to P signify? Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what would be it's implications?

Based on Yuval's answer, I wanted to throw this scenario into the place also.

If we have a problem in P which we can reduce in polynomial time to an NP-complete problem for e.g vertex cover, what happens then?

There would be no implications, and indeed I will now exhibit just such a reduction. The reduction takes an instance of vertex cover, finds the optimal value (in exponential time), and then reduces it to the language $\{0\} \in P$ (the language consisting of the single string $0$), by outputting $0$ if there is a vertex cover below the required threshold, $1$ otherwise.


If A is NL-complete then complement of A is also NL-complete? We know that coNL = NL. But, is this also true?

  If A is NL-complete then complement of A is also NL-complete?

I don't see a reason for that it could be true.

Start with the definition of $coNL$.
$$coNL = \{A\mid \overline{A} \in NL\}$$
Since $NL=coNL$, every $coNL$-complete language is $NL$-complete as well.
Let $A$ be a $NL$-complete problem. Then
$$\forall B \in NL,B \leq_L A$$
or equivalently
$$x \in B \Longleftrightarrow f(x) \in A, \text{  where } f \text{is logspace computable}$$
$$x \notin B \Longleftrightarrow f(x) \notin A, \text{  where } f \text{is logspace computable}$$
$$x \in \overline{B} \Longleftrightarrow f(x) \in \overline{A}, \text{  where } f \text{is logspace computable}$$

and so $$\forall \overline{B} \in coNL,\overline{B} \leq_L \overline{A}$$
This shows that $\overline{A} $ is $coNL$-complete and hence $NL$-complete (since $coNL=NL)$.


What does $\{$ a set $\}^{+}$ mean in the context of languages? I came across this notation and I don't know the meaning of it, or if it's a typo:  $\{$ some set $\}^{+}$

What does the + mean, i.e., the plus operator applied to a set?

This is the Kleene plus. It stands for
$$ L^+ = \bigcup_{i \geq 1} L^i. $$
Here $L^i$ is the set of concatenations of $i$ words from $L$.
In words, $L^+$ consists of all concatenations of one or more words from $L$. A related operator is the Kleene star
$$ L^* = \bigcup_{i \geq 0} L^i, $$
which also allows the empty string ($L^0$).

For example, if $L = \{a\}$ then $L^+ = \{a,aa,aaa,aaaa,\ldots\}$ while $L^* = \{\epsilon,a,aa,aaa,aaaa,\ldots\}$. If $L = \{a,b\}$ then $L^+ = \{a,b,aa,ab,ba,bb,aaa,\ldots\}$. If $L = \{aa,b\}$ then $L^+ = \{aa,b,aaaa,aab,baa,bb,aaaaaa,\ldots\}$.


Can one insert non-unique elements into an AVL tree? Is it possible to insert a sequence of non-unique elements into an AVL tree?

For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree?

Is it:

        3
      /   \
     3     3

A BST (from which the AVL descends) with duplicate keys can have its rotation make nodes with the same key be on both sides of the parent node, in which case, some ambiguity might result. However, you could make your life a whole lot easier and have each node contain a key and the number of times that key had been inserted into the tree, to therefore keep track of successive inserts of successive keys and disambiguate its structure.

You would still insert a node (first by searching for the expected placement for the node) with respect to its key, initialize its count to 0, and towards the end of completing the insert increment that count).


Linear programming, Checking a constraint based on condition I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like:

if (Y==1)
      then check the constraint
else
      Don't care about the constraint

How to do it.

If $X$ and $Y$ are zero-or-one (binary) integer variables, then this is encoded as

$$X \ge Y.$$

Why does this work?  If $Y=1$, then this enforces the constraint $X \ge Y$, as you wanted.  If $Y=0$, this enforces the constraint $X \ge 0$, i.e., it doesn't impose any rstrictions on $X$, which is also as you wanted.

In general, conditional constraints can be handled using the techniques found on page 7 of AIMMS Modeling Guide - Integer Programming Tricks, which is a helpful tutorial on how to encode constraints in integer programming.  Thanks to @adrianN for pointing to that resource.

You can also take a look at https://cs.stackexchange.com/a/12118/755 and at Formulating Integer Linear Programs: A Rogues' Gallery for other techniques and practice problems.


Why does the Count-Min Sketch require pairwise independent hash functions? The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream.  Intuitively, it works by picking a variety of hash functions, hashing each element with those hash functions, and incrementing the frequencies of various slots in various tables.  To estimate the frequency of an element, the Count-Min sketch applies the hash functions to those elements and takes the minimum value out of all the slots that are hashed to.

The original paper on the Count-Min Sketch mentions that the data structure requires pairwise independent hash functions in order to get the necessary guarantees on its expected performance.  However, looking over the structure, I don't see why pairwise independence is necessary.  Intuitively, I would think that all that would be required would be that the hash function be a universal hash function, since universal hash functions are hash functions with low probabilities of collisions.  The analysis of the collision probabilities in the Count-Min Sketch looks remarkably similar to the analysis of collision probabilities in a chained hash table (which only requires a family of universal hash functions, not pairwise independent hash functions), and I can't spot the difference in the analyses.

Why is it necessary for the hash functions in the Count-Min Sketch to be pairwise independent?

Thanks!

You are right: universal hashing suffices. Pairwise independence, while stronger, is the usual method to construct a universal hash family. Also pairwise independence is contrasted in the paper with the 4-wise independence required by previous methods, such as the AMS sketch.


Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$? In CLRS book, in the road cutting example there is a recursion formula

$$
    1+\sum_{j=0}^{n-1}T(j)
$$
and it can be proved that the sum is
$$
    2^n
$$

by simple induction. In 3-rd edition it is a formula 15.3 on a page 364.

As I can understand from the recursion-tree aproach, the recursion tree which can be built for the said problem is
$$
    1->(n-1)->(n-2)|each.node->(n-3)|each.node->...
$$

and so on, which can be summed as
$$
    \sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]
$$

How can I come up with the suggestion of $2^n$ from this recursion tree (or why this tree is wrong and what can be the right approach to suggesting $2^n$ running time)?

Minor nit: your first displayed expression should be
$$
T(n) = \begin{cases}
  1 & \text{if $n=0$,}\\
  1 + \sum_{j=0}^{n-1}T(j) & \text{otherwise}
\end{cases}
$$
You can indeed solve this by looking at the recurrence tree, but you don't wind up with your sum of products expression (try it for $n=4$ to see that). For this problem there's an easier way, though:

Hint: What is $T(n+1)-T(n)$?

You can take a look at our reference question, on recurrence relations, as well.


Are every problems in EXP karp reducible to any EXP-Complete? According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$ into $L$ in polynomial time. I believe this definition is fine but I have some observation that are confusing me. I construct a language $L''$ in $EXP$ such that $L''$ can not be convert into $L$ with polynomial time reductions and $L''$ is in $EXP$ with an algorithm M in this way:

let $f_i$ be the iteration of all reductions.

1) $input(i,x)$

2) run $f_i(i,x)$ in time at most $2^n$ if the computation time is greater than $n^{\log  n}$ then accept.

3)else accept $(i,x)$ iff $f_i(i,x) \not \in L$.

Obviously $Language(M) \in EXP$ so there exists a polynomial time reduction from $Language(M)$ to $L$ but this makes a contradiction because M prevents the reductions of less than $n^{\log n}$  time to $L$ and it is because of line 3 of algorithm.suppose $f_j$ is polynomial reduction, the membership of $(i,x)$ in $L(M)$ is the opposite of the member ship of $f_j(j,x)$ so $f_j$ is not a reduction from L(M) to L by the line 3 of algorithm.

My question is: where is my mistake?

Are every problems in EXP karp reducible to any EXP-Complete?

Yes. That's the definition of $\mathrm{EXP}$-completeness.

  My question is: where is my mistake?

Your mistake is in believing that $L''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you mean by "$M$ prevents the reductions" – you're trying to reduce from $L(M)$ to $L$, not from $L$ to $L(M)$.

On the other hand, $L''$ is not $\mathrm{EXP}$-complete, by the time hierarchy theorem. Any language reducible to $L''$ must be in time $O(2^{(\log (n^c))^2})$ for some $c$, but this is just time $O(2^{(c\log n)^2})=O(2^{(\log n)^2})$.


How to convert process / cpu core based upon MIPS? I want to know how can i find number of cpu cores/processor supported given i have the MIPS value?

For e.g I want to know the number of matching cores/processor to process speed of 18 triilion instructions / sec.

For a modern CPU there is no exact MIPS rating since it depends on the specific instruction stream, power saving mode, and other factors. As a reference number you may look at the BogoMIPS rating that is calculated by the Linux kernel.

A desktop CPU core at 3GHz can process about 2 instructions per clock cycle on average resulting in a rating close to 6000 MIPS (or 6 billion instructions per second), therefore 18 trillion instructions would require about 3000 cores.


Reception of numerical infinities A group of computer scientists associated with numerical analyst Yaroslav Sergeyev have published numerous publications recently on a scheme proposed by Sergeyev that uses terms like Infinity Computer, numerical infinitesimal and numerical infinity, claiming that the approach facilitates the solution of many problems.

The mathematicians (including logicians) have been for the most part sceptical but there are a few exceptions, such as Elemer Rosinger and Gabriele Lolli. How have these ideas been received by computer science professionals?

Note. On 19 dec '17 a retraction page was created for this issue.

So the paper's

"Numerical infinities and infinitesimals: Methodology, applications, and repercussions on two Hilbert problems", Yaroslav D. Sergeyev (2017),

and it's basically a discussion on the author's "grossone" approach that they've been pushing for quite a while now (at least since 2004).

The tl;dr on it is that they're proposing a slightly abstracted data type, kinda like how complex number data types generalize real number data types, except this one's focused on infinities instead of imaginaries.

The author seems to want CPU's to include support for grossone's in their arithmetic logic units (ALU's), e.g. as specified in their patent.  The author's website and publications seem to focus on applied use in mathematical optimization; they seem to justify their work in terms of theoretical work as an afterthought.

Some of the harshest criticism seems to come from folks who're knocking it as-though the author were trying to report their work as some new theory, arguing that it's weaker and less sophisticated than prior work, e.g. hyperreal numbers.  The weird part about this is that, as far as I can tell, that's what the author wanted to do; they're trying to make an abstract data type to replace floating-point data types for common calculation units, not solve the mysteries of the universe.

In general, I'd expect folks who get the author's intent to receive it with a bit of a yawn.  The arguments for modifying mainstream ALU's don't seem too compelling, and at-current there's likely not much demand for custom CPU's that implement it.

The author appears to have implemented grossone's at a software level, kinda like how computers do complex-number operations.  Since they're using a non-primitive numeric data type, their calculations'll be slower for it; but if they distribute the library and can demonstrate how it's worth the performance hit in some useful applications, some folks might start using it in those cases.

In short, it looks like the controversial proposal's for an abstract data type that includes infinities for use in common calculations.  It looks like applied work rather than theoretical, a misunderstanding which seems to have ruffled some feathers; however, at the end of the day if the authors can show that it's useful in real-life coding scenarios and make it available, then folks might use it.


Does $\Sigma^* \cdot a^nb^n=\Sigma^*$ Is it true to say that $\Sigma^* \cdot$ {$a^nb^n: n>=0$}  =  $\Sigma^*$

Becuase if we take $\Sigma^*$ and concatenate it to {$a^nb^n: n>=0$} we don't get any "new" words than those we had in $\Sigma^*$ in the first place.

Yes if $\Sigma \supseteq \{a, b\}$. To show the equality, let's show one is a subset of the other, and vice versa.

$\Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \subseteq \Sigma^\ast$ holds, because for any word $w \in \Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\}$, we know $w = u a^n b^n$ for $u \in \Sigma^\ast$, therefore $w \in \Sigma^\ast$ since $\Sigma \supseteq \{a, b\}$.
$\Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \supseteq \Sigma^\ast$ holds, because

$$
  \Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \supseteq \Sigma^\ast \cdot \{ a^0 b^0 \} = \Sigma^\ast \cdot \{ \varepsilon \} = \Sigma^\ast
$$

where $\varepsilon$ is the empty word.


Why does (y  0 ^ y < 10)? My lecturer recently released solutions to an assignment. One of the questions was to determine the weakest precondition of:

{y < 10} if (x > 0 OR y < 10) -> y:=10 fi {true}

According to the provided solution, the weakest precondition of the selection command

(x > 0 OR y < 10) -> y:=10

is

(x > 0 OR y < 10)

I understand how the weakest predicate was arrived at, but why does the solution then state that the total assertion is true because

 (y < 10) IMPLIES EVERYWHERE (x > 0 OR y < 10)

Isn't y < 10 weaker than (x > 0 OR y < 10)? Therefore, there are potential precondition states where y < 10 but x !> 0. Since the program doesn't have guards for such a condition, it then aborts.

I'm an idiot.

Of course (y < 10) implies (x > 0 OR y < 10). I was somehow mistaking OR for AND. I'm dumb.


Is the problem of evaluating a boolean formula on a given assignment P-complete? I know that the CIRCUIT VALUE problem is P-complete.
In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the given input.

I wish to know if the problem of evaluating a Boolean formula on a given assignment is also P-complete. From one hand, it seems that a Boolean circuit and a Boolean formula are very similar objects. Also, the proof of that CIRCUIT VALUE is P-complete results from the Cook-Levin problem, the same theorem that actually shows that SAT is NP-Complete, so I don't see a reason why this problem won't be P-Complete.
From the other hand, it seems pretty easy to evaluate a Boolean formula in logarithmic space, so if this problem is indeed P-complete I think it would imply L = P which is unknown.

So I think I'm missing something.. any ideas people?

In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.


Designing CFG that accepts a^n b^m (n<m<2n) Designing CFG for the following language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n\le m \le 2n \}$ is easy.

  $S \to aSb \mid aSbb \mid \lambda$

Then how about this? Language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n<m<2n \}$.

It is somewhat difficult for me. I have no idea how to exclude $n=m$ or $m=2n$.

Could you give me some hints?

Try this to remove the two cases the first time :

$$S\to aAb$$
$$A\to aCbb$$
$$C\to aCb|aCbb|\lambda$$

If you go to $A$ you cannot have $a^nb^{2n}$ and while going from $A$ to $aCbb$ you are removing the possiblity to get $a^nb^n$.


Number of Configurations of LBA(Linear Bounded Automaton) The lemma is:

  Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet.
  There are exactly $qng^n$ distinct configurations of $M$ for a tape of
  length $n$.

I want know why LBA has $qng^n$ configurations.

Following is the proof:

  A configuration of $M$ is like a snapshot in the middle of its computation. A configuration consists of the state of the control, position of the head, and contents of the tape. Here, $M$ has $q$ states. The length of its tape is $n$, so the head can be in one of $n$ positions, and $g^n$ possible strings of tape symbols appear on the tape. The product of these three quantities is the total number of different configurations of $M$ with a tape of length $n$.

If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options for the first three symbols and so on. If you are not convinced, try it with for example a $3$-symbol alphabet.

Since your tape has length $n$ there are $n$ possible head positions, so you multiply the number of strings on the tape with $n$.

Finally, there are $q$ states, so for every possible string on tape and every possible head position, we can be in either of the $q$ states, making $qng^n$ configurations of the Turing machine.


Clarification of Definition for Functional version of TSP The decision version of $TSP$ is $NPComplete$. I was reading about the functional version of $TSP$ i.e. the class $FP^{SAT}$.

It is mentioned in the original paper that TSP is complete for the class $FP^{SAT}[n^{O(1)}]$. By definition of the class, it means TSP can be solved in polynomial time by making $[..]$ calls to an $NP$ Oracle.

But I am still confused what $n$ is in case of a TSP instance?

In definitions of complexity classes, $n$ is always the input length in bits.

Often the definitions are invariant under polynomial blowup (for example, polytime and logspace), and in such cases you can also take $n$ to be other parameters of the input, the resulting class being the same. For example, if the input is an unweighted graph, you can take $n$ to be the number of vertices.


Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity? Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case?

Even in the case of a reversely sorted list, it's not like it'll have to compare each element with all the other elements. For example in [4, 3, 2, 1], 4 won't be compared with anything. 3 will only be compared with 4. 2 will be compared with 4 and 3 but not 1. And only 1 will be compared with all the other 3 items.

How is this O(n^2) and not O(nlogn)? What am I missing here?

My implementation of Insertion Sort:

const insertionSort = (arr) => {
  for (let i of arr) {
    for (let x = arr.indexOf(i) - 1; x >= 0 && arr[x] > i; x--) {
      arr[x + 1] = arr[x];
      arr[x] = i;
    }
  }

On an array of length $n$ which is reversely sorted, the first element would be compared to 0 elements, the second element to 1, the third element to 2, and so on. In total, the number of comparisons will be
$$
0 + 1 + 2 + \cdots + (n-1) = \\
\frac{1}{2} \bigl((0 + 1 + 2 + \cdots + (n-1)) + ((n-1) + \cdots + 2 + 1 + 0)\bigr) = \\
\frac{1}{2} \bigl((0 + (n-1)) + (1+(n-2)) + (2+(n-1)) + \cdots + ((n-1)+0)\bigr) = \\\
\frac{1}{2} \bigl(\underbrace{(n-1) + (n-1) + (n-1) + \cdots + (n-1)}_{\text{$n$ times}}\bigr) = \\
\frac{n(n-1)}{2}.
$$
This number scales like $n^2$.


Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP? Basic sanity check on NP-complete solutions:

Suppose there was a polynomial time solution for an NP-complete problem,
but the size of NP-complete problems that could be solved is still
relatively small (i.e. N = 32-64) due to limits in technology.

Would this show that P = NP? Or would this be more like the
pseudo-solution that the unary subset sum is in P?

If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone NP-complete) becomes a finite language when restricted to instances of constant size. All finite languages can be decided in constant time.

If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that P$\,=\,$NP. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of P and NP don't depend on that short-hand.


Coming up with a loop invariant for the partition section Quicksort? void partition(int a[], int L, int R) {
int i = L;
int pivot = a[R];
 for (int j = L; j < R; j++) {
     if (a[j] <= pivot) {
     swap(a[i], a[j]);
      i++;
     }
  }
swap(a[i], a[R]);
}

My code is above. My loop invariant is "At the beginning of the iteration, j is in the range of a[L] to a[R-1]". Is this correct? Or if it is not am I on the right track. Thank you.

You're sort of on the right track in that you're trying to relate the position of array elements to their value, but your statement makes a serious error in directly comparing the value of an index, $j$, to the value of arbitrary data, $a[L]$ and $a[R-1]$.
I think you meant to say $L\leq j\leq R$ is a loop invariant. Observe that $L\leq i\leq j$ is as well, but neither are very interesting statements.
Remember, the motivation for identifying loop invariants is so that we can use them to verify that our code does what it's supposed to. Here, implementing the partition stage of Quicksort, our goal is to rearrange the elements of $a$ such that all the data to the left of the pivot will be less than or equal to the pivot, and all the data to the right of the pivot will be greater than or equal to the pivot.
One important loop invariant is $$\text{For all indices }k \text{ with } L\leq k<i, \text{ we have } a[k]\leq\text{pivot}=a[R]$$
We can see this in your code:
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];
    //a[k]<=pivot for all k with L<=k<L=i (true since there are no such k)

     for (int j = L; j < R; j++) {
         //a[k]<=pivot for all k with L<=k<i (inductive hypothesis)

         if (a[j] <= pivot) {
             swap(a[i], a[j]);
             //we have now ensured a[i]<=pivot
             //it is an invariant that i<=j
             //so the elements a[L],...,a[i-1] are unchanged
             //thus a[k]<=pivot for all k with L<=k<i+1

             i++;
             //now a[k]<=pivot for all k with L<=k<i
         }
      }
    swap(a[i], a[R]);
    }

Another important loop invariant is $$\text{For all k such that } i\leq k< j, \text{we have } a[k]\geq\text{pivot}=a[R]$$
Again we can see this looking at your code:
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];

    //a[k]>=pivot for all k with i=L<=k<L=j (true since there are no such k)
     for (int j = L; j < R; j++) {
         //a[k]>=pivot for all k with i<=k<j (inductive hypothesis)

         if (a[j] <= pivot) {
             //it is an invariant that i<=j. now either i<j or i=j
             //if i=j, then there are no k such that i<=k<j, so assume i<j
             //then i<=i<j, and consequently a[i]>=pivot

             swap(a[i], a[j]);
             //now a[j]>=pivot and a[i]<=pivot
             //the other elements are unchanged
             //so now a[k]>=pivot for k with i+1<=k<=j

             i++;
             //now a[k]>=pivot for k with i<=k<=j

         }
      }//after incrementing j by 1, now a[k]>=pivot for k with i<=k<j

    swap(a[i], a[R]);
    }


Don't understand minimax algorithm in terms of chess I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question

black or white players comprises of several pieces, so what piece is the AI predicting moves for, as the player could move any of their 16 pieces?

all i keep seeing is that we need to write the code to look several moves ahead in which the player could potentially make, my issue is that there are multiple pieces the player could pick from so what moves exactly are we talking about and how would the AI determine which of its pieces to move based on that.

I just need a brief explanation, no source code or how to's. I've spent days trying to wrap my head around this concept.

In minimax you fully explore the game tree. So the answer to "which piece" is all of them. All possible moves for all movable pieces. And then it selects the minimum or maximum (depending on the depth) out of those options.

Obviously this isn't feasible which is why we never apply raw minimax to chess. It is always with other optimizations such as alpha-beta, and stopping after a certain depth and using a heuristic evaluation of that position instead of continuing.


How to make a Neural network understand that multiple inputs are related to the same entity? Neural networks can have multiple inputs.
But some times two or more of these inputs can often be related to a single entity.

E.g : Height and weight of a person to predict the probability of disease or price and Volume of a stock to predict it's value.

How can we make a neural network understand that two inputs are related to the same entity?
Is there any efficient (or inefficient) way of 'tagging' them together?

It is not necessary to indicate this to the neural network (and not possible).  This is not part of how neural networks are typically used -- or part of how other machine learning algorithms are used, either.

I confess I'm not clear on why you think it would make a difference, but it doesn't matter: there's no way (that I know of) to do that, and it's not something people normally do.


What is the underlying pattern/rule in this question? I can't find a concise algorithm for the following coding problem:

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.You can assume that the messages are decodable. For example, '001' is not allowed.

I've recognized that any number <=26 can be represented 2 ways. I've tried to observe what happens when I add a number like 2, which can later form another 2-digit number with the one after it (e.g. 22 - 2 combinations, 222 - 3, 2222 - 5, 22222 - 8). But I can't seem to find a robust pattern.

This was a coding interview question that was supposed to last 30min, so I'm embarrassed I can't see the latent rule.

I believe the pattern you are looking for is dynamic programming. In the case at hand, the answer for a message can be based on answers for prefixes of the message. This leads to a linear time and linear space algorithm that computes answers for all prefixes in order of increasing length.


Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming I have recently been working on an applied project where I have to solve optimization problems.

I have found that it is much easier to solve an integer linear program (ILP) as opposed to a mixed-integer linear programs (MILP), in the sense it is faster for me to find feasible solutions as well as to prove optimality.

I am wondering if there is some kind of formal result that confirms this (i.e. on the time complexity of ILP vs. MILP).

To be clear, when I am refering to an ILP I mean an optimization problem of the form

$$\begin{align} \min_{x} \quad & c^Tx \\ \text{s.t.} \quad & Ax = b \\ \; & x\in\mathbb{Z}^N\end{align}$$

where the variables are integer-valued so that $x\in\mathbb{Z}^N$ but the parameters are real valued so that $c \in \mathbb{R}^N$, $A \in \mathbb{R}^{M \times N}$, $b \in \mathbb{R}^M$. In turn, an MILP would be different in that at least one of the variables would take on a real value.

Knowing that integer programming (ILP) is NP-complete, it follows that mixed integer linear programming (MILP) is NP-complete too as MILP generalizes ILP.

My guess is that your thinking and feeling comes from insufficient testing: you don't have enough test cases with different structure, and you don't mention what algorithms you use. Even though both problems are hard, there are (even exact) algorithms that perform well on suitably structured instances. You should look at where the really hard instances are (they are not necessarily large), and try running your algorithms again.


Recurrence doesn't add up I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for some reason:

\begin{align}
T(n-2) &\leq c2^{(n-2)/2}\\
T(n) &= 2(c2^{(n-2)/2})+n\\
&\leq c2^{n/2} \quad (?)
\end{align}

But as far as I see, it can never add up, because it will always be greater than the $+n$ term and times $2$. Any help will be much appreciated.

The hints you've been given almost work. The important idea is that your guess, $T(n)≤c2^{n/2}$, while correct, doesn't behave nicely in your induction proof, as you noted. What's the problem? Clearly, it's that "$+n$" term in the recurrence, so let's try to make it work by choosing a better guess:
$$
T(n)≤c2^{n/2}−kn \quad\text{for some suitable } k
$$

With this guess, we'll have
$$\begin{align}
T(n)&=2T(n−2)+n\\
&\le 2(c2^{(n−2)/2}−k(n−2))+n\\
&=c2^{n/2}−2k(n−2)+n\\
&=c2^{n/2}−2kn+4k+n
\end{align}$$
and if we can find a suitable $k$ to make this less than or equal to $c2^{n/2}−kn$ we'll be done. In other words, we need to find $k$ such that
$$
−2kn+4k+n≤kn
$$
It's not hard to see that this will happen if
$$
k\ge\frac{n}{n−4}
$$
and this will be satisfied when $k=5$ for any integer $n>4$. Now go back to the inductive proof and recast it for the guess $T(n)\le c2^{n/2}−5n$. You'll find that everything works nicely. Finally, observe that $c2^{n/2}−5n=O(2^{n/2})$ and you'll be done.

This is explained in a bit more detail in this answer to a similar question.


Which one of these two sequences is random, and which one is not? We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$:

$$
B_k(\alpha_1\ldots\alpha_k) =
\begin{cases}
1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1
\\
0 \text{ otherwise}
\end{cases}
$$

Then we define two sequences:

$$B_3(\alpha_1\alpha_2\alpha_3)B_3(\alpha_4\alpha_5\alpha_6)B_3(\alpha_7\alpha_8\alpha_9)\ldots$$
$$B_4(\alpha_1\alpha_2\alpha_3\alpha_4)B_4(\alpha_5\alpha_6\alpha_7\alpha_8)B_4(\alpha_9\alpha_{10}\alpha_{11}\alpha_{12})\ldots$$

Which one of these two sequences is (algorithmically) random, and why? I should note that apparently there is an obvious measure-theoretic fact that gives away which one is not random.

The second sequence is not random.  Let $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ be random, iid Bernoulli $1/2$ random variables.  Let $\beta = B_4(\alpha_1 \alpha_2 \alpha_3 \alpha_4)$.

What is the distribution of the random variable $\beta$?  Answer: $\beta=1$ if at least two of the $\alpha$'s are $1$, so $\Pr[\beta=1] = 11/16$.

In other words, $\beta$ is biased towards $1$.  It follows that the second sequence is not algorithmically random: it is a set of independent Bernoulli random variables with $p=11/16$, i.e., the outcome of an infinite sequence of tosses of a biased coin.


Are all countable partial functions computable? I know all computable partial functions are countable. Wondering if it is the the other way around as well.

You must be mistaken about a definition.  It is not that any single computable partial function is countable.  Rather, the set of all computable partial functions is a countable set.  (There isn't any such thing as a countable partial function.)


Calibration and overlay of RGBD with a thermal camera I have a thermal camera that I would  like to overlay automatically to the output of a RGBD camera (e.g., Kinect).

I can retrieve the intrinsic parameters of the thermal camera by using a special board I built, that allows the thermal camera to give as output a series of points similar to the ones obtained with a visible sensor and a typical calibration chessboard.

Once the intrinsic parameters of the thermal camera are obtained, what would the next steps be to align all the cameras?  It's important to take into account that the two cameras deeply differ from each other, because they operate in different wavelengths.

I suggest that you obtain both the intrinsic and extrinsic parameters for both cameras.  The extrinsic parameters will include information like the offset/distance between the two cameras and the relationship between their two headings, which is needed to relate their images.  (If only the relative position and orientation/heading of the two cameras is known, that will be enough.)

Once you have these parameters, you'll be able to map each pixel in the RGBD image to its corresponding pixel in the thermal image.  This will let you align those two images.  Then, depending upon the specific setup, you might need to do fine-grained image stabilization (e.g., if they are not on tripods).

It's not clear why the different wavelengths would have any impact on alignment of the two images.

See also https://en.wikipedia.org/wiki/Camera_resectioning.


Can every DCFG be converted to DGNF? I know you can convert every context-free grammar into Greibach normal form grammar.

But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?

If by deterministic GNF you mean as a deterministic grammar that is also GNF then yes, here is the paper. Normal forms of deterministic grammars

  It is shown that every strict deterministic language may be given a
  strict deterministic grammar which is also in Greibach normal form.

EDIT
Here is a paper outlining the technique to do the conversion Strict deterministic grammars and Greibach normal form


Weakest reduction for P-completeness It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-one $C$-reductions.

  What is the weakest many-one reduction (computable in class $C$) for which the class of P-complete problems remains unchanged?

Note that $C$ is contained in $P$.

There is first-order reductions.

See Immerman's book, Chapter 3, Theorem 3.26 which states that $\mathrm{REACH}_a$ is complete for $\mathrm{P}$ via first-order reductions.

Also, see my question, for related information on $\mathrm{NP}$.


How to solve for the precondition give a postcondtion that must satisfy two conditions I tried solving past exam question but there is this one that I haven't been able to solve.

The question states that a suitable precondition should be found for the statement.

$$
 a= i +2; i++\{(a = 7)\land(i = 5)\}
$$
Here's my solution and where I got stuck:

$$
wp(a= i +2; i++,(a = 7 \land i = 5) \\
=wp(a= i +2, wp(i=i+1,a = 7\land i = 5)
$$

I've tried solving it intuitively and I arrive at the conclusion that no such value for ii should exist.

I haven't been able to find a rule to combine the two predicates of the post-condition.

Please I would like to know when solving similar questions can I change the ^ to an algebra symbol or should I take the relevant condition and find the weakest precondition with that.

The rules for $wp$ are straightforward for non-loops:

$$wp(c_1 ; c_2, V) = wp(c_1, wp(c_2, V))$$
$$wp(x := e ; V) = V\left[x \mapsto e\right]$$

Plugging in the original values, you need to compute

$$
wp(a := i + 2; i := i + 1, (a = 7) \wedge (i = 5))
$$

The first rule applies here, giving

$$
wp(a := i + 2, wp(i := i + 1, (a = 7) \wedge (i = 5)))
$$

In the second $wp$ expression, the second rule applies, giving

$$
wp(a := i + 2, (a = 7) \wedge (i + 1 = 5))
$$

Now the second rule applies again to the remaining $wp$:

$$
((i + 2) = 7) \wedge (i + 1 = 5)
$$

Now, you just need to know that the above is always false, regardless of the value of $i$. There are various automatic approaches to do this (since these are linear equations, you could use the simplex method). In this case, since they're so simple, you could just normalize your equations into $i = constant$:

$$(i = 7 - 2) \wedge (i = 5 - 1)$$

Knowing $7 - 2$ and $5 -1$ are constant expressions, you can get
$$i = 5 \wedge i = 4$$
which would imply
$$4 = 5$$
which is always false, so the original statement must be always false.


Are there established complexity classes with real numbers? A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:

  I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one reduction), so $P$ is NP-hard.

My answer was basically:

  Since $P$ has instances with values from $\mathbb{R}$, it's trivially not Turing-computable so you can skip the reduction.

While formally true, I don't think this approach is insightful: we'd certainly like to be able to capture the "inherent complexity" of a real-valued decision (or optimisation) problem, ignoring the limitations we face in dealing with real numbers; investigating these issues is for another day.

It is, of course, not always as easy as saying, "the discrete version of Subset Sum is NP-complete, so the continuous version is 'NP-hard' as well". In this case, the reduction is easy but there are famous cases of the continuous version being easier, e.g. linear vs. integer programming.

It occurred to me that the RAM model naturally extends to real numbers; let every register store a real number and extend the basic operations accordingly. The uniform cost model still makes sense -- as much as in the discrete case, anyway -- while the logarithmic one does not.

So, my question boils down to: are there established notions of complexity of real-valued problems? How do they relate to the "standard" discrete classes?

Google searches yield some results, e.g. this, but I have no way of telling what is established and/or useful and what is not.

The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes.

Some interesting problems in this domain are the classes $P_R$, $NP_R$, and of course the question of whether $P_R$ = $NP_R$. By $P_R$ we mean the problem is polynomially decidable, $NP_R$ is the problem is polynomially verifiable. There are hardness/completeness questions about the class $NP_R$. An example of an $NP_R$ complete problem is the the problem of $QPS$, Quadratic Polynomial System, where the input is real polynomials in $m$ variables, and $p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$ of degree at most 2, and each polynomial has at most 3 variables. The question whether there is a common real solution  $R^n$, such that $p_1(a), p_2(a), ... p_n(a) = 0$. This is an $NP_R$ complete problem.

But more interestingly there has been some work on the relationship between $PCP$,(Probalistically Checkable Proofs), over the Reals, ie the class $PCP_R$, and how it relates to the algebraic computation models. The BSS model pans to all of $NP$ over reals. This is standard in literature, and what we know today is that $NP_R$ has "transparent long proofs", and "transparent short proofs". By "transparent long proofs" the following is implied: $NP_R$ is contained in $PCP_R(poly, O(1))$. There is also an extension which says, the the  "Almost (approximated) Short Version" is true too. Can we stabilize the proof and detect faults by inspecting considerably less many (real) components than $n$? This leads to questions about existence of zeros for (system of) univariate polynomials given by straight line program. Also, by "transparent long proofs" we mean

"transparent" - Only, $O(1)$ to be read,
long - superpolynomial number of real components.

The proof is tied to $3SAT$, and sure one way to look at real valued problems is how it might be related to Subset Sum - even approximation algorithms for the real valued problems would be interesting -as for optimization - Linear Programming we know is in the class $FP$,but yes it would be interesting to see how approximatability might impact the completeness/ hardness for the case of $NP_R$ problems. Also, another question would be the $NP_R$ $=$ $co\text{-}NP_R$?

While thinking of the class $NP_R$, there are counting classes also defined to allow for reasoning about polynomial arithmetic. While $\#P$ is the class of functions $f$ defined over $\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$ for which there exists a polynomial time Turing machine $M$ and a polynomial $p$ with the property that $\forall n $$\in$$ \mathbb{N}$, and $x$$\in$$\{0,1\}^{n}$, $f(x)$ counts the number of strings $y \in$$\{0,1\}^{p(n)}$that the Turing Machine $M$ accepts $\{x,y\}$. For reals we  extend this idea there are additive BSS machines - BSS machines that do only addition, and multiplications (no divisions, no subtractions). With additive BSS machines(nodes in computation only allow addition, and multiplication) the model for $\# P$ becomes one in which the count is over the vectors that the additive BSS  machines accepts. So, the counting class is $\#P_{add}$ this class is useful in the study of Betti numbers, and also the Euler characteristic.


Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not I am trying to show whether this language is regular or not:

$$L = \{0^m1^n  \mid m \neq n\}$$

Since I cannot create or think of an automaton that recognizes $L$, I am suspecting that $L$ is not regular. From the book I am using, it seems I can use the pumping lemma, I have done this:

Let $p$ be the pumping lemma constant, and let $w=0^p1^{p+1}$

In this case
$$|w|=2p + 1\geq p$$

We can divide $w$ into $xyz$, where $x=0^{p-1}$, $y=0$, $z=^{p+1}$, then $|y|\geq 1$

If L was regular, then $\forall k \geq 0, xy^kz \in L$. Let choose $k=2$, then:

$$xyyz=0^{p-1}001^{p+1}=0^{p+1}1^{p+1}$$

Here is where I am stuck, how do I prove that $L$ is not regular?

Another question, pumping lemma applies only to infinite languages?

You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular (where the overbar represents complement), and since regular languages are closed under intersection, $\overline{L}\cap 0^*1^*$ would be regular (where the regular expression denotes the language $0^*1^*=\{0^n1^m\mid n,m\ge 0\}$), but $\overline{L}\cap0^*1^*=\{0^n1^n\mid n\ge 0\}$, which you likely know is not regular, establishing the contradiction we needed. Thus your language isn't regular.

In answer to your other question, the PL generally applies only to infinite languages since you don't know what the PL integer $p$ is, so absent other information, you need an infinite language to be sure that there is some string of length $\ge p$ in the language, regardless of how large $p$ is.


Let $G = (V,E)$ be an infinite digraph: $E \subset \mathbb{N}\times \mathbb{N}$ is decidable. Does it imply that $\delta (i,j)$ is a total function? Problem:

  Let $G = (V,E)$ be an infinite digraph, such that $V = \mathbb{N}$, and $E \subset \mathbb{N}\times \mathbb{N}$ is decidable set. Does it imply
  that $\delta (i,j)$ is a total function?

  *(where $\delta (i,j)$ is the shortest path function between vertex
  $i$ and $j$).

I'm having a hard time trying to understand the problem, so any help would be appreciate.

Well, this is what I know (hopefully I'm not misunderstanding anything here):

A language (or set) $L$ is decidable if $\exists$ and algorithm $A$, such that if $v \in L$, then $A(v) = \text{Accept}$ and halts and if $v\not\in L$, then $A(v) = \text{Reject}$ and halts.

A function $f$ is total if $\exists$ and algorithm $B$ that computes it $\forall v\in \mathrm{Dom}(f)$ and always halts.

My attempt:

Suppose $\delta (i,j)$ is a total function and let algorithm $B$ be the Bellman-Ford algorithm ($BFA$).

The relaxation step in $BFA$ is given by

// Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

Because $|V| = \infty$ we have that the algorithm never halts, since size(vertices) - 1 $= |V| -1 = \infty$. This implies that $BFA$ doesn't compute $\delta (i,j) \implies \delta (i,j)$ is not a total function (So, to my understanding it would be only a partial function, since $\exists$ some vertices $u,\ v$ for which the function $\delta (u,v)$ is undefined).

Although to me at first glance it makes kind of sense, I guess I'm wrong, mainly because I didn't consider the fact that $E$ is a decidable set.

This function is not necessarily total, even when the set of edges is decidable. Note that you haven't proved it, but simply showed why we can't directly use some classic algorithm for finite graphs, though perhaps some smarter algorithm exists?

Imagine $G$ is a "universal configuration graph". To explain what i mean, lets first discuss what is the configuration graph of a Turing machine $M$. Given a Turing machine $M$, let $G_{M}$ denote the graph whose vertices are configurations of the form $C=(q,s_1,s_2)$ where $q$ is the machine state, and $s_1,s_2$ are the strings to the right and left of the read/write head correspondingly (the first symbol of $s_2$ is the current symbol under examination). $(C_1,C_2)\in E$ if you can go from $C_1$ to $C_2$ in a single step. The number of vertices in $G_M$ is countable (since we go over all possible contents of the tape).

Now I want to define $G$ as $\bigcup\limits_{M} G_{M}$. The graph $G$ is the disjoint union of all possible configuration graphs (so we go over all Turing machines, note that the number of vertices remains countable). To identify each vertex (configuration) in $G$ to the graph $G_{M}$ it's belonging to, we can add the encoding of the machine to the description of each vertex. The set of edges of $G$ is clearly decidable, since given two vertices
$v_1=\left(\langle M\rangle , C_1\right)$ and $v_2=\left(\langle M'\rangle , C_2\right)$, we check if $\langle M\rangle=\langle M' \rangle$, and if so, we check if $M$'s transition function allows us to move from $C_1$ to $C_2$ in a single step.

If reachability in $G$ is decidable, then you can decide the halting problem. Given a Turing machine $M$ and input $x$, check if the accepting configuration of $M$ is reachable from the initial configuration of $M$ on input $x$ (for simplicity, you can assume there is a unique accepting configuration).


What is the difference between variables and pointers? Whist reading an article outlining differences in OO and Functional programming I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked up pointers to refresh my memory.

Pointers are variables that contain a reference to a memory address. They can be considered to point to the data that is contained in that memory address if such data exists. Or, as in the case in the article, they might indicate the entry point to a section of code and can be used to call that code.

Why is this different from a variable? Variables are symbolic names for memory addresses and compilers will replace the name with the actual address. This means that variables contain references to memory locations and can be considered to point to the data at that address if such data exists.

If the difference is in behaviour (maybe a pointer cannot be reassigned at runtime, or can only be assigned a symbolic variable name, not any other value) doesn't that mean it is just a variable of a particular type, the pointer type? In just the same way a variable declared to be of type integer is restricted by the compile in what it can be used for.

What am I missing here?

Your question is interesting in several ways, as it requires careful
distinctions for several issues. But your vision seems to me to be
essentially correct. I did not read your reference before writing most
of this answer to avoid biasing my answer.

First, your statement Variables are symbolic names for memory
addresses, it is almost correct, but confuses the concept and its
usual implementation. A variable is actually just a container that can
contain a value that can be changed. Usually, this container is
implemented on a computer as a bock of memory space, characterized by
and address and a size since variables may contain object that
require representations with more or less information.

But I will consider mostly a more abstract point of view of the
semantics of languages, independently of implementation techniques.

So variables are just containers from an abstract point of view. Such
a container need not have a name. However, languages often have
variables that are named by associating to it an identifier, so that
uses of the variable can be expressed by the identifier. A variable
can actually have several identifiers through various aliasing
mechanism. A variable can also be a subpart of a larger variable: an
example is a cell of an array variable, which can be named by
specifying the array variable and the index of the cell, but could as
well be also associated with identifiers through aliasing.

I am deliberately using the word container that is somewhat neutral, to avoid invoking other words that may be semantically loaded technically. It is actually close to the concept of reference described in wilipedia, which is often confused with a memory address. The word pointer itself is often understood as a memory address, but I do not think that is meaningful when considering most high-level languages, and probably inappropriate in the discussion paper you refer to (though addresses can be used), as it is inappropriately referring to a specific implementation. However, it is appropriate for a language like C, which is supposed to be much closer to
implementation concepts and the machine architecture.

Actually, if you look at variables or values at the implementation
level, there may be several complex systems of indirection, of
"machine level pointers", but that are (and should be) invisible to
the user, so that the abstract point of view I develop can be valid.
For most programming languages, the user should not have to worry, or
even know, about implementation, as implementation can vary a lot for a given
language. This may not be true for some languages, such as C, that are
intentionally close to the machine architecture, as an advanced
substitute for assembly languages that are in almost direct relation
to explicit binary coding, but far too low level for convenient use in most situations.

What the user of a language should know, and sometimes it should be even less than
that, is what are values and associated operations, where they can be
contained, how they can be associated to names, how the naming system
works, how can new kinds of values be defined, etc.

So another important concept is identifiers and naming. Naming an
entity (a value) can be done by associating an identifier with a value
(usually in a declaration). But a value can also be obtained by
applying operations to other named values. Names can be reused, and
there are rules (scoping rules) to determine what is associated to a
given identifier, according to context of use. There are also special
names, called litterals, to name the values of some domains, such as
integers (e.g. $612$) or boolean (e.g. true).

The association of an unchanging value with an identifier is usually
called a constant. Litterals are constants in that sense.

"Value containers" can also be considered as values, and their
association with an identifier is a variable in the usual "naive"
sense that you have been using. So you might say that a variable is a
"container constant".

Now you might wonder what is the difference between associating an
identifier with a value (constant declaration) or assigning a value to
a variable, i.e. storing the value in the container defined as a
container constant.  Essentially, declaration may be seen as an
operation that defines a notation, that associate an identifier which
is a syntactic entity to some value which is a semantic entity.
Assignment is a purely semantics operation that modifies a state,
i.e. modifies the value of a container. In some sense, declaration is
a meta concept with no semantic effect, other than providing a naming
(i.e. syntactic) mechanism for semantics entities.

Actually, assignments are semantic operations that occur dynamically
as the program is executed, while declarations have a more syntactic
nature and are usually to be interpreted in the text of the program,
independently of execution. This is why static scoping (i.e. textual
scoping) is usually the natural way to understand the meaning of
identifiers.

After all this, I can say that a pointer value is just another name for a container,and a pointer variable is a
container variable, i.e. a container (constant) that can contain another
container (with possible limitations on the containing game imposed by
some type system).

Regarding code, you state [pointers] might indicate the entry point
to a section of code and can be used to call that code. Actually this
is not quite true. A section of code is often meaningless alone
(from high level or implementation point of view). From a high-level
point of view, code usually contains identifiers, and you have to
interpret these identifiers in the static context where they were
declared. But there is actually a possible duplication of the same
static context, due essentially to recursion which is a dynamic
(run-time) phenomenon, and the code can only be executed in an
appropriate dynamic instance of the static context. This is a bit
complex, but the consequence is that the proper concept is that of a
closure that associate a piece of code and an environment where the
identifiers are to be interpreted. The closure is the proper semantic
concept, i.e. is a properly definable semantic value. Then you can
have closure constants, closure variables, and pointers to closures,
which are containers that can contain another container containing a
closure.

A function is a closure, usually with some parameters to define or
initialise some of its entities (constants and variables).

I am skipping many variations on the uses of these mechanisms.

Closures can be used to define OO structures in imperative or
functional languages. Actually, early work on OO style (probably
before the name) was done that way.

The paper you reference, which I skimmed quickly, seems to be an
interesting one, written by a competent person, but possibly not an
easy reading if you do not have significant experience with a variety
of languages and their underlying computational models.

But remember: many things are in the eyes of the beholder, as long as
he preserves a consistent view. Points of view may differ.

Does this answer your question?

PS: This is a long answer. If you consider some part of it inadequate, please be explicit about which it is. Thank you.


Is P contained in NP-hard? I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.

NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained in NP. Then it is possible to reduce a problem X in P to a problem Y in NP-hard? This does not add up to me in the scenario P!=NP.

What am I missing here? Is P contained in NP-hard?

NP-hard has all problems that can be reduced in polynomial time from an NP to them.

Not quite: NP-hard consists of all problems to which every NP problem reduces.

Suppose $X\in \mathsf{P}$. If $\mathsf{P}\not=\mathsf{NP}$, then $SAT$ (for example) is not reducible to $X$. So $X$ is not $\mathsf{NP}$-hard: there are some problems in $\mathsf{NP}$ which do not reduce to $X$.

Note that the class of problems to which some problem in $\mathsf{NP}$ reduces is ... the class of all problems whatsoever! This is because (as you observe) once we discard the "edge cases" $\emptyset$ and $\mathbb{N}$, every problem in $\mathsf{P}$ is also in $\mathsf{NP}$, and problems in $\mathsf{P}$ are trivially reducible$^1$ to everything.

$^1$With respect to polynomial-time many-one reducibility. Change the reducibility, and you potentially change the situation. E.g. $\mathsf{P}$ is $\mathsf{NP}$-hard with respect to exponential-time many-one reducibility, since with respect to this reducibility all problems in $\mathsf{NP}$ are trivial.

The "many-one" bit is why $\emptyset$ and $\mathbb{N}$ are problematic: no nonempty set is many-one reducible to $\emptyset$, and dually no no set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$. This annoyance goes away with more intricate reducibilities, like (variations of) Turing reducibility: literally every problem in $\mathsf{P}$ is reducible to everything with respect to polynomial-time Turing reducibility.

In complexity theory, the default reducibility notion is polynomial-time many-one reducibility. So if we just say "$\mathsf{NP}$-hard" we mean with respect to that reducibility - in which case "there is an $\mathsf{NP}$-hard problem in $\mathsf{P}$" is equivalent to $\mathsf{P=NP}$.


Why anyone learn compiler? I am learning compiler in my Uni. I have been through all major compiler techniques like top-down parsing, bottom-up parsing, Lexical analyzer, Symbol table, etc. I have a good understanding of them, but I am still confused about the course.

What is the point of learning all these things? What are their applications? Where these applications are used? The main point is, if someone asks me, Why Compiler? What is the benefit of taking this course?

Let me break up several possible interpretations of your question:

What is the purpose of learning compilation?

There are several possible answers:

So that you know how to build a compiler should you have to. This is not a good answer nowadays.
Part of the goal of the computer science curriculum is to explain to you how a computer works, stopping at the hardware. This includes the operating system, file systems, the compiler, the network stack, and more.
As a programmer, you will be using compilers. Sometimes it will be useful to know what happens under the hood. For example, understanding garbage collection will help you choose which language to use in embedded applications.
Compilation is part of the standard curriculum, so you might get asked about it in interviews.

Why are they teaching me compilation?

Apart from the reasons listed above, there is an additional one: universities are very conservative. In the past it used to be more important to understand how compilers work. Nowadays this is less important, but change is slow, so material
that made sense 10 years ago is still being taught today.

That said, some universities might reform their compilation curriculum, for example by de-emphasizing parsing, concentrating on more exciting aspects such as optimization, memory management, dynamic and static analysis, and the like.

Why am I studying compilation?

As an aspiring programmer, your university training contains lots of apparently useless classes, for example calculus. People choose to go to university for various reasons - it's a rite of passage, an opportunity for socialization and finding a partner, and it might help you get a job; or even just family or peer pressure.

Some people do away with university training, preferring other formal training, or even self-training. Some of these people are very successful.
For whatever reason, you chose to attend university rather than any of these alternative routes. You should accept that university training is rather theoretical, and try to make the most out of it.


How can I use prefix sum of an array to solve this problem? I attempted this question on hackerrank. It seemed simple enough, and my program ran on small inputs. But my approach was "naive". And failed for more computationally intensive inputs. Here is the question:

Problem Statement

You are given a list of size , initialized with zeroes. You have to perform  operations on the list and output the maximum of final values of all the  elements in the list. For every operation, you are given three integers ,  and  and you have to add value  to all the elements ranging from index  to (both inclusive).

Input Format

First line will contain two integers  and  separated by a single space.
Next  lines will contain three integers ,  and  separated by a single space.
Numbers in list are numbered from  to .

Constraints

2 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9

Output Format

A single line containing maximum value in the updated list.

Here is the editorial describing how to solve the problem

  You are given a list of size N, initialized with zeroes. You have to
  perform M queries on the list and output the maximum of final values
  of all the N elements in the list. For every query, you are given
  three integers a, b and k and you have to add value k to all the
  elements ranging from index a to b(both inclusive).

First thought which comes into mind after reading this problem will be segment tree with lazy propogation but that will not pass here as N <= 10^7 :)

So, We have to use some different kind of approach. We can do a O(1) update, i.e. given a b k add k to index a and add -k to index (b+1). By doing this kind of update ith number in array will be prefix sum of array from index 1 to i.

So, We can do all M updates in O(M) time. Now we have to check the largest number in the original array. i.e. the index i such that prefix sum attains maximum value.

We can calculate the all prefix sums as well as maximum prefix sum in O(N) time which will get Accepted. Another approach is we can do it in O(MlogM) time because we have to check the value of prefix sum at only 2*M indices. i.e. a and b values of all the updates. See setter's code.

I don't understand how adding k to index a and adding -k to index (b+1) gives us an array in which the the ith number in the array is the prefix sum of the array from index 1 to i.

Consider a new type of query (t2q, type 2 query) of the form $(index, value)$ where we add $value$ to all items from $index$ to the end.

Then the original type of query (t1q, type 1 query) is equivalent to 2 t2q. $(lower, upper, value) \equiv (lower, value) \oplus (upper+1, -value)$. Notice that the second t2q cancels the first t2q over all items that should not be affected

Now, 2 t2q with the same $index$ could be reduced to a single t2q easily. $(index, valueA) \oplus (index, valueB) \equiv (index, valueA+valueB)$. Therefore, we have at most $N=\text{size of our vector}$ type 2 queries. In other words, we can store all those queries in a vector. And if there is an $index$ with no query associated, we just create a "dummy query" using the identity element of our operation (zero in this particular problem).

$$
(index, value) \equiv t2q[index]=value
$$

Next, a particular item in our vector $v[j]$ is only affected by a t2q iff $index <= j$. In other words, $v[j]$ is affected by all type 2 queries with lower $index$. To calculate the value of a particular $v[j]$ just add all $values$ of t2q with lower $index$ and add the value of $v[j]$ which is zero.

$$
v'[j] = v[j] + \sum_{i=0}^j{t2q[i]} = \sum_{i=0}^j{t2q[i]}
$$

If we iterate from the beginning, then each item can be calculated in $\mathcal{O}(1)$ if we store the previous sum. And simultaneously, we look for the maximum.

$$
v'[j+1] = \sum_{i=0}^{j+1}{t2q[i]} = t2q[j+1] + v'[j]
$$

Edit

This approach will take $\mathcal{O}(M+N)$-time and $\mathcal{O}(N)$-space, because we first process every query in $\mathcal{O}(1)$ (updating two positions in our vector), adding $\mathcal{O}(M)$, and then we spend $\mathcal{O}(N)$ looking for the maximum.

Like you said, there are $\mathcal{O}(M)$ values different than zero in $t2q$. We can ignore those zeros using a Self-balancing Binary Search Tree instead of a vector. Then we go from $\mathcal{O}(1)$ to $\mathcal{O}(lg\,M)$ while updating every entry (process every query) and from $\mathcal{O}(N)$ to $\mathcal{O}(M)$ for store all those entries.

So now, we first spend $\mathcal{O}(M\,lg\,M)$ to process all queries ($\mathcal{O}(M)$ insertions of $\mathcal{O}(lg\, M)$. Then we traverse in-order looking for the maximum using the previous idea in $\mathcal{O}(M)$.

$$
v'[j] = t2q[j] + v'[i] \, \text{iff} \, (index, 0) \, \forall i < index < j
$$

Finally, this new approach takes $\mathcal{O}(M\,lg\,M)$-time ($\mathcal{O}(M\,lg\,M)$+$\mathcal{O}(M)$) and $\mathcal{O}(M)$-space. Even better, is (reasonably) independent $N$ (now we can handle $N \approx 2^{64}$).


Does this Turing Machine M decide the language of polynomials? Does this Turing Machine decide
language of polynomials with integer coefficients which have integer roots:
The input represents a polynomial over variables x1, . . . , xn with integer coefficients.
1. Examine all possible integer values of x1, . . . , xn.
2. Evaluate the polynomial on all of them.
3. If any of them evaluates to 0, accept; else reject

From what I know I would say No, since: "M decides a language L iff M accepts all strings in L and reject all strings not in L ". Where L is the language of polynomials.  Is this correct?
Any help is appreciated!

The problem with this algorithm is that it never terminates when the polynomial has no integer roots. Its semantics are:

If the input polynomial is in $L$, the machine halts and answers YES.
If the input polynomial is not in $L$, the machine never halts.

The semantics we are after are a bit different:

If the input polynomial is in $L$, the machine halts and answers YES.
If the input polynomial is not in $L$, the machine halts and answers NO.


Computing every possible sum of integers taken from different sets I'm trying to proove $NP$-membership for a problem from the following certificate.
I have $n$ sets of integers :
$$(S_i)_{i \in \{1,\dots,n\}}$$
Each set has a number $m_i$ of integers.
I make "combination" from those sets by taking at most one element in each set.
A "combination" has between $0$ and $n$ elements (assuming sets are not empty).
A "combination" has a value : the sum of its elements.
I have to compute the sum of every possible "combination" values,
and look if it is greater than a given value.
An analytical formula would be nice, but I'm not sure it exists.
Otherwise, do you think this sum is easily computable ?


Efficient algorithm to find number of sequences in string Suppose I have a string that goes like "abcabcdeaabcdef", where each character is either one more than the previous one or a.

If the character at position i is "c", I know that it is preceded by "ab".

I want to find the number and length of all sequences (substrings that contain sequential characters). For example, the above string would give "abc", "abcde", "a", "abcdef".

Is there a more efficient algorithm to do this than simply doing a O(n) search over the string?

You cant create an algoithm to do this in the worst case. Even if we read right to left and if we assume we can do some level of jumping (e.g if we see an f we can jump 6 spaces left) we still have to, in the worst case (the string of a's), read over the entire string. This can never be done in $o(n)$ time. The right to left with skipping will run in $O(m)$ time where $m$ is the number of increasing subsequences, and $m$ is $O(n)$.


Can all regular tree types be expressed as $\mu$ types? In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct subtrees.

I'm wondering, is the converse true? Can every regular tree type be expressed using the $\mu$ fixpoint notation? It seems obvious that this can be done if you have mutually recursive types: you have a type for each subtree of the regular tree type. But can it be done with singly recursive types?

You can reduce mutual recursion to a single recursion, see Bekic's Theorem, see e.g. Section 10.1 of Winskel's (1), where Bekic is worked out for programs rather than types. Note however that the details depend on the exact nature of the formal system in question. See A. Bauer's answer in (2) for the case of types.

G. Winskel, The Formal Semantics of Programming Languages.
CSTheory Stackexchange, Can Isorecursive types capture mutually recursive data types?


What are the possible sets of word lengths in a regular language? Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$

Which sets of integers can be the length set of a regular language?

First, an observation which is not crucial but convenient: the set $\mathscr{S}$ of sets of integers that are $LS(L)$ for some regular language $L$ on a non-empty alphabet $\mathscr{A}$ does not depend on the choice of alphabet. To see that, consider a finite automaton that recognizes $L$; the lengths of the words that are in $L$ are the lengths of the paths on the automaton seen as an unlabeled graph from the start state to any accept state. In particular, you can relabel every arrow to $a$ and get a regular language with the same length set over the alphabet $\{a\}$. Conversely, if $L$ is a regular language over a one-element alphabet, it can be trivially injected into a larger alphabet, and the result is still a regular language.

Therefore we are looking for the possible length sets for words over a singleton alphabet. On a singleton alphabet, the language is the length set written out in unary: $\mathrm{LS}(L) = \{n\in\mathbb{N} \mid a^n \in L\}$. Such languages are called unary languages.

Let $L$ be a regular language, and consider a deterministic finite automaton (DFA) that recognizes $L$. The set of lengths of words of $L$ is the set of lengths of paths in the DFA seen as a directed graph that start on the start state and end in one of the accept states. A DFA on a one-element alphabet is pretty tame (NFAs would be wilder): it's either a finite list or a circular list. If the list is finite, number the states from $0$ to $h$ following the list order; if it's circular, number the states from $0$ to $h$ following the head of the list, and $h$ to $h+r$ along the loop.

Let $F$ be the set of indices of accept states up to $h$, and $G$ be the set of indices of accept states from $h$ to $h+r$. Then

$$\mathrm{LS}(L) = F \cup \{ k \, r + x \mid x \in G, k\in\mathbb{N} \}$$

Conversely, let $h$ and $r$ be two integers and $F$ and $G$ be two finite sets of integers such that $\forall x \in F, x \le h$ and $\forall x \in G, h \le x \le h+r$. Then the set $L_{F,G,r} = \{ a^{k\,r+x} \mid x\in G, k\in\mathbb{N} \}$ is a regular language: it is the language recognized by the DFA described above. A regular expression that describes this language is $a^F \mid a^{G} (a^r)^*$.

To summarize in English, the length sets of regular languages are the sets of integers that are periodic¹ above a certain value.

¹
To hang on to a well-established notion, periodic means the characteristic function of the set (which is a function $\mathbb{N}\to\{\mathtt{false},\mathtt{true}\}$ which we lift to a function $\mathbb{Z}\to\{\mathtt{false},\mathtt{true}\}$) is periodic. Periodic above a certain value means that the function restricted to $[h,+\infty[$ can be prolonged into a periodic function.


What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?

It is not too hard to search for it using SageMath. The graph you are looking for seems to be the Wagner graph.

It takes a couple of minutes to run, you can check it yourself here.


Polynomial kernelization for Set Splitting In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$.  A set in $F$ is split by $f$ if $F$ receives both colors.
The Set Splitting problem is defined as follows:

Given an set system $(U, F)$  and an integer $k \in \mathbb{N}$, does there exists a coloring of $(U,F)$ that splits at least $k$ sets from $F$?

I wish to show that there exists kernel with $2k$ sets and $|U|\in O(k^2)$. So far I have these reduction rules:
Rule 1: If there is $x\in U$ s.t. there's no $W\in F$ s.t. $x\in W$, then we can delete $x$ from U and work with a new instance. $(F,U\setminus\{x\},k)$.
Rule 2: If $W\in F$ is a singleton, then we can remove it and work with $(F\setminus \{W\},U,K)$ because such $W$ will never contain two elements of different colors.
Rule 3: If $V\in F$ is s.t. $|V|\geq 2$ and $V\cap W$ is empty for each other $W\in F$, then we can color elements in $V$ somehow to satisfy the distinctness and we can lower $k$ by one.
Rule 4: From instance $(F,U,k)$ create instance $(F,U\cap \bigcup F,k)$, i.e. we are interested in coloring only the elements that are actually in some set $W\in F$.
Not really sure how to proceed from here. Any hints appreciated.

I understood the question as "select a subset of size $2k$ from $F$ such that (there exists coloring for $F$ $\iff$ there exists coloring for the subset)".
As you've said, you can remove all singleton and empty sets. The remaining sets have at least $2$ elements. You can show that any $2k$ such sets suffice.
Select $2k$ arbitrary sets with at least two elements. We assume that they have exactly $2$ elements (it's the worst case; the analysis is easy to modify for more than $2$ elements). We use the probabilistic method. For each element, we select the color randomly, and we compute the expected number of sets that have both colors.
We show that the expected number of sets with both colors is $k$. Note that this is an expectation over all random colorings. Therefore, there must exist a coloring that gives the value greater or equal to the expectation, i.e. $\ge k$, as required.
Let $\{S_i\}_{i=1}^{2k}$ be the selected sets.
For each set $S_i$ we introduce indicator variable $I_i$, which equals $1$ when the set $S_i$ has both colors, and $0$ otherwise.
The expectation above equals $\mathbb E[\sum_{i=1}^{2k} I_i] = \sum_{i=1}^{2k} \mathbb E[I_i]$.
For set $S_i = \{x_1, x_2\}$, with probability $\frac 12$, $x_1$ and $x_2$ have different colors. Therefore, $\mathbb E[I_i] = \frac 12$, and the required expectation is $2k \cdot \frac 12 = k$.


Symmetry in Pattern Databases I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the paper Pattern Databases by Joseph C. Culberson and Jonathan Schaeffer (University of Alberta) in Computational Intelligence, Volume 14, Number 3, 1998.

In the paper, they explain the different kinds of symmetries we can use on the 15-Sliding Tile Puzzle such as Horizontal, Vertical and Mirror. But what I do not understand is how exactly are we going to use those symmetrical configurations of a puzzle to find a good lower bound on the estimated cost of a state from the goal.

I would really appreciate if anybody can explain the process of using symmetry in pattern databases or can point toward a good explanation.

From your question I assume you understand how symmetries are computed. As an exercise, make sure to understand the example given in Figure 4 which refers to the easiest of all symmetries, the Mirror (also known as Diagonal) denoted as $D$. In the following I will refer to this symmetry only unless otherwise noted.

Next, hope you also understand that symmetries create isomorphic puzzles so that the number of moves necessary to optimally solve the reflected state is precisely the same number of moves (but different) necessary to optimally solve the original state ---see Figure 3 in the paper for a good example of a path reflection which results from applying $D$.

Hence, when computing the heuristic estimate of any state $p$, compute its symmetrical state $p'$ (in time linear in the size of the puzzle), and look up the Pattern Database for both states $p$ and $p'$. Since Pattern Databases are indeed homomorphisms let $\rho$ denote such mapping ---i.e., what tiles are mapped to themselves and what tiles are replaced by the don't care symbol. Thus, you can safely take the maximum of both values returned from the PDB:

$h(p)=\max\{V(\rho(p)), V(\rho(p'))\}$

where $V(n)$ denotes the value stored in the PDB for the abstracted state $n$ which consists of tiles and don't care symbols. The two values within brackets are indeed those mentioned at the beginning of Section 4.3.

Note the importance of the blank tile: The other symmetries H, V and D' do not preserve its location and therefore Section 4.2 proposes to use some corrections (3, 3, and 6 respectively) to both the lower and upper bounds.

Of all these symmetries, the most widely used are $D$ and $D'$. Other works (among many others) exploiting them are given below:

Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. Artificial Intelligence, 134, pp. 9--22, 2002

Ariel Felner, Richard Korf, S. Hannan. Additive Pattern Database Heuristics. Journal of Artificial Intelligence Research, 22, pp. 279--318, 2004.

Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer, Duality in Permutation State Spaces and the Dual Search Algorithm, Artificial Intelligence, 172 (4--5), pp. 514--540, 2008

To finish, let me reproduce here a paragraph from the last paper:

  Because all valid, alternative PDB lookups provide lower bounds on the
  distance from state $S$ to $G$, their maximum can be taken as the
  value for $h(S)$. Of course, there is a tradeoff for doing this
  ---each PDB lookup increases the time it takes to compute $h(S)$. Because additional lookups provide diminishing returns in terms of the
  reduction in the number of nodes generated, it is not always best to
  use all possible PDB lookups.

Hope this helps,


Where should I start to understand how computers work? I am interested in how computers work but I have no idea how the concept of 0's and 1's converts to making possible for people to control a computer by programming. I would like to understand from very fundamental levels of computer and continue studying more in depth until I am satisfied. Where should I start? Is there a name for this topic? What books should I read?

**Edit: This was my first post and I think I got a lot of good suggestions on where to start. I will be looking up all the answers posted here. Thanks a lot for everyone who answered on this post.

You're asking a very broad question that isn't particularly easy to answer "correctly".

What you are describing is what you learn if you follow through with a degree in computer science or maybe more precisely in electrical engineering and computer science.

So I would recommend you to do exactly that:  Go to you favorite university websites and look up what the content of a degree in EE/CS is.

For example, I've heard that MIT has a degree in EECS, so I looked it up, and found a long list of courses.

There I found a course called 6.01 —  Introduction to Electrical Engineering and Computer Science I which even has a downloadable lecture notes document:

  6.01 Course Notes, Spring 2011 (PDF - 4.9MB)

in which the basics of circuits are covered in Chapter 1.

Summa summarum you're asking for what goes into a degree in electrical engineering and computer science, and the best way to find the answer to that is to go to the source.

Universities and schools exist for a reason. :)


Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard? Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note.  This problem is studied in wireless communication where the set represents links in a wireless network, the $P_i$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example here, but the reduction is very hard for me.

This problem can be solved in polynomial time.  Therefore, it's likely not NP-hard (unless P = NP).

After a little bit of algebraic manipulation, we find that the condition on $S$ is equivalent to requiring that

$$2 P_i \ge \varepsilon + \sum_{j \in S} P_j \quad \text{for all $i \in S$}.$$

This, in turn, is equivalent to requiring

$$2 \min \{P_i : i \in S\} \ge \varepsilon + \sum_{j \in S} P_j.$$

For convenience, sort the $P_i$'s into increasing order, so $P_1 \le P_2 \le \dots \le P_n$.

Now one can prove that if there is any set of cardinality $k$ that satisfies this equation, then there's a set of the form $S = \{t,t+1,t+2,\dots,t+k-1\}$ that satisfies this equation, for some $t$.  (This can be proven using an exchange argument, swapping pairs of indices as needed and showing that the swap leaves the left-hand side unchanged and only decreases the right-hand side.)

Now you can try all possible values of $t$ and see whether the corresponding set satisfies the condition.  There are only $n$ possible values of $t$, so this can certainly be tested in polynomial time.  In fact, with clever programming (prefix sums, etc.), you can implement this in $O(n \lg n)$ time, or in $O(n)$ time if the $P_i$'s are already provided in sorted order.

More generally, if you want to find the set $S$ of maximum cardinality that satisfies the equation, such a set will have the form $S=\{t,t+1,t+2,t+3,\dots,u\}$ for some $t,u$.  Therefore, you can try all such possibilities and see which has largest cardinality.  This too can be done in $O(n \lg n)$ time using appropriate methods (binary search, prefix sums).  Alternatively, you can do binary search on $k$, and apply the decision algorithm of the previous paragraph for each candidate value of $k$ to find the largest $k$ for which a solution exists.  The running time is again $O(n \lg n)$.


How does the automatic complexity analysis of Codility work? When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code.

I was just wondering how it does this automatically - i.e. without any O(n) analysis?

Probably only Codility knows for sure how they do it.  But here is how I bet they do it.

First, they devise a set of test cases of varying sizes.  They run your program on each test case and time how long it takes.  This gives them a set of observations $(n_i,t_i)$, where $n_i$ is the size of the $i$th test case and $t_i$ is the time your program takes given that input.  These can be viewed as a set of points in the 2D plane.

Second, they try to fit a curve to these points.  For instance, they check whether a line appears to fit the points, or a quadratic, or a cubic.  They probably have a library of a set of families of curves (e.g., $cn, $cn^2$, $c n \lg n$, $c \lg n$, and so on), and they check each to which ones are consistent with the observation.  Then they output that one as the running time of your algorithm.

I would imagine some adjustments might be necessary.  Rather than checking whether the points fit the curve, it might be necessary to check whether the points all fall below the curve.  For instance, rather than checking whether there exists a constant $c$ such that $t_i \approx c n_i^2$ for all $i$, they might check whether there is a constant $c$ such that $t_i \le c n_i^2$ for all $i$ (with some constraints on $c$, e.g., $c \le 1000$).  Out of all asymptotic running times that seem to be consistent with the observations, they select the asymptotically smallest one and output that one.

This approach has the advantage that it does not require analysis of source code.  All they need is the ability to run your program and time its running time.

At the same time, this heuristic is definitely not foolproof: it can give the wrong answers in some cases.  See How to fool the plot inspection heuristic?


Algorithm to solve constraint satisfaction problems I have group of people. Each person can be described by few characteristics:

age, occupation, city, favorite_color

I would like to generate 60 random people and combine them into pairs.
With a constrain that no person in a pair can share any characteristic, for example I can't have two people in a pair whose favorite_color is green.

I was thinking about using Backtracking algorithm to solve it.

What other algorithms I could use to solve this particular problem?
I would like to research and implement some.

Use an algorithm to find a perfect matching in a graph.  Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for a perfect matching.  If none exists, you can throw away that data and generate a new random sample, and repeat until you find a valid solution.


Prove count without revealing data Suppose I maintain a proprietary database and claim that it has N records. Before subscribing to my database a client wants a proof that the database is indeed this large. What theoretical protocol can I employ to prove my database size with possibly revealing only a small number of records?

I think the usual way of doing this is that you hash each record (with a known cryptographically secure hash) and provide the client with $N$ hash values. The client chooses $k$ out of those hash values and you reply with the corresponding $k$ records. The client can then verify that the hash values match up correctly with the provided records plus whatever record validation they'd like to do. Note that if you have duplicate records in your DB, those duplicates could be inferred from provided hash values (e.g.: the client could get a pretty good estimate of the number of distinct records in your DB). If this is undesirable, then you can salt the hashes.


Proof for factors of a number I was trying to prove the following:

  if  x%(x/2) != 0 or x%(x/2) == 0

  then x%(x/y) != 0 or x%(x/y) == 0  such that y = [2,4)

So I am trying to figure out whether a number can have a factor in between its half and its fourth.  I am trying to use it in a factoring algorithm.

If a number $n$ has a factor $m$ in the range $n/4 \leq m \leq n/2$, then the quotient $k = n/m$ satisfies $2 \leq k \leq 4$, that is, $k \in \{2,3,4\}$. This should give you a fast algorithm for determining whether such a factor $m$ exists.


Is there a name/algorithm for this problem related to set cover and CSP? Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy multiple graduation requirements (e.g., writing, quantitative literacy, and art), each class may only count for up to two graduation requirements for a single student. We wish to be able to determine the mapping of courses (within a given transcript) to graduation requirements that satisfies the most graduation requirements in order to see if a student can graduate, and, if not, what graduation requirements are unmet. I've tried writing this up semi-formally:

Given:

A set of graduation requirements $\cal G$.
A set of classes $\cal C$ offered at the college.
A map ${\cal M: C} \rightarrow 2^\cal G$ indicating which classes fulfill which requirements. A given class can fulfill anywhere from 0 to $|\cal G|$ requirements.
A set of classes $\cal T$ (for transcript) $\subseteq \cal C$.

Determine:

A set $\cal S$ of $(c, g)$ pairs, where $c \in \cal T, g \in \cal M(c)$ that maximizes coverage of $\cal G$ but contains no more than 2 pairs with the same $c$.

Is there a name and known algorithm to solve this problem?

Just to be sure, I assume that $\mathcal{G}^* = 2^\mathcal{G}$, i.e. that $\mathcal{G}^*$ is the power set of $\mathcal{G}$.

Alright, we can use the following flow network $(V,E,\text{cap})$: let $V = \{s\} \uplus \mathcal{T} \uplus \mathcal{G} \uplus \{t\}$. Now let $E = \{(s, c) : c \in \mathcal{T}\} \uplus \{(g,t) : g \in \mathcal{G}\} \uplus \{(c,g) : c\in \mathcal{T} \wedge g \in \mathcal{G} \wedge g \in \mathcal{M}(c)\}$. Finally, we need capacity constraints:

\begin{align}\text{cap}(s,c) &= \min\{|\mathcal{M}(c)|,2\} \qquad &\text{(every class covers at most 2 requirements)}\\
\text{cap}(g,t) &= 1\\
\text{cap}(c,g) &= 1
\end{align}

Now we run maxflow to find an $s-t-$flow and we are done; while there may be fractional maximum flows, finding an integral one is easily done via an augmenting path algorithm (since all capacities are integral).

The problem reminds me of maximum matching, but I can't reduce it to matching off the cuff. Maybe some generalization, not sure.