# Question
Title: Which case of the master theorem is this recurrence?
I have a question about the following recurrence relation:

$$T(n) = 27 \cdot T\left(\frac n 3\right ) + n^3 \log n$$

Using the master theorem, will this be

* $T(n) = \Theta(n^3)$, or
* $T(n) = \Theta(n^3 \log \log n)$?

# Answer
If a recurrence relation is of the form

$$ T(n)= aT \left( \frac{n}{b} \right) + {n^k}(\log n)^p $$

then, as per the Master Theorem, we have *six conditions* depending on value of $a,b,k$ and $p$

* If $\log\_b a\>k$ : Answer is $\Theta(n^{\log\_b a})$
* If $\log\_b a=k$ and $p\>1$ : Answer is $\Theta({n^k}({\log n})^{p+1})$
* If $\log\_b a=k$ and $p=1$ : Answer is $\Theta({n^k}\log\log n)$
* If $\log\_b a=k$ and $p\<1$ : Answer is $\Theta(n^k)$
* If $\log\_b a\<k$ and $p \geq 0$ : Answer is $\Theta({n^k}({\log n})^p)$
* If $\log\_b a\<k$ and $p \< 0$ : Answer is $\Theta({n^k})$

In any problem, our main motive is to find $a,b,k$ and $p$.

For the problem with

* $a=27$
* $b=3$
* $k=3$
* $p=1$,

$\log\_3 27 = 3$, so $\log\_b a = k$, and since $p=1$, the answer is $\Theta({n^k}\log\log n)$

$$\Theta({n^3}\log\log n)$$
> 1 votes

# Answer
Quick check:

$$\Theta(n^3)=27\\,\Theta\left(\frac{n^3}{27}\right)+n^3\log\log n$$

does not hold.
> 0 votes

---
Tags: recurrence-relation
---


title: How is pipelining possible?

text:
# Question
Title: How is pipelining possible?
As far as I understand pipelining is a way to excecute a instruction every clock cycle. It is a process performed on single cores. My question is how does the control unit handle this, at some point the control unit will have to store results from a completed instruction while simultaneously decode or fetch a new instruction.

To my understanding a core can have a couple of ALUs but only 1 control unit.

# Answer
The design of CPU control is not very well explained in textbooks, and this is partly because it's highly variable, but also because it's not very interesting from a computer science point of view, as opposed to an engineering point of view. There are lots of ways to do it, such designing a control component as a state machine and using traditional sequential circuit design (or whatever Verilog outputs), to ad hoc bus arbitration, to microcode.

As ratchet freak rightly pointed out, CPU control tends to be decentralised for timing reasons if nothing else. And so, yes, even today, microcode is a common implementation technique for at least part of the control system; the overall control of a core might be RISC, but the control of some specific pipelined unit might use microcode if it's more convenient.

There is an interesting paper on the AMD Jaguar FPU which goes into a little detail as to how the control was designed. The FPU was designed as a coprocessor (which already means it doesn't share master control with the rest of the core), and uses state machines for various functional units communicating with a more central control.

For another take on CPU control, where all decisions are local, you could look at something like the counterflow pipeline.
> 2 votes

# Answer
The control unit is split between the pipeline stages.

Typical is that there is the front-end which fetches the instruction and decodes what it needs to do. This decoded instruction is sent to the scheduler which then tells the execution units what needs to happen.

The passing of information between stages itself can happen in a few ways. The most conceptually simple way is using a D-latch register, the first stage calculates its output and sets the input of a D-latch register and on the next clock cycle the output of the latch will change to what the previous stage output and keep it stable for the duration of the clock cycle even as the previous stage prepares the next cycle's output.
> 2 votes

# Answer
A not completely outdated processor which has at least pipelining won't have a simple "control unit", but various units in different places that control things locally.

For example if you have four pipeline stages, then the second stage will decide whether it is ready to accept fresh data from stage 1; stage 1 will check whether stage 2 is ready *and* whether it has completed a task and if both is the case then push that data to stage 2. Stage 3 and 4 will do the same. So decisions are distributed.
> 1 votes

---
Tags: cpu
---


title: Clique vs Complete Graph

text:
# Question
Title: Clique vs Complete Graph
Is there a difference between a complete graph and a clique topology? As far as I understand, both refer to graphs in which every possible edge between any two vertices is present. Is there a subtle difference between these two concepts?

# Answer
> 18 votes
A complete graph is a graph with every possible edge; a clique is a graph or subgraph with every possible edge. That is, one might say that a graph "contains a clique" but it's much less common to say that it "contains a complete graph".

# Answer
> 1 votes
A clique is an induced subgraph that is itself complete graph.
What's an induced subgraph?
Ans: Given a graph, we pick a set of vertices and construct a subgraph. But now if we also select all edges that were incident on the selected set of vertices in the original graph, then we construct an induced subgraph. If this induced subgraph has an edge between all vertex pairs then its is complete.
So I think every complete graph can be thought of as an induced subgraph of some larger graph and hence every complete graph can be considered as a clique.

# Answer
> 0 votes
From \[1, page 5, Notation and terminology\]:

> A graph is complete if all vertices are joined by an arrow or a line. A subset is complete if it induces a complete subgraph. A complete subset that is maximal (with respect to set inclusion) is called a clique.

So, in addition to what was described above, \[1\] says that a clique needs to be maximal.

\[1\] S. L. Lauritzen. Graphical Models. Oxford University Press, New York, NY, 1996.

---
Tags: graphs, terminology
---


title: Max RAM capacity on modern cpus

text:
# Question
Title: Max RAM capacity on modern cpus
I am wondering why modern consumer cpu usually has 128GB memory limit when server cpu supports terabytes. 128GB is really not that much.

Do they really can't handle more RAM? How wide is their address bus?

Is it possible to put more RAM if motherboard handles it?

-- Edit --

I think that my question is simple, but let me clarify it.

As we know theoretical limit of address space for 64bit is very large. I know that currently no one supports it (both on software and hardware). Windows x64 supports at least 2TiB, but it works with virtual memory so it doesn't have to be RAM only. On the other hand wikipedia states that virtual and physical address space uses 48 bits which is 256TiB of RAM.

Looking at the numbers MMU is able to translate at least 2TiB from virtual to physical space so my question is: "Why Intel/AMD states in the spacification that processor supports only 128GB of RAM?" Is it limited by design in hardware or artificialy to force people to buy more expensive cpus with larger limits?

# Answer
> 1 votes
There is no fundamental reason. It's simply an engineering decision, an implementation detail. If you want 1TB of RAM, you buy a server system that can handle 1TB of RAM, not a desktop system that can only handle 32GB.

The limitation is more likely to be in the memory controllers which generate the electrical signals to talk to the memory chips, not in the memory management unit. More chips means more signals, more complex decoding, and also stronger drive current needed to make the signal reach all the chips. Servers often use "registered ECC" where each RAM stick has a "register" which acts as a signal booster.

The same memory management unit (or a very similar unit) is used on the 1TB systems and the 32GB systems - so the same software can run on both units

---
Tags: computer-architecture, cpu, memory-hardware
---


# Question
Title: Find the smallest difference between two numbers in a DS in O(1) time
I got an assignment to create a new data structure, with the following rules:

1. Init - O(1).
2. Insert x - O(log$\_2$n).
3. Delete x - O(log$\_2$n).
4. Search for x- O(log$\_2$n).
5. Find max difference between two values in the DS - O(1).
6. Find min difference between two values in the DS - O(1).

I've outlined the basics of the structure to look somewhat like an array/arryaList in which I can complete the tasks using heap-like methods, and that way I'll be able to complete 1-4 in the times given.

Regarding 5 - I need to return the difference between the maxVal and minVal of the array, so it'll be the first number (arr\[0\]) and I'll change the leaves to be so that the max is the last value (a\[n-1\]), and then I'll be in O(1).

**Regarding 6, and this is where I'm stuck** \- how can I find the smallest difference between two values in O(1) time? I don't know of any methods that accomplish the task in O(1)...

Thank you!

# Answer
Use an AVL tree with each node having three additional entries $\min,\\; \max$, and $\text{closest\_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the time of insertion and deletion, these values will be updated (Note that only $O(\log(n))$ node updates are needed per insert/delete operation). Now, this data structure represents your required data structure.

N.B. For a node $i,$ following relation holds. $i$.closest\_pair = closest( \[ ($i$.left,$i$), ($i$,$i$.right), $i$.left.closest\_pair, $i$.right.closest\_pair \] )
> 4 votes

# Answer
I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes:

* the minimum difference between two leaves in the subtree;
* the minimum and maximum values of a leaf in the subtree.

This can yield the wanted complexity:

1. init is an empty tree
2. inserting $x$ is first done in the usual way in $(a,b)$-trees, then you need to update all ancestors of the leaf containing $x$. Since each internal node has at most $b$ children, updating a node is done in constant time. Since each internal node has at least $a$ children, $x$ has $\mathcal{O}(\log n)$ ancestors. Note that the minimum difference can either be the minimum difference in a child, or the difference between the maximum and the minimum of two consecutive children ;
3. deleting is done in a similar way ;
4. searching is done the usual way in $(a,b)$-trees ;
5. and 6. are done in $\mathcal{O}(1)$ using the information stored at the root of the tree.

Actually, I think this can also be done with any kind of balanced binary search tree, storing the same kind of information:

* the min of a node $N(l, x, r)$ is either the min of $l$ or $x$ if $l$ is empty (and it is similar for the max);
* the min difference of $N(l, x, r)$ is one of the following:
    + the min difference of $l$;
    + the min difference of $r$;
    + the difference between $x$ and the maximum of $l$;
    + the difference between the minimum of $r$ and $x$.
> 1 votes

# Answer
I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations.

A possible data structure consists of an AVL tree $T$ plus a priority queue $H$ that supports insertions, deletions, and lookup of the minimum in time $O(\log n)$, $O(\log n)$, and $O(1)$ (respectively). The tree $T$ stores your collection and also keeps track of the minimum element $m$ and the maximum element $M$ in it. The priority queue $H$ stores all the differences between adjacent elements in the sorted version of the collection, and is allowed to contain multiple copies of the same value ($H$ can be implement using a min-heap and suitably managing pointers to elements to allow for fast deletions, or using another AVL tree).

The operations are implemented as follows:

* Init: create an empty tree $T$ and an empty priority queue $H$.
* Search $x$: search for $x$ in $T$ as usual.
* Insert $x$: insert $x$ in $T$ as usual. Update $m$ and $M$ by searching for the minimum and maximum element in $T$. Find the successor $y$ of $x$ in $T$ (if any). If $y$ exists add $y-x$ to $H$. Find the predecessor $z$ of $x$ in $T$ (if any). If $z$ exists add $x-z$ to $H$. If both $y$ and $z$ exist, delete $y-z$ from $H$.
* Delete $x$: delete $x$ from $T$ as usual. Update $m$ and $M$ by searching for the minimum and maximum element in $T$. Find the successor $y$ of $x$ in $T$ (if any). If $y$ exists delete $y-x$ from $H$. Find the predecessor $z$ of $x$ in $T$ (if any). If $z$ exists delete $x-z$ from $H$. If both $y$ and $z$ exist, add $y-z$ to $H$.
* Find max difference between two values: return $M-m$.
* Find min difference between two values in the dataset. Return the minimum in $H$.
> 1 votes

---
Tags: time-complexity, data-structures, runtime-analysis, binary-trees, heaps
---


title: Which z should I pick?

text:
# Question
Title: Which z should I pick?
I'm currently trying to show that the language $L\_2=\\{0^n \text{ } | \text{ } n=2^k, k\geq 0\\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find any regular expressions or DFA for it). I know all the steps that I need to go through, but I am having a very hard time figuring out which specific $z\in L\_2$ I need to use. I tried using $z=0^{2n}=0^{2^{k+1}}$ and $z^{2^n}$, but I had no luck.

Do you think I'm doing something wrong and using the wrong z's or are the above two okay to work with, but I'm just not comprehending it?

# Answer
We want to show that the language $L\_2 = \\{0^n: n=2^k, k \ge 0\\}$ is nonregular. By way of contradiction, suppose $L\_2$ is regular. Let $p$ be the pumping length. Let $z = 0^{2^p}$. Then, $z \in L\_2$ and $|z| \ge p$. Let $z=abc$ be a partition of $z$ such satisfying $|ab| \le p, |b| \ge 1$. Observe that $2^p \< |abbc| \le 2^p + p \< 2^p + 2^p = 2^{p+1}$, whence $abbc \notin L\_2$, a contradiction.
> 0 votes

# Answer
If $n$ is the pumping length and $m = 2^{\left\lceil \log\_2 n\right\rceil}$ ($m$ is the smallest power of $2$ greater than $n$), then $z = 0^m$ should do the trick. You need to show that if $z = uvw$ is the pumping decompositon, then one of $uw$ or $uv^2w$ is not in $L\_2$.
> 0 votes

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


# Question
Title: If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
For a language $\mathcal{L}$ over an alphabet $\Sigma$, define

$$\mathcal{SW(L)} := \\{ y ∈ Σ^∗ \mid \exists x \in Σ^\* \text{ such that } xyx \in \mathcal{L}\\}$$

How can I prove that if $\mathcal{L}$ is regular, then $\mathcal{SW(L)}$ is also regular?

# Answer
Take a DFA $(Q,\Sigma,\delta,q\_0,F)$ accepting $\mathcal{L}$. We can associate each word $x \in \Sigma^\*$ with a function $\delta\_x\colon Q \to Q$ given by $\delta\_x(q) = \delta(q,x)$. In other words, if the DFA is at state $q$ and it reads the word $x$, then it reaches state $\delta\_x(q)$. Let $\Delta = \\{ \delta\_x : x \in \Sigma^\* \\}$.

A word $y$ is in $\mathcal{SW}(\mathcal{L})$ if there exists $x \in \Sigma^\*$ such that $(\delta\_x \circ \delta\_y \circ \delta\_x)(q\_0) \in F$. Hence in order to determine whether $y \in \mathcal{SW}(\mathcal{L})$, it suffices to maintain $\delta\_y$, which can be done using a DFA whose set of states is $Q^Q$. I leave the rest of the details to you.
> 4 votes

# Answer
**Idea:** Suppose we have an NFA $(Q, \Sigma, \Delta, I, F)$ for $\mathcal{L}$. To build an NFA for $\text{SW}(\mathcal{L})$, our plan is to make a separate copy of the states of the NFA for each candidate start state $q$, where that machine reads in $y$ and checks whether it is possible for some $x$ to (i) get from an initial state $I$ to the candidate start state $q$ on $x$, (ii) get from $q$ to $q'$ on $y$, *and* (iii) read in the same string $x$ to get from $q'$ to an accepting state in $F$. Formally, the states of the new NFA are $Q \times Q$ (one copy of $Q$ for each possible start state $q \in Q$), and our new NFA is $$ (Q \times Q, \Sigma, \Delta', \\{(q, q) \mid q \in Q\\}, F') $$ where $F'$ is defined formally as $$ F' = \\{(q, q') \in Q \times Q \mid \exists x: q \in \Delta(I, x) \text{ and } \Delta(q', x) \cap F \ne \varnothing. $$

Note that the set $F'$ is a finite set -- we can just enumerate all the pairs in $Q \times Q$ and determine whether they are in $F'$ or not.

The definition of $\Delta'$ will be straightforward as it is the same for each copy of the original automaton.

Then we have to carefully argue two things (left as an exercise):

1. If $w \in \text{SW}(\mathcal{L})$, then there is an accepting run of the new automaton on $w$.
2. If there is an accepting run of the new automaton on $w$, then $w \in \text{SW}(\mathcal{L})$.
> 3 votes

# Answer
If $L$ is a language of $A^\*$ and $u, v$ are words, let $$ u^{-1}Lv^{-1} = \\{ x \in A^\* \mid uxv \in L \\} $$ It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is regular and the set $\\{u^{-1}Lv^{-1} \mid u, v \in A^\*\\}$ is finite. In particular, the subset $\\{u^{-1}Lu^{-1} \mid u \in A^\*\\}$ is finite. Now observe that $$ SW(L) = \bigcup\_{u \in A^\*} u^{-1}Lu^{-1} $$ to conclude that $SW(L)$ is regular.
> 2 votes

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


# Question
Title: A little confusion with Big Theta time complexity
I came across one Big Theta expression:

Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function f(n) execution time must lie between c1*g(n) (f(n) is greater than this function) and c2*g(n)(f(n) is smaller than this function) for some input size n greater than n'. And if I take the input size (n') as 1 than n^2 is 1 & n^3 is 1. c1 and c2 can be real constants. taking c1 as 1/2 and c2 as 2 then as per Big theta it should 2 \>1\>1/2.. and as per me this holds true while in reality the above statement stands to be false

# Answer
> 0 votes
"for some input size $n$ greater than $n'$" is wrong. The correct statement is "for *all* input sizes $n$ greater than $n'$".

Obviously,

$$\frac{n^3}2\le n^2\le 2n^3,$$

which is equivalent to

$$\frac12\le n\le 2,$$ cannot hold for unbounded $n$.

---

More generally,

$$\frac1{c\_2}\le n\le\frac1{c\_1}$$ is incompatible with $$n\>n'.$$

---

If you think of it a little, the condition "for some $n$" would be a nonsense, because if you take *any* $f,g,n'$ and *some* $n\>n'$, then

$$c\_1:=\frac{f(n)}{2\\,g(n)},c\_2:=\frac{2\\,f(n)}{g(n)}$$ always makes

$$c\_1\\,g(n)\le f(n)\le c\_2\\,g(n)$$ and $\color{red}{f(n)\in\Theta(g(n))}$.

# Answer
> 2 votes
If $f(n) \in O(g(n))$ and $g(n) \in O(f(n))$ then $f(n) \in \Theta(g(n))$, otherwise $f(n) \not\in \Theta(g(n))$.

$n^2 \in O(n^3)$ but $n^3 \not\in O(n^2)$ so $n^2 \not\in \Theta(n^3)$.

It works analogously to regular numbers. If $x \leq y$ and $y \leq x$ then $x=y$, otherwise $x \neq y$.

The error in your thinking is that $f(n) \in \Theta(g(n))$ is true only if $c\_1g(n) \< f(n) \< c\_2g(n)$ for all $n$ greater than some $n'$, not just a single example.

---
Tags: complexity-theory, time-complexity, asymptotics, big-o-notation
---


# Question
Title: Multi Objective Optimization Using Only Single Objective Optimization Algorithms
Let's say there is a single objective optimization problem SP (e.g. a linear program) and an optimization algorithm SA for it (e.g. simplex). Then applying SA to SP yields an optimal solution `s=SA(SP)`.

Now let's assume there is a multi objective optimization problem MP (e.g. a linear program with two linear objectives) but there is no access to a multi objective optimization algorithm to compute the (Pareto-optimal) solutions (front).

One option is of course to linearise the MP to turn it into a SP, basically the result is a weighted sum (in the example of two terms) but this obviously does not result in all Pareto-optimal solutions but it totally depends on the chosen weights.

Is there any way to iteratively apply the single objective algorithm SA to the multi objective MP to mimic a multi objective optimization algorithm MA?

# Answer
Actually, using a weighted sum *does* find all Pareto-optimal solutions.

Let your two objective functions be $f\_1,f\_2$. Define a single objective function

$$f(x) = \alpha f\_1(x) + (1-\alpha) f\_2(x),$$

where $\alpha$ is a constant. If you sweep $\alpha$ over all possible values in $\[0,1\]$ and, for each such $\alpha$, solve the single-objective optimization problem (minimizing $f$), then the set of solutions you obtain includes all Pareto-optimal solutions to the original multi-objective optimization problem.
> 1 votes

---
Tags: optimization
---


# Question
Title: Why is there a 'true' statement as precondition in the following loop invariant
> Precondition: true
> int i = 0;
> while (i \< a.length && a\[i\] != x) {
> i++;
> }
> Postcondition: (∀ j : 0 ≤ j \< i : a\[j\] ≠ x) ⋀ (i = a.length ∨ a\[i\] = x) }

As I read it, the program has no precondition to be established, thus the precondition is always true? Is it like an indicator: "This program has no precondition"?

# Answer
The program does have a precondition: `true`. Which means that it is fulfilled, regardless the state variables.

The annotation would still be correct with a stronger precondition, such as `a.length > 0`. `true`cannot be weakened, so it is the weakest precondition.
> 2 votes

---
Tags: loop-invariants
---


# Question
Title: Find a subsequence with fastest time for specific distance
I have two arrays.

```
seconds = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ..., 2680]

totalMeters =  [0, 3.2, 7.1, 10.6, 14.1, 17.9, 21.5, 24.2, 27.8, 32.5, 36.9, ..., 5000]

```

The `totalMeters` array is the total meters that I have run at this specific point of time. The sampling is 2 seconds.

I would like to find where in the array is the fastest 100 meters I have run, as well as its time.

# Answer
You cannot generally get time for **exactly** $100$ meters with this data. The better approach would be to search for the longest run within some multiple of $2$ seconds.

**Find the longest distance run in $2\cdot k$ seconds:**

* Set desired `k`.
* Set `i = 0` and `j = k-1`.
* Set `currentSum = maxSum = totalMeters[j]`.
* While `j < totalMeters.length - 1` do
    + `i++; j++;`
    + `currentSum = totalMeters[j] - totalMeters[i]`
    + if `currentSum > maxSum` then `maxSum = currentSum`

This should also give you an idea how to build other similar algorithms for this problem, if you don't change your approach.
> 1 votes

# Answer
Here is an $O(n)$ two-finger algorithm for the problem in Python:

```
from random import random
from sys import exit

n = 500
vels = [1 + 10*random() for _ in range(n)]
i = 0
j = 0
d = 0
mv = 0
while j < n:
    # Scan until d >= 100
    while d < 100 and j < n:
        d += vels[j]
        j += 1
    # Flush extra.
    while d - vels[i] >= 100:
        d -= vels[i]
        i += 1
    v = d / (j - i)
    if v > mv:
        print('best: %.2fm in %ds %.2fm/s.' % (d, (j - i), v))
        mv = v
    d -= vels[i]
    i += 1

```

`vels` contains velocities for each time interval and is easily computed from the `totalMeters` array. You can also adapt the code to work on 2-seconds-intervals instead of 1-seconds-interval.
> 1 votes

---
Tags: algorithms, search-algorithms, arrays, mathematical-programming
---


# Question
Title: finite automata that accepts integers divided by 3?
I have found in a book the example of how to make a FA that accepts those numbers that are divisible by 3, that means that n mod 3=0. In the example the author used the binary representation of the number to be evaluated. The resulting automata is:

The states represent the probable remainders, that could be 0, 1 or 2. Some additional explanation is in the following part:

I have tried the following examples to test this automata:

* If I try to do 6 mod 3 that will result in 0, so I will go from the initial state (upper part of the figure) to the acceptance state, that is because the modulus is 0.
* If I try 5 mod 3 or 101 mod 11 that would be 2, which in binary is 10. If I want to apply again 2 mod 3. I will end up again with 2 and not reaching an acceptance state. From the upper part I followed the path 1--state 1--0--state 2. What happens there? it just stays in that state 2?

I just do not have a clear picture of how to test this FA for example with an input of 81 mod 3, does it make partial divisions? When I try to follow it I end up in an acceptance state even before finishing to evaluate the remainder.

Any help?

# Answer
> 5 votes
I believe you are misunderstanding the way finite automata work. A finite automaton accepts a *language*, i.e. a subset of the finite strings of a given finite alphabet. In your case, the accepted language is the set of strings made of $0$ and $1$ which encode a well-formed multiple of $3$.

Given a string, imagine placing a token on the initial state, then for each character of the string, left to right, move the token along the transition labelled $0$ or $1$, according to which character you read.

After having consumed each character of the string, the automaton accepts if and only if the token is on one of the accepting states.

Considering your automaton, intuitively, the top three states determine whether the string encodes a well-formed number (i.e. a string that starts with $1$ or is exactly $0$, for instance, $1000$ is valid, but $000$ isn't) while the bottom three determine whether or not it is divisible by $3$ using elementary number theory.

# Answer
> 2 votes
We want to design a **Deterministic Finite Automaton (DFA)** that **accepts** Binary Representation of Integers which are divisible by 3.

> Now, by **accept**, in layman terms, we can say that when we are done with scanning string, we should be in one of the multiple possible Final States.
>
> More Formally, Let $w = a\_1a\_2…a\_n$ be a string over the alphabet $Σ$. The automaton accepts the string $w$ if a **sequence of states**, $r\_0, r\_1, …, r\_n$, exists in $Q$ with the following conditions:
>
> 1. $r\_0 = q\_0$
> 2. $r\_{i+1} = δ(r\_i, a\_{i+1})$, for $i = 0, …, n − 1$
> 3. $r\_n \in F$
>
> In brief, A word $w=a\_{1}a\_{2}...a\_{n}\in \Sigma ^{\*}$ is an accepting word for the automaton if $\overline {\delta }(q\_{0},w)\in F$, that is, if after consuming the whole string $w$, the machine is in an accept state.

**Approach :** Essentially, we need to divide the Binary Representation of Integer by 3, and track the remainder. If after consuming/scanning \[From Left to Right\] the entire string, remainder is Zero, then we should end up in Final State, and if remainder isn't zero we should be in Non-Final States.

Now, DFA is defined by Quintuple$/5$-Tuple $(Q,q\_0,F,\Sigma,\delta)$. We will obtain these five components step-by-step.

---

**$Q$ : Finite Set of States**
We need to track remainder. On dividing any integer by $3$, we can get remainder as $0,1$ or $2$. Hence, we will have Three States $Z, V$ and $T$ respectively. $$Q=\\{Z,V,T\\}$$ If after scanning certain *part* of Binary String, we are in state $Z$, this means that integer defined from *Left to this part* will give remainder $Z$ero when divided by $3$. Similarly, $V$ for remainder $1$, and $T$ for remainder $2$.
$\hspace{6cm}$

Now, we can write these three states by Euclidean Division Algorithm as

> $Z=3m\\V=3m+1\\T=3m+2\\ \text{where } m \in \mathbb{Z} \text{ (Set of Integers)}$

---

**$q\_0$ : an initial/start state $q\_0\in Q$**
Now, start state can be thought in terms of empty string $(\varepsilon)$. An $\varepsilon$ directly gets into $q\_0$.
Now, what remainder does $\varepsilon$ gives when divided by $3$?

> Now, we can append as many $0s$ in left hand side of a *Binary Number*. In the similar fashion, we can append $\varepsilon$ in left hand side of a *Binary String*. Thus, *$\varepsilon$ in left* can be thought of as *0*. And $0$ when divided by $3$ gives remainder $0$. Hence, $\varepsilon$ should end in State $Z$. But $\varepsilon$ ends up in $q\_0$.

Thus, starting state should be

> $$q\_0=Z$$ $\hspace{6cm}$

---

$F :$ **a set of accept states,** $F\subseteq Q$
Now we want all strings which are divisible by $3$, **or** which gives remainder $0$ when divided by $3$, **or** which after complete scanning should end up in state $Z$, and gets accepted. Hence, $$F=\\{Z\\}$$
$\hspace{8cm}$

---

$\Sigma :$ **Alphabet (a finite set of input symbols)**
Since we are scanning/reading a Binary String. Hence,

> $$\Sigma=\\{0,1\\}$$

---

$\delta :$ **Transition Function** $(δ : Q × Σ → Q)$
Now this $\delta$ tells us that if we are in state $x\in Q$ and next input to be scanned is $y\in \Sigma$, then at which state $z\in Q$ should we go.

> In context of this problem, if the string upto this point gives remainder $1/V$ when divided by $3$, and if we append $1$ to string, then what remainder will resultant string give.

Now, this can be analyzed by observing *how magnitude of a binary string changes on appending 0 and 1*.

> In Decimal (Base-$10$), if we add/append $0$, then magnitude gets multiplied by

> $10$
> **Example :** $64$, on appending $0$ it becomes $640$

> Also, if we append $7$ to decimal, then

> Magnitude gets multiplied by $10$, and then we add $7$ to multiplied magnitude.

> In **Binary (Base-$2$),** if we **add/append $0$**, then magnitude gets multiplied by

> $2$ (The Positional Weight of each Bit get multiplied by $2$)
> **Example :** $(1010)\_2$ *\[which is $(10)\_{10}$\]*, on appending $0$ it becomes $(10100)\_2$ *\[which is $(20)\_{10}$\]*

> Similarly, In **Binary**, if we **append $1$**, then

> Magnitude gets multiplied by $2$, and then we add $1$.
> **Example :** $(10)\_2$ *\[which is $(2)\_{10}$\]*, on appending $1$ it becomes $(101)\_2$ *\[which is $(5)\_{10}$\]*

> Thus, we can say that for Binary String $x$,
>
> * $x0=2|x|$
> * $x1=2|x|+1$

We will use these relation to analyze three States

* **Any string in $Z$ can be written as $3m$**

+ On $0$, it becomes $2(3m)$, which is $3(2m)$, nothing but state $Z$.
    + On $1$, it becomes $2(3m)+1$, which is $3(2m)+1$, that is $V$.
    *\[This can be read as if a Binary String is presently divisible by $3$, and we append $1$, then resultant string will give remainder as $1$\]*
    $\hspace{3cm}$
* **Any string in $V$ can be written as $3m+1$**

+ On $0$, it becomes $2(3m+1)=6m+2$, which is $3(2m)+2$, state $T$.
    + On $1$, it becomes $2(3m+1)+1=6m+3$, which is $3(2m+1)$, state $Z$.
    *\[If $m\in \mathbb{Z}$ (Set of Integers), then $(2m+1)\in \mathbb{Z}$\]*
    $\hspace{3cm}$
* **Any string in $T$ can be written as $3m+2$**

+ On $0$, it becomes $2(3m+2)=6m+4$, which is $3(2m+1)+1$, state $V$.
    + On $1$, it becomes $2(3m+2)+1=6m+5$, which is $3(2m+1)+2$, state $T$.
    $\hspace{3cm}$

---

**Hence, the final DFA combining Everything**

---

**To Test $6$**, which in binary is $110$

* On $Z$, scan $1$, go to $V$.
* On $V$, scan $1$, go to $Z$.
* On $Z$, scan $0$, go to $Z$.

String Consumed. We are in $Z\in F$. Hence $110$ accepted.

**To Test $5$**, which in binary is $101$

* On $Z$, scan $1$, go to $V$.
* On $V$, scan $0$, go to $T$.
* On $T$, scan $1$, go to $T$.

String Consumed. We are in $T\notin F$. Hence $101$ rejected.

**To Test $81$**, which in binary is $1010001$

* On $Z$, scan $1$, go to $V$.
* On $V$, scan $0$, go to $T$.
* On $T$, scan $1$, go to $T$.
* On $T$, scan $0$, go to $V$.
* On $V$, scan $0$, go to $V$.
* On $V$, scan $0$, go to $V$.
* On $V$, scan $1$, go to $Z$.

String Consumed. We are in $Z\in F$. Hence $1010001$ accepted.

---

# Answer
> 0 votes
**Hint:**

If the remainders of $n$ by $3$ are $0, 1, 2$, then the remainders of $n$ followed by zero (i.e. $2n$) are $0, 2, 1$, and the remainders of $n$ followed by one (i.e. $2n+1$) are $1,0,2$.

This explains the transitions between the bottom states marked $0,1,2$.

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


# Question
Title: How many different boolean functions exist up to permutation of its $n$ variables
i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them all. But if you know the name of what i am searching for or have some strategy how i could approach this or tips for literature where i can read about it, that would also help.

My question is the following:

How many different boolean functions exist up to permutation of its $n$ variables. That is two functions $f$ and $g$ are considered the same if $$ g(x\_1,x\_2,\dots,x\_n) = f(x\_{\sigma^{-1}(1)},x\_{\sigma^{-1}(2)},\dots,x\_{\sigma^{-1}(n)}) \quad \text{for some} \quad \sigma \in S\_n $$ For example, i want to treat $A \wedge \neg B$ as if it was equal to $\neg A \wedge B$, and therefore count it only once.

Edit: I also want to treat $A \wedge \neg B$ as if it was equal to $\neg B \wedge A$. That means, i want to treat functions as equal if they are

1. semantically equal
2. semantically different but there exists a permutation of variables that makes them semantically equal

# Answer
You are looking for A003180.

The related sequence A003181 counts functions depending on all variables.

Often one allows further operations: negation of inputs, and negation of the output. The corresponding sequence is then A000370.
> 2 votes

---
Tags: boolean-algebra, permutations, boolean-complexity
---


# Question
Title: Why is $A_{TM}$ not mapping reducible to $E_{TM}$?
$A\_{TM}= \\{ \langle M,w\rangle \mid M$ is a TM that accepts $w\\}$

$E\_{TM}= \\{ \langle M\rangle \mid L(M) = \emptyset \\}$

The standard proof for the undecidability of $E\_{TM}$ is given in this question, right?. Doesn't this automatically create a mapping reduction $f$ from $A\_{TM}$ to $E\_{TM}$ ? Whenever $w \in A\_{TM}, f(w) \in E\_{TM} $ obviously. The other way: $ f(w) \in E\_{TM} \Rightarrow w \in A\_{TM} $ seems true, although I suspect that's where the fundamental restriction lies. Can someone clarify this?

The proof given for $A\_{TM}$ not being Turing reducible to $E\_{TM}$ is the following:

> Suppose for a contradiction that $A\_{TM}$ $≤\_{m}$ $E\_{TM}$ via reduction $f$. This means that $w ∈ A\_{TM} \iff f(w) ∈ E\_{TM} $, which is equivalent to saying $w \notin A\_{TM} \iff f(w) \notin E\_{TM} $. Therefore, using the same reduction function $f$, we have that $\overline{A\_{TM}} \le\_m \overline{E\_{TM}} $. However, $\overline{E\_{TM}}$ is Turing-recognizable and $\overline{A\_{TM}}$ is not Turing-recognizable.

I understand the proof above I think. It seems I am misunderstanding something fundamental about mapping reductions, or that I am confused about some step in the reduction from $A\_{TM}$ to $E\_{TM}$ in the standard proof.

# Answer
Given $\langle M,w\rangle\in A\_{TM}$, the mapping $f$ in the question maps $\langle M,w\rangle$ to $\langle M\_1\rangle$, where Turing machine $M\_1$ accepts input $x$ iff $x$ is $w$ and $M$ accepts $w$.

$f$ is NOT a mapping reduction from $A\_{TM}$ to $E\_{TM}$, since $M\_1$ accepts $w$, i.e., $f(\langle M,w\rangle )=\langle M\_1\rangle\not\in E\_{TM}$ when $\langle M,w\rangle \in A\_{TM}$.

On the other hand, $f$ is a mapping reduction from $A\_{TM}$ to $\overline{E\_{TM}}$, if we let $f$ map any string not of the form $\langle M,w\rangle$ to $\langle M\_{\text{loop}}\rangle$, where $M\_{\text{loop}}$ is a Turing machine that runs forever for all inputs.

---

The reason why $A\_{TM}$ is not mapping reducible to $E\_{TM}$ is given by the proof in the question.
> 4 votes

# Answer
**Note:** This answer was given *before* the definition of $A\_{TM}$ was added to the question and was assuming the following definition instead $A\_{TM} = \\{ \langle T \rangle \mid L(T) = \Sigma^\* \\}$.

$E\_{TM}$ is mapping reducible to $A\_{TM}$. Here is a sketch of a possible reduction:

Given (the description of) a Turing Machine $T$, compute (the description of) a Turing Machine $T'$ that behaves as follows:

* $T'$ takes two inputs, a word $w$ and a non-negative integer $n$.
* $T'$ simulates $T$ with input $w$ for $n$ steps.
* If the simulation of $T$ accepts within $n$ steps, $T'$ rejects.
* Otherwise, $T'$ accepts.

If $T \in E\_{TM}$ then for every word $w$ and every integer $n$, the simulation of $T(w)$ either rejects or does not halt within $n$ steps, causing $T'$ to accept. Therefore $T' \in A\_{TM}$.

If $T \not\in E\_{TM}$, then there is some word $w$ for which $T(w)$ accepts. Let $n$ be the number of steps taken by $T(w)$ to accept. The Turing Machine $T'$ with inputs $w$ and $n$ rejects. Therefore $T \not\in A\_{TM}$.
> 1 votes

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


# Question
Title: Cosine distance in a space, and cheating?
I read an example of using cosine distance in RGB space, and it pointed out that (eg.) dark red and light red have a cosine distance (CD) of zero because CD only gives you the angle between vectors and doesn't consider length. Fair enough. I wondered if a way to fix this was by making it a four dimensional problem by adding the vector length VL, calculated in the normal Euclidean way way.

But this seems to be cheating because the R,G,B components are independent of each other whereas the length component VL is clearly a function of R, G and B. In some sense I'm not adding new information (or am I?)

I can't help feeling this shouldn't work, but it seems to as far as I can tell. Am I mistaken?

This is not about Cosine Vs. Euclidean distance but what the implications are of adding the latter to the former.

(I'm starting to wonder if, as CD is blind to vector length VL, I'm simply making VL visible to it by explicitly adding it back in as an extra dimension. That said, VL is entirely a function of the other dimensions so something doesn't feel right).

# Answer
> 1 votes
To compare colors, the cosine distance is interesting as it cancels the effect of light intensity (so yes, dark red and light red are both two reds).

If you don't want this effect, the Euclidean distance (in RGB space) is fine.

---
Tags: machine-learning, euclidean-distance
---


# Question
Title: A Quine–McCluskey variant for conjunctive normal form?
There is the Quine–McCluskey algorithm for finding a *minimal* expression of a boolean expression in *dis*-junctive normal form. Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?

Is there an equivalent algorithm for *con*-junctive normal form? Not necessarily looking for something efficient as the results will be cached, just if such an algorithm exists.

# Answer
> 2 votes
I'm not 100% sure about this but here's what I think:

> Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?

If you negate the expression and then apply De Morgan's laws you get a CNF for the negation of the original expression. I think it's also minimal though I don't have a rigorous proof.

> Is there an equivalent algorithm for con-junctive normal form?

You can use Quine–McCluskey with a minor modification based on the previous idea. First negate the expression. Then apply Quine–McCluskey to get DNF for the negation. Then apply negation again and De Morgan's laws to get the original expression in CNF form.

Another way to look at this is that normal Quine–McCluskey basically combines 1s in the truth table of the expression to get minterms and a minimal DNF. With the modification I gave the algorithm essentially combines 0s to get a CNF (which I think is also minimal).

---
Tags: propositional-logic
---


# Question
Title: Is the set of languages satisfying the pumping lemma closed under concatenation?
Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation?

I couldn’t prove it or find a counterexample.

# Answer
> 5 votes
Suppose that $L\_1$ satisfies the pumping lemma: there exists $p\_1$ such that every word $w \in L\_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p\_1$, $y \neq \epsilon$, and $xy^iz \in L\_1$ for all $i \geq 0$. Similarly, suppose that $L\_2$ satisfies the pumping lemma, with constant $p\_2$.

I claim that $L = L\_1L\_2$ satisfies the pumping lemma with constant $p = p\_1 + p\_2$. Suppose we are given a word $w = w\_1w\_2 \in L$ of length at least $p$, where $w\_1 \in L\_1$ and $w\_2 \in L\_2$. Then either $|w\_1| \geq p\_1$ or $|w\_2| \geq p\_2$. You take it from here.

---
Tags: regular-languages, pumping-lemma, closure-properties
---


# Question
Title: Are reversed reverse preorder traversals equivalent to a postorder traversal?
I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse preorder traversal (because it is considerably easier to implement iteratively), and then reversing the output. To my further surprise, I could not find a single counterexample to these conjectures, which I will state clearly:

* Conjecture 1: The post-order traversal of a tree $T$ is equivalent to the reversed reverse pre-order traversal of $T$.
* Conjecture 2: The reverse post-order traversal of a tree $T$ is equivalent to the reversed pre-order traversal of $T$.

I thought about this plenty, and came up with an extremely informal justification for this: LRN = reverse(NRL) and RLN = reverse(NLR). Not sure if this is purely coincidental or not. Can anybody either provide a proof of either conjecture? Furthermore, if true, do these conjectures extend to any arbitrary graph/digraph?

# Answer
> 6 votes
This can be proven by induction on trees. I give details on the conjecture 1 here.

* It is clearly true for the empty tree and for leaves;
* Suppose it is true for trees $l$ and $r$. Consider $t$ a node with $l$ and $r$ as left and right children, and $x$ as root. Then, if we denote $Rpre(t)$ the reverse pre-order of $t$, $post(t)$ the post-order of $t$, and $\overline{seq}$ the reversed sequence of $seq$, we get:

$$Rpre(t) = x\cdot Rpre(r)\cdot Rpre(l) = x\cdot \overline{post(r)}\cdot \overline{post(l)} = \overline{post(l)\cdot post(r)\cdot x} = \overline{post(t)}$$

The conjecture 2 is proven in the same way.

I doubt there is an equivalent property for graphs because children are unordered in graphs (but I may be wrong…)

# Answer
> 5 votes
Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation.

The postorder traversal of a binary tree can be found following an Euler traversal of the tree. That is, we follow the path along the tree starting at the root, counterclockwise, noting the vertex at its last visit (postorder) which is represented by the green dot below.

If we look at the reverse pre-order, we follow the same Euler tour, but clockwise (as we visit the right subtree before the left one) and we note each vertex at its first visit: which is now also the green dot.

Hence the reverse pre-order is the post-order in reverse.

---
Tags: binary-trees, graph-traversal
---


# Question
Title: Does a constant time compression algorithm proves that P=NP?
Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP?

That is, an algorithm that doesn't rely on patterns/redundancy occurrence in data to work, but instead on some clever mathematical operations.

Such algorithm will be able to compress random data, but of course, not every data, since it will need to output the variables that the decompression part of it will run mathematical operations on to rebuild the original data.

Please try not be condescending in your answer. I'm a programmer too, but I'm aware I know little compared to most of you here.

I just want to know if such algorithm proves P=NP.

I'm not asking about the possibility of the algorithm, so try not to tell me especially in a condescending way it is impossible.

I'm very aware of the impossibility based on patterns/redundancy reliance for the current algorithms to work on.

I'm working on an alternative method that uses pure mathematics right now. No reliance on data redundancy. But I won't say I have the algorithm. Sometimes you thought you've had something but turns out it's just another mirage.

If it's really a practical and better alternative to the current ones, I will edit this post and post a link to it for you to review before I file a patent (1 year grace in the US after disclosure)

# Answer
Just to be clear question at hand is the following:

> Let $c$ be a constant. Does the existence of an algorithm that takes a string $x \in \\{0,1\\}^\*$ as input and outputs a string $f(x) \in \cup\_{i=0}^c \\{0,1\\}^c$ such that $f$ is invertible (i.e., there exists some function $f^{-1}$ such that $f^{-1}(f(x)) = x$ for every $x$) imply that $\mathsf{P}=\mathsf{NP}$?

Formally, the answer to your question is "yes" but you might find the argument unsatisfactory: since there can be no algorithm with the properties above, the question is equivalent to "is it true that $\mathsf{false}$ implies $\mathsf{P}=\mathsf{NP}$?", which is clearly true (see principle of explosion).

If you want a more direct proof you can reason as follows. Take any $\mathsf{NP}$-complete language $L$ and consider the language $L' \in \\{f(x) \mid x \in L\\}$. Since $f$ is injective, $|L| \le |L'| \< 2^{c+1}$ implying that $L$ is a finite language and hence it belongs to $\mathsf{P}$.
> 2 votes

---
Tags: complexity-theory, time-complexity, np-complete, polynomial-time, data-compression
---


# Question
Title: Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?
I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y HTTP3 REST calls. At the QUIC level, all of these streams are going over the same connection and are demultiplexed via a `go` hash map by Stream ID. This is working fine, but I was wondering about scaling; specifically the Web Transport streams are typically more latency sensitive than the REST API calls. More generally, I find that I want to prioritize the active streams that have sent the most data.

Focusing on the `go` hashmap that treats all keys equally, is there any hash table that prioritizes keys that get referenced the most? So if Stream N gets referenced 100K times and Stream M gets referenced 10 times, the hash algorithms checks for a match of N before M?

### Update

To clarify QUIC's connection/stream model more (and ignore crypto for now):

* A QUIC connection, ignoring crypto, can be thought of as a typical UDP connection. It is over this that QUIC Frames get passed.
* QUIC Streams act like TCP connections, data regarding a stream is passed over the connection in a QUIC Stream Frame with the Stream ID in the header.

So a QUIC connection allows for the passing of QUIC Frames, and both client and server must identify which frames belong to which streams (via Stream ID mapped to an internal context) and pass the data along. to local conversation handlers.

### Update #2

As stated in the comments by other users, implementing this very well may not be worth the overhead, but here is an unoptimized version of what I am talking about:

```

type WeightedMap []WeightedEntry

type WeightedEntry struct{
    refcount uint64
    Key int //streamID
    Value interface{} // basically a pointer in go
}

func (w *WeightedMap)Get(key int) (out interface{}){
    vm := *w
    for i := range vm{
       if vm[i] == key{
         vm[i].refcount++
         out = vm[i].Value
         break
       }
    }
    if out != nil{
      sort.SliceStable(wm, func(i, j int) bool {
          return wm[i].refcount > wm[i].refcount
      })
    }
}

```

A better version could at least greatly improve the Sort step by just looking at the entry in question and its neighbor with a higher index. Just wanted to convey a rough idea.

# Answer
> 1 votes
A hash table takes a key, calculates a hash value for the key, and maps the hash value to a sequence of indexes into the table. The mapping key -\> hash value is fixed at least while the hash table exists.

Usually the number of possible hash values is huge; it might be $2^{64}$ which means you won't have the same hash value twice in practice. But each hash produces a sequence of indexes, and many keys might use the same index.

Usually you keep the hash table substantially larger than the number of values stored, so if the indexes were random, you would find a key very often at the first index, quite often at the second index, rarely at the third or later index. So the number of indexes to check should be small anyway; otherwise you increase the table size. And skipping the wrong index is very fast: You store the hash key with the value in the hash table, so when you check index i, all you do is to compare the hash values which are stored in the table or just computed. This is very fast.

The things costing substantial effort are: 1. Calculate the hash value for the key to look up. 2. When an index with the right hash value is found, compare the keys. Everything else has minimal execution time, so there's very little need to improve the time for the keys used most often.

---
Tags: algorithms, search-algorithms, search-trees, hash-tables
---


# Question
Title: What does it mean to prove that a set of binary integers is regular?
I'm not exactly sure what this question is asking me to do:

> Show that the set of binary integers (given as strings over $\\{0, 1\\}$) that are divisible by $3$ is regular, by giving a DFA that recognizes it. Leading 0s are allowed. The empty string should be accepted. Briefly explain your answer.

Is this asking me to construct a DFA where the set of binary integers add up to be divisible or the number of elements is divisible?

I understand that by constructing the DFA I prove that it is regular.

# Answer
> 2 votes
The question asks you to construct a DFA for the language

$$L = \\{x \in \\{0,1\\}^\* : x \text{ is the binary representation of an integer that is divisible by three}\\}.$$

In other words, the DFA should accept a string if and only if this string is the binary representation of a number that is divisible by three.

# Answer
> 0 votes
Hint: Make three states, $q\_0, q\_1, q\_2$, representing the fact that in state $q\_i$ you have seen a string of 0s and 1s that, when interpreted as a binary number, represents a number with remainder of $k$ when divided by 3. For example, having read $\mathtt{00101}$, the FA would be in state $q\_2$, since the binary string $\mathtt{00101}$ corresponds to the decimal value 5, which has a remainder of 2 when divided by 3.

Now fill in the transitions: If, say we're in state $q\_2$ having read a string that corresponds to a number $n$, what state would the FA be on reading a $\mathtt{0}$? What happens when you add a zero to the right of the representation of $n$, going, say from $\mathtt{00101}$ to $\mathtt{001010}$? Use this idea to fill in all the transitions and then decide what the final state(s) should be.

# Answer
> 0 votes
The question want us to design a **Deterministic Finite Automaton (DFA)** that **accepts** Binary Representation of Integers that is divisible by 3.

> $\mathcal{L}=\\{x\in\\{0,1\\}^∗:x$ is the binary representation of an integer that is divisible by three$\\}$

> A word $w=a\_{1}a\_{2}...a\_{n}\in \Sigma ^{\*}$ is an accepting word for the automaton if $\overline {\delta }(q\_{0},w)\in F$, that is, if after consuming the whole string $w$, the machine is in an accept state.

**Approach :** We need to divide the Binary Representation of Integer by 3, and note the remainder. If after consuming/scanning \[From Left to Right\] the entire string, remainder is Zero, then we should end up in one of the Final States, else we should be in Non-Final States.

Now, DFA is defined by Quintuple$/5$-Tuple $(Q,F,q\_0,\Sigma,\delta)$. We will obtain these five components step-by-step.

---

**$Q$ : Finite Set of States**
We need to note remainder. On dividing any integer by $3$, we can get remainder as $0,1$ or $2$. Hence, we will have Three States $Z, V$ and $T$ respectively. $$Q=\\{Z,V,T\\}$$ If after scanning certain *part* of Binary String, we are in state $T$, this means that integer defined from *Left to this part* will give remainder $T$wo when divided by $3$. Similarly, $V$ for remainder $1$, and $Z$ for remainder $0$.
$\hspace{6cm}$

Now, we can write these three states (by Euclidean Division Algorithm) as

> $Z=3m\qquad V=3m+1\qquad T=3m+2\qquad$ where $m \in \mathbb{Z}$

---

$F :$ **a set of accept states,** $F\subseteq Q$
Now we want strings which are divisible by $3$, **or** which gives remainder $0$ when divided by $3$, **or** which after complete scanning should end up in state $Z$, and gets accepted. Hence, $$F=\\{Z\\}$$
$\hspace{8cm}$

---

**$q\_0$ : an initial/start state $q\_0\in Q$**
An Empty String $(\varepsilon)$ directly gets into $q\_0$. And $\varepsilon$ should get accepted. Thus $q\_0$ be one of the Final State. And since we have only one Final State. Hence,

> $$q\_0=Z$$ $\hspace{6cm}$

---

$\Sigma :$ **Alphabet (a finite set of input symbols)**
Since we are scanning/reading a Binary String. Hence,

> $$\Sigma=\\{0,1\\}$$

---

$\delta :$ **Transition Function** $(δ : Q × Σ → Q)$
Now this $\delta$ tells us that if we are in state $a\in Q$ and next input to be scanned is $b\in \Sigma$, then at which state $c\in Q$ should we go.

> In context of this problem, if the string upto this point gives remainder $1/V$ when divided by $3$, and if we append $1$ to string, then what remainder will resultant string give.

Now, this can be mathematically analyzed by observing *how magnitude of a binary string changes on appending 0 and 1*.

> In Decimal (Base-$10$), if we add/append $0$, then magnitude gets multiplied by

> $10$
> **Example :** $64$, on appending $0$ it becomes $640$

> Also, if we append $6$ to decimal, then

> Magnitude gets multiplied by $10$, and then we add $6$ to multiplied magnitude.

> In **Binary (Base-$2$),** if we **add/append $0$**, then magnitude gets multiplied by

> $2$ (The Positional Weight of each Bit get multiplied by $2$)
> **Example :** $(1010)\_2$ *\[which is $(10)\_{10}$\]*, on appending $0$ it becomes $(10100)\_2$ *\[which is $(20)\_{10}$\]*

> Similarly, In **Binary**, if we **append $1$**, then

> Magnitude gets multiplied by $2$, and then we add $1$.
> **Example :** $(10)\_2$ *\[which is $(2)\_{10}$\]*, on appending $1$ it becomes $(101)\_2$ *\[which is $(5)\_{10}$\]*

> Thus, we can say that for Binary String $x$,
>
> * $x0=2|x|$
> * $x1=2|x|+1$

We will use these relation to analyze three States

* **Any string in $Z$ can be written as $3m$**

+ On $0$, it becomes $2(3m)$, which is $3(2m)$, nothing but state $Z$.
    + On $1$, it becomes $2(3m)+1$, which is $3(2m)+1$, that is $V$.
    *\[This can be read as if a Binary String is presently divisible by $3$, and we append $1$, then resultant string will give remainder as $1$\]*
    $\hspace{3cm}$
* **Any string in $V$ can be written as $3m+1$**

+ On $0$, it becomes $2(3m+1)=6m+2$, which is $3(2m)+2$, state $T$.
    + On $1$, it becomes $2(3m+1)+1=6m+3$, which is $3(2m+1)$, state $Z$.
    *\[If $m\in \mathbb{Z}$, then $(2m+1)\in \mathbb{Z}$\]*
    $\hspace{3cm}$
* **Any string in $T$ can be written as $3m+2$**

+ On $0$, it becomes $2(3m+2)=6m+4$, which is $3(2m+1)+1$, state $V$.
    + On $1$, it becomes $2(3m+2)+1=6m+5$, which is $3(2m+1)+2$, state $T$.
    $\hspace{3cm}$

---

**Hence, the final DFA combining all Five Components is**

Since, we have constructed DFA. Hence, the language $\mathcal{L}$ is regular.

---

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


title: Time Complexity of ${n \choose k}$

text:
# Question
Title: Time Complexity of ${n \choose k}$
I want to know the time complexity of specifically calculating ${n \choose k}$ where it is defined as

$$ {n \choose k} = \frac{n!}{k!(n-k)!}. $$

If the factorial function is recursive $O(n)$:

```
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

```

then the time complexity would be $O(n + k + (n-k)) = O(2n)$? This seems counterintuitive as there are 2 inputs to $n \choose k$ but it seems like $O(2n)$ only considers one input yet $O(2n)$ has more definite proof to me as I could list out $O(n + k + (n-k)) = O(2n)$. I get that $O(2n)\propto O(n)$, that is not what I am looking for.

# Answer
> 2 votes
I'll assume $k\<n/2$, for simplicity (otherwise replace $k$ by $n-k$).

One way to calculate it is via

$${n \choose k} = {n (n-1)(n-2) \cdots (n-k+1) \over k!}.$$

This can be calculated using $2k$ multiplications. So, if we counted each multiplication/division/addition as $O(1)$ time, this would be $O(k)$ time.

However, that is misleading. The size of the numbers grows dramatically. So, if you want to compute this exactly (as a rational number), we need to operate on very large numbers, which takes more than $O(1)$ time. In particular, the numbers can grow as large as $n \lg k$ bits long, so each multiplication or division might take $O((n \lg k)^2)$ time \[\*\]. So, the running time might something like $O((n \lg k)^2 k)$ bit operations. If you are a bit cleverer about the order in which you do the multiplications and divisions (multiplying small numbers first, using a binary tree structure to minimize the number of large numbers you have to deal with) you can get this down to something like $O(k^2 \log n)$ bit operations.

---

Footnote \*: I am ignoring sub-quadratic multiplication algorithms. There are algorithms that are asymptotically faster, for very large numbers, but they tend to be only useful when the numbers are super-large, so for simplicity of analysis, I'm ignoring them.

---
Tags: time-complexity
---


title: Find $k$ shortest paths in linear time

text:
# Question
Title: Find $k$ shortest paths in linear time
Suppose given number $k$ and undirected unweighted graph $G=(V,E)$, also given two vertices $s$ and $t$. Can we find $k$ shortest paths between $s$ and $t$ in $O(n+m)$ without term $k$?

I read this link but I can't findout the answer of my question. I think this problem can't solve in polytime.

# Answer
> 1 votes
No. The output needs to be of length at least $k$, so you obviously need at least $k$ time steps even just to print the output.

To give yourself some intuition: imagine the case where $n=100$, $m=100$, and $k=$ a gazillion. Are you really expecting an efficient algorithm that takes only a few hundred steps for that case?

---
Tags: algorithms
---


# Question
Title: Exponential Time Hypothesis and the input size vs number of variables
According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$. The real input size in the worst case is $\Theta(n)$, therefore for an asymptotic analysis one can assume $n$ to be the input size. Such a formula can be bruteforced in time $o(2^n)$, but not in time $o(2^V)$.

In an extreme case one could have $V = O(\log n)$ which would produce a problem in $\mathsf P$ and, therefore, invalid for Exponential Time Hypothesis. Can one assume that a valid problem for Strong Exponential Time Hypothesis has $V=\Theta(poly(n))$ or even $V = \Theta(n)$?

# Answer
> 4 votes
ETH says that, for $s\_k = \inf \alpha$ such that k-sat can be solved in $2^{\alpha n}$, it holds that $s\_3 \> 0$.

The strong exponential time hypothesis (SETH) says that $\lim\limits\_{k \rightarrow \infty}s\_k = 1$. I think you mean the latter in your description.

Answering your question: The conjecture presents a lower-bound for a problem, meaning that no algorithm (in simple terms) solves all instances of $SAT$ much better than $O(2^{|V|})$\[1\]. However, in your question, you provided an example where a specific algorithm has a larger running time than this lower-bound for a specific class of instances.

On one hand, larger running time only makes a lower-bound stronger (it contradicts nothing). On the other side, even if you show that for some class of instances (there are surely many of them), the problem can be solved efficiently, this does not contradict the lower-bound since it is general and your algorithm has to solve SAT more efficiently on any given instance.

On a side note, the sparsification lemma \[Impagliazzo et al.\], used to show that SETH is stronger than ETH reduces an instance of SAT to many instances such that in each of them we have linear number of clauses in the number of variables. This might satisfy your curiosity since it shows that SETH also has implications on instances with linear bound on the number of clauses.

Some examples of classes of formulas that can be solved efficiently are CNF formulas whose primal-, dual- or incidence-graphs have bounded values of some width parameters (tree width / branch width / etc.)

---

\[1\]: This is equivalent to the CNF-SAT conjecture. SETH is a stronger hypothesis.

# Answer
> 1 votes
In their paper Impagliazzo and Paturi in Theorem 1 claim that ETH is equivalent to $\mathsf{SNP \not \subseteq SUBEXP}$.

Since complexity classes are defined on the input size and a formula on $o(n)$ variables is solvable in subexponential time, it follows that the number of variables has to be linear in the number of literals for ETH.

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


# Question
Title: Prove there is only one MST in a graph with distinct weights
> Let $G = (V, E)$ be an undirected, connected and weighted graph.
>
> Let also $(e\_{1},\ldots , e\_{|E|})$ be some sort of the edges of $G$.
>
> Let $w, w' \colon E\rightarrow \mathbb{R}$ such that: $$w(e\_{1})\<w(e\_{2})\< \dots \< w(e\_{|E|})$$ $$w'(e\_{1})\<w'(e\_{2})\< \dots \< w'(e\_{|E|})$$
>
> Prove that the two MST's resulting from the weights function are identical.
>
> Deduce that for every sort of the edges there is only one unique MST, meaning only one $T = \mathrm{MST}(e\_{1},\ldots , e\_{|E|})$.

My idea for the first part was to assume by the contradiction that there are $T\_{1}$ and $T\_{2}$ such that $T\_{1} \neq T\_{2}$, each for $w$ and $w'$. I wasn't able to come to a contradiction, so I thought maybe I should use Kruskal's algorithm.

Any help would be appreciated.

I realize the intuition but I can't formally write it.

# Answer
> 1 votes
Kruskal's algorithm goes over all edges in increasing order of weight. For each such edge, it adds it to the tree being build if it doesn't close a cycle.

As you can see, the outcome of the algorithm depends only on the relative order of the weights, not on their values.

Formally speaking (if the above informal argument isn't considered convincing enough), you can prove the claim that you're after by induction on the number of iterations of the main loop in Kruskal's algorithm. You show that an edge is added when the weights are $w$ iff it is added when the weights are $w'$.

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


# Question
Title: Formal mathematical resolution for Recurrence Relations
let's suppose we've got a simple Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$

At lesson we've resolved it, but I tried two other ways of resolution, and I would like to ask you if they're right and which, among all, is the most formal way to resolve it.

**Method 1**

Drawing the recurrence tree (whose each node has only one child), we see that its height is $n$ and each node receives as input $n-i$, where $i$ is its level. So each node costs $\Theta(n-i)$. Hence the total cost is $$T(n) = \sum\_{i=0}^{n-1}\Theta(n-i)$$

**Method 2**

We see that the cost of each node is $\Theta(n-i)$ which is a $\Theta(n)$, so the total cost is $$T(n) = \sum\_{i=0}^{n-1}\Theta(n)$$

Is what I did mathematically right? Even if in this example it looks trivial that it is right, then why when we have an algorithm that equally divides a problem in two equal-size subproblems (e.g. `mergesort`), the CLRS Book writes that each subproblem costs $\Theta(\frac{n}{2^i})$ but does not "simplify" it into $\Theta(n)$? So their final sum would be $\sum\_{i=0}^{h}\frac{n}{2^i}$ and not $\sum\_{i=0}^{h}\Theta(n)$ like I would do, since $\Theta(\frac{n}{2^i}) \in \Theta(n)$.

In this case it'd look like each node costs the same as its parent, which obviously can't be, but it is mathematically right.

**Method 3**

In *Method 2* we said that each node costs locally $\Theta(n)$, and $n$ is the value we call the first recursive call with. But when $n=1$, its cost is $1$, so we should write $$T(n) = 1+\sum\_{i=0}^{n-2}\Theta(n)$$

When $n=2$, its cost is $\Theta(2) = \Theta(1)$ and not $\Theta(n)$ (remember that this $n$ is the value of the first rec. call when we resolve the summation). But this would apply even when $n=3, n=4, ...$ So I'd write it as $$T(n) = \sum\_{i=0}^{k}\Theta(1) + \sum\_{i=1}^{n-k}\Theta(n)$$ meaning that there are a constant number of nodes that cost $\Theta(1)$ and the others cost depending on the value of $n$.

I do not know which one is the most formal way of resolving these relations. In all of these methods seem that there's something off, something not formal.

# Answer
Let me make the following suggestion: *get rid of asymptotic notation*.

Here is how to do that. Your recurrence relation is really the following: $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + f(n) & \text{otherwise}, \end{cases} $$ where $f(n) = \Theta(n)$. Since $f(n) = \Theta(n)$, there are $c,C,N \> 0$ such that $cn \leq f(n) \leq Cn$ for all $n \geq N$. If we assume that $f(n) \> 0$ for all $n$, then we can assume that $N = 1$ (otherwise, the following needs to be slightly modified). Now define a new recurrence relation, depending on a parameter $\gamma$: $$ T\_{\gamma}(n) = \begin{cases} 1 & \text{if } n = 1, \\ T\_\gamma(n-1) + \gamma n & \text{otherwise}. \end{cases} $$ A simple proof by induction shows that $$ T\_c(n) \leq T(n) \leq T\_C(n) $$ for all $n$. Hence it suffices to analyze $T\_\gamma(n)$. In fact, we can calculate $T\_\gamma(n)$ exactly: $$ T\_\gamma(n) = 1 + \sum\_{m=2}^n \gamma m = 1 + \gamma \frac{(n-1)(n+2)}{2}. $$ From here it is easy to deduce that $T(n) = \Theta(n^2)$.

I suggest now repeating your various methods, applying them directly to $T\_\gamma$. Check which of them still works in this more concrete setting. Of course, if a method doesn't seem to work for $T\_\gamma$, then in fact it didn't work already for the original recurrence $T$.
> 2 votes

# Answer
Formaly, for all $n\>N$,

$$T(n-1)+c\_0n\le T(n)\le T(n-1)+c\_1n$$

If we expand the right inequality, $$T(n)\le T(n-1)+c\_1n\le T(n-2)+c\_1n+c\_1(n-1)\le\cdots \le T(N)+c\_1\sum\_{i={N+1}}^ni\\ =T(N)+c\_1\frac{n^2+n-N^2-N}2.$$

We can repeat the reasoning with the left inequality. In the end, $T(n)=\Theta(n^2-n-N^2-N)=\Theta(n^2)$.
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: The average time complexity of linear search with weighted probability
Given array of numbers $A\[1..n\]$. We search for element $x$ with linear search. Also we know that, element $x$ occurs in $A$ and probability of $x$ be in second half of the array is $3$ times of probability $x$ be in first half. What is the time complexity of linear search in average case?

Because of $x$ is in $A$, let $p$ be probability $x$ be in first half, so $$p+3p=1$$ so $p=\frac{1}{4}.$

Also I define Random variable $X$ as follow:

$$ X\_i = \begin{cases} \frac{1}{4}& ,1\leq i\leq \frac{n}{2} \\ \frac{3}{4}& ,\frac{n}{2}\<i\leq n \end{cases} $$ Let $$X=X\_1+X\_2+\dots+X\_n.$$ Now the expected of $X$ is as follow

$$ E\[X\]=\frac{1}{2n}\sum\_{i=1}^{\frac{n}{2}}X\_i+\frac{3}{2n}\sum\_{i=\frac{n}{2}+1}^{n} X\_i $$ After solving above equality, $E\[X\]=\frac{10n+8}{16}$. But I think the answer is $\frac{5n}{8}$. What is my wrong?

# Answer
> 1 votes
We must assume $n$ even. As the average of an arithmetic progression is the average of the extreme members, the number of comparisons for the first half is $\dfrac{n+2}4$, and that for the second half is $\dfrac{3n+2}4$.

Then taking the weighted sum,

$$\dfrac{5n+4}8.$$

Anyway, we can spare the very last comparison because we know that the element is in the array and we must deduct $\dfrac3{4n}$.

---
Tags: algorithms
---


title: Set partitions into singletons or pairs

text:
# Question
Title: Set partitions into singletons or pairs
I am trying to build an algorithm to compute the partition of a set into singletons or pairs for a set of cardinality 16. I am doing it in MATLAB and came up with codes that either run forever or require more memory than available. Do you know any time and space efficient algorithm?

I have added my function below.

```
function out = partition2(n)

A000085 = [1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, 618884638912, 3257843882624, 17492190577600, 95680443760576, 532985208200576, 3020676745975552];
lenA000085 = length(A000085);
if n>length(A000085)
    error(['Cardinality of Y larger than ' num2str(lenA000085) ' not supported yet!']);
end

base = n+1;
lft = ones(1,n) * base.^(n-1:-1:0).';
rgt = (1:n) * base.^(n-1:-1:0).';
out = zeros(A000085(n),n);
cnt = 0;
m = ones(1,n-1)+1;
d = lft;
powers1 = base.^(1-n:0);
powers2 = base.^(n-1:-1:0).';
while d<=rgt
    bs = mod(floor(d.*powers1), base);

    vec = 1:n;
    ndx = vec(bs(2:end)>m);
    if isempty(ndx)
        k = 1;
        bad = false;
        while k<n && ~bad
            if sum(bs==k)>2
                bad = true;
            end
            k = k + 1;
        end

        if ~bad
            cnt = cnt + 1;
            out(cnt,:) = bs;
        end
        d = d + 1;
    else
        tmp = n-1:-1:1;
        d = d + base.^tmp(ndx);
        bsNew = mod(floor(d.*powers1), base);
        bsNew(ndx+1) = 1;
        d = bsNew * powers2;

        m = cummax(bsNew) + 1;
        m = m(1:end-1);

    end
end

```

# Answer
> 0 votes
Here is one way to generate all partitions of an input array $A$ into singletons and pairs:

1. Let $x$ be the first element of $A$.
2. Recursively generate all partitions of $A \setminus \\{x\\}$, and add $\\{x\\}$ to all of them.
3. Go over all elements $y \in A \setminus \\{x\\}$ (if any); for each one, recursively generate all partitions of $A \setminus \\{x,y\\}$, and add $\\{x,y\\}$ to all of them.

A naive python implementation generated all partitions of $1,\ldots,16$ in 18 minutes on my laptop.

---
Tags: partitions
---


# Question
Title: Envyless location using divide and conquer
We have a cake of length $n$ and we have two arrays $A$ and $B$ of size $n$. The two arrays have order like below. $A\[0\]\<A\[1\]\<\dots \<A\[n\]$, $B\[0\]\>B\[1\]\>\dots \>B\[n\]$. We define a envyless location as a cut in the cake where it satisfies $A\[i\]=B\[i\]$. For example, $A=\[1,2,3,4,5,6,7\]$ and $B=\[7,6,5,4,3,2,1\]$, $A\[3\]=B\[3\]=4$, therefore, cutting the cake at length 4 makes the cut envyless. If the algorithm finds an envyless location it returns it's location, and if the envyless location does not exist, it returns null. I am trying to use divide and conquer to solve this problem with worst-case runtime of $O(\log n)$.

I have tried the following procedure and failed. First, divide the cake in half. Find the mid point of the splitted cake and compare $A\[mid\]$ and $B\[mid\]$. If found, terminate and return the location. If not found, keep on dividing and comparing.
I expected this to run on $O(\log n)$ time but it cannot because for example, if $A=\[1,2,3,4,5,6\]$ and $B=\[20,11,9,8,7,6\]$, the envyless location is at location 6, and the algorithm needs to do $n$ comparison, making the algorithm to run at $O(n\log n)$.

Any help will be very helpful.

# Answer
If $A\[\text{mid}\] \< B\[\text{mid}\]$ then you can recurse on $A\[\text{mid}+1, \dots, n\]$ and $B\[\text{mid}+1, \dots,n\]$ since, if an envyless cut exists, it must be after location $mid$.

The situation $A\[\text{mid}\] \> B\[\text{mid}\]$ is symmetric and you can recurse on $A\[0, \dots, \text{mid}-1\]$ and $B\[0, \dots, \text{mid}-1\]$.

The resulting algorithm takes time $T(n) \le T(\lfloor n/2 \rfloor) + O(1)$, which has solution $T(n) = O(\log n)$.
> 1 votes

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: Optimal greedy algorithm solution for cell tower placement
Supose we have $n$ customers with interval that represent their range. For example, $\[1,8\], \[2,5\], \[4,6\], \[1,9\]$ for each customer. For a customer to have range coverage, a tower must be present within their range. For example, for customer $\[1,8\]$ to have coverage, a tower must be within range $\[1,8\]$. I need to make a greedy algorithm that will generate a list of tower locations that will cover all customers with the least number of towers. For the example above, the optimal solution will be location 4 or location 5 because only one tower at either location 4 or 5 will cover all customers. The algorithm should have a worst-case runtime of $O(n\log n)$.

I have tried the following method and failed. First, calcuate the length of each interval and make a tuple of (starting point, length) and add it to a array in assending order in respect to length. So, for the example above the list will look like $\[(4,2), (2,3), (1,7), (1,8)\]$. This will take $O(n)$ time to process. Second, I picked the customer with the smallest interval and tried to place a tower in the customer's interval. However, a problem rises, because greedy algorithms do not calcuate multiple options and then choose the optimal choice I have trouble of where to place the tower in the customer's interval. I have thought of three choices: at the very left, at the very right, at the middle. The middle, is statistically the most optimal one but not always correct because if the customer's interval is at the boundary and every other customer's interval starts at the very right point of the current customer's interval, the very right point is the right choice for this situation.

Any help for finding the optimal solution will be very helpful.

# Answer
Lexicography sort the list; i.e. Priority is based on the first and then second elements. For example $S\_1=(1,8), (1,9), (2,5), S\_4=(4,6)$.

Then, produce $\cap\_{k=1}^iS\_k$ where $\cap\_{k=1}^{i+1}S\_k=\emptyset$. Select from $\cap\_{k=1}^iS\_k$, delete $S\_1,...,S\_i$ and continue with the rest of the list.
> 2 votes

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


# Question
Title: Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B
I've been given the question in the title:

Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in it that the amount of lexicographic smaller string from A in the structure equals the amount of lexicographic larger string from B, in time complexity O(|Smax|) (the size of longest string in the structure).

I should solve it using simple trie trees. My idea was saving in every intersection in the tree the amount of leaves in the sub tree from group A and group B (two different variables).

But that doesn't seem to be enough because I wasn't able to build a search algorithm with this data that works within the time complexity, there are certain cases I cannot definitively choose whether to proceed from current intersection with letter x or letter x+1 because the difference between the smaller leaves in A and larger leaves in B is 1 and the string could exist in the sub tree of letter x or x+1 (depends on the inner order in these sub trees).

Would really appreciate any help with this.

# Answer
Your idea to use a trie is good. I think that what might do the trick is only to store additionnal information at each node: the number of strings of $A$ and of $B$ contained in the corresponding subtree.

This does not change the time complexity of usual operations on tries, you only need to adjust the numbers in the ancestors of the string you added/deleted.

Moreover, it allows you to search for "the middle string" when doing the required request: given a node $N(x, \[t\_1, t\_2, …, t\_k\])$, if we denote $a\_1,…, a\_k$ the number of strings of $A$ in $t\_1, …, t\_k$ and $b\_1, …, b\_k$ the number of strings of $B$ in those trees, then you want to continue the search in subtree $t\_i$ such that $\sum\limits\_{j = 1}^{i-1}a\_j \< \sum\limits\_{j = i}^{k}b\_j$ and $\sum\limits\_{j = 1}^{i}a\_j \geqslant \sum\limits\_{j = i+1}^{k}b\_j$.

Since the alphabet is of constant size, the overall operation is at most in the height of the trie, or similarly the maximum size of a string in the trie.

Note: I supposed here that children are ordered by their roots.
> 1 votes

---
Tags: trees, strings
---


# Question
Title: A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.

The proof I am familiar with states the following: we are given a non-deterministic turing machine $N$ for our language $A$. It is known that for inputs in $A$ that $N$ accepts by using $O\left( f \left( n \right)\right)$ space. I would like to construct a deterministic turing machine $M$ that accepts inputs from $A$ in $O\left( \left( f \left( n \right)\right) ^2 \right)$ space, and this will prove the correctness of the theorem.

Knowing that $s,t-Path$ is in $DSPACE\left( \left(\log{n} \right)^2\right)$, we define the (deterministic) turing machine $M$ to work the following way (on a given input $a$:

1. Construct the configuration graph for the computation of $N$ on $a$.
2. Run a space-efficient algorithm for $s,t-Path$, where $s$ is the initial configuration and $t$ is the accepting configuration (assume, w.l.o.g., only one accepting configuration exists. If not, adjust $N$ accordingly so it will hold).
3. If such a path was found, accept. Else, reject.

Phase (2) takes $O\left( \left(\log{n} \right)^2\right)$ space. But what about phase (1)? How Am I to construct the configuration graph, which has $\Theta \left( 2^{O\left( f \left( n \right) \right)} \right)$ vertices, in only $O\left( \left(\log{n} \right)^2\right)$ space?

I read that the graph can be built on the fly, but then - how do we check whether an edge exists? If the graph itself is not fully computed ahead of time, we must always call to $N$ to check what are the destination configurations from our current configuration. Now, this gets a bit tricky, as $N$ is not part of the input. Should we assume we can somehow approach it? Without taking time? Where is $N$ maintained? This takes space as well.

I am aware my question is not the main focus of the theorem, but its something that bugs me in this proof. Or are there better proofs? (Also, how can this small issue be better explained, in this proof?)

# Answer
**Lemma**: let $N$ be a deterministic Turing machine running in space $f(n)$. Then it is possible to know if there is a transition between two configurations (that both use space $\leqslant f(n)$) in space $\mathcal{O}(f(n))$.

**Proof**: Using alphabet $\\{0,1\\}$, a configuration can be encoded using the tape content, the position of the head and the state of the Turing machine. That means that there exists $\alpha \> 0$ such that there are at most $m \leqslant 2^{\alpha f(n)}$ configurations that use space $\leqslant f(n)$. Know given $i, j\leqslant m-1$, if you want to know if there is a transition between $i$ and $j$, you have to:

* write $i$ and $j$ (at most $\alpha f(n)$ bits);
* move the head to the right position (using a counter $\leq f(n)$);
* simulate all transitions from configuration $i$.

All this can indeed be done in space $\mathcal{O}(f(n))$.
> 2 votes

---
Tags: complexity-theory, turing-machines, space-complexity, nondeterminism
---


# Question
Title: Are all Scott-continuous functions computable?
A chain-complete partial order (equivalently, a pointed dcpo) is a set $D$ with a partial order $\leq$ such that all chains of $D$ have a supremum. The least upper bound ($\bigsqcup$) of the empty chain is the least element $\bot$ of the CCPO.

A function $f\colon M \to N$ is monotone if for all $a, b \in M$, the following holds: $$a \leq b \implies f(a) \leq f(b)$$

A function $f\colon M \to N$ between two CCPOs is Scott-continuous if it is monotone and for every chain $C$ of $M$, we have

$$f(\bigsqcup\_{c \in C} c) = \bigsqcup\_{m \in C} f(c)\\,.$$

Scott-continuous functions play an important part in defining denotational semantics of programs, and as is well-known in computing science, every Turing-computable function is Scott-continuous$^0$. Is the converse true? Is every Scott-continuous function computable?

---

0. See this question, from which I took and edited some definitions.

# Answer
$\newcommand{\TM}{T\\!M}$

Let $\TM$ be the set of Turing machines and $2 = \\{0,1\\}$.

The powerset of any set with $\leq$ equal to $\subseteq$ is a CCPO, its least upper bounds being the unions of the chains.

Take the function $f\colon P(\TM) \to P(\TM \times 2)$ that maps a set of Turing machines $S$ to $$\\{ (t, h) \mid t \in S \text{ and $h$ equals whether $t$ halts on empty input } \\}$$

The function $f$ is Scott-continuous $-$ it is defined pointwise, so it's monotonous and $$f(\bigcup\_{c \in C} c) = \bigcup\_{c \in C} f(c)\\,,$$ and therefore $$f(\bigsqcup\_{c \in C} c) = \bigsqcup\_{c \in C} f(c)\\,.$$

It is also obviously not computable.
> 2 votes

---
Tags: computability
---


# Question
Title: How does CPU determine Reserved Exponent cases?
Using IEEE 754 algorithm i assume, that it can be implemented in a branchless way.

But how does CPU determine special cases (Reserved Exponent values):

| Exponent | Significand | is |
| --- | --- | --- |
| 11111111 | 000000000... | Inf |
| 11111111 | 00000**1**000... | NaN |
| 00000000 | 000000000... | 0 |
| 00000000 | 00000**1**000... | Subnormal |

Without any tricks which i don't know / understand it should be expensive.

**EDIT**

It was too big for comment, so editing source question:

I'm currently reading ARM spec/documentation https://developer.arm.com/documentation/ddi0403/d/Application-Level-Architecture/Application-Level-Programmers--Model/The-optional-Floating-point-extension/Floating-point-data-types-and-arithmetic?lang=en#BEIBFIBJ and especially interesting part is `FPUnpack()` pseudocode. If i understand correctly, CPU doesn't have intrinsics / instructions for special cases, but the compiler, that produce machine code should consider to validate result from registers (FVP for old ones and NEON for new). The example i found from ARM team https://github.com/ARM-software/ComputeLibrary/blob/8f587de9214dbc3aee4ff4eeb2ede66747769b19/include/CL/cl\_half.h#L135. Am i right ?

**EDIT:**

Nope, i'm not right, according to this answer https://stackoverflow.com/questions/61646510/how-does-the-cpu-cast-a-floating-point-x87-i-think-value.
But it's still the question how does CPU registers handle special cases...

# Answer
> 2 votes
Not really. There are eight bits to check in two numbers usually to see there is a special case. For infinity/NaN you don’t need to do the normal operation anymore, so the rest is not time critical. More time critical is normalising the mantissa for a zero exponent.

But there are processors that assumed these cases are so rare that many can be handled by an interrupt (not directly in hardware, but by executing code).

---
Tags: cpu, floating-point
---


# Question
Title: Universal family of hash functions — dependent on table size?
> Given the following family of hash functions:
>
> $$ \mathbb{H} = \\{h\_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \\}, $$ where $m$ is the key size.
>
> Prove that $\mathbb{H}$ is not a universal family of hash functions.

So I got the following idea:

If $m = 12 $ then $H$ is not an universal family of hash functions. But is this enough or have I to prove it for every/random m?

This leads to the question: Is a universal family of hash functions dependent on the hash table size?

# Answer
> 2 votes
Ultimately this is a question for the person who posed the exercise. They need to specify if they are asking "Is H non-universal for all m?" or if they are asking "Is H universal for all m?"

If they're asking the former, then you proving H is non-universal for m = 12 is not enough. If they're asking the latter, it is.

---
Tags: hash, hash-tables, hashing
---


# Question
Title: Sets of problems in different models of computation and cardinality
In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg

Essentially, Pushdown Automata (PDA) can solve more problems (i.e. recognize more languages) than Finite State Machines (FSM), Turing machines (TM) can solve more problems than PDA etc. To continue, suppose $s(FSM), s(PDA), s(TM)$ denotes the set of problems solved by FSMs, PDAs and TMs, respectively. Then, the figure states that: $s(FSM) \subset s(PDA) \subset s(TM)$

However, I have a confusing argument regarding the cardinality of the above sets.

1. All sets of computational models (e,g, FSMs, PDAs and TMs) are countably infinite. Because all can be represented as computer programs in binary string form, which are also countably infinite.
2. If FSMs are countably infinite, then the problems that can be solved with FSMs, $s(FSM)$, cannot be more than countably infinite. The same is true for $s(PDA)$ and $s(TM)$.
3. Countably infinite sets have cardinal number $\aleph\_0$ (aleph zero). Thus if $C(.)$ denotes cardinality, $C(s(FSM)) = C(s(PDA)) = C(s(TM)) = \aleph\_0$.

Is the above argument correct? If it is true and the above sets have the same cardinality, in what sense is the figure (which states that $s(FSM) \subset s(PDA) \subset s(TM)$ true?

The only hypothesis I can think of is an argument of "redundancy". That is that while there is an equal number of TMs and FSMs, the same is not true for the problems that can be solved with these. That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent. Thus, more problems can be solved with TMs than can be with FSMs. Stated differently, the set of problems solved by TMs is greater than the problem set solved by FSMs. However, both problem sets are infinite and there is no infinity smaller than $\aleph\_0$, so the two problems sets should have the same cardinality $\aleph\_0$

# Answer
#### Cardinality is a Weak Property

As described in the question, cardinality is a very weak property. It is not strong enough to distinguish $s(FSM)$, $s(PDA)$, $s(TM)$. It cannot differentiate any two different sets that are both countably infinite.

That is not surprising at all.

For example, we know that $$\mathbb N\subsetneq(\mathbb N\cup\\{-1\\})\subsetneq\mathbb Z\subsetneq\mathbb Q\subsetneq\mathbb Q(\sqrt2).$$ However, $$C(\mathbb N)= C(\mathbb N\cup\\{-1\\}) = C(\mathbb Z) = C(\mathbb Q)=C(\mathbb Q(\sqrt2))=\aleph\_0.$$

#### the Meaning of $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$

Fix any alphabet $\Sigma$ such as $\\{0,1\\}$ or $\\{a,b,c\\}$. Let $s(FSM)=s\_\Sigma(FSM)$ be the set of regular languages over $\Sigma$. Similarly, $s(PDA)$ be the set of context-free languages over $\Sigma$ and $s(TM)$ be the set of computably-enumerable languages over $\Sigma$. Then $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$.

In case you are not satisfied with a fixed alphabet, we can switch to different definitions. Let $\Sigma\_1\subset\Sigma\_2\subset\cdots$ be a sequence of alphabets. (Each alphabet is still finite.) Let $s(FSM)=s\_{\Sigma\_1}(FSM)\cup s\_{\Sigma\_2}(FSM)\cup s\_{\Sigma\_1}(FSM)\cup\cdots$. Define $s(PDA)$ and $s(TM)$ similarly. Then we still have $s(FSM) \subsetneq s(PDA) \subsetneq s(TM)$.

"That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent..." It might be better not to consider that kind of logic, which is basically trying to compare $\infty/\infty$ with another $\infty/\infty$, where we have four different infinities. (In fact, my intuition indicates the other way. For example, it is decidable whether two FSMs solve the same problem while it is undecidable whether two TMs solve the same problem.)
> 5 votes

---
Tags: turing-machines, computability, finite-automata, pushdown-automata, infinity
---


# Question
Title: Proving transitivity in an intuitionistic type theory without the K rule
In Agda, if I disable axiom $\mathbb{K}$ I'm not able to prove $$ \forall\\{A : \textbf{Set}\\}\\{a\ b : A\\}\\{p\ q : a \equiv b\\} \to p \equiv q, $$ which I guess is normal since the system does not truncate equalities. However, I'm still able to prove transitivity $$ \forall \\{A : \textbf{Set}\\}\\{a\ b\ c : A\\} \to (b \equiv c) \to (a \equiv b) \to (a \equiv c) $$ by pattern matching on $\textit{refl}$s, i.e. $\textit{trans }\textit{refl }\textit{refl} = \textit{refl}$. Am I missing something obvious here? What axiom is the system applying to assume the path is the reflexivity path (is it axiom $\mathbb{J}$?)? Thanks in advance.

# Answer
$\newcommand{\J}{\mathsf{J}} \newcommand{\K}{\mathsf{K}} \newcommand{\refl}{\mathsf{refl}}$

Yes, this just uses axiom $\J$. $\K$ is only necessary for translating certain particular cases of pattern matching.

$\J$ works when you have an identity like $p : E \equiv a$, where $a$ is a variable that doesn't occur in $E$. Then you can reduce the proof obligation to one where we have replaced $p$ by $\refl : E \equiv E$ while replacing $a$ with $E$. In Agda, this is presented as matching on the case $\refl$ (and 'matching' $a$ with the pattern $.E$ if it's an explicit argument). In the $\mathsf{trans}$ case, this easily applies both times (and there are variables on both sides, so you could also consider an opposite version of $\J$ where $E$ is on the right).

The proof that all identities $a \equiv b$ are equal fails this rule. Using the above method, one match will refine $p$ to $\refl$ and $b$ to $a$, meaning the second match is on $q : a \equiv a$. Now $a$ is on both sides, and we can't justify the match with $\J$, and require $\K$.
> 4 votes

---
Tags: type-theory, functional-programming, dependent-types, proof-assistants, agda
---


# Question
Title: Lower bound union of a unsorted array with sorted array
I read this link and I have similar question.

Suppose given two Arrays $A$ that is sorted array with length $n$ and $B$ unsorted array with length $n$. We want to find union of two arrays (i.e. we try to compute $A\cup B$) with comparison computation model. Can we claim that the lower bound of this problem is $\Omega(n\log n)$?

# Answer
I think this is possible in $\mathcal{O}(n)$ average case, using hashtables.

You just need to create a hashtable of your elements, and before adding a new one to the result, you can check in $\mathcal{O}(1)$ average if it is already present, and add it to the hashtable if not.

I suppose here that a comparison between two elements is done in $\mathcal{O}(1)$ time.
> -1 votes

# Answer
But I think this is possible in $O(n(log(n)))$. Since, you can set C=A (suppose that we have no duplicate in A) and then for addition of each member from B to C it is sufficient to search it in sorted array A and if it was not in A then add the member to C.
> -1 votes

---
Tags: algorithms, lower-bounds
---


title: Heap sort worst case

text:
# Question
Title: Heap sort worst case
I am really confused about this. I am trying to prove that the worst case of heap sort is Ω(nlogn) but i don't even know how to start.

# Answer
> 0 votes
After the build-up phase of the heap, HeapSort repeatedly removes the root of the heap. You can find configurations such that every root removal implies the movement of nodes on every level, resulting in a total work proportional to $\log(n)+\log(n-1)+\dots+ \log(1) \sim \log(n!)$.

# Answer
> -3 votes
Write code for heap sort or copy it from somewhere and run some tests to make sure it is correct.

Then analyse the code. You will find there are lots of operations that run in O(log n), and you’ll need O(n) of them.

---
Tags: heap-sort
---


title: Lamport Timestamps and Causality

text:
# Question
Title: Lamport Timestamps and Causality
I'm having trouble understanding lamport timestamps in practice and how they guarantee causal ordering.

### Definitions

Lamport defines the "happens before" relationship in his paper. He states that an event a happens before an event b (denoted as a -\> b) under the following conditions:

> (1) If a and b are events in the same process, and a comes before b, then a -\> b. (2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a -\> b. (3) If a -\> b and b -\> c then a -\> c.

He then describes the algorithm for each node to keep track of the event timestamps.

> 1. Each process Pi increments (counter) Ci between any two successive events.
> 2. (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm= Ci(a). (b) Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.

This supposedly guarantees a causal ordering to events in the system

### Question

In the following hypothetical sequence of events on 3 processes, isn't there a conflict in causal ordering? Event (2,1) happens before event (4,2), and (4,2) happens before (7,3), but then (7,3) happens before the receipt of (2,1). Since (4,2) had information from (2,1), applying the state from the broadcast of (2,1) *after* applying the state from the broadcast of (5,2) seems like it would result in an inconsistency? What am I missing?

* Note each event in the table is notated with the corresponding lamport timestamp (counter, nodeId)
* Events within a process occur in order from top to bottom
* "Broadcast(a,b)" is the event (a,b) that is the broadcast of state from node b to all other nodes
* "Receive(a,b) -\> (x,y)" indicates the event (x,y) that is the receiving of some broadcast event (a,b).

| P1 | P2 | P3 |
| --- | --- | --- |
| (1,1) | (1,2) | (1,3) |
| Broadcast(2,1) | (2,2) |  |
|  | Receive(2,1) -\> (3,2) |  |
|  | (4,2) |  |
|  | Broadcast(5,2) |  |
| Receive(5,2) -\> (6,1) |  | Receive(5,2) -\> (6,3) |
|  |  | (7,3) |
|  |  | Receive(2,1) -\> (8,3) |

# Answer
No, there is no inherent logical/temporal inconsistency in the events described in the question, although it can be considered "unfair" that process P2 can receive and broadcast messages faster than other process. Well, this kind of "unfairness" occurs naturally and commonly. It is not the responsibility of Lamport timestamps to remove or hide this "unfairness".

Note that the events in the question can happen in the same temporal order, without any reference to Lamport timestamps. That is, a message sent by P1 was received by P3 only long after the message was received by P2. We can imagine, for example, both the messaging link between P1 and P2 and the messaging link between P2 and P3 are fast channels while the messaging link between P1 and P3 are sluggish. It takes a second for a message to go between P2 and another process while it takes a day for a message to go between P1 and p3. So, these events cannot involve any impossible "causal ordering".

In fact, we could say that Lamport timestamps makes it easier to identify this kind of "unfairness" or "difference of communication speeds", such as when an event like "Receive(5,\*)" happens before an event like "Receive(2,\*)".
> 3 votes

---
Tags: distributed-systems, partial-order, ordering, consistency-model
---


# Question
Title: Modifying Dijkstra’s algorithm to favor the path with least amount of edges
I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths.

I am thinking to add another data field to count the number of edges from start and compare them in same way as weights. Would that work?

# Answer
Yes, it should. You can simply keep a count of edges traveled. If you discover a new shortest path which is of the same distance as the last shortest path, make an if statement asking whether or not the new path has less number of edges. Here is a short pseudo code that you can use in the "relaxation" part of algorithm.

```
if (new_path == shortest_path && new_path_edges < shortest_path_edges)
    shortest_path= new_path
elseif (new_path < shortest_path)
    //The relaxation part of Dijkstra's algorithm

```

EDIT. Fuller answer below.

```
 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:
 3          dist[v]      := infinity;
            dist_edges[v]:= 0;
 4          visited[v]   := false;
 5          previous[v]  := undefined;
 6      end for
 7
 8      dist[source]  := 0;
        dist_edges[source] := 0;
 9      insert source into Q;
10
11      while Q is not empty:
12          u := vertex in Q with smallest distance in dist[] and has not been visited;
13          remove u from Q;
14          visited[u] := true
15
16          for each neighbor v of u:
17              alt := dist[u] + dist_between(u, v);
                alt_edges := dist_edges[u] + 1; //Note the increment by 1
                if (alt = dist[v] && alt_edges < dist_edges[v])
                    previous[v] := u;
                    dist_edges[v]= alt_edges
18              if alt < dist[v]:
19                  dist[v]  := alt;
                    dist_edges[v] := alt_edges;
20                  previous[v]  := u;
21                  if !visited[v]:
22                       insert v into Q;
23                  end if
24              end if
25          end for
26      end while
27      return dist;
28  endfunction

```
> 4 votes

# Answer
If you want a simpler answer and want to minimize space cost, you can simply add .00000001 (or some other extremely small fraction that is small enough that it will not significantly affect the weights of the paths and thus will not alter the overall result of running Dijkstra's) to every edge. This way, a path of size E = 5 and a path of size E = 10 that would otherwise be seen as equivalent in length under Dijkstra's can be differentiated due to the fact that the path of E = 10 will be 5 * whateverSmallFraction greater than the path of E = 5.
> 2 votes

# Answer
You can add a small value positive $\delta$ to each edge and use Dijkstra's algorithm to find the shortest path. Any $\delta \< \frac{1}{V}$ will suffice.
> 1 votes

# Answer
The $\delta$ trick will work with a suitable choice of $\delta$, but a bulletproof method is to rate the paths with the pair (sum of weights, length), and use lexicographical ordering (i.e. in case of ties on the sums, compare the lengths).

Besides this, the algorithms remains completely unchanged.
> 1 votes

---
Tags: algorithms, graphs
---