# Question
Title: The universal relation problem in communication complexity
In the universal relation $UR\_n$ problem \[1\] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \\{0,1\\}^n$, Bob gets a string $y \in \\{0,1\\}^n$ with the promise that $x \ne y$. The players exchange messages and the last player to receive a message must output an index $i \in \[n\]$ such that $x\_i \ne y\_i$. Moreover, the players have access to public randomness.

In a recent talk that I attended, the speaker mentioned that the following without giving a proof:

> Any protocol for $UR\_n$ can be transformed into an $UR\_n$ protocol that has the additional property that each possible index $i$ where $x\_i \ne y\_i$ is output with the same probability, without changing the communication complexity.

I have been thinking about this for a while, but I could not come up with a proof. I would be thankful for any suggestions or pointers to literature.

\[1\] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC ’88, pages 539–550, New York, NY, USA, 1988. ACM.

# Answer
> 0 votes
If public randomness is allowed, then the two parties apply a common random permutation on their inputs, and XOR their inputs with a common random string.

Suppose that the inputs are $x,y$, and that they differ on the index set $I = \\{i\_1,\ldots,i\_k\\}$. For each permutation $\pi$ of $1,\ldots,k$, we can find a permutation $\alpha$ of $1,\ldots,n$ and a vector $z$ such that $(\alpha(x) \oplus z, \alpha(y) \oplus z) = (0^n,1^k0^{n-k})$, and furthermore, the $k$ initial coordinates originate from $i\_{\pi(1)},\ldots,i\_{\pi(k)}$. Choose such $\pi$ at random.

If we apply a random permutation and then a random XOR on $(\alpha(x) \oplus z, \alpha(y) \oplus z)$, then the resulting distribution is identical to what we would get if we applied a random permutation and then a random XOR on $x,y$ (this is because the object consisting of applying a permutation followed by an XOR forms a group).

If we translate the answer to the final pair to the pair $(\alpha(x) \oplus z, \alpha(y) \oplus z)$, then we get some distribution on the first $k$ coordinates. Translating this back to $(x,y)$, we get a uniformly random coordinate in $I$, since the permutation $\pi$ was random.

---
Tags: randomized-algorithms, communication-complexity
---


# Question
Title: What is the time complexity of adding to a BST if we are to maintain balance
If we have a BST but want to keep it balanced, how much more expensive does adding an element to it become? Clearly adding an element (without maintaining balance) is of time complexity O(log(n)), as we traverse the tree down to the point where we should add the element, but if we want to maintain a balanced tree such that our worse case search time remains O(log(n)), how much more expensive are the operations of

1. Checking if our tree is balanced after we have added an element
2. Balancing the tree through left or right rotations if it is now unbalanced. Thanks

# Answer
> 0 votes
Checking if a tree is balanced is clearly in time linear in the size of the tree.

However, balancing when inserting or deleting nodes can indeed be done in $\mathcal{O}(\log n)$, using AVL trees or red-black trees for example.

# Answer
> 0 votes
The cost of inserting into a height-balanced binary search tree (i.e. an AVL tree) is $O(\log n)$. You would first augment the BST’s data structure so that a height value is stored for each node.

For an insert operation, finding the insertion point takes $O(\log n)$ time. Then, rebalancing the tree requires retracing the path upwards from the insertion point towards the root, which takes $O(\log n)$ time. More specifically, as you go upwards, the height values are updated and you check for height imbalance, performing rotations if necessary. Each rotation takes $O(1)$ time. So the total cost of insertion - of both finding the insertion point and rebalancing - is $O(\log n)$.

---
Tags: binary-search-trees
---


title: Counting the number of parenthesization

text:
# Question
Title: Counting the number of parenthesization
I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says:

> Denote the number of alternative parenthesizations of a sequence of $n$ matrices by $P(n)$. When $n$ = 1, we have just one matrix and therefore only one way to fully parenthesize the matrix product. When $n$ $\geq$ 2, a fully parenthesized matrix product is the product of two fully parenthesized matrix subproducts, and the split between the two subproducts may occur between the $k$th and ($k$ \+ 1)st matrices for any $k$ = 1, 2, ..., $n$ \- 1.

what I don't understand is the the part about the split? what exactly does it mean to split the two subproducts?

# Answer
> 3 votes
The split in a product is between the two outermost pairs of parantheses. For example, in $((a\*b)\*(c\*d))\*(e\*f)$, the split is between the $d$ and $e$ because the last multiplication that is performed is between the results of the products $abcd$ and $ef$. The split tells you where the last multiplication is performed and let’s you decompose the problem into two subproblems.

# Answer
> 4 votes
Suppose you have $n$ matrices $M\_1, M\_2, …, M\_n$.

The product of all matrices is $M\_1\times M\_2\times…\times M\_n$ and since the matrix product is associative, there is no need for parentheses from a mathematical point of view.

However, from a complexity perspective, the product may not takes the same amount of computation time if you compute $M\_1\times (M\_2\times … \times M\_n)$ or $(M\_1\times M\_2)\times (M\_3\times…\times M\_n)$ and so on.

For example, using the naive matrix multiplication algorithm, if $n = 3$ and the dimensions of $M\_1$ are $10 \times 100$, the dimensions of $M\_2$ are $100\times 5$ and the dimensions of $M\_3$ are $5\times 2$, then computing $M\_1\times (M\_2\times M\_3)$ uses $100\times 5 \times 2 + 10 \times 100 \times 2 = 3000$ scalar multiplications, but computing $(M\_1\times M\_2)\times M\_3$ uses $10\times 100 \times 5 + 10 \times 5 \times 2 = 5100$ scalar multiplications.

The split the book is talking about is about the position of the parentheses in the computation, separating the computation of $n$ matrices into the product of two matrices, the first one being the result of $M\_1\times … \times M\_k$ and the second one of $M\_{k+1}\times …\times M\_n$, for a certain $k\in \\{1, …, n-1\\}$.

---
Tags: dynamic-programming, matrices
---


# Question
Title: Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$

I've tried this formula on an example where n =5 and k = 2 and I can't even find 5 walks. Any help understanding this formula and example would be greatly appreciated. Thanks.

# Answer
> 2 votes
I think there may be a mistake in your statement, unless you allow a walk to stay in the same vertex on a step, instead of crossing an edge (but that's not the usual definition of walk), or unless you consider each vertex in a complete graph to have a loop (but again, that's not the usual definition).

I think you could do a proof by induction on $k$, distinguishing the cases where $u = v$ and $u \neq v$. Denote $A(k)$ the number of walks of length $k$ from $u$ to $v$ **if we suppose $u = v$** and $B(k)$ **if we suppose $u \neq v$**.

* the base cases are as follow:

+ $A(1) = 0$ (there is no edge from $u$ to itself); $A(2) = n-1$ (a $2$-walk is $u-w-u$, with $w\neq u$);
    + $B(1) = 1$ (there is exactly one edge from $u$ to $v$); $B(2) = n-2$ (a $2$-walk is $u-w-v$ with $w\neq u$ **and** $w\neq v$);
* the induction case can be described as such: a walk of length $k+1$ from $u$ to $v$ is $u-w\sim v$, where $w\sim v$ is a walk of length $k$ from $w$ to $v$.

+ if $u = v$, then $w\neq u$ and $w\neq v$, and there are $n-1$ choices for $w$. That means that $A(k+1) = (n-1) B(k)$;
    + if $u \neq v$, then $w\neq u$, but $w$ could be equal to $v$. Distinguishing the cases $v = w$ and $v\neq w$, we get $B(k+1) = A(k) + (n-2)B(k)$.

Combining the two, we get $B(k+1) = (n-1)B(k-1) + (n-2)B(k)$. This is a constant-recursive sequence of order $2$.

Solving this, we get an expression $B(k) = \alpha(-1)^k + \beta(n-1)^k$. Since $B(1) = 1$ and $B(2) = n-2$, that means that $\alpha = -\frac{1}n$ and $\beta = \frac1n$. We conclude that: $$B(k) = \frac1n((n-1)^k - (-1)^k)\qquad A(k) = \frac1n((n-1)^k+(-1)^k(n-1))$$ This is indeed an integer.

For example, the number of walks of length $3$ in a complete graph of order $5$ from the vertex $1$ to the vertex $3$ is $\frac15(4^3-(-1)^3) = \frac{65}5 = 13$. Indeed, those walks are: $$1013, 1023, 1043, 1203, 1213, 1243, 1303, 1313, 1323, 1343, 1403, 1413, 1423$$

---
Tags: graphs, discrete-mathematics, graph-traversal
---


# Question
Title: Are there any freely available resources to study randomized algorithms?
I am a student want to study randomized algorithm. Someone recommend cs271 to me, but it's restricted now.

Can someone recomend a good resource to study randomized algorithm, thank you a lot.

# Answer
A few days ago, my tutor recommend Stanford cs265 to me. I have read some lectures and watched some videos, I think it's really a great course for those who want to study randomized algorithm.
> 2 votes

# Answer
I can recommend you the book from Michael Mitzenmacher and Eli Upfal called "Probability and Computing". I bought a hard copy of it recently and I absolutely don't regret it. It's very detailed and goes through many different probabilistic tools along with important chapters from randomised algorithms. It is complemented by various examples and some programming exercises. You can find a copy of it here
> 1 votes

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free
Given that $\\#\notin \Sigma$ and $L\subseteq \Sigma^\*\\#\Sigma^\*$, prove that if $L$ is context-free language then $L' = \\{w\_2\\#w\_1 \mid w\_1\\#w\_2\in L\\}$ is context-free. I'm trying to prove this in this way:

1. because $L$ is context-free then $G$ is context-free grammar for $L$, then $L(G)=L$.
2. by showing that the reversed grammar $F$ of $G$ is the same grammar of $L$ and because $G$ is context-free then $F$ is context-free then $L(F)=L'$ is also context-free. but can't figure out a way to prove this, so I need help to do this.

# Answer
> 1 votes
There is a unique path in the derivation tree that leads from the axiom $S$ to the terminal symbol $\\#$. An idea would be to turn this tree upside down along that path.

This solution follows the construction for the closure under cyclic shift for context-free languages, as suggested in the book by Hopcroft and Ullman.

---
Tags: regular-languages, context-free, computation-models
---


# Question
Title: Find the largest subset of unpaired elements
I have a large list (around 200k) of element pairs `(e.g. A-B, A-C, B-C, ...)`. How can I find the largest subset of elements amongst which none are paired?

Example of pairs:

```
A-B
A-C
A-F
B-C
C-D
E-F
F-G

```

Here the largest subset would be of size 4, and one of the subsets with size 4 would be: `{A,D,E,G}`.

# Answer
Let $G$ be the graph whose edges are the given pairs. Then, the problem is to find a maximum independent set in $G$. There exist algorithms for this, but this problem is NP-hard in general.
> 2 votes

---
Tags: algorithms, optimization, np-complete, sets
---


title: Dynamic routing algorithm

text:
# Question
Title: Dynamic routing algorithm
In static routing where the network parameters dont change, we can use Djikstra's or Bellman-Ford's algorithm to find the shortest path to send data from source to destination.However in dynamic routing how do we do that?

# Answer
$DVR($uses Bellman-Ford algorithm to reach the next hop e.g., $RIPv\_1)$ and Link state$($uses Dijkstra algorithm for finding the shortest path to keep the knowledge of entire topology e. g. $OSPF)$ is the example of dynamic routing protocol.

In dynamic routing routers exchanges the routes (routing database) periodically with neighbors (for $DVR$) or with whole entire topology(for $OSPF$) to confirm that "is there any change has made in route"? For example if there is any broken has happen in route then router will find alternative route to reach any other router.
> 1 votes

---
Tags: computer-networks, weighted-graphs, dynamic-graphs
---


# Question
Title: Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal
I want to construct a context-free grammar for this language:

\begin{align\*} L = \\{uc^nd^nv\mid \ u,v \in \\{a,b\\}^\* \text{ and the number of a's and b's in } uv \text{ are equal}\\} \end{align\*}

I know how to contruct a grammar for a language that has words with an equal number of a's and b's: \begin{align\*} &S\to aSb \\ &S\to bSa \\ &S\to SS \\ &S\to \epsilon \end{align\*} I also know how to construct $c^nd^n$: \begin{align\*} &S\to cSd \\ &S\to \epsilon \end{align\*} Could you give any hints how to combine these rules?

# Answer
> 2 votes
Consider the following operation on context-free languages. For $L\subseteq \\{a,b\\}^\*$, we have $L\_\square = \\{ u\square v \mid uv\in L\\}$, where $\square$ is a new symbol. Thus $L\_\square$ adds a single symbol $\square$ at an arbitrary position in the strings of $L$. That position of $\square$ can be used for the axiom to "insert" another language in your strings, by putting the axiom of this other language at that position.

How do we add a single new symbol? By tracing a path in the derivation tree, using "marked" copies of the original nonterminals, until one of these marked copies "drops" the symbol $\square$ in the string.

In your specific case that means introducing productions like $\hat S\to a\hat Sb$, $\hat S\to \hat SS$, $\hat S\to S\hat S$, $\hat S\to \square aSb$, $\hat S\to a\square Sb$ and more.

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


# Question
Title: Can quantum computers be modelled as a classical computer with access to an oracle?
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.

and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as opposed to $O(n2^n)$ time.

We can usually reduce time complexities by pretending that we can do some thing faster - introducing oracle's that can solve a problem instantly.

Is there a constant time oracle that encodes all the quantum speed ups we get?

# Answer
> 2 votes
Vacuous answer: because $\text{BPP}^\text{BQP} = \text{BQP}$, giving a computer access to a $\text{BQP}$ oracle makes it equivalent to a quantum computer at solving decision problems in polynomial time. This is sort of like saying "if your computer has access to a quantum computer, then you have access to a quantum computer" but it does meet the criteria in your question.

Also, quantum computers can't do a Fourier transform on $2^n$ bits in $O(n^2)$ time. Quantum computers can apply a Fourier transform to the state vector of $n$ qubits in $O(n^2)$ time. It's not at all the same thing.

# Answer
> 1 votes
Technically, the main differences between classical and quantum algorithms are **super-position** and **entanglement** that make the concept of oracle in quantum algorithms. As these two are only meaningful in quantum mechanics, you can't have that oracle with the same cost as the quantum algorithms, in classical algorithms.

# Answer
> 0 votes
Yes. BQP has problems that are complete for BQP. So, an oracle for any BQP-complete problem suffices.

# Answer
> 0 votes
Let me add to the previous questions that BQP capture the power of quantum computers for decision problems, but there are other algorithmic tasks to consider. It is a reasonable conjecture that equipping a BPP computer with an oracle for BQP complete problems does not enable performing quantum sampling (or even just boson sampling). And perhaps this conjecture remains true if you equip it with a PH oracle as well!.

It seems likely that equipping a classical computer with quantum sampling powers give it full BQP power. I don't know about other algorithmic tasks for quantum computers that leads to interesting complexity classes, e.g. even more powerful than quantum sampling.

---
Tags: time-complexity, quantum-computing, oracle-machines, oracles
---


# Question
Title: If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?
I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable?

I think it is Undecidable since if ¬P holds then P doesn't hold, and the characteristic function of P is undefined when P doesn't hold so we can't come up with a characteristic function that results in 1 when ¬P holds.

However, I'm not sure if my answer and reasoning are correct. It'll be helpful if you can shed some light on this.

# Answer
There is no definitive answer. If predicate $P$ is partially-decidable, $\neg P$ can be decidable, partially-decidable or undecidable.

* Let $P(n)$ be "is $n\>1$?". $P$ is partially decidable. $\neg P(n)$ is "is $n\not\gt 1$?", which is decidable. (Note that a partially-decidable predicate such as $P$ can be decidable.)
* Let $P(n)$ be "is $n\>1$?". $P$ is partially decidable. $\neg P(n)$ is "is $n\not\gt 1$?", which is partially-decidable. (Note that a decidable predicate is also partially-decidable.)
* Let $P(n)$ be "does the $n$-th Turing machine halt on blank tape?". $P$ is partially decidable. $\neg P(x)$ is "does the $n$-th Turing machine run forever on blank tape?", which is undecidable.

A predicate is called co-partially-decidable if its negation is partially-decidable.

To summarize, if predicate $P$ is partially-decidable, then $\lnot p$ is co-partially-decidable. A co-partially-decidable predicate can be decidable, partially-decidable, or undecidable. (If you think I am saying nothing, then you have understood the situation clearly.)

By the way, "partially-decidable" is also named "computably-enumerable (c.e.)", "recursively-enumerable (r.e.)", "semi-decidable", or "Turing-recognizable". You may add the prefix "co-" to each of them.
> 2 votes

---
Tags: undecidability, semi-decidability, decidability
---


# Question
Title: Pushdown automaton that accepts $a^{2k} b^{3k}$, without multiple pop
I am trying to create a PDA with at most 7 states that accepts the following language over the alphabet $\Sigma = \\{a,b\\}$:

$$ \\{a^{2k}b^{3k} \mid k \geq 0\\} $$

The tricky part is that multiple push allowed but multiple pop is not allowed. I was able to find the easy solution when multi push/pop is allowed. I am looking for solutions where ***multi push/pop is not allowed*** and ***multi push is allowed but multi pop is not allowed.***

# Answer
For every second $a$ that you read, push $BBB$ into the stack.
> 1 votes

# Answer
Here is another solution. For every $aa$ you could check every $bbb$(skips first $b$, keep stack's present top $a$ as it is and pop $2a$ against for last $2b$).
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?
If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata?

Bonus question: Can we think of the universe as a big ass DFA? (Standart Model, interaction of particles, etc.)

Sorry for the long list of questions. I am curious about this topic and I found these questions related.

# Answer
> 1 votes
DFAs have a bounded amount of memory. In contrast, PDAs and Turing machines can use an unbounded amount of memory. The amount of memory used by a PDA or a Turing machine at any given time is finite, but is not necessarily bounded.

For example, the standard PDA for the language of all words of the form $a^nb^n$ uses $\Theta(n)$ memory. In contrast, a DFA uses at most $C$ memory, where $C$ is some constant which depends on the DFA but not on the input.

Most accounts of the physical world involve real numbers having infinite precision. In order to represent these exactly you truly need an infinite amount of memory.

# Answer
> 0 votes
Finite automata can have any amount of memory, but it will always be finite. Pushdown automaton and Turing machine do have unbounded memory at their disposal.

Apart from that, the Turing machine concept is an answer to the question what is an algorithm. In the same way the equivalence between context-free grammar and push-down automaton has taught us about the relation between recursion and stack computations.

One can turn the question around and ask What is the point of finite automata? as Turing machines are more powerful? The answers to that question are enlightening and tell us that each model comes with suitable concepts and properties.

---
Tags: complexity-theory, turing-machines, finite-automata, pushdown-automata
---


# Question
Title: Given a set of 2D vectors, find the furthest reachable point
> Input: a set of 2D vectors $S=\\{v\_1,v\_2,\dots,v\_n\mid v\_i\in \mathbb{Z}^2 \\}$
> Question: name $P=\\{\sum\_{v\_i\in S'}v\_i\mid S'\subseteq S \\}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In words, $P$ is the set of all possible vectors we can form by adding vectors from $S$.
> What is the length of the longest vector in $P$?

An idea:
(An easy observation is that if all $v\_i\in S$ are in one orthant (or quadrant?) we just have to add them. If the vectors are in on hyperplane this is not true.) Start from an arbitrary vector $v\_1\in S$, get the next one $v\_2$ (either left or right) and add $V=v\_1+v\_2$. Generally, at each step $V=V+v\_i$. Continue this while $|V|$ is increasing.

At some time we find $v\_j$ such that $V=V+v\_j$ shortens. Set $V=V-v\_1+v\_j$ and continue. The idea is to maintain a "window" where we add all the vectors inside. If the next vector (the one side of the window) does not add, remove the first one (the other side of hte window).

I know I am not clear enough but hope you get the idea.

Is this correct? Am not sure...
An other ideas/approaches?

(This, of course, can be generalized to any dimension $k$. I mentioned the 2D case because it is easy to visualize.)

I am looking for algorithms with polynomial time on $n=|S|$.

Related problem: lattice problems.

Let set $S$ be the basis of the lattice $L$. Then $L$ is defined as $$L(S)=\\{\sum\_{i=1}^{n}a\_i v\_i \mid v\_i\in S, a\_i\in\mathbb{Z}\\} $$

Our set $P$ is a special case if, instead of $a\_i\in\mathbb{Z}$ we let $a\_i\in \\{0,1\\}$.

# Answer
Suppose you knew the direction $\hat{d}$ of a longest vector sum. Then finding a subset of vectors that should be included in the longest-vector sum is trivial:

* Include $v$ when the dot product $v \cdot \hat{d} \> 0$.
* Exclude $v$ when $v \cdot \hat{d} \< 0$.
* There won't be a $v$ where $v \cdot \hat{d} = 0$, unless $v=0$, because that contradicts $\hat{d}$ pointing towards a longest vector sum.

Now consider what happens if we vary $\hat{d}$ away from the optimal direction to get $d^\prime$. The sum-along-directions stays constant... until we turn so much that one of the dot products $v \cdot d^\prime$ switches sign. That only happens when $d^\prime$ is perpendicular to a $v$.

Since we're working in 2-d, we can think in terms of angles instead of directions. We have a function $f(\theta)$ that adds up all vectors $v$ even-slightly-aligned with the angle $\theta$. And we know this function only changes values when $\theta$ is perpendicular to one of the vectors $v$. And we know there are at most $2n$ such critical angles.

Ah.

# Algorithm

Make a list of all the critical angles where $f(\theta)$'s value changes due to $\theta$ being perpendicular to a $v$. Sort the list. Find a maximizing $\theta$ by sampling $f$ at the midpoint between each contiguous pair of critical points (remembering to include the midpoint where the angles wrap around). Use that $\theta$ to recover a best set of vectors.

By adjusting the total as vectors cross in and out of alignment, instead of recomputing it every time, the algorithm will run in time $O(n \log n)$ with the most expensive step being the sorting of the critical points.

Here's some quick and dirty pseudo-code. WARNING: THIS CODE WAS WRITTEN BY HAND WITHOUT BEING RUN OR TESTED. IT WILL CONTAIN BUGS.

```
import math

def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]

def vec_sum(vecs):
    t = [0, 0]
    for v in vecs:
        t[0] += v[0]
        t[1] += v[1]
    return tuple(t)

def vectors_along(vec_set, angle):
    d = (math.cos(angle), math.sin(angle))
    return [v for v in vec_set if dot(d, v) > 0]

def transitions(vecs):
    # compute (critical-angle, vector, entering-vs-leaving) tuples
    results = [(t % (2*math.pi), v, b)
               for v in vecs
               for (t, b) in [(math.atan2(v[0], -v[1]), True),
                              (math.atan2(-v[0], v[1]), False)]]
    return sorted(results, key=lambda e: e[0])

def longest_subset(vecs):
    best_angle = None
    current_total_vec = None
    best_norm = 0
    for transition, vec, entering in transitions(vecs):
        # TODO: If two transitions are less than 0.00001 apart this fails
        # TODO: In particular, equal/opposite vectors cause equal transitions.
        angle = transition + 0.00001
        if current_total_vec is None:
            current_total_vec = vec_sum(vectors_along(vecs, angle))
        else:
            current_total_vec += vec * (1 if entering else -1)
        current_norm = dot(current_total_vec, current_total_vec)
        if current_norm > best_norm:
            best_norm = current_norm
            best_angle = angle
    return vectors_along(vecs, best_angle)

```

# Higher Dimensions

This idea works quickly in 2d, but in 3d the boundaries that add/remove a vector from the along-direction sets are great circles instead of points. So everything gets more complicated and more expensive there and continues to get more complicated as you go to higher dimensions.
> 3 votes

# Answer
This problem appears on the competitive programming contest here:

https://szkopul.edu.pl/problemset/problem/NZSCUwz2ACePsBKuVCIVzrRt/site/?key=statement

Apparently it's the Polish Olympiad in Informatics 2018.

The problem has $n \le 200,000$ vectors, meaning that any brute force solution won't work.

I solved this problem in $O(N \log N)$ with a polar sort, so I'll share how I did it. Assume we start at $(0, 0)$.

1. Polar sort all vectors $O(N \log N)$
2. Traverse all vectors in $O(N)$ and do the following with Two-Pointers:

```
long long calculate(const vector<Point>& points) {
  Point curr{0, 0};
  long long ans = 0;

  for (int i = 0, j = 0; i < (int)points.size(); i++) {
    curr = curr + points[i]; // vector addition

    while (j < i) {
      const long long new_dist = (curr - points[j]).magnitude();

      if (new_dist > curr.magnitude()) {
        curr = curr - points[j];
        j++;
      } else {
        break;
      }
    }

    ans = max(ans, curr.magnitude());
  }

  return ans;
}

```

In this case, magnitude is the squared distance, so it's always an integer. Either apply square root afterwards or keep it like that, whatever you need.

In my implementation, I had to do 4 polar sorts in total. I assume this is because the code misses some corner case.

```
long long a, b, c, d;

sort(points.begin(), points.end());
a = calculate(points);

reverse(points.begin(), points.end());
b = calculate(points);

// Reflect the X coordinate, so that
// the next polar sort sorts the points differently (?)
for (Point& p : points) p.x *= -1;

sort(points.begin(), points.end());
c = calculate(points);

reverse(points.begin(), points.end());
d = calculate(points);

// Final answer
cout << max({a, b, c, d}) << endl;

```

Observation: The subset of vectors chosen (in the optimal solution) is always a subarray of the polar sorted vectors, in other words, the vectors are contiguous. I verified this with brute force as well (by traversing all subsets in $O(2^n)$).
> 1 votes

# Answer
The complexity of your problems depends on whether the vectors are represented in unary or binary.

## Unary

If the vectors are represented in unary, all of the problems you mention can be solved in polynomial time using dynamic programming.

You introduce an array $A\[\cdot,\cdot,\cdot\]$ where $A\[k,x,y\]=1$ if there's a subset of $v\_1,\dots,v\_k$ that sums to the vector $(x,y)$; the array has polynomial size, and can be filled in in polynomial time. Then by iterating over the entries of $A\[n,\cdot,\cdot\]$, you can find the shortest vector, the longest vector, the closest vector to any other desired vector, and the convex hull.

## Binary

If your vectors are represented in binary, the shortest vector problem is NP-hard by a reduction from subset sum. Given integers $x\_1,\dots,x\_n$, we form two-dimensional vectors by $v\_i=(x\_i,0)$. Then the shortest vector in $P$ has length 0 if and only if there is a subset of $x\_i$'s that sum to zero. Thus, if you had an efficient algorithm for your shortest vector problem, you could solve subset sum efficiently. Since subset sum is NP-complete, it follows that you're unlikely to be able to find an efficient algorithm for the shortest vector problem you describe.

I don't know what the complexity of the longest vector problem is, but I suspect you might be able to find a reduction from some other NP-hard problem (e.g., something knapsack-related).
> 0 votes

---
Tags: algorithms, optimization, computational-geometry
---


# Question
Title: Algorithm to calculate lower incomplete gamma function
I'm trying to understand the implementation of the algoritm here. Please see GammaLowerRegularized(a, x) function.

I understand 1st part of the function for `x <= 1 || x <= a`. The authors use Kummer's confluent hypergeometric function `M(1,a,x)`, because it converges under the specified conditions.

But don't understand the rest of the algorithm. On each iteration the following ratio is calculated:

`(p2*z - p3*yc) / (q2*z - q3*yc)`

Here is the code fragment:

```
        public static double GammaLowerRegularized(double a, double x)
        {
            const double epsilon = 0.000000000000001;
            const double big = 4503599627370496.0;
            const double bigInv = 2.22044604925031308085e-16;

            double ax = (a*Math.Log(x)) - x - GammaLn(a);

            // ...Skipped...

            int c = 0;
            double y = 1 - a;
            double z = x + y + 1;

            double p3 = 1;
            double q3 = x;
            double p2 = x + 1;
            double q2 = z*x;
            double ans = p2/q2;

            double error;

            do
            {
                c++;
                y += 1;
                z += 2;
                double yc = y*c;

                double p = (p2*z) - (p3*yc);
                double q = (q2*z) - (q3*yc);

                if (q != 0)
                {
                    double nextans = p/q;
                    error = Math.Abs((ans - nextans)/nextans);
                    ans = nextans;
                }
                else
                {
                    // zero div, skip
                    error = 1;
                }

                // shift
                p3 = p2;
                p2 = p;
                q3 = q2;
                q2 = q;

                // normalize fraction when the numerator becomes large
                if (Math.Abs(p) > big)
                {
                    p3 *= bigInv;
                    p2 *= bigInv;
                    q3 *= bigInv;
                    q2 *= bigInv;
                }
            }
            while (error > epsilon);

            return 1d - (Math.Exp(ax)*ans);
        }

```

Could you please explain 1) what series is calculated in this function and 2) what approximation approach is used? Or maybe you can suggest another good implementation?

The difference between lower incomplete gamma function and regularized lower incomplete gamma function doesn't matter for me, because the algorithms are almost identical.

# Answer
> 2 votes
It seems that the algorithm is based on the approximation of the following continued fraction:

(The image from the Boost C++ Library documentation)

To approximate such a fraction one can use the following recursion:

The result of approximation is value of the upper incomplete gamma function. Lower incomplete gamma function can be derived using the following equation:

`LowerGamma(a, x) = Gamma(a) - UpperGamma(a, x)`

---
Tags: numerical-algorithms, numerical-analysis
---


# Question
Title: Count-to-infinity avoidance techniques and hold-down timeout based question
I am trying to understand count-to-infinity avoidance techniques, and came across this topology. Now, suppose the **interface eth1 on R1 has gone bad**, and assuming that split horizon, triggered updates and poison reverse are all enabled, what is the effect of hold-down timeout on convergence? Will it help to avoid the count-to-infinity problem or unnecessarily delay the learning of alternate routes?
Any help on this would be appreciated!

# Answer
> 1 votes
**Holddown Timer** is another loop-prevention mechanism employed by distance vector routing protocol($DVR$). This feature prevents a router from learning new information about a failed route. When a router receives the information about the unreachable route, the holddown timer is started. The router ignores all routing updates for that route until the timer expires (by default, $180$ seconds in $RIP$). Only updates allowed during that period are updates sent from the router that originally advertised the route. If that router advertise the update, the holddown timer is stopped and the routing information is processed.

In your example Router $R\_1$ has advertised its directly connected subnet $R\_2$ through $RIP$. After some period of time, the interface $Eth1$ on $R\_1$ fails and the router $R\_1$ sends the poisoned route to $R\_2$. $R\_2$ receives the routing update, marks the route as unreachable and starts the **holddown timer**.During that time all updates from any other routers about that route are ignored to prevent routing loops. **This allows more time for the network to converge**.

If interface $Eth1$ on $R\_1$ comes back up, $R\_1$ again advertises the route. $R\_2$ process that update even if the holddown timer is still running, because the update is sent by the same router that originally advertised the route.

Reference

---
Tags: computer-networks, routing
---


# Question
Title: Is infinitely fast computer fundamentally impossible even theoretically?
This may get slightly philosophical, but consider the following program:

```
bool lampState = false;
TimeSpan timeout = 1;
while (true)
{
    lampState = !lampState;
    Thread.Sleep(timeout);
    timeout = timeout / 2;
}

```

DotNet Fiddle link for C# code

This is obviously an implementation of Thomsons lamp in C#.

So the question is what is the value of lampState after 2 seconds of execution?

Lets assume that no physical law prevents us from constructing an infinitely fast computer. Static code analysis shows that we will never exit the while loop. Does this mean that we can have an algorithm that is arbitrary fast, but not infinitely fast, not even theoretically (because we run in to a contradiction?

# Answer
No, it doesn't mean that.

The problem with Thompson's lamp is that a particular state of an abstract machine is not well-defined. This is nothing unusual. E.g., dividing by 0 also yields an undefined value, because any value we could choose would lead to inconsistencies with *other* definitions that we would like to keep - at any rate, more than the isolated, unimportant definition of 1/0.

Abstract machines can be implemented in real machines, but there are limits; one if them is that you have only finite matter, space and time available. Therefore, infinitely fast machines, just as infinitely big machines, *cannot* be implemented. This merely means that we cannot check the question by physical experiment.

There are many other machines that are infinitely large that we also can't build, but which at least yield a well-defined prediction (for instance, the machine that never does anything would leave the state at the initial value). Those machines cannot be tested by experiment, but they *can* be predicted theoretically. This machine cannot even be predicted, because it has been carefully defined to fall into an undefined niche of logics.

But this has nothing to do with the question how fast an algorithm can be. There are many algorithms of which we do not know whether (given enough time) they eventually terminate. Some of these may be testable by running them and waiting long enough, but since we don't know how long "long enough" is, physical experiment can only ever give the answer "yes", but never "definitely no".

Therefore you shouldn't be too worried about the fact that a certain machine can't actually be built. Some problems are better handled via experiment, and some via theory. Those that cannot be handled either way are vexing, but almost always they are far removed from any practical problem that we *really* need to solve.

Example: if mathematics weren't incomplete, i.e. it it **were** possible to determine the truth of any propositional formula via a single algorithm, mathematicians would be glad, but everyday life would not be much affected. Even knowing P = NP would do little; it is one thing to know that a prime can be factored in polynomial time, quite another thing to be actually able to do it.
> 11 votes

# Answer
There is a problem with the idea of "infinitely fast." If speed of execution is the number of instructions per time unit, and the speed is infinite, it means that the time between instructions becomes zero.

That would mean that all the instructions execute simultaneously, but then one instruction can't use the results from the preceding, so the algorithm falls apart.

So my the answer to your final question would be yes.
> 7 votes

# Answer
*Disclaimer: This post is written by a layman, without any theoretical computer science knowledge beyond what is typically known to laymen programmers.*

*Readers seeking a formal approach should instead read about Hypercomputation.*

---

*My post does not directly answer the question (about Thomson's Lamp), but discusses the properties of an insanely fast computer, and hinting at that Thomson's Lamp is itself not possible to implement on a computer that is merely insanely fast, simply because it won't see its RTC increment beyond any time period required to make the first toggle of its light switch.*

*By definition, a Thomson's Lamp requires an RTC connected to the physical notion of time, which cannot be implemented if it has no access to any RTC or the outside world, and in particular cannot be implemented on top of software's own measurement of execution progress.*

---

Instead of considering a literally infinitely fast computer, we first consider an "*insanely*, but still *finitely* fast" computer.

The computer may or may not have access to a "real time clock" (RTC). An RTC is a device accessible by the computer (and by the software) that is able to tell time as it passes through.

---

In the absence of any RTC, the only notion of progress (changes in states) would be the effects of the execution of the program:

* The program must execute its own executions;
* The program can perform arithmetic operations and memory operations
    + In particular, the program can implement an integer counter, and increment it one at a time.
        - See note on "optimization".
    + Or, it may implement a mathematical operation that is hard to optimize, so that the computer has to actually carry out the steps.

---

*(Note on optimization.)*

* A for-loop that executes an increment on an integer variable for a million times, may be replaced by code that simply implement the same integer variable by one million, in a single step.
* A for-loop that repeated evaluates the same expression, when every such evaluation can be shown (proven by a compiler) to give the same numerical result (with no other side-effects, i.e. changes to other program variables), it could be moved out of the for-loop.
* A program that is originally written to first performs some heavy-lifting (known to consume some amount of time), and then sets a flag to indicate "completion", may be transformed into another program that sets the "completion" first, and then chuck along the heavy-lifting.
* There are many others; but **for every computer to be a computer, there must be some kind of operations, or workloads, for which it must *(had to)* carry out multiple steps, without the possibility of obtaining the calculation result in a magically faster way.**

The subsequent discussion will focus on the use of such **irreducible** computation operations to observe the notion of progress.

---

---

For the sake of time, now we go back to the thing mentioned earlier - the RTC, or any time-telling device.

As the computer gets more and more *insanely* faster, it will observe that the RTC "goes slower" in the relative sense. That is, if the computer is set to perform a possibly unbounded number of operations in a loop (and count the numbers of operations performed) until the RTC has shown a certain amount of time has elapsed, a faster computer will find that it could run more operations in that time period.

So, a truly theoretically infinitely fast computer will:

* If its own progress-counter has a finite precision, it will overflow before any amount of real-world time has elapsed.
    + This is no laughing matter. The standard library (runtime) of the famous Turbo Pascal 5, 6 and 7 had an infamous RTC speed calibration overflow that is exactly like this. It essentially turned Turbo Pascal into an *abruptly obsolete* programming environment by the turn of the century.
* If the program implements a progress-counter using arbitrary-precision integers, one which allocates more memory to account for the need for bits to represent the counter's increasingly larger values, then as ***Pieter B*** mentioned in a comment - it will consume memory at a rate proportional to `O(log Freq)`. The eventual outcome depends on whether the computer has finite or infinite memory.
* If the program does nothing but just repeatedly querying the RTC, it will see that the RTC never seems to move.
    + Again, this is no laughing matter. Search "dead RTC".
> 2 votes

# Answer
In any given physical implementation, there's an incompressible minimum of time between two instructions. The interval of time between two runs of the loop is not the argument you pass to `Thread.Sleep`, but the sum of the time that `Thread.Sleep` spends in waiting plus the time it takes to execute the rest of the loop: the function call to `Thread.Sleep`, the calculation of the new timeout value, the calculation of the new lamp state. Even if the program simply had `Thread.Sleep(0)` all along, you'd have a tight loop that still takes nonzero time per iteration.

In a theoretical machine model, you can make the time it takes to run instructions as small as you like, but it's still nonzero. In fact, most models of computation don't actually care about time as defined by clock values; they only care about time in the sense that one thing happens after another: time is *defined* by the sequence of instructions. So, from a theoretical perspective,

```
while (true)
{
    lampState = !lampState;
    Thread.Sleep(timeout);
    timeout = timeout / 2;
}
print(lampState);

```

isn't all that different from

```
while (true)
{
    lampState = !lampState;
    timeout = timeout / 2;
}
print(lampState);

```

from which you can eliminate the unused variable `timeout` and get

```
while (true)
{
    lampState = !lampState;
}
print(lampState);

```

which is a perfectly well-defined program.

As long as you keep a model of sequential execution, where one thing happens after another, you still have to spend at least the time to perform `lampState = !lampState` at each iteration, so each iteration takes some time. The final instruction `print(lampState)` is unreachable — it'll never run. This is an important consideration when analyzing programs — for example, the snippet above matches the requirement “this program must not print the lamp state”.

Classical models of computation define the program's behavior by assigning a value of each variable to each clock tick — the behavior of the program is defined as $\ell : \mathbb{N} \to \\{\mathtt{false},\mathtt{true}\\}$ where $\ell(t)$ represents the value of `lampState` at clock tick $t$ and $\mathbb{N}$ is the set of nonnegative integers. Recall that time is defined as one thing happening after another; conventionally we represent the starting time of the program as $0$, and $\ell$ alternates between $\mathtt{true}$ and $\mathtt{false}$. You can choose a time scale; but things happening another *define* a time scale, where `lampState = !lampState` is the smallest discernible event, and in this timescale, $\ell$ alternates between $\mathtt{true}$ and $\mathtt{false}$ at each clock tick. Even if you choose a different clock, this one exists.

Now when dealing with theory, you can define a new meaning for the syntax. In the time scale defined by flipping the lamp taking one clock tick, “after the execution of the loop” means an infinite clock value, in the sense that this clock value is larger than any finite clock value — the clock tick represents an event that comes after all possible counts of execution of the loop body. Mathematicians have long thought about how you could have numbers that are larger than any finite number, and came up with infinite ordinals. Of course, infinite ordinals don't enjoy all the nice properties of finite ordinals; c'est la vie.

A sequence of finite ordinals (i.e. integers as we known them) that continues with infinite ordinals is called *transfinite*. So what we're looking here is at *transfinite time*.

(Note that I'm saying that time reaches infinite values, with the time spent per instruction remains constant. You could say that instead the time spent per instruction goes down to zero, and the time value remains finite. But all that does is change the time *scale*, not change the semantics — the notion of time defined by the succession instruction still exists, whether you call the time values $0,1,2,3,4,\ldots$ or $0,\frac{1}{2},\frac{3}{4},\frac{7}{8},\frac{15}{16},\ldots$.)

So what is the value of `lampState` when time reaches the smallest non-finite ordinal (which mathematicians write $\omega$)? You get to choose! It's theory, remember? When dealing with theory, definitions are purely arbitrary. *Useful* definitions, of course, are motivated by considerations such as practical applications, possibilities for further theoretical considerations, and aesthetics. It's hard to see what practical application defining $\ell(\omega)$ could have. Aesthetically, there's no reason to favor one value over the other.

And theoretically? All signs point to *leaving the value undefined*. The function $\ell$ defined by the instruction clock ($\ell(x) = \mathtt{true}$ if $x$ is odd, $\ell(x) = \mathtt{true}$ if $x$ is even) is not continuous at $\omega$. If you took calculus in college, you've probably studied continuity of functions of real variables. The same concept is also useful with other kinds of mathematical objets when studying computation, notably on posets to define the semantics of programs. A lot of reasoning relies on continuous functions. Defining $\ell(\omega)$ would be very much like defining the value of $0/0$: you can declare that $0/0 = 42$ if you like, but it won't buy you anything — that new definition won't help with any algebraic theorem about multiplication and division that only holds for nonzero values.

If you'd like to read more on this topic, models of computation with infinite time are called hypercomputation.
> 2 votes

# Answer
The universe is finite, not infinite. Any finite volume of space contains only a finite amount of information.

Your machine would require an infite amount of states. Therefore your idea can never work. Even with infinite time.
> 1 votes

# Answer
*Oh that's easy! **It's `false`.***

We just need to know how many computations occur and determine whether it's an even or odd number! So ...

If we have,

```
t = time for a single Loop
N = Number of loops
T = Total execution time

```

And we know that the basic relationship between these variables is:

```
t * N = T

```

And since an **infinitely** fast computer must be capable of executing an infinite number of loops `N` in *any* `T`, it follows that a value `t` must satisfy `N = <infinity>` with any `T`:

```
t = T / <infinity>

```

Hence, our time per loop `t` is necessarily `0`:

```
0 = T / <infinity>

```

And now things become clear, `t` is actually a constant. And if we plug our constant `t` into the initial equation:

```
0 * N = T

```

We see that for any `N`, `T` is also always `0`!

So, regardless of our total runtime limit `T`, the actual runtime is always `0`. Substituting `0` for `T`:

```
t * N = 0

```

And with a little basic algebra:

```
N = 0 / t

```

For any value `t`, the total number of executions is `0`. And the state of `lampState` remains unchanged.

**And this can be proven empirically.** By simply setting the loop-cycle duration `t` on your own computer to `0` (turn the power off), you'll find that it does absolute nothing.
> 1 votes

# Answer
Malament-Hogarth space-times allow for infinite computations to be performed in finite time (in the observer's frame of reference), by essentially placing a classical computer into a black hole and then retrieving it. Practically, there are some difficulties in extracting intact objects from a black hole, but the theoretical framework is there.
> 1 votes

# Answer
Many years ago I was asked for help by a mate who studied economics. His professor had developed a model for work per time: After you perform X units of work, your experience grows, and therefore you can perform one unit of work Y percent faster. And my mate couldn't wrap his head around it.

Since you ask about theoretical, a model of computation made by a professor of economics surely counts. And with his model, you can easily figure out that you can perform any amount of work in some fixed time.

Let's translate this into computers. Assume you have a computer that today runs with a clock speed of 1GHz. And every trillion clocks the clock speed increases by exactly 1 percent. With this model, your computer can do an unlimited amount of work in exactly 101,000 seconds. (Note that the time until the clock speed doubles gets exponentially shorter). Most of the work will be done in the last second.
> 0 votes

---
Tags: computation-models, hypercomputation
---


# Question
Title: Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?
I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?

# Answer
You can use $\\{0,1\\}$ if you want, and this point of view appears in many applications, for example in combinatorics and random graph theory. What is important is that you use the Fourier basis.

Sometimes other bases are used. For example, every function $f\colon \\{0,1\\}^n \to \mathbb{R}$ can be expressed in the form $$ \sum\_{S \subseteq \[n\]} \tilde{f}(S) x\_S, \text{ where } x\_S = \prod\_{i \in S} x\_i. $$ This basis is sometimes useful, but its properties differ from the Fourier basis significantly. The main source of difference is the lack of orthogonality: whereas the Fourier basis is orthogonal (with respect to the inner product $\langle f,g \rangle = 2^{-n} \sum\_{x \in \\{0,1\\}^n} f(x) g(x)$), the basis $(x\_S)\_{S \subseteq \[n\]}$ is not. Much of the usefulness of the Fourier basis stems from its orthogonality (together with its other defining property, that $\chi\_S$ depends only on the coordinates in $S$).
> 1 votes

---
Tags: boolean-algebra
---


# Question
Title: How are epipolar lines useful in computer vision?
Why do use epipolar lines and what are it's benefits in computer vision ?I am unable to find the uses of epiploar lines and how they are helpful although i am aware of epiploar geometry concepts.

I would be so helpful if someone could pin point one or two uses of epipolar lines in computer vision .

# Answer
> 0 votes
When working with multiple cameras, epipolar geometry enables you to triangulate points in space, find the position of the cameras in space and more stuff addressing multiple cameras.

I can recommend to you the book "Multiple View Geometry" by Richard Hartley and Andrew Zisserman for more detailed understanding. (Chapter 9ff)

---
Tags: computational-geometry, computer-vision, image-processing
---


# Question
Title: Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.

```

 = ∅;          //the matching is initialized to zero

for ( = {, } ∈ ) {   //for each edge in the graph

    if ( x and y vertices are free)  //check if M U e is a matching

     =  ∪ ;
}

```
1. Give an example where this algorithm does not calculate a max matching
2. Prove that the algorithm is 2-approximation(The algorithm always calculates a matching M which has size |M| \>= |M\*|/2, where M\* a max matching of the initial graph)

# Answer
For the lower bound take a path of three edges $P\_3$. If the algorithm considers the middle edge first, it gets a matching of size one, meanwhile the matching consisting of the first and last edges has size two.

For the second part, note that the algorithm provided in the question yields an (inclusionwise) maximal matching, in the sence, that you cannot add more edges to the matching in such a way that it stays a matching. So it suffices to prove that any maximal matching in a graph is at least half as big as the maximum matching in this graph.

To prove this, we use notion of vertex cover. A vertex cover is a set of vertices that is incident to all edges in the graph. Note that if a graph $G$ has a matching of size $k$, then the smallest vertex cover of the graph must have size at lest $k$, since these edges do not share endpoints and we need to choose one endpoint of each such edge in the matching. So the vertex cover number of a graph $\nu(G)$ (the smallest size of a vertex cover) is at least the matching number $\mu(G)$ of this graph (the size of a maximum matching).

On the other hand, note that for a maximal matching $M$, the set $S$ containing both endpoints of each edge in $M$ is a vertex cover, since otherwise, there must exist an edge with both endpoints not in $S$, but such an edge can be added to $M$ to get a larger matching which contradicts the assumption that $M$ is maximal. Hence $2|M| \geq |S| \geq |\nu(G)|\geq |\mu(G)|$.
> 0 votes

---
Tags: approximation, matching
---


# Question
Title: Algorithm to calculate the period where cumulative days within a rolling period exceeds a threshold
I'm struggling to think of the algorithm to transform one data set to another. The problem I'm looking at is creating a dataset of periods of time where cumulative days absent within a period (eg 30 days) is greater than a certain threshold (eg 14 days). I can easily determine what sub-periods are within master-period the The dataset I'm working from is

| Absence\_ID | Absence\_Start | Absence\_End |
| --- | --- | --- |
| 1 | 10/01/2021 | 16/01/2021 |
| 2 | 23/01/2021 | 30/01/2021 |

So in this example the rolling 30 day period would result in the cumulative sum of days exceeding 14 on the 29th of January and ending on the 11th of February

| Exception\_ID | Exception\_Start | Exception\_End |
| --- | --- | --- |
| 1 | 29/01/2021 | 11/02/2021 |

But because the sub-periods vary in duration, start and number (n \> 0) I'm struggling to get an initial insight into calculating Exception\_Start and Exception\_End.

Brute force checking each day isn't ideal due to the scale of the data.

# Answer
> 0 votes
I know this is over a year, but just wondering what you came up with? I'm thinking of using a Queue. I would initialize the queue with the known days and amounts and sum the entries. Then with each new day, I would add it to the queue and add the amount for that day to the sum, and then remove an entry from the queue and subtract it's amount from the sum. That way you're only adding/subtracting a couple numbers rather than trying to sum the whole thing each time.

You wouldn't necessarily need to initialize the queue with all the days that have 0 amounts. Just do a peek() on the queue and only remove it if it is outside of 30 days.

---
Tags: algorithms, databases
---


# Question
Title: Is finding the union of all minimum hitting sets NP-hard?
Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \\{S\_1, S\_2, S\_3\\} = \\{\\{1, 2, 5, 9\\}, \\{1,2,7\\}, \\{42, 13, 23, 1, 2\\}\\}$ for example, we wish to find some minimum cardinality set $H$ composed of elements from the union of all elements of $U$ of such that $H \cap S \neq \emptyset, \forall S \in U$. In the above example, it's easy to see that $H = \\{1\\}$ or $H = \\{2\\}$.

Now, suppose that instead of returning a minimum hitting set, we wish to return a **union** of all minimum hitting sets. In the above example, that would be $\\{1,2\\}$. Note that this is itself a hitting set, but it is no longer a *minimum* hitting set. Given that finding a minimum hitting set is NP-hard, is finding the union of all minimum hitting sets also NP-hard?

I personally think the answer is yes because in the case where we know there is exactly one minimum hitting set, finding the union of all such sets is equivalent to finding the minimum hitting set (and thus NP-hard). Thus, I think the union problem is at least NP-hard, since a special case of it can clearly be reduced to a known NP-hard problem. However, I'm not sure that this reasoning is sound and so wanted some confirmation.

Any input is much appreciated!

# Answer
Your logic isn't sound, because it could be that the minimum hitting set (MHS) problem where there is a unique hitting set is much easier. In general you can't assume a problem is hard because it solves a specific subset of a known hard problem, only if it could solve *all* instances of a known hard problem.

But the answer to your question is still yes, by a proper *reduction* valid for all instances.

Suppose we could solve the union MHS variant efficiently, we can choose an arbitrary element $x$ of its solution and augment $U \leftarrow U \cup \\{\\{x, u\_1\\}, \\{x, u\_2\\}\\}$ where $u\_1, u\_2$ are arbitrary unique values previously not found in $U$. Our augmentation guarantees that *all* MHS of the augmented $U$ will contain $x$, as the alternative, $\\{u\_1, u\_2\\}$, would be less efficient. Also note that $x$ was part of *at least one* MHS before this augmentation, so any MHS of the augmented collection is also a MHS of the original. Thus by augmenting $U$ we have constrained our problem to just those MHS containing $x$.

We repeat this procedure with different choices of $x$, only modestly increasing the size of $U$, until all our choices of $x$ equals the union MHS. When this happens we have found a MHS of the original collection of sets.

So union MHS is also NP-hard because MHS is, and any efficient algorithm for union MHS would prove MHS easy.
> 1 votes

---
Tags: np-hard, check-my-answer
---


# Question
Title: Is there an algorithm for mapping two ambiguous and unrelated data sets?
I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets.

So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac sign, height, and weight. How would someone go about creating an algorithm based on that?

Another example is something based on a book you like I will match to you something you should eat for dinner.

How would someone go about this? Would it just be completely biased or is there an algorithm that's based on this? The closest thing I can think of is some kind of recommendation algorithm but I'm not sure.

# Answer
For discrete, non numerical data, you can use a relation (in the sense of relational database).

For numerical data, you can use multivariate interpolators, such as neural nets with overfitting.

What you feed to the input of such devices will return as output what was trained on.

---

Needless to say, if your hope is that you will get interesting outputs from new, unknown inputs, you will be very disappointed.
> 1 votes

---
Tags: algorithms, randomized-algorithms, software-engineering
---


# Question
Title: Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for him but also for myself since it's important to me too.

***Question:*** Prove or Disprove: if $L$ is a decidable language, so is $\text{Prefix}(L)$.

***My Answer:*** I think that the claim is wrong. I used the language:

$$L=\\{\langle M,x,t\rangle\ |\ M\text{ halts on }x\text{ within }t\text{ steps}\\}$$

It's clear that $L$ is decidable. I assume by contradiction that $\text{Prefix}(L)$ is decidable also.

**Claim:** $\text{Prefix}(L)$ is decideable $\iff \text{HALT}$ is decidable.

$(\Longrightarrow)$: Let $\langle M,x,t\rangle\in L$ so $M$ halts on $x$ within $t$ steps therefore $\langle M,x\rangle\in \text{HALT}$.

$(\Longleftarrow)$: Let $\langle M,x\rangle\in \text{HALT}$ so $M$ halts on $x$ within finite number of steps, let's call this number $t$, therefore $\langle M,x,t\rangle\in \text{Prefix}(L)$.

**Conclusion:** if $\text{Prefix}(L)$ is decidable then the $\text{HALT}$ problem is decidable too, which is known to be wrong. QED.

# Answer
It is correct that if $L$ is decidable language $\text{Prefix}(L)$ can be undecidable. The language $L$ given in the question is a concise example of a decidable language the prefix language of which is undecidable.

---

However, your proof is somewhat specious.

Firstly, in order to show $\text{Prefix}(L)$ is undecidable, all you need to show is $$\text{Prefix}(L) \text{ is decideable}\Longrightarrow\text{HALT} \text{ is decidable}.$$ There is no need to show the other direction, "$\Longleftarrow$". This is a minor issue, since it does not matter much when you have done unnecessary work.

Secondly, the way you prove "$\Longrightarrow$" does not make much sense to me. What you want to show that if we can decide (the membership problem of) $L$, then we can also decide (the membership problem of) $\text{HALT}$. The following is a correct proof of "$\Longrightarrow$".

Suppose we are given a Turing machine $T$ and a word $w$.

* If $\langle T, w\rangle\in \text{Prefix}(L)$, then there is a $t$ such that $\langle T, w, t\rangle\in L$, which means $T$ halts on word $w$.
* Otherwise, $\langle T, w\rangle\not\in \text{Prefix}(L)$, then there is no $t$ such that $\langle T, w, t\rangle\in L$, which means $T$ does not halt on word $w$.

Hence, if we can decide whether $\langle T, w\rangle\in \text{Prefix}(L)$, we can decide whether $\langle T, w\rangle\in \text{HALT}$.

---

Exercise: Given an oracle that can decide $\text{HALT}$, $\text{Prefix}(L)$ is still not decidable. Here $L$ is specified in the question.

The exercise above means that the proof for the direction "$\Longleftarrow$" in the question is specious.
> 3 votes

---
Tags: turing-machines, undecidability, halting-problem, check-my-answer
---


title: An interesting plane sweep algorithm?

text:
# Question
Title: An interesting plane sweep algorithm?
I'd like to devise an algorithm which, given n non-intersecting line segments in the plane and a point p that does not lie on any of these segments, determines the region of the plane that is “visible” to p (see the image I've provided below). Ideally, this algorithm should run in O(n log n) time.

# Answer
> -1 votes
This is a rather easy geometry problem.

First of all, here's a similar competitive programming problem I solved:

https://www.beecrowd.com.br/judge/en/problems/view/1497

This problem called "Hide and Seek" gives you several points where the first 10 are "seekers". Also, several walls are given, represented as segments. For each of the 10 seekers, count how many other points can be seen. Both walls and points are up to $10^4$ (including seekers and non-seekers). In this problem, walls are also non-intersecting and no three points are collinear (among points or wall endpoints).

The algorithm involved is polar sort plus radial sweep, and runs in $O(N \log N)$ for each seeker, so the algorithm must be run 10 times.

My solution in C++ is here (https://github.com/ChrisVilches/Algorithms/blob/main/urionlinejudge/1497-hide\_and\_seek\_2.cpp) and I will explain the most important things.

First, create the events:

```
// For every wall, create two events, one for each endpoint.
// Store the point centered on the seeker, and the wall index.
for (int j = 0; j < W; j++) {
  events.push_back({walls[j].p - seeker, j});
  events.push_back({walls[j].q - seeker, j});
}

// Polar sort the events. Refer to the Point comparator
// in order to see how the polar sort is done.
sort(events.begin(), events.end());

```

When performing the radial sweep, you need to have a mechanism to know which wall is the closest one. In the problem I linked to, it's also necessary, and I implemented it like this:

```
struct Segment {
  Point p, q;
  // ...

  pair<Point, Point> sorted_endpoints() const {
    return p.cross(q) > 0 ? make_pair(p, q) : make_pair(q, p);
  }

  bool operator<(const Segment& s) const {
    const auto [p1, q1] = sorted_endpoints();
    const auto [p2, q2] = s.sorted_endpoints();

    if (p1.cross(p2) > 0) {
      return p1.to(q1).cross(p1.to(p2)) < 0;
    } else {
      return p2.to(q2).cross(p2.to(p1)) > 0;
    }
  }
};

```

Note the comparator (`operator<`). This comparator will be used to store the segments in a `std::set<Segment>` while doing the sweep. This comparator is a special type of comparator which has the property that's specifically designed to work during a radial sweep, and cannot be used elsewhere (i.e. the order will get messed up).

So in order to make this comparator work, you insert into the set the segment when it enters the sweep, and remove it when it leaves.

Then for this particular problem, you can do something like this (I haven't implemented it, so you might need to tweak):

1. The expected solution will be an array of points that form a (concave) polygon.
2. Point $A$ enters the radial sweep. Is it the segment that's closest to $p$? If no, then do nothing.
3. (Similar to previous step) If yes, then find the intersection of the ray starting from $p$ and stretching towards the point $A$ (current sweep event) with the previous closest segment. Find the intersection point, and add this point to the polygon. Also add point $A$ next.
4. Similar cases are handled in a similar fashion.
5. Runs in $O(N \log N)$ since at every step we insert/query the set in $O(\log N)$ and/or do some $O(1)$ operations.
6. If at any point the set becomes empty, this means the region is infinite, and the area is infinite as well (visibility is not obstructed).

One observation is that if one segment is completely covered by another one closer to $p$, then nothing will happen with this segment (no points will be added). Points are only added when the closest segment becomes another segment at some enter/leave event.

One problem of this algorithm is that I haven't thought about where to start the radial sweep, and what work needs to be previously done. In Hide and Seek (problem linked above), I had to first "activate" the segments that cross the angle $0°$ so that when the sweep starts, they are already activated even if no endpoints have been sweeped through yet.

Also, is this problem part of a competitive programming problem? If so, can you share the link? I only found a paper containing this statement though. It'd be fun to implement it .

---
Tags: algorithms, computational-geometry
---


# Question
Title: How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from *Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis*:

> Imagine that the following big-O expressions correspond to the worst-case running times of different algorithms, where $n$ denotes the input size and $p$, $q$ and $r$ are potential parameters (for which we assume that $p, q, r \leq n$). Which of these can be made to conform to the requirements of fixed-parameter tractability? Either give the smallest possible set of parameters for which this is the case (and show that it is indeed the smallest), or argue why $p$, $q$ and $r$ are not suitable parameters for this.

Specifically, I'm trying to find the smallest set of parameters for the following big-O expression:

$O(p^r\sqrt{q}n^2)$

I have looked at an older thread by The G - Determine smallest possible parameter set for FPT where the same question is asked for $O(p^q\*n^2)$. From the answer to that thread I can derive that the smallest possible set of parameters which conform to the requirements is $\\{p,q\\}$. However I feel like this conflicts with the definition of FPT by Wikipedia where it says

> The crucial part of the definition is to exclude functions of the form $f(n,k)$ such as $n^k$.

from which I would assume that it is not possible for a problem in FPT to have two parameters of which the one is a polynomial of the other.

Personally I'm stuck with figuring out how FPT works with multiple parameters. Am I right in thinking that the smallest set which satisfies the requirements of FPT of my problem is $\\{q\\}$ (since it is consistent with the definition $FPT = O(f(k)\*|x|^{O(1)})$)?

# Answer
Here is a simple method to find the parameters with respect to which (the problem whose worst runtime is bounded by) a big $O$-expression becomes fixed-parameters tractable (FPT), i.e., bounded by a product of some polynomial of the input size $n$ and a function that depends only on those parameters.

For example, $p^r\sqrt{q}n^2$, where $n$ is the input size.

Is it tractable if the fixed parameters are $\\{p\\}$?
Replace all other parameters with $n$. You get $p^n\sqrt{n}n^2$, where the term $p^n$ can be not expressed as a product of a function of $p$ and a function of $n$. In fact, $p^n$ cannot be bounded by such a product.

Is it tractable if the fixed parameters are $\\{r\\}$?
Replace all other parameters with $n$. You get $n^r\sqrt{n}n^2$, where the term $n^r$ can be not be expressed as a product of a function of $r$ and a function of $n$. In fact, $n^r$ cannot be bounded by such a product.

Is it tractable if the fixed parameters are $\\{p, r\\}$?
Replace all other parameters with $n$. You get $p^r\sqrt{n}n^2$, which can be seen as the product of $p^r$ and $\sqrt nn^2$. The former, $p^r$ is a function that depends on the selected parameters only. The latter, $\sqrt nn^2$ is a function of $n$ that grows slower than $n^3$ (or, in fact, a "polynomial" function by itself). So $\\{p,r\\}$ is a valid choice.

Is it tractable if the fixed parameters are $\\{q\\}$?
Replace all other parameters with $n$. You get $n^n\sqrt{r}n^2$, where the term $n^n$ is independent of $q$ and not bounded by a polynomial of $n$. Hence, $\\{q\\}$ is not a valid choice.
> 3 votes

---
Tags: complexity-theory, runtime-analysis, big-o-notation, parameterized-complexity
---


# Question
Title: Switching between doing something and not doing it within $k$ steps in LTL
Imagine that we are designing a system in which we have the action to brake or not brake. How can we write an LTL specification that guarantees that we cannot switch between braking and not braking within three time steps?

# Answer
> 1 votes
You can simply require that whenever there is a switch (i.e., the braking status changed from one to another), the status will not change for the next three steps. Technically, let $b$ denote the propositions that brake is on, then we have the following: $$G((\neg b\wedge Xb)\to (XXb\wedge XXXb) )\wedge G((b\wedge X\neg b)\to (XX\neg b\wedge XXX\neg b) )$$ Note that you can put the two conditions inside one $G$ operator. I just find this way easier to read.

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


# Question
Title: I think I have discovered a new sorting algorithm using binary search tree
If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and vice versa, such a configuration of BST is inherently sorted with its root being approximately in the middle (in case of nearly complete BST’s). To to this we need to do reverse rotations. Unlike AVL and red black trees, where roatations are done to make the tree balanced, we would do reversed rotations.

I would like to explain the pseudo code and logical implementation of the algorithm through the following images. The algorithm is to first sort the left subtree with respect to the root and then the right subtree. These two subparts will be opposite to each other, that is, left would interchange with right. For simplicity I have taken a BST with right subtree, with respect to root, sorted.

# Answer
Nice work, but not useful because

* trees are not really sorted (in the sense of a sorted array) as the nodes may be stored non-contiguously in memory, and you need to follow the links;
* any BST *is* sorted because traversing the nodes in infix order gives a sorted list, there is no need to reorganize.
> 2 votes

---
Tags: sorting, trees, binary-search-trees
---


# Question
Title: Can Boolean circuits of polylog depth represent all Boolean functions?
Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to the output. I wonder if Boolean circuits with a depth Polylog in the number of inputs are sufficient to express any Boolean function. I only know that a depth of $O(n)$ is sufficient ($n$ is the number of inputs), by using the disjunctive normal form to construct a Boolean circuit.

Note that this question is different from the $NC$ complexity, since in $NC^i$ the size of the Boolean circuit is also constrained to be polynomial, while this question does not constrain the size. Thank you!

# Answer
A $k$-ary circuit of depth $d$ has size at most $k^d$, hence polylog-depth circuits of fan-in $2$ have quasipolynomial size. Thus, the vast majority of Boolean functions cannot be computed by such circuits, as most functions require exponential circuit size $\Omega(2^n/n)$.
> 3 votes

---
Tags: circuits, boolean-complexity
---


# Question
Title: Finding a Hamiltonian Cycle in a directed graph - graph problem
$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like to plan his journey in such a way that starting from any town, he visits all towns exactly once and returns to the starting town.

The connection network of towns is given as a list of tuples $G$ (towns are numbered from $0$). The *i*-th tuple contains two lists: the first list contains the numbers of towns that can be reached from the *i*-th town via the *i*-th town's northern gate, the second one - similarly, only with the southern gate. It is guaranteed that we will be able to get to at least one city from each gate.

When you travel to a city, you have to go through this gate, from which we can get to the city you came from.

For example for $G=\[(\[1\],\[2\]),(\[2\],\[0\]),(\[0\],\[1\])\]$ if we want to get from city $0$ to city $1$, we have to go through the north gate in city $0$ (because $1$ is in the first list in the tuple) and we have to go through the south gate in city $1$ (because the number of the city we came from - $0$, is in the second list in the tuple)

I need to find an algorithm that, given a list $G$, returns a list of the numbers of the cities visited consecutively by the merchant (or ***None*** if no such route is possible).

Example:

```
G = [ ([1], [2, 3, 4]),
 ([0], [2, 5, 6]),
 ([1, 5, 6], [0, 3, 4]),
 ([0, 2, 4], [5, 7, 8]),
 ([0, 2, 3], [6, 7, 9]),
 ([1, 2, 6], [3, 7, 8]),
 ([1, 2, 5], [4, 7, 9]),
 ([4, 6, 9], [3, 5, 8]),
 ([3, 5, 7], [9]),
 ([4, 6, 7], [8]) ]

the result is the list [ 0, 1, 5, 7, 9, 8, 3, 2, 6, 4 ]

```

The first thing that popped into my head, because it is quite obvious, is that this is a Hamiltonian cycle problem (because we have to visit each vertex of the graph exactly once and return to the starting vertex). However, the condition related to gates indicates that we are dealing with a directed graph (at least that's what I think), which complicates things.

Would anyone have an idea how to solve this problem in a reasonable time (I know the Hamiltonian cycle problem is NP-complete, but suppose the number of vertices is not large)?

# Answer
> 1 votes
You can introduce a network $G\_{new}$ such as follows:

For each vertex i (or town) in G introduce two vertices $i'$ (for north gate) and $i''$ (for south gate) which are connected to each other; i.e. There exist both arcs $i'i''$ and $i''i'$. Moreover, if we can move between $i$ and $j$ from northern gate of vertex $i$ then add $i'j'$ and $i'j''$ arcs and if we can move between $i$ and $j$ from southern gate of vertex $i$ then add $i''j'$ and $i''j''$ arcs.

Now, it is sufficient to introduce a Hamiltonian cycle on $G\_{new}$, where for all vertices $i'$ and $i''$, we should traverse exactly one of the arcs $i'i''$ or $i''i'$; e.g. add the constraint $X\_{i'i''}+X\_{i''i'}=1$ to an optimization model of the Hamiltonian cycle problem.

---
Tags: algorithms, graphs, python, hamiltonian-path, hamiltonian-circuit
---


title: Length of a regular expression

text:
# Question
Title: Length of a regular expression
What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count? For example: let r = $(ab)^\*\cup$ $a$. What is $|r|$?

# Answer
> 7 votes
I assume, you want to define the length of a regular expression such that you can make statements like: *The Thompson construction creates an NFA from a regular expression with a number of states that is linear in the length of the expression.*

In that case, it is crucial to include operator symbols, otherwise the above statement would not be true for the expression $a^{\ast\ast\ast\ast\ast\cdots\ast}$.

However, if you preprocess expressions such that there are no nested Kleene stars or trailing $\varepsilon$s, then it does not matter much, as then the different definitions only differ by a constant factor. A short write up on this which I think is quite good, you can find in this paper

¹ Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei Wang. *Regular Expressions: New Results and Open Problems.* Journal of Automata, Languages and Combinatorics, 10(4) 2005

# Answer
> 7 votes
There are two conventions I know of.

One is defining the size of a regular expression as the size of the binary tree representing the expression. As such, the size of the expression is the total number of symbols in the expression, counting $\emptyset$, $a\in \Sigma$, $\*$, $|$ and $\cdot$ (parentheses are not counted).

An other definition removes the $\cdot$ (concatenation product) from being counted. This is somewhat usefull in the Thompson's construction: the constructed NFA for $e$ has at most $2|e|$ states (this is due to the fact that the concatenation symbol does not increase the size of the automaton).

---
Tags: regular-expressions
---


# Question
Title: Allocating m rooms of varying capacity to n booking requests of varying sizes
I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize number of rooms used and minimize room capacity wasted. The only reason why we want to minimize number of rooms used is to prevent booking requests being split into too many rooms. For example, Allocating (d,e) is better than allocating (a,b,c,d). The primary goal is to minimize wasted capacity.

I hope the following example will help you to understand the above narrative. Let say we have 6 rooms with the following capacities:

| a | b | c | d | e | f |
| --- | --- | --- | --- | --- | --- |
| 1 | 2 | 3 | 4 | 6 | 14 |

> avg. room capacity = 5

Let say we have two booking requests with following group sizes (# of people): 7, 10

| r1 | r2 |
| --- | --- |
| 7 | 10 |

***Assuming*** processing booking requests in the descending order of their size may lead to optimal solution, we start with r2 (size 10).

**Option 1:**

We can see that we could use rooms (a,b,c,d) or (d,e) or just (f). With (a,b,c,d) option we use 4 rooms with 0 wasted capacity. With (d,e) option we use 2 rooms with 0 wasted capacity. Hence (d,e) is better than (a,b,c,d). If we go with (d,e), the only option for r2 is room f, in which case we would have used 3 rooms with wasted room capacity of 7.

**Option 2:**

Now if we go with just room f, we use 1 room with 4 (14-10) wasted capacity. However, r2 can be fulfilled with either (c,d) or (a,e) with 0 wasted capacity. Total 3 rooms used and wasted room capacity is 4.

Option 2 is better.

**Tie breaker** (not claiming it is correct or logical) Let say we arrive at multiple solutions. For example, if we have to decide between 2 room 7 wasted capacity and 3 rooms 4 wasted capacity, then we can take avg room capacity (in this case 5) as 1 room equivalent. 3 rooms 4 wasted capacity can be considered equivalent to 2 rooms 9 (4 + 5) wasted capacity. So 2 room 7 wasted capacity is better. We can also tweak this room equivalent parameter (c). Default it to avg. room capacity. If we want to go ahead with minimum wasted capacity only, we can set c to 0. With c = 0, 3 rooms 4 wasted capacity option would be better.

This narrative and examples show the problem at hand and also the attempts I have made to solve them.

**Objective Function** The "goodness" of the allocation may be measured by the following expression: (r\*c)+u, where r is total number of rooms used, c is a constant (c\>=0) and u = unutilized or wasted capacity. **The less the better.** The optimum allocation can be determined by the least value of the goodness factor. The constant c may be 0 if we only want to optimize for capacity regardless of number of rooms used.

**Update** I initially wrote that "Assume bookings cannot share rooms." But we need to solve this for shared rooms scenarios as well. We can use unoccupied capacity for allocation. For example, room f (14 capacity) will have unused capacity of 4 after allocating r2. This should be considered while allocating r1. Updated table will look like this:

| a | b | c | d | e | f (updated) |
| --- | --- | --- | --- | --- | --- |
| 1 | 2 | 3 | 4 | 6 | 4 |

I need your help to answer the following:

1. Is there any well known algorithm to solve this problem. Knapsack and Bin packing come close but don't fit the problem completely.
2. If not, how to efficiently allocate rooms? Please provide algorithm with time complexity analysis.

# Answer
> 3 votes
One plausible approach is to use integer linear programming. Introduce 0-or-1 variables $x\_{q,r}$, where $x\_{q,r}=1$ means that room $r$ is assigned to request $q$. Then you can write down linear inequalities that characterize the properties of a valid solution: e.g., $\sum\_r \text{capacity}(r) x\_{q,r} \ge \text{size}(q)$ for all $q$, $\sum\_q x\_{q,r} \le 1$ for all $r$, etc. Then you are trying to minimize $$\sum\_{q,r} x\_{q,r} + \sum\_q (\sum\_r \text{capacity}(r) x\_{q,r} - \text{size}(q)).$$ This can be solved with an off-the-shelf ILP solver.

---
Tags: optimization, dynamic-programming, optimal-strategy
---


# Question
Title: How to convert AFA to ε-NFA / NFA / DFA?
Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and that from Q∀ are 'and'ed.

Is there an algorithm for converting AFA to ε-NFA, NFA or DFA? I tried searching in Google, but all I get is conversions between ε-NFA, NFA and DFA. I didn't get any more resources about AFA.

# Answer
The construction yields a nondeterministic NFA $A'$ that is equivalent to the original alternating AFA $A$.

The states of the new automaton are sets of states of $A$, just as in the classic construction of a deterministic DFA from an NFA. In the new DFA we collect *all* reachable states and accept if one of the states in this set is accepting in the original NFA.

Here the situation is dual: we accept in a state $X$ if *all* states are accepting in the original AFA: $X\subseteq F$, or in other words $X\in 2^F\setminus \\{\varnothing\\}$. From a set $X$ we move (nondeterministically) to a new set $X'$. For each $q\in X$ we do the following.

1. If $q\in Q\_\forall$ is universal, then all successor states $\delta(q,a)$ must lead to acceptance, so *all of them* are part of the new state $\delta(q,a) \subseteq X'$.
2. If $q\in Q\_\exists$ is existential, then *at least one* of the successor states $\delta(q,a)$ must be accepting, so at least one of those states must be in the new state: $\delta(q,a) \cap X' \neq \varnothing$.

This construction keeps track of the computation tree, but when states occur more than one time in that tree they are collapsed into one. See this figure from the paper you linked (K. Narayan Kumar, Chennai Mathematical Institute, Notes on Automata, Logic, Games and Algebra, Lecture 6: Alternating Automata):
> 3 votes

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


# Question
Title: Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?
The problem concerns finding shortest paths in graph from a single source to a single destination.

So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A\* runs in expected time O(E), because It uses additional information to find the path faster.

Now let's simplify the problem and remove the weights. In an undirected and unweighted graph BFS runs in O(E+V), but can potentially be stopped earlier if a better solution is found.
Now consider some good heuristic is also available for the distance from any vertex to the destination - even though all edges have the same length (for example we are looking for a path on a grid composed of unit-length edges with obstacles on some edges).

The fact that such heuristic exists is (of course) some added information, and this added information should theoretically be usable to improve the running speed of the algorithm, but I was not able to find any methods that utilise this additional information to optimise how fast BFS runs. I believe the lower bound is still O(E), for example for a simple path, but the constant multiplier should probably be smaller.

I have searched Wikipedia for different methods and I came across Beam search and Best first search - but both utilise a queue, so in theory it bumps the computational complexity to that of Dijkstra.

To sum up - can some heuristic information be used to improve the runtime of BFS?

# Answer
A$^\*$ can be an improvement of BFS in some cases, for example when searching a path in a maze.

Coincidently, I am currently working on such graph traversal with my students. Here are some of the results. The first image is done with BFS (yellow are unsuccessfully explored parts of the maze, in green is the solving path), the second with A$^\*$.

This answer may not be what you are looking for, because A$^\*$ uses a priority queue, so the time complexity may be worse than BFS.
> 5 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Efficient search of a large set of documents to find documents that only contain a particular set of words
Say I have a set of documents $D = \\{d\_1, d\_2, \dots, d\_n\\}$ in some natural language.

Each document $d\_i$ consists of a subset of words from a word pool $W = \\{w\_1, w\_2, \dots, w\_k\\}$. For example, $\text{words}(d\_1) = \\{w\_1, w\_5, w\_{7}\\}$. $\text{words}(d\_1)$ is an ordered multiset, but that isn't too important to this problem - we can treat it as a typical set.

Say I have some $K \subset W$.

And there is also $S \subset K$.

I want to efficiently find $E \subset D$ such that:

1. $\forall e\in E\space \exists\space s: s \in S \land s\in e $ (the documents in E all contain at least one word from $S$).
2. $\forall e\in E\space (w \in e \implies w \in K )$ (all documents in E only contain words that are in $K$).

My first extremely naive solution to this was simply putting this data into a normalized relational database, and finding the set of documents for a given $K$ and $S$ using a join. This very quickly becomes too slow on a dataset of say, 2 million documents (even with useful indexes added, powerful machine etc). In that database I had a pretty unexciting schema:

| Document | Sentence | Word |
| --- | --- | --- |
| id: int | id: int | id:int |
| text:string | text: string | text: string |
|  | document\_id: int | sentence\_id: int |
|  |  | index\_in\_sentence: int |

Two avenues I am considering exploring are building a word trie and building an inverted index. I studied undergrad computer science a few years ago but now no longer work in tech, so I don't have any academic or industry people to ask (none of the industry people I discussed this problem with had a good suggestion.)

The problem is different to typical search engine search, which generally doesn't care about the set $K$, instead just looking for matches based on the smaller set $S$.

But I was hoping that anyone reading this can tell me 'the problem you are working on has been solved, just go check out algorithm X or data structure Y', that would be amazing.

Some further context: for my problem, both $D$ and $W$ are fixed ($D$ is several million documents, $W$ is in the order of high 10s or low hundreds of thousands, ie a natural language). $S$ might be from 10-100 in size typically, and $K$ might be from 50-5000 typically.

But I want to build a data structure (whether in postgres, neo4j, reddis, or even just in some application language like C or Python) that I can query with a variety of $K$ and $S$ values, and quickly find the subset of $D$ that satisfies the above constraints.

I am not looking for programming language or database choice level solutions here, just any pointers on how to efficiently do this kind of search. Of course, if it happens that some programming or database paradigm is a great fit, please let me know.

Note: I have found a rather similar question with some suggested solutions here.

I am going to investigate these options, but in the mean time I welcome any pointers!

# Answer
> 2 votes
You are trying to compute the set

$$E = \\{e \in D \mid e \subseteq K \land e \cap S \ne \emptyset\\}.$$

There is a naive algorithm. Store $K,S$ in a hashtable (using a hash function that maps each word to its hash value). Then for each $e \in D$, iterate through the words of $e$, look them up in the hashtable for $K$ and $S$, and check whether it satisfies the conditions; if it does, include it in $E$. If you prefer a database-style approach, you can probably express this using joins (e.g., a join between $e$ and $S$, a join between $e$ and $K$), and use any join algorithm you like: a hash join, a sort-merge join, etc.

I imagine you're hoping for a faster algorithm, whose running time is sub-linear in $|D|$. I don't hold out a lot of hope for such an algorithm. You're basically looking for the ability to perform subset queries, which I think might be hard. See, in particular, state of the art of subset, set containment and partial match queries, Data structure for testing all subsets of a query for membership, Best data structure for queries about subsets?, Finding containing sets in a set of sets. I suspect you may find that none of them are that much better than the naive algorithm.

---
Tags: dynamic-programming, search-algorithms, natural-language-processing, search-problem, information-retrieval
---


title: Inorder Traversal of the Ternary Tree

text:
# Question
Title: Inorder Traversal of the Ternary Tree
As per Wikipedia, Algorithm for In-order Traversal of Binary Tree

> 1. If the current node is empty/NULL/None return nothing.
> 2. Traverse the left subtree by recursively calling the in-order function.
> 3. Display the data part of the root (or current node).
> 4. Traverse the right subtree by recursively calling the in-order function.

I was interested in Algorithm for In-order Traversal of Ternary Tree. Upon referring Professor Robert Sedgewick's Lecture of Ternary Search Tries, I found that if I do the In-order traversal on the Ternary Search Tree (a type of Trie data structure) for a particular searched string then visiting order of nodes should be

> 1. Check if the current node is empty or null.
> 2. Traverse the left subtree recursively calling in-order function.
> 3. Display the data part of the current node.
> 4. Traverse the middle subtree by recursively calling the in-order function.
> 5. Traverse the right subtree by recursively calling the in-order function.

But I got result different from claimed in one Assignment Problem, and in one Competitive Exam Problem.

**Problem 1 :** Find the In-order Traversal of the following tree

* Mine Answer : `AKBJCLIEDHFG`
* Given Answer : `AKBJCLIDEHFG`

**Problem 2 :** Consider the rooted tree with the vertex labelled `P` as Root. Find the order in which nodes are visited during an in-order traversal of the tree.

* Mine Answer : `QSPTRUWV`
* Given Answer : `SQPTRWUV`

Please verify whether my answers are correct or not and If I am wrong somewhere then please correct me.

# Answer
> 1 votes
> According to me answer should be :- AKBJCLIEDHFG

Your answer is ((A) (K) ((B) (J) (C))) (L) (I) (((E) (D)) (H) (F) (G))

Please take a close look at the part ((E) (D)). Here lies the ambiguity/confusion/uncertainty. The ambiguity is whether D is the left subtree or the middle subtree or the right subtree of E.

Because of the limited drawing spaces that shows the tree, it can be argued in a few ways. I could swear that D is meant to be the left subtree or E. On a different day, I might, agreeing with you, insist that D is so apparently the middle subtree of E. On another day, I could stretch myself a little bit, unabashedly claiming that D is in fact the right subtree of E. Unless there are some kind of instructions such as your textbook or whatever material you have been using has defined the rules how to tell the class of subtree from the way is drawn in case of ambiguity, it is impossible to conclude which subtree of E D is.

So your question is reduced to whether there are those kind of rules in your material. Or in your instructor's notes or oral guide. Or, what is general convention in your culture or your context to interpret "left", "middle" and "right". This question is not so much of computer science, but more about linguistics and drawings and culture.

If I had to pick one solution out of no context, I would be very frustrated on deciding whether D is a left subtree or right subtree of E. I would choose one of many possible actions below, without any particular preference.

* try finding the context or the rules.
* just choose left subtree.
* just choose middle subtree.
* wave my hands, declaring no value to solve a question that is not well-formed.
* presenting two solutions or three solutions, each with its assumption stated clearly.
* redraw the graph in the question.
* raise a question about that question to seek other's judgements as you just did
* had I been a student, my TA should have been my savior and my professor should have been the ultimate arbitrator.
* the last option that stands for all the remaining possibilities.

(By the way, I just searched the lecture briefly. I have not found any definitive guide on how to tell left or middle or right subtree. Of course, I might have missed some hints or conspicuous rules.)

# Answer
> 0 votes
A *tree* is a finite set of one or more nodes such that there is one specially designated node called the root node of the tree, and the remaining nodes are partitioned into trees $T\_1,\ldots,T\_k$ (called the subtrees of the root), where $k\ge0$.

Given a tree with a root node $n$ and subtrees $T\_1, T\_2, \ldots, T\_k$, the inorder listing of the nodes of the tree is the list of nodes of $T\_1$ in inorder, followed by $n$, followed by the list of nodes of $T\_2, \ldots, T\_k$, with the nodes in each group listed in inorder. Note that trees are also called ordered trees because the order in which the subtrees are mentioned does matter.

Thus, if you have a tree with a root node $E$ and a single child $D$, then the inorder listing would be $D,E$ because the first subtree $T\_1$, which consists of the single node $D$, would be listed before the root node $E$.

We need to be clear on the definition of a tree (aka ordered tree) and the definition of a binary tree (which is not a special case of a tree; in fact, trees must be nonempty whereas a binary tree can be empty). Also, the inorder definition for a binary tree is different from the inorder definition of a tree. When you are given a binary tree, it must be specified whether a unique child is a left child or a right child, whereas in a tree a unique child would be (the root of) the first subtree.

A good reference for the definition of trees is \[Knuth, "The art of computer programming, volume 1"\] and for the definition of inorder traversal of (ordered) trees is \[Aho, Hopcroft and Ullman, "Data structures and algorithms", Section 3.1\].

---
Tags: algorithms, data-structures, trees, tree-traversal
---