# Question
Title: Language of all even-length words with no 1's in left half
Consider the following language:

$$L=\\{w \in \textstyle\Sigma\_1 ^\*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\\},$$

where $\Sigma\_1 = \\{0,1\\}$.

I need to show that this is not regular. I tried to prove this with the pumping lemma.

Imagine that there exists a pumping length $d$, and consider the string $s=0^d1^d$. If we choose $s=xyz$ arbitrarily with $|y| \> 0$, we will have three options.

1. $y$ can be in the first half of the string.
2. $y$ can be in the second half of the string.
3. $y$ can contain the first and second half of the string.

In the last option, $y$ can only be in the following form: $0(0)^+$ or $(0)^+(1)^+$. (Here $^+$ means Kleene plus.)

For the last form ($(0)^+(1)^+$), we see that $xyyz$ will have a $1$ in the first half, which is not in $L$. Consequently, $L$ cannot be regular.

# Answer
Two points:

* the reasoning is incomplete: you need to show that pumping $y$ in the two first cases also leads to elements outside $L$
* the reasoning does not use $ |xy|\<d$ which entails that only the first case occurs.

But it is not wrong. If you want to ignore $|xy|\<d $ then you need to argue the three cases. The first case holds because deleting $y$ creates a string of odd length or one in which a $1$ appears in the first half. The second case holds because if we pump $y$ $ n \>1$ times a $1$ will flow into the first part.
> 2 votes

# Answer
Take $s = 0^d 1^d$. Given a decomposition $s = xyz$ such that $|xy|\leq d$ and $y \neq \epsilon$, you can check that $xy^0z \notin L$, hence $L$ is not regular.
> 0 votes

---
Tags: regular-languages, pumping-lemma, check-my-answer
---


# Question
Title: Method of communication in Distributed Systems
Why the method of communication used in DS is message passing and not shared memory ?

# Answer
Because in a distributed system, nodes do not have access to shared memory that is shared between all nodes. Shared memory is only typically feasible when the nodes are on a common memory bus, e.g., for multiple core within a parallel processing machine.
> 1 votes

---
Tags: distributed-systems, message-passing, shared-memory
---


title: Solution to T(n) = 2T(n/2) + log n

text:
# Question
Title: Solution to T(n) = 2T(n/2) + log n
So my recursive equation is T(n) = 2T(n/2) + log n

I used the master theorem and I find that a = 2, b =2 and d = 1.

which is case 2. So the solution should be O(n^1 log n) which is O(n log n)

I looked online and some found it O(n). I'm confused

Can anyone tell me how it's not O(n log n) ?

# Answer
> 1 votes
Mater theorem requires that $f(n) = n^c, c\in Z$. In your example, you cannot apply the master theorem directly. Here is my explanation for the answer. We always have $n \geq \log n$. Thus, $T(\frac{n}{2}) + \log n \leq T(\frac{n}{2}) + n$. We can apply master theorem to $T(\frac{n}{2}) + n$ which is $O(n \log n)$. This is a valid bound but not the tightest bound. If you need the tightest bound, I suggest the tree recursion method but algebra can be messy.

---
Tags: algorithms, time-complexity, data-structures, master-theorem
---


# Question
Title: Do you have to do reduction both ways to prove a problem is NPC?
Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!

# Answer
To prove that a problem is NP-complete, you need to show two things:

1. The problem is NP-hard, i.e. it's at least as hard as any problem in NP
2. The problem is in NP, i.e. it's no harder than NP

Doing a reduction both ways is the easiest way to do this: reducing something in NP to a new problem shows that the new problem is NP-hard, and reducing your new problem to something in NP shows that the new problem is no harder than NP.

I've never heard "transforming" used formally, but I would guess from context it's the same as doing a polynomial-time reduction.
> 1 votes

# Answer
The answer by Draconis is wrong in "showing that the new problem is NP-hard." Reducing from something in NP to a new problem does not show NP-hardness. In particular, if a problem A is in P it is also in NP. Suppose there is a reduction from such a polynomial-time solvable A to some new problem B. Then, problem B still can be in P, and in this case B is not NP-hard.

The correct version of this answer says that to show that a new problem is NP-hard one has to reduce from another NP**-hard** problem A. Then, the new problem cannot be "simpler" than the hardest problem in NP. If it were, then one could solve all NP-hard problems via the new problem, first reducing any problem to A (which is NP-hard by assumption) and then to B.
> 3 votes

---
Tags: np-complete, reductions
---


# Question
Title: Exact runtime of median of median algorithm
Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be

$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$ which can be proven by induction equal to $O(n)$.

Assume it takes around $14$ steps to sort group of $7$ elements. How do I find exact runtime if I want to find $k$th smallest element in sequence, by exact run time I mean a solution for above recurrence.

My idea was that since $T(n)=O(n)$ then $T(n)=an+b$ ,where $a $ or $b$ might be depend on value of $k$. How can I find value of $a$ and $b$ or it is impossible to find value of $b$, as value of $a$ can be found but I am not sure how.

# Answer
> 2 votes
"since $T(n)=O(n)$ then $T(n)=an+b$" it's wrong assumption, because big-$O$ gives only upper bound. For example $n^\alpha \in O(n)$ for $\alpha \in (0,1))$, $\log n \in O(n)$ etc., so you cannot reduce situation for only linear functions.

For exact estimation you need to elaborate $O(n)$ in recurrence relation.

---
Tags: time-complexity, algorithm-analysis, runtime-analysis
---


# Question
Title: Ordering the tasks to minimize penalties
So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows:

---

In your calendar you have an $L$ list of all the tasks you need to complete today. For each task $i \in L$ the duration $d\_i \in \mathbb{N}$ is specified which indicates the time required to complete it and a penalty factor $p\_i \in \mathbb{Z^+}$ which aggravates the delay. You must determine in what order to perform all the tasks to get the result that accumulates less total penalty.

Note that:

• In an instant you can only perform one task,

• Once you start a task, you must continue it until it is completed, and

• All tasks must be completed.

The actual penalty associated with a task $i \in L$ is the completion time $t\_i$ of its completion, multiplied by its penalty $p\_i$. The completion time $t\_i$ corresponds to the time elapsed from the start of the working day (i.e. from time instant 0) to the time the task has been completed.

Provide an algorithm (as efficient as you can) to solve it.

---

I have figured out that the completion of a task $i ∈ L$ with completion time $t\_i$ must started at instant $t\_i - d\_i$.

I'm stuck with the optimization criteria. I tried sorting the tasks by $p\_i$ decreasingly, or by $p\_i * d\_i$ increasingly and doing the tasks in such order, but it doesn't work. I can find a counter-example for both approaches. What would be a good optimization criteria for this problem?

# Answer
> 1 votes
Note the minimum penalty for a task is always $p\_i d\_i$. If I choose at a point in time to do task $i$, then all other tasks $j$ will incur an extra penalty of $p\_j d\_i$.

Therefore, you need to do the most expensive task first (i.e., having the largest $p\_i$). If there are multiple such tasks, then the one with the shortest $d\_i$ needs to be performed first.

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


title: Algorithm to find pairs

text:
# Question
Title: Algorithm to find pairs
Task: There are N persons. Some of the persons were meet before. I need to find pairs of persons, that were not meet before.

Example: 4 persons - A, B, C, D. A and B were meet before. Good solutions: (A + C, B + D) OR (A + D, B + C). Bad solution: (C + D) because it is forrbidden to create pair (A + B).

What algorithm can help to resolve this task?

# Answer
It seems that you are looking for a maximum matching in a graph where vertices represent people and an (undirected) edge $(u,v)$ means that $u$ and $v$ have not met before.

This problem can be solved in time $O(n^{1/2} \cdot m) = O(n^\frac{5}{3})$, where $n$ is the number of people and $m$ is the number of pairs of people that have not yet met.
> 2 votes

---
Tags: algorithms
---


title: Upper bounds for a binomial coefficient

text:
# Question
Title: Upper bounds for a binomial coefficient
I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $.

I need an argument which shows that the runtime complexity is solely a function of its parameter $k$, i.e. that the input size $p$ does not matter for runtime complexity.

My own argument goes as follows:

$$ \binom{k}{p-1} = \frac{k!}{(p-1)!(k-(p-1))!} \leq k!$$ Where the first equality follows from the definition of the binomial coefficient and the second inequality follows from the observation that both $(p-1)!$ and $(k-(p-1))!$ are greater than or equal to $1$.

Thus the algorithm runs in $\mathcal O (k!)$, which is a not a function of $p$ as required.

Is this argument correct or am I missing something? Maybe I am overcomplicating things and there is a faster / better argument?

# Answer
> 5 votes
The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows:

$$ \binom{k}{p-1} \le \sum\_{i=0}^{k} \binom{k}{i} = 2^k $$

Where the equality $\sum\_{i=0}^{k} \binom{k}{i} = 2^k$ follows from the fact that the summation on the left is counting the number of possible subsets of a set with $k$ elements, grouped by cardinality: the $i$-th term of the sum (for $i=0, \dots, k$) is the number of subsets with exactly $i$ elements.

Also, using Stirling's approximation and assuming that $k$ is even (this is just for convenience, if it's not you can consider $k+1$ instead to get the same asymptotic bound):

$$ \binom{k}{p-1} \le \binom{k}{k/2} = O\left( \frac{ (k/e)^k \sqrt{k} }{ k (k/2e)^k } \right) = O\left(\frac{2^k}{\sqrt{k}} \right). $$

# Answer
> 3 votes
There are well known inequalities: $$\frac{n^k}{k^k}\leqslant \binom{n}{k}\leqslant \frac{n^k}{k!}$$

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


title: Question about complexity of algorithms

text:
# Question
Title: Question about complexity of algorithms
I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?

# Answer
> 2 votes
We can understand it as set $\\{2^{f(n)}: f \in O(n)\\}$.

For example any $n^k,k\>0$, will be in $2^{O(n)}$: $n^k=2^{k\log\_2 n}$ and we have $\log\_2 n \in O(n)$.

**Note**: I especially not write $k \cdot \log\_2 n \in O(n)$, because multiplication on positive constant has no influence.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Serving $k$ customers with bounded time window
A person provides a service and he/she can serve $k$ clients each minute.

Now, client number $i$ comes at the beginning of minute $a\_{i}$ and waits $w\_{i}$ minutes to receive the service and if they don't receive the service in the interval $\[a\_{i}, a\_{i} + w\_{i}\]$, they leave.

If we have $n$ clients, can the person serve all them or not?

**My question**: Does the above problem have a formal name? I want to write a python code for that but I don't know which keywords should I search?

# Answer
> 1 votes
The problem can be solved in $O(n \log n)$ time where $n$ is the number of clients (Note that in the trivial case where $k \> n$, you simply serve all clients as soon as they come.)

The algorithm is well-known: Sort the intervals by startpoint, endpoint.

Then you iterate over the intervals, for each minute.

If you are at a point where more than $k$ intervals end the next minute, you cannot solve it.

Otherwise you remove the $k$ first intervals in your list, and increase the minute counter.

---

Note that to be truly polynomial, you might need to skip further ahead than to the next minute, but that's an exercise. (E.g. when the input is $$\left\[(2^0, 2^1), (2^2, 2^3), (2^4, 2^5), ..., (2^{100}, 2^{101})\right\]$$ or other large numbers.)

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


# Question
Title: For dynamic programming problems, how do we know the subproblems will share subproblems?
So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data\_structures\_algorithms/dynamic\_programming.htm) mentions is that, we use dynamic programming when:

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

So my question is that how do we know when in a problem if we apply the divide-and-conquer approach, we will get overlapping sub-problems?

Eg: Let's take the famous problem from Cormen.

> A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting, and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Here, how do we know that subproblems will overlap?

# Answer
> 3 votes
The answer is - you don't. Not in advance. There are no guarantees and there is no silver bullet process.

Instead, dynamic programming is a way of thinking about a problem, a framework for approaching a problem. You typically won't know whether that approach will be successful or not in advance.

Dynamic programming basically amounts to finding a recursive algorithm for the problem, and then speeding it up with memoization. You'll have to try different recursive algorithms (different ways of decomposing into subproblems) and see, for each candidate, if it has the properties that are needed to apply these ideas successfully. You usually won't know in advance whether any particular decomposition into subproblems will be successful. You might be able to tell whether those subproblems will be "overlapping", but not whether it'll lead to a useful dynamic programming algorithm. It's partly an art, where experience helps give you some intuitions for what kinds of subproblems might be useful in any particular situation.

I encourage reading What is dynamic programming about?, When can I use dynamic programming to reduce the time complexity of my recursive algorithm?, and Deciding on Sub-Problems for Dynamic Programming to get a sense of this perspective.

Personal opinion: I personally don't find "overlapping subproblems" as a very helpful way to think about dynamic programming. I encourage you to use whatever works for you, but that one never worked very well for me. If you want to understand it, think about algorithms that work on an array $A\[1..n\]$. Divide-and-conquer will work on some subarrays, say $A\[1..n/2\],A\[n/2+1..n\],\ldots$, but no pair of those have a partial overlap. Dynamic programming may work on all subarrays, say $A\[i..j\]$ for all $i\<j$, and there are pairs of those that partly overlap (e.g., $A\[3..5\]$ overlaps with $A\[4..9\]$). That's what is meant by "overlapping subproblems", and that is one distinction between dynamic programming vs divide-and-conquer. That said, I don't find that a very helpful characterization, personally -- and especially, I don't find it helpful at designing an algorithm (it might be more helpful once I already have an algorithm and am wondering whether I should call it divide-and-conquer vs dynamic programming, but at that point I often don't care too much what we call it).

---
Tags: dynamic-programming
---


# Question
Title: Cryptosystems whose hardness depends on solving the halting problem?
There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.

Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf

Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115

# Answer
For any reasonable public key cryptosystem that I can think of, no, this is not possible. You cannot base a practical public key cryptosystem on any complexity class larger than EXPTIME.

If the private key is linear in the size of the public key (i.e. if the public key is $b$ bits in size, then the private key is no larger than $\alpha b + \beta$ bits for some constants), then you can test all possible private keys (in exponential time) and see which one decrypts a message.
> 1 votes

---
Tags: undecidability, halting-problem, cryptography
---


# Question
Title: What is the shortest total path between pairs of points?
I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.

Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.

Any pointers welcome.

# Answer
> 4 votes
This appears to be a maximum matching problem. Well, minimum matching, but you should be able to make the necessary adaptations.

# Answer
> 0 votes
This is a modification of a maximum matching problem, as answered by DW. Modifying Hopcroft-Karp for this use is a undergrad uni level assignment (one I had to do myself at that level).

---
Tags: shortest-path, traveling-salesman
---


title: Simplify Boolean expression

text:
# Question
Title: Simplify Boolean expression
The following Boolean expression is simplified into its minimal number of literals:

$$x'y' + yz +x'yz' \implies x'+yz.$$

How do you logically conclude this using the Boolean Laws?

# Answer
$$ \begin{align\*} x'y' + yz + x'yz' &= x'y' (z+z') + (x+x')yz +x'yz' &\mbox{(identity)} \\\&= x' y' z + x' y' z' + xyz + x'yz + x'yz' &\mbox{(distributivity)} \\\&= x' y' z + x' y' z' + xyz + x'yz + x'yz + x'yz' &\mbox{(idempotence)} \\\&= x'(y' z + y' z' + y z + y z') + (x+x')yz &\mbox{(distributivity)} \\\&= x'+yz. &\mbox{(identity)} \end{align\*} $$
> 1 votes

---
Tags: boolean-algebra
---


# Question
Title: Find an infinite recognizable not decidable subset of an infinite decidable language
If $L$ is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable.
b) An infinite subset that is recognizable and not decidable.

For the (a) I considered all the subsets of $L$, i.e., $\mathbb{P}(L)$. Since $|\mathbb{P} (L)| = |\mathbb{R}|$, there exists $A \subset L$ that is not recognizable (for there are not enough Turing machines to recognize them all). If $A$ were finite, it would be decidable and hence recognizable, which would be a contradiction. Therefore $A$ is infinite and not recognizable.

For (b) I thought about $B=L\setminus A$. Then $B$ is recognizable because $A$ is not. But I'm not really sure.

# Answer
> 1 votes
Let $K$ be the set of indices of Turing machines which halt on the empty input. Consider the following language:

$$X = \\{ 0 w : |w| \in K \\} \cup \\{ 1 w : |w| \notin K \\}. $$

You can check that neither $X$ nor its complement are recognizable.

Therefore your proof idea doesn't work. Here is a different idea. Let $w\_1,w\_2,w\_3,\ldots$ be the words in $L$, enumerated according length and then lexicographically (so if $L = \Sigma^\*$, the order would be $\epsilon,0,1,00,01,10,11,\ldots$). The language

$$ Y = \\{ w\_i : i \in K \\} $$

is recognizable but not decidable.

---
Tags: turing-machines, semi-decidability
---


# Question
Title: How to prove that Bellman-Ford algorithm detects a negative cycle?
I have read that if we run the outer-loop of the Bellman-Ford algorithm for |V| times (where |V| is the number of nodes in the graph) and check if any distance has changed in the |V|th iteration (i.e. the last iteration) then there exists at least one negative weight cycle in the graph. But why does this work? Why only run for |V| times, why not more than that?

1. I am looking for a **mathematical proof** on why a change in the value of the distance of a node during the last iteration (|V|th iteration) implies that there is a negative weight cycle?
2. Can we detect all the nodes that are either reachable or are parts of the negative weight cycles **after the |V|th iteration** (can this also be **proved** **mathematically**)?

It would be helpful if someone can either provide the proofs and explanations or direct to the relevant resources.

Thank you.

# Answer
Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists).

To prove this, we can use induction: Clearly this holds after the first step as a path of length $1$ is just an edge connecting two vertices. Now suppose we found minimal weight paths from $s$ to any other vertex of length $\leq k$ after the $k$-th step and we execute the $(k + 1)$-th step. Note that any path $p\_{sv}$ of length $k + 1$ from $s$ to some vertex $v$ can be formed by taking some path $p\_{sw}$ of length $k$ from $s$ to a neighbor $w$ of $v$ and then appending the edge $wv$ and in particular we find that if $p\_{sv}$ is of minimal weight w.r.t. all $s$-$v$-paths of length $k + 1$ then $p\_{sw}$ must already be weight-minimal w.r.t. all $s$-$w$-paths of length $k$ (otherwise one could use a better path from $s$ to $w$ and adjoin $wv$ to get a path with less weight than $p\_{sv}$) and the claim follows.

Now let us address your first question. Note that any simple path (i.e. one that does not self-intersect) between any two vertices in $G$ is of length at most $|V(G)| - 1$ and conversely, any path of length $\geq |V(G)|$ must contain a cycle. Hence, a path from $s$ to $v$ of length $|V(G)|$ (or greater) can be decomposed into three parts: some initial path segment starting at $s$ and ending at some vertex $w$, a cycle (of positive length) starting and ending at $w$ and some final path segment from $w$ to $v$ (note that the path segments need not be cycle-free themselves).

If $G$ contained no negative cycles, then the path obtained from appending the final path segment to the initial one is cannot be of larger weight than the one also containing the cycle and thus, the weight of any path containing a cycle can never be shorter than the cycle-free path obtained from cutting said cycle out in the manner I outlined and in particular, this means that the algorithm cannot improve on the paths it found in $|V(G)| - 1$ steps. However, if at least one negative cycle exists in $G$ we can use the lemma we proved in the beginning we get that the Bellman-Ford-algorithm will find an improved path in the $|V(G)|$-th step which could not exist in a graph with no negative cycles, showing that the graph contains a negative cycle if and only if we detect such an improvement in the $|V(G)|$-th step.

The answer to your second question is negative and it is easy to construct counterexamples where arbitrarily many iterations are needed to find all vertices reachable via paths including negative cycles: Consider the butterfly graph $B$ on the five vertices $v\_1, ..., v\_5$ such that both $C\_1 = \\{v\_1, v\_2, v\_3\\}$ and $C\_3 = \\{v\_3, v\_4, v\_5\\}$ are the triangles of $B$ (i.e. $v\_3$ is the "center vertex" of degree 4) and set the weights such that $C\_2$ forms a negative cycle of weight $-1$ while $v\_1 v\_2$ and $v\_1 v\_3$ have both weight $0$ and $v\_2 v\_3$ has weight $n$. Now consider the paths from $v\_1$ to $v\_2$ -- using the negative cycle $n + 1$ times we are able to find a path better than the one consisting only of the edge $v\_1 v\_2$ but such a path has length $2 + 3 \cdot (n + 1)$ and hence by choosing $n$ to be some large enough value (really $n \> 1$ suffices) and recalling our initial result we can see that the Bellman-Ford algorithm will not find that $v\_2$ can be reached via a negative cycle until step $2 + 3 \cdot (n + 1)$. Since of course every vertex in such a negative weight cycle is also one reachable via one, this also negatively answers the second part of this question.

However, note that if some vertex $v$ cannot be reached via a negative cycle from the starting vertex $s$ then the distance (in the algorithm's table) between $s$ and $v$ can only decrease at most $|V(G)| - 1$ times while for any vertex that can be reached via a negative cycle said distance can decrease arbitrarily often, so it is possible to find all such vertices eventually with some additional bookkeeping.
> 2 votes

---
Tags: graphs, shortest-path, weighted-graphs
---


title: Decidability of PDA

text:
# Question
Title: Decidability of PDA
I have following problem:

```
   INFPDA={⟨A⟩ |A is PDA and L(A)=infinite language}

```

Prove that this is decidable problem.

So my idea how to solve this problem is the following:

1. k = number of states of A, create finite automata D, which accepts all words which have length=k and more
2. Create context-free grammar G based on A

And now I am lost. If the automata would be DFA then I would do: L(M) =L(A)∩L(D) then I would check whether L(M) = ∅ using turing machine (tm) for emptiness. And I would use pumping lemma. But as far as I know, I cannot use ∩ with context-free language.

How to prove this then, please? Thank you

# Answer
Consider a context-free grammar $\mathcal{G}$ for $L(A)$ in Greibach normal form with no useless nonterminals (i.e., non-terminals that cannot be transformed into a sequence of only terminals by applying production rules). Such a grammar can be mechanically constructed from $A$. Now build a directed graph $G = (V,E)$ as follows:

* Each nonterminal of $\mathcal{G}$ is a vertex of $G$.
* For each production of $\mathcal{G}$ where a nonterminal $A$ appears on the left side and a (not necessarily distinct) nonterminal $B$ appears on the right side, add the edge $(A,B)$ to $G$.

Clearly if there is a cycle in $G$ then the cardinality of $L(\mathcal{G}) = L(A)$ is infinite. Indeed, for every $k \in \mathbb{N}$, there exists a walk from $S$ on $G$ of length $k$. By first applying the productions corresponding to the edges of this walk, and then a suitable set of productions to get rid of the leftover nonterminals, you can build a word $w \in L(A)$ such that $|w| \ge k$.

Conversely, if the language is infinite, for every $k \>0$ there must be a derivation in $\mathcal{G}$ that uses at least $k \ge |V|$ productions. This induces a walk (from $S$) on $G$ of the same length $k$. This walk traverses at least $k+1 \ge |V|+1$ (not necessarily distinct) vertices of $G$ and, by the pigeonhole principle, at least one vertex must appear two or more times. This shows the existence of a cycle in $G$.

Determining whether a directed graph is cyclic is a decidable problem (a simple DFS visit suffices).
> 2 votes

---
Tags: turing-machines, context-free, pushdown-automata
---


# Question
Title: How can I prove the correctness of this exponentiation algorithm using induction?
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, `Exp(n)`${}= 2 ^ n$?

```
Exp(n)
    If n = 0
        Return 1

    If n is even
        temp = Exp(n/2)
        Return temp × temp
    Else
        temp = Exp((n−1)/2)
        Return temp × temp × 2

```

# Answer
$Exp(0) = 1 = 2^0$ is trivially correct (hard coded) by the algorithm.

Assume the algorithm holds for values of $n$ up to $k$. Now consider the algorithm for input $n = k+1$. We compute $Exp(n) = Exp(k+1)$ using the algorithm:

**In the case that $n = k+1$ is even:**

The algorithm computes $temp = Exp(\frac{k+1}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k+1}{2}}$ because we assumed the algorithm is correct for values up to $k$ \[1\]. The algorithm correctly returns $temp\*temp = 2^{\frac{k+1}{2}}\*2^{\frac{k+1}{2}} = 2^{k+1}$.

**In the case that $n = k+1$ is uneven:**

The algorithm computes $temp = Exp(\frac{n-1}{2}) = Exp(\frac{k+1-1}{2}) = Exp(\frac{k}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k}{2}}$ because we assumed the algorithm is correct for values up to $k$ \[1\]. The algorithm correctly returns $temp\*temp\*2 = 2^{\frac{k}{2}}\*2^{\frac{k}{2}}\*2 = 2^{k+1}$.

i.e. since $Exp(0) = 1$ is trivially correct by the algorithm and we showed that the algorithm is correct for $Exp(n+1)$ if $Exp(n)$ is correct; it follows that the algorithm is correct for every $n \geq 0$.

\[1\] Technically you also have to show that $\frac{k+1}{2} \leq k$ and $\frac{k}{2} \leq k$ for every $k \> 0$ but that seems easy enough to prove.
> 2 votes

---
Tags: algorithms, algorithm-analysis, discrete-mathematics, induction
---


# Question
Title: Why we don't consider cycles in path problems?
I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(including circles) in the result. Is it because the complexity is way too expensive? Thanks in advance for your help!

# Answer
> 1 votes
When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.

---
Tags: graphs, shortest-path, weighted-graphs, database-theory
---


# Question
Title: Intuition behind the Reversal Algorithm [ Rotation of Array ]
I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody give me the intuition or simple math explanation for me to understand.

```
void rotate(vector<int>& nums, int k) {
    k %=nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin()+k);
    reverse(nums.begin()+k, nums.end());
}

```

# Answer
> 1 votes
Imagine flipping a deck of cards over, then dividing it into two parts and flipping each part over. The cards in each part end up in their original order because they're flipped twice. The first flip also swaps the two parts. The net effect is the same as cutting the deck, i.e. rotating it.

# Answer
> 0 votes
For me it is helpful to see the proof. Consider the equivalent algorithm where you reverse $0...n-k-1$, reverse $n-k...n-1$, and finally reverse $0...n-1$.

Let’s say you are rotating an array of $n$ elements by $k$. For $0 \leq i \leq n-k-1$, the new position of element $i$ is $i+k$. For $ n-k \leq i \leq n-1$, the new position of element $i$ is $i+k-n$.

Now let’s look at the transformation when following the algorithm above. For an element at position $i$, the first reverse will put that element at $n-i-1$. The third reverse will take an element at position $j\leq n-k-1$ and put it at $n-k-j-1$. Therefore, an element beginning at position $i \geq n-k-1$ will end up at $n-k-(n-i-1)-1=k+i$. A similar proof follows for the elements in the upper part of the array rotation ($i\geq n-k$).

The proof for the algorithm you posted above is essentially the same, the difference being that the elements in the sub array rotations are no longer necessarily all $\leq n-k-1$ or $\geq n-k$.

---
Tags: algorithms, data-structures, c++
---


# Question
Title: Proving the language of non-primes is in NP
I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.

Show the following language is in NP:

Not-Prime = {n ∈ N: n is not a prime number}

So far, I have created an efficient decider for the language with a certificate, but I'm not sure how to prove that the language is actually in NP. Thank you for any advice!

# Answer
> 2 votes
If you created a deterministic polynomial-time algorithm $A$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $\mathsf{NP}$.

Say that a polynomial upper bound on the length of the certificate is $p(s)$, where $s$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:

* Guess the length $\ell$ of the certificate in $\\{0, \dots, p(s)\\}$.
* For $i=1, \dots, \ell$: guess the $i$-th bit $c\_i$ of the certificate.
* Run $A$ on the certificate $c\_1 c\_2 \dots c\_\ell$. If $A$ accepts, accept. Otherwise reject.

A certificate for an instance $n$ of Not-Prime is just a non-trivial prime factor of $n$ (which requires at most $\lceil \log n \rceil$ bits to be represented, so you can pick $p(s)=s$).

---
Tags: formal-languages, undecidability, np
---


# Question
Title: Time complexity of removing a vertex from a graph represented as collection of adjacency lists
I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated to any particular vertex $v\_i$ contains the vertices directly reachable from $v\_i$ (i.e. the edges with origin $v\_i$).

Let's assume that the graph is represented as a hash map, which pairs a certain vertex with its adjacency list, which is a linked list. Iterating over a linked list of $m$ elements has a time complexity of $O(m)$, and deleting a node of the list as one iterates over it has constant complexity $O(1)$.

In order to remove a vertex $v\_d$ I would need to:

1. Remove the pair with key $v\_d$ from the hash map (which is $O(1)$).
2. Iterate over the adjacency lists of the rest of the vertices, removing any occurrence of $v\_d$.

The second step would mean iterating over each vertex $v\_i$ in the key set of the hash map (~$n$ vertices, after having removed one), and for each vertex $v\_i$ iterate over its adjacency list, which is of length $e\_i$.

Now, it is clear that $\displaystyle\sum\_{i=1}^{n} e\_i = e$, so my first thought is that the time complexity of the second step is $O(e)$, and so is the total cost of removing a vertex in this situation. Note how this is independent of the number of vertices in the graph.

However, I'm thinking about the case in which there are no edges at all. In that case, step two still requires iterating over the whole list of vertices, so I'm lead to believe that the number of vertices has to play some role inthe time complexity of the method.

**What is the actual time complexity in this set up and how can you reconcile the two (apparently contradictory) conclusions I've reached?**

# Answer
> 1 votes
In step 2, vertices with no neighbours have an empty adjacency list, but it still takes one time step to realise that the list is empty. So the runtime is $\sum\_{i\in\[n\]\smallsetminus \\{d\\}} \max(1,e\_i)=O(n+e)$.

---
Tags: graphs, time-complexity
---


title: Find number of platters of a given disk

text:
# Question
Title: Find number of platters of a given disk
I am kinda blocked trying to figure out the answer to this question. Mind helping?

A manufacture wishes to design a hard disk with a capacity of 60 GB or more (using the standard definition of 1GB = 230 bytes). If the technology used to manufacture the disks allows 512-bytes sectors, 1024 sector/track, and 60% tracks/ platter, how many platters are required?

# Answer
As per the given question,

Capacity of hard disk =60GB=60GB

1GB=2^{30}=10737418241GB=2 30 =1073741824 bytes

Number of bytes per sector =512=512 bytes/sector

Number of sector per track =1024=1024 sector /track

Number of track per platter =60%=60% tracks /platter

The capacity of one platter =512\times 1024\times \frac{60}{100}=314572.8=512×1024× 100 60
=314572.8 bytes/platter

Hence,capacity of one platter in GB =\frac{314572.8}{1073741824}=0.0002929GB= 1073741824 314572.8
=0.0002929GB

Hence, number of required platter to make 60GB hard disk =\frac{60}{0.0002929}=204848.0= 0.0002929 60
=204848.0
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: asymptotic tight bounds for quadratic functions
In **Introduction to Algorithms** by CLRS, it's said

> For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a\>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, we take constants $c\_1=a/4, c\_2=7a/4$ and $n\_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}).$ You may verify that $0\leq c\_1n^2\leq an^2+bn+c \leq c\_2n^2$ for all $n\geq n\_0.$

They didn't specify how values of these constants came? I tried to prove it but couldn't.

# Answer
> 1 votes
I think I can suggest more easy way. Having $a\>0$ in $f(n)=an^2+bn+c$ we can take any $a\_1\<a$ and then show that $a\_1n^2 \< an^2+bn+c$ for some $N\_1,n\>N\_1$ , because it is same as $a\_1 \< a + \frac{bn+c}{n^2}$.

Same we can make for any $a\<a\_2 \Rightarrow an^2+bn+c \< a\_2n^2$ for some $N\_2,n\>N\_2$ because it is same as $a + \frac{bn+c}{n^2}\< a\_2$.

At last we will have $a\_1n^2 \<an^2+bn+c \< a\_2n^2$.

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Is "backward substitution" and "backtracking" the same thing?
From my limited knowledge, they both are related to solving recurrence relation.

Solving recurrence relation using backward substitution

Solving recurrence relation using backtracking

* Can the terms be used interchangeably?

In terms of algorithm, I found the following:

> Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. wiki

> Backward substitution is a procedure of solving a system of linear algebraic equations Ux=y, where U is an upper triangular matrix whose diagonal elements are not equal to zero. The matrix U can be a factor of another matrix A in its decomposition (or factorization) LU, where L is a lower triangular matrix. This decomposition can be obtained by many methods (for example, the Gaussian elimination method with or without pivoting, the Gaussian compact scheme, the Cholesky decomposition, etc.). Here we also should mention the QR decomposition when the matrix A is represented in the form A=QR, where Q is an orthogonal matrix and R is an upper triangular matrix. Since the matrix U is triangular, a procedure of solving a linear system with the matrix U is a modification of the general substitution method and can be written using simple formulas.
>
> A similar procedure of solving a linear system with a lower triangular matrix is called the forward substitution. Note that the backward substitution discussed here can be considered as a part of the backward Gaussian elimination in the Gaussian elimination method for solving linear systems.
>
> There exists a similar method called the backward substitution with normalization. The scheme of this modification is more complex, since a number of special operations are performed to reduce the effect of round-off errors on the results. algowiki

1. Are backward substitution and backtracking the same in terms of recurrence relation?
2. Is backtracking algorithm is the same as the recurrence relation's backtracking?
3. Is backward substitution (same as back substitution?) in recurrence relation the same with backward substitution algorithm?
4. Is backtracking algorithm the same as backward substitution?
5. **What are their relations to each other? *backtracking (recurrence relation) - backtracking (algorithm) - backward substitution(recurrence relation) - backward substitution(algorithm)***
6. **Can the terms be used interchangeably?**

# Answer
> 2 votes
* **Backward substitution** is a specific method to solve a particular problem: a linear system of equations;
* **Backtracking** is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial solution to a complete solution.

This should answer your "can the terms be used interchangeably?" questions: no, they can't.

Imagine you are solving a crosswords puzzle. One algorithm would be: for each definition, find the list of possible words; then try every combination of those words and check if that combination solves the puzzle. This is a bruteforce approach and pretty inefficient. A much better approach is to use backtracking: for each definition, find the list of possible words; choose a word for the first definition; choose a word for the second definition; check immediately for any inconsistency between the two chosen words. If they are inconsistent, "backtrack" by choosing a different word for the second definition. If you run out of words for the second definition, "backtrack" even further by choosing a different word for the first definition. Only if they are consistent, move on to the third definition. This is a **backtracking** algorithm. Backtracking algorithms are often very straightforward to implement using recursion.

**Backward substitution** is a method to solve a system of linear equations. A system of linear equations is something that looks like:

```
a x + b y = c
d x + e y = f

```

As you can see it is a very specific problem. There is no notion of recursion here. Linear equations are often written in matrix form: `A X = B`; in my example, `A = ((a b)(d e))`, `X = (x y)` and `B = (c f)`.

The article you linked mentioned "recurrence" because they had a problem with cascading linear equations; the linear equations are called a "recurrence relation" because they define a sequence, where `X1 = A X0`, `X2 = A X1`, `X3 = A X2`, etc.

---
Tags: algorithms, algorithm-analysis, recurrence-relation, recursion
---


# Question
Title: Confusion about dynamic programming on unconstrained subset sum vs constrained subset sum
In class, we discussed two problems: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.

Question 1: Given an unconstrained set of numbers, find whether or not a certain subset of them adds up to a target value.

Question 2: Given a constrained set of numbers, find whether or not a certain subset of them adds up to a target value.

Now in answer to these questions, our professor mentioned that in the former case, there is no way to do better than $2^{n}$ since we would need to check all possible combinations of the $n$ numbers. But in the second case, we can do better since if we know our numbers are in the range of $\[0,n\]$, our sums can only be in range $\[0, n^{2}\]$, so our running time may be polynomial and not exponential. I have understood up until this point, but when discussing the specific implementation of the two programs is where I am confused.

So, for unconstrained subset-sum, the idea is that we do an implicit traversal of a tree. Where for each number in the set we say, use this or no don't use this. So we get $2^{n}$ possible combinations.

But in the other case, the approach used in class was we used a linked list to store all the possible sums that could be computed by a certain subset of the numbers, and then we took another number from the set, and added it to all the values in the linked list to generate all possible sums that could be formed using this number. If the number is already in the list, we don't bother to add it.

**Question 1:**

What I fail to understand is that, how come this time around the running time is polynomial, when really we are still trying to generate all possible sums like we did the last time? After all we are still trying to generate all possible sums right?

**Question 2:**

I saw that we could use dynamic programming. I am wondering how we can use DP, because the way I am looking at it, each time we are generating a unique subset and so we will never share subproblems?

**Question 3:**

Why cannot we use the second approach (using a linked list to store all possible sums) to solve the unconstrained subset sum problem?

# Answer
> 1 votes
If you have $n$ non-negative integers $x\_1,\ldots,x\_n$ in the range $0,\ldots,T$, then their susbets can sum up only to integers in the range $0,\ldots,nT$. This allows us to solve SUBSET-SUM efficiently in the constrained case. The idea is to use dynamic programming: for $m = 0,\ldots,n$, we determine which of the $nT+1$ potential sums are achieved by subsets of $x\_1,\ldots,x\_m$.

When $T$ is small, say polynomial in $n$, then this leads to a polynomial time algorithm. This is the constrained case. When $T$ is arbitrary, the corresponding algorithm is not efficient. This is the unconstrained case. The difference between the two cases is the number of potential sums – in the constrained case there are only polynomially many potential sums, in the unconstrained case there could be a lot more. In other words, you can use the dynamic programming algorithm in both cases, but the algorithm will only be efficient in the constrained case.

Let me also mention that the $O^\*(2^n)$ algorithm in the unconstrained case can be dramatically improved upon using meet-in-the-middle, to $O^\*(2^{n/2})$. A naive implementation of meet-in-the-middle uses a lot of memory, $\Theta^\*(2^{n/2})$, but this can be improved to $O^\*(2^{n/4})$ (the classic Schroeppel-Shamir algorithm).

---
Tags: algorithms, time-complexity, dynamic-programming, subset-sum
---


# Question
Title: Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?
**Example**: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $ O(\log\_t n) $ (where $t \in \mathbb{N}$ is the order of the tree).

There was one true/false **question** on exam which asks if the Big-O complexity of the operation mentioned in the example above is $ O(\log\_2 n) $.

I am beginner in this topic but I understand that both $ O(\log\_2 n) $ and $ O(\log\_t n) $ belong to the same Big-O complexity category of $ O(\log n) $. The only thing which confuses me is whether it matters if the base of a logarithm is given as a constant or as a variable.

Additionally: Would the answer change if we swap the bases from the **example** and the **question**?

Edit (if relevant): The mentioned complexity is related to the number of disk accesses and it is not the time complexity.

# Answer
Let's look at the root of question: we have $\log\_2 n=\frac{\ln n}{\ln 2}$ and $\log\_t n=\frac{\ln n}{\ln t}$, so $\log\_2 n = \frac{\ln t}{\ln 2} \log\_t n$ and when $t$ is constant, then logarithms are in same complexity class.

Bit if $t=t(n)$, then we can ruin this relation and create any class $O(f(n))$ of complexity taking $t(n)=e^{\frac{\ln n}{f(n)}}$ we have $\log\_t n=\frac{\ln n}{\ln t}=f(n)$.
> 2 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: How to construct an NFA Ai for the given Regular property P1 and P2?
> Let AP = {a; b; c}.
>
> Consider the following regular safety properties:
>
> (a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds.
>
> (b) P2: Between two neighbouring occurrences of a, b always holds.
>
> Construct an NFA Ai for each property Pi such that L(Ai) = BadPref(Pi).
>
> Hint: You may use a symbolic NFA with propositional formulae over the set AP as transition labels.

In the above question,

1. What is symbolic NFA?
2. What would be the propositional formula for P1 and P2?
3. How to construct an NFA from the above two statement?
4. Are there any concrete steps to do it?

The **NFA for bad prefixes** would be just the negation of an NFA right?

I have the solution for it, but I don't understand how did they arrive at the solution.

It would be great if somebody could explain or provide a link on how to do it?

Note: I hope it's not related to LTL since it is not part of the syllabus. Anyways, I believe that one can only construct NBA from the LTL or CTL formula right?

Thank you very much.

# Answer
We have several definitions and notations here, let's go through these first:

* We are given a set of atomic propositions AP. It is not said here explicitly, but usually this means we are interested in languages that have as alphabet the power set of AP. So for AP = {a,b,c}, our alphabet would be Sigma = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }.
* As you can see, writing out this power set alphabet can be a lot of work. For this reason, there is an alternative notation based on propositional formulas. Consider a propositional formula phi over the variables AP. We can take a symbol x from Sigma and in phi set all atomic propositions contained in x to true and all other atomic propositions to false. Then we evaluate phi and it becomes true or false. We can understand phi to refer to all those x from Sigma for which phi evaluates to true.

For example, the formula phi="a and not b" refers to the symbols {a} and {a,c}. The formula phi="a" refers to the symbols {a},{a,b},{a,c},{a,b,c}. The formula phi="not a" refers to the symbols {},{b},{c},{b,c}. The formula phi="not a and not b and not c" refers only to the symbol {}. The formula phi="true" refers to all symbols from Sigma. The formula phi="false" refers to no symbol (not to be confused with the symbol {}). And so on ...

This logic is the notation used on the NFA edges in your example.
* We call a language L over finite words "regular" if there is a NFA that accepts L.
* We call a language L over infinite traces a "safety property" if every trace not in L has a bad prefix, meaning a finite prefix w, such that no infinite continuation of w is in L.
* We call a safety property "regular" if the language of its bad prefixes is regular. Note we are dealing with two different notions of "regular" here, one for languages of finite words and one for safety properties over infinite traces.

## General approach

You are dealing with the problem of going from an informal description of a safety property to a formal description of the language of its bad prefixes. There is no general rule for how to do this, but remember that on an intuitive level, a safety property means "some bad event never happens". The language of the bad prefixes is then exactly those finite words for which "the bad event happens at some point". Your approach would therefore be to analyze what the "bad event" is.

(This is a general problem in model checking of course, when going from informal descriptions to a formal model there is a risk of not perfectly capturing the original description.)

Consider P1: The bad event is "a becomes valid and afterwards b is valid only finitely many steps and becomes false before c becomes true". We can turn this into a slightly more verbose description: "a becomes valid, afterwards we see some b's but no c's and then we see no b and no c". We can use this description to derive a formal definition for "the bad event happens at some point". I personally find regular expressions more intuitive than NFAs, so I would first try to build a regular expression and then build the NFA from that afterwards:

```
(true)* a (b and not c)* (not b and not c) (true)*

```

This regular expression describes all finite words where at some point the bad event happens. We use the (true)\* at the beginnging and the end because we do not care what happens before or after the bad event. The regular expression is already very close the NFA in your example, in general it should be easy to build NFAs from such regular expressions. You can see that the notation based on propositional formulas makes this much more compact compared to writing out the symbols explicitly, e.g. writing "a" is shorter than writing the full regular expression ({a} + {a,b} + {a,c} + {a,b,c}).

This is not the only solution, instead of requiring to see (b and not c)\* before seeing (not b and not c), it would also suffice to require to see (not c)\* before seeing (not b and not c). This would result in the regular expression:

```
(true)* a (not c)* (not b and not c) (true)*

```

The only difference to the first solution would be that instead of requiring to match the first (not b and not c) we see, we could also skip over some (not b and not c)'s because they also match (not c), as long as we match a (not b and not c) eventually. So in a way the first solution is the better one because the resulting NFA is more deterministic.

Consider P2: The bad event would be having two a's such that in between at some point b does not hold. Turning this into a slightly more verbose description, we would get "we see a, afterwards we see some b's without seeing a, then we reach a point where we see neither b nor a, afterwards we see any symbols until we reach the closing a". Turning this into a regular expression for "the bad event happens at some point" gives us:

```
(true)* a (b and not a)* (not b and not a) (true)* a (true)*

```

Again this is very similar to the NFA in your example, it should be easy to see how to construct an NFA from such an expression. As before we could also obtain an alternative solution, by relaxing the (b and not a)\* to (not a)\*, the only difference would be that this would allow to skip over some (not b and not a), as long as we match one eventually. Also, we could strengthen the middle (true)\* to (not a)\*, requiring us to match the first closing a instead of allowing to skip over some a's before matching the closing a:

```
(true)* a (not a)* (not b and not a) (not a)* a (true)*

```

## Regarding the number of states

Since you asked about how to know the number of states: I would first try to obtain some NFA and then check if it can be simplified. For the NFAs in your example, I see no way to further reduce the number of states, but in general minimizing NFAs is a hard problem (reference), so there is no efficient algorithm for that. Of course, if you obtain a fully deterministic automaton, you can apply the standard algorithm for minimizing DFAs.
> 1 votes

---
Tags: finite-automata, propositional-logic
---


# Question
Title: Calculating a jackpot winner based on probabilities
Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a `roll [0-100]`, how would you calculate the winner?

**My solution and the pitfall**

To determine winning users, you could check if a drawn `roll [0-100]` falls between a stack of users' winning probabilities.

Winning probability for each user is calculated by applying `Fc(Bet, Pot Size) = Bet * 100 / Pot size`.

The only algorithm I have in mind to determine who the winner is, is to perform math server-side and iterate each user's winning probability, and check if `roll` falls within:

```
user_bets = [250,250,500]
pot_size = sum(user_bets)
roll = 32.21;
cur_range = [0,0]
for bet in user_bets:
    win_chance = bet * 100 / pot_size
    cur_range = [  cur_range[1] , win_chance + cur_range[1] ]
    if roll >= cur_range[0] and roll <= cur_range[1]:
        # cur_range[0] = 25, cur_range[1] = 50
        # We found the winner
        break

```

**Goal**

The goal is to possibly adopt a one-liner algorithm to determine the winner within `SQL` language, whereas **no iteration** is involved

**Graphic example**

```
User X = BET    =  $13.000
User Y = BET    =   $6.500
User Z = BET    =   $3.250

POT_SIZE        =  $22.750
----------------------------------------------------------------------------------------------------
User X Win range               = 0 ->  57,14     (57% win chance)
User Y Win range               = 57.15 ->  85,71 (29% win chance)
User Z  Win range              = 85,72 ->  100   (14% win chance)
----------------------------------------------------------------------------------------------------
ROLL Example          = 32.27...
WINNER                = User X
----------------------------------------------------------------------------------------------------
ROLL Example          = 91.38...
WINNER                = User Z

```

# Answer
> 0 votes
For each user, sample the exponential distribution with rate equal to the size of that user's bet. The user with the smallest random variate wins the pot. Generation is something like $-\log(1 - \text{random}()) / \text{bet}$ where $\text{random}()$ returns a random number in $\[0, 1)$.

---
Tags: algorithms, probabilistic-algorithms
---


# Question
Title: Does every DAG have at most one "universal source"?
A "universal source" in a directed graph is a vertex v for which out-deg(v)=n-1 and in-deg(v)=0. I know that any DAG has at least one source but can it have more than one for a universal? I know there can be none, and there can be one (binary tree for example, root is universal source) but can there be two?

# Answer
Suppose towards a contradiction that a DAG $G=(V,E)$ on $n$ vertices has more than one universal source and let $u,v \in V$ be two distinct universal sources of $G$.

Since $\mbox{out-deg}(u)=n-1$, and $G$ contains no self-loops, vertex $u$ has edges towards every other vertex in $G$. In particular $(u,v) \in E$. As a consequence $\mbox{in-deg}(v) \ge 1 \> 0$ showing that $v$ cannot be a universal source.
> 2 votes

---
Tags: graphs, directed-graphs
---


# Question
Title: Are all $\Sigma^0_1$ sets of infinite sequences infinite?
I think I figured out some things about $\Sigma^0\_1$ and $\Pi^0\_1$ in the arithmetical hierarchy, for sets of infinite sequences, and I'm hoping I can get confirmation that I'm right, or can understand the ways in which my thinking is incorrect.

What I think I have figured out is that every set of infinite sequences in $\Sigma^0\_1$ must be infinite in size--in fact uncountable--since a sentence containing only existential quantifiers over indexes into a sequence can only require that some digits satisfy a predicate. Therefore, any sequence satisfying the sentence would do because of a property of a finite number of locations in the sequence. All subsequent digits after those locations would be allowed to vary freely, in which case the number of sequences with the same initial pattern would be uncountable.

By contrast, sets of infinite sequences in $\Pi^0\_1$ may be either be finite or infinite, I think. For example:

$\\{x: (\forall n)\\, x\[n\]=0\\}$ contains only one element, $000\ldots$ .

$\\{x: (\forall n)\\, x\[n\]=0$ if $n$ is odd$\\}$ allows the digits at the even-numbered locations to vary freely, so the number of sequences that satisfy this predicate for all $n$ is uncountable.

Is this correct? Are there ways in which I'm confused, or some obvious nuance that I'm missing?

# Answer
> 2 votes
First observe that any $S \subseteq \\{0,1\\}^\mathbb{N}$ described by a $\Delta^0\_1$-formula is clopen (open and closed subset), where we topologize with the product topology. Indeed, the subbasic sets of the form $B\_{i,k} = \\{x \in \\{0,1\\}^\mathbb{N} \mid x(i) = k\\}$ are clopen by definition, and then complements (negation), finite unions (disjunction and bounded $\exists$) and intersections (conjunction and bounded $\forall$) of those are still clopen.

A $\Sigma^0\_1$ subset $S \subseteq \\{0,1\\}^\mathbb{N}$ is a countable union of $\Delta^0\_1$ sets, therefore it is open. But every open subset of $\\{0,1\\}^\mathbb{N}$ is either empty, or it contains a basic open set and is therefore uncountable.

---
Tags: computability
---


# Question
Title: Citation for finding node disjoint paths using maximum flow
We can find the maximum number of vertex disjoint paths in a directed graph using maximum flow algorithm keeping the node capacity and edge capacity to one. I could not find the reference paper for this technique. Please let me know the citation for this technique.

# Answer
This reduction appears in §4 (Menger's theorem) of ON THE MAX-FLOW MIN-CUT THEOREM OF NETWORKS, G. B. Dantzig and D. R. Fulkerson without citation to another work. It's possible that this was a reinvention, but it's not clear to me where to look next.
> 1 votes

---
Tags: network-flow
---


# Question
Title: There should be some common piece of hardware /firmware or software among different devices, isn't it?
There should be some common piece of hardware /firmware or software among different devices, isn't it? like among PCs, PlayStation, Xbox, Android phones or feature phones from pre 2008 era etc. Is there or not? like something exactly the same, some chip, transistors, anything??

# Answer
> 0 votes
All the devices you mentioned have a processor that is built using integrated chips made of silicon.

* The fundamental building block of these digital chips is the transistor. Moore's law mentions the growth rate of transistors because this is common across integrated circuits.
* Transistors are further used to build NAND gates that is used to construct logic. If you are interested in learning more about this, you can check out nand2tetris which is a course aimed at going through different levels of abstraction in modern computing starting from the very basic level

---
Tags: memory-hardware
---


# Question
Title: Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
in one of my college assignments i came up with the following recursive function which I'm ask to solve: $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

I could not use master method on it and it is not an LHR either. I assume this must have something to do with recursion tree but i cant figure the relation if so.

# Answer
> 4 votes
When $n$ is large, $T(n-\sqrt{n})$ is much larger than $T(\sqrt{n})$. Therefore, roughly speaking, $$ T(n) \approx T(n-\sqrt{n}) + \Theta(n). $$ Now let us imagine extending $T$ to all inputs, and suppose that it was differentiable. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and consequently $$ T'(n) \approx \Theta(\sqrt{n}) \Longrightarrow T(n) = \Theta(n^{3/2}). $$

Armed with this guess, let us now attempt to show that it indeed describes the order of growth of your recursion. On the one hand, unrolling $T(n) \geq \Theta(n) + T(n - \sqrt{n})$, we get $$ T(n) \geq \Theta(n + (n-\sqrt{n}) + \cdots + (n-\lfloor \sqrt{n}/2 \rfloor \sqrt{n})). $$ Here there are $\Omega(\sqrt{n})$ summands, each of which is at least $n/2$, and so $T(n) = \Omega(n^{3/2})$.

In the other direction, let us assume that $\Theta(n) \leq Cn$, and let us try to prove inductively that $T(n) \leq Kn^{3/2}$. For the inductive step to go through, we would need $$ K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2}. $$ The mean value theorem shows that for some $\theta\_n \in \[0,1\]$, $$ n^{3/2} - (n - \sqrt{n})^{3/2} = \sqrt{n} \cdot \frac{3}{2} \sqrt{n-\theta\_n \sqrt{n}} \geq \sqrt{n} \cdot \frac{3}{2} \sqrt{n - \sqrt{n}}, $$ which is at least $n$ for $n \geq 4$. Therefore for $n \geq 4$, we have $$ K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} - Kn + Kn^{3/4} + Cn. $$ For $n \geq 16$, we have $n^{3/4} = n \cdot n^{-1/4} \leq 16^{-1/4} n = n/2$, and so $$ K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} + (C-K/2)n, $$ which is at most $Kn^{3/2}$ if $K \geq 2C$.

---

More generally, similar arguments should show that if $k(n) = o(n)$ then the recurrence $$T(n) = T(k(n)) + T(n-k(n)) + \Theta(n)$$ should have the solution $$T(n) = \Theta\left(\int \frac{n\\,dn}{k(n)}\right). $$

---
Tags: complexity-theory, computability, recursion, order-theory
---


# Question
Title: Are there any functions with Big O (Busy Beaver(n))?
So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than exponentials, faster than the Aaronson sequence, and faster than a recursive use of Knuth's up-arrow notation.

This led me to a thought: are there any algorithms that grow in size with Big O (Busy Beaver(n)), aside from the Halting Problem? Is it even possible to design such an algorithm on that would run on a Turing Machine-equivalent computer?

# Answer
> 37 votes
The usual meaning of *algorithm* is *a program that always halts*. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an algorithm could be used to solve the halting problem (assuming you knew a constant $c\>0$ such that the running time is at least $c\mathit{BB}(n)$), since you could use the algorithm to get an upper bound on $\mathit{BB}(n)$.

On the other hand, *any* algorithm has a running time of $O(\mathit{BB}(n))$, precisely because the busy beaver function grows faster than any computable function.

---
Tags: algorithms, algorithm-analysis, big-o-notation, busy-beaver
---


# Question
Title: Why can't DFS be used to find shortest paths in unweighted graphs?
I understand that using DFS "as is" will not find a shortest path in an unweighted graph.

But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on the subject simply state that it cannot be done. I'm unconvinced (without having tried it myself).

Do you know any modifications that will allow DFS to find the shortest paths in unweighted graphs? If not, what is it about the algorithm that makes it so difficult?

# Answer
> 15 votes
The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored.

The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current node (from small to large). It is easy to construct a counterexample for this rule:

<sup>\[source\]</sup>

Now, that is no proof that there does not exist a strategy of choosing the next child to be investigated which will make DFS find shortest paths.

However, no matter the rule¹ you can construct graphs that have DFS commit to a long detour at the very first node, just as I did for the greedy rule. Assign edges $(s,t)$ and $(s,a)$ weights such that the rule chooses to visit $a$ first, and assign $(a,b)$ a weight greater than the one of $(s,t)$. Therefore, it is plausible that DFS can never find shortest paths (in general graphs).

Note that since you can express every (positive-integer-)weighted graph as unweighted graph -- simply replace edges with cost $c$ with a chain with $c-1$ nodes -- the same examples deal with DFS on unweighted graphs. Here, the situation is actually even more bleak: without weights, what can DFS use to determine the next child to visit?

---

1. As long as the rule is deterministic. If it is not, it can clearly not *always* find shortest paths.

# Answer
> 12 votes
*Breadth*-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS here. You can find some nice pseudo-code here.

# Answer
> 8 votes
You can!!!

Mark the nodes as visited while you are going depth and unmark while you return, while returning as you find another branch(es) repeat same.

Save cost/path for all possible search where you found the target node, compare all such cost/path and chose the shortest one.

The big(and I mean BIG) issue with this approach is that you would be visiting same node multiple times which makes dfs an obvious bad choice for shortest path algorithm.

# Answer
> 0 votes
BFS has a nice property that it will check all the edges from the root and keep the distance from the root to the other nodes as minimal as possible, but dfs simply jumps to the first adjacent node and goes depth wise. You CAN modify DFS to get the the shortest path, but you will only end up in an algorithm that be of higher time complexity or will end up doing the same thing BFS does

# Answer
> 0 votes
i think you can find the shortest path using slightly tweaked version of DFS . This is what i have came up with.

```
struct visited{
bool v;
int src;
int dest;
visited():v{0},src{INT32_MIN},dest{INT32_MIN}{
}
};
void setvisit(bool val,int src,int dest,visited & obj){
    obj.src=src;
    obj.v=val;
    obj.dest=dest;
}
bool check(visited & obj,int src,int dest,visited * v){
if(obj.v){
    if(obj.src !=src && obj.dest==dest){
        visited v1=v[src];
        if(v1.src==dest && v1.dest==src && v1.v){
            return false;
        }else{return true;}
    }else if(obj.src==INT32_MIN && obj.dest==INT32_MIN){
        return true;
    }else{
        return false;
    }
  }else{
      return true;
  }
}
void Dfs(int src,int & res,int dest,std::vector<int> g[],visited ** visit,int count){
visited *v=*visit;
for(int i=0;i<g[src].size();i++){
    if(check(v[g[src][i]],src,g[src][i],v)){
        if(g[src][i]==dest){
            res=std::min(res,count+1);
            return;
        }else{
            setvisit(1,src,g[src][i],v[g[src][i]]);
        }
        Dfs(g[src][i],res,dest,g,visit,count+1);
       }
     }
  }
int shortestPath(int src,int dest,std::vector<int> g[],int n){
   if(src==dest){return 0;}
   visited * visit=new visited[n];
   setvisit(1,src,INT32_MIN,visit[src]);
   int res=INT32_MAX;
   Dfs(src,res,dest,g,&visit,0);
   delete [] visit;
   return res;
}

```

I might be wrong but until now all the test cases i have tried it has worked. i have used these rules to make modifications in DFS

```
1. you cannot go to source again from any other edge i.e you can never travel from any other edge towards source edge.
2. if there are two edge A & B with B !=destination_edge with an undirected edge connecting them
i.e A------B then
a. if we travelled through A to B then
   a1. we cannot travel from B to A using same edge.
   a2. we can always travel from A to B again using same edge if we again somehow land at edge A.
3.  you can travel directly towards destinaton any number of times from any edge i.e A-----dest.
then you can travel towards destination from A again an again using same edge.

```

# Answer
> -3 votes
IT is possible to find the path between two vertices with the minimum number of edges using DFS. we can apply level approach

# Answer
> -3 votes
You can

just traverse the graph in dfs manner and check

```
if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

```

Here is the link for full solution

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


# Question
Title: Seeding the Mersenne Twister Random Number Generator
I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I noticed there were two ways to seed the MT: with a single integer seed or an array of integer seeds. What is the point in seeding with an array? Does it produce a better distribution or a longer period?

Also, I would appreciate it if somebody could explain to me what is meant by the "state" of the RNG, as I am seeing that word all over the source code. Is it like a finite state machine in a way?

Thanks for your time!

# Answer
> 3 votes
A random number generator has the following simplified pseudocode:

```
state S;

int random() {
  S = advance_state(S);
  return extract_integer(S);
}

```

The random number generator maintains an internal state, which in the case of MT consists of an array of words and an index. Every time you want to generate a new number, two things happen: (1) the state is modified in some devious way; (2) the state is compressed to the output word. The entire random number generator is thus a finite state machine which proceeds deterministically from state to state (there is no "input"), while also producing output.

MT is implemented slightly differently by generating several output words at once, but this is just an optimization - you can also implement it in just the way I described.

Here is a simple naive example. The internal state S is a 32-bit word. It is updated by increasing it by 1. The output is the least significant bit. If S is seeded by 0, then the first few outputs are 0, 1, 1, 0, 1, 0, 0, 1, ... (the first $2^{32}$ bits in the Thue-Morse sequence).

How does the internal state get initialized? There are two ways. One way is to give the entire internal state. The other way is to give a smaller "seed", and from the seed generating an internal state in some devious way. If we do it deviously enough, then the function associating a seed with the resulting internal state will look like a random function (in other words, it will seem as we're selecting $2^{32}$ different random internal states, when the seed is a 32-bit integer).

The cryptographic strength of the second way is only 32 bits - you only need to try all $2^{32}$ different seeds in order to complete a given sequence. If you care about that and the seed is too short for your taste, you can use the first method and come up with an entire internal state, though that's usually not necessary, and certainly isn't necessary if all you want is random numbers for simulation purposes. (If you want cryptographically secure random numbers, please don't use MT.)

Other ways of seeding a random number generator, which sit on top of these methods, include using a password or passphrase (which is converted to a seed using a hash function) and using random data from your computer (which again passes through a hash function which functions as a randomness extractor).

# Answer
> 0 votes
The answer from @Yuval is good, but does not describe TinyMT behavior and does not answer all questions, as it mostly focus on what is the state of a random number generator. You can see from https://github.com/MersenneTwister-Lab/TinyMT/blob/master/tinymt/tinymt32.c that

* An int seed will populate the state with random numbers based on this seed, using an implicit simple random number generator.
* An array of int seed will also populate the state with random numbers based on this array. The array size may be larger than the state size.

So there is no real difference between one or the other approach. Arguably, the single int seed is preferable, since the underlying algorithm to create the state is better understood/analyzed (same as Mersenne-Twister 2002).

In particular you won't have a better period or better distribution by seeding with an array.

Now to make the connection with @Yuval answer, for some random number generators, initialization with an array consisted in copying the array to the state. So you were effectively directly setting the initial state. This is dangerous for many random number generators, since then there is no guarantee that the state is properly initialized (for Mersenne Twister, it could have too many zero bits for example. More caveats @ Matsumoto *Common defects in initialization of pseudorandom number generators*).

The state is just an internal array, updated at each call to produce a next() random number.

---
Tags: algorithms, randomized-algorithms, pseudo-random-generators, random-number-generator
---


# Question
Title: Are colored graphs and red-black trees related?
I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected conceptually.

Do they have anything to do with each other?

# Answer
No. They don't have anything to do with each other.
> 2 votes

---
Tags: graphs, compilers, red-black-trees
---


# Question
Title: How do you create a sentential form in a given grammar?
I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$

I need to decide whether $aBaabda$ can be produced in the given grammar.

I am unsure how the grammar can actually be read. For example, under what circumstances can you read $abT$ in $S$? Can you skip past $aBS$ and go to $abT$ or $a$?

I understand that deciding whether $aBaabda$ can be produced is a theoretical question, so you can theoretically create anything as long as its within the bounds/rules of a language. But I don't *fully* understand the rules of producing a sentential form.

And on not understanding rules fully: can you stop reading input on a *non-terminal*? It's name, of course, implies not. For example, without creating a derivation tree can you tell that something like $aaaabdaaaaBS$ or $aabdaB$ can't be made because it ends in a non-terminal? Except, writing this I realised that a non-terminal such as $B$ has ϵ, so that implies you can end on $B$, right?

Or can you end simply when you have matched a sentential form? For example, if you create a derivation tree and have a node for $S$, do you **have** to carry on reading or can you simply end?

# Answer
If you know how to decide whether a word belongs to the language generated by a grammar, then you can extend this to sentential forms, in the following way. For each nonterminal $A$, add a new terminal $\mathbf{A}$. Add rules $A \to \mathbf{A}$. Given a sentential form, replace each nonterminal $A$ with the terminal $\mathbf{A}$. Now ask whether the resulting word belongs to the language generated by the augmented grammar.

As an example, your grammar turns to \begin{align} S &\to aBS \mid abT \mid a \mid \mathbf{S} \\ T &\to d \mid dT \mid \mathbf{T} \\ B &\to da \mid \epsilon \mid S \mid \mathbf{B} \end{align}

The original grammar generates $aBaabda$ iff the augmented grammar generates $a\mathbf{B}aabda$.
> 1 votes

---
Tags: finite-automata, formal-grammars, compilers, nondeterminism
---


# Question
Title: How to iterate the Hardy-Ramanujan integers quickly
The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:

$$ \begin{array}{lll} 1 & = & 1\\ 2^1 & = & 2\\ 2^2 & = & 4\\ 2^1 \times 3^1 & = & 6\\ 2^3 & = & 8\\ 2^2 \times 3^1 & = & 12\\ 2^4 & = & 16\\ 2^3 \times 3^1 & = & 24\\ 2^1 \times 3^1 \times 5^1 & = & 30\\ 2^5 & = & 32\\ 2^2 \times 3^2 & = & 36\\ 2^4 \times 3^1 & = & 48\\ 2^2 \times 3^1 \times 5^1 & = & 60\\ \vdots \end{array} $$

As you can see, the exponents don't really follow much of an order that I can see. I thought perhaps the exponents increased in some way, but we have $288 = 2^5 \times 3^2$ shortly followed by $480 = 2^5 \times 3^1 \times 5^1$.

Is there a method to iterate these integers quickly?

I can only see a simple way of listing all of them below some upper bound $u$. I find the maximum exponent for $2$ by $\lfloor \log\_2(u) \rfloor$, find the maximum # of primes, and iterate all decreasing sequences of exponents $\leq \lfloor \log\_2(u) \rfloor$.

# Answer
> 3 votes
I'm very happy that the site linked me to How can I generate first n elements of the sequence 3^i * 5^j * 7^k?. It was a critical stepping stone, which enabled me to solve my own question after lots of thinking.

---

First I want to elaborate on that answer a bit, as it took me a while to understand and code it.

We want to iterate $3^i 5^j 7^k$.

The next element must be one of $3 x, 5 y, 7 z$, where $x, y, z$ is a previous number in the sequence. This is because $x \< 3 x, y \< 5 y, z \< 7 z$, and $3 x, 5 y, 7 z$ satisfy the constraints.

For $x$, we start with the first element in the sequence. We increment it's position whenever $3 x$ is the smallest out of $3 x, 5 y, 7 z$. To see why, we've already included $3 x$ in the sequence, for all $x$s in the sequence so far. So the only possible $3 x$ that can be inserted in the sequence, is if $x$ is the new element we just inserted.

Similarly for $y$ and $z$.

The following code iterates this sequence:

```
def main():
    x = 1
    y = 1
    z = 1
    S = []
    x_iter = iter(S)
    y_iter = iter(S)
    z_iter = iter(S)
    for _ in range(20):
        m = min(3 * x, 5 * y, 7 * z)
        S.append(m)
        if m == 3 * x:
            x = next(x_iter)
        if m == 5 * y:
            y = next(y_iter)
        if m == 7 * z:
            z = next(z_iter)
    print(S)

```

---

The *Hardy-Ramanujan Integers* can be defined as the integers $2^{e\_1} 3^{e\_2} 5^{e\_3} \cdots$, s.t. $e\_1 \geqslant e\_2 \geqslant e\_3 \geqslant \cdots \geqslant 0$.

It seems that these two problems are related, and indeed they are the same, if we re-write the *Hardy-Ramanujan Integers* by removing the decreasing exponents constraint, as $2^{e\_1'} (2^{e\_2'} 3^{e\_2'}) (2^{e\_3'} 3^{e\_3'} 5^{e\_3'}) \cdots$.

Now the only issue is that compared to the previous problem, our list of bases is infinite. But note that a new prime $p$ can only be included in the sequence, if it's smallest form, $2^1 3^1 \cdots p^1$, is less than the next sequence element, produced with primes $\< p$. So we only need to introduce a new prime when this occurs.

Before this occurs, The exponent of $p$ is 0. Any prime $\> p$ will give a sequence element bigger than $2^1 3^1 \cdots p^1$, so does not yet need to be considered.

This gives the following code:

```
import math

from sympy import nextprime

def main():
    S = [1]
    primes = [2]
    next_prime = nextprime(primes[0])
    # The smallest Hardy-Ramanujan integer that includes `next_prime`
    next_prime_product = primes[0] * next_prime
    candidates = [1]
    candidate_S_indexes = [0]
    for _ in range(20):
        m_options = [
            math.prod(primes[:i + 1]) * candidate
            for i, candidate in enumerate(candidates)
        ]
        m = min(m_options)
        if next_prime_product < m:
            # Add a new prime & candidate
            m = next_prime_product
            primes.append(next_prime)
            next_prime = nextprime(next_prime)
            next_prime_product *= next_prime
            candidates.append(m)
            candidate_S_indexes.append(len(S))
        S.append(m)
        for i, m_option in enumerate(m_options):
            if m_option == m:
                candidates[i] = S[candidate_S_indexes[i] + 1]
                candidate_S_indexes[i] += 1
    print(S)

```

---

P.S. I saw some answer in Haskell in German before at:

but could not understand the German at all, nor the Google-translated version, nor the Haskell code. But I'm quite satisfied with my algorithm here. It feels pretty optimal.

# Answer
> 1 votes
For a prime p, let hm(p) be the sequence of Hardy-Ramanujan numbers with no prime factor greater than p.

hm(2) is the sequence 1, 2, 4, 8, 16, 32 etc.

hm(3) is created by merging hm(2) and 6 x hm(3).

hm(5) is created by merging hm(3) and 30 x hm(5)

and so on. The numbers up to 210-1 are in hm(5), the numbers up to 2310-1 are in hm(7), the numbers up to 30,030-1 are in hm(11) etc.

---
Tags: algorithms, number-theory, enumeration, iteration
---


# Question
Title: An algorithm to find the closest match between 2 arrays of RGB pixel tuples
So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.

Suppose we have 2 arrays of `RGB` pixel tuples-

A -\> `{(56, 39, 75), (125, 222, 32), (156, 201, 102)}`

B -\> `{(125, 195, 93), (53, 31, 67), (118, 219, 48)}`

I'd like the sort the second array in such a way that **for each index** of the 2 arrays, the corresponding RGB tuple pairs have the **least deviation** in value such that the **optical difference** between the 2 tuples is **imperceptible** to the human eye. For example, the difference between (122, 36, 18) and (126, 31, 25) is imperceptible, this is what we want.

For the example arrays A and B, I think sorting B like so will keep the arrays as optically identical as possible- `{(53, 31, 67), (118, 219, 48), (125, 195, 93)}`

# Constraints

* Both arrays are of same length
* The RGB pixel tuples themselves **must** remain unchanged, only their order in the array should be changed.
* The first array must remain unchanged, only the second should be sorted accordingly
* There may not be *enough* **optimal elements** in the second array to provide a perfect/good match, in this case *the least amount of sacrifices will be preferred.* The end goal is for the new pixel array to be as identical to the original array as possible. The least amount of sacrifices will ensure that the arrays of pixels, when turned into a picture, will look as identical as possible. **Note**: By the word "sacrifice", I mean when the deviation in 2 pixel tuples is enough for the human eye to notice a difference.

# Answer
> 1 votes
You can't satisfy both goals. Suppose $A=\[10,20,30\]$ and $B=\[10,20,30\]$; then you presumably want the modified $B$ to be $\[10,20,30\]$. Now suppose $A=\[10,20,30\]$ and $B=\[10,30,20\]$; then you presumably want the modified $B$ to be $\[10,20,30\]$. The original A and the modified B are the same in both cases, so there is no way to tell from them what the original $B$ was (both remain a possibility).

# Answer
> 1 votes
The question in its current form has a simple answer: This is an instance of the Assignment Problem, or equivalently of finding a minimum-weight matching in a bipartite graph.

1. Decide on a cost function $f(x, y)$ to measure the dissimilarity between two given RGB tuples $x$ and $y$ -- that is, this function should assign identical RGB tuples a cost of zero, and the more dissimilar two RGB tuples are, the higher the cost they should be assigned. (E.g.: Euclidean distance, or maximum absolute difference of the 3 components.)
2. Construct a complete bipartite graph with a vertex in part A for each element in array A, a vertex in part B for each element in array B, and an edge of weight $f(A\[i\], B\[j\])$ between the $i$-th vertex in part A and the $j$-th vertex in part B.
3. Use one of the algorithms for solving the Assignment Problem (these include the Hungarian algorithm, which will take $O(n^3)$ time in this case, and linear programming) to find an optimal matching (subset of edges such that each vertex is incident on at most one edge).
4. Loop through the vertices in part A: For the $i$-th A-vertex, read off the vertex it is matched with in part B to determine what element to put in $B\[i\]$.

---
Tags: algorithms, sorting, image-processing, matching
---


# Question
Title: How to understand the solution to Task Scheduler problem on LeetCode?
LeetCode Task Scheduler problem is the following:

> Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
>
> Return the least number of units of times that the CPU will take to finish all the given tasks.

> Example 1:
>
> Input: tasks = \["A","A","A","B","B","B"\], n = 2
>
> Output: 8
>
> Explanation:
>
> A -\> B -\> idle -\> A -\> B -\> idle -\> A -\> B There are at least 2 units of time between any two same tasks.

> Example 2:
>
> Input: tasks = \["A","A","A","A","A","A","B","C","D","E","F","G"\], n = 2
>
> Output: 16
>
> Explanation:
>
> One possible solution is A -\> B -\> C -\> A -\> D -\> E -\> A -\> F -\> G -\> A -\> idle -\> idle -\> A -\> idle -\> idle -\> A

This is a solution I found:

```
    def leastInterval(self, tasks: List[str], l: int) -> int:
      freq = [0]*26
      maxOccurrence = 0

      for task in tasks:
        freq[ord(task) - ord('A')] +=1

      freq.sort(reverse=True)

      idleBlocks = freq[0] - 1
      idlesState = idleBlocks * n

      for i in range(1, 26):
        idlesState -= min(freq[i], idleBlocks)

      return len(tasks) + max(0, idlesState)

```

Basically, it works like this:

Given the tasks `["A","A","A","A","A","A","B","C","D","E","F","G"]`

1. Sort the tasks by frequency descendingly

`{ A: 6, B: 1, C: 1, D: 1, E: 1, F: 1, G: 1 }`

2. We first place the most frequent character. All the spots between the same characters are first idle.

`A _ _ A _ _ A _ _ A _ _ A _ _ A`

3. We try to fill the remaining characters in the idleSpots using the sorted task array. (most frequent filled first)

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

4. If the idleSpots \< 0, we return the total number of tasks, else we return the total number of tasks + idleSpots.

I'm having issues proving this statement:

`If the idleSpots < 0, we return the total number of tasks.`

In other words, if we manage to fill all the idle spots between the most frequent character, why are we sure to complete all the tasks without complimentary idle tasks?

How come we can't we end up with a case like this

`A X X A X X A B _ _ B _ _`?

Where X represents a character such that the idle spots between all the As are filled.

Can you give me some hints?

# Answer
> 3 votes
When `idleSpot` (or, as in the code, `idleState`) is zero or negative, it means we have enough tasks other than `A` to fill the required **minimum** cooldown periods between `A` tasks.

Well, suppose `BB` are the overflowing tasks. Instead of appending them to the end of scheduling queue, we can just insert them, one right after each `A`. So instead of
$\quad$`A X X A X X A B _ _ B _ _`
we will have
$\quad$`A B X X A B X X A`.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between `B`s are as long as the cooldown periods between `A`s, so they are no shorter than the minimum as well.

If we have addition overflowing tasks, such as `CC`, then we can do the same thing, inserting them one right after each `A`. So we would have
$\quad$`A C B X X A C B X X A`.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between `C`s are as long as the cooldown periods between `A`s, so they are no shorter than the minimum as well.

And so on.

---
Tags: optimization, correctness-proof, greedy-algorithms
---


# Question
Title: How to represent zero as floating point number?
For the floating-point number, we have the form $\pm d\_0.d\_1d\_2···d\_{P-1}\times\beta^E$

* $\pm$ --------------------------- sign
* $d\_0.d\_1d\_2···d\_{p-1}$ --------- significant
* $\beta$ ---------------------------- base (int) $0\le d\_i\lt \beta$ are the significant digits
* $P$ ---------------------------- precision (int) specifies number of digits carried -\> controls accuracy
* $E$ ---------------------------- exponent (int) $L\le E\le U$
    + $L$ -- lower
    + $U$ -- upper

For example, suppose $F(10,3,-10,10)$

$4.00\times10^5$ represents the number $400000$

But how are we going to represent $0$ in such case?

Are we going to give $0$ directly or $0.00\times10^0$?

# Answer
**Note:** In the interest of making this somewhat self-contained, I am using terminology from the most recent versions of the IEEE-754 standard. Prior to 2008, "subnormal numbers" were called "denormal numbers", and "binary32" was called "single precision". Some textbooks/papers/etc may use the old terms.

The representation that you are talking about here is called, in IEEE-754, normal numbers. A normal number is one which has a single nonzero digit on the left-hand side of the radix point (i.e. decimal point or binary point) of its mantissa.

The representation for zero uses a slightly different representation, namely, subnormal numbers.

Taking binary32 as our example, there are three fields:

* The *sign bit*, which is 1 bit in size.
* The *exponent field*, which is 8 bits in size.
* The *significand field*, which is 23 bits in size.

The sign bit is `0` if the number is positive, and `1` if it is negative.

There are 8 bits reserved for the exponent field, so we can store a number between 0 and 255. We encode the exponent with with a bias of 127, using only the range of -126 to 127 for normal exponents.

The significand field is used to store the mantissa. In binary, the only nonzero digit is 1, so it is not stored explicitly in the IEEE-754 representation of normal numbers. So, for example, to represent the number $3$, we first express it in normal form:

$$+1.1\_2 \times 2^1$$

The sign bit is `0` (because the number is positive). The exponent field is $1 + 127$, the true exponent plus the bias, which is `10000000` stored as a bit field.

The mantissa is $1.10000000000000000000000\_2$. In normal form, the digit before the binary point is always $1$, so we don't store it, giving `10000000000000000000000` for the significand field.

The reason for the distinction between "mantissa" and "significand" is because the mantissa is the true mathematical mantissa of the number, but the "significand" is only the bits that we need to store.

Using this biased representation for the exponent gives us two bit patterns that we didn't use: `00000000` and `11111111`.

The "all ones" pattern is used for values that are not finite numbers: infinity and NaN ("not a number"). I won't talk further about these here.

The "all zeroes" pattern is used for subnormal numbers. What it means is that the mantissa is the significand field with an implicit zero before the binary point, and the exponent is fixed to be -126. So, for example, if the sign bit is zero (positive), the exponent field is all zeroes, and the significand field is `10000000000000000000000`, then this represents the number:

$$+ 0.10000000000000000000000\_2 \times 2^{-126} = 2^{-127}$$

By setting the sign bit, the exponent field and the significand field to all zeroes, this gives us a representation for zero. Plus, it's the most desirable representation as far as programmers are concerned: if you have zeroed-out memory (all of the bits are set to zero) and read it as a floating-point number, it means zero.

There is also a representation here for negative zero. This is by design, but the reasoning behind it is beyond the scope.

Now this is all binary, and you are asking about decimal. IEEE-754 also defines a decimal floating point format, with two different binary encodings. While the exponent is always base-10, the mantissa/significand field can be either binary or densely packed decimal. The idea is still the same. One exponent value is reserved, and zero is represented using that special value.
> 4 votes

---
Tags: floating-point, numerical-analysis
---