Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model? Karlheinz Brandenburg depicts a MP3 encoder like this:

Source: MP3 and AAC Explained

I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the psychoacoustic model be applyed to the so called lines after the modified discrete cosine transform (MDCT) without performing a FFT?

I have some literature here, saying the frequency resolution is not accurate enough. Does this mean, dividing the original signal into 576 lines (like the filterbank and the MDCT do) is not accurate enough for the psychoacoustic model to work properly? Is the FFT more accurate?

I would suggest a more detailed explanation of mp3 codec.

FFT is applied on the time domain signal, so in fact it does not use the result from the MDCT.  The input to the psychoacoustic models is in the frequency domain, hence the FFT.

There at least several reasons to do it.
MDCT with filterbanks operates on very short overlapping chunks, maximizing the compression – the FFT uses longer samples and has better spectral resolution. (It is hard to compare since MDCT operates as short-term transform; if this is of big importance to you I will have to make that comparison.)

You can think of filterbank MDCT in the same way as JPEG quantization (it is a very good analogy, since both use DCT) and FFT to detect DCT artifacts from compression.
Then, the psychoacoustic model smooths the errors to fall under the "hearable" threshold, but in order to do that, the time domain samples (here PCM – Pulse Code Modulation is not enough, because sudden frequency shifts are heard as cracks) - so it uses the frequency domain to detect such discontinuities and then smooth it in time domain.

Two things are not explained in articles but are crucial. When PCM differences, are high the speaker has more distance to travel, so there is time delay and depending on speaker abilities it might just cause additional vibrations, which are quite distinct noises from speaker.
The second part is between lines, the quantized version of signal is transformed back to compare it with original sound and check how much it deviates.

Based on the masking type of windows (based on comparison of FFT and inverted MDCT) is chosen to compensate better for audible deviations from the original.

Humans perceive frequency shifts better than amplitude changes, so the filter operates in the both domains at once, and the quantized signal is reversed and smoothing is done back in time domain.

Yes, the resolution of MDCT with filterbanks is not enough, but this is the part where a fair share of the compression happens, and then it is masked. But the psychoacoustic model has spectral resolution as given in the paper.

Yes, FFT is more accurate because it gets longer samples, so it has better resolution between bins.

Footnote
The (M)DCT is commonly implemented by performing FFT, so this has nothing to do with transform used. MDCT can be seen as a bit-modified Short-Term Fourier Transform with a specially chosen filter (the filterbanks resemble Mel scale for speech recognition).

FFT is used longer, provides easier algorithms for pitch shifting and is easier to apply on sound.
(M)DCT minimizes the number of components, meaning that we can cut more data from the result than from FFT.

But in the case of sound those components are not stable, cutting always e.g. two bins out will give bigger disortion between consecutive frames than doing equivalent operation on FFT results.
So, the connection between FFT and what we hear is bigger than (M)DCT and what we hear, but available compression is the other way around.


Paint the balls: what patterns can be painted? You are given a number $k$ which specifies the number of consecutive balls you can paint in a go. You are given a string $S$ of length $l$. $l$ is the number of balls and each character in the string specifies the color of the $i^{th}$ ball. I want to know whether it is possible to color all the balls in the given pattern.

e.g.,
$S=rrggg$,
$l=5$,
$k=3$

We can color this pattern in two operations. As a first step we paint first three balls in red color and in the second step last three balls in green. Hence the answer should be $2$.

I conjecture that we can always generate a pattern provided that there's at least one consecutive sequence that has same color and $l \ge k$. I've formed this conjecture using various sample tests but there's no concrete proof that I could produce.  Is the conjecture true?  Can you prove it?

If this can be proved logically, it's easier to code the solution of the above problem. I'd like to see the proof of the conjecture that it's always possible to produce the pattern if there's at least one consecutive sequence that has same color and $l \ge k$.

Every pattern with a run of length $\ell$ is feasible. Indeed, consider first that the last run has length at least $\ell$. We go over the string from left to right, and for each $i$, we paint balls $i,i+1,\ldots,i+\ell-1$ with the required color for position $i$. After going over all possible indices (i.e., all but the last $\ell-1$), we have painted the pattern.

Now suppose that there is such a run in the middle, say $r,\ldots,s$. We run the algorithm above up to position $r-1$, and the we run a similar algorithm going from left to right, until ball $r$ is painted. We have painted the pattern.

As for the optimal number of moves, one natural algorithm to consider is the algorithm described above, with a simple optimization: when attempting to paint the $i$th ball, if it is already of the correct color, then don't bother. I conjecture that this algorithm, or some simple variant of it, is indeed optimal.


Extracting the set of chains from a partial order Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)?

Note: I am asking here instead of math.SE because i'm looking for an algorithm for the problem.

Yes there is, have a look at :

Chen, Yangjun, and Yibin Chen. "On the Decomposition of Posets." Computer Science & Service System (CSSS), 2012 International Conference on. IEEE, 2012.

and also this:

Daskalakis, C., Karp, R. M., Mossel, E., Riesenfeld, S. J., & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), 597-622.


Problems in NP but not in #P Are there problems that are in NP class but not in #P class?
According to Wiki definition:

  More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time"

So I am thinking, if you already have a poly nondeterministic Turing machine that can accept correct paths, then you can just use this to count in poly time.
Is there something I am missing here?

NP is a class of decision problems, while #P is a class of functions. If a function $f$ is in #P then the decision problem $L = \{ x : f(x) > 0 \}$ is in NP.

As far as I know, it is not expected that for every $f$ in #P, the decision problem $L = \{ (x,y) : f(x) = y \}$ is in NP. In particular, it is not clear how you would verify non-deterministically that a given non-deterministic machine has exactly $y$ (or even at most $y$ or at least $y$) accepting paths (where $y$ is encoded in binary; if it's encoded in unary, then the task is perfectly possible). Do you have any suggestions?


Is process address space part of Process Control Block(PCB)? I recently read about the process address space and PCB and trying to link them together. I don't find much literature on their relation.

Is the process address space a part of the PCB data structure?

Let me start off like this.

The process state includes all the registers that the process may be using, especially the Program counter, plus any other operating system-specific data that may be necessary. This is usually stored in a data structure called a process control block (PCB) or switch frame.
This is what happens in context switching.
The PCB is stored on a per-process stack in kernel memory (as opposed to the user-mode call stack), or there may be some specific operating system-defined data structure for this information.
When a process is ready to run again, its PCB is restored. The program counter from the PCB is loaded, and thus execution can continue in the chosen process.
So, the process's address space is not a part of the PCB data structure.


Recursive methods with stacks I'm doing some practice papers for revision for my finals and I came across this question:

  "This question is about recursion. A recursive method can always be implemented by an iterative method that uses a stack to keep track of intermediate values. Could the stack be replaced by, for example, a queue? Explain (no explanation means no marks)."

And their answer is:
"No, a stack is needed to reuse the results of the recursive calls, which means we need a LIFO (i.e., reversed) order. A stack is perfect since each call can be interpreted as a push and each return as a pop of the result."

Now this is sort of confusing me. Couldn't you also say that a queue is also okay because each call can be interpreted as an append and each return can be interpreted as a serve?

If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice.

The idea is to represent a stack, say $[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)}$, so
$$
[\ a\ b\ c\quad \stackrel{\mathtt{push(x)}}{\longrightarrow}\quad[\ a\ b\ c\ x
$$
would be simulated as
$$
\langle\ c\ b\ a \rangle\quad \stackrel{\mathtt{enque(x)}}{\longrightarrow}\quad\langle\ x\ c\ b\ a\ \rangle
$$
The $\mathtt{pop()}$ operation is a bit more complicated. We first enqueue a marker, #, and then keep pulling elements off the head of the queue and placing them back on the tail until we come to the marker, indicating that the last element we pulled off corresponds to the top of the stack, so we don’t replace that element on the queue and we finish by removing the marker. In pseudocode, what we do is:

enque(#)
v = head()              ; save the head element
deque()                 ; remove it
while (head() != #)
   enque(v)             ; put the element back on the tail
   v = head()           ; save the next element
   deque()              ; remove it
deque()                 ; finally, remove the marker

For example, starting with $\langle c\ b\ a\rangle$, we'd have
$$\begin{align}
\langle\ c\ b\ a\ \rangle &\longrightarrow \langle\ \mathtt{\#}\ c\ b\ a\ \rangle \\
&\longrightarrow \langle\ a\ \mathtt{\#}\ c\ b\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ c\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ \rangle \\
&\longrightarrow \langle\ b\ a\ \rangle
\end{align}$$


Computing a Sequence of People Entering and Leaving a Room I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows.

  You start with an empty room and a group of n people waiting outside. At each step, you may either admit one person into the room, or let one out. Please design an algorithm which generates a sequence of $2^n − 1$ steps, so that every possible combination of people is achieved exactly once. For example, for $n = 3$, one possible sequence would be

  $\qquad\displaystyle e_1, e_2, x_1, e_3, e_1, x_2, x_1$.

  where $e_i$ means person $i$ enters the room and $x_j$ means person $j$ exits
  the room

  Hint: study the Hanoi Tower algorithm.

In my research on the prompt, I've found many people referencing Gray Code, but I don't understand how to implement it in an algorithm to compute this combination. I also found a very similar problem, but there wasn't an actual implementation of it.

It would be greatly appreciated if you could point me in the right direction on where to go with this algorithm.

Base case It's easy to generate the combinations when $n=1$: just use the operation $e_1$.

Recursion Now assume that you have a sequence $ops_n$ that will generate all the combinations of $n$ people. Define $rops_n$ to be the sequence of operations that "undoes" $ops_n$, namely first form the reverse of $ops_n$ and then replace all "enter" operations with "leave" operations and vice versa. For example, if $ops_2 = \langle\, e_1, e_2, x_1\,\rangle$, then $rops_n =\langle\, e_1, x_2, x_1\,\rangle$. It's not difficult to see that $ops_n, rops_n$ will generate all the combinations of $n$ people and then produce the same combinations in reverse order.

Finally, show that if $ops_n$ generates all the $n$-combinations, then the sequence $ops_n, e_{n+1}, rops_n$ will generate all the $(n+1)$-combinations: first all the ones without person $n+1$ and then all the ones with person $n+1$. From this construction it's clear inductively that you can generate all $n$ combinations with $2^n-1$ operations.

As per the hint you were given, this is very similar in spirit to the Towers of Hanoi problem: To move $n+1$ disks from peg 1 to peg 2, you first move $n$ disks from peg 1 to peg 3, then move the largest disk to peg 2, and finally move the $n$ disks on peg 3 to peg 2.


What do you call a subtree covering a subset of contiguous leaves? In the data structure field, what is the (best) term used to identify (designate) a subtree covering a subset of contiguous leaves?

You seem to mean a subtree obtained by taking a certain node and all its successors.

In data structures, the implicit assumption usually is that we consider rooted (and often ordered) trees. Therefore, "subtree" is usually taken to mean what you intend; "subtree" as in graph-theoretic "subgraph" is rarely used (in my experience).

If you want to make very clear what you mean, you can write

  The subtree of $T$ which is rooted in $x \in T$.

A common notation for this tree is $T_x$.


What is the advantage of probability algorithm? What is the advantage of probability algorithm? e.g. Las Vegas. I would also like to know some applications of the randomized algorithms. Are there any recommendable courses or books?

What is advantage of probability algorithm (we usually use randomized algorithm instead of probability algorithm)? Well this is a big question, e.g. we don't know if $P = BPP$, if so then we would say that deterministic algorithm is the same as randomized algorithm. If not, i.e. $P \ne BPP$ then randomized algorithm gives us more power than deterministic algorithm. I think randomized algorithm can give us some polynomial speed up but I'm not sure if it can give us an exponential speed up over deterministic.
Note that P is the class of all problems that can be done by efficient algorithm (i.e. polynomial algorithm in the size of the input) while BPP stands for Bounded-error Probabilistic Polynomial time, i.e. it contains all problems that have a non-deterministic TM with at least 1/2 of the branches accepts and less than 1/3 of the branches rejects.
A quick example of a randomized algorithm is verifying polynomial identities, e.g. given (x+2)(x-4)(x+22)(x-43)(x+11) = x^5-2x+4. The question is: Can you verify that the right-hand side is equal to the left hand side? One way to do is to multiply all terms together which takes O(n^2) where n is the number of terms. But we can do it in O(n) time by selecting some random number and text whether they are equal or not. Yes, there is a probability of wrong answer, but with many run of the algorithm (say 100) if there is at least one counterexample, then this is enough.
There are two major textbooks in randomized algorithm which are:

Probability and Computing - Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal

Randomized Algorithm By Rajeev Motwani and Prabhakar Raghavan

I recommend the first since it is easier and have one or more examples in each chapters while the second is good if you are interested in randomized complexity.


What is the meaning of $O(m+n)$? This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. Is that right? I keep seeing this notation, especially when discussing graph algorithms. For example, you routinely see: $O(|V| + |E|)$ (e.g. see here).

You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.

Simply speaking, since
$$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$
you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent asymptotic upper bounds.

On the other hand  $O(n+m)$ is different from $O(\min\{n,m\})$, since if you set $n=2^m$, you get $$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$$


Computing inverse matrix when an element changes Given an $n \times n$ matrix $\mathbf{A}$. Let the inverse matrix of $\mathbf{A}$ be $\mathbf{A}^{-1}$ (that is, $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$). Assume that one element in $\mathbf{A}$ is changed (let's say $a _{ij}$ to $a' _{ij}$). The objective is to find $\mathbf{A}^{-1}$ after this change. Is there a method to find this objective that is more efficient than re-calculating the inverse matrix from scratch.

The Sherman-Morrison formula could help:

$$ (A + uv^T)^{-1} = A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u}. $$

Let $u = (a'_{ij}-a_{ij}) e_i$ and $v = e_j$, where $e_i$ is the standard basis column vector. You can check that if the updated matrix is $A'$ then
$$ A^{\prime -1} = A^{-1} - \frac{(a'_{ij}-a_{ij})A^{-1}_{i\rightarrow} A^{-1T}_{\downarrow j}}{1 + (a'_{ij}-a_{ij})A^{-1}_{ij}}.$$


Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$ My thoughts process: let number of elements in heap be $n$, total height of binary heap be $H$, height of node be $h$, and let number of nodes with height $h$ be $x$.

Then number of nodes with height $H-1 \le 2^1, H-2 \le 2^2, ... => x \le 2^{H-h} = 2^{\lfloor \lg n \rfloor - h} = \frac{2^{\lfloor \lg n \rfloor }}{2^h}$

However, I don't see how this can be transformed to $\lceil \frac{n}{2^{h+1}} \rceil$, as $n/2$ is less than $2^{\lfloor \lg n \rfloor }$

$n$ element tree has depth $\lceil{\log_2n}\rceil-1$. If $h$ is the height of nodes in any $n$ element heap from leaves then the nodes are situated at the depth of $\lceil{\log_2n}\rceil-1-h$ from the root.

Now, at most $2^{\lceil{\log_2n}\rceil-1-h} = \lceil{\frac{n}{2^{h+1}}}\rceil$ nodes/leaves are possible with $\lceil{\log_2n}\rceil-1-h$ depth in a heap.

Note that depth is the number of edges from the root & height is the number of edges from the highest level in a heap.


Why is the syntax of some programming languages very much not according to earlier conventions? Looking at the syntax of the programming language C and others inspired by it, I cannot help but ask the question in the title. Mathematics, logic and other subjects have been existing for many ages and so have natural languages and all of their symbols. Still, instead of respecting these conventions fully, designers of languages such as C have gone against them, for example by using the very old &, used in logic and natural language to denote conjunction, for something totally different, or by using the well-known = and == in unexpected ways, or by using ! for negation. Why?

Even if there were constraints to work with, certainly a programming language designer and implementor could make the syntax much more readable, less cryptic, and still concise and more natural, respecting established conventions? After all, there have been examples of that (Wirthian programming languages). And they can certainly do it these days.

Furthermore, certainly subjects such as philosophy, logic, mathematics and natural languages are very much primary and very essential subjects without which there would not even exist any computer science and no programming language. The symbols there used are very much known by many or they are at least standard. Why then go against established principles?

Today, most people who learn a programming language know very little mathematical notation and are more familiar with other programming languages, and with symbols that are available on their computer keyboard. Of course, this wasn't the case in the 1950s and 1960s when some of the major programming language families that exist today appeared.

A lot of programming languages use a C-like syntax today because this has become the earlier convention. C established conventions such as braces {…} to delimit code blocks, semicolons ; to delimit instructions, dot . to access an element of a compound structure by name, the equal sign = as the assignment operator, double-equal == as the equality operator and != as inequality, && and || as logical-and and logical-or, square brackets […] for array indices, etc. C also participated in some conventions inherited from mathematics, such as the decimal notation for numbers, infix binary operators with parentheses for precedence, and the function call syntax with parentheses around the argument lists and commas to separate arguments function(argument1, argument2, …).

The conceptors of C, like Wirth, followed some conventions already established in ALGOL. I think (but I'm not sure) that's where brackets for array access comes from.

Syntax choices are of course very strongly influenced by technical reasons: most languages use syntax that programmers will be able to type on their keyboard. To start with, most languages represent their source code as a sequence of lines, each line being itself a sequence of printable characters. This rules out some aspects of mathematical notation such as subscripts, superscripts, superposition (like the fraction notation), etc.

The set of available characters is usually limited to what typical computers of the time allow people to type easily. This self-perpetuates because operating system and keyboard manufacturers keep making these characters easily available. The basic standard set of characters today is ASCII: computer systems that don't support ASCII are extremely rare. Some of the characters in ASCII today weren't commonly available in the 1950s and 1960s, which explains why some languages that trace their roots to this time period don't use all of them.

An example of characters that are used by mathematicians, but weren't commonly available on computers at the time, is the logical operators $\wedge$, $\vee$ and $\neg$. FORTRAN and ALGOL 58 spelled them out AND, OR and NOT. C (following some of its ancestors) used &&, || and !. Mathematicians never used & for conjunction, as far as I know¹: that came from Latin (& started out as a ligature for “et”, which is how the Latin word for ”and“ is spelled). Later versions of ALGOL added ∧ and ∨ as syntax for boolean operators, but since most computers didn't have them, they allowed other spellings, including /\ and \/, which contributed to the imposition of the backslash as a standard character.

Some languages stray further from classical mathematical notations than C. A major example is Lisp, where the syntax for a function call is (function argument1 argument2 …) and there are no infix operators. Lisp made this choice in the interest of uniformity: there is only one syntax for function calls and not many ($2+3$, $2^3$, $2x$, $\sin x$ are some examples of mathematical notations for function calls that don't follow the usual $f(x,y,\ldots)$ syntax). This uniformity has some theoretical advantages (Lisp was heavily inspired from the mathematical work on the lambda calculus), technical advantages (Lisp makes it easy to manipulate code as data objects), and sociological advantages (it makes the language easier to learn: for example you don't need to learn operator precedence).

A (basically the) notable language that baked in more classical mathematical notations is APL. It's still limited by the line syntax, but uses a special character set that includes characters such as $\leftarrow$, $\rightarrow$, $\neq$, $\neg$, $\subset$, $\supset$, etc. The special character set was a strong barrier to adoption because it required special software and made it harder to learn to type programs. The syntax of APL makes it very terse, and is a reasonably good fit for numerical programming, but it isn't particularly readable.

Beyond symbol availability, another reason for programming languages to depart from mathematical notation is the need for new concepts. Most programming languages incorporate syntax for imperative programming, with major concepts that mathematics doesn't have: operations done in sequence, assignment. For sequencing, the most logical character would have been . following the typography of most languages, but that character was also used in mathematics for decimal numbers. ;, which is not used in mathematics, was the next logical candidate. For assignment, some languages tried to introduce $\leftarrow$, but since it wasn't available in typical character sets, it never really took on. The symbol = was a logical candidate for both equality testing (“are these things equal?”) and assignment (“make this equal to that”). C uses = for assignment and == for equality testing. Other languages made different choices. ALGOL used the arguably more fitting := for assignment (more fitting because it's asymmetric, leaving the symmetric symbol = free for the symmetric concept of equality). PL/1 uses = for both and distinguishes the meaning from context, but this requires the language to distinguish between contexts that allow an assignment and contexts that allow a predicate and not to have any context that allows both. Some languages go closer to mathematical notation and use syntax like set x = … or let x = …; I think the designers of B and C considered this too verbose. I think FORTRAN was the heaviest original influence on imposing = for assignment.

¹  Linear logic uses $\&$ but that's not the ordinary conjunction and that came later.


Worst case time complexity of heap sort I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:

1. Build a max-heap out of the unsorted array, say A. (O(n))
2. Exchange root of the heap (max element in the heap) with the last
   element of the heap.
3. Decrement the heap size by 1.
4. Run MAX-HEAPIFY on A(1).
5. Keep repeating steps 2-4 until all elements have been sorted.

The step 3 takes time O(lg m), where m is the current size of the shrinking heap being max-heapified (m ranges from (A.length - 1) to 2). So the total time taken max-heapifying would be Σlg(n - j) where the summation runs from j = 1 to j = n-2. So the total time taken would be lg((n-1)!). We know that lg((n-1)!) < nlgn. So how can nlgn be the lower bound? (It should be lg((n-1)!) as per the above). Its ok if we are talking about the upper bound since nlgn is greater always, and we can say that heap sort in worst case takes O(n lg n).

I understand that the algorithm can have worst-case running time that is both O(nlgn) and Ω(nlgn); the former specifying an upper bound, and the latter the lower bound. What I understand is that the if runtime is Ω(nlgn), it means that the algorithm will take time of the order of nlgn lower bound. My question is different. The time taken in case of heap sort should Σlg(n - j), summing all the run times of max-heapify instances, which comes out to be lg((n-1)!. So heapsort in the worst case should have a run time of Ω(lg((n-1)!) instead of Ω(nlgn) ; also lg((n-1)!) < nlgn (since nlgn = lg (n raised to n)) Please correct me if wrong.

An algorithm can have worst-case running time that is both $O(n \lg n)$ and $\Omega(n \lg n)$; those don't contradict each other.  See How does one know which notation of time complexity analysis to use? and https://cs.stackexchange.com/a/201/755 for some background that might help understand why that is so.


Lower bound for co-NP Suppose someone will prove lower bound (for NTM) for co-NP, say exp(n/d) for some constant d. Would it in some way imply lower bound (for DTM) for NP?

Thank you

Yes.  If you can decide all languages in NP on a DTM in polynomial time, then P = NP = co-NP, i.e., you can also decide all languages in co-NP on a DTM in polynomial time, basically by negating the output of the DTM.  Taking the converse... if there exists a language $L$ in co-NP that can't be solved in polynomial time on a DTM, then there exists a language $L'$ in NP that can't be solved in polynomial time on a DTM (for instance, you can take $L'$ to be the complement of $L$).


Induction Proof on Independent Set Variation Algorithm So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise.

My algorithm is suppose to output impossible if there is no independent set of size k, or output an independent set of size k if it exists.

How might this be approached?

Let $G$ be a graph with an independent set of size $k$, and let $v$ be an arbitrary vertex. There are two potential types of independent sets of size $k$ in $G$:

Independent sets not containing $v$: These are independent sets of size $k$ in $G \setminus \{v\}$.
Independent sets containing $v$: These are formed by adding $v$ to independent sets of size $k-1$ in $G \setminus \{v\} \setminus N(v)$, where $N(v)$ is the neighborhood of $v$.

Using an oracle for independent set, we can find which of these cases happen.

The basic idea can be implemented in many ways. Here is a recursive implementation, which uses the oracle $O(G,k)$, which answers whether $G$ contains an independent set of size $k$.

Procedure $I(G,k)$
Input: Graph $G$ and integer $k \geq 1$
Output: Independent set of size $k$ in $G$, or "No" if none exists

If $O(G,k)$ returns "No", then return "No".
Let $v \in G$ be arbitrary.
If $k = 1$, return $\{v\}$. Otherwise, continue.
If $O(G \setminus \{v\},k)$ returns "Yes", return $I(G \setminus \{v\},k)$.
Otherwise, return $O(G \setminus \{v\} \setminus N(v),k-1) \cup \{k\}$.


What's wrong with the following shuffle algorithm? Suppose I have an array A of size n, with the initial state of:
A[0] == 1, A[1] = 2, ... A[n-1] = n

I know that one way to get a uniformly-distributed permutation of that array is to use Fisher-Yates Algorithm, but I am more interested in what's flawed with the following naive approach:
for i = 0 to n-1:
   rand_i = random(0, n-1, UNIFORM_DIST)
   swap(A[i], A[rand_i])

When I tried to use that with n = 3, it seems like some permutations are more likely to be drawn than others.
Here's the output of running the above algorithm 10,000,000 times, and then averaging on the results (shown in percentage of likelihood):
#> swap.out --iteartions 10000000
00: (1,2,3): 14.8237
01: (1,3,2): 18.5105
02: (2,1,3): 18.504
03: (2,3,1): 18.5216
04: (3,1,2): 14.7975
05: (3,2,1): 14.8427

To rule out the possibility that the Pseudo-Random-Generator is not uniform, I compared that with an algorithm that builds db of all permutations and then, using the same PRG - chooses one permutation:
#> choose_permutation.out --iterations 10000000
00: (1,2,3): 16.6847
01: (1,3,2): 16.6649
02: (2,1,3): 16.6731
03: (2,3,1): 16.6706
04: (3,1,2): 16.6516
05: (3,2,1): 16.655

This pattern is consistent; permutations 1,2,3 always come up with a higher likelihood than 0,4,5.
With n = 4:
#> swap.out --iteartions 10000000
00: (1,2,3,4): 3.90774
01: (1,2,4,3): 3.90958
02: (1,3,2,4): 3.91321
03: (1,3,4,2): 5.46167
04: (1,4,2,3): 4.29965
05: (1,4,3,2): 3.51932
06: (2,1,3,4): 3.89793
07: (2,1,4,3): 5.83975
08: (2,3,1,4): 5.45905
09: (2,3,4,1): 5.47537
10: (2,4,1,3): 4.30715
11: (2,4,3,1): 4.3
12: (3,1,2,4): 4.29691
13: (3,1,4,2): 4.3075
14: (3,2,1,4): 3.51411
15: (3,2,4,1): 4.29534
16: (3,4,1,2): 4.30452
17: (3,4,2,1): 3.90896
18: (4,1,2,3): 3.12621
19: (4,1,3,2): 3.50413
20: (4,2,1,3): 3.52526
21: (4,2,3,1): 3.12843
22: (4,3,1,2): 3.89564
23: (4,3,2,1): 3.90257

And comparing to randomly choosing from db of permutations:
#> choose_permutation.out --iterations 10000000
00: (1,2,3,4): 4.16284
01: (1,2,4,3): 4.16721
02: (1,3,2,4): 4.15893
03: (1,3,4,2): 4.17306
04: (1,4,2,3): 4.15853
05: (1,4,3,2): 4.16169
06: (2,1,3,4): 4.16584
07: (2,1,4,3): 4.17245
08: (2,3,1,4): 4.17309
09: (2,3,4,1): 4.15519
10: (2,4,1,3): 4.17007
11: (2,4,3,1): 4.17163
12: (3,1,2,4): 4.16276
13: (3,1,4,2): 4.17367
14: (3,2,1,4): 4.17147
15: (3,2,4,1): 4.16955
16: (3,4,1,2): 4.16576
17: (3,4,2,1): 4.1659
18: (4,1,2,3): 4.16653
19: (4,1,3,2): 4.16749
20: (4,2,1,3): 4.17225
21: (4,2,3,1): 4.1668
22: (4,3,1,2): 4.16797
23: (4,3,2,1): 4.15932

What's flawed with that method and why are those specific permutations come up more often?

This approach cannot work, for the following simple reason. The probability to obtain any permutation is of the form $A/n^n$, for integer $A$. However, we need it to be $1/n!$, so we need $A = n^n/n!$. Unfortunately, for $n \geq 3$ this is not an integer.

One can still ask why we might expect this algorithm to work, and where is the gap between our intuition and reality.
After the $i$'th step of the algorithm, $A[i]$ is a uniformly random element. So if we randomize $A[0]$, then $A[1]$, then $A[2]$, and so on until $A[n-1]$, won't we get a random permutation?
While it is true that $A[n-1]$ will be completely random, this is not the case for other entries. Indeed, let us try to analyze the distribution of $A[0]$ as the algorithm progresses.
After the first iteration, $A[0]$ is uniformly random.
After the second iteration, $A[1]$ is uniformly random, but this comes at a cost: we might have swapped $A[0]$ and $A[1]$. This means that $A[0]$ will have a slight preference towards $1$ (the original value of $A[1]$) and $0$ (the value of $A[1]$ in case it was swapped with $A[0]$).
Quantitatively, after the second iteration, if $i > 1$ then
$$ \Pr[A[0] = i] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) = \frac{1}{n} - \frac{1}{n^2}, $$
since this happens when $A[0]$ was swapped with $A[i]$, and $A[1]$ was not swapped with $A[0]$. Similarly,
$$ \Pr[A[0] = 0] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n}, $$
accounting for the additionally possibility in which $A[1]$ is swapped with $A[0]$ in the second round. Finally,
$$ \Pr[A[0] = 1] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \left(1 - \frac{1}{n}\right) \cdot \frac{1}{n} = \frac{2}{n} - \frac{2}{n^2}, $$
accounting for the possibility that $A[0]$ was not swapped with $A[1]$, but $A[1]$ was swapped with $A[0]$.
Similar phenomena persist throughout the algorithm.


Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one.

A greedy algorithm for this would keep removing digits such that the resulting integer is the smallest. For the above example:

Step 1: Remove 2 => 114532
Step 2: Remove 5 => 11432
Step 3: Remove 4 => 1132
Step 4: Remove 3 => 112

Can you prove that this algorithm is optimal (i.e. the final integer is the smallest possible)? Or if it is not, show a counterexample?

Thanks!

The greedy algorithm is optimal.

The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.

Given an $n$-digit number $A=a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is a digit, let $a_t$ be the rightmost digit of $A$ such that $a_n, a_{n-1}, \cdots, a_t$ is non-decreasing. Let $r$ be the number of all digits that are equal to $a_t$ from $a_t$ to its left. In other words, the digits of $A$ are classified as displayed in the following illustration for some integer $t$ and $r$, where $ a_t>a_{t-1}$ and $a_{t+r}<a_{t+r-1}=\cdots=a_{t+1}=a_t$. Note that if there is only one digit in $A$, it is $a_t$ with $t=0$ and $n=r=1$.
$$\begin{aligned}
A&=\overbrace{a_{n-1}a_{n-2}\cdots a_{t+r}\ \underbrace{a_{t+r-1}\cdots a_{t+1}a_t}_{r\text{ copies of }a_t}}^{\text{longest non-decreasing}}\ a_{t-1}\cdots a_0\\
\mu(A)&=a_{n-1}a_{n-2}\cdots a_{t+r}\{r\text{$-$}1\text{ copies of }a_t\}a_{t-1}\cdots a_0\\
\end{aligned}$$

Define integer $\mu(A)$ as shown above, which is $A$ but with one of $a_{t+r-1},\cdots,a_{t+1}, a_t$ removed. For example, $\mu(1214532)=114532$, $\mu(112)=11$, $\mu(40012)=0012$ and $\mu(0012)=001$. Note that the value of $\mu(A)$ does not depend on the number of leading $0$'s in $A$. For example, $\mu(001332)=00132$${}=\mu(1332)=132$.

Lemma. $\mu(A)$ is the smallest number that is $A$ with one digit removed.
Proof. Easy.

Let $G$ be the greedy algorithm. The lemma above says $G(A,k)=\mu^k(A)$.

Claim. For all non-negative integer pairs $(A,k)$, $G$ is optimal, i.e., $G$ returns the smallest number.
Proof. Let $P(k)$ be the proposition that $G(I,k)$ will return the smallest number for all integer $I$ of more than $k$ digits. The claim is $P(0)$, $P(1)$, $P(2)$, $\cdots$ are true.

Use induction on $k$. The base case, when $k=0$, is trivially true.

Assume $P(k)$, the induction hypothesis, is true. Let $A$ be an integer and $S$ be some $k+1$ digits of $A$ such that $B$, which is $A$ with digits in $S$ removed, is as small as possible. We will prove $G(A,k+1)\le B$, i.e, $P(k+1)$ is true, thus completing the induction.

Let us reuse the classification above of the digits of $A$, i.e., they start with the non-decreasing sequence $a_{n-1}, a_{n-2}, \cdots, a_{t}$ with $a_{t}>a_{t-1}$ and $ a_{t+r}<a_{t+r-1}$.

$S$ does not contain any digit in that sequence.

This cannot happen, since we can get a number smaller than $B$ by removing $a_{t}$ and arbitrary $k-1$ digits to the right of $a_{t-1}$.
$S$ does contain one of the digits in that sequence, say, $a_\ell$.

$S$ does not contain any one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.

We can modify $S$ by substituting $a_t$ for $a_\ell$. The removal of the digits in the modified $S$ will return a number smaller than $B$. So this case cannot happen, either.
Otherwise, WLOG, let $a_\ell$ be one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.

The lemma above tells us that $A$ with $a_\ell$ removed is $\mu(A)$. Let $S_-$ be $S$ without $a_\ell$. So $S_-$ are some $k$ digits of $\mu(A)$. We have the following diagram, where the arrow reads "become". $\require{AMScd}$
\begin{CD}
    \mu(A),k@>\text{greedy algorithm}>> G(\mu(A), k)\\
    @| \\
    \mu(A),k@>{\text {remove elements in }S_-}>> B\\
  \end{CD}

The induction hypothesis ensures $G(\mu(A), k)\le B$. Since $G(A,k+1)=G(\mu(A), k)$, we are done.

Exercise. (A couple of minutes or more) Given two positive integers $k\lt n$ and an $n$-digit integer $A>0$, how can you remove $k$ digits from $A$ such that the resulting integer is the biggest one? Explain the greedy algorithm. Prove it is correct.

The exercise shows that the greedy algorithm is still optimal in the original problem when $A$ is negative.


How do I determine the basic operation of this algorithm? Admissions:

Yes, this is a homework assignment.
No, this is not me trying to outsource my homework to the internet.

I am honestly fazed by my teacher's explanation of the "basic operation", and the internet is not helpful either. I get lists that say what a basic operation can be (e.g. assignment, multiplication, comparison), and what it is used for (determining time complexity) but not how to determine it for a given algorithm.

Here is the algorithm in question.

// Problem: Search a given value K in a given array A by sequential search
//Input:  array A[0..n − 1] and a search key K
//Output: The index of the first element in A that matches K and −1 if there are no matching elements.

SequentialSearch(A[0..n − 1], K)
{
   i ←0
  while i < n and A[i] ≠ K do
  {
    i ←i + 1
  }
  if i < n
     return i
  else
   return −1
}

The question: is the basic operation assignment, or comparison?

Candidates that I see:

Comparison: A[i] ≠ K
Assignment: i ←i + 1

The problem is that both of these would work to determine time complexity. The comparison is executed 1 time in best-case and n times in the worst-case scenario. The assignment is executed 0 times in best-case and n-1 times in worst-case. Towards infinity, constants do not matter, so really they both work equally well.

So the irony is that I know the time complexity of this algorithm, but not the basic operation which I am supposed to determine to figure out the time complexity.

What is the logic to use here to figure out which one is the basic operation, and which one isn't?

"Basic operations" are whatever you choose. You may get different results based on your choice, which is great as it leads to understanding algorithms better! You may have seen the number of comparisons and swaps being analyzed independently in array sorting algorithms.

As a corollary, your professor can pick whatever they want. We can't possibly know their mind; you'll have to ask them.

That said, if you're after "time complexity", you want to count how often a dominant operation occurs. See here and here (section "A note on asymptotic cost"). In case of doubt, just count all candidate operations.

  Getting different results based on my choice is something I also think is not applicable here, as the two options I am struggling between have identical results in when going towards infinite input sizes.

In that case, the choice doesn't matter. Either both operations are dominant and your result is correct, or they are both not and you need to pick another operation entirely.


$P=PP$ or $P=PSPACE$ vs $VP=VNP$ We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$?

Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$?

Is there a way to show $\#P$ is in $FP^{PP}$?

Note that $\#P\in FP^{PP}$ follows from a simple binary search. Given some non-deterministic machine $M$, the language $\{(x,k) |\#M(x)\ge k\}$, where $\#M(x)$ is the number of accepting paths on input $x$, is in PP (you can change the constant in the definition of PP to any FP function). Thus, using a PP oracle we can count the number of accepting paths via binary search.
This implies that $\mathsf{P=PP}$ puts permanent in $VP$, as the problem of counting the number of perfect matchings in a bipartite graph (or equivalently, computing the permanent of the adjacency matrix) is in $\#P$.


what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$ what steps should I take to find out what is the context free grammar of

$L(w) = \{a^i b^j c^k \mid k = |i-j| \}$

Use the fact that CF are closed under union, and start by considering cases, whether $i\ge j$ or $j\ge i$.

In the first case we get the language $L_1 = \{ a^i b^j c^k \mid k+j=i\}$, which is the same as $L_1 = \{ a^{k+j} b^j c^k \mid k,j \ge 0\}$.

Make a grammar for $L_1$, and then consider the second case.


PDA accepting of a specific symmetric language Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$.
if we have $a$ This side of the string, on the other side of the string we have $aa$.
and if we have $b$ This side of the string, on the other side of the string we have $bb$.
Examples of words in this language (middle point emphasized):
$ab\, bbaa$
$aaa\, aaaaaa$
$bab\, bbaabb$
What is a PDA accepting this language?
I can find a grammar for this language but I can't find a PDA.
The grammar: $S \to aSaa \mid bSbb \mid aaa\mid bbb$

There are general constructions that give a PDA given a CFG.
In this case, start with the PDA for $\{a^n b^n \colon n > 0\}$, instead of storing one $A$ on the stack for each input $a$, store two, and the same for $b$. When reaching the middle, start discounting and accept by empty stack.


What should be the minimum value when the two threads are executed concurrently int count=0;
void *thfunc()
{
    int ctr=0;
    for(ctr=0;ctr<100;ctr++)
    count++;
}

If *thfunc() is executed by two threads concurrently in a uniprocessor system, what will be the minimum value of count when both threads complete their execution? Assume that count++ is performed by using three instructions:(1) Read value of count from memory to a CPU register R,(2) Increment R,(3) Store the value in memory.

(a) 200

(b) 2

(c) 100

(d) None of the above

According to me, the answer should be 100. I cant find any execution sequence in which the count value can go down below 100. But my manual says that the answer is 2.

Can anyone please tell me what I am doing wrong? Also, please explain how the answer 2 is obtained?

Thanks in advance!

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory.

Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=?
Thread 2 performs 99 iterations. count=99, R1=0, R2=99
Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=99
Thread 2 starts iteration #100, performing only a read. count=1, R1=1, R2=1
Thread 1 performs the other 99 iterations. count=100, R1=100, R2=1
Thread 2 completes its iteration #100 (increment and write). count=2, R1=100, R2=2
Both threads now exit, having completed their execution.

So, the sequence is something like

rX = read by thread X
iX = local increment by thread X
wX = write by thread X

r1,
r2,i2,w2,r2,i2,w2,...,r2,i2,w2,  (99 full iterations)
i1,w1,
r2,
r1,i1,w1,r1,i1,w1,...,r1,i1,w1,  (99 full iterations)
i2,w2


How do Functional Reactive Programming and the Actor model relate to each other? FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete events) through potentially impure objects, called actors.

So on the surface they seem related.

What else can we say about how they related? Also, what can say about which of them might be more appropriate for different application domains?

Neither actors nor FRP are about streaming. Actors don't even support external configuration of an output stream.

FRP is strongly characterized by its modeling signals and events on a linear timeline, which enables FRP behaviors to compose in a deterministic manner. Actors are strongly characterized by processing messages in non-deterministic order, and have scarcely any compositional properties (i.e. you can't treat an arrangement of two actors as a larger actor).

If you're seeking similarities, both actors and FRP have a close relationship to lambda calculus. Both can model systems responsive to human input. Both support modeling of internal (local) state.

FRP supports local state through integrals or accumulators (fold over time), while actors model supports state by allowing each actor to specify its behavior for the next message in response to the current one. This pervasive support for local state makes both FRP and Actors inadequate for live programming (or runtime upgrade of program code); it becomes too easy to lose important state.

Regarding application domains:

Actors model is well suited for open systems, where we might wish to install or maintain actors at runtime. Actors model is also weakly suited to distributed systems, as the non-deterministic ordering of messages can make a conforming implementation easier. (The reason actors are not more strongly suited to distributed systems is that ensuring a message arrives 'once and only once' is quite difficult in the face of disruption, and actors also tend to require distributed GC, which is a pain.)

FRP is well suited to closed systems that operate over time - e.g. robotic controllers, music programming, computational toys. The determinism and compositional features make FRP more convenient to work with than actors, at least in those cases where FRP can directly model a solution. Integrating FRP with effects (elegantly, without hacking the model with impurity) has proven difficult. There has been recent work on effectful FRP via 'wormholes' - effectively, unique or linear typed access to resources.

There are other models that lie somewhere between FRP and Actors.

Flow Based Programming (FBP), developed by John Paul Morrison, really does support streaming of messages.

Time Warp protocols (or the more recent work on Lightweight Time Warp (LTW)) places actors-like messages on a logical timeline to provide a more controlled and compositional notion of message passing. Time warp is often used for large parallel and distributed systems, e.g. scientific computing. The original time warp was unsuited for interactive simulatons (responsiveness to human input), and LTW is only marginally suited.

I am developing Reactive Demand Programming (RDP) which enables responsive, compositional, FRP-like manipulation and processing of signals in open and distributed systems, and eliminates local state. RDP is achieved by constraining side-effects to commutative, idempotent influence on resource state by signals over time. RDP requires rethinking of resource and state models.


Mildly context-sensitive grammar Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context is either empty or consists of just one terminal).

Is the language defined by such a grammar necessarily context-free ?

In all the toy examples I considered, the original context-sensitive grammar can be enlarged into an equivalent context-free one.

You could have written a paper bases on your discovery had you been living many years ago.

In fact, the paper Terminal Context in Context-Sensitive Grammars by Ronald V. Book, 1972 mentioned by Yuval proved the following theorem, edited slightly for the sake of current question.

  Theorem 3. If $G$ is a context-sensitive grammar with terminals $\Sigma$, non-terminals $N$ such that every non-context-free rule is of the form $\alpha Z\beta \to \alpha\gamma \beta$ where $\alpha\in\Sigma^*$, $\beta\in\Sigma^*$ and $Z\in N$, then $L(G)$ is context-free.

The grammar in the theorem above is much more general than the grammar described in the question. In fact, if we restrict $\alpha$ to be empty and $\beta\in\Sigma$, we obtain the grammar described in the question.

You can check that article for a proof of the theorem as well as more insight into how to force context-sensitive grammars to be context-free. (You could probably write a paper if you solve the conjecture at the end of that paper.)

Here is one exercise that is within easy reach.

Exercise 1. If $G$ is a context-free grammar except one rule, which is of form $Aa\to Ba$, where $a$ is a terminal and $A$ and $B$ are two non-terminals, then $L(G)$ is context-free.


L = {w belongs to {0, 1} * ∣ w has at most three 0’s}. Why is this regular language? L = {w belongs to {0, 1}* ∣ w has at most three 0’s}. Why is this regular language?

According to pumping lemma, what I think is that....
Suppose $x$=$0^2$, $y$=$0^1$, $z$=$1^n$ ($w=xyz$=${0^2}{0^1}{1^n}$),  then if we pump $y$, we may have more than three $0$s. What am I missing?

As the other answers have said, the key is in the statement of the pumping lemma.

The key to understanding how to apply the pumping (and how not to as well) is paying close attention to the quantifiers ("for all" and "there exists") and the order they come in:

  The Pumping Lemma for Regular Languages

  If the language $L \subseteq \Sigma^{\ast}$ is regular, then there exists a constant $p \geq 1$ such that for every string $s \in L$ where $|s| \geq p$, there exists a division of $s = xyz$ such that:

  $|xy| \leq p$,
  $|y| \geq 1$, and
  for all $i \in \mathbb{N}$, $s' = xy^{i}z \in L$.

So if you wanted to show that a language obeyed the pumping lemma (note that is would not prove that it's regular, there are non-regular languages that can also be pumped), you have to first determine the pumping length $p$, then look at every string $s \in L$ and show that there is some way that $s$ can be broken down so that it can be pumped according to the conditions.

So in your case, if we ignore that you don't know $p$, the mistake is showing that one way of breaking it up doesn't work. So assuming that the pumping length is at least $4$ (it is, but why...?), then the breakdown $x = 000$, $y = 1$, $z = 1^{n-1}$ can quite happily be pumped.

When this has settled in, it also shows how the proofs of non-regularity via the pumping lemma work. You just have to find one string, but you have to show that there is no workable breakdown for that string.


Simple routing table question I'm having difficulties understanding the solution to the following question:

  Consider the following description of a LAN:

  The main Internet connection is connected to our gateway router. This
  in turn is part of the backbone network on the 65.21.1.0/24 subnet.
  The backbone also supports two further routers SALES and RESEARCH.
  There is one Sales subnetwork 65.21.6.0/23, and two research
  subnetworks 65.21.100.0/24 and 65.21.200.0/26.

If the Interface addresses are:

• i1–65.21.1.1
• i2–65.21.1.2
• i3–65.21.6.1
• i4–65.21.1.3
• i5–65.21.100.1
• i6–65.21.200.1

  What are the routing tables for the SALES and RESEARCH routers?

How is the via and interface column derived in the solution?

Thanks in advance.

This is a simple question on the definition of routing tables. I will add a brief explanation.

Let's take the SALES router. It has two interfaces.

The interface top (65.21.1.2) is connected to the network 65.21.1.0/24.

The interface bottom (65.21.6.1) is connected to the network 65.21.6.0/23.

This can be expressed as the following routing table:

network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/24     direct      bottom

Now we have two research networks accessible via the router RESEARCH. This router has an ip address 65.21.1.3 on the network 65.21.1.0/24. This network is already in the routing table, so the traffic to the research networks can be routed with the following rules.

network          via        interface
---------------+-----------+---------
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top

Finally the traffic to all other networks should be sent to the GATEWAY for further processing. Here is the final routing table.

network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/23     direct      bottom
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top
default          65.21.1.1   top

The routing table for the RESEARCH router can be assembled following the same logic.


QTM & Halting problem "Can QTM (Quantum Turing machine) solve halting problem"
Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the same proof which turing use it"
Let H be a program in a quantum turing machine that will solve the issue of halting , why not say that a contradiction will occur
Thanks

Because we can simulate QTM with DTM and it is an easier proof method than proving directly for QTM (which we can do). Also, this method of simulating a model with DTM to prove they are equivalent in power is somewhat a standard tool, not just for various TMs, but also for other computaitonal models ($\lambda$-calculus, RAM-machines,$\ldots$)

I think this question and answers address everything else you may be wondering

References on comparison between quantum computers and Turing machines


Is the image of a function the codomain of a function? Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012):

  Let $f$ be a function from $A$ to $B$, and let $S$ be a subset of $A$. The image
  of S under the function $f$ is the subset of $B$ that consists of the
  images of the elements of $S$. We denote the image of $S$ by $f(S)$, so:

  $f(S) = \{t \mid \exists s \in S (t = f(s)) \}.$

  We also use the shorthand $\{ f(s) \mid s \in S \}$ to denote this set.

So I guess I am just a little confused with the idea of an image. Is it the same as the codomain? And where it says, "The image of $S$ under the function ...".  What do you think it means by "under"?  Some examples would be great.

The image is the subset of the co-domain that the domain actually maps to. Take for instance the following function $$f: \mathbb{N} \rightarrow \mathbb{N}, \quad f(x) = 5.$$

It is simply the constant function that always "returns" 5, no matter what natural number is "passed in." The domain/co-domain defining $f$ is fine, but observe that the only value in the co-domain ever "used" is 5. In this case, the image of $f$ would just be the set $\{5\}.$

"The image of $S$ under $f$" is an explicit reference to the image of $f$ given $S$. That is to say, it is whatever each element in $S$ maps to as defined by $f$.


Are these sets of indices also index sets? An index set is a set of all indices of some family of computably enumerable sets.  It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set.

The following was an exam question I didn't manage to answer:

  Which of the following sets are index sets?

  1)  $\emptyset $

  2)  $K= \{ x \mid x \in W_x \}$

  3) $E = \{2,4,6,8, \dots \}$

  4) $\{ x \mid \phi_x = \phi_{x^2}\}$

I think:

It is known $K$ (i.e., the halting set) is not an index set so
(2) is ruled out.  I read on this on last page problem 4 that the set
of even numbers is an index set, so I'm not sure that (1) and (3) is
true!  But the answer sheet wrote just (1) is true.  I don't know what
is the definition of $E$ in (3) and not sure about (4).

Can anyone clarify me in order to better understand this challenging
 question?  Why are (3) and (4) not index sets?  I'm not familiar with
 notation (4), any description?

We start with a bit of notation:

$\phi_x$ is the partial function computed by program $x$.
$W_x = \operatorname{dom} \phi_x$, that is, the set of inputs on which program $x$ halts.
An index set is a set of programs $I$ such that if $\phi_x = \phi_y$ then $x \in I \Leftrightarrow y \in I$. (That is, $I$ is a union of equivalence classes of the equivalence relation $x \equiv y \Leftrightarrow \phi_x = \phi_y$.)

Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.

We can now go over the four sets in the question:

$\emptyset$ is trivially an index set.
$K = \{ e : e \in W_e \}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W_e = \{e\}$. There are infinitely many programs which halt only on input $e$ and output $\phi_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi_e = \phi_{e'}$. (This proof is taken from S. Barry Cooper, Computability Theory, mention by Pål GD in the comments.)
$E = \{2,4,6,8,\ldots\}$ is computable and so not an index set by Rice's theorem.
$\{ x : \phi_x = \phi_{x^2} \}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi_x = \phi_{x^2} = \phi_y$ then also $\phi_y = \phi_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi_x = \phi_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi_x = \phi_y$. It would be a major coincidence if for all $x,y$ we would have $\phi_y = \phi_{y^2}$.)

In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \{ x : \phi_x = \phi_{x^2} \}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.

For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:

$I$ can be an index set: Fix some admissible numbering $\phi_x$. Let $p_i$ be the $i$th prime. Define a new admissible numbering $\psi_x$ by $\psi_{p_i^k} = \phi_i$ for all $k \geq 1$, and $\psi_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi_x = \psi_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.
$I$ can be not an index set: Fix some admissible numbering $\phi_x$. Define a new admissible numbering $\psi_x$ by
$$ \psi_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi_{x-5} & x \geq 5 \end{cases} $$
In this case $\psi_1 = \psi_{1^2} = \psi_2$ but $\psi_2 \neq \psi_{2^2}$, showing that $I$ is not an index set.

I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.


Is it generally possible to convert CNF to Horn clauses? My intuition is that it is not generally possible, but I cannot think of a proof.

In "Renaming a Set of Clauses as a Horn Set" Harry Lewis showed that a CNF formula could be converted to Horn form iff a particular 2-CNF formula constructed from the original formula is satisfiable.  The satisfying assignment to the 2-CNF formula tells you which literals to flip.  The 2-CNF formula can be constructed in time quadratic to the number of literals appearing in the original formula.  Faster algorithms have been published since which reduce the problem of Horn-renaming a CNF formula to linear-time if it is possible to do at all.


Big-O Solving Recurrence Relation by iteration with fractions I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$  by following the accepted answer here. I expanded which resulted in $$ B(n) = B(n-8) + \frac{1}{n-1} + \frac{5}{(n-1)^{2} + 6} + \frac{7(n-1)^{2}}{3(n-1)^{3} + 8} + \frac{1}{n} + \frac{5}{n^{2} + 6} +  \frac{7n^{2}}{3n^{3} + 8}$$

This lead to $$ B(n) = B(n-4k) + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8} + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} +  \frac{7(n-k)^{2}}{3(n-k)^{3} + 8}$$ However, I get stuck when replacing $k$ with $n$ since this results in dividing by zero. How do I proceed? Can it solved by the iteration?

We can rewrite your recursion as
$$
B(n) = B(n-4) + \Theta\left(\frac{1}{n}\right).
$$
It follows that
$$
\begin{align*}
B(n) &= \Theta\left(\frac{1}{n} + \frac{1}{n-4} + \frac{1}{n-8} + \cdots\right) \\ &=
\Theta\left(\frac{1}{n/4} + \frac{1}{n/4-1} + \frac{1}{n/4-2} + \cdots \right) \\ &=
\Theta(\log (n/4)) = \Theta(\log n),
\end{align*}
$$
using the formula for the sum of a harmonic series.


How to enumerate combinations in parallel I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried to do it with Matlab but it takes too long time specially when $n>20$ and I couldn't find a way how to generate in parallel the $n\choose k$ indices.

I found online a paper titled A Parallel Algorithm for Enumerating Combinations but they didn't provide their code in that paper.

Since you just need to select $k$ rows, this becomes the same as choosing $k$ elements of a given set of $n$ elements, say $\{1,2,\dots,n\}$.

You can generate $n \choose k$ combinations in lexicographic order (i.e. starting with $\{1,2,3, \dots, k\}$ and ending with $\{n-k+1, ..., n-1,n\}$), with the next one depending only on the previous one.

The fact that the order is predictable, and that you only need the previous state, allows you to split the output space, and apply independent parallel computations to each.

There are plenty of algorithms available on the web for lexicographic generation, for instance Frank Ruskey's book: Combinatorial Generation has a chapter (4) on lexicographic algorithms, and for your purposes, you can use Algorithm 4.4 which appears on page 58.


Can the program determine the frequency of the CPU or is it impossible? In order to understand the question, imagine a simple situation. Alice tells Bob that her CPU's frequency is X Hz. Bob does not take her word for it. Bob can not meet with Alice and check what frequency her processor really has. Can Bob send her a soft program that accurately determines the frequency of Alice's CPU? Is such a program possible or not in principle?

In these days of superscalar, multicore, virtualisation, power scaling, managed operating systems, and so on, what does "CPU frequency" even mean?

Note that it may be possible for Alice to convince Bob that she has compute power capable of performing X operations of a known type in a given time, as you find in a proof-of-work system. If it is a problem for which parallel algorithms are believed not to be feasible, he may be convinced that it happened on a single compute device, and not (say) a cloud or cluster.

But for all Bob knows, Alice may have an asynchronous device which doesn't even have a clock speed.


Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our resources and $G$ is our necessary minimal reward, is there a set $R' \subseteq R$, so that $\sum_{(z,g)\in R'}z \leq Z$ and $\sum_{(z,g)\in R'}g \geq G$?
I want to show its NP-completeness and have shown that it is in NP already. I am struggling with the NP-hardness. My known NP-hard problems are the SAT, 3SAT, partition, subset sum and bin packing.
My struggle seems to be mostly with the fact that we have to balance two different values now, the cost and the reward. This is not the case in any of the set related problems I mentioned and I am unable to think of how to model this in SAT or 3SAT. What am I missing here? How can I show the NP-hardness and as such the NP-completeness of this problem using only these given problems?

This sounds to me like the Knapsack problem where

$z$ is the weight of each item,
$Z$ is the capacity of the knapsack,
$g$ the value of the item, and
$G$ the value to be achieved.

The problem is NP-complete but solvable, using dynamic programming, in pseudo-polynomial time $O(n \cdot W)$ where $W = \max_{(z,g) \in R}(g)$.
You can prove that the Knapsack Problem is NP-complete by reducing from the Subset sum problem.  Indeed, Subset Sum is a special case of Knapsack where $z = g$; The "weight" of each problem is the same as its "value".


"Fuzzy" Chinese Remainder Theorem I have some "fuzzy" congruences like these:
\begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \text{ with } a_3 \in \{5,6\}\\ \end{align}
These example moduli would provide a unique solution for $x \mod lcm(3,5,7)$, if the $a_i$ were fixed.
Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \mod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, there exists an additional condition, which provides an upper bound for $x$. For example:
\begin{align} x \mod lcm(3*5*7) &< 5 \end{align}

We can assume that all moduli $m_i$ are primes, f.e. $lcm(m_1,m_2,...) = \prod_i m_i$.
Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example). Additionally, the possible values of $a_i$ are consecutive ($a_2 \in \{1,3,4\}$ is not allowed).
So the generic equations look like:
\begin{align} x&\equiv a_i \mod m_i &\text{ with } a_i \in U_i \text{ and } U_i \subset \{0,1,...,m_i-1\} \wedge |U_i| = t \wedge \\&&\forall i,j: |i-j|=1 \Rightarrow |U_i[i]-U_i[j]| = 1
\\ x \mod \prod_i m_i &< k \end{align}

Is it partical feasible to calculate one solution for parameters like $\prod_i m_i \approx 10^{1000}$, all $m_i < 100000$, $k \approx 10^{50}$ and $t \approx 50$?

I tried to use the Chinese Remainder Theorem Method to find a solution for x:

Set $M_i:=lcm(m_1,m_2,...)/m_i$. It holds $gcd(M_i,m_i)=1$.

Hence, we can use the Extended Euclidean algorithm to find 2 Integers $r_i$ und $s_i$, which fulfill $r_i \cdot m_i + s_i \cdot M_i = 1$.

Set $e_i:=s_i \cdot M_i$, then \begin{align} e_i &\equiv 1 \mod m_i \\ e_i &\equiv 0 \mod m_j, j \neq i\end{align}.

The number $x:=\sum_{i=1}^n a_i \cdot e_i \mod lcm(m_1,m_2,...)$ is a solution.

Now i tried to solve $(\sum_{i=1}^n a_i \cdot e_i \mod \prod_i m_i) < k$ with $minValue(U_i) <= a_i <= maxValue(U_i)$.

These equations can be formulated as an Integer Programming instance (add an additional variable for the mod Operation). I tried to use mathematica to solve these, but it seems unfeasible even for "small" parameters like $\prod_i m_i \approx 10^{50}$, all $m_i < 1000$, $k \approx 10^{2}$ and $t = 3$.

Is there a more efficent way to solve this?

This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.


Decidability of a problem concerning polynomials I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite exact representation of these polynomials). If needed, we may suppose that the degree of both polynomials is equal. Let us denote by $x_p$ (resp. $x_q$) the greatest absolute value of some (real or complex) root of the polynomial $p$ (resp. $q$). Is the property $x_p = x_q$ decidable?

If not, does this property hold for some restricted families of polynomials? In the context from which this problem arises, the polynomials are characteristic polynomials of matrices, and their roots are eigenvalues.

I am aware of some numerical algorithms for computing roots of polynomials / eigenvalues, however these seem to be of no use here, since the output of these algorithms is only approximate. It seems to me that computer algebra might be useful here, however, unfortunately, I do not have almost any knowledge in that field.

I am not searching for a detailed solution to this problem, however any intuition and ideas where to search for the solution would be helpful.

Thank you in advance.

I'm not knowledgeable in that field either, but I think I can provide a non-constructive answer.
The first-order theory of real closed fields is decidable. Your problem can be stated as a system of algebraic equations and inequations over the real algebraic numbers. Consider $2 (\deg P + \deg Q)$ variables $x_1,\ldots,x_{\deg P}, y_1,\ldots,y_{\deg P}, x'_1,\ldots,x'_{\deg P}, y'_1,\ldots,y'_{\deg P}$. You want to know whether the following system is satisfiable:
$$\begin{align*}
  P(x_j+i\,y_j) &= 0 & \text{for \(1 \le j \le \deg P\)} \\
  Q(x'_k+i\,y'_k) &= 0 & \text{for \(1 \le k \le \deg Q\)} \\
  x_j^2 + y_j^k &\le x_1^2 + x_2^2 & \text{for \(2 \le j \le \deg P\)} \\
  {x'}_j^2 + {y'}_j^k &\le {x'}_1^2 + {x'}_2^2 & \text{for \(2 \le k \le \deg Q\)} \\
  x_1^2 + y_1^2 = {x'}_1^2 + {y'}_1^2 \\
\end{align*}$$
The first two equation families express that the $x_j+i\,y_j$ and $x'_k+i\,y'_k$ are roots of the polynomials, the next two inequation families express that $x_1+i\,y_1$ and $x'_1+i\,y'_1$ have the largest absolute value, and the last inequation compares these largest absolute values.
It is decidable whether this system is satisfiable: your problem is decidable. However, this statement is probably not the most efficient way to go about it.
A more useful answer probably involves the theory of Gröbner bases. If you're trying to solve that problem for yourself, I think reading the first few chapters of any computational algebra book will give you the requisite background. If you're just aiming to solve your underlying problem, there is probably an off-the-shelf algorithm you can implement.


Why is GFp -> GFq false in LTL, even though GFp and GFq are false? Consider the Kripke structure:
$$
\begin{array}{ccccccc}
  \to & (p, \neg q) & \to & (\neg p, \neg q) & \to & (\neg p, q) \\
  & \circlearrowright & & \circlearrowright & & \circlearrowright & \\
\end{array}
$$

where $(p, \neg q)$ means “$p$ and not $q$” and $\circlearrowright$ is a self loop. We number the states $s_1, s_2, s_3$ from left to right.
Now consider the three LTL properties:
$$
\begin{array}{ll}
  M \vDash \mathbf{G}\,\mathbf{F}\,p \to \mathbf{G}\,\mathbf{F}\,q & \text{false} \\
  M \vDash \mathbf{G}\,\mathbf{F}\,p & \text{false} \\
  M \vDash \mathbf{G}\,\mathbf{F}\,q & \text{false} \\
\end{array}$$

The oddity is this: how can $\text{false} \to \text{false}$ be false?

P.S.: I am sure of the results because I used NuSMV with the following code:

MODULE main
VAR
   state : {a, b, c};
   p : boolean;
   q : boolean;

ASSIGN
   init(state) := a;
   next(state) :=
       case
         state=a : {a,b};
         state=b : c;
         state=c : c;
   esac;
p :=
  case
    state=a : TRUE;
    state=b : FALSE;
    state=c : FALSE;
  esac;
q :=
  case
    state=a : FALSE;
    state=b : FALSE;
    state=c : TRUE;
  esac;

LTLSPEC
   ((G ( F p = TRUE)) ->  (G ( F q = TRUE)))
LTLSPEC
   (G ( F p = TRUE))
LTLSPEC
   (G ( F q = TRUE))

This happens because of the way LTL formulae are evaluated over Kripke structures: Recall that LTL is first of all a logic of traces; when we say that a Kripke structure $S$ satisfies $\varphi$, we mean that all its traces do, i.e. we have an implicit universal quantification.

The consequence is that, for an LTL formula $\varphi$, it is possible that neither $\varphi$ nor $\neg\varphi$ is true for $S$, because neither holds for all traces. Similarly, none of your three formulas above holds for every trace.

If you are more familiar with predicate calculus, this is just saying that $(\forall x.A)\vee(\forall x.\neg A)$ is not a tautology, and neither is $(\forall x.A)\vee(\forall x.B)\vee(\forall x.A\to B)$.


How can MLTT etc encode computability? I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For sure" is a good source for surprises so I think I should try to prove it, probably formally.

But then I recall MLTT is compatible with LEM, and now my brain is in a loop:

To prove that theory is undecidable, I have to show that

forall x y ... z, ~({P x y ... z} + {~P x y ... z})

where x y ... z are the parameters. Namely, it's not true that we can decide the problem for all inputs.

On the other hand, LEM claims that for all P x y ... z we can obtain either witness or refutation, and its compatibility with type theory just says the falsehood is not provable. This means MLTT and others are just not able to express computability problems. Therefore, I am wondering can formal systems encode computability at all, or it's just I am mistaken? Is there anyone actually tried to formally prove undecidability in formal systems like Coq?

Even though I am using Coq, but since the compatibility is from MLTT, so I guess LEM does not have to live in Prop.

Apologies if I am being stupid for the moment but I think my brain is in a serious loop now.

You have your quantifiers wrong. The ~ should be on the outermost level. That is:

~(forall x y z, {P x y z} + ~{P x y z})

i.e. to prove it's undecidable, you assert that there's no function which decides every instance. There may be functions which decide particular instances, which your type would rule out.

If you add LEM to MLTT, you can still have a perfectly good logic system, but provability in this logic no longer implies decidability.

Moreover, even the type I've listed above isn't sufficient: just because a problem isnt' expressible in MLTT or COC or any other non-Turing-complete logic, doesn't mean that it's undecidable.

A better approach would be model Turing Machines or (even better) a Turing Complete Lambda Calculus in your language, and assert that there are no functions in this model that always halt and answer your problem. This way, you're not trying to use your logic to reason about decidability within that logic, but an external model.

If you want an easier way, you could provide a function that takes as a parameter a function of type forall x y z . {P x y z} + ~{P x y z}, and returns a decision procedure deciding a commonly undecidable problem. (My favorite is Post's Correspondence, simulating a 2-counter machine is also an easy one). This reduces the trusted base of your proof: now the reader only needs to believe that PCP or 2CM is undecidable in order to see that your problem is.


Practical application of Finite State Machines I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...

It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in string matching like KMP algorithm.

What is the significance of NFA, Moore and Mealy machines?

Each time you do a search (particularly a "pattern search") in your favorite editor/tool, the pattern is translated into some form of finite state machine, which does the matching.

The lexical analysis part of your compiler/interpreter (yes, even your shell) is again a finite automaton which matches keywords and other tokens recognized by the language.

Any vending machine is a finite automaton which takes in coins of different denominations and recognizes when the correct amount has been entered (OK, today's vending machines probably have a small CPU inside doing the adding, but the end result is the same).


Defining Gap Problems I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across online are somewhat inaccurate and confusing.

Specifically, the concept of gap problems wasn't completely clear to me. It was presented to us that gap problems are a way to formulate decision problems from approximation problems. However, it seems to me that a gap problem isn't precisely a decision problem (or, let's say, a language), but rather a set of decision problems/languages that satisfy two common conditions.

For example, I would think that gap-$IndependentSet[a,b]$ could be defined as the set of all languages $L$ such that:

If $G=(V,E)$ has an independent set of size $>b$ than necessarily $G\in L$
If $G=(V,E)$ doesn't have an independent set of size $>a$ than necessarily $G\notin L$

If such a definition for a gap problem is valid, then I think two more definitions need clarification:

A gap-preserving-reduction isn't in fact a proper Karp reduction, because it doesn't map a single language to another language. Rather, it maps certain "good inputs" to other "good inputs" and "bad inputs" to other "bad inputs", without having any requirements about the rest of the inputs.
A gap problem cannot be an element of a complexity class (such as $NP$), but rather a subset of the class. In that case, saying that a certain gap problem is $NP$-complete would actually mean that all languages in the problem are $NP$-complete

Is this a valid way to think about the subject? Am I just confusing myself? Should I stick to the basic intuition and not try to define approximation related concepts in these terms?

Gap problems are examples of promise problems, which are really the three-valued logic analogs of languages: some elements are in the language, some elements are not, and for the rest, we don't care.

A promise problem is in P if there is a polynomial time algorithm that answers Yes on all Yes instances and No on all No instances; we don't care what it answers on the don't care instances.

A promise problem $L$ is NP-hard if for every NP problem $L'$ there is a polytime reduction $f$ such that if $x \in L'$ then $f(x)$ is a Yes instance of $L$, and if $x \notin L'$ then $f(x)$ is a No instance of $L$.

We can similarly define the analogs of many other properties of languages. Usually this is done in an ad-hoc basis. We definitely think of promise problems as single languages rather than as a class of languages.


Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right? I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I thought there could only possibly be one block, since linear probing will go through all addresses sequentially?

For single key, there is only one block. But as it grows, it may reach the next cluster, making this cluster much larger:

aaaa.bbbb...

Here aaaa is cluster for "a" key, and bbbb is cluster for "b" key. Once you fill the first "." entry with data, clusters are combined. Now the next item for "a" key will be inserted after bbbb, so find() operation need to search the entire cluster:

aaaaabbbba..

There are techniques such as Robin Hood hashing which keeps all keys sorted by the position of the first entry where they can be stored, so the same data will build the following table:

aaaaaabbbb..


How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding When storing the encoded Huffman bit stream in bytes, in general, either

the final byte gets padded or
a pseudo end-of-file symbol gets used

In the former case, the number of bits padded needs to be stored somewhere, requiring another 3 bits. In the latter, you will lose some efficiency due to the additional pseudo symbol.

So how can I avoid the extra cost of a pseudo symbol, and also avoiding the need to store/transmit extra bits to hold the number of pad bits?

N.B. On the one hand, I'm interested in compressing short strings, so saving 3 bits on average can shave off another 1% or so of the data.

But more importantly, getting rid of the need to send the padding info (which is only known after compressing the whole string) before the encoded data means I can more easily perform the algorithm in a streaming fashion. This is not really necessary for short strings, where everything may be kept in memory, but sometimes my strings actually do get much longer, and I don't want to have to keep that in memory (considering there are hundreds of simultaneous encodings going on).

There's a way that neither needs to store the number of padded bits, nor - in most real life scenarios *) - add a pseudo symbol.

The idea is this: The maximum padding is 7 bits, so if after the last encoded symbol, we pad with the first bits of a symbol that is encoded as 8 or more bits, the decoder will stop in the middle of decoding when the bit stream finishes, so no extraneous symbol gets decoded.

For this to work, the total byte length of the Huffman encoded data needs to be known when decoding.

*) If there is no existing symbol of length 8 or longer, then an end-of-file pseudo-symbol needs to be created. This should be added with the least possible frequency, in order not to make the encoding of real symbols grow in length, if possible. The length of the end-of-file symbol does not matter. If it is shorter than 8 bits, it can just be repeated multiple times to pad the last byte, and if longer than 8 bits, only the first bits necessary to pad the final byte will be used.


Algorithm for generating coprime number sequences? Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother?

Ideally I'm looking for something that has random access abilities so i could ask for the 100th item in the set without having to first calculate items 0 to 99.

Also, I would like to be able to specify a minimum value for these numbers, to specify that none of them should less than 50 for example.

Does anyone know of an algorithm to do this, or at least satisfy part of my asks?

Thanks!

Yes.  It's possible to satisfy all of your requirements, by combining some standard tools:

Let $F$ be a function that, given a sequence of random bits as input, outputs a random 1000-bit prime.  $F$ can be implemented by repeatedly picking a random 1000-bit number, then using a primality test to check if it is prime, and outputting the first prime number you see.
Let $G$ be a pseudorandom generator that expands a short random seed to a long sequence of pseudorandom numbers, e.g., AES-CTR mode.
Let $H$ be a cryptographic hash function, e.g., SHA256.
Let $s$ be a random seed.

Now define

$$f(i) = F(G(H(s,i))).$$

Then the sequence

$$f(1),f(2),f(3),f(4),f(5),\dots$$

satisfies all of your requirements:

Every number in the sequence is prime, and it is super-unlikely that any prime will repeat (this can be quantified using the birthday paradox), so all of the numbers in the sequence are co-prime.
It is super-unlikely that any number will be less than 50.  If you prefer an absolute guarantee, you can tweak the definition of $F$ to require that the number is both prime and at least your lower bound.
The sequence can be efficiently computed: each of the building blocks $F,G,H$ has efficient instantiations, so $f$ can be computed efficiently.  Moreover, this construction permits efficient random access into the sequence.


Modelling regex replacement via a DFA I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis:

s = <string matching regex R1>
t = s.replace(<regex R2>, <string matching regex R3>)
# What is the set of possible strings of t?

More formally, given DFAs $R_1$, $R_2$, and $R_3$, I want to find some automaton $R_o$ that is the result of replacing substrings of $R_1$ that are accepted by $R_2$ by some string that is accepted by $R_3$.

Unfortunately, while the literature seems to discuss this, I am unable to pin down a precise implementation of this operation. In addition, I am having trouble even defining the set of strings that $R_o$ should accept. Does there exist an algorithm to solve this problem? Is it even solvable in general?

Depending on the exact semantics of the replace operation (regarding multiple matches, overlapping matches, etc.), it can likely be modelled as a finite-state transducer.  The set of possible values of s can be modelled as a regular language.  It is known that the application of a finite-state transducer to a regular language gives you another regular language, and there are standard algorithms for computing it, using the product construction.


What are some examples of types that can't be derived set theoretically? I'm hoping for examples that aren't too abstract or useless in day-to-day programming, though not with a lot of hope, since in Bartosz Milewski's book, it is stated that generally speaking, the category Set is good enough, but mentions polymorphic functions and there not being a set that includes all sets as being one possible example.

For polymorphic functions, I'm not really sure how this comes up. For example, with id[A](x: A): x -> x, where A is a type parameter, I do not see why we could not just say: A is a member of the type universe corresponding to our programming language, which would just be the set of all types supported by our language. Perhaps if our programming language supports a type universe hierarchy, then this argument could be made, but I do not know if any languages do support it in any meaningful way (perhaps theorem proving languages like CoQ?)

Notes on answers

Recursively defined types

For type t = bool + (t -> t), since we assume t corresponds to a set T, t->t would be size T^T (ref). In Scala it looks like this:

sealed trait T
final case class Foo(value: Boolean) extends T
final case class Bar(value: T => T) extends T

There are several type-theoretic constructions that cannot be easily handled with set theory. Note that when we say "set theory" we mean that we intend to interpret types as sets and type-theoretic functions as set-theoretic functions. In particular, the set-theoretic interpretation of types requires that a function type A → B must be interpreted as the set of all set-theoretic functions from A to B.

If our type theory has general recursion then it cannot be interpreted set-theoretically. General recursion allows us to define, for any type A, the fixed-point operator fix : (A → A) → A

fix f = f (fix f)

but the only sets which have such a fixed-point operator are the singletons. For example, if we take A to have two elements, then it will have a function without fixed point (the one that swaps the elements).

Another reason that set theory may not be sufficient is polymorphism, as you indicated. Here the reasons are perhaps a bit technical and it is best to read the famous paper Polymorphism is not set-theoretic by John Reynolds. Beware: reasoning about how one might get away with a polymorphic identity function is not proof that set theory models polymorphism. In any case, your suggestion to use universes is not going to work for System F. You can have an identity function that works for one universe, but to make it work for all universes you will have to make it universe-polymorphic, and so you're back to square one.

A third reason that a type theory may not be set-theoretic is that it allows constructions of types that do not exist in set theory. For example, in many programming languages we can define recursive types (Haskell and ML are like this) such as

type t = bool + (t -> t)

The set-theoretic counterpart of this is a set T such that
$$T \cong 2 + T^T$$
but such a set $T$ does not exist, because the cardinality of $2 + T^T$ is strcictly larger than the cardinality of $T$.

A fourth reason that a type theory may not be set-theoretic is that it may contain constructs that prevent this. For example, we could have a type theory with a timeout construct which works as follows: timeout k x e computes e for at most k steps (where "step" need to be suitably defined). If e finishes with result y within k steps then the overall result is y, otherwise the overall result is the "fallback" value x. From a programming point of view, this is a reasonable construct that can actually be implemented. However, as soon as we have timeout we can write down functions that do not exist in set theory. One such function is the modulus of continuity which witnesses the fact that "all functions are continuous". In set theory there are many discontinuous functions.

Lastly, if we take "spartan" type theory without any special features (no general recursion, no polymorphism, no recursive types, etc.) then it is set theoretic. You need to extend type theory in some fashion to break the set-theoretic interpretation.


"Insensitive" CNF/DNF SAT always satisfying same number of clauses I came across this paper, which mentions an interesting variation on SAT:

  We call a CNF formula F insensitive if every total assignment α satisfies the same number of clauses of  F.

I hadn't come across this before. You can easily define the same property for DNF formulae as well.

Which brings me to the following question:

Given either a DNF or CNF formula, how hard is it to tell if the formula is insensitive?

It is clear that the decision problem "is this formula insensitive?" for both DNF and CNF is in co-NP, because two assignments satisfying different numbers of clauses serve as a "no" certificate. Its complement, which is "is this formula sensitive?" is in NP. But are these problems complete in their respective classes?

I suspect the answer is "yes," because most variants of SAT turn out to be NP-complete. But I don't know how to prove this, and I cannot find any information on "insensitive" formulas outside of this paper. Does any info on this exist?

Consider a DNF $C_1 \lor \cdots \lor C_m$.

For any clause $C_i$, we can compute the probability that a random assignment satisfies $C_i$: it is 0 if $C_i$ contains both a variable and its negation, and otherwise it is $2^{-|C_i|}$, where $|C_i|$ is the number of literals in $C_i$.

For any two clauses $C_i,C_j$, we can compute the probability that a random assignment satisfies both $C_i$ and $C_j$: it is just the probability that a random assignment satisfies $C_i \land C_j$.

Given this data, it is routine to compute the variance of the number of satisfied clauses under a random assignment. The DNF is insensitive iff the variance is zero. The corresponding algorithm runs in polynomial time, and so the problem is in $\mathsf{P}$.

If we have a CNF, we can negate it to obtain a DNF which is insensitive iff the original CNF is.


Intuitive proof for a tree with n nodes, has n-1 edges I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.

You can see a (binary) tree as a directed graph: suppose the root is the "lowest" node and the leaves are the "highest" ones, then say that all the edges are oriented upwards. Then, every node that is not the root will have exactly one edge entering in it, and every edge will be pointing at exactly one node. This means that if you have $n$ nodes, you have to have $n-1$ edges (one per node with the exception of the root).


Is the following language context free? Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.

$L$ is not context free. You can use the Ogden's lemma to show it.

I'll use the Wikipedia notation linked above.

For every $p$ take the word $a^pb^pc^p$. For a the marking where only c are marked whatever the decomposition $uxyzv$ you take, $ux^iyz^iv$ will not be in $L$.
Four cases: $z\in c^*$ then it fails for $i=0$ or $z\notin c^*$ then it fails for $i>0$. And the symmetric cases for $x$.

Hope it helps.


Representing Negative and Complex Numbers Using Lambda Calculus Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?

First encode natural numbers and pairs, as described by jmad.

Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus):

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

The case of complex numbers is similar in the sense that a complex number is encoded as a pair of reals. But a more complicated question is how to encode reals. Here you have to do more work:

Encode a rational number $q$ as a pair $(k,a)$ where $k$ is an integer, $a$ is natural, and $q = k / (1 + a)$.
Encode a real number $x$ by a function $f$ such that for every natural $k \in \mathbb{N}$, $f k$ encodes a rational number $q$ such that $|x - q| < 2^{-k}$. In other words, a real is encoded as a sequence of rationals converging to it at the rate $k \mapsto 2^{-k}$.

Encoding reals is a lot of work and you do not want to actually do it in the $\lambda$-calculus. But see for example the etc/haskell subdirectory of Marshall for a simple implementation of reals in pure Haskell. This could in principle be translated to the pure $\lambda$-calculus.


Standard notation for the language of the universal Turing machine? The universal Turing machine $U_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does.  The language of the universal TM is the set of all encodings of a TM/string pair as a string for which the TM accepts the string.

I have seen several different names for the language of the universal Turing machine.  Michael Sipser refers to it as $A_{TM}$ (the acceptance language for Turing machines), while Hopcroft, Ullman, and Motwani call it $L_u$ (the universal language).

Is the a standardized term for the language of the universal Turing machine?  I would understand if there might be many "universal Turing machines" that vary in their encoding schemes, so if the answer is "no, there is no general term for this" that would be good to know.  I'm mostly asking because I'm teaching an introductory course in the theory of computation and have been using the term $A_{TM}$ for this without knowing if there is a better term to use.

Thanks!


Does Subset Sum allow multisets? In the Subset Sum problem can some of the given numbers $a_1,a_2,a_3,\dots,a_n$ be the same? For example, we might have $[1,1,1,2,3,4]$ and the target is $5$? Can I assume that I have a specific solution with numbers $2$ and $3$ and $1,1,1$ and $2$ is not?

One question we could ask is "Can we reduce this back to the subset sum problem?" In this case, the answer is yes: for each duplicate $z$ we replace it with two numbers $x$ and $y$ such that $x+y=z$.
$$[-1,-1,2,3]\to [-7,-1,2,3,6]$$

However, we need to be careful that we don't introduce additional solutions (those using just $x$ without $y$), which we can do by making $x>\lvert \Sigma(a_i)\rvert$ for $a_i<0\in A$, and $y<-\lvert\Sigma(a_i)\rvert$ for $a_i>0 \in A$. Specifically, this precludes the use of $x$ without $y$ (and vice versa) by making the sum of $x$ and all negative numbers strictly above zero (and thus doesn't satisfy the traditional subset sum problem).