Maximum subset pairwise not divisible by $K$ I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$.
I tried to solve this problem, but I have found the quadratic solution, which is not efficient response.
$K < 100, N < 10000$, where $N$ is the number of elements and $K$ is given constant. Is there better than quadratic solution?

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words,

$$K \mid ( n_1 + n_2 ) ~~~~ \Longleftrightarrow ~~~~ K \mid \left((n_1 ~mod ~K) + (n_2 ~mod ~K)\right).$$

The second concept that you need to consider is that, the sum of two numbers $r_1 \neq r_2$ is $K$, only if one of them is strictly smaller than $K/2$ and the other is no less than $K/2$. In other words,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ r_1 <K/2, ~r_2 \geq K/2~~~~~~ (r_1 \neq r_2,~\text{w.l.g.}~r_1 < r_2).$$

The third concept that you need to consider is that, if the sum of two numbers $r_1 \neq r_2$ is $K$, they both deviate from $\lceil K/2 \rceil -1$ by a certain $k \leq \lceil K/2 \rceil$, i.e.,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ \exists_{k \leq \lceil K/2 \rceil -1}~~~\text{such that}~~~ r_1 = \lceil K/2 \rceil -1 -k, ~r_2  = \lceil K/2 \rceil +k.$$

So, for evey $k$ in the third concept, you need to put either $r_1$ or $r_2$ in the solution set, but not both of them. You are allowed to put one of the numbers that are actually divisible by $K$ and if $K$ is even, you can add only one number that its remainder is $K/2$.

Therefore, here is the algorithm.

Given a set ${\cal N}=\{ n_1, n_2, \cdots, n_N \}$, let's find the solution set ${\cal S},$

Consider ${\cal R} = \{ r_1=(n_1 ~mod ~K), r_2=(n_2 ~mod ~K), \cdots, r_N=(n_N ~mod ~K) \}$
${\cal S} \gets \emptyset$
for $k \gets 1$ to $\lceil K/2 \rceil -1$:
$\hspace{1.3em}$ if $count({\cal R},k) \geq count({\cal R},K-k)$:
$\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=k$
$\hspace{1.3em}$ else:
$\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=K-k$
add only one $n_i$ to ${\cal S}$ such that $r_i=0\hspace{1em}$// if exists
if $K$ is even:
$\hspace{1.3em}$ add only one $n_i$ to ${\cal S}$ such that $r_i=K/2\hspace{1em}$// if exists
Output ${\cal S}$

The algorithm is quite long, but the idea is very simple.


What roadblocks are there to HSA becoming standard, similar to floating point units becoming standard? I remember when my dad explained to me for the first time how a certain model of computer he had came with a "math coprocessor" which made certain math operations much faster than if they were done on the main CPU without it. That feels a lot like the situation we are in with GPUs today.
If I understand correctly, when Intel introduced the x87 architecture they added instructions to x86 that would shunt the floating point operation to the x87 coprocessor if present, or run some software version of the floating operation if it wasn't. Why isn't GPU compute programming like that? As I understand it, GPU compute is explicit, you have to program for it or for the CPU. You decide as a programmer, it isn't up to the compiler and runtime like Float used to be.
Now that most consumers processors (Ryzen aside) across the board (including smartphone Arm chips and even consoles) are SoCs that include CPUs and GPUs on the same die with shared main memory, what is holding back the industry from adopting some standard form of addressing the GPU compute units built in to their SoCs, much like floating point operation support is now standard in every modern language/compiler?
In short, why can't I write something like the code below and expect a standard compiler to decide if it should compile it linearly for a CPU, with SIMD operations like AVX or NEON, or on the GPU if it is available? (Please forgive the terrible example, I'm no expert on what sort of code would normally go on a GPU matter, hence the question. Feel free to edit the example to be more obvious if you have an idea for better syntax.)
for (int i = 0; i < size; i += PLATFORM_WIDTH)
{
    // + and = are aware of PLATFORM_WIDTH and adds operand2 to PLATFORM_WIDTH
    // number of elements of operand_arr starting at index i.
    // PLATFORM_WIDTH is a number determined by the compiler or maybe
    // at runtime after determining where the code will run.
    result_arr[a] = operand_arr[i] + operand2;
}

I am aware of several ways to program for a GPU, including CUDA and OpenCL, that are aimed at working with dedicated GPUs that use memory separate from the CPU's memory. I'm not talking about that. I can imagine a few challenges with doing what I'm describing there due to the disconnected nature of that sort of GPU that require explicit programming. I'm referring solely to the SoCs with an integrated GPU like I described above.
I also understand that GPU compute is very different than your standard CPU compute (being massively parallel), but floating point calculations are also very different from integer calculations and they were integrated in to the CPU (and GPU...). It just feels natural for certain operations to be pushed to the GPU where possible, like Floats were pushed to the 'Math coprocessor' of yore.
So why hasn't it happened? Lack of standardization? Lack of wide industry interest? Or are SoCs with both CPUs and GPUs still too new and is it just a matter of time? (I am aware of the HSA foundation and their efforts. Are they just too new and haven't caught on yet?)
(To be fair, even SIMD doesn't seem to have reached the level of standard support in languages that Float has, so maybe a better question may be why SIMD in general hasn't reached that level of support yet, GPUs included.)

A couple issues come to mind:
Synchronization/Communication overhead
In order to seamlessly transition from CPU to GPU code you need to communicate with the GPU. The GPU additionally has to be available(aka not rendering the screen), and all instructions on the CPU side of things need to retire/finish executing. Additionally you need to make sure that any pending writes have reached L3 cache/main memory, so that the GPU sees writes. As a result a transition to GPU code is quiet expensive, especially if the GPU is doing something latency sensitive(like rendering the next frame of something), and you need to wait for that process/task/thread/whatever to finish. Similarly returning back to the CPU is also expensive.
In addition you have to handle what happens if multiple CPU cores start fighting over the GPU.
Differing Memory Performance Needs
GPUs typically require high bandwith memory, but low latency is not as important, while CPUs are typically more sensitive to low latency.
Low performance GPUs can and do use main memory, but if you wanted a high performance GPU built into the CPU you would potentially need two different types of memory. At which point there isn't much advantage to having everything on one chip, since all that does is make cooling harder.
Inertia/Dev Infrastructure
SIMD has compiler support right now and lots of work put into it. Simple GPU style workloads like dot products are already memory bound anyway on a CPU, so existing CPU+GPU combos would not benefit.
Could just have lots of SIMD
Not much more to say beyond heading. SIMD+Many cores+lots of execution units would give you a more GPU like CPU. Add better SMT for a bonus. See Xeon Phi for a real world implementation of this concept. Though one thing worth mentioning is silicon spent on more GPU style features is silicon not spent on branch prediction etc.
Edit:
Another thing that comes to mind is there are broadly speaking three reasons to have a GPU.

Just want to browse the web, display Netflix etc. For this use case existing CPU and GPU performance/architecture is more than sufficient.
Want to play high end videogames etc. Existing architecture has a lot of momentum behind it, and I'm not convinced gaming CPU workloads really need better SIMD performance, and instead need better cache/branch etc, though I don't really know. However the GPU is likely already busy so it might not be the best idea to shift even more work to the CPU
HPC applications. Custom hardware like Xeon Phi is available for people who need a more GPU like CPU.


Finding a solution to the following conditions? So for these 5 conditions, I am trying to find the solution/formula for them.
What would $a_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a_n = a_{n - 1} + 2n$.   Any help would be greatly appreciated.

$$
\begin{align*}
a_0 &= 4 \\
a_1 &=  6 \\
a_2 &= 10 \\
a_3 &= 16 \\
a_4 &= 24
\end{align*}
$$

There are infinitely many sequences starting $4,6,10,16,24$. If I understand you correctly, this sequence was generating according to the rule $a_n = a_{n-1} + 2n$ with the initial value $a_0 = 4$. In that case, you have
$$
a_n = a_0 + \sum_{k=1}^n (2k) = a_0 + 2 \frac{n(n+1)}{2} = n^2 + n + 4.
$$


triangle inequality TSP is NP-complete? I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete.

If you accept a proof that TSP without triangular equation is NP-complete then it is easy: If you take an instance of "TSP without triangular equation", then you just add a large enough constant to each edge to get the triangular equation, solve it as an instance of "TSP with triangular equation", and that solves your original problem.


Solving road trip problem in linear time Consider the following problem:

  You are on a road trip, and there are $n$ cities along a road, labeled
  $1$ to $n$. Conveniently, these cities all lie on a single road, and
  the distance between two adjacent cities is one mile. We are currently
  at city $1$, and would like to drive to city $n$. Each day, we can
  drive at most $k$ miles, before we sleep for the night. We pay $a_i$
  for lodging at the city located at mile $i$. Each lodging cost is a
  positive number. Given that we can spend an arbitrary number of days
  on the road trip, determine a plan of driving to minimize lodging
  costs.

  Input: An integer $k$, and a length $n$ array of positive integers
  $a_1,...,a_n$.

  Output: The minimum lodging cost to complete the road trip starting
  from city 1 and ending at city n.

The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?

This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.


How fast can we optimally cluster 1-D data? K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) is minimized overall, i.e. the clusters as as "tight" as possible.

While NP-hard in the general case, I know it is $\text{PTIME}$-tractable if the points are on a line.

What is the best known upper bound on the time complexity of optimal clustering for the 1-dimensional case?

Note: Lower bounds are also interesting, but less so.

Here's what my search has come up with:

There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. This is described in:

  Wang, Haizhou, and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal 3, no. 2 (2011): 29.

That being said - I'm thinking perhaps this can be improved to $\mathop{o} \left( k \cdot n \log{n} \right)$ somehow, or at least $\mathop{\omega} \left( k \cdot n^2 \right)$.


How to prove that algorithm returns the value which appears more than $n/2$ times in the array? Given the following algorithm (pseudocode):

alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned.

$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the count decreases by one.

CASE 1: If the pattern is strictly alternating combinations of type $C$  then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the candidate is $M$.

CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the candidate will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the count will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.

I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.

Note: In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of distinct elements. Therefore, if a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.


Context-free grammar for language with unequal numbers of a and b I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

S -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> aT

This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

S-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> bT | aTb | bTa

This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'...

I've been trying to think the way where you can input an alphabet (i.e S -> aV | bV) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.

Here are some hints:

Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w) < \#_b(w) \}$. Below we concentrate on $L_a$.
Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.
Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.


Advanced placement CS A Exam What would be the standard topics covered in an 'Advanced Placement Computer Science A' test? Is there any good study reference someone can share?

Edit: Answer

An adjustment for my search term returned a Wikipedia page just for this type of exam and the AB version.

I used the following book as a resource material and it was pretty good:

  Barron's AP Computer Science A

You can see the book preview there along with the contents.


Reconstruct the minimal path cost from the delta-stepping algorithm? I was coding the delta-steppping algorithm from this paper. They describe almost everything about the algorithm but not how to get the path.
As an output I am getting the dictionary tent where tent[v] contains the minimal cost to go from $s$ to $v \in V$. How can I retrieve the path of the minimum cost based on this algorithm?

The algorithm that you're implementing is based on the Dijkstra Algorithm, so we can use the same idea to get the path, that is, keep the predecesor data each time you relax the edges (see pred data structure below). Actually, in the same paper, they state where you have to look at in the following method.

However, we need the information of the vertex we are using in the relaxation method, as you know we are comparing these two values, $tent[w]$ vs $tent[v] + Cost[v,w]$. So if after all $tent[v] + Cost[v,w]$ is less than $tent[w]$, we need keep $v$ to say we are going to use the edge $(v,w)$.

Then I suggest you to introduce $v$ as follows:

Replace $Req$ for this definition, $$ Req = \{(w, tent(v) + c(v,w), v)\ :\ v\in B[i] \text{ and  } (v,w) \in light[v]\}. $$

Add a third argument to the method relax:

 relax(w,d,v)
    if d < tent[w]:
        pred[w] = v
        ...

And fix all for each with $(w,d,v)\in Req$ and the other.

To retrieve the path from $s$ to $w$, do something like:

for v in V: pred[v] = INF
...
def findpath(w):
  v = w
  path = []
  while pred[v] is not INF:
     path.append(v)
     v = pred[v]
  path.reverse()
  return path


k-center algorithm in one-dimensional space I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution found, not an approximation) in O(n^2) polynomial time without depending on k or using dynamic programming.

A general description of the k-center problem: Given a set of nodes in an n-dimensional space, cluster them into k clusters such that the "radius" of each cluster (distance from furthest node to its center node) is minimized. A more formal and detailed description can be found at http://en.wikipedia.org/wiki/Metric_k-center

As you might expect, I can't figure out how this is possible. The part currently causing me problems is how the runtime can not rely on k.

The nature of the problem causes me to try to step through the nodes on a sort of number line and try to find points to put boundaries, marking off the edges of each cluster that way. But this would require a runtime based on k.

The O(n^2) runtime though makes me think it might involve filling out an nxn array with the distance between two nodes in each entry.

Any explanation on how this is works or tips on how to figure it out would be very helpful.

First,

  There exist optimal solutions in which each cluster consists of a contiguous sequence of points in the real line.

Any other optimal solutions can be transformed into the cases above. In the following, we focus on the optimal solutions of the kind above.

The complexity of the following "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

The case for $k=1$ is easy. Denote the optimal solution to $k=1$ in $n$ points by $R_{n,1}$.

Let $R(n,k)$ be the optimal solution for the problem of $k$-center in the first $n$ points. For convenience, define $R(n,k) = 0$ if $k \ge n$ (This is reasonable because we can choose each point as the center of the cluster consisting of only itself).

For general $k > 1$, we consider all the cases according to the number (denoted $m$) of points that are assigned to the last cluster (that is, the last cluster contains a contiguous sequence of the rightmost $m$ points).

$$R(n,k) = \min_{0 \le m \le n} \{ R(n-m, k-1) + R_{m,1} \}$$

The complexity of the "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

Note: This paper [1] gives an $O(n \log n)$ time algorithm.

[1] Efficient Algorithms for the One-Dimensional $k$-Center Problem. arXiv, 2014.


What are some concrete (near-)"worst-case" examples of subset-sum? I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.

However, I suspect it may be faster than existing solvers in "near-worst" cases, but I don't know how to check this.
What are some concrete examples of near-worst-case subset-sum problems I can try it on?

Note that I'm looking for reasonable examples here (< 64 bits -- i.e., numbers that actually pop up in the real world), not, for example, an instance with 500 digits. I'm looking for reasonable examples here. The idea is that I'm trying to solve real-world subset-sum problems well in "hard" cases.

The naive dynamic programming complexity is $O(sN)$ where $s$ is the integer bit precision, $N$ is the set cardinality. With some slight tricks in memoization cutting the precision constant in half, an instance with 64 bits precision should be solvable without much optimization in a linearly increasing fashion and as fast as memory access allows.

However, the naive method for small $s$ but large $N$ is dynamic programming which has subjectively large memory requirements. In practice this is the constraint that is prohibative for large instances skewed towards small precision, since many of the non-cryptographic applications I can think of deal with embedded systems having low memory and real-time constraints that limit non-uniform memory access.

At the other end of the spectrum if you have PiB subset-sum instances with small $s$ but very large $N$, the same issues arise as in sorting. These instances are incredibly 'easy' from a theory perspective but the micromanagement constant factor details dominate such as cache usage, memory walls, parallelization, bandwidth saturation, and code/data locality. Many of the techniques for fast solvers become invalidated at that size due to either reliance on a central memoization table or chaotic memory access.

The major applications for subset-sum that I know of are cryptographic in nature, which necessitates that the natural 'real-world' integer precision is far larger than 64 bits. In addition, most of the various manufacturing and finance applications do encounter the need for integer precision much larger than 64 bits as a way to actually encode the problem without blowing up $N$ in a very non-linear manner. This is required even though the original 'real-world' quantities are far less than 64 bits.

So hard subset-sum instances with 64 bit precision don't exist in the manner that I think you want to test. If an analogy helps, this is similar a complexity outcome to finding the prime factorization of a very large number but limited to prime factors with 64 bits of precision rather than the general case.


Inequality over the entropy of an integer-valued random variable I stumbled upon this inequality over a course on Information Theory :

  If $Z\in\mathbb{N}$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})$ where $h$ is the binary entropy function

I have been trying to prove it using the log-sum inequality :

  $ \sum_i a_i \log \frac {a_i}{b_i} \geq (\sum_i a_i) \log \frac {\sum_i a_i}{\sum_i b_i} $ for $a_i, b_i$ non-negative numbers

Using, for example, $a_i = P(Z=i)$ and $b_i = iP(Z=i)$.
But I couldn't really get throught it.

Part of my problem with this inequality is that I don't understand it : where does this use of the binary entropy function come from ? Even the relation between entropy and the mean seems unnatural to me.

Man, that's a nasty inequality.

Anyways, given a certain expectation $E[Z]=\mu$, it is known that the distribution that maximizes $H(Z)$ while keeping $E[Z]=\mu$
 is the the Geometric Distribution with parameter $p=1/\mu$.

Then, it is easy to check that the inequality is satisfied (in fact the equality holds).
Indeed, if $Z\sim Geo(p)$ then $E[Z]=1/p$ and $H(Z)=-\log p -\frac{1-p}{p}\log(1-p)$.
Since this distribution maximizes $H(Z)$, any other distribution with the same expectation will have a lower left-hand side, while the right-hand side won't change (since $E[Z]=\mu$ didn't change). This proves the claim.


Hardness amplification of PRFs by increasing key length I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF constructions which take into account key length for increasing hardness? Alternatively, are there any constructions which transform a $(t, \epsilon)$ PRF of key length $k$ to something like $(t^2, \epsilon)$ PRF of key length $2k$ or $k^2$?

It's important to be clear about what is the purpose of the GGM construction.  The GGM construction is designed to build a PRG out of a PRF: i.e., to construct one primitive, given an instance of a different primitive.  It's not designed to increase the security of the underlying primitive.

This is a general theme in a lot of provable cryptography: you have to start with a primitive that is secure; then you can build other things out of it, but the primitive you start with has to be secure, or else you can't do anything.  The standard constructions don't increase the security of the basic primitive; instead, that's the job of the person who designed the basic primitive.

Hardness amplification is a different task.  Hardness amplification means: given a primitive of type T, build another primitive type T that is more secure (in some sense).  In general, provably-secure hardness amplification is very difficult to achieve.  Why?  Well, we don't know how to build any crypto algorithm that is provably secure; all we know is conditional results (if you give me a secure one-way function, then I can build other things that are secure).

There are some examples of techniques that given a $(t,\epsilon)$-scheme construct a new scheme that is something like $(t,\epsilon^2)$-secure, but that's different.  (If you're interested in that, spend some quality time with Google and Google Scholar looking at results on "hardness amplification"; see, e.g., Yao's XOR lemma.)  I don't know of any techniques that given a $(t,\epsilon)$-scheme construct a $(t^2,\epsilon)$-scheme.


A function computable using a circuit of size $10s$ but not of size $s$ I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help.

  Prove that for every function $s(n)$ such that $n \le s(n) \le \frac{2^n}{100n}$ there exists a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$
  such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$.

One possible approach is as follows. A counting argument shows that there are function on $n$ bits that require circuits of size $\Omega(2^n/n)$, and on the other hand a non-trivial construction that you probably saw in class shows that every function on $n$ bits can be computed using a circuit of size $O(2^n/n)$. This takes care of the case $s(n) = 2^n/{100n}$.

For general values of $s(n)$, you can use functions depending on $m \leq n$ variables, making sure that the resulting lower bound $\Omega(2^m/m)$ and upper bound $O(2^m/m)$ fit snugly around $s(n)$.


On complexity of the sieve, start crossing at the square of $p$ This question is about a common optimization in the basic sieve of Erathostenes.

If we look at this paper (page 3, footnotes), the author says:

  If we start crossing off at $p^2$ rather than $p$, the number of composites
  we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our
  sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor

Similarly, I have seen the same conclusion in other places, so according to them we have that the total cost counting crossings is about (ignoring the $\sqrt n$ optimization):

$\sum_{p\leq n}(\frac{n}{p}-p+1)$

Where $p$ is prime.

But if we look at this algorithm (in pseudocode) implementing this same optimization:

//omitting sieve[2..n] initialization
for p:=2 to n
   if (sieve[p] is prime)
      for k:=p^2 to floor(n/p)
         sieve[k*p] := not prime     //cross multiples of p

I would say the total cost is:

$\sum_{p\leq n}(\frac{n}{p}-p^2+1)$

because the cost of the inner loop is

$\sum_{k=p^2}^{\frac{n}{p}}=\frac{n}{p}-p^2+1$

Am I wrong?

Your algorithm is wrong. The starting point should be $p$ rather than $p^2$, since in the body of the loop $k$ gets multiplied by $p$.


looking for a strongly NP Complete related problem I'm looking for a problem that is NP-Complete (even) if the number of input values is at most a polylog of the input size. So some or each value in the input should be so large that the number of values is "negligable".

One way to do this is to say that there is only one input value that should be split and represents the input to another NPC problem. But I consider this a bypass and I'm looking for a more conventional problem.

According to Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? and its answers, I cannot simply take a strongly NP-Complete problem and represent its input as unary.

Wikipedia's list of NP-complete problems lists the following problem:

Input: positive integers $A,B,C$
Question: do there exist positive integers $x,y$ such that $Ax^2+By-C=0$?

This is a NP-complete problem that has only 3 input values (which is certainly at most poly-log of the input size).

You can find another example of a NP-complete problem with only 3 input values at A Query regarding Quadratic Residuocity Problem.


Are there any paradigms that describe how to save program state checkpoints that can be restored later? I was wondering if there were any paradigms that describe how to save "state checkpoints" in a program so that a user may go back and reopen a program to the given state.

In my situation I see that there are many ways to do it each with their own drawbacks. I wanted to know if there is a way that has proved to have the best performance over most all cases of the problem?

What I think would be the most popular system is one that saves state changes, then when a user wishes to return to a previous state it walks the changes backwards until it reaches a specified time stamp reversing the changes along the way.

Or is this problem just application specific.

In general you cannot do this. The state of your application might depend on the state of external systems, and you won't be able to go back. For example you can't go back to a previous saved value of time if your systems requires that your clock should be within a small value compared to other machines in the network.

So its not always possible, and when it is, it is definitely application specific.


Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$ I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow.

I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ using a truth table as it's easy to see.

However, I can't seem to turn $A \vee (\neg A \wedge B)$ into $A \vee B$ using steps such as distributive / absorption etc.

Can someone talk me through the steps that you would take to simplify this?

Note that

$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;

you can "multiply out". Add in

$\qquad (A \lor \lnot A) \land B \equiv B$

and you are done.


Is summing over all possible $k$-combinations NP-hard? Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute

$$
\sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c \in C} a_c
$$

Naively this requires $O(k\binom{n}{k})$ operations.

This is different from from computing the permanent where there are permutations.

Is this problem known to be NP-hard when $n=2k$ or other conditions such as $n=\Theta(k^2)$?

You can compute the coefficient of $x^k$ in
$$ \prod_{i=1}^n (1+xa_i). $$
Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,\ell)$ be the sum of $\ell$-combinations of $a_1,\ldots,a_m$. We have
$$ b(m,\ell) = b(m-1,\ell) + a_m b(m-1,\ell-1), $$
where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,\ell) = 0$ for $\ell \neq 0$. What you want is $b(n,k)$.

In both cases, there is an optimization that only keeps track of $\ell$-combinations for $\ell \leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.


How to prove that insert complexity in binary search tree is minimum O(log n)? Is it connected to BST search O(log n) or height log n?
How to prove that insert will give give you correct BST in minimum O(log n) time?

The minimal height of a BST is always log n, you can easily prove it by induction. Then if you want to insert a new node you need to find the corresponding leaf where to insert it, which takes at least log n operations (comparisons) in the worst case, more if the tree is not balanced (larger height). Hence you obtain an insert cost of O(log n). We always focus on the worst case scenario to compute the O-complexity.


How does literals in compiled languages differ from literals in interpreted languages? A literal is a piece of data which gets its value at compile time.

Means: Becomes set at compile time and afterward the value is fixed incorporated into the machine code as a code consisting out of 0s and 1s.

What are literals in interpreted languages like for example JavaScript?

As far as I know the code within JavaScript functions aren't touched by the interpreter until it becomes executed.

Can one say that literals exists in these languages? regarding my definition of a literal (first paragraph).

A literal is a piece of data which gets its value at compile time.

I don't think that's a good definition of literals. A literal is a source-code token that represents a fixed value of some type. For example, in almost all programming languages, 23 is a literal representing the integer twenty-three. These aren't pieces of data that get their value at compile-time: rather, they are representations of the values themselves.  For example if, in Java, you write

static final int magic = 23;

then magic is a constant (a variable whose value cannot be changed) that is set at compile-time to have the value twenty-three, which is the meaning of the literal 23.

This is no different between compiled and interpreted languages.


Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$? I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples.

The question equation: $f(n) = 6n^3 + n^2\log n$

The exact line written for the answer is: $f(n) \leq 6n^3 + n^2 \centerdot n \text{, for all }n \geq 1, \text{since} \log n \leq n$

First of all, I don't really see why the logarithm was removed or why it actually matters when the dominant piece is the $6n^3$. I also don't get why it's $n \geq 1$ instead of $n \geq 6$ (unless it's a continuation of the first one.

Been staring at it for about 15 minutes and still not getting how it comes down to $n \geq 1$. Would anybody be kind enough to give me a hint as to what's wrong?

First of all, it is not a "question equation" but the definition of $f$.

The task at hand is to show that $f(n) \in O(n^3)$. By the definition of $O(n^3)$ this means that we need to find $n_0$ and $C$ such that $f(n) \leq C n^3$ for all $n \geq n_0$. There may be many $n_0$ and $C$ that work, we just need to find one.

I pull out of my hat $n_0$ and $C$ that work (because I am a professional mathematician), namely $n_0 = 1$ and $C = 7$. Now we have to verify: for all $n \geq 1$ we have $f(n) \leq 7
n^3$.

Because $\log n \leq n$ whenever $n \geq 1$ (draw a graph of $y = \log x$ and $y = x$, and stare at it for a while) we may replace $\log n$ in the definition of $f$ with $n$, and we will get something bigger. So we have for all $n \geq 1$:
$$f(n) = 6 n^3 + n^2 \log n \leq 6 n^3 + n^2 \cdot n = 6 n^3 + n^3 = 7 n^3$$
We have established that $f(n) \leq 7 n^3$ for all $n \geq 1$, as required. We get an A on the midterm.

The question remains how I pulled out of my hat $n_0 = 1$ and $C = 7$, since this is what you will have to do on your mid-term. You start with $f(n)$ and "massage" it into something that is larger and has the form $C n^3$. On the way you observe that your massaging only works for $n$ large enough, and that gives you $n_0$.

Let us have another example: show that $g(n) = 23 n^2 + 17 + \log n$ is in $O(n^2)$. The massaging process goes as follows: turn every term which grows more slowly than $n^2$ into something of the form $C n^2$, and think about which $C$ to use and for which $n$ it is going to work. We have three terms to worry about, and notice how each has several possible ways of massaging:

the term $23 n^2$ is already in the correct form.
the term $17$, we give three possibilities just for fun:

$17 \leq 17 n^2$ for $n \geq 1$
$17 \leq 17 n^2$ for $n \geq 100$
$17 \leq n^2$ for $n \geq 5$

the term $\log n$:

$\log n \leq 42 n^2$ for all $n \geq 3$

I have purposely chosen weird and suboptmal values for $C$ and $n_0$ for each of the terms to show you that there is a lot of choice. For example, it would have been more "optimal" to say that $\log n \leq n^2$ for $n \geq 1$. For the term $17$ I gave three possible massages, let us work with the second one. We compose our observations together by replacing each term with its upper bound:
$$g(n) = 23n^2 + 17 + \log n \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2.$$
I was too lazy to compute $23 + 17 + 42$ so I just approximated it with something larger, namely $1000$. Thus our $C = 1000$. We still have to figure out $n_0$. As far as the term $23 n^2$ is concerned any $n_0$ is ok. The term 17 wants $n_0 = 100$ and the term $\log n$ wants $n_0 = 3$. So we may take any $n_0$ that is larger than or equal 100 and 3, for example let us take $n_0 = 4127$.

We have now successfull pulled $C$ and $n_0$ from a hat. It is time to write the official solution so that we appear to be very smart, and to confuse students who start studying only two days before the midterm:

  The function $g(n) = 23n^2 + 17 + \log n$ is in $O(n^2)$ because for every $n \geq 4127$ we obviously have $g(n) \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2$. We used here the easy observations that $17 \leq 17 n^2$ and $\log n \leq 42 n^2$ for every $n \geq 4127$.


Grammer Class/Production Rules of Programming Languages I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions:

Doesn't variable scoping require a context-sensitive grammer?  Particularly, I'm thinking of the following valid C code:

int main(){
    int count=0;
    count++;
    return count;
}

As opposed to the following invalid C code:

int main(){
    count++;
    int count=0;
    return count;
}

There could also be some other stuff involving namespaces and classes for C++, or the '.' operator for C structs, for example.  I get the impression that, as a result, C (and various descendents) does (do) have context-sensitive aspects (though this may only be partial context-sensitivity).  Thus question 1:

Is it correct to say that C and some derivative languages, as well as some other languages, can only be generated by grammars with a minimum of context-sensitivity?

Secondly is there a relationship between language class and grammar class?

Particularly, I'm thinking of the language BrainF*** when I ask, since its syntax is clearly generated by a context-free grammar, yet its implementation is turing complete (assuming an implementation with an infinite tape).  Does this mean that there are languages that have regular grammars, yet are turing complete?

The issue is where you want to draw the line for what is considered "syntax". Sure, variable scoping typically requires context-sensitivity, but that doesn't need to be handled by the parser. The parser could just parse the syntax allowing out-of-scope variables, and a follow-on pass could check for out-of-scope errors. In practice, many real implementations of parser for real languages are context-sensitive, but this is handled in an ad-hoc manner by sharing state between productions and allowing "actions" to be attached to context-free productions. In particular, few (no?) languages use general-purpose context-sensitive parsing approaches. In fact, few uses general-purpose context-free parsing approaches. Instead, tooling for potentially limited classes of context-free grammars is used and, as mentioned, ad-hoc "semantic actions" lead to the parser actually being context-sensitive but this done in a way that is not captured by the context-free grammars that putatively describe the language.

In other words, a context-free grammar for a language often describes a larger language than what is actually accepted. But rejecting a program after parsing it for out-of-scope variables, say, is no different than rejecting it for having a type error. Type checking is almost never done while parsing. So what checks are done while parsing or later is usually done as a matter of convenience, and many aren't nicely described by a grammar.

The grammar complexity of the syntax has little to do with the computational complexity.  For example, every bit string is a syntactically (and semantically!) valid Jot program, and Jot is Turing-complete.


Problem in Papadimitriou's "Computational Complexity" seems odd I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition.

On page 66, we have:
3.4.1. Problem: For each of the following problems involving Turing machines determine whether or not it is recursive:

(a) Given a Turing machine $M$, does it halt on the empty string?
(b) Given a Turing machine $M$, is there a string for which is halts?
(c) Given a Turing machine $M$, does it ever write symbol $\sigma$?
(d) Given a Turing machine $M$, does it ever write a symbol different from the symbol currently scanned?
(e) Given a Turing machine $M$, is $L(M)$ empty? ($L(M)$ denotes here the language accepted by the Turing machine, not decided by it.)
(f) Given a Turing machine $M$, is $L(M)$ finite?
(g) Given two Turing machines $M$ and $M'$, is $L(M)=L(M')$?
Which of the non-recursive languages above are recursively enumerable?

Now, what puzzles me about this problem is that very little of the information it provides needs to be used in order to solve it. It is easy to see that all seven items describe non-trivial properties of Turing machines (that is, they are true for some Turing machines but not others) and, according to Rice's Theorem described on page 62, this means they cannot be recursive. There is barely any need to think at all about the properties described.

It seems a little odd that the author would go through the trouble of describing several different languages in some detail, when those details barely matter. It makes me wonder if my reasoning about Rice's Theorem is correct.

So my question is: is my reasoning correct that, according to Rice's Theorem, none of these described languages are recursive?

Incidentally, I think the last question in the problem is more interesting and does require more thinking about the individual languages. However, it sounds like a very secondary question, so it still makes me wonder about my answer to the main question.

Rice's theorem is about non-trivial properties of partial functions. It states that if $P$ is a non-trivial property of partial functions, then no algorithm can decide, given the description of a Turing machine $M$, whether $L(M) \in P$.

Rice's theorem doesn't say anything about the operation of Turing machines. A property like "$M$ ever writes $\sigma$" is not a property of $L(M)$, and so Rice's theorem doesn't apply to it.


Variable rule in dependent type theory This is the = Type variable rule that I'm seeing through out the my course and unable to grasp it completely.

$$\dfrac{\phi \vdash \Gamma[\mathrm{ctx}] \qquad \Gamma(x) = \tau}
        {\phi; \Gamma \vdash x : \tau}
        \textsf{(ty-var)}$$

The first thing in antecedent looks like it's stating that $\Gamma$ is well-formed under the context $\phi$, is that right? What does the second thing in antecedent mean? I have a feeling of this but I am unable to get this simple rule.

Essentially, $\Gamma$ is a store that maps variables to types.

This rule says that we can deduce that a variable has a type in a context if that type is stored for our variable in the context.

The rule is deliberately simple, and is a base case for the inductive process that is type derivation.

In short, to check the type of a variable, just look it up in the environment.


Difference between $\beta$-contracts and $\beta$-reduces in Hindley I brought the book Lambda-Calculus and Combinators: An Introduction by J. Roger Hindley and the author explains what is $\beta$-reduction.

Now there is a difference between $\beta$-contracts and $\beta$-reduces:
$$
\begin{align*}
P &\rhd_{1\beta} P^\prime\\
P &\rhd_{\beta} P^\prime
\end{align*}
$$

Could someone please explain me what is the difference?

Notation and terminology varies a little between authors, so you should check the definitions used by the author. When you ask such questions, you should quote the definitions.

The expression “$P$ $\beta$-contracts to $P'$” means that $P$ contains a subterm which is an application and $P'$ is the result of substituting the argument into the abstraction body. That is, there exist $C$, $M$, $N$ and $x$ such that $P = C[(\lambda x.M) \, N]$ and $P' = C[[N/x] M]$ where $[N/x] M$ means the term obtained by substituting $N$ for $x$ in $M$ and $C[\cdot]$ is a term with a hole. Thus

All terms of the form $(\lambda x.M) \, N \triangleright_{1,\beta} [N/x] M$ are $\beta$-contractions at the top of the term.
If $P \triangleright_{1,\beta} P'$ then $M \, P \triangleright_{1,\beta} M \, P'$ and $P \, M \triangleright_{1,\beta} P' \, M$ and $\lambda x. P \triangleright_{1,\beta} \lambda x. P'$. The contraction is sometimes said to happen “in a context”.

The expression “$P$ $\beta$-reduces to $P'$” means that there is a chain of $\beta$-contractions that goes from $P$ to $P'$. For example:

For any term, $P \triangleright_{\beta} P$ (a term reduces to itself in zero steps).
If $P \triangleright_{1,\beta} P'$ then $P \triangleright_{\beta} P'$: a contraction is a reduction in one step.
If $P \triangleright_{1,\beta} P'$ and $P \triangleright_{1,\beta} P'$ then $P' \triangleright_{\beta} P''$: a contraction in two steps.
etc.

In a nutshell, a beta contraction is one step, a beta reduction is any number of steps. Note that some authors use different terminology and might call one step a beta reduction and many steps “a chain of beta reductions” or “a $\beta^*$ reduction”.


Does $n\log n = O(n \log n + n)$ hold? Does $n\log n = O(n \log n + n)$ hold?

I don't think it does trivially because I think as $n$ grows larger, $n\log n$ will converge to one value, and as the $+ n$ grows, $n\log n + n$. But I am uneasy about my initial thoughts about this. For example, mergesorting a list and then iterating through each element to compare for the smallest difference would result in a running time of $O(n\log n+n)$, yet mergesort is $O(n\log n)$.

I'm not sure what do you mean that "$n \log n$ will converge to one value" because in fact $\log n$ diverges to infinity (so is $n \log n$).

Recall that $f(n) \in O(g(n))$ iff exists constants $c, N$ so that $f(n) \leq c \, g(n)$ for every $n \geq N$ (intuitively, $f(n)$ could be bound above by a constant multiple of $g(n)$ as $n$ grows large enough).

$n \log n \in O(n \log n + n)$ is then obviously true since $n \log n + n > n \log n$.

It is worth noting that the other side $n \log n + n \in O(n \log n)$ also holds because $n \leq n \log n$ as $n \geq \mathrm{e}$, so choosing $(c, N) = (2, \mathrm{e})$ proves this.


How can I sum pixel values over a rotated rectangle? I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution is not fast enough.

The region can be rotated arbitrarily so that I can't use an integral image; integral images only work for axis-aligned rectangles.

Does someone know a generalization of the integral images for that problem or has a different idea?

Update:

The rectangles have different rotations, so that I can't rotate the rect.
The rectangles have a size similar to the one of the full image (each ~20%)

One simple technique that's probably not optimal, but is better than naively enumerating all pixels in the rotated rectangle, is to use "integral columns" (thanks to Yves Daoust for the name):

Preprocessing: Let $I[\cdot,\cdot]$ be the image.  For each $x$ value, build a 1D integral image for $I[x,\cdot]$.  In other words, we build a table $S[\cdot,\cdot]$ where $S[x,y] = S[x,0] + S[x,1] + \dots + S[x,y]$.  This can be done in linear time.

Answering a query: Given a rotated rectangle $R$, we find the range of $x$-values of pixels within $R$ (i.e., the leftmost part of $R$ and rightmost part of $R$).  This can be done in $O(1)$ time.  Next, for each $x$ in that range, we find the range $[y_\ell,y_u]$ of $y$-values such that $(x,y)$ is in $R$ for each $y_\ell \le y \le y_u$.  We sum the pixel values of those by computing $S[x,y_u] - S[x,y_{\ell}-1]$.  This takes $O(1)$ time per $x$-value, so the total running time to sum the pixels in a rectangle is proportional to the width of $R$ (in contrast, the naive method's running time is proportional to the area of $R$).

As a trivial optimization, you can precompute sum tables for both $x$ and $y$; for each $R$, you can check which is smaller, the width or height of $R$, and then decide whether to enumerate $x$-values or $y$-values.


Computer Music Composition I've been looking into computer assisted music composition lately for my school project. While searching for literature I came across GenJam, an interactive jazz improvisation software which uses genetic algorithms to produce musical phrases.

I was wondering If anyone has done some work on computer generated music and could suggest term papers, books or other reading material I should look into.

see also eg

Wikipedia evolutionary music
A genetic algorithm for producing music Matic
A fitness function for computer-generated music using genetic algorithms Alfonseca
Computer Models of Musical Creativity Cope / "asks whether computer programs can effectively model creativity -- and whether computer programs themselves can create"
Virtual Music: Computer Synthesis of Musical Style Cope / "the author and a distinguished group of experts discuss many of the issues surrounding the program, including artificial intelligence, music cognition, and aesthetics."
Machine Musicianship "This book explores the technology of implementing musical processes such as segmentation, pattern processing, and interactive improvisation in computer programs."


Example Context free grammar Is there a nice way to give context free grammar for
$$\{a^nb^ma^kb^l:n+m=k+l\}?$$

From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack if we see a, pop + from stack if we see b and accept if you have empty stack.

Here is a simple grammar:
$$
\begin{align*}
& S \to aSb|U|V \\
& U \to aUa|T \\
& V \to bVb|T \\
& T \to bTa|\epsilon
\end{align*}
$$


PDA recognising all strings with a $1$ in the second half My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says:

  Let $\Sigma = \{0,1\}$ and $B$ is the collection of all strings that contain at least one $1$ in the second half. To state it more precisely: $B=\{uv\mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast} 1 \Sigma^{\ast}, |u|\geq|v|\}$. Give a PDA that recognizes $B$. Give a diagram to describe your PDA.

My question is why do I need a PDA or really a stack for this because all I am looking at is the second half which I can just epsilon to the second half and then when I read a $1$, go to the accept state. For example if $u=1001010101$ and $v=000011$, wouldnt I just loop around for a bit for u and then epsilon over to say I am now looking at $v$. Then when I read the first $1$, I just accept. I wouldnt need to use the stack at all would I?
I'm not sure if I understand it correctly or not and would appreciate any help.

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

Footnotes:

As Babou points out in his answer, you don't need a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.


Is there a method for automatic runtime analysis of algorithms? I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)?

I googled "Automatic algorithm analysis" which gave me this but it is too mathy. I just want a simple example in psuedocode that I can understand. Might be too specific, but I thought it was worth a shot.

No algorithm can decide whether a given algorithm ever halts or not, so in particular no algorithm can tightly analyze the complexity of a given algorithm.


How might I express a sequence of operations in formal terms? I want to be able to represent a set of operations in sequential order such that they will represent what is traditionally called a "function" (which is not always the mathematical definition of a "function"). However, I'm trying to define more primitive terms:

object - Anything that can be manipulated throughout the course of a program; that is, they can be read and set.

place - A container that can hold value. (e.g. variables)
value - A value. (e.g. 2+2 is a value but not a variable).

procedure - A sequence of operations.

I want to be able to define procedure in more definite terms. Note that I will be starting without the definitions of operations, as I want to be able to define basic operations as procedures.

I know that I may want to introduce the sense of "time" and "space" for programs, time being necessary due to the definition of "sequence" that I put forth. Is there a better way to define it? Is there already work out there that explores this?

How would you formally define a procedure or operation at its most basic level?

Take a look at Gurevich's abstract state machines. See also the abstract state machine homepage. A key paper is Gurevich's Sequential Abstract State Machines Capture Sequential Algorithms.


$O(n+nm) = O(nm) = O(m+nm)$? I am thinking about the worst-case space complexity of an algorithm.

Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true?

$O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)O(n) = O(nm)$

If that were true then $O(n+nm) = O(m+nm)$

As mentioned in the question, obviously $O(nm) \subseteq O(n + nm)$ as $n,m \rightarrow  \infty $.

The reverse is also true when $n, m$ grow ever larger:

For all $n,m \geq 1  : m +nm \leq nm+nm = 2nm$ and so:
$O(m+nm)  \subseteq O(nm+nm) = O(2nm) = O(nm)$ as $n,m \rightarrow \infty$.

$O(2nm) = O(nm)$ as $n,m \rightarrow \infty$ is a property of big-O that follows directly from the definition.

With respect to the penultimate line in the question (the long sequence of equalities), there is some unusual notation. To make sense there, the product of two sets must be an element-wise product such as $O(n) \cdot O(m) =\{fg ∣ f∈O(n), g∈O(m)\}$. The ‘$+$’ sign before the first equal sign probably means the Minkowski sum A+B={a+b ∣ a∈A and b∈B} instead of A∪B, but in both cases the first equality would hold.


Graph cycles on 40 vertices I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language.

The language specifies that a graph is only part of this language if it has a cycle on 40 vertices. (The cycle doesn't need to be induced.)

Now, I'm considering the fact that there could be a huge number of vertices within this graph. For example, we could have 100000 vertices, and there could be a cycle of 300, but this would not be in the language. If this graph had a cycle of 300 AND a cycle of 40, then it is.

I'm thinking that depth-first search would be the proper way to approach this question. Then, using this, we'd possibly have check every vertex within the graph?

This is just a guess at the moment though, and help/thoughts would be greatly appreciated.

When you say "cycle", do you mean a simple cycle of length 40 (so no vertex is allowed to be repeated), or would you allow an arbitrary walk of length 40 that ends where it starts (i.e., vertices are allowed to be repeated in the cycle)?  The answer to your question depends on what you mean by cycle, so I'll answer both cases.

Simple cycles

The problem of testing whether a graph contains a simple cycle of length $k$ is hard.

No efficient algorithm is known; all known algorithms have running time that is exponential in $k$; and if $k$ is part of the input, the problem is NP-hard.  See here and here.  In your case, $k=40$.  The best algorithms that I know of have either a $O(k!)$ factor or a $O(n^{k/2})$ factor in the running time, so they will be totally infeasible: $O(n^{20})$ is not feasible for any non-trivial value of $n$, and $k! \approx 2^{159} \approx 10^{48}$, which is also infeasibly large.  (See Louis's answer for pointers to an algorithm of the former type.)

If you allow repeated vertices

If you allow the cycle to contain repeated vertices, then the problem becomes much easier, and there is a polynomial-time solution.

Hint: Consider the adjacency matrix of the graph, $M$.  Look at $M^2$.  Can you find any relationship between the $i,j$ entry of $M^2$ and paths of some length?  Can you generalize?

(Since this looks like a natural exercise problem, I am just giving you a hint, and letting you take it from here.)


Distance function such that we visit every "color region" once Consider the following image:

Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right.

We must go through each color exactly once, and once we go outside a color, we can't go back to the same one.

Here is a example of what I think is a optimal path:

As per dikisjtra algorithm, we update the distance at once node if d[current] + weight(this_node, next_node) < d[next_node]. Usually these weights are given to us, but in this case, we must create a weight function such that given any two pixels (x1,y1),(x2,y2), our path follows something like what I have drawn in white.

You can assume all the colors are indeed different, even though they might look similar because of shades.

I am thinking of the following conditions to check in the weight condition:

going from old color -> same color -> maybe a weight of 5

going from old color -> new color -> a low weight of 1

What are the cases of the weights I can assign so dijikistra finds the path shown in white?

Summary of your problem: You have a graph and a particular path through the graph, and you want to assign weights to the edges so that running Dijkstra's algorithm on that graph will give you that path.

Solution to your problem: assign a weight of 1 to each edge in the path, and a weight of $\infty$ (or some very large number) to each edge not in the path.  (It suffices to choose a weight that is larger than the number of vertices in the graph.)  You can easily verify that the shortest path only uses edges of weight 1 (any path that includes any other edge will have a total distance that is larger than that of the desired path).


Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc? Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing machines with an extra black box device that can be queried and give an output that normally would be uncomputable. For example, a halting oracle would tell the machine a bit encoding whether an input program would ever terminate. Such "hypercomputation" machines can calculate various forms of uncomputable outputs.

My questions are:

Is hypercomputation compatible with our laws of physics?
What about other incomputable things like Russell's set (things which its result is not computable because it does not exist)? Or what about other uncomputable/illogical/impossible/non-existent/inconsistent things? Are there hypercomputational systems that could encode/compute them?

Thank you for your help

It is a little hard to say for sure since since one has not found a final Theory Of Everything in physics. Mostly it seems that hypercomputation is physically impossible.

On the other hand, an amusing development is the work of Nemeti et al. on using time travel (closed timelike curves) to do hypercomputation.

The so-called Malament-Hogarth spacetimes are known for exactly this --- that one can compute forever in them and thus solve the halting problem.

Hogarth worked on this in the 90s and Welch showed that even a larger class of problems than those solvable using the halting problem (all hyperarithmetic problems) can be solved in MH-spacetimes. This does not include all oracles though, as there are uncountably many oracles and only countably many hyperarithmetic ones.

(As for things that are logically impossible, like Russell's set, they are also physically impossible since "physics obeys logic".)


Why have quantum circuits won out over quantum Turing machines? As I understand it, quantum circuits as a model are equivalent to quantum Turing machines, or at least they can be simulated on each other.

So my question is, why have quantum circuits become the chosen implementation rather than quantum Turing machines, such as in the IBM Q?

Is it related to entanglement and reversible gates? I wondered if quantum Turing machines could not take full advantage of entanglement.

I've popped up here 7 months too late but in response to the question here's my short-ish answer: Quantum Turing machines are physically unreasonable. Prof. Peter Shor originally wrote his factoring algorithm using a Turing machine and so from a theoretical perspective they work just fine. However, it requires the tape heads to be entangled, which is why you couldn't realistically make it work. The Circuit model (which has been around longer than Turing machines) also has it's own problems which is why Turing needed his machine. One main reason (there are others) is that circuits are designed for a given input size whereas Turing machines are independent of input size. Therefore the circuit model is better suited to quantum computation as it is a more realistic reflection of the devices we could build.


Why is the language $NP-hard$? Let's denote $IS(G)$ to be the size of the maximal independent set in $G$.
Consider the following language:
$$A = \left \{  G\ |\ IS(G)\ge \frac{1}{5}n \right \}$$

I know that $gap-IS [1/8 + \varepsilon , 1/4-\varepsilon]$ is $NP$-hard.

How can I infer that $A$ is $NP$-hard by utilizing the gap problem?

You reduce $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ (for any $\epsilon < 1/20$) to $A$. The reduction is the identity function. Let's see why it works:

If a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has an independent set of size at least $(1/4-\epsilon)n \geq n/5$.
If a graph $G$ is a NO instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has no independent set of size $(1/8+\epsilon)n < n/5$.

Hence a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ if and only if it is a YES instance of $A$.


Hanoi tower with forbidden direct move from source to destination I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you instead of that should first move disk from source to middle and then from middle to destination) and other rules as normal problem?

I didn't find any article about it.

Notation
Let's denote least number of moves needed to move $n$ disks from column $i$ to column $j$ with $T_{ij}$. Let $A$ be the source and $C$ be the destination column.

Recurrence relations
We can say the followings about each $T$:
\begin{equation}
T_{AC}(n)=T_{AC}(n-1)+1+T_{CA}(n)+1+T_{AC}(n-1)
\end{equation}
To move $n$ disks from source to destination, we first have to move the top $n-1$ disks to column $C$ and then move the last one to Column $B$, Then return the $n-1$ disks to $A$ so as to free up destination column, then move the biggest disk to $C$ and once again move the $n-1$ disks to $C$. It's easy to see that this is the optimal set of operations. This equation can be written as:
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+2+T_{CA}(n-1)
\end{equation}

For other $T$s we have a different situation:
\begin{equation}
T_{CA}(n)=T_{CB}(n-1)+1+T_{BA}(n-1)\\
T_{CB}(n)=T_{CA}(n-1)+1+T_{AB}(n-1)\\
T_{BA}(n)=T_{BC}(n-1)+1+T_{CA}(n-1)\\
T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1)\\
T_{BC}(n)=T_{BA}(n-1)+1+T_{AC}(n-1)
\end{equation}

Solving the system of recurrence relations
Let's start with $T_{AB}$ or $T_{BC}$ . We already know:
\begin{equation}
T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1)
\end{equation}
We try to rewrite $T_{CB}$'s equation by replacing $T_{AB}$ from the above equation.
\begin{align}
T_{CB}(n)&=T_{CA}(n-1)+1+(T_{AC}(n-2)+1+T_{CB}(n-2))\\
&=T_{CA}(n-1)+T_{AC}(n-2)+T_{CB}(n-2)+2
\end{align}
\begin{equation}
T_{CB}(n)-T_{CB}(n-2)=T_{CA}(n-1)+T_{AC}(n-2)+2
\end{equation}

By the same method we get:
\begin{equation}
T_{BA}(n)=T_{CA}(n-1)+T_{AC}(n-2)+T_{BA}(n-2)+2
\end{equation}

It can immediately be seen that $T_{BA}(n)=T_{CB}(n)$. Then we rewrite $T_{CA}$ as:
\begin{equation}
T_{CA}(n)=2T_{CB}(n-1)+1 \Rightarrow
\end{equation}
\begin{align}
T_{CA}(n)-T_{CA}(n-2)&=2(T_{CB}(n-1)-T_{CB}(n-3))\\
&=2(T_{CA}(n-2)+T_{AC}(n-3)+2)\\
&=2T_{CA}(n-2)+2T_{AC}(n-3)+4
\end{align}

Now let's go back to the main relation, to $T_{AC}$:
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+2+T_{AC}(n-1) \Rightarrow\\
\end{equation}
\begin{align}
&T_{AC}(n)-3T_{AC}(n-2)\\
=&2(T_{AC}(n-1)-3T_{AC}(n-3))+(T_{CA}(n-1)-3T_{CA}(n-3))=\\
=&2(T_{AC}(n-1)-3T_{AC}(n-3))+(2T_{AC}(n-4)+4)\\
=&2T_{AC}(n-1)-6T_{AC}(n-3)+2T_{AC}(n-4)+4 \Rightarrow
\end{align}
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+3T_{AC}(n-2)-6T_{AC}(n-3)+2T_{AC}(n-4)+4
\end{equation}

There! We have reduced the system of recurrence relations to a single relation, involving only the target series. Ok, the rest is easy from here on. I leave it as an exercise to the reader! $\ddot\smile$


Minimum cost to match $n$ people with $m$ shops We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost of one matching is sum of all matchings, and for each matching its cost is calculated as Manhattan distance between those two points. It will always hold that $m > n$.

For me, this looks a lot like the bipartite matching problem, however I'm not sure what to do with the costs of the matchings. I started thinking about algorithms that starts with one trivial matching and update it if making some other matching decreases the cost. However, I'm not sure if this will work. What is the correct way to solve this problem. I don't have much experience with matching algorithms, so I'm not sure how to approach this problem.

Your problem is an instance of minimum bipartite perfect matching. This is known as the assignment problem, and there are known efficient algorithms.

As a first step, you should compute the weights of all edges, using the formula your are given (L1 distance between the point corresponding to the person and the point corresponding to the shop).


Can any non-halting Turing Machines with blank tape input print out any irrational number? The fact that square root of 2, pi etc are computable numbers only means they can be approximated to arbitrary nth decimal, so these TM that approximate them do not count since they halt after printing out the nth digits. I would appreciate a definitive answer and reasoning.
If the answer is NO, which I suspect, is the following statement equivalent?
Any TM with blank tape input can only print rational numbers, assuming its alphabets are coded in integers.

I choose to represent numbers in base $\pi$. My machine prints $10$ and terminates, that's exactly $\pi$.

A Turing machine performs meaningless operations on meaningless objects, you provide the semantics, you find meaning in the computation. The answer to your question is a direct consequence of how you decide to represent numbers with the finite alphabet of the machine. It is certainly true that not all real numbers can be exactly computed under an unified semantics by Turing machines: there are uncountably many real numbers but countably many Turing machines.

But you might be able to represent some of them. For instance, with enough symbols to write integers, fractions, square roots and the imaginary unit, you can represent exactly the segments constructible with straightedge and compass, each of them in a finite amount of space.


Algorithm to find best combination of datasources (Quality and price) I have some sources of data, and each one of this sources have a cost per request. I know wich data attributes each one of these sources have, and what are the best sources for each attribute.

Given a list of attributes, I have to decide the best group of datasources to consume, thinking about Quality of the data first, and secondly about costs.

Its common to make requests to multiple datasources, getting just some attributes from each one, but i will give a simple example below:

Say I have something like this:

DATASOURCE A costs $0.50 returns NAME (good), BIRTHDAY (good), ADDRESS (good)

DATASOURCE B costs $1 and returns NAME (good), MONTHLY INCOME (good), ADDRESS (medium)

DATASOURCE C costs $0.70 returns MONTHLY INCOME (good), NAME (medium)

If i want NAME, it would be better to consume DATASOURCE A (quality and cost of NAME).

If i want MONTHLY INCOME, it would be better to consume DATASOURCE C. (quality and cost of MONTHLY INCOME)

If i want NAME and MONTHLY INCOME, now it would be better to consume DATASOURCE B (because NAME and MONTHLY INCOME are GOOD).

But if i want NAME, MONTHLY INCOME and ADDRESS, I need to consume DATASOURCE A (for NAME and ADDRESS) but will consume DATASOURCE B too for MONTHLY INCOME.

Im trying to make some algorithm that makes sense to do it, but its getting very messy hehe. I would love any help with the logic. Maybe in javascript, java, c# or anything else I could read and have good idea about the best way to solve this.

Any help will be apreciated.

edit

some things to note:

I will have only 3 types of Quality here, and always prefer the best quality, so If i know any datasource has quality GOOD for the attribute, i can filter all other datasources with quality lower than Good for this attribute.

I know that in my case, we will have something like 5 or 10 datasources at all, and only 2 or 3 will have the same attribute.

What you're asking reminds me of some of the work I did a Linear Programming course and made me think of the Hungarian Algorithm. I hope this helps!


Recursive function problem This might seem very simple but it's been giving me lots of headaches.

For example if I run f(12345) the result is 5310135.

I understand why it would return 5310, the rest of 135 is what is giving me troubles. Sorry if the question sounds dumb, I am a newbie seeking for help:).

function f (integer n)
{
    print n%10;
    if (n!=0)
    {
        f(n/100);
        print n%10;
    }
}

You missed the second print instruction.

We can rephrase the algorithm as follows:

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    f(n/100)
    print n % 10
  }

Now we can do "recursion unrolling":

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      f(n/10000)
      print (n/100) % 10
    }
    print n % 10
  }

One more level:

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      if n/10000 equals 0 {
        print 0
      } else {
        print (n/10000) % 10
        f(n/1000000)
        print (n/10000) % 10
      }
      print (n/100) % 10
    }
    print n % 10
  }

Suppose for the moment that all of n, n/100, n/10000 differ from zero. The executed code is then

print n % 10
print (n/100) % 10
print (n/10000) % 10
f(n/1000000)
print (n/10000) % 10
print (n/100) % 10
print n % 10

Hopefully you can see the pattern.

The printed string is always an odd-length palindrome with a 0 in the middle, a property which you can prove by induction.


Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$ Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$.

Is $L$ decidable? Recognizable?

Given that membership in $L$ asserts something about $M$'s behavior on an infinite set of strings, it seems extremely unlikely to me that $L$ could be either. I have shown that co-$L$ is Turing-recognizable (I think): you can make an enumerator that tests each $M_1, M_2, \dots, $ for each $s_1, s_2, \dots$ and emits $M$ if it does not accept some $s$ in at most $200|x|$ steps.

Since co-$L$ is recognizable, either $L$ is not recognizable, or it is decidable. I can't imagine that $L$ is decidable. However, it definitely cannot be reduced to the halting problem, nor can Rice's theorem be applied to it (since the quality in question is the quality of halting in a particular number of steps, being able to decide it doesn't let us decide other arbitrary properties).

It seems to me that the best way to go will be to show that $L$ lets me recognize something that is unrecognizable, since the only problems it solves are ones which require me to run over infinite sets of strings. But I can't think of what this could be. I thought that maybe co-HALT would work, but I can't ever prove that a TM will never halt on some input.

I'm stuck. What direction should I go in?

The language is actually decidable, but the proof is quite involved, and uses crossing-sequence arguments. See this paper for details.

If you change $200|x|$ to a faster growing function, such as $|x|\log |x|$ (plus some constant), then the language becomes undecidable by standard reduction arguments.


Does the time complexity of a problem change with encoding of the problem? Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$.

Is there any theorem relating the time complexity of $L$ and $L'$?

How does the time complexity of a problem change with different encodings of the same problem?

Yes, the complexity depends on the encoding. The only thing you can be sure of is that if translating from encoding $L$ to encoding $L'$ or vice versa has the complexity $f$, and $D$ can be solved with complexity $g$, then $D'$ (same problem expressed with the encoding $L'$) can be solved with complexity $O(f+g)$ by going back and forth between encodings.

It isn't just a matter of length of the encoding. To give a simple example, let $L$ be positive integers represented in binary, and $L'$ be positive integers represented by their prime factorization. There is a polynomial bound in the size of one representation in terms of the other. Yet for a long time, it was not known whether primality testing can be solved in polynomial time in the binary representation; but in the factorization representation, it's trivially polynomial (probably $O(1)$ depending on the representation details).

Or consider the decision problem “is integer $n$ a member of set $S$”. If the set is represented by an unordered list of integers, this problem evidently requires at least linear time. But if the set is represented by a balanced search tree, lookup time is polylogarithmic in the size of the set.

In most concrete cases, there is an evident representation that everyone assumes, or more precisely there is a class of representations that are all equivalent up to a transformation that takes negligible time. But sometimes the representation is relevant, most frequently when analyzing data structures with more precision than polynomial time.


Proving a value is the result of the execution of an algorithm Assuming an algorithm $A$ known to both Alice and Bob.

Alice runs the algorithm and gets a result $R$.
How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random value (without having Bob run the algorithm himself)?

The goal is for Bob to perform less calculations checking Alice proof than running the algorithm itself. A probabilistic scheme for the proof is fine.

Please note that Alice does not have to prove correctness of $R$, just that she ran $A$ to obtain $R$.

The algorithm and its inputs can be modified to build the proof if necessary

Note: from the discussions below. I am happy with heuristics or techniques to obtain the proof. This is not a rhetorical question on algorithms.

Note2: @DavidRicherby suggests providing an execution trace, which seems perfectly reasonable. This leads to two sub-questions

How does Alice practically build a trace which proves to Bob with high probability that the trace is the one linked to the result ? (Bob should run less calculations checking the trace, than running the calculation himself)
Could such a mechanism be generic i.e. work with any algorithm ? For instance by confining execution inside a Virtual Machine which could record all operations.

This is known as verifiable computing or verified computation.  There are many protocols for verified computation, with different properties.  Some of them rely upon special hardware (e.g., SGX).  Many of them don't rely on special hardware and use cryptography.  Among the cryptographic solutions, there are some protocols that can be used with any program (but are potentially inefficient), and some that can only be used for specific programs or types of computations (but are much more efficient).

There's an entire line of research papers on the subject, and it is too broad to summarize in a single paragraph or two.  I suggest reading about interactive proofs, and about the Pepper, Ginger, Zaatar, Pinocchio, Pantry, and Truebit systems, among others.  I also recommend reading the following survey paper for an overview of cryptographic solutions that can handle general computation:

Verifying computations without reexecuting them, Michael Walfish, Andrew J. Blumberg, CACM 58(2), February 2015.

In practice, I suspect that the SGX-based schemes or Truebit are likely to be the most practical for general computation at the moment, though the research literature is progressing rapidly and this could change in the future.  For specific computations, it is sometimes possible to design a custom protocol that does much better, but that depends on the particular computation.


Intuitive meaning of modal $\mu$-calculus formula I am solving one of the past exams and I am not certain with my solution to one of the exercises. The exercise is asking to give intuitive meaning to modal $\mu$-calculus formula:

$$ \phi = \mu Z. \langle - \rangle tt \wedge [-a]Z $$

According to an article Modal logics and mu-calculi: an introduction by Bradfield and Stirling[1] the intuition behind $\mu$ operator is "finite looping". So my reasoning is following: on every path through states in $Z$ there must be only a finite number of transitions with labels different from $a$ and then we must reach a state which is both non-terminal (from the first condition) and all transitions from it are labelled $a$ (from finiteness).

Hence on every path through states in $Z$ there must eventually be a transition labelled $a$. (similar to CTL formula $\forall F(a)$).

Is my reasoning correct? I am unable to find any formal reason for my solution to be right, can you give me a little hint?

[1] http://homepages.inf.ed.ac.uk/jcb/Research/bradfield-stirling-HPA-mu-intro.ps.gz

Let's break it down.

First, let's look at $[-a]\phi$. This means every non-$a$ transition leads to a state where $\phi$ holds. It follows then that $[-a]\mathrm{ff}$ holds for states that have no non-$a$ transitions, which we will use when looking at the least fixed point semantics.

$\langle-\rangle\mathrm{tt}$ is pretty simple. It holds in any state that has any transition, i.e. is not deadlocked.

So together $\langle-\rangle\mathrm{tt} \land [-a]\phi$ means the state can take a transition and $\phi$ holds after every non-$a$ transition.

One way to view the meaning of $\mu Z.\phi(Z)$ is by the approximants referenced in your linked tutorial. If the formula is satisfied in state $s$ then there is some $\beta$ such that $\bigvee_{\alpha<\beta} \phi^{(\alpha)}(\mathrm{ff})$ is satisfied in $s$. The notation $\phi^{(n)}(x)$ means $\phi$ iterated on $x$, $n$ times, i.e. $\underbrace{\phi(\phi(\dots\phi(x)))}_{\text{$n$ times}}$. Let's look at some of these.

\begin{align}
\phi^{(0)}(\mathrm{ff}) &= \mathrm{ff} \\
\phi^{(1)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(0)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff} \\
\phi^{(2)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(1)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff}) \\
\phi^{(3)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(2)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff}))
\end{align}

Hopefully it is clear that these have the meanings

$\phi^{(1)}(\mathrm{ff})$: States that can take only $a$ transitions
$\phi^{(2)}(\mathrm{ff})$: Live states that

have only $a$ transitions; or
all length 1 non-$a$ paths lead to a live state with only $a$ transitions

$\phi^{(3)}(\mathrm{ff})$: Live states that

have only $a$ transitions; or
all length 1 non-$a$ paths lead to a live state with only $a$ transitions; or
all length 2 non-$a$ paths lead to a live state with only $a$ transitions

If that is unclear, remember that $[-a]\phi$ is trivially satisfied for states with no non-$a$ transitions.

Now you should see that $\phi^{(n)}(\mathrm{ff})$ is true if and only if the state can take at most $n-1$ non-$a$ transitions before reaching a live state with only $a$ transitions. It turns out that $\phi^{(n)}(\mathrm{ff}) \implies \phi^{(n+1)}(\mathrm{ff})$ so we don't need to take the disjunction with lesser approximants and can simply say $\mu Z. \langle-\rangle\mathrm{tt} \land [-a]Z \iff \exists \beta \in \mathbb{N}. \phi^{(\beta)}(\mathrm{ff})$, or in english, after a finite number of non-$a$ transitions we reach a live state with only $a$ transitions.


Can someone give a generic definition of any Definite Language in set builder notation? What I have come across as a definition is - a language $L ⊆ Σ^*$ is said to be definite if and only if $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$

Using these questions - Show that every definite language is accepted by a finite automaton

and What are definite languages? How do you formally define them?,

I understand that a definite language is a language where the membership of a string depends on it's last k-symbols only, i.e, those strings sharing the last k-symbols either belong to the language or don't. On these lines, I don't understand how the definition correspond to - $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$.

Having an intuitive idea, I am not quite able to get my head around a generic definition of a definite language in Set Builder Form. Could you please give a definition in Set Builder Notation specifically? I also request you to explain why you have defined it in such a manner, as I don't want to be in a situation where I couldn't understand the prior definition being $L = E ∪ Σ^*Η$. I have been going at this for an entire week, now.

In set-builder notation, it's just $E\cup \{vw\mid v\in\Sigma^*\text{ and }w\in H\}$.

So, why is this the same thing as "Languages that can be recognized by the last $k$ characters of the string"

One direction is fairly simple. If $L$ can be recognized by looking at the last $k$ characters, then there must be some set $H$ of length-$k$ strings such that, if the last $k$ characters form a string in $H$, you accept the string, and if they form a string not in $H$, you reject. Furthermore, there may be some strings that you accept even though they have fewer than $k$ characters: this set is $E$.

The other direction is a little more complex.  Suppose that $L = E\cup\Sigma^*H$ for some finite $E$ and $H$. We need to show that there is some $k$ and sets $X\subseteq\Sigma^{<k}$ and $Y\subseteq \Sigma^k$ such that $L=X \cup\Sigma^*Y$. Note that this is different from the hypothesis that $L=E\cup\Sigma^*H$ because it's more specific: $E$ and $H$ can be any finite sets of strings, whereas $X$ contains only strings of length less than $k$ and $Y$ contains only strings of length exactly $k$.

The solution is to take $k$ to be whichever is the larger of:

the length of the longest string in $H$;
one plus the length of the longest string in $E$.

(Since both $E$ and $H$ are finite, each has a longest string, or several longest strings of the same length.)

We start by taking $X=E$, which we're allowed to do because every string in $E$ has length strictly less than $k$.  Now, consider some string $h=h_1\dots h_\ell\in H$.  We have $\ell\leq k$ by the choice of $k$.  If $\ell=k$, we're happy: just add $h$ to $Y$.  Now suppose that $\ell<k$. If a string ends with $h$, then either it has length less than $k$ or it has length at least $k$ and its last $k$ characters are $a_1\dots a_{k-\ell}h_1\dots h_\ell$ for some $a_1, \dots, a_{k-\ell}\in\Sigma$. Therefore, we add to $X$ all strings of length less than $k$ that end with $h$, and we add to $Y$ all strings of length exactly $k$ that end with $h$. And we repeat this for every $h\in H$.

I've explained how to construct $X$ and $Y$. I won't write out their formal definitions as sets because those definitions are so full of notation that they're not enlightening.


Can every CFG be converted into an equivalent CFG of this form? Question:

Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables.

For this question, I have considered that it can be proved by using Greibach Normal Form, because we can get the form: A → aABCDEF... which is similar to the form above: A → xBC or A → ϵ.

However,the pre-condition of Greibach Normal Form is that any context-free grammar which doesn’t produce ϵ. I am not sure whether it can prove with GNF.

Can anyone give me suggestions of this proof ?

Since you're allowing $x = \epsilon$ in a production of the form $A \rightarrow xBC$, it seems you can first convert the grammar to Chomsky Normal Form so that every production is of one of the forms $A \rightarrow \epsilon BC$, $A \rightarrow x$, and $A \rightarrow \epsilon$. The only problem is that the productions which produce only a single terminal are not of the form you want, but that isn't too difficult to remedy.


How does this allow list operations to be applied to lists with elements of any type? In Types and Programming Languages by Pierce, Chapter 11 is simple extensions of the simply typed lambda calculus with any simple base types. Section 11.12 introduces Lists.

How does the section allow list operations to be applied to lists with elements of any type? Specifically, my confusions are:

Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference? (The book doesn't introduce type inference till Chapter 22 and parametric polymorphism till Chapter 23.)

Does "When we ﬁrst introduced lists in §11.12, we used “custom” inference rules to allow the operations to be applied to lists with elements of any type" in Section 23.4  mean that Section 11.12 makes use of type inference to achieve similar behavior of "polymorphism"?
Does  "For every type T, the type List T describes ﬁnite-length lists whose elements are drawn from T" in Section 11.12 mean

that  List T is a single literal type name for all possible specific typess for T, or
that List T  should be instantiated differently for different specific types for T, e.g.  List Boolean, List Nat?

Is [T]  part of the  the names of the list operators, e.g. nil[T], cons[T], isnil[T]?

Should [T] in nil[T] be instantiated differently for different specific types for T, e.g. nil[Boolean], nil[Nat]?
Does Section 23.4 use the same type List T as in Section 11.12? Where is List T defined?
I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12  cover lists?

Thanks.

  11 Simple Extensions

  11.12 Lists

  The typing features we have seen can be classiﬁed into base types like
  Bool and Unit, and type constructors like → and × that build new types
  from old ones. Another useful type constructor is List. For every type
  T, the type List T describes ﬁnite-length lists whose elements are
  drawn from T.

  Figure 11-13 summarizes the syntax, semantics, and typing rules for
  lists. Except for syntactic diﬀerences (List T instead of T list,
  etc.) and the explicit type annotations on all the syntactic forms
  in our presentation, these lists are essentially identical to those
  found in ML and other functional languages. The empty list (with
  elements of type T) is written nil[T]. The list formed by adding a
  new element t1 (of type T) to the front of a list t2 is written
  cons[T] t1 t2 . The head and tail of a list t are written head[T] t and tail[T] t. The boolean predicate isnil[T] t yields true iﬀ
  t is empty.

and

  23 Universal Types

  23.4 Examples

  Polymorphic Lists

  As an example of straightforward polymorphic programming, suppose our
  programming language is equipped with a type constructor List and term
  constructors for the usual list manipulation primitives, with the
  following types.

ñ nil : ∀X. List X
cons : ∀X. X → List X → List X
isnil : ∀X. List X → Bool
head : ∀X. List X → X
tail : ∀X. List X → List X

  When we ﬁrst introduced lists in §11.12, we used “custom” inference
  rules to allow the operations to be applied to lists with elements
  of any type. Here, we can give the operations polymorphic types
  expressing exactly the same constraints

Most importantly, Section 11.12 does not introduce polymorphic lists, but introduces monomorphic lists annotated by a type of its elements.

For example, Fig. 11-13 introduces a new term cons[T] t t. Here [T] is a type annotation, which indicates a type of elements of the list. Note that T is a metavariable ranged over types, not an object-level type variable or a type-level abstraction. In other words, it is different statements that "For every type T, the type List T has property P" and "the type of polymorphic lists ∀X. List X has property P". See Section 3.1 for details of metavariables.

I think most of your questions are answered in short by the above explanation. The followings are more detailed answers.

Q1

Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference?

Neither. It introduces monomorphic lists annotated by an element type (No need of type inference).

Q2

What does "For every type T, the type List T describes ﬁnite-length lists whose elements are drawn from T" in Section 11.12 mean?

T is a metavariable. For instance, it implies a type List Bool describes finite-length lists whose elements are drawn from Bool.

Q3

Is [T]  part of the  the names of the list operators, e.g. nil[T], cons[T], isnil[T]?

T is a metavariable. It may give you an intuition to try typing some actual program which contains lists.

Q4

Does Section 23.4 use the same type List T as in Section 11.12?

Yes/No. Both sections try to define the type List T as "a type of lists whose elements are drawn from T", but they define List T individually: List T of Section 11.12 is defined in Figure 11-13, and List T of Section 23.4 is defined informally in sentences.

  ... suppose our programming language is equipped with a type constructor List and term constructors for the usual list manipulation primitives, with the following types. ...

As written in the book, the notation of List T is the same, but list-related primitives are defined differently.

Q5

I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12 cover lists?

Chapter 20 describes a type system to handle general recursive types, rather than a specific recursive type (e.g. List T). Actually the beginning of Chapter 20 takes List T as an example of recursive types.


How to prove universality in complex systems? I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once.  The input consists of numbers, a sequence of numbers ranges from (-infnite to infinite), like ('5','65443'or'9921075').

From the sequence of numbers {input}, i can see each number's behavior and how it interacts with other numbers by analysing the different structures it outputs, it is like a Cellular Automaton structure simulates another Cellular Automaton structure.

How can i relate these properties to universality, What should i look for or analyze in these structures to show universality?

In order to show that your computation model is universal, you have to show that you can implement every computable function in your model. You do this by picking some other computation model $M$ and showing how to simulate $M$ in your model. For somewhat more formal definitions, see this answer.

As stated, this sounds difficult, and the first step is to look at various proofs of universality to get some ideas of what is involved. Some examples are listed in the Wikipedia article. It's possible that your model can easily simulate one of the simpler computation models such as counter machines, and this is perhaps the first thing to check.

It is also possible that your model is not Turing-complete but is still quite strong, say PSPACE-complete or EXPTIME-complete.


Kleene closure of the empty set In the book introduction to automata theory and languages, $L^*$ is defined as

$$L^* =  \bigcup_{i=0}^\infty L^i $$

The book also says that $\emptyset^* = \{  \epsilon   \}$. But since $\emptyset$ is the empty set

$$L^* =  L^0 \cup L^1 \cup L^2 ... $$

$$=  L^0 \cup \emptyset$$ -- since $ \emptyset\emptyset = \emptyset $ and there are 0 elements of $L$

Now since L is $ \emptyset $, then it does not contain $\epsilon$ either. So thus

$$L^* =  \emptyset $$

But that does not seem to be the case. According to the book, $L^0$ is $\{ \epsilon \}$ and thus $L^* = \{ \epsilon \}$, for L = $\emptyset$. Where am I going wrong?

You are correct with $L^* = L^0 \cup \emptyset$.

But $L=\emptyset$ does not imply $L^0 = \emptyset$. Consider $L^i$ to be built incrementally: You start with $\epsilon$ and then add a word from $L$ to the end $i$ times.

If $i\ge 1$ and $L=\emptyset$, this will fail when you try to add the first word, since there are no words in $L$. So here $L^i$ becomes $\emptyset$. But for $L^0$ you never try to take a word from $L$. So the fact that $L$ is empty does not matter, you simply terminate after initialising your word as $\epsilon$.

Thus $L^0=\{\epsilon\}$ and $L^* = \{\epsilon\} \cup \emptyset = \{\epsilon\}$.