title: A question about NP and coNP

text:
# Question
Title: A question about NP and coNP
It is an open question if ***NP*** $\neq$ ***Co-NP*** but if the conjecture were proved, this would mean that ***P*** $\neq$ ***NP*** because ***P*** is closed under complement. Now a fact that fails to enter my head is the following:

We take ***3SAT*** which we know is ***NP-complete*** and then we take ***3TAUTOLOGY*** which is ***Co-NP-complete***. The last formal language is a subset of the first, however it seems to have certain structural properties that make it (more) difficult to recognize. it is known that the certificate for ***SAT*** consists in a binary distribution of the literals that satisfies the formula but the certificate for a ***TAUTOLOGY*** must necessarily contain **ALL** the distributions of the variables, which must **ALL** satisfy the formula, otherwise we could not ascertain in any way that it is a tautology.

Therefore, based on this fact, verifying belonging to the ***3SAT*** set by having a certificate requires time polynomial to the input but verifying membership in the set ***3TAUTOLOGY*** no. Why is this fact not enough to show that ***NP*** $\neq$ ***Co-NP***?

Is the reasoning correct up to this point? if so, should it still be formally demonstrated? Is it in doing this that lies the immense difficulty?

# Answer
> -1 votes
Suppose $P=NP$ then there is polynomial certificate for TAUTOLOGY and it is still open. In the world $P \neq NP$ there is still a hope for $NP = coNP$ but unlikely. May be there exits a polynomial certificate for TAUTOLOGY that shows $NP = coNP$. you can see the proof of $NL = coNL$ by Immerman or Szelepcsenyi, it is like p and np but for space complexity. before they introducing the proof many of people thought that $NL \neq coNL$.

# Answer
> -1 votes
> it is known that the certificate for SAT consists in a binary distribution of the literals that satisfies the formula but the certificate for a TAUTOLOGY must necessarily contain ALL the distributions of the variables, which must ALL satisfy the formula, otherwise we could not ascertain in any way that it is a tautology.
>
> ...
>
> Is the reasoning correct up to this point? if so, should it still be formally demonstrated? Is it in doing this that lies the immense difficulty?

The error occurs when you say that a certificate for TAUTOLOGY must *necessarily* contain all assignments to the variables. If you can prove this, then yes, $\mathsf{NP} \neq \mathsf{coNP}$. Intuitively this may (or may not, depending on your own intuition) seem to be the case, but it is exceptionally difficult to prove.

One thing worth noting is that 2SAT is solvable in deterministic polynomial time, so your corresponding problem of 2TAUTOLOGY is also solvable in polynomial time. Accordingly, for a width-2 DNF $\varphi$, if $\varphi$ is a tautology, there is a *very* short certificate of this fact (and this certificate does not need to look at all possible assignments of the input variables to $\varphi$).

---
Tags: np-complete, satisfiability, co-np
---


# Question
Title: Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?
This post and this post indicate that when the dimensionality gets higher, KDTree gets slower.

Per scikit-learn doc, the KDTree becomes inefficient as D(dimensions) grows very large (say, $D\>20$): this is one manifestation of the so-called “curse of dimensionality”.

Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?

# Answer
> 3 votes
The problem arises due to curse of dimensionality. If the dimensionality is $k$ , the number of points in the data, $N$ should be $N ≫ 2^k$. Otherwise, when $k-d$ trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than brute force search. So for high value of $k$, approximate nearest-neighbour methods should be used instead.

> most of the points in the tree will be evaluated

When the dimensionality increases to high value, the volume of the space increases so fast that the available data become sparse.Organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. Hence $k-d$ trees become ineffiecient for high dimensions.

---
Tags: search-algorithms
---


# Question
Title: Minimum time to assemble multipart object
I've been asked to do this task in an online assessment. I've passed, so my solution is supposedly correct, but I am unable to prove it. The task is:

Given a set of parts (array of integer part sizes), worker must put them all together. Parts are assembled in pairs. To put together two parts of sizes A and B worker needs A+B minutes. The resulting part's size is also A+B. Write a program to determine the minimum time required to put together given set of parts.

My solution was:

```
MinHeap h
for p in parts:
  h.push(p)
time = 0
while h.size() > 1:
  v1 = h.pop()
  v2 = h.pop()
  time += v1 + v2   ### assembly time
  h.push(v1 + v2)   ### adding new part
return time

```

This solution passed all tests.

**Question:**

Does this solution produce correct min time, and if yes, how to prove it?

# Answer
> 3 votes
Your solution (of greedily merging the two smallest objects available) is indeed correct. This problem is very classic and you can find it under the name 'rod connection' or 'rope connection'. Here (https://stackoverflow.com/questions/43715207/how-to-prove-this-greedy-algorithm-as-optimal-rod-connection) is the proof of optimality.

---
Tags: algorithms
---


title: generating all pairs

text:
# Question
Title: generating all pairs
suppose I have 6$\\{0,1,2,3,4,5\\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t

* each number should be in one pair and also every number should be paired
* a pair(like 0-1) should be present in only one of the pairing. and also every possible pair should be present somewhere

i) 0-1 , 2-3 ,4-5

ii) 0-4 , 1-2 ,3-5

iii) 0-3 , 1-4 ,2-5

iv) 0-2 , 1-5 ,3-4

v) 0-5 , 1-3 ,2-4

similarly if I have N numbers. I need $(N-1)$ pairing of numbers s.t in each pairing there are $N/2$ pairs.

essentially this is grouping $\binom{n}{2}$ combinations into $n-1$ groups s.t each number is present exactly once in each group

# Answer
As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following:

```
def get_sets(a: list):
    # Simple implementation of
    # https://nrich.maths.org/1443
    center, *rest = a
    for _ in range(len(rest)):
        rest = rest[1:] + rest[:1] # put 1st element to back of list
        solution = [[center, rest[len(rest) // 2]]] # combine middle element with center
        for i in range(len(rest) // 2):
            solution.append([rest[i], rest[~i]]) # combine i-th element from front with i-th from back
        yield solution

for s in get_sets(list(range(50))):
    print(s)

```

Note that this implementation creates a new list for each "set" in the output. This is not strictly necessary, as the same result could be achieved by using only the initial list (actually array) and use smart indexing.
> 1 votes

# Answer
Your problem is related to the balanced tournament design problem.

Suppose that you have $2n$ tennis players, there are $n$ tennis courts, and you need to play a round robin tournament in $2n-1$ rounds. The courts aren't the same, to to balance the effect of the different courts, you want to ensure that no player competes more than twice on any one court. The problem is to design the rounds.

Formally, a BTD of order $n$ is an arrangement of all of the distinct (unordered) pairs of a set $V$ (where $|V| = 2n$) into a $n$ by $2n-1$ array such that:

* Every element of $V$ appears precisely once in each column.
* Every element of $V$ appears at most twice in each row.

While your problem isn't exactly the same as the BTD problem, any solution to the BTD problem is a solution to your problem. So a solution to the BTD problem solves your problem if $N$ is even. (I don't know what you want to do if $N$ is odd.)

The BTD problem has a very simple solution. See, for example, this blog post by Rachel Silverman.
> 1 votes

---
Tags: algorithms, combinatorics
---


title: Divide a number in k powers of 2

text:
# Question
Title: Divide a number in k powers of 2
Example

N = 9 and K=3

4 + 4 + 1 = 9 .

What I have tried.

We can not go on dividing with 2.

We can use unbounded knapsack with array elements from 2^0 to 2^32.

# Answer
If $k\>N$, this cannot be done (as $\forall p\_1,\dots, p\_k\geq 0,\sum\_{i=1}^k 2^{p\_i}\geq k\>N$)

If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct).

1. If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order to obtain $N$ as a sum of $k$ powers of two (you cannot be stuck with only terms of the form $2^0$ -which cannot be split- before reaching $k$ terms as $k\leq N$ by assumption).
2. If $n\>k$, then it cannot be done. Indeed, assume it could be done, and consider the decomposition into $k$ powers of two. (Iteratively) merge these powers of two until you reach a binary decomposition of $N$. This decomposition has at most $k$ $1$s, which is absurd by uniqueness of the binary decomposition.
> 3 votes

---
Tags: algorithms, data-structures, subset-sum
---


# Question
Title: What are the differences between NP-Complete and NP-Hard?
What are the differences between NP, NP-Complete and NP-Hard?

I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's out there, or there is something that I'm not aware of.

# Answer
A problem $\Pi$ is $\textrm{NP}$-hard if every problem in $\Pi' \in \textrm{NP}$ can be reduced to $\Pi$ via a Karp reduction $\le\_p$, i.e., if $\Pi' \le\_p \Pi$.

A problem $\Pi$ is $\textrm{NP}$-complete if it is $\textrm{NP}$-hard and belongs to $NP$.

Intuitively, a $\textrm{NP}$-complete problem is as hard as the hardest problem in $\textrm{NP}$ while a $\textrm{NP}$-hard problem might be even harder.

Finding a polynomial-time algorithm $A$ for any $\textrm{NP}$-hard problem $\Pi$ (therefore also for any $\textrm{NP}$-complete problem) would immediately yield a polynomial-time algorithm for all problems in $\textrm{NP}$: reduce (in polynomial-time) an instance $x$ your problem $\Pi' \in \textrm{NP}$ of choice to an instance $y$ of $\Pi$ and then solve $y$ it using $A$.
> 0 votes

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


# Question
Title: Algorithm for solving system of congruences
I'm trying to understand an algorithm shown in my textbook for solving a system of congruences. The problem states:

Let $r$ and $m$ be arrays of size $n$, such that every two numbers (modulos) from $m$ are coprime. Find $x$ such that

$$x \bmod m\_0=r\_0\\x \bmod m\_1=r\_1\\\...\\x \bmod m\_{n-1}=r\_{n-1}$$

So yeah, the classic congruence system problem. The naiive approach is shown first and then comes this:

> Let $M = m\_0 \cdot m\_1 \cdot ... \cdot m\_{n-1}$. Let's assume we can find the numbers $w\_0, w\_1, ...w\_{n-1}$ such that $w\_i \bmod m\_i = 1$ and $w\_i \bmod m\_j = 0$ for $i \neq j$. So we're finding numbers $w\_j$ such that it is divisible by every number except for $m\_j$ where the remainder is $1$. Then the solution x can be constructed as: $$x = r\_0\cdot w\_0 + r\_1\cdot w\_1 + ...+r\_{n-1}\cdot w\_{n-1} (\bmod M)$$

Well I guess my question is simply - why? I can't seem to reason this out. It seems to me that $x$ is always going to be zero. If we take the sum given above and break it up into sums $$(r\_0\cdot w\_0)\bmod M + (r\_1\cdot w\_1)\bmod M + ...$$

it seems like everything should be zero? Let's take the first expression $(r\_0 \cdot w\_0) \bmod M$. We've got $r\_0$ times something that's a multiple of every $m$ except for $m\_0$ (because of the way the numbers $w$ were defined), meaning that whole thing will be a multiple of every $m$ except for $m\_0$. And then we're taking a modulo $M$ which is also a multiple of every $m$.

How does this give us a solution? The textbook is pretty vague about this and doesn't explain why it works this way. So, any ideas?

Thanks.

# Answer
> 1 votes
It is often less confusing to refrain from using congruences and simply write what it means in extension. I.e. when the textbook says to take an $x$ which is equal modulo $M$ to $r\_0\cdot w\_0 + \dots + r\_{n-1}\cdot w\_{n-1}$, it means that any $x$ of the form $x=r\_0\cdot w\_0 + \dots + r\_{n-1}\cdot w\_{n-1} + k\dot M$, with $k\in \mathbb{Z}$, is a solution. Under this form it should be clearer that $x$ is indeed a solution since $\forall i\in \mathbb{N}\_n,x\equiv\_{(m\_i)}r\_i\cdot w\_i + \sum\_{j\neq i}r\_j\cdot w\_j+ k\cdot M\equiv\_{(m\_i)}r\_i$ (as $m\_i|M$, $w\_i\equiv\_{(m\_i)}1$, and for $j\neq i$ $m\_i|w\_j$).

---
Tags: algorithms
---


# Question
Title: Can non-metric TSP be approximated within some non-constant value?
It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some constant value (unless P= NP), thanks to Sahni and Gonzalez.

It isn't clear however if non-metric TSP can be approximated within some non-constant value, such as the number of nodes of the instance, or the largest cost on its edges? Does Sahni and Gonzalez's result still hold for these values?

# Answer
> 3 votes
Indeed, it trivially can. If each edge has positive integer weight $w\_e$, then any algorithm that outputs a valid tour has approximation ratio $w\_{max} = \max\_e w\_e$, since the optimal solution costs at least $n \cdot 1 = n$ while the cost of any valid tour $T$ is at most $\sum\_{e \in T} w\_e \le n \cdot w\_{max}$.

Note: If edges can have weight zero this argument won't work, because in that case even deciding if a tour of cost zero exists is NP-hard; you can reduce Hamiltonian Cycle to it. Hence your algorithm will sometime output a nonzero cost tour, when a zero cost tour exists, which means the approximation ratio cannot be bounded.

# Answer
> 0 votes
TSP can be used to solve “Hamiltonian path”: is there a path connecting all nodes?

You do this by specifying a TSP instance where distance = 1 if two nodes are connected, distance = H otherwise (where H is some huge number), and checking if the shortest path has length n (instead of n + H - 1)

An approximation cannot be good enough to solve Hamiltonian path.

I have never seen this mentioned, but I could imagine that "almost Hamiltonian path" where you are supposed to find a sequence of n nodes of which at least n-m are connected would be NP-complete for some combinations of n and m, for example if m=1. In that case, an approximation better than m * H would solve the "almost Hamiltonian path" problem.

You can find a path by starting at some node and then always going to the nearest neighbour. You can take that as a baseline, or n times the longest distance, or the sum of the longest distances from each node. I suspect you won't be better than this baseline times some small constant.

On the other hand, you can turn a TSP into TSP with metric by increasing all distances by some value. You can determine the minimum increase to guarantee triangular equation, and go from there.

---
Tags: approximation, traveling-salesman
---


# Question
Title: Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B
I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 \[219\].

* Why Isn't this construction considered a counterexample to P = NP? And if it is not, can it be strengthened into one? It seems tome that we have constructed a languge recognizable in NP time but not in P time.
* In the proof there is the sentence "If P\_i^B(i) accepts 0^n, then place no string into B at this stage." How can this possibly happen?

I figured that, since B is intially empty, the oracle B(i) ALWAYS rejects. So the only reason why P\_i would accept is some reason OTHER than a question to B(i). Please correct me if I am wrong.

The proof in question is verbatim reproduced here. The original paper is here.

# Answer
> 5 votes
As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know.

As you can see there, the complete statement of Baker, Gill, Solovay is:

> There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$

The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "divide" by B so to say. Constructing a oracle language $L^A$ out of a "normal" language $L$ is not that easy. The languages $P^B$ and $NP^B$ behave completely different than $P$ and $NP$. To show you an example for this: Even if $P=NP$ is true, the statement $P^B \neq NP^B$ is still valid. This shows how different $P,NP$ and $P^B, NP^B$ behave.

> It seems to me that we have constructed a language recognizable in NP time but not in P time.

Be careful here. It is shown that unary language $U\_B$ can be recognized by a $NP^B$-TM, not by a $NP$-TM. Again, this is because Oracle-Languages/TMs behave completely different than their "normal" counterparts. If you want to recognize $U\_B$ in $NP$ without the oracle, you have to do a lot more work as you could guess a word $w$ of length $i$ in poly. time, but you cannot decide $w \in B$ that easy, as we have no clue by BGS if $B \in NP$ or not.

> And if it is not, can it be strengthened into one?

Maybe yes, maybe not. As this would solve $P=NP?$, which is unknown, it is unknown if you could strengthen it or not.

> In the proof there is the sentence "If $P\_i^{B(i)}$ accepts $0^n$, then place no string into B at this stage." How can this possibly happen?

As you just simulate all TMs in $P\_i^{B(i)}$ and don't change them, you cannot change whether the TM accepts or not. For example, the TM that accepts all words is in $P$, so it also is in $P^B$, so it will be simulated at some point. Then, your case will happen. Of course, this TM will not call the oracle once.

Edit 3:

Now I want to convince you that your Algorithm does not run in $NP$-time. I can't convince you by now that really $B \not \in NP$, but I think I can convince you now at least that this algorithm does not gives us $B \in NP$.

Let's try to formulate your algorithm as an $NP$-TM that decides $w \in B$ (using original BGS, Theorem 3 now):

1. Guess $i$ s.t. $M\_i^B(1^{|w|})$ is the poly-TM where $n:=|w|$ is choosen. See that $M\_i$ has access to oracle $B$. ~~Guessing $i$ is possible because $i\leq n$ as each stage needs a unique $n$. However, can we verify that $i$ is right? To do so, we might have to really build $B$ from stage $i=0$, which would take to long.~~

~~2. Simulate $M\_i(1^{|w|})$ for $2^n/10$ time. I'm not sure whether we can do this. We don't know if $M\_i$ is a poly-time TM, so we can't really guess a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ so it could really run for $2^n/10$ time as we enumerate all TM's so e.g. also the $EXP$-hard ones. Can you find a fix for this? If so, I will re-edit this answer to describe the next steps.~~ Using original BGS now:
2. Simulate $M\_i^B(1^{|w|})$ for $p(|w|)$ time. ~~We can guess the polynomial $p$ in $NP$-time. However, can we verify that $p$ is the right polynomial? We cannot assume that it's right and I can't find an easy way to do this.~~ But here comes the problem: Can we really simulate $M\_i^B(1^{|w|})$ in poly. time? I want to convince you that this is not the case.

2.1. If $M\_i^B(1^{|w|})$ writes $x\_B$ on the oracle tape and asks $x\_B \in B?$, what can we do in $NP$ without the oracle? We can only start another simulation, guess another $i'$ s.t. stage $i'$ takes $n':=|x\_B|$ and simulate $M\_{i'}^B(1^{|x\_B|})$.

However, how many such new simulations do we have to do in the worst case? $M\_i^B(1^{|w|})$ with running time $p(|w|)$ could ask the oracle $p(|w|)$ questions of length $p(|w|)$. Let's look at some arbitrary question at step $j$ now. Let the asked question in step $j$ be $x\_B \in B?$. Now, we have to guess $i'$ s.t. $n':=|x\_B|$ and simulate $M\_{i'}^B(1^{|x\_B|})$. Let $p'(|x\_B|)$ be the running time of $M\_{i'}^B(1^{|x\_B|})$. Now, in the worst case, $M\_{i'}^B(1^{|x\_B|})$ asks the oracle $B$ in every of the $p'(|x\_B|) = p'(p(|w|))$ steps again a question of length $p'(|x\_B|) = p'(p(|w|))$. And this can go on and on.

In the end, we have build a tree with the vertex degree being $O(p''(|w|))$ for some polynomial $p''$. The depth of this tree can be pretty huge, because $i$ could equal $i'$. Let's assume just for simplicity that in each step $j$ we asked each stage $k \in \\{1,\cdots,n\\}$ exactly one question. Then we have depth $n$ for each path from the root to some leaf in the tree. Therefore, to answer the initial question $w \in B?$, we have to look at each of the $O(p''(|w|))^n$ verticies. Clearly, this can only be done in exponentioal time and not in polynomial time, because we have a exponention number of vertecies w.r.t $|w|$. Therefore, the algorithm does not run in $NP$-time.

---
Tags: complexity-theory, p-vs-np, oracles
---


# Question
Title: What order logic does a system correspond to under Curry–Howard correspondence?
In *Types and Programming Languages* by Pierce,

1. Section 9.4 *Curry–Howard correspondence* on p109 has a table

Does the table mean that the simply typed lambda calculus `λ→` corresponds to propositional logic (i.e. the zeroth order logic)?
2. Does the following quote on p109 mean that System F correspond to the second order logic?

> System F (Chapter 23), whose parametric polymorphism involves quantiﬁcation over types, corresponds precisely to a second-order constructive logic, which permits quantiﬁcation over propositions.
3. Which programming language system correspond to the first order logic?

In system `λ→`, a term varies in a type, so doesn't `λ→` more correspond to the first order logic than to the propositional logic?
4. Which logic system does the untyped lambda calculus correspond to?

Does Curry-Howard Correspondence only care about typed systems, not untyped systems?
5. p109 continues to say

> System Fω (Chapter 30) corresponds to a higher-order logic.

Section 30.4 on p461 defines system Fi, where i = 1, ..., in terms of kinds, and calls F2 (the same as System F above) the second order lambda calculus. Is system F1 (the same as System `λ→` above) called the first order lambda calculus?

What order logic does System Fi correspond to?
6. Do the order in logical system and the order in the hierarchy of kinds in Section 30.4 not match?

For example, `λ→` corresponds to the proposititional logic (my part 1), so its order of logic system is 0, or it might correspond to the first order logic, and its order might be 1 (see my part 3). `λ→` is system F1 in the hierarchy by kinds (c.f. Section 30.4), so its order in the hierarchy of kinds is 1. The two orders may or may not match, depends on which logic `λ→` corresponds to.

For another example, System F corresponds to the second order logic (my part 2), and is system F2 in the hierarchy by kinds (c.f. Section 30.4). So the two orders seem to match.

Thanks.

# Answer
I'm not confident enough about the later questions, but I hope I can give a partial answer, since this hasn't been given much love.

1. Yes
2. Yes
3. There is nothing in particular, since first-order logic quantifies over non-logical objects, but a priori there are no non-logical objects we're reasoning about for the lambda calculus. There is a similar-sounding type system (Hindley-Damas-Milner which allows some quantification over types, but this is not related to the non-logical quantification of FOL)
4. The untyped lambda calculus does not directly correspond to anything, since the Curry-Howard correspondance related Types to Propositions, so in the untyped setting there is no proposition to prove. Also: since the untyped lambda calculus has the Y combintor, so it's very likely any attempt will make it inconsistent. To answer a potential further question, we would also get inconsistency if we added a fixed-point combinator $\mu: (\tau \to \tau) \to \tau$ to most any lambda calculus. This is more or less equivalent to naive set comprehension. The exceptions for losing consistency are some weak linear logics (E.g. EAL or Łukasiewicz) and corresponding lambda calculi.

To the best of what I can tell, you're mostly correct here.

5. For system $F\_i$, $i \geq 2$ should correspond to ith-order logic. The only difference is that first-order logic doesn't quite fit into this hierarchy.
6. Seems like yes
> 2 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: Running time of algorithm (effect of j*j in for loops) - Theta Runtime
### In Theta notation what are the running times of these algorithms?

# Algorithm 1

```
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

```

Since the outer loop is going to n and the inner loop is going to sqrt(n). My guess is that it is Θ(n^2)

$$ \sum\_{i=1}^{n} O(1) \sum\_{j=1}^{\sqrt n}O(1) = \sum\_{i=1}^{n} \sqrt j\*\sqrt j = \theta(n^2) $$

Thought process for the summations: **number of terms * max term**

# Algorithm 2.

```
for i=1..n
    j=2
    while j <= i
        j = j * j

```

j performs similar to a log function. Since the outer loop is n. My guess is $Θ(n\log n)$

$$ \sum\_{i=1}^{n} O(1) \sum\_{j=2}^{\log n}O(1) = \sum\_{i=1}^{n} (\log n -2) * O(1) = \theta (n * (\log n -2)) = \theta (n\log n) $$

# Answer
# 1

For the first case, you had the right idea, but just had some algebra mistakes.

```
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

```

Let $T(n)$ be the time complexity. $$T(n) = \sum\_{i=1}^n\sum\_{j=1}^\sqrt{i}1\leq \sum\_{i=1}^n\sqrt{n}=\leq n^{3/2}$$ $$= O(n^{3/2})$$

# 2

I'm assuming you meant the pseudocode below since it is more analogous to your first case (I believe the pseudocode you posted has the same complexity). You are correct though, it is $O(n\log n)$ for the reason you described.

```
for i=1..n
    j=2
    while j <= i
        j = j * j

```
> 1 votes

---
Tags: algorithms, data-structures, asymptotics, runtime-analysis, loops
---


title: Another vertex cover question?

text:
# Question
Title: Another vertex cover question?
I'm not sure this is equivalent to bipartite vertex cover question. The question is:

Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex from the left side.

e.g. In the following graph, the answer is 1, cause vertex g has connection to all vertex on the left.

# Answer
> 1 votes
It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\\{d\\},\\{d\\},\\{a,b,c,d\\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.

---
Tags: graphs, vertex-cover, bipartite-graph
---


# Question
Title: Is Finding A Hitting Set of Size n/2 NP-Hard?
In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E.

In decision version of the problem, we are asked if there exists a hitting set H of size at most k.

This problem is known to be NP-hard. However, I wonder if the problem is still NP-Hard when are asked if there exists a hitting set whose size is strictly less than n/2, i. e., at most n/2 - 1, (where n is the size of V).

I'm currently working on another problem and I'm convinced that the problem is NP-hard. So I'm trying to find a reduction. I've realized that if the above problem is NP-hard, then I am done.

Any help is appreciated.

# Answer
> 1 votes
I think the easiest way is to reduce

> $ VC\_{n/2}=\\{G∣G=(V,E) $ has a vertex cover of size $|V(G)|/2\\}.$ ( https://cs.stackexchange.com/a/90487/72705)

to

$ HS\_{n/2}=\\{(S,F)∣\exists H\subseteq S: $$H$ is a HS of $F$ of size at most $|S|/2 $$\\}$.

In https://cs.stackexchange.com/a/90487/72705 , they show that $VC\_{n/2}$ is $NP$-hard.

Now, we reduce $VC\_{n/2}$ to $HS\_{n/2}$, which is the standard reduction from normal $VC$ to $HS$:

* $S = V$
* $F = E$, where $E:= \\{e\_1,e\_2,\ldots,e\_m\\}$ with $e\_i = \\{v\_j, v\_k\\}$ and $v\_j, v\_k \in V$

Clearly, this reduction can be done in poly. time and is correct, as one element in $F$ corresponds to one edge in $E$, so the HS can be mapped one to one to the vertex cover set and vice versa.

As you can see, the vertex cover set has the same number of elements as the corresponding hitting set (if there exists one). Also, $|S| = |V|$. Therefore, the Vertex Cover Set of size $|V|/2$ gives a HS of size $|S|/2$. To get a HS of size $(|S|/2) -1$, one could add two completely new elements $\alpha, \beta$ to $S$ (let this be $S'$) without changing $F$. Therefore, $\alpha$ and $\beta$ will never be in the HS of $F$, but the Hitting Set now has a size of $|S|/2 = (|S'| -2) / 2 = (|S'|/2) -1$.

---
Tags: reductions, set-cover
---


# Question
Title: Category theory structures to describe topics and queues
What are the category theory structures describing queues and topics? By queues and topics I mean the ones described in systems like Apache Kafka, AcriveMQ or Java Messaging Service.

Where I can find material about that?

# Answer
A data structure Queue is very close to the concept of a List, however a Queue is a First-In-First-Out (FIFO) data structure. The available operations to interact with the List structure then, are limited to `enqueue()` and `dequeue()` (it is not a case in fact that a queue can be implemented using a List structure).

In the context of Category Theory you might find a parallelism between a List data structure and a Free Monoid https://ncatlab.org/nlab/show/free+monoid which can provide a recursive implementation of a List data structure. The same category equipped with ad-hoc morphism can be used to describe the behaviour of Stacks and Queues data structure.

In the case of Kafka and other similar queue services, besides the complications coming from the distributed case scenario, they don't really resemble the usual case of a Queue data structure. In fact, such a data structure is always supposed to be finite - they are rather implementing the concept of a stream (which could be finite or infinite) under the access condition of a queue (to be completely precise, for Kafka that's not even completely true, since you have the ability to access elements arbitrarily from the topic/queue using an offset). To model such kind of streaming structures an approach similar to this https://ncatlab.org/nlab/show/stream could be used.
> 3 votes

---
Tags: category-theory, queues
---


# Question
Title: Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?
I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail?

If we divide into blocks of $7$ then we will get: Solving it by substitution I think the following manner: It is a recursive tree. In the worst case it takes $T(10n/14)$ time. So in the worst case it goes down to the bottom by $(10/14)^kn=1$ steps; $k=log\_{14/10}n$. At each level of recursive tree the total cost is $\le cn$ for some constant $c$. So by the simplified assumptions using substitution $k \< n$ $T(n)\le dn \log(n)$

$T(n) \le T(n / 7) + T(10n / 14) + O(n) \le d\frac{n}{7}lg(n/7)+d\frac{10n}{14}lg(10n/14)+cn \le d(\frac{n}{7}lgn - \frac{n}{7}lg7) + d(\frac{10n}{14}lgn - \frac{10n}{14}lg10/14) + cn = d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg\frac{10}{14} + cn=d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg10 - d\frac{10n}{14}lg14 + cn \le d\frac{12n}{14}lgn + cn$

So, $T(n) = O(nlgn)$

The same way for blocks of size $3$.

$T(n) \le T(n / 3) + T(2n / 3) + O(n)$ we get $T(n) = O(nlgn)$

Now, how to show that $T(n)$ for 7 is also $O(n)$ and for 3 it can not be $O(n)$. Also, in general how can I guess that the $T(n)$ is also $O(n)$ because here in both cases my thoughts are they both $O(nlogn)$?

# Answer
Let's take a look at the case of size 7 first. Here, we want to show a linear *upper bound* for $T(n)$. Thus, we choose the recurrence relation $T(n) \leq T(n / 7) + T(5 / 7 n) + dn$ (remember, it is an upper bound). We guess that the solution is of the form $T(n) \leq cn$ for some constant $c$ and prove it with induction: $$T(n) \leq T(n / 7) + T(5 / 7 \cdot n) + dn \leq c \cdot n/7 + c \cdot 5/7 \cdot n + dn = 6/7 \cdot cn +dn. $$ To this end, we choose $c = 7 d$, resulting in $T(n) \leq cn$.

Now we want to show a *lower bound* for size 3 (for the worst-case, tho!). So we have find a lower bound for its recurrence equation, namely: $$T(n) \geq T(n/3) + T(2/3 \cdot n) + dn .$$ The list of medians takes $T(n/3)$ since there are $n/3$ medians (resp. blocks). In the worst case, we have to recursively search in an area of size at least $2/3 n$. Clearly, this recurrence relation is not linear. To get an intuition for this, imagine that we would have equality. Assuming a solution of the form $T(n) = cn$, we get $T(n) = 1/3 \dot cn + 2/3 \dot cn + dn$. Since $d\>0$, $T(n) \> cn$ which contradicts our assumption.

For more information, check out the analysis on Wikipedia.

The key part is that for block size $3$ the sizes of the recursive calls add up to $n$, which does not help to reduce the running time.

If you have more questions, feel free to ask!
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting, order-theory
---


# Question
Title: Prove regular languages are closed under f(n) = 2^n and f(n) = n^2
Suppose $ R $ is a regular language, let $ f(R) = \\{ w \mid \exists x \text{ such that } |x| = f(|w|) \land wx \in R\\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've been on this question for a while now, and I'm not really sure how to approach it. I only really know elementary techniques like Myhill-Nerode and constructing DFA/regex, so I probably won't understand solutions using more complex logical models of regular languages.

# Answer
> 1 votes
For $f(n)=2^n$:

Let $M=(Q,\Sigma,\delta,q\_0,F)$ be the DFA recognizing $R$. Denote by $\mathcal{G}$ the set of functions from $Q$ to $\mathcal{P}(Q)$ (where $\mathcal{P}(Q)$ means the power set of $Q$), and for any $g,h\in\mathcal{G}$, denote by $gh$ the function defined as $$gh(\cdot)=\bigcup\_{q\in h(\cdot)}g(q).$$

Construct a new DFA $M'$ of whose states each is labeled a pair $(q,g)\in Q\times\mathcal{G}$. The transition function $\delta'$ of $M'$ is defined as

$$\delta'((q,g),a)=\left(\delta(q,a),gg\right),$$

for all $q\in Q, g\in\mathcal{G}, a\in\Sigma$. The start state of $M'$ is $(q\_0,g\_0)$ where $g\_0$ is defined as $g\_0(\cdot)=\\{\delta(\cdot,a)\mid a\in \Sigma\\}$. The set of accept states of $M'$ is $\\{(q,g)\in Q\times\mathcal{G}\mid g(q)\cap F \neq \emptyset\\}$.

Now we claim that

> After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g)$, where $g(\cdot)$ represents the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $f(|w|)$.

This cliam can be proven by mathematical induction on $|w|$. With this claim, we can see $M'$ indeed recognizes $f(R)$.

---

For $f(n)=n^2$, the proof is similar. In this case, each state of $M'$ is labeled a tuple $(q,g\_1,g\_2)\in Q\times \mathcal{G}^2$, the transition function becomes

$$\delta'((q,g\_1,g\_2),a)=\left(\delta(q,a),g\_1g\_0,((g\_2g\_1)g\_1)g\_0\right),$$

where $g\_0(\cdot)=\\{\delta(\cdot,a)\mid a\in \Sigma\\}$ as above, the start stae becomes $(q\_0,I,I)$ where $I(\cdot)=\\{\cdot\\}$, and the set of accept states becomes $\\{(q,g\_1,g\_2)\in Q\times\mathcal{G}\mid g\_2(q)\cap F \neq \emptyset\\}$.

Also, our claim becomes

> After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g\_1,g\_2)$, where $g\_1(\cdot),g\_2(\cdot)$ respectively represent the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $|w|,|w|^2$.

# Answer
> 0 votes
$f(R)$ is regular since it can be decided by a one-tape TM in linear time.

Do a constant-sized matrix multiplication inside the TM's finite control.

The DFA transition can be viewed as a 0-1 matrix $A$ by forgetting the arc label. First comput $A^n$, then bounce back to compute $A^{n^2}$. Then proceed to run the DFA as usual to know the last state it ends after finishing readinv $x$. Query the computed $A^{n^2}$.

Similarly for $2^n$.

# Answer
> 0 votes
For this and similar problems you need to first prove a property of finite state machines: The set of lengths of strings that transition from one state to another is either a finite set of integers, or there is a k \>= 1, and two finite sets X and Y such that every possible length is either in X, or is equal to n\*k + y, where n \>= 0 and y is an element of Y.

Second, if we know the lengths of all inputs going from state S to a fixed accepting state T, can we determine the set of integers k, such that after going from initial state to S, we can reach the accepting state after a total of f(n) steps?

As an example, if we took k steps from initial state to S,and there are 7j + 15 steps needed to reach an accepting state, and f(n)= n^2 then n^2 mod 7 = 0,1,4,2,2,4,1 so k+7j+15 = n^2 If k mod 7 is 7, 0 or 3.

And here it is essential that not only can we solve this for k, but the solution is easy enough that we can modify our stat machine to handle it.

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


# Question
Title: How is parallel tag checking achieved in associative Mapping?
I originally posted this question on stack overflow and then realised it was better suited to computer science .

In the book on computer organization and architecture by William stallings , in the cache memory chapter and associative mapping topic , the author says that the cache control logic simultaneously checks all the tag fields for a match when presented with an address . However , there is nothing said about how this actually happens , how the simultaneous checking takes place and I wanted to know about how this is implemented and what kind of circuitry is required to achieve this.

# Answer
\[I don't have this book\]

Let's take a common example : A 4 ways, 16kB cache made of 4 ways of 4kB. And a cache line of 32 bytes.

Each way of the cache is made of a 4kB RAM containing data and another RAM which stores cache tags, its size is 4096/32 = 128 lines, each tag can probably fit in a 32 bits.

The tag RAM is indexed with the low address bits (here A\[12:6\]), and its content is compared with the high address bits A\[31:7\].

If you have 4 ways, you have 4 tag RAMs, the address bits are the same, but you have 4 comparators.

Cache is made of ordinary RAM blocks.

(In current advanced CPUs, to save power and complexity, the cache ways are often not compared at the same time, there is a preferred way, selected with some heuristics, wich is tested first, the other ways are tested only if the first one do not match)
> 1 votes

# Answer
In the book `Computer Architecture: Fundamentals and Principles of Computer Design by Dumas` in 2.3.4 chapter (https://books.google.ru/books?id=TZ6VDQAAQBAJ&pg=PT89&hl=ru&source=gbs\_selected\_pages&cad=2#v=onepage&q&f=false) it is explained as associative type mapping is physically organized by storing tags in special type memory - content associative memory CAM, which locates not by address, but by content. You can read more on it in wiki, where there are mentions of specific semiconductor implementations: https://en.m.wikipedia.org/wiki/Content-addressable\_memory
> 0 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Closure of CFL against right-quotient with regular languages
> Let $A/B$ = $\\{ w \mid wx \in A$ for some $x \in B \\}$. Show that if A is context free and B is regular, then $A/B$ is context free.

My interpretation of this is is that we need to show that if a string $wx$ is accepted by a CFG, and we know that $x$ is accepted by a regular language (and therefore is also accepted by a context-free language), then $w$ must also be accepted by a CFG.

My initial thought on how to solve this would be a proof by contradiction in which we assume that $A$ is context free, $B$ is regular, and then assume that $A/B$ is not context-free. Since $A$ is context free, we can construct an equivalent PDA that accepts $A$.

From here, my thought was to take an arbitrary $wx$ that is accepted by $A$, such that $x \in B$. We can then construct another PDA based on the first that only accepts $wx$. We could then break the PDA into two pieces: one that accepts $w$ and one that accepts $x$ (with the two pieces concatenated together). Since there then would exist a PDA that accepts just $w$, and $w$ is arbitrary insofar as $wx$ was arbitrary, $A/B$ must therefore be context-free after all (contradiction).

Will this approach work? (Is this a good general approach?) If so, how would I go about breaking the PDA that accepts $wx$ into chunks formally?

# Answer
> 8 votes
Imagine you have a pushdown automaton (PDA) $X$ for $A$ and a DFA $Y$ for $B$.

You want to build a PDA $Z$ for $A/B$. You can do as follows: the states $Q\_Z$ of $Z$ are $Q\_X\times Q\_Y$. There are two phases:

Phase 1: You just read the input word and advance in $X$, states of $Y$ are ignored. This corresponds to the word $w$ of your language.

Phase 2: When you reach the end of $w$, you are allowed to perform $\epsilon$-transitions in order to reach an accepting state of $X\times Y$. So you guess a word $x$ that will continue to advance in $X$ and start to advance in $Y$, and that has to reach acceptance in both automata simultaneously. If there is an accepting run of this automaton, then the input word $w$ is in $A/B$ since you guessed the witness $x$ (and vice-versa, if $x$ exists, then it can be guessed by your automaton $Z$).

The reason why $B$ has to be regular instead of CFL is that you cannot manage two stacks at the same time, if you want to stay CFL.

# Answer
> 5 votes
Here is a very short proof relying on rational transductions. Let $X$ be the alphabet. First the relation $\tau$ defined by $\tau(u) = uB$ is a rational transduction. Indeed its graph $(\Sigma\_{x \in X} (x,x))^\*(\\{1\\} \times B)$ is a rational subset of $X^\* \times X^\*$. This is the place where the hypothesis that $B$ is regular is mandatory. Now $$ A/B = \\{u \mid \tau(u) \cap A \not= \emptyset \\} = \tau^{-1}(A) $$ where $\tau^{-1}$ denotes the inverse of the relation $\tau$, which is also a rational transduction. Finally, it suffices to use the fact that if $L$ is context-free and $\sigma$ is a rational transduction, then $\sigma(L)$ is context-free.

# Answer
> 3 votes
Above answers are excellently written. But one other approach would be helpful I think.

We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \\{w\space|\space wx \in A,\space x\in B,\space w\in \Sigma^\*\\, ,\space x\in \Sigma^\*\\}$ is also a $CFL$.

Let's use fact that set of regular languages and set of context free languages are closed under homomorphism and inverse homomorphism.

Let's define $\overline\Sigma^\* = \\{\overline a\space|\space a\in\Sigma\\}$

Now define homomorphism

$unbar:\space (\Sigma\space \cup \overline\Sigma)^\* \rightarrow \Sigma^\*$

$unbar(a) = a, \space \space if\space a\in \Sigma$

$unbar(\overline a) = a, \space \space if\space a\in \overline\Sigma$

and

$rembar:\space (\Sigma\space \cup \overline\Sigma)^\* \rightarrow \Sigma^\*$

$rembar(a) = a, \space \space if\space a\in \Sigma$

$rembar(\overline a) = \epsilon, \space \space if\space a\in \overline\Sigma$

Now, proof

$L\_1 = unbar^{-1}(A)$

```
L_1 is CFL because A is CFL and CFL is closed under inverse homomorphism.
L_1 is set of strings in A with arbitrary letter annotated with bars.

```

$L\_2 = unbar^{-1}(B)$

```
L_2 is a regular because regular set is also closed under inverse homomorphism.
Meaning of L_2 is similar to above.

```

$L\_3 = L\_2\space\cap\space\overline\Sigma^\* $

```
Now L_3 is also regular because L_2 is regular and regular set is closed under intersection.
L_3 is set of strings in B with every letter annotated with bar.

```

$L\_4 = \Sigma^\*L\_3$

```
This too is regular.

```

$L\_4$ is set of strings of form $xy, x\in \Sigma^\*$ and $y$ is string in B with every letter annotated by bar.

$L(A/B) = rembar(L\_1 \space\cap\space L\_4)$

```
Now this is CFL because L_1 is CFL and L_4 is regular and CFL is closed under regular
intersections.

```

Now this is little hard to explain but you may infer the meaning.

Inshort, $L(A/B) = rembar(unbar^{-1}(A) \space\cap\space (\Sigma^\*(unbar^{-1}(B)\space\cap\overline\Sigma^\*)))$

```
All operations used preserve Context-free-ness so L(A/B) is CFL.

```

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Using function composition to turn a function into point free one
In Tacit Programming page on wikipedia, it is stated that the point free version of

`p x y z = f (g x y) z` is
`p = ((.) f) . g`

and that the point free version of

`mf criteria operator list = filter criteria (map operator list)` is
`mf = (. map) . (.) . filter`.

I can not figure out how can we get from one side to the other, in either way. Would you please show me a step by step explanation of why those equivalences hold?

# Answer
Going from the point-free version to the lambda version is mechanical. Remember that composition is defined by `(f . g) = (.) f g = \x. f (g x)`, so `(f . g) x = f (g x)`. Remember also that `(f . g)` is syntactic sugar for `(.) f g` and `f x y` is shorthand for `(f x) y`. It's easier to follow what's going on if you apply one argument at a time.

```
p = ((.) f) . g
p x = (((.) f) . g) x = ((.) f) (g x) = (.) f (g x)
p x y = (p x) y = ((.) f (g x)) y = (.) f (g x) y = (f . g x) y = f (g x y)
p x y z = (p x y) z = (f (g x y)) z = f (g x y) z

```

To go in the other direction, arrange the function calls so that there is a single occurrence of the function's parameter in the function body, and arrange it to be at the end of the call. In addition to `.` for composition, this may require the use of auxiliary functions such as `flip` to change the order of arguments.

```
p x y z = f (g x y) z
p x y = f (g x y)
p x = \y. f (g x y) = \y. f ((g x) y) = \y. (f . g x) y = (f . g x) = ((.) f) (g x)
p = \x. ((.) f) (g x) = \x. ((.) f . g) x = ((.) f . g)

```
> 4 votes

# Answer
I found the following at \[Haskell-cafe\] Exercise in point free-style which states that:

```
func2 f g l = filter f (map g l)
func2 f g = (filter f) . (map g)    -- definition of (.)
func2 f g = ((.) (filter f)) (map g)    -- desugaring
func2 f = ((.) (filter f)) . map    -- definition of (.)
func2 f = flip (.) map ((.) (filter f)) -- desugaring, def. of flip
func2 = flip (.) map . (.) . filter     -- def. of (.), twice
func2 = (. map) . (.) . filter      -- add back some sugar

```
> 0 votes

---
Tags: functional-programming, programming-paradigms
---


# Question
Title: Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass?
In *Types and Programming Languages* by Pierce, Section 18.6 Simple Classes in Chapter 18 Imperative Objects says:

> We should emphasize that **these classes are values, not types.** Also we can, if we like, create many classes that generate objects of exactly the same type. **In mainstream object-oriented languages like C++ and Java, classes have a more complex status—they are used both as compile-time types and as run-time data structures.** This point is discussed further in §19.3.

The only place which Section 19.3 Nominal and Structural Type Systems says about classes is:

> These type names play a crucial role in Java’s subtype relation. Whenever a new name is introduced (in a class or interface deﬁnition), the programmer explicitly declares which classes and interfaces the new one extends (or, in the case of a new class and an existing interface, “implements”). The compiler checks these declarations to make sure that the facilities provided by the new class or interface really extend those of each super-class or super-interface— this check corresponds to record subtyping in a typed lambda-calculus. The subtype relation is now deﬁned between type names as the reﬂexive and tran- sitive closure of the declared immediate-subtype relation. If one name has not been declared to be a subtype of another, then it is not.

Does the above quote or some other places in Section 19.3 explain the second highlighted sentence in the first quote from Section 18.6, i.e. why

> In mainstream object-oriented languages like C++ and Java, classes have a more complex status—they are used both as compile-time types and as run-time data structures

? (I don't see Section 19.3 mentions that a class is a type of objects in mainstream OO languages, and even explains it.)

In Chapter 18 Imperative Objects, is an interface a type of objects?

In mainstream OO languages (such as Java, C#, I am not sure if C++ has interface),

* is an interface a type of objects?

An interface seems to me a type of classes, since many classes can implement the same interface. Since a class is a type of objects, is an interface a *kind*?
* Is an abstract class essentially the same concept as an interface? (In terms of being a type of classes or something else)
* in Python, there is another concept "metaclass". Is a metaclass a type of object, a *kind*, or something else?

I have a related post a while ago: Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?. It also introduces concept "metaclass" of Python, and my confusions between interface, class, abstract class, and metaclass. Appreciate if you could also take that into account.

Thanks.

# Answer
> 3 votes
Unfortunately I don't have a copy of TAPL with me, so I can't figure out exactly what the author intends. But there is a point we should make, that types are something which classifies terms or values, even if there are other pieces that are related to the type.

As such, classes and interfaces are not literally types themselves in Java or C++. Rather, each instance of a class/interface defines a few things simultaneously:

* At runtime, we associate with each such defined class, a table of details. This can include where to find code for overrideable methods, but also information like which methods exist, what fields and the like, for reflection.
* Both at compile time, and runtime, it defines a type with the same name, which denotes those objects whose runtime class is a subclass of said class. So here we have a distinction we can make: Each object has exactly one class, but belongs to potentially many different types (the transitive reflexive closure of the subtyping relation).

This is different from the situation in something like OCaml, or likely, those simple objects in TAPL. If there is no means of distinguishing which class created an object, we likely do not want to associate it with a type (as we cannot do anything different with it). In particular, classes in OCaml define a means of constructing an object, so they are a value (just as in the function x -\> x + 2).

Following this reasoning, we can think about what metaclasses imply for Python. When we define a metaclass, it creates a particular object, much the same as any other Python object. This portion is a value. Now, later code may reference that value for construction of classes. As stated, we haven't quite made them relate to types yet.

And from here, the answer really comes down to what we decide the types are. It is reasonable to say that objects have a type based on their class (Note again, this is distinct from the denotation given by the type function in Python, which returns a value related to our type). In this situation, yes, metaclasses can be considered to define a kind, as to each class-type, we have an associated metaclass. But we'd be just as reasonable to not consider anything here to be types, and to work only with values and functions.

To really talk about this, we might want to say that Python has a reflection principle: for every class value, we have an associated class type, and vice versa. Extending this we can talk about metaclasses as kinds, (but that will begin requiring subkinding, which may be undesirably complex).

So the key point of distinction we come down to is this: types are classifications, and values are concrete data structures. There can certainly be relations in languages which have run-time type information, but they are not literally identical, and there may be multiple sorts of things defined simultaneously.

# Answer
> 1 votes
There is just nothing that you can generalise. Every language is different.

A class describes what instances of the class (objects) look like. In Java, a class is also an object in its own right. All classes are instances of a class named "class", which allows the programmer to ask the class for example "what is your name", "what are the instance variables of your instances" and so on.

An interface describes what are the requirements for a class so it can claim it implements the interface. Again, in Java an interface is also an object in its own right. In Java, there are no instances of an interface. There are only instances of classes, and some classes implement some interfaces, so you can say "this object is an instance of some class that implements the interface".

C++ doesn't have interfaces. Some people claim that abstract classes are interfaces, they are not.

In Swift, "interfaces" are called protocols, and protocols actually have instances (which refer to some other object that implements the protocol).

So every language is different.

---
Tags: programming-languages, type-theory, object-oriented, types-and-programming-languages
---


title: confused with Time Complexity

text:
# Question
Title: confused with Time Complexity
I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true?

1) $n = o(n\log\log n)$

2) $n\log\log n = o(n\log n)$

3) $n\log n = o(n^2)$

# Answer
Basically, when you see $f(x)=o(g(x))$, it indicates that $\lim\_{x\rightarrow\infty}\frac{f(x)}{g(x)}=0$. If you plug them in, e.g., $\lim\_{x\rightarrow\infty}\frac{n}{n\log\log n}=\lim\_{x\rightarrow\infty}\frac{1}{\log\log n}=0$, you will see they satisfy it.
> 1 votes

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: How to find min or max in constant time using infinite # processors?
Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ability to perform concurrent writes

I have tried dividing up the numbers into groups of 2 each and then using $n/2$ processors at the first step and then $n/4$ processors on the output of the first step etc. I can't see how to make use of more than $n/2$ processors given that I have $\infty$ of them

# Answer
> 4 votes
I managed to solve this so hoping it's alright to answer your own question. Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number against every other number on $n \choose 2$ processors. Each processor switches the bit corresponding to the smaller of its two elements to 1. Assumption is that the processors can do concurrent writes to $A$. The bit in $A$ remaining off denotes the maximum element.

This is $\Theta(1)$ (constant time) as the depth of the computational graph is independent of the number of elements. The work required is however $\mathcal {O(n^{2})}$.

# Answer
> 0 votes
You can get constant time if you use n^2 processors. Basically, every processor makes 1 comparison and writes a 0 to a shared memory array of size n if their comparison is smaller. The index in the array with a 1 left in it at the end is the max.

# Answer
> -1 votes
If you find max and min using recursion, then the best case complexity is O(log n). So, I think you can get constant time, by dividing the work into n parts and assigning each of that partition to a processor. Infinite processors can be used only when n is too large.

---
Tags: algorithms, parallel-computing
---


# Question
Title: Efficient algorithm for assigning weights to nodes in graph to create steady state flow
I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:

**Definitions**: Given a graph $(V,E)$, with non-negative weights assigned to it's edges $w\_E:E \rightarrow \mathbb{R}^+\cup\\{0\\}$ and non-negative weights assigned to it's vertices $w\_V:V \rightarrow \mathbb{R}^+\cup\\{0\\}$ we define the flow on the edge $e=(v\_1,v\_2)\in E$ to be the wight of the vertex where the edge starts times the weight of the edge, $f(e=(v\_1,v\_2)) \equiv w\_V(v\_1)\cdot w\_E(e)$. The inward flow to vertex $v\in V$ is defined by the sum of the flows on all inward edges $f\_{in}(v) = \sum\_{e\in E\\;s.t.\\; e=(u,v)}f(e)$ and the outward flow the sum of flows on all the outward edges $f\_{out}(v) = \sum\_{e\in E\\;s.t.\\; e=(v,u)}f(e)$.

**The Problem** Given a finite directed graph $(V,E)$ and an edge weights assignment $w\_E$, find a **non-trivial** weights assignment to the vertices $w\_V$ such that the inward flow and the outward flow are equal for each vertex, $\forall v\in V\\; f\_{in}(v) = f\_{out}(v)$. The trivial solution is $w\_V\equiv 0$. Notice that I'm only looking for one non-trivial solution (there could be more than one). If there is no non-trivial solution the algorithm should return some error message.

Any ideas? Thank you for your help

# Answer
I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer).

You can solve this problem by using linear programming in similar manner to finding maximal flow.

$\forall\_{v \in V} w\_V$ is constant.

$\forall\_{e \in E} w\_e$ is variable.

Firstly, for each node we want to be sure that inward flow is equal to outward flow: $$\forall\_{v \in V} \sum\_{(v\_{i}, v)\in E}w\_{v\_{i}}w\_{(v\_{i}, v)} = \sum\_{(v, v\_o)\in E}w\_{v}w\_{(v, v\_o)}$$

Then we want to be sure, that every edge is non negative: $$\forall\_{e \in E} w\_e \geq 0$$

You can notice, that if there is any non-trivial solution then there are infinitely many, arbitrary large flows (you can multiply weight of every edge by constant $c$ and it will be still valid). So if there is any non-trivial solution, then there is a solution with sum of weights of edges not smaller then 1: $$\sum\_{e \in E} w\_e \geq 1$$

Now what's left is to check if there is a solution for this linear programming instance.
> 0 votes

---
Tags: graphs, network-flow, weighted-graphs
---


# Question
Title: What is an efficient data structure for prefix matching?
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to `words[i].toLowerCase().startsWith(pattern.toLowerCase())`.

A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.

I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.

For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.

**Example:**

```
Dictionary: [banana, apple, banter, orange]

Pattern: ban
Return: banana (any match)

Pattern: grapes
Return: null

```

# Answer
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.

If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors.

Another data structure to consider is to store every prefix of each word in a hashtable. This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice. The asymptotic running time will remain the same. You'll have to decide whether you're willing to trade off space for time.

Suffix trees and suffix arrays don't seem relevant. You're asking about prefix matching, not suffix matching or matching in the middle of the string.
> 6 votes

# Answer
Another possibility would be to store all the words in an array, sort it, and then do lookups on it using binary-search.

Disadvantages compared to a Trie:

* Worse asymptotic time complexity for lookups ($O(\mathrm{log}\ n)$ average where n is the number of entries).
* Probably less efficient to insert additional entries, as the array will need to be resized.

Advantages compared to a Trie:

* Probably more efficient to build if all entries are added in one go with no further modification.
* Uses less memory.
* Lookups are probably more CPU-cache friendly if the array isn't too large, due to the entries being consecutive in memory (see locality).
> 1 votes

---
Tags: data-structures, search-algorithms, strings, substrings
---


# Question
Title: Efficient data structure for matching 3D lines
I'd like to

* Store a set of many infinite undirected 3D lines.
* Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?"

The incidence-checks would of course have to be fuzzy to account for floating-point errors.

### Question:

What would be a good data structure to implement such a set?

### My thoughts so far:

Each line is originally represented as:

$$\begin{align\*} p &= \text{an arbitrary point on the line} &= 3 \\;\text{floats} \\ v &= \text{an arbitrary vector parallel to the line} &= 3 \\;\text{floats} \end{align\*}$$

To facilitate lookups, this should probably be converted such that coincident lines turn into the same tuple of floating-point numbers (within the margin of error). For example like this:

$$\begin{align\*} p' &= \text{the point on the line closest to}\\;(0,0,0) &= 3 \\;\text{floats} \\ v' &= \text{normalized direction vector} &= 2 \\;\text{floats} \end{align\*}$$

Where "normalized" means unified (that's easy) and reversed in half the cases (this will be a bit tricky to do without introducing inconsistencies).

And then I'd just need a data structure for fuzzy look-up of tuples of 5 floats.

* A 5-dimensional Binary Space Partitioning Tree, maybe?
* Or just multiply the 5 floats together to get one float per line, use them as keys in a sorted map (e.g. `std::multimap<double, Line3D*>` in C++ or `TreeSet<Double, List<Line3D>>` in Java), and do range lookups like $\[x - \epsilon, x + \epsilon)$ for a given key $x$ and error margin $\epsilon$ and then only do the full incidence check for each line in that range?

Or maybe there's an altogether different approach?

# Answer
Any line can be represented in the form $\\{p + xv : x \in \mathbb{R}\\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line. Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\\|v\\|\_2$). Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we can take $p$ to be a point whose $z$-component is zero.

So, let's represent any line by the pair $p,v$, where $v$ is chosen to have norm 1 and where $p$ is chosen to have its $z$-component be zero. Then this is a canonical representation of the line: each line has a unique representation, and two lines coincide iff their $p,v$-representations are identical.

This means that you can store each line in a hash table, where you store the pair $p,v$. Thus, it is a hash table where each key is a 6-tuple. You could compress it so each key is a 4-tuple (you can represent $v$ with 2 dimensions, and you only need to store the $x$\- and $y$-components of $p$), but this probably doesn't gain you much.

To deal with floating-point errors, you could round $p,v$ to the nearest multiple of $\epsilon$ before storing it in the hashtable. Or, you could store it in a data structure that supports nearest neighbor queries, such as a k-d tree.
> 2 votes

---
Tags: data-structures, computational-geometry, sets
---


# Question
Title: Solve recurrence relation that depends on depth of recursion
The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is:

> A frog is sitting on the edge of a pond facing the opposite bank. In front of the frog, running along the pond's diameter, is a line of $N$ lilypads. This is a very athletic frog: it is able in a single leap to land on any of the $N$ lilypads in the pond or on the opposite bank (for a total of $N + 1$ possible destinations). The frog first considers all $N+1$ positions in front of it, chooses one randomly with uniform probability, and then jumps to this location. It then repeats the process of choosing a new random position from those remaining in front of it (never jumping backwards). This goes on until the frog eventually reaches the opposite bank.
>
> The puzzle is twofold: First, if $N=10$, what is the expectation value of the number of jumps the frog will take to reach the other side of the pond? Second, find an explicit formula (NOT a recurrence relation!) for the expectation value of the number of jumps in general for $N$ lilypads.

(It's a great puzzle; if you haven't yet given it a shot, I'd highly recommend doing so before reading any possible spoilers in the rest of this post!).

To attempt this puzzle, I first calculated the first few terms by hand and then tried to generalize my result. I eventually came up with a recursive algorithm for the expectation value $f$:

```
def f(n, depth=1):
    if n == 0:
        return depth
    else:
        return (n * f(n - 1, depth) + f(n - 1, depth + 1)) / (n + 1)

```

However, the second part of the puzzle explicitly disallows recurrence relations as solutions, so I am trying to un-roll/solve the recurrence relation. There are already several questions on strategies for solving recurrence relations (see this and this), but none I can find on solving recurrence relations which are dependent on the depth of recursion. Any help on how to do this is appreciated.

# Answer
> 2 votes
diplodoc explained in the comments one way to solve the recursion. Your recursion is $$ A\_n = 1 + \frac{A\_0 + \cdots + A\_{n-1}}{n+1}, \quad A\_0 = 1. $$ The trick is to calculate $$ (n+1)A\_n - n A\_{n-1} = (n+1 + A\_0 + \cdots + A\_{n-1}) - (n + A\_0 + \cdots + A\_{n-2}) = 1 + A\_{n-1}, $$ and so $A\_n = A\_{n-1} + 1/(n+1)$. From here it follows easily that $A\_n$ is the $(n+1)$th harmonic number.

---

Another possibility is to use generating functions. Let $$ P(x) = \sum\_{n=0}^\infty A\_n x^n. $$ Since $\frac{1}{1-x} = 1 + x + x^2 + \cdots$, it follows that $$ \frac{xP(x)}{1-x} = \sum\_{n=0}^\infty (A\_0 + \cdots + A\_n) x^{n+1}. $$ Integrating, we get $$ \int\_0^x \frac{yP(y)}{1-y} \\, dy = \sum\_{n=0}^\infty \frac{A\_0 + \cdots + A\_n}{n+2} x^{n+1}. $$ It follows that $$ \frac{1}{1-x} + \frac{1}{x} \int\_0^x \frac{yP(y)}{1-y} \\, dy = P(x). $$ In terms of $Q(x) = \int\_0^x \frac{yP(y)}{1-y} \\, dy$, this reads $$ \frac{1}{1-x} + \frac{Q(x)}{x} = \frac{(1-x)Q'(x)}{x}, $$ which simplifies to $$ \frac{x}{1-x} + Q(x) = (1-x)Q'(x) = \[(1-x)Q(x)\]' + Q(x), $$ and so $$ (1-x)Q(x) = \int^y \frac{y}{1-y} \\, dy = \int^y \left(\frac{1}{1-y}-1\right) \\, dy = C - x - \log(1-x). $$ It follows that $$ Q(x) = \frac{C-x-\log(1-x)}{1-x}. $$ Since $Q(0) = 0$, we deduce $C = 0$. Differentiating and multiplying by $(1-x)/x$, we find that $$ P(x) = \frac{-\log(1-x)}{x(1-x)} = \frac{\sum\_{n=0}^\infty x^n/(n+1)}{1-x}, $$ from which we can extract the coefficient of $P(x)$ to be $H\_{n+1}$.

---

Finally, we can solve this without using *any* recurrences. Consider a random permutation of the numbers $1,\ldots,n+1$, which we think of as the $n$ places and the goal. The frog jumps to the first number. If it is not $n+1$, it scans the list to the first larger number, and jumps there. Repeat in this way, until you get to $n+1$. You can check that this defines the same random process.

Given a permutation, the number of jumps is the number of *left-to-right maxima*, that is, elements which are larger than all that precedes them. The probability that the $i$th number is a left-to-right maximum is exactly $1/i$, and so linearity of expectation shows that the expected number of jumps is $1 + 1/2 + \cdots + 1/(n+1)$.

---

As a bonus, the last solution allows us to calculate higher moments of the distribution. The main observation is that the indicator variables $X\_i$ for the $i$th number being a left-to-right maxima are *independent* Bernoulli random variables. This implies that the variance of the number of left-to-right maxima is $$ \sum\_{i=1}^{n+1} \frac{1}{i} \left(1-\frac{1}{i}\right) = H\_{n+1} - \sum\_{i=1}^{n+1} \frac{1}{i^2} = H\_{n+1} - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right). $$

One checks that the central limit theorem applies, and so the total number of left-to-right maxima is asymptotically normal.

---

Why is the answer roughly $\log n$? One might expect the answer to be closer to $\log\_2 n$, since at each step, $n$ is roughly cut in half. However, this argument assumes that the changes to $n$ are *additive*, whereas in reality they are *multiplicative*. It is better to consider instead the effect of each step on $\log n$. If $m$ is the new value of $n$, then the expected value of $\log m$ is $$ E\[\log m\] = \frac{\log 1 + \cdots + \log n}{n+1} \approx \frac{1}{n}\int\_0^n \log x \\, dx = \left.\frac{1}{n} (x\log x-x)\right|\_0^n = \log n - 1. $$ Therefore the value of $\log n$ decreases by roughly 1 each step, and so we expect the number of steps to be around $\log n$ rather than $\log\_2 n$.

(With some work, this intuition can be made rigorous.)

---
Tags: algorithms, algorithm-analysis, recurrence-relation, recursion
---


# Question
Title: Proving a language is not regular using the Myhill-Nerode Theorem
I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.

1. $\\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\\}$
2. $\\{w \in\\{0,1\\}^{\ast}\mid w\text{ is not a palindrome}\\}$

For the first question, I did the following:

I considered the set $\\{0^n1^m \mid{} m,n\ge 0\\}$. To prove that this set is pairwise distinguishable by the original language, I said that for all $m$ and $n$, $0^n1^m$ is distinguishable from all previous $0^i1^m,\\:0\\:\le i\le n-1$ because there exists a $z=0^n$ such that $0^n1^mz$ is an element of the original language but $0^i1^mz,\\:0\le i\le n-1$ is not an element of the original language.

I first want to ask whether this was indeed the correct way to do the proof?

I am also quite confused for the second question as I can't even seem to find a string that is part of the language but is a palindrome. All the strings other than the empty string in that language are not palindromes. So I am quite confused on how to approach the problem.

Any help would be highly appreciated!

# Answer
> 3 votes
The words $0^n1$ are pairwise distinguishable, since $0^n10^n$ is a palindrome but $0^n10^m$ isn't (for $n \neq m$).

With a bit more work, you can show that in fact *all* words are pairwise distinguishable. See for example here or here.

---
Tags: regular-languages
---


# Question
Title: Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$
So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, but how can I find both upper and loewr?

# Answer
It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$\- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".
> 2 votes

# Answer
It automatically implies that $ O(n^4)$ and $\Omega (n^4)$ because of $f(n)\in O(n^4)$ and master theorem $ \Theta (n^4)$.
> 0 votes

---
Tags: algorithm-analysis, recursion, lower-bounds, upper-bound
---


# Question
Title: Is the Kleene star of an intersection always equal to the intersection of kleene stars?
I know that the Kleene star of an intersection is contained in the intersection of Kleene stars, but are they necessarily equal?

For example, given two formal languages, $A$ and $B$, I know that $(A\cap B)^\*\subseteq A^\*\cap B^\*$, but does $(A\cap B)^\*= A^\*\cap B^\*$?

# Answer
Clearly not.

Let $A=\\{a\\}$ and $B=\\{aa\\}$.

Now,

$A\cap B = \emptyset$

so

$(A\cap B)^\* = \\{\epsilon\\}$

but

$A^\*\cap B^\*=B^\*=\\{a^{2i} : i \in \mathbb{N}\\}$

(all strings consisting of an even number of $a$).
> 4 votes

---
Tags: formal-languages, kleene-star
---


# Question
Title: Class of languages recognised by a Forgetful Turing Machine
A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, regardless of the current state and the current letter (although the read/write head is still allowed to move either Left or Right, according to the instruction). What class of languages is recognised by FTMs?

Is the language non-empty with only the letter $a$? Does this mean that it is regular since it can be represented by $aa^\*$?

# Answer
> 0 votes
The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.

Given a FTM $F$ with the set of states $Q$, we use the Myhill–Nerode theorem to show the language it recognizes is regular. Given a string $x$, we ask the following query:

1. If $F$ runs on $x$, does $F$ ever leave $x$ to the right? If so, in which state is $F$ when it first moves to the first position to the right of $x$? If not, does $F$ accept $x$?

... and the following $|Q|$ queries for each state $q\in Q$:

2. If $F$ runs on $\underbrace{a\cdots a}\_\text{the number of $a$ = $|x|$}$, but is started on the rightmost $a$ and in state $q$, does $F$ ever leave the input to the right? If so, in which state is $F$ when it first moves to first position to the right of the input? If not, does $F$ accept the input finally?

We collect the strings that give the same answers to the $|Q|+1$ queries above into the same class. Since there are $(|Q|+2)^{|Q|+1}$ possible answers to the $|Q|+1$ queries above, there are only finite many classes. Next, we are going to prove that for any strings $x,y$ in the same class, i.e., that give the same answers to the $|Q|+1$ queries, for any string $z$, $F$ accepts either both or neither of $xz$ and $yz$, which completes the proof by the Myhill–Nerode theorem.

Consider that $F$ runs respectively on $xz$ and $yz$. Note the answers to query 1 are the same for $x$ and $y$, there are two cases:

1. $F$ never leaves $x$ to the right on $xz$, and $F$ never leaves $y$ to the right on $yz$. In this case, $F$ runs as if the inputs are respectively $x$ and $y$. Since the answers to query 1 are the same for $x$ and $y$, $F$ accepts either both or neither of $xz$ and $yz$.
2. $F$ ever leaves $x$ to the right on $xz$, and $F$ ever leaves $y$ to the right on $yz$. In this case, $F$ is in the same state when it first moves to the leftmost position of $z$, so $F$ behaves the same until it returns respectively to the rightmost position of $x$ and $y$. According to the definition of FTM, the input must become $a\cdots a$ when $F$ returns, and we can apply a recursive analysis according to query 2 (you can use mathematical induction to write a strict proof). As a result, $F$ accepts either both or neither of $xz$ and $yz$.

Of course, the analysis above assumes the tape of the FTM is restricted such that the head cannot leave the input to the left. The proof is similar without this assumption.

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


# Question
Title: Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them
Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs?

Example 1: set(a, b, c, d, e) pairs(a\>b, ce)

Example 2: set(a, b, c, d, e) pairs(a\>b, d\>b, c\>d, d\>e)

# Answer
The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.

Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible orderings consistent with the partial order. I'm not sure that their algorithm is efficient, though. The best constant in the big O is the subject of the 1/3–2/3 conjecture.
> 1 votes

---
Tags: algorithms, graphs, optimization, sorting
---


# Question
Title: Why is {w | no prefix of w starts with b} = {w | the first character of w is a} ∪ {e}?
> \begin{align} L &= \\{ w \in \\{a, b\\}^\* \mid \text{ no prefix of $w$ starts with $b$}\\} \\ &= \\{w \in \\{a, b\\}^\* \mid \text{ the first character of $w$ is $a$} \\} \cup \\{e\\} \end{align}

Why is it in union with an empty string? If an empty string from $b$ can also be a prefix.

# Answer
> 3 votes
The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Can most programs (except the IO part) be re-written as a sequence of matrix operations?
I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to render the 3D world in a game) by processing the data in memory. All of these tasks could be done through a sequence (probably a graph) of matrix and vector operations, such as multiply, add, sum, etc.

For instance, I used to work for a car pool company, there was a piece of code to decide which car should respond to user. That logic was implemented with c++ stl containers and flow controls like if/else/break. Then I realized that it can be re-written as logistic regression (the business logic is stored in the linear predictive model) , with certain precision.

In this sense, matrix operation is a programming language by itself.

Can anyone share any thoughts here? Is there any introductory discussion wiki that I can read ?

# Answer
> 3 votes
If you regard the output of a program as a function of its input then matrices can be used to represent *some* programs, namely those where the output is a linear function of the input. So a program that takes two arguments $a$ and $b$ and returns $a+b$ and $a-b$ could be represented by the matrix

$\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

But most programs are not linear functions. For example, if the program instead returns $a^2+b^2$ and $a^2-b^2$ how will you represent that as a matrix ?

---
Tags: programming-languages, discrete-mathematics, functional-programming, mathematical-analysis
---


# Question
Title: Which parser has the highest reduce moves?
From what I have learned the number of reducing moves in the parsers are generally in the order

**LR(0)\>= SLR(1) \>= LALR(1)**.

But I am unable to understand where should I place CLR(1) in this category?

Is it **CLR(1)\>=LR(0)\>= SLR(1) \>= LALR(1)** ?

# Answer
The number of reductions in a successful parse is strictly dependent on the grammar, since every production must be reduced exactly once.

Consequently, all LR parsing algorithms which can parse a given grammar will parse all sentences accepted by the grammar using the same number of reduction steps (and the same number of shift steps).

The only moment in the parse where an extra reduction might possibly occur is just before an error action for a sentence which cannot be parsed by the grammar. The sequence of reduction/shift steps is still the same for all parsing algorithms up to and including the last shift; the only possible difference is some algorithms can perform more reductions before the error is noted.

This will be affected not only by the choice of parsing algorithm but also by the particular parse table compression algorithm used, since table compression generally involves replacing some error actions with the state default action in order to reduce table size. (Since the sentence is not recognised by the grammart, the parser will not be able to shift the lookahead token. So replacing an error action with a default reduction action must still produce an error before the lookahead token is shifted.)
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Minimum-cut with minimum number of edges
I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.

Firstly, let's state (for completeness) that an s-t cut is the partitioning of the vertices in the graph, into two parts, such that the source s is in one partition and the sink t is in the other. The cut-set is the set of edges that are going from vertices in the partition that contains s to those in the other partition.

There may be multiple s-t cuts that have the same capacity as the min-cut (with different sized cut sets). The problem that I wish to solve is, how to find the minimum s-t cut that also has the minimum size cut set?

For example, in the following graph where s = 0 and t = 4:

We can clearly see that the capacity of the minimum cut is 2. One possible way to get this is to take edges 0-2 and 1-3 (This cut set has size 2). Another possible way to do this is to take edge 3-4 instead (This cut set has size 1) which is the optimal answer.

I have researched about this question and some people are saying that we need to transform the edge capacity, C, of every edge to C * (|E| + 1) - 1, where |E| is the number of edges in the graph.

One such discussion here: https://codeforces.com/blog/entry/51748
Another such discussion here: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-minimum-cuts-in-flow-network

The problem is, I don't understand why this formula works. In particular, why do we need to multiply by (|E| + 1) and not some other number? I cannot see how multiplying by any other number would "change" the augmenting paths in the graph as stated in the cited links.

Could someone please advise me?

**Edit:** The offset in the formula should be +1 and not -1 in order to get the cut-set of the smallest size.

# Answer
Those answers assume that all edge capacities are integers. Assuming they are, this works.

Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger capacity, its original capacity will be $x+1$ or more, so its total capacity in the transformed graph will be $(x+1)(|E|+1)+k'$ for some $k'$ in the range $0 \le k' \le |E|$. Now

$$\begin{align\*} (x+1)(|E|+1)+k' &= x(|E|+1)+|E|+1+k'\\ &\> x(|E|+1)+|E|\\ &\ge x(|E|+1)+k, \end{align\*}$$

so any cut in the original graph that isn't a min-cut won't be a min-cut in the transformed graph, either.

In other words, any min-cut of the transformed graph will be a min-cut of the original graph.

Moreover, out of all of the min-cuts in the original graph, the one whose cut set is smallest is the one that will have lowest capacity in the transformed graph (since the transformation adds one for each edge in the cut set). So, the min-cut in the tranformed graph will be a min-cut in the original graph, and it will break ties by choosing the one with smaller cut set.
> 13 votes

---
Tags: algorithms, graphs, network-flow, minimum-cuts
---


title: packing with time-variant weights

text:
# Question
Title: packing with time-variant weights
*This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions.*

**Scenario 1: Tough (for me!)** There is a one day conference with a set of (4 or more) sessions. The conference will be attended by a number of companies, each one being represented by a (1 or more) representatives.

Across sessions the number of representatives for each company will vary (and may be zero), with each individual having the same chance of being present as any other individual (so there is an increasing likelihood of a company being represented when it has more representatives).

There is a single row of seats in the conference. There are more than enough seats for the most popular session. (e.g., if the most popular session has 100 delegates, there could be 120 seats for the whole conference).

**Constraints**

* A rep. belongs to one company
* A rep. must be seated in a session they are going to.
* A rep. must not change seats across consecutive sessions
* A rep. is assigned to one chair in each session they attend.

**Goal** To fit the constraints and priorities optimally. Example. 15 chairs, 4 companies (A-D), 4 sessions (S1-S4).

```
// Session attendees by company
S1: A2 B6 C3 D3
S2: A4 B5 C1 D2
S3: A3 B3 C4 D1
S4: A5 B2 C5 D0

// Possible solution (I did this manually!)
S1: [AA.BBBBBBCCCDDD]
S2: [AAAABBBBBC...DD]
S3: [AAA...BBBCCCC.D]
S4: [AAAAA..BBCCCCC.]

```

**Question** How can I solve this algorithmically? The algorithm doesn't have to be particularly fast but it does need to yield working results.

**Scenario 2: Tougher?!** The same as above but the row of seats has enforced break points (like pillars, walkways, etc). I think this latter issue is merely a 'knapsack'-type modification to the above problem

**Thoughts towards a solution** It seems that it should be possible to have consecutive seating available in most cases, which implies that a solution could be found by identifying company-invariant seats by filling the minimum company representation across all sessions, leaving gaps between companies that are somehow calculated based on the variation of the company and it's neighbour.

It is trivial to find cases where there is only a partial solution, eg the following, but that's okay. I still need to get the best solution I can.

```
S1:   [AAAACB]
S2:   [ACCCCB]

```

**Edit**: I managed to resolve this, using OR-Tools. It required 3 separate solvers in the end, in order to split the problem into tranches.

Tranche division is done with a solve for the rows, based on a count of seats to work per tranche. This uses two slack criteria to allow for (a) allocation wiggle room - and (b) one for an overflow (where there are large rows)!

Then a weight-change-over-each-session bin-packing variation to allocate organisations to the tranches.

Finally, seat allocation is managed. The seat allocation can manage about 100 representatives per tranche before it slows down due to scaling problems that seem to be inevitable with constraint programming systems. The constraints are as listed above. eg. for the constraint that one rep belongs to one company:

```
model.AddImplication(del_chairs[d_tuple], org_chairs[o_tuple])

```

# Answer
I'd suggest formulating this as an instance of SAT or ILP, then using an off-the-shelf SAT or ILP solver. This smells like the kind of problem that might be NP-hard in general and thus it might not be reasonable to expect a general, efficient algorithm that always outputs the optimal solution.

For example, if you only wanted to find a solution that meets all of the constraints, and you ignore the priorities, then you could express this as a SAT instance easily. You could use a one-hot encoding, where the boolean variable $x\_{i,j,k}$ if representative $i$ is assigned to seat $j$ in session $k$. Then each constraint can be translated into a logical predicate on these boolean variables and thus into SAT. I find the Z3 solver convenient for expressing these kinds of constraints.

To capture the priorities, you could introduce additional boolean variables, say $y\_{i,k}$ is 1 (true) if representative $i$ changes seat after session $k$ or 0 (false) otherwise, and then add constraints to capture the relationship between the $x$'s and $y$'s, and finally minimize the sum of the $y$'s, or require that the sum of the $y$'s be below some threshold $\tau$ and use binary search on $\tau$. For that, pseudo-boolean inequalities or integer linear programming might be useful.

There are many details that would need to be filled in. I'll let you work out the details.

See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP), Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, When to use SAT vs Constraint Satisfaction?, https://stackoverflow.com/q/43081929/781723 for some relevant reading. The operations research community and tools (e.g., OR-Tools) might also be relevant.
> 1 votes

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


# Question
Title: What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?
I know one can compute things using tail recursion with helper functions like:

```
let sum_helper n accumulator =
match n with
| 0 -> accumulator
| _ -> sum_helper (n-1) (accumulator+n-1);;

let sum_tail n = sum_helper n accumulator 0;;

sum_tail 3;;

```

which gives:

```
# sum_tail 3;;
- : int = 3

```

but I wanted an example of something that didn't use a helper function (idk if the above can be made without a helper function).

Ideally something simple so to understand the concept better since I'm trapped into thinking all tail recursions look like that.

# Answer
There's an example staring at you in the face: write a function that takes two arguments `a` and `b` and returns the sum of the integers from 0 to `a`, plus `b`.

Here's another example: write a function that returns the last element of a list, or a special value if the list is empty.

```
let rec last l =
  match l with
  | [] -> None
  | [x] -> Some x
  | h::t -> last t

```

Here's another example, in an imperative language: apply a function to all the elements of a list, in order, without returning a value.

```
let rec iter f l =
  match l with
  | [] -> ()
  | h::t -> f h; iter f t

```

So you can see that tail-recursive don't *have* to take an extra argument. However, taking an extra argument is a common pattern, and there is a deep reason for that.

A common reason to write a recursive function is to traverse a recursive data structure. For example, the list data structure is defined recursively: a list is either the empty list (“nil”), or a pair (“cons”) consisting of an element (“head”) and a list (“tail”). In Ocaml syntax:

```
type list_of_foo = Foo_nil | Foo_cons foo * list_of_foo;; (* Foo_cons (head, tail) *)

```

To act on a list, you need to specify what to do on the empty list, and what to do on a non-empty list. To traverse the whole list with a function, you make a recursive call to process the tail in the case of a non-empty list. A generic list traversal is called a fold. Writing a recursive function is one way to write a fold; another way is to call a generic `fold` function and tell it what to do with nil and what to do with a cons (as a function of the head and the result of processing the tail of the list).

This generalizes to all recursive data structures. A particularity of lists is that there's never more than one sub-list, so the call to process the tail can be a tail call. Contrast with a binary tree, for example:

```
type btree = Leaf of int | Node of btree * btree

```

To process a `btree`, when you reach a `Node`, you need to process both the first subtree (left child) and the second subtree (right child). They can't both be tail calls. But with lists, the one recursive call can be a tail call.

Integers don't look much like a data structure. But in fact recursion on an integer is typically based on the structure of integers. For example, when you recurse by enumerating integers from 0 to `n` or from `n` to 0 (or 1 to `n`, etc.), you're using the structure provided by the Peano axioms: an integer is either 0 or the successor of an integer.

So you have a recursive function which takes a data structure as an argument. It makes a recursive call, calling itself on a sub-structure of the original data. What does it return? If the recursive call is a tail call, what it returns has to be the value returned in a case where the function doesn't make a recursive call. Often, that's the “starting” case, e.g. 0 for a function that recurses on an integer or the empty list for a function that recurses on a list. What can you return in the starting case? If you return a constant, that's not very interesting. If you want to return something that depends on information collected from the data structure, you need to pass this information through the tail calls. And that's where the extra argument comes from. A tail-recursive function needs an extra argument (in addition to the data structure that it recurses over) to collect data read from the data structure.

In the starting case, you often do want to return a constant. Hence you write a pair of functions: a tail-recursive functions with two arguments (the data structure to traverse and the accumulator), which returns the accumulator when it reaches the end of the data; and an auxiliary function just to give an initial value to the accumulator. This corresponds to the initial value argument for `fold` functions.
> 2 votes

# Answer
This is an example:

```
let rec all_positive l =
match l with
| [] -> true
| x::xs -> if not(x>=0) then false else all_positive xs;;

```

the is to notice that the function always points to return the value of the next recursive function call AND also does the main computation first. So its not accumulating anything. I don't think it can be done if an accumulator is required.
> 0 votes

---
Tags: recursion
---


# Question
Title: Are there any NP complete problems in SUB EXP TIME?
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$

Has something like $O(2^\sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?

# Answer
> 7 votes
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known

# Answer
> 3 votes
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L \in NP-complete$. define $L'=\\{1^{n^c-n}l| l\in L\\& |l|=n \\}$ it is easy to prove that $L' \in NP-complete$ and there is a $O(2^{\sqrt\[c\]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(\log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.

---
Tags: complexity-theory
---