# Question
Title: Are the functions always asymptotically comparable?
When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the two algorithms.

Is this always the case? That is, does at least one of the relationships $f(n) = O(g(n))$ and $g(n) = O(f(n))$ always hold, that is for general functions $f$,$g$? If not, which assumptions do we have to make, and (why) is it ok when we talk about algorithm running times?

# Answer
Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and $$ g(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\\ n^2 & \text{if $n$ is even}. \end{cases} $$ Moreover, functions like $g(n)$ do actually arise as running times of algorithms. Consider the obvious brute-force algorithm to determine whether a given integer $n$ is prime:

```
IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

```

This algorithm requires $\Theta(1)$ arithmetic operations when $n$ is even, $O(\sqrt{n})$ operations when $n$ is composite, but $\Theta(n)$ operations when $n$ is prime. Thus, formally, this algorithm is *incomparable* with an algorithm that uses $\sqrt{n}$ arithmetic operations for *every* $n$.

Most of the time when we analyze algorithms, we only want an asymptotic upper bound of the form $O(f(n))$ for some relatively simple function $f$. For example, most textbooks would simply (and correctly) report that `IsPrime(n)` runs in $O(n)$ arithmetic operations. Typical upper bound functions are products of exponentials, polynomials, and logarithms (although more exotic beasts like factorials and iterated logarithms also show up occasionally). It is not hard to prove that any two such functions are comparable.

See also this MathOverflow question.
> 23 votes

# Answer
From wikipedia, definition of big O notation:

> if and only if there is a positive constant M such that for all sufficiently large values of $x$, $f(x)$ is at most M multiplied by $g(x)$ in absolute value. That is, $f(x) \in O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x\_0$ such that

$|f(x)|\<= M |g(x)| \quad \text{for all} \\; x \> x\_0$

**What happens for functions that do not converge (to a constant nor infinity)?**

Look at the functions $f(x) = |xsin(x)|$, and $g(x) = 10$

for each $x\_0$, there is some $x \> x0$, such that $x = k\pi$, thus $f(x) = 0$ - so for each $M$ - $Mf(x) \> g(x)$ will yield false, and $g(x) \\; \not\in O(f(x))$

However, it is easy to see that $|xsin(x)|$ is not bounded by any constant as well, thus for each $M$,$x\_0$, there is some $x \> x\_0$ such that $f(x) \< Mg(x)$ will also yield false, and $f(x) \not\in O(g(x))$

Note: for definition if big O that allows a maximum constant difference between $Mf(x)$ and $g(x)$, the same idea will apply with $g(x) = \log(x)$
> 7 votes

# Answer
Here's a pair **monotonic** functions that are not asymptotically comparable. This is relevant because most complexities arising in practice are in fact monotonic.

$$ f(x) = \Gamma( \lfloor x \rfloor + 1 ) = \lfloor x \rfloor ! $$ $$ g(x) = \Gamma( \lfloor x-1/2 \rfloor + 3/2 ) $$

Here, $ \Gamma $ is the gamma function. The second function is specially constructed to be very similar to the factorial, just "sampled" at slightly offset points in the gamma function. The functions cross each other periodically in such a way that neither is asymptotically bound by the other.
> 6 votes

# Answer
Let $\mathcal{L}$ be the class of functions obtained from the identity function and constants using the following operations: addition, subtraction, multiplication, division, logarithm and exponential. For example, $\exp(2\sqrt{\log x + \log\log x})/x^2$. Hardy proved that for every two functions $f,g \in \mathcal{L}$ which are positive and tend to infinity, one of the following is true: $f = o(g)$, $f = \omega(g)$, $f/g$ tends to a constant. See page 18 of his book "Orders of infinity".

The upshot is that any two "simple" functions occurring in the analysis of algorithm *are* comparable. Here "simple" means that there is no definition by cases (other than finitely many base cases), and no surprising functions appear, such as the inverse Ackermann function which sometimes figures in running times.
> 4 votes

# Answer
For completeness, here's a slightly easier version of Ambroz's answer. Not only is it strictly increasing, but smooth as well!

Intuitively, we want to construct a function that oscillates between fast-growing and slow-growing, with larger and larger swings. We'll start with $$f\_0(x)=x,\quad g\_0(x)=x$$

We need some oscillation, so let's tweak $f$ to be $x+\sin{x}$. That's non-decreasing, but a small tweak regains strictly increasing $$f\_1(x)=2x+\sin{x},\quad g\_1(x)=2x$$

We now have an additive gap. We can make that a multiplicative gap via exponentiation $$f\_2(x)=2^{f\_1(x)}=2^{2x+\sin{x}},\quad g\_2(x)=2^{g\_1(x)}=2^{2x}$$

Finally, we can replace the multiplicative gap with an "exponentiative" gap in the same way. $$f(x)=f\_3(x)=2^{f\_2(x)}=2^{2^{2x+\sin{x}}},\quad g(x)=g\_3(x)=2^{g\_2(x)}=2^{2^{2x}}$$

Whenever $\sin{x}=-1$, we get that $$f(x)=2^{2^{x-1}}=2^{0.5\*2^x}=(2^{2^x})^{0.5}=g(x)^{0.5}$$

Similarly, whenever $\sin{x}=+1$, we get that $$f(x)=2^{2^{x+1}}=2^{2\*2^x}=(2^{2^x})^2=g(x)^2$$
> 2 votes

---
Tags: asymptotics, mathematical-analysis
---


# Question
Title: In propositional logic how is the negation equivalent?
I am unable to understand how the negation of a sentence into CNF actually makes sense, hopefully somebody can explain it to me in understandable terms!

Given the sentence: ***If the battery is charged (A) and the screen is not cracked (B) then the phone is working (C)***

The following makes perfect sense:

`(A ∧ B) => C`

I cannot get my head around how the negated form is true or how it works:

`¬A ∨ ¬B ∨ C`

I am struggling because "not A" means if the battery is not charged? So I cannot see how if the battery is not charged ***or*** the "screen is cracked" **or** the "phone is usable".

If A is false, so battery is not charged, how is that applying ¬A to it does not make it now true?

Any help would be appreciated.

# Answer
First thing is to accept and understand, that $A \Rightarrow C$ is same as $(\neg A) \lor C$. Using your example we obtain, that "**If the battery is charged, then the phone is working**" is same with "**the battery is not charged or the phone is working**".

Now following initial sentence $(A \land B) \Rightarrow C$ we have $\neg(A \land B) \lor C$, where last sounds as "**not fulfilling (the battery is charged and the screen is not cracked) or (the phone is working)**".

Now we come to negation of $\neg(A \land B) = (\neg A) \lor (\neg B)$. So sentence "**not fulfilling (the battery is charged and the screen is not cracked)**" is same as "**(the battery is not charged) or (the screen is cracked)**"

Putting everything together we have $$(A \land B) \Rightarrow C \text{ is same with } (\neg A) \lor (\neg B) \lor C $$

in words last is "**(the battery is not charged) or (the screen is cracked) or (the phone is working)**"
> 1 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Comparing growth of two sums of functions
Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?

# Answer
Yes, asymptotically. You can see that $n + n^4 = \omega(n^3 + n^2)$ by taking the limit:

$$ \lim\_{n \to \infty} \frac{n^4 +n}{n^3 + n^2} = \lim\_{n \to \infty}\frac{n + n^{-2}}{1 + n^{-1}} = + \infty $$.

See also this answer.
> 1 votes

# Answer
1. Polynomials of higher degree grow faster than polynomials of lower degree.
2. The polynomial $n + n^4$ is of degree 4.
3. The polynomial $n^2 + n^3$ is of degree 3.
4. Therefore, the $n^4$ polynomial grows faster than the other polynomial.
> 1 votes

# Answer
Let me add way with simple inequalities: $$n^2+n^3 \leqslant n^4 +n^4=2n^4 \leqslant 2(n^4+n) $$ Now taking constant $C=2$ we have $n^2+n^3 \in O(n^4+n)= O(n^4)$.
> 0 votes

---
Tags: algorithm-analysis, big-o-notation
---


title: Completing tasks on a graph

text:
# Question
Title: Completing tasks on a graph
Consider a graph $G = (V, E)$, where $V = \\{0, 1, 2, \ldots, n\\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that we must complete. The task at vertex $v$ takes $q\_v \> 0$ minutes for $v \neq 0$, and we must complete all tasks. We start at Vertex $0$, and we have $q\_0 = 0$.

It will obviously take us exactly $\sum\_{i = 1}^{n} q\_i$ total time for us to complete all of the tasks on our own (it doesn't take any time to traverse the edges). However, suppose we have a single helper. We are allowed to dispatch the helper at any node (say $v$), and we can leave the node, go work on other tasks, and pick up the helper after $q\_v$ minutes to drop it off at another node. A caveat is that the helper cannot move on its own; it must be picked up and dropped off.

Is there some sort of algorithm that allows one to find the best strategy (i.e., one that minimizes the total time) when we are allowed one helper?

A naive strategy would be a greedy strategy that always drops off the helper at the vertex with the largest $q\_i$. It seems like this would minimize the time that the helper is idle; however, I have no reason to believe that this is optimal.

Does anyone have any suggestions or heuristics for an approximate solution?

# Answer
> 4 votes
**Hardness**

The problem is strongly $NP$-hard so there likely is no fast algorithm solving it.

Consider the 3-Partition problem wherein we are given $3n$ distinct integers $x\_1,\ldots, x\_{3n}$ and an integer $T$ such that $T/4\< x\_i\< T/2$ and asked to decide whether we can group the $3n$ integers into $n$ groups of $3$ integers with sum equal to $T$ for each triple.

We create an instance of the problem with $4n$ tasks, $3n$ of those tasks having length $x\_i$ (one for each $1\leq i\leq 3n$) and $n$ tasks having length $T$.

There exists a solution with no idle time if and only if the 3-Partition instance is solvable. Clearly, if there is a solution to the 3-Partition instance there is a solution to the task planning instance: just have the helper do the length $T$ tasks and have us handle the other tasks in groups of 3 (each with length exactly equal to $T$).

Conversely, in any solution with no idle time, the helper cannot do any task of length less than $T$. If we start the helper on some task with length less than $T$ (i.e., some length $T/4\< x\_i\< T/2$), we must find tasks to do ourselves with length exactly equal to $x\_i$. However, no task other than $i$ itself has length $x\_i$ (since all the integers $x\_i$ are distinct) and for any two integers $x\_j,x\_k$, $x\_j+x\_k \> T/2 \> x\_i$.

Thus, in any solution with no idle time, all the tasks done by the helper are of length $T$. The tasks we do ourselves during each task done by the helper must then form a solution to the 3-Partition instance.

**Heuristic/approximation**

Clearly the idle time cannot be approximated (since it is already hard to decide whether it is non-zero). There is however an EPTAS for the makespan.

Consider the algorithm that always assigns the longest job to the helper, and then fills out the schedule of the master by considering jobs in order of decreasing length and assigning each job that still fits (so that the length of master's schedule does not exceed that of the helper). Repeat this process with the remaining jobs untill all are scheduled. We call a single job done by the helper together with a set of jobs done by the master a "round".

This yields a solution with idle time of at most $L\_\textrm{max}$ where $L\_\textrm{max}$ denotes the length of the longest job. To see this, note that if during a round the master is idle for $\epsilon$ units of time, $L\_\textrm{max}$ decreases (in the set of remaining jobs) by at least $\epsilon$: if there was a job longer than $L\_\textrm{max}-\epsilon$ the master would have done that job and obtained a shorter idle time.

Suppose that the sum of all job lengths is $1$ and let $\epsilon \< 1$. If $L\_\textrm{max}\leq \epsilon$, the above procedure returns a $1+2\epsilon$-approximation (since the optimal solution has makespan $\geq 1/2$). Otherwise, consider the jobs with length $\geq \epsilon$ of which there are at most $1/{\epsilon}$ (long jobs). Consider also the jobs with $\epsilon \<$ length $\geq \epsilon^2$ of which there are at most $1/{\epsilon^2}$ (medium jobs). The remaining jobs (with length $\<\epsilon^2$) are called short.

We now, by brute force, enumerate all schedules with the following properties: all long jobs are scheduled, and possibly some medium jobs are scheduled and every round contains at least one long job. For each such schedule, we greedily fill any idle time the master may have with short jobs (so that the master does not work longer than the helper in any round). This is the first phase schdule. We then schedule the remaining short/medium jobs according to the previous greedy algorithm. This is the second phase schedule.

The idle time in the second phase is at most $\epsilon$ (since $L\_\textrm{max}\< \epsilon$). We now need to bound the additional idle time (over that in an optimal solution) in the first phase.

Take an optimal schedule. If the helper does a short job while the master does a long one, swap the jobs done by the helper and the master -- this does not change the makespan. Delete all short jobs from the schedule and all rounds containing only short/medium jobs. Assume the solution obtained by our approximation algorithm is based on this (modified) schedule, which will be part of the brute force enumeration (so our approximate solution will be at least as good as one obtained from this schedule).

If there are no short jobs in the second phase, then it is easy: We know that the medium jobs scheduled in the second phase do not need to be scheduled together with any long job in an optimal solution. In an optimal case they would be scheduled with at most zero idle time, and the greedy algorithm adds at most $2\epsilon$ extra idle time. We also have not increased the makespan of the brute-force schedule, so it must be optimal.

If there are any short jobs in the second phase, the first phase has at most $1/\epsilon$ rounds (because every round contains a long job) and no phase has more than $\epsilon^2$ idle time for the master (since otherwise we could have scheduled some of the remaining short jobs). Thus the total idle time for the master is at most $\epsilon$. In rounds were the helper has idle time, note that this round is unmodified from the original optimal schedule (since the master would not start a new job if the helper was idle). Thus, the additional idle time, over that of an optimal schedule, is at most $\epsilon$ (from rounds in which the master is idle; the rounds in which the helper is idle do not contribute any additional time).

An interesting question is what happens if the master is impatient and always starts a new job instead of having the option to wait for the helper to finish.

---
Tags: algorithms, graphs, dynamic-programming
---


# Question
Title: How does BFS guarantee the minimum path for this problem?
https://leetcode.com/problems/bus-routes/

You are given an array routes representing bus routes where `routes[i]` is a bus route that the ith bus repeats forever.

For example, if `routes[0] = [1, 5, 7]`, this means that the 0th bus travels in the sequence `1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 ->` ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return `-1` if it is not possible.

The solutions for this problem involve doing a BFS from each of the vertices(bus stops), but **how does that guarantee a the minimum path ?**

# Answer
> 1 votes
BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current one and divides itself into all of those. Basically, at every junction, it divides itself and continues down that path until it encounters the destination node.

So effectively, it can be said that it checks for all the paths of length `len` from the source node starting `len` from `0` and incrementing it by `1` until it reaches the destination.

Let's say it got to the destination with length 7, now this means that it tried all the paths of length 0, 1, 2 ... 6 but was not able to get to the destination.

So, this means that whenever BFS finds a path, it already tried all paths of length (or cost) lower than the current one but was able to find a complete path that reaches the destination. Which means it always finds the shortest (or cheapest) path.

---
Tags: graphs, minimum-spanning-tree, breadth-first-search
---


# Question
Title: How to construct the following turing machine?
> Construct a turing machine (TM) over the alphabet {a,b,0,1,#} that reads strings of the form (ab)^n with n\>0. If the string w on the tape has this structure, the TM should overwrite all letters with the character 1 and go into an accepting state and if not, the TM should overwrite all letters with the character 0 and remain in an unaccepting state.

I am not able to do the overwrite. Can someone show me how such a TM would look like?

# Answer
> 0 votes
Use a separate pair of states, let's say $p$ and $q$, for the overwriting.

In state $p$,

* check whether to continue overwriting;
* if not, you move to a post-overwriting state;
* if yes, overwrite the cell and go to state $q$.

In state $q$, move to the next cell and go to state $p$.

---
Tags: turing-machines
---


title: Propositional Logic: Entailment

text:
# Question
Title: Propositional Logic: Entailment
Given the sentences, ***S1***, ***S2***, if ***S1*** |= ***S***2 then all models that satisfy ***S1*** also satisfy ***S2***, how is the following statement correct?

`A ∧ ¬A |= B`

How can something and not something equate to true?

I am stuck trying to work out how true and false can still entail true, actually how can A and ¬A occur at the same time?

Thanks.

# Answer
> 0 votes
It's not easy to give a full explanation without knowing your axioms and rules, however, $A \land \neg A$ is a contradiction, and it is by exploiting that, that you can prove whatever you like.

First, let $\top = A \lor \neg A$.

We know that "*true **or** whatever else*" must be true. Since $\top$ is a tautology, then $\top \lor B$ must be true.

But since $A \land \neg A = \neg (A \lor \neg A) = \neg \top$ is assumed to be true we conclude the following:

* from $\top \lor B$ and $\neg \top$
* $B$

---

It all hinges on the fact that $A \lor \neg A$ is a tautology and that you assume that the negation of a tautology is true.

So to answer your question *"actually how can $A$ and $\neg A$ occur at the same time?"* It cannot, unless you have a contradiction. When you *assume* a contradiction, you can prove anything.

# Answer
> -1 votes
Think of it this way.

There are no elements of the empty set $\emptyset$. Moreover, for all sets $A$, $\emptyset \subseteq A$.

But what does subset actually mean? $A \subseteq B$ means that any element of $A$ must be an element of $B$. That is, $\forall x \in A, x \in B$.

It follows that for all sets $A$, $\forall x \in \emptyset, x \in A$. Every single element of $\emptyset$, every one of them, every *none* of them, is an element of every other set.

Assuming that $A \wedge \neg A$ is false in your logic (there are logics that admit controlled contradiction), then there are *no* models satisfy $S\_1$. It follows that *all* models that satisfy $S\_1$, every one of them, every *none* of them, also satisfy $S\_2$.

---
Tags: logic, propositional-logic
---


title: $\Theta(n^2 ) =\Theta(n^2 + 1)$

text:
# Question
Title: $\Theta(n^2 ) =\Theta(n^2 + 1)$
I'm reading *The Algorithm Design Manual* and this is one of the excersizes:

> Prove or disprove the following statement:
>
> $\Theta(n^2 ) = \Theta(n^2 + 1)$

I think this is untrue because the right side of the equation claims to have a multiple $c$ such that it is smaller than all the multiples of $n^2$, which is untrue. But since the book doesn't have answers and I'm not really sure about this question I had to ask.

Thanks a lot :)

# Answer
As we have on both sides of equality sets, then it should be prove correspondingly i.e we need to show, that $\Theta(n^2) \subset \Theta(n^2+1)$ and $ \Theta(n^2+1)\subset \Theta(n^2) $. Let's start with first:

Assume $f \in \Theta(n^2)$. This means, that for some constants $A\_1, A\_2 \gt 0$ holds

$$A\_1 n^2 \leqslant f(n) \leqslant A\_2 n^2$$. To obtain inequalities for $\Theta(n^2+1)$ we need $$B\_1 (n^2+1) \leqslant f(n) \leqslant B\_2 (n^2+1)$$ It's easy to see, that it's enough to take $B\_2 = A\_2$ for right hand and $0\<B\_1 \leqslant \frac{A\_1}{2}\leqslant \frac{A\_1 n^2}{n^2+1}$ for left hand, as $A\_2\>0$.
> 2 votes

---
Tags: asymptotics
---


title: Valid orderings for topological sort

text:
# Question
Title: Valid orderings for topological sort
I am reading *Algorithms* by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.

Are the other 3?

* B, A, D, C, F, E
* B, D, A, C, E, F
* B, D, A, C, F, E

# Answer
A *source* is a vertex with in-degree zero.

An order of the vertices is a *topological order* if deleting the vertices in that order deletes only *sources*.

Hence, you can verify that an order is topological by deleting one and one vertex, and never deleting a vertex with an in-edge.

Your answer is correct, the topological orders are `B,{A,D},C,{E,F}`, where you can choose the order inside the braces, i.e., there are four of them.
> 1 votes

# Answer
You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.
> 1 votes

---
Tags: topological-ordering
---


# Question
Title: Is transfer learning applied on only similar datasets only?
I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . I know it is too short, that is why I am now moving towards pretrained model. My question is that I read on Internet that Transfer learning applied on only similar datasets like lets say VGG model trained on Cats and Dogs , so we can use it for training the tiger images also . Can I use different dataset like I am using MobileNet on different brands of logos . Will it give good accuracy ?

# Answer
> 1 votes
Let me start by making an acknowledgement that in machine learning intuitions can be wrong and it is not possible to know beforehand what would work and what wouldn't work. That's why machine learning is very much an experiment based method. Having made this acknowledgement let me tell you my intuition. If you transfer learning from image processing problem to a different image processing problem then it shouldn't hurt if your network is deep enough. Most likely, a convolutional network's earlier layers find simple features that are useful to describe any image. Like horizontal lines and diagonal lines. Then, the deeper layers vary according to specificity of the dataset to find more complex features. Even if you are working on a wildly different image problem, what you can try to do is keep the earlier layers constant during the learning and just learn the deeper layers. After some learning you can allow the earlier layers to change as well to do some fine tuning.

---
Tags: algorithms, optimization, machine-learning, artificial-intelligence, neural-networks
---


title: Problem from the Cormen appendix C 1.13

text:
# Question
Title: Problem from the Cormen appendix C 1.13
I am currently working on *CLRS 1.13*. The idea is to use Stirling's approximation to prove that

$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$

Now directly replacing Stirling's approximation I arrive to something like:

$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$

Now the quotient is a function that ends up being $O(\frac{1}{n})$ because we have terms in $O(\frac{1}{n})$ and $O(\frac{1}{2n})$. The problem is that even if there is a quotient of two functions that are $O(\frac{1}{n})$.

I don't know if the result is still $O(\frac{1}{n})$. In fact I haven't seen any general rule for the quotient of two big $O$ s.

Is there a general rule that I can apply here?

# Answer
> 2 votes
Just simply use the inequality $1 + \Theta(1/n) \geq 1$ in the denominator. You will get the required answer.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Question concerning subset sum problem: split into 3 equal subsets
**Task:** Given an array $arr\[a\_1, a\_2, \dots, a\_n\]$ of integers, let $A = \sum\limits \_{i\in \\{1, 2, \dots, n\\}}a\_i$. Determine whether it is possible to spit $arr\[\]$ into 3 subsequences of equal sum, i.e. if $s\_1 =s\_2 = s\_3 =\dfrac{A}{3}$ where $s\_1 ,s\_2 , s\_3$ denoted the splitted arrays.

**My thoughts:** I will first examine whether there exists some sequence of numbers that sums up to $\dfrac{A}{3}$ via dp, then I will backtrack those numbers, "throw them out" (meaning I won't consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $\dfrac{A}{3}$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.

**Recurrence of DP:** $dp\[i\]\[j\] = dp\[i-1\]\[j-a\_j\] \text{ OR } dp\[i-1\]\[j\]$

$dp\[\]$ is a boolean array of dimension $n \times\dfrac{A}{3}$.

# Answer
Here my solution:

```
    boolean 3_Partition(int arr[]) {
        if (arr == null)
            return false;
        int sum = Arrays.stream(arr).sum();
        if (sum % 3 != 0)
            return false;
        int n = arr.length;
        boolean dp[][][] = new boolean[n+1][sum = sum / 3 + 1][sum];
        for (int i = 0; i < n+1; i++) {
            for (int j = 0; j < sum; j++) {
                for (int k = 0; k < sum; k++) {
                    if (i == 0 ) dp[i][j][k] = false;
                    else if (j == 0) dp[i][j][k] = true;
                    else if (k == 0) dp[i][j][k] = true;
                    else  dp[i][j][k] = j >= arr[i-1] && k >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k]
                          : j >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k]
                          : k >= arr[i-1] ? dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k] : dp[i - 1][j][k];
                }
            }
        }
        return dp[n][sum-1][sum-1];
    }

```
> 0 votes

# Answer
I don't think the proposed algorithm is correct. It may happen that the first solve for $A/3$ picks a set of numbers that makes it impossible to split the remainder into equal halves. Consider this example:

* Given the set of numbers $\\{1,1,3,3,3,4,8,10\\}$, which sum to $A=3\*11$
* Assume that the first DP picks $||\\{1,1,3,3,3\\}||\_1=11$
* It is impossible to split the remaining set $\\{4,8,10\\}$ into equal halves.

Here's a recursive function in pseudocode instead which computes what you need in a single step:

```
bool CanBuild3EqualSums(int sumA, int sumB, int sumC, int[] numbers)
{
    if(numbers is empty)
        return sumA == sumB && sumB == sumC;
    else
        return CanBuild3EqualSums(sumA + numbers[0], sumB, sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB + numbers[0], sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB, sumC + numbers[0], numbers.WithoutFirst())
}

```

This is a pure function (without side-effects). Add memoization and you'll end up with a DP algorithm. Of course, there are many other ways to formulate this. There is some potential for a more efficient, practical implementation:

* You could pass the index of the next number, instead of the whole array.
* You could get rid of sumC, and compute when needed, based on sumA and sumB
* If you have small values, a bottom-up formulation might be more efficient.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: Computing square vs computing square-root? Time complexity
I am working on something that requires checking a very large **natural** number $x$ to determine if it is the square root of an even larger **natural** number $y$. So I am wondering what are the fastest algorithms for computing square and square root, and how should I be approaching this i.e.

1. Computing $\sqrt{y}$ and comparing it with $x$
OR
2. Computing $x^2$ and comparing it with $y$

So as to write a code that has minimum time complexity.

# Answer
> 2 votes
There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$. Do this a few times for a few random primes $p$. (You can even pick a random number $p$ without requiring it be prime.) If there is any error in your square root, then it is likely that it will be detected by this test. The chances of failing to detect an error is exponentially small.

# Answer
> 1 votes
D.W.'s suggestion is absolutely worth doing if you expect the answer to be "false" a significant proportion of the time. With very little effort, you will be able to calculate most of the "no" answers quickly.

You're not really asking about the complexity of computing a square or a square root, because the problem that you're actually trying to solve is to *test* if some specific number is the square of another specific number. This problem is known to be solvable in close-to-linear time.

Interestingly, integer root classification is also solvable in close-to-linear time. For example, Bernstein's paper below shows that given $y$, we can find an $x$ and $k\ge 2$ such that $x^k = y$, or show that they do not exist, in $O(n\\,e^\sqrt{\log n \log \log n})$ time.

See:

# Answer
> 1 votes
If you want to write the code with minimum time complexity, and you ask about it here, then you can't write it. If you ask about the simplest code with a better than quadratic time complexity, look up the Karatsuba method for fast multiplication, and possibly the Toom-Cook method.

In principle, the fastest square root algorithm and the fastest multiplication algorithm will have the same time complexity until we find a multiplication algorithm faster than O (n log n) since the square root can be calculated using few multiplications of n bit, n/2 bit, n/4 bit etc. numbers. But your problem is easier solved using multiplication.

---
Tags: algorithms, time-complexity, discrete-mathematics
---


# Question
Title: Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"
I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$. It's claimed that the algorithm is linear time. *However, I wonder if this assumes the dimension n is constant.*

My understanding of the analysis is that to generate $N$ points requires $2N-1$ iterations, and each iteration is constant time. I agree with the $2N-1$ iterations, but I'm not sure about each iteration being constant time.

In each iteration, they sample a small constant $k$ points, and then check whether or not these points are near to any of the previously generated points using a background grid to assist. However, isn't the number of neighboring cells to check exponential in $n$? It seems like the runtime of the given algorithm using the background grid should be something like $k N \exp(n)$, (or $kN^2$ if you just check the other points directly).

Have I misinterpreted the algorithm or the analysis? I get that for a fixed $N$ it will be constant (assuming $k$ is constant). Is that the standard assumption when saying an algorithm is "linear time"? To me this seems a bit misleading because they mention dimension in the title. If you go to high enough dimension and use the "constant time" algorithm, the constant will be exponential in $n$ which means the algorithm is not "fast" in "arbitrary dimensions".

As an afterthought, does it even make sense for $k$ to be constant. If you don't increase $k$ exponentially with $n$ then the "density" (number of points per volume) of the points will go to zero (although this is more of a "modeling" choice than an analysis choice).

# Answer
I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see.

Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a line to a square to a cube, etc. A more accurate implementation can slow this growth by excluding the corners of the hypercube in higher dimensions, since they don't fulfil the distance criteria, but it won't stop the exponential growth.

Increasing the $k$ for the higher dimensions, on the other hand, does not make much sense to me. $k$ are the candidate points to be tested for acceptance, so if you find at least one valid point among them, the algorithm will continue until the entire space is filled. If anything, I think it's easier to find a valid point for a higher-dimensional case, since there are more degrees of freedom.

Also, here's a link to my implementation: https://github.com/diregoblin/poisson\_disc\_sampling
> 3 votes

---
Tags: time-complexity, graphics
---


# Question
Title: What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions
Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. **What is the sequence of indexes $i\_1,i\_2...i\_m$ such that $\sum\_{j=1}^mA\[i\_j, j\]$ is maximized, subject to the constraint that each run of a value in $i\_1...i\_m$ must be at least $r$ entries long?**

A correct algorithm with time linear in $m$ seems possible with dynamic programming. It would be even nicer to know **the name of the problem and some academic reference to a correct solution.** This is a minor methodological step in an analysis I'm doing for an interpersonal communication research paper, so ideally I'd like to find a paper to cite. This smells very similar to the dynamic programming homework problems I did in undergrad, so I'd be surprised if there isn't work on it.

In practice, $m \approx 12000$, $n=3$, and $20 \leq r \leq 200$.

# Answer
> 1 votes
I believe this can be solved in $O(nm)$ time using dynamic programming:

$$\begin{align\*} B\[i,k\] &= A\[i,k\] + \dots + A\[i,k+r-1\] + C\[i,r\]\\ C\[i,k\] &= \max(A\[i,k\] + C\[i,k+1\], \max\_{i'} B\[i',k\]) \end{align\*}$$

Note that you can compute $A\[i,k\] + \dots + A\[i,k+r-1\]$ in $O(1)$ time as the difference of two prefix sums (assuming you have done a one-time precomputation to compute all prefix-sums).

The answer is then $\max\_i B\[i,1\]$. Computing it takes $O(nm)$ time, as there are $O(nm)$ entries to fill in, and each one takes $O(1)$ time to fill in, using the equations above.

Interpretation:

* $B\[i,k\]$ is the maximum possible value of $\sum\_{j=k}^m A\[i\_j,j\]$ such that $i\_k=i$ and $i\_k,\dots,i\_m$ satisfy the repetition rule
* $C\[i,k\]$ is the maximum possible value of $\sum\_{j=k}^m A\[i\_j,j\]$ such that $i\_k,\dots,i\_m$ satisfy the repetition rule *except* that if $i\_k=i$, the run starting at $i\_k$ can be of any length (but all subsequent runs must be at least $r$ long). In other words, $$C\[i,k\] = \max\_\ell A\[i,k\] + \dots + A\[i,k+\ell-1\] + \max\_{i'} B\[i',k+\ell\]$$

Generally, this is not the kind of thing I would expect to find papers about. I would expect to see a one-sentence "can be solved by dynamic programming", possibly with an explanation of the max-trick above to reduce the running time from $O(nmr)$ to $O(nm)$, but not an entire paper about it. So I would not bet on such a paper existing. But I could be wrong. It's certainly possible there could be such a paper. I would not know how to go about looking for it.

---
Tags: dynamic-programming
---


# Question
Title: What data structure to use for large scale DHCP server
What data structure would one use to keep a large number of IP addresses (v4 and v6, but not at the same time if that makes a difference), and I'm talking about millions, preferably hundreds of millions at a time for fast look-up.

The preference would be for fast look-up. Initial filling of the data structure is not too big of a concern. To have a small memory footprint is not also a big concern, but it would be nice to have that part as small as possible.

I was thinking in lines of using some sort of binary tree, but don't know if hash map would suffice...

Thanks in advance!

# Answer
A good data structure for IPv4 translation is a 256-way trie, this means any lookup always requires exactly 4 memory accesses, and shared prefixes will be hot in cache.

You can do the same for IPv6 but implementing a unique suffix check (instead of always expanding trie nodes) is probably worth it.
> 1 votes

# Answer
It sounds like the only operations you need to do are lookup, insert, and delete. If so, a simple data structure is a hashtable. It should achieve constant-time access on average.
> 1 votes

---
Tags: data-structures
---


# Question
Title: High dimensional Pareto dominance query data structure
I have a large (10 million+) set $X$ of data points in some high dimensional $\mathbb{R}^d$ ($d \geq 500$) space. Each data point is quite sparse, e.g. has around $10$ components. Every missing component can be seen as having value $-\infty$ for the purposes of this problem. Associated with each data point $X\_i$ is a price $y\_i$.

As a quick refresher, a Pareto order is a partial order that orders vectors by those that are 'strictly better', component-wise. That is, for $a, b \in \mathbb{R}^d$ we have

$$a \preceq b \iff \forall i : a\_i \leq b\_i.$$

In this case we also say that $b$ *dominates* $a$ (although not strictly, $a$ and $b$ could be equal). Finally note that this is very much a *partial* order, it very often happens that $a$ and $b$ are incomparable.

Let $D(z) = \\{x \in X : z \preceq x\\}$ be the elements in our dataset that dominate $z$ (taking into account only the data points, not their associated prices). I wish to know if there exists an efficient data structure that can answer two things about some $z \in \mathbb{R}^d$ (even sparser, e.g. around $4$ to $5$ components):

1. the number of items that dominate $z$, or $|D(z)|$, and
2. the cheapest $k$ prices among those that dominate $z$, or the smallest $k$ elements of $\\{y\_i : X\_i \in D(z)\\}$.

Note that $k$ is small here (e.g. $10$) even though $D(z)$ might contain thousands of elements.

---

Does a data structure solving this problem efficiently exist? Every approach I can think of suffers badly from the curse of dimensionality.

# Answer
Here is one approach you could consider. If the number of non-missing coordinates is tightly concentrated around 10, it might help you partly avoid the curse of dimensionality. I don't know whether it will be useful in practice.

Choose a random hash function $h:\\{1,\dots,d\\} \to \\{1,\dots,10\\}$. If $x \in \mathbb{R}^d$ is a data point, let $f(x)$ be its *signature*, where $f:\mathbb{R}^d \to \mathbb{R}^{10}$ is defined as $$f(x) = (x^\*\_1,\dots,x^\*\_{10})$$ where $x^\*\_j = \max \\{x\_i \mid h(i)=j\\}$.

Notice that the signature is dense, i.e., $f$ maps a sparse high-dimensional vector to a dense low-dimensional vector.

Also, notice that $f$ is monotonic: if $z \preceq x$ then $f(z) \preceq f(x)$. The converse does not necessarily hold.

The approach will be to build a data structure that, given a query $z$, helps us enumerate all $z$ such that $f(z) \preceq f(x)$; then we will check each such $x$ to see whether $z \preceq x$, and count the number that do, or output the lowest-priced ones that do. This reduces the problem from a 500-dimensional problem (on sparse data points) to a 10-dimensional problem (on dense data points).

How does the 10-dimensional data structure look? We can use a simple trie, where the $i$th level branches on the value of $x^\*\_i$, and each leaf stores one data point. In practice, I suggest organizing the list of children at the $i$th level using a binary search tree keyed on $x^\*\_i$, rather than as a list.

Now, the lookup algorithm simply traverses the trie recursively, but with the traversal pruned in the obvious way. In other words, at each level we only explore the children $x^\*\_i$ where $z^\*\_i \le x^\*\_i$ (for query $z$). Using the binary search tree data structure, at each level it is easy to enumerate only those children without having to enumerate the other children.

What is the running time of this algorithm? The worst-case time could be bad, but I'll analyze the average-case running time, via an extremely crude heuristic. If $z,x$ are two randomly chosen data vectors, then crudely $\Pr\[z^\*\_i \le x^\*\_i\] \approx 1/2$ for each $i$, as we have two randomly chosen numbers from $\mathbb{R}$ and it is roughly equally likely which one is larger. Therefore, we can expect that only about a $1/2^{10}$ fraction of the data points $x$ will satisfy $f(z) \preceq f(x)$. And, the running time of the recursive traversal of the trie will be approximately proportional to the number of such data points $x$. Therefore, this heuristic predicts the average-case running time of this algorithm, on a random query $z$, to be something like $O(|X|/2^{10})$ time. In other words, this is approximately a 1000-fold speedup over the naive algorithm of enumerating all data points in your dataset. This crude analysis is overly optimistic and probably the true running time will be worse (e.g., due to collisions in the hash function, as this analysis implicitly assumed that both $z$ and $x$ have exactly 10 components and there are no collisions in the hash function, but in practice neither of those will always be true).

---

P.S. There are multiple variants possible. We can also consider replacing 10 by an arbitrary $d'$ and optimizing over $d'$. Also, we can alternatively define $f$ by $$f(x) = (x^\*\_0,x^\*\_1,\dots,x^\*\_{d'})$$ where $x^\*\_0$ is the number of $x^\*\_1,\dots,x^\*\_{d'}$'s that are not $-\infty$. I don't know whether either of those would be better, but they could be variants to try on your data set.

Another possible optimization is to precompute a dozen different copies of the data structure for a dozen different hash functions. Then, when you want to answer a query for $z$, check which hash function maximizes the number of coordinates in $f(z)$ that are not $-\infty$, and use the corresponding data structure for the lookup. If $x$ has exactly 10 non-missing coordinates, then it is very likely that one of these hash functions leads to a signature with only 0, 1, or 2 coordinates at $-\infty$. Also you could consider an approach where $d'$ is large, say $d'=20$; then there is a good chance that there will be one hash function that does not introduce any collision... though I'm not sure what the effect of increasing the dimension like that might be on running time.
> 1 votes

# Answer
Your problem can be also stated as a counting version of the orthogonal range searching problem which is well studied in computational geometry. Let us see how.

Let $m\_{i}$ denote the maximum $i^{th}$ coordinate value among all the points in $X$. Then, the query of finding $|D(z)|$ can be stated as follows:

> Given an axis-parallel rectangle $R$ with the bottom left coordinate as $z$ and the top right coordinate as $(m\_{1},m\_{2}, \dotsc,m\_{d})$, find the number of points in $X$ that lie inside $R$.

---

However, this does not answer your question accurately since in your scenario we have an added advantage that the vectors are sparse. This property can surely exploited to design more efficient algorithms.
> 0 votes

---
Tags: data-structures, computational-geometry, pareto
---


# Question
Title: Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$
how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much..

$$\[\\; (a+b)^\* c^\* (a+b)^\* \\;\] \cap \[\\; (c+b)^\* a^\* (c+b)^\*\\;\]$$

# Answer
Any word can be written as a concatenation of *runs*. For example, $$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$ Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.

The regular expression $(a+b)^\*c^\*(a+b)^\*$ captures all words with at most one $c$-run. Similarly, the regular expression $(b+c)^\*a^\*(b+c)^\*$ captures all words with at most one $a$-run. Therefore the intersection consists of all words with at most one $c$-run and at most one $a$-run.

Since the only other possible run is a $b$-run, we get that the intersection is $$ b^\*a^\*b^\*c^\*b^\* + b^\*c^\*b^\*a^\*b^\*. $$
> 1 votes

---
Tags: formal-languages, regular-languages, automata, regular-expressions
---


# Question
Title: Running time of a function $P$ calling itself via $P(P(n/2))$
```
int P(int n)
{
  if (n==1)
    return 1;
  else
    return P(P(n/2));
}

```

How will this function `P(P(n/2))` be executed and what will be the recurrence relation for this code?

Original image with the code

# Answer
> 1 votes
There is an unwritten assumption that the input is always at least $1$ (otherwise your function never terminates). Under this assumption, it is easy to prove by induction that the function does terminate, and always returns $1$. Therefore in the expression $P(P(n/2))$, we are first invoking $P$ with the input $n/2$, and then with the input $1$. It follows that the running time $T(n)$ of your function satisfies the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + \Theta(1), $$ with initial condition $T(1) = \Theta(1)$. The solution is $T(n) = \Theta(\log n)$.

---
Tags: complexity-theory, data-structures, algorithm-analysis, recurrence-relation, recursion
---


# Question
Title: Problems solvable in time $f(n)$ but not in time $o(f(n))$
Suppose I have some (increasing, nice asymptotics) function $f(n)$. Does there exist a complexity theoretic problem (e.g. PATH, 3-SAT, GO etc.) that can be solved in time $\Omega(f(n))$ on a deterministic Turing machine. In other words is there a problem proven to be an element of $\mathsf{DTIME}(f(n))$, but not $\mathsf{DTIME}(g(n))$ for any function $g$ such that $\frac{f(n)}{g(n)} \to \infty$ as $n \to \infty$?

# Answer
> 3 votes
Consider the language of all binary words which consist only of zeroes. It can be decided on a deterministic Turing machine in time $O(n)$, but not in time $o(n)$.

For general time-constructible functions $f(n)$, the time hierarchy theorem shows that the problem of deciding whether a Turing machine halts in time $f(n)$ can be solved in time $O(f(n)\log f(n))$ but not in time $o(f(n))$. It is not known how to eliminate this logarithmic gap in general.

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


title: Sum duplicates in array problem

text:
# Question
Title: Sum duplicates in array problem
I get $n$ numbers, where every number is an integer between 1 and 1000. If within given numbers are duplicates, I sum all of them to one number. I repeat it until I have only distinct elements. As a result I return number of distinct elements at the end.

How do I do it in additional space complexity $O(1)$ and time complexity $O(n)$.

I know how to do it in space complexity $O(k)$ and time complexity $O(n+k\log k)$, where $k$ is number of distinct numbers.

# Answer
Create an array $A$ of 1000 elements, indexed from $1$. Store in $A\[i\]$ the number of input elements equal to $i$. This can be done in linear time by scanning the input elements once.

Create a list $L$ which will contain at most $1000$ elements (and can hence be implemented using a fixed-size array). Each element of $L$ is a pair $(m\_x, x)$ where $x$ is a number and $m\_x \> 0$ is the number of its occurrences. Initialize $L$ from $A\[i\]$ as follows: for each $i$ with $A\[i\]\>0$ append to $L$ the pair $(A\[i\], i)$ (this can be done in constant time since $A$ contains only $1000$ elements).

From now on the algorithm is trivial, as it is just a simulation of the rules in your question.

Repat:

* Search $L$ for the element $(m\_x, x)$ with $m\_x \> 1$ that minimizes $x$.
* If such an element does not exist, return the length of $L$.
* Otherwise:
    + Delete $(m\_x, x)$ from $L$.
    + If $L$ contains an element $(m\_y, y)$ where $ y = x m\_x$ increment $m\_y$ by $1$; Otherwise add $(1, x m\_x)$ to $L$.

An iteration can be carried out in constant time since all list operations take constant time as well ($L$ always has at most $1000$ elements).

Consider now the quantity $\eta$ defined as the number of elements in $L$ plus the number of elements in $L$ with multiplicity greater than $1$. Initially $\eta$ is at most $2000$. In all but the last iteration one of the following two things happens:

* An element with $(m\_x, x)$ with $m\_x \> 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and some $m\_y$ is incremented (causing $\eta$ to increase by at most $1$).
* An element with $(m\_x, x)$ with $m\_x \> 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and a new element $(1, x m\_x)$ is added to $L$ (causing $\eta$ to increase by $1$).

In any case, each but the last iteration decreases the value of $\eta$ by at least $1$. Since the final value of $\eta$ must be positive, it follows that the total number of iterations is at most $2000 - 1 + 1 = 2000 = O(1)$.

Finally, observe that above procedure only uses constant amount of memory and that any $O(n)$ time and $O(1)$ space algorithm is also a $O(n + k \log k)$ time and $O(k)$ space algorithm, thus also answering your second question.
> 1 votes

# Answer
Assuming that you only add together identical numbers to themselves (e.g. not `2 + 2 + 4 + 4`), and all in one go (e.g. `2, 2, 2` becomes `6`, not `4, 2`), there is a fairly simple algorithm. Let array $A$ be your input.

1. Initialize an empty priority queue $Q$ (that pops in ascending order) and $C$ as a hash map with $O(1)$ access where missing values are reported to have value $0$ instead.
2. For $1 \leq i \leq n$: increment $C\[A\[i\]\]$, then if $C\[A\[i\]\] = 1$ add $i$ to $Q$.
3. While $Q$ is not empty, pop from $Q$, giving $i$. If $C\[i\] \> 1$, increment $C\[i \cdot C\[i\]\]$, add $i \cdot C\[i\]$ to $Q$ and delete $C\[i\]$. Otherwise if $C\[i\] = 1$ this is a final distinct element, and you can save it (or increment a counter).

Step 1 takes constant time, step 2 takes $O(n)$ time (at most $1000$ appends to $Q$ are made so that's constant time).

For step 3, if we let potential $p = |Q| + |\\{i : C\[i\] \> 0\\}| + |\\{i : C\[i\] \> 1\\}|$, at each iteration we always reduce $p$ by $1$ because we pop from $Q$. Then, if $C\[i\] \> 1$ we stay at worst neutral because we delete $C\[i\]$ (reducing $p$ by $2$), increment $C\[i\cdot C\[i\]\]$ (increasing $p$ by $1$ only if it was initially $0$) and append to $Q$ (increasing $p$ by $1$). Thus in each iteration $p$ decreases by at least $1$, and trivially initially $p \leq 3000$, meaning step $3$ finishes in a constant number of iterations at worst. Each iteration of 3 is also constant time, with the only question mark being put at appending to $Q$ \- however $Q$ has at most $1000$ elements at any time, thus that is constant as well.

The total amount of space used is also constant, both $C$ and $Q$ have a $1000$ elements at worst.
> 1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Generating sparse connected Erdős–Rényi random graphs
Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of the graph: if $p$ is greater than $t$ the graph will be almost surely connected, otherwise disconnected. The farther you move $p$ from the threshold the higher the chance that the resulting graph will be disconnected/connected (source: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi\_model).

I am currently trying to output from an Erdős–Rényi process a graph that is as sparse as possible. In my case $n=10000$ and therefore $t=0.00092$, which means that a connected random graph of 10000 nodes should have on average 46000 edges. Through testing with igraph I could go as low as 37000 edges: $t=0.00074$. Now I'm stuck (because the probability of outputting a sparser graph is too low) and I don't know how to further lower the degree of the graphs. Is there a way to generate sparser random graphs? I know I'm already far below the threshold. In case no solution is found for this model what is the best way to generate a very sparse connected graph?

# Answer
> 1 votes
Brenday McKay suggests an algorithm on mathoverflow. He considers a fixed number of edges, but you can also sample from $G(n,p)$ according to his method. First, calculate $c\_{n,m}$ for all $m$. Then sample $m$ in proportion to $p^m (1-p)^{\binom{n}{2}-m} c\_{n,m}$. Then use his algorithm.

Gray, Mitchell, and Roughan, Generating connected random graphs, suggest an MCMC algorithm, and analyze it empirically.

Both of these algorithms are for sampling $G(n,p)$ random graphs conditioned on the result being connected. There are also many heuristics for sampling other distributions of random connected graphs in the sparse regime, where usually the focus is on generating some "random-looking" distribution rather than a specific one. For example, you can generate a $G(N,p)$ random graph and pick a connected component, or you can add a random spanning tree to a $G(n,p')$ random graph.

---
Tags: graphs, random-graphs
---


title: Query Regarding Direct cache mapping

text:
# Question
Title: Query Regarding Direct cache mapping
Thank you for looking into this, I have a problem regarding direct cache mapping, My problem really though is with the question formation itself and the problem I am about to present seems to have inconsistency and has unclear description. So the problem is as follows ( I am presenting exactly as given )

> 32 bit architecture
> Main memory size = 8GB
> cache size = 512KB
> Block size = 32 words
>
> To Find
>
> 1. Number of bits required for Byte Offset = ?
> 2. Number of bits required for main memory address = ?
> 3. Number of bits required for main memory block number = ?
> 4. Cache Index bits = ?
> 5. Tag-bits = ?
> 6. Size of Tag Directory = ?

Now My Interpretation of the solution is as follows

> As it is 32 bit architecture which means **Word** size is **4 Byte** ( I am confused about this part the most as the question states cache block size in **Words** but expects to calculate **Byte** offset ) but for the sake of this problem, moving on main memory size is **8GB** that's **233Bytes**, cache size ( blocks only, this does not include tag directory which is part of cache controller ) Block size of **32 Words** or **128 Bytes**, now If you agree with me on this much, or else this is probably where I am wrong so please correct me right here. Now assuming I am correct so far, I will first calculate main memory address bits, that will be, first let's calculate it's size then let's do binary log, that will be **233Bytes / 4 Bytes per word** this comes out to be **231 Words** means **31 bits** for memory address and our second answer, next I calculate number of main memory blocks that will be **233Bytes / 128 Bytes per block** this comes out to be **226 Blocks** of main memory so the number of bits required for main memory block number would be **26 bits**, so this gives our third answer, moving forward as I assume a single cache/main memory block to be of **128 *Bytes*** and not ***Words***. So for byte offset within a block it must be **7 bits** ( Point of highest concern ) and this should be our first answer according to the question. Now let's calculate number of cache blocks that will be **219Bytes / 128 Bytes per block** which is **212 Blocks** so cache index size will be **12 bits** which is our fourth answer, we're almost done ! Now Tag bits should be and since it's direct mapped it should be **memory address size - ( cache index + Word or Byte offset )** that is **( 31 - (12 + 7)) = 12 bits** that is our fifth answer and finally size of tag directory will be **212Cache Blocks * 12bits per tag**, Now not going into exact answer in **KB's** is this approach right or have I made a mistake or is the problem formulation incorrect ( as I think the mistake must be with cache blocks being in bytes or words ) ?

# Answer
I am going to talk about **the cache - related** questions:

1. Block size is $$32 \text{words} = 2^5$$ . That, means that you need, **5 bits for offset**.
2. $$\\#\text{blocks}=\frac{2^{19}}{2^5}=2^{14}$$, so you need **14 bits for the index** ( to indentify which block in cache is going to represent your wanted memory adresss )
3. For a 32 - bit adress, **tag** is the rest : $$32 - 14- 5 = 13$$ bits.
> 1 votes

---
Tags: computer-architecture, cpu-cache, cpu, memory-access, cache
---


# Question
Title: Algorithm to evenly distribute a hierarchical dataset
I am working on a chatbot designer interface. The dataset for the conversation flow consists of messages. Each message has a parent message and can have multiple possible next messages. The system displays one of the possible next messages depending on the reply. This makes it a complicated structure of parent-children relations.

On the dialog flow designer interface, the user is able to drag messages around in order to achieve a visual clarity of the designer dialog flow. This is loads of work for the user.

I want to implement an algo that would do this job for the user. So the messages should distribute themselves at even distances and making sure that their children are also around their parent message evenly distributed.

I have not studied algos, so I am not sure what jargon to look for. I don't even know the proper tag to use in this question. What this kind of algorithm is called and how to achieve this?

# Answer
You want to use an algorithm for graph layout. There are many out there, as well as some tools.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Each cycle in the graph, the edge with the minimum weight belongs to MST
Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$ a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in each cycle in the graph, the edge with the minimum weight belongs to $T$.

I either need to prove it in a positive way or give a counterexample.

# Answer
Following is a simple counterexample: Take a complete graph on four vertices: ${u\_{1},u\_{2},u\_{3},u\_{4}}$, with edge weights $w(u\_{1},u\_{2}) = 1$, $w(u\_{2},u\_{3}) = 2$, $w(u\_{1},u\_{3}) = 4$, $w(u\_{1},u\_{4}) = 5$, $w(u\_{2},u\_{4}) = 3$, and $w(u\_{3},u\_{4}) = 6$. Here MST is composed of edges: $(u\_{1},u\_{2})$, $(u\_{2},u\_{3})$, and $(u\_{2},u\_{4})$ with total weight $6$. And, no edge of the cycle $(u\_{1},u\_{3},u\_{4})$ is part of the MST.
> 3 votes

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


# Question
Title: Boolean logic: why is the "opposite" of and equal to or?
In *boolean logic*, why is the "opposite" of AND (`&`) equal to OR (`|`)?

For example, why would `!(A & B)` be equal to `(!A | !B)`?

I understand that *not `A`* would simply be `!A`, but why does AND change to OR?

# Answer
This is called DeMorgan's law, and let us think about it like this... By the way, let

* $\land$ be &&
* $\lor$ be ||
* $\neg$ be !

You have a door, and the door has two locks. To open the door you therefore need keys $A$ and $B$, written $A \land B$.

Well, suppose that someone is not able to open the door. Well, then that must be because they don't have both keys, or, $\neg (A \land B)$.

But analysing this situation, if you *do not have two keys*, you either lack $A$ or you lack $B$, or in other words, you either $\neg A$ or you $\neg B$.

Hence, $\neg (A \land B) = \neg A \lor \neg B$.

You can go through the exercise with a door where you need 1 of 2 keys to open for the reverse case.
> 3 votes

---
Tags: propositional-logic
---


title: Families of sets indexed by another set

text:
# Question
Title: Families of sets indexed by another set
I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.

If we have a set $A=\\{ab,b\\}$ do we get to assume that the null string $\epsilon$ is also a member of that set? If we have another set $B=\\{\epsilon\\}$, does $A\cap B = \\{\epsilon\\}$ or does $A∩B=\emptyset$?

On a related note, I am having trouble understanding the meaning of a little chunk in the textbook. What does "family of set indexed by another set $I$" mean? What does the set $I$ consist of here? I am very confused by the notation as well. Anything you can do to help me understand the excerpt below is appreciated.

> Set concatenation distributes over union: \begin{align} A(B\cup C) &= AB \cup AC, \\ (A \cup B)C &= AC \cup BC. \end{align} In fact, concatenation distributes over the union of any family of sets. If $\\{B\_i \mid i \in I \\}$ is any family of sets indexed by another set $I$, finite or infinite, then \begin{align} A \bigl( \bigcup\_{i \in I} B\_i \bigr) &= \bigcup\_{i \in I} AB\_i, \\ \bigl( \bigcup\_{i \in I} B\_i \bigr) A &= \bigcup\_{i \in I} B\_iA. \end{align} Here $\bigcup\_{i \in I} B\_i$ denotes the union of all the sets $B\_i$ for $i \in I$. An element $x$ is in this union iff it is in one of the $B\_i$.

# Answer
The notation $\\{ x\_1,x\_2,x\_3,\ldots,x\_n \\}$ means "the set of elements $x\_1,x\_2,x\_3,\ldots,x\_n$". In particular, *all* elements in the set are listed. If an element isn't listed, it doesn't belong to the set. For example, $\epsilon$ is *not* an element of $\\{ab,b\\}$. There is absolutely nothing special about $\epsilon$. It is a bona fide word, and undergoes no special treatment. It is not an element of $\\{ab,b\\}$ just as $abba$ is not an element of $\\{ab,b\\}$.

As for your second question, here is a family of sets indexed by $I = \\{a,b,c\\}$: $$ B\_a = \\{a,ba\\}, B\_b = \\{b,ba\\}, B\_c = \\{\epsilon,aa,bbb\\}. $$ The union of this family is $$ \bigcup\_{i \in I} B\_i = B\_a \cup B\_b \cup B\_c = \\{\epsilon, a, b, aa, ba, bbb \\}. $$ The set $I$ is completely arbitrary. It could be the empty set, it could be a singleton, it could be a larger finite set, it could be an infinite set. For example, we can define a family of sets indexed by the natural numbers (including zero): for every $n \in \mathbb{N}$, $S\_n = \\{n,-n\\}$. The union of this family consists of all integers: $\bigcup\_{n \in S\_n} S\_n = \mathbb{Z}$,
> 1 votes

---
Tags: strings, sets
---


title: Reduce PDA for a given language

text:
# Question
Title: Reduce PDA for a given language
I drew a Push-down Automata, accepting the following language: $$ \\{ xcy : x,y \in (a+b)^\*, \\#\_a(x) \> \\#\_{bb}(y) \\}. $$ Here $\\#\_{bb}(y)$ counts the number of times that $bb$ appears in $y$, *with overlaps*. For example, $\\#\_{bb}(bbb) = 2$.

My question here. Is it possible to reduce my PDA to less states? Thanks.

# Answer
> 1 votes
Yes. You can obtain a PDA with only one state by "encodng" the state of your PDA into the stack of the new PDA. See this document.

---
Tags: automata, pushdown-automata
---


# Question
Title: Maximum-coverage minimum-overlap intersection of sets
I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.

The question I *think* I need the answer to: **given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities?** Alternatively, **what is the smallest number of cameras I need to have 100% coverage of all points of interest?** The latter is the real underlying form of the question, but the former may be an XY problem.

How do I optimize this problem?

---

My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:

Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could *put* cameras ("sentries").

Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.

I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.

---

My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. `set([1,3,4])`) or a numpy array that's a bitmask of targets viewable (e.g. `numpy.array([False,True,False,True,True],dtype=bool)`), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).

I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.

My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will *always* be preferred.

# Answer
> 2 votes
Without knowing anything about the restrictions to your problem, the general version is Set cover, one of Karp's 21 NP-complete problems.

However, if you know more about the structure of the data, you might be able to get better algorithms, see for example the Art gallery problem, where you are given a polygon, and want to find the minimum number of guards/cameras you should place that cover the entire polygon.

---
Tags: optimization
---


# Question
Title: Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular
I'm trying to prove that $L=\\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it via closure properties (for example a union of $L$ and another regular language which may give a non-regular language).

It simply doesn't occur to me any language to use alongside $L$ (I guess I lack some imagination...)

# Answer
> 3 votes
Consider the intersection of your language $L$ with the regular language $L' = \\{b^r a^m \mid r,m \ge 0 \\}$. Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \\{ b^r a^r \mid r \ge 0 \\}$, which is a well-known non-regular language.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Why do we need Kleene Star when there is concatenation?
For an alphabet $A = \\{ a\_1, a\_2..., a\_n \\}$, the set of regular langages $L\_r$ on $A$ are recursively defined by closed union, concatenation, and Kleene star's operator. I understood that languages ($A^\*$) and regular languages (a subset of $A^\*$) are different. **Why do we need Kleene star, isn't concatenation enough for this definition?**

Very simple "proof" that should be obviously wrong:

If $X \in L\_r$ a regular language on $A$, and $E \in X^\*$ (if i'm right also $X^\* \in L\_r$) a word then we could write $E$ as $e\_1e\_2\dots e\_n = e\_1 . e\_2 \ldots e\_{n-1} . e\_n$, with each $e\_i \in X$. Then $E$ is explicitly constructible by concatenation.

I forgot $\epsilon$ but so just add a simple rule that allow $\epsilon$. My intuition says that it has something to do with infinity, that Kleene Star allows infinite-lengh chains whereas concatenation doesn't. Is it that?

# Answer
Regular expressions without Kleene star define *finite* languages. You can prove this by induction on the structure of the regular expression. In contrast, $a^\*$ is a regular expression which defines an infinite language.

We could try to define $a^\*$ using concatenation and union: $$ a^\* = \epsilon + a + a^2 + a^3 + \cdots $$ Unfortunately, the required regular expression is *infinite*, which we do not allow (infinite expressions do make sense in some contexts, for example in infinitary logic, but not here).
> 6 votes

---
Tags: regular-languages
---


title: Indentations in If-Else?

text:
# Question
Title: Indentations in If-Else?
I am a beginner at Java and this code example came up in class:

```
int horsepower = 15;
      if(horsepower > 15)
         if(horsepower <= 20)
            System.out.println("There is a lot of horsepower");
      else
          System.out.println("The car super fast");

```

the output is nothing but I can't understand why.

I have 2 questions I would like to clarify:

1. why did the code under the else statement not get executed?
2. I understand that without the brackets { }, the if condition can only execute the next statement. In this case, if horsepower variable is 17 instead, will "There is a lot of horsepower." be printed ? I am unsure if the System.out.println("There is a lot of horsepower"); still qualifies as being part of the next statement of the first if condition.

Please advise. Thanks!

# Answer
Indentation has absolutely no syntactic or semantic meaning in Java, and indeed in most popular languages (the main exception is Python).

Which *if* does your *else* belong to? This is an instance of the famous dangling else problem. The syntax of Java associates each *else* to the innermost *if*, so the Java compiler understands your code in a way which is different than what your indentation suggests. If you want to associate the *else* with the outer *if*, you can use curly brackets.
> 3 votes

---
Tags: java
---


# Question
Title: All prefixes with same length as their suffix is a regular language
Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \\{x \in \Sigma^\* \mid \exists y \in \Sigma^\* (xy\in L \wedge |x| = |y|)\\}$$ is regular. I thought of taking the set of even length strings over $\Sigma^\*$ (given by $(00\cup01\cup10\cup11)^\*$) and then interescting with $L$, which would be regular because the intersection of regular languages is regular. Then, the set of prefixes of this language is regular (by a previous exercise), but that's useless because that set of strings isn't actually the set $\frac{1}{2}L$. In particular, we didn't constrain the prefixes to be the ones with equal length suffixes.

Baically, I'm really stuck on how to make a FA that recognizes the length of the strings. Namely, given $x$ how do we add $\epsilon$ transitions to arrive at $xy$ with $|x| = |y|$, which we then pass in $xy$ to the FA for $L$? Thanks in advance, I've been scratching my head on this for a while.

# Answer
Given a DFA $A$ for $L$, construct an NFA which operates as follows:

* The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
* The NFA will maintain two states, $q\_1,q\_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
* For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ (which corresponds to a symbol in $y$), and advance $q\_1$ using $\sigma$ and $q\_2$ using $\tau$.
* The NFA is at an accepting case if $q\_1 = q$ and $q\_2$ is an accepting state of $A$.
> 4 votes

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


# Question
Title: Finding a clique in undirected graph is P or NP? (proof)
Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| \> |V|/2$ is in P or NP-hard? How can I prove it?

# Answer
Given a graph $G=(V, E)$, the problem of **finding** a clique $C$ with $|C| \ge \frac{|V|}{2}$ is a search problem and, as such, is neither in $\mathsf{P}$ nor in $\mathsf{NP}$ since $\mathsf{P} \subseteq \mathsf{NP}$ and $\mathsf{NP}$ only contains **decision** problems.
> 0 votes

---
Tags: algorithms, graphs, np-complete, clique
---


# Question
Title: why does LSPACE(log space) complexity class exist but not logtime?
I noticed that in complexity classes, logspace class is defined but there is no logtime.

I was wondering how is that possible?

Normally, I would expect the opposite, It is possible to do a search query in an ordered list in time less than the time of iterating over all items (==\> Logtime?). However you can't store a list in of size n in log(n) space...

So how come Logspace exists but not logtime? there's obviously something wrong with my reasoning.

Could someone please correct me?

Thanks in advance

# Answer
Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting.

What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform circuits. A related complexity class is ALOGTIME, which is the uniform version of NC¹. Buss famously proved that the formula evaluation problem is ALOGTIME-complete. For comparison, the circuit evaluation problem is P-complete.

Algorithms running in $o(n)$ time on random-access machines are known as *sublinear time algorithms*. Such algorithms also abound in the area of *data structures*.
> 17 votes

---
Tags: complexity-theory, time-complexity, space-complexity
---


title: Condition to prove $f$ is a reduction

text:
# Question
Title: Condition to prove $f$ is a reduction
A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq\_m B$.

But i'm confused if should I prove if :

1. $(x \in A \Rightarrow f(x) \in B )\land (f(x) \in B \Rightarrow x \in A)$

Or

2. $(x \in A \Rightarrow f(x) \in B ) \land(x \notin A \Rightarrow f(x) \notin B)$

in which circunstances because I've seen both in demonstration. Or maybe are they equivalent ?

For example, here is a solution to the empty string problem. But with $f$ such as, $f: \text{M accepts w} \to \text{M accepts } \epsilon \\ f(\langle M, \epsilon \rangle) = \langle M \rangle$, we can proove 1. Is it valid ?

# Answer
> 2 votes
It is called contraposition :

$f(x) \in B \Rightarrow x \in A$

is equivalent to

$x \notin A \Rightarrow f(x) \notin B$.

So, the two statements that you have seen are equivalent as well.

---
Tags: computability, reductions
---


# Question
Title: MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?
Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a Node that only has children Nodes with terminal game states ( and so on and so on )?

# Answer
> 1 votes
What you can do is to add a counter $t$ to each node, initially 0, indicating how many of its children are terminal.

When $t = c$ where $c$ is the number of children of a node, the node itself becomes terminal and increments the $t$ counter of its parent. Note that with this definition leaf nodes are automatically terminal, as they have no children, giving $0 = 0$.

As one more optimization, if a node has a terminal child that is losing, you can immediately mark its parent as terminal and winning.

Then, during selection you can ignore any terminal child.

---
Tags: trees, monte-carlo, minimax
---


# Question
Title: "Equality" problem in distributed computation
I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads).

I have seen as a side note in a few lower bound proofs, a reference that says the proof could be shorter using the "linear lower bound theorem for the Equality problem", but I couldn't find the statement or proof of this theorem.

I would like to know a few things:

* What exactly is this "Equality" problem? (how is it formulated?)
* Where can I find a proof for its lower bound? (or if the proof is short enough, I would be glad if you could add it here)

Thanks!

# Answer
> 3 votes
This is probably referring to the communication complexity of the function $f(x,y) = 1$ if $x=y$ and $f(x,y) = 0$ if $x \ne y$. See https://en.wikipedia.org/wiki/Communication\_complexity#Example:\_%7F'%22%60UNIQ--postMath-00000031-QINU%60%22'%7F for the formulation and a proof of the lower bound.

---
Tags: graphs, distributed-systems, lower-bounds
---


# Question
Title: How to prove a language isn't necessarily regular?
Assuming we have a regular language $L$, how can we prove that $L'= \\{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\\}$ isn't necessarily regular.

So far I can't come up with much for how to solve this. I was thinking we could solve this by either generating an example where $L'$ isn't regular or we could use the pumping-lemma, but I'm unsure how to get started. This was the hardest one in my set of practice problems.

# Answer
> 1 votes
If we take $L = \\{a^n \mid n \in \mathbb{N}\\}$, then $L' = \\{a^{2n} \mid n \in \mathbb{N}\\}$, which is a perfectly fine regular language. Or even more trival, we could observe that $\emptyset' = \emptyset$.

As such, it does not hold that $L'$ is never regular for a regular language $L$. This means that answering the question will involve constructing a **particular** language $L$ for which you can prove that $L'$ is not regular (and such a proof could use the pumping lemma).

As a heuristic for how to attempt this, I would first look at some typical examples of non-regular languages, and try to find a way to express them as $L'$ for some regular language. If I don't succeed with that, I'd attempt to built $L$ by simultaneously ensuring that $L$ itself is regular, and by running the pumping lemma on $L'$ to prove that it is not.

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


title: Inverting an image, as a matrix

text:
# Question
Title: Inverting an image, as a matrix
I am curious about something pretty simple, though I have never heard, read and more sadly seen any example of it. Take any image, represent it as a matrix, invert the matrix (assuming the inverse exists) and represent it as an image again. This in some sense visualizes the process of inverting a matrix. It would be pretty easy to code this, but before doing that I just wanted to ask if anybody has examples at hand or can say anything about this. Thanks!

# Answer
> 2 votes
I tried it on square grayscale images myself (just hoping they would be invertible, which was always the case (not much luck involved here, since invertible matrices lie dense)). I added a few examples so you can judge the inverses yourself. Their precise look of course depends on the particular normalization (I used cv2.normalize and also normalized manually by

as done here (I used this to create the LaTeX expression)).

Moreover, I ran this procedure on all test/cat images from CIFAR-10. You can find the results here. Notice that actually a lot of these 32x32 images were (as a matrix) not invertible.

As was asked for by user *fiveclubs*, here are the normalized inverses of the normalized inverses. They are nowhere near their originals.

Dolphin inverse of inverse:

Painting inverse of inverse:

Tower inverse of inverse:

---
Tags: image-processing, matrices
---


# Question
Title: Is it possible to do face recognition with just the eyes?
Assuming the input photo is focused on a person's face, if the person is wearing a surgical mask, most face recognition software fail to identify the subject's face.

Most facial landmark models are trained to identify at least the eyes and the tip of the nose (for example, dlib's 5 point landmark).

Is it possible to construct a model that is trained to identify a face based on only the eyes?

# Answer
> -1 votes
Recognising the right face is not the problem. Reliably rejecting the wrong face is.

---
Tags: machine-learning, artificial-intelligence, facial-recognition
---


# Question
Title: Why is 2s complement of 000 equal to 111, but 9s complement of 000 is not 888?
I'm pretty confused so I hope I don't mix up the different terms here.

1. The two's complement representation of decimal `0` is simply `000`
2. The two's complement of `000` is `111`

* I imagine that complementing a number is equivalent to flipping bits in binary
3. The nine's complement of `000` is `999`

* This is what confuses me. Are two's complement and nine's complement similar (except for the base change obviously)?
    * If they are, then I'd expect the nine's complement of `000` to be `888` because `8` is the biggest digit in radix `9` and therefore the complement operation would assign the highest digit (`8`) to the lowest value input (`0`) \[I imagine a folding from the center\]

Obviously this is totally wrong but I'm not sure which part I've misunderstood.

# Answer
> 32 votes
You are very confused due what is simply poor terminology, to be honest. Both your statements 2 and 3 are false due to the same misunderstanding.

For each base $b$ there are *two* mainstream variants of the 'complement', the radix complement and the diminished radix complement.

The two most common bases in computer science are base $2$ and base $10$. Confusingly, the definitions usually used are:

* one's complement: the diminished radix complement of base $2$
* two's complement: the radix complement of base $2$
* nine's complement: the diminished radix complement of base $10$ (**not** $9$!)
* ten's complement: the radix complement of base $10$.

# Answer
> 12 votes
The two's complement of 000 is 000. It is formed by complementing all bits and adding 1 to the result. The one's complement of 000 is indeed 111, but it is not used in computing.

The ten's complement of 000 is 000. It is formed by complementing all digits and adding 1 to the result. The nine's complement of 000 is indeed 999.

I suggest thoroughly reading the Wikipedia article on Two's complement.

---

What is behind two's complement?

The goal of two's complement is to come up with a negation operation $N(x)$ so that $x - y = x + N(y)$. The idea is that if all integers have width $w$, then all computation is implicitly done modulo $2^w$, and so $x - y = x + 2^w - y$. Now $2^w - y = (2^w-1-y)+1$. The binary expansion of $2^w-1$ consists of $w$ many $1$s, and so $2^w-1-y$ is the same as complementing $y$. That's why we compute the two's complement by complementing all bits and adding $1$.

Ten's complement works in the same way: $x - y = x + 10^w - y$, and $10^w - y = (10^w-1-y)+1$. Now $10^w-1$ consists of $w$ many $9$'s, and so $10^w-1-y$ corresponds to complementing all digits. Therefore ten's complement is formed by complementing all digits and adding $1$.

# Answer
> 1 votes
The position of the apostrophe matters.

If the number is used in the singular possessive form, as with "two's complement", one forms the complement by subtracting from the value one would get if one multiplied the base by what would, in unsigned form, be the place value of the most significant digit. So to take an eight-bit two's-complement of a number, because the most significant bit of an unsigned 8-bit number would be 128, one takes the quantity (two times 128) and subtracts the number from it.

If the number is used in the plural possessive form, as with "ones' complement" or "nines' complement", one subtracts from the value one would get if one replaced all of the digits with the indicated value (which should be one smaller than the base).

Thus, twos'-complement form (as distinct from two's-complement form) would be a means of representing base 3 values where an 8-bit negative number would be formed by subtracting the positive value from 22222222.

Although it's not uncommon for people to write "one's complement" when they really mean "ones' complement", or "twos' complement" when they mean "two's complement", putting the apostrophe in the write place and recognizing its distinction will make clear the distinction between the two general kinds of complement.

---
Tags: number-formats
---


# Question
Title: Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs?
Many times, I've wished to plug in my backup hard disks into my PC without the risk of any of the data being deleted, overwritten, or modified in any manner. Purely for "inspection" and copying over certain files from it.

But, unlike on the old floppies, there's just no hardware switch anywhere to enable "read-only" mode, or "write-protected mode". Why?

This very simple, mechanical thing was a thing back then, but later, "we" decided that it was unnecessary?

# Answer
> 5 votes
I'm not entirely sure that this question is on topic, but nonetheless, I suspect it has a simple answer.

Physical write protection mechanisms predate floppy disks. At my school holiday job in the 1980s, my desk had a drawer full of write rings for reels of 9 track tape. If the ring is in place, you can write to the tape.

There are certainly flash devices with physical write protection mechanisms. Many older USB drives have them. Memory Stick and SD both have a write protection lock. You can see it on the left-hand side of an SD card.

*Micro* SD cards don't have them because there's no way to effectively make them "micro". And I suspect that's the main reason why they went out of vogue. Once it became unimportant for one removable medium, many of the rest followerd.

The history of storage is about maximising speed, and minimising size and price. Adding a write protection lock adds to both size and price when devices are very small.

In addition, moving parts wear out faster than devices with no moving parts. Unlike disks or tape, flash memory has no moving parts by default. Adding a write protection lock means adding a moving part, which effectively shortens its usable life.

---
Tags: security, storage
---


# Question
Title: Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good
Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. However, suppose that I can check a partial specification to see if there are any words consistent with it. By partial specification I mean an assignment of some letters to some positions, with the others free to vary. E.g. "is there a word that starts with "HO" and ends with "Y" (but has any of the 2^26 configurations of third and fourth letter)?

An obvious algorithm would be to formulate it as a 26-tree, and traverse it depth-first, stopping once a pattern was deemed not "good" (e.g. as far as I'm aware there are no five letter words in English that start with "AAA", so we can skip checking "AAAAA", "AAAAB", ..., "AAAZZ").

Is it possible to do any better (average, worst case)? How about under additional assumptions on the distribution of letters (any such learning would need to be part of the algorithm, since my actual problem is not about natural language)? As another view on the second question: what sorts of heuristics are helpful?

# Answer
`If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations.` $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently efficient.

If we are talking about words of a sufficiently small length, then you can just precompute the answer in advance. I.e. word `cut` will be in an answer for masks `___`, `c__`, `_u_`, `cu_`, etc. For words of length at most 5, it'll result in $\le 2^5 \cdot10^5$ memory, which is of order of few MBs.

If the length is big, then you can split the mask into two parts. For each part, we find all the answers, and then intersect them. For example, we treat mask `a_b_c_d_e_` as an intersection of `a_b_c|_____` and `_____|_d_e_`. For both submasks, we find the set of words containing this submask, and then intersect them. If the final answer is small, then, hopefully, the result for at least one of these submasks will be small. You can also try to select the positions to include into each submask randomly.

For even bigger lengths, you can split the mask into more than $2$ parts. However, you can probably use that there are not many very large words and simply enumerate them all.
> 1 votes

# Answer
The following paper considers your task in the general case:

Partial-Match Retrieval Algorithms. Ronald L. Rivest. SIAM Journal Computing, vol 5 no 1, March 1976.

It yields a data structure with a running time that is slightly better than enumerating all words in the dictionary and checking each to see if it meets the conditions.
> 0 votes

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


# Question
Title: On efficiency analysis of randomized divide-and-conquer median find
I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort. Here as per book terminology $S$ denotes array of integers, $v$ is pivot, $S\_{L}$ and $S\_{R}$ are left and right side of pivot element.

*To distinguish between lucky and unlucky choices of $v$, we will call $v$ good if it lies within the 25th to 75th percentile of the array that it is chosen from. We like these choices of $v$ because they ensure that the sub lists $S\_{L}$ and $S\_{R}$ have size at most three-fourths that of $S$ (do you see why?), so that the array shrinks substantially. Fortunately, good $v$’s are abundant: half the elements of any list must fall between the 25th to 75th percentile!*

In one of the interview it was asked to me up till what range this median finding gives average running time of $n$. i.e. Favourable range of selection is within 25 to 75 percentile. But up to what extent we can reduce this and still have average running time of $n$

My approach was to write recurrence relation and then from the height of the tree comment on average running time, but I doubt is it a correct way to have answer? Also it might not provide tighter bounds.

It will be helpful if someone can also suggest what mathematical tool/technique will be useful for this kind of analysis.

# Answer
> 1 votes
There's no need to do any calculation. There is absolutely nothing special about the numbers 25 and 75.

If $0 \< \alpha \< \beta \< 1$ and you are promised that the median is between the $\alpha$'th percentile and the $\beta$'th percentile, then the running time of the algorithm will be linear. Indeed, if $\gamma = \min(\alpha,1-\beta)$, the length reduces by a factor of at least $1-\gamma$ in each recursive call, so the total running time will be proportional to at most $$ n \sum\_{i=0}^\infty (1-\gamma)^i. $$ Even without computing the sum, we can tell that in converges, so we get a bound of $O(n)$. If we compute the sum, we get the dependence on $\gamma$: $$ \frac{n}{\gamma}. $$

This sort of behavior always occurs when we reduce a problem to a subproblem which is smaller by a constant factor bounded away from 1. Once you know that, you don't need to do any calculations.

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


# Question
Title: Recurrence relations and the Master Theorem
Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation:

```
T(n) = 99T(n/100) + log(n!)

```

I'm trying to learn about algorithms, but I'm not really comfortable with logarithms(haven't studied in school yet), so I'd really appreciate a bit of help. Thanks.

# Answer
We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$

Let $c=\log\_{100} 99 \< 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.

This is tight because $\Omega(n \log n)$ is also a lower bound since: $$ T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n). $$

To summarize, you have $T(n) = \Theta(n \log n)$.
> 1 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Meaning of Free (Arbitrary Abstract Algebra Term)
I'm currently learning abstract algebra and the word free appears (free monoid, free vector space) throughout different literatures. Is there a general (and simple) definition of the word (and possibly examples in functional programming) or is it merely a highly overloaded word? Many Thanks!

# Answer
> 2 votes
Yes, and in fact there is even a general notion of an algebraic theory, and thus algebraic object. An algebraic theory consists of:

* a sort
* constants and function symbols
* algebraic axioms, that is universally quantified sentences which may contain equality, but no other logical symbols (ie. $\exists,\vee,\to,\neg$)

It is worth noting that the theory of fields is not algebraic, thus there are no free fields.

So the theory of monoids $\mathcal M$ has a sort $M$, constant $e : M$, function symbol $\mu:G\times G\to G$, and axioms

* $\forall x.\mu(x,e)=x$
* $\forall x.\mu(e,x)=x$
* $\forall x,y,z.\mu(\mu(x,y),z)=\mu(x,\mu(y,z))$

In general, given an algebraic theory $T$ we may consider the set of terms in this theory. Categorically, a free algebra for $T$ is the initial object in the category of algebras for $T$. The standard way to construct the free algebra is to take the *term model* for $T$, that is the underlying set of the free algebra is the set of terms of $T$ modulo the equivalence relation generated by the axioms of $T$.

So what we mean by a free structure in the theory $T$ generated by the set $B$, is to consider a free algebra for the theory $T\_B$ containing an additional constant symbol for each element of $B$.

This description is concrete but a bit complicated. There is a much simpler but more abstract construction using the theory of monads, because an algebraic theory corresponds precisely to a monad.

---

An example for monoids in a functional programming language could look as follows, by interpreting the theory of monoids as a monad:

```
type 'a mon =
| Id
| Bin of 'a mon * 'a mon
| Var of 'a

let return (x : 'a) : 'a mon = Var x

let rec bind (x : 'a mon) (f : 'a -> 'b mon) : 'b mon =
match x with
| Id -> Id
| Bin (s,t) -> Bin (bind s f, bind t f)
| Var u -> f u

let rec eq (a_eq : 'a -> 'a -> bool) (s : 'a mon) (t : 'a mon) : bool =
match (s,t) with
| (Bin (Id,u), v) | (Bin (u,Id), v) | (u, Bin (Id,v)) | (u, Bin (v,Id)) -> eq u v
| (Bin (Bin (u1,u2),u3), v) -> eq (Bin u1, Bin (u2,u3)) v
| (u, Bin (Bin (v1,v2),v3)) -> eq u (Bin v1, Bin (v2,v3))
| (Id,Id) -> true
| (Bin (u1,v1), Bin (u2,v2)) -> (eq u1 u2) && (eq v1 v2)
| (Var x, Var y) -> a_eq x y
| _ -> false

type two = A | B

let two_eq x y : bool =
match (x,y) with
| (A,A) | (B,B) -> true
| _ -> false

```

Then the type `two mon` with relation `eq two_eq` gives the free monoid on two elements.

The function `return : two -> two mon` gives us the two generators `return A` and `return B`.

The function `bind : two mon -> (two -> 'b mon) -> 'b mon` tells us that a map from the free monoid on two elements to another (in this case free) monoid is uniquely determined by what the elements of `two` are mapped to.

---
Tags: functional-programming, category-theory, algebra
---


# Question
Title: Distance transform with variable "impedance"
The distance transform gives the distance of each pixel in a mask to the nearest zero.

E.g. lets take the Taxicab distance transform:

```
input       distance
1 1 0       2 1 0
1 1 1   ->  3 2 1
1 1 0       2 1 0

```

I'm looking for a generalized distance transform where each each element in the mask also has a "weight" or "impedance" quantifying "how much it costs to step into this square". Weight would be undefined for zeros.

```
input     weight      distance
1 1 0     0 2 X        2 2 0
1 1 1  ,  3 2 3   ->   4 2 3
1 1 0     1 0 X        1 0 0

```

My questions are:

* Is there a name for this transform?
* Can it be done in O(N) like the traditional distance transform?
* Is there a nice way to generalize this to euclidian distance?

# Answer
I don't know whether there is a name for the transform you want but it can be computed in time $\tilde{O}(N)$ where $N$ is the number of entries of the matrix, assuming that the weights are non-negative.

Let the dimensions of the input matrices be $n$ and $m$. Call $A$, $W$, and $D$ the matrix with the pixel data, the weights, and the distances in output, respectively. Assume for simplicity that $W\[i,j\]=0$ whenever $A\[i,j\]=0$.

Create a directed graph $G = (V,E)$ where $V = \\{s\\} \cup \\{1, \dots, n\\} \times \\{1, \dots, m\\}$ and $E$ contains all edges $(s, (i,j) )$ for which $A\[i, j\]=0$ and and edge $( (i,j), (i',j') )$ with weight $W\[i',j'\]$ for each pair of vertices $(i,j)$ and $(i', j')$ that satisfy $|i-i'|+|j-j'|=1$.

The distance $d(i,j)$ from $s$ to $(i,j)$ in $G$ is exactly the distance you are looking for, i.e., $D\[i,j\] = d(i,j)$.

To compute all values $d(i,j)$ it suffices to run any single-source shortest-path algorithm from $s$ on $G$. Using Dijkstra's algorithm the time required is $O(|E| + |V| \log |V|) = O(N \log N)$. Faster algorithms might be possible if you have additional assumptions about the weights. For example, if they are bounded by a constant then $O(N)$ time suffices.
> 1 votes

---
Tags: algorithms, weighted-graphs, computer-vision
---