# Question
Title: Can we use reductions to design approximation algorithms for NP-hard problems?
Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is the size of the input of problem $Q$) to $P(n)$ and showed that $P(n)$ is NP-hard. The time complexity of the reduction is $O(n^k)$ for some fixed $k$.

Can I use a known approximation algorithm for problem $Q(m)$ that is $O(f(m))$-approximation for problem $Q(m)$ to design an approximation algorithm for problem $P(n)$ that is $O(g(n))$-approximation for problem $P(n)$?

# Answer
> 4 votes
Yes, but you need an approximation-preserving reduction in the opposite direction.

---
Tags: reductions, np-hard, approximation, polynomial-time
---


# Question
Title: Language of words that begin and end with same symbol and have equal numbers of a's and b's
I wish to find the CFG for a language on two symbols (say *a* and *b*) whose words begin and terminate with the same symbol, and have equal quantities of *a*'s and *b*'s. What is the thought process I should use for finding such a grammar? What is the most natural or simplest grammar for this language? I hope you'll explain your answer. Hopefully this will suggest some patterns I should look for when trying to synthesise a grammar for a specified language.

---

Here's the best solution I could come up with on my own:

$ S \to aTbbTa \mid bTaaTb$

$ T \to abT \mid baT \mid aTb \mid bTa \mid \epsilon$

I *think* this grammar is correct. Informal argument: I can see that if the word is $awa$ ($w$ being a substring), then there are at least two $b$'s in $w$ that are adjacent. This suggests the form $aTbbTa$ in the first production rule. (The argument holds if the roles of the two symbols are reversed). The second set of production rules is meant to generate every possible word of the language while keeping the number of $a'$s and $b'$s equal. Symmetry suggests that the rule $abT$ should be accompanied by the rule $baT$, and $aTb$ by $bTa$. Initially was wondering if any of the rules in the second set was redundant, but I don't think so - I can think of words that couldn't be formed if any of the second set of production rules was missing. Rather I need to be sure there aren't any words from the language that my grammar can't generate.

\[I guess I would need induction to prove my grammar generates every possible word in the language. But right now I'm more interested in the thought process behind coming up with a grammar, and as far as I know, induction (in general) doesn't help much in synthesising a solution/rule/formula/etc.; it principally serves to verify a purported solution.\]

# Answer
> 3 votes
Here is the thought process I would use. I would notice that your language $L$ can be written as $L= L\_1 \cap L\_2$, where $L\_1$ is the set of words that begin and end with the same symbol, and $L\_2$ is the set of words that have equal quantities of *a*'s and *b*'s.

Then, I would note that $L\_1$ is regular and so can be expressed by a simple DFA (with 5 states). Also, I would note that $L\_2$ is context-free and can be expressed by a simple CFG: e.g., $S \to \varepsilon \mid aSb \mid bSa \mid SS$.

Finally, I would recall the standard closure property: the intersection of a regular language and a context-free language is context-free. It follows that $L\_2$. The proof of this standard closure property includes a construction that shows how to construct a CFG for $L\_2$, given a DFA for $L\_1$ and a CFG for $L\_2$. This gives a CFG for your language. The resulting CFG will have $5^2=25$ non-terminals; some of them are unreachable and can be pruned, but the result is still quite messy.

The resulting CFG isn't the simplest or smallest CFG for your language. Whether it is the most natural is open for debate. But since you asked for the thought process behind coming up with a grammar, this illustrates one general technique for constructing CFG's: separate out the part that requires something more than finite state (equal quantities of *a*'s and *b*'s) from the part that can be handled with a finite-state automaton.

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


# Question
Title: Techniques to create a PDA for a language that is the conjunction of two languages
When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are closed under intersection. Now, I am having many difficulties in drawing PDAs especially the ones that are apparently the intersection of two other PDAs. For example, suppose I am asked to build the PDA for $$\\{w \mid w \text{ is a palindrome and w has at most two 0s } \\}$$

I think I would be able to build a PDA that recognises palindromes (which is one of the easiest ones), and also one that recognises a language that has at most two $0$s. But I am having many difficulties in building a PDA for the language above.

Apparently CFG are not closed under intersection, so I suppose there's no mechanical way of coming out with a solution for an intersection of two languages. Since this might be the case, do you have any suggestions on how could I start thinking on how to draw a PDA that is apparently the intersection of two other languages?

Note that I am asking for techniques to come up with PDAs for languages that are the conjunction of other simpler languages and not for a solution for the particular case above.

# Answer
The intersection of a CFL and a regular language is itself a CFL. There is a standard construction for computing this intersection. It's documented in automata theory textbooks; look in your favorite automata theory textbook, and you should find it there.
> 2 votes

# Answer
The idea of the construction is quite simple: Run a DFA and a PDA in parallel, accepting if both do. Much like the construction for intersection between DFA-accepted languages.

Take a DFA and a PDA accepting by final state. You build a PDA whose states are pairs, a state of the DFA and a state of the PDA. Your combined transition function follows the DFA in the first component, and uses the other component of the state and the stack to follow the PDA's computation. You accept when both automata do, i.e., final states are pairs of a final state of the DFA and a final state of the PDA.
> 2 votes

---
Tags: context-free, automata, pushdown-automata
---


# Question
Title: How do you return the k smallest elements of an array using Mergesort?
I'd like to create a modified mergesort algorithm to return the *k* smallest elements of an array. The mergesort algorithm below sorts an unordered array of size *n*. How do I modify the algorithm so that it returns the *k* smallest elements of the array?

```
A = [1...n]

Mergesort (A,p,r)  //start with p = 1 and r = A.length
  if p < r
    q = floor((p + r)/2)
    Mergesort (A,p,q)
    Mergesort (A,q + 1,r)
    Merge-Sort (A,p,q,r)

Merge-Sort (A,p,q,r)
  n1 = q - p + 1
  n2 = r - q
  Let L[1,2,..,n1+1] and R[1,2,..,n2+1] be new arrays
  for i = 1 to n1
    L[i] = A[p + i - 1]
  for j = 1 to n2
    R[j] = A[q + j]
  L[n1 + 1] = (an infinitely big number)
  R[n2 + 1] = (an infinitely big number)
  i = 1
  j = 1
  for m = p to r
    if L[i] <= R[j]
      A[m] = L[i]
      i = i + 1
    else
      A[m] = R[j]
      j = j + 1

```

# Answer
> 2 votes
One way to do this would be a select, partition then sort technique. First you use the Median of medians algorithm to find the $k$th smallest element, this takes $O(n)$ time.

After that has been found you partition your list, partition using this $k$th element as a pivot. This takes $O(n)$ time.

Now if you want the result sorted you can use mergesort on these $k$ elements, taking $O(k\log k)$ time, at worst case if $n=k$ then this whole process runs in $O(n\log n)$ time, the expected case is less but depends on $k$.

# Answer
> 0 votes
What if in Merge Step you only merge first K elements ? That way you should have O(k\*logN) time complexity !

---
Tags: algorithms, search-algorithms, sorting
---


# Question
Title: Anotation rules for while rule in deductive verification
I have been studying deductive verification of software lately, with weakest precondition, strongest postcondition, annotation calculus, and etc.

I came across the following rules for the while sentence:

But, my problem is when should I use which rule? I mean the second and third one that includes $t$, which is the variant here, is usually related to the loop condition, but when again when should I use the second while and when the third one? I couldn't find any clarification anywhere about when to choose which one. (Note that $t$ is not a variable of the program, but a variant used to prove termination.)

# Answer
As you have already said, the second and third rule include a variant `t` to prove termination whereas the first rule does not consider it.

The second rule guarantees that the variant is always non-negative. This is necessary to have a lower bound for the variant which decreases every iteration.

The third rule relaxes that condition a little bit. The variant is always non-negative except in the last iteration (where `e` is false at the end of the block). This still guarantees termination (who cares about the variant if we know it's the last iteration?).

I think whether you choose the second or third rule is a matter of taste. Until now I knew only the second one. It should be easy to alter code or a variant whose correctness can be shown by the third rule such that it is also provable with the second one.

Choosing the first rule is of course only an option if you're not interested in termination.
> 3 votes

---
Tags: formal-methods, software-verification
---


# Question
Title: Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?
I stumbled across this question and answer (source):

> Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.
>
> Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.

Does this mean that the Ford-Fulkerson algorithm will reach max flow if given **any** valid flow as input, instead of initializing all edges to 0 at the start?

# Answer
> 6 votes
Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a different initial flow does not change this.

---
Tags: algorithms, network-flow, ford-fulkerson
---


# Question
Title: Counterexample for LTL - CTL equivalence
I have to find an example of a model where the LTL-formula $F G p \wedge F q$ is valid and the CTL-formula $EF AG p \wedge AF q$ is not valid. I found this example, but I'm not completely sure whether it's correct:

# Answer
> 1 votes
Consider the following model: you have 3 states, $s\_0,s\_1,s\_2$ with the transitions: $s\_0\to s\_0$, $s\_0\to s\_1$, $s\_1\to s\_2$ and $s\_2\to s\_2$ and the labels are $L(s\_0)=\\{p,q\\}$, $L(s\_1)=\emptyset$ and $L(s\_2)=p$.

Then, every computation starts with $q$, so $Fq$ holds, and every infinite computation eventually gets stuck in $s\_2$, or it is $s\_0^\omega$, and both satisfy $FGp$, so the LTL formula holds.

However, it never holds that $AFq$, so the CTL formula does not hold.

---
Tags: linear-temporal-logic, temporal-logic
---


title: Reduction from 4COL to 3COL

text:
# Question
Title: Reduction from 4COL to 3COL
I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$.

Is there any elementary proof to do it?

# Answer
> 1 votes
Your question is answered in a blog post of Lance Fortnow. Solutions are given by Fortnow and by Lovász.

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


# Question
Title: Importance of a person to another person in social network
In social network (an unweighted indirect network), is there some measure of importance of a person `A` on another person `B`, denote as `I(A,B)`, so that (approximately):

1. The smaller the shortest distance between `A, B` in the the network, the higher the `I(A,B)` (closeness)
2. If `A_1` is 1 of the 100 friends of `B_1`, `A_2` is 1 of the 2 friends of `B_2`, then `I(A_1,B_1) < I(A_2,B_2)` (the more friends I have, the less importance of each one)
3. Some other reasonable properties that resemble the importance of a friend to another friend in real society.

# Answer
> 3 votes
yes, social networks have a simple (graph) connectivity property in many or most cases/ situations/ contexts (such as "friend" connections on a social network like Facebook etc), but also a *weighted* property of the graph in various other situations. a common aspect of this now measured is widely/ generally referred to as the *influence* of the "friendship". two users may be connected, but *influence* measures other aspects.

one aspect of high interest to marketers and driving a lot of research is how much "friends" influence each others *purchasing decisions* ie if person *A* buys *x*, does that influence friend *B* to buy *x* also, or a *y* similar to *x*. here are a few papers/ refs on this subject. there are different ways to attempt to measure *influence* and in some cases it may be derived/ estimated that some users have more friends and are more thus influential on those friends, in other ways it can be determined from additional data such as looking at buying patterns of *A, B* if *A, B* are connected etc.

buying *influence* is just one of the major/ dominating areas of weighting under study, but there are various others. another key aspect coming up in 2016 in the US is *voting influence* that is under some study also, ie tendency of connected users to vote in similar ways.

---
Tags: graphs, social-networks
---


title: Oblivious RAM write protection

text:
# Question
Title: Oblivious RAM write protection
I'm trying to understand how oblivious RAM works, specifically path oblivious RAM. While I understand how this technique offers protection when reading data - multiple randomly distributed reads obfuscate the access pattern of the data actually requested - I can't tell how that helps protect against an attacker who is interested in the users write access.

Surely multiple randomly addressed writes would potentially overwrite critical data that is later required by the program. Similarly, while batching the writes would stop an attacker knowing exactly which addresses were written to at a given time, this would not stop them discovering which addresses were written to, nor the presence of those writes.

# Answer
> Surely multiple randomly addressed writes would potentially overwrite critical data...

Nope. The oblivious RAM data structures take care to ensure that, when doing reads and writes at random locations, they don't mess up the data. For instance, if doing an extra write, then they make sure to write the same value that was already there (except in encrypted form), so that it doesn't change what value is stored there.

> batching the writes would stop an attacker knowing exactly which addresses were written to at a given time

But the attacker would still know which set of addresses were written, which is leakage of partial information. Oblivious RAM aims to eliminate even this partial leak. So oblivious RAM achieves a stronger property than batching could ever provide.
> 2 votes

---
Tags: security
---


# Question
Title: Metrics for measuring the tradeoff between efficiency and effectiveness in Information Retrieval
I'm comparing several methods for building inverted indexes (n-grams, hash boundaries, etc.). Given a set of queries, these indexes perform differently. On one hand, I get performances metrics (efficiency) such as the time needed to execute the query. On the other hand, I get metrics such as precision and recall (effectiveness) by checking the relevance of the results. Depending on the method I use, there is a tradeoff between efficiency and effectiveness. For example, some methods loose a little in term of effectiveness for a huge gain in term of efficiency.

Are there some metrics which puts the effectiveness (precision, recall, etc.) in perspective with the efficiency (throughput, memory, etc.)?

# Answer
> 1 votes
I assume that your question is being put in the context of boolean retrieval. It seems that there is not a single metric that takes into account both efficiency and effectiveness and provide a theoretical framework for IR evaluation.

This is mainly because these two issues can sometimes be quite independent between each other. We use certain methods to build inverted indexes in order to mitigate memory issues that arise when we try to index large collections of documents. Some of these methods (such as hash tables) provide fast access to the dictionary (in $O(1)$ time) but fail to accomodate proximity queries (the sort of "find documents that have the word "Beatles" near the word "Animals"). Moreover there are implications arising if we are to index a collection that might change in size and content. Usage of B-trees can overcome these issues as these structures permit an ordering of their contents.

On the other hand some other methods (such as k-gram auxiliary indexes) charge us with additional processing time but offer a more broad range of queries that can be computed (complex wildcard queries such "co\*ter\*ed"). In general this results in a more powerful IR system in the sense of a wider capability in answering queries.

There is of course the "user happines" measure that takes into account the extent to which the user's information need is satisfied by the system but this is not always the case as users tend to take into consideration several other factors like the user interface which is independent of the system's performance.

In my humble opinion the issue of the relation between effectiveness and efficiency is something that can be examined more thoroughly in the "real" context of an implemented IR system. It is in this setting that more concrete conclusions can be extracted about the effect that different indexing methods have on the performance of the IR system.

An excellent resource in these topics is the following book by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze http://nlp.stanford.edu/IR-book/information-retrieval-book.html

---
Tags: information-retrieval
---


# Question
Title: Iota combinator and implicational propositional calculus
There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between these languages and propositional calculus.

We know $K := P → (Q → P)$ and $S := (P → (Q → R)) → ((P → Q) → (P → R))$

My question is this: Is there a relation between iota $λx.xSK$, jot, or iota prime $λx.xKSK$ with Łukasiewicz's axiom system?

$((P → Q) → R) → (R → P) → (S → P)$

# Answer
The axiom scheme you reference represents a classical logic, i.e. one with excluded middle. The computational interpretation of Peirce's law (implicitly embodied in Łukasiewicz's system) is call/cc. Neither iota nor jot support first-class continuations (or continuations of any sort), so they do not encode or imply Peirce's law.

Added much later:

I think I just now realized that the minimally functionally complete is talking about completeness of logical connectives and had originally thought it had been referring to the completeness of the SK basis. This realization doesn't invalidate my answer but makes it so that there is more to say.

The first thing to say is that functional completeness in the context of propositional logic is (usually) talking about Boolean functions and thus we usually talk about collections of *connectives* (like $\to$ and $\land$) being or not being functionally complete. It doesn't really make sense to use it to refer to programming languages which we usually want to be *Turing-complete* which is a very different notion.

Nevertheless, taking a logical view of the SK combinatory logic, as the question does, the only connective is $\to$ which is *not* functionally complete. This is mentioned on the referenced page on Łukasiewicz's system. That page also strongly implies that Axiom 3 is not derivable from Axiom 1 and Axiom 2 which correspond to $K$ and $S$ respectively. If true (which it, of course, is), that would mean that the single axiom can't be derived from Axiom 1 and 2 either, since you would then be able to derive Axiom 3. My original paragraph was a high-level argument of why this is the case. A more direct argument would be to provide a counter-model by using a non-classical model of intuitionistic logic which will validate Axioms 1 and 2 but not Axiom 3 and therefore not the single axiom.

As a final note, in the above I've been assuming a typed version of iota and jot which are untyped languages. This is necessary for the logical reading to be meaningful. It is worth noting that a type version of iota and jot would *not* be Turing-complete.
> 3 votes

---
Tags: lambda-calculus, propositional-logic, combinatory-logic
---


# Question
Title: From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
I am reading one of Guido van Rossum's essays on optimization in Python.

We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward algorithm.

```
def f3(list):
    string = ""
    for character in map(chr, list):
        string = string + character
    return string

```

Guido claims that the following algorithm avoids the quadratic behavior in the string concatenation.

```
def f5(list):
    string = ""
    for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
        s = ""
        for character in map(chr, list[i:i+16]):
            s = s + character
        string = string + s
    return string

```

How does this actually help and what is the significance of the value 16 in `f5`?

`f5` does not actually turn out to be faster, but I want the intuition that went into trying this strategy of optimization.

Note: we can assume that we are working with a list of length exactly 256.

# Answer
Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:

> Read the list in chunks of $k$, convert them to strings, and sum the chunks.

Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. Adding the chunks takes time $\Theta(k+2k+\cdots+n) = \Theta(k(1+2+\cdots+n/k)) = \Theta(k(n/k)^2) = \Theta(n^2/k)$. In total, we get a complexity of $\Theta(n(k+n/k))$. The optimal choice of $k$ is $\sqrt{n}$, and this gives a complexity of $\Theta(n^{3/2})$. In contrast, the trivial algorithm has $k = 1$ and so complexity $\Theta(n^2)$.

---

More generally, you can consider $d$ levels of recursion. Let $f\_d(n)$ denote the optimal complexity of such a scheme, measuring just the merging steps. Clearly $f\_1(n) \approx n^2/2$. Given an algorithm with $d$ levels, we can construct a $d+1$-level algorithm which cuts the input into chunks of length $k$, runs the $d$-level algorithm on each of them, and concatenates the result. This takes time roughly $(n/k)f\_d(k) + n^2/2k$. For example, $$ \begin{align\*} 2f\_2(n) &\approx \max\_k nk + n^2/k \approx 2n^{3/2} & (k=\sqrt{n}), \\ 2f\_3(n) &\approx \max\_k 2nk^{1/2} + n^2/k \approx 3n^{4/3} & (k=n^{2/3}), \\ 2f\_4(n) &\approx \max\_k 3nk^{1/3} + n^2/k \approx 4n^{5/4} & (k=n^{3/4}). \end{align\*} $$ We get that $2f\_d(n) \approx dn^{(d+1)/d}$. Calculus shows that the best choice of $d$ is $d = \log n$, in which case we obtain $2f\_{\log n}(n) = \Theta(n\log n)$. However, this scheme is not necessarily achievable.

If we choose a branching factor of 2 then we get an algorithm whose running time is $\Theta(n\log n)$ which resembles merge sort. In fact, the sorting lower bound gives a lower bound of $\Omega(n\log n)$ on any such merging procedure.

We can also prove the lower bound directly. For a sequence $\sigma\_1,\ldots,\sigma\_m$ of chunk lengths summing to $n$, define its potential by $$ \Phi(\vec\sigma) = nH(X\_{\vec\sigma}), \text{ where } \Pr\[X\_{\vec\sigma} = i\] = \frac{\sigma\_i}{n}. $$ Here $H$ is the entropy function.

The potential function starts at $\Phi(1,\ldots,1) = n\log n$ and ends up at $\Phi(n) = 0$. Suppose that $\vec\tau$ is obtained from $\vec\sigma$ by merging $\sigma\_i$ and $\sigma\_j$ to a new chunk $\tau\_k$. We can sample $X\_{\vec\sigma}$ by first sampling $X\_{\vec\tau}$, and if the result is $k$, sample according to the marginal distributions $\frac{\sigma\_i}{\sigma\_i+\sigma\_j},\frac{\sigma\_j}{\sigma\_i+\sigma\_j}$. Calculation shows that $$ \begin{align\*} \Phi(\vec\sigma) = nH(\vec\sigma) &= nH(\vec\tau) + n\Pr\[X\_{\vec\tau}=k\] h\left(\frac{\sigma\_i}{\sigma\_i+\sigma\_j}\right) \\ &= \Phi(\vec\tau) + (\sigma\_i+\sigma\_j) h\left(\frac{\sigma\_i}{\sigma\_i+\sigma\_j}\right) \\ &= \Phi(\vec\tau) + O(\sigma\_i+\sigma\_j). \end{align\*} $$ Here $h$ is the binary entropy function.

This shows that the potential difference is a lower bound on the running time. Since the overall potential difference is $n\log n$, we obtain a lower bound of $\Omega(n\log n)$. Furthermore, the calculation shows that it's best to always merge chunks of identical size.
> 10 votes

---
Tags: algorithms, strings, efficiency, arrays, loops
---


# Question
Title: Why do caches fetch data to the right if the offset bit is 0 and to the left if it is 1 in a 2-word block
Here is an example of table with 32 bit addresses and their respective indexes and tags. The cache has a total of 8 blocks and 2-word blocks.

So since we have 2 word blocks, that means that the offset is 1 and we use the least most significant bit as the offset. So in the first row, it not only brings 3 but it also brings 2 into the cache because the offset bit is 1(why not 4 if the offset bit is 1). Now I understand that the importance of this is to reinforce the idea of spatial locality, I just want to understand more about the procedure and what kinds of conflict it would cause if it was the other way around. If you can show it with an example that would be great.

# Answer
> 1 votes
The two-word blocks are always *aligned*, and you can find where they start by zeroing the LSB. So the two blocks are always of the form $x0,x1$. So if you fetch $x1$ you also fetch $x0$, and vice versa. This makes indexing the block easy, since to find what block a word belongs to, you just need to drop the LSB.

---
Tags: cpu-cache
---


# Question
Title: Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?
I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain the middle element of the array.

$T(n) = 2T((n+1)/2) + c$

However, I want to simplify this recurrence relation more.

Since you can often times omit floors and ceilings in recurrence relations, can I omit the $+ 1$?

If so, then my relation is now: $T(n) = 2T(n/2) + c$

Would this alter my big-Theta time complexity? Why or why not?

# Answer
This probably does not change the asymptotic order.

From $T'(n) = 2 T'(n/2) + c$, you can obtain $T'(n) = \Theta(n)$.

Then you can try to prove that your original $T(n) = \Theta(n)$ by mathematical induction.
> 4 votes

# Answer
We can rewrite the original recurrence as

$$T(n-1+1)=2T(\frac{n-1}2+1)+c$$ or, setting $m:=n-1$ and $S(m):=T(m+1)$,

$$S(m)=2S(\frac m2)+c,$$ which is of the simplified type.

After solving for $S(m)$,

$$T(n)=S(n-1)$$ and the solutions are virtually identical.
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Is integer sorting possible in O(n) in the transdichotomous model?
To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:

> Given a sequence of length $n$ consisting of finite integers, find the permutation where every element is less than or equal to its successor.

But is there a proof that it doesn't exist, in the transdichotomous model of computation?

---

Note that I'm not limiting the range of the integers. I'm not limiting solutions to comparison sorts either.

# Answer
Integers can be stably sorted in $O(n)$ time with $O(1)$ additional space. More precisely, if you have $n$ integers in the range $\[1, n^c\]$, the can be sorted in O(n) time.

This was only shown a couple of years ago by a team including the late Mihai Pătrașcu (which should surprise nobody who is familiar with his work). It's a remarkable result which I'm surprised more people don't know about, because it means that the problem of sorting integers is (theoretically) solved.

There is a practical algorithm (given in the paper above) if you're allowed to modify keys. Basically, you can compress sorted integers more than you can compress unsorted integers, and the extra space that you gain is precisely equal to the extra memory needed to do the radix sort. They also give an impractical algorithm which supports read-only keys.
> 4 votes

# Answer
For integers, you can use the Radix sort. It creates buckets and then sorts a list of numbers in $O(bn)$ where $b$ is an upper bound on the size in bits of any integer, and $n$ the number of elements to sort.

If there is no upper bound on the size of your integers, then I don't believe there is any known linear-time sorting algorithm.
> -1 votes

---
Tags: complexity-theory, sorting, computation-models, lower-bounds
---


# Question
Title: Probability with an unusual pseudo-random generator
I will preface this with the actual question taken from lecture:

> An unusual pseudo-random generator outputs integers between 1 and 4, inclusive, in such a way that each value, v, occurs with a probability that is inversely proportional to v. For example, 4 is half as likely to occur as 2, and 1 is three times as likely to occur as 3. Determine the probability P(v) for all possible values of v. Explain in detail, and give the final answer(s) explicitly, in decimal notation.

This seems like a very simple probability question; however, I just want to make sure I am looking at this the correct way. It says that each value occurs with a probability that is inversely proportional to *v*. I understand that the sample space here is `S={1,2,3,4}`, but wouldn't this not be possible due to the fact that the probability of *1* would be *1* (which is the inverse of *1*). Thus, `P(v)` would not sum up to be equal to 1, which is a basic property of probability on events.

Just double checking that I am looking at this question the correct way, and whether or not it is a trick question. Thanks!

**EDIT**: I understand that this question lies more as a statistical problem; however, it is from a CS class, so I thought it would still be appropriate to post here.

# Answer
> 1 votes
The key here is the part of the problem that says "each value, $v$ occurs with a probability that is *inversely proportional* to $v$". You can do this by assigning $$ P(1)=c, P(2)=\frac{c}{2}, P(3)=\frac{c}{3}, P(4)=\frac{c}{4} $$ Then, since these values are the only ones possible, we'll have $$ c\cdot 1+\frac{c}{2}+\frac{c}{3}+\frac{c}{4} = 1 $$ so $$ 1 =c(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}) = c\cdot\frac{25}{12} $$ and so $c=12/25$, giving us $P(1)=12/25, P(2)=6/25, P(3)=4/25, P(4)=3/25$. It's easy to see that these satisfy the requirements of the problem.

---
Tags: pseudo-random-generators
---


# Question
Title: How to determine if a regular language L* exists
I'm trying to make sense of regular languages, operations on them, and Kleene operations.

Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that there can be no string in the language that contains the substring 'xx'. Thus, my language could be expressed as L = {y, xy, yx}, since that language conforms to the definition.

Could I then argue that there is no language L\* since L\* could contain LL? That is, can a particular but arbitrarily chosen finite language that conforms to the definition exist, but since LL can't be in L\*, L\* cannot exist? Or must any L necessarily omit anything preventing L\* from existing?

# Answer
> 4 votes
Your confusion seems to stem from the incorrect assumption that if a language $L$ has a certain property, then $L^\*$ must also have that property. Consider this simpler example. Over the 1-symbol alphabet $\\{a\\}$ consider the property

> $L$ contains no words of length more than three

Then one language with this property is $L=\\{a, aaa\\}$. Then by the definition of the $^\*$ operator $$\begin{align} L^\*&=\\{\epsilon\\}\cup L\cup LL\cup LLL \cup\dotsm\\ &=\\{\epsilon\\}\cup\\{a, aaa\\}\cup\\{aa,aaaa, aaaaaa\\}\cup\dotsm\\ &=\\{\epsilon,a,aa,aaa,aaaa,aaaaa,aaaaaa,\dotsc\\} \end{align}$$ In other words, given this $L$, $L^\*$ consists of *all* finite strings of $a$s, which certainly doesn't have the property that $L$ did.

Now of course there are some properties of a language $L$ which are shared by $L^\*$: being regular is one such, consisting of just the empty string is another, and consisting of only even-length strings is yet another.

# Answer
> 4 votes
$L^\*$ always exists. ${}^\*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^\*$. Specifically, $L^\*$ is the language of all strings that can be made by concatenating zero or more strings from $L$. That's well-defined for any language $L$.

What you've observed is that $L^\*$ might have different properties from $L$. If we take your example of $L = \\{y,yx,xy\\}$, we see that no string in $L$ has $xx$ as a substring ($L$ is not the only language with this property but that's beside the point). On the other hand, $L^\*$ includes the string $yxxy$, which does have $xx$ as a substring. That doesn't mean that $L^\*$ doesn't exist; it just means that it doesn't have some property that $L$ has. Well, that's no surprise because $L$ and $L^\*$ are often different languages, in which case they can't have exactly the same properties.

# Answer
> 2 votes
Simply saying that $L$ has the alphabet $\\{x, y\\}$ and that no string in $L$ contains the substring $xx$ doesn't define a single language - there are infinite such languages. What you call expressing $L = \\{y, xy, yx\\}$ is actually defining such a language $L$ with three words that happens to have the property of no strings containing $xx$. $L^\*$ doesn't have this property, because it contains the word $yxxy$ (as well as infinite other words with double $x$).

I'm not sure exactly what you're trying to prove in the second part of your post. For any language $M$, the Kleene closure $M^\*$ always exists; if $M$ is regular, than $M^\*$ is also regular by definition. Whether it has the property of containing no words with the substring $x$ depends on the definition of $M$.

# Answer
> 1 votes
$L^\*$ exist. You have to see the languages as a set of words. The language $L$ is the **infinite set** of words formed with the symbols $x$ and $y$ that don't contain the substring $xx$. $L^\*$ is the smallest superset of $L$ that contains the empty string $\epsilon$ and is closed under the string concatenation operation.

Note: You don't have to determine if $L^\*$ exist. If $L$ is a regular language then by definition $L^\*$ exist and it is a regular language too.

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


# Question
Title: The language of machines that accepts all palindromes is not Turing recognizable
I have this question:

> $L = \\{\langle M \rangle | M$ is TM that accepts every palindrome over its alphabet $\\}$
>
> Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language.

What I have tried to do is to show reduction from $A\_{TM}$ (Accept problem) to $\bar L$, and I didn't succeed to show one. I tried to create a new machine that will reject some palindrome(s) if $M$ accepted $w$ when $\langle M,w\rangle$ is the input of $A\_{TM}$. But if $M$ will not halt on $w$, then the palindrome(s) will reject also by mistake.

So how can I show reduction from $A\_{TM}$ to $\bar L$ (or $\bar {A\_{TM}}$ to $L$)?

# Answer
> 2 votes
Here's a reduction $\overline{A\_{TM}}\le L$. Define the mapping from $(\langle\\:M\\:\rangle,w)\rightarrow \langle\\:N\\:\rangle$ where

```
N(x) =
   if x is a palindrome
      run M on w for |x| moves
      if M hasn't accepted yet
         accept

```

Now,

* If $(\langle\\:M\\:\rangle,w)\in\overline{A\_{TM}}$, then $M$ will never accept $w$ and so $N$ will accept all palindromes, so $\langle\\:N\\:\rangle\in L$.
* If $(\langle\\:M\\:\rangle,w)\notin\overline{A\_{TM}}$, then $M$ will accept $w$ in some number, $m$ of moves, so $N$ will accept all and only those palindromes of length $\<m$, so $\langle\\:N\\:\rangle\notin L$.

Finally, we conclude that $(\langle\\:M\\:\rangle,w)\in\overline{A\_{TM}}$ if and only if $\langle\\:N\\:\rangle\in L$ and since $\overline{A\_{TM}}$ is unrecognizable, then so must $L$ be.

To be fair, this is almost exactly Denis' argument, just specified for the reduction you required. It's a useful idiom that can be used to show that many languages are unrecognizable.

# Answer
> 1 votes
Let $M\_p$ be a TM that decides palindromes with runtime on $x$ at least $|x|$. Given $\langle M \rangle$ construct $\langle M' \rangle$ where $M'$ on $x$ behaves as follows:

* Run $M$ on $\langle M \rangle$ and $M\_p$ on $x$ in "parallel" (i.e. step by step, on separate cells, e.g. $M$ only uses odd cells, and $M\_p$ uses only even cells of the tape).
* If $M$ on $\langle M \rangle$ terminates, $M'$ rejects unconditionally.
* If $M\_p$ on $x$ terminates and $M$ on $\langle M \rangle$ is still continuing the computation at this step, $M'$ terminates the simulation of $M$ and outputs according to $M\_p$ on $x$.

Note that $M$ on $\langle M \rangle$ does not halt if and only if $M'$ decides the language of palindromes. (Why?)

---
Tags: computability, semi-decidability
---


title: Trying to understand max heapify

text:
# Question
Title: Trying to understand max heapify
I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and heapsort but did not find this clear.

I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

# Answer
> $Q\_1:$ I do not understand the function of `max-heapify`. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

`max-heapify` can be described as a recursive function. There is no particular prevention from a recursive function running in logarithmic time. For `max-heapify`, the recurrence is $T(n) \le T(2n/3) + \Theta(1)$ (here $2n/3$ is the worst case when the leaves is exactly half full; where $n$ is the size of the subtree rooted at the node under `max-heapify`). You can solve it by Master Theorem.

Another way of looking at `max-heapify` is to unfold the recursions: it "floats down" a value through a path of the subtree, whose length is $\sim \Theta(\lg n)$.

> $Q\_2:$ To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

The answer is simple: We don't run `max-heapify` on a min-heap. Use `min-heapify` for min-heap instead.
> 2 votes

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: Generate integer from 0 to 1 with equal probability
I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0\_4()) which generates random number from 0 to 4.

I am wondering if I can approach this way:

a). if gr0\_4() = 0 or 1 then I will use 0

b). if gr0\_4() = 2 or 3 then I will use 1

c). if gr0\_4() = 4 I will repeat the a) and b) steps.

Is my understanding correct that the "a" and "b" step each has 50% probability of happening?

```
def gr0_1():
  while True:
    x = gr0_4()
      if x == 0 or x == 1:
        return 0
      elif x == 0 or x == 1:
        return 1

```

What if I want to use gr0\_1() to create gr1\_7() i.e. create number between 1 to 7 with equal probability?

Can I use below reasoning to create that function gr1\_1().

As 7 consists of 3 bits. I can generate each bit with equal probability using gr0\_1(). So I will call gr0\_1() three times and based on that value I get, I will set/unset the corresponding bits to generate a number between 1 to 7 including the numbers 1 and 7. However I can get the number 0 but I don't want that so I will repeat the process again. Will the probability of each number generation between 1 to 7 will be 1/7 in that case also?

Some simple mathematical calculation will be nice to answer this. I tried to read up on rejection sampling but couldn't understand much.

# Answer
> 2 votes
Yes, this is exactly rejection sampling and it works in the way you think it works, assuming that your initial procedure `gr_04()` generates the numbers $0$–$4$ with equal probability (you say it's random but you don't say it's uniform).

If $X$ is distributed uniformly on $\\{0, \dots, 4\\}$, then $\Pr(x\in\\{0,1\\}) = \Pr(x\in\\{2,3\\}) = 2/5$. With probability $1/5$, you'll have to try again but, on your second attempt, the probability of getting $0$ or $1$ is still equal to the probability of getting $2$ or $3$. The number of attempts you have to make before you get something in $\\{0, \dots, 3\\}$ is just a geometric random variable with parameter $p=4/5$ and this has expectation $(1-p)/p = 1/4$ so, on average, you'll have to make $5/4$ calls to `gr_04()`, including the one that succeeds.

The analysis of your second example is similar: your procedure generates each possible answer with the same probability and each attempt succeeds with probability $7/8$, so you'll need an average of $8/7$ calls to `gr_01()`, which means an average of $(8/7)(5/4)=10/7$ calls to `gr_04()`.

---
Tags: algorithms, pseudo-random-generators, random-number-generator
---


# Question
Title: Maximal number of rotations after deleting a node in an AVL tree
What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.

I know that it is $O(\log n)$ but I'm trying to find a more precise number – it is in $\[\log n, 2\log n\]$ of course.

Nevertheless, I am dying to see the exact value of $c$.

# Answer
***Note:*** This does not answer the question exactly. However, it would be helpful for further study.

---

Quoted from Section 6.2.3 (entitled "Balanced Trees") of TAOCP "Sorting and Searching", 2nd Edition:

> In order to figure out the running time of Algorithm A (*for AVL search and insertion*; \[emphasis mine\]), we would like to know the answers to the following questions:
>
> * How many comparisons are made during the search?
> * How much adjustment is needed in step A6?
> * How often do we need to do a single or double rotation?

Before going into details, it summarizes:

> It is not difficult to derive upper bounds on the worst case running time, using Theorem A, but of course in practice we want to know the average behavior. No theoretical determination of the average behavior has been successfully completed as yet, since the algorithm appears to be quite complicated, but several interesting theoretical and empirical results have been obtained.

You would probably be interested in Theorem A mentioned above:

> Theorem A (Adelson-Velsky and Landis). The height of a balanced tree with $N$ internal nodes always lies between $\lg(N + 1)$ and $1.4404 \lg(N + 2) - 0.3277$.

You can also find many empirical results (and some theoretical results) in the following paragraphs.
> 2 votes

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


# Question
Title: Maximal difference of height between two leaves in an AVL tree
What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.

I am not sure about my answer - I think that it is $O(\log n)$, given the fact that at every level we may have difference equal one.

Am I right?

# Answer
We consider Fibonacci tree (\[TAOCP3, Knuth98, Sect. 6.2.1\]) and compute the maximal height difference in it.

A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP):

> * If $k = 0$ or $k = 1$, the tree is simply a single node.
> * If $k \ge 2$, the tree has a left subtree of order $k-1$ and a right subtree of order $k-2$.

It is easy to verify that a Fibonacci tree is also an AVL tree.

---

From the figure above, we observe that the two leaves at the leftmost $l$ and at the rightmost $r$ differ most by heights ($H\_l, H\_r$ among all pairs of leaves. We can compute the height difference as follows.

A Fibonacci tree of order $k$ has $n = F(k+2)-1 \sim \Phi^{k+2}$ nodes in total, where $\Phi$ is the golden ratio.

$$H\_l - H\_r = k \text{ (leftmost path; decrease by 1}) - k/2 \text{ (rightmost path; decrease by 2}) = k/2 \text{ (maybe floor or ceiling functions here; I omit the details)}.$$

Because $n = \Phi^{k+2}$, we have $k/2 = \log\_{\Phi} \sqrt{n} - 1$.
> 6 votes

# Answer
Here is an *almost perfect* visualization of an AVL tree.

>

As you can see, you can increase the the maximal difference between leaves only once per level.

In other words, to have your AVL balanced you've got to keep the balance factor between $-1$ and $1$. So, if you want to maximise the highest difference between two leaves, then you don't want the balance factor to be equal $0$ in any node.

Basically, the maximal difference is $O(logn)$.

Here are some more AVL trees I've drawn to test my reasoning.

I guess that the maximal level is $\lfloor log(n) \rfloor - 1$ however I am not sure.

Resources:
> 2 votes

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


# Question
Title: User level threads are transparent to the kernel?
Find whether given statement True or False? Explain.

> User level threads are transparent to the kernel?

---

### My attempt :

False. Since, user level threads are managed by a user level library however, they still require a kernel system call to operate. It does not mean that the kernel knows anything about thread management. Not at all, it only takes care of the execution part. the lock of the cooperation between user level threads and the kernel is a known disadvantage.

---

Somewhere it explain as : "The kernel knows nothing about user-level threads and manages them as if they were single-threaded processes".

I found another statement "*User level threads are transparent to OS and kernel level threads are scheduled by OS*". It seems correct.

My question is :

> Are user level threads transparent to the kernel? What is meaning of transparent here?

# Answer
> 6 votes
As, the linked answers and the explanations provided by your textbooks describe that, *user level threads are transparent to the kernel*, yes they are indeed.

Kernel Level threads are not transparent to the kernel, but user level threads are. Because you yourself said, that User Level Threads are managed by the User level library, and what happens is, the user level threads can get assigned to one or many kernel threads. About **these** kernel threads the kernel keeps track of (are not transparent to kernel). But it doesn't know which user threads have got assigned onto these kernel threads and how many.

Say, if five user threads are assigned onto one kernel thread and 4 other user threads are assigned onto another kernel thread, the kernel sees just two kernel threads (requesting execution) and doesn't know that there are altogether 9 threads, but it just knows that the program called the User Level Application(s) is(are) using two of the kernel threads.

I hope this helps. Also, I suggest you read the linked posts carefully. They're pretty explanatory.

---
Tags: operating-systems, concurrency, process-scheduling, threads, os-kernel
---


# Question
Title: Why is my regular grammar for palindromes wrong?
I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with.

I've created grammar which can generate all palindromes and that is why I wonder why it's wrong.

```
A -> e
A -> a | b | ... | z
A -> aAa | bAb | ... | zAz

```

# Answer
Your grammar is correct, in the sense that it does generate all palindromes over the alphabet $\\{a, \dots, z\\}$. But it's a context-free grammar and not a regular grammar. In a regular grammar, you're only allowed rules of the form $A\to\epsilon$, $A\to a$ and $A\to aB$, i.e., there is at most one non-terminal on the right and any terminals must come before it.

(Alternatively, you get the same class of languages by insisting that any terminals on the right must come after the nonterminal but you can't mix the two in a single grammar.)
> 4 votes

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


# Question
Title: Can anybody suggest some algorithms for computing the edit distance other than Wagner–Fischer algorithm?
I'm currently working with finding **edit distance between two string of unequal length**. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'm dealing with some cryptographic measure with edit distance where algorithm with dynamic programming is not suitable. Please have a look at the algorithm. If we want to do this computation homomorphically, circuit-based computation is needed here which will time consuming one. Usually homomorphic computation works well where there is more additions than multiplications.

This is why, I'm looking for another algorithm rather than the above one.

# Answer
The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.
> 6 votes

---
Tags: algorithms, reference-request, string-metrics, edit-distance
---


# Question
Title: How to optimize a function by maximizing 1 variable and minimizing another?
**Problem**

I want to implement an optimization algorithm for my file transfer program.

The program buffers data in a local file before uploading to central server periodically and it compresses the files before transferring.

I would want the program to intelligently predict the time and size thresholds before transferring.

The objective function could be defined as following

f(u) = theta1\*u + (theta2\*u)/b + theta3

where

* u is the size of data
* b is the network bandwidth (bps)
* f(u) is the time taken to transfer u bytes of data.
* theta1\*u refers to amount of time taken to compress u bytes of data
* theta2\*u\*b refers to time taken to transfer compressed data.
* theta3 is constant protocol overhead

I want to be able to optimize the transfer by minimizing time and maximizing uncompressed size. If I were to simply minimize f(u) that would have been easy but then in this particular case , I would also want to maximize amount of data to be transferred. The idea is to be able to come up with a machine learning algorithm which can change as per different network scenarios and fluctuating bandwidth , rather than user providing it at start of program.

Of course, I would implement it with some sane seed values and keep them within sane boundaries.

**Solution space**

Given the nature of this problem , which class of algorithms should I be looking into? Would gradient descent be the right way to approach this? is it possible to apply maximize and minimization on same function of 2 different variables? Am I over-thinking this ?

# Answer
You would have to look at multiobjective optimisation, with these methods you can optimise two functions at the same time. Just be aware that, depending on the method that you end up using, you might have in the end a number of solutions equally good (trade offs) which you would have to choose from.
> 2 votes

# Answer
You can't. The optimal solution is not well-defined. In general there will be a range of tradeoffs between minimizing time and uncompressed size, and you haven't specified anything that would allow uniquely identifying which you want.

Your first step is that you need to specify a single objective function, where the goal is to find a solution that maximizes the objective function. Then you can try applying standard methods from mathematical optimization, e.g., gradient descent, Newton's method, and so on.
> 4 votes

---
Tags: optimization, machine-learning, gradient-descent
---


# Question
Title: Why add a +1 to the constant proving an O(n) bound?
I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$.

To determine the constant $C$ given by the relation $|T(n)| \< C \cdot g(n)$, we take

$\qquad\displaystyle \lim\_{n \to \infty} T(n)/g(n)$

which gives us

$\qquad\displaystyle \lim\_{n \to \infty} (4+4n)/n = 4$.

However, in the answer sheet it say to take

$\qquad\displaystyle \lim\_{n \to \infty}(4+4n)/n + 1 = 5$.

What is the purpose/reasoning for this $+ 1$ term, I haven't seen anything about before?

# Answer
We want to find a $c$ such that $4+4n\le cn$ for all $n$ greater than or equal to some bound $N$. So we need a $c$ such that $(4+4n)/n \le c$, or $(4/n)+4\le c$. Now while it's true that $$ \lim\_{n\rightarrow\infty}\frac{4}{n}+4=4 $$ we can't use $c=4$ since for all positive $n$ we have $(4/n)+4\>4$. In other words, we need to pick $c$ to be some number larger than 4 and 5 is as good a choice as any in this case. There's nothing magical about picking a $c$ one greater than the limit; it's just one choice out of infinitely many.
> 4 votes

---
Tags: asymptotics, proof-techniques, landau-notation
---


# Question
Title: Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions
Assume $X$ and $N$ are two sets of vectors (observations) from a normal distribution, where $X$ represents clean data and $N$ represents noise; and $A$ a projection matrix of a filter. The scenario is that our clean data was corrupted by a multiplicative noise via matrix $A$ and an additive noise of $N$:

$$Y=A X + N.$$

How can we learn the projection matrix $A$ and $N$ from the training data $X,Y$? Does the Gaussian assumption of $A$, $N$ and $X$ help to have a better estimation or guide to use a specific solution?

Here is matlab code for the training data, noise and a simple projection:

```
    dataVariance = .10;
    noiseVariance = .05;
    mixtureCenters=randn(13,1);
    X=randn(13, 1000)*sqrt(dataVariance ) + repmat(mixtureCenters,1,1000);

    %N and A are unknown and we want to estimate them.
    N=randn(13, 1000)*sqrt(noiseVariance ) + repmat(mixtureCenters,1,1000);
    A=2*eye(13);

    Y=A*X+N;

    for iter=1:1000
        A_hat,N_hat = training(X_hat,X,Y);
    end

```

---

Note: if necessary, for each estimation of $A$, an error can be calculated for an estimation of $N$ using a current $A$.

For example:

```
for iterate=1:1000
  initiate A
  estimate N using current A (N=Y-A*X)
  calculate error of estimation (err=Y-A*X+N)
  update A

```

But I would prefer not to go for gradient descent approaches.

# Answer
> 1 votes
Your problem is that of *multivariate linear regression*. Finding each row of $A$ corresponds to a classical *linear regression* problem, which can be solved using the method of least squares, which is optimal here since the noise is Gaussian.

Once you have an estimate for $A$, you can estimate the parameters of $N$ by isolating $N = Y-AX$. (This is not necessarily the optimal method since you only have an estimate for $A$, but practically it might be good enough.)

# Answer
> 0 votes
Just to summarize the answers given for this question, here I provide a visualization of different methods carried out to learn the projection matrix $A$ given clean samples $X\_i$ and noisy samples $Y\_i$:

In the first row we can see 5 different projection matrices ($A$) chosen to project $X$ before adding Gaussian noise $N$.

In the second row, you can find the random projections initialized to be learned via different methods.

In the third row, using the normal equation, we directly derive the projection matrix: $$ \hat A = (X^T \times X)^{-1} \times X^T \times Y$$

In the fourth row, a linear regression using gradient descent is used to learn the projections via $X$ and $Y$.

And finally, the last row, using kalman filtering method (find out more about it here).

As you can observe, the GD solution and the normal equation are very similar and since in this example, $(X^T \times X)^{-1}$ is feasible to calculate, it sounds a more reasonable solution and can be done in only one step. If the dimensionality of our features were too high, then we can use the GD since both $X$ and $Y$ are Gaussian.

The KF solution converges faster than GD, but can not achieve a good performance as GD, I believe.

After learning $A$, $N$ can be calculated via: $$\hat N=Y- \hat A \times X$$

and further $\hat {\mu\_N}$ and $\hat {\Sigma\_N}$ can be computed using $\hat N$.

---
Tags: statistics, error-estimation
---


# Question
Title: Proof for Minimum number of insertions to convert a string to a palindrome
For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is:

$$ c\[i,j\] = \begin{cases} c\[i+1,j-1\] & \text{if } S\[i\] = S\[j\], \\ \min(c\[i+1,j\],c\[i,j-1\]) + 1 & \text{otherwise}. \end{cases} $$

(where $c\[i,j\]$ denotes the minimum insertions for the substring of $S$ beginning with index $i$ and ending with $j$).

But how do we (formally) prove the correctness of that relation? I tried to use the "cut-and-paste" method, but wasn't sure how to apply it here (to either the first or second line of the recurrence relation).

# Answer
As D.W. indicates, you use proof by induction. I'll explain this with some hints on the case $S\[i\] = S\[j\]$. The intuition is that if $S\[i\] = S\[j\]$ then the best way of converting $S\[i\],\ldots,S\[j\]$ into a palindrome is converting $S\[i+1\],\ldots,S\[j-1\]$ into one, and then converting this to a solution for $S\[i\],\ldots,S\[j\]$ at no further cost (how?).

Formally, we need to prove two things:

1. $c\[i,j\] \leq c\[i+1,j-1\]$.
2. $c\[i,j\] \geq c\[i+1,j-1\]$.

For the first inequality, you need to show that if you can convert $S\[i+1\],\ldots,S\[j-1\]$ into a palindrome by inserting $m$ characters, then you can convert $S\[i\],\ldots,S\[j\]$ into a palindrome by inserting at most $m$ characters. You get the first inequality by taking $m = c\[i+1,j-1\]$. The proof is not difficult and left to you.

The second inequality is more delicate. Now you need to show that if you can convert $S\[i\],\ldots,S\[j\]$ into a palindrome by inserting $m$ characters then you can convert $S\[i+1\],\ldots,S\[j-1\]$ into a palindrome by inserting at most $m$ characters. To show this, consider the insertions converting $S\[i\],\ldots,S\[j\]$ into a palindrome: $$ w\_{i-1},S\[i\],w\_i,S\[i+1\],w\_{i+1},\ldots,w\_{j-1},S\[j\],w\_j. $$ Here the $w\_t$'s are words which may be empty.

> Claim: We can modify this solution to a solution with possibly less insertions in which at least one of $w\_{i-1},w\_j$ is empty.

(Proof left to you.) If both $w\_{i-1},w\_j$ are empty then it is easy to complete the proof (details left to you). Otherwise, suppose without loss generality that $w\_j$ is empty, that is, the insertions are

$$ w\_{i-1},S\[i\],w\_i,S\[i+1\],w\_{i+1},\ldots,w\_{j-1},S\[j\]. $$

Since $w\_{i-1}$ is non-empty and the word is a palindrome, it must start with $S\[j\]=S\[i\]$. Writing $w\_{i-1} = S\[j\] x$, we can rewrite this solution as

$$ S\[i\],x,S\[i\],w\_i,S\[i+1\],w\_{i+1},\ldots,w\_{j-1},S\[j\]. $$

I'll let you finish the proof of this case from here, and to mimic this proof for the case $S\[i\] \neq S\[j\]$.
> 4 votes

---
Tags: algorithms, recurrence-relation, dynamic-programming, correctness-proof
---


# Question
Title: What is wrong with my LP exercise (longest path cost for a graph)
I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have also two nodes (marked as B and E), and I have to find the maximum path cost from B to E. Also, each edge can be used at most k times and the total cost of the path must be at most C.

I have inserted also the constraint regarding the balance of each node as follow (where E are the edges and x\[i,j\] tells me how many times an edges is been used, and the two nodes B and E):

$\sum\nolimits\_{j |(j,i) \in Edges} x(j,i) -\sum\nolimits\_{j | (i,j) \in Edges} x(i,j) =0$

$\sum\nolimits\_{j | (j,B) \in Edges} x(j,B) -\sum\nolimits\_{j | (B,j) \in Edges} x(B,j) =-1$

$\sum\nolimits\_{j | (j,E) \in Edges} x(j,E) -\sum\nolimits\_{j | (E,j) \in Edges} x(E,j) =1$

The objective function is: $max \sum\nolimits\_{(i,j) \in Edges} x(i,j)\*cost(i,j)$

Other constraints:

$x(i,j) \<= K \forall (i,j) \in Edges$

$\sum\nolimits\_{(i,j) \in Edges} x(i,j)\*cost(i,j) \<= C$

When i run the LP solver the solution that it gives me, of course it includes a path from B to E, but also an other cyclic path that not includes nodes B and E.

Any suggestion?

# Answer
> 1 votes
You are on a fool's errand: Longest Path is NP-hard, thus there *is no LP* for solving it.

---
Tags: graphs, optimization, linear-programming
---


# Question
Title: How do I derive a regular grammars from this regular expression?
How do I derive a regular grammars from this regular expression?

```
(a or b)*ba(ba)*

```

I'm stuck with the last part so

```
S -> A | B | C
A -> aA | bA
B -> bC
C -> cD
D->bE ?
E->af | ^ ?

```

Any help would be appreciated thanks!

# Answer
> 3 votes
Use Thompson's algorithm to convert the regular expression to a NFA. Then, you can directly read a regular grammar off, given the NFA: each non-terminal represents one state of the NFA.

---
Tags: formal-grammars, regular-expressions
---


# Question
Title: Stronger versions of P != NP which better express actual convictions
Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy doesn't collapse!" expresses the core of "P is not equal to NP!" ? Let me try to elaborate:

The P vs NP problem implicitly invokes a number of related but distinct challenges and convictions. Focusing on the convictions, we have that NP != coNP is believed with nearly the same conviction as P != NP, and is part of the conviction that the polynomial hierarchy doesn't collapse. (Because the polynomial hierarchy is less familiar than NP, this conviction is weaker, but still strong enough to be used as a reasonable assumption in a proof.)

Similarly, "L != NP is incredibly hard to prove" is believed with nearly the same conviction as "P != NP is incredibly hard to prove". Now there may be weaker statements which we don't know how to prove either, like "$U\_{E^\*}$-uniform TC0 != PH", but they don't necessarily feel natural enough to be part of real convictions. So my question is whether "L-uniform NC1 != NP is incredibly hard to prove" would qualify as a natural (and sufficiently strong) conviction. (I'm pretty certain that "NC1" is appropriate here, but I'm less certain about "L-uniform" and "NP". Maybe something like "non-uniform NC1 != PH/poly is incredibly hard to prove" would be much more natural and somehow imply all the other related natural convictions.)

# Answer
Considering that the conviction "P != NP is incredibly hard to prove" is largely based on known barrier results, one promising approach (for answering this question) would be to look for a statement expressing a natural separation, and ask why it is hard to prove. Then one can check which of the known barrier results for P != NP can be extended to that statement.

The question "Why is it hard to prove ALogTime != PH?" should be most promising in this respect. This statement is weaker and more natural than "L-uniform NC1 != NP", because $\subset$ PH and

> ALogTime = DLogTime-uniform NC1 = $U\_{E^\*}$-uniform NC1 $\subset$ L-uniform NC1.

For the relativization barrier, it would be enough to show ALogTimeA = PHA for A := TQBF, where TQBF is the PSPACE-complete problem to decide true quantified Boolean formulas. No idea whether the natural proofs and the algebrizing proofs barrier should be expected to carry over, but at least checking whether they do should not be terribly difficult.

---

I also wonder whether the statement "ALogTime != PH" points to the right place where the difficulties for proving separation results start. Below ALogTime, we have the logarithmic time hierarchy LH, which probably doesn't collapse either, but the question is whether this has been proved (or whether this is relatively easy to prove, just in case nobody cared yet).

**Edit:** It turns out somebody actually cared to prove that the logarithmic time hierarchy is strict, and how it is related to the AC0 hierarchy. See Searching Constant Width Mazes Captures the AC0 Hierarchy by Barrington et al. I didn't check which results were already proved in one of the references, and which results have been proved for the first time in that paper.

This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH". Observe that (it seems that) coNLogTime verification can be used instead of PTime verification when characterising NP, so this is actually really equivalent to a statement where "polynomial time" no longer occurs, only some version of "read only polynomial length witness string".
> 2 votes

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


# Question
Title: Finding a small element in a changing array
Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like.

The array is initialized to zeros.

The goal to to support two operations:

* `Update(k,v)` \- sets $A\[k\]=v$.
* `Small()` \- returns an index in which the element is smaller than or equal to the median.

Assuming that finding a small item has to be done in $O(1)$ time, how fast can we perform updates?

Some notes:

* You can use preprocessing to initialize any data structure you wish before the sequence of updates starts.
* I'm *only* looking for deterministic algorithms. A randomized algorithm for this problem is trivial.
* Making update run in $O(\log n)$ is straightforward (e.g. using a balanced BST).

Can we improve to $o(\log n)$ or show an $\Omega(\log n)$ lower bound?

# Answer
> 4 votes
**Here is an amortized solution to the problem in which updates may only increase values:**

Maintain:

1. A linked list of some of the items less than the median
2. A linked list of all items greater than the median (and some items less than it)

To return a small item, return an item from #1.

To update an item greater than the median, change its key in #2.

To update an item less than the median, remove it from #1 and add it to #2. If this makes #1 empty, rebuild both lists using a linear-time partitioning algorithm.

Update takes amortized constant time, using physicists argument and a potential function of twice the size of list #2 or the bankers argument and two coins on each item in list #2.

**Here is an amortized solution in which updates may increase or decrease values:**

To start, build three linked lists of size $n/3$. All items in list #1 should be less than all items in list #2, and all items in list #2 should be less than all items in list #3. One more list will be maintained; I'll call it the junkyard.

To change the key of an item:

* When increasing the key of an item in #1, move it to the junkyard.
* When decreasing the key of an item in #3, move it to the junkyard.
* When changing the key of an item from #2, move it to the junkyard.
* When changing any other key, do not remove it from or add it to any list.

The junkyard is called "full" when it has size $n/6$. Until then, all items in #1 are less than the median. Once the junkyard is full, rebuild.

The amortization argument works the same, but now the potential is six times the size of the junkyard, or, equivalently, each move to the junkyard requires 6 coins.

**Here is a complete deamortized solution:**

All operations can be done in constant time using a technique called *incremental global rebuilding*.

Maintain three copies of the second version of the structure designed above, along with three pointers to them, called PAST, PRESENT, and FUTURE. If a structure is pointed to by A and we want to point to it from B, we call that "renaming A to B".

We will proceed in four stages. After stage 4, we will rename PRESENT to PAST, rename FUTURE to PRESENT, and point the FUTURE pointer at empty space (or the null pointer). Then we will start with stage 1 all over again.

Each stage lasts $n/36$ updates. Queries are always answered from PRESENT

Stage 1:

When this stage starts:

* We will never query the structure pointed to by PAST again. It is dead, so we don't really care about its contents.
* PRESENT's junkyard has at most $2n/36$ items in it.
* FUTURE is just a null pointer.

During this stage, updates are performed on PRESENT as usual, but for each update, we perform 36 steps of destructing PAST. As a result, by the end of this stage, $n$ destructing steps have been performed on PAST and it is empty, using no memory.

At the end of this stage, PRESENT's junkyard might be as large as $3n/36$.

Stage 2:

When this stage starts, we allocate an empty linked list that we call FUTURE.

During this stage, for each update to PRESENT we also copy 36 items into FUTURE. Also, for each item that is updated, we update its key in FUTURE if it already has been copied. Note that the update in FUTURE doesn't touch any junkyards, since FUTURE is just a linked list at this point.

At the end of this stage, PRESENT's junkyard might be as large as $4n/36$, and the items in PRESENT and FUTURE are identical.

Stage 3:

When this stage starts, we allocate an empty queue that can hold representations of update operations (for instance, as a pair containing a pointer to the item and its new value).

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue, and we perform 36 steps of the initialization of FUTURE into the structure described in section 2 above. As a result, by the end of this stage, $n$ initialization steps have been performed on FUTURE and it is completely initialized, with a junkyard size of 0. However, because updates were queued, it does not hold the same data as PRESENT, which we will have to fix in Stage 4.

At the end of this stage, PRESENT's junkyard might be as large as $5n/36$ and the queue has size $n/36$.

Stage 4:

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue and dequeue two operations to play back in FUTURE. During this stage the queue grows by $n/36$ operations and shrinks by $2n/36$, leaving it empty at the end of the stage.

At the end of this stage, PRESENT's junkyard might be as large as $6n/36$ and FUTURE's junkyard might be as large as $2n/36$. We now switch names as described above, renaming PRESENT to PAST, FUTURE to PRESENT, and pointing FUTURE at the null pointer. The prerequisites for Stage 1 are now met, and at no point did PRESENT have more than $n/6$ items in its junkyard.

---
Tags: algorithms, data-structures, time-complexity, arrays, lower-bounds
---


# Question
Title: Is the following language recursively enumerable?
Let $L =\\{ \<M\> | $ the amount of words $w\in\Sigma^\*$ that $M$ does **not** halt on is finite $\\}$.

I would like to prove that $L\notin RE$.

I can show that $\overline{L}\notin RE $ that is $L\notin CoRE$.

I do this with showing a reduction: $\overline{L\_{acc}} \leq \overline{L} $ and since $\overline{L\_{acc}}\notin RE$ then $\overline{L}\notin RE$.

The reduction goes as follows:

* **input:** $\<M\>,\<w\>$
* **output:** $\<M\_w \>$

where $\<M\_w\>$ is a TM that, on an input $x$ ignores it and performs:

1. Run $M$ on $w$
2. If $M$ rejected get yourself into an inf loop
3. If $M$ accepted then accepts as well.

Now if $\<M\>\<w\>\in\overline{L\_{acc}}$ then $w\notin L(M)$, thus $M$ either rejects $w$ or does not end its calculation on it, but in both cases $M\_w$ will not end its calculation on all inputs. Otherwise, if $\<M\>\<w\>\notin \overline{L\_{acc}}$ then $w\in L(M)$ and then $M\_w$ will halt (and accept) its calculation on every input $x$.

So I have that $\overline{L\_{acc}} \leq \overline{L} $ and thus $\overline{L}\notin RE$, that is $L\notin CoRE$.

But I am at a loss on how I can prove $L\notin RE$? I tried a reduction from $\overline{L\_{acc}}$, but this idea does not work because $M$ might not halt on $w$. I also tried from $L\_{\Sigma^\*}$ or from $L\_d$, but could not find a reduction that will prove me that $L\notin RE$.

Does someone have an idea for such a reduction? Or perhaps another method to prove $L\notin RE$?

# Answer
> 3 votes
I'll provide some hint. Try building a reduction $\overline{L\_{acc}} \leq L$ changing your argument as follows:

... where $\<M\_w\>$ is a TM that, on an input $x$ it performs:

1. Run $M$ on $w$ for $|x|$ steps
2. If $M$ rejected within $|x|$ steps ...
3. If $M$ accepted within $|x|$ steps ...
4. If $M$ did not halt within $|x|$ steps ...

When $M$ does not accept $w$, you want the above to diverge only on finitely many $x$s.

When $M$ accepts $w$, you want the above to diverge on infinitely many $x$s.

---

Alternatively, you can try to exploit the Rice-Shapiro theorem.

---
Tags: computability, turing-machines, reductions, undecidability
---


# Question
Title: Find set of non-overlapping rectangles in a 2D grid
I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.)

I want to find a subset $S$ of rectangles, so that $S \subseteq R$, so that no two rectangles in $S$ overlap, and so that $S$ is as large as possible. (Alternatively, you can think of this as finding a maximum independent set in a graph where we have one vertex per rectangle, and an edge between two rectangles if they overlap.)

Can this problem be solved in polynomial time? Is it NP-hard?

I can see how to solve the one-dimensional analog (maximum set of non-overlapping intervals) in polynomial time using dynamic programming, but that algorithm doesn't seem to extend to this case. Wikipedia calls this the maximum disjoint set problem and says that when the set of shapes is arbitrary, the problem is NP-hard, but it doesn't discuss the specific case of axis-aligned rectangles with integer coordinates. That makes me suspect this problem might be NP-hard, but I haven't found a reference or proof of that.

# Answer
> 5 votes
The problem you state is shown to be NP-Hard \[1, 2\]. However, there is an $O(\log \log n)$ approximation algorithm for the problem \[3\].

\[1\] H. Imai, T. Asano. Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms 4(4): 310-323, 1983.

\[2\] R.J. Fowler, M.S. Paterson and S.L. Tanimoto, Optimal packing and covering in the plane are NPcomplete. Information Processing Letter. 12 3 (1981), pp. 133137.

\[3\] Parinya Chalermsook, Julia Chuzhoy: Maximum independent set of rectangles. SODA 2009: 892-901

---
Tags: algorithms, computational-geometry, np-hard
---


title: Approximation for vector bin packing

text:
# Question
Title: Approximation for vector bin packing
I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing.

To clarify, inputs to the bin packing problem are real numbers $x\_1,...,x\_n\in \[0,1\]$, which should be divided into $k$ bins $S\_1,...,S\_k$ such that for all $i$: $\sum\limits\_{x\in S\_i}x\le 1$.

Inputs to the vector bin packing problem are vectors $x\_1,...,x\_n\in \[0,1\]^d$, which should be divided into $k$ bins $S\_1,...,S\_k$ such that for all $1\le i \le k$ and $1\le j\le d$: $\sum\limits\_{x\in S\_i} x^j\le 1$, where $x^j$ is the $j'th$ coordinate of $x$.

It seems intuitive to use the 2-approximation on each coordinate of the given vectors $x\_1,...,x\_n\in \[0,1\]^d$ and obtain $d$ partitions into at most $2k$ bins (where $k$ is the minimal number of bins for the vectors partition). However, i cant seem to combine those bins into a partition of size at most $2d\cdot k$. For any vector $x\_i\in \[0,1\]^d$, let $b\_i\in \left\\{1,...,2k\right\\}^d$ be the vector whose $j'th$ entry is the bin in which $x\_i^j$ was placed (after running the approximation on all the $j'th$ components). Since i cant allow two vectors $x\_i,x\_j$, whose corresponding vectors $b\_i,b\_j$ differ in at least one component, go into the same bin, it seems i need at least $(2k)^d$ bins. What am i missing?

# Answer
> 1 votes
Create an instance $y\_1,\ldots,y\_n$ of bin packing by taking $y\_i = \max(x\_i^1,\ldots,x\_i^d)$, and solve it using the given approximation algorithm. The solution is feasible for the vector bin packing problem. On the other hand, given a solution for the vector bin packing problem, you can construct a solution for the "max" bin packing problem using at most a factor $d$ more bins by splitting each bin into $d$ bins according to the largest coordinate.

---
Tags: algorithms, approximation
---


# Question
Title: Delete a consecutive range of leaves from a binary tree
Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values).

I want to delete a consecutive interval of leaves. In other words, suppose we order the leaves from left to right and number them $1,2,\dots,n$. I am given a pair of indices $i,j$, and I want to delete leaves $i,i+1,\dots,j-1,j$. This operation should also delete an interior node if all of its descendant-leaves are deleted.

Can this be done efficiently? Can it be done in $O(d)$ time, regardless of $i,j$?

# Answer
> 1 votes
Yes. This can be done in $O(d)$ time. As a nice consequence, if we have a balanced binary tree, then $d = O(\lg n)$, so range-deletion can be done in $O(\lg n)$ time, regardless of how large the range is.

This is hard to explain without a picture, but the key insight is this: it suffices to delete a set $S$ of nodes, where $S$ can be chosen so that $|S| \le 2d$. (This will of course delete all of the descendants of every node in $S$.) Since $|S| = O(d)$, the running time to delete the nodes in $S$ will be $O(d)$. In other words, the interval $\[i,j\]$ can be expressed as a union of $O(d)$ subtrees. Roughly speaking, the set $S$ will be chosen by taking a subset of the siblings of the nodes on the path from $i$ or $j$ to the root.

In particular, we will define

$$S = \\{n : L(n) \subseteq \[i,j\] \text{ and } L(\text{parent}(n)) \not\subseteq \[i,j\]\\},$$

where $L(n)$ is the set of leaves that are descendants of $n$. I will show first that deleting $S$ has the desired effect, and second that that $|S| \le 2d$, from which it will follow that the range-deletion can be done in $O(\lg d)$ time.

**Lemma 1.** Deleting $S$ will have the effect of deleting leaves $i,i+1,\dots,j-1,j$ but not any of the other leaves.

*Proof.* Consider any leaf $\ell$ with $i \le \ell \le j$. Then $\ell$ is a descendant of some $n \in S$: if $\ell \notin S$, then some ancestor of $S$ must be in $S$ (imaging walking up from $\ell$ along the path towards the root; consider the last ancestor $n$ of $S$ such that $L(n) \subseteq \[i,j\]$; since $L(\ell) =\\{\ell\\} \subseteq \[i,j\]$, such an ancestor must exist). Conversely, a leaf $\ell$ is deleted only if it is a descendant of some $n \in S$; but by construction, $L(n) \subseteq \[i,j\]$ and $\ell \in L(n)$, so it follows that if leaf $\ell$ is deleted, $\ell \in \[i,j\]$.

Now let's show that $|S| \le 2d$. Let $P(\ell)$ denote the set of nodes along the path from $\ell$ to the root. Let $Q(\ell)$ denote the set of siblings of the nodes in $P(\ell)$ ($\ell$'s sibling, $\ell$'s parent's sibling, $\ell$'s parent's parent's sibling, and so on). Then I claim:

**Lemma 2.** $|Q(\ell)| \le d$ for all $\ell$.

*Proof.* Since the tree has height $d$, $|P(\ell)| \le d$. Now $|Q(\ell)| \le |P(\ell)| \le d$.

**Lemma 3.** $S \subseteq Q(i) \cup Q(j)$.

*Proof.* Suppose $n \in S$, so that $L(n) \subseteq \[i,j\]$ but $L(\text{parent}(n)) \not\subseteq \[i,j\]$. Let $m$ be $n$'s sibling. Note that $L(\text{parent}(n)) = L(n) \cup L(m)$. It follows that we must have $L(m) \not\subseteq \[i,j\]$ (otherwise $L(\text{parent}(n)) \subseteq \[i,j\]$ and $n$ wouldn't be in $S$). Also $L(n) \cap L(m) = \emptyset$ and $L(n)$ and $L(m)$ are adjacent intervals ($L(n) \cup L(m)$ is itself an interval; there is no gap in between $L(n)$ and $L(m)$). It follows that either $i \in L(m)$ or $j \in L(m)$, i.e., $m$ must be an ancestor of either $i$ or $j$, i.e., either $m \in Q(i)$ or $m \in Q(j)$.

**Lemma 4.** $|S| \le 2d$.

*Proof.* Follows from Lemma 2, Lemma 3, and the union bound.

---

Caveat: I haven't checked whether rebalancing can also be done in $O(d)$ time. For instance, for a balanced binary tree like an AVL tree or a red-black tree, we have $d=O(\lg n)$, and it would be nice if we could delete the entire range in $O(\lg n)$ time. However, it's not clear whether this is possible. While we can indeed delete the nodes in $S$ in $O(\lg n)$ time, I haven't checked whether it's possible to do all necessary subsequent rebalancing operations in $O(\lg n)$ time. Rebalancing is certainly doable in $O((\lg n)^2)$ time, but I don't know whether it can be done in $O(\lg n)$ time.

---
Tags: data-structures, binary-trees, intervals
---


# Question
Title: Differentiating between BubbleSort and InsertionSort
This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this.

The problem is this:
You have two unknown sorting algorithms, one is Bubble Sort, the other Insertion Sort.
Identify which is which given that you can only differentiate them via differences in asymptotic time for different data sets. (Meaning no run time cross comparison between the two sorts, as our professor may add constant time costs making Insertion Sort slower).

Edit: To clarify, we can specify any array of length n, with a particular sequence if you wish, to see the time it took to sort.
However, you may not compare times between the two sorts. E.g. This sort is faster, therefore this is Insertion Sort.

My findings:

```
            Insertion Sort | Bubble Sort
Best case:            O(n) | O(n)
Worst case:         O(n^2) | O(n^2)
Average case:       O(n^2) | O(n^2)
Stable:                Yes | Yes
In-place:              Yes | Yes
Nearly Sorted:        O(n) | O(n)
Reversed:           O(n^2) | O(n^2)
Few Unique: closer to O(n) | closer to O(n^2) // not sure

```

Given how similar the two sorts are, it's really hard to distinct them...

# Answer
> 3 votes
Unfortunately, your problem statement is contradictory, so the problem cannot be solved in its current form. Your question states that we can obtain the running time for finite values of $n$. However, it also states that we only learn the asymptotic running time. This is self-contradictory, because it is not possible to infer the asymptotic running time based on any finite number of measurements.

If I had to speculate, I'd guess that maybe what the instructor actually wants you to do is find an infinite sequence of inputs $a\_1,a\_2,a\_3,\dots$ such that: (1) $a\_i$ is an array of length $i$; (2) the asymptotic running time of Insertion Sort on these inputs differs by more than a constant factor from the asymptotic running time of Bubble Sort on these inputs. If that's correct, your next step should be to investigate various ways you might construct such a sequence. I emphasize that this is only speculation, and not something that can be definitively derived from the problem statement as provided.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, sorting, experimental-analysis
---


# Question
Title: Is there a known, fast algorithm for counting all subsets that sum to below a certain number?
I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call *subset below-sum*:

* Given a set of integers, $S$, and a target number, $n$, what is the number of subsets of $S$ that sum to **less than** $n$?

For example, if $S$ is $\\{1, 2, 3, 7, 7, 15\\}$, and $n$ is $20$, the answer is $38$.

Is this an NP-Complete problem? If not, what is a fast algorithm to compute the answer?

# Answer
> 2 votes
Subset below-sum appears to be NP-Hard. This is informal, but consider, if you can solve subset below-sum in polynomial time, you can solve subset sum in polynomial time.

* Given: does any subset of $S$ sum to exactly $n$?
* Let $A$ be $subset\\\_below\\\_sum(n)$ and $B$ be $subset\\\_below\\\_sum(n + 1)$. If $B - A \gt 0$, the answer is yes, otherwise, the answer is no.

# Answer
> 1 votes
The similar problem #Subset-Sum, in which we want to count the number of subsets summing to some target, is #P-complete (this is implied by this paper). This hints that your problem, which is clearly in #P, might also be #P-complete.

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


# Question
Title: Count the number of Euler PATHs in directed graph?
* **I would like to find all Euler PATHs in a directed graph.**
* **Counting (instead of finding) all the Euler PATHs is sufficient.**
* **Circuits are not good for me, only Paths.**

I am doing a problem, that I have derived to a point, where knowing the number of paths fast would help. Currently, I have written (in c++) a recursive function that finds all of them, but it complexity grows quickly, so my algorithm gets slow fast. My algorithm is ~O(2^n). I would like a faster one for counting, if possible.

I have researched the topic, but I can only find proofs (for being NP complete, or polynomial) and algorithms for Euler Circuits in directed and undirected graphs. But again, I am looking for Euler Paths in directed graphs.

My graphs have only two nodes, but a lot of edges, that should be touched only once, like in an Euler Path.

So in summary:

1. Euler **Path**.
2. **Directed** Graph.
3. Only two nodes.
4. High edge count.
5. Edge costs are the same.

Here is an image to illustrate a possible set up.

# Answer
You can actually come up with a formula for this. Let $\ell\_0,\ell\_1$ be the number of self-loops at $0,1$, and let $e\_{01},e\_{10}$ be the edges from $0$ to $1$ and in the other direction. We must have $|e\_{01}-e\_{10}| \leq 1$. If $e\_{01} = e\_{10}+1$ then the path must start at $0$; if $e\_{10} = e\_{01}+1$ then it must start at $1$; if $e\_{01} = e\_{10}$ then both are possible. We will count paths starting at $0$.

Given an Eulerian path starting at $0$, we can write it as $$ L\_0 E\_1 L\_1 E\_2 \cdots E\_m L\_m, $$ where $L\_0,L\_2,\ldots$ are collections of self-loops at $0$, $L\_1,L\_3,\ldots$ are collections of self-loops at $1$, $E\_1,E\_3,\ldots$ are $0\to 1$ edges, and $E\_2,E\_4,\ldots$ are $1\to 0$ edges. We can decompose this path into three components: $$ E\_1 E\_2 \ldots E\_m \\ L\_0 L\_2 \ldots \\ L\_1 L\_3 \ldots $$ We can choose the first component in $e\_{01}! e\_{10}!$ ways, the second component in $\ell\_0!$ ways, and the third component is $\ell\_1!$ ways. It remains to choose a way of partitioning the latter two strings into their components. In order to count this, assume that $m$ is even (the case $m$ odd is very similar) and divide the original path differently: $$ L\_0 E\_1 L\_2 E\_3 L\_4 \ldots E\_{m-1} L\_m \\ L\_1 E\_2 L\_3 E\_4 L\_5 \ldots E\_{m-2} L\_{m-1} E\_m $$ The first line contains $m/2$ "breakpoints" out of $\ell\_0 + m/2$ symbols in total, so the number of ways of breaking $L\_0L\_2\ldots L\_m$ into its $m/2+1$ parts is $\binom{\ell\_0+m/2}{m/2}$. The computation is similar for the second line, once we remove the $E\_m$ which must appear at the end; we get $\binom{\ell\_1+m/2-1}{m/2-1}$.

I'll leave you the task of bringing everything together to one formula.
> 1 votes

---
Tags: algorithms, graphs, counting, eulerian-paths
---


title: Why does λz.zq reduce to q?

text:
# Question
Title: Why does λz.zq reduce to q?
The way I see it, it should not be further reducible. I'm thinking `λz.zq` is like

```
lambda z: z(q) # Python, not lambda calc

```

and you do not know z nor q so it is not further reducible.

The below derivation (where I am wondering about the last steps) is from the new Haskell book:

# Answer
> 3 votes
It is $\beta$-reduction defined in terms of substitution (rename ($\alpha$-conversion) first if necessary):

$$(\lambda z. zq) (q) \to\_{\beta} \[z/q\](zq) = qq. $$

---

In Haskell, $\lambda z.zq$ defines an anonymous function which takes a single parameter (represented by $z$) and performes $zq$.

---
Tags: lambda-calculus
---


# Question
Title: How exactly does a Max 2 Sat reduce to a 3 Sat?
I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard.
However, if you see the article, I'm *not able to understand why*, after `ci` is satisfied, 7 out of 10 clauses are satisfied and if it is not satisfied, the 6 out of 10 clauses are satisfied.
Can someone explain to me in simple terms, and demystify what exactly the article wants to convey? Essentially, I have come to know that a max-2-sat problem is the same as a 3 sat problem. The question is I'm not able to understand why.
More formally, I wish to solve this problem:

> Consider the problem MAX2SAT described as follows.
> Given a 2-CNF (Conjunctive Normal Form) Boolean expression (with m clauses, n variables) and an integer k, Decide if there is an assignment satisfying at least ‘k’ of the total clauses? Compute the complexity class (P or NP or NP Complete) of the MAX2SAT with justification.

# Answer
It seems that the lecture note has abused the symbol $c\_i$. You should check the original paper.

---

Replacing each clause $C\_i = (a\_i \lor b\_i \lor c\_i)$ of 3CNF by the collection of 2CNF clauses:

$$(a\_i), (b\_i), (c\_i), (d\_i), (\bar{a\_i} \lor \bar{b\_i}), (\bar{a\_i} \lor \bar{c\_i}), (\bar{b\_i} \lor \bar{c\_i}), (a\_i \lor \bar{d\_i}), (b\_i \lor \bar{d\_i}), (c\_i \lor \bar{d\_i})$$

where $d\_i$ is a new variable.

---

> Theorem: If an assignment $\alpha$ satisfies $C\_i$, then exactly seven of the ten clauses in the 2-CNF collection can be satisfied.

***Proof:*** $\alpha$ satisfies $C\_i$, then either one, two, or three of $a\_i, b\_i, c\_i$ must be `true`. In all cases, there is a truth setting for $d\_i$ causing exactly seven of the clauses to be satisfied. For example, suppose $a\_i = \top, b\_i = c\_i = \bot$, then $d\_i = \bot$ causes 7 clauses to be satisfied.

> Theorem: If an assignment $\alpha$ does not satisfy $C\_i$, then exactly six of the ten clauses can be satisfied.

***Proof:*** $\alpha$ does not satisfy $C\_i$, then $a\_i = b\_i = c\_i = \bot$. In this case, if $d\_i = \top$, 4 clauses are satisfied; if $d\_i = \bot$, then 6 clauses are satisfied.
> 3 votes

---
Tags: complexity-theory, reductions, np-hard, satisfiability, decision-problem
---


title: A program for polytime languages

text:
# Question
Title: A program for polytime languages
Does their exist a program P\[m,s\] which always halts and for any polytime language exists an m; possibly incomputable; such that P\[m,s\] accepts only those strings s which are in the language.

# Answer
> 1 votes
Hint: Let $m$ code both a Turing machine for the language and a polynomial time bound on its running time.

---
Tags: computability, polynomial-time, enumeration
---


# Question
Title: Changing from Kernel mode to User mode (and vice versa)
I am reading Operating Systems book by Galvin. Galvin explains, what are kernel & user modes, instruction privileges given for both modes & also about mode-bit. But I am interested to know how mode changes from one to another. Basically I want to solve following question :

> A CPU has 2 modes, privileged and non-privileged. In order to change the mode from previledged to non-previledged
>
> a) A hardware interrupt is needed
>
> b) A software interrupt is needed.
>
> c) A privileged instruction is needed.
>
> d) A non-privileged instruction is need.

From what I understand,

from user mode to kernel mode - Hardware Interrupt is needed \[like in Disk I/O\]. Now, in case user program tires to access an memory which is beyond its permissible range, a trap occurs, which is basically a software interrupt which will be handled by OS. Now, in user mode we cannot execute any privileged instructions. So, a non-privileged instruction such as I/O request can change user to kernel mode. So I think, to change

> from non-privileged(user) to privileged(kernel) - H/W Interrupt, S/W Interrupt & non-Privileged instruction will do.

Now coming to, kernel to user mode. The OS can change kernel to user mode. So, it will simply run a privileged instruction to change from kernel to user mode. It does not need to generate either H/w or S/w interrupt. So I conclude, to change

> from previledged to non-previledged - a privileged instruction will do.

Am I right ?

Also when executing in kernel mode, all interrupts will be disabled right ? So answer cannot be (a) or (b). Also, since OS is basically a software, it cannot generate H/W interrupts.

Also, since OS itself handles interrupts, it does not make sense to me why has to generate a interrupt (& service it) to change from kernel to user mode.

Please let me know if I am wrong anywhere. Any help regarding this is appreciated.

# Answer
> 8 votes
**Usermode to kernelmode:** Wrong! ;-) Yes, interrupts are processed in kernel mode, and originally the way to enter kernel mode was by an interrupt forced somehow by software. On the DEC 2020 there was a set of UIOs (Unimplemented Instruction Opcodes), calling any of those caused a trap to the operating system. They included floating point instructions (if not in hardware) and other exotic instructions, but also the means to do operating system calls. The i?86 family has the `int` (interrupt) instruction, traditionally used as you say. Newer members of the family have SYSTENT to do supervisor calls more efficiently. The means of going to supervisor mode can't be privileged, but must somehow be tightly controlled by the kernel (where you enter the kernel, what arguments you pass, ...).

**Kernelmode to usermode:** No need for the "drop privileges" operation to be privileged. If you don't have privileges, dropping them is a no-op. But the exact mechanism is architecture dependent in extreme.

**Interrupts disabled in kernel:** Interrupts indicate some condition that has to be handled as soon as possible (for example, if the data arrived over the net isn't saved from the card before the next arrives, it will get overwritten). Thus interrupts are very rarely disabled. In original Unix systems (and contemporaries), there was one CPU, and the simplest way to get a critical region ("nobody mess with my data while I modify it") was just to disable interrupts. Pains were taken to keep the "interrupt disabled" stretches as short as possible because of the above. On current multi-CPU machines, disabling interrupts on one CPU does nothing much in this direction; disabling interrupts globally is *extremeñy* costly in inter-CPU coordination, so it is not done (or extremely rarely).

# Answer
> 0 votes
From kernel(privileged) to user(unprivileged) mode , we use RtI(return from interrupt) , which is a privileged instruction (https://www-01.ibm.com/support/knowledgecenter/ssw\_aix\_71/com.ibm.aix.alangref/idalangref\_rfi\_retfinter\_instrs.htm). so , according to me it should be option C.

---
Tags: computer-architecture, operating-systems, memory-management, memory-access
---