# Question
Title: Mathematically determine if two strings are permutations of each other
I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each string to char codes and perform mathematical operations on them to determine equivalence.

My idea was to sum up the char values of each and compare. Then multiply the values of each string and compare. If both the sum and product are the same for both strings then the strings are permutations of each other.

Note: this is assuming strings of equal length. instantly reject strings of different length.

example:
A = "abcd" = \[1, 2, 3, 4\] -\> Sum: 10 -- Product: 24
B = "bcda" = \[2, 3, 4, 1\] -\> Sum: 10 -- Product: 24

Sum A = Sum B and Product A = Product B therefore A is a permutation of B

Is there a case where this would not hold true? how would one go about proving this. I want it to be true because it would be more space efficient than https://stackoverflow.com/a/2145221/2001647 which also runs in O(n)

# Answer
> 3 votes
Your algorith isn't correct.

Take $abbc = \[1, 2, 2, 3\]$ and $acd = \[1, 3, 4\]$. Their product is $12$ and their sum $8$, yet they aren't permutations of each other; they don't even have the same length.

# Answer
> 3 votes
You need a function that uniquely maps *multi-sets* of symbols to numbers -- a *bijection*. Here is one example that is easy to understand.

Say your string is $w = w\_1 \cdot \dots \cdot w\_n$ over alphabet $\\{1, \dots, k\\}$. Denote with $m(w)$ the multi-set of its characters. Let $p\_i$ the $i$-th prime number. Then,

$\qquad\displaystyle p(w) = \prod\_{i=1}^n p\_{w\_i}$

has the required property, i.e.

$\qquad p(v) = p(w) \iff m(v) = m(w) \iff v$ is a permutation of $w$.

This follows directly from the uniqueness of prime factorizations and commutativity of integer multiplication.

This works fine and fast for small alphabets (say, Roman) but is horrible for large ones (say, Unicode).

---

In the unit-cost RAM model, of course, this has linear running-time and constant space cost, assuming a fixed and finite alphabet. But that's not a very useful model here.

For the logarithmic cost model, here's a start. The $k$-th prime is smaller than $k (\ln k + \ln \ln k)$, so the resulting number $p(w)$ has less than $n \cdot \log\_2(k (\ln k + \ln \ln k))$ bits (worst-case bound from string $k^n$). Depending on the multiplication algorithm you use, you can derive the time to compute this.

---

More practical alternatives:

1. Define *canonical forms*; for instance, sort the strings w.r.t. some ordering on your alphabet. Strings are permutations of each other if they have the same canonical form. Time: $\Theta(n \log n)$ per string, then $O(n)$ comparison.
2. Explicitly create the multi-set of characters in the strings and compare, e.g. using a dictionary data structure. One possible advantage is that you can update this set according to string operations. Time: $O(n \log k)$ when using balanced BSTs, plus $O(k)$ comparison of the dictionaries.
3. Similar: compute the Parikh vectors of the strings.

---
Tags: algorithms, strings, permutations
---


# Question
Title: minimize sum of primes with a lower bound on product
I can't quite figure out an algorithm for this:

Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n?

Example: 6 -\> 2\*3,

2308 -\> 2\*3\*5\*7\*11,

14 -\> 3\*5

Does anybody know how I would do this?

This is part of a research project I'm doing on finite automata right now.

# Answer
Your problem is: given $t$, find a set $S$ of primes whose sum is minimized, such that the product is at least $t$.

This is equivalent to: given $u$, find a set $S$ of primes whose sum is minimized, such that $\sum\_{p \in S} \log p \ge u$. (Simply take $u=\log t$.) This is a knapsack problem, so it can be solved exactly using standard dynamic programming algorithms, or you can find good (but not necessarily optimal) solutions using standard approximation algorithms. I'll summarize a few options below, but the knapsack problem is well-studied, so you can probably adapt any of the standard methods to your setting.

## Dynamic programming

There is a straightforward dynamic programming algorithm that solves your problem in $O((\log n)^3)$ time. We will construct an array $A\[\cdot,\cdot\]$ such that

$$A\[s,q\] = \max \\{\prod\_{p \in S} p : \sum\_{p \in S} p = s \text{ and } p \le q \text{ for all } p \in S\\},$$

i.e., $A\[s,q\]$ stores the largest possible product that is attainable from a set of primes that are all at most $q$ and that sum to $s$. You can fill in the contents of the array $A$ using a straightforward recursion:

$$A\[s,q\] = \max(A\[s,q^\*\], q \times A\[s-q,q^\*\]),$$

where $q^\*$ is the previous prime before $q$. We'll fill in this array only for values $q$ that are prime. If we fill in the array in order of increasing $s$ and increasing $q$, each entry is known will be known before it is first used.

Finally, once we've filled in the $A$ array, we can find the smallest $s$ such that there exists a prime $q$ such that $A\[s,q\] \ge n$ by iterating over all the elements of the array.

How much of the array do we need to fill in? In particular, what's the largest value of $s$ and $q$ we need to fill in? Well, we can show that $s \le (\lg n)^2$ suffices. Also, we certainly have $q \le s$. Therefore, we only need to fill in $(\lg n)^3$ elements of $A$, and the algorithm has running time $O((\log n)^3)$.

I suspect that it can be done faster, and in particular, we can probably restrict to smaller values of $q$ (in particular, I suspect $q= O(\log s) = O(\log \log n)$ probably suffices)... but this gives a simple algorithm that is easy to show correct. Also, it is possible to find a tighter bound on the largest possible value of $s$, but that's not really necessary: if you fill in all of $A\[1,\cdot\]$, then $A\[2,\cdot\]$, then $A\[3,\cdot\]$, etc., and check each one to find the first that has an entry that is $\ge n$, this will enable the algorithm to terminate as soon as it finds the smallest attainable $s$.

## Approximation algorithms

There are many possible approximation algorithms. A simple one is to use a greedy strategy: take the first $k$ primes, choosing $k$ as small as possible such that their product is at least $n$.

Why is this a greedy strategy? Well, we're trying to minimize $\sum\_{p \in S} p$ subject to $\sum\_{p \in S} \log p \ge n$. So, the greedy algorithm for that is to sort the primes in order of increasing value of $p/\log p$, and take the first $k$, for some $k$. But sorting the primes in increasing value of $p/\log p$ is equivalent to taking the primes in increasing order ($p=2,3,5,7,11,\dots$).

There are other standard ways to improve on this.

Another approach is to formulate this as an instance of integer linear programming and feed it to an ILP solver. We want to minimize $\sum\_{p \in Q} p x\_p$ subject to $\sum\_{p \in Q} (\log p) x\_p \ge n$, where $x\_2,x\_3,x\_5,x\_7,\dots$ are the unknowns and each is constrained to be zero or one, where $Q$ is the set of primes $\le \lg n$. That's an ILP instance, so you can give it to an ILP solver and let it grind away at it.
> 2 votes

# Answer
I'll suggest a very simple and very fast algorithm that I believe produces the correct result unless n is very large.

Step 1: If n = 1 the solution is {}. If n = 2 or n = 3 the solution is { n }. Otherwise, find the smallest prime p such that the product of the primes from 2 to p is ≥ n. Let S = the set of primes from 2 to p, let P = the product of the primes from 2 to p. If p \< 2n then the result is S.

Otherwise, let r be the largest prime such that P / r ≥ n. Also, let q be the smallest prime \> p, and let r' be the largest prime such that (P * q / p) / r' ≥ n. If r' - r \> q - p then the result is S + { q } - { r', p }, otherwise the result is S - { r }.

The first n where this doesn't give the optimal solution is n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1 ≈ $2.622·10^{36}$.

Reasoning: We would want to use the smallest primes possible, because the ratio P / log p grows as p grows (with the exception of the primes 2 and 3). The exception is when we have a product that is quite a bit larger than n, and may get a product closer to n with a smaller sum.

If P \< 2n, then we might replace p with a larger prime q and remove the prime 2 from the product. But q ≥ p + 2, so the sum of primes will not get smaller.

If P ≥ 2n, then removing the largest possible prime from the product will obviously make the product smaller. This does *not* give the optimal solution if for example P / 7 ≥ n but P / 11 \< n, the next prime after p is q = p + 2, and replacing p with q in the product means that (P * q / p) / 11 ≥ n. In this case we increased the sum by 2 replacing q with p, and decreased it by 4 replace r with r'. But the algorithm will find this case.

This does *not* detect the case where replacing p with the next prime after q would improve the sum. Let q be the smallest prime \> p, and q' the smallest prime \> q. We know that q' ≥ p + 6 because p, p+2 and p+4 cannot all three be prime. So we might not find the optimal solution if the prime after r is r+8.

This is the case for the first time when r = 89 and the next prime is 97 = p + 8. If p = 101, then q = 103 and q' = 107 = p + 6. So take n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1: We need all the primes up to p = 101 to have a product P ≥ n. We can leave out r = 89 from that product, but not 97 because the remaining product is much smaller than n. If we exchange 103 for 101, we still cannot remove 97 because the product would be n-1. But we can exchange 107 for 101 and remove 97 instead of 89 from the product, getting a sum that is smaller by 2. So the optimal solution here is { 2, 3, ..., 83, 89, 107 } where the algorithm will return { 2, 3, ..., 83, 97, 101 }.
> 2 votes

---
Tags: algorithms, discrete-mathematics, knapsack-problems, primes
---


# Question
Title: Absorbing Markov Chains: An efficient algorithmic approach
Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows:

1. Given the transition matrix (P), row and column swap until the identity matrix is in the bottom right corner.

$$ P = \begin{bmatrix} Q & R \\ 0 & I \end{bmatrix} $$

2. Calculate the matrix N, and multiply by R to give the final probability matrix (B).

$$N = (I-Q)^{-1}$$ $$B = N\*R$$

Where the values in B represent the probability of moving from an initial non-absorbing state (rows) to a final absorbing state.

**My question is** if there is a more efficient method for solving this problem *if I know what my initial state is*. It seems wasteful to calculate the entire B matrix, given that I will only ever use one row in it.

I am writing a program to do this, so the matrix inversion step is particularly inefficient. Can I avoid this altogether?

# Answer
> 3 votes
There are several possible techniques.

Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)\_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start in state $i$, you'll end in state $j$ after $t$ steps. If $t$ is sufficiently large, this is a good approximation to the limiting value as $t \to \infty$.

So, one possible technique is to choose a sufficiently large value of $t$, compute $P^t$, and then evaluate $(P^t)\_{i,j}$. Notice that you can compute $P^t$ using $O(\lg t)$ matrix multiplications using the square-and-multiply algorithm, so it is possible to choose a very large value of $t$. Unfortunately, if $P$ is a $n\times n$ matrix, this will be slow: it will take $O(n^3 \log t)$ time, which is significant if $n$ is very large.

Another option is to use the power iteration method as used in the PageRank algorithm. Basically, you set the vector $x^0$ to be a vector that $1$ in its $i$th element and all zeros elsewhere. Then, you iteratively compute

$$x^{k+1} = P \cdot x^k.$$

After $t$ steps, you have computed $x^t$; now you read off the $j$th element in that, i.e., $(x^t)\_j$, and that is the probability after $t$ steps. If $P$ is dense, each iteration takes $O(n^2)$ time, for a total of $O(n^2 t)$ time. That might be better than the previous method, but still not too encouraging if $n$ is very large. However, in many real applications, $P$ is sparse, and thus each iteration can be computed in $O(n)$ time; in this case, the method takes $O(nt)$ time, which can be quite efficient.

How large does $t$ need to be? In practice, often $t$ doesn't need to be very large. You can analyze how large $t$ needs to be, as a function of the gap between the first largest and second largest eigenvalue of $P$. In particular, if $\lambda\_1$ denotes its first largest eigenvalue and $\lambda\_2$ its second largest eigenvalue, for a Markov process we have $\lambda\_1 = 1$ and $\lambda\_2 \le 1$. Now effectively we need $t$ to be large enough that $\lambda\_2^t$ is much smaller than $1$ (negligible compared to $1$). If $\lambda\_2$ is not too close to $1$, then $t$ won't need to be very large. In particular, $t = O(\log(1/(1-\lambda\_2)))$ iterations suffices.

As a result, the power iteration method can often be very effective and very efficient.

---
Tags: algorithms, graphs, linear-algebra, matrices, markov-chains
---


# Question
Title: Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)
I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials)

```
def generate(current_timetable, unallocated_courses):
    if conflicts(current_timetable):
        return
    if not unallocated_courses:
        results.add(current_timetable)
        return
    course = first(unallocated_courses)
    for section in course:
        new_timetable = copy(current_timetable) + section
        generate(new_timetable, rest(unallocated_courses))

```

(Storing results as a flat list for now)

Probably room for memoization in there, but that part of the program is fast enough already.

Now, since this generates too many timetables to easily compare, I decided to group them into 'families', which are connected undirected graphs of timetables in which you can navigate between any two nodes by swapping one section at a time for another. As a result, I get around ~10 very differently shaped timetables that I can subjectively compare.

My naive O(n^2) approach was to take every single combination of 2 nodes, build an adjacency list based on the delta between each pair, and then find connected components with BFS.

If I store results in a tree (i.e. non-leaves are incomplete timetables, root is empty, each child has 1 more course allocated than its parents, and the leaves are the completed timetables), is there any insight about this structure that could make finding connected components faster?

I realize that immediate siblings would be connected in the final graph, since their only difference is which section (of the course that their parents is missing) was picked, but there can also be leaves that are identical except for e.g. their grandparents, and those are the ones that I can't seem to detect without the O(n^2) approach.

To clarify: Each course has a bunch of sections. At each level of the tree, a certain course is considered, and for each section in that course, a subproblem is created.

For example:

At level 1, different sections of course A are considered. At level 2, different sections of course B are considered.

Here's sample output with 2 families (sorry about the current interface): https://dmitry.lol/public/timetablor/

# Answer
**EDIT** My initial interpretation was clearly incorrect although some of the content may be useful to someone so I'll leave it at the bottom of all this.

With that, it seems like each step further into the tree will lead you to a mutually exclusive path (e.g. timetables can't have $A\_1$ and $A\_2$). This split is what we can call a "decision point". Assuming all your leaf-node timetables are stored in a list, you could figure out where the decision point was, and then bounce over to the corresponding node with the alternate decision.

Example: Let's say, similar to your example we have courses $A$ and $B$, with sections $A\_1, A\_2, A\_3, B\_1, B\_2$. We then get a decision tree:

You can see the decision point of course $A$ is at the first level. Similarly you see the decision point of course $B$ is at the second level. The red line in there represents an example of two timetables that differ only by their grandparent, rather than just their parent. We can use some math and indexing to figure out how they're related.

As long as your *course* decision at each level is consistent, we can use some math and indexing to figure this out pretty easily.

Let's say you have $n$ courses: $c\_1, c\_2, \dots, c\_n$.

Now let's define the size of a course as the number of sections = $|c\_i|$.

It's pretty clear to see that, in the end, the number of leaf node timetables we'll have is $m = \prod\_{i=1}^n |c\_i|$. Let's assume courses are decided in increasing order (i.e. $c\_1$ is decided at level 1 in the decision tree, $c\_2$ is decided at level 2, etc.). If your leaf nodes are contained in a list, we can easily find related nodes based on the level of a particular course decision.

Let's say we look at leaf node timetable $j$. If we want to find all timetables that only differ at course $i$, we know they will be $\frac{m}{\prod\_{k = 1}^i |c\_k|}$ away.

An example might help, it's extremely clear if we're only dealing with a binary tree (each course has 2 sections). Let's say we have 3 courses: $A, B, C$. We then end up with a list of leaf nodes:

$$\left\[(A\_1, B\_1, C\_1), (A\_1, B\_1, C\_2), (A\_1, B\_2, C\_1), (A\_1, B\_2, C\_2), (A\_2, B\_1, C\_1), (A\_2, B\_1, C\_2), (A\_2, B\_2, C\_1), (A\_2, B\_2, C\_2)\right\]$$

We can represent these in binary:

$$\left\[000, 001, 010, 011, 100, 101, 110, 111\right\]$$

If we wanted to find where $111$ differs at course $B$. We find the distance between them is:

$$ \begin{align} d & = \frac{m}{\prod\_{k = 1}^i |c\_k|}\\ & = \frac{8}{\prod\_{k = 1}^2 |c\_k|}\\ & = \frac{8}{2 \cdot 2}\\ & = 2\\ \end{align} $$

Now deciding whether to subtract or add this distance is left up to simple edge case handling. But we see that 2 indices away from $111$ is $101$, which is the difference at course $B$ we were looking for. You should be able to take this approach to determine each differing timetable without having to compare everyone.

**Misinterpretted Response Below**

This algorithm seems similar to itemset lattice generation in association rule mining. Not the actual machine learning part, just the itemset generation. With this in mind, memoization in general would help downsize the repeated timetables. If you find that a child subproblem has already been solved, you can link the parent to that memoized solution, reducing the amount of links in your tree while keeping the children/parent connections consistent.

Memoization could also help with the "one section swap" connection. You already know all siblings will be "one section swap" connections. From there, it's simple to see that *all* leaf siblings will be connected. Using memoization these leaf-to-leaf sibling relationships will be much tighter and should basically figure themselves out.

Let's take an example with 5 sections $A, B, C, D, E$, assume a timetable is full when it gets 3 courses and just to add some variation let's say section $A$ conflicts with section $E$. If my understanding is correct your graph should look like the following, where green edges are "memoized" edges from parent to memoized child. Red crossed nodes are conflicting timetables.

Then, you may notice that we can construct a sibling graph of the leaf nodes:

Interestingly (but expected) the sibling graph connects all valid complete timetables **and** all connections are "one section swap" connections! So I definitely think memoization is the way to go.
> 2 votes

---
Tags: algorithms, graphs, trees, recursion
---


# Question
Title: When does the product automaton of two NFAs A and B not decide L(A) U L(B)?
We are given the following task:

> Let $\mathcal{A} = {}(Q\_A,\Sigma, \delta\_A, s\_A, F\_A)$ and $\mathcal{B} = {}(Q\_B,\Sigma, \delta\_B, s\_B, F\_B)$ be two NFAs and let their product automaton be defined as:
>
> $\mathcal{A} \times \mathcal{B} = {}(Q\_A \times Q\_B,\Sigma, \delta, (s\_A,s\_B), F)$ with
>
> $\delta = {}\\{ ((p,q),\sigma,(p',q')) \mid (p,\sigma,p') \in \delta\_A, (q,\sigma,q') \in \delta\_B \\}$ and
>
> $F= {}(Q\_A \times F\_B) \space \cup \space (F\_A \times Q\_B)$

(So the accepting (combined) states are the ones where at least one of the two individual states of $\mathcal{A}$ or $\mathcal{B}$ is accepting.)

> Give an example for two NFAs $\mathcal{A}$ and $\mathcal{B}$ so that their product automaton $\mathcal{A} \times \mathcal{B}$ does not decide the language $L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now the one thing that is by far confusing me the most (and what I want to focus on in this question) is the following tip that is given as well:

> Tip: There is an example in which $\mathcal{A}$ only has one state.

I can't see how that could be possible, with the following reasoning:

If $\mathcal{A}$ only has one state - let's call it $q$ \- this means two things:

1. $q$ is either accepting or it is not accepting
2. All of the transitions of $\mathcal{A}$ start at and directly lead back to $q$.

Based on 1. we have two cases.

Let's first consider the case that $q$ is accepting ($q \in F\_\mathcal{A}$). Because of 2. it follows that $\mathcal{A}$ accepts every word $w \in \Sigma ^\*$ (so $L(\mathcal{A}) = \\{w \in \Sigma^\*\\}$).

Let $\mathcal{B}$ be an arbitrary NFA. Based on the definition of $F$ and the fact that $q$ is accepting it is clear that all of the states of $\mathcal{A} \times \mathcal{B}$ will be accepting as well, which implies that the product automaton also accepts every $w \in \Sigma ^\*$.

This means that $\space L(\mathcal{A} \times \mathcal{B}) = \\{w \in \Sigma^\*\\} = L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now let $q$ be non-accepting ($q \notin F\_\mathcal{A})$. Again, based on the definition of $F$ we can see that the accepting states of $\mathcal{A} \times \mathcal{B}$ are going exactly correspond to the accepting states of $\mathcal{B}$.

Point 2 implies that the transitions of $\mathcal{A}$ will "not have any impact on the transitions of $\mathcal{A} \times \mathcal{B}$", by which I mean that the product automaton is going to have the same transitions as $\mathcal{B}$ and therefore be isomorphic to $\mathcal{B}$, which again results in

$L(\mathcal{A} \times \mathcal{B}) = L(\mathcal{B}) = L(\mathcal{B}) \space \cup \space \varnothing = L(\mathcal{B}) \space \cup \space L(\mathcal{A})$

(since $\mathcal{A}$ doesn't accept any input, which means $L(\mathcal{A}) = \varnothing$)

This proof is trying to show that if $\mathcal{A}$ only has one state, then $\mathcal{A} \times \mathcal{B}$ will always decide $L(\mathcal{B}) \space \cup \space L(\mathcal{A})$.

Obviously, there has to be a logic fault in my thinking and in the proof above somewhere, which I can't seem to be able to figure out, so I'd really appreciate if anyone could point out what I'm missing.

# Answer
The culprit is the fact that, in the presence of nondeterminism, automata need not have transitions to other states for the same input symbols.

Consider two NFA over the input alphabet $\\{a,b\\}$:

$$N\_1 = (\\{q\_1\\},\\{a,b\\},q\_1,\delta\_1,\\{q\_1\\})$$

where $\delta\_{1}(q\_1,a) = \\{ q\_1 \\}$ and $\delta\_{1}(q\_1,b) = \emptyset$

and

$$N\_1 = (\\{q\_2\\},\\{a,b\\},q\_2,\delta\_2,\\{q\_2\\})$$

where $\delta\_{2}(q\_2,a) = \emptyset$ and $\delta\_{2}(q\_2,b) = \\{ q\_2 \\}$

– that is, each of these automata has a single state, which is accepting, and a single transition, which is a loop on $a$ or $b$, respectively.

Clearly, $L(N\_1)= \\{ a^n \mid n \geq 0 \\}$ and $L(N\_2)= \\{ b^n \mid n \geq 0 \\}$. But the product construction will give us an automaton

$$N\_{12} = (\\{ (q\_1,q\_2 \\}, \\{ a,b \\}, (q\_1,q\_2), \delta\_{12}, \\{ (q\_1,q\_2)\\})$$

where $\delta\_{12}((q\_1,q\_2),a) = \emptyset$ and $\delta\_{12}((q\_1,q\_2),b) = \emptyset$, since there is no symbol $x$ such that both $N\_1$ and $N\_2$ admit an $x$-transition from their sole state.

Therefore $L(N\_{12}) = \\{ \varepsilon \\} \neq L(N\_1) \cup L(N\_2)$.
> 6 votes

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


# Question
Title: How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method
The guess solution to the

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

is $\Theta(n \log{\log n})$. This is my solution: $$ T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} + \frac{n}{\log n} \\ \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ \leq cn \log{\log {n}} + \frac{n}{\log n} $$

that fails to for the $T(n) \leq cn \log{\log {n}}$

Now I try to solve the $T(n) \leq c(\log \log n - \frac{n}{\log n})$, we have $$ T(n) \leq 2c\left(\left(\frac{n}{2}\right) \log \log {\frac{n}{2}} - \frac{\frac{n}{2}}{\log {\frac{n}{2}}}\right) + \frac{n}{\log n}\\ \leq cn \log \log {\frac{n}{2}} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ \leq cn \log \log {n} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ $$ and it will never be $\leq cn \log \log {n} - \dfrac{n}{\log n}$

How can I solve the recurrence?

# Answer
$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):

$$ \begin{align} T(n) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\ & = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\ & = n \left\[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right\]\\ & = n \sum\_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\ & = n \cdot H\_{\log n}\\ \end{align} $$

Where $H\_n$ is the $n$th Harmonic number. It's known that $H\_n = \Theta(\log n)$.

We can thus conclude $$T(n) = \Theta( n \log \log n )$$

Now with this being said; I believe this issue in your logic is the following steps: $$ \begin{align} T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \leq cn \log{\log {n}} + \frac{n}{\log n} \end{align} $$ The jump from step 1 to step 2, while not incorrect, is not tight. Which is why you're not meeting the necessary conclusion. It should be something like: $$ \begin{align} T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \leq cn \left\[\log \log \frac{n}{2} + \frac{1}{\log n}\right\] \end{align} $$ It can then be proven by induction that:

$$\log\_2 \log\_2 \frac{n}{2} + \frac{1}{\log\_2 n} \< \log\_2 \log\_2 n$$

For $n \> 2$. The proof is pretty straightforward and I'll leave it as an exercise for the reader, but it then follows that:

$$ T(n) \leq cn \log\log n $$
> 7 votes

---
Tags: recurrence-relation
---


title: Questions About P, NP, languages

text:
# Question
Title: Questions About P, NP, languages
I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too.

1. Given language L, which is non-recognizable, is L\* context free?
2. Is P countably infinite, and why?
3. Are all recognizable languages NP-complete?

# Answer
> 1 votes
1.) Every context free language is decidable. CFL are not unrecognizable. Refer

2.) P is countably infinite because P is the class of decision problem that can be solved on a deterministic turing machine in polynomial time. Every turing machine can be thought of as a finite string over some finite alphabets but all possible set of turing machines are countable infinite hence P is also countably infinite.

3.) NP complete languages are recognizable. A NP Complete languages can be found by modifying the halting problem which is just another form of halting problem(NP-Complete). Halting problems are undecidable but recognizable hence all NP-Complete problems are recognizable. Refer  fro details.

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


# Question
Title: Generating grammar for the given language
Can someone please give a couple of examples of the language and construct a grammar for the language (given below), or at least show me how I can go about it?

I am looking for a context-free grammar generating the language

$$ L = \\{ a^n b^m \mid n,m \geq 0 \text{ and } n \neq 2m \\}. $$

I asked a similar question on stackoverflow, where it was closed.

After seeing that question one thing is very clear to me:

1. Take care of the case when $n\<2m$ (as in the stackoverflow question).
2. Take care of the case when $n\>2m$ (not sure how to do that).

# Answer
Let $G = (\\{S\\}, \\{A, B\\}, P, S)$ the formal grammar which production rules $P$ are:
$S \to aaSb \mid A \mid B \mid aB$
$A \to aA \mid a$
$B \to Bb \mid b$

We have $L(G) = L$.

## Explanation:

* $n \< m$ : The $a$'s are generated in $S$. Whenever the count is right, the remaining $b$ are generated in $B$. If $n$ is odd, the production rule $S \to aB$ is used.
* $m \< n \< 2m$ : Same as above.
* $n = 2m$ : The only way to generate such a word is in $S$; if you branched to either $A$ or $B$, the hypothesis wouldn't hold anymore as you would prepend (*resp.* append) at least one $a$ (*resp.* $b$). As this symbol is nonterminal, this class of words isn't accepted.
* $n \> 2m$ : The $b$'s are generated in $S$, and the remaining $a$'s are generated in $A$.
> 2 votes

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


# Question
Title: approximation algorithm with polynomial complexity
It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't understand what it means, I searched a lot and here is my assumption.

First, for some NPc or NP hard problem, we can try to solve them approximately, because there is no optimization algorithm right now. So compared with some opotimal solution theoretically, some optimazation problem can use approximation algorithm to get an approximation solution, such like vertex covering problem.

Then it is the term polynomial complexity, an algorithm is polynomial if for some k\>0, its running time on inputs of size n is O(n^k).

So is "approximation algorithm with polynomial complexity" means an approximation algorithm that whose complexity is in polynomial time? So is it means there are approximation algorithm that has other complexity such as exponential complexity.

By the way, through the approximation algorithm for vertex covering problem, I know what the algorithm is (briefly it is takes an arbitrary edge from subset E' of all possible set of edges, add two vertax at set S and remove all edge who has the same vertex with that arbitrary edge and continue until E' is empty). But how to observe it is polynomial complexity or what?

I really apprexiate if someone can solve my confusion.

# Answer
> 1 votes
As you say, we believe there is no polynomial-time algorithm for solving an NP-hard problem. So if we wanted to have a polynomial-time algorithm, it seems like we need to give up the hope of always finding an optimal solution. So you are right: typically, we strive to find approximation algorithms that run in time polynomial in the input size. But sure, there is nothing that prevents you from considering approximation algorithms that run in exponential-time (or for example in FPT-time for some parameter).

Sometimes these approximation algorithms are very simple to state. This is perhaps often the case for greedy algorithms, like the one you mention for vertex cover. To see that it runs in time polynomial in the size of the input graph, you need to perform a runtime analysis in the usual way.

# Answer
> 1 votes
An "approximation algorithm with polynomial complexity" means just that: an approximation algorithm which complexity is polynomial. As you mentioned, an algorithm has polynomial complexity if $\exists k \mid T(n) = O(n^k)$. To ensure that your algorithm has polynomial complexity, you need to go back to the $O$-notation definition and do a proper analysis.

The algorithm you mention happens to compute an appoximative solution for a problem: this is a *characteristic*. However, The fact that it has polynomial complexity is a *property*. While most used approximation algorithms have polynomial complexity or less, nothing ensures that this is the case for every approximation algorithm.

---
Tags: approximation, polynomial-time
---


# Question
Title: Efficient algorithm for simple constraint satisfaction problem
There are

* $k$ **Boolean** variables $x\_1, x\_2, \dots, x\_k$.
* $m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., one of $m$ constraints may be $x\_1 + x\_3 + x\_5 + x\_6 = 1$.
* $n$ arbitrary subsets of these variables such that sum of each set is at least $1$ (i.e., at least one of the variables should be $1$). E.g., one of $n$ constraints may be $x\_1 + x\_6 + x\_8 \geq 1$.

The solutions are not necessary, but I want to know **how many solutions exist**.

What is an efficient way to calculate the number of solutions?

# Answer
There is unlikely to be any efficient algorithm.

Your first class of constraints are monotone exactly-1 CNF clauses. Your second class of constraints are monotone CNF clauses. The monotone part indicates that negated literals aren't allowed (you can't have $x\_1 - x\_3 = 1$ or $x\_1 - x\_4 \ge 1$).

Thus, in the special case where you have only type-2 constraints, the problem becomes #monotone-SAT. Unfortunately, this problem is known to be hard. #SAT is #P-complete, and monotone #SAT is #P-complete as well: it is #P-complete even for monotone 2CNF clauses (i.e., type-2 constraints with only two variables). It is also known that it is NP-hard to approximate the number of solutions. As a result, there is unlikely to be any efficient solution unless the number of variables and constraints is fairly small. Of course, your problem (with a mixture of type-1 and type-2 constraints) is potentially even harder.

So what can you do, to make the best of the situation?

One approach is to code this as an instance of #SAT, and try applying some off-the-shelf #SAT solver. You can encode type-1 constraints in SAT using the methods described at Encoding 1-out-of-n constraint for SAT solvers.

Or, you could express the constraints as a BDD and then apply model-counting methods for BDDs. I expect this to perform worse than a #SAT solver, but you could try it.

Another approach is to use an approximation algorithm. There are existing algorithms for approximate-#SAT, though they too will hit a limit if you have too many variables and/or clauses.
> 6 votes

---
Tags: algorithms, data-structures, satisfiability, integer-programming, constraint-satisfaction
---


# Question
Title: Crafting a dataset to train a NN that recognizes image styles
In this paper the authors show how to use two NN that respectively recognize an art style and an image content to apply style filters to photographs.

However, I am confused about how would one train a NN to consistently identify the style of a given author, given that the dataset cannot be too big (an author may paint around ~100 famous canvas in his life?) and normally you need a really big dataset to train for such a thing.

I am just being pessimistic about NN capacity to learn from small datasets or is there a technique for expanding a dataset which could be used in this context?

---

Reference: *A Neural Algorithm of Artistic Style*, by Leon A. Gatys, Alexander S. Ecker, Matthias Bethge

# Answer
> 3 votes
You have to know how to read these papers, and set your expectations low. The prior ability to do anything of this sort was so low that any advance, even a highly imperfect one, is exciting and unexpected.

It's like one of those animal trick shows, where the cute dog sits in front of the piano and plays Happy Birthday on it. You're not expecting Beethoven's Moonlight Sonata or mastery-level playing. It would be churlish to complain that the piece was overly simplistic, the playing lacked expression, and halfway through, the dog got distracted and started chasing his tail and never finished playing. Come on, it's a piano-playing puppy! How often do you see that?

Same deal here. It's probably not really fully capturing "style" as a human would consider it.

Don't think of this as transforming an image to make it look like it was painted by some specific painter or artist. It's not going to take my cellphone-snap of a tree in my backyard and make it look like an Ansel Adams composition. Don't think of this as learning the style and idiosyncracies of a particular painter. Don't even think of this as learning "style" as humans would consider it.

Rather, what they do is propose a technical transformation to an image, and then they look at its effect on some examples and -- woah -- the effect is pretty cool! In some cases it comes surprisingly close to mimicking some aspects of human style. It's not wonderful, but hey, it's more than one would otherwise expect.

At a technical level, they identify some particular attribute or property of an image that they can compute: if $I$ is an image, let $f(I)$ denote the value of this attribute. Then, given an image $I\_1$ and an image $I\_2$, they show how to modify $I\_2$ to get a new image $I'\_2$ such that $f(I'\_2)$ is similar to $f(I\_1)$. They look at some examples and empirically find that (a) $I'\_2$ often seems to have "similar visual content" to $I\_2$, and (b) $I'\_2$ often seems to have captured some of the aspects of "artistic style" of $I\_1$ (it seems to have a similar "style" as $I\_1$), in some vague sense.

Based on this, they decide to call $f(I)$ the "style" of $I$. That's probably playing a bit fast and loose with naming, as I suspect $f(I)$ falls far short of always capturing all of the elements of artistic style as a human would judge it.

At a technical level, $f(I)$ is computed by computing some kind of correlation matrix on the responses of internal layers of a particular neural network when applied to image $I$... or something like that. The details don't matter so much, as the fact that empirically their transformation provides results that are interesting and unexpected.

And that's why they don't require a large training set per artist: they don't try to capture anything specific to a single artist. They're not doing what you seemed to expect them to be doing. Also, the neural network was obtained by pre-training it on a dataset of millions of images, so it probably captures some kind of information about typical patterns that are seen in images.

---
Tags: neural-networks
---


# Question
Title: Complexity of recursive Fibonacci algorithm
Using the following recursive Fibonacci algorithm:

```
def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

```

If I input the number 5 to find fib(5), I know this will output 5 but how do I examine the complexity of this algorithm? How do I calculate the steps involved?

# Answer
Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get $T(n) = \Theta(\phi^n)$, where $\phi$ is the golden ratio ($\phi = \frac{(1 + \sqrt{5})}{2}$).

If you want to find out more about how to solve recurrences I strongly recommend you to read chapter 4 of Introduction to Algorithms.
> 23 votes

# Answer
as an alternative to recurrence relations/ math analysis (but not a *substitute*) a simple empirical exercise, apparently not taught very often in classes but very informative, is to count the # of executions of the function, and then graph the count for a range of small *n* inputs, and then curve fit the result. results will generally closely match the theoretical math approach.

good supporting material for this exercise can be found in the free online chapter 3, running time of algorithms/ Foundations of Computer Science, Ullman
> 0 votes

# Answer
The result of fib (n) is the sum of all recursive calls that returned 1. Therefore there are exactly fib (n) recursive calls evaluating fib (1). So the execution time is Ω(fib (n)); you'd need to show that the calls returning 0 and the other recursive calls don't add significantly to this.

The same reasoning would apply to any recursively defined function that either returns 1, or 0, or the result of another recursive call.
> 0 votes

# Answer
A lower bound is intuitive: $T(n)=T(n-1)+T(n-2)$ $T(n)\>2T(n-2)$ since $T(n-1)\>T(n-2)$ Hence $T(n)= \Omega(c^{n})$
> 0 votes

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


# Question
Title: How to figure out if a language is recognizable by a finite state machine FSM
I have a finite state machine FSM like below.

I want to know which of my languages are recognized by my FSM:

$$L\_1=L(0^\*1(10)^\*(00^\*1(10)^\*)^\*)$$ $$L\_2=L((0+1(10)^\*0)^\*1)$$ $$L\_3=L(0^\*1(10+00^\*1)^\*)$$ $$L\_4=L(0^\*(1(10)^\*0)^\*1(10)^\*)$$

---

I tried to figure out, but I got confused.

# Answer
* There are many - indefinitely many - regular expressions for the same language.
* There is one minimal FSM for the language.

So the sensible thing to do is to derive the minimal FSM for each of the regular expressions, and see if it equates to the one you have.

How do we do that? Let's try

$$L=0^\*1(10)^\*(00^\*1(10)^\*)^\*$$

Define $L / w$ for word $w$ as the set of words $z$ for which $wz$ is in $L$.

Then

$$\begin{align} L/0 &= L\\ L/1 &= (10)^\*(00^\*1(10)^\*)^\* \end{align}$$

and

$$\begin{align} L/10 &= (10)^\*(00^\*1(10)^\*)^\*/0\\ &= (00^\*1(10)^\*)^\* / 0 \\ & = 0^\*1(10)^\*(00^\*1(10)^\*)^\* \end{align}$$

So

$$\begin{align} L/100 &= L/10/0 \\ & =0^\*1(10)^\*(00^\*1(10)^\*)^\* / 0 \\ & = L/10 \end{align}$$

So far, it looks like this is an isomorph of the diagrammed FSM, where $L$ equates to $q\_0$. I'll leave you to deal with $L/11$ and its progeny.

You can find a description of the algebra in *Chapter 5: The Differential Calculus of Events* of John Conway's *Regular Algebra and Finite Machines*.
> 1 votes

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Minimum depth of addition and multiplication circuit using XOR and AND gates
What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we have an OR gate. Can I achieve that using XOR gates?

# Answer
You can simulate an OR gate using a constant number of AND and XOR gates:

$$x \lor y = ((x \oplus 1) \land (y \oplus 1)) \oplus 1.$$

Consequently, anything you can do in depth $d$ using AND and OR gates, can be done in depth $\le 3d$ using AND and XOR gates.
> 0 votes

---
Tags: arithmetic, circuits, multiplication, xor
---


# Question
Title: Verification of regular expression computed from finite automata
Here in the given image, our question is to find regular expression from finite automata. I found three answers based on which state I am resolving. Are these answers in the photo correct? If any answer is incorrect then please provide me the correct answer.

# Answer
There is an algorithm for computing a regular expression $R$ from a deterministic finite-state automaton $M$ such that $L(R) = L(M)$. It is covered in any standard course on formal language theory.

Have you used this conversion algorithm? It does not appear to be the case, but it is very difficult to figure out how you have proceeded in coming up with your attempted solution, since you insist on not writing very much.
> 1 votes

---
Tags: computability, finite-automata, regular-expressions
---


# Question
Title: Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula
I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption of what I should do, I would be appreciate if someone can guide me.

First a boolean formula is satisfiable if it can be made TRUE by assigning appropriate logical values, so "deciding the satisfiability" means to decide whether this boolean formula can be made a TRUE result.

Then for conjunctive normal form is means a conjunctive of clauses which are disjunctive inside. and 1-conjunctive normal form means each clause contains one variable, such like A\wedge B.

Now is the problem, what means an algorithm to decide it? I mean isn't the way to decide the satifiability of a boolean formula is try ture and false assiagnments to find whether it can be TRUE as a result? For example: since it is conjunctive normal form so each result of clauses needs to be TRUE, and it is 1-conjunctive normal form, so each variables need to be TRUE. Is this one an accpaptable algorithm to deal with the question?

# Answer
> 4 votes
Most satisfiability algorithms do actually find an assignment for the variables to satisfy the equation, but in your case (a conjunction of single variables) this is not necessary.

When the entire logic formula is just a single conjunction of variables, the only way it is **not** satisfiable is if it contains both $a$ and $\neg a$. If there is no variable which is contained both positive and negatively in the formula, the formula is satisfiable.

---
Tags: satisfiability, boolean-algebra
---


# Question
Title: Combine the following IP Addresses into a single block
I was asked to combine the ip addresses into a single block: 16.27.24.0/26, 16.27.24.64/26, 16.27.24.128/25

I managed to convert the given ip addresses into binary: 00010000.00011011.00011000.00000000 | 00011010 00010000.00011011.00011000.01000000 | 00011010 00010000.00011011.00011000.10000000 | 00011001

I am not quite sure what needs to be done in order to convert it properly. I believe that in this link it is explained what is supposed to be done. I should do it the way it is explained there. I am not able to access it, but whatever is shown in the preview, that is probably the way it would be gone about. Please help. Thanks

# Answer
> 3 votes
An ip address has two parts: the address and the netmask.

The address is just a 32-bit binary number. E.g. yours:

```
00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000

```

However, these addresses are very precise, and without any further information point to **exactly one address**. But we want to be more general, and be able to talk about a whole group of addresses. That is a block, and what the netmask is for.

When I use a netmask of `/n`, it means 'only look at the first *n* bits of this address, those are meaningful, the rest can be anything'. Think of it like this, the address we give is full, but then we strike out the most specific parts that can be anything:

> United States, Middleberge, Otter Lane 5322

In your case, the first 26 or 25 bits matter, so we strike through the last 6 or 7 bits:

```
00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000
```

But we still need to combine the blocks. Note that the top two lines have the exact same start, but then one ends in a 0 followed by anything, and the other in a 1 followed by anything. But since that exhaustively covers everything, we can just extend the 'anything' part one up to combine them:

```
00010000.00011011.00011000.00000000
00010000.00011011.00011000.10000000
```

Here we can do the exact same:

```
00010000.00011011.00011000.00000000
```

We can now convert our IP address back to decimal, giving `16.27.24.0`. The netmask is 32 - 8 = 24 (because we strike out 8 binary digits). So the full IP address + netmask is `16.27.24.0/24`.

---
Tags: computer-architecture, computer-networks, database-theory
---


title: Showing a problem is in coNP

text:
# Question
Title: Showing a problem is in coNP
We have the problem $C = \\{\<G,S\>| \text{ S is a minimal cover of G }\\}$ and we want to show that $C\in coNP$.

I can easily show that there's a ND TM that decides $coC$ using a guess to check if the drawn vertices are a minimal cover and if they are, return false. But it seems like it's wrong since this can be done with anything.

So is there another way to show that?

# Answer
Since coNP is confusing, let us construct an NP machine for $\overline{C}$. The input to the machine is a pair $\langle G,S \rangle$, where $S$ is a cover of $G$. The machine guesses another cover $T$, and verifies that $T$ is a cover of $G$ which is smaller than $S$. The cover $T$ is thus a witness to the fact that $S$ is not a cover of minimum size.

If $S$ is not a minimal cover, then there exists some smaller cover $T$, and so the machine accepts the instance $\langle G,S \rangle$ if it guesses $T$. Conversely, if $S$ is a minimal cover, then no smaller cover exists, and so the machine rejects the instance $\langle G,S \rangle$ whatever the guess is. In total, the machine accepts the language $\overline{C}$.

Here is a another way to look at things. We construct a machine that on input $\langle \langle G,S \rangle,T \rangle$, accepts if $S,T$ are covers of $G$, and $T$ is smaller than $S$. Then

> There exists $T$ such that the machine accepts $\langle \langle G,S \rangle,T \rangle$ if and only if $\langle G,S \rangle \in \overline{C}$.

This machine is polytime, and it accepts $\overline{C}$, showing that $\overline{C} \in \mathsf{NP}$, and so $C \in \mathsf{coNP}$.
> 1 votes

---
Tags: complexity-theory, np, complexity-classes, co-np
---


title: How does malloc(sizeof(char)) work

text:
# Question
Title: How does malloc(sizeof(char)) work
AFAIK, malloc(sizeof(char)) is intended to allocate a 1-byte block of VM and strcpy requires that

> the destination string dest must be large enough to receive the copy

That means theorically that if the length of src is strictly upper to 1, the strcpy operation fails, and it's impossible to copy more than one character to src.

However, the following code shows a counterexample, where 27 characters gets copied to s (including the '\0') as the program displays:

> s length = 26

```
int
main()
{
  const char *msg = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
  char *s = malloc(sizeof(char));

  strcpy(s, msg);

  printf("%s\n", s);
  printf("s length = %i\n", strlen(s));
  printf("msg length = %i\n", strlen(msg));
}

```

So, why malloc(sizeof(char)) allocates 27 characters contrarily to what it is intended to allocate theorically? How does this allocation work?

# Answer
> 3 votes
Quick note, `sizeof(char)` is **defined** to be 1. So you can just simplify to `malloc(1)`.

The real answer however is quite boring. Your program has what's so called *undefined behavior*. In C (and C++), if you make an error like this the result is *undefined*. This *could* mean that your program will crash right as you trigger the bug. But it doesn't necessarily crash. It might do what you expect. It might format your hard drive and kill your cat. Whatever happens is *fair game* according to the C standard. Because you triggered *undefined behavior*.

---
Tags: data-structures, strings, virtual-memory, memory-allocation
---


# Question
Title: Understanding a detail in the proof of bin packing approximation
***Input***: $n$ item with sizes $s\_1,...,s\_n$, without lose of generality, all sizes are $\leq1$.
In addition, $s\_i \< \delta$ for all $i$ for some constant $\delta$.
***Output***: Minimal numbers of bins to pack the items, where each bin has volume 1.

The scheme used is first-fit, where if the current used bins are indexed, we insert the $i\_{th}$ item to bin with the lowest index it fits into. Therefore, we open a new bin only when we can't fit an item into any bin.

Denote by $OPT$ the minimal number of required bins (for some input), and by $FF$ the number of bins output by first-fit scheme, the claim is that:

$$FF \leq OPT(1+2 \delta)+1$$ The proof is divided into cases, one when $\delta\geq {1 \over 2}$ , and the second where $\delta\< {1 \over 2}$.
My problem is in the later case.
In class we were shown that when the algorithm (that uses first-fit scheme) ends running, there are at least $FF-1$ bins, such that their empty space is $\<\delta$. (which I understand why)
Here a link to the final configuration of the algorithm to make things more clear.

Then the professor claimed that: $(FF-1)(1 - \delta) \leq OPT$.
Why is that?

# Answer
> 2 votes
We have $u = 1 - e$ where $u$ is used space and $e$ is empty space.

Since for at least $FF - 1$ bins we have $e \< \delta$ (which you understand why), for those we also have $1- e \> 1 - \delta$ or $u \> 1-\delta$.

So in at least $FF - 1$ bins we use at least $1 - \delta$ space. Since each bin has maximum size $1$ we can also say that at least $FF - 1$ bins are at least $1 - \delta$ fraction full. In other words, we have at least $(FF - 1)(1 - \delta)$ bins worth of 'stuff', so that must be less than or equal to the optimal amount of bins we need to use (or else we'd have more stuff than that could fit).

---
Tags: algorithm-analysis, approximation
---


title: Proving $\#CYCLE \in \#P$

text:
# Question
Title: Proving $\#CYCLE \in \#P$
I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\\#CYCLE \in \\#P$, if I could represent a distinct cycle, then I'll have a witness.

I saw this question: Number of cycles in a graph? they mention the reduction from HAM #CYCLE in Counting Complexity by Arora and Barak, but I don't understand how does that help.

You have some directed graph, no one said it has a hamilton cycle, and the gadget doesn't return how many cycles there in the graph or a way to distinguish between them, it just makes all the cycles longer.

So instead, is it possible to use a topological sort to count cycles? since it can detect every cycle, we can use it to distinguish between them.

# Answer
The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying $$ f(x) = |\\{ |y| \< p(|x|) : R(x,y) \\}|. $$ In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.
> 3 votes

---
Tags: complexity-theory, graphs, counting
---


# Question
Title: Link-cut trees: using access() and link()
I am having some trouble on understanding link-cut trees, so I need some help.

Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:

> 1. Link(A,B)
> 2. Link(B,C)
> 3. Link(C,D)

Following instructions of https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/MIT6\_851S12\_L19.pdf, I get

However, when we draw preferred paths, I should get

Am I doing something wrong when doing access(X)?

Thanks in advance.

# Answer
> 1 votes
I think you might be mixing up the **represented tree**, $R$, and the **auxiliary tree representation of the represented tree**, $T$.

Recall the definition of $LINK(v, w)$:

> $link(v, w)$ - Makes vertex $v$ a new child of vertex $w$.

This happens in the **represented tree**. Then to keep the auxiliary representation consistent we make $w$ the *left* child of $v$ because they are keyed by their depth in the represented tree (i.e. left children are higher, right children are lower in the represented tree). So your proposed linking should happen like so:

1. $link(A, B)$ - Make $A$ the child of $B$ in $R$. Make $B$ the left child of $A$ in $T$ (assumptions are omitted).

2. $link(B, C)$ - Make $B$ the child of $C$ in $R$. Rebalance the splay tree in $T$ and make $C$ left child of $B$.

3. $link(C, D)$ - Similar to step 2.

Then we have the preferred path in the *represented tree* is simply $D \rightarrow C \rightarrow B \rightarrow A$.

---
Tags: data-structures, trees, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: A comparison operation for lists, based on P(a > b)
Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from list $B$ such that $a\>b$.

More precisely, define $$ Q(A,B) = \sum\_{i,j} \text{sign}(a\_i-b\_j)$$ If $Q(A,B) = 0$, then we can say the lists "tie". If $Q(A,B)\>0$ then $A$ "beats" $B$, and likewise $Q(A,B)\<0$ can be said as $A$ "loses" to $B$.

The naive way of calculating this comparison of lists involves checking each pair of elements and thus takes $n^2$ time.

> Is there a faster way to calculate this?

Note, that somewhat non-intuitively, $A$ can still beat $B$ even if the average value of $A$ is less than $B$. (Also, even more non-intuitive, this comparison operator is non-transitive. Known as "intransitive dice", you can have dice such that A beats B, B beats C, C beats A.)

I believe if we take the $O(n \log n)$ hit to sort $A$ and $B$ first, then there should be a better way to calculate the comparison. But I'm having trouble filling in the pieces. Hopefully this is a useful hint instead of a red-herring.

# Answer
> 1 votes
Let $A \cup B$ denote the union of $A$ and $B$. Sort $A \cup B$ into increasing order, keeping track for each element which list it came from. Now for each element of this sorted list, annotate it with the number of elements of $A$ that are smaller than it and the number of elements of $B$ that are smaller than it. Those annotations can be filled in with a single linear scan (starting from the start of the list, and scanning left-to-right, and keeping track of the number of elements of $A$ and $B$ seen so far). Then you can compute the sum from those annotations: for each $i$, you can compute $\sum\_j \text{sign}(a\_i-b\_j)$ directly from the annotation.

This algorithm takes $O(n \log n)$ time: $O(n \log n)$ time to sort, plus $O(n)$ for the scan, plus $O(n)$ time to add up the sums.

---
Tags: algorithms, combinatorics, algorithm-design
---


# Question
Title: Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite?
I was reading "Why Only Us" by Chomsky and Berwick, and it said:

> If one subscribes to the Church-Turing thesis along with the assumption that the brain is finite, then there is no way out: we require some notion of recursion to adequately describe such phenomena.

I find this sentence confusing. What does the Church-Turing thesis have to do with recursion and the human brain? If anything, it seems obviously false to me because the Church-Turing thesis talks about computable things that require a Turing Machine, which in turn obviously requires an **infinite** tape. The brain obviously doesn't have this since the brain is finite, unless we somehow assume the brain can always "get a new piece of paper to write on". But even if that was resolved, what does recursion have to do with this, and how is any of this related to language?

# Answer
> 1 votes
This was a fun little rabbit-hole to jump into! My understanding is not that dissimilar from what you wrote in your comment:

**"Basically IF Church-Turning & Brain finite THEN recursion."**

But you forgot to add "and if there is arbitrarily deep layering of semantic meaning". So, really we would have:

**If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.**

Now let's see if I can unpack that a little for you.

The authors are arguing that the components of sentences are placed into semantic layers that can group words rather differently than strict word-ordering would suggest, and furthermore, that these layers are effectively unlimited. Consider this sentence:

*Mary and John went to the new movie (which was excellent) with Sam.*

Mary, John, and Sam are at one semantic layer, the new movie is at a second, and the fact that the movie was excellent is at yet a third layer.

*Mary and John went to the new movie, (which, as you expected, was excellent) with Sam.*

We've now added a fourth semantic layer. And, I hope it is obvious that we could keep going! The sentence would become convoluted and hard to follow, but we could keep adding semantic layers as many times as we wish.

There is a second idea here as well. It is interesting that Mary, John, and Sam are at the same semantic layer, even though they are far apart in the sentence. This is evidence that there really is some kind of semantic layering, and not merely word proximity at play. We read "Mary and John", delve down into a new layer, and eventually return back to this first layer in order to add "with Sam". I mention this because it is already suggestive of recursion!

I understand your objection about having a finite amount of brain, and it is a very good counter-argument to the idea that we can *follow* arbitrarily deep semantic layers, but it is not an objection to the idea that human language is structured to be able to *create* them, which is really what the authors are arguing.

If you accept that language is structured in such a way as to permit this arbitrarily deep layering, then you are doing something very similar to a Turing Machine, which can represent any computable function using a finite number of states.

The Church-Turing thesis involves the notion that all of these representations are, somehow, recursive. This makes sense if you consider that all three of the systems involved (Godel, Turing, and Church) can do this same trick of going arbitrarily deep using a finite number of rules at the start. There must be some mechanism that allows arbitrary depth, which means that we must be able to repeat rules or states, which means recursion.

We are very close to having finished here. **If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.**

We only are left with the finite brain. But of course, if the brain were infinite, then we would have no need for recursion. We could represent every semantic layer in a new region of the brain, and keep doing this forever.

---
Tags: formal-languages, computability, turing-machines, artificial-intelligence, recursion
---


title: Expected Time for LookUpSkipList

text:
# Question
Title: Expected Time for LookUpSkipList
A skip list

Let C(k) = the expected length of the path that raises k levels backwards.

Thus C(0) = 0

For any node P in the path, with k levels higher to go, there are two cases:

1. P is a node of level i and proceeds backwards to a node of at least level i and still k levels to go
2. P is a node at a level higher than i and must yet rise (k-1) levels

Each of these two cases has a probability of 0.5

Why C(k) = 2k and how to interpret this formula? Is the analysis formula in the figure right?

# Answer
The recurrence can be solved as: $$ \begin{align} C(k) &= \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}\\ 2 \cdot C(k) &= 1 + C(k) + 1 + C(k-1)\\ C(k) &= 1 + 1 + C(k-1)\\ C(k) &= 2 + C(k-1)\\ \end{align} $$ Then this can clearly be expanded to a summation: $$ \begin{align} C(k) &= 2 + C(k-1)\\ &= 2 + 2 + C(k - 2)\\ &= 2 + 2 + 2 + C(k - 3)\\ & \dots\\ &= 2 + 2 + \dots + C(1)\\ &= 2k\\ \end{align} $$

I haven't done much investigation into skip lists, but the math you've shown checks out. ✓

**EDIT**

The reason $C(k)$ appears in the left and right side of the equation, which seems *concerning*, is because of the Skip List structure. Take this procedure (source) to $find(86)$:

Now let's consider the *reverse* of this path. Notice we *always* move up if we can. So for any node in the *reverse* path, we can either (1) move up or (2) move left:

1. We move up. Now we have $C(k-1)$ more levels up to go: $$1 + C(k - 1)$$
2. We move left. We have made **no** progress upwards, therefore we still have $C(k)$ more levels up to go: $$1 + C(k)$$

For a randomized skip list, either of these scenarios occurs with probability $\frac{1}{2}$. This is how we get the final recurrence:

$$C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}$$
> 1 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, lists
---


# Question
Title: Can String be a subtype of Character in a programming language?
Could a programming language be designed so that there is an inheritance relationship between `string` and `character` (both of which are native types), such that the inheritance alone resolves the use of an arbitrary binary operator between the two types: `<string> @ <character>`; coercion and overloading cannot be used. My intuition is that `string` would be a subtype of `character` because a `string` may be composed of characters, and all basic methods defined for a `character` work with a `string`. As a subtype, `string` could have very specific functionaity such as a `length` method or attribute. On the other hand, I can see how it might make sense that `string` is the supertype and `character` is the subtype. Namely, a `character` could be thought of as a `string` of length 1. Which interpretation is correct, or at least which interpretation is more sound?

# Answer
> 6 votes
Character and String are conceptually very, very different. Google for "inheritance vs. composition" - you seem to think that Character and String should be connected via inheritance, but in reality a String is composed of 0, 1 or more Characters.

And to throw a spanner in the works: Strings are often large, and String operations must be very efficient. Therefore, even though conceptually a String is an array of Characters, it will not be implemented as a sequence of objects, but as an array of somehow simpler elements, for example UTF-16 codes.

And then you can think about how to implement Character efficiently if you use Unicode and an emoji character can easily be made up of a dozen Unicode code points - but the huge majority of Characters doesn't need that complexity, and you want an implementation that is space efficient and fast.

# Answer
> 4 votes
1. Subtyping is conceptually very different from inheritance.
Subtyping refers to shared interfaces; $\tau$ is a subtype of $\tau'$, i.e. $\tau \<: \tau'$, then all expressions of type $\tau$ could be used when one of type $\tau'$ is expected. Inheritance refers to the reuse of implementation; if class A inherits class B then A reuses the implementation of B. A doesn't have to be a subtype of B. For example, a "Stack" class might inherit from and reuse the implementation of a "List" class, but it "Stack" can't be a subtype of "List".
For more on subtyping and inheritance, see, e.g., Turbak, Gifford and Sheldon, *Design Concepts in Programming Languages*, pp. 701-25.
2. "Character" can't be a subtype of "String" if the implementation is to be useful
Sure you could design a language with "Character" as the subtype of "String". However, how useful would this design be? It is easy to find a function that you couldn't implement under this design, e.g. convert a character to a hex code based on its encoding; a "String" wouldn't be valid input to this function.
But you are be right the other way. A "Character" could be thought of as a "String" of length 1; but that would imply $\mathtt{Character} \<: \mathtt{String}$, not the other way. This is probably not the best programming language design decision you could make, but it'd work.

---
Tags: programming-languages, language-design, polymorphisms
---


# Question
Title: How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?
In the last section of chapter 3 (page 57) in *Probability and Computing: Randomized Algorithms and Probabilistic Analysis* by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. The algorithm discussed is a Monte Carlo algorithm. As such if we would like to run this variation of algorithm till we find a solution, how do we show that it still has a linear running time?

The Algorithm (source, starts on slide 66, page 53):

> Input: A set $S$ of $n$ elements over a *totally ordered universe*$^{\***}$.
>
> Output: The median of set $S$, denoted by $m$.
>
> 1. Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random *with* replacement.
> 2. Sort the set $R$.
> 3. Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th smallest element in sorted set $R$.
> 4. Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th smallest element in sorted set $R$.
> 5. By comparing every element in $S$ to $d$ and $u$, compute the set: $$C = \left\\{ x \in S : d \leq x \leq u \right\\}$$ and the numbers $$\ell\_d = |\\{x \in S : x \< d\\}|$$ and the numbers $$\ell\_u = |\\{x \in S : x \> u\\}|$$
> 6. If $\ell\_d \> \frac{n}{2}$ or $\ell\_u \> \frac{n}{2}$ then $FAIL$.
> 7. If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.
> 8. Output the $(\lfloor \frac{n}{2} \rfloor - \ell\_d + 1)$th element in the sorted order of $C$.

# Answer
> 1 votes
I'm assuming you're referring to this as your source.

Short answer: The algorithm *terminates* in linear time. This does **not** mean it identifies a median in linear time.

The text first proves, by Theorem 3.9 on page 54, that the algorithm *terminates* in linear time.

Then it proves, by Theorem 3.13 on page 57, that the probability of failure is bounded by $n^{-1/4}$.

Then the text mentions (page 57):

> By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a **random running time**. The samples taken in successive runs of the algorithm are independent, so the success of each run is independent of other runs, and hence the number of runs until success is achieved is a geometric random variable. As an exercise, you may wish to show that this variation of the algorithm (that runs until it finds a solution) still has **linear expected running time**.

The algorithm merely *terminates* in linear time, making it a Monte Carlo Algorithm. Although by successive runs and a bound on the probability of failure, we can guarantee a success at *some* point, making it a Las Vegas Algorithm. This successive trial algorithm is what you would attempt to show has an *expected linear running time*, by working on the geometric random variable represented by $k$ successive trials with bounded failure probability $n^{-1/4}$.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, randomized-algorithms
---


# Question
Title: Non-reducible Unsatisfiable 3SAT instance example
Can someone provide with the smallest (as small as possible) 3SAT example (w.r.t. number of variables and the number of equations) that is:

1. Unsatisfiable.
2. Not provable unsatisfiable by simply reduction (successive simplification and rewriting) of the equations by the process similar to as described below:

Example:

Assuming a 3SAT Problem that includes 4 equations:

1. ~a + b + c = 1
2. ~a + ~b + c = 1
3. b + d + ~e = 1
4. b + d + e = 1

(1. and 2.) combined can be replaced with ~a+c=1. (3. and 4.) combined can be replaced with b+d=1. and so on..

Thus, we require a problem instance where such a successive reduction/simplification of the equations (containing either 2 or 3 variables) in the given problem do not automatically lead to the conclusion of unsatisfiability.

# Answer
Resolution is a complete proof system for contradictions: if a given set of clauses is contradictory, then this fact is provable using resolution.

Since Resolution exactly corresponds to your "simple reduction", it follows that your question cannot be answered.
> 6 votes

---
Tags: complexity-theory
---


# Question
Title: Pumping lemma for regular languages proof
I'm trying to prove that if P(L,n) is true then L is regular, where P(L,n) is a property equivalent to the pumping lemma. This is in the context of single letter alphabet. Any suggestions how to do it?

# Answer
We will construct an $NFA$ that decides $L$. Suppose that the single letter is $1$.

Assuming $n$ is the length given by the pumping lemma, every input of size larger than $n$ can be 'pumped' , and remain in $L$.

Let's look at the input: $1^n$. Note that by pumping the input just once, it's size grows by $s$, for $s$ equal or less than $n$(that's by definition). So every input of length $n + k\*s$ , where $k$ is a natural number or $-1$, is in $L$.

We can do the above for every input of size between $n$ and $2n-1$ (why do we need to? and why up to 2n-1? hint for the first question: think for example on the case where $n = 3$, and $L$ is a language of all the words whose size is divisible by $2$ or $3$).

Then constructing the $NFA$ is quite simple: There is a finite number of words in $L$ of size $\<= n$, we will just accept the word if it is of the right size (we can get the sizes by picking $k = -1$ in the previous paragraph).

For words larger than L, we will 'guess' in which form the word is - there are $(2n-1) - n = n-1$ forms available that the language accept (we saw that earlier).
> 1 votes

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


title: Reliable path in graph

text:
# Question
Title: Reliable path in graph
Suppose Bob has a messaging network (which is a graph), where a message travels from a vertex `V` to its adjacent vertex `U`. However, the messaging network is very unreliable, and the probability that the message sent from vertex `V` will fail to reach an adjacent vertex `U` is `PROBABILITY(U, V)`.

How to find a path where there is a minimal probability that a message will get lost on the path? What's the approach to this problem?

# Answer
Given a path $u = x\_0, x\_1, \ldots, x\_n = v$, the probability that the message arrives is $p(x\_0,x\_1) \times p(x\_1,x\_2) \times \cdots \times p(x\_{n-1},x\_n)$, where $p(a,b)$ is the probability that the edge $(a,b)$ is "open". If you take a logarithm, then the product becomes a sum, and this reduces your problem to a more familiar one, shortest path.
> 0 votes

---
Tags: graphs
---


# Question
Title: Binary search trees: multiple `Successor()` calls
> Show that, given a tree node `a`, the time complexity of calling k times to `Successor()` is $O(k+h)$, where $h$ is the tree height.

I understand that we're passing by at least $k$ nodes, but how I can prove that in all these calls we do not iterate over the tree height (at most)?

# Answer
> 0 votes
Here are a few hints that could help you:

1. Consider a complete binary tree, and suppose that you run the successor operation, starting with the left-most leaf. The number of edges you go up and down at each step are 2, 4, 2, 6, 2, 4, 2, 8 and so on. You can use an explicit formula to show that the average number of steps in any prefix is always at most 4.
2. If you start this sequence in the middle, then there could be a "bump", and this corresponds to the appearance of $h$ in your formula. With some effort, you can show that the total sum of any consecutive subsequence of the above sequence is $O(h+k)$, where $k$ is the length of the subsequence, and $h$ is the maximal number appearing (which is double the height).
3. A general binary search tree need not be complete, but in some sense a complete binary tree is the "worst case", though you'd have to argue this formally somehow.

---
Tags: time-complexity, binary-search-trees
---


title: Big Oh where $g(n)$ is $n^2-n$

text:
# Question
Title: Big Oh where $g(n)$ is $n^2-n$
I have to solve the following $n^2+n \in O(n^2−n)$.

I did it this way: $n^2+n \in O(n^2−n) = n^2 \in O(n^2−n) = n^2 / n^2-n = 2n / 2n-n$ which is infinite.

I don't know if this is correct because the $-n$ in the $O$ notation is confusing me and I haven't found anything about it online. I know if this would be at example -1000 that $n^2+n \in O(n^2−n)$ would be correct.

Could someone explain it to me ?

# Answer
$f \in O(g)$ means there's $n\_0$ and $c\>0$ such that $n\>n\_0$ implies $f(n) \leq cg(n)$.

Note that for $n\>2$, we have $n^2 \geq 3n$.

Then, for $n\>2$, we have: $$ \begin{align} 2(n^2 - n) & = n^2 - 2n + n^2 \\ & \geq n^2 - 2n + 3n\\ & = n^2 + n\\ \end{align} $$

Summarizing: for $n\>2$, we have $n^2+n \leq 2(n^2-n)$. Thus $n^2+n \in O(n^2-n)$.
> 5 votes

---
Tags: asymptotics
---


# Question
Title: Higher-ranked polymorphism without explicit application or subtyping?
So, I'm familiar with two main strategies of having higher-ranked polymorphism in a language:

* System-F style polymorphism, where functions are explicitly typed, and instantiation happens explicitly though type application. These systems can be impredicative.
* Subtyping-based polymorphism, where a polymorphic type is a subtype of all of its instantiations. To have decidable subtyping, polymorphism must be predicative. This paper provides an example of such a system.

However, some languages, like Haskell, have impredicative higher-ranked polymorphism without explicit type applications.

How is this possible? How can type-checking "know" when to instantiate a type without an explicit instantiation or cast, and without a notion of subtyping?

Or, is typechecking even decidable in such a system? Is this a case where language like Haskell implement something undecidable that happens to work for most peoples' use cases.

**EDIT:**

To be clear, I'm interested in the *uses*, not definitions, of polymorphically-typed values.

For example, suppose we have:

```
f : forall a . a -> a
g : (forall a . a -> a) -> Int
val = (g f, f True, f 'a')

```

How can we know that we need to instantiate `f` when it's applied, but not when it's given as an argument?

Or, to separate ourselves from function types:

```
f : forall a . a
g : (forall a . a) -> Int
val = (g f, f && True, f + 0)

```

Here, we can't even distinguish the use of `f` as applying it versus passing it: it's instantiated when passed as an argument to `&&` and `+`, but not `g`.

How can a theoretical system distinguish these two cases without a magical "you can convert any polymorphic type to its instance" rule? Or with a rule like that, can we know when to apply it, to keep decidability?

# Answer
> 7 votes
The Dunfield & Krishnaswami paper's introduction refers to Practical type inference for arbitrary-rank types

> As can be seen, it scales well to advanced type systems; moreover, it is easy to implement, and yields relatively high-quality error messages (Peyton Jones et al. 2007)

In System F-ish approach there is also a "subtyping" relation. See section 3.3 Subsumption.

---

I'd also *emphasize* that Haskell doesn't have impredicative types (or inference for them). See: https://mail.haskell.org/pipermail/ghc-devs/2016-September/012940.html for pointers.

> * You can write a polytype in a visible type argument; eg. f @(forall a. a-\>a)
> * You can write a polytype as an argument of a type in a signature e.g. f :: \[forall a. a-\>a\] -\> Int
>
> And that’s all. A unification variable STILL CANNOT be unified with a polytype. The only way you can call a polymorphic function at a polytype is to use Visible Type Application.
>
> In short, if you call a function at a polytype, you must use VTA. Simple, easy, predictable; and doubtless annoying. But possible.

I.e. `id id` will always be elaborated as

```
forall a. id @(a -> a) (id @a)

```

*not*

```
id @(forall a. a -> a) id

```

Yet, you can write the latter explictly, if you enable `ImpredicativeTypes`.

# Answer
> 3 votes
To check the application of a function like `g : (forall a. a -> a) -> Int` to `f`, we need to check that `f : forall a. a -> a`.

Instead of matching quantifiers (which would be quite brittle), we introduce a fresh, rigid (i.e., non-unifiable) variable, say `a1`, and we need to check that `f : a1 -> a1`, and now we can carry on as usual, instantiating `f` at `a1` (modulo additional checks to ensure that `a1` does not escape its scope).

The actual algorithm is detailed in the paper phadej linked.

> Or, is typechecking even decidable in such a system? Is this a case where language like Haskell implement something undecidable that happens to work for most peoples' use cases.

The general problem of *type inference* in the presence of higher-ranked polymorphism remains undecidable. However, with full type annotations it becomes a (mostly?) decidable *type checking* problem. GHC's algorithm must thus be incomplete, but tries to cover as much ground as it can in the middle of these two situations, with the help of a few sparse type annotations.

---
Tags: programming-languages, type-theory, functional-programming, type-checking, polymorphisms
---


# Question
Title: Context-free Languages closed under Reversal
In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted to see the proof so I've been searching for the past few days but all I've found is most people just say that to reverse the productions is enough to prove it. Those that do go a little more formal just state there is an easy inductive proof you can give. Can anyone provide me with some more information/hints about the inductive proof? Try as I might I can't come up with it.

# Answer
> 17 votes
Your sources are right, and I am afraid there is only little to add, except formalism. Indeed it is enough to reverse all productions to reverse the language. I denote the reverse (mirror) of string $w$ by $w^R$.

If $G$ is a grammar, let $H$ be its reverse, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.

Then by induction we show that original grammar $G$ generates a string iff the reverse grammar $H$ generates the reverse of the string. Formally $A\Rightarrow\_G^\*w$ iff $A\Rightarrow\_H^\*w^R$.

* (*basis*) In zero steps we have $A\Rightarrow\_G^0 A$ iff $A\Rightarrow\_H^0 A$.
* (*induction*) Assuming $A\Rightarrow\_G^\*w\_1Bw\_2$ iff $A\Rightarrow\_H^\*w\_2^RBw\_1^R$ we can apply any production $B\to u$ in $G$ (and in $H$ in reverse) and obtain $A\Rightarrow\_G^\*w\_1uw\_2$ and $A\Rightarrow\_H^\*w\_2^Ru^Rw\_1^R$ respectively, where indeed $w\_2^Ru^Rw\_1^R$ is the reverse of $w\_1uw\_2$.

This is a very condensed proof, but contains all necessary ingredients. Again, a derivation of the reverse grammar is the reverse of the original one. This is especially clear when looking at the two derivation trees: they are just reversed (or mirrored).

# Answer
> 16 votes
There is another way to look at this problem.

Consider that the Language $L$ is a CFL. This means that there is a grammar $G=\\{N,\sum,P,S\\}$ that satisfies the CFL. We can assume that this is in Chomsky Normal Form.

If $\epsilon$ is part of the language, trivially $\epsilon^R$ is also part of the language. Now for every production of the form $P\_1 \longrightarrow AB$, replace it with, $P\_1 \longrightarrow BA$ and for the productions of the form $P\_1 \longrightarrow a$, where $a \in \sum$, leave it the same.

From the parse tree of the derived string, it is easy to see that the language derived will be exactly the reverse of the initial language as the construction mirrors the original parse tree.

# Answer
> 4 votes
First off. CFL's are not closed under intersection or complement (or difference for that matter). They are closed under Union, Concatenation, Kleene star closure, substitution, homomorphism, inverse homomorphism, and reversal. NOTE: The two homomorphism's are usually not covered in an intro Computer Theory course.

To prove reversal, Let L be a CFL, with grammar G=(V,T,P,S). Let LR be the reverse of L, such that the Grammar is GR = (V,T,PR,S). That is, reverse every production.

Ex. P -\> AB would become P -\> BA

Since GR is a CFG, therefore L(GR) is a CFL.

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


# Question
Title: Prove that a and b commute if and only if they are powers of the same word
Two words $a$ and $b$ commute if $ab=ba$.

How to demonstrate that $a$ and $b$ commute if and only if they are powers of the same word ?

$ab=ba \Leftrightarrow \exists \space \tau \in \Sigma^{\*} \mid a=\tau^{k} and \space b=\tau^{k'}$

The demonstration in this direction is trivial:

$\space \exists \space \tau \in \Sigma^{\*} \mid a=\tau^{k} and \space b=\tau^{k'} \Rightarrow ab=ba$

But I don't manage to find an elegant solution for the other direction.

# Answer
By induction.

> If $|a|=|b|$ then $a=b$ and we are done. Otherwise, assume $|a|\<|b|$. Then $a$ is a prefix of $b$, so there is a word $c$ such that $b = ac$. Now $ab = ba$ implies $aac=aca$, or, after deleting prefix $a$, $ac=ca$. By the inductive property $a$ and $c$ are both powers of the same word $\tau$, and so is $b$.
> 4 votes

# Answer
If $ab=ba$ then the word $w = ab$ satisfies $R^{|a|}(w) = w$, where $R$ is the right-rotation operator, and $R^{|a|}$ just applies this operator $a$ times. Since $R^{|w|}(w) = w$, Bezout's identity implies that $R^{(|a|,|w|)}(w) = w$, where $g = (|a|,|w|)$ is the greatest common divisor of $|a|$ and $|w|$. Since $g \mid |w|$, we see that $w = z^{|w|/g}$ for some word $z$ of length $g$. Since $g \mid |a|$, we see that $a = z^{|a|/g}$ and $b = z^{|b|/g}$.
> 3 votes

---
Tags: formal-languages
---


# Question
Title: Fewest induced subgraphs of order <= k which cover every edge
I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-complete).

I have a graph $G$ with $|V|$ vertices. Every vertex has at least one edge connected to it. I want to find the induced subgraphs of $G$ *of order $\leq k$*, where every edge in $G$ is found in at least one subgraph and the number of subgraphs is minimized. I can assume as a pre-condition that a solution exists (there exist no cliques with order $\>k$).

For example, here is a graph $G$ with 5 vertices. If $k=4$, there's no solution with 1 subgraph since there are more than 4 vertices in $G$. A solution for $k=4$ with 2 subgraphs is shown beside it:

The order of each subgraph can be less than $k$, so $\\{\\{1, 2, 3\\},\\{1, 2, 4, 5\\}\\}$ is another valid solution.

This is not a solution because the black edge between $2$ and $3$ is not covered by either subgraph:

All I'm looking for is a name for the problem, if it exists, so that I can research it and hopefully find an approximation algorithm. Having subgraph order $\leq k$ is a hard requirement but the "minimum number of subgraphs" part can be approximated as long as it's close to minium.

# Answer
> 1 votes
Your problem is known as $k$-clique cover. Goldschmidt, Hochbaum, Hurkens and Yu describe several approximation algorithms in their paper Approximation algorithms for the $k$-clique covering problem. The paper is from 1995, so there are likely newer works on this topic, which you can find by scanning the papers citing this paper.

---
Tags: graphs, sets
---


# Question
Title: Is per-record timeline consistency is somehow equivalent to causal consistency?
What I understand about per-record timeline consistency is:

> For a specific primary key all the insert/update/delete operations should be read in the same order by all replicas.

Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), then per-record timeline consistency is somehow equivalent to causal consistency. If they are essentially equivalent, then why put another name on it? Am I missing something?

# Answer
> 2 votes
You may know that per-record timeline consistency is used in PNUTS: Yahoo!’s Hosted Data Serving Platform:

> We provide per-record timeline consistency: all replicas of a given record apply all updates to the record in the same order.

**Answer your questions:**

> Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), ...

They are actually totally (or sequentially) ordered, stronger than "causally related".

> ... then per-record timeline consistency is somehow equivalent to causal consistency.

Given the reason above, per-record timeline consistency is more like sequential consistency (wiki). In fact, per-record time consistency is also called per-key sequential consistency, which is stronger than per-key causal consistency. Because sequential consistency is not local, per-key sequential consistency is not equivalent to (i.e., weaker than) sequential consistency defined over multiple keys.

---
Tags: distributed-systems
---


# Question
Title: Is it a problem that "successful" machine learning algorithms have large VC dimension?
In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension. For example, XGBoost is famous for being used to win the Higgs Boson Kaggle competition, and Deep Learning has made many headlines. Both algorithm paradigms are based on models that can be scaled to shatter any dataset, and can incorporate boosting which increases VC dimension.

According to VC dimension analysis, a large dimension is supposedly a bad thing, it allows models to overfit or memorize the data instead of generalize. For example, if my model shatters every dataset, e.g. a rectangle around every point, then it cannot be extrapolated outside the dataset. My grid of rectangles tells me nothing about points outside the grid. The larger the VC dimension, the more likely the model will shatter a dataset instead of generalizing, and thus once exposed to new data outside the training dataset, it will perform badly.

Back to the original point, many of the most "successful" machine learning algorithms have this common trend of having a large VC dimension. Yet, according to machine learning theory this is a bad thing.

So, I am left confused with this significant discrepancy between theory and practice. I know the saying "In theory there is no difference between theory and practice, in practice there is" and practitioners tend to brush aside such discrepancies if they get the results they want. A similar question was asked regarding Deep Learning, and the consensus was that it did have large VC dimension, but that doesn't matter because it scores very well on benchmark datasets.

But, it is also said "there is nothing more practical than good theory." Which suggests such a large discrepancy has a significance for practical application.

My question then, is it true that the only thing that really matters is low error scores on test datasets, even when the theoretical analysis of the algorithm says it will generalize poorly? Is overfitting and memorizing instead of generalizing not that big of a deal in practice if we have hundreds of billions of samples? Is there a known reason why the theory does not matter in practice? What is the point of the theory, then?

Or, are there important cases where a very large VC dimension can come back to bite me, even if my model has great scores? In what real world scenario is low error and large VCD a bad thing, even with hundreds of billions of samples in the training data?

# Answer
To expand my point in your previous post, VC theory (and PAC learning) is a WORST CASE theory. The requirement to handle any possible distribution on the data is too restrictive for real life applications. If $\mathcal{C}\subseteq 2^\mathcal{X}$ is a concept class with high VC dimension, there might still be an algorithm that achieves small generalization error relative to, say, the uniform distribution on $\mathcal{X}$. The question now is, whether the uniform distribution is something we can expect when treating examples from $\mathcal{X}$ (if for example I'm trying to separate pictures of dogs from pictures of cats, I wouldn't expect the uniform distribution on images to be meaningful here).

"Is it true that the only thing that really matters is low error scores on test datasets, even when the theoretical analysis of the algorithm says it will generalize poorly?"

Definitely not. It is useful to have an algorithm that seems to work, but you would be even happier if you could provide formal guarantees (error lower bound). We need some non worst case theory that finds the right conditions under which the algorithms you mentioned are indeed successful (in some formal sense), and argues why those conditions are satisfied in the cases where we witness empirical success. This will give us better understanding in general, and perhaps carve the way towards even better learning algorithms.
> 3 votes

# Answer
When left with a discrepancy between theory and data, data is king. Theory is intended to be predictive -- to make predictions about the world -- but when it fails to predict what we actually observe and experience, when its predictions disagree with our experience, then there is obviously something lacking in the theory.

In this case, VC theory just isn't adequate to understand modern practice in machine learning.

Unfortunately, VC theory ignores methods like regularization. Regularization is widely used in practice, so that's a pretty important gap in VC theory. VC theory counts the number (size, dimension) of possible models, and treats all of them as "equally valid/likely".

When we train a model with regularization, we depart from that paradigm. Regularization implicitly encodes the assumption that "all else being equal, simpler models (explanations) are more likely to be correct". In other words, regularization is essentially an application of Occam's Razor. In effect, regularization encodes some kind of prior on the distribution of likely models: not all models are equally likely; simpler models are more likely to be right. Classical VC theory doesn't take that into account, and thus can't make useful predictions about the behavior of machine learning methods that use regularization.

Practitioners aren't "brushing aside" the theory. Rather, VC dimension simply doesn't seem to be super-relevant to practice. It is too limited.

It's still an open question to understand why techniques like deep learning work so well. VC dimension was an early attempt to understand machine learning -- a powerful, beautiful, valiant attempt, one that may still be of some interest -- but ultimately one that doesn't seem to give us the whole picture, perhaps partly because it does not account for things like regularization and our priors on the model.
> 5 votes

---
Tags: machine-learning, vc-dimension
---


# Question
Title: Algorithm for finding the minimum index in array with value exceeding x
Given a set $S = \\{s\_1, \ldots, s\_k\\}$, find the minimum index $j$ such that $\sum\_{i = 1}^j s\_i \geq \frac{1}{2}\sum\_{i = 1}^k s\_i$.

I was reading in a paper about an algorithm for this problem that is described as follows:

> The idea is to construct an array of size $k$, whose $j$th position contains $\sum\_{i = 1}^j s\_i$. Then one can find the appropriate index $j$ in $O(\log(\min\\{j, k - j\\}))$ time by using a form of binary search simultaneously from both ends of the array.

Can someone explain how the binary search might work? I know that constructing the array still takes $O(k)$, but I want to use this in an algorithm where the array would be computed just once and used with recursive calls to this algorithm.

# Answer
Assuming the $s\_i$ positive (which wasn't said in the OP), the prefix sum of $s\_i$ forms a monotonic sequence.

You can start a simultaneous exponential search from both ends, followed by a standard binary search when the half sum has been crossed. The left exponential search takes $O(\log(j))$ and the right one $O(\log(k-j))$. As they are performed simultaneously, the fastest "wins".
> 1 votes

---
Tags: arrays, binary-search
---


# Question
Title: Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?
I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive.

For example, some problems require loops practically - making `10^100^1000^10000` repeated calculations (even no-ops) is not possible practically as the space necessary to store the code would likely be greater than the number of atoms in the universe, but would be possible theoretically given infinite memory (similar to how current implementations of programming languages only approximate Turing-completeness).

Alternatively: is there a problem which requires Turing-completeness to solve *theoretically*?

# Answer
> 2 votes
The answer is no (although from a rather syntactic reason, which might not be what you were looking for).

Let $f : \Sigma^\* \rightarrow \Sigma^\*$ be some arbitrary function, then it is implementable in the following "stupid" language which is not Turing complete:

Any string $s\in \Sigma^\*$ is a valid program, and all strings represent the program which, given $x$ as input, outputs $f(x)$. Note that I don't really care how it computes $f$ (as I'm defining a new model of computation). If this bothers you, imagine any string is translated to the same fixed Java program which computes $f$ (assuming $f$ is computable).

---
Tags: computability, computation-models, turing-completeness
---


# Question
Title: Is a language of TMs undecidable using Rice's theorem
Given a language: $A = \\{ \<M\> | M\ rejects\ the\ string\ "101" \\}$

Can I prove it is undecidable using Rice's theorem?

See like the theorem conditions are met (there exists non trivial language that describes the machine language )

# Answer
> 2 votes
Rice's theorem says that any nontrivial *semantic* property of TMs is undecidable. The property in question is clearly nontrivial, but let's see if it's semantic.

A semantic property of TMs is a set of TMs $P$ such that for every two TMs $M\_1,M\_2$, if $L(M\_1)=L(M\_2)$ then either $M\_1,M\_2\in P$ or $M\_1,M\_2\notin P$. That is, membership in $P$ is determined only by the language, and not by the "inner workings" of the machine.

In this case, since "rejecting" and "never halting" are the same thing from the point of view of the language, then the property is **not** semantic. That is, there can be two machines with the same language, where one rejects 101, and the other doesn't halt on 101.

So no, you can't use Rice's theorem here.

---
Tags: computability, turing-machines
---