Does Turing Machine divergence depend on the input? If there is a Turing Machine $M_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?

No. It is very easy to reduce $A_{TM}=\{(M,w): M$ accepts $w\}$ to the complement of the problem you describe: given input $(M,w)$, output a machine $M'$ that simulates $M(w)$. If $M$ accepts $w$ then $M'$ halts and accepts. Otherwise, $M'$ goes into an infinite loop (either if $M$ loops on $w$, or manually if $M$ rejects $w$).

Now, if $M$ accepts $w$, then $M'$ does not diverge on every input, and otherwise it does.


Most Efficient Way to List All $n$-bit Permutations Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers).  What are some efficient ways to do such a listing using as few bits as possible?

Attempt: My thought is that the verbose listing of all $n$-bit numbers has a lot of redundancy, so if we start by listing all $2^n$ numbers, $2^{n-1}$ of those numbers will have a number that is identical except for one bit (that has been previously listed)––so we can drop the $n^{th}$ bit of those $2^{n-1}$ numbers.  Now among that same set of $2^{n-1}$ numbers, there will be $2^{n-2}$ values that will have a number  that is identical until the last two bits, so we can drop the $n-1^{th}$ bit of those $2^{n-2}$ numbers as well.  Continuing on iteratively, we can find $2^{n-k}$ numbers that can have the final bit dropped, with $k=1,2,3,4,...n$. Finally, there is one number that can be eliminated entirely (intuitively, this makes sense because the last number in a known set can always be determined if we know all others).

Here is an example that lists all 3-bit numbers (in increasing order):

000
00
010
0
100
10
110
.

It seems like we can model the number of bits this method uses as such:
$$2^{n-1}n + 2^{n-2}(n-1) + ... + 2^1(2) + 2^{0}(1) = \sum_{k=0}^{n-1} 2^k(k+1) = 2^n(n-1)+1$$

(saving $2^n -1$ bits from the verbose $2^n*n$ version)

Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists.  Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $\lceil log_2(2^n!)\rceil$ bits.

In practice, you can come arbitrarily close to this bound using arithmetic encoding, without having to manipulate very large integers.


Find 2 sets with an empty intersection I have the following problem. The problem can be formulated in three different ways

Given sets $B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy $B_i \cap B_j = \emptyset$

"Invert" the sets $B_i$

Define $A_k=\{i: k\in B_i \}$. $A_1, \ldots, A_m \subset \{-n,\ldots,n\}$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property $\{i,j\} \not\subset A_k$ for all $k=1,\ldots,m$

Relation instead of set of sets

Define relation $R\subset\{1,\ldots,m\}\times\{-n,\ldots,n\}$ with $kRi \equiv k \in B_i$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property for no $k=1,\ldots,m: kRi \land kRj$

Naive Algorithm

As far as I can tell, the 3 problems are the same thing viewed from slightly different perspectives. One possible algorithm would be to iterate through all pairs $(i,j)$ and check if the condition is satisfied. This algorithm has runtime of $\mathcal{O}(n^2\cdot f(m,n))$ with the runtime $f$ of the check if the pair satisfies the property.

Specifically for the first case:
Assuming the sets are implemented sorted lists the intersection can be checked to be empty in $\mathcal{O}(m)$ time via a simple mergesort-like scan.

Question

Is there an algorithm for this problem that solves it in $\mathcal{o}(n^2)$ time? (maybe with some tradeoff in the $m$ component)

Here is one example for an algorithm, which can run at $O(4^m \cdot m+ n\cdot m)$ time, which is $o(n^2)$ if $m\ll c\log n$ for every $c<0.5$.

We convert a subset $B_i$ into an ordinal number $1\leq j\leq 2^m$, a number of $m$-bits, in $O(m)$ time, where the $k^{\text{th}}$ bit of $j$ euqals one iff $k\in B_i$. Now, for every ordinal number $j$ we save a link list $L_j$ which contains pointers to all subsets $B_i$ that are associated with ordinal number $j$. This can be done in $O(n\cdot m)$ time.

Second, since all subsets with the same ordinal number are containing the same elements, using $O(m)$ time we can determine for every ordinal numbers $j_1,j_2$ if the corresponding subsets of $L_{j_1},L_{j_2}$ have a common element (i.e., there exists $1\leq k\leq m$ s.t., the $k^{\text{th}}$ bit  of both $j_1$ and $j_2$ is one) or not. In case the corresponding subsets have empty intersection, and in case that $L_{j_1}$ and $L_{j_2}$ are non empty, and it is NOT the case where $L_{j_1},L_{j_2}$ containing a single subset, pointing respectively to to $B_{n}$ and $B_{-n}$, then we can find $B_{i}$ and $B_{j}$ satisfying the above condition in $O(1)$.

In the worst case, we run over all ordinal numbers $1\leq j_1,j_2\leq m$ in $O((2^m)^2)=O(4^m)$ time, and checking an empty intersection takes $O(m)$ time. Since the first step takes $O(n\cdot m)$ time, the complexity of the algorithm is  $O(4^m \cdot m+ n\cdot m)$.


Converting Decimal Numbers between 0 and 1 to Binary I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater than or equal to 1), to convert a decimal to binary, the results turn strange likely due to floating point imprecision.
For example, the following is a result you might find when applying the algorithm:

The number 0.531904 multiplied by 2 and then subtracted by 1 should result in 0.063708 instead of what is highlighted. Successive instances of this cause the error to eventually propagate to a much greater margin after more iterations.
Thus, I have made 3 observations:

For a decimal between 0 and 1 with "N" places after the point, multiplying it by 2 should never make it more than "N" places. (e.g. multiplying 0.022, where N=3, by any power of 2 should never give it a fourth place etc.)

For a decimal number between 0 and 1 with "N" decimal places beyond the dot. (e.g. 0.022 has N=3 and 0.0101 has N=4) if the binary representation is repeating, then the repeating portion should be no longer than 10^N digits.

For a decimal number between 0 and 1 with the last (rightmost) digit being {1,2,3,4,  ,6,7,8,9} it will always have a repeating representation in binary. It will only not have a repeating representation if the last digit is 5.

My Questions are as follows:

Are these observations true?

If so, is rounding the number to "N" decimal places at every iteration step an appropriate way to fix the problem of precision?

Can someone confirm the result I obtained that 0.002992 has a repeating portion that is 12500 digits long?

You are not doing arithmetic on arbitrary infinitely precise numbers. You are doing arithmetic on the subset of number representable in your computer's native floating point format. Moreover, the values you see printed out are not infinitely precise representations of the actual values encoded in the computer. They are decimal numbers (of a maximum precision) which approximate the internal value. This makes it a little difficult to see what's really going on. At the very least, it is confusing.
Although some programming languages (and even some computers) natively support decimal arithmetic, most of the time the internal representations you will be working with are fixed-precision binary representation. By fixed precision, I mean that the number represented is a fraction $n/2^i$ where $i$ is an integer in a limited range and $n < 2^p$ for some fixed $p$, the precision. Typical CPUs have settled on a precision of 53 bits, so $n < 2^{53}$.
When you supply $.002992$ -- that is, $2992/10^6$ -- the programming language needs to find an internally representable number that is as close as possible to that value in order to minimise calculation errors. At least on my machine, the value selected is $1724770570891843/2^{59}$. That number is extremely close to $2992/10^6$ -- so close that if you round it off at the 18th decimal point you will still see $0.002992$ -- but it's not equal. So your calculation starts with a small inaccuracy.
However, if you just run your algorithm (multiply by 2; subtract 1 if the result is not less than 1), you will not increase the inaccuracy. Multiplying by 2 is exact (unless you exceed the exponent limits), since it only requires changing the exponent to the next integer. And 1 can be represented exactly. In fact, every integer up to $2^{53}$ can be represented exactly, as well as quite a few other integers (but not $2^{53}+1$). So your algorithm will reveal the binary representation of the number actually being used by your computer instead of $0.002992$. That number has no more than 53 binary digits of precision, but it is slightly longer than 53 binary digits because of the 9 leading 0s (in binary). There is no repeating part at all.
Trying to "correct" this computation by introducing additional round-off errors at each step is not going to help.
If you want to find the exact binary representation of $0.002992$, you can use integer arithmetic to work with successive rational numbers. Start with $2992/1000000$ and repeatedly double the numerator and, if necessary, subtract the denominator [Note 1]. (You don't need any extended precision for that. If you start with $0 \le n \lt d$, then $n$ will never exceed $2d$. In the case of $2992/1000000$, that's well within the range of a normal 32-bit integer.)
That will indeed show that the repeating fraction has a period of 12500. It's straightforward to show that the period of the repeating fraction of $n/d$ is less than $d$ in any base. The above algorithm only depends on the value of $n$ and never changes the value of $d$, so the second time you hit a particular value for $n$, your output will start repeating. The period must be less than $d$ because if $n$ is 0, you have an exact fraction, and there are only $d-1$ other possible values of $n$, so it must repeat before $d$ steps.

Notes:

Base 2 makes this particularly easy. If you want to do the computation for a base other than 2, you'll need to do the following
 n = n * b          # Note: n < d
 f = floor(n / d)   # Thus: f < b
 Output f as the next digit
 n = n - d * f      # Or: n = n mod d

The simpler base 2 case is just what happens if you plug $b=2$ into the above calculation.


What is a Trace bit? What is a trace bit in Processor Status register, I can't find any resource that describe about how it work, for now all I could find is that it take two bits 0,1 for Trace on/Trace off mode. Can anyone help me understand it in detail?

Yuval's comment is correct. When the flag is set, the processor executes one instruction and then issues a trap (i.e. an interrupt), which is typically caught by the operating system.
The purpose is to help with debugging.
Programmers who are debugging their software want to set breakpoints at specific locations. This can be implemented using a variety of mechanisms, including the processor's debug registers, modifying code (i.e. overwriting an instruction with another instruction which causes a trap; the single-byte INT3 instruction on x86 is for precisely this purpose), or through the virtual memory system (i.e. marking a page in such a way that executing code in that area causes a page fault).
From the earliest days, another desired feature is single-step debugging, where the processor executes one instruction at a time and then returns control to the debugger. Many early CPUs would actually let you stop and "toggle" the processor clock to support single-stepping, but this required additional specialised hardware to make use of it which would add to the cost of a home machine.
Hence, the trace flag.
As a final note, I'm not surprised at all that you didn't know this. Very little attention is paid these days to the kind of support needed by both the CPU and OS to implement a debugger. Code modification, for example, interferes with the instruction pipeline on modern superscalar CPUs, so some extra circuitry is needed to make techniques like INT3 work.


Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string? I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.

Example:

Set 1:

Some good product
Another product
Some name
Blah

Set 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

Set 1 contains "good" names. Set 2 contains "dirty" names.

I want: for every item from Set 2 (further: item2) find the longest item from Set 1 (further: item1) so that all words from item1 are contained in item2.

For the given example the pairs will be the following:

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

So far I couldn't think of anything better than brute force algorithm:

Split every string from Set 1 into words = we get a set of lists of words, let it be Set 3
Split every string from Set 2 into words = we get a set of lists of words, let it be Set 4
Pick up a list of words from Set 3 (further: list3), compare it to all the lists of words from Set 4 until find some list which is fully contained in the list3.

However it has pretty high complexity and works quite slow. My simple implementation takes about 1.8s to find 1 pair (Set 1 has 3mln items, Set 2 has 4mln items). If I implement same task using MySQL-fulltext indexes (it allows to search for strings which contain all given words) then 1 search takes about 0.4s. So I'm wondering whether there are some good approaches which could be applied here with small blood :)

My programming language is PHP7. The data is stored in MySQL DB.

I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed.

Indices

You can build up an index for each word.  Build a hash table.  For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word.  This hashtable can be built up once in a linear scan of the set of dirty names (Set2).

Then, given a clean name, iterate over the words in the clean name.  For each word, look it up in the hash table, and iterate over all the dirty names that contain that word, and check how many words it has in common with the clean name.  Keep the best match.

This can be optimized a bit.  If the clean name contains a word that occurs in many dirty names, handling that word will be slow.  So, you could find the number of times each word occurs in some dirty name (its frequency) and store this in a hash table.  Then, given a clean name, you could iterate over the words in the clean name in order of increasing frequency, keeping track of the best match you've found so far.  If you've found a match of length $\ell$, then you can stop the iteration early without iterating over $\ell-1$ highest-frequency words in the clean name without missing any valid matches.

Tries

The order of words in a name is irrelevant, so sort the words in each phrase.  For instance, 'some good product' becomes 'good product some'.  Do this to each name in each set.

Next, build a trie to represent the set of good names (Set1).  For instance, in your example the trie will be

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

Now, pick a dirty name.  We want to find a match for it from the trie.  I suggest you use a recursive algorithm to find all matches: to find a match for the name $w_1 \cdots w_n$ in the trie $T$, check whether there is an edge out of the root of $T$ labelled $w_1$, and if so, recursively find all matches for $w_2 \cdots w_n$ in the subtrie pointed to by that edge; also recursively find all matches for $w_2 \cdots w_n$ in $T$.  Once you have found all matches, keep the longest one.

For instance, for 'another very long product name', after sorting this becomes 'another long name product very'.  You look that up in the trie by recursively finding all matches for 'long name product very' in the subtrie +-- product --+, and by finding all matches for 'long name product very' in the main trie.

This search process can be optimized in various ways, e.g., by keeping track of the longest match found so far and stopping early if there's no way the recursive call could find a longer match based on how many words you've matched so far and how many words remain.

There's no requirement to sort by lexicographic order.  You can sort in any other order, as long as it is consistent.  For example, you could sort by the frequency of words in the entire dataset (into the least common words first), which might help reduce the number of recursive calls.


Extension of Tarski's result on the decidability of reals Due to Tarski's result, it is well-known that the first-order theory of reals $(\mathbb{R},+,\cdot,<,=,0,1)$ is decidable. I am working on a paper where I need an extension of this result. More precisely, I would like to consider formulas that involve rational functions, rational coefficients, minima and maxima. Trigonometric functions or exponential functions, instead, are excluded.

While this seems to me to be a straightforward consequence of Tarski's result (essentially, rewrite any formula with the above functions into one with polynomials only; e.g., rewrite $\sqrt[2]{x}$ into $\exists z (z^2 = x)$; for two polynomials $p$ and $q$, rewrite the formula $p / q \leq 1$ into $p \leq q$ and so on).

To my surprise, I could not find any paper that formally establishes this.

Before providing the proof on my own, I wanted to ask around whether someone is aware of a paper that establishes this result.

I doubt there's a proof you can cite, since the result is obvious. The "features" you're adding are first-order definable, and first-order logic is closed under substitution.


Does two system's clock synchronises to communicate with each other? If two computer system's has to do some kind communication like data transfer or receiving should its clock sync to do that?If not then how they transfer bytes without having syced clocks?

Your question is a bit vague, depending on what is communicating, so I will try to give a general answer. There are essentially two big ways of communicating:

Sending data together with a clock signal (source synchronous): this is used in I2C, RAM, SPI
Sending just data and let the other side recover the clock from it (clock recovery): this is used in USB, PCI Express, Ethernet (I think)

The bottom line is that synchronization is important, two systems will never have exactly the same clock because they drift and yet they have to agree on some clock when transferring data. Both approaches have advantages and drawbacks:

source synchronous: can achieve higher speed but needs one more wire and increases complexity of the receiver because it has to deal with two clock domains (its own and the sender's)
clock recovery: one less wire but requires the signal to toggle often enough, a process known as self-clocking which adds overhead to the signal (for example USB sends 10 bits for 8 bits of data, this is known as 8b/10b encoding)


Primal-dual schema in approximation algorithms I was studying Set Cover via the Primal–Dual Schema on my own that I faced a problem in the following paragraph:
Consider an LP-relaxation for an NP-hard problem. In general, the relaxation
will not have an optimal solution that is integral(why?? when we relax an LP we can choose the variables from the interval of [0,1] so the solution must be integral!!!). Does this rule out a complementary slackness condition driven approach? Interestingly enough, the answer is ‘no’. It turns out that the algorithm can be driven by a suitable relaxation of these conditions!(what this paragraph tries to say, I don't get the concept of relaxation here, why we do it??)
I apologize for my long question, I really appreciate if anybody can help me.

You are asking many questions. I will only answer the first.

The answer to the first question is that in linear programming we cannot enforce the variables to be integers. Therefore the optimal solution could be fractional. Consider for example the vertex cover problem for a graph $G = (V,E)$:

$$
\begin{align*}
&\min \sum_{v \in V} x_v \\
s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\
& x_v \in \{0,1\}
\end{align*}
$$

This is an integer program whose LP relaxation is

$$
\begin{align*}
&\min \sum_{v \in V} x_v \\
s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\
& 0 \leq x_v \leq 1
\end{align*}
$$

Now take the case of the triangle. The smallest vertex cover has size 2, but the optimal solution for the LP is $(1/2,1/2,1/2)$. As you can see, it isn't integral.


Why are recursive types needed as primitives for proofs in dependent type systems? I'm relatively new to type theory and dependent programming. I've been studying the calculus of constructions (CoC) and other pure type systems. I'm particularly interested in using it as a proof-preserving intermediate representation for a compiler system.

I understand that (co-)recursive types are representable, computationally, using $\Pi$ as the only type constructor. I've read, though, that they cannot be used to build proofs by induction (forgive me, I can't find where now!), e.g., that I couldn't prove that $0\neq 1$ in plain CoC (even though $\texttt{Nat}$ is typeable as $\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$).

I assume this is why they built the calculus of inductive constructions (CIC). Is this correct? But why? I couldn't find any material explaining why such proofs cannot be represented without using (co-)inductive types as primitives. If this is not true, then why add them as primitives in CIC?

I'm not an expert, but I'll share what I understood so far with an example.

Let's consider the boolean type in CoC, using its standard encoding:
$$
\begin{array}{l}
\mathbb{B} = \Pi_{\tau:*} \tau \to \tau \to \tau
\\
\mathsf{tt} = \lambda \tau:*,x:\tau,y:\tau.\ x
\\
\mathsf{ff} = \lambda \tau:*,x:\tau,y:\tau.\ y
\end{array}
$$
We might expect to be able to prove
$$
\Pi_{b : \mathbb{B}} b={\sf tt} \lor b = {\sf ff} \qquad(*)
$$
Indeed, this quickly follows from the dependent elimination/induction principle we have e.g. in CiC
$$
\mathbb{B}_{ind} : \Pi_{P:\mathbb{B}\to*} P({\sf tt}) \rightarrow P({\sf ff}) \rightarrow \Pi_{b:\mathbb{B}} P(b)
$$

However, we can not really expect (*) to hold in all models of CoC!
Intuitively, a value in $\mathbb{B}$ should roughly be a family of functions
$\{f_\tau\}_{\tau}$ assigning to each type $\tau$ a value in the interpretation of $\tau\to\tau\to\tau$. But this does not force $f_\tau$ to be one between the values of $\sf tt,ff$. We could have e.g. (informally)
$$
f_{\mathbb{N}}(n)(m) = n+m
$$

To be sure that the values of $\sf tt,ff$ are the only possible values, we need to restrict ourselves to parametric models. Indeed (I think) the property $(*)$ can be proven from the free theorem associated to the polytype $\mathbb{B}$.

However, as far as I understand, CoC does not rule out ad-hoc models, where parametricity does not hold. In some of those, $(*)$ is simply false. By soundness, in the presence of a countermodel, we conclude that $(*)$ is not inhabited in CoC. Consequently, there's no $\mathbb{B}_{ind}$ term in CoC, either.


Modulo hash function and multiples of three This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$.

The explanation given is:

  If keys are alphabetic, two keys that differ only by permutation of letters would differ in numeric value by a multiple of 3. This occurs because $2^{2n} \bmod 3 = 1$ and $10^{n} \bmod 3 = 1$)."

I'd be grateful, if someone can clarify why this is so, and how that equation is connected to alphabetical keys and $M$ being a power of $3$.

Observe that $2^{2n} = 4^n \equiv 1^n\equiv 1 \mod 3$ and $10^n \equiv 1^n\equiv 1  \mod 3$.  The relevance of $2^{2n}$ is that exchanging two characters (stored in bytes with even numbers of bits) amounts to multiplying one part of a key by $2^{2n}$ for some $n$, and dividing another part by a like amount.  (Also note, powers of 3  ($3^k$ for some $k$) are multiples of 3 ($3\cdot m$ for some $m$ if $k>0$) but multiples of 3 are much more common than its powers.)


Is an NP-hard problem which is in NP is NP-complete? I'm reading Combinatorial Optimization book by Bernhard Korte and Jens Vygen. There's a part that they said:

It is an open question whether each $NP$-hard decision problem $A \in NP$ is $NP$-Complete, because of the difference between polynomial reduction and polynomial transformation.

I understand that, but when I read wikipedia article about NP-complete, I see this picture
According to wikipedia, a decision problem is $NP$-complete when it is both in $NP$ and $NP$-hard, which make me confused. Can someone help me understand the difference between the book and wikipedia?

Definition 15.15. Let P1 and P2 = (X, Y) be decision problems. Let f : X → {0, 1} with f (x) = 1 for x ∈ Y and f (x) = 0 for x ∈ X \ Y . We say that P1 polynomially reduces to P2 if there exists a polynomial-time oracle algorithm for P1 using f
Definition 15.17. Let P1 = (X1, Y1) and P2 = (X2, Y2) be decision problems. We say that P1 polynomially transforms to P2 if there is a function f : X1 → X2 computable in polynomial time such that f (x1) ∈ Y2 for all x1 ∈ Y1 and f (x1) ∈ X2 \ Y2 for all x1 ∈ X1 \ Y1.

Check the definitions of NP-completeness and NP-hardness. I suspect they use Karp reductions for one and Cook reductions for the other.

Then, the quote makes sense: it is indeed unknown if Cook reductions and Karp reductions are equivalent in this sense. This is related to the question whether co-NP = NP; Cook reductions can not separate the two but Karp reductions might. See here for some details.

However, the authors use different definitions than (most of) the rest of the CS world: the widely accepted standard is to use Karp reductions. I recommend you read our reference question (and get a better book).

To be fair, the authors want to talk about optimization problems, in which case they need a notion of (NP-)hardness that is not tied to decision problems. Karp reductions won't get them there directly.

They picked a poor way out, arguably, by defining the notions differently from everybody else. There are cleaner (but more involved) ways, defining complexity classes for optimization problems rigorously, providing them with their own types of reduction, and tying them to the classic decision-problem classes using threshold languages.


Control flow graphs - Tree decomposition Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example :

While A
if B
do ..
else do ..
end while

For above example, while doing decomposition, I can say its

  D2 (D1)

i.e while  and then inside while, its if-then-else.

Considering same situation. How can you represent

  CONTINUE and BREAK statements

Ever for  FOR statement there is no defined terminology like for while and if then else. FOR statement falls under while.

My prof says in theory, there is nothing about Break and continue statement and I couldnt find anything online too.

For example :

# include <stdio.h>
int main(){
   float num,average,sum;
   int i,n;
   printf("Maximum no. of inputs\n");
   scanf("%d",&n);
   for(i=1;i<=n;++i){
       printf("Enter n%d: ",i);
       scanf("%f",&num);
       if(num<0.0)
       break;                     //for loop breaks if num<0.0
       sum=sum+num;
}
  average=sum/(i-1);
  printf("Average=%.2f",average);
  return 0;
}

Control flow graph for this is as below: the nodes has line number written : (Sorry the image is side ways)

I decomposed this as :

P1;P1;D2(P1;P1;D1);P1

* P1 represents set of statements outside loops

I'm not sure if this is correct. My professors says to use something as D22 for break, like create a new term from above image.

  My main question here is the decomposition. I Know that i drew the
  CFG correctly, but is the decomposition correct according to the first
  image?. The break state kind of creates a while as you can see in CFG,
  but i'm not sure if it has to be considered as while and I guess we
  cannot, as per my professor.

I am working on this and wanted to know, if anyone has come across something for Break and continue statements while decomposition of graphs, please let me know.

Thanks.

PS : Please, Let me know, if am unclear and if anymore info is needed. I can probably write down an example and upload the picture.

There are many different kinds of control-flow constructs that only map to "structured programming" (tree decomposition) constructs when you add extra data variables and extra tests.  continue is usually okay (as long as its not nested any deeper), but break is one of the hard ones.  Another relatively painful case is short-circuit conditional evaluation.

A preprocessing step of converting while x stmt to if x repeat stmt until not(x) will make everything a little easier (and you want to do this anyway, because it lets you safely optimize loop invariants).  Example:

while i<=n:
  something
  if condition break
  something_else
  i = i+1

becomes

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
  until not(i<=n)

A second preprocessing step of saving the (possibly complicated) calculation of the loop condition as a boolean temporary variable will also help.  So:

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
    t0 = not(i<=n)
  until t0

Now we can convert our break into a if-else:

if i<=n:
  repeat:
    something
    if condition:
      t0 = false
    else:
      something_else
      i = i+1
      t0 = not(i<=n)
  until t0

So we've converted, but the result is kind of ugly: we now have to keep track of t0 and we have two tests where we only had one before.  "Structured programming" is not the panacea it is often made out to be.


Two way finite state Automaton NP Compleness definition clarification? INSTANCE: A two-way nondeterministic finite state automaton A over single Alphabet I.
QUESTION: Is there an string x (over I) such that A accepts x ?

Since a 2-way NFA with N states, there’s an equivalent nfa with n^(n+1) states. So that’s we get the exponential time from.

I am clear about that, but if I understand correctly the size of the string accepted by the 2Way NFA would still be (in the worst case) polynomial to number of states in the 2Way NFA. Cause if the smallest string accepted was exponential in size, the verification will also take exponential time and thus the problem by definition would not be NP Complete ? Or is there a mistake in this reasoning?

For a problem to be in NP, there needs to be a polynomial time verifier for it. This polynomial time verifier need not be the "obvious" one. Ruling out one specific verifier doesn't prove that the problem is not in NP.

For a problem to be NP-complete, it needs to satisfy two properties: (i) it needs to be in NP, and (ii) it need to be NP-hard. You can look these concepts up in many sources. In particular, the fact that there is some natural exponential time algorithm for a problem doesn't imply that it is NP-complete, though it is true that every problem in NP has an exponential time algorithm.

Unfortunately I am not versed well enough in two-way automata to answer your specific question, but my comments above imply that the answer doesn't necessarily have a direct bearing on whether the emptiness problem for 2NFAs is NP-complete or not (or even in NP or not).


Decision tree complexity of finding parameters of "zigzag" array I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:

An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.
Input: a zigzag array.
Output: the position of $i$ and $j$.

My answer:

Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.

The obvious lower bound is $\Omega(\log n)$, since there are $\binom{n+1}{2}$ possible answers. It is likely that using smart binary search you can find $i,j$ in $O(\log n)$ queries. I suggest starting with the easier case in which $j = n$, that is, the array increases and then decreases, and you want to find its maximum in $O(\log n)$ queries. Such arrays are known as bitonic, and indeed you can find $i$ in $O(\log n)$ comparisons (see for example this solution).


Can the regular image of a context-free language be undecidable? I just need to know the truth or falsity of a simple statement.

Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special metacharacter “|”. Suppose that every string in $L_1$ contains exactly one metacharacter. Let the left half and right half of a string in $L_1$ denote the part of the string before the “|” and the part after, respectively.  Let $L_2$ be the language over $\Sigma$ containing all the right halves of the strings in $L_1$.

Then is membership in $L_2$ decidable? What about if $L_1$ is restricted to be nice in some way? I'm fairly sure there are counterexamples in any case, but I can't find them.

If $L_1$ is context-free, then so is $L_2$. You can show this easily using closure properties of context-free languages. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$; we assume that $\Sigma$ and $\Sigma'$ are disjoint. Define a homomorphism $h\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^* \cup \{|\}$ by $h(\sigma) = h(\sigma') = \sigma$ and $h(|) = |$, and a homomorphism $k\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^*$ by $k(\sigma) = \sigma$ and $k(\sigma') = k(|) = \epsilon$. Then
$$
L_2 = k(h^{-1}(L_1) \cap \Sigma^{\prime\ast} | \Sigma^*).
$$
The family of context-free languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages, hence $L_2$ is context-free as well.


Help in understanding exactly how lattices used as one way functions for hashing (This question is related to homework)
I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers and videos in an attempt to build my understanding of the subject, but due to the intensely technical manner in which information on the subject is presented, I have not been able to answer many questions in my mind. Due to the structure of my long distance course I have no access to professors or extensive libraries so my question is one which merely seeks to increase my understanding, please bear with me.

Thus far I have understood that:
- Lattices are a collection of regularly ordered points in euclidean space (its terms like this which have caused me to be searching for answers for days)

A lattice may be defined through n vectors called a basis where n = the dimension (for now I am working in dimension 2), and any other basis can be found by applying positive or negative multiples of each vector in the basis to another vector in the basis
Defining a lattice L1 as a set of points allows one to multiply the whole set by some co-efficient which will essentially transform it into a new lattice L2
The determinant of the vectors of the basis essentially tells us the volume (area in 2 dimensions) of the parallelpiped which will be repeated to form the lattice, the lattice points being the vertices.

Having said this, I am now stuck in understanding how I move all of this to cryptography. I am on a question which asks me to compute the output for 3 inputs to a function:

'We will see that q-ary lattices give provably collision-resistent hashing. We choose integers q; a
and b. Our hash function (presented by Mikl´os Ajtai in a breakthrough paper in 1996) is a 2-variable
function: h(x, y) = ax + by mod q.
(a) For q = 5; a = 14; b = 13; compute h(17, 8), h(21, 16) and h((17, 8) - (21, 16))'

Having found the answers, h(17, 8) = 14*17 + 13*8 = 342 mod 5 = 2; h(21, 16) = 14*21 + 13*16 = 502 mod 5 = 2; h((17, 8)-(21, 16)) -> (h(-4, -8) = 14*-4 + 13*-8 = 160 mod 5 = 0

I believe this means that with the first two points the lattice has been moved by some multiple of 5 plus two, which has displaced it by two and thus formed a new lattice. While in the last case, the lattice has been moved by a multiple of its determinant and thus is the same lattice.

However, I just cannot understand the link to hashing. In an application would the points be the cleartext and the 'answer modulo 5' the output of the hash function? If so would'nt there be too many collisions as we have already seen two examples of which give the answer 2? How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing? Are q-ary lattices only an attempt to store the basic pattern needed to reproduce the lattice? and if so wouldn't the lattice itself be the cleartext and the basic pattern (given by the basis and the determinant) the answer from the hash function??? How exactly would you encrypt a message using a lattice???

I just wish I could find some text which explained this in English rather than symbols.. like this http://www.wisdom.weizmann.ac.il/~odedg/COL/cfh.pdf . I really hope I have not repeated any questions through my lack of understanding. Thanks in advance.

You have several confusions regarding cryptography. First, the nature of hash functions. The non-cryptographic use of hash functions is to hash long messages into shorter ones in a "uniform" fashion. So we expect there to be many collisions, by design. Cryptographic hash functions have the additional properties that collisions are hard to find (there are several, inequivalent ways of stating this). Therefore, while it is possible to find collisions even for cryptographic hash functions (simply because the range is smaller than the domain), this should be difficult. Such hash functions can be used in various ways in cryptography, for example in digital signatures: you sign on the (small) hash rather than the (large) message.

Second, encryption is a different primitive from hash functions. Encryption itself comes in two main kinds, symmetric and public key, which are rather different, and there are many other cryptographic constructions out there. There are reductions between some of the cryptographic "primitives" (hash functions, one-way functions and the like), for example you can use them to construct HMACs (message authentication codes) and PRNGs (pseudorandom number generators), but perhaps not encryption schemes.

Regarding the matter at hand: the idea of Ajtai's hash function is to use a random lattice $A$, the hash function being $x \mapsto Ax \pmod{q}$, for some prime $q$. Here $x$ is a binary vector in $\{0,1\}^m$, embedded into $\mathbb{Z}_q^m$. The parameters here are important — the size of $A$ and $q$ — but I'll ignore them here. In order to show that this is cryptographically secure, under one definition we need to show that it is difficult to find a collision, that is two messages $x,y$ with the same hash. Such messages would satisfy $A(x-y) \equiv 0 \pmod{q}$, and so $x-y$ would be in the dual lattice $A^{\perp}$. Now $x-y \in \{-1,0,1\}^m$, so (for the correct choice of parameters) it is "short", and finding it is conjectured to be difficult. This shows the (conditional) security of the scheme.

Lattice-based encryption can also be used for public-key encryption (Regev's scheme) and for homomorphic encryption. These schemes rely on a different problem, LWE (learning with errors), which is similar to CVP (closest vector problem). The details are more complicated &mdash you can have a look at Regev's scheme in Section 5.4 of his survey with Micciancio, though it could be hard to glean from there why exactly the scheme works. Perhaps this is explained later in your course, and if you need more explanations, you can ask another question here.


Proof that the Blank Tape Halting Problem is undecideable I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not)

Proof: Suppose that the Blank Tape Halting problem is decideable, then there exists a universal turing machine $M$ that decides it. So given any turing machine $T$, $M$ decides if $T$ halts after being started on a blank tape.

Now let any turing machine $T$ and input $w$ be given. Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Then if $M$ takes $R$ as input, $M$ decides if $R$ halts on a blank tape and thus decides if $T$ halts on $w$. Since $T$ and $w$ were chosen arbitratily $M$ decides the Halting problem, a contradiction, so the Blank Tape Halting Problem is undecideable. $\square$.

Is there anything wrong with my reasoning above? I assume that there must be some key detail that I'm overlooking, or that my proof isn't completely rigorous

I guess the problematic argument may be the following

  Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Since I haven't explicitly constructed such a turing machine $R$ in my proof above.

You need to explain how to construct $R$. In your case this can be done formally, by constructing a machine which works as follows:

Write $w$ on the input tape.
Move the head back to its initial position.
Transfer control to $T$.

It is not too hard to construct $R$ explicitly from $T$.

In order for your argument to go through, you need to show that this reduction is computable. Usually we describe such reductions informally and just claim (without proof) that it is computable, since actually proving such things formally is extremely technical and longwinded.


Issue with Campaign problem to find distinct valid campaigns Question:

An email campaign has a sequence of email messages
where each email message belongs to one of two categories:
transactional (and/or) marketing.
Given the campaign size n and the gap length k, find the total number
of distinct valid campaigns.

My Approach:
My initial thoughts were around generating all the valid permutations for each scenario and then counting it. However, I am not sure if that's the way to go!
I would appreciate any insights.

Let $DP[i]$ be the number of distinct valid campaigns whose last marketing email is the $i$-th email, $i$ from $1$ to $n$. As an extension, let $DP[0]=1$, which is the number of distinct valid campaigns without marketing emails.

For all $i\le k+1$, it is clear that the only valid campaign whose last marketing email is the $i$-th email is the campaign that has no marketing email other than the $i$-th email. That is,
$$DP[i]= 1\quad\color{#d0d0d0}{\text{ for all }i\le k+1.}$$
For all $i\gt k+1$,

Consider a valid campaign $\mathcal C$,  whose last marketing email is the $i$-th email. If the last marketing email of $\mathcal C$ is changed to a transactional email, $\mathcal C$ will become another valid campaign, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails.
Conversely, consider a valid campaign $\mathcal D$, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails. If we change the $i$ email of $\mathcal D$ to a marketing email, $\mathcal D$ will still be a valid campaign, whose last marketing email is the $i$-th email.

So, we have
$$DP[i]= DP[0] + DP[1] + \cdots + DP[i-k-1]\quad\color{#d0d0d0}{\text{ for all }i>k+1.}$$
The number of all distinct valid campaigns is
$$DP[0] + DP[1] + \cdots + DP[n].$$
If we implement the above approach to compute the array $DP$ iteratively, we can get an algorithm that runs in $O((n-k)^2)$ time and $O(n)$ space.

The algorithm above runs in time that is quadratic of $n$ when $k$ is not near $n$. It might not be fast enough when $n$ is large.
Let us do better. Since
$$DP[i+1]= DP[0] + DP[1] + \cdots + DP[i-k-1] + DP[i-k],$$
we have the following simpler recurrence relation,
$$DP[i+1]= DP[i] + DP[i-k]$$
for all $i\ge k+1$. Now we can write an algorithm that runs in $O(n)$ time and $O(k)$ space.

Here is a sample implementation in Python. For simplicity, $O(n)$ space is used.
def ways(n, k):
    dp = [1] * (n + 1)

    for i in range(k + 1, n):
        dp[i + 1] = dp[i] + dp[i - k]

    print(dp)  # for educational purpose.
    return sum(dp)

def test():
    print(5, 0, ways(5, 0))
    print(5, 1, ways(5, 1))
    print(5, 2, ways(5, 2))
    print(5, 3, ways(5, 3))
    print(5, 4, ways(5, 4))
    print(5, 5, ways(5, 5))

test()


What are the main ideas used in a Fenwick tree? While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this technique. So in an effort to understand Fenwick trees, I researched all online sources in vain because reading them in details is a pain!

No one seems to be able to explain the main concepts behind this data structure in a concise and clear way. Can anyone please give a high level exposition of the main ideas related to Fenwick trees without going into unnecessary details?

A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array.

Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on top of the array. Furthermore, label all the left edges in this tree with a "0" and all the right edges with a "1". We get something like this:

This is the so called Fenwick tree (or binary indexed tree). As can be seen, all the leaf nodes are indexed by a 4-digit binary number from 0000 till 1111 (left to right). Don't worry about this indexing for the time being. Now suppose that every leaf node contains the numeric value of its mapped array element and that every non-leaf node contains the sum of its two children. This means that the root node of the tree will contain the sum of the whole array. Also the left(right) child of the root will contain the sum of the left(right) half of the array and so on and so forth.

Up till this point we haven't really done anything special apart from storing partial sums. What we really want to do is to use these partial sums to compute cumulative sums in the array. We can do this for example by carefully selecting some nodes and returning their sum. This poses the question: Is there a strategic way to mark some nodes of the index tree that allows efficient cumulative sum calculations? It turns out that there is and this is the main idea behind Fenwick trees.

Before describing this marking, we first elaborate on the concept of uniform arcs. A uniform arc in a binary indexed tree is a directed path from any leaf to any other leaf situated to its left such that the labels on this path have the form: "00...011...1" (read from left to right). We can also assume the existence of a uniform arc from every leaf node to itself (with a length of 0). For example, the uniform arc connecting the fourth leaf to the first has a label of "0011". See the following figure for some illustrative examples of uniform arcs.

Now comes the crucial idea of Fenwick trees. The marking that allows us efficient computation of cumulative sums is obtained by coloring the middle node of the largest uniform arc emanating from every leaf node. This marking is illustrated in the following figure:

The nodes coloured in red are the so called responsibility nodes. This is due to the fact that each red node is responsible for maintaining the sum of values of all leaf nodes beneath it. Note that there are 16 responsible nodes and the whole tree can be implemented using a single array of the same size of the original array and here is when the binary indexing becomes handy. The yellow nodes are not needed and are used here only for pedagogical purposes. Note that all non-leaf responsible nodes have indexes length < 4 bits. We can restore the 4 bit length by padding successive "1"s to the right of the corresponding index. After applying the padding, the indexes of all responsible nodes fit nicely into a single array. See the following figure:

All we have to do now is figure out a way to compute (or update) the cumulative sum for every leaf node as follows:

A- To read the cumulative sum at a leaf, we first prepend a "0" and append a "1" to its index then we use the "flipping" technique as follows. Starting from the right most bit we first note the first "1" to "0" transition then flip all "1"s to "0"s one at a time. The sum of the found responsible nodes is then returned. The following examples illustrate this technique: (note: node "" is the root)

leaf "1010", becomes "010101" =>  responsible nodes: {"1010", "100", "0"}

leaf "1011", becomes "010111" =>  responsible nodes: {"10", "0"}

leaf "0111", becomes "001111" =>  responsible nodes: {"0"}

leaf "1111", becomes "011111" =>  responsible nodes: {""}

B- To update a value, trace all responsible nodes from the leaf to the root and update them accordingly. The tracing is done by prepending and appending a "0" to the index of the leaf and then successively noting all "0" to "0" and "1" to "0" transitions in the resulting index starting from rightmost bit. The following examples illustrate this technique: (note: node "" is the root)

leaf "1000", becomes "010000" =>  responsible nodes: {"1000", "100", "10", ""}

leaf "1111", becomes "011110" =>  responsible nodes: {""}

leaf "0100", becomes "001000" =>  responsible nodes: {"0100", "010", "0", ""}

leaf "0000", becomes "000000" =>  responsible nodes: {"0000", "000", "00", "0", ""}

You can verify the above examples by direct visual inspection of the third figure. A detailed explanation of Fenwick trees can be found at BIT: What is the intuition behind a binary indexed tree and how was it thought about? and https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/. Hopefully by now reading the mentioned sources will be much easier.


How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range.

For example, if we consider PRNG algorithm being a simple counter counting from 0 tom MAX, the distribution is uniform and there's a guarantee of not repeating numbers in a sequence. So, not repeating numbers does not break uniformness. But probably it breaks randomness, does it? To what extent? If so, does it mean, that the better the algorithm, the less guarantee we have to not generate similar numbers in sequence?

I'm particularly interested in the answers regarding Mersenne Twister as a most popular PRNG in programming languages implementations. It'd also be great to know how things are in operating systems' crypto-secure PRNGs – Yarrow (macOS), Fortuna (FreeBSD) or ChaCha20 (Linux).

Given the same internal state, a pseudorandom number generator (PRNG) must produce the same output.  PRNGs have a period: if you run one long enough, it will start repeating the same sequence.  (For good PRNGs, the period is long enough that you don't have to worry about it.)  For very simple PRNGs such as a simple linear congruent generator of the form

new number = old number $\times$ constant $+$ another constant

the state is just the previous value.  In that case, it's impossible to generate the same number twice in a row unless the constants are poorly chosen and the PRNG gets stuck in a short loop.  (This has been known to happen, and you don't want to use such a PRNG!)  However, you will sometimes generate numbers that are similar (not the same) in various respects.  The tests that vonbrand's answer mentioned are designed to verify that such similarities occur with relative frequencies that are close to what should be found if each number had equal probability.

The most common version of a Mersenne Twister (MT) has a 624$\times$32-bit internal state.  If the MT is being used to generate 32-bit numbers, it uses up 32 bits of its state each time it outputs a number, and when all 624 internal state words have been used, the MT generates a new 624-word state from its old state.  (The number that is output is not the same as the state word that's used; it's a function of the state word, though.)  I suppose an MT could theoretically sometimes output the same number in two successive calls on the MT, although I am not certain that that is possible.  I think that would require that two successive words in the generated 624-word state were identical (unless it happened because you seeded the MT with a bad state that included the same number multiple times).  I don't know whether this is possible; I suspect that it is.  But it should be very, very, very rare in the sense that the relative frequency of successive duplicates across the entire period of MT should be small.

For 32-bit numbers, ideally, the relative frequency of choosing the same number twice in a row should be $1/2^{32} \times 1/2^{32} = 2^{-64}$.  That would be very rare.  On the other hand, the period of the widely-used version of MT, versions of MT19937, is $2^{19937}-1$. This is the number of successive pairs that could, theoretically, contain duplicates, and $2^{-64} \times 2^{19937}-1 = 2^{19873}$ is a large number.  However, any use of MT will only make use of a small fraction of the period.  At this point, if I wanted to know how common or rare duplicates are, I would look at the test in TestU01 or another test suite that checks the frequency of duplicates.  I wouldn't test the entire period, though, unless I had a lot of computing power and was patient.  I don't know whether it's possible to assess the frequency of duplicates analytically from the design of MT19937.

I listed some other relevant resources in this answer and said more about Mersenne Twisters in this answer.


Minimum cost subset of sensors covering targets I have a dynamic programming problem:

  If I have a set of sensors covering targets (a target might be
  covered by mutiple sensors) how can I find the minimum cost subset of
  sensors covering all targets given each sensor has a cost?

I have thought a lot about this, but I can't reach the recursive formula to write my program. The greedy algorithm does not always provide the correct minimum cost subset. My problem is that sensors overlap in covering targets. Any help?

Example: I have set of sensors $\{s_1,s_2,s_3\}$ with costs $\{1,\frac{5}{2},2\}$ and 3 targets $\{t_1,t_2,t_3\}$. Sensors cover $\{t_1 t_2,t_1 t_2 t_3,t_2 t_3\}$ and I need to get minimum cost subset by dynamic programming. For the above example if I use greedy algorithm I would get $s_1,s_3$ but the right answer is $s_2$ only.

Your problem is equivalent to the weighted version of Set Cover, which is NP-complete (and delving into other complexity classifications, W[2]-complete and inapproximable within $O(\log n)$).

If you want a polynomial-time algorithm, you're going to have to impose restrictions on either your problem or the input.


Determining the optimal threshold value for a one-dimensional decision stump classifier I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows:

Say we are given $N$ ordered data points on the real line: $x_1,\ldots,x_N \in \mathbb{R}$ such that $x_1 < x_2 < \ldots < x_N$.

Each of the points $x_i$ has a label $y_i \in \{0,1\}$. We are asked to predict this label using a decision stump classifier, $h(x;t) = \mathbb{1}[x>t]$. The decision stump classifier predicts $\hat{y}_i = 1$ if $x_i > t$. Thus, the accuracy of this classifier depends on the threshold parameter $t$.

I am looking for an efficient algorithm to determine the value of $t$ that maximizes the number of correctly classified points. That is, solve the problem:

$$\max_{t\in\mathbb{R}} A(t)=\sum_{i=1}^N \mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t] + \mathbb{1}[y_i=1]\mathbb{1}[x_i>t]$$
Some insights:

Since there are $N$ data points, we only need to consider $N+1$ values of $t$. These are values that lie in the $N+1$ intervals $(-\infty,x_1), [x_1,x_2),\ldots, [x_{N-1},x_N), [x_N,\infty]$.
When $t < \min_{i}x_i$, the decision stump predicts $\hat{y}_i=1$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]}=N^+$.
When $t \geq \max_{i}x_i$, the decision stump predicts $\hat{y}_i=0$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]}=N^-$.
The number of correctly classified points $A(t)$ can be decomposed as $B(t)+C(t)$, where
$$B(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t]}$$
is the number of correctly classified points with negative labels and
$$C(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]\mathbb{1}[x_i>t]}$$
and the number of correctly classified points with positive labels. Note that $B(t)$ is monotonically increasing in $t$ while $C(t)$ is monotonically decreasing in $t$.

There is a straightforward algorithm that runs in $O(N)$ time, by scanning from left-to-right and right-to-left.  Basically, it takes advantage of a simple recurrence relation for $B(\cdot)$ and $C(\cdot)$.

Let $t_0,t_1,\dots,t_N$ denote a sequence of $N+1$ candidates for the threshold (i.e., $t_i \in [x_i,x_{i+1})$, etc.), as you articulated in the question.  Our job is to find the value of $i$ that maximizes $B(t_i)+C(t_i)$.

I claim we can compute the $N+1$ values $B(t_0),B(t_1),\dots,B(t_N)$ in $O(N)$ time, using a left-to-right scan.  This is because, given $B(t_{i-1})$, it is easy to compute $B(t_i)$.  In particular, notice that $B(t_i)$ can be written as the summation

$$B(t_i) = \sum_{j=1}^i 1[y_j=0].$$

In other words $B(t_i)$ is the count of how many of the first $y$'s are equal to zero.  Thus we get the recurrence relation

$$B(t_i) = B(t_{i-1}) + 1[y_i=0]$$

with the base case $B(t_0)=0$.  This allows us to compute all of the $B(t_i)$'s in $O(N)$ time.

We can similarly compute the $N+1$ values $C(t_0),C(t_1),\dots,C(t_N)$ in $O(N)$ time, by scanning from right-to-left.  Here we take advantage of a recurrence relation that computes $C(t_i)$ given $C(t_{i+1})$.  The details are similar to that for $B(\cdot)$.

The result is that we can compute the sequence of $N+1$ values $B(t_0)+C(t_0),B(t_1)+C(t_1),\dots,B(t_N)+C(t_N)$ in $O(N)$ time.  Then it is easy to find the largest value in that list.  The running time in total is $O(N)$ time.

I don't think you can do any better than $\Theta(N)$ worst-case running time, since you may need to examine every item (in the worst case).  Therefore,the method I have outlined above appears to be asymptotically optimal (up to constant factors).


Alternate reduction from 3SAT to 4SAT? It seems that the standard reduction method you see online from 3SAT to 4SAT is that we let $\phi = (a \lor b \lor c)$ be a 3SAT clause, and so there is an assignment that satisfies $\phi$ iff $\phi' = (a \lor b \lor c \lor z) \land (a \lor b \lor c \lor \neg z)$ is also satisfiable.

Is it just as valid to say that $(a \lor b \lor c)$ is satisfiable iff $(a \lor b \lor c \lor c)$ is satisfiable? This seems like a much simple solution..

It depends on the exact definition of $k$-SAT that's being used.  If $k$-SAT is defined to have clauses of length at most $k$, your reduction is perfect; if it's defined to have clauses with exactly four distinct literals, then you're out of luck.


Find an element in sorted 2D-array (matrix) Given an $N\times N$ array, where elements are decreasing in every row and every column.

What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it does not exist in the array?

(Copied from a post on StackOverflow)

Here's a simple approach:

Start at the bottom-left corner.
If the target is less than that value, it must be above us, so move up one.
Otherwise we know that the target can't be in that column, so move right one.
Goto 2.

For an NxM array, this runs in O(N+M).  I think it would be difficult to do better.  :)

Edit: Lots of good discussion.  I was talking about the general case above; clearly, if N or M  are small, you could use a binary search approach to do this in something approaching logarithmic time.

Here are some details, for those who are curious:

History

This simple algorithm is called a Saddleback Search. It's been around for a while, and it is optimal when N == M.  Some references:

David Gries, The Science of Programming. Springer-Verlag, 1989.
Edsgar Dijkstra, The Saddleback Search. Note EWD-934, 1985.

However, when N < M, intuition suggests that binary search should be able to do better than O(N+M): For example, when N == 1, a pure binary search will run in logarithmic rather than linear time.

Worst-case bound

Richard Bird examined this intuition that binary search could improve the Saddleback algorithm in a 2006 paper:

Richard S. Bird, Improving Saddleback Search: A Lesson in Algorithm Design, in Mathematics of Program Construction, pp. 82--89, volume 4014, 2006.

Using a rather unusual conversational technique, Bird shows us that for N <= M, this problem has a lower bound of Ω(N * log(M/N)).  This bound make sense, as it gives us linear performance when N == M and logarithmic performance when N == 1.

Algorithms for rectangular arrays

One approach that uses a row-by-row binary search looks like this:

Start with a rectangular array where N < M.  Let's say N is rows and M is columns.
Do a binary search on the middle row for value.  If we find it, we're done.
Otherwise we've found an adjacent pair of numbers s and g, where s < value < g.
The rectangle of numbers above and to the left of s is less than value, so we can eliminate it.
The rectangle below and to the right of g is greater than value, so we can eliminate it.
Go to step (2) for each of the two remaining rectangles.

In terms of worst-case complexity, this algorithm does log(M) work to eliminate half the possible solutions, and then recursively calls itself twice on two smaller problems.  We do have to repeat a smaller version of that log(M) work for every row, but if the number of rows is small compared to the number of columns, then being able to eliminate all of those columns in logarithmic time starts to become worthwhile.

This gives the algorithm a complexity of T(N,M) = log(M) + 2 * T(M/2, N/2), which Bird shows to be O(N * log(M/N)).

Another approach posted by Craig Gidney describes an algorithm similar the approach above: it examines a row at a time using a step size of M/N.  His analysis shows that this results in O(N * log(M/N)) performance as well.

Performance Comparison

Big-O analysis is all well and good, but how well do these approaches work in practice?  The chart below examines four algorithms for increasingly "square" arrays:

(The "naive" algorithm simply searches every element of the array.  The "recursive" algorithm is described above.  The "hybrid" algorithm is an implementation of Gidney's algorithm. For each array size, performance was measured by timing each algorithm over fixed set of 1,000,000 randomly-generated arrays.)

Some notable points:

As expected, the "binary search" algorithms offer the best performance on rectangular arrays and the Saddleback algorithm works the best on square arrays.
The Saddleback algorithm performs worse than the "naive" algorithm for 1-d arrays, presumably because it does multiple comparisons on each item.
The performance hit that the "binary search" algorithms take on square arrays is presumably due to the overhead of running repeated binary searches.

Summary

Clever use of binary search can provide O(N * log(M/N) performance for both rectangular and square arrays.  The O(N + M) "saddleback" algorithm is much simpler, but suffers from performance degradation as arrays become increasingly rectangular.


How powerful is a k-stack pushdown automaton with a unary stack alphabet? I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's.  Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet.

I've figured out that a $k$-UPDA is at least as powerful as a $(k-1)$-PDA (see proof at the end). This implies that a $k$-UPDA is equivalent in power to a Turing machine when $k \ge 3$ (as it is at least as powerful as a Turing machine when $k \ge 3$, as you can simulate a TM with a 2-PDA, and by the Church-Turing thesis, no more powerful).

A 1-UPDA is more powerful than a NFA/DFA, as a 1-UPDA can recognize, for instance, the language $\{0^n1^n:n \in \mathbb{N}\}$. But, at the same time I suspect (although I do not know) that a 1-UPDA is less powerful than a 1-PDA.

My questions are as follows:

What is the complexity class recognized by a 1-UPDA? Or at the very least, are there better bounds than "more powerful than a NFA/DFA and no more powerful than a 1-PDA"?
What is the complexity class recognized by a 2-UPDA? Or at the very least, are there better bounds than "at least as powerful than a 1-PDA and no more powerful than a 2-PDA"? In particular, is a 2-UPDA more powerful than a 1-PDA?
Is there a $k$ such that you can simulate a TM with a $k$-UPDA without exponential overhead?
Is there a standard name for a UPDA?

Proof that a $k$-UPDA can simulate a $(k-1)$-PDA: use one stack for scratch space. You emulate a stack alphabet of $m$ symbols with a unary number, base $m$. To push a number $x$ to a stack, you multiply the number of elements in the stack by $m$ and then push $x$ more symbols. (You also need to check for if the stack is empty, but that is simple enough.) To pop a number, you modulo the stack by $m$ for the number to pop, and divide the number of symbols in the stack by $m$.

Such automata are called counter-automata. Each counter holds a natural number, which can be tested for zero. (So your UPDA has a single stack symbol plus a way to recognize the empty stack.)

Two push-downs are Turing complete, i.e., they can compute any Turing computable function. Basically, because two stacks can simulate a queue. So you have proved yourself that 3-UPDA is Turing complete. But actually two counters are enough. The trick is to code two numbers $(i,j)$ into a single number $2^i 3^j$ and doing your own construction again.

The family of languages is called one-counter languages, which have some fame in formal language theory. I browsed my own old answers and found: Which languages are recognized by one-counter machines?

Also: The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).


Question about idempotent and Dominance Laws in Boolean Algebra If I have the following statements:

For Idempotent:

Since X * X = X, would that imply that ~X * ~X = ~X

For Dominance:

Since X + 1 = 1 would that imply that ~X + 1 = 1

The principle of substitution states that if $\varphi$ is a valid (fully parenthesized) formula in variables $x_1,\ldots,x_n$ and $e_1,\ldots,e_n$ are arbitrary expressions, then if we substitute $e_i$ for $x_i$ in $\varphi$ (you have to substitute all occurrences of $x_i$ by $e_i$) we still get a valid formula. You can apply this principle to your examples.

Perhaps the principle will become easier to understand if we take an example from algebra. Consider the identity $(x+y)(x-y) = x^2-y^2$. If we substitute $2a$ for $x$ and $1+a$ for $y$ then we get $((2a)+(1+a))((2a)-(1+a)) = (2a)^2-(1+a)^2$, which is still valid. The same happens in your case.


Minimum weight k-induced subgraph Let $G$ be multipartite directed weighted graph with $k$ independent sets (we will call
them "layers"). We select exactly one node from each layer and form the induced subgraph $H_k$. That is, $H_k$ has exactly $k$ nodes (one from each layer) and contains all edges from $G$ that have both endpoints in $H_k$.

Our goal is to find $H_k$ such that the total weight of all of its edges is minimized:
$$\min_{H_k \subset G}\sum_{e \in H_k} weight(e)$$

(you can assume that the graph is connected, so a solution always exists)

Case #1: Graph is flat

To better illustrate the problem I will give some examples. Consider a
special case where all edges in $G$ are from layer $i$ to layer $i+1$:

This problem can be easily solved, by adding 2 new nodes entry and exit
to $G$. Then we add edges with $0$ weight from entry to every node in layer #1 and from every node in layer #$k$ to exit. Finally the solution to our problem is the shortest path from entry to exit.

In our example, the minimum weight 4-induced subgraph will be:
$A_3, B_1, C_1, D_1$, with total weight $20$.

Case #2: Graph has backward edges

In this case, we allow a layer to have backward edges; that is, a layer $i$ can have edges to any layer $j$ as long as $i \ne j$. For instance, consider
the graph from the previous example, but this time add some backward edges
(with blue color):

Unfortunately, the previous approach does not work anymore, as the previous
approach will give us the same solution $A_3, B_1, C_1, D_1$ with a total
weight of $70$, but the minimum subgraph is $A_3, B_2, C_1, D_2$ with total
weight $34$

Case #3: Re-define the problem

Clearly, the introduction of "layers" can make the analysis hard. So, we can
redefine the problem without requiring $G$ to be multipartite.
That is, instead of having layers,
we add an edge with $\infty$ weight between every pair on the same layer. Then
the minimum weight k-induced subgraph $H_k$, cannot have two nodes from the
same layer, as this would imply that $H_k$ contains an edge with $\infty$ weight.
Back in our example, the previous graph becomes:

The case #3 is NP-hard

Unfortunately in the general case this problem is NP-hard (because it is an optimization problem), as there is a reduction from k-clique:

Let $R$ be an undirected unweighted graph that we want to check whether it has a $k$-clique. That is, we want to check whether $clique(R,k)$ is True or
not. Thus, we create a new directed graph $R\space'$ as follows:

$R\space'$ contains all the nodes from $R$
$\forall$ edge $(u,v)\in R$, we add the edges $(u,v)$ and $(v,u)$ in
$R\space'$ with $weight = 1$
$\forall$ edge $(u,v)\notin R$, we add the edges $(u,v)$ and $(v,u)$ in
$R\space'$ with $weight = \infty$

Then we find the minimum weight k-induced subgraph $H_k$ in $R'$. It is true that:

$$\sum_{e \in H_k} weight(e) < \infty \Leftrightarrow clique(R,k) = True$$
$:\Rightarrow$
If the total edge weight of $H_k$ is not $\infty$, this implies that for every
pair of nodes in $H_k$, there is an edge with weight $1$ in $R\space'$ and thus
an edge in $R$. This by definition means that the nodes of  $H_k$ form a k-clique
in $R$.
Otherwise (the total edge weight of $H_k$ is $\infty$) it means that it does not
exist a set of $k$ nodes in $R\space'$ that has all edge weights $< \infty$.

$:\Leftarrow$
If $R$ has a k-clique, then there will be a set of $k$ nodes that are fully connected. This set of nodes will have no edge with $\infty$ weight in
$R\space'$. Thus, these nodes will form an induced subgraph of $R\space'$
and the total weight will be smaller than $\infty$.

(proof is not formal; I just describe the general idea)

The Question

Although the problem that I described is NP-hard (assuming that my analysis
is correct), I want to find an approximation algorithm (along with a proof) that
can give me a solution that is at most $n$ times worse than optimal (obviously
we want $n$ to be as small as possible).

There is also a paper that solves a similar problem, but I don not know
if that helps.

The problem cannot be approximated. Consider the reduction that you described from k-clique to your problem but this time assign zero weight to the original edges. Any (multiplicative) approximation algorithm also solves the k-clique problem this is because it must return 0 if there is a k-clique.


Entropy notation: What does this mean? If you look at page 13 of the lecture slides here there is this line

$H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$

I don't really understand what the term on right hand side is. At first I thought it's joint probability of binary random variables but that does not make sense. After a while I notice that the first parameter is the probability of $Y = 0$, the second parameter is the probability $Y = e$ and the third parameter is the probability $Y = 1$. However, I still dont really understand what this notation means, and why this equates to

$H(\alpha,(1-\alpha)) + (1-\alpha)H(\pi,(1-\pi))$

Can someone please help me out here?

Thank you!

The first thing you should realize to understand it is that the $H(Y)$ notation corresponds to the calculation of the information entropy for the states in $Y$, such that $H(Y) = -\sum\limits_{y \in Y} p(y) \log[p(y)]$.  With that in mind, we can interpret the expression and equate the terms.  You are correct that the three parts correspond to the probability of $0$, $e$, and $1$, where $e$ is the state of erased information.  Expanding it we get:

$H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha)) $
$\quad= -(1-\pi)(1-\alpha)\log[(1-\pi)(1-\alpha)] - \alpha\log(\alpha) - \pi(1-\alpha)\log[\pi(1-\alpha)]$

This gives us the full expression for calculating the entropy of the system composed of those three states.  Next, as we usually do when proving an equality, we cheat and look at the answer to see what form we need it in.  Your last term has all the $\pi$ terms clumped onto one side, and all the $\alpha$ terms clumped onto another (except for where they are also a coefficient).  Thus we will organize the log terms in this manner.  First we use the log rules to expand the products:

$ \quad= -(1-\pi)(1-\alpha)\log(1-\pi) - (1-\pi)(1-\alpha)\log(1-\alpha) $
$\quad\phantom{=} - \alpha\log(\alpha) - \pi(1-\alpha)\log(\pi) - \pi(1-\alpha)\log(1-\alpha)$

Then we sort all the log terms in the order of the final expression:

$ \quad = -\alpha\log(\alpha) - (1-\pi)(1-\alpha)\log(1-\alpha)  - \pi(1-\alpha)\log(1-\alpha) $
$ \quad\phantom{=} - \pi(1-\alpha)\log(\pi) -(1-\pi)(1-\alpha)\log(1-\pi)$

Then we simplify and factor:

$ \quad = -\alpha\log(\alpha) - (1-\alpha)\log(1-\alpha) + (1-\alpha) \cdot [ -\pi\log(\pi) - (1-\pi)\log(1-\pi) ]$

And this is equivalent to:

$$H(\alpha, 1-\alpha) + (1-\alpha) H(\pi, 1-\pi)$$

This can be interpreted as the left part being the entropy from erasing (probability $\alpha$) or not erasing, and the right part being, in the event it was not erased, the entropy from it being a 1 (probability $\pi$) or a 0.  It should also make some intuitive sense that this will be equal to the entropy from the distribution of final states of $0$, $e$ (erased), and $1$.


Why is a heap better than a linked list for implementation of a priority queue? Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.

Why is it better to have log-n for both than n for one and constant time for the other?

It only really matters in the limit: for small sizes, the difference isn't really important.

But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is asymptotically faster than $O(n) + O(1) = O(n)$.


Why does higher-order abstract syntax need an inverse to define catamorphisms? In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of higher-order abstract syntax (HOAS):

  One obstacle preventing the widespread use of this technique is the difficulty in using elimination forms, such as catamorphisms, for datatypes containing functions. The general form of catamorphism for these datatypes requires that an inverse be simultaneously defined for every iteration. Unfortunately, many operations that we would like to define with catamorphisms require inverses that do not exist or are expensive to compute.

They go on to demonstrate this problem with a small example, in Haskell. They define the following datatypes to represent simple lambda terms with HOAS:

data Exp = Lam (Exp -> Exp) | App Exp Exp
data Value = Fn (Value -> Value)

Lam represents lambda terms, App represents function application, and Fn represents evaluated functions. They next attempt to define eval :: Exp -> Value, but this causes trouble, as it requires converting a function of type Exp -> Exp to one of type Value -> Value. Since Exp appears in both positive and negative positions, this requires functions from both Exp -> Value and Value -> Exp to define.

The remainder of the paper proposes a solution to that problem, but I am stuck on something else: I don’t understand why it’s a problem at all. Usually, in programming language papers, we define languages with grammars like the following one:

$$
\begin{align*}
v &::= \lambda x. e \\
e &::= v \thinspace | \thinspace e \thinspace e
\end{align*}
$$

If we define a big-step evaluation relation $e \Downarrow v$, we have no need to define some other “unevaluation” relation $v \Uparrow e$, as lambdas are already values, so $\lambda x.e \Downarrow \lambda x.e$, which is quite straightforward.

It seems to me that a natural translation of the above grammar to HOAS is different from the one Washburn and Weirich present. Specifically, I think it would look more like this:

data Exp = Lit Value | App Exp Exp
data Value = Fn (Value -> Exp)

Defining eval on this grammar is as simple as defining the usual big-step relation:

eval :: Exp -> Value
eval (Lit v) = v
eval (App e1 e2) = case eval e1 of
  Fn v -> eval (v (eval e2))

But this solution seems much too simple to be right. Boxes Go Bananas is a well-cited paper from reputable authors published at a reputable PL conference, so its solution surely must have some advantage over the one I presented above. My question, therefore, is simply this: what is that advantage? What am I missing?

By being corecursive between the types, you indeed get a representation of a grammar, and it does have binding. But now you've sort of "baked in" the unembedding by making it "definitionally id". (This is similar to the Place constructor in Fegaras and Sheard).

So you can evaluate to Value. But what if you want to evaluate to anything else? You can't, unless it is something that "passes through" Value. So consider writing an "abstract interpreter" for your language (i.e., where you evaluate only to the "type" of the expression but without computing, or where you only "count the reductions" without computing). You can't, because you need to pass through having concrete elements of Value to go under lambdas.

You can fix this by having both Place and also a normal HOAS binding form, as in the above paper. But then that still doesn't suffice, for reasons they explain (and similar to what I've described -- see section 2) and so you make Place go further abstract by parameterizing over it, etc. Follow your nose further and you'll hit free monads. I got an intuition for this stuff from Edward Kmett's phoas post.


Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$ Prove if a oracle machine $K$ is given with $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$.

Lets assume that $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{co\text{-}P^k}=\mathsf{co\text{-}NP}$.  I am stuck here, I don't know how to prove this. Can someone help?

I know that $\mathsf{P}=\mathsf{co\text{-}P}$ but can I also say $\mathsf{P^k}=\mathsf{co\text{-}P^k}$ or do I have to prove it ?

Hint: The proof that $\mathsf{P}=\mathsf{co\text{-}P}$ relativizes. That means that if the machines in question are allowed access to some oracle, then the proof goes through. The reason is that the proof just works even when you add the oracle - go over the proof carefully and convince yourself.

"Can I also say that ... or do I have to prove it?" You should be able to answer this yourself. If you can't, go over the definitions a few more times until you really understand what they mean, and then, at the very least, you can say whether "..." follows directly from something that you saw in class, or whether it does not. In the latter case, you should prove it.

In this specific case, given that you already saw a proof of a similarly looking result $\mathsf{P}=\mathsf{co\text{-}P}$, it should seem reasonable to try and see if that same proof generalizes to give $\mathsf{P}^K = \mathsf{co\text{-}P}^K$. In this case it does; in other cases it might not, and then you have to work harder.


The cheapest path in the graph I am supposed to decide, if the statement is true or false and use arguments for my answer.

In every weighted n-vertices graphs:

with no negative weighted edges,
with n>10,
in which every weighted edge appears constant number of times(e.g. 1,2,3.., but not n number of times), but graphs, in which every edge has the same value, does not satisfy this condition,

there exists between every two vertices at most 4*n^3.

I tried to draw some graphs and I conclude that all of them satisfy my conditions. But I do not have general explanation.

So is that true? If not, can you say me some counter example?

Thanks.

Hint: consider cases where every weight is very large.


How is a type system related to a progam? In another question about Lambda Calculus, Andrej Bauer made the comment:

  Lambda calculi of various forms are formal systems. They consist of
  abstract syntax (for terms and for types, if present), judgments
  (typing judgments and equations), and rules of inference. They are not
  programming languages (unless we prescribe operational semantics) and
  neither is it the case that a type system equals a program that checks
  types. So I think this whole question is a bit misdirected, still. Of
  course, an important aspect of a type system is how to implement it on
  a computer, which brings in questions about algorithms, etc. But a
  priori, the type system has none of that.

I understand most of this, but I cannot wrap a logical understanding around:

  neither is it the case that a type system equals a program that checks types.

My understanding of a type system is that it is a set of rules in a formal system used to determine if a type is valid in a context and that those rules, via implementation, are used to establish the validity of a use of a type in a context in a programming language.

However the statement has me thinking there is no connection, or that there is more meaning to the statement but I don't see the details to separate a type system from a program or make a logical connection between the two so that the statement makes sense.

What is the relation between a type system and a program?

Your understanding that a type system is a set of rules in a formal system is right, but the rest is a bit garbled.  The purpose of the type system is to delineate which terms or programs make sense.  It is up to the language designer to decide which programs "make sense".  There is no claim that the language specifies all programs that make sense.  When somebody proposes a new type system, they are saying, "here are more programs that make sense and our type system captures them."

Andrej is saying one shouldn't equate the type system with the type checker (which is a program).

There is nothing too deep about it.  Merely that the type system, i.e., the set of rules, stand independently of any particular implementation.  One could even devise type systems that are undecidable, i.e., no possible type checking program exists.  Admittedly such type systems may not be of much practical use, but nobody denies that they are type systems in the first place!


For the time hierarchy theorem, how is the input translated efficiently? I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book.  The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is assumed that the encoding of N's tape alphabet using M's alphabet causes only a constant factor slowdown. This seems plausible since if N's alphabet is size k then M can use $\log k$ cells to represent each symbol that N writes to the tape.

But my question is this: If this is how the simulation works then before the simulation starts M will have to change the input so that each bit is repeated $\log k$ times and I don't know how to do this without adding a quadratic term to the time. I should say its assumed that N's computation is no faster than $O(n\log(n))$.

This has been clarified in the book's online errata:

  Page 369, Proof of the Time Hierarchy Theorem 9.10.

  The proof requires some additional technical discussion at one place. In Stage 4 of D, it simulates M on w. This simulation may require representing each cell of M's tape with several cells on D's tape because M's tape alphabet is arbitrary and D's tape alphabet is fixed. However, initializating the simulation by converting D's input w to this representation involves rewriting w so that its symbols are spread apart by several cells. If we use the obvious copying procedure for spreading w, this conversion would involve O(n^2) time and that would exceed the O(t(n)) time bound for small t.
  Instead, we observe that D operates on inputs w of the form x10^k where x = ‹M›, and we only need to carry out the simulation when k is large. We consider only k > |x|^2. We can spread w by first using the obvious copying procedure for x and then counting trailing 0s and rewriting these by using that count. The time for spreading x is O(|x|^2) which is O(n). The time for counting the 0s is O(n log n) which is O(t(n)) because t is time constructible.

  Reported 11/15/12 by Kaveh Ghasemloo of the University of Toronto.


Classification training data, but regression prediction Suppose I'm performing machine learning on a simple dataset, and have a bunch of training data of the form:

x (feature)   y (label)
-----------------------
1             0
2             1
3             1
4             0
5             1
6             1
...

Where the labels are values in two classes, $[0, 1]$.  Clearly, this training data lends one to believe that it will be a classification task.

However, suppose I want to output instead the probability that a feature will take the class $1$.  Then, my output is more of a regression task.

Consequently, when I'm designing a simple neural network with just a single input layer and single output layer, how many output units should I have?  Should I have two output units, one for each class, and if so, how do I ensure that each pair of outputs will be a valid probability distribution (i.e. sum to one)?  Or should I have only one output unit, and treat the entire problem as a regression task?

There are probably pros/cons to each approach... thanks for your help!

This is still a binary classification task.  In the abstract, there are two ways to handle this:

Most classifiers can output a predicted class and a confidence score (which indicates how confident the classifier is in its prediction).  If you don't need a probability, you can use the confidence score.  If you want to turn it into a probability, you can use various calibration procedures to turn this into a probability in the range [0,1].
Some classifiers can output a probability directly.  Generative models in particular are good at this.  For instance, logistic regression outputs both a predicted class and a probability for the class.

If you construct a neural network with $k$ outputs, one per class, using a softmax output and train it to minimize the cross-entropy loss function, then you can interpret the output as a probability distribution on the classes (though beware that it might be biased or over-confident).  The softmax ensures the outputs are normalized to be in the range [0,1] and to sum to one.

In your case, you can try both approaches (two outputs with softmax; or a single output with a sigmoidal activation function).  The only way to know which will perform better is to try both, but personally, I'd lean towards using two outputs and softmax.


Simplest Turing-complete ruleset for Markov algorithm Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?

Rule 110 is universal, and can be expressed as a Markov algorithm.

In particular, Rule 110 corresponds to the Markov system with alphabet $\{0,1,\verb!^!,|,\$ \}$ and a pair of bits for each element in the automaton. The pair of bits records the current status of that element (empty or filled) and the previous status.  Elements are updated by doing a left-to-right scan; the marker $|$ keeps track of where we are in the scan, $\verb!^!$ indicates the start of the string, and $\$$ indicates the end of the string.  We obtain the following $2^6 + 2^2 + 2^6 = 132$ rewriting rules:

$uv|wxyz \to uvxt|yz$ where $t = \text{Rule110}(u,x,z)$,
$|uv\$  \to vv\$ $
$\verb!^! uvwxyz \to \verb!^! vv|wxyz$

where $u,v,w,x,y,z$ are meta-variables that range over $\{0,1\}$.  In other words, the first bullet item corresponds to $2^6$ rewriting rules: $00|0000 \to 0000|00$, $00|0001 \to 0001|01$, etc.; the second bullet item corresponds to $4$ rewriting rules, corresponding to all possible ways to assign $0$ or $1$ to $u$ and $v$; and the third bullet item corresponds to $2^6$ more rewriting rules.

What's going on with this crazy re-writing system?  It's actually not as ridiculous as it looks.  For a cellular automaton with $n$ elements, we start with a string of length $2n+2$ of the form $\verb!^! 0x_1 0x_2 0x_3 \dots 0x_n \$ $, where each $x_i$ is $0$ or $1$ according to whether that element is empty or filled.

The interpretation of the pair of symbols $uv$ is that the current status of the element is given by $v$, and the previous status is given by $u$.  We scan over the elements from left to right, updating the status of each element.  The marker $|$ indicates where we are in the scan right now.  Notice that we need to keep track of both the previous and current state of each element, which is why I use a pair of bits for each element rather than one bit per element.

The first bullet item takes care of the left-to-right scan.  The second bullet item makes sure that the scan terminates, and removes the $|$ marker.  The third bullet item ensures that if there is no $|$, then we re-start the scan starting at the left.

You can also play a similar trick with any Turing machine, and thus emulate a universal Turing machine with a Markov algorithm.

Suppose we have a Turing machine with tape alphabet $\Gamma$ and finite state space $Q$.  Then the Markov system has alphabet $\Sigma = \Gamma \cup Q \cup \{\text{<}\}$.  The idea is that the string $t_1 t_2 \cdots t_i \text{<} q t_{i+1} \cdots t_n$ corresponds to a configuration of the Turing machine that has $t_1 t_2 \cdots t_i t_{i+1} \cdots t_n$ on its tape, has state $q$ in its finite-state control, and where the head is positioned over $t_i$ in the tape.  The marker $\text{<}$ indicates the current position of the head.

Then it's easy to write a finite set of rewriting rules that correspond to the operation of the Turing machine.  In particular, the behavior of the Turing machine depends only on the symbol under the head and the state of the finite control.  Thus, we'll get a set of rewriting rules of the form $t \text{<} q u \to t' u \text{<} q'$ (for transitions where the head moves right) and $s t \text{<} q \to s \text{<} q' t'$ (for transitions where the head moves left).  Since the finite-state control has only finitely many state transitions, we'll need only finitely many rewriting rules in the Markov algorithm.

Finally, we can apply this to your favorite universal Turing machine.  The smaller the universal Turing machine, the simpler the resulting Markov algorithm will be.


Is F(F(s,x), x) necessarily a PRF if F is? Given a PRF - F, is $G_s(x)=F_{F_s(x)}(x)$ necessarily a PRF?

First I thought how to tackle this problem. First I tried using a hybrid argument:
$|\mathbb P[F_{F_s(x)}(x)] -\mathbb P[f(x)]|\leq |\mathbb P[F_{F_s(x)}(x)] -\mathbb P[F_{f(x)}(x)]| + |\mathbb P[F_{f(x)}(x)] -\mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.

Let $\mathrm{RF}_n$ be the set of random functions over $\{0,1\}^n$. Let  $F_{f,i}$ be an oracle that answers the first $i$ queries with $F_{f(\cdot)}(\cdot)$ and answers the remaining queries with $f(\cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $\{f\leftarrow \mathrm{RF}_n:F_{f(\cdot)}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$, it can also distinguish  $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$ for some $k$.

Now construct a new distinguisher $D'$. Given an oracle $\mathcal{O}(\cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns

$F_{f(x)}(x)$ if $i<k$, or
$\mathcal{O}(x)$ if $i=k$, or
$f(x)$ if $i>k$.

We can see if $\mathcal{O}$ is $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$. If $\mathcal{O}$ is $\{s\leftarrow\{0,1\}^n:F_s(\cdot)\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$. Since $D$ can distinguish $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$, our distinguisher $D'$ can distinguish $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$ and $\{s\leftarrow\{0,1\}^n:F_s\}$, which contradicts to the fact that $F$ is a PRF.

So $\{f\leftarrow \mathrm{RF}_n:F_{f(\cdot)}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.


Upper bound and lower bound of a custom function T(n) Assume a function $T(n)$:
$$T(n)=\log{\log^{*}{n}}$$
Let's define:
$$\log^{*}{n}=\min\{i\ge{0}:\log^{(i)}{n}\le1\}$$
and:
$$\log^{(i)}{n}=\log{(\log^{(i-1)}{n})}$$
Is the following $f(n)$ function an upper bound or a lower bound of $T(n)$?
$$f(n)=\log^{*}{\log{n}}$$

To see if $f(n)$ could possibly be an upper bound, I feel like the following limit needs to be gone through:
$$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{\log^{*}{n}}}=?$$
Now I wonder if the above limit might boil down to this:
$$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{(\min{\{\log\log\log\cdots\log^{(0)}{n}\}})}}$$
I'm not quite sure how to solve the above limit to get an idea of the upper bound of $T(n)$. Also, the lower bound is another story which I have little idea about.

For $n$ satisfying $\log n > 1$, we have $\log^* \log n = \log^* n - 1$ (exercise). On the other hand, $\log \log^* n $ is much smaller than $\log^* n$. Hence $\log \log^* n = o(\log^* \log n)$.


Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps? The halting-after-$n$ steps problem may be defined as the question if a given turing machine halts after a maximum of $n\in\mathbb{N}$ steps. Is it theoretically possible to solve this problem in general in less than $n$ execution steps (just execution the program) or can't this be done? If not, why not?

Thank you

The time hierarchy theorem, or rather its proof, gives some answer to this question. If you look at the proof, you should get a lower bound of $\Omega(n/\log n)$.

In more detail, consider the language $L$ of all triples $\langle M,x,1^t \rangle$ such that $M$ halts on $x$ after at most $t$ steps. Suppose that this can be solved in time $f(n)$, where $n$ is the input length (which is $t + |M| + |x|$). Then you can construct a Turing machine which on input $\langle x,1^t \rangle$ determines whether $\langle x,x,1^t \rangle \in L$, if so runs into an infinite loop, otherwise halts. When run on itself as input, this machine either halts in time $f(t + O(1)) + O(1)$ or never halts. Hence if $f(t + O(1)) + O(1) \leq t$, we reach a contradiction. This shows that $f$ has to essentially be at list linear.