Quadratic equations using 2 different approaches I am reading Mark Newman's Computational Physics and at chapter 4 page 133 in Exercise 4.2 he asks

a) Write a program that takes as input three numbers, a, b, and c, and prints out the two solutions to the quadratic equation $ax^2 + bx + c = 0$ using the standard formula $x = −b± (b^2 − 4ac)^{1/2}/2a$ . Use your program to compute the solutions of $0.001x^2 + 1000x + 0.001 = 0$.

b) There is another way to write the solutions to a quadratic equation. Multiplying top and bottom of the solution above by $-b∓ (b^2 − 4ac)^{1/2} $, show that the solutions can also be written as $x = 2c/−b∓(b^2 − 4ac)^{1/2}$. Add further lines to your program to print these values in addition to the earlier ones and again use the program to

I tried both ways and a) gives me

[-9.99989425e-13 -1.00000000e+00]
and

b)
[-1.00000000e-06 -1.00001058e+06]

how can I understand which one is correct ? Or why is this happening ?

You can understand which, if either, solution is correct by substituting it back into the quadratic and seeing which one works.

As to why you get different answers, it's to do with the accuracy of floating point representations.  Roughly speaking, numbers are represented to some number of significant figures and this can cause problems when you add numbers with different orders of magnitude or subtract numbers that are approximately equal.  For example, evaluated left-to-right to one significant figure, $0.3+0.3+1 = 0.6+1 = 2$, whereas $1+0.3+0.3=1+0.3=1$.

This is a particular issue in the calculation of $b^2-4ac$ in your example, where $b=1000$ and $a=c=0.001$: the correct answer is $999\,999.999\,996$, which is very susceptible to even slight rounding errors. You then have to calculate the square-root of that, which gives a number very close to $1\,000$, and compute $1\,000$ minus that number.  All of these steps cause problems.

The concepts you need to read up on are loss of significance and numerical stability.


Transforming 3 SAT to Simultaneous In-Congruence Problem? Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2):

Given a collection $[(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod\ b_i)$?

But I am struggling with the transformation and not much clue how to go about it nor can find any literature on it. Thus, needed help with the transformation?

Given a SAT instance on $n$ variables, find $n$ relatively prime integers $p_1,\ldots,p_n \geq 2$ of polynomial size (for example the first $n$ primes). The idea is to encode the value of variable $x_i$ as $x \bmod{p_i}$. The first step is to ensure that the variables are indeed binary. To this end, for each $i$ and for each $2 \leq a < p_i$, we add the constraint $x \not\equiv a \pmod{p_i}$.

Each clause involving $p_i,p_j,p_k$ corresponds to one forbidden value of $x \bmod{p_ip_jp_k}$ via the Chinese reminder theorem. For example, consider the clause $x_i \lor x_j \lor \lnot x_k$. Find the value $0 \leq a < p_ip_jp_k$ which satisfies $a \equiv 0 \pmod{p_i}$, $a \equiv 0 \pmod{p_j}$, and $a \equiv 1 \pmod{p_k}$. Add the constraint $x \not\equiv a \pmod{p_ip_jp_k}$.

The resulting system is completely equivalent to the original 3SAT instance.


Are regular languages closed under sort (Parikh image)? Assume $L$ is a regular language over an ordered alphabet.  Is the language built by taking every word in $L$ and sorting it always a regular language?

No. Counterexample: assuming $a < b$, we have $(ab)^\ast \xrightarrow{\;\;\text{sorted}\;\;} \{ a^n b^n \;|\; n \geqslant 0 \}$, which cannot be expressed by a regular expression, by the pumping lemma for regular languages.


Abstract algebra and programming languages Quite often, I stumble upon abstract algebra concepts like initial algebra, free algebra, and similar while reading papers on programming languages. For instance, in papers on algebraic data types, monads, separation logic, models of polymorphic lambda calculus, etc.

Where can I find materials that will introduce me to such concepts, i.e., ones that are related to programming languages and logics? Hopefully, the number of such materials would be small.

Initial algebras and free algebras are basic concepts of category theory. Thus
you may try the first chapters of [1] (in particular Section 2.2 Functional programming languages as categories) or the books [2] or [3].

[1] Category Theory for Computing Science by Michael Barr and Charles Wells

[2] Basic Category Theory for Computer Scientists
by Benjamin C. Pierce.

[3] A taste of category theory for computer scientists by Benjamin C. Pierce.


Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem? The Kraft-Chaitin theorem (aka KC theorem in Downey & Hirschfeldt, Machine Existence Theorem in Nies, or I2 in Chaitin's 1987 book) says, in part, that given a possibly infinite list of strings $s_i$, each paired with a desired program length $n_i$, there is a prefix-free Turing machine s.t. there is a program $p_i$ of length $n_i$ for producing each $s_i$, as long as $\sum_i 2^{-n_i} \leq 1$. The list of $\langle s_i, n_i \rangle$ pairs is required to be computable (D&H, Chaitin) or computably enumerable (Nies).

The proofs in the above textbooks work, it seems, by showing how to choose program strings of the desired lengths while preserving prefix-free-dom.  The details differ, but that construction is the main part of the proof in each case.  The proofs don't try to explain how to write a machine that can compute $s_i$ from $p_i$ (of course).

What I'm puzzled about is why we can assume that an infinite list of results can be computed from an infinite list of arbitrarily chosen program strings using a Turing machine that by definition has a finite number of internal states.  Of course many infinite sequences of results require only finite internal states; consider a machine that simply adds 1 to any input.  But in this case we're given a countably infinite list of arbitrary results and we match them to arbitrary (except for length and not sharing prefixes) inputs, and it's assumed that there's no need to argue that a Turing machine can always be constructed to perform each of those calculations.

(My guess is that the fact that the list of pairs is computable or c.e. has something to do with this, but I am not seeing how that implies an answer to my question.)

Let's take the example in which $n_i = i + 1$. In this case, we can choose the $i$'th program to be $0^i1$. Here is how the prefix-free Turing machine works. It reads the input, and determines $i$. Now it runs a Turing machine which enumerates the list $\langle s_j,n_j \rangle$ until it reaches $\langle s_i, n_i \rangle$, at which point it outputs $s_i$.

More generally, we choose the programs (i.e., the potential inputs to the prefix-free Turing machine) in such a way that we can effectively convert a program $p_i$ to an index $i$. In other words, contrary to what you write, the programs are not arbitrary, only their lengths are. In general the conversion from program to index might require partial knowledge of the sequence $n_i$.

The actual programs can be constructed greedily. See for example lecture notes of Satyadev Nandakumar, proof of Theorem 3.3.5.


Are Linear Bounded Automatons Turing Complete? Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.

But this causes them to not be Turing Complete? Why?

A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.


Proving that CFLs are closed under even-ness using grammars This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2.

  Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the strings in $L$ that have even length. Then $L_{even}$ is context-free.

The question is to prove this theorem using two of three different methods: using grammars, PDAs, or a theorem about language intersections.

I can very easily find a proof using PDAs (maintain your current odd/even status using the stack), and intersections (intersect with $\Sigma^*_{even}$, which is regular) - but I can't think of how to do it using properties of grammars. I suspect either Chomsky or Greibach Normal Forms comes in handy here but I'm not sure how.

Actually you can shoot all three qestions with a single stone.

Since you can easily define a regular language $Even=\Sigma^{2n}$ for all
even strings :

you prove the result by applying closure of CF languages under
intersection with regular sets.
You use the standard construction of such an intersection based on
CF grammar to get the grammar version of the proof.
You use the standard construction of such an intersection based on
PDAs to get the PDA version of the proof.

You have to know at least one of the two constructions, since it is
usually how the closure under regular set intersection is proved.

The purpose of the question is to check that you know the theorem, and at least one way to prove it.


Amortized analysis of max-heap Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time.

  Question: If extract max is $O(1)$ amortized does that mean worst case is $O(n)$?

My answer: No, A sequence of $n$ EXTRACT_MAX will cost $O(n\log n)$. This is because in a Heap the leaves are almost on the same level and the number of leaves in a Heap is $O(n/2) = O(n)$. Calling EXTRACT_MAX each time removes the maximum element from the root and replace it with a new second maximum element and decrement a leaf. Thus, decrementing all the leaves (which are of $O(n)$) will take $O(\log n)$ time each as all leaves are almost in the same level totally giving a time complexity of $O(n\log n)^{1/4}$.

Does this make sense?

If an operation, any operation, has an amortised cost of O(1), then performing it n times has cost O(n), by definition of “amortised cost”. Either your amortised cost is wrong, or your total cost is (assuming you change “O(n log n)” to “not O(n)”, to be a bit pedantic).


How can CFGs have epsilon rules if CSG may not have them? I am new to theory of computer science and I am currently reading about CTF grammars. In our lecture we defined that a Type 1 grammar is context-free if for $w_1 \to w_2$, $\vert w_1 \vert \leq \vert w_2 \vert$.

I looked on the internet for an example and found this context-free grammar for palindromes: $G = \{\{P\},\{0,1\},A,P\}$ with the production rules: $P \to \epsilon|0|1|0P0|1P1$, but aren't those production rules violating the definition for a CTF? First of all $\vert w_1 \vert \leq \vert w_2 \vert$ is violated by $P\to\epsilon$ and secondly in my notes there is mentioned that we can only use an epsilon transition if P isn't on the right site.

The definition you state is for noncontracting grammars, which define the context-sensitive languages (modulo the issue of the empty word). In contrast, context-free grammars define the context-free languages, which are a strict subset of the context-sensitive languages.

So whoever told you that a Type 1 grammar is context-free iff it is noncontracting, used highly idiosyncratic terminology. Or perhaps they just made a mistake.

The Wikipedia article mentions a paper of Chomsky in which noncontracting grammars are called "Type 1". In an earlier paper of Chomsky, he used "Type 1" to mean context-free grammars. This might be the source of the confusion.

Finally, to answer the question in your title: noncontracting grammars only define the context-sensitive languages without $\epsilon$. Conversely, the context-free languages without $\epsilon$ are defined by context-free grammars without $\epsilon$ productions (this follows from Chomsky normal form, for example). In this sense a noncontracting grammar is a generalization of a context-free grammar, in both cases for languages without $\epsilon$. If you want to include also languages with $\epsilon$, you need to consider essentially noncontracting grammars instead; these are also allowed to contain the product $S\to\epsilon$, assuming $S$ doesn't appear in the right-hand side of a production.


How is the directory implementation done using a linear list? I am reading Operating System Concepts by Silberchatz, Galvin, Gagne and they write that a directory can be implemented using a linear list. [pg 470, 8th ed]

However, I visualize directories as a rather hierarchical data structure which can be implemented using a B-tree.

Also, when they say that the nodes contain a pointer to the data blocks, what do they mean?

A directory is a collection of files, some of which could be directories. You can store the list of files forming a directory as a linear list. This is somewhat similar to the adjacency list representation of a graph (imagine that the graph were a tree).

Each node in the list contains some sort of information regarding the file, such as the name, size and contents. The contents themselves are not stored at the list, but somewhere else in the filesystem. Each node just contains a pointer to the data, which is what is meant by data blocks. The exact way in which this is implemented depends on the file system – the main issue here is that the file isn't stored contiguously.


Applications of queues Let suppose a simple (FIFO) queue, where elements enter at a side and exit at the other side.

I know the classical use of queues in everyday life and computer networking. I would like to know more specific uses, for instance in distributed applications.

Are there client-server applications where we need to investigate elements of the queue which are not at its extreme sides ? (that is, elements which are not the first and the last of the queue).

Thank you.

Here is an application of FIFOs in multiprocessor computers. A multiprocessor computer can be regarded as a distributed system.

To make a multiprocessor computer that correctly executes multiprocess programs, two requirements are given by Leslie Lamport [1]. The second one reads,

  Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.

For what it concerns applications of non-FIFO queues, I am confused about your requirement: Why do you use a queue if you don't need its features?

Anyway, is the priority queue an application in which we need to investigate elements of the queue which are not at its extreme sides?

[1] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. By Leslie Lamport. IEEE Transactions on Computers, 1979.


Upper bound on size of minimal binary coverage code Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that every $x \in \mathscr X_n$ is within Hamming distance $\le r$ of some $y \in S$. A minimal $r$-coverage code is one for which the cardinality $|S|$ is minimal. Let this minimal cardinality be $N_n(r)$. Note that we have the trivial bound $N_n(r) \le 2^n$.

Question. What are good upper-bounds for $N_n(r)$ in terms of $N$ and $r$ ?

So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider $q$-ary binary codes of length $n$, such that $n \to \infty$ with $r/n \to p \in [0,(q-1)/q]$, then the minimal code size has the following asymptotic limit
$$
(1/n)\log_q N_{n,q}(r) \to 1-H_q(p),
$$
where $H_q(p)$ is the $q$-ary entropy of $p$. This answers my specific problem which corresponds to $q=2$.


Help with figuring out if MAX(L) is a CF language We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as:

$MAX(L)$ = {$w_1 \in L $| $w \notin L$ so that $w_1$ is a true prefix of $w$}

prove (or disprove): If the language L is CF then the language $MAX(L)$ is CF.

I think that the correct direction here is to disprove.
The question is, how do I disprove it for a general $L$?

I know how to use the pumping lemma to disprove a certain language, but I'm not sure if it can work for a general $L$?

Am I going in the right direction or am I completely wrong?

Let $L = a^*b^*c^* \setminus \{ a^n b^n c^k : k > n \}$. To see that $L$ is context-free, note that we can write it as follows:
$$
L = \{ a^n b^m c^k : n > m \} \cup \{ a^n b^m c^k : m > n \} \cup \{ a^n b^m c^k : k \leq n \}.
$$
The only way in which a word in $L$ cannot be extended non-trivially into another word in $L$ is if the word is of the form $a^nb^nc^n$ for $n \geq 1$. Therefore
$$
\mathrm{MAX}(L) = \{ a^n b^n c^n : n \geq 1 \},
$$
which is known to be non-context-free.


Closure properties of a non-regular language under complement? Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language.
But let's say if the complement of L1 is a non-regular language, is it safe to conclude that L1 is a non-regular language as well?

Since I'm trying to prove a language L1 is not a regular language, and the pumping lemma doesn't work well with this case. But I can easily prove the complement of L1 is not regular, I'm wonder if that option is possible.

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

non-context-free languages are not closed under complement.
non-context-sensitive languages are closed under complement.
non-deterministic-context-free languages are closed under complement.


Is the complement of MAX-CLIQUE in NP? Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$

Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
If $NP=P$, does $MAX-CLIQUE\in P$?

I cannot think of a polynomial verifier for $MAX-CLIQUE$'s complement. There might not be a max clique of size k due to two reasons:

There's a bigger clique than k (and then the verifier will get such clique and verify it).
There's no clique of size k in the graph (and this is cannot be verified in polynomial time).

Regarding the second question: it's known that $MAX-CLIQUE$ is just $NP-HARD$ and not $NP-COMPLETE$. I understand from that that probably $MAX-CLIQUE \notin NP$, therefore even if $P=NP$, so $MAX-CLIQUE \notin NP=P$.
So does it mean that the answer to all the question is simply "no"?

$MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
The answer is yes: your variant of $MAX-CLIQUE$ is in $\mathsf{P^{NP}}$, since knowing the size of max clique you can solve your problem.

There is no polynomial verifier (if $\mathsf{NP \neq P^{NP}}$) for this problem, because it is not in $\mathsf{NP}$.

Classic $MAX-CLIQUE$ which only asks if there is a clique of size at least $k$ is $\mathsf{NP}$-complete. But if $\mathsf{P = NP}$ you can ask a machine if there is a clique of size $|V|, |V| - 1, |V|-2...$ until the answer is "YES" to find max clique. Of course, you can use binary search instead of linear.

So, $\mathsf{P = NP}\Leftrightarrow MAX-CLIQUE\in \mathsf{P}$.


is there an example of an algorithm that has O(1/n)? Possible Duplicate:
  Complexity inversely propotional to $n$

I'm curious if anyone's come up with a problem or method as n => infinity t => 0. Are there any sort of cases found in quantum computing?

As the complexity of an algorithm is a measure of the number of operations (in a sense to be defined in each context) needed to do some computation in function of the size of some input, sub-constant complexity does not make any sense. With your exemple, $O(\frac1n)$, it means that for a sufficiently large input, the algorithm does strictly less than one operation, which in terms of Turing machines means that the initial state is accepting, which means that the corresponding Turing machine does not output anything.

Edit: I had not seen the quantum computing reference, so my answer might not be total, although I doubt it makes sense even in that context.


Find longest common substring using a rolling hash The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring of length $k$. We can then use binary search to find the maximum $k$. This takes time $\cal O(n \lg n)$ provided that solving the relaxed problem takes linear time.

Finding a $k$-common substring can be solved using a rolling hash:

Compute hash values of all $k$-length substrings of $s$ and $t$.
If a hash of $s$ coincides with a hash of $t$, then we've found a $k$-length common substring.

Step 1 uses a rolling hash to achieve linear time but I can't see how we can perform step 2. in linear time. Any suggestions?

In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t$, look it up on the table. This takes expected linear time for a large enough hash table.


Big O of rational function using the definition I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$.

I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction.

How would I go about doing this?

Rewrite $\frac{3x^3+2x^2+x+1}{4x^2+1} = \frac{3}{4}x \cdot \frac{12x^3+8x^2+4x+4}{12x^3+3x} = \frac{3}{4}x (1 + \frac{8x^2+x+4}{12x^3+3x})$.

Clearly, the limit of $f(x) = \frac{8x^2+x+4}{12x^3+3x}$ for $x \to +\infty$ is $0$ and hence, for any constant $c'>0$, there is a constant $x'_0$ such that $f(x) \le c'$ for all $x \ge x'_0$. Pick your favorite constant $c'$, for example $c'=1$. You want to figure out any value of $x'_0$ for which $f(x) \le 1$ or, equivalently:

$$
12x^3+2x - 4 \ge 8x^2.
$$

This is clearly true for $x'_0=1$. Indeed, if $x \ge 1$:
$$
12x^3+2x - 4 > 12x^2 - 4 \ge 8x^2 + 4x^2 - 4 \ge 8x^2.
$$

Going back to the original formula we can conclude that, for every $x \ge 1$,
$$
 \frac{3}{4} x \cdot \left(1 + \frac{8x^2+x+4}{12x^3+3x} \right)
\le \frac{3}{4} x \cdot (1 + 1)
= \frac{3}{2} x.
$$

Which satisfies the definition of $O(x)$ once you pick $c = \frac{3}{2}$ and $x_0=1$.


Proof for Minimum number of insertions to convert a string to a palindrome For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is:

$$
c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = S[j], \\ \min(c[i+1,j],c[i,j-1]) + 1 & \text{otherwise}. \end{cases}
$$

(where $c[i,j]$ denotes the minimum insertions for the substring of $S$ beginning with index $i$ and ending with $j$).

But how do we (formally) prove the correctness of that relation? I tried to use the "cut-and-paste" method, but wasn't sure how to apply it here (to either the first or second line of the recurrence relation).

As D.W. indicates, you use proof by induction. I'll explain this with some hints on the case $S[i] = S[j]$. The intuition is that if $S[i] = S[j]$ then the best way of converting $S[i],\ldots,S[j]$ into a palindrome is converting $S[i+1],\ldots,S[j-1]$ into one, and then converting this to a solution for $S[i],\ldots,S[j]$ at no further cost (how?).

Formally, we need to prove two things:

$c[i,j] \leq c[i+1,j-1]$.
$c[i,j] \geq c[i+1,j-1]$.

For the first inequality, you need to show that if you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting $m$ characters, then you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting at most $m$ characters. You get the first inequality by taking $m = c[i+1,j-1]$. The proof is not difficult and left to you.

The second inequality is more delicate. Now you need to show that if you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting $m$ characters then you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting at most $m$ characters. To show this, consider the insertions converting $S[i],\ldots,S[j]$ into a palindrome:
$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j],w_j.
$$
Here the $w_t$'s are words which may be empty.

  Claim: We can modify this solution to a solution with possibly less insertions in which at least one of $w_{i-1},w_j$ is empty.

(Proof left to you.)
If both $w_{i-1},w_j$ are empty then it is easy to complete the proof (details left to you). Otherwise, suppose without loss generality that $w_j$ is empty, that is, the insertions are

$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

Since $w_{i-1}$ is non-empty and the word is a palindrome, it must start with $S[j]=S[i]$. Writing $w_{i-1} = S[j] x$, we can rewrite this solution as

$$
S[i],x,S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

I'll let you finish the proof of this case from here, and to mimic this proof for the case $S[i] \neq S[j]$.


What is the fastest algorithm for finding shortest path in undirected edge-weighted graph? I am looking for the most efficient algorithm for finding shortest path between two Vertices.

The graph is:

undirected
edge-weighted
Non-negative
less then 300 nodes

I understand that most of the algorithms based on Dijkstra's shortest path algorithm. But which one is the most efficient for the case a specified above. Thank you.

Use Dijkstra's algorithm.  It is quite efficient, and on a graph with only 300 nodes, it will run extremely fast, so fast that it's not worth worry about.

You mentioned in a comment that your main concern is that the algorithms are described for directed graphs, but you have an undirected graph.  No worries.  You can apply Dijkstra's algorithm to an undirected graph, too.  Whenever your graph has an undirected edge between vertices $u$ and $v$, think of that as equivalent to the two directed edges $u \to v$ and $v \to u$.  In this way, you can convert your undirected graph to a directed graph -- and then you can apply Dijkstra's algorithm to the result.  The same goes for any other algorithm for directed graphs; it can be applied to an undirected graph in the same way.


Algorithms for two and three dimensional Knapsack I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work?

By 2D (3D) Knapsack I mean I have a square (cube) and a I have list of objects, all data are in centimeters and are at most 20m.

Knapsack can be solved by dynamic programming in pseudo-polynomial time $O(nW)$ with $n$ the number of objects and $W$ the size of the knapsack. So, as long as your container is small (numerically), you can solve the problem efficiently. Note that you can adjust $W$ by changing resolution; no need to measure a shipping container to the µm, but meters are probably to coarse (depending on your objects).

Knapsack can also be approximated arbitrarily well in polynomial time (see polynomial-time approximation schemes).

However, Knapsack only considers fitting numbers into another number; it does not care about geometrics. If you need to "puzzle", you need another problem; considering Tetris, this is probably much harder than Knapsack.


Are Context Sensitive Grammar with Polynomial Complexity Time? Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.

Assuming a Deterministic Parser is the one which can parse unambiguous grammars in something like linear time complexity, while a NonDeterministic Parser can parse any grammar in some worst time complexity like $O(n^5)$ or exponential.

When something is on Linear Space, it takes Exponential time to be parsed by a Deterministic Parser? (probably space complexity has no relation to its time complexity, maybe something in $NSPACE(n)$ or $PSPACE(n^2)$ can affect time complexity?)
Can any Context Sensitive Grammar be parsed in a Polynomial Complexity Time?

To your first question, the answer is affirmative:

On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time.

On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. However, until now, nobody has been able to prove either way. Even for the hardest problems that take polynomial space, the PSPACE-complete problems, it is not known whether they can be done in polynomial time: we don't know whether PSPACE = P. If you can prove for a single PSPACE-complete problem that it can be done in polynomial time, or that it cannot, you will be famous in computing science forever. In practice, for such problems, we have no better than exponential algorithms.

To answer your second question: parsing context-sensitive grammars is PSPACE-complete, so it takes exponential time in practice; it takes only polynomial time for growing context-sensitive grammars.


Do you >have< to define the upper and lower bound? (context: traveling salesman) Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling salesman problem (TSP))

Additional question:
After having calculated the upper bound (using eg. the Nearest Neighboor algorithm), and the lower bound (using eg. kruskal's algorithm) ... let's say we get:  [4; 8]

Can we say for sure that the cost of the optimal route is a number in the interval [4; 8]? Is it possible to find a route whose cost is not within the interval?

If you want to compute X (whatever X is), then you just need to compute X, and whatever intermediate results are required by your method for computing X.  If your method doesn't need upper and lower bounds, there's no need to compute them.

The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and they may be enough to answer your question. For example, as a typical student, you don't need to know the exact price of a helicopter to know that you can't afford one: helicopters surely cost at least \$100,000 and you don't have \$100000. Conversely, if you're a millionaire, you don't need to know the exact price of a chocolate bar to know that you can afford to buy one: surely a chocolate bar doesn't cost more than \$100 and you definitely have \$100.

  Can we say for sure that the cost of the optimal route is a number in the interval [between the lower bound and upper bound]?

Yes. That's what "upper bound" and "lower bound" mean.

  Is it possible to find a route whose cost is not within the interval?

Again, by definition of "lower bound" and "optimal", no route can be shorter than any lower bound on the length of an optimal route. Depending on what upper bound you use, it might be possible to find a route that is longer than an upper bound on the optimal route. For example, on upper bound on the length of a TSP route is to say that, since the optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex. But, if you think about it, that's actually an upper bound on any route, whether the route is optimal or not. So it's not possible to exceed this upper bound. However, it's possible that you could come up with a smarter upper bound such that the optimal route is definitely not longer than your bound, but suboptimal routes might be.


Find all rational roots of a polynomial equation I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest worst-case complexity? This algorithm will be for a general purpose computer(Turing Machine).

The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The CGAL library (in version 4.9) for example uses the method developed by Arno Eigenwillig in his PhD thesis Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs.


Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results) I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:

  For all ε > 0, DTIME(O(n)) = DTIME( (1+ε) n).

Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):

  DTIME(n) ≠ DTIME(2n).

Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c>0$.  That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).


How prefix property of language affects the PDA I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this fact:

In PDA we have two modes of accepting the language, which are "empty stack method" and "final state acceptance method".
Language accepted by both of these modes in PDA (NPDA) are equal, but in DPDA language accepted by "final state method" > "empty stack method" (strictly).
Thirdly we know that those "deterministic context-free language" having prefix property can not be accepted by "empty stack". An example is $L = \{ a^n \mid n>0 \}$. So for these languages, we need final state method of DPDA.

Now my doubt is that if every DPDA is NPDA then the language accepted by both of the modes should be same in DPDA. I think that I am missing something here because individually all of the above result are ok, but when put sequentially they seems to cause a contradiction.

The root of your problem is in the second statement:

  Language accepted by both of these modes in PDA (NPDA) are equal.

I'm not sure what you mean by that. You might mean the following false statement:

  The language accepted by a PDA using the empty state acceptance condition is the same as the language accepted by the same PDA using the final state acceptance condition.

The true statement is the following:

  If a language is accepted by some PDA using the empty stack acceptance condition, then it is accepted by a different PDA using the final state acceptance condition; and vice versa.

This involves two conversions: from an "empty stack" PDA to a "final state" PDA, and vice versa. The first conversion preserves determinism, the second doesn't. In other words, if we apply the first conversion to an "empty stack" DPDA, then we get a "final state" DPDA. But if we apply the second conversion to a "final state" DPDA, we get an "empty stack" NPDA which is in general not deterministic.

The same statement can be stated differently:

  The set of languages accepted by "empty stack" PDAs is the same as the set of languages accepted by "final state" PDAs.

The same doesn't hold for DPDAs, though it is true that the set of languages accepted by "empty stack" DPDAs is a subset of the set of languages accepted by "final state" PDAs.


Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$? I have an algorithm with this time complexity:
$$ T(n) = O(n) + \frac{n}{\log n} \cdot \log \frac{n}{\log n}. $$
I tried to figure out how to solve this
and I tried to say something like this :
if I have $\frac{\log n}{n}$ then the value is going to be very small, if I switch between them the value becomes very big,
so I came to this: $T(n) = O(n)+$ something very big.
I am trying to determine if the result is larger than linear time or not, but I am lost.

Clearly, $\log(\frac{n}{\log(n)}) \le \log(n)$.
Substitute this into the equation to get that $T=O(n)+\frac{n}{\log(n)}\left(\log\left(\frac{n}{\log(n)}\right)\right)\le O(n)+\frac{n}{\log(n)} \log(n)=O(n)+n=O(n)$
So $T=O(n)$, and indeed it is not bigger than linear time.


Is there a mistake in the expression for clean behavior in Pnueli's article from 81'? I am reading an article called The temporal semantics of concurrent programs
.

On page $9$, there is a small section (numbered as $2$) called "clean behavior".

I think that there is a problem with this part, what does Pnueli meant by "Let $\lambda_i$ be the leagality condition for the statement departing from $m^i$" ?

I have marked the word "the" in bold since, as I see it, there can be more than one edge departing from $m^i$, an example can be seen on page $11$, at the beginning of part $5$.

Did I missunderstood something , or is there actually a mistake in the article by not addressing the fact that there can be more than one statement that can be exectuded after $m^i$, and that this expression for clean behavior need to be corrected accordingly ?

It would seem that in (1) (still page 9) he refers to a sequential program, so there is no concurrency. I think this assumption holds for the rest of the articles. So the "the" is ok there.


Calculate number of error-correcting code check bits To design a code with $m$ data bits and $r$ check bits which allow all single-bit errors to be corrected, the formula
$$(n + 1) 2^m  \leq 2^n$$
with $n = m + r$ and $(m + r + 1) \leq 2^r$ is used.
Why is $+ 1$ used here, doesn't $n$ contain already all possible codewords?

Consider a binary code $C$ of length $n$ (each codeword consists of $n$ bits), containing $2^m$ codewords, and allowing all single-bit errors to be corrected.
Let $x \in C$, and let $B_x$ denote all words at distance at most $1$ from $x$, that is $x$ itself, as well as any word obtained by flipping a single coordinate. Any word in $B_x$ could result from a transmission of $x$ followed by at most one error. Since $C$ allows all single-bit errors to be corrected, for any $y \in B_x$, the only codeword within distance $1$ from $y$ must be $B_x$. In other words, the balls $B_x$ are disjoint.
Since there are $2^m$ balls $B_x$, each one contains $n+1$ words, the balls are disjoint, and there are $2^n$ possible words, we deduce that $(n+1)2^m \leq 2^n$. This is the so-called sphere-packing bound or Hamming bound.


Difference between the tilde and big-O notations Robert Sedgewick, at his Algorithms - Part 1 course in Coursera, states that people usually misunderstand the big-O notation when using it to show the order of growth of algorithms. Instead, he advocates for the tilde notation.

I understand the big-O is an upper bound for certain problem at certain condition.

What is the difference between the tilde and big-O notations?

The $\sim$ notation is similar to the more conventional $\Theta$ notation. There are two main differences between $\sim$ and $O$:

$O$ only provides an upper bounds, while $\sim$ is simultaneously an upper bound and a lower bound. When we say that the running time of an algorithm is $O(n^2)$, this doesn't preclude the possibility that it is $O(n)$. In contrast, if the running time is $\sim n^2$ then it cannot be $\sim n$.
 Another notation with these properties is $\Theta$.
$O$ only holds up to a constant: $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C > 0$ (and large enough $n$). In contrast, for $\sim$ the implied constant is always $1$: if $f \sim g$ then $f/g \to 1$. This contrasts with $\Theta$ in which the implied constant is arbitrary, and indeed there could be different constants for the lower and upper bounds.

Exact constants are impractical in general, for many reasons: they are machine dependent, hard to compute, and could fluctuate depending on $n$. The first problem can be mitigating by measuring some proxy for the actual time complexity, such as the number of comparisons in a sorting algorithm.

Sampling the course, it seems they are using $\Theta$, but call it order of growth.


Space complexity of Travelling Salesman Problem I am having trouble coming up with the space complexity of the TSP algorithm.

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($N!$) where N is the number of cities/nodes/vertexes.

Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($N!$), but the site says the space complexity is O($2^{N}$)

Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.

Thank you

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space requirements are $O(n\log n)$.

The dynamic programming solution, as mentioned in the comments, uses a table of size $O^*(2^n)$. This is much more memory than the brute force solution, but the complexity is exponential instead of factorial, which is much better.

(The notation $O^*$ means that we ignore polynomial factors.)

In fact, every problem in NP can be solved using polynomial space, using a brute force approach that simply goes over all possible witnesses, and for each of them, verifying (in polynomial time per witness) whether it is a valid witness. This extends the brute force algorithm for TSP.


Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit I have such a task at university:
we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+1$. We can perform at most 1 task at a time and we cannot interrupt performing it. Create an algorithm to check if it is possible to perform all the tasks. $b(i)$ and $e(i)$ may not be integers.

I have done some research online, but I haven't found anything concerning this problem.

Actually I think the following algorithm would work (I haven't found a counterexample yet):

iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

If this algorithm works, how could I prove it?

I have proved that my algorithm works, so here's the algorithm, just to remind:

  Iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

And the proof follows:

Suppose the algorithm is not correct and there exist such data, that it returns false, while it is possible to perform a plan (mapping: task -> time) in which each task is performed.

Now let's find the first task (chronologically), which is performed at different time in plan created by my algorithm (further called my plan) and the optimal plan.

Then, this task is performed earlier in my plan (because of how the algorithm works) and this is the task we must most hurry with (compared to the rest of tasks performed later in my plan) (because of the order of tasks list processed by the algorithm).

So, we can safely reschedule this task (call it $t$) (in optimal plan) to the time when it is performed in my plan.

If this rescheduling bears any conflict with another task (call it $t'$) in the optimal plan, we can also safely move $t'$ to the time of, when $t$ was performed originally in the optimal plan (because $e(t) < e(t')$).

So we see that we can safely rearrange the optimal plan, so it becomes my plan. Hence my plan is optimal and the algorithm works.


Integer LP formulation and the existence of a solution A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will provide $p_j$ dollars, but only on the condition that certain actors $L_j \subseteq \{1,2,...,n\}$, are included in the cast (all actors $i \in L_j$ must be chosen in order to receive funding from investor $j$). The producer's profit is the sum of the payments from investors minus the payments to actors. The goal is to maximize this profit.

Express this problem as an integer linear program in which the variables take on values on [0,1]
Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching).

I am lost on both parts for this problem.

Express this problem as an integer linear program in which the variables take on values on [0,1]

$$\begin{align}
\text{max: } &\sum_i^m y_i \cdot p_i - \sum_j^n x_j \cdot s_j &\\
\text{subject to: } &x_i \geq y_j &\forall i \in L_j \\
 &0 \leq x_i \leq 1 &\forall i \\
 &0 \leq y_j \leq 1 &\forall j
\end{align}$$

We see that if we select an investor $y_j$ we must select all of the investor's actors $x_i$ for $i \in L_j$. Our profit is the residual income left over from paying actors.

  Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching)

If our constraint matrix $A$ is totally unimodular, then the relaxed LP is sufficient to give a 0-1 solution.

Sketch: Observe that $A$ is an $N \times M$ matrix where $N = n + m$ and $M = \sum_j^m |L_j|$. This defines an incidence matrix of a bipartite graph where each row corresponds to an edge $(y_j, x_i)$ with coefficients $(-1, 1)$. We see that any cycle in the graph defined by $A$ will be balanced. That is, for any cycle $C$, $\prod_{e \in C: e=(u,v)} A_{e, v} = 1$. The proof for this can be done using the fact that any cycle in a bipartite graph is even. The corollary to this is that the incidence matrix for any balanced signed graph is totally unimodular.


Computing follow sets conservatively for a PEG grammar Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it.  I would be happy with a good approximation that is conservative -- if a character can follow a node then it must appear in the follower set.

The grammar is represented as a tree of named productions whose bodies contain nodes representing

Character
Concatenation
Union
Non-terminal references

So given a grammar in ABNF style syntax:

A := B ('a' | 'b');
B := ('c' | 'd') (B | ());

where adjacent nodes are concatenated, | indicates union, single quoted characters match the character they represent, and upper case names are non-terminals.

If the grammar's start production is A, the annotated version might look like

A :=
  (
    (B /* [ab] */)
    (
      ('a' /* eof */)
    |
      ('b' /* eof */)
    /* eof */
    )
  /* eof */
  );

B :=
  (
    (
      ('c' /* [abcd] */)
      |
      ('d' /* [abcd] */)
    /* [abcd] */
    )
    (
      (B /* [ab] */)
      |
      ( /* [ab] */)
    /* [ab] */
    )
  );

I want this so that I can do some simplification on a PEG grammar.  Since order is important in unions in PEG grammars, I want to partition the members of unions based on which ones could accept the same character so that I can ignore order between partition elements.

I'm using OMeta's grow-the-seed scheme for handling direct left-recursion in PEG grammars, so I need something that handles that.  I expect that any scheme for handling scannerless CF grammars with order-independent unions that is conservative or correct would be conservative for my purposes.

Pointers to algorithms or source code would be much appreciated.

Follow or lookahead sets are a standard concept in compiler theory. I would expect every textbook on the topic to contain an algorithm for them; as for online resources, try this or  that one. It seems as if the choice of algorithm depended on what kind of grammar -- LL, LR, LALR, ... -- you have.


Is it possible to achieve greater than perfect compression using machine learning and big data? Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using machine learning to analyze thousands of petabytes of data on their database to extract a dictionary of the most redundant file sequences. Lets say the most redundant hexadecimal found was the sequence:

"64 65 63 69 6d 61 6c 20 66 6f 72 6d 61 74 2e 20 43 6f 6d 70 75 74 65 72 73 20 73 74 6f 72 65 20 74 65 78 74 20 61 73 20 6e 75 6d 62 65 72 73 2c 20 61 6e 64 20 77 69 74 68 20 68 65 78 20 79 6f 75 20 64 69 73 70 6c 61 79 20 74 68 65 20 6e 75 6d 62 65 72 73 20 6e 6f 74 20 61 73 20 61 20 64 65 63 69 6d 61 6c 20 6e 75 6d 62 65 72 2c 20 62 75 74 20 69 6e 20 62 61 73 65 20 31 36 2e 20 48 65 78 20 6f 72 20 62 61 73 65 20 31 36 20 6f 72 20 68 65 78 61 64 65 63 69 6d 61 6c 20 69 73 20 61 20 6e 75 6d 65 72 61 6c 20 73 79 73 74 65 6d"

They stored this sequence in their dictionary at index 1 and included this dictionary file in their Chrome update. For every user that had the latest Chrome update if they requested a file that had this sequence Google's server would return a flag and the index 1 (e.g. "D 1") such that the Chrome browser could lookup the bytes locally without the need of transferring them over the network. In essence the file being transferred would become something like "data data data D 1 data data"

Furthermore, they did this for gigabytes of sequences causing a larger Chrome update but faster file transfer times.

And to make things more interesting they used machine learning to analyze end-user behavior to predict which sequences were more likely to be requested.

After adding this functionality they achieved faster load times and decreased network congestion and possibly saved in electricity costs by removing redundancy across their entire network.

Questions:

What would this be called? Distributed Cached file transfer?  Would this be practical or desirable? I imagine it could save money in terms of electricity for a large company like google.

Is it possible to achieve greater than perfect compression...

No.  Any lossless compression scheme that makes at least one string shorter must make at least one string longer. This is an unavoidable consequence of the simple fact that there are more long strings than short ones.

The best you can do is be smart about what strings get made shorter, and I guess that's what you're trying to do with machine learning, big data, and any other applicable buzzwordstechnologies. Effectively, though, you're trying to use a big global dictionary.  This is probably less efficient than standard dictionary compression which builds up the dictionary from the data that's being compressed (a dictionary containing lots of Spanish and Chinese isn't going to be useful for compressing Stack Exchange, for example). Also, if you're going to cut network traffic, that big global dictionary needs to be already sitting on your computer, taking up huge amounts of space for dictionary entries you'll probably never use.
Indeed, if that huge dictionary comes as part of my next Chrome update, it's not even obvious that there'll be a net saving in data transfer.


Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property? I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions.
My idea was that it is decidable because we have an countably infinite amount of Godel numbers and the number of TMs which fulfill a certain property is also countably infinite. Therefor, we could make a reduction with the Halting-problem and show via this way that it is undecidable.

That definitely isn't enough. The set of Turing machines that always halt is countable (being a subset of the countable set of all Turing machines), but very not decidable.
Don't overcomplicate: If you are given a Turing machine, any property of the machine as such (number of states, number of transitions, is it deterministic, ...) that can be checked by a deterministic algorithm is obviously decidable.


How to Prove NP-Completeness of Minimum Crossing Problem? In graph theory, the crossing number cr(G) of a graph G is the lowest
  number of edge crossings of a plane drawing of the graph G.
  (from wikipedia)

I know that the problem of counting the Crossing Number of a graph to be less than or equal to K is proven to be NP-Complete by Garey and Johnson in 1983. I couldn't find the actual proof papers though.

So, what is the proof idea?

One way would be to reduce (in polynomial time) from some known NPC problem but to which one?

Here is a short summary of the original paper. More modern treatments can be found in a paper of Cabello proving a hardness of approximation result. We are concerned with three different problems:

CROSSING NUMBER: Given a graph $G$ and a number $K$, can it be drawn with at most $K$ crossings?

BIPARTITE CROSSING NUMBER: Given a connected bipartite graph $G$ and a number $K$, can it be drawn in the unit square so that vertices of one part are on the top side, vertices of the other part are on the bottom side, all edges are within the square, and there are at most $K$ crossings?

OPTIMAL LINEAR ARRANGEMENT: Given a graph $G$ and a number $K$, can we arrange the vertices of $G$ in a line so that the total length of all edges is at most $K$.

The latter is known to be NP-complete. The reduction is from OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER, and then from BIPARTITE CROSSING NUMBER to CROSSING NUMBER.

There are several variants of the concept of crossing number, and the one meant here can be gleaned from the proof that crossing number is in NP: given a graph $G$ and a number $K$, to show that the crossing number is at most $K$, identify up to $K$ pairs of crossing edges, for each one introduce a new vertex, and add the appropriate edges so that the resulting graph becomes planar; planarity can be tested in polynomial (indeed, linear) time.

OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER: Given an instance $G=(V,E),K$ of OPTIMAL LINEAR ARRANGEMENT, we construct an instance of BIPARTITE CROSSING NUMBER as follows:

For each $v \in G$, we include two vertices $v_1,v_2$ on opposite bipartitions, and $|E|^2$ copies of the edge $(v_1,v_2)$.
Fix some ordering of $V$. For each $(x,y) \in E$ such that $x < y$, include the edge $(x_1,y_2)$.
Set the new $K$ to be $|E|^2(K-|E|) + |E|^2 - 1$.

Given a good arrangement $A$ of the vertices in $V$, the intended drawing of the new graph has both copies of $V$ equally spaced and ordered according to $A$, with edges $(v_1,v_2)$ being vertical (but slightly fanned so that they don't cross each other) and the "real" edges being straight. A "real" edge spanning a stretch of $\ell$ crosses $(\ell-1)|E|^2$ vertical edges, for a total of $(K-|E|)|E|^2$ crossings. There are also at most $\binom{|E|}{2} \leq < |E|^2$ crossings between "real" edges.

Conversely, any drawing of the new graph with fewer than $|E|^4$ crossings must be of the form above (due to the vertical edges), and so we can read off a good arrangement of the original graph.

BIPARTITE CROSSING NUMBER to CROSSING NUMBER: Given an instance $G=(V_1,V_2,E),K$ of BIPARTITE CROSSING NUMBER, we construct an instance of CROSSING NUMBER as follows:

We take all vertices in $V_1,V_2$ along with two special vertices $o_1,o_2$.
We include all original edges.
We connect $o_i$ to each vertex in $V_i$ using $3K+1$ edges (for $i=1,2$).
We connect $o_1$ and $o_2$ using $3K+1$ edges.
We use the same $K$.

Given a good drawing of the original graph, we draw the new graph by putting $o_1$ above $V_1$, $o_2$ below $V_2$, the edges from $o_i$ to $V_i$ are (almost) straight, and the edges connecting $o_1$ and $o_2$ go around the entire construction. This adds no new crossings.

In the other direction, we show that every good embedding of the new graph must be of this form, in a step by step fashion, completing the proof. I'm leaving this part to the reader.


How many languages exist over a finite alphabet? I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams.
Link

In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question is,

  How many languages exist over the symbol sets from (a)?

Question (a) describes the alphabets $S=\{a,b\}$ and $S=\{1\}$. The answer to the question as provided in the same link is

  In both cases, $|Σ^*| = \mathbb N$, that is, there are $2^{\mathbb N}$ many languages over these alphabets – indeed, over any finite alphabet there are $2^{\mathbb{N}}$ languages.

Here $\mathbb{N}$ is the set of all natural numbers. I am confused as to how the author came to this conclusion.

Update:
In my understanding, since {a,b} is a set of strings of {a,b}, it follows that it is a subset of {a,b}* or the set of all strings over {a,b}. So, as per set theory, the cardinality of a set containing the subsets of all strings over {a,b} = powerSet({a,b}*) whose cardinality is equal to $2^{\mathbb{N}}$. Is my understanding correct?

The number of possible words is countably infinite, since we can list them in increasing order of length:
$$
\epsilon,a,b,aa,ab,ba,bb,\ldots \\
\epsilon,1,11,111,1111,11111,\ldots
$$
This is why $|\Sigma^*| = \aleph_0$ (to use a more common notation). The set of all possible languages is the set of all subsets of $\Sigma^*$ (known also as the power set of $\Sigma^*$), which by definition has cardinality $2^{\aleph_0} = \aleph$.

If you are unfamiliar with these terms, you need to do some reading on elementary set theory.


Language of regular grammar What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow aAb|\epsilon$$ $$B \rightarrow cBd|\epsilon$$
But I'm not sure if I'm right until here. Is it good?
Edit: This language is not regular, for this language you can look for the answer down: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\} \cup \left\{a^nb^mc^md^n\left|n,m\ge 1\right|\right\}$$

Here's a simpler grammar:
$$
S\rightarrow XY\\
X\rightarrow aXb\mid ab\\
Y\rightarrow cYd\mid cd
$$
The key observation in cases like this is that strings in the language consist of two pieces concatenated: $a^nb^n$ and $c^md^m$, each of which can be generated by a simple grammar.


How to decide whether a language is decidable when not involving turing machines? For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no luck. How to prove that this is undecidable?

It might come as a surprise to you, but the language $$L=\{k\in\mathbb N :\text{the binary expansion of} \sqrt2\text{ contains $k$ consecutive $1$s}\}$$ is decidable, even if we could not construct an algorithm that can demonstrate whether the binary expansion of $\sqrt2$ contains $k$ consecutive $1$s or not given arbitrary $k$.

As Yonatan N indicated, let us take a closer look at $L$. There are two disjoint cases.

$L$ is $\mathbb N$. Then $L$ is trivially decidable. For any given $k$, just return "Yes".
$L$ is not $\mathbb N$. Then there are some numbers in $\mathbb N$ that is not in $L$. Let $m$ be the minimum of such number. Then $L$ must be $\{1, 2, 3, \cdots, m-1\}$. Why?

Since $m>2$ is the minimum number that is not in $L$, $m-1$, which is a number smaller than $m$, must be in $L$. That is, $\text{bin}(\sqrt 2)$ contains $m-1$ consecutive $1$s. So it also contain $k$ consecutive $1$s for all $k\le m-1$.
Since $\text{bin}(\sqrt 2)$ does not contains $m$ consecutive $1$s, it does not contain $k$ consecutive $1$s for any $k\gt m$. That is, $k\not\in L$.

Now we can construct an algorithm that decides $L$. For any given $k$, check whether $k\lt m$. If yes, return "Yes". Otherwise, return "No".

In either case, there exists an algorithm that decides $L$. Hence $L$ is decidable.

Most people, I believe, felt a bit disoriented the first time when this kind of proof/conclusion was encountered. Or at least myself.

The essential point is we do not have to identify/construct/bind to one algorithm that decides $L$.  We do not have to understand fully what is $L$. All we need is there exists an algorithm that decides $L$, whatever $L$ turns out to be. This deviates from "the naive sense of decidability" that you might have even before you encountered the theory of computation/decidability/computability.

In particular, I do not know whether $L$ is $\mathbb N$ or not. Some people claimed to have proved that $L=\mathbb N$. I have not checked their proof, yet. Although it is certainly interesting to find whether $L=\mathbb N$, its result will not change the fact that $L$ is decidable.


NL Completeness Log space reduction $PATH$ to $EQ_{DFA}$ Let $$PATH = \{(G, s, t) | \exists \text{ a directed path from $s$ to $t$ in $G$}\},$$
$$EQ_{DFA} = \{(M_1, M_2) | \text{DFA $M_1$ and $M_2$ over the same alphabet are equivalent}\}.$$
Is there a log space reduction from $PATH$ to $EQ_{DFA}$?

My attempt was to first show that there exists a DFA that accepts a string iff $M_1$ and $M_2$ do. At this point, I am unsure how to reduce the first problem to the second.

It is easier to think about a reduction from $\overline{PATH}$ (since it is NL-complete, this answers your question in the positive). You can treat the graph as a DFA, with initial state $s$ and a single accepting state $t$, and ask whether this automata is equivalent to some DFA for the empty language. Note that the alphabet here is not really important, and you could simply use fresh letters for each vertex.


$2d+1$ threshold for error detection Why is the threshold for detecting errors $2d+1$?
I am aware that the question has been asked before, for example here, but the answers provided didn't really justify why the formula contains $+1$.

So why is there $+1$ in the equation?

Let's look at a simple, concrete example where $d=4$.  Suppose the codebook is $C = \{0000,1111\}$.  This means the sender transmits either the codeword $0000$ or the codeword $1111$ during each block of communication, and no other binary strings are transmitted.  For example, to transmit a $0$ bit, the string $0000$ is transmitted, and to transmit the $1$ bit, the string $1111$ is transmitted.  The hamming distance of this code is $4$.

Suppose the sender transmits one of the above two codewords, and suppose the receiver gets $0010$. Then the receiver knows that the transmitted codeword has been corrupted by the noisy channel because the received vector is not either of the two transmitted codewords (only $0000$ or $1111$ could have been transmitted).  Thus, the receiver is able to "detect" that an error has occurred (i.e. that the transmitted codeword has been corrupted by the noisy channel).  If the noisy channel flips up to any $3$ bits, the receiver will detect an error, but if the channel flips all $4$ bits  - say $0000$ was transmitted and $1111$ was received - then the receiver will wrongly conclude that the received codeword $1111$ was the transmitted codeword.  Thus, we say this code can detect up to $3$ bit errors because the minimum distance between any two codewords in this codebook is at least $4$.  If only up to $3$ bits are flipped, then such an error can't convert one codeword into another because any two codewords differ in at least $4$ positions. More generally, if the hamming distance is $d$, then up to $d-1$ errors can be detected.

Suppose again that the received vector is $0010$.  Then, the receiver will detect that an error has occurred.  But can it correct the error and figure out which codeword was transmitted?  The receiver can use the nearest-neighbor decoding rule, which says if the received vector is not one of the codewords (in the codebook), then make the decision that the transmitted codeword is the one closest (in hamming distance) to the received vector.  This is a good rule when the probability of a bit getting flipped is small. Because $0000$ is closer to $0010$, the receiver concludes that $0000$ was transmitted.  But what if the received vector is $0011$?  Then, both $0000$ and $1111$ are equally distant from the received vector.  The receiver will not be able to correct $2$ errors (it can only detect that an error has occurred, but not correct it).

Ideally, we would like any two codewords to differ in a large number of positions.  Define the sphere of radius $d$ centered around a codeword $x$ to be the set of all codewords which differ from $x$ in at most $d$ positions. For example, the sphere of radius $1$ centered at $0000$ is the subset of vectors $\{0000,1000, 0100, 0010, 0001\}$.  Because the sphere of radius $1$ centered at $0000$ and the sphere of radius $1$ centered at $1111$ are disjoint, the nearest-neighbor decoding rule will decode correctly if the number of bit flips is at most $1$. The above code of hamming distance $4$ can correct up to $\lfloor (4-1)/2 \rfloor = 1$ error.  Because of the possibility that the received vector can be $0011$ or $0101$, etc, the code can't correct $2$ errors.

More generally, if the spheres of radius $d$ centered at any two codewords in the codebook are disjoint, then the nearest-neighbor decoding rule will correct up to $d$ errors.  For any two such spheres to be disjoint, any two codewords must differ in at least $2d+1$ positions.  If there exist some two codewords in $2d$ or fewer positions, then these two codewords could both be the nearest-neighbors of some received vector.  Visualize in your mind the picture in $3$ dimensions of two spheres of radius $d$, which end up being disjoint because the distance between their centers is $2d+1$.

Thus, if the hamming distance is $2d+1$, the code can correct up to $d$ errors. Or, if the hamming distance is $d$, the code can correct up to $\lfloor (d-1)/2 \rfloor$ errors.


Has connect 4 in 3D been studied in CS? Connect 4 is a classical game in computer science. Recently I found a web game where one could play the game on a 3d board. One version can be found here

https://www.mathsisfun.com/games/connect3d.html

I know Connect 4 has been completed, and developed algorothms for solving it. Like the minmax strategy.

Algorithms for Connect 4?

My question is: Is there written any articles / done research on connect 4 in 3D before? Has there been developed any algorithms etc?

I couldn't find anything on that particular game, but I found an analysis of a similar game called qubic in Victor Allis' PhD thesis chapter 4: http://fragrieu.free.fr/SearchingForSolutions.pdf

It is essentially Connect 4 in 3D without gravity.


Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time? This question came up while a group of students at my school were studying for our qualifying exams.  The question on an old exam was,

  Consider the following six classes of languages: Context free (CFL), Regular(REG), P, NP, Recursive(R), and Recursively enumerable(RE). (1) indicate the relationships between these six classes e.g., by drawing a Venn diagram. (2) name the minimum type of machine needed to recognize languages in the different classes.

OK, so we know that REG$\subseteq$CFL, either P$\subseteq$NP or P=NP, NP=RE, and P=R.

We also know that the minimum machine type for each language class is REG:DFA, CFL:PDA, P/R:DTM, NP/RE:might be NTM.

We know that a Turing machine is more powerful than a pushdown automata, but we can't find anything that actually proves that all CFLs can be recognized in polynomial time, or think of a way to prove it ourselves.  When I asked the teacher who originally wrote the problem about this, he didn't have a ready answer.

There are several misconceptions in this question and too many to cover in a comment.

We do not know that $\mathrm{P}=\mathrm{R}$ or that $\mathrm{NP}=\mathrm{RE}$. In fact, we know that both of these things are false. The time hierarchy theoreom tells us that both $\mathrm{P}$ and $\mathrm{NP}$ are strictly contained within the recursive languages.
$\mathrm{P}$ is not the class of languages accepted by any old deterministic Turing machines: they're DTMs running in polynomial time. Similarly, $\mathrm{NP}$ languages are accepted by NTMs running in polynomial time.
Without time bounds, the class of deterministic TMs and the class of nondeterministic TMs accept exactly the same languages: you can simulate nondeterminism deterministically but exponentially slower.
Also, we know that $\mathrm{REG}\subsetneq\mathrm{CFL}$, which is consistent with what you wrote but a stronger statement. Exercise: can you give an example of a context-free language that is not regular?
Another nitpick: you write "$\mathrm{P}\subseteq\mathrm{NP}$ or $\mathrm{P}=\mathrm{NP}$"; the second statement is already included in the first.


Concrete understanding of difference between PP and BPP definitions I am confused about how  PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions correct:
$BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \}$
$PP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] > \frac{1}{2} \}$

If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions.

Some concrete examples with clear insight into the subtle points would be very helpful.

Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively.

Let $M$ be a bounded error probabilistic polynomial-time algorithm for a language $L$ that answers correctly with probability at least $p\geq\frac{1}{2}+\delta$. Let $x$ be the input and $n$ the size of the input.

What distinguishes an arbitrary $\mathsf{PP}$ algorithm from a $\mathsf{BPP}$ algorithm is the positive gap between the probability of accepting $x\in L$ and the probability of accepting $x\notin L$. The essential thing about $\mathsf{BPP}$ is that the gap is at least $n^{-O(1)}$. I will try to explain why this distinction is significant and allows us to consider $\mathsf{BPP}$ to be considered efficient algorithms (even conjectured to be equal to $\mathsf{P}$) whereas $\mathsf{PP}$ is considered inefficient (actually $\mathsf{PP}$ contains $\mathsf{NP}$). All of this comes from this gap.

Let's start by looking at $\mathsf{PP}$ more carefully.

Note that if an algorithm uses at most $r(n)$ random bits during its execution and the error probability is smaller than $2^{-r(n)}$ then error probability is actually $0$, there cannot be any chose of random bits that will make the algorithm answer incorrectly.

Furthermore, an algorithm with running time $t(n)$ cannot use more than $t(n)$ random bits, so if a probabilistic algorithm's error with worst-case running-time $t(n)$ is better than

With a similar argument we can show that the case where the difference between the probability of accepting an $x\in L$ and the probability of accepting an $x\notin L$ is too small is similar to the case where we don't have almost no difference as in $\mathsf{PP}$ case.

Let's now move towards $\mathsf{BPP}$.

In probabilistic algorithms, we can boost the probability for correctly answering. Let's say we want to boost the correctness probability to $1-\epsilon$ for say error probability $\epsilon=2^{-n}$ (exponentially small error).

The idea is simple: run $M$ several times and take the majority's answer.

How many times should we to run $M$ to get the error probability to be at most $\epsilon$? $\Theta(\delta^{-1} \lg \epsilon)$ times. The proof is given at the bottom of this answer.

Now let's take into the consideration that the algorithms we are discussing need to be polynomial-time. That means that we cannot run $M$ more than polynomially many times. In other words, $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$, or more simply

$$\delta^{-1} \lg \epsilon = n^{O(1)}$$

This relation categorizes the bounded error probabilistic algorithms into classes depending on their error probability. There is no difference between the error probability $\epsilon$ being being $2^{-n}$ or a positive constant (i.e. doesn't change with $n$) or $\frac{1}{2}-n^{O(1)}$. We can get from one of these to the other ones while remaining inside polynomial time.

However if $\delta$ is too small, say $0$, $2^{-n}$, or even $n^{-\omega(1)}$ then we don't have a way of boosting the correctness probability and reducing the error probability sufficiently to get into $\mathsf{BPP}$.

The main point here is that in $\mathsf{BPP}$ we can efficiently reduce the error probability exponentially so we are almost certain about the answers and that is what makes us consider this class of algorithms as efficient algorithms. The error probability can be reduced so much that a hardware failure is more likely or even a meteor falling on the computer is more likely than making an error by the probabilistic algorithm.

That is not true for $\mathsf{PP}$, we don't know any way of reducing the error probability and we are left almost as if we are answering by throwing a coin to obtain the answer (we are not completely, the probabilities are not half and half, but it is very close to that situation).

This section gives the proof that to obtain error probability $\epsilon$ when we start with an algorithm with gap $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ we should run $M$ $\Theta(\delta^{-1} \lg \epsilon)$ times.

Let $N_k$ be the algorithm that runs $M$ for $k$ times and then answers according to the answer of majority. For simplicity, lets assume that $k$ is odd so we don't have ties.

Consider the case that $x \in L$. The case $x \notin L$ is similar. Then
$$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$$
To analyze the correctness probability of $N_k$ we need to estimate the probability that majority of the $k$ runs accept.

Let $X_i$ be 1 if the $i$th run accepts and be $0$ if it rejects. Note that each run is independent from others as they use independent random bits. Thus $X_i$s are independent Boolean random variables where
$$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$$

Let $Y = \Sigma_{i=1}^k X_i$. We need to estimate the probability that majority accept, i.e. the probability that $Y\geq\frac{k}{2}$.

$$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$$

How to do it? We can use Chernoff bound which tells us the concentration of probability near the expected value. For any random variable $Z$ with expected value $\mu$, we have

$$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$$

which says that the probability that $Z$ is $\alpha\mu$ far from its expected value $\mu$ is exponentially decreases as $\alpha$ increases. We will use it to bound the probability of $Y < \frac{k}{2}$.

Note that by linearity of expectation we have
$$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$$

Now we can apply the Chernoff bound. We want an upper-bound on the probability of $Y< \frac{k}{2}$. The Chernoff bound will give an upper-bound on the probability of $|Y-(\frac{k}{2}+k\delta)| > k\delta$ which is sufficient. We have

$$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if we pick $\alpha$ such that $\alpha kp = k\delta$ we are done, so we pick $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$.

Therefore we have

$$Pr\{Y < \frac{k}{2} \} \leq Pr\{|Y - (\frac{k}{2}+k\delta)| > k\delta\} \leq Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if you do the calculations you will see that

$$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$$

we have

$$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$$

We want the error to be at most $\epsilon$, so we want

$$e^{-\Theta(k\delta)} \leq \epsilon$$

or in other words

$$\Theta(\delta^{-1} \lg \epsilon) \leq k $$

One essential point here is that in the process we will use many more random bits and also the running time will increase, i.e. the worst-case running-time of $N_k$ will be roughly $k$ times the running-time of $M$.

Here the mid point of the gap was $\frac{1}{2}$. But in general this doesn't need to be the case. We can adopt a similar method for other values by taking other fractions in place of majority for accepting.


Maximum sum of depths of all external nodes in a Binary Tree Let $T$ be a (possibly improper) binary tree with $n$ nodes, and let $E(T)$ be the
sum of the depths of all the external nodes of $T$.  (In a proper binary tree each node have 0 or 2 children.  An external node is a leaf, i.e., any node that is not an internal node.)

Is there a configuration for $T$ such that $E(T)$ is $\Omega(n^2)$?  Is there an infinite sequence of trees $T_1,T_2,T_3,\dots$ such that $T_n$ has $n$ nodes and $E(T_n) = \Omega(n^2)$?

I have found 2 extreme cases for $E(T)$:

each internal node has 1 child (then $E(T)$ is $O(n)$), or
each internal node has 2 children (then $E(T)$ is $O(n \log_2 (n))$).

I have tried shaping the tree like this:

but as you can see it grows asymptoticly similar to Arithmetic Series and $E(T)$ is $O(n)$. I even showed it algebraically.

Internal nodes are just arithmetic sum, and leafs are the last term of this sum times 2.

$x$ - level of a tree
$$\sum_{i=1}^{x}i=\frac{x(x+1)}{2}$$
$$\frac{x(x+1)}{2} + 2x = n$$
solving for x gives
$$x = \sqrt{2n+\frac{25}{4}} - \frac{5}{2}$$
$x$ is $\Omega (\sqrt{n})$.
Now lets try calculation $E(T)$:
There are $2x$ leafs each with depth $x$
$$E(T) = 2x \cdot x $$
$$E(T) \text{ is } \Omega (2\sqrt{n} \cdot \sqrt{n}) = \Omega(n) $$
So my question is how this tree should look like?

Consider a tree that has a chain of length $n/2$ at the top, where each node has exactly one child. Then, the remaining $n/2$ nodes are attached at the bottom of the chain, as a complete tree of depth $\log_2 (n/2)$.

With this shape, every leaf is at depth $n/2 + \log_2 (n/2) = \Theta(n)$. There are about $n/4=\Theta(n)$ leaves.  So, the sum of the depths of the leaves is $E(T) = \Theta(n^2)$.

This is asymptotically optimal; no tree can have $E(T) = \omega(n^2)$, as the maximum possible depth is $n$, and the maximum number of leaves is $n$, so we have $E(T) \le n^2 = O(n^2)$.


In the Data Link Layer, is it better to use large or small frames? I understand how the layer works to an extent, but cannot seem to figure out if the data link handles big frames more efficiently due to error detection or small frames better.

I am assuming from my understanding that the data link works better with small frames as it can save time by not having to keep retransmitting larger frames when an error is detected.

Is this reasoning correct?

Havent used stackexchange in a long while so apologies if these type of questions are no longer permitted

Bigger frames mean a higher useful data fraction (same header size, more payload). But bigger frames mean a higher probability of the frame getting corrupted by random errors (thus getting lost). Larger frames mean higher latencies (need to wait for all of it to arrive, be checked, and handed to the application to be able to use any data in it). They also mean larger buffers might be a problem in limited devices).

As you can see, frame size is an exercise in compromise among a host of conflicting desirable measures.


Big O notation question for set insertion with sequential scan? A friend and I are asking some questions on Big O Notation.

We have an operation that requires a sequential scan on insertion of an element O(n).
The insertion itself of an element is O(1).
We are inserting a whole set of n items.

We both agree the time for insertion is O(n+1) or simply O(n) reduced. But, we have two questions..

Does Big O Notation ever refer to the time for a set operation such as insertion of a whole set, or only to an individual elements operation on the set?
Can we ever say the time for an "insertion of a whole set of n size is O(n**2)" per the above?

First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of any mathematical function (well, at least those defined on the real numbers). It is not tied to algorithm analysis.

Performing algorithmic analysis on a program $p$ that takes input $x$, you want to find a function $f(n)$ so that, for every input $x$ of size $n$, one has $T(p(x)) \leq f(n)$, where $T(p(x))$ denotes the run-time of a program. That is, we are finding the worst-case bound on the run-time of $p$.

Now, it may very well be the case that

$$T(p(x)) \leq e\times n^{3/2} + 2.73 \log_{\pi} \sqrt n \times + .23432342 $$

However, this is not very useful. It's difficult to conceptualize the growth of this function. That is one reason we use asymptotic bounds (the other being it is often easier to determine the asymptotic behavior than the exact behavior). It is much more approachable to write

$$ T(p(x)) = O(n^{3/2}) $$

Anyway, to answer your question: you'll note here that $p$ is an arbitrary program. You can take that program to be whatever you like, including "insert $n$ elements into the set". No one can tell you what to analyze.


Algorithmic complexity of a Maximum Capacity Representatives variant I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can be something similar to a special instance of the Maximum Capacity Representatives problem, which is NP-complete. However, the objective function to optimize in my case is different than the one in the MCR problem.

The problem that I am trying to solve is the following:

INSTANCE: Disjoint sets  $S_1, \ldots, S_m$ and, for any $i \neq j$, $x \in S_i$, and $y
\in S_j$, a nonnegative capacity $c(x,y)$.

SOLUTION: A system of representatives $T$, i.e., a set $T$ such that, for any $i$,  $\vert T \cap S_i\vert=1$.

MEASURE: $\min \{c(x,y): x,y \in T \}$.

And my goal is to maximize $\min \{c(x,y): x,y \in T \}$.

Do you know any way to determine the complexity of my problem? Is there any well known problem in the literature that can be reduced to this one?,

Thanks in advance.

I'm assuming that the goal of your optimization problem is to maximize $\min \{ c(x,y) : x,y \in T \}$. The decision problem is then:

  Given a system $S_1,\ldots,S_m$ of disjoint sets, a cost function $c\colon S \times S \to \mathbb{R}_+$ (where $S = S_1 \cup \cdots \cup S_m$) and a number $\gamma \in \mathbb{R}_+$, decide whether there is a choice of representatives $t_i \in S_i$ such that $c(t_i,t_j) \geq \gamma$ for all $i \neq j$.

This problem is NP-hard (and so NP-complete), by reduction from max clique. Given a graph $G = (V,E)$ and a number $m$, let $S_i = \{i\} \times V$, define $c((i,v),(j,w))$ to be 1 if $(v,w) \in E$ and 0 otherwise, and let $\gamma = 1$. The graph $G$ contains an $m$-clique if and only if the answer to your decision problem is affirmative.


Fast algorithm for finding the size of each connected component in a graph of 2D points I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all connected components in $G$.
The vertices of the graph are 2-dimensional points and there is an edge between $v_1$ and $v_2$ if the Euclidian distance between them is less than a given distance $t$ (the threshold above), otherwise there is no edge between $v_1$ and $v_2$.
Up until now, I've tried DFS methods and also attempted to use a QuadTree to group together "close enough" points.
For the attempt at QTs, I subdivide the plane into cells the diameter of which is sufficiently small to guarantee connectedness, then traverse the tree upwards to find all the neighboring cells and check if they make more connected points.
What I'm asking for is a more efficient algorithm (mainly on the time complexity front) (can be completely different or an improvement on the above, I'm open to anything). For context, the size of the samples I'm dealing with is ~100K.
PS: I do realize there are various other answers dealing with how to determine the connected components of a generic graph, but I believe that in this case (2D points and the need to "only" find their sizes) could benefit from more efficient methods. I could be wrong but there is no better way to find out.

You can do it in $O(n \log n)$ time by forming an Euclidean minimum spanning tree, and then dropping any edge with length greater than $t$.


Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function Thanks in advance for the help.

I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title.

Specifically I have a knapsack problem where I must exactly fill the knapsack.  Additionally, the order in which I place the elements into the knapsack affects the strength of the solution (but not the volume of the individual elements).  The function that is used to evaluate the strength, or goodness, of the packing is non linear and very complex.  Because of this, I have a model that I will use to repeatedly simulate my evaluation function to get an idea of the strength of each solution rather than directly evaluating my evaluation function (sort of like a surrogate function).

For example, suppose I have a knapsack of size ten.  The following would be possible solutions assuming integers are the elements that I can place into the knapsack (for all intents in purposes my actual problem can be visualized in this manner): [5,5], [3,3,4], [4,3,3], etc.

What I'm interested in is two-fold.  First, does this problem reduce to any well studied problems from which I could read up more on how they are solved?  I'm currently thinking about using some kind of heuristic search to solve this problem, such as a Genetic Algorithm (I don't have to have the optimal solution, though I would like the best that I can get).  Second and somewhat related to the first, what work if any has been done on problems that fit the description that I have given above?  The knapsack problem is a very well studied problem and I would find it hard to believe if there hasn't been any work done on problems that fit my current one.  Unfortunately though, while I've found work somewhat related to my problem, I haven't been able to find anything that directly reduces to my problem.

If your function (or your surrogate function) has no structure, then there's nothing to say: you can't do any better than exhaustive search.  In particular, you must examine every possible combination of the items that has the right weight.  If your function has no structure, then you must evaluate it on each possible combination of items whose total weight matches the desired value: you can't rule out any of the possible combinations.  There are exponentially such combinations, so your problem requires evaluating the function (or surrogate function) on exponentially many possible inputs.

Also, if your function has no structure, there are no heuristics or approximation algorithms that will do better than brute force (try some randomly chosen set of combinations and see which does best).

No, this case probably hasn't been studied, because it isn't interesting: there's nothing interesting or useful you can say about it, beyond what I've listed above.


Dijkstra shortest path yields unintuitive results Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, the distance from 0 to 2 will be calculated by passing through 1 instead of 3.

The final distances (from 0) would come out to:

0 -> 0

1 -> 0.2

2 -> 1000.2

3 -> 0.5

The weights in this case are bi-directional but I don't see a way for information of the connection between 2 and 3 to ever affect the final distance between 0 and 2. Am I missing something about the limitations of this algorithm on this type of graph or are the steps listed incorrect?

In the wikipedia article you linked, the final distance is only computed when the node is visited (step 6). The tentative distance is (re)calculated each time to visit a parent of a node, and overwritten if it's smaller (step 3).

So in your example,

We visit node 0.  We set tentative(1) = 0.2, tentative(3) = 0.5
We visit node 1, since it has the smallest tentative distance. We set tentative(2) = 1000.2
We visit node 3.  Since 0.6 < 1000.2, we set tentative(2) = 0.6
We visit node 2.  Its final distance is tentative(2), which is currently 0.6


Proof that a language is not regular as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| \geq m$ is fulfilled.
 I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| \leq m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?

You've almost solved it already. You need to define which part of your word x, y, and z represent, and the obvious partition works well here. You know, by the pumping lemma, that you can repeat y any number of times, and the new word will still be in the language.
In this case, repeat y twice. Is the resulting word still a member of the language?


By what criteria is the base value selected in Rabin Karp algorithm? In the Rabin Karp algorithm the rolling hash is calculated as follows:

H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0

where a is a constant. On what basis is this a selected? In Cormen they have used a value 10 and at some other places it is 26. By observation, when the string is of digits they have taken a = 10 and when the string is of English characters then they have taken a = 26. Is it not possible to compute the hash value using a = 10 for English characters. If not what flaws does it introduce or i am assuming it wrong. I would appreciate help.

You can use any value you want, but it is best to choose a value that is relatively prime to the modulus, as that reduces the number of hash collisions.

For efficiency you might want to choose a value that is small (like 3), as that may make some computations faster.


Java, strong typing, covariance and contra-variance While studying for a test in my OOP course, I came upon this question which had an answer I didn't really understand. The question is as follows (translated):

The programming language "Sava" is similar to Java in every way except in the following:

It's structurally typed
When overriding a method the argument can be contravariant and the return type can be covariant.

Given the following class and interface, is the following assignment legal?

  interface I{
    boolean equals(I i){…}
  }

  class C{
    boolean equals(C c){…}
  }

I i = new C();

The answer that was given to this question was:
The assignment isn't legal. The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

At first I thought the professor forgot to add "Implements I" but the answer also stated the following:
Answers that refereed to the fact that C doesn't implement I weren't accepted because given that it's a Structurally Typed language it doesn't matter if it were a subtype.

I'm not sure I understand how we can refer to these methods as covariant / contravariant if there is no relation of subtyping between C and I.

Can anyone clear this up for me?

"Structurally typed" means that you don't need to write implements I: if your type has all the methods I has, with compatible signatures, it's automatically a subtype of I. However, in this case, C.equals(C) does not implement I.equals(I) (due to variance) and so C isn't a subtype of I.

EDIT:

  I'll explain: For C to be structurally equivalent to I we need to know the type hierarchy for the arguments of equals.

Yes, here you have recursive structural types, which complicate the issue quite a bit.

  The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

This is strictly speaking incorrect, this isn't covariant (again, since C isn't a subtype of I). It should instead say e.g. "if we assume C is a subtype of I, then the equals method in C changes the parameter in a covariant way and we get a contradiction". You could claim C and I should be treated as equivalent (i.e. both subtypes of each other), and then there is no contradiction.

Another problem is that definition of C depends on C itself, so you have recursive structural types, which complicate the language quite a bit.


Reduction from Clique-6 to Clique-3 Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices.

Let us define the problem $Clique-k$ as follows:
$$\{ \langle G \rangle \mid G \text{ is an undirected graph that contains a clique of size  } k\}$$

Question: Find a reduction $f$ from $Clique-6$ to $Clique-3$ such that $f$'s input is a graph $G$ with $n$ vertices, $f(G)$ is a graph with $O(n^2)$ vertices, and $$G \in Clique-6 \Leftrightarrow f(G) \in Clique-3$$

The required time complexity for the computation of $f$ is $O(n^4)$.

I am not sure how to approach this problem, and would be thankful if someone can provide insights \ directions to the solution.

Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).


Locally finite graph without an optimal path If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest path between them?

I think that it can only happen if the goal node is somewhere in the infinity, but then we wouldn't be saying that the goal node actually exists, right?

Could anyone help me on this?

It can happen. Let $P_0,P_1,\ldots$ be a one-way infinite path, where $P_0$ is the start node, and the edge from $P_i$ to $P_{i+1}$ has weight $1/2^{i+1}$. Let $Q_0,Q_1,\ldots$ be a one-way infinite path, where $Q_0$ is the goal node, and the edge from $Q_i$ to $Q_{i+1}$ has weight $1/2^{i+1}$. Connect $P_i$ to $Q_i$ with an edge of weight $1/2^{i-2}$. The weight of the path $P_0-\cdots-P_i-Q_i-\cdots-Q_0$ is
$$(1/2+\cdots+1/2^i)+1/2^{i-2}+(1/2^i+\cdots+1/2) = \\
(1+\cdots+1/2^{i-1})+1/2^{i-2} = \\
(2-1/2^{i-1})+1/2^{i-2} = \\
2+1/2^{i-1} \, .
$$ So for each $\epsilon > 0$ there is a $P-Q$ path of weight $2+\epsilon$, but there is no path of weight $2$.


How does the Earley Parser store possible parses of an ambiguous sentence? I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two?

the grammar im talking about is the following:

S -> VP NP
VP -> V VP
VP -> VP PP
NP -> NP PP
NP -> Det N
PP -> P NP

so you while parsing could either attach a PP to an NP or to an VP.

my question is detail is how the graphical chart would look like, meaning the positions of predict, scan and complete. I was assuming that both parses would be stored in one (big) chart. So S' will then be found in, let's say, s[0][8] and s[0][16] ? Is that right?

An attached image or link with a graphical chart parsing through an ambigous sentence would help.

This is an example of what the graphical chart looks like when there are n tokens in the string:

$\begin{array}{}
[1,1] & [1,2] & [1,3] & \cdots & [1,n] \\
 & [2,2] & [2,3] & \cdots & [2,n] \\
 &  & [3,3] & \cdots & [3,n] \\
 &  &  & \ddots & \vdots \\
 &  &  &  &  [n,n]
\end{array}
$

Because $S$ is the root of the grammar, the two parses of $S$ will be stored in the $[1,n]$ cell of the chart. Here as you can already guess, $[i,j]$ stands for the position indices of the parses, in other word, the span.

In case of $S$, the positions span the whole string. If the positions do not span the whole string, what you have is a set of valid constituent parses in that span.

So the answer to your question is: Possible parses are stored in the same chart, they may be stored in different cells of the chart if their spans are different. If their spans are the same, they are stored in the same cell in the chart.

Btw, I think the first two rules in your grammar do not look right.
Maybe you want

S -> NP VP and VP -> V NP instead.