Is this classic puzzle book game NP-complete? There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked out just like a cross-word, and some squares have a letter already pre-written in them. The goal is to write each word from the list once and only once in the puzzle, where each word is written either horizontally (left to right) or vertically (top down) into non-blacked out consecutive squares, and when you write a word, the two squares flanking the ends of the word must either be blacked out or off the board. Also for the letters pre-written into some squares, the words written that overlap these squares must respect the pre-written letter.

Now, if we assume a fixed size alphabet for the words, is deciding whether we can fill the board with a valid solution using exactly each word on the list once and only once an NP-complete problem, if the side length of the board is not fixed?

Sorry for answering an old post.

I´ve been thinking about it and i think that the problem with a fixed alphabet is NP-complete as well.

I´m going to reduce positive 1-in-3 SAT to this word problem

Yesterday i was having trouble coming with ideas for solving the problem. I had trouble making each variable different until i looked again at the question and i realized that you allowed having squares with planted symbols. This simplified the reduction a lot. My other idea was to have words of different length for each different variable.

THE REDUCTION

Now i´m going to describe the gadgets we are gonna use:

Variable gadget

We label each variable with a different numerical index and we will have a different number for each variable. We pick the biggest index and we represent the number in binary, we will call this binary chain $n$.

Then we create two different vertical words for each variable. All words will have a length of $3 + |n|$ (Only if we allow duplicate words in the list of words), where $|n|$ is the length of the binary chain $n$.

For instance, let the biggest index be the number $4$. When we transform this number in binary we obtain the chain $100$ in binary, this chain has a length of three. So each variable word will have a length of $6$ in this example.

Now we create two different words for each variable. One word will have the symbol $3$ at the beginning, then the symbol $2$ below, then a binary chain that represents the index of the variable and we pad with zeroes the chain so that it has the same length that chain $n$ and finally the symbol $3$ at the end. Of course the symbols can be changed.

The other word is almost the same but it will have the symbol $4$ instead of the symbol $3$.

For instance, let the biggest index be the number $4$. We will have the following two words for the variable with index $1$:

$320013$ and $420014$

As we see we have padded the binary reperesentation of the number $1$ with zeroes so that it has a length of $|n|$

We have to copy these words many times, we will need one copy of each word for each occurence of a variable in the SAT instance. This will create duplicates in the list of words. We can get rid of the duplicates by adding another binary chain to the binary chain that uniquely identifies the variable. This new chain will uniquely identify each ocurrence of a variable.

To do that, we simply assign each ocurrence of the variable another binary chain and we olace that chain at the end of the binary representation of the variable.

To create this new binary chain first we have to create a different index for each variable, we call the biggest number in each index $n_i$ where $i$ is an identifier for each variable.  After that, we transform the number $n_i$ into a binary chain and then we count the length of the chain, we call this number $|n_i|$. Then, for each index, we create a different binary number for each ocurrence of the variable. We pad the number with zeroes until the length of the binary chain becomes $|n_i|$ so that all the words that belong to each ocurrence of the variable have the same length.

This will get rid of duplicates inside the variable words.

For instance, suppose that variable $x_2$ appears three times in the SAT instance.
We create the following words:

$32010013$ $42010014$, $32010103$ $42010104$ and $32010113$ $42010114$

Clause gadget

For each clause gadget, we will create three new horizontal words, each clause word will have  a length of $6$ squares (Only if we allow duplicate words in the list of words). These are the words that we will create for each clause:

$535354$, $535453$ and $545353$

We have a different clause word for each possible way of satisfyng the clause, the symbol $4$ represents a literal set to true and the symbol $3$ represents a literal set to false. The number $5$ is used to indicate that it is a clause word.

There will be repeated words in the list of words, we can get rid of the repetitions by using the procedure that we used to uniquely identify the variable words.
That is, we create a different binary chain for each clause and we append each chain to the clause words corresopnding to each clause.
To do that we create a new index for the clauses and we pick the biggest number of the index, we will call this number $m$. We represent $m$ as a binary chain and we call the length of this binary chain as $|m|$. Now, we create a different binary number for each clause, starting with the number 1, and we pad the number  with zeroes to make a binary chain that has a length of $|m|$. We append each binary chain to the clause words that belong to the clause.

Now, let´s see a picture of a clause gadget in the board:

This example represents the clause $(x_2 \lor x_3 \lor x_4)$ and the 1 in 3 instance being reduced is $(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $

As we see, there are written squares. The vertical columns have written symbols to indicate which literals are inside the clause. The end and the beginning of the column are blank squares. This lets the player choose the value of the variable.
The marked symbols in the horizontal row force the player to put a clause word in that row. Because all clause words have only a  single symbol $4$ that means that only one of the literals that is inside the clause gadget can be set to "true".

If we don´t allow duplicates inside the list of words we will have to modify the image.

The clause row in the image will become: $5b5b5b10$ and the literal columns will be, from left to right:

$b201010b$, $b201110b$ and $b21001b$

Where the symbol $b$ means blank square

See an example:

Variable consistency gadget

This is a gadget that ensures that the player can only asign the same value for all literal columns of a variable.

We will have a new gadget for each variable

We will create two new words for each gadget.

The length of the word will depend on the number of ocurrences of a variable. The length of a word will be $2 * k$ where $k$ is the number of ocurrences of a variable. So if variable $x_2$ appears two times in the sat instance, the words will have a length of four.
One of the two words is formed by repeating the chain $63$ $k$ times, where k is the number of occurrences of the variable. The other word is formed by repeating
the chain $64$ $k$ times, where k is the number of occurrences of the variable in the SAT instance being reduced.

For instance if a variable $x_2$ has two ocurrences, the words that belong to the corresponding variable assignment gadget will be:

$6363$ and $6464$

If we want to avoid repeated words, notice that each consistency gadget belongs to a different variable. So we can append the binary chain that identifies each variable to the two words that we created for this gadget.

Now let´s see an example picture of this gadget:

This gadget is for the variable $x_2$ and the 1 in 3 instance being reduced is $(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $.

As we see, there are two horizontal rows, the symbols written inside the rows make sure that we can only place words containing those symbols, those words are the words that we created for this gadget. In one of the rows, we see that there are two columns coming into it, because of the symbols that are placed in the columns we make sure we can only place variable words. Because the only words we can only place on the variable consistency row have only the symbol $3$ or only the symbol $4$ in them, we force the player to place all variable words with that symbol inside the gadget. This means that the only variable words that are available to be placed inside the clause gadgets have only the symbol $3$ or only the symbol $4$. We can place the remaining word of this gagdet in the other row

If we don´t allow duplicates in the list of words, the words inside the example picture will be:

For the rows:

$6b6b010$ and $6b6b010$

For the columns:

$b201001b$ and $b201010b$

Where the symbol $b$ means blank square

See an example:

Clause dump gadget

This is a gadget created to place the unused clause words. To do that, we have only to place two rows for each clause word in an empty part of the board. These rows are not connected to any other row or column.

With this we finish the reduction, as we claimed we only need 6 symbols for the reduction.

Example

If the previous explanation was confusing, here is an example picture of an instance of positive 1 in 3 SAT that has been reduced to this word problem:

If we disallow repeated words:

The instance that has been reduced is:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $


Find all shortest paths in a graph where path has even number of edges and greater than 6 Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an even number of edges and the number of edges is greater-equal to $6$.

So I know I need to use Dijkstra algorithm on a modified graph. Somehow I need to "count" the number of edges. I think I need to add some vertices for each vertex which will make the "count" but I can't figure it out completely.

I'd be glad for help.

Thanks.

Hint: Use an appropriate layered graph. If you find the problem difficult, try solving it under only one of the conditions (only an even number of edges, or only at least 6 edges).


is little-o notation correct after being powered by a number? I just wanted an example in which the  equation given below is not correct.

$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$

Trivially: $f(n) = 0, g(n) = 1$. Then $lim_{n \to \infty} f(n)/g(n) = lim_{n \to \infty} 0 / 1 = 0$ and $lim_{n \to \infty} 2^{f(n)}/2^{g(n)} = lim_{n \to \infty} 1 / 2 \neq 0$. You may want to think if less trivial cases exist.


Increasing an edge weight. Shortest time to recompute an $MST$? I have an $MST$ tree $T$. I increase the weight of a single edge $e$ by $c$(a non negative constant).
I need to recompute an $MST$ as fast as i can. How I do this? The idea I had in mimd is to remove $e$ from $T$. Loop over all crossing edges between the two "halves" of $T$. See which one is minimal weight. Add her instead.
This will require $O(|E|)$ time. Is there a faster idea? Or does my idea requires less than $O(|E|)$?
I suspect a more efficient algorothm exists because i do not use the fact that $e$'s weight increased.

If you're required to solve this "one-shot" problem, you're not allowed to perform any pre-processing, and you don't have any additional assumption, then a running time of $O(m)$ is the best you can hope for.
Indeed, consider an edge $e$ such that the fundamental cut $C_e$ induced by $e$ contains $\Theta(m)$ edges. All edges in $C_e$ have distinct weights that are strictly larger than the weight $w_e$ of $e$. For every value of $m$, it is easy to come up with a graph $G$ , an associated MST $T$, and and edge $e$ that satisfy these properties.
Suppose that there is a (deterministic) algorithm $A$ with a running time of $o(m)$. Then, when $A$ is run with inputs $G$, $T$, and $e$ there is at least one edge $f \in C_e$ whose weight is never read by $A$, and such that $f$ is not added to the new MST $T'$.
We can then run $A$ with inputs $G'$, $T$, and $e$, where $G'$ is a copy of $G$ in which the weight of edge $f$ has been set to $w_e$. The returned MST must still be $T'$, but this is incorrect since the new MST must include edge $f$.


What is the amount of programs for which we can solve the halting problem? The halting problem is undecidable of course.
This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the halting problem is undecidable, it could still be that there is a program that can decide for every program except itself whether it halts or not.

So I am wondering, for what percentage of programs can we solve the halting problem?
That is, if we assign a Gödel number G to every program. What is the value of the limit with respect to G to infinity of:

  ${s}/n$

where s = the number of programs with Gödel number 1 to G, for which we can decide whether it halts or not.

and n = the number of programs with Gödel number 1 to G, for which we cannot decide whether it halts or not.

I am not looking for a specific answer like 75%. I am looking for an answer like: less than 0.01 % or more than 9.99%, or anything really that gives a hint at an answer.

If we read the question as written then the answer is 100%. Let us be careful about what is being asked.

Attempt 1

Consider the set of numbers $n$ such that the $n$-th program either halts or it does not. If you believe in classical logic then every number is in this set, because "the $n$-th program either halts or it does not" is an instance of the Law of Excluded middle. So the answer is 100%.

Attempt 2

Sometimes people try to fix Attempt 1 by differentiating between "program $n$ halts or it does not" and "we have a decision procedure for $n$" (as witnessed by the comment "For every fixed program the halting problem is decidable." by adrianN above). That is, they think that it makes sense to have many decision procedures, one for each number. This leads to the following (failed) attempt:

Consdier the set of numbers $n$ such that there is a decision procedure for the halting of the $n$-th program. Once again every number is in this set:

If the $n$-th program halts then the decision procedure is print "it halts".
If the $n$-th program does not halt then te decision procedure is print "it does not halt".

However, and this is quite important:

we are here not talking about a single (posssibly non-computable) decision procedure,
we are talking about many decision procedures, one for each number (which is weird, which is why this is a failed attempt)
if we try to combine the decision procedures together somehow, we have a problem: even though for each particular $n$ there is a decision procedure $D_n$, the function $n \mapsto D_n$ is not computable

Attempt 3

The lesson learned from Attempt 2 is that we need one decision procedure that handles all numbers. But there is no such decision procedure because it would be a Halting oracle. We can still ask how well can we do with a single procedure?

Say that a procedure $P$ is a partial Halting oracle if, for every $n$,

$P(n)$ is undefined, or
$P(n) = 1$ and the $n$-th machine halts, or
$P(n) = 0$ and the $n$-th machine does not halt.

Define the success rate $s_P$ of such a decision procedure $P$ to be
$$s_P = \lim_{n \to \infty} \frac{\big|\{i \leq n \mid \text{$P(i)$ defined}\}\big|}{n}$$
Now we can ask whehter $s_P$ is well-defined (does the limit exist)? If sohow big can $s_P$ be?

Summary: The way you asked your question looks like you are going for Attempt 1 or Attempt 2, but it is not really clear. The problem is that you speak of "a solvable program". That does not make any sense. Every single program "is solvable" because it either halts or it does not (attempt 1, maybe attempt 2). You need to phrase the question carefully.


What is the real advantage of Google's new Fuchsia operating system kernel? Google's new in-production OS which it desires to replace not only Android but many other devices utilizes a completely new kernel:

  The code differs from Android and Chrome OS due to its being based on the "Zircon" kernel (formerly "Magenta") rather than on the Linux kernel.

https://en.wikipedia.org/wiki/Google_Fuchsia

  Zircon does not support Unix-style signals and provides no way to directly implement them. Instead, it supports waiting on handles, which can be in a number of different signal states, such as ready for writing, running, stopped, etc. Similarly, Zircon does not have Unix-like fork or exec but uses the launchpad library to create processes.

https://www.infoq.com/news/2018/04/google-fuchsia-zircon-early-look

I've seen demos of Fuchsia by reviewers but these are all just demos of a desktop interface and don't actually describe any of the advantages towards moving to a new platform and the motivation for a building a new kernel.

I see a lot of technical jargon and engineering-speak being thrown around but this isn't anything different from what I hear about every new platform and its super-sauce kernel.

In my opinion, it's always been about market penetration and mindshare. Google has a unique advantage in that they have a widespread platform already with Android and may be able to strong arm vendors into switching from Android to Fuchsia. But this may also be a re-run of several failed attempts by previous market leaders to do this very thing.

Software compatibility is, in my opinion, a constant when it comes to enticing existing users to move to a new platform. Apple was able to do this gracefully with Rosetta and Windows with NTVDM. I think that it will be very interesting to see how well Android can handle this with so much fragmentation.

So that was a little history and some of my opinion. But my actual question is on what, from a technical standpoint, does Fuchsia's new kernel "Zircon" bring to the table? Creating an entirely new userspace is one thing but swapping out a kernel is a completely other beast. Especially when there is so much existing experience not only for Android but also Linux kernel expertise.

My personal opinion may be dark but I feel that it comes down to licensing and an attempt at increasing vendor lock-in by moving away from Linux; that Google went window shopping and happened upon what became the basis of Zirkon. But this is speculation. What I would like to know is if there is any real technology that brings tangible benefit to all of this work when we already have the venerable Linux kernel available to us?

I would also like to highlight the following source for your reference:

https://fuchsia.googlesource.com/zircon/+/master/docs/concepts.md

I am an applications programmer and don't understand what the benefit is of Zircon's kernel as a design and welcome being educated on how it compares to existing architectures. If Google thinks that it is worthy as the successor of Android's Linux kernel then I feel that there are probably tangible benefits being brought to the table that I am just too inexperienced to appreciate.

From what I understand you are asking what are the technical benefits of zircon over linux?

First of all zircon is a micro kernel as opposed to the linux monolithic kernel. So lets look at some of the advantages of an microkernel over a monolith:

Segmentation, a micro kernel has a very segmented model and drivers live outside of the kernel. That means you have more control over what those pesky vendors put into your kernel to slow it down. Security is increased because you can protect the core of the kernels functions from god knows what monster code the vendors wanna chuck in there as drivers.
Size, a micro can be way way smaller in size and together with the modularity of the micro kernel can help so you have the same kernel on everything from your phone, laptop to a IoT thermometer.
Speed, although in practice you have a lot of microkernels that are slower than monoliths because all the communication between the pieces of the kernel create a lot of overhead, you could have speedier communication with things like File I/O, network traffic and other components by the lack of context switching between kernel space and user space (think >10Gbps networks).
Control over updates. One of the biggest problem with Android is fragmentation, if you wanna build an app you have 839274326 versions of Android out there, for which version do you build your app? Also you have vendors not applying patches because they need to build their version with all the modifications they put in. If you had a really segmented core that you could update without affecting the vendor modifications that would be a big win for Google.
Real-time operation, they probably want a pure real time implementation because it goes well with their data collection needs.


Why computer take long time to open huge text files? Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be opened very fast.

Why the computer doing this ? What is the difference between the two operations?

The difference would be between loading the complete file into memory and reading the file part-by-part as you need each part.

If I open a file in some applications I am asking for it to be fully loaded into memory all in one go.

If I play a movie file or DVD in most player applications the applications will be structured to just fetch data as it needs it, not all at once.

There are different ways to open files and devices in operating systems and they are not all the same.


How to I get a TM with lowest index? I'm struggling to understand this question:

  Give an encoding of the Turing machine with lowest index that accepts anything but the empty set.

I know what an encoding of a Turing Machine is. But my professor didn't explain what the index of a Turing machine is and how I know that it is lower or higher? Can someone explain what lowest index is and how would I go about this problem?

If I understand your question correctly, then it simply asks for the TM with the encoding who is ordered first in the lexicographic ordering.

As you surely know, many TMs perform the same task.
Look at all the TMs that accept anything but empty set. Look at the encodings of all of those. Each encoding is simply a string. If you write all those string ordered using the lexicographical ordering (like in the dictionary), which string comes first? That should be your answer.


Algorithms for elementary operations using other elementary operators The question asks to provide an algorithm to compute

$(i)$ The product of $n$-bit numbers using
reciprocation operation and addition operation but not using multiplication
and squaring.

$(ii)$ The square of a polynomial of degree $n−1$ using only
reciprocation and addition operation but not using multiplication
and squaring.

$(iii)$ The product of two $n − 1$ degree
polynomials using only squaring and addition operations but not using multiplication and reciprocation operations

All the operations stated above are on $n$-bit integers.

My try: The question asks to express some operator in terms of other elementary operators , so for eg. for (i) I tried writing $(\frac{1}{A} + \frac{1}{B})^{-1} = \frac{AB}{A+B}$, but to get $AB$,  I still have to multiply LHS by $A + B$. I think I can do $(ii)$ if I do $(i)$ as a polynomial is similar to a n-bit integer if you consider the bits as $(a_ix^i)$. I don't have an idea for $(iii)$ yet.

Throughout this answer, when we say we will be using some operations, it implies that no other operations is allowed. We also assume 1 is available as an operand.

The above clarification is considered as an improvement of original statement of problems. There will be further modification/clarification of the original problems, which have to be made because of the ambiguity of the original problems.

Here is the answer to part (i)

  Part (i). The product of two non-zero numbers using only reciprocation operation and subtraction operation.

Please note I have replaced by addition by subtraction; otherwise, it is impossible. Also I removed the specification of $n$-bits, which seems distracting and harmful; otherwise, $\dfrac13$ is problematic. I have also added the condition that the numbers are non-zero. Otherwise, we have to add an operation that checks whether a number is non-zero and acts accordingly. Also 1 have to be available. Otherwise, we cannot produce 1, which is needed in the final operation.

Let the two non-zero numbers are $A, B$.

we get addition by $X+Y=X-((Y-Y)-Y)$.
we get 4=1+1+1+1.
we get $X\to \dfrac {X^2}4$ by $\dfrac {X^2}4=X+\dfrac1{\dfrac1{X-4}-\dfrac1X}$.
We get multiplication by $AB=\dfrac{(A+B)^2}4-\dfrac{(A-B)^2}4$.

This answer at mathoverflow uses division by 2 or multiplication by $\dfrac12$ without explanation, which can be considered as a minor flaw. In fact, we can do division by 2 as $\dfrac A2=\dfrac1{\dfrac1A+\dfrac1A}$.

  Part (ii). The square of a polynomial with given coefficients using only reciprocation and subtract operation.

Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, this part can be done easily as a consequence of part (i).

  Part (iii). The product of polynomials with given coefficients using only squaring and subtraction operations and division by 2.

We get addition by $X+Y=X-((Y-Y)-Y)$. We get multiplication by $XY=\dfrac{(X+Y)^2-X^2-Y^2}2$. Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, we can compute the product of two polynomials.

Note that division by 2 is needed. Otherwise, it can be proven that it is not possible to do multiplication although we have $2XY=(X+Y)^2-X^2-Y^2$.


What is the time complexity of a binary multiplication using Karatsuba Algorithm? My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity.

In general, the Karatsuba Multiplication is said to have a time complexity of O(n^1.5...).
The algorithm assumes that the addition and subtraction take about O(1) each. However, for binary addition and subtraction, I don't think it will be O(1). If I'm not mistaken, a typical addition or subtraction of two binary numbers takes O(n) time.

What will be the total time complexity of the following program then that multiplies two binary numbers using Karatsuba Algo that in turn performs binary addition and subtraction?

long multKaratsuba(long num1, long num2) {
 if ((num1>=0 && num1<=1) && (num2>=0 && num2<=1)) {
   return num1*num2;
 }

 int length1 = String.valueOf(num1).length(); //takes O(n)? Not sure
 int length2 = String.valueOf(num2).length(); //takes O(n)? Not sure

 int max = length1 > length2 ? length1 : length2;
 int halfMax = max/2;

 // x = xHigh + xLow
 long num1High = findHigh(num1, halfMax); // takes O(1)
 long num1Low = findLow(num1, halfMax); // takes O(1)

 // y = yHigh + yLow
 long num2High = findHigh(num2, halfMax); // takes O(1)
 long num2Low = findLow(num2, halfMax); // takes O(1)

 // a = (xHigh*yHigh)
 long a = multKaratsuba(num1High, num2High);

 // b = (xLow*yLow)
 long b = multKaratsuba(num1Low, num2Low);

 //c = (xHigh + xLow)*(yHigh + yLow) - (a + b);
 long cX = add(xHigh,xLow); // this ideally takes O(n) time
 long cY = add(yHigh,yLow); // this ideally takes O(n) time
 long cXY = multKaratsuba(cX, cY);
 long cAB = add(a, b) // this ideally takes O(n) time
 long c = subtract(cXY, cAB) // this ideally takes O(n) time

 // res = a*(10^(2*m)) + c*(10^m) + b
 long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)
 long resC = c * (long) Math.pow(10, halfMax); // takes O(1)
 long resAC = add(resA, resC); // takes O(n)
 long res = add(resAC, b); // takes O(n)

 return res;
}

You're mistaken.
The analysis of the Karatsuba algorithm takes addition and subtraction into account.

If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ...,  run in $O(n)$.

Therefore you get the recursion $T(n) = 3 \cdot T(n/2) + O(n)$ for the complexity, which gives the following according to the Master theorem: $$T(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1.58...})$$

Fun fact: even if you assume that all the bitwise operations (addition, subtraction, ...) take $O(1)$, the code will still have the same complexity.
Since the number of calls to the three subproblems dominates the other work. But I doubt, that any book/lecturer would assume that the bitwise operations are constant, since the whole point of the algorithm is that you want to multiply large numbers.

Btw, you have some small errors in your pseudo-code/analyze.
E.g. here:

long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)

You want to multiply with a power of 2, to make it efficient (since you are working with binary numbers). And even corrected it will not run in $O(1)$, because you need to copy/move $O(n)$ bits. So this line will also run in $O(n)$.


Empirical studies about benefits of Q&A sites for programming I'm looking for empirical papers which investigate if a user can benefit from Q&A sites like Stack Overflow. I welcome any papers related to this topic, e.g:

an experiment, investigating if a specific task can be executed faster,
an analysis, investigating if a user understands the solutions on Q&A sites or if he just does copy&paste without thinking about it,
a comparative analysis of the code quality of users with access to Q&A sites in contrast to users without internet access (but just offline documentation of APIs).

There was a presentation on ICSE 2011, at the New Ideas and Emerging Results track, entitled "How do programmers ask and answer questions on the web?". They only had initial results, but they sounded very interesting and promising. Maybe you could contact the authors if you need more info (they're from the Dept. of Comput. Science, University of Victoria, Victoria, BC, Canada). Here is the full reference:

Treude, C.; Barzilay, O.; Storey, M. How do programmers ask and answer questions on the web?. In Proc. of the 33rd International Conference on Software Engineering (ICSE), 2011.

UPDATE: This paper was just mentioned at the Stack Exchange blog:

Chris Parnin, Christoph Treude, Lars Grammel, Margaret-Anne Storey. Crowd Documentation: Exploring the Coverage and the Dynamics of API Discussions on Stack Overﬂow. Georgia Institute of Technology, Tech. Rep, 2012. [PDF]


Vertex Cover, Hardness of Approximation In chapter of Hardness of Approximation in V. Vazirani's book it says:

For establishing a hardness of approximation result for, say, the vertex cover problem, PCP theorem is used to show the following polynomial time reduction. It maps an instance φ of SAT to a graph G = (V,E) such that
• if φ is satisfiable, G has a vertex cover of size ≤ 2/3*|V |, and
• if φ is not satisfiable, the smallest vertex cover in G is of size >
α· 2/3*|V |,

Next line it claims:

Claim 29.1 As a consequence of the reduction stated above, there is no polynomial time algorithm for
vertex cover that achieves an approximation guarantee of α, assuming P
≠ NP. (α>1)

I couldn't understand that claim, while in previous chapters it says Vertex Cover have 2-approximation algorithm (with Maximal matching).
Could anyone explain what does it means? How it obtained 2/3*|V|? and Why it said there is no α approximation while in previous chapters it proposed ones?

We can proof this claim by contradiction. If there exists an α-approximation algorithm for Vertex Cover, we will be able to use it for solving SAT problem in polynomial time and it's a contradiction by giving P≠NP.

We assume that there exists a gap introducing reduction that converts an instance of SAT to an instance of Vertex Cover giving:

• if φ is satisfiable, OPT(VC) ≤ 2/3 * |V|, and

• if φ is not satisfiable, OPT(VC) > α * 2/3 * |V|.

We can use this reduction and convert φ to I(VC) in polynomial time, then use the α-approximation algorithm for Vertex Cover in polynomial time and calculate objective function value (we call it f) for it.

As we know value of f stands between two bounds:

OPT(VC) ≤ f ≤ α*OPT(VC)

After that, we can use f to make a decision about φ satisfaction state:

If f ≤ α * 2/3 * |V|, then yes, else no.

We claim that if f is less than α * 2/3 * |V|, φ should be satisfiable because if φ isn't satisfiable, f can't be less than α * 2/3 * |V| which is lower bound to OPT(VC) (according to reduction assumptions) and objective function value can't be less than optimum.

Also we claim that if f is greater than α * 2/3 * |V|, φ shouldn't be satisfiable because if φ is satisfiable, it violates the approximation inequality. (f ≤ α*OPT(VC))


Why is Radix Sort $O(n)$? In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list.

Now if we have list of $n$ numbers we need $\log n$ bits to distinguish between those number. So number of radix sort passes we make will be $\log n$. Each pass takes $O(n)$ time and hence running time of radix sort is $O(n \log n)$

But it is well known that it is linear time algorithm. Why?

if we have a list of $n$ numbers we need $\log n$ bits

No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general.

If the numbers are all distinct, then $\log n \ge k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the complexity of radix sort is $\Theta(n \, k)$ where $n$ is the number of elements to sort and $k$ is the number of bits in each element.

To say that the complexity of radix sort is $O(n)$ means taking a fixed bit size for the numbers. This implies that for large enough $n$, there will be many duplicate values.

There is a general theorem that an array or list sorting method that works by comparing two elements at a time cannot run faster than $\Theta(n \log n)$ in the worst case. Radix sort doesn't work by comparing elements, but the same proof method works. Radix sort is a decision process to determine which permutation to apply to the array; there are $n!$ permutations of the array, and radix sort takes binary decisions, i.e. it decides whether to swap two elements or not at each stage. After $m$ binary decisions, radix sort can decide between $2^m$ permutations. To reach the $n!$ possible permutations, it is necessary that $m \ge \log (n!) = \Theta(n \log n)$.

An assumption in the proof that I did not write out above is that the algorithm must work in the case when the elements are distinct. If it is known a priori that the elements are not all distinct, then the number of potential permutations is less than the full $n!$. When sorting $k$-bit numbers, it is only possible to have $n$ distinct elements when $n \le 2^k$; in that case, the complexity of radix sort is indeed $\Omega(n \log n)$. For larger values of $n$, there must be collisions, which explains how radix sort can have a complexity that's less than $\Theta(n \log n)$ when $n \gt 2^k$.


$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard part. One way to do it would be to reduce a known NP-complete problem to $U$. Another way would be to find a general way to reduce any NP problem to $U$ in polynomial time.

I've found some online proofs for doing this. They all seem to reduce some arbitrary NP problem, say $A$, to $U$ by using the polynomial bound for the nondeterministic polynomial-time decider for $A$. So let $A$ be some NP problem, and let $N$ be its non-deterministic decider which runs in $n^{k}$ time for some $k$. Then output $\langle N, x, \#^{k} \rangle $. The issue I have with this solution is, how do you know what $k$ is? You know that $A$ is NP, so there is a non-deterministic polynomial time decider for it, but how do you know the actual degree of that polynomial? It seems false to assume it is already known, surely one should have to compute it manually to obtain a reduction. How could you compute the degree of this polynomial in polynomial time? The existing proofs seem to gloss over this critical fact.

Finding the running time of a given Turing machine is undecidable. Luckily, you don't need to find the actual degree. You only need to show the existence of a reduction from $A$ to your language, not to construct a procedure that given a description of $A\in\mathsf{NP}$ (say, as the encoding of its verifier), will output a reduction from $A$ to your language.

Think of it this way, let $\{f_n\}_{n\in\mathbb{N}}$ be a sequence of functions, where $f_i(x)=\left(M_A,x,\#^{|x|^i}\right)$. One of the functions in this sequence is the reduction you're looking for, and I don't need to point out which one (note that I can specify it in terms of the degree of the polynomial in the running time of $M_A$).


Operations with Asymptotic Notations I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve:
$$\frac{\Theta(n)}{o(n)} =?$$
There are not many combinations and I was wondering if anyone could help me.

Classical resources: CLRS Introduction to Algorithms, 3d edition, pages 47, 1150,  Donald Ervin Knuth TAOCP, 1997, volume 1, page 107.
More formal good resource for such cheatsheet you can find  in Jeremy Avigad and Kevin Donnelly article.
And, at end, for non negative case, let me bring some well known properties:
$$ \begin{array}{l}O(f ) + O(g) = O(f + g) =O(\max(f,g))\\
C=Const. \Rightarrow C\cdot O(f) = O(C \cdot f) = O(f) \\
 O(f )  O(g) = O(f g) \\
O( O( f)) = O(f ) \\
 g \ne 0 \Rightarrow \frac{O(f)}{g} = O\left(\frac{f}{g}\right)
\end{array}
$$
For your case: $f \in \frac{\Theta(n)}{o(n)}$, if an only if $\lim\limits_{n \to \infty}f(n)=\infty$.


Why escape and escape in byte stuffing? Denoting the two special bytes as FLAG and ESC, and any other as X, where FLAG denotes the start and end of the message and ESC is used to escape any flags within the original message,
if the original message was for example,

X FLAG ESC FLAG FLAG ESC ESC FLAG X X

this can be byte stuffed as,

FLAG X ESC FLAG ESC ESC FLAG ESC FLAG ESC ESC ESC FLAG X X FLAG

where the added bytes are in bold. I don't think it is necessary to escape the escapes. In the receiving side, only FLAG comming after ESC together will be changed to FLAG and when any other bytes come after ESC, that ESC will be ESC as is. For example, if you see the ESC byte at the 5th byte of the received message, since ESC comes after ESC, the 5th ESC will be interpreted as ESC and nothing more. I thought about this, and I think it also works this way. But every resources I can find including my networks book says that an escape should be escaped as well as the flags when originally contained in the message. Why so?

Think of a message (ending in) FLAG. You need to escape it, of course, so your message looks like: FLAG (rest) ESC escaped-FLAG FLAG

Now think of a message (ending in) ESC. If you do not escape it, your message looks like this: FLAG (rest) ESC FLAG

Now, “ESC FLAG” and “ESC escaped-FLAG” are undistinguishable. So, that last ESC needs to be escaped.

Now you can go backwards, again and again, until you find that, if one ESC has to be escaped, they all need to be escaped, from the first one.


Is it possible to design a Turing Machine without extra symbols for this language? Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?

Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following:

If the current symbol is $\varepsilon$: accept
If the current symbol is $1$: reject
Delete the current symbol (by writing $\varepsilon$)
Move right until you find the next $\varepsilon$ symbol
Move left (the head is now on the last non-blank symbol, if any)
If the current symbol is $\varepsilon$: reject
If the current symbol is $0$: reject
Delete the current symbol (by writing $\varepsilon$)
Move left until you find the previous $\varepsilon$ symbol
Move right (the head is now on the first non-blank symbol, if any)
Repeat


Cases of Master Theorem Suppose that we have  $ \\ T(n)=\left\{\begin{matrix}
c, & \ \text{if } n<d\\
aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d
\end{matrix}\right.$

The Master theorem is the following:

If $f(n)=O(n^{\log_b a- \epsilon})$, then $T(n)= \Theta(n^{\log_ba})$
If $f(n)= \Theta(n^{\log_b a} \log^k n)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$
If $f(n)=\Omega(n^{\log_b a+ \epsilon})$, then $T(n)= \Theta(f(n))$, provides $af\left(\frac{n}{b} \right) \leq \delta f(n)$ for some $\delta<1$ for all $n \geq d$.

Proof:

Using iterative substitution, let us see if we can find a pattern:

$$T(n)=aT\left( \frac{n}{b}\right)+f(n)=a \left(aT \left(\frac{n}{b^2} \right) +f\left( \frac{n}{b}\right)\right)+f(n)= \dots\\= a^{\log_bn}T(1)+ \sum_{i=0}^{(\log_bn)-1} a^i f\left( \frac{n}{b^i} \right)=n^{\log_b a} T(1)+ \sum_{i=0}^{(\log_b n)-1} a^i f\left(\frac{n}{b^i} \right)$$

We then distinguish the three cases as

The first term is dominant
Each part of the summation is equally dominant
The summation is a geometric series

Don't we have to explain further which case correponds to which of the following cases

The first term is dominant.
Each part of the summation is equally dominant.
The summation is a geometric series

and justify why it is like that? How could we justify it?

The three cases correspond exactly to the three cases in the statement of the theorem. Let's consider them one by one. Suppose for simplicity that $T(1) = 1$.

Case 1. Suppose that $f(n) = n^\delta$, where $\delta < \log_b a$. Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta.
$$
Since $\delta < \log_b a$, we have $b^\delta < a$ and so $a/b^\delta > 1$. Therefore
$$
\sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i =
\left(\frac{a}{b^\delta}\right)^{\log_b n} \sum_{j=1}^{\log_b n} \left(\frac{b^\delta}{a}\right)^j = \Theta(n^{\log_b a - \delta}),
$$
since the geometric series $\sum_j (b^\delta/a)^j$ converges, and $\log_b (a/b^\delta) = \log_b a - \delta$. We conclude that
$$
T(n) = n^{\log_b a} + \Theta(n^{\log_b a - \delta} n^\delta) = \Theta(n^{\log_b a}).
$$
(So it is not quite true that the first term is dominant.)

Case 2. Suppose that $f(n) = n^{\log_b a}$ (this is the case $k = 0$; the case $k > 0$ is similar though slightly more complicated). Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^{\log_b a}.
$$
This time $a = b^\delta$, and so each summand is equally dominant, leading to
$$
T(n) = n^{\log_b a} + (\log_b n) n^{\log_b a} = \Theta(n^{\log_b a} \log n).
$$

Case 3. Suppose that $f(n) = n^\delta$, where $\delta > \log_b a$. Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta.
$$
Since $\delta > \log_b a$, we have $b^\delta > a$, and so $a/b^\delta < 1$. Therefore the geometric series $\sum_i (a/b^\delta)^i$ converges, implying that
$$
T(n) = n^{\log_b a} + \Theta(n^\delta) = \Theta(n^\delta).
$$

These proof sketches serve to explain that proof hints. However, they're not a complete proof, for two reasons. First, I assumed that $f$ has a specified form rather than a specified order of magnitude. Second, there is a tacit assumption that $n$ is a power of $b$. With more work we can take these points into account and prove the complete theorem. (A third and more minor point is the base case – you have assumed a base case of $1$, whereas the theorem calls for an arbitrary base case.)


Maximum number of states in NFA concluded from the converted DFA Assume I have a DFA with 20 states, is it possible to know the maximum number of states of the NFA which it was converted from?

I know that the minimal number of states would be 5 (because you cannot have created a DFA with 20 states from an NFA with 4 states).

But I don't really understand how can I know if there's a maximum that can be determined.

No, because there is no maximum.  There are infinitely many NFA's that are all equivalent and accept the same language.  For instance, you can take any NFA you think it might have come from and add some extra disconnected states, and the new NFA will also have the same language and thus could correspond to the same DFA.

(Your only hope is that if you know exactly what conversion procedure was used, and if the conversion procedure retains useless states and forms a bijection from NFAs to DFAs, then maybe.  But in practice I would not expect ordinary conversion procedures to have that property.)


proving existence of TM that accepts the next language I have an idea of how to approach the problem, but I'm not sure about it.
Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run uses endless cells of the tape.
However, I am not sure how I can use the number of states and what I should check.
What confuses me is that entering an endless loop does not necessarily require the use of endless cells of the film.
$L_k=\{<M>| \,M\,\,\,is\,\,a\,\,TM\,\,that\,\,uses\,\,at\,\,most\,\,k\,\,tape\,\,cells\,\,\,when\,\,\,running\,\,\,on\,\,\,\epsilon\}$
prove that:
$L^*=\bigcup\limits_{k\,\in\,\mathbb{N}} L_k\,\in\,\,\,RE\setminus R$

The language $L^*$ consists of all Turing machines $M$ which either eventually halt or repeat a configuration. For each machine $M$, by simulating the machine you can easily observe that one of these possibilities has happened.


What is the difference between oblivious and non-oblivious merging, sorting etc Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?

Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as sorting net_ is oblivious, because it always compares the same elements disregarding data it gets, while Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data. Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from $n$ steps to $n^2$ (for example).

This definition for cache is very similar, it means that it takes advantage of cache independently of its size (cache length).


Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation) We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:

$$T(n)=\begin{cases}
0 &\text{ if } n=0,\\
3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.}
\end{cases}$$

Prove that for each $n\in\mathbb{N}_0$: $T(n) \leq 8n^2$

How can I prove such statement? I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. Any help appreciated

I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach.

You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}_0$.

Since this is a proposition on natural numbers, we should use mathematical induction. Because $T(n)$ is related to $T(\lfloor n/2\rfloor)$, we will use strong induction.

Base case. $n=0$:   $T(0)=0\le 8\cdot0^2$.

Inductive step. Assume for all $k < n$, prove for $n >0$:

$$T(n)=3T(\lfloor{n/2}\rfloor) + 2n^2\le3\cdot8(\lfloor{n/2}\rfloor)^2 + 2n^2\le24(n/2)^2+2n^2=8n^2$$

Note that since $\lfloor{n/2}\rfloor\lt n$, we can apply the induction hypothesis to obtain $T(\lfloor{n/2}\rfloor)) \leq 8(\lfloor{n/2}\rfloor)^2$.

Exercise 1. Show that $T(n) \lt 8n^2$ for all $n >0$.

Exercise 2. What is the largest $n$ such that $T(n) \le 7n^2$?

Exercise 3. Show that $\dfrac{T(n)}{n^2}\to8$ when $n\to\infty$.


Djikstra's algorithm to compute shortest paths using at least k edges I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s to vertex t using at least k edges but less than 20. No vertex may be repeated in a path.

I am aware of this problem: Dijkstra's algorithm to compute shortest paths using k edges?

That problem wants to find the shortest paths using at most k edges.

My current idea is to create the product graph via V' = V x {0, 1, 2, ..., 20} and then ignore any shortest paths from (s, 0) to (t, n) where n < k.  However, because the product construction essentially duplicates nodes, I am not aware of a way to ignore duplicate vertices in the path-finding algorithm.

P.S. If k were very large, say, k = |V|, wouldn't this be the Hamiltonian path problem and therefore NP-complete?

Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice.

Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in polynomial time for $k=n-1$ and thus find a path that visits eeach vertex in $V$ exactly once. In other words, we can "solve" Hamiltonian Path.

If you know in advance that $k \leq 20$ then you can exhaustive search all paths of length at most 20, and therefore solve for small $k$.

An exhaustive search, at worst, is to search every vertex order starting from $s$ that ends in $t$ (corresponding to existing edges), so in total you will search:
 $$(n-1)(n-2)(n-3)...(n-20) = O(n^{20})$$


What is the name of this problem in Computer Vision? My google skills have failed me during research for a college project. Our task is write a program that describes an image in spacial terms, e.g. "Cat on the left of a chair", or for a simple image "Two triangles over a large circle, and a sqaure underneath it".
Suppose that after analysing an image I have a set of objects, with names, coordinates, sizes, orientations. I want to transform this set into sentences like above, i.e. describing relative positions, overlaying and so on.
Unfortunately, I cannot find anything on this subject. "Scene decription" means 3D graphics description languages. "Image description" is about the nouns and, recently, the verbs describing an image. It seems that I have the wrong keywords.
I'd much appreciate any hints about what to look for. Links to scientific papers to peruse (if you have any at hand) would be great too.

This seems to be exactly scene description as described, for example, in Timor Kadir's thesis:

  Broadly speaking, the aim of scene description is to arrive at a set of descriptions of a real world scene which sufficiently capture the component parts of the scene, their positions, poses, motions and interactions. (p. 3)


How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable? So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show the following language is decidable

$L=\{\langle G,w \rangle $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derived in $G$ by at least 2 differents derivations trees. $\}$

In other words, find an algorithm that when given a grammar that is in normal form of Chomsky and a word $w$, it concludes after a finite number of steps if yes or no $w$ can be derived by two derivations trees.
Here's my attempt (correct me if this is wrong) :
Entry : $\langle G,w \rangle $

Try every derivations in $G$ of length $2|w| -1$.
If two derivations generate $w$ stop and accept $\langle G,w \rangle $. Else stop and reject $\langle G,w \rangle $.

Question 2 :
Show that this language is Turing recognizable $K = \{\langle G \rangle : G$ is a grammar in normal form of Chomsky and $G$ is ambiguous ( can have two derivation tree for same word).$\}$ In other words, give an algorithm that when given an grammar in normal form of Chomsky, it returns "true" if $G$ is ambiguous and return "false" or doesn't stop when $G$ is not ambiguous. ( Give an answer based on the algorithm used in question 1)
My reflexion on question 2 :
For this part i am kinda lost, i know that we will use algorithm of question 1 to be able to return true but for the infinite loop part i am not sure on how to say this.
I am also not sure if i can use a word "$w$" since our entry is a grammar $G$.
Entry : $\langle G \rangle$

Apply algorithm from question 1 if it returns true,  return true. ( Because question 1 basically confirm that the CNF is ambiguous).

note sure how to handle the rest for it to loop.

Your answer to question 1 is nice and correct.

On question 2, of course, you can use a single word $w$ to test the grammar $G$. However, it is not enough to use just one word, since the grammar could be ambiguous on another word.
Well, we can use all words to test the grammar.
Here is the high-level description of a Turing machine $R$ that recognizes $K$.

Loop through all words:

for each word $w$, try every derivation in $G$ of length $2|w|−1$.
If two derivations generate $w$ stop the machine and accept $G$.

There are many ways to loop through all words. For example, we can fix an arbitrary order of all terminals and iterate by short-lexicographic order.
Note that when $G$ is not ambiguous, $R$ will run forever. That means $R$ is not a decider for $K$. In fact, no Turing machine can decide $K$ since $K$ is undecidable.


Finding a minimum set of dependencies in a cycle-filled dependency graph I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies.

My goal is to find the smallest subset of targets that, if I remove all of their dependencies, breaks all of the cycles, leaving me with a buildable dependency tree.

This sounds very much like a well-understood graph problem to me, but I can't figure out which one. I'm afraid it also smells like an NP complete problem, but I'm hoping there's a good trick that I've missed. Can someone suggest what the name of this problem might be so that I can read a bit more about it, or what a good approach to solving it could be?

Decompose your graph into strongly connected components.  Now each strongly-connected component (SCC) of size $>1$ contains a cycle.

Let $G=(V,E)$ be the dag of SCCs obtained by this decomposition.  Sometimes $G$ is called "the metagraph".  Let $S \subseteq V$ be the set of SCCs of size $>1$.  Now our algorithmic problem is as follows:

  Given the dag $G$ and the set $S$, find a minimum-size set $T \subseteq V$ such that for every $v \in S$, there's a path from $v$ to some vertex of $T$.

The rest of the answer below is incorrect, but I'll leave the problem statement above in case it helps someone else find a clean algorithm.

This problem can be solved using a network flow algorithm.

In particular, this problem can in turn be rephrased as something akin to a minimum-cut problem: if we add a source vertex $s$ with an edge to each vertex of $S$ and a sink vertex $t$ with an edge from each vertex of $T$ to $t$, we want to find a minimum-size set of vertices that completely disconnect $s$ from $t$.  Notice that this isn't quite the normal minimum-cut problem, because here we care about minimizing the number of selected vertices rather than minimizing the cost of the edges that cross the cut, but it's close.

Here's how we can solve this problem.  For each vertex $v \in V$, we add two vertices $v_\text{in},v_\text{out}$, and we add an edge with cost 1 from $v_\text{in}$ to $v_\text{out}$.  Also, we replace each edge $(v,w) \in E$, with the edge $(v_\text{out}, w_\text{in})$, and we make this edge have cost $\infty$.  We add a source vertex $s$ and, for each $v \in S$, we add a source vertex $s$ and an edge of capacity $\infty$ from $s$ to $v_\text{in}$.  We also add a sink vertex $t$ and, for each $v \in V$, we add an edge of capacity $1$ from $v_\text{out}$ to $t$.  Let $G'=(V',E')$ be the resulting graph.

Finally, we find a minimum $(s,t)$-cut in $G'$.  This can be done by using a standard network flow algorithm to compute the maximum $(s,t)$-flow, and then using the Ford-Fulkerson min-cut/max-flow theorem to reconstruct a minimum $(s,t)$-cut.  Suppose the cut is $(U,V'\setminus U)$, where $s \in U$ and $t \notin U$.  Then for each vertex $v \in V$ such that $v_\text{in} \in U$ and $v_\text{out} \notin U$, we add $v$ to $T$.  This gives us a set $T$ of vertices that, in $G$, disconnect $s$ from $t$, and by construction, the size of $T$ is minimal.


Turing Machine that both halts and loops in NP This is in regards to a specific TM:

$UNIQUE: \{$ TM | TM loops on at least an input, and TM also halts on at least one input $\}$

This is a play on the Halting Problem, where it basically combines $HP$ as well as $\overline{HP}$ into one. We know that $HP$ is NP-Hard, we also know that $\overline{HP}$ is NP-Hard, but would combining the two also be NP-Hard? How would the proof for this go?

It's not only NP-hard, it's undecidable!

For the easy proof, use Rice's Theorem. This is a non-trivial semantic property, so it's undecidable (and thus NP-hard). Done.

For a more interesting proof:

For any Turing machine $T$, let's define a new machine $Z_T$ like this:

  $Z_T$ looks at the first symbol on the tape. If it's a 1, it moves to the right and runs $T$ on the remainder of the tape. If it's anything else, it loops forever.

Now, suppose there exists a machine $U$ that can decide UNIQUE. I'm going to use this machine to decide the "Any-Input Halting Problem" ("is there any input that will make this machine halt?"), which is known to be undecidable (and NP-hard).

For any Turing machine $T$ that you give me, I can create a $Z_T$. Then I run $U$ on $Z_T$. I know that, for the input 0, $Z_T$ will loop forever. I also know that $Z_T$ halts on input 1XYZ only if $T$ halts on input XYZ. Therefore, $U$ will accept $Z_T$ if and only if $T$ halts on some input.

Since we know the Any-Input Halting Problem can't be decided, this hypothetical $U$ can't exist. Therefore UNIQUE is also undecidable, and anything undecidable is also NP-hard.


Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$ From Computational Complexity - A Modern Approach, it is claimed in a remark that the following holds true.

Remark 5.5
Note that $\mathbf\Sigma_1^p = \mathbf{NP}$ and $\mathbf\Pi_1^p = \mathbf{coNP}$. More generally, for every $i \geq 1$, $\mathbf\Pi_i^p = \mathbf{co\Sigma}_i^p = \{ \overline{L} : L \in \mathbf\Sigma_i^p\}$. Note also that $\mathbf\Sigma_i^p \subseteq \mathbf\Pi_{i+1}^p$, and so we can also define the polynomial hierarchy as $\cup_{i>0} \mathbf\Pi_i^p$.

However, I am having trouble understanding this. Similar claims are made in lecture notes found on the web, but none of them give a proof since they are all left as exercise. Would it be possible to prove this using NTM instead of verifiers?

It is a direct consequence of the definition of $\textsf{PH}$.

Remember:

$\qquad \Sigma_i^P = \textsf{NP}^{\Sigma_{i-1}^P}$

$\qquad \Pi_i^P = \textsf{coNP}^{\Sigma_{i-1}^P} $

What we want to prove is:

$\qquad \bigcup_{i>0}\Sigma_i^P = \bigcup_{i>0}\Pi_i^P $

We have:

$\qquad \Sigma^P_i \subseteq \textsf{coNP}^{\Sigma^P_i} = \Pi_{i+1}^P$

$\qquad \Pi^P_i \subseteq \textsf{NP}^{\Pi^P_i} = \textsf{NP}^{\Sigma_i^P} = \Sigma^P_{i+1}$

Taking the union yields:

$\qquad \bigcup_{i>0} \Sigma^P_{i} \subseteq \bigcup_{i>0} \Pi^P_{i} \subseteq \bigcup_{i>0} \Sigma^P_{i}$

which is exactly our goal.


Consensus/ranked ordering algorithm Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote? For example, if 3 people vote and their votes are [1, 2, 3, 4, 5], [2, 1, 3, 4, 5], and [1, 2, 3, 5, 4], then the consensus ordering would be [1, 2, 3, 4, 5]. Ideally the algorithm would support votes of partial orderings as well, such as [2, 5, 4].

I'm pretty sure I can extend the ranked voting system to produce a complete ordering of the "candidates," but I'm wondering if there's already an algorithm to do this.

I have both good news, and bad news.  Not only is there a way to do it; there are many candidate ways to do it.  For instance, you could use IRV, Condorcet voting, Borda count, or many other schemes.  See https://en.wikipedia.org/wiki/Ranked_voting and https://en.wikipedia.org/wiki/Social_choice_theory.

Unfortunately, there are also negative results showing that no scheme provides all of the properties that we might desire.   See Arrow's theorem: https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem and https://en.wikipedia.org/wiki/Condorcet_paradox.


Why is a quantum computer not capable of solving more problems than a classical computer? On the Wikipedia page for quantum algorithm I read that

  [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.


Can Tarjan's SCC algorithm find satisfying assignment to just 'any' digraph? Is Tarjan's algorithm capable of finding satisfying assignment to any digraph consists of variables (vertices) and implications (edges)? I know that it solves implication graphs constructed by 2SAT clauses, but I wonder if the algorithm can handle the digraphs which cannot be expressed as 2SAT clauses. Let me clarify this by the following examples:

(a+b)(~b+c) translates to the following
(~a -> b),
(~b -> a),
(b -> c),
(~c -> ~b)
It is OK. But how about the following implications:
(a -> b),
(b -> ~c)
There is obviously no corresponding set of 2SAT instances. Does Tarjan's algorithm find a satisfying assignment to this?

You have a faulty premise.  There is a 2SAT instance corresponding to $(a \implies b) \land (b \implies \neg c)$.  Just note that $x \implies y$ is equivalent to $\neg x \lor y$.  Then you can transform the original formula to $(\neg  a \lor b) \land (\neg b \lor \neg c)$, which is obviously a 2SAT instance.

That algorithm you refer to can solve 2SAT, but it can't solve anything stronger as is.  However, there are related graph-based algorithms to test satisfiability of arbitrary conjunctions of Horn clauses.


Ambiguity vs. context-sensitivity It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which admits ambiguities because the ambiguities will go away anyway once you evaluate your AST with attributes anyway. For this reason it is useless to invent an intractable CS grammar for your language.

This strongly associates ambiguities with context sensitivity in my mind. However, there is an expert in the field who states brazen faced that context sensitivity is absolutely irrelevant to ambiguity but supplies no support to ground his statement. Can you untangle the conflicting opinions by some light?

I cannot refrain from asking the same question in the following form. My mind is highly influenced by this description the of grammar type comparison in "Parsing Techniques: A Practical Guide"

  Type n grammars are more powerful than Type n+1 grammars, for n =
  0,1,2”, and one often reads statements like “A regular (Type 3)
  grammar is not powerful enough to match parentheses”. It means that
  more powerful grammars can define more complicated boundaries between
  correct and incorrect sentences. Some boundaries are so fine that they
  cannot be described by any grammar (that is, by any generative
  process). This idea has been depicted metaphorically in Figure 2.33,
  in which a rose is approximated by increasingly finer outlines. In
  this metaphor, the rose corresponds to the language (imagine the
  sentences of the language as molecules in the rose); the grammar
  serves to delineate its silhouette. A regular grammar only allows us
  straight horizontal and vertical line segments to describe the flower;
  the result is a coarse and mechanical-looking picture. A CF grammar
  would approximate the outline by straight lines at any angle and by
  circle segments. The result is stilted but recognizable. A CS grammar
  would present us with a smooth curve tightly enveloping the flower,
  but the curve is too smooth: it cannot follow all the sharp turns, and
  it deviates slightly at complicated points; still, a very realistic
  picture results. An unrestricted phrase structure grammar can
  represent the outline perfectly. The rose itself cannot be caught in a
  finite description; its essence remains forever out of our reach.

  A
  more prosaic and practical example can be found in the successive sets
  of Java programs that can be generated by the various grammar types:

  The set of all lexically correct Java programs can be generated by a regular grammar. A Java program is lexically correct if there are no
  newlines inside strings, comments are terminated before end-of-file,
  all numerical constants have the right form, etc.
  The set of all syntactically correct Java programs can be generated by a context free grammar. These programs conform to the
  (CF) grammar in the manual.
  The set of all semantically correct Java programs can be generated by a CS grammar. These are the programs that pass through a Java
  compiler without error.
  The set of all Java programs that would terminate in finite time when run with a given input can be generated by an unrestricted phrase
  structure grammar. Such a grammar would incorporate detailed
  descriptions of the Java lib and the Java run-time system.
  The set of all Java programs that solve a given problem cannot be generated by a grammar (although the description of the set is
  finite).

I see that CF can generate the syntactically valid programs and you need CS grammar to accommodate the semantics of the language. This more complete grammar can resolve if x(y) is a call of a function or type conversion. It will also iron out the associativity ambiguity in a+b+c telling that difference between (a+b)+c and a+(b+c) is immaterial. For this reason I think that CF -> CS also resolves ambiguities. Why telling that context sensitivity and ambiguity are orthogonal after that?

This is plainly wrong. The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem), and so can't be generated by any grammar.

Ambiguous context free grammars are hard to parse efficiently, compiler writers prefer unambiguous grammars (or use tricks in the parser to bypass ambiguities). If the underlying grammar is ambiguous, chances are that the attributed grammar won't give a unique meaning either.

A context free grammar is called ambiguous if there is a string generated by the grammar with two different derivation trees. Context sensitive grammars don't have any similar description of the derivation that is independent of the order of productions applied, so ambiguity doesn't make sense for them.


Prove that the 2-approximation of a modified local search algorithm for max-cut is tight Consider the following local search approximation algorithm for the unweighted max cut problem:
start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you can move 1 or 2 vertices from one side of the partition to the other, or switch between 2 vertices on opposite sides of the partition, in a way that improves the cut, do so.

I know that this algorithm is a 2-approximation algorithm. I want to prove that this approximation is tight. That is, the algorithm is not an $\alpha$-approximation algorithm for any $\alpha < 2$ .

I found an example for the tightness of the "regular" local search approximation algorithm of max-cut, where at each iteration, you can move only 1 vertex from one side of the partition to the other, and can't switch between two vertices on opposite sides. The example is of the complete bipartite graph $ K_{2n,2n} $. If the initial cut includes $n$ vertices from each side of the graph in each side of the partition, the cut will include half of the edges, while the optimal cut will include all of them. The "regular" algorithm will not be able to improve the cut from this initial position.

However, this example doesn't work for the algorithm described on top, because we can improve the cut by switching between two vertices from opposite sides of the partition.

Can someone please describe an example or a give clue for an example that can prove that the approximation is tight?
Thanks.

Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}$. You can verify the resulting graph is an example showing the approximation ratio of your algorithm is at least $2-1/n$, when the initial cut is $\left(\{u_1,\ldots,u_n,v_1,\ldots,v_n\},\{u_{n+1},\ldots,u_{2n},v_{n+1},\ldots,v_{2n}\}\right)$.


How to scale down parallel complexity results to constantly many cores? I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC:

  NC is the class of problems that can be solved by a parallel algorithm in time $O(\log^cn)$ on $p(n) \in O(n^k)$ processors with $c,k \in \mathbb{N}$.

We can assume a PRAM.

My problem is that this does not seem to say much about "real" machines, that is machines with a finite amount of processors. Now I am told that "it is known" that we can "efficiently" simulate a $O(n^k)$ processor algorithm on $p \in \mathbb{N}$ processors.

What does "efficiently" mean here? Is this folklore or is there a rigorous theorem which quantifies the overhead caused by simulation?

What I am afraid that happens is that I have a problem which has a sequential $O(n^k)$ algorithm and also an "efficient" parallel algorithm which, when simulated on $p$ processors, also takes $O(n^k)$ time (which is all that can be expected on this granularity level of analysis if the sequential algorithm is asymptotically optimal). In this case, there is no speedup whatsover as far as we can see; in fact, the simulated parallel algorithm may be slower than the sequential algorithm. That is I am really looking for statements more precise than $O$-bounds (or a declaration of absence of such results).

If you assume that the number of processors is bounded by a constant, then you are right that a problem being in NC does not mean much in practice.  Since any algorithm on a PRAM with k processors and t parallel time can be simulated with a single-processor RAM in O(kt) time, the parallel time and the sequential time can differ only by a constant factor if k is a constant.

However, if you assume that you can prepare a computer with more processors as the input size grows, then a problem being in NC means that as long as you can prepare more processors, running time will be “very short” or, more precisely, polylogarithmic in the input size.  If you think that this assumption is unrealistic, compare it to the assumption of unbounded memory: actual computers have only finite amount of space, but in the study of algorithms and complexity, we almost always assume that a computational device does not have a constant upper bound on space.  In practice, this means that we can prepare a computer with more memory as the input size grows, which is how we usually use computers in the real world.  NC models an analogous situation in parallel computation.


What is monograph and digraph in keyboard optimization problem? I have been working on Bangla keyboard optimization. I've taken this paper as a reference. In this paper they have introduce two terms monograph and digraph. But it is not clear how they have calculate these two things. In this paper it is written -

  A monograph is an isolated key which is struck in the process of typing a text. A digraph is a sequence of two consecutive keys hit in the process of typing a text. This idea allows the distinction between rules that concern the absolute position of a given key and the relative position of two consecutive keys.

What I am assuming that digraph is those two consecutive character that are used often in any language word. Like in English language ph, qu etc. But I can not understand what is monograph.

Therefore I would need a clear explanation about monograph and digraph and what is the method to calculate these in respect to keyboard optimization problem.

The article uses monograph to refer to a single key, say "e", in a position on the keyboard. In the interest of efficiency, you'd want the frequently-used letters to be in locations where a model typist would have to expend the least motion to strike. A digraph, on the other hand, would be two keys which would be struck in sequence, like the "in" which I typed a few characters ago. In this case, we would be looking for a keyboard layout which minimized the effort depending not just on the absolute positions of the characters, but on the relative positions of the pairs.


Biggest number of components in a graph? What is the biggest number of components in a graph that has 14 vertices and 44 edges?

Since total degree of all vertices in a graph equals to 2 * number of edges, I calculated that for 44 edges, 14 vertices together must have 88 degrees. 88 / 14 = 6, therefore each of them would have to be connected to other 6 vertices and we would still have 4 edges left. So, the only solution I see is using a full graph K10, where we'd have 90 edges ((n*(n-1))/2). We'd use 10 vertices and eliminate 2 edges. And the rest 4 vertices we would leave isolated, so we'd get 5 components all together.

Suppose that a graph having $n$ vertices and $m$ edges consists of $k$ connected components, say of sizes $n_1,\ldots,n_k$. Then
$$
m \leq \binom{n_1}{2} + \cdots + \binom{n_k}{2}.
$$
Conversely, given $n_1,\ldots,n_k$ summing to $n$ which satisfy this inequality, we can construct a graph with $n$ vertices, $m$ edges, and at least $k$ connected components. We conclude that the maximum number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that we can find $n_1,\ldots,n_k \geq 1$ summing to $n$ satisfying the inequality above.

This leads to the following question: given $k$, maximize $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ subject to the constraint that $n_1,\ldots,n_k \geq 1$ are integers summing to $n$. The key is the following observation:
$$
\binom{a+1}{2} + \binom{b-1}{2} - \binom{a}{2} - \binom{b}{2}  = a-b+1.
$$
This shows that as long as $n_i \geq n_j$, moving a vertex from $n_j$ to $n_i$ increases $\binom{n_i}{2} + \binom{n_j}{2}$. It follows that the choice of $n_1,\ldots,n_k$ maximizing $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ is $n_1=n-k+1$, $n_2=\cdots=n_k=1$.

We have proved: the maximal number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that $$ m \leq \binom{n-k+1}{2}. $$


Worst known case for log rank conjecture The log rank conjecture states that there is some universal constant $c > 0$ so that

$$CC(f) = O(\log^c \text{rk}\,(M_f))$$

where $f : X \times Y \to \{0, 1\}$ is a boolean function, $CC$ denotes the deterministic communication complexity, $M_f$ is the $|X| \times |Y|$ binary matrix associated to $f$, and $\text{rk}\,(M_f)$ is the rank of $M_f$ calculated over the reals. In the literature, it mentions that this $c$, if it exists, is at least $\log_3 6 \approx 1.631\ldots$, and attributes this to an unpublished result of Kushilevitz in 1994.  Does anyone know what example Kushilevitz uses to achieve this lower bound? I think it would be interesting to see what the worst case might be and it might give insight into how to solve the problem in general.

The function is described in a footnote in Nisan and Wigderson's paper On rank vs. communication complexity. It is

$$
E(z_1 \dots z_6) = \sum_i z_i - \sum_{ij} z_{i}z_{j} + \\z_1z_3z_4 + z_1z_2z_5 + z_1z_4z_5 + z_2z_3z_4 + z_2z_3z_5 + \\ z_1z_2z_6 + z_1z_3z_6 + z_2z_4z_6 + z_3z_5z_6 + z_4z_5z_6.
$$


assertion in first order logic Can anybody give me  an idea how to write this assertion in in first order logic?

  X has not passed one or more of the prerequisites for A.

Here, X is the name of a person and A is a constant representing a course name.

Expressing properties of elements of the universe in first order logic is mostly achieved through defining appropriate relations. So for this you might like to consider relations like:

$P(x)$ - $x$ is a person,
$C(x)$ - $x$ is a course,
$Pre(x,y)$ - $x$ is a prerequisite of $y$ (note that this doesn't actually say that $x$ and $y$ are courses),
$Pass(x,y)$ - $x$ has passed course $y$.

(The parentheses are just included for clarity - you may have seen different notation where relations are written without.)

Then the rest is just building the logical formula, which in this case should be fairly obvious.

   $notready(x,a) \equiv P(x) \wedge C(a) \wedge \exists y(C(y) \wedge Pre(y,a) \wedge \neg Pass(x,y)) $


Why is the zero-th power of the empty set {ε}? It has been asked before why $\emptyset^\star=\{\epsilon\}$.
The answer boils down to $\emptyset^\star$ being defined as
$$ L^\star = \bigcup_{i=0}^\infty L^i, $$
where a word in $L^i$ is the concatenation of $i$ words from $L$. So, for the empty language this leaves empty sets for all $i>0$, "but $L^0 = \{ \epsilon \}$
 since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$." (quoted from the answer.)

And that's what I'm curious about: is there a good reason to say that the concatenation of zero words is $\epsilon$ even for the empty set? Can you compare it to $0^0=1$ in arithmetics (where it's just more or less arbitrary) or is there a strong logical reason for this to be true?

Strings with concatenation and the empty word form a monoid.

In monoids, the empty concatenation/sum/product yields the neutral element, i.e. $\varepsilon$/0/1.

An empty concatenation does not need any words to start with, so $\emptyset^0 = \{\varepsilon\}$.

Intuitively, if you specialize

  $L^n$ is the set of all words obtained by $n$-fold concatenation of words in $L$

to

  $L^0$ is the set of all words obtained by zero concatenations (of words in $L$)

you can just stop reading after "concatenations" and the contents of $L$ do not matter; we don't even need it to be non-empty.


Conversion of RE to NFA I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct?
And in what situation we add a state that accepts an epsilon/lambda?
RE:1*(00|011*)*00

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol.
You need them for two cases
$1.$ The string or part of the string includes a Kleene star $^*$. E.g. $(10)^*$
$2.$ We have the option to choose between different strings. E.g. $0|1$
Now to make the string $$1^*(00|011^*)^*00$$ much easier, we will split the string in different steps.
Step $1$: Find NFA for $1^*$. We can do this by the following

Step $2$: Find $(00|011)^*$. We will skip $1^*$ to make it ourself easier.

Step $3$: Now we add $1^*$ to the previous NFA. We actually can 'substitute' the DFA in step $1$.

Step $4$: Make sure the string ends with $00$.

If we combine the previous steps, we get the following

You also can always check your answers by a RE to DFA/NFA converter.
Note: The above NFA is made inductivly and can be reduced by removing $\epsilon$ transitions as it is not necessary.


What are the axioms, inference rules, and (formal) semantics of lambda calculus? Wikipedia says that lambda calculus is a formal system. It defines lambda calculus by giving its alphabet, and inductively describing what is inside its formal language.

Since lambda calculus is a formal system, what are its

axioms and
inference rules?

Does lambda calculus have semantics? If yes, how does an interpretation of lambda calculus look like as a mapping from what subset to another?

First of all, note that the notion of a formal system is an informal notion and there is no general (or generally accepted), formal definition of what a formal system is. In my opinion, the Wikipedia article on formal systems does not do a good job at explaining this and creates the illusion that formal systems are more or less the same as (the syntactic part) of logical systems, axiomatic systems, or proof systems, etc. Personally, I would rather go with the intuition given by the link at the bottom of the article, that leads to the following quote from John Haugeland's Artificial Intelligence: The Very Idea (1985), pp. 48-64.

  A  formal system is like a game in which tokens are manipulated
  according to rules in order to see what configurations can be
  obtained.  (Examples: chess, checkers, go, tic-tac-toe. Nonexamples:
  marbles, billiards, baseball).   All formal games have three essential
  features:

  They are token manipulation games;
  they are digital; and
  they are finitely playable.

where

  A digital system is a set of positive and reliable techniques (methods, devices) for producing and reidentifying tokens, or configurations of tokens, from some prespecified set of types.

From this perspective, it is much easier to see lambda calculus as a formal system:

the tokens are lambda expressions
the reduction rules provide the techniques as required per the "digital system"

If you want to reconcile this with the Wikipedia definition of the topic, you could consider the reduction rules to be the inference rules and the set of axioms to be empty.

Another way to look at it, is by considering the equational theory of the $\lambda$-calculus, which would look something like

Axiom: reflexivity $$\frac{}{s=s}$$
Rules: symmetry and transitivity
$$\qquad \frac{s=t}{t=s} \qquad \frac{s=t \quad t=u}{s=u}$$
Rules: application and abstraction
$$
 \frac{s=s^\prime\quad t=t^\prime}{st = s^\prime t^\prime} \quad \frac{s=t}{\lambda x.s = \lambda x.t}
$$
Axiom:  $\beta$-conversion $$\frac{}{(\lambda x.s)t=s[t/x]}$$

It is easy to show that $t =_\beta s$ (i.e. $t$ $\beta$-reduces to $s$) if and only if $t=s$ can be proved using the axioms and rules above. Using this system, it also makes sense, for example, to ask the usual "logical" question of consistency: Are there terms $s$ and $t$ for which we can not prove $s=t$.

Regarding the question of semantics, you can use the reduction rules in order to give $\lambda$-calculus operational semantics and there are also denotational semantics see Dana Scott's Data Types as Lattices For the latter, it might be easier to go via combinator algebras, see Engelers Algebras and Combinators. On a side note, this article on architectures for interpreters gives a good idea of what denotational and (small-step and big-step) operational semantics mean in this context.

In general, these questions are, however, quite hard and it might be better to first consider the simply typed $\lambda$-calculus as a starting point. Here, it is (somewhat) easy to see that it actually is a logic via the Curry-Howard correspondence. You will also find a nice answer to the question of semantics in this simple case. From the simply typed $\lambda$-calculus you can go on to consider more complicated systems in the lambda cube or things like homotopy type theory.

Also, maybe the discussion Is lambda calculus a logic? in the Lambda the Ultimate forum might also provide further insights.

Finally, this might be slightly off-topic, but if you really want to go deep down into the rabbit hole of $\lambda$-calculus, logic, and semantics, Girard's Proofs and Types and The Blind Spot might be worth a look.


Interest in Artificial Intelligence (If I am posting this in the wrong StackExchange site, then please direct me to the correct one)

Okay, so some small background first: I am currently third-years student in Computer Science on the university.

I have big interest in Artificial Intelligence and I was wondering if I could practice it somewhere, for example a challenge versus other people that gets updated/executed every set time period (possibly per week).

Example of a challenge that I do like:

Assume that there is an infrastructure set by the organisator to run a poker game via poker bots. I would like to code such a poker bot that would challenge other people, by using AI via a statistical approach, but also via doing fake moves, remembering what the other players have done so far.

It could even be fun to add in real players and see who wins in the end.

Example of a challenge I do not like:

Given a partially filled in Sudoku puzzle, make an algorithm that solves the puzzle.

Why don't I like the Sudoku? Well, I would rather challenge other players or have an interactive way of using AI. I don't even think that an algorithm like this involves any AI. However when asked to do this exercise as part of my study, I didn't mind it, because it was still an interesting programming problem.

Has anyone else been in the same boat? Or is someone being in the same boat currently?

Please share any thoughts, I definately would like to practice around with this, but for example doing the poker bot thing just by myself would be somewhat... dull.

Regards.

edit: Forgot to add, but for a challenge or anything I would prefer Java, as I am used to doing that. But any raw format (so just sending data to a channel and receiving data from a channel would also do)

Background first, too: I am currently third-years student in Information and Computer Science at a Chinese university.

I think most of your problems can be solved by common algorithms. For example, Sudoku game, can be solved by searching, or DLX(Dancing links and X algorithm) if you wanna improve the performance.

I think you can do some exercises to improve your basic skills. Some online judge services are suggested, such as Codeforces, SPOJ, poj.org, etc. There's an interesting game on a contest few days before. codeforces->contest->346->problem->A

Some of AI algorithms are based on searching. To improve the performance, we have some optimizing skills such like evaluation function(e.g. A* algorithm) or randomization(e.g. GA or Simulated annealing). Another part is base on learning, responses of a quest are according to large amount of data(e.g. ANN, and some algorithms for classifying).

Huge amount of code cannot be avoided. And some Lisp symbolic programming languages are good at such things. You can learn it if you're interested.

So just enjoy playing with what you make!


Solving divide & conquer reccurences if the split-ratio depends on $n$ Is there a general method to solve the recurrence of the form:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

for $c < 1$, or more generally

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

where $g(n),r(n)$ are some sub-linear functions of $n$.

Update: I have gone through the links the provided below and also sifted through all the recurrence relations in Jeff Erickson's notes. This form of the recurrence is not discussed anywhere. Akkra-Bazi method applies only when the split is fractional. Any poignant reference will be apprieciated.

Let's say you have a recurrence
$$
T(n) = \begin{cases}
T(n - n^c) + T(n^c) + f(n) & \text{n > 2} \\
1 & \text{otherwise}
\end{cases}
$$
that ranges over positive reals.

What can we do with this function? Well, not a lot unless we superimpose certain structures upon it. I came from a numerical analysis background, which is paved with numerical recipes that somehow works even when the underlying problem is either not smooth enough (doesn't matter, let's still throw Newton's method at its divided differences) or too complicated to analyze (sort of like this problem). My gut reaction towards these problems is to make some handwaved assumption, cross our fingers, and hope for the best. In this case, it seems to give relatively good bounds.

In particular, I want to make two major assumptions. One of these assumptions is more or less baseless, but we won't get very far without it. The other has a somewhat nice visual intuition that you can hopefully grok, but it is still more handwavy than anything else.

I will assume that $T(n)$ is "smooth-ish". It's fairly easy to see that $T(n)$ is not everywhere differentiable. In fact, it isn't even continuous, since for $f(n) = \log(n)$ and $c = \frac{1}{2}$, $\lim_{n \to 2^-} T(n) = 1$ and $\lim_{n \to 2^+} T(n) = 2 + \ln 2$. Therefore, given the iterated maps generated by $n \mapsto \sqrt{n}$ or $n \mapsto n - \sqrt{n}$, $T(n)$ will contain a discontinuity at $n$ if its iteration tree contains $2$ somewhere in its trajectory. That is a lot of discontinuities, it might even give Dirichlet's function a run for its money. If we're getting to the point where we are comparing a function's behaviors to that of the prototypical example of a nowhere-continuous function, isn't it laughable to try to claim that it is "smooth-ish"? Well, it turns out that in practice, the effects of these discontinuities asymptotically diminishes, to the point that your graph looks almost smooth when $n$ tends towards infinity! Therefore, I propose that we put down our pitchforks and just look the other-way in this circumstance. In particular, I will assume that at any point of interest $n$ that is sufficiently far away from the origin, $T(n)$ is differentiable, or at least approximately differentiable around some neighborhood.
I will also assume an even stronger stance of smoothness when $n$ is sufficiently far away. Suppose that $\alpha(n)$ is some sublinear function such that $n > \alpha(n)$ (for example $n^c$), then the derivative $T'(\xi \in (n - \alpha(n), n)$ does not vary significantly when $\alpha(n)$ is slow enough. Intuitively, as $n$ gets larger, the relative size of the neighborhood $(n - \alpha(n), n)$ decreases (since its size is just $\alpha(n)$, which grows much much slower than $n$ does). Eventually, the size of this neighborhood becomes so insignificant (relative to $n$) that the rate of change of $T(n)$ within this neighborhood no longer changes all that dramatically.

Now, both of these properties are assumed, and I have zero idea how to go about actually proving either in any rigorous way. But like I said before, let's cross our fingers and hope for the best.

Let's start with the recurrence relation:
\begin{align*}
T(n) &= T(n - n^c) + T(n^c) + f(n) \\
T(n) - T(n - n^c) &= T(n^c) + f(n) \\
n^c\frac{T(n) - T(n-n^c)}{n^c} &= T(n^c) + f(n)
\end{align*}
Now, I'll assume that $T$ is smooth enough on the interval between $n - n^c$ and $n$. Appealing to one of our classical analytic tools, the mean-value-theorem, gives us
$$
\frac{T(n) - T(n-n^c)}{n^c} = T'(\xi \in (n - n^c, n)).
$$
Furthermore, when $n$ is sufficiently large, we assume that $T'(\xi)$ is approximately the same throughout this interval, and hence takes the value of any of the finite differences within this interval as well. This then means that
$$
T'(\xi) \approx \frac{T(n) - T(n - \epsilon)}{\epsilon} ~~~~ \epsilon < n^c
$$
In particular, take $\epsilon = 1$ to get a one-step divided difference approximation
\begin{align*}
n^c (T(n) - T(n-1)) &\approx T(n^c) + f(n) \\
T(n) - T(n-1) &\approx \frac{T(n^c) + f(n)}{n^c} \\
\end{align*}
We can telescope this out to get
$$
T(n) \approx \sum_k^n \frac{T(k^c)}{k^c} + \sum_k^n \frac{f(k)}{k^c}
$$

Perturbing $T(n)$ reveals that $T(n)$ has two asymptotic phases, depending on the asymptotic nature of $f(z)$.

When $f(n) = o(n^c)$ ($f$ is faster than $n^c$), then the right sum dominates, and we have $T(n) = \Theta\left(\sum\limits_k^n \frac{f(k)}{k^c}\right)$  which can often be approximated with the integral $\int\limits^n \frac{f(x)}{x^c} dx$.

When $f(n) = \omega(n^c)$, then the left sum dominates the right. Here, we have to analyze the sum
$$
\left(\sum_k^n \frac{T(k^c)}{k^c}\right) + F_c(n)
$$
where $F_c(n) = \int\limits^n \frac{f(x)}{x^c}dx$.

By virtue of the smoothness argument, we can once again look at this as a left-anchored Riemann sum, approximating the integral $\int_n \frac{T(x^c)}{x^c} dx$. Applying a similar mean-value-theorem over the integral gives
$$
\sum_k \frac{T(k^c)}{k^c} \approx \int^n \frac{f(x^c)}{x^c} dx = n\frac{T(\xi < n^c)}{\xi^c}
$$
We can just go ahead and approximate this by $n\frac{T(n^c)}{n^c}$, which gives the approximation
\begin{equation}
T(n) \le n M \frac{T(n^c)}{n^c} + F_c(n)
\end{equation}
for some constant $M$ that bounds the series.

Now, suppose that we have the iterated sequence $(n, n^c, n^{c^2}, n^{c^3}, \dots, n^{c^k})$ where $n^{c^k} < 2$, then we can use this sequence to telescope the above inequality to get:
$$\label{eqn:meh}
T(n) \le n \left(\sum_i^{k-1} \frac{M^i}{n^{c^i}}F_c(n^{c^i}) + \frac{M^k}{n^{c^k}}\right) \tag{*}
$$
Once again, we can bound the $F_c(n^{c^i})$ term by some constant to find that
$$
T(n) = O\left(F_c(n) + n F_c(n^c) \left(M n^{-c} + M^2 n^{-c^2} + \dots + M^k n^{-c^k}\right)\right)
$$
where $k = \log_c\left(\frac{\log(2)}{\log(n)}\right)$. Simplifying a bit and coalescing some of the $Mn^{-c}$ terms together (in particular, we know that $n^{-c^k}$ is a constant), we get
$$
T(n) = O\left(n k F_c(n) M^{k} \right)
$$

However, this bound is relatively loose, and you should refer to $(\ref{eqn:meh})$ whenever possible.

Be aware that in no way is this rigorous. I have not provided any support that this ought to work beyond some clumsy approximations. Nevertheless, if you just need a quick asymptotic guess for the sake of informal analysis, then you can actually see that this scheme works well (for large enough values of $n$, usually $n > 10$ suffices) in practice.

Anyways, for all of the choices of $c$ and $f$ that I've tried, the following computation
\begin{align*}
\hat T(n) &= n \sum_k^{\log_c \log_n 2} \frac{M^k}{n^{c^k}} F(n^{c^k}) \\
F(n) &= \sum_k^n \frac{f(k)}{k^c}
\end{align*}
where
$$
M \approx \frac{\sum_k \frac{T(k^c)}{k^c}}{n \frac{T(n^c)}{n^c}}
$$
seems to give good approximations. This technique also generalizes to recurrences of the form
$$
T(n) = T(n - \alpha(n)) + T(\beta(n)) + f(n)
$$
which can be approximated with
\begin{align*}
\hat T(n) &= n \sum_k^{\#_\beta(n)} \frac{M^k}{\alpha^k(n)} F(\beta^k(n)) \\
F(n) &= \sum_k^n \frac{f(k)}{\alpha(k)}
\end{align*}
where $\alpha^k(n) = \alpha(\stackrel{k}{\cdots}(\alpha(n)))$ and $\#_\beta(n)$ denotes the number of elements of the sequence $n, \beta(n), \beta(\beta(n)), \dots, \beta^{\#_\beta(n)}(n)$ such that the last term is between $1$ and $2$.


Construct a proof tree in Hindley-Milner with function overload I'm reading Wadler's paper called "How to make adhoc polymorphism less ad hoc".
I'm trying to understand the given rules for function overload (over and inst) and I want to create a small example of a proof tree using them. All deductions rules are in Figure 9 and Figure 10.

I decided to proof the following expression/type: $(over\: eq:: Eq\: \alpha\: in\: inst\: eq :: Eq\:Int \:=\: eqInt\: in\: eq\:1\:2)::Bool$.

Some people gave me a tip: construct the tree in bottom-up.

So here is what I did:

I think I'm stuck. I have no idea how to go up in the tree. And I'm not sure if I can, at some point, discharge the assumption about $eqInt$.

I would like to know what I'm doing wrong and how to finish this proof.

EDIT:
As said in the paper, $Eq\: \tau$ is a abbreviation for $\tau \rightarrow \tau \rightarrow Bool$.

After some time I realized that is not possible to proof
\begin{align*}
\vdash (over\: eq:: Eq\: \alpha\: in\: inst\: eq :: Eq\:Int \:=\: eqInt\: in\: eq\:1\:2)::Bool
\end{align*}
 without suppositions about $1$, $2$ and $eqInt$ ( $\emptyset$ as the context). They need to be bound to the context , because they should be seen as build in
to the system. In alternative I could create new rules (like $const$ rules) for the integer numbers ($1$, $2$...) and for $eqInt$, that don't insert stuff to the context.

So, my final result is this proof tree:

I'm not sure if I can use $weakening$ in the context, but I did.

I hope that some one could comment something about my answer. If I'm right or if I created some non-sense.