# Question
Title: What is a recursion for Huffman encoding?
If I had to write the Huffman encoding as a recursion in terms of the cost $C\_{ij}$, given weights/frequencies $W = \[w\_1,\ldots,w\_n\]$, how would I do it? (where this is creating a minimum cost tree, $C = \sum\_i w\_i \cdot \mathrm{depth}\_i$).

I am going off of Dasgupta's Huffman procedure:

> **procedure Huffman**(*f*)
>
> Input: An array *f*\[1···*n*\] of frequencies
>
> Output: An encoding tree with *n* leaves
>
> let *H* be a priority queue of integers, ordered by *f*
>
> for *i* = 1 to *n*: insert(*H*,*i*)
>
> for *k* = *n*+1 to *2n*–1:
>
> *i* = deletemin(*H*), *j* = deletemin(*H*)
>
> create a node numbered *k* with children *i*,*j*
>
> *f*\[*k*\] = *f*\[*i*\] + *f*\[*j*\]
>
> insert(*H*,*k*)

It should be something like the matrix multiplication order minimization algorithm, which seeks to minimize the total number of components calculated when multiplying a string of matrices,

$$ C\_{ij} = \min(C\_{ik} + C\_{k+1,j}+(m\_i-1) \cdot m\_k \cdot m\_j) $$

Where $m\_i,m\_j$ are the dimensions of the matrix multiplication at the level directly below the node...

I wrote something like:

$$ aC\_{ij} = \min((a+1)C\_{ik} + (a+1)C\_{k+1,j}),\text{ for all } i,j,k $$

With base case: $C\_{ii} = w\_i$

Knowing full well that this is probably incorrect. But I don't understand how I should write it. I mean, I have the algorithm fine—just Huffman + DFS afterward (which always turns left, then right) to find out the order of the elements. But I don't understand how the recursion notation works in this situation.

# Answer
> 1 votes
Huffman's algorithm uses the greedy heuristic, which is different from the dynamic programming approach in the other problem you mention. However, we can still define the cost recursively.

There are actually several options. In all cases, given a distribution $p\_1,\ldots,p\_n$, we will find a formula for $C(p\_1,\ldots,p\_n)$, which is the optimal cost of a prefix code.

Let's start with Huffman's algorithm itself:

1. $C(1) = 0$.
2. $C(p\_1,\ldots,p\_n) = p\_i + p\_j + C(p\_1,\ldots,\widehat{p\_i},\ldots,\widehat{p\_j},\ldots,p\_n,p\_i+p\_j)$, where $p\_i,p\_j$ (for $i \< j$) are the two smallest probabilities (i.e. $\max(p\_i,p\_j) \leq p\_k$ for all $k \neq i,j$), and $\widehat{p\_i}$ signifies that $p\_i$ is removed.

The proof that this recurrence is correct is not immediate.

If we want a Huffman-like recurrence whose correctness is immediate, we need to tweak this only slightly:

1. $C(1) = 0$.
2. $C(p\_1,\ldots,p\_n) = \min\_{i\<j} \[p\_i + p\_j + C(p\_1,\ldots,\widehat{p\_i},\ldots,\widehat{p\_j},\ldots,p\_n,p\_i+p\_j)\]$.

This recurrence holds since (i) given a code for $p\_1,\ldots,\widehat{p\_i},\ldots,\widehat{p\_j},\ldots,p\_n,p\_i+p\_j$ we can get a code for $p\_1,\ldots,p\_n$ which is worse by $p\_i+p\_j$ by splitting the node corresponding to $p\_i+p\_j$ into two, and (ii) given a code for $p\_1,\ldots,p\_n$, if we choose any two sibling leaves $p\_i,p\_j$ then $C(p\_1,\ldots,p\_n) = p\_i + p\_j + C(p\_1,\ldots,\widehat{p\_i},\ldots,\widehat{p\_j},\ldots,p\_n,p\_i+p\_j)$.

A short reflection reveals that we can always ensure $j = n$ (say), and this leads to a simpler recurrence:

1. $C(1) = 0$.
2. $C(p\_1,\ldots,p\_n) = \min\_{i\<n} \[p\_i + p\_n + C(p\_1,\ldots,\widehat{p\_i},\ldots,p\_{n-1},p\_i+p\_n)\]$.

The last two recurrences are bottom-up. There is also a top-down recurrence:

1. $C(1) = 0$.
2. $C(p\_1,\ldots,p\_n) = 1 + \min\_{S \sqcup T = \[n\]} \[C(p\_S) + C(p\_T)\]$, where the minimization is over all partitions of $\\{1,\ldots,n\\}$ into two non-empty sets, and $p\_S = (p\_i : i \in S)$.

In this recurrence we are splitting the root instead of merging two sibling leaves. I leave to correctness proof for the reader.

Only the first recurrence above can be implemented efficiently.

---
Tags: algorithms, recursion, huffman-coding
---


# Question
Title: Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?
If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to state the complexity is amortized $O(n\log n)$?

I have a tree building algorithm - when adding elements a rebalancing operation occurs every so often, with those operations getting progressively more expensive as the tree size grows close to a power of two elements (before becoming cheaper again once we pass such a power). At every power of two elements its easy to state the number of steps done so far but in between it's not so easy.

I'm slightly embarrassed by this question as I currently assume it is OK to state an amortized time of $O(n\log n)$ for this situation but my conclusions, from reading a discussion elsewhere (see next part), seemed to contradict this.

---

**Update**: I've move the second part of part of this question, relating to Conc-tree lists and my confusion over how such trees could be built in $O(n)$, into a separate question.

# Answer
You are asking several questions. I will only answer some of them.

Suppose that the running time of an algorithm as a function of $n$ satisfies $T(2^k) = O(2^k \log 2^k)$. Is it true that $T(n) = O(n \log n)$? Without any more information on the running time, this is patently false. For example, consider the function $$ T(n) = \begin{cases} n\log n & \text{if $n$ is a power of $2$}, \\ n^2 & \text{otherwise}. \end{cases} $$ However, in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold. Suppose that $T(n) \leq Cn\log n$ whenever $n$ is a power of $2$. Given arbitrary $n$, we can find $m \leq 2n$ which is a power of $2$, and then $$ T(n) \leq T(m) \leq Cm\log m \leq 2Cn \log n + O(n) = O(n\log n). $$

Suppose now that there is a data structure such that the first $n$ operations take time at most $Cn$ whenever $n$ is a power of $2$. If we let $T(n)$ denote the maximal time that $n$ operations take, then $T$ satisfies the conditions stated above (in particular, monotonicity is built-in), and so the amortized time per operation is indeed $O(1)$. Your case is a bit more complicated since different operations have different amortized running times, but the conclusion should be the same.
> 4 votes

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


# Question
Title: Pittsburgh approach, how does encoding and fitness function work?
I am writing a genetic algorithm for Machine learning and came across Pittsburgh approach in some research papers. The papers didn't explain the algorithms proper or I am too stupid to understand. I know that each Individual contains set of rules and I have also implemented in binary but am having trouble with 6 float type values. My question is:

* How am I generating uncertainty value in the genes?
* How will I be using encoding with real/floating type values?
* How is the fitness function going to work?

I would love to it also if you could send me references to which I might be able to better understand the algorithm. I will be using float number so no binary methods or explanation.

# Answer
> 1 votes
So both the Pittsburgh and Michigan approaches are techniques for applying evolutionary methods to learning (essentially) a set of "if/then" rules for performing some task effectively. The important bit is the "set" there in "set of rules". You need to learn multiple rules that can each fire in different situations in order to cover the entire space of behaviors the algorithm needs to learn. Where the Pittsburgh and Michigan approaches differ is in how you arrive at that set of rules.

They're both GAs under the hood, so there's a population of things. In the Pittsburgh approach, those "things" are complete candidate solutions to the problem. A single individual in a Pittsburgh algorithm might contain many rules. A single individual in a Michigan approach contains only one rule. In order to form a viable actual algorithm for solving the problem, the Michigan approach needs to take the entire population and hope that each of those individuals with their individual rules combine together in a way to cover the problem space well.

Under the hood though, as I said, they're basically just GAs. So you can do recombination and mutation however you like. You can handle floating point genes the same way you'd handle them in any other GA -- perhaps by using variation operators that natively work on floats or by encoding the values as binary yourself. Fitness in Pittsburgh systems can be reasonably straightforward. Every individual is intended as a complete solution, so you just run your simulation and calculate how well that individual's rule set solves the problem. The answer is that individual's fitness. For Michigan approaches, it's harder, because there's a credit assignment problem. One individual encodes one rule, and that rule may be perfect for its niche, but if the rest of the population is terrible, performance will be poor.

Another problem is that the structure inherent in classifier systems like this means that typical genetic operators won't necessarily work that well. You can use them, but tweaks to the ideas can perform quite a bit better. The Learning Classifier Systems community has done quite a bit of work figuring this stuff out. My general advice would be to start by looking at Stewart Wilson's XCS algorithm.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.2210&rep=rep1&type=pdf

http://opim.wharton.upenn.edu/~sok/papers/b/XCSAlgDesc01202001.ps

---
Tags: algorithms, machine-learning, genetic-algorithms
---


title: Growing a set given constraints

text:
# Question
Title: Growing a set given constraints
I am trying to solve the following:

Given a set $S\_0$, find min $|S|$ where $S\_0 \subseteq S$ subject to:

$\forall s \in S$ $\exists$ $s\_a, s\_b \in S $ $|$ $ ( s\_a \neq s, s\_b\neq s ) \land ( s = s\_a + s\_b \lor s = 1 \lor s=2 ) $

Or in english, forall s in S there exists sa, sb in S such that sa != s, sb != s AND ( s = sa + sb OR s = 1 OR s = 2 )

For example if $S\_0 = \\{ 7, 9, 13, 22 \\}$ then the solution is $S = \\{ 1, 2, 3, 4, 7, 9, 13, 22 \\}$ as

```
1 -> is 1 so allowed
2 -> is 2 so allowed
3 = 1 + 2
4 = 1 + 3
7 = 3 + 4
9 = 7 + 2
13 = 9 + 4
22 = 9 + 13
|S| = 8

```

$|S\_0|$ is not particularly large but the numbers in $S\_0$ can be very very large such that expressing all numbers possible is infeasible.

I have tried an ILP and ran out of memory expressing the binary variables for each number in the set.

My current approach ( which gives a pretty bad solution ) is pick the lowest number that is violated, heuristically pick two numbers and put them in the set. Repeat until all numbers meet constraints.

An approximate solution is fine. Anyone have any ideas?

# Answer
I suggest you formulate this as an instance of integer linear programming (ILP). Let $m$ be the largest number in $S\_0$. For each $i$ such that $1 \le i \le m$, introduce the zero-or-one variable $x\_i$, with the intended meaning that $x\_i=1$ means that $i \in S$ and $x\_i=0$ means that $i \notin S$.

Now your constraints can be readily converted into linear inequalities: e.g., for each $s$ such that $2\<s \le m$, we obtain that $x\_s=1$ implies $\lor\_{s\_a,s\_b} (x\_{s\_a}=1 \land x\_{s\_b}=1)$, where the disjunction is taken over all $s\_a,s\_b$ such that $1 \le s\_a \< s$ and $1 \le s\_b \< s$. This can be converted into a linear inequality; see Express boolean logic operations in zero-one integer linear programming (ILP). Also, for each $i \in S\_0$, we add the requirement $x\_i=1$. Finally, we minimize $\sum\_i x\_i$. Feeding this to an off-the-shelf ILP solver should yield a solution.

This should find the exact optimal solution, as long as the largest number in $S\_0$ is not too large. However, the running time is potentially exponential in $m$, the largest number in $S\_0$. I don't know if there is a polynomial-time solution.

(You could also formulate it as an instance of SAT instead of ILP. This will require applying the Tseitin transform to convert the implication/disjunction into CNF, and it will require constructing an adder-circuit to add the requirement that the size of $S$ is at most $k$ and then doing binary search over $k$. Then, you could feed it to an off-the-shelf SAT solver. I have no idea whether this will work better than the ILP approach.)
> 2 votes

# Answer
If you list the numbers in increasing order, then this is the problem of finding a minimum-length addition chain. According to that article, this problem was proved NP-complete here *for a set of numbers* (as in your case), though it appears the complexity status is still open for a single number.

The Wikipedia page also gives links to some other articles, for example this one, whose abstract says that they can compute optimal addition chains for all $n \le 2^{32}$.
> 2 votes

---
Tags: optimization, discrete-mathematics, set-cover
---


# Question
Title: which error is it - a semantic error or a link error?
I am having a simple doubt in C programming language.

**In any simple C code snippet, if by mistake suppose i have written intmain()** **instead of main().**

Then it represents what type of error ?

---

It will not be a lexical error as compiler will correctly make a token for it and it is also not a syntax error clearly.

I think it is a semantic error as in this phase compiler checks with the meaningful statements, scoping, binding, variable not declared, function not declared, any variable declared twice, etc.

---

But, on the other hand, I also think it as a linker error as in the semantic phase, it can throw a error that function intmain() is not declared and it is been directly used.

---

**Can anyone make this crystal clear that what is the actual error ?**

# Answer
We can reproduce your error using this C++ code:

```
intmain() {
    return 0;
}

```

The following error is returned during compile time:

```
error: ISO C++ forbids declaration of ‘intmain’ with no type [-fpermissive]

```

Every function in C/C++ has to have a type. In this sense, it's a type error, which falls in the category of (static) semantic errors. On the other hand, your error is caused by a typo. This sort of error is considered a lexical error, which falls under syntax errors.

There is a lot of discussion whether certain errors are syntactical or static semantic. My opinion is this case is that the error is lexical, considering the cause.
> 1 votes

---
Tags: compilers
---


# Question
Title: Comparing two recurrence relations w.r.t. asymptotic growth
I have two functions $T\_1(n),T\_2(n)$. How do I decide which is asymptotically faster?

One is given by the recurrence relation

$$ T\_1(n) = \sqrt{n} T\_1(\sqrt{n}) + 3 n, \quad T\_1(1) = T\_1(2) = 1. $$

The other is given by the recurrence relation

$$ T\_2(n) = 3 T\_2(n/3) + 2n \log n, \quad T\_2(1) = T\_2(2) = 1. $$

For the first function I guess there is $O(\sqrt{n} \cdot \sqrt{n})$ for loop, and $O(n)$ for the $c$; which becomes $O(n^2)$ in total.

For the second one, the Master's theorem is applicable, but as I assume the complexity becomes $O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$ for loop, and $O(n\log n)$ for $c$.

So if I am comparing both $O()$'s, we can in total see that

$$ O(n^2) \< O(n^2 \cdot \log n) $$

Was there any mistake, or is this not how recurrence unrolling is done?

# Answer
You can sort of get a feel of the asymptotic behavior of a recurrence by flatting out the recurrence into an equivalent problem of the form $A\_k = c\_1(k) A\_{k-1} + c\_2(k)$.

First of all, to see that $O(n^2)$ is an extremely loose bound, notice how $T\_1(16)$ expands out: \begin{align\*} T\_1(16) &= 4 T\_1(4) + 3 \cdot 16 \\ &= 4 (2 T\_1(2) + 3 \cdot 4) + 3 \cdot 16 \\ &= 8 + 2 \times (3 \cdot 16) \end{align\*} Similarly, you'll find that $T\_1(256)$ expands out to \begin{align\*} T\_1(256) &= 16 T\_1(16) + 3 \cdot 256 \\ &= 16 (8 + 2 \times (3 \cdot 16)) + 3 \cdot 256 \\ &= \frac{256}{2} + 3 \times (3 \cdot 256) \end{align\*} This strongly suggests that $T\_1(2^{2^k}) = 2^{2^{k-1}} + 3k 2^{2^k}$, or $T\_1(n) \approx \frac{n}{2} + 3 n\log\_2 \log\_2 n$. We can show this by first relaxing the domain of the function to those of the form $2^{2^k}$. Since $\sqrt{2^{2^k}} = 2^{2^{k-1}}$, we have $$ T\_1(2^{2^k}) = 2^{2^{k-1}} T\_1(2^{2^{k-1}}) + 3 \cdot 2^{2^k} $$ Let $A\_k = T\_1(2^{2^k})$, then \begin{align\*} A\_k &= 2^{2^{k-1}} A\_{k-1} + 3 \cdot 2^{2^{k}} \\ &= 3 \cdot 2^{2^{k}} + 2^{2^{k-1}}(3 \cdot 2^{2^{k - 1}} + 2^{2^{k - 2}}A\_{k-2}) \\ & \cdots \\ &= 2^{2^{k - 1}}A\_{0} + 3 \cdot 2^{2^{k}} + 3 \cdot 2^{2^{k}} + \stackrel{k}{\dots} + 3 \cdot 2^{2^{k}} \end{align\*}

which shows that when $n = 2^{2^k}$, then $T\_1(n) = \Theta(n\log\log n)$. Suppose we now open $T\_1(n)$ over the whole real domain (that is, we relax the domain restriction imposed previously), then it should be easy to show that if $T\_1(x) = 1$ whenever $x \in \[1, 2\]$, then $T\_1(n) = \frac{n}{2} + 3n \log\_2\log\_2 n$ extends uniformly. (Proof: Use the same derivation above, but for some other $p \in \[1, 2\]$, do the case analysis on $p^{2^k}$ instead)

Therefore, we have $T\_1(n) = \Theta(n \log\log n)$ and $T\_2(n) = \Theta(n^2 \log n)$. Asymptotically, $T\_2$ still dominates $T\_1$.
> 2 votes

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


# Question
Title: Algorithm for finding best match between two database rows
Let's say we have a database with a given table named food. The food table has many columns but we are interested in only 3 of them:

1. `buyorsell`, which specifies if the food is for selling or buying.
2. `amount`, which is the amount of food to be bought or sold.
3. `isVegan`, which is set true if the food is vegan.

The goal is to find the best match between 2 rows. The best match should satisfy the following rules:

1. Both rows have the same value for 'isVegan'
2. One row should be buy/sell and the other row must be the opposite
3. Both amounts must be equal

The table will have millions of rows and the table is changing rapidly.

What is the right algorithm in matters of speed and resource usage for this matching problem?

# Answer
> 1 votes
Assuming we're talking about a relational database, a straightforward query would be to do a theta-join on two copies of the *food* relation, renamed $a$ and $b$, with the condition $$ \theta = (a.isvegan)\land\neg(a.buyorsell=b.buyorsell)\land(a.amount=b.amount) $$ Without knowing the internal workings of the DB engine, your question about the "right" algorithm to use is impossible to answer. For instance, does the engine use, say, merge join or hash join to answer the query; is the table sorted by some attribute, do you have indexes to help you, if so how are they implemented?

---
Tags: databases, matching
---


# Question
Title: Discrete Math/Logic Problem used in Computer Science Class: Who Robbed the National Bank?
The following question is supposed to give you insight on how to maintain logic when making programs. Please be open minded as this may not look like a Computer Science Problem, but it definitely contains logic that you will use when making If statements and Booleans, so PLEASE keep that in mind.

## Who Robbed the National Bank?

Inspector Malone knows that the culprit is one and only one of the following: Alex, John, or Sally. He interrogates them. Each makes two statements.

Alex: "It wasn't me." "John did it."

John: "Listen, Alex did it.""And Sally did it."

Sally: "I didn't do it." "Neither did Alex."

Each has made one TRUE statement and one FALSE statement. Who did it?

# Answer
Let's look over each statement one at a time. Keep in note that each person has a statement which is FALSE, and a statement which is TRUE.

Alex said it wasn't him. John did it.

If Alex was telling the truth that it wasn't him, he can lie about John doing it, which leaves Sally.

In the other case, he lies that it wasn't him, BUT John did it. This is logically impossible, because only one person did it.

So far it looks like Sally's pretty guilty! Let's go to the next statement.

John says Alex did it and so did Sally. If he tells the truth about Alex but lies about Sally, then Alex OR HIMSELF did it. Vice versa, then Sally OR HIMSELF did it.

Last statement. Sally says she didn't do it but neither did Alex. If she told the truth she didn't do it, then Alex did it. If Alex didn't do it, Sally did it.

To sum up, let's look at each statement again.

Alex: 1st Statement: If true, Sally did it. 2nd Statement: If true, logically impossible.

Going off of JUST Alex's statement, we can already confirm that Sally did it.
> 1 votes

---
Tags: discrete-mathematics
---


# Question
Title: Prove correctess of recurrence result by mathematical induction
I have the following recurrence relation which I already solved using repeated substitution.

$T(n) = \begin{Bmatrix} 1 & if & n = 1\\ 4T(\frac{n}2) + n & if & n \>= 2 \end{Bmatrix} where$ $n=2^k$

The result I get is $T(n) = 2n^2 - n$
Let´s suppose my result is correct. Now, I am asked to prove the correctness of the result using mathematical induction.

Base case is easy:
For $n = 1$ we have $T(1) = 2(1^2) - 1 = 2 - 1 = 1$
This result agrees with initial formulation of the problem above.

Now, comes the $Inductive$ $Hypothesis$ which I guess is as follows:
Assume this holds for $2 \<= k \<= n$
$4T(\frac{k+1}2) + (k+1) = 2(k+1)^2 - (k+1)$

Am I doing things correctly?
How would the $Induction$ $Step$ would be?
I will very much appreciate your feedback.

# Answer
> 2 votes
We prove by induction that for every $n\in\mathbb{N}$ it holds that $T(n)=2n^2-n$. The inductive hypothesis is that for all $1\le k\<n$ we have:

$T(k)=2k^2-k$.

We proceed to show that $T(n)=2n^2-n$.

By definition, $T(n)=4T\left(\frac{n}{2}\right)+n$. Since $\frac{n}{2}\<n$, we can use our inductive hypothesis and obtain $T\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2-\frac{n}{2}$. After substituting this back into $T(n)$ we have:

$T(n)=4\left(\frac{n^2}{2}-\frac{n}{2}\right)+n=2n^2-n$.

# Answer
> 0 votes
In another "form". First we state an inductive hypothesis: $$\forall 1 \le k \quad T(k) = 2k^2 - k$$

So we have to prove that: $$T(k + 1) = 2(k+1)^2 - (k + 1) $$

So: $$\begin{align} T(k + 1) &= 4T\left(\frac{k+1}{2}\right) + (k + 1)\\ &\stackrel{by \\, IH }{=} 4\left\[2\left(\frac{k+1}{2}\right)^2 - \frac{k + 1}{2}\right\] + (k + 1)\\ &= 4\left(\frac{k^2 +1 + 2k}{2} - \frac{k + 1}{2}\right) + (k + 1)\\ &= 2(k + 1)^2 -2k - 2 +k + 1\\ &= 2(k+1)^2 - (k + 1) \end{align}$$

---
Tags: recurrence-relation, induction
---


# Question
Title: Lower-order term constraints and wrong guess
I'm a self-taught and I'm studying from CLRS. I'm having difficulty with this recurrence relation: $$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$

The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd. My inductive hypothesis about $\mathcal{O}(n)$ is: $$\exists c \gt 0 \\,\\,\exists n\_0 \gt 0 \\,\\,\exists b \ge 0 \quad\forall n\_0\le k\lt n \quad T(k) \le ck - bn \le ck $$

From here I haven't problem during the "proof": $$\begin{align} T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n \\ &\le 3\left(c\frac{n}{2} - bn\right) + n \\ &= \frac{3}{2}cn - 3bn + n \\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st) \\ &\le cn \end{align}$$

The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from: $$\frac{3}{2}cn - n(3b - 1) \le cn$$

**--EDIT--**
It's also easy to prove that $$(1st) \le cn - bn$$ It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$ **--END EDIT--**

So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.

**Synthesis**: https://cs.stackexchange.com/questions/65549/lower-order-term-constraints-and-wrong-guess/65579?noredirect=1#comment139380\_65579

# Answer
First of all, the way you state the induction hypothesis is a bit strange, and it definitely doesn't prove that $T(n) = O(n)$. Assuming that the induction is on $n$, what your induction hypothesis states (more or less) is that for every $n$ there exists $C$ such that $T(k) \leq Ck$ for all $k \leq n$. The function $T(n) = n^2$ satisfies this, with $C = n$.

What you really want to do is to fix the parameters $b,c,n\_0$ in advance. In other words, you want to prove $$ \exists b,c,n\_0 \\, \forall n \\, \forall n\_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ You first instantiate $b,c,n\_0$, and then you prove only the following part by induction: $$ \forall n \\, \forall n\_0 \leq k \leq n\colon T(k) \leq ck - bn. $$ At each step of the induction, you are proving $$ \forall n\_0 \leq k \leq n\colon T(k) \leq ck - bn $$ for the current value of $n$.

Now for your mistake. Your induction hypothesis states that for all $k \leq n$, $$ T(k) \leq ck - bn. $$ However, in the inductive step, you only prove $$ T(k) \leq ck. $$ Also, you only prove it for $k = n$, despite the form of your actual induction hypothesis.

Indeed, it is very strange that your inductive hypothesis gives an upper bound on $T(k)$ *which depends on $n$*. This is quite unorthodox. Usually the upper bound only depends on $k$. Moreover, you are not really subtracting a *lower-order* term: $n \neq o(k)$!

Here is what an application of subtracting a lower-order term usually looks like. Suppose that we want to prove that $T(n) = O(n)$. Then you find $b,c,n\_0$ and prove the following by induction:

$$ \forall n \geq n\_0\colon T(n) \leq bn - c\log n.$$

Note that there is no $k$ here, and that $\log n = o(n)$ is indeed of lower order.
> 2 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: A variant of travel salesman problem in grid graph
In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. The problem is to determine the starting position and the directions of robot so it can cover the whole grid (also in some situations there can be no solution). An example of this game is shown below, where the starting position is chosen to be near the lower right corner, in this example, robot fail to cover the whole places. The movement constraint of robot is similar to ricochet robot but this robot can only visit a place once. I want to know if this problem has been studied before and if there is efficient algorithm to solve it. Currently I just use depth first search to attack this problem, which is quite slow on a large grid. I think this problem can be transformed into a boolean satisfiability problem. I found that this problem is called full house and is published by Erich Friedman.

# Answer
> 2 votes
This is similar (but not identical) to the game Zen Puzzle Garden. The important difference for the purposes of your question is that in ZPG you can also have “walkable” squares which the robot (or rather monk, in that game) can walk freely across without leaving a trace.

It is known that ZPG is NP-complete, but our proof makes critical use of these walkable squares and so it does not extend to this problem.

When I was working on the proof above, I spent some time thinking about whether it was possible to show NP-hardness without using walkable squares, but without success. As far as I know the question is still open.

---
Tags: algorithms, graph-traversal, traveling-salesman
---


# Question
Title: Maximum # of nodes with maximum 3-distance in ternary tree
how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3?

if the maximum distance was 1, the answer would be 4.

# Answer
For a maximum distance of 3, your number of nodes would equal 7 or 8.

I read your question in such a way, that even the distance from one arbitrary node to another is at maximum 3. You get seven nodes if you imagine the following: The root node and the parents are a full tree with a total of four nodes, which equals your result for maximum distance 1. If you now add a single node to one of the child nodes, you immediately jump to a distance of 3, since you now can go from this child's child node to another child node via the root node. The only options to add other nodes to this tree is now to fill the child section of the node you already started with. Some exemplary tree could look like this:

```
  1
/ | \
2 3  4
    / | \
   5  6  7

```

Another possible solution is assuming that you do not have to fill up your root level before starting another level, so you could add another root node which is only linking to one other node (which would be the root node of the first solution, looking like this:

```
  1
  |
  2
/ | \
3 4  5
    / | \
   6  7  8

```

Your result would obviously differ if it was only concerning the distance from your root node to the furthest child (which is usually more common in trees), but I hope this is a satisfying answer.
> 0 votes

---
Tags: algorithms, optimization, trees, clique
---


# Question
Title: Is there a general pattern/structure/format to most (if not all) computer functions?
First time posting.

I know this is a very generalized question, sorry for that, I don't know how to more appropriately word this.

I've noticed a tread, a pattern in methods, it seems in almost all methods, for example, in Java (haven't programmed much in other languages although I would imagine it's the same) the method seems to share a general pattern in their creations.

It's something on the order of: \- Create local variables to store/copy things from instance variables \- Create a loop to iterate through things \- Create a series of if statements/conditions, possibly accessing premade methods \- Check for any sort of possible exceptions/problems along the way \- Return the desired output of the operations from the above

And all the other aspects such as polymorphism, recursion, interfaces, inheritance seem to be conceptual features/additions to the codes performance and functionality

Is this true? I know that each method is unique and a special combination of the above is probably require. Generally speaking do most methods follow a pattern? Is there a better way of writing out the above list, in a more formal way?

Thank you, I appreciate you taking the time to read this post.

# Answer
A method is just a precise sequence of instructions (in the ordinary English-language sense of the word) of how to perform some specific task. It's certainly true that many tasks – and I mean this in a completely general sense, not just computer programs but things like recipes, travelling to work, repairing a bicycle, building a house – follow a general pattern of "get things ready, do the main part of the work, then tidy up." However, there's no reason that all tasks must follow this pattern, and certainly not at the level you suggest of looping, then doing conditionals, then returning something. In general, methods do whatever it is that they need to do to accomplish the specific task at hand: ultimately, everything really is its own unique snowflake.

Having said that, we should note that we could, in principle, force everything to have a particular pattern. The CPU itself is essentially a loop of "read the next instruction, obey that instruction" where a particular effect of obeying an instruction might be to change what the "next instruction" will be – that would be a jump or goto. So, in principle, we could write every program in this style. However, people find this kind of program extremely difficult to write, understand and debug so, in practice, we use higher-level languages, and use compilers and/or interpreters to translate them into terms that the CPU understands.
> 2 votes

---
Tags: java
---


# Question
Title: Heuristic algorithms for the dense assignment problem
Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or variants.

However, if $n$ is large, $O(n^3)$ may not be feasible from a timing perspective. Moreover, storing the complete $n^2$ cost matrix may require a prohibitive amount of memory.

Are there heuristic algorithms that give "good enough" solutions, with are significantly faster? I have seen some algorithms that claim to be faster, but they assume the number of edges is smaller than $O(n^2)$, which is not true in the dense case.

# Answer
> 5 votes
This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$):

1. Deterministic time $O(n^2 \sqrt n \log N)$.
2. Randomized $O(n^{2.373} N)$.
3. $(1 - \epsilon)$-approximation in $O(n^2 \epsilon^{-1} \log N)$.

These algorithms are mostly very complex and go through $LP$ formulations. It is unlikely that any of them are truly what you're looking for. Also, regarding their use of space, I am not sure, but you can follow the papers for the different algorithms and see for yourself, if you can make them work in less space. (By the way, isn't your cost function already using quadratic space?)

If you want a heuristic with no provable guarantees, then I recommend the simple local search. You basically start with some random permutation (this is a feasible assignment, since your bipartite graph is complete) and make random swaps that improve the cost. If you do many such searches, you get a good solution more often then not. You can make the whole thing run in $O(t (n + s))$ time and linear space, if you do $t$ searches (from random permutations), each for $s$ steps. Choose $t, s$ to trade-off quality of the solution with complexity.

---
Tags: optimization, approximation, heuristics, assignment-problem
---


# Question
Title: Assigning a unique representation to equivalent circular queues
First, a few vague definitions:

**Circular queues** (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle"). wikipedia

Let's say that **2 circular queues are equal** if they have the exact same elements in them and the order of items in them are exactly the same.

Example: if we form a circular queue from the string "**absa**" and one from "**bsaa**", the two will be equivalent.

My task is to group together "cyclic equivalent" strings. I'm trying to find a "base representation" for all "cyclic equivalent" strings to use it as an "index" in a hash table which would make grouping them more efficient.

**Help me find an algorithm that can assign a single unique representation to all equal circular queues!**

* is it even possible? (let alone useful?)
* what about problematic ones like "asdasd"? (see balanced bike wheel analogy)

Some ideas to base the algorithm on:

* bicycle wheel analogy: Imagine your bike's wheels have colored spokes, all kinds of colors, each color having a different weight (terrible idea for everyone except for computer scientists). If you flip your bike upside down letting the wheel spin freely, the part of the wheel with the most torque will rotate to the bottom and the wheel will stay in that "base position" and that bottom point of the wheel could be called its "base index". If we recorded the order of the colored spokes starting at that point, that order could be called a linear "base representation" of the wheel. This would not happen in the case of a properly balanced wheel, which would not start rotating. What could we do in that case?
* ?

Some practical use cases:

* finding equivalent circular transportation routes on a map (like those of public transportation) regardless of starting and ending point
* ?

# Answer
Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then any two equivalent queues will get the same representative / same index.

If the queue has $n$ items, implementing this naively takes $O(n^2)$ time. However, it can be done more efficiently. When the contents of the queue are random, sorting the rotations lexicographically, using a string comparison operator that only compares as much of a prefix as necessary to find the first mismatch, will have running time $O(n \log^2 n)$. If you want to get more fancy, you can do it in $O(n)$ time, using a suffix tree or suffix array; though the constant factors and implementation complexity probably won't make this worthwhile unless your queues are extremely large.
> 11 votes

# Answer
This is a variant of the tandem repeats problem. Such a problem can be attacked via (generalized) suffix trees. This problem is strongly related to the lexicographically minimal rotation problem, for which there are fast algorithms different from the below. A more thorough description of the below appears in chapter 7 of Gusfield's "Algorithms on Strings, Trees, and Sequences".

Since every suffix of any (once through) cyclic representation of a circular queue is a prefix of any matching (once through) representation of a circular queue, construct a (generalized) suffix tree on a (twice through) cyclic representation where each character of the second copy of the string (and only those characters) are treated as terminal characters.

In your "asdasd" example, the resulting tree will have path length$^\*$ three, will have three leaves, all terminal, and all of its leaves will have a pointer to the root. This is adequate evidence that your primitive cyclic string may be taken to be "asd".

Then, take the canonical string to be constructed iteratively from the root: at each node, sort the labels on the children's edges and select the edge that sorts least. Stop when you reach a (automatically terminal) leaf.

Constructing the tree for a cyclic representation of length $n$ takes $\Theta(n)$ time and space and reading out its canonicalization cannot take longer or more space. Thus, we have a $O(n)$ solution in both time and space.

$\*$: Since edges may have labels of arbitrary length, the useful definition of path length in this tree is not the number of edges, but the total of the lengths of the edge labels along the path.
> 4 votes

# Answer
Always use minimal lexicographic word to put into your hash. There is a special algorithm for that purpose called Booth's algorithm, which runs in $\mathcal O(n)$ time.
> 3 votes

---
Tags: data-structures, strings, queues
---


# Question
Title: Can we do better than $O(n\log n)$ building a balanced binary tree?
I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?

Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. If these properties hold then it seems *to me* that it must be possible to build a balanced binary tree in better than $O(n\log n)$ time.

I don't believe this so I'm wondering where the flaw is in my thinking.

The data-structure is the conc-tree list. In it's standard form it looks like a normal binary tree and comes with a `concat` operation that ensures the invariant that the left and right subtrees of any node never differ in height by more than one. As expected `concat` has complexity $O(\log n)$.

But there's a builder variant of the conc-tree list called the `Append` list. This variant allows for temporary height differences in subtrees of more than one. Amortized $O(1)$ time appends are claimed for this variant.

So it seems appending $n$ elements must have a complexity of $O(n)$.

However it's a characteristic of this variant that whenever $n$ is a power of two one ends up with a complete balanced binary tree (containing all elements inserted so far). So while temporary imbalances are allowed the tree becomes balanced every power of 2 insertions.

In this variant a new class of nodes, called `Append` nodes, are introduced and it's these nodes whose subtrees are allowed differ in height by more than one. However every $2^k$ insertions all such temporary nodes are eliminated.

The Wikipedia page page describes the algorithm fairly succinctly (see the description of the basic data-structure and the `append` method in particular).

So when $n$ is a power of two our cost for inserting elements is $O(n)$ and we've built a balanced binary tree. Or so it seems.

In a separate question I effectively asked "if I can state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, is this enough to allow me to state the complexity for all values of $n$?"

I can see from Yuval Filmus's answer that the answer is no, but that "in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold."

So it seems to me that in this case if inserting $n$ elements has complexity $O(n)$ and every $2^k$ elements I have a balanced binary tree then the cost of building balanced binary trees with this conc-tree variant approach must be $O(n)$.

So what's wrong here? To be honest I can't see the amortized $O(1)$ append time claimed for this variant. I can see that often insertions do have cost $O(1)$ but that when one looks at what's happening with the temporary `Append` nodes the overall insertion cost looks to me to be amortized $O(\log n)$.

If this is the case then building our balanced binary tree has an unsurprising $O(n\log n)$ cost.

Sorry for such a long question and sorry for not going into detail about the algorithm in question - instead leaving you to look around on Wikipedia.

# Answer
> 7 votes
If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:

```
L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
  n = q.pop
  if k < L.size:
     n.left = node{value=L[k]}
     k++
     q.add(n.left)
  if k < L.size:
     n.right = node{value=L[k]}
     k++
     q.add(n.right)

```

It is not hard to see that this code does run in linear time and builds a balanced binary tree.

What you cannot do, is build a balanced binary **search (ordered)** tree in $O(n)$ time (using only comparisons on the values). The algorithm above does not guarantee that the value on the root is greater than or equal to every value in the left sub-tree and is less than or equal to every value in the right sub-tree, for every sub-tree.

The algorithm above does not guarantee it and neither does the conc-tree (using appends and prepends). From the wikipedia page, it only guarantees $O(1)$ amortized time for **appends** and **prepends**. For inserts, it can only guarantee $O(\log n)$ time.

# Answer
> 7 votes
Adding to aelguindy's answer: You just can't put n unsorted items into *any* kind of data structure, and then enumerate them in sorted order, in better than O (n log n) total time - because if you could, then you could sort an array in better than O (n log n) time.

If we define a "sorted" data structure as any data structure that can be enumerated in sorted order in O (n) time, then we can't create any sorted data structure faster than in O (n log n). That would include sorted trees, both balanced and unbalanced.

---
Tags: complexity-theory, algorithm-analysis, data-structures, time-complexity, search-trees
---


# Question
Title: recursion code counting down and counting up
My apologies in advance if this is going to cause further confusion. So, I wrote a very simple recursive method shown below. As you see line # 3 keeps track of value of n before recursive call and line # 5 keeps track of n after recursive call. As you can see both lines # 3 and 5 are printed to see the change in n value. *I am puzzled why line 5 is printed in increments of one six times where n value goes from 0 to 5 as the unexpected (to me) output shows: "after: n: 0" ... "after: n: 5".*

```
1    def countdown(n)
2      return n if n == -1
3      p "before: n: #{n}"
4      countdown(n-1)
5      p "after: n: #{n}"
6    end
7
8    countdown(5)

```

Output:

```
"before: n: 5"
"before: n: 4"
"before: n: 3"
"before: n: 2"
"before: n: 1"
"before: n: 0"
"after: n: 0"
"after: n: 1"
"after: n: 2"
"after: n: 3"
"after: n: 4"
"after: n: 5"

```

# Answer
> 2 votes
Look at the definition of your countdown function.

If I call countdown (5), then it prints "before: n = 5", then it does lots of stuff including lots of printing, then it prints "after: n = 5" and finishes. So your output must start with "before: n = 5" and it must end with "after: n = 5" and all kinds of things might happen in between.

And that's exactly what happens.

---
Tags: computability
---


# Question
Title: Why are these FIRST sets not combined into a single set?
In Sebesta's *Concepts of Programming Languages 10th edition* on page 189 he explains the concept of $\text{FIRST}$ sets using the following example:

> $A \rightarrow aB \ | \ bAb \ | \ Bb$
>
> $B \rightarrow cB \ | \ d$
>
> The $\text{FIRST}$ sets for the RHSs of the $A$-rules are $\\{a\\}$, $\\{b\\}$, and $\\{c, d\\}$, which are clearly disjoint.

Why aren't the first two sets combined into a single set $\\{a, b\\}$ instead? If $\\{c, d\\}$ is constructed by taking the two leftmost terminal symbols from $B$ then why don't we likewise take the two leftmost terminal symbols from $A$ into a single set?

# Answer
> 1 votes
There are three $A$-rules, each one with its right-hand side: $aB$, $bAb$, and $Bb$. Each produces a set as its value for $FIRST$. $FIRST(aB) = \\{a\\}$, and $FIRST(bAb) = \\{b\\}$.

In its turn, $FIRST(Bb) = FIRST(B)$ (because $B$ does not derive the empty string), and $FIRST(B) = FIRST(cB) \cup FIRST(d) = \\{c\\} \cup \\{d\\} = \\{c,d\\}$.

Naturally, $FIRST(A) = \\{a, b, c, d\\}$.

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


# Question
Title: After the training phase, is it better to run neural networks on a GPU or CPU?
Sorry if this is the wrong forum for this question. My understanding was GPUs were more efficient for running neural nets, but someone recently suggested GPUs are only needed for the training phase. Once trained, it's actually more efficient to run them on CPUs.

Is this true?

# Answer
> 1 votes
Running trained artificial neural network is repeated performing of a matrix with vector multiplication and performing the same nonlinear function for each element of a vector. If both operations could be parallelised and vectorised, it is what is GPU well suited for. But it strongly depends on the size of given vectors and matrixes which depend on the size of the neural network. For small nets, CPU could be faster than GPU but it would not matter anyway. For huge nets, GPU would be probably much better suited if algorithm is written right.

---
Tags: machine-learning, neural-networks, efficiency
---


title: Unusual elevator algorithm

text:
# Question
Title: Unusual elevator algorithm
An elevator with a capacity of N people in a building with E floors works in a pretty unusual way.

The elevator starts at the first floor and it goes to the top floor before returning to the first floor.

It stops at every floor that is a destination of a person in the elevator.

It also stops when 1) there is someone at the current floor who wants to travel in the same direction as the elevator is currently traveling and 2) there is still room in the elevator.

At least how many round trips to the top and back are necessary to carry every person to their destination?

I assume that some kind of Greedy algorithm can give a good algorithm to solve this problem, but I still have no idea how to write a pseudocode for it.

# Answer
> 1 votes
I don't see any optimisation problem, no need for any greedy algorithm, nothing.

You described the behaviour of the elevator. All you need to do is to simulate that behaviour and count the number of movements.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Proof required for edges in a minimum spanning tree
G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

**The answer is only statement 2 is correct**.

I was able to prove statement 1 is false using ***contradiction***. When we think of a complete graph with `4 vertices` and edge weights `1,2,5,6` in non diagonal and diagonal edges `3 and 4`. `4,5,6` will create a cycle and we can exclude the lighest edge e `(4)` from it, in a MST.

But statement 2 cannot be proved using the same. What should be the proof for proving statement 2 is correct?

# Answer
Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? May it be the case that another edge in the cycle can play the 'role' of e in MST?
> 1 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$
Prove that $H\_r(S) = H(s) / \log\_2r$.

I'm not sure how to prove this. Any help would be greatly appreciated!

# Answer
There's nothing to prove here, this follows by Definition. Assume a discrete r.v. $X$, then

$$H(X) \triangleq \mathbb{E}\[-\log \Pr(X)\]$$

and,

$$H\_r (X) \triangleq \mathbb{E}\[-\log\_r \Pr(X)\].$$

Therefore, the claim follows (using $E(aX)=aE(X)$ for a constant $a$). Note that in your question you use $H(X)$ as the binary entropy $H(X) \triangleq H\_2(X) = \mathbb{E}\[-\log\_2 \Pr(X)\]$, hence the multiplicative factor is $\log\_2 r$.
> 2 votes

---
Tags: information-theory
---


# Question
Title: Finding alternative way of combinatorial counting
The question is related to databases:

> There is a relation $R(A\_1,A\_2,...,A\_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are?

I thought if any one of the $(n-2)$ attribute combinations is chosen then the number of superkeys that can be formed with it will be 4, as there will be $2^2$ combinations of remaining two attributes. So I gave answer $nC\_{n-2}\times 2^2$.

But then the answer given was $nC\_{n-2} + nC\_{n-1}+ nC\_{n}$ which is also quite obvious. But then I realized that my solution does not equate to this one and that my solution count certain superkeys more than once.

However I am not able to form an equation of the count of those duplicate superkeys so that I can subtract it from $nC\_{n-2}\times 2^2$ in order to get another expression for the solution (somewhat inclusion-exclusion approach). What is that expression/equation which counts those duplicate superkeys?

# Answer
> 1 votes
The correct answer can be rewritten as $\frac{n(n-1)}{2} + n + 1$.

Let's call the two remaining attributes $A\_k$and $A\_l$.

You are counting each combination of $nC\_{n-2}$ candidate keys four times: (1) when they are alone, (2) when they are with $A\_k$, (3) when they are with $A\_l$, (4) when they are with both $A\_k$ and $A\_l$.

Your formula then boils down to the following sum:

$nC\_{n-2} + nC\_{n-2} + nC\_{n-2} + nC\_{n-2}$

The problem is that you are counting each combination in case (2) an excessive number of times, because each $A\_k$ appears in $n-2$ additional identical combinations, when it is taken as a part of the candidate key. The same is true for case (3).

There is just one singular combination in case (4), the one with all attributes.

The corrected version of you formula is then:

$nC\_{n-2} + \frac{nC\_{n-2}}{n-1} + \frac{nC\_{n-2}}{n-1} + \frac{nC\_{n-2}}{nC\_{n-2}}=\frac{n(n-1)}{2} + \frac{n}{2} + \frac{n}{2} + 1=\frac{n(n-1)}{2} + n + 1$

---
Tags: combinatorics, database-theory, counting, word-combinatorics
---


# Question
Title: Optimization of Thompson Construction of an NFA
I would like to ask under which circumstances can these optimizations be used,supposed that they are part of a bigger NFA and when can they lead to an error ??

# Answer
In general these reductions are OK when there are no other edges incident to the edges you are contracting. Whenever there are other edges there can be unexpected paths.

I do not know of a good characterization when they can be used. If such an improvement would have been obvious, I think Thompson would have included it.
> 1 votes

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


title: What is a unifier?

text:
# Question
Title: What is a unifier?
Currently I read up on unifiers, however have some problem understanding its concept. Thus far I found an example of an equation:

add(suc(x); y) $\stackrel{.}{=}$ add(y; suc(z))

and unifiers to it:

$\omicron$ = \[suc(x)/y; x/z\],

$\omicron'$ = \[suc(suc(z))/y; suc(z)/z; suc(z)/x\] and

$\omicron'$ = $\omicron$\[suc(z)=x\]

However I do not understand how one generally derives these unifiers from the equation above. Any construcive comment/answer would be appreciated.

# Answer
A unifier of a set of terms is just any substitution that, when applied to each of the terms, makes them all equal. There's also the concept of a "most general unifier" (MGU), which is a unifier $\sigma$ of the terms such that any other unifier can be written as $\sigma\circ\tau$ for some substitution $\tau$: in other words any other unifier can be written as "first do an MGU and then do some more substitutions, which were kinda unnecessary because you'd already made the terms equal."

As for finding unifiers, there are various algorithms; see the Wikipedia article for more details. In terms of what's required for undergraduate exercises, though, the most natural "algorithm" is the rather unhelpful "Look at the terms and see what works." Once you understand the definition and you're comfortable with it, a unifier is usually pretty immediate.
> 7 votes

---
Tags: logic, unification
---


# Question
Title: Assigning all nodes in a tree a parent and children
If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and each node be assigned children and a parent such that by recursing up through its parent, its parents parent and so on the eventually one will eventually hit the root e.g.

Could be represented as **`4,1 4,2 4,3 4,5 6,5`**

and a possible solution could be

`1: parent:4, children: None
 2: parent:4, children: None
 3: parent:4, children: None
 4: parent:None, children:1,2,3,5
 5: parent:4, children: 6
 6: parent:5, children: None`

where 4 is the root.

# Answer
> 5 votes
The tree in your diagram is undirected. Undirected trees don't have a uniquely determined root because the edge $xy$ just means that nodes $x$ and $y$ are related: it doesn't specify that one is the parent of the other.

If you're told to make a particular node the root, you can do so by directing all of the edges away from the root, which you can do by depth-first search (or breadth-first search, or any other enumeration procedure).

Conversely, if the edges *are* directed, so $xy$ means "$x$ is the parent of $y$" (or vice-versa, if you want to adopt the opposite convention), then you can find the root by starting at any node and navigating to the parent until you find a node without a parent. Since the root is the unique node without a parent, you're done. You might also want to check that the graph really is a tree, i.e., that it is connected and acyclic.

---
Tags: graphs, trees
---


# Question
Title: Is finding a set cover of size $k$ NP-complete?
I know that set cover problem is NP-complete. We are given a universe $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe and an integer $k$. The set cover problem is to identify a sub-collection of $S$ of size $k$ **or less** whose union equals the universe?

Now if I remove **or less**, and ask instead that is there a sub-collection of $S$ of size $k$ whose union equals the universe? Is this still NP-complete?

Here, of course, $k\<m$.

My answer is that the problem is still NP-complete. From the initial problem we simply keep the same instance and we find a set cover of size $s\leqslant k$ then the modified problem has a set cover of size $k$ if $s=k$.

Any help?

# Answer
Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$.

For example, for $k = n / 3$, 3-dimensional matching can be directly reduced to your problem.
> 8 votes

# Answer
I have found an answer for my question in \[1\]. The problem I am interested in, called in \[1\] MINIMUM COVER, is NP-complete by reduction from 3-EXACT COVER.

The 3-EXACT COVER is defined as \[1\]: Given a family $F=\\{S\_1,\ldots,S\_n\\}$ of $n$ subsets of $S=\\{u\_1,\ldots,u\_{3m}\\}$, each of cardinality three, is there a subfamily of $m$ subsets that covers $S$?

The 3-EXACT COVER is NP-complete \[1\].

The MINIMUM COVER is defined as \[1\]: Given a family $F=\\{S\_1,\ldots,S\_n\\}$ of subsets of a finite set $U$, and an integer $k\leqslant n$, is there a subfamily $C$ of $F$ containing $k$ sets such that $\bigcup\limits\_{S\_j\in C}S\_j=U$?

As stated in \[1\], *the 3-EXACT COVER is just the special case of MINIMUM COVER in which $|S\_j|=3$ for $j=1,\ldots,n$, and $k=\frac{1}{3}|U|$. Consequently, any instance of 3-EXACT COVER can be trivially transformed into an instance of MINIMUM COVER. ...*

---

\[1\] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization. Algorithms and Complexity. Dover Publications, 1998. First published in 1982 by Prentice-Hall.
> 5 votes

---
Tags: reductions
---


# Question
Title: How to use PHOG and LPQ features for Emotion Recognition?
I have a database that consists of PHOG and LPQ features for each image. Now, I wish to train an SVM on these features for emotion recognition i.e SVM classifies the images on basis of emotion in the image.

Please provide a detailed procedure on how to use these features to train SVM.

# Answer
To train your SVM inevitably you need some baseline, which can be accquired from FERA 2011 contest. The whole procedure using this data is described in Emotion Recognition Using PHOG and LPQ features by Abhinav Dhall, Akshay Asthana, Roland Goecke and Tom Gedeon. After reading that there is a follow up FERA 2015.
> 2 votes

---
Tags: image-processing, computer-vision, svm
---


# Question
Title: Why register access bandwidth is higher then residing inside CPU cache?
Access to registers claimed to be faster then cache. Why is it? Is it because cache has less wires or spatially further from functional units?

# Answer
There are slower and faster technologies for memory. And there are technologies for creating bigger or smaller amounts of memory. Obviously a technology that creates slower and smaller memory is useless. So of the useful technologies, the fastest one will always provide the smallest amount of memory, and the ones providing the biggest amount of memory will be the smallest.

Register memory is smaller than cache, therefore it's faster. It has nothing to do with technology, it is a basic economic principle. If the technology used for cache was faster, it would be used for registers.
> 2 votes

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: How to work out physical address corresponding to logical address?
I am looking to calculate the physical address corresponding to a logical address in a paging memory management scheme. I just want to make sure I am getting the calculation right, as I fear I could be wrong somewhere.

So, the data I have is as follows:

* The logical address: $717$
* Logical memory size: $1024$ bytes ($4$ pages)
* Page Table:

\begin{array}{| c | c |} \hline Page\ Number & Frame\ Number\\ \hline 0 & 5\\ \hline 1 & 2\\ \hline 2 & 7\\ \hline 3 & 0\\ \hline \end{array}

* Physical memory: $16$ frames

So, with $1024$ bytes in the logical memory, and $4$ pages, then each page is $256$ bytes.

Therefore, the size of the physical memory must be $4096$, right? ($256 \times 16$).

Then, to calculate the logical address offset:

$$1024 \mod 717 = 307$$

Is that how we calculate the offset?

And, we can assume that $717$ is in page $2$ ($\frac{1024}{717} = 2.8$)?

So, according to the page table, the corresponding frame number is $3$.

And so to get the physical address, we multiply the frame number and page size?

$$2 \times 256 = 768$$

Then, do we add the offset, like so:

$$768 + 307 = 1,075$$

Thank you for taking the time to read. If I don't quite have this correct, would you be able to advise on the correct protocol to calculating this?

# Answer
> 6 votes
You are correct in your reasoning that the pages are $256$ bytes and that the physical memory capacity is $4096$ bytes.

However, there are errors after that.

The offset is the distance (in bytes) relative to the start of the page. I.e., logical\_address mod page\_size. The bits for this portion of the logical address are not translated (given power of two page size).

The logical (virtual) page number is number of (virtual) page counting from zero. I.e., $$\frac{logical\\\_address}{page\\\_size}$$

As you noted, the physical page is determined by the translation table, indexed using the logical (virtual) address.

Once the physical page number had been found, the physical address of the start of that page is found by multiplying the physical page number by the page size. The offset is then added to determine the precise physical address. I.e., $$(physical\\\_page\\\_number \times page\\\_size) + offset$$

So a logical address of, e.g., $508$, with $256$ byte pages would have an offset of $$508 \mod 256 = 252$$ The logical/virtual page number would be $$\frac{508}{256} = 1$$ With the given translation table, logical page $1$ translates to the physical page number $2$. The physical address would then be $$physical\\\_page\\\_number \times page\\\_size + offset = 2 \times 256 + 252 = 764$$

# Answer
> -1 votes
* offset = 717%256 = 205
* page no = 717/256 = 2.\__ = 2
* frame no = 7
* physical address = 7\*256 + 205

# Answer
> -1 votes
page no =717/256=2.\_ (page no 2. since logical memory is divided into 4 pages (0-3))

offset = 717%256=205 (205th byte in page no 2)

frame no=7 (from page table)

physical memory also is divided into 16 equal frames of size 256 bytes

physical address=(7\*256)+205=1997

---
Tags: operating-systems, memory-management, paging
---


# Question
Title: Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set
Let $B = \\{z \mid (\exists x)\\; P(x,z)\\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set.

**My attempt**

As $P$ is a computable predicate then there is a program that computes it, therefore $B= \\{z \mid (\exists x)(\exists t)\\;\text{STP}^{(1)}(x,z,t)\\} \Rightarrow B= \\{z \mid \Phi(x)\downarrow\\} = W\_z$ and so $B$ is a recursive enumerable set.

**Further info**

$\text{STP}^{(n)} (x\_1, \ldots, x\_n, y,t)$ is a predicate that is true if the program number $y$ halts after $t$ or fewer steps on inputs $x\_1, \ldots, x\_n$.

*Note: please note this is the first time I ever try to solve this kind of exercises, so even if I got everything wrong and nothing makes sense, every nudge in the right direction is really welcome.*

# Answer
Hint, do you know the argument for the countability of the rational numbers?

Just enumerate every pair $a,b$ of natural numbers and output the $b$ if $P(a,b)$ is true.

Other way, can you construct a machine that given a $b$, answers YES if there is an $a$ such that $P(a,b)$ is true?
> 2 votes

# Answer
Your set $B$ includes all programs $z$ that halt on some input. This has no connection to $P$. Your proof should start like so: *Suppose that $P$ is computed by program number $y$*, and should invoke $\mathrm{STP}^{(2)}$, since $P$ has two inputs.
> 1 votes

# Answer
In fact being able to express $B$ in that form and saying that $B$ is recursively enumerable are equivalent.

Here's a proof using Kleene Normal Form when $P$ is any partial recursive relation. First I'll show that if $B\subseteq\mathbb{N}^n$ is r.e., then there is a recursive relation $P\subseteq\mathbb{N}^{n+1}$ such that $$B(x\_1,\ldots, x\_n)\iff\exists y P(x\_1,\ldots, x\_n,y).$$

If $B=\emptyset$ the result is clear. Else let $f:\mathbb{N}\to\mathbb{N}^n$ be a total recursive function such that $B=\operatorname{range}(f)$. Then we have \begin{align\*}B(x\_1,\ldots, x\_n) &\iff\exists y (f(y) = x\_1,\ldots, x\_n) \\ &\iff\exists y\forall i\le n (f\_i(y) = x\_i)\end{align\*} which is in the desired form.

Now we show that there is a partial recursive function $f:\mathbb{N}^n\to\mathbb{N}$ such that $B=\operatorname{dom}(f)$. We can write $B(x\_1,\ldots, x\_n)\iff\exists y P(x\_1,\ldots, x\_n,y)$ where $P$ is a recursive relation. Then we simply take $$f(x\_1,\ldots, x\_n)=\mu y P(x\_1,\ldots, x\_n, y).$$ $f$ is recursive and $f(x\_1,\ldots, x\_n)\downarrow\iff B(x\_1,\ldots, x\_n)$.

Finally, we'll use the Kleene Normal form theorem get a primitive recursive function $f:\mathbb{N}\to\mathbb{N}^n$ such that $B=\operatorname{range}(f)$ or $B=\emptyset$. Indeed, write $B=\operatorname{dom}(f)$ for partial recursive $f$. Then, there are primitive recursive functions $U$ and $T$ and some $e\in\mathbb{N}$ such that $$f(x\_1,\ldots, x\_n)=U(\mu c T(e, \langle x\_1,\ldots, x\_n\rangle, c)).$$ Then $$B(x\_1,\ldots, x\_n)\iff f(x\_1,\ldots, x\_n)\downarrow\iff\exists c T(e,\langle x\_1,\ldots, x\_n\rangle, c),$$ which is in the form we wanted.

It is easy to see that the last condition implies the usual definition for r.e. sets, so we are done.
> 0 votes

---
Tags: computability, check-my-proof, enumeration
---


# Question
Title: Understanding a binary classifier problem
I'm trying to understand a problem that's more mathematical in nature that I'm accustomed to. Below I'll try to present the problem and what I have so far understood of it.

**The problem**

We have $X\_1,..,X\_n$ i.i.d. binary outcomes distributed according to Bernoulli distribution. The probability that $X\_i = 1$ is given by $E\[X\_i\] = p$. Hoeffding's inequality is somehow useful in solving the problem. It tells us that the total number of outcomes with value $1$ divided by $n$ is not too far from its expectation, which is $E\[\frac{1}{n} \sum\_{i=1}^n X\_i\] = \frac{1}{n} \sum\_{i=1}^n E\[X\_i\] = p$:

$Pr\[|p-\frac{1}{n}\sum\_{i=1}^n X\_i| \> \epsilon\] \le 2exp(-2n\epsilon^2)$

Now I have to solve for the value $\epsilon$ for which the above probability equals $\alpha$. E.g. $n = 10$, $\alpha = 0.05$ this provides a bound that guarantees that with 95 % probability, the observed number of occurrences of $X\_i = 1$ is within the interval $\[n(p − \epsilon), n(p + \epsilon)\]$. I must also evalute the width of this interval.

**My understanding right now**

The outcomes $X\_1,..,X\_n$ are something like coin tosses with a biased coin. We have some expectation $p$ for the coin toss to equal heads. The Hoeffding's inequality part says that if we take the sum of all of the expected values and multiply it with $\frac{1}{n}$ we get something close to $p$ (but why is it not $\frac{np}{n} = p$?) and the probability for it to be greater than $\epsilon$ is some (rather small?) number.

Now if we use the values of the example, the inequality would look like $0.05 \le 2^{-20\epsilon^2}$. I suppose I could solve that $\epsilon$ but the result is still an inequality and I think I need a concrete value to calculate $\[10(p - \epsilon), 10(p + \epsilon)\]$.

And if I'm correct the answer to the problem is some real valued range like $\[5, 8\]$ which says that there's a 95% possibility to get from 5 to 8 heads in 10 tosses, but I have no idea how to come up with the true range using that inequality.

I'm also not sure whether it's good to apply any real world scenarios in to this kind of abstract problems, or should I just try to learn to think on an abstract level and forget about the physical world? Especially if I'm to see a lot more problems like this.

Do you know of any materials that could possibly show me what's actually going on in that kind of equations? It's ok if I can't solve the problem but I would love to understand it on a level that doesn't make me want to scream and run away.

**tl;dr**

I'm having a hard time understanding probability distributions and inequalities with greek letters, but I would like to. Right now I'm stuck and I could use a pointer to the right direction.

I'll try to post updates as I go on.

**Update**

Ok so this is what I gathered:

So what the inequality is essentially saying is that when the amount of trials grows, the probability that we would deviate from our expected average by over some number $\epsilon$ decreases. And higher deviation also means smaller probability. It makes sense if I consider those coin tosses, because it's easy to see that during a large amount of trials the distribution should follow the the bias (if the coin has some).

Now if I estimate this $\alpha = 0.05$ for $100$ trials, I get that $2e^{-2\*100\*0.136^2} = 0.0494 \le 0.05$, which allows me to claim that in 95% of the cases I would deviate from the expected average by at most $0.136$.

How we arrive in to this conclusion without knowing anything about the initial probabilities is still beyond me. If I do not know them, the interval in the problem will take the form of $\[100p-0.136, 100p+0.136\]$ if I'm not mistaken?

Thanks for the explanation, I hope I understood it correctly and my apologies in advance if I didn't.

# Answer
> 1 votes
This kind of analysis could be confusing if you are new to it. I think you need some intuition about what's going on. I will assume you understood until this point

$$ Pr\[|p - \frac{1}{n} \sum\_{i = 1}^{n} X\_i| \> \epsilon\] \leq 2 e^{-2n\epsilon^2} $$

(If not, hold tight and ask in the comments, I will elaborate).

So this inequality tells you this. You should be expecting the average value to be around the expected value of the average (that's why they call it expected value), and larger and larger deviations should be less and less likely. So if you ask what is the probability the average is at least $0.01$ away from the expected value, you plug-in $\epsilon = 0.01$ in the right hand side and get an upper bound on the probability that this happens.

Notice that as $\epsilon$ gets larger the probability gets smaller and smaller. Also notice that as $n$ gets larger, the probability gets smaller. These reason behind these two statements should be clear to you. (If not, pause and think about it).

Now you ask the inverse question. If I want to be 95% sure that the average is within $\epsilon$ from the expected, how big must epsilon be. Notice that the answer to this question must necessarily be a lower bound on $\epsilon$. Since if you are 95% sure that the average is within $\epsilon$ from the expected value, then with even bigger probability you are sure that it is within a bigger range from expected.

So what you want to do is assert that $Pr\[\dots \> \epsilon\] \leq 0.05$, that is the probability that the average is farther away than $\epsilon$ be at most 5%. You cannot calculate the probability exactly, but you do have an upper bound on how big it can be (given by your inequality above). So if you want to be certain the probability is less than 5%, you can assert that the upperbound on the probability is less than 5%. That is, you want to solve:

$$ 2 e^{-2n\epsilon^2} \leq \alpha = 0.05 $$

Note, that solving this will give you something like $\epsilon \geq \dots$ That means as long as you choose $\epsilon$ to be at least this, you are sure that the probability of deviating from the expected value by at least $\epsilon$ is at most 0.05.

Of course you can do the entire analysis for a variable $\alpha$ instead of 0.05.

---
Tags: machine-learning, probability-theory
---


title: Hashing Probabilities

text:
# Question
Title: Hashing Probabilities
I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a simple uniform hash, what is the expected number of buckets that have exactly 1 item? What is the expected number of buckets with at least 2 items? What is the expected number of buckets with exactly k items?", so will appreciate any help with respect to hashing probabilities.

# Answer
For sufficiently large $M$, the size distribution of hash slots with good uniform hash functions follows a Poisson distribution.

Let $\lambda = \frac{N}{M}$ be the load factor. Then the expected proportion of buckets with exactly $k$ items in it is:

$$P(\hbox{# of items in the bucket is } k) = \frac{e^{-\lambda} \lambda^k}{k!}$$
> 2 votes

---
Tags: algorithm-analysis, data-structures, probability-theory, hashing
---


# Question
Title: Characterisation of Turing completeness?
I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language.

For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). That gives an easy way to say if a language is Turing complete, as soon as we've found out that it is imperative.

Hence my question **is there any similar, characterization of Turing completeness which would work for any language?**

# Answer
> 0 votes
It seems very unlikely that there is any useful characterization other than the definition. Any such characterization would have to deal with all kinds of programming languages (imperative, functional, declarative and everything else) along with, assuming the claims from the Wikipedia article you link are correct, Minesweeper, Conway's game of Life and Magic the Gathering.

If you did have a characterization, it would probably be no easier to apply that characterization than to just apply the definition.

---
Tags: programming-languages, computation-models, turing-completeness
---


# Question
Title: Complexity of finding the shortest simple even s-t-path
Consider a graph $G=(V,E)$ and two vertices $s,t$.

> What is the complexity of finding the length of the shortest **simple** $s-t$ path that has even length?
>
> Does the problem become harder if the graph is edge weighted?

---

Note that the requirement that the path is simple makes it harder than to simply to use two copies of the graph

# Answer
Its in P for undirected graphs and NP hard for directed once: http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/pdf
> 3 votes

---
Tags: complexity-theory, graphs, shortest-path
---


title: Proving landau notation statements

text:
# Question
Title: Proving landau notation statements
If we have the function $f : \mathbb{N}\_0 \rightarrow \mathbb{N}$ with $f(n) = n^2$ and we look at the following representations of the sets $\mathcal{o}(f),\mathcal{O}(f),\Theta(f),\Omega(f),\omega(f) $:

Now I have to list all necessary statements which are proving that the illustration is correct.

The necessary statements are in my opinion:

\begin{align} \Theta (f)&\subseteq \mathcal{O}(f) \\ \Theta (f)&\subseteq \Omega (f) \\ \Theta (f)&= \mathcal{O}(f) \cap \Omega (f) \\ \omega (f)&\subseteq \Omega (f) \\ \hbox{o}(f)&\subseteq\mathcal{O}(f) \\ \\, \emptyset &=\\, \omega (f) \cap \hbox{o}(f) \end{align} Now I have to proof two statements of my choice. But how to proof that in a formal correct way. (I understand the intuitive proofs but I don't know how to do it formally correctly.)

Hope somebody can help.

# Answer
Here is an explanation by example. Let $\Theta'(f) = \\{ g : g(n)/f(n) \text{ tends to a positive limit} \\}$. I will show that $\Theta'(f) \subseteq \Theta(f)$. The first step is to write the definitions. There are several variants of the definitions, and I picked one arbitrarily; you should use the definitions that were stated in class.

> Let $f\colon \mathbb{N} \to \mathbb{N}$.
>
> 1. $\Theta'(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $x \in \mathbb{R}\_+$, $\lim\_{n\to\infty} g(n)/f(n) = x$.
> 2. $\Theta(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $a,b \in \mathbb{R}\_+$ and $n\_0 \in \mathbb{N}$, for all $n \geq n\_0$ it holds that $a f(n) \leq g(n) \leq b f(n)$.

The next step is to take a function $g \in \Theta'(f)$.

> Let $g \in \Theta'(f)$. Then there exists a positive $x \in \mathbb{R}\_+$ such that $$ \lim\_{n\to\infty} \frac{g(n)}{f(n)} = x.$$

Finally, we have to show that $g \in \Theta(f)$. For that we have to come up with positive $a,b \in \mathbb{R}\_+$ and $n\_0 \in \mathbb{N}$ such that $af(n) \leq g(n) \leq bf(n)$ for all $n \geq n\_0$.

> By the definition of limit, there exists $n\_0$ such that for $n \geq n\_0$, $$ \left|\frac{g(n)}{f(n)}-x\right| \leq \frac{x}{2}. $$ Therefore for $n \geq n\_0$, $$ \frac{x}{2} \leq \frac{g(n)}{f(n)} \leq \frac{3x}{2}, $$ implying $$ \frac{x}{2} f(n) \leq g(n) \leq \frac{3x}{2} f(n). $$ Taking $a = x/2$ and $b = 3x/2$, we see that $g \in \Theta(f)$.

Only the latter two steps really belong to the proof. The first one states the claim. It is a very important step — without knowing what you're trying to prove, you won't be able to prove it.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Transitive reduction of rectangle containment hierarchy DAG
I am looking for a $O(|V| + |E|)$ algorithm for finding transitive reduction of a rectangle containment hierarchy DAG, i.e. a directed edge exists from one rectangle to another if the first rectangle contains the second.

That is, remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach it after removal of edges.

Assume that rectangles are unique, so we are dealing with a DAG.

---

This is useful, for example, with quantitative association rule mining from Srikant/Agrawal 1996. There, we are interested in close ancestors for hyperrectangles s.t. ancestors contain us. Determining close ancestor is similar to determining close descendant, which is related to transitive reduction with rectangle containment. This kind of rule mining is related to APRIORI algorithm for standard (i.e. "Boolean") association rule mining from Agrawal/Srikant 1994.

A similar problem is transitive reduction of standard DAG, which is here:
Transitive reduction of DAG

**References**

* Agrawal, Srikant - Fast algorithms for mining association rules (1994)
* Srikant, Agrawal - Mining quantitative association rules in large relational tables (1996)

# Answer
Dec. 14, 2018

# **Standard approach and a heuristic alternative**

## **Standard approach -- use graph and distance product**

We note that transitive reduction is reduceable to transitive closure and vice versa both in additional time in $O(n ^ 2)$. Then, we know that if we can solve transitive closure in $O(n ^ 2 \cdot \textrm{polylog}(n))$ time, then we can also solve lax Boolean matrix multiplication (MM) in similar time by reducing it to transitive closure (or transitive reduction), according to Fischer/Meyer 1971. Lax Boolean MM is where input values are in $\\{0, 1\\}$ and we have semi-ring of $(\textrm{OR}, \textrm{AND})$. We can solve lax Boolean MM by reducing to standard (plus, times) MM. This means that significantly-subcubic-time approach is currently unlikely for transitive reduction. We can reduce node-based DAG transitive reduction to rectangle-containment-based DAG transitive reduction via topological ordering and shapes that have size inversely related to distance from source. For rectangle application, we should of course not have cycles, which happen when the rectangles are identical, in which case we should remove duplicates. A more direct algorithm is for computing reduction assuming sparse graph, which takes $O(n ^ 3)$ time. These times are also ignoring that to come up with initial DAG we ought to perform $n ^ 2$ containment tests, each of which takes time in $O(d) = O(2) = O(1)$.

## **Heuristic alternative -- use R-tree**

Alternatively, assuming we have dimension $d$ moderately low and fixed and not bound tightly by $O(n)$, we can arrive at times that appear to be subcubic in $n$. We have two options -- both use an R-tree variant with bulk-loading e.g. via sort-tile-recursive (STR) approach via Leutenegger 1997 and that is balanced and that is dynamic via bkd-tree-like occasional rebuilding (see Procopiuc 2003) to support inserts and deletes in $O(\log^2(n))$ time. See Guttman 1984 for details on standard R-tree. The main idea is that we find close descendants for each of $n$ provided rectangles via a total of $n$ close-descendant queries. We consider both options to involve heuristics because we may have many intermediate hunches for close-descendant that do not ultimately survive, even though subqueries have good guaranteed time for option one.

If we have pair-wise rectangles that do not frequently involve enclosure/containment and overlap is highly correlated with enclosure/containment, then it is conceivable that we can get better performance using R-tree via either of the two options for our approach. We note that a rectangle enclosure query asks for given a query rectangle rectangles that contain it and a rectangle containment query asks for given a query rectangle rectangles that fit in it. Close-descendant query roughly works via a heuristic approach. We find primitive rectangles contained by query rectangle and use auxiliary queries to see if returned rectangles have parents that are contained by original query rectangle. The candidate close descendants we store in a "conflict" secondary R-tree for purpose of speeding up checks in form of enclosure subquery with early-stopping that determine whether a candidate parent encloses (and disqualifies) a candidate close descendant; we maintain this conflict tree via inserts and deletes. We note that when we encounter rectangles of same shape, we may choose to keep one of them arbitrarily. We use a best-first priority queue to guide bounding box consideration order; we prefer contained bounding boxes and we tie-break by preferring larger bounding box area (because it is harder to be a middle-man for a larger contained box).

**Option #1 -- use look-ahead**

The first option is to use look-ahead for subqueries such as rectangle enclosure and rectangle containment in conjunction with corner transformation. Close-descendant query would then not directly use look-ahead; its subqueries do. Then, we have a coefficient of $d$ for look-ahead-using queries for edge checks. We won't go into much detail about look-ahead except that it requires roughly disjoint bounding boxes for siblings (though shared edge is allowed) and that it is related to knowing that one child out of two subtrees definitely has a match (which is made more straightforward to notice assuming we also use corner transformation) via $d$ edge checks at each node. It should be noted that without look-ahead enclosure and containment already take at least $d$ time for each node for an R-tree. We modify enclosure subquery to use early-stopping, which leads time for such a query to be $O(\log(n))$ instead of $O(\log^2(n))$. Time for each close-descendant query is in $O(k \cdot \log^2(n))$, where $k$ is number of hunch close-descendants s.t. $k$ is in $O(n)$. This means for $n$ close-descendant queries overall we take time in $O(k \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$. Since this is less than cubic in $n$ (though we omit a factor of $d$ assuming it is moderately low and fixed), this approach may be used to get better performance in practice. We have left out detail that for look-ahead-using enclosure/containment subqueries we may take non-constant time even if there are zero matches.

**Option #2 -- do not use look-ahead**

The second option is to not use look-ahead and all we can say (without further simplifying assumptions) is that for each close-descendant query we have worst case of $n$ hunches, each of which would then take $O(\log(n))$ time to find (because we don't go down a branch more than once). We note that we assume that we do not use corner transformation. As a result, we have an exceedingly loose and pessimistic time bound of $O(n \cdot \log(n))$ for attempt to disqualify a hunch close descendant via enclosure subquery with early-stopping. Time for a close-descendant query then is bounded by $O(k' \cdot n \cdot \log(n))$, where $k'$ is worst-case number of hunches (i.e. $n$). Time for $n$ close-descendant queries then is bounded by $O(k' \cdot n ^ 2 \cdot \log(n))$ = $O(n ^ 3 \cdot \log(n))$. This figure is more than cubic in $n$ (again noting that we omit a factor of $d$ as it is moderately low and fixed), but the times for the approach are considerably pessimistic and we believe there is still a chance that it can perform well in practice w.r.t. brute-force. We show that this is plausible by now making a few assumptions, which we discuss below. While the first option does not take advantage of possibility that number of hunches can be significantly lower than $n$ either, it has lower theoretical bounds because they take advantage of possibility that enclosure subquery with early-stopping for disqualifying a hunch close descendant can be guaranteed to be fast.

**Option #2 -- three assumptions**

Assumption "zero-overlap" says that (i) bounding boxes do not overlap with query rectangle unless we enclose query rectangle for enclosure query or we are contained by query rectangle for containment query; and (ii) bounding boxes for siblings s.t. neither sibling is contained in the other do not overlap except at a boundary. We note that part one of that assumption can only mostly be true e.g. because a real rectangle collection has a largest rectangle that cannot be enclosed and a smallest rectangle that cannot contain. We introduce $b$, which describes average false-positive-to-actual-positive ratio for believing that a child for a node is associated with a guaranteed match during disqualify attempt subquery s.t. $b$ is in $\[0, 1\]$. Time for second option close-descendant query is broken into two parts. The first part describes getting the hunches. The second part describes attempts to disqualify each hunch. The third part is to handle updates to conflict tree. Assume number of hunches is $k''$. The time for the first part is $O(k'' \cdot \log(n))$. The time for the second part is $O(k'' \cdot (b + 1)^{\log(n)} \cdot \log(n))$. The time for the third part is $O(k'' \cdot \log^2(n))$. The total time is loosely (assuming $b$ is one) in $O(k'' \cdot n \cdot \log^2(n))$. The time for $n$ close-descendant queries is $O(k'' \cdot n ^ 2 \cdot \log^2(n))$ = $O(n ^ 3 \cdot \log^2(n))$ if $k''$ is in $O(n)$. This does not appear to be better than brute-force. If we make "zero-overlap" assumption, $b$ is zero, which gives $n$ close-descendant query time of $O(k'' \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$ if $k''$ is in $O(n)$. The factor of $\log^2(n)$ (instead of $\log(n)$) comes from insert/delete for conflict tree of hunch close descendants. This assumption can be true for rectangles for a hierarchy that is highly coherent -- i.e. one with many realized enclosure/containment relationships and good separation between rectangles that are not related via enclosure/containment.

We have two other assumptions -- "uniform sparsity" and "no pruning", each of which have secondary purposes that are related to our application of quantitative association rule mining. They allow us to tune to reduce work drastically given that the second option for close-descendant query can be very time-costly. Specifically, say average number of partitions for a quantitative attribute (treating categorical attribute as possibly multiple two-partition quantitative attributes) is $p$; then, number of solid regions considered for each quantitative attribute is $p ^ 2$ -- all of which survive if we have "no pruning" assumption. As we reduce $p$, the space of all possible multi-dimensional rectangles shrinks and via "uniform sparsity" assumption for fixed $n$ we have more collisions (i.e. possibly more enclosure/contain relationships) but number of rectangles (that are made of combinations of solid regions for different attributes) shrinks faster -- this means that w.r.t. close-descendant query the amount of time required we can drastically shrink by reducing average number of partitions $p$ slightly.

**Miscellaneous shared details**

The only reason we believe one might wish to not use option one is slightly more implementation difficulty. We don't often see a proposed algorithm that performs reporting and that has for each match a coefficient for time that is not one. Still, the coefficient that we have of $\log(n)$ or $\log^2(n)$ is fine; $\log^q(n)$ for low $q$ is often acceptable wherever we see $O(1)$, as opposed to when we have e.g. $n$ where we see $O(1)$. In general, an R-tree is better than multi-layer segment tree for rectangle enclosure/containment/intersection queries or point domination query if $d$ is less than $\log^{max(d - 1, 1)}(n)$ for $d \geq 1$ given that for an R-tree we do not clone stored rectangles. Option one and option two with assumptions imply that we appear to be better than brute-force given that it is appropriate to omit $d$.

# **References**

* Pratyaksh - Transitive reduction of DAG - Answer (2014)
https://cs.stackexchange.com/q/29133
* Wikipedia - Transitive reduction - Computing the reduction in sparse graphs
https://en.wikipedia.org/wiki/Transitive\_reduction
* Fischer, Meyer - Boolean matrix multiplication and transitive closure (1971)
* Leutenegger et al. - STR: A simple and efficient algorithm for R-tree packing (1997)
* Procopiuc et al. - Bkd-tree: A dynamic scalable kd-tree (2003)
* Guttman - R-trees: A dynamic index structure for spatial searching (1984)
> 5 votes

---
Tags: algorithms, graphs, dag
---


# Question
Title: Generate collision resistant identifiers with two-way hashing
*Objective:* We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions.

*High-level idea:* Compute $$fK := hash(k\_1)\\; and\\; sK := hash(k\_1^{-1})\\; where\\; k\_i^{-1}\\; is\\; the\\; reversed\\; bitstring\\; k\_i$$

We then proceed to set, our identifier to be: $$\<value\\\_of\\\_fK\>\\\_\<value\\\_of\\\_sK\>$$

*Assumption:*

For two keys $$k\_1\\; and\\; k\_2,\\; if\\; hash(k\_1) = hash(k\_2)\\; and\\; hash(k\_1^{-1}) = hashs(k\_2^{-1})\\; then\\; k\_1 = k\_2$$

where our hash function is FNV1a.

*Hypothesis:* For any given input bitstring, we will have a unique identifier and no collisions.

I would like to have your input on this

# Answer
Your assumption is probably false. It can only be true if the size of the hash is at least half the size of the key.

If you want to generate an absolutely unique identifier, why not use the key itself? Another option, if you want an alphanumeric identifier, is to use Base64 (which also uses a few punctuation marks).

If you just want a practically unique identifier, you can just use a hash function – any industry-standard one would do. That's exactly their goal. Since it doesn't seem you care about cryptographic security, you can just use MD5 or SHA1.
> 2 votes

---
Tags: strings, correctness-proof, hash-tables, hashing
---


# Question
Title: Finding maximum-cardinality independent set with a particular oracle
We suppose we have a polynomial algorithm which receives a graph $G$ (any graph) and returns a stable set of $G, SA(G)$ with the following property:

$\alpha(G) − |SA(G)| \leq k$ , for every natural $k$ ($k$ is a constant)

$\alpha(G)$ is the stability number

I need to show that this algorithm can be used to find(in polynomial time) a stable set (of maximum cardinality) in a graph.

I discovered that if I give $k=0$ then we get to this relation. But does that mean that the algorithm finds the stable set with maximum cardinal.

# Answer
If $k = 0$ then your algorithm outputs a stable set of maximum size. In the general case, try duplicating each vertex $k+1$ times, and see if it helps.
> 1 votes

---
Tags: algorithms, graphs, reductions
---


# Question
Title: Check if adding an edge to a DAG results in a cycle
On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest in 2011 organised by Warsaw School of Computer Science.

I have a graph with $V$ $(1 \le V \le 5 \cdot 10^5)$ vertices without edges and a list of $E$ $(1 \le E \le 5 \cdot 10^5)$ directed edges. On the $i$-th second $i$-th edge is being added to a graph. I want to know after which second there will be a cycle in a graph.

The most obvious solution would be to perform DFS after adding each edge, but it would take $O((V + E)^2)$ time. Another solution would be to keep the graph topologically sorted and when adding an edge, I could place it in such a way so that it will not disturb topological ordering. This would take at most $O(V^2)$ time. I did some research on Google and it seems that this is the fastest online algorithm.

As I know all the edges beforehand I can use offline algorithm. The fastest offline algorithm I can think of is binary search. If after $k$-th second graph contains a cycle then obviously it will have a cycle at any other second $l \ge k$. So I can do binary search to find smallest $k$ by performing DFS $O(\log E)$ times, each of them taking $O(V + E)$ time, so the total complexity of this solution would be $O((V + E) \log E)$.

It is quite fast, but I wonder if there exist any faster offline algorithm. One thing I can think of is giving for each edge weight equal to the time when this edge was added to a graph. Then the task would be equivalent to finding a cycle with minimal maximum edge weight. I don't know if it leads to anywhere.

# Answer
## KWillets' algorithm

KWillets seems to have the best algorithm. Basically, you iteratively alternate between the following two steps:

1. For each source (vertex with no outgoing edge), remove the source and all edges leading out from it. Repeat until there are no more sources.
2. Remove the highest-numbered edge, i.e., the one that is at the latest time (out of all remaining edges). Go back to step 1.

When the graph is empty, undo the last step 1 and step 2, and there's the earliest graph with a cycle. In other words, take the last edge removed in the last step 2 before the graph becomes empty, and the graph containing that edge and all earlier edges is the first one containing a cycle.

Since your list of edges is already sorted by increasing time, this can be implemented in $O(V+E)$ time. You'll maintain the list of edges in a doubly-linked list, with pointers between those nodes and the corresponding edge in the graph. Step 1 requires $O(1)$ time per node or edge deleted, if you keep a separate worklist of all source vertices and any time you delete an edge you check whether that has created a new source vertex.

## Binary search

It's possible to make some small optimizations to your binary search method, though they won't improve the asymptotic running time: the asymptotic running time will still be $O((V+E)\log E)$.

Suppose you analyze the graph at time $k$, and discover that it does contain a cycle. Decompose the graph into strongly connected components. Now you can permanently delete all isolated nodes (i.e., nodes that are in a SCC of size 1); they cannot be part of a cycle. You can continue the binary search from here.

Also, when you decompose into strongly connected components, for each strongly connected component, do the following. Count the number of nodes in the SCC, say $n\_0$ of them. Sort the edges within the SCC in increasing time. Look at the time of the $n\_0$th of them, say time $j\_0$. Then the first time when there is a cycle within that strongly connected component must be time $j\_0$ or later. Do this for each strongly connected component, and take the earliest of those times. Then, as an optimization, there is no need to consider any time earlier than that during the binary search.

However, these two optimizations probably won't provide more than a small constant-factor speedup, at best.
> 2 votes

# Answer
Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well. I use it for cycle checking, where an actual topological sort is not needed. In this variant, nodes are discarded as they are visited, instead of being added to the output, and the error termination indicates at least one cycle.

It works by pruning off root or leaf nodes (having in-degree or out-degree 0 resp.) from the graph one at a time, until no more nodes of that type can be found. Since this process cannot cut a cycle (all nodes on a cycle have indegree and outdegree \> 0), it terminates with a nonempty graph if at least one cycle exists.

If we cut the maximum remaining edge e at each such termination point, we can continue the process to see if E\e still contains a cycle, and so on iteratively until we've cut enough edges to make E acyclic. The last such edge cut k is the first k that makes E\[1...k\] cyclic.

Kahn's algorithm does this leaf-cutting process linearly by using a work queue of nodes to be deleted; it is initialized with the leaves of the entire graph (at least one of which must exist, if it's acyclic), and, as each is deleted, its parent node(s) are checked to see they in turn become leaves, and if so they are added to the work queue. By checking the neighborhood of each deletion, it works linearly through the graph, without the need for indexing structures beyond the FIFO queue.

We can do the same neighbor-leafness check as we cut the maximum edge, and add any leaves created to the work queue, or, if none are created, continue cutting.

In order to make the max-cutting process linear, we have to find the maximum non-deleted edge via a descending scan of the edges array, but each scan starts where the previous left off, and the algorithm only does a single pass through the whole array, so that part is O(E) in total. Overall I believe this method is O(V+E), the same as Kahn's alone.
> 6 votes

---
Tags: algorithms, graphs, searching
---