# Question
Title: What is the time complexity of this аlgorithm? O(n * r)
> Given function `rand7` returns random integer in interval `[0, 6]`. Your task is to implement function `rand5` which should return random integer in interval `[0, 4]` using function `rand7`.

This is a question from my book. So, this is how I solved it (the algorithm is written in C):

```
int rand5(void){
  return (int)(rand7() * 4. / 6. + .5);
}

```

Basically, I just scaled the interval to `[0, 4]`. The `+ .5` part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.

Solution in my book is very weird to me. This is how they did it:

```
int rand5(void){
  int a;
  while((a = rand7()) > 4);
  return a;
}

```

The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.

Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is `O(r)` where `r` is time complexity of `rand7`. But what is the complexity of their algorithm?

The complexity should be `O(r * n)` where `n` is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function `rand7` and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is `O(infinity)` which doesn't make any sense.

Of course, if `rand7` if properly implemented, it will for sure return at lest one time number in interval `[0, 4]`. But, theoretically, it can return any number of consecutive numbers which belong in interval `[5, 6]`. Is then complexity indeterminate?

Also, how is that possible that *"there is no other solution"*? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval `[0, k]` for given number `k` using only `rand2` (for example), such that the algorithm should work in finite time complexity?

# Edit

Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?

# Answer
Investigating worst-case cost is rarely useful for randomized algorithms. Here, the worst case is indeed that the loop never stops -- but this event has probability zero!

Instead, perform *average*-case analysis. What is the probability of the loop running $k$ times?

> That means it misses the interval $k-1$ times, and then hits it. Assuming that `rand7` has indeed uniform distribution, the probability of the former is $\frac{2}{7}$, and of the latter $\frac{5}{7}$. The result is, assuming that separate calls of `rand7` are stochastically independent, $\bigl(\frac{2}{7}\bigr)^{k-1} \cdot \frac{5}{7}$.

Now you compute the *expected* number of iterations using basic facts from stochastics.

> The above weights are those of a *geometric* distribution. Looking up its properties, we learn that its expected value is $\frac{7}{5}$.

As it turns out, this is not too bad. You can also investigate the standard deviation or compute some probabilities to get a feeling for how unlikely high iteration counts are.
> 3 votes

# Answer
# Regarding complexity of `rand5`

## Hand waving and reasonable assumptions

The procedure (it is not a function in the mathematical sense) `rand7` has no arguments to depend on. Therefore, the only thing it can depend on is global state. Since `rand7` is a black box (we don't know its implementation), we can only make a reasonable assumption that the complexity is a constant `k7`.

Therefore, since the complexity function of `rand5` is `T = k5 * k7`, and `T \in O(1)`.

If we know more about `rand7`, we can do a deeper analysis through solving a recursive cost function where the implicit state becomes an explicit parameter to the algorithm.

## Strict analysis

If we are to strictly adhere to the definitions of asymptotic complexity (Big-O), a black box can possibly never terminate. If it never terminates, which is the worst case, the complexity of the procedure is undefined.

> The Big-O complexity of a genuinely infinite loop is undefined.

See: https://stackoverflow.com/a/14309914/1063961 for more information.

## Empirical analysis

We can not statically analyze the complexity of a black box. But we can do it via empirical analysis. For more details on how accomplish this, see the paper "Automatic Grading of Programming Exercises using Property-Based Testing".
> 1 votes

# Answer
Regarding the distribution:

you solution takes 1 output from rand7 and then maps it to \[1, 5\],

```
If it outputs 0 then you output 0
If it outputs 1 then you output 1
If it outputs 2 then you output 1
If it outputs 3 then you output 2
If it outputs 4 then you output 3
If it outputs 5 then you output 3
If it outputs 6 then you output 4

```

This means that you are twice as likely to get 1 or 3 than a 0, 2 or 4.

The solution is to drop the 5 and 6 output and repeat the sample until you get one that is within the output range.

In the other direction (creating a rand7() from a rand5()) you will need to combine 2 samples to create a rand25 by doing `sample1*5 + sample2` and then extract out a rand21() using the same method above and dividing by 3.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, randomness
---


# Question
Title: Converting if-then-else condition to integer linear programming with equality constraints
I have an if-then-else condition with three binary variables $A$, $B$ and $C$:

```
if A = 1
       then B = 1
else
       B = C

```

How do I express this as an integer linear program with equality constraints?

# Answer
We have three binary variables $x, y, z \in \\{0,1\\}$ and the following if-then-else (ITE) condition

$$\text{if } x = 1 \text{ then } y = 1 \text{ else } y = z$$

If $x = 1$, then $y = 1$ but $z \in \\{0,1\\}$. If $x = 0$, then $y = z \in \\{0,1\\}$. Therefore, we have the following $4$ vertices of the $3$-cube

$$\\{ (0,0,0), (0,1,1), (1,1,0), (1,1,1) \\}$$

Using SymPy, we obtain the following **product of sums** (POS):

```
>>> from sympy import *
>>> x, y, z = symbols('x y z')
>>> minterms = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]]
>>> POSform([x, y, z], minterms, [])
And(Or(Not(x), y), Or(Not(y), x, z), Or(Not(z), y))

```

Converting the formula in POS, i.e., in conjunctive normal form (CNF), to integer programming, we obtain the following system of linear inequalities

$$\begin{array}{rl} (1-x) + y &\geq 1\\ x + (1-y) + z &\geq 1\\ y + (1-z) &\geq 1\end{array}$$

which can be rewritten as follows

$$\begin{array}{rl} -x + y &\geq 0\\ x - y + z &\geq 0\\ y -z &\geq 0\end{array}$$

Verifying in Haskell:

```
λ> triples = [ (x,y,z) | x <- [0,1], y <- [0,1], z <- [0,1] ]
λ> filter (\(x,y,z)->(-x+y>=0) && (x-y+z>=0) && (y-z>=0)) triples
[(0,0,0),(0,1,1),(1,1,0),(1,1,1)]

```
> 3 votes

---
Tags: linear-programming, integer-programming
---


title: Eliminating cycles from a grammar

text:
# Question
Title: Eliminating cycles from a grammar
I have the following grammar:

```
S -> Xb | Y

Y -> X | a

X -> S | c

```

Here the lowercase letters are terminals.

I have an algorithm to find the cycle in this grammar. It is `S->Y->X->S` and in fact there is a smaller cycle buried in there, namely `S->X->S`.

I've tried to devise an algorithm to remove these cycles, without too much thought, but I've come up with nothing.

Any help would be appreciated.

# Answer
An algorithm to specifically remove cycles can be adapted from the more general algorithm to reduce a grammar to its Chomsky normal form. Specifically, it is the elimination of unit productions, usually abbreviated as UNIT, which is responsible for breaking cycles. Really what follows is a explanation (in fact two, the second being more refined) of how UNIT works, as far as I understand it. The best thing to do is probably to work through the example I gave in the question.

For the `S` production I have:

```
S -> Xb | Y

   = Xb | X | a   [replace Y with X | a]

   = Xb | a | c   [replace X with c]

```

Note that `X` is replaced with just `c` and not its full right hand side `S | c`, presumably to avoid introducing the cyclic unit production `S->S`. Note also that the `X` is effectively moved to the end during the process of eliminating it (I am unable to work out why this should be the case and would love it if someone could tell me).

For the `Y` production I have:

```
Y -> X | a

   = a | S | c   [replace X with S | c]

   = a | c | Xb  [replace S with Xb]

```

Note again that the unit productions are effectively moved to the end during the process of elimination. And again note that `S` is replaced with `Xb` and not `Xb | Y`, presumably for the aforementioned reason of not introducing the cyclic unit production `Y->Y`.

For the `X` production I have:

```
X -> S | c

   = c | Xb   [replace S with Xb]

```

Note here that `S` is replaced with `Xb` rather than `Xb | Y`. The reason for this is that the production `S->Y` has already been used up, so to speak, and therefore should not be introduced again.

This last step, although it now seems to make sense, confused me at first. In what follows the same algorithm is refined further in order to highlight these kinds of steps. It is also closer to a real implementation. I'll work on a different grammar, this one:

```
S -> Xb | Y

Y -> X | a

X -> Z | d

Z -> Y | c

```

I start by dividing up the grammar into non-unit and unit productions:

```
*******
S -> Xb
Y -> a
X -> d
Z -> c
*******

S -> Y
Y -> X
X -> Z
Z -> Y

```

I keep the list of non-unit productions fixed, and work on the stack of unit productions. As I create new unit productions, I add them to the *top* of the stack, effectively replacing the old ones. However, I keep the old ones, they remain above the dashed line (ideally I wish I could cross them out), so I have a record of unit productions that I must not re-introduce. At the same time, as I create new non-unit productions, I put them to one side in a new list and do not pollute the original list. I'll write the stack and list next to each other.

So, I eliminate `S->Y`, adding a new non-unit production `S->a` and a new unit production `S->X`, which I get from applying the unit production `Y->X` that can be found lower down in the stack to the right hand side of `S->Y`:

1

```
  S -> Y    S -> a   [from Y->a in the list of non-unit productions]
  ------
  S -> X             [from applying Y->X from further down the stack]
  Y -> X
  X -> Z
  Z -> Y

```

I'll continue with the process only adding qualifications occasionally when new points crop up...

2

```
  S -> Y    S -> a
  S -> X    S -> d
  ------
  S -> Z
  Y -> X
  X -> Z
  Z -> Y

```

3

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c   [no more to do, S->Y has been eliminated already]
  ------
  Y -> X
  X -> Z
  Z -> Y

```

4

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  ------
  Y -> Z
  X -> Z
  Z -> Y

```

5

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  ------
  X -> Z
  Z -> Y

```

6

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  ------
  X -> Y
  Z -> Y

```

7

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  ------
  Z -> Y

```

7

```
  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  Z -> Y    Z -> a
  ------

```

I hope these steps are clear. Finally, collating we get:

```
S -> Xb | a | d | c

Y -> a | d | c

X -> d | c | a

Z -> c | a

```

The astute may notice that the cycle is in fact `X->Z->Y->X`, `S` plays no part. It is possible to detect cycles, or more correctly strongly connected components, as a preliminary step, and then apply UNIT only to these components, which would no doubt make for a more efficient algorithm.
> 4 votes

# Answer
There are known algorithms to convert context-free grammars to Chomsky normal form. Grammars in Chomsky normal form don't contain cycles, and indeed one of the steps is removing cycles. One such algorithm is described in Wikipedia.

Some people have graciously implemented one of these algorithms online, for example Matthew Peveler. Running his tool on your grammar, we get the following result (try!):

$$ \begin{align\*} &S \to XA \mid a \mid c \\ &Y \to a \mid c \mid XA \\ &X \to c \mid XA \\ &A \to b \end{align\*} $$ Undoing one step, we get a simpler grammar, which might be what you're looking for: $$ \begin{align\*} &S \to Xb \mid a \mid c \\ &Y \to a \mid c \mid Xb \\ &X \to c \mid Xb \\ \end{align\*} $$ The online tool is provided with source code which you can examine, though textual descriptions (available in Wikipedia and elsewhere) will probably be easier to follow.
> 3 votes

# Answer
Starting with

```
S -> Xb | Y

Y -> X | a

X -> S | c

```

I would rewrite it as

Step 1: get rid of Y

```
S -> Xb | X | a
X -> S | c

```

Step 2: get rid of X

```
S -> Sb | cb | c | a

```

You get a grammar with the immediate left recursion which can be eliminated further if you need to.

But if you need a systematic way to eliminate cycles, then you need to use algorithms that transform a CFG to normal form.
> 3 votes

# Answer
You can treat productions as equations, and solve them accordingly.

Taking up where @fade2black left off, we have

$$\begin{align} S &= Sb | cb | c | a\\ &= Sb | (cb|c|a) \end{align}$$

The solution to

$$X = X \alpha | \beta$$

is

$$ X = \beta \alpha^\*$$

So

$$\begin{align} S &= (cb|c|a)b^\* \end{align}$$
> 1 votes

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Recurrence relations that do not have a closed form solution
A recurrence relation computes value $d\_n$ with the $\\{d\_{i},d\_{j}\ldots\\}$ previous digits of the sequence

So for example, the Fibonacci sequence is defined as follows: $$ F\_n = F\_{n-1}+F\_{n-2},\ \ \ F\_0=0, F\_1=1 $$ The classic closed form solution is given by the Binet formula: $$ F\_n = \frac{\phi^n-\psi^n}{\sqrt{5}} $$ where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=1-\phi$.

The question is: are there such sequence of digits defined through some arbitrary recurrence relation that do not have a closed form solution, that is, that provably do not have a closed form solution?

I am asking this question in CS stack exchange because the context of this question is Random Number Generation... If such iterated sequences exist, this could be (could be) helpful in designing RNG's...

# Answer
Yes, there are. Consider the recurrence $a\_{n+1}=(7a\_n/4 + 1/2) - (5a\_n/4 + 1/2)(-1)^{a\_n}$ where $a\_0$ is a given integer value. It is well known that this gives the Collatz sequence. There is no "known" closed form solution to the recurrence (and if you find it, you would be quite famous in mathematical circles). Furthermore, it is also well known that there are recurrent sequences that can't be solved in closed form. For instance, Conway shows that a natural generalization of the Collatz problem is undecidable. On the other hand, there are large classes of recurrence relations for which methods are known to determine closed form solutions in terms of sometimes multiple finite or infinite sums. Hypergeometric functions can be used to solve large classes of them. For instance, in theory, all linear recurrences with polynomial coefficients can be solved. More information can be found in *Solving Linear Recurrence Equations with Polynomial Coefficients* by Petkovsek and Zakrajsek (PDF).
> 6 votes

# Answer
Assuming you are asking about *linear* recurrence relations, roughly speaking, the answer is "No, but that's OK".

More precisely: If the sequence can be defined by a linear recurrence relation with finite memory, then there is a closed form solution for it... but this is not a barrier to building useful PRNGs.

Suppose there is a linear recurrence relation, say

$$a\_j = c\_1 a\_{j-1} + c\_2 a\_{j-2} + \dots + c\_k a\_{j-k} + d \text{ for $j\ge k$.}$$

Form the corresponding generating function, $A(z) = a\_0 + a\_1 z + a\_2 z^2 + \dots$. From the recurrence relation we can find a simple relationship on the generating function and then solve for $A(z)$ to find

$$A(z) = {p(z) \over q(z)},$$

for some polynomials $p(z),q(z)$ of degree at most $k$. This gives us a closed form expression for $A(z)$, and now we can say that $a\_j$ is the coefficient of $z^j$ of $A(z)$. I don't know if you want to count that as a closed form solution or not.

If you don't, let $\alpha\_1,\dots,\alpha\_k$ be the complex roots of $q(z)$. This typically lets us express $a\_j$ as a linear function of powers of $\alpha\_1,\dots,\alpha\_k$. In other words, this gives us a closed-form expression for the recurrence.

For details on how to do this, see our reference question Solving or approximating recurrence relations for sequences of numbers, and especially the exposition on generating functions (https://cs.stackexchange.com/a/3135/755).

---

Such recurrences are not a good way to build a RNG. There is a rich literature on RNGs and PRNGs. RNGs need to generate truly random numbers (not pseudorandom numbers); to paraphrase Knuth, "anyone who uses \[deterministic algorithms\] to produce random numbers is in a state of sin". Therefore, different techniques are used when building a RNG.

You might be asking about PRNGs, which are for generating pseudorandom numbers. Recurrence relations can be useful for building PRNGs. For instance, I suggest you study LFSRs and linear congruential generators, two kinds of PRNGs that take the form of a recurrence relation. However, the fact that there is (or isn't) a closed-form expression for the output isn't a make-or-break consideration; those generators are useful for some purposes despite the existence of a closed-form solution.
> 2 votes

---
Tags: recurrence-relation, random-number-generator
---


# Question
Title: SAT formula and satisfying assignment yield another different satisfying assignment
Given P=!NP

Is there a polynomial time TM such that for an input of formula and a satisfying assignment will yield a different satisfying assignmentif such exist?

# Answer
> 3 votes
Your problem is NP-complete. Let's call it NextSAT$(F,\tau)$: accept iff $\tau$ is a satisfying assignment of $F$ and there exists a satisfying assignment of $F$ different from $\tau$.

NextSAT is clearly in NP. We now show that SAT $\leq$ NextSAT.

Let $F$ be a CNF on variables $X = \\{x\_1,\ldots,x\_n\\}$. If $F$ is the empty CNF, it is obviously satisfiable and we can thus pick any satisfiable instance of NextSAT for the reduction.

Assume now that $F$ has at least one clause. Choose $\tau : X \rightarrow \\{0,1\\}$ that does not satisfy $F$. It is easy to find by simply choosing a clause of $F$ and negating all its literals. Let $$G = F \lor (\bigwedge\_{i \leq n} \ell\_i) = \bigwedge\_{C \in F} \bigwedge\_{i \leq n} C \lor \ell\_i$$ where $\ell\_i = x\_i$ if $\tau(x\_i) = 1$ and $\ell\_i = \neg x\_i$ otherwise. We see that $G$ can be written as a CNF of size polynomial in the size of $F$.

Now, clearly, the satisfying assignments of $G$ is the disjoint union of the satisfying assignments of $F$ and $\tau$ since $\tau$ is the only satisfying assignment of $\bigwedge\_{i\leq n} \ell\_i$ and does not satisfy $F$. Thus, $F$ is satisfiable if and only if there exists a satisfying assignment of $G$ different from $\tau$. That is, if and only if NextSAT$(G,\tau)$ returns $1$.

---
Tags: complexity-theory
---


# Question
Title: How to check if two strings are permutations of each other using O(1) additional space?
Given two strings how can you check if they are a permutation of each other using O(1) space? Modifying the strings is not allowed in any way.
Note: O(1) space in relation to both the string length AND the size of the alphabet.

# Answer
> 7 votes
The naive approach would be building histograms of both strings and checking whether they are the same. Since we are not allowed to store such a data structure (whose size would be linear to the size of the alphabet) that could be computed in one pass, we need to count the occurences of each possible symbol after the other:

```
function count(letter, string)
    var count := 0
    foreach element in string
        if letter = element
            count++
    return count

function samePermutation(stringA, stringB)
    foreach s in alphabet
        if count(s, stringA) != count(s, stringB)
            return false
    return true

```

This does of course assume that the counts and iterator indices are integers of constant size, instead of being dependent on the length of the strings.

# Answer
> 12 votes
Denote the arrays by $A,B$, and suppose they are of length $n$.

Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:

1. Compute the minimum values of both arrays, and check that they are identical.
2. Compute the second minimum values of both arrays, and check that they are identical.
3. And so on.

Computing the minimum value of an array clearly uses $O(1)$ space. Given the $k$th smallest element, we can find the $(k+1)$st smallest element by finding the minimal value larger than the $k$th smallest element (here we use the fact that all elements are distinct).

When elements are allowed to repeat, we modify the algorithm as follows:

1. Compute the minimum values $m\_{A,1},m\_{B,1}$ of both arrays, count how many times each appear, and verify the $m\_{A,1} = m\_{B,1}$ and that the counts are identical.
2. Compute the minimum values $m\_{A,2},m\_{B,2}$ larger than $m\_{A,1},m\_{B,1}$ in the two arrays (respectively), and count how many times each appear. Verify that $m\_{A,2} = m\_{B,2}$, and that the counts are identical.
3. And so on.

# Answer
> 2 votes
Define some function f(c) which maps some character c to a unique prime number (a = 2, b = 3, c = 5, etc).

```
set checksum = 1
set count = 0 <-- this is probably not even necessary, but it's another level of check
for character c in string 1
    checksum = checksum * f(c)
    count = count + 1
for character c in string 2
    checksum = checksum / f(c)
    count = count = 1

permutation = count == 0 and checksum == 1

```

Just declaring that you can use a prime number mapping function is a bit handwavey, and most likely where a problem would arise keeping $\textit{O}\textbf{(1)}$ space.

# Answer
> 0 votes
You can do this is `O(nlogn)`. Sort the two strings, and compare them index by index. If they differ anywhere, they're not permutations of each other.

For an `O(n)` solution, hashing could be used. This hashing function would work, and `e` for any letter would be its ascii value. If the two hashes of the strings differ, they're not permutations of each other.

The hashing function in the link:

> One potential candidate might be this. Fix a odd integer R. For each element e you want to hash compute the factor (R + 2\*e). Then compute the product of all these factors. Finally divide the product by 2 to get the hash.
>
> The factor 2 in (R + 2e) guarantees that all factors are odd, hence avoiding that the product will ever become 0. The division by 2 at the end is because the product will always be odd, hence the division just removes a constant bit.
>
> E.g. I choose R = 1779033703. This is an arbitrary choice, doing some experiments should show if a given R is good or bad. Assume your values are \[1, 10, 3, 18\]. The product (computed using 32-bit ints) is
>
> (R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 Hence the hash would be
>
> 3376724311/2 = 1688362155.

Using double hashing (or for overkill even more) by changing the value of R would successfully identify them as permutations with **very high** probability.

# Answer
> 0 votes
Let's say you have two strings called s and t.

You could use heuristics to make sure that they are not unequal.

1. s.length == t.length
2. sum of chars of s == sum of chars in t
3. \[the same as in 2. but with xor instead of sum\]

After this you can easily run an algorithm to prove that the string are equal.

1. sort one string to be equal to the other and compare (O(n^2))
2. sort both and compare (O(2n log(n))
3. check for each char in s if there are the same amounts in both strings (O(n^2))

Of course you can't sort that fast if you are not allowed to use additional space. So it does not matter which algorithm you choose - each algorithm will need will run in O(n^2) time when there is only O(1) space and if the heuristic was unable to prove that they can't be equal.

# Answer
> 0 votes
In C-style code for the whole routine:

```
for (int i = 0; i < n; i++) {
   int k = -1;
   next: for (int j = 0; j <= i; j++)
       if (A[j] == A[i]) {
          while (++k < n)
              if (B[k] == A[i])
                  continue next;
          return false; // note at this point j == i
       }
}
return true;

```

Or in very verbose pseudo code (using 1-based indexing)

```
// our loop invariant is that B contains a permutation of the letters
// in A[1]..A[i-1]
for i=1..n
   if !checkLetters(A, B, i)
      return false
return true

```

where the function checkLetters(A,B,i) checks that if there are M copies of A\[i\] in A\[1\]..A\[i\], then there are at least M copies of A\[i\] in B:

```
checkLetters(A,B,i)
    k = 0 // scan index into B
    for j=1..i
      if A[j] = A[i]
         k = findNextValue(B, k+1, A[i])
         if k > n
            return false
    return true

```

and function findNextValue searches in B for a value starting from an index, and returns the index where it was found (or n+1 if not found).

The idea here is that we have already validated that we have a permutation of the characters before i in the outer loop. In the j loop, we proceed through all the characters that match A\[i\], and we need to be able to find unique indices in B that match for them (including the i-th position). Thus for each of those, we need to move our scan forward through B. Time is O($n^2$).

# Answer
> 0 votes
I think this is the most simplest algorithm (with $O(n^3$) time, $n$ length of strings)

Loop through `string1` and `string2`, for every character check how often it can be found in `string1` and `string2`. I a character is more often in one string than in the other one, it is not a permutation. If the frequencies of all characters are equal then the strings are permutations of each other.

Here is a piece of python to make this precise

```
s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references string1
    #  string2, it is not a copy
    for char in string:
      count1=0
      for char1 in string1:
        if  char==char1:
          count1+=1
      count2=0
      for char2 in string2:
        if  char==char2:
          count2+=1
      if count1!=count2:
        print('unbalanced character',char)
        return()
  print ("permutations")
  return()

check_if_permutations(s1,s2)

```

The program needs some pointers to strings (`string`, `string1`, `string2`, `char`, `char1`, `char2`) and variables of size $O(\log n)$ for counting (`count1`, `count2`). It needs to check if characters are equal or not but it dows not need any order on these characters. Maybe it needs some variables for small integers (e.g. to hold boolean values or to represent the postition of `string` in `[string1, string2]`.

Of course you don't even need the count variables but can use pointers.

```
s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references one of string1
    # or string2, it is not a copy
    for char in string:
      # p1 and p2 should be views as pointers
      p1=0
      p2=0
      while (p1<len(string1)) and (p2<len(string2)):
        # p1>=len(string1): p1 points to beyond end of string
        while (p1<len(string1)) and (string1[p1]!=char) :
          p1+=1
        while(p2<len(string2)) and (string2[p2]!=char):
          p2+=1
        if (p1<len(string1)) != (p2<len(string2)):
          print('unbalanced character',char)
          return()
        p1+=1
        p2+=1
  print ("permutations")
  return()

check_if_permutations(s1,s2)

```

This second program needs similar variables as the first one except that it does not need the $O(\log(n))$-size variables for holding the count values.

So it actually does not depend of $n$ or the size of the alphabet.

---
Tags: algorithms, strings, space-complexity
---


# Question
Title: Minimal DFA for language of all strings over $\{a,b\}$ whose penultimate symbol is $b$
> Design a minimum state deterministic finite automata for accepting those strings over the alphabet $\\{a, b\\}$ whose last but one symbol is $b$.

# Answer
> 2 votes
Note that we have at least three states:

1. The second last character is $b$ so the tail 2-substring is either $ba$ or $bb$.
2. The last two characters are $ab$ (read at least one more character).
3. The last two characters are $aa$ (read at least two more characters).

which leads to the following DFA:

The above DFA contains minimal number of states if and only if it equals its minimization. Following this page in *DFA Minimization using Equivalence Theorem* we have

$P\_0 = \\{(1, 2), (3)\\}\\ P\_1 = \\{(1), (2), (3)\\}$

In $P\_1$ we used the fact that one single character may lead state 2 to an accepting state, whereas 1 does not "reach that far". Since $P\_1$ gives no opportunity for further refinement, we may stop and we know that the DFA is minimized.

# Answer
> -3 votes
Here second symbol from rhs is b or penultimate symbol is b

---
Tags: automata, finite-automata
---


# Question
Title: algorithm complexity calculation T(n) = 2T(n/2) + n*log(n)
I guess I lack at understanding basic things at algorithm calculations, while learning for an exam.

* at the result, does one write like O(ld n) or just log instead of ld ?
* regarding the following calculation (not from me) at the yellow mark - why is it Theta(n) ? why not O(n) ? I dont get it..

big thanks in advance !

# Answer
> 2 votes
Let's start at the beginning.

Basically, there are 3 very popular notations to express time complexity of algorithms:

* $\Theta(g(n))$,
* $\mathcal{O}(g(n))$ (this is the well-known Big O notation),
* $\Omega(g(n))$.

The first thing that is in most cases a little bit confusing (and misused), that these notations denote sets - **sets of functions**. For example, the interpretation of $\Theta(g(n))$ is as follows:

$$\Theta(g(n)) = \\{ f(n) \\; | \\; \text{There exist } n\_0, c\_1 \text{ and } c\_2 \text{ constants so that } 0 \leq c\_1 \cdot g(n) \leq f(n) \leq c\_2 \cdot g(n) \text{ for all } n \> n\_0. \\}$$

So, $\Theta(g(n))$ is a set of $f(n)$ functions for that $g(n)$ can be used as both an **upper** and a **lower** bound (with the use of the given $c\_1$ and $c\_2$ constants). In other words, if you plot these 3 functions, $f(n)$ is going to be between $c\_1 \cdot g(n)$ and $c\_2 \cdot g(n)$ - at least, for all inputs larger than or equal to $n\_0$. (It's worth taking a look at figures about these in Google so that you can get a better understanding of it.)

*Note*: because of the use of $n\_0$ and all larger inputs than it, these notations are also called **asymptotic** notations.

The interpretation of $\mathcal{O}(g(n))$ and $\Omega(g(n))$ are very similar to the one above, but they only refer to either the upper bound or the lower bound, respectively. (Of course, the existence of only one $c$ constant is enough for these 2 definitions.)

Just in case, see the definition of $\mathcal{O}(g(n))$ below:

$$\mathcal{O}(g(n)) = \\{ f(n) \\; | \\; \text{There exist } n\_0 \text{ and } c \text{ constants so that } 0 \leq f(n) \leq c \cdot g(n) \text{ for all } n \> n\_0. \\}$$

In other words, $g(n)$ is an upper bound for all the functions in the set $\mathcal{O}(g(n))$. For example, let's denote the time complexity of the insertion sort with $T(n) = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2}$ (you can derive this easily if you think through the algorithm). Now, here $T(n) \in \mathcal{O}(n^2)$ means that the time complexity of the algorithm is quadratic - so if the size of the input is $n$ (we have an array to be sorted consisting of $n$ elements), the algorithm must perform the most expensive operation at most $c \cdot n^2$ times (where $c$ might be 1). Three notes here:

* Typically, we don't care about the "weaker" members of the equations, like $\frac{n}{2}$ in the example above, because of the asymptotic property I mentioned earlier (that wants to say something like "for large enough inputs always the strongest members will only count").
* Typically, we only consider the most expensive operations of an algorithm, i.e., in the case of sorting algorithms, the number of comparisons.
* Many times, people use the notations of $T(n) \in \mathcal{O}(g(n))$ and $T(n) = \mathcal{O}(g(n))$ like they were equivalent (basically, they aren't, but it's a common thing since the use of the latter can be advantageous as well).

So now, that hopefully we are done with the basics, you can see, that if a function $f(n) \in \Theta(g(n))$, it is also true that: $f(n) \in \mathcal{O}(g(n))$ and $f(n) \in \Omega(g(n))$ (in most textbooks, this is presented as a theorem with its proof, as well). In most cases, people **don't care about the lower bounds** of an algorithm's time complexity - so, it shouldn't really matter whether you see $\mathcal{O}$ or $\Theta$ (this would be the answer to your second question). I think that $\Omega$ is much less frequent than the other two.

I haven't ever seen the $ld$ notation you mentioned. However, I would prefer to use $\log\_2$, it will be clear for anyone. Of course, you can use the one you would like to, but make sure to put them into either $\mathcal{O}$ or $\Theta$ (I can't recall a case when only the function was indicated).

Truly hope that I managed to provide a detailed answer you find useful enough. If you have any further question, please feel free to ask.

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


# Question
Title: Highest possible value of combinations of 5
According to https://www.heroescounters.com/teampicker a Hero has a synergy value with another hero, Heroes of the Storm have 60+ heroes each one with a synergy value for example:

```
HeroID  Synergy.With.HeroID      Synergy.Points
1               2                       97
1               3                       95
1               4                       94
45              1                       2
45              2                       11

```

A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:

```
Team_total_synergy = Synergy_Points(Hero1 with Hero2) +
mean(Synergy_Points(Hero3 + Hero1) + Synergy_Points(Hero3 + Hero2)) +

mean(Synergy_Points(Hero4 + Hero1) + Synergy_Points(Hero4 + Hero2) + Synergy_Points(Hero4 + Hero3)

[And so on... till Hero5]

```

Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.

My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.

# Answer
> 2 votes
I suggest you solve it with integer programming (you can download gusek for free for not too complicated computations).

Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s\_{i,j}$ for $(i,j) \in E$.

Define, for $i \in V$, $X\_i$ the boolean variable equal to 1 iff you take hero $i$

Define additional real positive variables $Y\_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.

You want to solve

$\max \sum\_{(i,j) \in E} Y\_{i,j}s\_{i,j}$

such that $\sum\_{i \in V}X\_i = 5$

$\forall (i,j) \in E, Y\_{i,j} \leq X\_i $

$\forall (i,j) \in E, Y\_{i,j} \leq X\_j $

*other formulations are possible. I like this one, since it only has $|V|$ boolean variables*

If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.

Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.

---
Tags: algorithms
---


# Question
Title: Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)
I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every problem in coNP can be reduced to $\text{TAUT}$ in polynomial time. To do that, I would need one of two things:

1. A known coNP-complete problem for reduction or
2. a proof that a problem is coNP-complete if its complement is NP-complete.

Neither of these was given to us in lecture, so I cannot use anything without proving it myself. Did I miss anything which should have been obvious? Where should I start?

# Answer
I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general).

The answer of your questions easily follows from the definition of $coNP$. Remember that a language $L \subseteq \\{0,1\\}^\*$ is in $coNP$ is $\bar{L} = \\{x \in \\{0,1\\}^\* \mid x \notin L\\} \in NP$. For example, $\overline{TAUT}$ is the set of DNF that are not a tautology. To prove that a DNF is not a tautology, you only have to find an assignment that does not satisfy your formula, which can be done in polynomial time with a NTM (just "bruteforce" the assignments). Hence, it is in $NP$. In other words, $\overline{TAUT} \in NP$ thus $TAUT \in coNP$.

Now take an $NP$-complete language $L$. By definition, $\bar{L} \in coNP$. We show that $\bar{L}$ is $coNP$-complete, that is, for every language $A \in coNP$, $A \leq \bar{L}$. Let $A \in coNP$. Then $\bar{A}$ is in $NP$. By $NP$-completeness of $L$, there exists a function $f$, computable in polynomial time such that $x \in \bar{A}$ iff $f(x) \in L$. This is equivalent to say that $x \notin \bar{A}$ iff $f(x) \notin L$. Which in turn, is equivalent to $x \in A$ iff $f(x) \in \bar{L}$. Thus, $f$ is also a reduction from $A$ to $\bar{L}$, meaning that $A \leq \bar{L}$. In other words, $\bar{L}$ is $coNP$-complete.

Now, if you want to show that $TAUT$ is $coNP$-complete, you only have to show that $\overline{TAUT}$ is $NP$-complete. And it is not hard to see that $SAT \leq \overline{TAUT}$. Indeed, a CNF $F$ is satisfiable iff $\neg F$, which is a DNF, is *not* a tautology.
> 11 votes

---
Tags: complexity-theory, np-complete, proof-techniques, co-np
---


title: A* graph search time-complexity

text:
# Question
Title: A* graph search time-complexity
Some confusion about time-complexity and A\*.

According to A\* Wiki the time-complexity is exponential in the depth of the solution (shortest path):

> The time complexity of A\* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d: $O(b^d)$, where $b$ is the branching factor (the average number of successors per state).

The comment to this accepted answer points out that it makes more sense to give the complexity in termes of the size of the graph and therefore it should be $O((|V| + |E|) \cdot log |V|)$

Obviously, if the heuristic assigns a value of 0 to every node, A\* becomes Dijkstra's algorithm and any uniform cost heuristic will essentially disable the heuristic.

If we assume the heuristic to be $O(1)$ (and consistent), it would make sense that the worst case is essentially degrading A\* to Dijkstra's algorithm which has complexity

$O(|E|+|V|\log|V|)$

with a min-priority queue implementation (Fibonacci heap).

**Am I wrong?**

Any book etc I have been looking at always gives the complexity in terms of the depth of the solution

# Answer
> 17 votes
These are basically two different perspectives or two different ways of viewing the running time. Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that typically arise in AI.

In the algorithms community and CS theory community, folks there tend to like to count the running time as a function of the number of vertices and edges in the graph. Why? In that context, worst-case running time is what makes most sense; also, in the problems that are typically considered in that community, in the worst case we need to examine the entire graph, so you typically can't hope to do better than $O(|V|+|E|)$.

In the AI community, folks tend to count the running time differently. They often consider a specific kind of graph: a tree with branching factor $b$. Also, in the situations that arise there, the graph is often infinite or very large. Typically we try hard to avoid examining all of the graph -- that's often one of the major goals of the algorithms. Thus, counting complexity in terms of $|V|$ and $|E|$ doesn't make sense: $|V|$ may be infinite, and in any case, we don't plan on examining all of the graph, so all that matters is the number of vertices we actually visit, not the number that may exist elsewhere but that we don't care about.

So, for the situations that often arise in the AI community, it's often more meaningful to measure the running time in terms of the branching factor of the tree ($b$) and the depth of the goal node ($d$). Typically, once we find the goal node, the algorithm stops. In such a tree, if we examine every vertex at depth $\le d$ before we find the goal node, we'll end up visiting $O(b^d)$ vertices before we stop. Thus, if you like, you could think of this as visiting a subset of the graph with $|V|=O(b^d)$ (where now $V$ includes only the vertices we visit) and $|E|=O(b^d)$ ($E$ includes only the edges we look at), and you could think of an $O(b^d)$-time algorithm as one whose running time is $O(|V|+|E|)$... though this is a bit of an abuse of the $|V|,|E|$ notation. Anyway, hopefully you can see why $O(b^d)$ is more informative than $O(|V|+|E|)$ in this context.

# Answer
> 2 votes
It is common in the combinatorial search community to define search spaces *implicitly*, that is, as a set of states and transitions between them - as opposed to *explicitly*, that is, as concrete sets of vertices and edges. In implicit search spaces, states can be represented as vertices and transitions as edges, however, in many cases the practical set of states *may not have finite bounds* and therefore the number of edges and vertices cannot always be defined with finite cardinalities (either practically or theoretically). Thus for many applications it makes more sense to define performance in terms of the branching factor $b$, as opposed to vertex and edge cardinalities.

---
Tags: algorithms, algorithm-analysis, graphs, runtime-analysis, shortest-path
---


# Question
Title: Maximum weight tree with weights on vertices
**Problem Statement**

Let, $G(V,E)$ be a graph with a weight function $w(v)$ defined for all vertices. We need to find a tree $T(V',E')$ such that the resulting tree have maximum sum of weights of vertices, where $V' \in V$ and $E' \in E$. In short, we need to remove some vertices(along with all their edges) from $G(V,E)$ such that the resulting graph is a tree and have maximum weight among all such trees. $T(V'.E')$ should be an induced subgraph of $G(V,E)$.

**My Attempt**

First, sort the vertices in descending order. Then, pick the vertices in that order ensuring that adding a vertex won't create cycles. If it creates cycles, don't consider that vertex. To check if adding a particular vertex adds cycles, I thought of assigning each component a uniaue number. Hence, if adding a vertex results in joining that vertex to two vertices of the same component, we don't add that vertex. But, I couldn't find an efficient way on how should we keep track of which vertex belongs of which component. Can DSU help me with this approach?

# Answer
It would seem that you need a Disjoint-set data structure.

When introducing each node $u$ with highest weight not in the tree, get all the nodes $u$ is connected to, call that neighbor set $C$. Iterate over all pairs $\\{v, v'\\}$ in $C$, $v \neq v'$, and check to see wether the disjoint-set trees of $v$ and $v'$ are same; if yes, adding $u$ will introduce a cycle. Finally, if adding that node $u$ restoring all the induced edges is possible without introducing a cycle, make sure that you add that $u$ to the same Disjoint-Set "tree" that contains all the prior nodes.
> 1 votes

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: Closure Properties between different Language Classes
I am trying to understand closure properties between different language classes. For example, if L1 is regular and L2 is recognisable, then is L1 intersection L2 decidable? My answer is that L1 is also recognisable and therefore L1 intersection L2 is recognisable. However, this cannot guarantee that it is decidable. Is this a correct solution?

# Answer
> 1 votes
Yours is a correct *intuition*: $L\_1 \cap L\_2$ is indeed recognisable.

However, you can't say that such language is not decidable only because you failed to prove it decidable. In theory, there could be a more complex argument that you were not able to find, which could establish that $L\_1 \cap L\_2$ is actually decidable.

To prove it, you need a counterexample. It is usually helpful to try corner cases, first.

For instance if $L\_1 = \Sigma^\*$, which is regular, we get $L\_1 \cap L\_2 = L\_2$ which is decidable only if $L\_2$ is such. Hence, since recognizable but non decidable languages exist, we get a counterexample.

Further, note that if we took $L\_1 = \emptyset$, which is regular, then $L\_1 \cap L\_2 = \emptyset$ which is decidable, whatever $L\_2$ is.

Hence, from the given hypotheses, we can not conclude that $L\_1 \cap L\_2$ is decidable, nor that it is not. This is because we found counterexamples to both conjectures.

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


# Question
Title: How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions
How to encode a sequence of n non-decreasing integer of \[0, ..., m\] fulfilling the following conditions:

1. no or minimal redundancy
2. only use 1 integer variable or k independent integer variables with a range of \[0, ..., j(k)\], It means there exist an inverse function f-1(x) to map the encoded sequence, an integer x of the domain \[0, 1, ..., |valid sequence| - 1\], back the original sequence.
3. usual integer operations
4. no or minimal lookup tables
5. closed form formula to decode back to the sequence without loops or recursions

For example,

```
0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
...
0, 0, 0, m
0, 0, 1, 1
0, 0, 1, 2
...
m, m, m, m

```

The purpose of this counting function is to enumerate all possible values in the non-decreasing integer sequence later being used in constraints.

# Answer
> 3 votes
Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\\{0,\ldots,m\\}$, and let $C(n,m) = |\mathcal C(n,m)|$ be the number of such sequences. It is not hard to verify the following recursion: $$ \begin{align\*} &C(0,m) = 1, \\ &C(n,m) = \sum\_{k=0}^m C(n-1,k) \text{ for } n \> 0. \end{align\*} $$ In fact, it is not hard to check that $$ C(n,m) = \binom{n+m}{m}. $$ But the recursion allows us to rank and unrank sequences. More explicitly, we will now describe a bijection $r\_{n,m}$ from $\mathcal C(n,m)$ to $\[0,C(n,m))$ (i.e., $\\{0,\ldots,C(n,m)-1\\}$). The bijection is defined recursively as follows (below, $\lambda$ is the empty sequence): $$ \begin{align\*} &r\_{0,m}(\lambda) = 0, \\ &r\_{n,m}(\sigma\_1,\ldots,\sigma\_n) = \sum\_{k \< \sigma\_n} C(n-1,k) + r\_{n-1,\sigma\_n}(\sigma\_1,\ldots,\sigma\_{n-1}). \end{align\*} $$ This doesn't order the sequences in the order you listed, though one can easily adapt it to your order (by considering the first rather than last element). We can also describe the inverse bijection explicitly: $$ \begin{align\*} &r^{-1}\_{0,m}(0) = \lambda, \\ &r^{-1}\_{n,m}(r) = r^{-1}\_{n-1,k}\left(r - \sum\_{\ell\<k} C(n-1,\ell)\right),k, \\ &\qquad \text{ where $k$ is defined by } \sum\_{\ell \< k} C(n-1,\ell) \leq r \< \sum\_{\ell \leq k} C(n-1,\ell). \end{align\*} $$

Finally, if all you want is to list the sequences in order, say the order in your post, then you can use the following simple "counter" algorithm. Start with the all-zero sequence $\sigma\_1 = \cdots = \sigma\_n = 0$. At each step, find the maximal $i$ such that $\sigma\_i \< m$ (if $\sigma\_1 = \cdots = \sigma\_n = m$, we are done). Increase $\sigma\_i$, and set all numbers following it to its new value. This will enumerate all sequences in lexicographic order, in amortized time $O(1)$ per sequence.

---
Tags: algorithms, permutations, counting, encoding-scheme, constraint-programming
---


# Question
Title: Could we design a Turing machine that output every bit of $\pi$ one after another correctly with limited tape length?
Could we design a Turing machine that output every bit of $\pi$ one after another correctly?

I think we have computer programs that calculate the value of $\pi$ day after day, and thus it's viable.

Could we do that if the Turing machine has a limited tape length?

# Answer
> 4 votes
If by "limited tape length", you mean having a finite amount of memory, then the answer is "no". With a finite amount of memory, the Turing machine as a whole can be modeled as a finite state machine. A finite state machine that doesn't terminate must eventually repeat a state and thus fall into a loop. Therefore, the output of any such machine must correspond to the binary expansion of a rational number. The binary expansion of any irrational number whatsoever will require an unbounded amount of state.

# Answer
> 2 votes
As $\pi$ is a transcendental (yet computable) number, all algorithms that calculate its digits will have to rely on approximation strategies that entail the instantaneous use of increasingly large numbers.

If there was a limit to these quantities, it wouldn't be possible to continue representing digits with ever greater precision, and repetitive patterns (that we know do not exist) would necessarily emerge in the execution of any deterministic algorithm.

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


title: What is an approximation oracle?

text:
# Question
Title: What is an approximation oracle?
I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am somewhat familiar with the idea of an "oracle machine" in complexity theory.

# Answer
An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the approximation.

Approximation oracles are a formal way of stating results of the following form:

> Given a polynomial time $C$-approximation algorithm for $X$, there is a polynomial time $f(C)$-approximation algorithm for $Y$.

Formally, we give a polynomial time $f(C)$-approximation algorithm for $Y$ which uses a $C$-approximation oracle for $X$.
> 6 votes

---
Tags: complexity-theory, approximation, oracle-machines
---


title: Meaning of Merge[A[1,..n], m]

text:
# Question
Title: Meaning of Merge[A[1,..n], m]
I was reading JeffE's (Prof. Jeffrey Erickson) notes on solving recurrences, and he used Merge\[A\[1,...n\], m\] where A is an array(I think) and m is an integer. What does this mean? I thought Merge sort took two arrays as input. He includes psuedo code, but I can't decipher what is means. What is it doing?

Thank you for any help.

Link: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

# Answer
> 1 votes
$Merge\[A\[1,...n\], m\]$ means merge arrays $A\[1..m\]$ and $A\[m+1..n\]$.

They are recursively sorted before merging by

```
MergeSort(A[1 .. m])
MergeSort(A[m + 1 .. n])

```

---
Tags: algorithms
---


title: How can I prove DP completeness?

text:
# Question
Title: How can I prove DP completeness?
We defined the class $\text{DP}$ like this:

$$\text{DP} := \\{ A \setminus B : A, B \in \text{NP} \\}$$

We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \text{DP}$, meaning that every language $X \in \text{DP}$ can be reduced to $P$ in polynomial time.

For a particular problem (which I do not expect you to solve, so I won't explain all the details), I already proved that $P \in \text{DP}$, but I do not know how to continue. Also, I could not find more information about this class.

Could someone give me a hint how to start such a proof or point me to further information about this complexity class which might help me to achieve it?

**Edit**: The definition is from a lecture about complexity of algorithms. The task is to prove that

$$\text{SAT-UNSAT} = \\{\\, (F,G) : F \text{ is satisfiable}, G \text{ is not}\\, \\}$$

is DP-complete. I proved that $\text{SAT-UNSAT} \in \text{DP}$, but I failed to prove the completeness.

# Answer
> 4 votes
The DP-hardness of SAT-UNSAT is a direct consequence of the fact that SAT is NP-hard.

Suppose that $L \in \mathrm{DP}$. Then there exist languages $A \in \mathrm{NP}$ and $B \in \mathrm{coNP}$ such that $L = A \cap B$. Since SAT is NP-complete, there exists a polytime reduction $f$ such that $x \in A$ iff $f(x) \in \mathrm{SAT}$. Since UNSAT is coNP-complete, there exists a polytime reduction $g$ such that $x \in B$ iff $g(x) \in \mathrm{coSAT}$. You can check that the polytime reduction $h(x) = (f(x),g(x))$ satisfies $x \in L$ iff $h(x) \in \mathrm{SAT\text{-}UNSAT}$. This shows that SAT-UNSAT is DP-hard.

To complete the proof that SAT-UNSAT is DP-complete, you have to show that SAT-UNSAT is in DP. Presumably you already know how to do that.

Note that DP contains both SAT and UNSAT, and in particular differs from NP unless NP=coNP.

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


# Question
Title: How can I convert a for loop to a recursive function?
My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a\<=b. The function will then create a list of numbers from a to b.

This is what I created:

```
 def cat(a,b):
     j = []
     for i in range (a,b):
     j.append(a+1)
     a +=1

```

I honestly cannot figure out how to turn this into a recursive function.. I have tried things which I realize don't make any sense and I'm not really sure where to start. Any help would really be appreciated :) Thanks

# Answer
> 2 votes
Here is a recursive version of this procedure, in python:

```
def cat(a,b):
  if a == b:
    return [a]
  else:
    return [a] + cat(a+1,b)

```

Another option is

```
def cat(a,b):
  if a == b:
    return [b]
  else:
    return cat(a,b-1) + [b]

```

These conversions are heavily geared toward this particular function. Here is a more general conversion, in the context of state machines without input (inputs can easily be added):

```
def run_my_algorithm(state = None):
  if state is None:
    state = initial_state
  if is_final_state(state):
    return extract_answer(state)
  else:
    state = next_state(state)
    return run_my_algorithm(state)

```

Hopefully the notation is self-explanatory.

---
Tags: recursion, loops
---


title: Domain Theory and Polymorphism

text:
# Question
Title: Domain Theory and Polymorphism
Domain theory gives an amazing theory of computability in the presence of simple types. But when parametric polymorphism is added there doesn't seem to be a nice theory that explains whats going on quite as nicely as domain theory explains computation over simple types. Certainly I wouldn't expect such a thing to exist for System-F because no set theoretic models of System-F exist. What about a restriction of System-F that has predictive and has a universe hierarchy? Has this been studied? Is there a nice domain theory that applies to it? Going further what about dependent types? Can domain theory somehow be mixed with weak $\omega$-groupoids to accomplish something?

# Answer
There are many ways to model polymorphism via domain theory, let me just describe one that is easy to understand, so you can think about it yourself. It's a "PER model".

Take any model of the untyped $\lambda$-calculus, for instance a domain $D$ such that $D \to D$ is a retract of $D$ (for instance, take $D$ such that $D \cong \mathbb{N}\_\bot \times (D \to D))$. Let $\Lambda : D \to (D \to D)$ and $\Gamma : (D \to D) \to D$ be the retraction and the section, respectively.

We are going to interpret the types as partial equivalence relations (PER) on $D$. Recall that a PER is a relation which is symmetric and transitive, but it need not be reflexive. To each type $\tau$ we thus assign a PER $\sim\_\tau$. Think of $x \sim\_\tau x$ as "$x$ is an element of $\tau$" and $x \sim\_\tau y$ as "$x$ and $y$ are equal as far as $\tau$ is concerned".

We can have some basic types (but need not), for instance if we make sure that $\mathbb{N}\_\bot$ is a subdomain of $D$ via an embedding $\iota : \mathbb{N} \to D$ then we may define $\sim\_\mathtt{nat}$ by $$x \sim\_\mathtt{nat} y \iff \exists n \in \mathbb{N} . x = \iota(n) = y.$$

Given PERs $\sim\_\tau$ and $\sim\_\sigma$, define the *function space PER* $\sim\_{\tau \to \sigma}$ by $$x \sim\_{\tau \to \sigma} y \iff \forall z, w \in D . z \sim\_\tau w \Rightarrow \Lambda(x)(z) \sim\_\sigma \Lambda(y)(w)$$

The terms are interpreted as untyped $\lambda$-calculus terms as one would normally interpret them in $D$.

Here's the punchline. You may interpret polymorphism as intersection of PERs, that is: $$x \sim\_{\forall X. \tau(X)} y \iff \text{for all PERs $\approx$, $x \sim\_{\tau(\approx)} y$}. $$ We can caclulate the PER corresponding to $\forall X. X$: it is the intersection of all PERs, but that is going to be the empty PER. Calculating $\forall X . X \to X$ is an interesting exercise. Calculating $\forall X . X \to X \to X$ is a difficult exercise (which kept me busy for a week when I was a student of domain theory).

If we want recursion in our language then we need to account for fixed points. One possibility is to restrict PERs to those which contain $\bot\_D$ and are closed under suprema of increasing chains. More precisely, take only those PERs $\approx$ for which

* $\bot\_D \approx \bot\_D$, and
* if $x\_0 \leq x\_1 \leq x\_2 \leq \cdots$ and $y\_0 \leq y\_1 \leq y\_2 \leq \cdots$ are increasing chains in $D$ such that $x\_i \approx y\_i$ for all $i$, then $\sup\_i x\_i \approx \sup\_i y\_i$.

We can now interpret $\mathtt{fix}\_{\tau} : (\tau \to \tau) \to \tau$ by applying the Kanster-Tarski theorem about existence of fixed points, just like we do in ordinary domain theory. This time, $\forall X . X$ is not empty, as it contains precisely $\bot\_D$.
> 6 votes

# Answer
Roy Crole gives a nice explanation of how to use domain theory to model type polymorphism in his book *Categories for Types*, specifically in section 5.6.
> 0 votes

---
Tags: computability, type-theory, dependent-types
---


# Question
Title: Algorithm for deciding alpha-equivalence of terms in languages with bindings
I am interested in the alpha equivalence relation in languages with variable bindings, such as:

```
t := x:y    'x belong to y'
  | bot     'False'
  | t -> t  'implication'
  | Ax.t    'forall x, t'

```

Or the pure lambda calculus:

```
t := x       'variable'
  | (t t)    'application '
  | Lx.t     'abstraction: \x -> t'

```

I am looking for an algorithm allowing me to determine whether two terms of the language are alpha-equivalent or not. Any published reference is very welcome too. I am assuming a data representation of the terms as a standard recursive type, for example in Haskell:

```
newtype Var = Var Int
data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term

```

# Answer
There are several ways to do what you want. One of them is to use a different syntax representation under which $\alpha$-equivalent terms are actually equal. Such representations go under the name *nameless* or *locally nameless* syntax. A popular one uses de Bruijn indices. See my blog posts How to implement dependent type theory I, II and III for a blitz introduction to implementing this sort of thing (part III has de Bruijn indices explained).

If you insist on your representation, then we may still secretly use de Bruijn indices, as follows. As we descend inside a subterm during comparison, we keep a list of pairs of bound variables so far encountered. For example, when comparing `Forall x1 e1` and `Forall x2 e2`, we add the pair `(x1, x2)` to the list and recursively compare `e1` and `e2`. When asked to compare variables `x` and `y`, we search down the list: either they must both appear in the same spot (they were bound by the same quantifier) or neither appears and they are equal (they are both free and they are equal).

I am not well-versed with Haskell, but you'd get something like this:

```
newtype Var = Var Int deriving Eq

data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term

equalVar :: [(Var,Var)] -> Var -> Var -> Bool
equalVar [] x y = (x == y)
equalVar ((x,y):bound) z w = (x == z && y == w) || (x /= z && y /= w && equalVar bound z w)

equal' :: [(Var, Var)] -> Term -> Term -> Bool
equal' bound (Belong x1 y1) (Belong x2 y2) = (equalVar bound x1 x2 && equalVar bound y1 y2)
equal' bound Bot Bot = True
equal' bound (Imply u1 v1) (Imply u2 v2) = equal' bound u1 u2 && equal' bound v1 v2
equal' bound (Forall x u) (Forall y v) = equal' ((x,y):bound) u v
equal' _ _ _ = False

equal :: Term -> Term -> Bool
equal e1 e2 = equal' [] e1 e2

```
> 9 votes

---
Tags: logic, lambda-calculus, first-order-logic
---


# Question
Title: How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?
> We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:
>
> 1. Creates a new array double the size of the original one.
> 2. Copies all elements of the old array to the new array, preserving the order.
>
> Adjust the algorithm so that the insertion of new element will be in constant time in the worst case.

The limitation here is we must use arrays as stack implementation.

The worst case is when for example the old stack of size $n$ is full and now we need to insert a new element. So we create a new stack $S\_2$ of size $2n$ and we want to insert the new element to $S\_2\[n+1\]$.

I'm stuck with the constant time requirement, I'd appreciate any hints to the right direction.

**NB:** I'm aware that the title is a bit general, I couldn't think of anything more specific, if you know under which category of algorithms it falls under please let me know and I'll edit the heading.

# Answer
> 3 votes
I don't think that it is possible to push an element to a **full** array-based stack in worst case $\mathcal{O}(1)$ time. However, you can rest assured that each push runs in constant **amortized** time whenever you multiply the length of the full array by a factor of $q \> 1$ (like you do; $q = 2$ in your case). This is why:

Suppose the initial array capacity is $m$. Next we choose $q \> 1$ such that $\lfloor qm \rfloor \> m$, or namely, $q$ must be sufficiently large in order to trigger an array expansion.

Suppose the total accumulated work of adding $n$ elements to the stack is

$$W = m + mq + mq^2 + \dots + \overbrace{mq^k}^n$$.

We require $k$ to be the smallest integer such that $mq^k \geq n$, which leads us to the following inequalities:

$$ \begin{aligned} mq^k &\geq n \\ q^k &\geq \frac{n}{m} \\ \log\_q q^k &\geq \log\_q \Bigg( \frac{n}{m} \Bigg) \\ k &\geq \log\_q n - \log\_q m. \end{aligned} $$

Since $k$ is required to be the smallest integer satisfying the above inequality, we can set $k = \lceil \log\_q n - \log\_q m \rceil$. Also,

$$ \begin{align} qW = mq + mq^2 + \dots + mq^{k + 1} &\Rightarrow W - qW = m(1 - q^{k+1}) \\ &\Rightarrow W = m\frac{1 - q^{k+1}}{1-q}. \end{align} $$

Since $k = \lceil \log\_q n - \log\_q m \rceil$, we obtain $$ \begin{align} W &= m\frac{1 - q^{\lceil \log\_q n - \log\_q m \rceil + 1}}{1 - q} \\ &\leq m\frac{1 - q \cdot q^{\lceil \log\_q n \rceil}}{1 - q} \\ &\leq m \frac{1 - q \cdot q^{\log\_q n + 1}}{1- q} \\ &= m \frac{1 - q^2n}{1 - q}. \end{align} $$

Now we have that

$$ \begin{align} \frac{1}{n} W &\leq \frac{1}{n} \Bigg\[ m \frac{1-q^2n}{1-q} \Bigg\] \\ &= \frac{1}{n} \Bigg\[ \frac{m}{1-q} - \frac{nmq^2}{1-q} \Bigg\] \\ &= \frac{m}{(1-q)n} - \frac{mq^2}{1-q} \\ &\leq \frac{m}{1-q} - \frac{mq^2}{1-q} \\ &= \frac{m(1-q^2)}{1-q} \\ &= \frac{m(1+q)(1-q)}{1-q} \\ &= m(1+q), \end{align} $$ which is constant since $m$ and $q$ are fixed parameters independent of $n$.

# Answer
> 0 votes
If you use *one* array for storage, and you add more and more items to the stack, then at some point you need to increase the size of the array. Most likely your "array" implementation doesn't allow increasing the array size in constant time.

So the only possible solution: Reserve all available space for the array, at the time the stack is created, that is before adding the first item. Since all available space has been reserved, it is impossible to increase the array size, so all operations can be done in constant time.

It is kind of cheating though.

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


title: Prove "almost clique" is NP complete

text:
# Question
Title: Prove "almost clique" is NP complete
Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called **almost clique** if by adding a single edge, $S$ becomes a clique.

Consider the language: $L=\\{\langle G,t\rangle \mid \text{the graph \\(G\\) contains a \\(t\\)-sized almost-clique}\\}$. Prove that $L$ is NP-complete.

Obviously, it is solved by polynomial reduction, but is it from Clique or 3SAT? And how?

# Answer
> 5 votes
You can reduce to this from $CLIQUE$.

Given a graph $G=(V,E)$ and $t$, construct a new graph $G^\*$ by adding two new vertices $\\{v\_{n+1},v\_{n +2}\\}$ and connecting them with all of $G$'s vertices but removing the edge $\\{v\_{n+1},v\_{n+2}\\}$, i.e. they are not neighbors in $G^\*$. return $G^\*$ and $t+2$.

If $G$ has a $t$ sized clique by adding it to the two vertices we get an $t+2$ almost clique in $G^\*$ (by adding $\\{v\_{n+1},v\_{n+2}\\}$).

If $G^\*$ has a $t+2$ almost clique we can look at three cases:

1) It contains the two vertices $\\{v\_{n+1},v\_{n+2}\\}$, then the missing edge must be $\\{v\_{n+1},v\_{n+2}\\}$ and this implies that the other $t$ vertices form a $t$ clique in $G$.

2) It contains one of the vertices $\\{v\_{n+1},v\_{n+2}\\}$, say w.l.o.g. $v\_{n+1}$, then the missing edge must be inside $G$, say $e=\\{u,v\\}\in G$. If we remove $u$ and $v\_{n+1}$ then the other $t$ vertices, which are in $G$ must form a clique of size $t$.

3) It does not contain any of the vertices $\\{v\_{n+1},v\_{n+2}\\}$, then it is clear that this group is in $G$ and must contain a clique of size $t$.

It is also clear that the reduction is in polynomial time, actually in linear time, log-space.

# Answer
> 0 votes
The subgraph $S$ of $G=(V,E)$ is a called an $s$-defective clique when $E(G\[S\]) \geq \binom{|S|}{2} - s$, i.e., missing at most $s$ edges from clique. Your definition is similar to 1-defective clique.

The question about hardness can be done in one line. Observe, that defective clique is a hereditary structure. By Yannakakis theorem its optimization maximum problem is NP-hard.

---
Tags: np-complete, reductions, np, 3-sat, clique
---


# Question
Title: Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular
Given that language $L = \\{a = b ⊕ c \mid a, b, c ∈ \\{0,1\\}^\*, a = b \oplus c\\}$, with an alphabet $Σ = \\{⊕, =, 0, 1\\}$, I need to prove that this language is not regular. The following is as far as I have gotten in my proof, but I am getting stuck when showing why it is contradicting the pumping lemma:

$s = (1^p = 1^p ⊕ 0^p)$

$x = 1^l$

$y = 1^m$, where $l+m \le p$ and $m \> 0$

$z = (1^{p-l-m}=1^p ⊕ 0^p)$

Taking $i=2$, $xy^2z = (1^l1^{2m}1^{p-l-m}=1^p ⊕ 0^p) = (1^{p+m}=1^p ⊕ 0^p)$

—This is where I am getting stuck. From my example, this appears to be a contradiction, but there is nothing in the language dictating that $b$ and $c$ be of equal lengths. Were they to be different lengths, it could certainly be possible that no contradiction would be found by adding $m$ to $p$. How could I fix my proof via pumping lemma?

---EDIT: SECOND TRY---

$s = ((10)^p = (01)^p ⊕ (10)^p)$

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m \> 0$

$z = ((10)^{p-l-m}=(01)^p ⊕ (10)^p)$

Taking $i=0$, $xy^0z = ((10)^l(10)^{p-l-m}=(01)^p ⊕ (10)^p) = ((10)^{p-m}=(01)^p ⊕ (10)^p)$

Now, I have that $|a|\<|b|$ and $|a|\<c$, which is not possible, since the result of the exclusive-or must contain a leading 1, which cannot be truncated to a smaller string length. Therefore, this is a contradiction.

Is this a contradiction strong enough to prove the language is not regular? It only works in the case of a leading 1; do I need to show something that is a contradiction even with leading 0's?

# Answer
Suppose $L$ were regular. Let $p$ be the pumping constant assumed to exist and consider the string

$$s = 1^p = 1^p \oplus 0^p$$

Clearly, $|s| \geq p$ so for some strings $x,y,z$ we have $s = xyz$ where

1. $|xy| \leq p$
2. $|y| \> 0$
3. $xy^iz \in L$ for all $i \geq 0$

If condition 1 is to hold, $y$ must be a string of $1$s. If condition 2 is to also hold, then $y = 1^k$ for some $k \> 0$. But then condition 3 fails, since $xy^0z \notin L$.

For $xy^0z = 1^{p-k} = 1^p \oplus 0^k$, and this identity is false irrespective of whether we require $w\_1 \oplus w\_2$ to be defined for strings of the same length only, or in general.
> 1 votes

# Answer
Thought A)

Perhaps your definition of "a" needs to be reworked; eg. not count all the leading zeros as significant (0000 = 0). You can substantiate this by making the case that XOR is an arithmetic operation.

In this way given an acceptor for a given length of string you could pump through another string that output the same result proving that its not regular.

010 XOR 010 = 0 and 0110 XOR 0110 = 0

Thought B)

There are no "real" contradictions for the language "a". It consists of every string of { 0,1 }\* by definition. However using thought A) you can pump through multiple "definitions" of an accepted word in the language.

Thought C)

What do you think?
> -1 votes

---
Tags: regular-languages, proof-techniques, pumping-lemma
---


# Question
Title: Would limiting the number of operations in a transaction prevent SQL injection?
In my understanding all SQL injections need to add another operation to the one intended by the programmer.

For example, a badly written query:

```
query="Select * from Table where name="+name;

```

User inputs name as: `foo; Delete from Table;` and this would be an SQL Injection. But if the programmer would be able to limit the number of operations in a transaction to 1 (the Select in this case) or how much operations he intends to use the SQL Injection would be impossible. Is there a way we can limit the number of operations in most programming languages? Would this be enough to stop SQL Injection?

# Answer
> 1 votes
It could help avoiding *some* attacks. However, allowing the adversary to inject a part of the SQL `WHERE` clause is already quite dangerous.

E.g. injection can change this

```
SELECT * WHERE name="username"

```

into

```
SELECT * WHERE name="Bah!" or true or "too easy!"="x"

```

The sane thing would be to avoid injection completely. Ideally, in a typed language, the type of a SQL query should NOT be a string, so to prevent concatenation with user data. It should be a query template, to be filled with a special function. Something like

```
query = new Query(...);
fill(query, { "username": username })

```

Type systems excel for imposing these constraints of the programs. On the other hand, their use require some thoughtful library design. Sometimes it feels simpler to provide a more low-level solution (like using strings for everything), which is also simpler to use, and possibly document the potential security issues "programmers: don't do this", which can then be ignored by busy programmers, which would often take the shortest path to their goals. Types here would simply block the quick path, forcing the programmers to separate the "query template" part from the "user data" part.

Some languages still use strings for templates, but at least encourage programmers to avoid concatenation, and favor some `fill`-like function.

```
fill("SELECT * WHERE name=@username", { "username": username })

```

The above is doable even in an untyped language.

Moral: let the library perform all the string-escaping for you. The library always checks for special characters, and handles them correctly. You likely won't cover all the tricky cases.

Don't try to patch against an attack by imposing restrictions on just that attack. Consider all the variants for that attack which can pass the restriction. If injection is the problem, prevent injection at the root.

# Answer
> 1 votes
It is a totally inappropriate approach to the problem.

The whole premise of an SQL injection is sheer madness. It allows a possibly malicious end user to modify the code that the software developer has created. That is just mad. It is something that should never, ever be allowed to happen. To avoid this, write your SQL code so that the user cannot modify it (for example using parameterized queries).

Allowing the user to modify code and then somehow restricting what the code could do will inevitably fail. And you added the problem for the developer who wants to make his code work for normal situations, the he now must predict precisely how many operations his code will perform.

---
Tags: databases, security
---


# Question
Title: Two recurrences for the change-making problem with repetition
The change-making problem with unbounded repetition is:

> * Input: Unlimited quantities of coins with values $x\_1, \ldots, x\_n$ and an amount $v$.
> * Output: Can the given $v$ amount of money be made with these coins?

The first recurrence is based on the subproblems of $C\[w\]$: can $w$ be made with these coins?

$$ C\[w\] = \bigvee\_{i: x\_i \le w} C\[w-x\_i\]. $$

The second recurrence is based on the subproblems of $C\[i,w\]$: can $w$ be made with coins $x\_1, \ldots, x\_i$?

$$ C\[i,w\] = (C\[i, w-x\_i\] \land w \ge x\_i) \lor C\[i-1, w\]. $$ The recurrence consider both cases of whether $x\_i$ is used or not.

---

***Problem:*** I think both recurrences are correct. Therefore, I want to understand their connections.

Specifically, how are they equivalent (*if* both are correct, of course) in terms of the subproblems they solve.

Can we transform one to another by, for instance, introducing a second variable to the first one or eliminating one variable from the second one?

# Answer
First, the number of subproblems and dependencies among these subproblems for the first recurrence are $v$ and $nv$ respectively, while they are $nv$ and $2nv$ respectively for the second one.

Pictorially, the subproblem-dependency graph of the first recurrence is a 1D array and that of the second one is a 2D table.

Informally, the subproblem-dependency graph of the second recurrence can be regarded as a "compacted" version of that of the first one in the sense that the 2D table is compressed into a 1D array through the clause $\lor C\[i−1,w\]$ in the second recurrence.

Formally, inspired by the comment made by @Raphael, if we expand $C\[i−1,w\]$ recursively in the second recurrence, we get (ignoring the $w \ge x\_i$ details)

$$ \begin{align\*} C\[i,w\] &= C\[i, w-x\_i\] \lor C\[i-1, w\] \\ &= C\[i, w-x\_i\] \lor (C\[i-1, w-x\_{i-1}\] \lor C\[i-2, w\]) \\ &= C\[i, w-x\_i\] \lor C\[i-1, w-x\_{i-1}\] \lor C\[i-2, w-x\_{i-2}\] \lor C\[i-3, w\] \\ &= \cdots \\ &= \bigvee\_{j \leq i: x\_j \le w} C\[j, w-x\_j\] \end{align\*} $$

Therefore, we can conclude that $C\[n,w\] = C\[w\]$.
> 3 votes

# Answer
*This answer is wrong; see hengxin's.*

The second is more efficient because it uses an (arbitrary) order of coins whereas the first one treats the set of denominations as unordered set.

You get from the first to the second by noting that you check different permutations of the same (multi-)set of coins, and then doing away with this redundancy.
> 2 votes

---
Tags: algorithms, recurrence-relation, dynamic-programming, knapsack-problems
---


# Question
Title: algorithm that removes extraneous connections from a graph
For a nondirection graph $G=(V,E)$, I need to write an algorithm that finds connections that can be removed without destroying the graph (ex: a connection from a child of a child back to the root of the graph). I have created an algorithm with a runtime of $O(|V|+|E|)$ (utilizing BFS):

```
    smallerGraph(G,s):
    for all vertex u from V[G]do
      color[u]=WHITE
      p[u]=NIL
      n[u]=NIL
    end for
    for all vertex u from V[G]do
      if color[u]==WHITE then
        modifiedDFSVisit(G,u)
       end if
    end for
    return 0
    modifiedDFSVisit(G,u):
    color[u]GRAY
    for all vertex v from Adj[u]do
      if color==BLACK and p[v]!=u and p[n[v]]!=v then
        removeLink(u,v)
      end if
      if color[v]==WHITE then
        p[v]=u
        n[u]=v
        modifiedDFSVisit(G,v)
      end if
    end for
    color[u]=BLACK

```

Additionally, I am also looking algorithm that can solve the same problem, however this time with a runtime of $O(|V|)$. If this is possible, if someone could point me in the right direction, I would appreciate it. If it isn't possible, why? Would the answer change if I was given a list of the connections (as well as the number of connections)?

# Answer
You describe the graph as

* $V$ - a set of vertices
* $E$ - a set of edges, where each edge is (presumably) an unordered pair.

To determine where you can go from each vertex $v \in V$, you need to scan the whole of $E$, so you are already $\Theta (|V| + |E|)$.

If the graph is in the form ... $$ V \rightarrow 2^V$$ ... then you can find a spanning tree in $\Theta(|V|)$. To *enumerate* the edges left out, you are up to $\Theta (|V| + |E|)$ again. But if you don't need to enumerate them, you can determine whether any given edge is spare in constant time.

---

**Correction**

> If the graph is in the form $ V \rightarrow 2^V$, then you can find a spanning tree in $\Theta(|V|)$.

I think this is wrong. Whatever your search order, at each vertex you have to look through the neighbours to find an undiscovered one, which might be the last. Depending on the structure of the graph, this might happen at every vertex. So the worst case at least is $\Theta (|V| + |E|)$.
> 1 votes

---
Tags: algorithms, graphs, graph-traversal
---


title: Is Virtual Memory unreliable?

text:
# Question
Title: Is Virtual Memory unreliable?
I have a question regarding multilevel page tables. As far as I know, in most 64 bit systems only 48 bits are used in page tables which would allow for 256TB of virtual memory to be addressed.

For personal computers, I don't understand how they would ever be able to support that amount of memory being virtualized. If the processes currently running on your computer think they have a total of 256TB available, if they do end up using all that memory, the contents would eventually need to be flushed back to disk. This is not possible since your disk can't possibly hold that much memory.

I'm thinking on an analogy to a bank that tells its customers they can each take out loans of 1,000 gold bars. They give their customers a note saying they have 1,000 gold bars worth of funds. Now say that the customers have used their loans to obtain different goods which they want to store in the bank. The bank would not be able to hold all those goods, and the people (processes) wouldn't be able to hold those goods either since once a computer is shut off all the memory not on disk is volatile. In a sense the bank is offering more than it can really hold.

For a more practical example, say I have 1GB of disk memory available and my virtual memory system is able to virtualize 3GB of memory. Now say I open 3 text files and start typing stuff into them, eventually reaching that 3GB limit. Now I want to save those files, but I only have 1GB available on disk!

Isn't virtual memory unreliable from a process point of view since it's saying "I can store all this stuff for you" but at the end of the day it doesn't have the resources to do so?

# Answer
> 2 votes
At a hardware level, virtual memory means, essentially, a mapping from a virtual address space to a physical address space, the data structures and instructions to maintain them, and a facility to trap to the operating system if a mapping is not valid. This mapping is at the *page* level: a page maps to a page frame.

At the operating system level, we usually conceptualise a virtual address space as a collection of segments. A segment could represent part of a file which resides on secondary storage (e.g. disk). This could be program text, or a memory-mapped file. Or it could represent anonymous memory, that is, memory which is allocated by a process and may be swapped to secondary storage if not needed. Anonymous segments are often zero-fill, which isn't backed by physical memory until it is first used. Or it could represent a memory-mapped I/O area, or an operating system device, or an operating system data structure (e.g. the "u area" in Unix).

Segments can be shared between address spaces (e.g. after the Unix fork system call). They can be copy-on-write. And so on and so forth.

There are enough "things" that can be mapped which aren't really "memory" that you can't really say that virtual address space is only as useful as the amount of physical stuff that can be mapped to it.

One more thing: Another advantage of a large virtual address space is reduced external fragmentation. You see, the segments that comprise a virtual address space need to be allocated and deallocated just like anything else, and you can't really move them within the address space. So having a large virtual address makes it easier to allocate within it.

# Answer
> 1 votes
No. Virtual memory is reliable (typically). The OS might not let you allocate 256TB of virtual memory, unless you have a particularly beefy computer, but if it does let you allocate the memory and doesn't kill your process due to an out-of-memory situation, it is reliable.

(Separately: It's well within the realm of the possible to have 256TB of disk, even today, without inventing futuristic technology.)

Perhaps what is worth knowing is that the 48-bit address space is designed with future expansion in mind. Probably today it's unlikely that many machines will have 256TB of physical memory, or that a process will need 256TB of virtual memory. But in the future, as RAM becomes cheaper, and as data sets increase, perhaps some processes will benefit from being able to address that much virtual memory -- and the 64-bit x86 architecture is designed so it's ready for that day.

# Answer
> 1 votes
Who says that the virtual memory is restricted to mapping the local file devices?

When DEC introduced the Alpha, the first mass-market 64-bit processor chip, one idea was to map the whole of any database into VM. I believe that Oracle did/does so. The key to its viability is density of references, so that a good proportion of any realised page is useful.

Similar considerations apply to the page tables themselves. You want/need associative tables that tell you **fast** where in real memory every active realised virtual page lives. Anything else is a waste of space.

No computer has unlimited amounts of anything. And managing virtual memory needs code: inherently imperfect. Your argument explains why it is better to write applications in C than in Java - all that unreliable JVM memory management taking up space and time. Hang on! JVM memory management is an order of magnitude more reliable than anything you or I might write in an application. Similarly, the simplicity of modelling that a large virtual memory can provide may well lead to *improved* reliability. If it didn't have some such benefits, it wouldn't be there.

# Answer
> 0 votes
I don't know what you assume by non-reliable and based on what you decided the virtual memory is not reliable. In operating systems v.m. serves various purposes. This is from Wikipedia:

> The primary benefits of virtual memory include freeing applications from having to manage a shared memory space, increased security due to memory isolation, and being able to conceptually use more memory than might be physically available, using the technique of paging.

# Answer
> -1 votes
Without virtual memory, an attempt to allocate memory can fail. You can check the documentation for your programming language etc. to find out what exactly happens in that case.

With virtual memory, when attempts to allocate memory go beyond available RAM, virtual memory will be used, which will slow things down. If you have 4 GB of RAM, and your applications require 8 GB, the memory allocations will work, but your system will slow down, eventually to the point of unusability. In practice, memory allocations won't fail - the user will just die of boredom or old age before that happens.

Beyond that, it depends on the operating system and/or which strategies it uses. For some OS, memory allocation will fail or succeed, just as with non-virtual memory. For others, allocations will succeed, and then the whole system may run out of memory if an application tries to actually use this memory.

And beyond that, well, life isn't always easy.

---
Tags: computer-architecture, operating-systems, virtual-memory
---


# Question
Title: Generalized Büchi Automata - Formal definition of a state appearing infinitely often?
I am studying generalized Büchi automata and I don't really understand when a state is considered to appear infinitely often. The definition I have is:

A state $s$ appears infinitely often if there exists an infinite set of points $i \in N$ such that the $i$th state of the execution is $s$.

But there's also an example which I think contradicts this definition.

According to the example, the language accepted by this automaton is the language where the string $ab$ appears infinitely often.

Why isn't it just $a$ appearing infinitely often? State 2 would be reached even if we only had $a$ as input. Which is wrong, the example or the definition? Or did I misunderstand the definition?

# Answer
The definition and example are both correct.

If the automaton reads $a$ in state $2$ or reads $b$ in state $1$, then it rejects, because it has no state to go to. So, if the machine reads an infinite amount of its input, then it must read $a$ every time it is in $1$ and read $b$ every time it is in $2$. If the machine reads $b$ only a finite number of times, it only enters $2$ a finite number of times, so it must reject. Therefore, any string that's accepted must contain an infinite number of $b$s. Since $b$s can only be read in state $2$ and the only way of getting there is to read an $a$ from state $1$, any accepted string must contain an infinite number of $ab$s.
> 2 votes

---
Tags: automata, buchi-automata
---


# Question
Title: Lambda calculus :difficulty in getting hang of induction and conversion
I am going through the book on lambda calculus by Hindley and Seldin . They introduce the syntactic equivalence of expressions and proving them by a technique named "induction" , which has not been directly defined in the book .

> (a) $\[N/x\]x \equiv N$
>
> (b) $\[N/x\]a \equiv a$ for all atoms $a \not \equiv x$
>
> (c) $\[N/x\](PQ) \equiv (\[N/x\]P)(\[N/x\]Q)$
>
> (d) $\[N/x\](\lambda x.P) \equiv (\lambda x.P)$
>
> (e) $\[N/x\](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
>
> (f) $\[N/x\](\lambda y.P) \equiv \lambda y. \[N/x\]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
>
> (g) $\[N/x\](\lambda y.P) \equiv \lambda z. \[N/x\]\[z/y\]P$ if $x \in FV(P)$ and $y \in FV(N)$.

The above are the rules given for substitution in the book. I have some difficulty in understanding (d).

Why is it so that $$ \[N/x\] ( \lambda x . p) = ( \lambda x . p) $$ ? How to justify this ? Why can't this be defined to be or equal to $$( \lambda N . p) $$ ?

# Answer
In the definition of substitution $\[N\_1/ x\]N$, we describe how to replace all *free occurrences* of the variable $x$ by the expression $N\_1$ throughout the expression $N$.

The formation rules defining the syntax of $\lambda$-calculus expressions $e$ are

$$ N ::= x \mid \lambda x.P \mid N\_1 N\_2 $$

where $x$ ranges over a set of variables. One should think of the abstraction $\lambda x.P$ as a function with argument $x$ and body $P$ – or using standard programming terminology, we think of it as a procedure with formal parameter $x$ and body $P$.

In $\lambda x.P$, the variable $x$ is not free within $P$, so a substitution $\[N/x\](\lambda x.P)$ cannot change anything.

Moreover, writing $\lambda N.P$ does not make sense; the argument/formal parameter must be a variable.

If you are still puzzled, think of an applied lambda-calculus with integer numerals and consider the expression $\lambda x. x +7$ that informally denotes a function that adds $7$ to its argument. Your proposed substitution rule would give us that $\[14/x\](\lambda x. x+7) = \lambda 14. x +7$. What would that even mean? (I have no idea.)

By the way, the notion of induction is not esoteric at all. Induction is a central proof technique in mathematics and in computer science, and one cannot understand the lambda calculus without being familiar with it. See https://en.wikipedia.org/wiki/Mathematical\_induction for an introduction.
> 7 votes

---
Tags: lambda-calculus
---


# Question
Title: Need clarification about the use of Big-O to describe matrix sparsity
In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around on the net, and only found more such uses that I have an issue with.

To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.

I have the same logical problem with qualifications for graphs sparsity.

But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.

# Answer
What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. For example:

> Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.

What this really means is:

> For every $C \> 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.

The constant hidden inside the big O depends on $C$.

A similar convention explains the following sentence:

> There is a function $f\colon \\{0,1\\}^n \to \\{0,1\\}$ whose maximal influence is $O(\log n/n)$.

(The meaning of *maximal influence* is not important here.) What this really means is:

> There is a sequence of functions $f\_1,f\_2,\ldots$ such that $f\_n\colon \\{0,1\\}^n \to \\{0,1\\}$ and the maximal influence of $f\_n$ is $O(\log n/n)$.

Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.
> 2 votes

---
Tags: graphs, matrices, sparse-matrices
---


# Question
Title: Efficient Algorithm for determining who wins a game of Chess
I was reading Jeff E's lecture notes on Algorithms when I came upon the following question:

Describe and analyze an efficient algorithm that determines, given a legal arrangement of standard pieces on a standard chess board, which player will win at chess from the given starting position if both players play perfectly. \[Hint: There is a trivial one-line solution!\]

My only thought is to form a tree of possibilities and go down every tree to see where it ends. But this is neither one line or efficient. Any help is appreciated(I prefer hints to full solutions, and I will accept a hint as an answer if it leads me to the answer).

# Answer
> 4 votes
When talking about standard chess with an $8\times 8$ board, there is no asymptotics, so you can solve the problem in $O(1)$ time.

Your idea works fine, since for each position the size of the tree is bounded by some constant independent of the input (the tree size is bounded by the number of possible positions). You can now ask whether this solution is feasible or has any practical implications? The answer is obviously no, but when analyzing the asymptotic complexity of the algorithm, this doesn't matter.

---
Tags: algorithms, graphs
---


title: Flow Problem in Tripartite Graph

text:
# Question
Title: Flow Problem in Tripartite Graph
Given a Directed Tripartite graph with 3 Groups of vertices {A, B, C} such that:

1. Edges from A are directed in B.
2. Edges from B are directed in C.

Objective: Minimize the number of vertices in B (by keeping few and deleting the rest) such that every vertex in C is reachable from every vertex in A.

I think this can be converted into a flow problem but i am not sure how to go about it. Anyone ?

# Answer
> 7 votes
The decision version of this problem is NP-hard (and so NP-complete), by reduction from Hitting Set.

Let $S\_1,\ldots,S\_m$ be an instance of hitting set. We will have the following vertices and edges:

* Vertices $A\_i$ for $1 \leq i \leq m$ and $A\_{i,j}$ for $1 \leq i \neq j \leq m$.
* Vertices $B\_u$ for every $u$ in the universe of the hitting set instance, and $B\_{i,j}$ for $1 \leq i \neq j \leq m$.
* Vertices $C\_i$ for $1 \leq i \leq m$ and $C\_{i,j}$ for $1 \leq i \neq j \leq m$.
* For every $u \in S\_i$, edges $A\_i \to B\_u \to C\_i$.
* For every $1 \leq i \neq j \leq m$, edges $A\_{i,j} \to B\_{i,j} \to C\_{i,j}$.
* For every $1 \leq i \neq j \leq m$, edges $A\_i \to B\_{i,j} \to C\_j$.

Every feasible solution to this instance of your problem has to contain each $B\_{i,j}$, since this is the only way to connect $A\_{i,j}$ and $C\_{i,j}$. Hence every $A\_i$ is automatically connected to every $C\_j$ for $j \neq i$. In order to connect $A\_i$ to $C\_i$, we need to have $B\_u$ for some $u \in S\_i$. Hence the minimal solution contains $m(m-1) + k$ vertices iff the hitting set instance has a minimal solution with $k$ elements.

---
Tags: algorithms, graphs
---