# Question
Title: Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?
I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a check. There is a YouTube video explaining this whole function (and it includes the pseudo-code plus line numbers): https://youtu.be/5IBxA-bZZH8?t=323

The thing is, I think that `//case 2` needs its own check. The `else if z == z.p.right` is both meant for `//case 2` and `//case 3`. However, the code from `//case 2` shouldn't always fire. It should only fire when there is a triangle formation according to the YouTube video. In my implementation it always fires, even when it's a line.

So I feel the pseudo-code is wrong, it's also weird that it has an indentation, but I see no extra check.

Am I missing something?

Maybe superfluous, but I also typed the pseudo code given from the book here:

```
RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK

```

# Answer
> 4 votes
In an email with one of the authors it became clear that the following pseudo-code rule applies.

(this is not an actual quote, but the format seems better for this)

> Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things.

If that was too abstract, the code from question should be interpreted as follows:

```
RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else                  // this is the difference compared to code in the question
        if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK

```

---
Tags: data-structures, red-black-trees
---


# Question
Title: Minimize shipping cost based on weight and price constraints
I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows:

1. There is a limit on the max price of the combined package (say $15)
2. The cost of the package is determined using the following table:
    1. If total weight of package is \< 30 grams, cost is 7.5
    2. If total weight of package is \>= 30g and \<80g, cost is 7.5 + (weight - 30)x0.075
    3. If total weight of package is \>= 80g, cost is 7.5 + (weight - 30)x0.055

There is no limitation on the number of packages these items can be combined into as long they remain under the total price threshold.

I looked at the knapsack problem, but there are 2 major differences between the knapsack problem and my problem:

1. One is that we are not maximizing the weight or price of the items combined, instead we want to minimize a calculated variable that can only be determined after the combination.
2. Also, there isn't a direct correlation between weight and shipping cost.

# Answer
> 1 votes
Since the objective function is piecewise linear, the problem can be formulated as an integer linear program.

Given items with prizes $p\_1,\ldots,p\_n$ and weights $w\_1,\ldots,w\_n$, define binary variables $x\_i$ for $i\in\[n\]$ where $x\_i=1$ if item $i$ selected. For each of the three segments a binary variable $\delta\_k$ selects the active segment, and the convex combination of $(\lambda\_1,\lambda\_2)$, $(\lambda\_2,\lambda\_3)$, or $(\lambda\_4,\lambda\_5)$ defines the point in the first, second, or third segment, respectively. Note that $\lambda\_3=1$ and $\lambda\_4=1$ are different, since your objective function is not continuous at $80$. Auxiliary variables $w$ and $c$ hold the total weight and cost. Finally $W=\sum\_{i\in\[n\]} w\_i$ is an upper bound on the maximum weight.

With this you can \begin{align} \text{min.}\quad & c,\\ \text{s.t.}\quad & \delta\_1 + \delta\_2 + \delta\_3 = 1,\\ & \lambda\_1+\lambda\_2 = \delta\_1,\\ & \lambda\_2+\lambda\_3 = \delta\_2,\\ & \lambda\_4+\lambda\_5 = \delta\_3,\\ & w = 30\lambda\_2+80(\lambda\_3+\lambda\_4)+W\lambda\_5,\\ & c = 7.5\lambda\_1+7.5\lambda\_2+11.25\lambda\_3+10.25\lambda\_4+(7.5+0.055(W-30))\lambda\_5,\\ & \sum\_{i\in\[n\]} p\_ix\_i \leq 15,\\ & \sum\_{i\in\[n\]} w\_ix\_i = w,\\ & x\_i\in\\{0,1\\}, i\in\[n\],\\ & \delta\_1,\delta\_2,\delta\_3\in\\{0,1\\},\\ & \lambda\_1,\lambda\_2,\lambda\_3,\lambda\_4,\lambda\_5\geq 0,\\ & w,c\geq 0. \end{align}

For, say, about 100 items I guess a standard solver can find the optimal solution in a few minutes.

(From your question it is not clear me if you want to select a subset of the items that can be sent at optimal cost, or minimize the total cost for all packages to send all items. For the latter you can extend the model by using variables $x\_{ij}$ that indicate if item $i$ goes to the $j$th package, use similar constraints to define the cost for each package, and then minimize the total cost.)

---
Tags: algorithms, knapsack-problems
---


# Question
Title: Prove that "Finishing the degree in three years" problem is NP-Complete
I was asked in an interview the following question:

We'll define the "Finishing the degree in three years" problem in the following manner:

Given a list of courses $C=\\{c\_1, c\_2,\ldots, c\_n\\}$, where every course $c\_i\in C$ is given a list $R\_i\subseteq C$ of the precondition courses for this course, and also we are given the maximal amount of courses in each year $m\_1, m\_2, m\_3$, and we need to decide if it is possible to finish the degree in three years. Meaning, can we divide the courses for three years $Y\_1, Y\_2, Y\_3 \subseteq C$, such that the following conditions are satisfied:

1. All courses are studied within 3 years: $Y\_1\cup Y\_2\cup Y\_3=C$.
2. Each courses is studied only after all of its precondition courses have been studied, meaning: for any $c\_i\in Y\_1: R\_i\subseteq\emptyset$, for any $c\_i\in Y\_2: R\_i\subseteq Y\_1$, for any $c\_i\in Y\_3: R\_i\subseteq Y\_1\cup Y\_2$.
3. The number of courses studied in each year is not higher than maximum allowed, meaning: $|Y\_i|\le m\_i$ for each $i\in\\{1,2,3\\}$.

Prove that the "Finishing the degree in three years" problem is NP-Complete.

I was told that the reduction should be from the clique problem but it has been a week since I've started thinking about it and I couldn't prove it. If someone can please post a thorough solution I would appreciate it a lot.

# Answer
Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "edge course") in $G$. Each edge course has two precondition vertex courses corresponding to its two endpoints. In addition, we set $m\_1=k,m\_2=+\infty, m\_3=m-\binom{k}{2}$ where $m$ is the number of edges in $G$. Now we can see there is a clique of size $k$ in $G$ if and only if it is possible to finish the degree in three years.
> 7 votes

---
Tags: complexity-theory, np-complete, reductions, clique
---


# Question
Title: Non-deterministic Finite Automata | Sipser Example 1.16
I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$.

Could someone run me through why this is the case?

My understanding is that $\epsilon$ will move to $q\_3$ which is not an accept state.

# Answer
You are confusing $\epsilon$ with a letter. It's not a letter! It's just the empty string.

Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is labeled with an arbitrary word. We say that the word-NFA accepts a word $w$ if there is a walk from an initial state to a final state such that if we concatenate the edge labels across the walk, we get $w$. In symbols, a word-NFA accepts $w$ if there is a sequence of transitions $$ q\_0 \stackrel{w\_1}\to q\_1 \stackrel{w\_2}\to q\_2 \stackrel{w\_3}\to \cdots \stackrel{w\_n}\to q\_n $$ such that:

1. $q\_0$ is an initial state. (The usual model only allows one initial state, but we can relax that requirement.)
2. $q\_n$ is a final state (also called an accepting state).
3. Each transition $q\_{i-1} \stackrel{w\_i}\to q\_i$ corresponds to a transition of the word-NFA.
4. $w = w\_1 \ldots w\_n$.

An NFA is a word-NFA in which all transitions are labeled by letters (i.e., words of length exactly 1), and an $\epsilon$-NFA is one in which all transitions are labeled by letters or $\epsilon$ (i.e., words of length at most 1). Usually we also require that there be a unique initial state.

A word-NFA accepts $\epsilon$ if there is a sequence of transitions $$ q\_0 \stackrel\epsilon\to q\_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q\_n $$ such that $q\_0$ is an initial state, $q\_n$ is a final state, and all transitions are valid. In particular, if some state is both initial and final, then the word-NFA accepts $\epsilon$ (this correponds to $n = 0$).
> 9 votes

---
Tags: regular-languages, finite-automata, nondeterminism
---


# Question
Title: Shortest hamiltonian path for different dimension points
The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.

For example if for $k=1$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $O(n\log n)$.

My question is what happens when $k$ increases - does the solution become more and more complex or is it the same for all values of $k$ larger than $1$?

# Answer
Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity.

Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms:

1. For every fixed $k$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
2. Trevisan showed that there is no PTAS when $k = \log n$ (unless P=NP).
3. Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $k$!
> 2 votes

---
Tags: np, approximation, hamiltonian-path
---


title: Asymptotics of a sinusoid

text:
# Question
Title: Asymptotics of a sinusoid
Consider the function $$ f(n) = 2n^2 |\sin(\pi \cdot n/2)|. $$ Which of the following classes does $f(n)$ belong to? $$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$

I'm working in this and so far I have been trying to use different methods but always get to a dead end.

# Answer
> 2 votes
Let us notice the following: $$ |\sin(\pi \cdot n/2)| = \begin{cases} 1 & \text{if $n$ is odd}, \\ 0 & \text{if $n$ is even}. \end{cases} $$ This implies that your function $f(n)$ alternates between $n^2$ (for odd $n$) and $0$ (for even $n$). This means, for example, that $f(n) = O(n^2)$ (since $f(n) \leq n^2$ for all $n$) but $f(n) \neq \Omega(n^2)$ (considering even $n$).

---
Tags: complexity-theory, asymptotics, lower-bounds, upper-bound
---


# Question
Title: Can we find a computable function which cannot be calculated faster for any given time?
Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by:

$T(k,n) = 2^{T(k-1,n)}$

$T(0,n) = 1$

$T(1,n) = 2^n$

$T(2,n) = 2^{2^n}$

And denote the W.C. (worst case) time of computing $f(n)$ as $WC(f(n))$

Can we find computable functions $f\_i\colon \mathbb{N} \rightarrow \mathbb{N}$ such that computing $f\_i(n)$ takes $\Omega(T(i,n))$ W.C. and such that for every other computable function $f \equiv f\_i$ (I mean $f(n) = f\_i(n) \forall n \in \mathbb{N}$), we have $\lim\_{n \rightarrow \infty} \frac{WC(f\_i(n))}{WC(f(n))} \neq 0$?

I am in a sense trying to find a concrete example of functions that takes at least X time to compute, where X can be as large (asymptotically) as we want.

I was thinking maybe $f\_i(n) =$ the $T(i,n)$'th digit of $\pi$, but not quite sure this fulfills the second condition.

# Answer
> 2 votes
The "$f$-bounded halting problem" takes time at least (roughly) $f$ (for infinitely many $n$). The $f$-bounded halting problem asks whether a Turing machine halts on the input $0^n$ within time $f(n)$. Suppose we could solve this problem in time $g(n)$. Consider the following machine:

> On input $0^n$, ask whether the $n$th Turing machine halts within time $f(n)$ on the input $0^n$. If so, go into an infinite loop, and otherwise, halt.

This takes time $g(n) + Cn$ for some constant $C$. If $g(n) + Cn \leq f(n)$ then we obtain a contradiction by taking $n$ to be the code of this machine. Hence the $f$-bounded halting problem cannot be solved in time $f(n) - Cn$.

This argument only shows that we need time $f(n) - Cn$ for *some* $n$. But we could consider an infinite sequence of Turing machines equivalent to the one described above, and so obtain an "infinitely often" version of this statement.

It is possible that through trickery we can improve this to *all* $n$ (for reasonable functions $f$), and leave this for the reader to ponder.

---
Tags: algorithms, complexity-theory, time-complexity
---


title: Showing that HALF-2-SAT is in P

text:
# Question
Title: Showing that HALF-2-SAT is in P
I need to show that the following problem is in P: $$\begin{align\*}\text{HALF-2-SAT} = \\{ \langle \varphi \rangle \mid \\, &\text{$\varphi$ is a 2-CNF formula and there exists an assignment} \\ & \text{that satisfies at least half of the clauses} \\}\end{align\*}$$

I know that 2-SAT is in P, hence it got a decider and I wanted to use it for HALF-2-SAT but got stuck to find how to extract the right half of the clauses that will be satisfied in a polynomial way.

Is there an official way to choose half of the clauses that satisfy the formula?

# Answer
> Is there an official way to choose half of the clauses that satisfy the formula?

There is no official way. As noted by Juho, "any algorithm that you prove correct is acceptable". Moreover, you do not have to choose that half of the clauses explicitly.

---

Here is the simplest algorithm to decide $\text{HALF-2-SAT}$ that runs in polynomial time. In fact, it runs in constant time. (If the algorithm should verify the given input is valid, it runs in linear time.)

* Input: $\varphi$ and $m$, where $\varphi$ is a 2-CNF formula with $m$ clauses.
* Output: True if there is an assignment of the variables such that at least $m/2$ clauses become 1.
* Procedure: Return true.

---

Why does the above algorithm work? Here is the reason.

**Lemma.** Let $\varphi$ be a 2-CNF formula. Then there exists an assignment that satisfies at least half of the clauses in $\varphi$.

**Proof.** Let $f\_0$ assign 0 to all variables. Let $f\_1$ assign 1 to all variables. Let $c$ be any one of the clauses in $\varphi$. Suppose variable $x$ appears in $c$.

* the literal $x$ is in $c$. Then $c$ becomes 1 under $f\_1$.
* the literal $\neg{x}$ is in $c$. Then $c$ becomes 1 under $f\_0$.

So every clause becomes 1 under $f\_1$ or $f\_0$. So the number of clauses is not greater than the sum of the number of clauses that becomes 1 under $f\_1$ and the number of clauses that becomes 1 under $f\_0$. Hence, at least half of the clauses in $\varphi$ are satisfied under $f\_1$ or $f\_0$. QED.

---

Here are several exercises.

**Exercises 1**. Show the following language is in **P**: $$\begin{align\*}\text{3-SAT}\_{\ge\frac12} = \\{ \langle \varphi \rangle \mid \\, &\text{$\varphi$ is a 3-CNF formula and there exists an assignment} \\ & \text{that satisfies at least half of the clauses} \\}\end{align\*}$$

**Exercises 2**. Show that the following problem is in **P**: $$\begin{align\*}\text{2-SAT}\_{\le\frac34} = \\{ \langle \varphi, f \rangle \mid \\, &\text{$\varphi$ is a 2-CNF formula and $f$ is an assignment} \\ & \text{that satisfies at most three fourth of the clauses} \\}\end{align\*}$$

**Exercises 3**. Let $\varphi$ be a 2-CNF formula such that none of its clause involves only one variable. Then there exists an assignment that satisfies at least three fourth of the clauses in $\varphi$.
> 6 votes

# Answer
Your language consists of all valid encodings of a 2-CNF formula. Consider a random assignment to the variables of $\varphi$, i.e. each variable is assigned True/False with probability $\frac{1}{2}$, then the expected portion of satisfied clauses is $\frac{3}{4}$ (use linearity of expectation and note that each clause is not satisfied with probability $\frac{1}{4}$) , which means that there exists an assignment which satisfies at least $\frac{3}{4}$ of the clauses.

The above observation yields a simple deterministic algorithm for finding such an assignment. Let $S\_{\varphi}$ denote the random variable counting the number of satisfied clauses relative to a random assignment.

Note that for any variable $x\_i$ we have: $\mathbb{E}\big\[S\_\varphi\big\]= \frac{1}{2}\mathbb{E}\big\[S\_\varphi\big| x\_i = 1 \big\]+ \frac{1}{2}\mathbb{E}\big\[S\_\varphi\big| x\_i = 0 \big\]$.

Now, you can simply pick the assignment $b\in\\{0,1\\}$ to $x\_i$ which maximizes $\mathbb{E}\big\[S\_\varphi | x\_i = b\big\]$ (you can compute the expectation in linear time). To see why, suppose that $\mathbb{E}\big\[S\_\varphi| x\_i = 1 \big\] \ge \mathbb{E}\big\[S\_\varphi| x\_i = 0 \big\]$, then since $\mathbb{E}\[S\_\varphi\]=\frac{3}{4}m$, it must hold that $\mathbb{E}\big\[S\_\varphi| x\_i = 1 \big\]\ge\frac{3}{4}m$, which means that there exists an assignment for the variables of $\varphi$ which assigns $1$ to $x\_i$ and satisfies $\ge\frac{3}{4}m$ clauses.
> 4 votes

# Answer
Complementing the statement in the post, let us consider the following generalization of HALF-2SAT: for a constant $c$, the language $c$-2SAT consists of all 2SAT instances on $m$ clauses such that some assignment satisfies at least $cm$ clauses. HALF-2SAT is the special case $c = 1/2$.

We have seen above that when $c \leq 1/2$, the answer is always YES. When $c = 1$, this is just 2SAT, which can be solved in polynomial time. Complementing these results, let us show that if $1/2 \< c \< 1$, the language $c$-2SAT is NP-complete.

Our starting point is the PCP theorem, which states that there is a function $f$ mapping 3SAT instances to 3SAT instances such that:

* If $\phi$ is satisfiable then $f(\phi)$ is satisfiable.
* If $\phi$ is unsatisfiable then at most a $1-\epsilon$ fraction of the clauses of $f(\phi)$ can be simultaneously satisfied.

We compose this with a simple reduction of Garey, Johnson and Stockmeyer, which converts a 3SAT instance $\psi$ to a 2SAT instance $g(\psi)$ by mapping each original clause to 10 new clauses such that:

* For every assignment satisfying an original clause, 7 of the 10 new clauses can be satisfied.
* For every assignment not satisfying an original clause, at most 6 of the 10 new clauses can be satisfied.

Composing the two reductions, we obtain:

* If $\phi$ is satisfiable then a $0.7$ fraction of the clauses of $g(f(\phi))$ can be satisfied.
* If $\phi$ is unsatisfiable then at most a $0.7(1-\epsilon) + 0.6\epsilon = 0.7 - 0.1\epsilon$ fraction of the clauses of $g(f(\phi))$ can be satisfied.

This shows that $0.7$-2SAT is NP-hard. The astute reader will notice that the PCP theorem is not needed for this step – we could just use a direct reduction from 3SAT.

In order to boost this to arbitrary $c$, we either add lots of pairs of clauses of the form $x, \lnot x$ to push $c$ down, or add lots of clauses of the form $x$ to push $c$ up. This is where we use the gap provided by the PCP theorem, for technical reasons.

Let us start with the second case. Suppose that $g(f(\phi))$ contains $m$ clauses. For integers $a,b$, we duplicate $a$ times the formula $g(f(\phi))$, and add $b m$ clauses of the form $x$, where $x$ is a new variable. If $\phi$ is satisfiable, then in the new formula we can satisfy a fraction of $\frac{0.7 a + b}{a+b}$ of the clauses, whereas if $\phi$ is unsatisfiable, we can satisfy at most a fraction of $\frac{(0.7 - 0.1\epsilon)a + b}{a+b}$. We choose $a,b$ so that $$ \frac{(0.7 - 0.1\epsilon)a + b}{a+b} \< c \le \frac{0.7a + b}{a+b}. $$ To do this, suppose that $c = 0.7 + \delta$. Take $a$ to be large and $b = \lfloor \delta a \rfloor$. The right-hand side tends (as $a\to\infty$) to $c$ (from below) and the left-hand side tends to $0.7-0.1\epsilon+\delta$, so for large enough $a$ the inequality above will be satisfied.

When $c \< 0.7$, in addition to adding $bm$ clauses of the form $x$, we also add $bm$ clauses of the form $\lnot x$. Instead of $\frac{0.7a+b}{a+b}$ we now get $\frac{0.7a+b}{a+2b}$; we let the reader complete the proof from here.
> 1 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Recognizing Regular Languages in Layman terms
I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular.

I know that `0*1*` is regular because the machine just needs to make sure the 0s and 1s are in order

I know that `0^n 1^n`is non regular because the machine needs to keep count to make sure there is an equal number of 0s and 1s

But why is `(01)^n` considered regular? Doesn't the machine have to keep track to make sure that there are `n` amount of `01`?

How about `{0^m 1^n | n>m}`?

What is the general rule for quickly figuring out if something is regular or not in layman terms?

# Answer
the way to test if something is non regular is to use the pumping lemma for regular languages. It can prove that a language is non regular, but it will not necessarily prove that a language is regular. To prove that some language is regular, you can create a finite automata for that language.
> 0 votes

---
Tags: complexity-theory, computability, regular-languages, finite-automata
---


# Question
Title: What should I call algorithms with non-linear non-constant time?
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity `O(NlogN)`, and some of the are more complex (e.g polynomial-time) and I want to refer to them all in one term. Is there any common term to use in such a situation?

`linearithmic` refers to `O(NLOGN)` algorithms and it's narrower than what I'm looking for. I don't think of `non-linear` as a good term to use here. If it is, then correct me please.

my sentence:

> In such a setting, state-of-the-art community-detection algorithms does not scale well. To reduce the running time of these XYZ algorithms, each sub-graph is partitioned into chunks.

I want to change \`XYZ' in the above, to what I am asking for.

# Answer
> 4 votes
As mentioned by Bryce Kille in the comments, **superlinear** is what you are looking for. From Wiktionary:

> 2. (mathematics) Describing a function that eventually grows faster than any linear one

(By the way, the first phrase in your question strikes me as rather odd: "\[...\] I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity $O(N \log N)$." Do you simply mean "linear" instead of "polynomial-time"?)

# Answer
> 1 votes
On top of the other answers, you can also say $\omega(n)$ and people *should* know what you mean, but often won't.

# Answer
> 0 votes
> I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity `O(NlogN)`. Is there any common term to use in such a situation?

Yes: *polynomial*. Note that $O(N \lg N) \subset O(N^2)$.

> I am trying to mention that these algorithms' running time grow faster than linear.

That makes them *superlinear*. If you want to be explicit about the fact that you're talking about the intersection you could say *superlinear polynomial*.

---
Tags: complexity-theory, time-complexity, terminology, runtime-analysis, big-o-notation
---


# Question
Title: The problem of equivalence of a CFG and a RG?
Given a context-free grammar and a regular grammar, check whether they are equivalent. It's a fact that it's undecidable, but how could I prove it?

I want to clarify that my question is not about determining whether a CFG describes a regular language. In my problem I am given a CFG and a regular language and I need to tell whether they are equal or not. These are different problems as far as I understand, mine is easier than that one.

# Answer
There is no algorithm which can determine for any context-free grammar $G\_1$ and regular grammar $G\_2$ whether $L(G\_1) = L(G\_2)$.

However, it may well be possible to determine for *particular* $G\_1$ and $G\_2$, using heuristic proof techniques (aka human intuition).

Good luck with the assignment.
> 1 votes

---
Tags: formal-grammars, undecidability
---


title: Reductions between LIS and LCS

text:
# Question
Title: Reductions between LIS and LCS
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the *length* of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Alternatively, given an oracle for finding both the subsequence and length of the Longest Common Subsequence between two sequences, it's easy to find $\text{LIS}(A)$: Given a sequence $A$, sort $A$ into $A'$, and calculate $\text{LCS}(A,A')$.

This question is prompted by the fact that there are $O(n\log n)$ algorithms for LIS but not LCS. On a separate note, are there any results comparing the hardness of the two problems or giving a superlinear/quadratic lower bound to LCS?

# Answer
> Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the *length* of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Well, we can find $\text{LCS}(A,B)$ without any call to the oracle since we can just run any algorithm that finds $\text{LCS}(A,B)$ such as brutal force or a solution by dynamic programming.

What you intended to ask was how much we can reduce the time-complexity of algorithms that find $\text{LCS}(A,B)$ if the oracle is available. The time-complexity will consist of two parts. One part comes from ordinary operations, and the other part comes from the calls to the oracle. There are two questions here.

**Question one.** Can we use less ordinary operations (asymptotically) with the availability of the oracle?

**Question two.** If we can, how few calls to the oracle are needed to lower the complexity of the ordinary operations?

### When one of $A$ and $B$ consists of distinct elements

Suppose the elements in $A$ are distinct. Here is an algorithm that employs the oracle. The idea of the algorithm is that if we regard the natural order of elements in $A$ according to the indices as defining a strictly increasing order, a common subsequence of $A$ and $B$ is exactly an increasing subsequence of $B$.

1. Keeping $A$ intact, sort $A$ into a new sequence $\alpha$.
2. Initialize a new sequence $I$.
3. For $i$ from 0 to size($B$) exclusive, try finding the index $j$ such that $A\[j\]$ is $B\[i\]$. If found, append $\alpha\[j\]$ to $I$.
4. Return the length that is returned by the oracle given sequence $I$.

There are two ways to implement step 2.

* If the elements in $A$ and $B$ can be totally ordered, we can sorted the elements in $A$, keeping track of each element's index in $A$. Then a binary search can find that index $j$.
* Construct a hash set whose elements are $(A\[i\],i)$ for all $i$, where the hash depends only on $A\[i\]$. Then we can use the hash set to find that index $j$.

So an answer to question one and two is that we can use a single call to the oracle to lower the complexity of the ordinary operations from $O(nm)$ to

* $O(n\log n + m \log n)$ when $m\gg\log n$ or
* $O(m)$ if the operation of finding an element in a hashset is considered $O(1)$.

Here $n$ is the number of distinct elements in one array and $m$ is the number of the elements in the other array.

### When both $A$ and $B$ contain duplicate elements

It is not clear how we can take advantage of the oracle in order to reach a positive answer to question one. Instead, here is a conditional hardness result.

It is not possible to find $LCS(A,B)$ in time $O(n^{2 - \epsilon})$ for any positive constant $\epsilon$ where $n$ is the length of $A$ and $B$, if we can assume *the strong exponential time hypothesis*. This is shown in *Tight Hardness Results for LCS and Other Sequence Similarity Measures* by Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams, 2015.
> 2 votes

---
Tags: algorithms, complexity-theory, reference-request, dynamic-programming, strings
---


# Question
Title: How is diagonalization a valid argument for the undecidability of the halting problem?
All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.

```
def g():
    if halts(g):
        loop_forever()

```

My question is: how can the input of a TM contain the TM itself and its input?

If the description of the TM has states and transitions, then it has more than its input therefore the input of the TM has infinite size because it contains both the TM and the input.

# Answer
> 3 votes
Try the following code instead:

```
def quote(s):
    return s.replace("'", "\\'")

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

```

If we add the following halting routine:

```
def halts(prog):
    print prog
    return False

```

then we can run `g()` and see that the input to `halts` is indeed the code for `g()`:

```
>>> g()

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

```

A program that prints itself is called a quine. The corresponding result in computability theory is the recursion theorem, which ensures that (in a sense) a program can have access to its own source code.

# Answer
> 0 votes
A description of a Turing machine contains: 1. the set of states (including initial & accepting & rejecting states) 2. the alphabet 3. the transition function

Note that we do not need to keep the input in the description. It's actually the same as any program you write, you don't write the actual input in your code. The input does not have its impact until runtime.

---
Tags: turing-machines
---


# Question
Title: Undecidability of checking whether all words can be generated from a context-free grammar?
I know it's undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

# Answer
Let $T$ be a one-tape Turing machine. A *snapshot* of a Turing machine is the contents of its tape, where the location of the head is preceded by the current state of the machine (encoded using a disjoint set of symbols).

We can encode a halting computation of $T$ on the empty string as a string $s\_0 \\# s\_1^R s\_2 \\# s\_3^R \\# \ldots \\# s\_n$ (or $s\_n^R$, according to the parity of $n$), where $s\_0,\ldots,s\_n$ is the sequence of snapshots encountered during the run of $T$.

We can check that a string does *not* code a halting computation as follows:

* It is of the form $\Sigma^\*\\# s \\# \Sigma^\*$, where $s$ doesn't contain $\\#$ but doesn't correspond to a valid snapshot. (More accurately, we have two corner cases corresponding to the first and last snapshot, and we might have to count the number of $\\#$ in the prefix to determine whether it should be a snapshot or its reverse.)
* It is of the form $s\_0 \\# \Sigma^\*$, where $s\_0$ doesn't contain $\\#$ but doesn't correspond to an initial snapshot.
* It is of the form $\Sigma^\* \\# s\_n$ (or $s\_n^R$), where $s\_n$ doesn't contain $\\#$ but doesn't correspond to a final snapshot (i.e., the Turing machine is not in a final state).
* It is of the form $\Sigma^\* \\# s\_i \\# s\_{i+1}^R \\# \Sigma^\*$ (or $s\_i^R \\# s\_{i+1}$, according to the parity of $\\#$ in the prefix), where $s\_i,s\_{i+1}$ do not contain $\\#$ but $s\_{i+1}$ is not the snapshot following $s\_i$.

With some care, we can express all of these conditions as a context-free grammar. Here it is important that we encode the computation by reversing any other snapshot, since this enables us to ascertain that $s\_{i+1}$ doesn't follow $s\_i$ in a context-free manner (roughly speaking, this is just the language $w\\#w^R$ with small modifications).

This context-free grammar generates $\Sigma^\*$ if and only if $T$ doesn't halt on the empty string. It follows that universality of context-free grammars is co-r.e.-hard. It is also co-r.e.: if the context-free grammar is not universal, then there is a witness for it, namely a string not generated by the grammar (recall that the word problem for context-free grammars is decidable). Hence universality of context-free grammars is co-r.e.-complete.
> 1 votes

---
Tags: context-free, formal-grammars, undecidability
---


# Question
Title: Proving that the set of grammars generating L or L complement is undecidable
Let $X$ be a regular language, I need to prove that either $\\{G \mid L(G) = X\\}$ or $\\{G \mid L(G) = \overline{X} \\}$ is undecidable using the following hint: Use reduction to absurdity supposing that both sets are decidable and concluding that UNIVERSALITY is decidable.

UNIVERSALITY problem is $ \\{ G \in CFG \mid L(G) = \Sigma^\* \\} $, which is known to be undecidable.

I think that the goal is to arrive to the conclusion that UNIVERSALITY is decidable, maybe with a reduction, which means that there is a contradiction in terms of decidabilty of UNIVERSALITY.

# Answer
Suppose that given a context-free grammar $G$, you could decide whether $L(G) = X$ and whether $L(G) = \overline{X}$. You can use it to decide UNIVERSALITY as follows:

* Create a grammar $G\_1$ such that $L(G\_1) = L(G) \cap X$.
* Create a grammar $G\_2$ such that $L(G\_2) = L(G) \cap \overline{X}$.
* Accept if $L(G\_1) = X$ and $L(G\_2) = \overline{X}$.

The point is that we can construct the grammars $G\_1,G\_2$ algorithmically.

Note that for some $X$, deciding whether $L(G) = X$ could be decidable. The simplest example is when $X = \emptyset$. A more sophisticated example is $X = w^\*$ (this follows from Parikh's theorem, for example).
> 1 votes

---
Tags: computability, regular-languages, context-free, formal-grammars, reductions
---


title: Proof Big Theta (sum of a geometric)

text:
# Question
Title: Proof Big Theta (sum of a geometric)
Here sum of a geometric, where c is a positive real number.

$g(n)=1+c+c^2+...+c^n$

$\theta(1)$ if $c\<1$

Any idea to solve this?

# Answer
> 1 votes
It is known that $$ 1 \leq g(n) \< \sum\_{m=0}^\infty c^m = \frac{1}{1-c}. $$ You take it from here.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?
I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this :

https://en.wikipedia.org/wiki/NP-hardness#/media/File:P\_np\_np-complete\_np-hard.svg

I wonder if the following is possible ? Which means, P = NP, but not all of them are in NP-Hard :

Edit : I want to add this : I'm not here to say if the original image is wrong or right, I'm just here to ask a question if my image contains a possible situation. In other words, is it correct to assume that all 3 images are possible ?

# Answer
Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.)

If $\mathrm{P}=\mathrm{NP}$, Wikipedia claims that every problem in $\mathrm{P}$ is $\mathrm{NP}$-complete. However, this is not true: in fact, every problem in $\mathrm{P}$ would be $\mathrm{NP}$-complete, except for the trivial languages $\emptyset$ and $\Sigma^\*$.

You can't many-one reduce any nonempty language $L$ to $\emptyset$, because a many-one reduction must map "yes" instances of $L$ to "yes" instances of $\emptyset$, but $\emptyset$ has no "yes" instances. Similarly, you can't reduce to $\Sigma^\*$ because there's nothing to map the "no" instances to. However, if $\mathrm{P}=\mathrm{NP}$, then every other language in $\mathrm{P}$ is $\mathrm{NP}$-complete, since you can solve the language in the reduction.

So, just to make it explicit:

* your diagram is correct;
* Wikipedia's isn't (unless you read the tiny disclaimer);
* the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$" contains the two languages $\emptyset$ and $\Sigma^\*$, and nothing else;
* the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$-complete" contains every other language in $\mathrm{P}$ and nothing else.
> 12 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: NFA that accepts all numbers not divisible by 105
I have to create an NFA that accepts the following language L with no more than 15 states.

$L = \\{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \\}$.

To me it seems that all multiples of 105 have the same properties:

* sum of digits is divisible by 3
* the last digit is 0 or 5

I would appreciate if someone could help me here.

# Answer
> 3 votes
Here is a hint.

$L$ is the union of the following three languages.

* $L\_3=\\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 3}\\}$,
* $L\_5=\\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 5}\\}$,
* $L\_7=\\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 7}\\}$.

Construct the DFA for the above three languages. Then combine them together.

---

**Exercise.** (It may take some time to do this exercise.) Show that no NFA with less than 15 states accepts $L$ exactly.

---
Tags: finite-automata
---


# Question
Title: Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption
I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-one reduction $f$ from 3-Sat to Independent set. Let $\psi$ be the input to 3-SAT with parameter $\kappa\_{3-SAT} = \\#variables + \\# clauses$ and let $(G=(V,E),k)$ be the input for Independent Set with parameter $\kappa\_{IS} = |V| + |E|$

For every clause in the input formula $\psi$, add three vertices to the Graph, corresponding the the respective literals. Add an edge between two vertices if:

a) They correspond to literals in the same clause or

b) they correspond to a variable and its inverse

Then 3-Sat has a satisfying assignment if and only if the graph defined by this reduction has an independent set of size $m$, where $m$ is the number of clauses in $\psi$. For example:

I am now wondering whether this reduction suffices to show that (assuming ETH), Independent Set cannot be solved in $2^{o(|V|+|E|)}$ time. If I understand correctly, the number of vertices $|V| = 3m$ and the number of edges $|E| \leq 3m+nm$, since for each clause, we have $3$ edges between the respective vertices and then for each variable we have at most $m$ edges between a variable and its inverse. However, this is not linear in $\kappa\_{3-Sat}$ anymore.

Is my upper bound on the numer of edges wrong or do I a different reduction to show the desired result?

# Answer
> 2 votes
First, let me remark that $n=O(m)$ as in each clause only $3$ variables may appear, and that $m=O(n^3)$ without loss of generality as there can be at most $(2n)^3$ clauses up to repetition.

Your bound is not correct. Consider the case where some variable $X$ occurs positive in half the clauses and negative in the other half. This leads to roughly $\frac{m^2}{4}$ edges for $X$ alone. What is correct, however, is your suspicion that the parameter dependence is superlinear.

The reduction can be modified such that $|V|=3m+2n$ and $|E|=6m+n$. This would lead to a linear dependence of $k\_{IS}$ on $k\_{3-SAT}$. Consequently, with these parameterizations, independent set does not have a subexponential algorithm unless 3-SAT has.

However, there appears to be a further problem: The ETH uses a different parameterization. Namely just the number of variables, disregarding the number of clauses. I am not an expert in ETH. Possibly the sparsification lemma can help here.

---
Tags: complexity-theory, 3-sat, parameterized-complexity
---


# Question
Title: Distributed MST Construction in O(log log n) Rounds in a Clique
I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.

It shows by induction on k (phase number), that the spanning tree, for every cluster F (from phase k), is indeed an MST fragment of that cluster of vertices.

The claim is of course trivial for the base case, as the clusters are singletons of vertices. To show the induction step, it suffices to show that each edge $e$ (where $X\left(e\right)=\left(F\_{1},F\_{2}\right),\ F\_{1}\in\hat{F\_{1}},\ F\_{2}\in\hat{F\_{2}}$, where $F\_{1},F\_{2}$ are the original clusters, that is, the connected components of the previous round, now contracted into one vertex, and $\hat{F\_{1}},\hat{F\_{2}}$ are their super clusters, that is, the connected components containing them, created as part of this procedure in phase $k$) chosen by the procedure Const\_Frags is indeed a minimum weight outgoing edge (MWOE) of either $H\_{1}=\underset{F\in\hat{F\_{1}}}{\bigcup}F$ or $H\_{2}=\underset{F\in\hat{F\_{2}}}{\bigcup}F$. They assume wlog that $e$ was chosen as part of $F\_1$'s $\mu$ lightest outgoing weight edges, and want to show that $e$ is indeed the MWOE of $H\_1$. So they assume otherwise, that there exists $e'$ of lower weight than $e$ that is outgoing from $H\_1$.

What I don't understand is, why do they assume that $e'$ is of cluster $F\_1$ as well? The only thing we know about $e'$ is that it is outgoing from $H\_1$. This means that it **can** be outgoing from another cluster- $F'\in\hat{F\_{1}}\backslash\left\\{ F\_{1}\right\\} $. I would appreciate any help! thanks!

# Answer
I think I've found an answer, so will post here what I have. My proof seem to cover both scenarios I've mentioned. I still think their proof is incomplete. But in case I'm wrong, I would love to be corrected.

Similar to them assuming there is $e'$ outgoing from $F\_1$, I assumed there was $e'$ outgoing from $F\_3$ that is in $\hat{F\_{1}}$, of lower weight than $e$.

If it was chosen, than it happened before choosing $e$, since its lighter. But then we get a contradiction to $e'$ being outgoing of $H\_1$. So it wasn't chosen. If it wasn't chosen because it created a cycle, then it's yet again a contradiction to it being outgoing from $H\_1$, since if it created a cycle, then $F\_3, F\_4$ were already merged by the time we reached $e'$, and therefore when we reached $e$ as well.

Therefore we're only left with the option that it was deemed "dangerous" (and therefore removed). Then either $e'\notin\mathcal{A}\left(F\_{3}\right)$ or $\hat{F\_{3}}$ was finished by the time we reached $e'$ .

If $\hat{F\_{3}}$ was finished , then by the time we get to $e$ (which happens after $e'$, as $e'$ is lighter). But we assumed $F\_3$ is part of $H\_1$ by the time we reach $e$, therefore $\hat{F\_{1}}$ is also finished, which is a contradiction to it being unfinished.

Then $e'\notin\mathcal{A}\left(F\_{3}\right)$. This can happen for two reasons (as per their proof):

* There exists a lighter (than $e'$) $e''$ in $\mathcal{A}\left(F\_{3}\right)$ (such that $e''$ touches the same base fragments $e'$ touchs, which means its basically the same logical edge, just of lower weight). Therefore since $\hat{F\_{3}}$ wasn't finished, and there were no cycles, $e''$ was added earlier than $e'$ and therefore than $e$. But then by the time we reach $e$, $e'$ is no longer outgoing from $H\_1$. Contradiction yet again.
* Then there exists $\mu$ lighter edges in $\mathcal{A}\left(F\_{3}\right)$. Let $e''$ be the heaviest there (that is still lighter than $e'$ and therefore than $e$). Therefore after inspecting $e''$, $\hat{F\_{3}}$ is deemed finished, which is yet again a contradiction.
> 1 votes

---
Tags: algorithms, graphs, distributed-systems, minimum-spanning-tree, clique
---


title: Help with graph search problem

text:
# Question
Title: Help with graph search problem
For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know much about, to solve it).

As input we obtain a matrix (3x4) of connections ("|" or "-") which we must decode in the least amount of movements, to avoid that the bomb explodes. As an output inform one of the possible solutions.

The decoding consists in that the matrix must contain only characters "-". To achieve this they tell us that if we move an element of the matrix, both the values of the column and row of the matrix change. For example if I move the element (0,0) of the matrix in this case the "-" change to "|" and vice versa in the column 0 and row 0. In the image (where (1) represents the input matrix and (2) the decoded matrix) a solution to inform would be:

`move (0,3) and then (2,1)`

How to design an algorithm that solves this problem without using backtracking directly?

# Answer
"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem.

For this problem, think of a matrix, or a state, as a node in the graph. The pseudocode might look like this:

* Push the "input node" into a queue.
* While desired output node is not found:
    + Pop an element from the queue
    + Go through all the "moves" that could be done on that node. For a 3x4 matrix there would be 12 possible moves.
    + Push the results of each move into the queue.

Hope this helps!
> 1 votes

---
Tags: algorithms, graphs, backtracking
---


# Question
Title: Finding longest subset arithmetic progression with given difference
Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried using sets to solve this but I can't find a solution faster than $O(n^2)$. For example, I have tried adding all items in the array to a `TreeSet`. This automatically orders the elements, after which I brute force check all the possible sequences. Am I on the right lines or is there a better approach?

# Answer
> 3 votes
Using a hashtable, you can solve this in $O(n)$ expected time, as follows:

* Fill a hashtable $H$ with the given numbers.
* Go over all numbers in the list. For each number $x$, if $x-D \notin H$:
* + Go over the numbers $x + D, x + 2D, x + 3D, \ldots$ until you find a number not in $H$.

The running time of the first step is $O(n)$. As for the second step, the potentially expensive step is the sub-step. However, in this sub-step we go over each element in the list at most once (we check $y$ only for $x = y-aD$, where $a$ is the maximal integer such that $y-aD \in H$), and so the second step takes $O(n)$ time.

Without using a hashtable but assuming that the list is sorted, we can solve this in $O(n)$ time as follows:

* Go over all numbers in the list. For each number $x$, add an edge to $x+D$ if $x+D$ is in the list.
* Go over all numbers again. For each number $x$, if there is no edge pointing at $x$, follows the path starting at $x$ and calculate its length.

Using two pointers, we can implement the first step in $O(n)$. (The first pointer points at $x$, the other one is looking for $x+D$.) The second step takes $O(n)$ time for the same reason as in the hashtable algorithm.

Since it takes $O(n\log n)$ time to sort the list, this solution runs in time $O(n\log n)$. Using the fast $O(n\log\log n)$ integer sorting algorithm, we obtain a solution running in time $O(n\log\log n)$.

---
Tags: binary-trees, sets
---


# Question
Title: Assembly writer vs compiler in VLIW architecture
I read this sentence in a book:

> In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel.

What is the difference between assembly writer and compiler? Would an assembly writer also mean the same as assembler?

# Answer
The "assembly writer" in that book is a human software developer who writes code in assembler language.
> 33 votes

# Answer
> In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel

The meaning of this sentence is that in VLIW architecture, assembler (machine) code defines which instruction will be executed in parallel, so it's fixed at the time assembly code is written by a human or generated by a compiler.

This differs from super-scalar cpus, where instructions may be executed in parallel, this is a decision made by CPU each time it executes the instructions.

There are also CPUs that combine both approaches - Itanium2 is backward-compatible with Itanium, packing 3 instructions into VLIW word. But, afair, Itanium2 can execute two such packs in the single CPU cycle, and this decision is made at execution time.
> 10 votes

---
Tags: compilers, assembly
---


title: Running time correct with Omega?

text:
# Question
Title: Running time correct with Omega?
I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$.

Because: I know $\log(2^n) = n$. By that I would guess the same goes for $\log(n^{10})$ unimportant if the number is higher or not. By that it should be n. With this knowledge we already know it's higher than our $\Omega(\log^{10}(n))$.

We also know $\log(n)^2 = \log(n)$ again it will be higher or equal to our omega.

Is this correct?

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n = \Omega(\log^{10} n)$$

# Answer
Don't guess, but look at the definition which tells you that in order for $f(n) = \Omega(g(n))$ to hold, it must be the case that $\lim\_{n \to \infty} f(n)/g(n) \> 0$.

If I plug in $f(n)$ and $g(n)$ according to your description, I think I will get $\lim\_{n \to \infty} f(n)/g(n) = 0$. You should check whether I made a mistake and draw the appropriate conclusions.
> 1 votes

# Answer
When $\log^k(n) = \log (\log (...\log(n)))$,

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n \\ = \Theta((\log^2(n)+\log(n)+\log(n))\log(n)) \\ = \omega(\log^3(n)).$$

In fact, anything growing strictly slower than $\log(n)\log\log(n)$ will hold inside the $\omega$, so $\log^{10}(n)$ will also fit.

When $\log^k(n)=(\log(n))^k$, $$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n \\ = \Theta(\log^2(n)+\log(n)+\log(n))\cdot \log(n) \\ =\omega(\log(n)).$$

To see the big-$\Theta$ bounds are correct, verify that $$\lim\_{n\rightarrow \infty} \frac{(3 \log \log n + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{(\log \log(n) + \log(n)+\log(n))\log(n)}=O(1).$$ $$\lim\_{n\rightarrow \infty}\frac{(3 \log(n)\log(n) + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{(\log(n)\log(n)+\log(n)+\log(n))\cdot \log(n)}=O(1).$$

To see the $\omega$ bounds are correct: $$\lim\_{n\rightarrow \infty}\frac{(3 \log\log n + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{\log\log\log(n)}=\infty.$$ $$\lim\_{n\rightarrow \infty}\frac{(3 \log(n)\log(n) + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{\log(n)}=\infty.$$

You can derive the $O$ bounds and $\Omega$ bounds from the $\Theta$ bounds. I may have misplaced a few terms or two when typesetting; in which case, please point out.
> 1 votes

---
Tags: algorithms, runtime-analysis
---


# Question
Title: Finding a language that is $NP^L$-complete
I'm trying to prove a theorem and as a lemma I would like to identify an $NP^L$-complete language. I was thinking something like a machine that can decide $SAT$ equipped with an oracle for $L$ can decide every language in $NP^L$, but I'm not sure how to formalize this. Here's my attempt at doing so

$$ SAT^L = \\{\text{satisfiable boolean formulas with some clauses as }L(x\_1, \dots, x\_k)\\}$$

The clauses that are of the form $L(x\_1, \dots, x\_k)$ are queries that are true if and only if $(x\_1 \cdots x\_k) \in L$.

I think $SAT^L$ is $NP^L$-complete, for any language $L$, but I don't know how to prove this. It's of course in $NP^L$ since we can take a witness assignment and check it, and we can check the $L(\cdot)$ predicates with a query to our oracle to $L$. I'm not sure how to prove $NP$-hardness though.

I was thinking of just modifying Cook-Levin's construction so that I could add additional clauses to the formula of the form $L(x\_1, \dots, x\_k)$ when encoding the computation graph of an NTM $M^L$ but I'm not sure if this works in general, and is honestly more of a rough idea than anything else. This construction seems to be pretty sensitive to the "implementation" of the oracle queries, so I'm not sure how to make this rigorous.

Is there a more standard example of a $NP^L$-complete language?

# Answer
> 2 votes
What you are looking for is a relativization of the Cook-Levin theorem in the sense that you consider SAT and NP relative to an oracle for $L$. You can find the answer to that in this answer, point number 2. There you get (an extension of) Circuit-SAT as a complete language; reducing this to your version of SAT should not be too hard.

Note that, as mentioned in the linked answer, this is a bit different than a relativization in the sense that it is the *reduction* which possesses an oracle for $L$.

---
Tags: np-complete, satisfiability, relativization
---


# Question
Title: Is there any real difference between a compiler and an assembler?
Is there any difference between the two? As per Ullman's book, compilers convert one language to another (usually low level) language, and so does an assembler. How are the two different?

# Answer
An assembler translates assembly code to machine code. The translation is mechanical, and can be done in only one way. In contrast, a compiler has more freedom when it compiles the relevant programming language - it can optimize, for example, and even non-optimizing compilers produce different code. Also, compilers can be written in a way that separates the "front-end" (corresponding to the programming language) and the "back-end" (corresponding to the computer architecture), whereas with assemblers the two are always the same.
> 19 votes

# Answer
The bottom line is that it is more *fun* to write a compiler than an assembler. Assembly languages are usually designed to be nearly trivial to parse and type check and tend to involve a lot of table-driven generators ("the opcode for add is 01110", "for load instructions the destination operand register is specified by bits 17 through 21"). Usually the most interesting part of an assembler is the part that resolves symbolic labels into numbers.

*However*, most assemblers can do a small amount of arithmetic (adding together symbolic labels with small constants, for example) and most assemblers either have or are integrated with a macro processing facility. (On most Unix systems the macro feature is actually provided by running the C pre-processor over the assembly before passing it to the assembler proper.)

The MIPS assembler had to go a step beyond that and made some interesting code generation decisions and did a small amount of optimization. The MIPS machine language requires different code sequences to load different constants, for example, and so the assembler had to choose the code sequence after constructing the constant. Further, MIPS machine code had the notion of *delay slots*, but it was the responsibility of the assembler to abstract these away and present a more "normal" abstract assembly language to the compiler. So the MIPS assembler needs to do some local instruction scheduling.

The distinction is further blurred by some of Norman Ramsey's work, in particular his C-- portable assembly language. (The relevant paper is Ramsey and Peyton Jones, "A Single Intermediate Language That Supports Multiple Implementations of Exceptions", *Prog. Lang. Impl. and Dsgn.*, (PLDI-21):285–298, 2000.) And finally, there is also a Typed Assembly Language from David Walker and Greg Morrisett with an assembler that can guarantee memory safety.
> 12 votes

# Answer
A bit of simplified answer here, the reality is more complicated. I would expect the difference between an Assembler (A) and a Compiler (C) to be among other things:

1. One line of source code relates directly to one CPU opcode (A) or not (C)
2. Highly dependent on the actual CPU (A) or machine independant (C)

We tend to call assembly language "low level" and the source language a compiler understands "high level" (this is gross simplification, but still).

In assembly language you could as example do an add operation by saying:

* add a,b (for one specific CPU)
* add R5,R6 (for a different CPU)
* add (A5),D2 (for a different CPU)

In a high level language you might write:

* x = y + z ;

And this could result in one instruction or hundreds of instructions depending on a number of circumstances, one is what CPU the compiler creates instructions for.

As you can see the assembly source language is most often: (A) one line of source code gives one line of CPU opcodes and it very much depends on which CPU you are targeting. A high level language (C) compiler handles all these details for you -- one line of source code could become zero, one or many CPU opcodes and the compiler handles the details of what the CPU can do.

A compiler today often consists of several different stages. They could be named frontend / backend or beeing called other things. I typically see them as four stages:

1. The first stage reads the actual source code and creates an internal representation. This stage knows the actual source language.
2. The second stage looks at the internal representation and does a number of optimizations. Nowadays, the compiler would typically look for making the program faster and not caring for if it gets larger. The optimizing is done on the internal representation. Interestingly, parts of this could be generic for several different languages.
3. The third stage takes the internal representation and creates actual code for the selected CPU. There might be several different versions of this stage, targeting different CPU-s. In effect you could write source code once and then compile it for different CPUS-s.
4. Final preparations for "packaging" the program (this stage could be a linker).

Writing good compilers is a highly skilled profession -- making a toy language compiler can be done in an afternoon by an amatuer (or well, slightly longer).
> 2 votes

---
Tags: terminology, compilers
---


# Question
Title: How to draw an LTS based on the parallel process "|" in CCS Milner's logic?
I'm trying to provide a Hennessy-Milner logic formula for CCS expressions that are not (strongly) bisimilar. An example with a sketch:

> For each of the following CCS expressions, decide whether they are strongly bisimilar and if no, find a distinguishing formula in Hennessy-Milner logic.

$b.a.Nil+b.Nil$ and $b(a.Nil+b.Nil)$

I first draw these two to get a better understanding as follows (excuse my awful drawing skills but I couldn't figure out how to put it in LaTeX so I used draw.io):

You can clearly see the Right Hand Side could do $b.b$ but the Left Hand Side can't respond to that. And my distinguishing HML formula is $\[b\]\<b\>tt$. On the LHS you get: $\[b\]\\{b.a.Nil+b.Nil\\} = \emptyset$ and on the RHS you get: $\[b\]\\{b(a.Nil+b.Nil), a.Nil+b.Nil\\} = b(a.Nil+b.Nil)$. Therefore this is a valid distinguishing formula.

Hopefully, I made what the exercise is about clear. Now, the following CCS expressions that I have to distinguish are:

$a.Nil|b.Nil$ and $a.b.Nil + b.a.Nil$.

I know how to draw the RHS because the `+` denotes a choice but I don't have any idea of how the parallelism work in CCS and couldn't understand it after reading. My guess is the following but it doesn't make sense and is probably wrong:

Could someone help me understand how to sketch the LHS so that I can complete this exercise?

**P.S My tags are probably not correct but I couldn't find any tags to Hennessy-Milner logic, so feel free to edit them.**

# Answer
The last LTS in your question is wrong. It should be a diamond-shaped graph, where on one side you perform action $a$ then $b$, and on the other you perform action $b$ then $a$, both sides leading to $\sf Nil$.

This is because the $a$ action is run in parallel w.r.t. the $b$ action, so we get all the possible "interleavings" between such events.

The fixed LTS you posted in the comments looks right, instead.
> 2 votes

---
Tags: formal-languages, logic, ccs
---


# Question
Title: I have trouble translating Turing machine language, can you help me break down language notation to English?
My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing machine to recognize the language {0n1n | n ≥ 0}.

I have found this guide on a similar problem however I cannot grasp what is going on and what is required from the language statement. Any help in regards to how to read the specified language effectively would be appreciated.

# Answer
When $s$ is a symbol and $n$ is a natural number, "$s^n$" means "$s$ repeated $n$ times". So you're being asked to recognize the language of all strings that consist of $n$ zeros followed by $n$ ones, for any possible value of $n\geq 0$. That is, $\\{\epsilon, 01, 0011, 000111, 00001111, \dots\\}$, where $\epsilon$ denotes the empty string (some people write $\lambda$ for the empty string, instead).
> 3 votes

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Clarification on interplay between cache line size and read/write sizes
Say that you have cache lines with the size of 64 bytes and a set-associative or directly mapped cache. Let's also say that the word size is 8 bytes.

According to my understanding, we use a number of the most significant bits of a memory address in order to determine where in the cache to place the data. Am I correct in believing that, if I want load data starting from, for example, address 30, then all data starting from address 0 to 63 will be loaded into a cache line? Or will all data from address 30 to 93 be loaded?

If the former is the case, I assume that, if an instruction to load 16 bytes from address, say, 60, then this forces us to load two 64 byte cache lines (one line 0-63 and another 64-127). Is that correct or have I misunderstood something? Also, is this something that often occurs or are there reasons for why that isn't the case?

# Answer
Cache lines always start at a byte address that is a multiple of the cache size, like 0, 64, 128 etc. If you need 8 bytes starting at byte 30, then the cache line containing bytes 0 to 63 will be loaded.

If you need 8 bytes starting at byte 60, then you need bytes from two cache lines, so the cache line from byte 0 to 63 is loaded, then the line from byte 64 to 127. (Since this is more complicated, it very much depends on the CPU how long this will take, usually anything from "a little bit longer" to "a lot longer". Compilers will usually try to align data to minimise the cost of data straddling cache lines).

Sometimes the cache line size is bigger than the amount of bytes that can be read from RAM in one operation (say 64 byte vs 32 bytes). Some CPUs can then read the "right" 32 bytes first and deliver the data to the CPU, while the rest of the cache is being loaded. So if you want bytes 40..47 the CPU may be able to load bytes 32..63 first, then give the 8 bytes to the CPU while loading the second half.
> 2 votes

---
Tags: memory-management, cpu-cache, memory-access
---


# Question
Title: How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?
For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{denominator sum}}$ is maximized. As in this case, selecting $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$ will result in $\frac{4+2+1}{2+3+2}$ = 1 which is maximized.

How can I select $k$ fractions which will always result in the maximum $\frac{\text{numerator sum}}{\text{denominator sum}}$ value?

Edit:

* Attempt 1: Sorting fractions in descending order. This passes a few test cases but that it's. This can also be proven by example that it is not the optimal solution. Let's say we have a list of 3 fractions sorted in descending order, $\frac{1}{2}$, $\frac{20}{59}$, $\frac{1}{3}$ and $k = 2$. The optimal solutions is $\frac{1+1}{2+3}$, not $\frac{1+20}{2+59}$.

# Answer
For a list of fractions, define the ratio as (sum of numerator) / (sum of denominator).

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

We have obvious lower and upper bounds for r (the k-largest and the largest value of any fractions). With binary search we can easily find a list with maximum ratio.

Responding to some comments: What I presented is the basic idea. There is plenty of room for improvement.

For example "we pick the k fractions where x - ry is largest" - that can easily be done without sorting the array, much faster than n log n. Start like Quicksort, but only process subarrays that you need to determine the k largest values.

And it's not just binary search, because each time you actually find a list of fractions and can update the lower or upper bound for r or both. (For example if the lower and upper bound were 6.0 ≤ r ≤ 10.0, you look for a list with ratio 8.0 and only find one with ratio 7.6, then in the next search you know 7.6 ≤ r \< 8.0 is possible).

Since the lower bound for r is one that was actually achieved, you can also check which is the smallest eps for which you would have put a different fraction in the top k list of fractions.
> 2 votes

# Answer
Based on insights in the other answers, one simple and quite efficient algorithm is:

1. Set $r = 0$.
2. Choose the top $k$ values of $x\_i - ry\_i$ (using, e.g., quickselect in $O(n)$ time).
3. Sum the chosen $x\_i$ into $X$ and the $y\_i$ into $Y$.
4. If $X - rY \> 0$:
    * Set $r = X / Y$. (This will strictly increase $r$.)
    * Go to step 2.

The idea is to determine a set of lines that produce the highest possible sum at the current $r$ value, and then "slide right" along the sum of those lines (which is also a line) until it intersects the $x$ axis: where that intersection occurs is an achievable $r$ value, but it may not be the maximum possible such value, because there may be some other combination of lines that does even better. When this is no longer possible, we have found the maximum $r$.

Every time $r$ is successfully updated in step 4, at least one of the chosen $k$ lines is replaced at the following step 2 with a different line that is above it everywhere at and to the right of the current $r$ value; the replaced line will never be chosen again, so the loop executes at most $n-k$ times. Step 2 can be performed using quickselect in $O(n)$ time, for $O(n^2)$ time overall (and just $O(n)$ time when $n-k = O(1)$). Note that because we do not necessarily process each segment of the piecewise linear maximum function, there will be many inputs for which the loop executes less than the full $n-k$ times.

## Removing dominated lines

It is also possible to get rid of "dominated" lines after step 2 without altering the time complexity -- this should speed things up in practice. Line $i$ is dominated if $x\_i - ry\_i \< A$ and $y\_i \> B$, where $A$ is the smallest of the $k$ chosen $x\_i - ry\_i$ values, and $B$ is the largest of their denominators $y\_i$.
> 2 votes

# Answer
Extending gnasher's observation:

> Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?
>
> Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

For each fraction $\frac{x}{y}$ the graph of $x - ry$ against $r$ is a straight line. The sum of the $k$ highest lines is a convex monotonically decreasing piecewise linear function with discontinuities only possible when two of the straight lines intersect. Therefore we can take the pairwise intersections of the lines to find all values of $r$ at which the $k$ highest lines might change, use bisection as described by gnasher to find the linear piece where the sum crosses zero, and then interpolate linearly within that piece to find the exact value of $r$.

Cost:

* $\Theta(n^2)$ to find the intersections
* $O(n^2 \lg n)$ to sort them
* Finding the $k$ highest can be done in $O(n)$ time using quickselect, so $O(n \lg n)$ time for the bisection
* $O(n)$ time for the final interpolation

---

As an optimisation, it's not necessary to do the full sort. Using quickselect to partition at the median, you can test whether the sum at that median value is above or below zero and then recurse only on half of the intersections. This gives an algorithm with $\Theta(n^2)$ running time.

---

This description of the curve also gives a bisection algorithm without preprocessing. If you have a value of $r$ where the curve is above the line and a value where it's below the line, you can extrapolate the linear segments of the line at those two values to find their intersection point, which must be at an intermediate value of $r$. When both values are on the same linear segment you interpolate to find the root. There is an important subtlety in the selection of the top $k$ lines at $r$: depending on whether it's a lower or an upper bound you need to break ties differently to get the correct gradient.

This takes at most $n - k$ steps (as observed by j\_random\_hacker \- I'm kicking myself for not spotting it), so $O(n^2)$ time overall, but as with the algorithm they present it has a good chance to do better than worst case.
> 1 votes

# Answer
If you sort the fractions by their ratios in descending order, and take the k fractions with largest ratio, that gives you a lower bound. Why would this not be optimal?

The k-th fraction, the k-1st fraction and so on pull the average down. Say k = 10, you have five fractions 100/10, five fractions 20/10, and 100 fractions 1/1. Taking the ten largest ratios gives a result 600 / 100 = 6. Taking the five largest, and five times 1/1 gives 505 / 55 \> 9. So you want some large ratios, combined with small numerators and denominators.

In my example, can we get a result of 7? We obviously take the five fractions with a ratio ≥ 7, giving 500/50. Assume we add 5 more fractions with a sum X / Y, then we need (500 + X) / (50 + Y) ≥ 7, or 500 + X ≥ 350 + 7Y, or 150 + X ≥ 7Y or 7Y - X ≤ 150. For each fraction x / y we define its "badness" as 7y - x, then we need to find 5 fractions with a total badness ≤ 150. We take the fractions with the least badness; if the sum is ≤ 150 then we found 10 fractions with ratio ≥ 7, otherwise there are no such 10 fractions. In any case, we may have found 10 better points, and we adjust the ratio we are looking for.
> 0 votes

---
Tags: algorithms, optimization, number-theory
---


# Question
Title: Type system for Query DSL with only simple GADTs: what typing judgments are needed?
## Background

I have several F# codebases with reasonably high level of complexity of code. In order to convince myself that the code is solid I do whatever I can to write as much of it as possible type-driven and pure (up to what I am able to determine is pure without much help from the compiler) and unit test it like crazy (thanks, FsCheck & Expecto). The style that has got me the furthest within the infuriating constrains of F# is to use a command/query DSL. The queries take a shape like:

```
type Query<'a> =
  | GetMyFoo of (Foo -> 'a)
  | GetMyBarById of Guid*(Bar -> 'a)
  | GetMeNBazs of int*(list<Baz> -> 'a)

```

and so on. Inevitable I want a functor instance. The queries grow large and the functor instance is very rote, making me long for `deriving` a la Haskell. More than that though, It doesn't feel like we have separation of concerns here, since we are mingling in the handler of the query results everywhere. I would really like to be able to represent a query *not* as a functor at all, but simply as a GADT, and have one canonical functor instance for a query paired with a handler (Idris syntax):

```
record HandledQry (q : Type -> Type)  (a : Type) where
  constructor HandleQry
  qry : q i
  handle : i -> a

```

whose functor instance I do not mind writing once. Or perhaps I would use a freer monad since the ideas from that paper resonate very much with this. *The exact approach, whether to use `HandledQry` or a freer monad etc. is not the concern of this question; nor how to encode it into F#.*

## The Meat of It

I have an idea for how to encode simple GADTs in F#. However it does involve some localized exploitation of weaknesses in F#'s type system and some boilerplate code. Given that unsoundness is an excellent way to give rise to bugs, I am not interested in handrolling this F# code: I would like to generate it from a small, specialized DSL, which supports nothing but a subset of GADTs, something like this (contrived syntax similar to Idris):

```
%given_type Foo
%given_type Guid
%given_type Bar
%given_type (List Baz)

data Query : Type -> Type where
  | GetMyFoo : Query Foo
  | GetMyBarById : Guid -> Query Bar
  | GetMeNBazs : int -> Query (List Baz)

```

The idea is this. Existing F# types could be declared for use in the DSL as primitives, while being opaque to the DSL's compiler (it knows `Foo : Type`, and that is all). The DSL's compiler could make sure that the GADT it has been given is sound, and then generate F# code to use it, encapsulating the abuses of F#'s type system. However it is critical to me that the logic of the compiler be sound and based on type theory. To this end, I have been studying up on type theory. I am making progress, but it is a long road, and what we have here in my proposed DSL seems to be an odd mix of relatively few features, and yet those from a somewhat more advanced type system, with more basic features missing. I am not trying to build a full functional language right now and so what I am doing is a bit esoteric and unique.

It seems to me that we do not need:

* The lambda abstraction. The data constructors' type could be a function type, but functions, with bound parameters and bodies, never occur in any of the code I have as inputs or outputs of the queries so I am not interested in supporting them right now.
* (Full-on) dependent types. I have no idea how to encode a fuller version of dependent types into F#, nor do I have a need for them now (though as I understand it GADTs are a weak species of existential types).
* Product types (at least for starters). If the query takes multiple inputs, I can just use a curried function and translate it to e.g. `int*string` when I compile it to F#.
* Recursive or inductive types. `Query` should never have to reference itself and the other types are opaque.
* Parametric polymorphism. The cases of the query can always specific a concrete type for my purposes (and according to what I know how to encode in F#).
* The rest of an actual lambda calculus; I am only interested in defining types in this DSL (for now).
* I'm thinking that what I've got here is less than the full power of GADTs even in Haskell.

What I do need is:

* Sound type judgments, e.g. no `Type : Type` junk. This has been a stumblingblock in researching this; most intros to dependent types use `Type : Type` for ease (which I can understand in a tutorial) and I haven't found stuff to introduce just GADTs.
* At-least-somewhat-generalized algebraic data types.

I believe I am capable of translating whatever the rules are from the syntax of natural deduction into sound Idris code.

## tl;dr

**What type judgments are needed for a small type system that has only simple GADTs and primitive types?**

# Answer
> 1 votes
Lennart Augustsson and Kent Petersson 1994 present syntax and type rules for a small functional language which is basically just lambda calculus with GADTs. They have two kinds of judgments, one to indicate that "the expression `e` has type `T` in the type environment $\Gamma$" and the other to indicate that "the declaration `d` generates the type environment $\Gamma$". Using the second they have rules for type declarations and declaration sequencing, i.e. rules giving the ability to define types. Using the first they define typing rules for expressions: variables, constructors, pattern matching, and application.

**Note**: The paper is marked as `DRAFT` and does not seem to be as rigorous as some, but nevertheless has much valuable material.

---
Tags: compilers, type-theory, type-checking, typing, domain-specific-languages
---


title: Is a "local" version of 3-SAT NP-hard?

text:
# Question
Title: Is a "local" version of 3-SAT NP-hard?
Below is my simplification of part of a larger research project on spatial Bayesian networks:

Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses between the first and last clause in which it appears (where $k$ is a natural number).

Now consider the subset $(3,k)\text{-LSAT} \subseteq 3\text{-SAT}$ defined by the criterion that for any $C \in (3,k)\text{-LSAT}$, every variable in $C$ is $k$-local. For what $k$ (if any) is $(3,k)\text{-LSAT}$ NP-hard?

---

Here is what I have considered so far:

(1) Variations on the method of showing that $2\text{-SAT}$ is in P by rewriting each disjunction as an implication and examining directed paths on the directed graph of these implications (noted here and presented in detail on pp. 184-185 of Papadimitriou's *Computational Complexity*). Unlike in $2\text{-SAT}$, there is branching of the directed paths in $(3,k)\text{-LSAT}$, but perhaps the number of directed paths is limited by the spatial constraints on the variables. No success with this so far though.

(2) A polynomial-time reduction of $3\text{-SAT}$ (or other known NP-complete problem) to $(3,k)\text{-LSAT}$. For example, I've tried various schemes of introducing new variables. However, bringing together the clauses that contain the original variable $x\_k$ generally requires that I drag around "chains" of additional clauses containing the new variables and these interfere with the spatial constraints on the other variables.

Surely I'm not in new territory here. Is there a known NP-hard problem that can be reduced to $(3,k)\text{-LSAT}$ or do the spatial constraints prevent the problem from being that difficult?

# Answer
> 14 votes
$(3,k)\text{-LSAT}$ is in **P** for all $k$. As you have indicated, locality is a big obstruction to NP-completeness.

---

Here is a polynomial algorithm.

Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c\_1\wedge c\_2\cdots \wedge c\_m$, where $c\_i$ is the $i$-th clause.
Output: true if $\phi$ becomes 1 under some assignment of all variables.
Procedure:

1. Construct set $B\_i$, the variables that appear in at least one of $c\_i, c\_{i+1}, \cdots, c\_{i+k}$, $1\le i\le m-k$.
2. Construct set $A\_i=\\{f: B\_i\to\\{0,1\\} \mid c\_i, c\_{i+1}, \cdots, c\_{i+k} \text{ become 1 under} f\\}$.
3. Construct set $E=\cup\_i\\{(f, g)\mid f\in A\_i, g\in A\_{i+1}, f(x)=g(x)\text{ for all }x\in B\_i\cap B\_{i+1} \\}$
4. Let $V=A\_1\cup A\_2\cdots\cup A\_{m-k}$. Consider directed graph $G(V,E)$. For each vertex in $A\_1$, start a depth-first search on $G$ to see if we can reach a vertex in $A\_{m-k}$. If found, return true.
5. If we have reached here, return false.

---

The correctness of the algorithm above comes from the following claim.

**Claim.** $\phi$ is satisfiable $\Longleftrightarrow$ there is a path in $G$ from a vertex in $A\_1$ to a vertex in $A\_{m-k}$.
**Proof.**
"$\Longrightarrow$": Suppose $\phi$ becomes 1 under assignment $f$. Let $f\_i$ be the restriction of $f$ to $B\_i$. Then we have a path $f\_1, \cdots, f\_{m-k}$.
"$\Longleftarrow$": Suppose there is a path $f\_1, \cdots, f\_{m-k}$, where $f\_1\in A\_1$ and $f\_{m-k}\in A\_{m-k}$. Define assignment $f$ such that $f$ agrees with all $f\_i$, i.e., $f(x)=f\_i(x)$ if $x\in B\_i$. We can verify that $f$ is well-defined. Since $c\_\ell$ becomes 1 for some $f\_j$ for all $\ell$, $\phi$ becomes 1 under $f$.

---

The number of vertices $|V|\le 2^{3(k+1)}(m-k)$. Hence the algorithm runs in polynomial time in term of $m$, the number of clauses and $n$, the number of total variables.

---
Tags: np-hard, satisfiability, polynomial-time, 3-sat, 2-sat
---


# Question
Title: Converting a number from N to 0 in binary
Trying to solve this problem since 2 days. Still unable to figure out even a basic approach.

Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. Given a binary value of a number with length $M$ ($0$ indexed), we can:

1. flip the $i$th bit from $0$ to $1$ or $1$ to $0$ only if the $(i+1)$th bit is 1 and all bits at positions from $i+2$ to $M-1$ are NOT $1$, or
2. flip the rightmost bit unconditionally.

So the problem is to figure out the minimum number of steps to do the conversion.

For example: if $N=8$, then its binary representation is $1000$.

So to convert $1000$ to $0000$, the following steps apply:

```
1 -  1001 (flipping the rightmost bit unconditionally).
2 -  1011 (flipping bit at position 2 as bit at position 3 = 1 and there are no more 1 after it. There are no more characters infact. It is the last character).
3  - 1010 (flipping the rightmost bit unconditionally).
4  - 1110 (flipping the 1st bit as 2nd bit is 1 and no other bits after that are 1)
5  - 1111 (flipping the last bit unconditionally).
6  - 1101 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
7  - 1100 (flipping the last bit unconditionally).
8  - 0100 (flipping 0th bit as 1st bit is 1 and no other 1 after 1st bit).
9  - 0101 (flipping the last bit unconditionally).
10 - 0111 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
11 - 0110 (flipping the last bit unconditionally).
12 - 0010 (flipping 1st bit as 2nd bit is 1 and no other 1 after 2nd bit).
13 - 0011 (flipping last bit unconditionally).
14 - 0001 (flipping 2nd but as 3rd bit is 1 and no other bit after 3rd bit).
15 - 0000 (flipping last bit unconditionally).

```

So the result is $15$ as it took $15$ steps.

Unable to solve this problem. Please help.

# Answer
I think you can just do a simple breadth-first-search on this. First note that:

* There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop.
* It doesn't make sense to do move #2 twice in a row.

The important thing to do while searching is to note whether the number we've arrived at was by doing move #2 (otherwise we'd get stuck in a loop). So here's a pseudocode:

* Put the current number into a queue with flag 0
* While the dequeued number is not zero:

+ If you can do move #1 on the dequeued number then do move #1 and put that in a queue with flag 0
    + If the dequeued number's flag is 0, then do move #2, and put that in the queue with flag 1
> 2 votes

# Answer
First, we have some basic observations:

1. The minimum number of steps to convert $N$ to $0$ equals to the minimum number of steps to convert $0$ to $N$.
2. To convert $0$ to $N$, the optimal way would be to apply Operation 1 and 2 alternatively.

Now consider the bit sequence $b\_1\ldots b\_m0$. After performing Operation 1 and 2 alternatively, we get

$$b\_1\ldots b\_m0\rightarrow b\_1\ldots b\_m1\rightarrow c\_1 \ldots c\_m1\rightarrow c\_1\ldots c\_m0\rightarrow d\_1\ldots d\_m0\rightarrow d\_1\ldots d\_m1\rightarrow\cdots$$

where $c\_1\ldots c\_m$ is the bit sequence obtained by applying Operation 1 on $b\_1\ldots b\_m$ and $d\_1\ldots d\_m$ is the bit sequence obtained by applying Operation 2 on $c\_1\ldots c\_m$. Note every time we perform two operations, one operation is applied on the sequence of the first $m$ bits. That is to say, if we denote by $f(x\_1\ldots x\_m)$ the minimum number of steps to convert $0\ldots 0$ to $x\_1\ldots x\_m$, then we have

$$f(x\_1\ldots x\_m)=2f(x\_1\ldots x\_{m-1}) +\text{the number of the rest steps to convert the last bit to }x\_m.$$

Easy to see the number of the rest steps to convert the last bit to $x\_m$ depends on the parity of $f(x\_1\ldots x\_{m-1})$. If $f(x\_1\ldots x\_{m-1})$ is even, after performing $2f(x\_1\ldots x\_{m-1})$ operations, the last bit is $0$, so the number of the rest steps to convert the last bit to $x\_m$ is exactly $x\_m$. Otherwise, it is $1-x\_m$.

Now it is sufficient to use the recurrence above to calculate the minimum number of steps to convert $N$ to $0$ in $O(\log N)$ time if you don't care the detailed operation sequence.

Finally, for fun, you can prove using mathematical induction:

$$f(x\_1\ldots x\_m)=x\_12^{m-1}+(x\_1\oplus x\_2)2^{m-2}+(x\_1\oplus x\_2\oplus x\_3)2^{m-3}+\cdots+(x\_1\oplus\cdots\oplus x\_m).$$
> 1 votes

---
Tags: algorithms, bit-manipulation
---


# Question
Title: What does "Kan" mean in "Kan operations"?
I'm studying Cubical Type Theory and I see the word "Kan operations" (ref1, ref2, ref3, and there are many more), which is related to "adding a cap to a tube" (can be also explained as "given a path between `a` and `b`, and two paths that are between `a` and `c`/`b` and `d` respectively, we can use Kan operations to get a path between `c` and `d`").

I wonder if there's any references that can explain where this "Kan" word come from -- what does it mean? Is that "Kan extensions" in Category theory?

# Answer
Kan operations are likely named after Daniel M. Kan, in analogy to concepts such as Kan extensions, Kan complexes, Kan fibrations, Kan condition, and many more. Kan also introduced adjoint functors.
> 1 votes

---
Tags: cubical-type-theory
---


# Question
Title: Computability: Proving a predicate is not recursively enumerable
Let P(p) \<=\> for each x, comp(p,x) is defined.

Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?

# Answer
Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false.

The rest of the answer assumes that "comp(p,x) is defined" is the same as "program $p$ halts on input $x$".

In order to show that your predicate is coRE-hard, you need to show that for every coRE predicate $Q$ there is a computable function $f$ such that $Q(z)$ iff $P(f(z))$. A predicate $Q$ is coRE if there is a computable function $q$ such that $Q(z)$ iff for all $x$, $q(z,x)$. Hence we need

> for all $x$, $q(z,x)$ iff for all $x$, $f(z)$ halts on $x$.

You take it from here.

(In fact, your predicate is $\Pi\_2$-complete.)
> 1 votes

---
Tags: computability, recursion, halting-problem, primitive-recursion, predicate-logic
---


# Question
Title: Number of ways of tiling a 3*N board with 2*1 dominoes problem
I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a doubt, why aren't we considering the below cases for the above problem?

In the solution only these cases are mentioned,

```
********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

```

But my question is there can be other case as well, like below, why aren't we adding them, because the problem asks for the number of possible cases-

```
********   AA*******   AA******   A*******   AB******   CC******
******** = BB******* + B******* + A******* + AB****** + AB******
********   CC*******   B*******   BB******   CC******   AB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)  +   f(n-2) +  f(n-2)

```

Why aren't we adding them? Thanks for your help.

# Answer
> 2 votes
These two cases are already counted in the recursive calls `g(n-1)`.

```
A****
A****
BB***
g(n-1)

```

`g(n-1)` counts all possibilities to fill the empty space in this ^ form. One way would be to fill it out like the following image, so this case already gets counted and you don't need to add another recursive call.

```
AC***
AC***
BB***

```

---
Tags: algorithms, data-structures, dynamic-programming, tiling
---


# Question
Title: Are "of the order of n" and "Big O" the same thing?
I am learning from the MIT course Introduction to Algorithms.

The professor says:

> Now, remember $\Theta(n)$ is essentially something that says "of the order of $n$".

What does "of the order of $n$" mean? Are "of the order of $n$" and "Big O" the same thing?

Please provide the name of any widely recognized textbook that contains detailed explanation about this.

# Answer
> 1 votes
the professor mentioned two methods used to measure asymptotic complexity.

$\Theta(n)$ is the order of n.

$O(n)$ is big O of n.

the professor explained

$\Theta(n)$

> gives you both the lower bound and an upper bound.

$O(n)$

> is just upper bound.

# Answer
> 8 votes
"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses *asymptotic* behavior, not approximate values of a function (e.g., $10n \in O(n)$, despite $10n$ being 10 times as larger as $n$). They can hardly be considered the same things. What the lecturer is trying to do here is supposedly give you some (hand-wavy) intuition as to how Big O notation works, but that should not replace you actually sitting down and learning the precise definitions.

As for your request regarding further reading on Big O notation, (in addition to the linked Wikipedia article) I suggest you take a look at our reference question.

---

**An addendum:** After listening to the video again, you can make out the lecturer say "of the order of $n$". This is the British English version of American English "on the order of" and carries the same meaning.

---
Tags: terminology, asymptotics, big-o-notation
---


# Question
Title: k-enclosing rectangle in two-colored point set
I was asked to write an algorithm for the following problem, and discuss complexity:

> * There are p points of two colours, black and white, in an n\*m grid.
> * Any cell in the grid can contain 0 or more points, of any colour.
> * We are looking for an axis aligned rectangle, having (0,0) as a corner, containing k black points, and maximizing the number of white points in it.

It was mentioned that this problem is famous and I can use any online resource.

So far, the closest I have found is this paper, which deals with finding exact colored k-enclosing rectangles, that don't necessarily have the origin as a vertex.

Maybe someone here will be able to point me to some resources that discuss this version of the problem?

# Answer
> 1 votes
Ok as you have a working solution but seem concerned by optimization, I will detail here how to do it very efficiently. I assume that your rectangle has to follow the discretized grid (I now have a doubt on it reading your question).

Let's build 2 $n \times m$ count arrays $NB$ and $NW$ which are the number of respectively black and white points in each cell. You can fill these arrays in $O(p)$ as you just have to consider any point and decide which value of the array you increment.

Then you build the 2 $n \times m$ accumulator arrays $RB$ and $RW$. $RB\[i, j\]$ and $RW\[i, j\]$ are the number of respectively black and white points in the rectangle (left=0, up=0, right=$j$, down=$i$). You can fill these arrays with a very simple DP using $NW$ and $NR$, in $O(nm)$. Note that computing row after row, and in the row looping on elements, you can break the latter loop whenever $RB \> k$.

The overall time complexity will be $O(max(p, nm))$.

---
Tags: algorithms, time-complexity
---


title: Prior probability in HMM

text:
# Question
Title: Prior probability in HMM
This is the HMM model considered in the question

And this is the emission probabilities for the respective states. There are two emission values, bringing an umbrella and not bringing an umbrella.

**Description of the question:**

The question considered the *initial state as sunny*. On *day 2*, the person *brought an umbrella*. On *day 3*, the person *didn't carry an umbrella*.

We have to find the probability that it's foggy on 3rd day.

Given: Prior probability of the caretaker carrying an umbrella is 0.5.

According to me, the answer to this question was addition of the terms in the red circles.

Where α1 = 0.8 * 0.1, α2 = 0.05 * 0.8, α3 = 0.15 * 0.3

**Problem I faced:** But the answer included dividing the answer I got by (0.5)2. That is, I guess they are dividing by the prior probability two times for the two transitions, but I'm not clear as to why they are dividing.

# Answer
Let $s\_2,s\_3$ be the states on the second and third days, and let $x\_2,x\_3$ be the indicators of carrying an umbrella on these days. Then $$ \newcommand{\Sunny}{\mathit{Sunny}} \newcommand{\Rainy}{\mathit{Rainy}} \newcommand{\Foggy}{\mathit{Foggy}} \newcommand{\Yes}{\mathit{Yes}} \newcommand{\No}{\mathit{No}} \Pr\[s\_3 = \Foggy \mid s\_1 = \Sunny, x\_2 = \Yes, x\_3 = \No\] = \frac{\Pr\[s\_3 = \Foggy, x\_2 = \Yes, x\_3 = \No \mid s\_1 = \Sunny\]}{\Pr\[x\_2 = \Yes, x\_3 = \No \mid s\_1 = \Sunny\]} $$ It seems you might have forgotten the denominator.
> 0 votes

---
Tags: machine-learning, probability-theory, hidden-markov-models
---


title: Proving recursion depth of merge sort

text:
# Question
Title: Proving recursion depth of merge sort
Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$. I think I can prove this by recurrence equation and the master theorem: $T(N)=2 T(n/2)+O(N) $ however i need to get $O(\log(n)) $. Basically I want only to calculate the complexity of the deviding and remove the conquer part from this equation. How can I do this? Or is there another way to prove the height of the recursion tree?

In the picture below you can see I want to prove the height from red to gray.

# Answer
> 2 votes
First of all, let me correct the recursion for the running time of merge sort: $$ T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) & \text{if } n \> 1, \\ \Theta(1) & \text{if } n = 1. \end{cases} $$ The corresponding recursion for depth is: $$ D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 & \text{if } n \> 1, \\ 0 & \text{if } n = 1. \end{cases} $$ (The value of $D(1)$ could also be $1$, depending on how you define depth.)

The solution of this recurrence is $D(n) =\lceil \log\_2 n \rceil$.

When $n$ is a power of 2, you can calculate the depth of the recursion tree by noticing that the value of $n$ decreases by a factor of 2 at each level. For the general case, the main observation is that the depth is monotone in $n$, using which you can easily conclude $D(n) \leq \lceil \log\_2 n \rceil$ by considering the smallest power of 2 which is at least $n$.

---
Tags: time-complexity, master-theorem
---


title: Reaching Shannon capacity of a channel

text:
# Question
Title: Reaching Shannon capacity of a channel
Suppose I have the following from alphabet $\mathcal{X} = \\{0 ,1\\}$ to $\mathcal{Y} = \\{0 ,1\\}$. The channel simply does

\begin{align} 0 \rightarrow 0&\quad \text{with probability 1} \\ 1 \rightarrow 0&\quad \text{with probability 1/2}\\ 1 \rightarrow 1&\quad \text{with probability 1/2} \end{align}

The classical capacity of this channel is given by the mutual information between the input register, $X$ and output register $Y$ maximized over input probability distributions, $p(x)$. That is,

$$C = \max\_{p(x)} H(Y) - H(Y|X)$$

The appropriate distribution turns out to be $(0.6, 0.4)$ and the capacity is $0.3219$ bits.

How does one actually use this result to practically communicate (in the asymptotic limit) over this channel at this rate? Does it mean that I should use input codewords that obey these statistics over the input alphabet for example?

# Answer
> 2 votes
Your channel is known as the Z-channel. Take a look at Marco Mondelli, S. Hamed Hassani, and Rüdiger Urbanke, How to Achieve the Capacity of Asymmetric Channels.

---
Tags: information-theory, communication-protocols
---