# Question
Title: Maximise the value of the minimum weight intra edge
I've been doing review problems for a midterm and I came across this one problem that I haven't been able to solve. The problem essentially says that given a **complete** graph $G=(V,E)$ partition the vertices into two subsets $A$ and $B$ such that weight of the smallest intra edge (i.e. an edge $e=(u,v)$ such that $u$ and $v$ belong to the same subset) is maximized. The graph has $n$ vertices and $k$ weighted edges.

The edges with no weight can be assumed to have infinite weight. The required runtime is $O((n+k) \log k)$.

I thought of this in two ways:

1. Arrange the edge weights in increasing order and for every edge $(u,v)$, place $u$ and $v$ in different subsets.
2. Arrange the edge weights in decreasing order and for every edge $(u,v)$, place $u$ and $v$ in the same subset until all the vertices have been placed in some subset.

The second approach doesn't work because there could be a smaller edge among two vertices in the same subset.

Could someone please help me with this?

# Answer
Let $G=\left(V, E=\binom{V}{2}\right)$ be your input graph, let $n=|V|$, and call $w(u,v)$ the weight of edge $(u,v) \in E$. Let $x^\* = \max\_{A, B} \min\_{ (u,v) \in A^2 \cup B^2} w(u,v)$ be the value of an optimal solution to your problem (here $A \cup B = V$ and $A \cap B = \emptyset$).

Suppose that you have a guess $x$ on the value of $x^\*$ and let $D\_x$ be the set of all edges of weight smaller than $x$. Consider the graph $G'=(V, D)$.

If $G'$ is bipartite, then the two sides of a bipartition will give you a partition of $V$ such that every intra-edge has weight at least $x$. This shows that $x \le x^\*$.

If $G\_x$ is not bipartite then, for every partition $A,B$ of $V$, you have $D\_x \setminus (A \times B) \neq \emptyset$. Since the same must hold for every $x' \ge x$ (since $D\_{x'} \supseteq D\_x$) this shows that no partition of $G$ can have a measure of at least $x$. I.e., $x \> x^\*$.

You can then sort the set $W=\\{w(u,v) \mid (u,v) \in E\\}$ of all edge weights and binary search for the value of $x^\* \in W$. The binary search will require at most $O(\log n)$ iterations, and each iteration requires time $O(n^2)$ to check whether $G\_x$ is bipartite.

The overall running time is then $O(n^2 \log n)$.

---

If the edges are already sorted by their weight, or if the edge weights are polynomially bounded (w.r.t. $n$) you can improve the above time complexity by a factor of almost $\Theta(\log n)$.

Indeed, if you have already conducted a bipartiteness test on $G\_x$, and $G\_x$ was bipartite, and then you are asked to determine whether $G\_{x'}$, with $x' \> x$, is bipartite there is no need to check all edges in $D\_{x'}$. Indeed, you can get away with only checking the edges in $\Delta(x, x') = D\_{x'} \setminus D\_{x}$.

The idea is as follows: maintain a disjoint-set (union find) data structure $U$ on the vertices of $V$, such that if $u,v \in V$ belong to the same set in $U$, then they **must** also belong to the same side of the bipartition of the last tested graph $G\_x$.

To be more precise: $U$ will contain one set $S$ for each isolated vertex of $G\_x$ and two sets $S\_1, S\_2$ for each connected component $C$ of $G$ with at least $2$ vertices, where $S\_1, S\_2$ are the unique bipartition of $G$. It is also convenient to store, for each set $S\_i$ in $U$, the name $\eta(S\_i)$ of the set corresponding to the other side of the bipartition. Namely, $\eta(S\_1) = S\_2$ and $\eta(S\_2)=S\_1$. If $S$ is a singleton set, then $\eta(S)$ is undefined.

Initially $x=0$ (assuming w.l.o.g. that all edge weights are non-negative) so $D\_0 = \emptyset$ and $U$ contains $n$ singletons.

A bipartitness check on $G\_{x'}$ can be done as follows: For each edge $(u,v) \in \Delta(x, x')$ query $U$ to find the sets $S\_1,S\_2$ such that $u \in S\_1$ and $v \in S\_2$. We distinguish some cases:

* **Case 1:** $S\_1 = S\_2$. In this case $G\_{x'}$ cannot be bipartite since we already know that $u$ and $v$ must be on the same side of the bipartition.
* **Case 2:** $S\_1 \neq S\_2$, $\eta(S\_1)$ is defined, and $\eta(S\_1)=S\_2$. In this case $(u,v)$ connects two vertices in different sides of the bipartition of an already existing connected component. Do nothing.
* **Case 3:** $S\_1 \neq S\_2$ and $\eta(S\_1)$ is either undefined or $\eta(S\_1) \neq S\_2$. In this case we just discovered an edge across different connected components. Perform a union operation between $\eta(S\_1)$ and $S\_2$ and let $S'$ be the resulting set (if $\eta(S\_1)$ is undefined then $S' = S\_2$). Perform a union operation between $\eta(S\_2)$ and $S\_1$ and let $S''$ be the resulting set (if $\eta(S\_2)$ is undefined then $S'' = S\_1$). Set $\eta(S') = S''$ and $\eta(S'')=S'$. See the figure for an example.

If all edges in $\Delta(x, x')$ are processed without ever encountering case 1, then $G\_{x'}$ is bipartite.

The final algorithm checks whether $G\_x$ is bipartite for $x \in W$ in order, until $G\_x$ becomes not bipartite. Then it returns the predecessor $y$ of $x$ in $W$. The actual partition of $V$ can be found using standard techniques (the laziest one is to find a bipartition of $G\_y$ from scratch).

All the sets $\Delta(x, x')$ can be found in time $O(n^2)$ once $E$ is sorted w.r.t. $w(\cdot)$ (if $E$ is not already sorted we can use radix sort and the fact that the weights are polynomially bounded). Moreover, the number of find operations is $O(n^2)$ and the number of union operations is $O(n)$. Thus the overall required time $O(n^2 \alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.

Notice that $\Omega(n^2)$ is a trivial lower bound for your problem.
> 2 votes

# Answer
As I mentioned in the comments, the algorithm could be like this:

1. Sort the $k$ edges in $k \log k$ time and notice that $n$ doesn't really factor into the running time.
2. Iteratively add one and one edge (from small to large).
3. If an edge causes an *odd cycle*, you output the value of that edge, the rest of the graph can be partitioned arbitrary.

A graph is bipartite if and only if there are no odd cycle, so in step 2 you are iteratively building a bipartite graph. How do you quickly build up a bipartite graph?

Using Union find, you can merge components one component at a time, and you need to keep track of each vertex in a component whether it is "red" or "blue". However, you need to be able to flip all colors in a component in $O(1)$ time, which should be kept as a flag in the root of a component.

Therefore, once you add an edge within a component between two vertices of the same color, you are done.

All in all, this should be doable in $O(k \log k)$ time.
> 2 votes

---
Tags: weighted-graphs, partitions
---


# Question
Title: How do I compute the power consumption of a DRAM refresh?
Given a DRAM-based memory system with a total capacity of $x$ bytes, $y$ DRAM rows and a refresh time of $t$ milliseconds, how do I compute the power consumption for one DRAM refresh? I couldn't find something concerning this question so far.

# Answer
> 0 votes
$P = I \cdot \Delta V$, meaning one has to find the current consumption $I$ and the difference in voltage $\Delta V$, often denoted by $V\_{dd}$ of the respective DRAM, in this case one can choose an arbitrary DRAM since nothing is specified.

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: Karatsuba multiplication on numbers with odd length
I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length.

Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.

The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?

Later in the algorithm I have to multiply $((a\_1 + a\_0) \cdot (b\_1 + b\_0) - (a\_1 \cdot b\_1) - (a\_0 \cdot b\_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?

# Answer
> 5 votes
Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m \< n$. With $m = 2$ :

$a = 2 * 10^2 + 34$ and $b = 8 * 10^2 + 57$ ; thus, $a\_1 = 2$, $a\_0 = 34$, $b\_1 = 8$ and $b\_0 = 57$.

It follows that $ab = z\_2 B^{2m} + z\_1 B^m + z\_0$ where $z\_2 = a\_1 b\_1 = 16$, $z\_1 = a\_1 b\_0 + a\_0 b\_1 = 386$ and $z\_0 = a\_0 b\_0 = 1938$.

Thus, $ab = 16 \cdot 10^{2\*2} + 386 \cdot 10^2 + 1938 = 200538$.

I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).

# Answer
> 0 votes
You can add a zero to X and Y Eg : 729*784 change it into 7290*7840.then apply the algorithm . Then at last remove the two zeros. You are now left with X\*Y

---
Tags: multiplication
---


# Question
Title: How to prove the language of contractible strings is context-free but not regular?
How to prove this language is context-free but not regular? I can't figure out it.

> A string is **contractible** if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of consecutive identical symbols.
>
> For example, $abaaababb$ is contractible as witnessed by the following sequence of contractions,
> $$ab\underline{aaa}babb \rightarrow abba\underline{bb}\rightarrow a\underline{bb}a \rightarrow \underline{aa}\rightarrow \epsilon$$
>
> Let $L$ be the language of contractible strings over the alphabet ${a, b}$. Prove that $L$ is a context-free language and that $L$ is not a regular language.

# Answer
> 2 votes
For $i \ge 0$ consider the word $x\_i = (ab)^i$. For $0 \le i \< j$, $(ba)^i$ is a distinguishing extension for $x\_i$ and $x\_j$. Indeed $x\_i(ba)^i \in L$ but $x\_j(ba)^i \not\in L$. By the Myhill–Nerode theorem $L$ is not regular.

Given a non-empty word $w \in L$, $w$ can be written as $\alpha\_1 \alpha\_2 \dots ... \alpha\_k$ where (i) each $\alpha\_i$ is a non-empty contractible string that starts and ends with the same symbol, and (ii) the first symbol of $\alpha\_{i+1}$ differs from the last symbol of $\alpha\_i$.

Each $\alpha\_i$ starting with some symbol $x$ can be written, in turn, as $x \beta\_1 x \beta\_2 \dots \beta\_h x$, where $h \ge 1$, all $x$ are exactly the characters removed in a single contraction step, and all $\beta\_i$ are (possibly empty) substrings that are contracted before contracting $x$. It follows that each non-empty $\beta\_i$ must start and end with the unique symbol in $\\{a,b\\} \setminus \\{x\\}$.

Consider hen the following context-free grammar $G$, in which $A$ (resp $B$): generates a contractible string starting and ending with $a$ (resp. $b$):$$ S \to \varepsilon \mid S' \mid S''\\ S' \to A \mid AB \mid ABS' \\ S'' \to B \mid BA \mid BAS'' \\ A \to aa \mid aBa \mid aA \mid aBA \\ B \to bb \mid bAb \mid bB \mid bAB $$

The above observations imply that $L(G) \supseteq L$, while a parse tree for $w$ (according to $G$) provides a sequence of contraction for $w$, showing that $L(G) \subseteq L$.

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


# Question
Title: Computationally and memory efficient algorithm for a relatively simple problem
Given a list of non-overlapping ranges and values, i.e. `[(0, 5, 0.5), (10, 15, 1.1), ...]`, and a list of potentially overlapping ranges (*bins*), i.e. `[(0, 10), (5, 15), (0, 5), ...]`, find the average, min, max, standard deviation of the bins.

For example, the answer for averages would be `[0.25, 0.55, 0.5, ...]`. Assume there is a implicit range `(5, 10, 0)` in the first list.

The max range is from 1 to 109. The number of *bins* ranges from 1 $\le$ n $\ge$ 1010.

What is a memory and computationally efficient way of solving this problem?

Edit: The first list of non-overlapping ranges would create a list: `[0.5, 0.5, 0.5, 0.5, 0.5, 0, 0, 0, 0, 0, 1.1, 1.1, 1.1, 1.1, 1.1, ...]`. A pair in the second list would specify the indices of the range to find a statistic. The average for the first pair, `(0, 10)`, would be `(0.5 * 5 + 0 * 5) / 10 = 0.25`.

This is an actual problem in bioinformatics, and an algorithm already exists here, but I was wondering if there was a potentially better one.

# Answer
> 1 votes
I don't know what algorithm they use so I don't know whether this will be better, but there is an efficient algorithm for your problem, by using a tree. Form the list of all endpoints of all ranges and bins, and sort it. This partitions the real line into non-overlapping intervals, where each bin is a union of intervals that don't overlap.

Put those endpoints into a binary search tree. Each internal node in the binary tree represents a union of those intervals. You can store, in each tree, the min, max, sum, and sum of squares of all values in that interval, filling these in bottom-up. Note that given these statistics for the two children of a node, it is easy to compute these statistics for the node itself in $O(1)$ time.

This yields an $O(n \log n)$ time algorithm, where $n$ counts the number of ranges + number of bins. It takes $O(n \log n)$ time to sort the endpoints, then $O(n)$ time to build the binary search tree, then $O(n)$ time to fill in each node bottom-up.

You might also enjoy reading about interval trees and segment trees, if you do a lot of computation on ranges/intervals.

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


# Question
Title: Finding numbers near the median in linear time
Problem:

Describe (English is enough) a linear algorithm that, given a set $S$ of $n$ distinct numbers and a positive integer $k \leq n$, returns the $k$ numbers in $S$ that are closest to the median of $S$.

Answer:

I interpret the term linear algorithm to mean one that runs in $O(n)$ time. It is not clear to me if that means worst case or average case. I would tend to think worst case. \newline I claim that problem may not have a unique solution. For example, if we are given $S = \\{ 1, 2, 3, 4, 5 \\}$ and $k = 2$ then we have the following two valid solutions: \newline $S = \\{ 2, 3 \\}$ and $S = \\{ 3, 4 \\}$. Here is my algorithm, which I do not believe meets the performance requirements of the question:

```
Let ans be the set of numbers we want to return.
Compute the median of S and call that value m.

Initialize the set ans to the first k elements of S.
// One data structure to hold ans would be an array. A better choice might be
// a binary tree / heap.
for i = k+1 to n (inclusive)
       if S[i] is closer to the median then the element of ans that is farthest
            away from the median then
                update ans by replacing that element with S[i]
       end if
end for
return ans

```

I am assuming that we can find the median in $O(n)$ time. Depending on the data structure chosen for ans, the running time for the code will be $O( n \log k )$ which is linear in $n$. This does not seem right to me. Is it? If it is wrong, where did I go wrong?

Does this problem even have a valid solution?

# Answer
There is an algorithm that finds the $\ell$-th smallest element in an array of length $n$ in time $O(n)$. You can find the $(n-k)/2$-th smallest and the $(n+k)/2$-th smallest elements in $O(n)$ using this algorithm, and then, using an additional pass, find all elements in between.
> 3 votes

---
Tags: algorithms, sorting
---


# Question
Title: What is beta and k parameter in Incremental Decision Tree
I have read this paper https://arxiv.org/pdf/1803.03674v1.pdf for outlier detection problem with real data (online training)

In this paper, the authors used Incremental Decision Tree to build subspaces (nodes in tree) by 2-mean method. The problem is in the algorithm 2 (build tree in paper), the condition (line 22): if t = beta power k. with t is the round observations (maybe each round we observe one sample) the splitting is performed.

The question is: What is beta and k? I spent a lot of time thinking about this. In the experiment you can see the authors plot chart describe splitting space process. At round 5, 11, 40? These are t (in my understanding) 5 can't be a result of any number power any number.

Thanks you.

# Answer
> 0 votes
It appears that $\beta$ is a constant, and $k$ ranges over the integers. See paragraph 3 of Section IV.B.

Line 1 of Algorithm 2 tells you that $\beta$ is a parameter: it says "Select parameters $\beta$ and ..." Based on the body text in Section IV.B, presumably "if $t= \beta^k$" means "if there exists $k \in \mathbb{N}$ such that $t=\beta^k$".

---
Tags: algorithms, machine-learning, decision-tree
---


title: Index variable takes up log(n) space?

text:
# Question
Title: Index variable takes up log(n) space?
In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits." How does an array index requires log n bits? For example, A\[0\], 0 here just take O(1) bits, right? It is just 1 number.

I guess my question is about how an array establish its index. An array of size n has n space for its elements, and n space for storing the index numbers 0,1,2... I assume I am wrong, but I don't know how.

# Answer
> 5 votes
If you have a variable $x$ that can represent any number from $0$ to $n-1$ (or any value from a set of of $n$ possible values, really), such an the index of an array of $A\[0 \dots n-1\]$ of $n$ elements, then $x$ needs to use at least $\lceil \log\_2 n \rceil = \Omega(\log n)$ bits.

This is because there are $2^b$ combinations for the values of $b$ bits. Then, to represent $n$ values you need to have $2^b \ge n$, i.e., $b \ge \log\_2 n$. You can add the ceiling since $b$ must be an integer.

When you say "an array of $n$ elements uses $O(n)$ space" you are probably thinking of a word-RAM model. Here the memory is split into addressable *words*, i.e., groups of $w$ bits. Each entry in the array occupies one (or a constant number of) words of memory (this also means that the elements in the array can't represent more than $2^{\Theta(w)}$ values each).

Usually the word size $w$ is chosen to be $\Theta(\log n)$, where $n$ is some natural parameter of the input problem (e.g., the size of the instance). In this case an index of an array of $n$ elements can be stored into a single memory word, i.e., in $O(1)$ space.

However this is **not** contradicting the above lower bound of $\lceil \log\_2 n \rceil$ bits, it's just that these bits are all packed into a single (or into a constant number of) memory word(s).

---
Tags: arrays, space-analysis, in-place
---


# Question
Title: Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n
The Question of the CLRS $6.1-7$ exercise reads as:

> > Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n⌊n/2⌋+1,⌊n/2⌋+2,…,n$.

I looked for the solution here: https://walkccc.github.io/CLRS/Chap06/6.1/

The solution was provided like this:

Let's take the left child of the node indexed by $\lfloor n / 2 \rfloor + 1.$

\begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & \> 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned}

I can't understand this statement: $LEFT(⌊/2⌋+1) \> 2(/2−1)+2$

Please help me out. Thank you.

# Answer
> 1 votes
So, basically in heap representation, $LEFT(i)$ refers to the index of $i's$ left child. What we want to show is that index $⌊/2⌋+1$ is a leaf and is not a middleware node which can be proved if we could show the index of the left child is larger than the number of elements in the heap.

On the other hand, $LEFT(⌊/2⌋+1) = 2(⌊/2⌋+1) = 2⌊/2⌋+2 $ and with removing those brackets around the $n/2$ we can show that it is larger than $2(n/2-1)+2 = n$.

# Answer
> 0 votes
It's mathematical ture that

```
floor(n/2) > n/2 - 1

```

Maybe rearrange the equation can help understanding the question.

```
Left[floor(n/2) + 1]
=   2 * (floor(n/2) + 1)
>   2 * (n/2 - 1 + 1)
=   2 * n/2
=   n

```

---
Tags: algorithms, heap-sort
---


# Question
Title: Regular set of the "does not contain" kind
Given a language $L$ and a set of strings $\Sigma^\* = \\{0, 1\\}^\*$, how can I find a regular set that expresses

$L = \\{ w \in \Sigma^\* \mid w$ ends with $00$ and does not contain $11\\}$?

Well, the part that states that w must end with 00 is easy and I (think I) managed to find the regular set for it. But I can't modify it so that w won't contain 11.

I didn't find many articles about this subject on the internet, and the ones I did didn't help me much in this "does not contain" kind of problem. So it'd help a lot if you guys could mention some articles on regular sets to me.

# Answer
If a string doesn't contain $11$, then any $1$ is followed by $0$, unless it is the final $1$ in the string. Therefore you can break the string up into pieces of the forms $0,10,1$, the last one appearing only at the very end. This leads to the following regular expression for the set of binary strings excluding $11$: $$ (0+10)^\*(\epsilon+1). $$ If we furthermore want the string to end with $0$, then we have no terminal $1$. On the other hand, we also want to disallow the empty string. Altogether, we get $$ (0+10)^+. $$ A similar case analysis leads to a regular expression for your language. Details left to you.
> 1 votes

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


title: Maximal prefix codes and maximal length

text:
# Question
Title: Maximal prefix codes and maximal length
Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true that $X’ = X$? In other words, why is it true that one cannot obtain a maximal prefix code from another maximal prefix code with same maximal length by changing only the words of maximal length? Any reference for this result?

# Answer
I'll assume that a prefix code is a set of words in which no word is the prefix of any other, and "maximal" means it is impossible to add any word to the set and keep this property.

Let $w$ be a maximal-length word that is not in $X$. There are two possibilities:

* At least one (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could not add $w$ even if we first remove all words in $F$ from $X$;
* No (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could add $w$ to $X$ without needing to first remove any words in $F$, contradicting the assumption that $X$ is maximal.
> 1 votes

---
Tags: information-theory, coding-theory, word-combinatorics
---


# Question
Title: Formal Logic - Natural deduction: Problem with assumptions about exists-negation
I'm stuck on how to progress with this proof, despite I have tried, I cannot see the next move.

Given this proof without predicate:

**So far what I've accomplished:**

My idea is, as I can't see any other option using `(-(Sv(P->Q))` as the first assumption in order to introduce a conditional, so the assumption must end in `P ^ -Q ^ -S`. As you can see I have obatined `-Q and -S` but, **how do I proof `P`?**

# SOLUTION:

# Answer
> 2 votes
It is a bit hard to say exactly which introductions you should perform since we don't have your rule set, but I think the over all strategy should be as follows:

From $\neg (S \lor (P \to Q))$ you get $\neg (P \to Q)$. Since you have $\neg Q$, you should try to introduce $\neg P$ and thus obtain $P \to Q$. That should be a contradiction and you can conclude $P$.

---
Tags: logic, propositional-logic, natural-deduction
---


title: How to prove that $L^* = L^*L^*$

text:
# Question
Title: How to prove that $L^* = L^*L^*$
I need to prove or disprove that $L^\* = L^\*L^\*$.

Intuitively, I know this is true, and I know I need to prove that $L^\*$ is subset of $L^\*L^\*$ and that $L^\*L^\*$ is a subset of $L^\*$.

But I am really struggling to prove that.

# Answer
> 2 votes
Here is a partial answer, to put you on the right track. Try to complete it to a full answer.

Let's try to show that $L^\*\subseteq L^\* L^\*$.

Let $x\in L^\*$, so we know that we can write $x=y\_1\cdots y\_k$ where $y\_i\in L$ for all $i$. Now, let's assume for a moment that $k\ge 2$, then we can look at two words: $x\_1=y\_1$ and $x\_2=y\_2\cdots y\_k$. We then have that $x=x\_1x\_2$ and $x\_1\in L^\*$ and $x\_2\in L^\*$, so $x\in L^\*L^\*$.

If $k\<2$, then we can take $x\_2=\epsilon$, and possible $x\_1=\epsilon$, and the proof still works. So we have $L^\*\subseteq L^\* L^\*$.

Can you now follow a similar scheme for the other containment?

# Answer
> 1 votes
What colleague Shauli says in his answer, or if you are bold and not afraid of infinite unions:

$L^\*\cdot L^\* = ( \bigcup\_{i\ge 0} L^i )\cdot ( \bigcup\_{j\ge 0} L^j ) = \bigcup\_{i,j\ge 0} (L^{i}{\cdot}L^{j}) = \bigcup\_{i,j\ge 0} L^{i+j} = \bigcup\_{k\ge 0} L^k = L^\*$.

Do I see a hint of a Cantor traversal in the grid in this formula?

---
Tags: formal-languages
---


# Question
Title: Asymptotic bounds of the following operations
I have a very simple question about the best possible big-O bounds for the following data structure:

It starts out empty When you add an element, it is inserted, and the index it was at is associated with it. So if it was the first item inserted, it's index would be zero:

```
14 12 19 <- items
 0  1  2 <- associated indices

```

Now if I delete `12` in this instance, the indexes for the other items are updated like so:

```
14 19
 0  1

```

Adding another element, like 10:

```
14 19 10
 0  1  2

```

If I were to delete `14`, the `19` and `10` have their indices decreased by one.

In addition to adding and removing elements, you must also be able to search for a specific element and it should tell you what the index of that element is.

What is the tightest possible asymptotic bounds for these methods? Obviously I could do `O(n)` for removing elements and make search and add `O(1)`. However, I was able to use a Fenwick tree to get `O(log(n))` on add, search, and remove. Is it possible to do better than this?

# Answer
I contacted my professor about this question. He said he does not think it is not possible to do all three better than $O(\log n)$. For now I'll put this answer here for others, however if someone has a link to a proof, please do post it.

Edit: I am starting to think this problem cannot be reduced to sorting. I believe this is because we are dealing with a binary associative operator (addition) vs a binary *non* associative operator (comparison).

What I have noticed is that if you are trying to solve the problem of calculating any partial sum of an array, with the caveat that the data can also be modified, you cannot beat $O(\log n)$ for both calculating the partial sum and modifying the array. I am trying to come up with a proof for this.
> 0 votes

# Answer
If you could do all three operations faster than $O(\log n)$ time, then you would obtain a sorting algorithm whose running time is faster than $O(n \log n)$ time. That's known to be impossible for comparison-based algorithms.

So, you probably can't do better than $O(\log n)$ time for all three operations. In particular, you definitely can't do better using a comparison-based algorithm (one that only compares items but has no other knowledge about the values of items).

The reduction works as follows. First, scan through the list of $n$ numbers and insert each into your data structure. Second, scan through the list again; for each number $x$, look up its index, and then write it into an output array at that index. This does $2n$ operations on your data structure, so if your data structure can support insert and lookup in $O(\log n)$ time, the total running time will be $O(n \log n)$.
> 1 votes

---
Tags: data-structures, algorithm-analysis, asymptotics
---


title: LZW with dictionary clearing

text:
# Question
Title: LZW with dictionary clearing
How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used when compressing and decompressing data? My thoughts for compression are that it checks the table size, and if the table size has reached the maximum size it appends the flush character to the output before resetting the dictionary. I'm not sure what it does for decompression though.

# Answer
> 1 votes
When the compressor clears the dictionary, it emits the clear code. This enables the decompressor to stay in sync: when it sees the clear code, the decompressor clears its own dictionary. In this way, the decompressor can reconstruct/infer the state of the encoder's dictionary at each step.

Wikipedia says:

> Smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well.

---
Tags: algorithms, data-compression, dictionaries, lempel-ziv
---


# Question
Title: Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the top 4 teams (with the highest number of wins) make playoffs (with some tie-breaking procedure that can be done in polynomial time).

After some number of games, we are given the records for each team (including all head-to-head records). Assuming the remaining $g$ games have outcomes which are coin flips, we want to calculate the percentage chance each team makes playoffs.

---

Here's a brute-force solution. There are $g$ remaining games, so we can consider $2^g$ binary sequences where a 0 in each position means the team earlier in the alphabet wins, and a 1 means the team later in the alphabet wins. For each sequence, we can compute which teams make playoffs. Then, the percentage chance of making playoffs can be computed as the number of sequences in which a given team makes playoffs divided by $2^g$.

This obviously has exponential time complexity (in $g$). Is there a better algorithm to solve this problem - perhaps a polynomial time algorithm using dynamic programming? Is there some way to prove we can do no better than exponential time? Is it possible to show this problem is NP-hard?

---

One simplification that can be made (which unfortunately does not reduce the complexity) is that we can compute, in polynomial time, teams which are guaranteed to make or guaranteed to not make playoffs. All games between teams in either set will not affect the probabilities for teams in the middle. As $g \to 0$, this gives a substantial practical boost to the algorithm.

---

Note that 10 teams playing triple round robin are arbitrary and this problem can be generalized to $N$ teams playing a $k$-round robin. Specifically for the brute-force algorithm, it is exponential in $g$ which may not be related to $N$ or $k$. A sub-exponential algorithm should ideally be **not** exponential in any of $\\{N, k, g\\}$.

# Answer
A pragmatic solution is to use Monte Carlo: do one million random simulations, and for each team, count in how many simulations it made it to the top 5. This should give you a good approximation of these probabilities, even though the number is not exact.

If you want the exact probabilities, I think there is a complex solution that has polynomial asymptotic running time. I don't know whether it will be useful in practice. We'll enumerate all possibilities for the set of teams that make the top-4 and the 5th team, and for each such combination, compute the exact probability obtaining such an outcome. Asymptotically, if there are $n$ teams, this will involve enumerating $O(n^5)$ combinations, and I'll show below how to compute each of these probabilities in polynomial time, which yields a polynomial-time algorithm -- albeit one that might still be to slow to implement in practice.

Here's how to compute the probability of a particular combination of outcomes, namely, that a specified 4 teams make the top-4 (in some order) and one more specified team is #5. For each game yet to be played, we can introduce a zero-or-one variable $x\_i$ that records who wins. We can write down a set of linear inequalities that characterize the conditions under which the desired outcome occurs. The total number of wins of each team is a sum of some of these variables, and we want each of the top-4 teams to have at least as many wins as the #5 team, and every other team to have fewer wins than the #5 team, so we obtain inequalities comparing sums of these variables. Also for each $x\_i$ we have the inequality $0 \le x\_i \le 1$. This gives us a linear program, or in other words, a convex polytope. Now the question is to count the number of integer solutions to this linear program, or equivalently, the number of lattice points inside this convex polytope. There are known polynomial-time algorithms for this problem; see Finding all solutions to an integer linear programming (ILP) problem.

However, I suspect this fancy algorithm might be non-trivial to code up and might not be very useful in practice, even though it is polynomial time in theory, because of the large polynomials involved.

---

If you care about the asymptotic running time, I think there might be an improvement to the latter algorithm. For each team, enumerate all candidates for $t$, the number of wins of the #5-ranked team. Introduce zero-or-one variables $y\_i$, where $y\_i=1$ means that team $i$ was in the top 5. If we are counting solutions where team $j$ is in the top-5, force $y\_j=1$. We obtain an expression $e\_i$ for number of wins of team $i$, where $e\_i$ is linear in the unknowns $x\_i$. We can then add the inequalities $$y\_i t \le e\_i \le t-1 + (3n-2-t) y\_i$$ $$y\_1 + \dots + y\_n = 5$$ and count the number of solutions to this system.
> 0 votes

---
Tags: algorithms, complexity-theory, dynamic-programming, np-hard
---


# Question
Title: Is this the correct answer for the cardinality of this set?
This is a question from a practice quiz at my university.

Is the question asking for the cardinality of Σ1 = {a,b} to the power of four?

if that's the case, then the set would still have a cardinality of 2 since elements in a set are unique. It wouldn't be {a,b,a,b,a,b,a,b} right?

# Answer
> 1 votes
This is how you should solve it. Let $\Sigma\_1=\Sigma$

We are asked to find: $|\Sigma^ 4|$ Now

$$\Sigma^4 = \Sigma . \Sigma . \Sigma . \Sigma = \\{a,b\\} . \\{a,b\\}. \\{a,b\\} . \\{a,b\\}$$

$$\text{ Here . means the concatenation operator}$$

So this is equivalent to number of ways of forming strings of length $4$ with symbols from $\Sigma$.

We have $4$ places,

---

Each of the places have two choices to get filled : either $a$ or $b$. So,

```
_   _  _   _
2 . 2. 2. 2

```

So answer is $2^4 =16$

# Answer
> 1 votes
A set "multiplied" with another set is called the *cartesian product* and is formed of tuples of elements, one from each set you are multiplying.

If you have $S = \\{a, b\\}$ and $T = \\{x, y\\}$, then $$S \times T = \\{ (a,x), (a,y), (b, x), (b, y)\\},$$ and its cardinality is actually $|S\times T| = |S| \cdot |T|$.

---
Tags: sets, finite-sets
---


# Question
Title: Hamiltonian path greedy and anti-greedy algorithms
I had this question on a problem set recently, but I wasn't sure how to solve it.

Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path:

* **greedy:** start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with *smallest* weight
* **anti-greedy:** start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with *largest* weight

The question is, does there exist a $G$ so the anti-greedy algorithm is better than the greedy algorithm (smaller path weight)?

# Answer
> 4 votes
No.

---

In fact, we can prove the following stronger proposition.

**Claim.** Given a complete weighted undirected graph, a run of the greedy algorithm on it and a run of the anti-greedy algorithm on it, the $i$-th heaviest edge chosen by the greedy algorithm weighs no more than the $i$-th heaviest edge chose by the anti-greedy algorithm, for all valid $i$.

**Proof**. It is enough (and necessary) to show, given any weight $w$, the number of edges chosen by the greedy algorithm that weigh more than $w$ is no more than the number of edges chosen by the anti-greedy algorithm that weigh more than $w$.

Fix an arbitrary weight $w$. Let $\overrightarrow{u\_1v\_1}$, $\overrightarrow{u\_2v\_2}$, $\cdots$, $\overrightarrow{u\_kv\_k}$ be the edges chosen by the greedy algorithm that weigh more than $w$, in the same order as they were chosen by the greedy algorithm. Assume $k\ge1$; otherwise we are done.

Note that $u\_1, u\_2, \cdots, u\_k$ and $v\_k$ are distinct, since they are the starting vertex of distinct edges and the ending point of the last edge, respectively. Let $u\_{k+1}=v\_k$.

Consider any two vertex $u\_p$ and $u\_q$ such that the greedy algorithm visits $u\_p$ earlier than $u\_q$, i.e., $p\<q$. We know $\overrightarrow{u\_pv\_p}$ weighs no more than $\overrightarrow{u\_pu\_q}$ since it weighs the least among all edges from $u\_p$ to unvisited nodes. Since $\overrightarrow{u\_pv\_p}$ weighs more than $w$, so does $\overrightarrow{u\_pu\_q}$. We have just proved the simple and critical observation that all edges among $u\_1, u\_2,\cdots,u\_{k+1}$ weigh more than $w$.

The anti-greedy algorithm will visit each vertex in $u\_1, u\_2, \cdots, u\_{k+1}$ soon or later, since it will find a hamilton path. Consider the $m$-th time when the anti-greedy algorithm have just visited such a node. If $m\lt k+1$, then there is at least another such node that has not been visited, which means the next edge it will choose must weigh no less than the edge to that unvisited node, which weighs more than $w$ as we just proved above. That is, for each of the first $k$ times the anti-greedy algorithm must choose an edge that weigh more than $w$. $\quad\checkmark$

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


# Question
Title: How do I apply the Pumping Lemma to prove that this language is not regular?
I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it. I would appreciate a clear explanation of how I would use the Pumping Lemma to prove that this language S is not regular:

$$ S = \\{va^{7|v|}\text{ | }v \in \\{a,b\\}^\*\\} $$ |v| = length of v

How do I use the Pumping Lemma to show that S is not regular?

Thanks.

# Answer
Assume S is regular.

The pumping lemma says: There is a pumping length n. And if you take any string w in S with length \> n, then w contains a non-empty substring in the first n symbols that can be repeated 0, 2, 3, 4, ... times, and the result is in the language. (Why is that? A regular language has a finite state machine. If that state machine has n states, then while you are processing the first n symbols, you must enter one state twice, say the state X. So you could take the symbols that took you from X back to X, and remove them, or duplicate them, or repeat them a million times, and your string would still be in the language). So w = xyz, xy has length ≤ n, y has length ≥ 1, and xz, xyz, xyyyyyyyyyz etc. are all in the language.

Take any string v with length k \> n which doesn't end in a. The string w = v a^(7k) is in the language. When we split w into xyz, since the length of xy must be at most n, but v has a length k \> n, we actually split into $w = xyz a^{7k}$.

The pumping lemma says that $xy^mz a^{7k}$ is in the language for every y. But for m ≠ 1, 7k is not seven times the length of $xy^mz$ so it is not in the language, therefore S is not regular.
> 0 votes

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


title: Equivalence of Turing Machines

text:
# Question
Title: Equivalence of Turing Machines
Consider the following two arguments

> "*For every non deterministic TM M1 there exists an **equivalent** deterministic machine M2 recognizing the same language.*"
> "***Equivalence*** *of two Turing Machines is undecidable*"

These two arguments seem a bit contradicting to me. What should I conclude from these two arguments?

# Answer
These arguments are not really related, on several levels.

The first is that *existence* and *computability* are not the same thing. That is, even if there exists some object (e.g. a TM), it does not mean that *finding* (or computing) such an object can be done using a TM.

However, there is a more basic difference between the two statements. The first says that for every TM $M\_1$, there exists some equivalent machine $M\_2$. The second statement is that deciding, given $M\_1$ and $M\_2$, whether these two specific machines are equivalent, is undecidable.

Just to emphasize the difference, consider the following problem: given a TM $M\_1$, is there some TM $M\_2$, that is different from $M\_1$, which is equivalent to $M\_1$? This problem is trivial - the answer is always "yes" (e.g. just add a redundant state to $M\_1$).
> 9 votes

# Answer
"Equivalence is undecidable" means there is no *algorithm* (always halts after a finite time and correctly answers yes/no), "there is an equivalent" is just existence. I.e., given $M\_1$ and $M\_2$, no algorithm can tell if they are equivalent *for all cases of $M\_1$ and $M\_2$* (some cases can be answered simply, but not all). The other is that for $M\_1$ there is an equivalent $M\_2$. It is even easy to construct some, just shuffle the states around, or add a completely useless state.
> 3 votes

# Answer
Argument 1 says that for every non-deterministic Turing machine, we can build a deterministic Turing machine for recognizing the same language.

Argument 2 is not related to argument 1.

Argument 2 says that even though there may be two Turing machines that are equal, can not decide or prove they are equal. so it is undecidable.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: How can I derive a formula that produces a set of numbers per index?
For example, assuming I am using the set of natural numbers $\mathbb{N}^\* = \mathbb{N} \cup 0$ as my domain.

I want to create an algorithm such that at each index value $i$, I output a set.

For example,

* $0$ maps to $\\{1,2,3,4\\}$
* $1$ maps to $\\{5,6,7,8\\}$
* $2$ maps to $\\{9,10,11,12\\}$

How might I go about deriving the function needed to produce the desired codomain?

# Answer
Just map $n$ to $\\{4n + 1, 4n+2, 4n+3, 4n+4\\}$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Counting substrings that belong to a regular language
Given a regular language $L$ and a string $x$ give an efficient algorithm to count the occurrences of substrings $x\[i,j\] \in L$.

More in particular, I am looking for a linear time algorithm in the length of the string $|x|$, for a given deterministic automaton $M$ accepting the language $L$.

This question is meant to generalize the question of counting substrings where each symbol occurs an even number of times, asked before here.

# Answer
> 3 votes
You can do it in $O(|x|\cdot |M|)$ with dynamic programming.

Let $q\_0$ be the starting state, $\delta$ the transition function of $M$, and $a(q) \to \\{0, 1\\}$ a boolean function indicating whether $q$ is an accepting state in $M$.

Let $A\[i, q\]$ be the number of non-empty prefixes of $x\_ix\_{i+1}\ldots x\_n$ accepted by $M$ if we start in state $q$. We can directly compute $A\[n, q\] = a(\delta(q, x\_n))$. Then, going backwards row by row, we can fill the table using $A\[i,q\] = a(\delta(q, x\_{i})) + A\[i+1, \delta(q, x\_{i})\]$.

Finally, you sum $a(q\_0) +\sum\_{i=1}^nA\[i, q\_0\]$ as your answer, as this is the sum over all non-empty prefixes of all non-empty suffixes, plus one if the empty string is accepted, thus all substrings.

---
Tags: algorithms, regular-languages, counting
---


# Question
Title: Does every turing machine have an equivalent, single-state, n-tape turing machine?
Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has *only one state?* (We can assume that the accept and reject states are implicit here. If that bothers you, you may think about this as a question about 3-state machines instead.)

# Answer
> 12 votes
Yes, there always exists a machine, and we really only need 2 tapes.

Your standard TM transition might be written:

$\delta(S\_n, a) = (S\_m, b, r)$

This would mean that, from $S\_n$, if we read $a$, we would write $b$, move in direction $r$, and transition to state $S\_m$. We will allow our machine to move left, right, or stay in place ($\<$, $\>$, or $-$).

Now for the 2-tape machine, we'll go to our infinite shelf of Turing Machines and grab a standard two-tape model where both heads have independent left/right/stay capabilities.

As it turns out (just our luck!), on this machine, one of the motors actually broke a few years ago, so the second head can still read and write, but it can't move left or right any more. Not to fear, we won't be needing that motor. This machine will serve our needs just fine.

This model happens to be called the *TwoTapey*. On the *TwoTapey*, we could write a transition this way:

$\delta(S\_n, a\_1, a\_2) = (S\_m, b\_1, b\_2, d\_1)$

This transition would mean that, from $S\_n$, if the *TwoTapey* reads $a\_1$ on tape 1 and $a\_2$ on tape 2, it would transition to $S\_m$, write $b\_1$ on tape 1, $b\_2$ on tape 2, and move head 1 $d\_1$. On a normal two-tape TM, we'd need a $d\_2$ for the second head, but there's no need for that here, because that darned motor is still busted.

So, to translate our standard TM to the *TwoTapey*, we need to add each of our original state names ***as strings*** into the tape alphabet of the 2-tape machine. Then, take each transition, and translate it this way:

$\delta(S\_n, a) = (S\_m, b, r)$

becomes

$\delta(S\_0, a, \`\`S\_n") = (S\_0, b, \`\`S\_m", r)$

The key is that busted motor. Since we never move left or right on the second tape, this allows us to imitate our original states by simply using the second tape to hold our old state information. This allows us to transition from $S\_0$ back to $S\_0$, but still utilize just as many transitions as we used to have in the original machine.

As CandiedOrange pointed out to me, this is actually a really good way to show that the hardware/software divide is artificial. All state is just data, and all data is just state.

# Answer
> 1 votes
On all the comments:

Usually a TM is used to compute something, e.g. a yes/no about word \in language. Therefore, either we are nit-picking and require at least two halting states (accept, reject) PLUS one start/working state (although 2 states are usually considered sufficient for completeness for a singel-tape TM)... ... or the answer is in the final tape contents, and we stop e.g. by running off to the left (for a mono-infinite tape) or writing, then reading a symbol that incurs undefined behaviour - and the tape says "Nay" or "Yeah" (symbols abound).

As far as the completeness is concerned, Ben I. makes the point: Yes, the state can be completely moved out of the FSM onto the 2nd tape.

The essential point is the independence of the two read/write heads and the option to not move the head at all.

---
Tags: turing-machines, computation-models, simulation
---


# Question
Title: Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$
> Given a circle with $n$ equal segments. On each segment there is an integer. We want select segments at equal distance, maximizing the sum of integers on selected segments.

I have an algorithm with runtime $O(n^2)$ as follows:

First calculate maximum sum of segments at distance one. Second calculate maximum sum of segments at distance two, and so on. Return maximum of all above values.

According to the teacher, there is a solution with runtime $O(n\log n)$, but I cannot find it.

# Answer
> 0 votes
Denote the numbers by $a\_0,\ldots,a\_{n-1}$. We want to maximize, over all $m \mid n$ and $0 \leq r \< m$, the sum of all $a\_i$ such that $i \equiv r \pmod{m}$.

Let $p\_1,\ldots,p\_k$ be the prime divisors of $n$. Either $m = n$, or $m \mid (n/p\_i)$. In the latter case, we can fold $a$ into an array $b^{(n/p\_i)}$ of size $n/p\_i$, and solve the problem there, recursively. If we use dynamic programming, then each $b^{(m)}$ will explored once, for each $m \mid n$.

What is the running time of this algorithm? The work done at $b^{(m)}$ takes time $O(m\rho(m))$, where $\rho(m) = O(\log m / \log\log m)$ is the number of distinct prime factors of $m$ (the upper bound on $\rho(m)$ follows from $n \geq \rho(m)!$). It follows that the total running time is proportional to $$ \sum\_{m \mid n} m\rho(m) \leq \frac{\log n}{\log\log n} \sum\_{m \mid n} m = \frac{\log n}{\log\log n} \sigma(n) = O(n\log n), $$ since the divisor sum function satisfies $\sigma(n) = O(n\log\log n)$.

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: How to solve recursion T(n) = T(n/3) + T(2n/3) + n?
$T(n) = T(n/3) + T(2n/3) + n$

How can I solve this recurrence formula?

# Answer
Look at the recursion from QuickSort for the average case:

$T(n) = T(n/2) + T(n/2) + n$

which ends up in $O (n \log n)$.

Note that $n/2 + n/2$ sums up exactly to $n$. Just like $n/3 + 2n/3$ sums up exactly to $n$. Substitute the formula for $T(n)$ in $T(n/3)$ and $T(2n/3)$ and you'll see it's the sum of $T(x)$ for four values $x$ which add up to $n$, plus $2n$. Substitute again, and you see it's the sum of $T(x)$ for eight smaller values $x$ which add up to $n$, plus $3n$. And so on. Since the $x$ shrink by at least a factor $2/3$, the number of rounds until you end up at $T(1)$ is $O(\log n)$.

So that's what you guess, and once you guessed it you can prove it: $T(n) = O (n\log n)$.
> 1 votes

# Answer
You can solve recurrences of this form using the Akra–Bazzi method. The answer is $O(n\log n)$.
> 0 votes

---
Tags: time-complexity, asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$
As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$

My approach is to find $c, n\_0 \in \mathbb{R}\_+$ such that:

$$\forall n \geq n\_0, T(n) \leq c\log(n) -d \text{, where d is a constant}$$

Assume the statement is true for every $m \< n$, especially $m = \left\lceil{\frac{n}{2}}\right\rceil$, therefore

$$T(\left\lceil{\frac{n}{2}}\right\rceil) \leq c \log(\left\lceil{\frac{n}{2}}\right\rceil) - d $$ $$\iff T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1$$ $$\leq c\log(\left\lceil{\frac{n}{2}}\right\rceil) - d + 1$$ $$= c\log(\left\lfloor{\frac{n}{2}}\right\rfloor + 1) - d + 1$$ $$\leq c\log(\frac{n + 2}{2}) - d + 1$$ $$= c\log(n + 2) - c\log(2) - d + 1$$ $$= c\log(n + 2) - d$$

This is where I stuck and can not go further. I need to eliminate the constant $2$ in $n + 2$. Any help and hint is welcome.

Edit: In term of master theorem. I have to solve this recurrence with substitution method.

# Answer
> 1 votes
If you let T(0) = T(1) = 0, then prove by complete induction for every k \>= 1 that T(n) = k for all n such that $2^{k-1} \< n \<= 2^k$.

k = 1: True because T(2) = 1.

k -\> k + 1: Let $2^k \< n \<= 2^{k+1}$. Then $2^{k-1} \< n/2 \<= 2^k$, therefore $2^{k-1} \< \lceil n/2 \rceil\<= 2^k$, therefore $T(\lceil n/2 \rceil) = k$, therefore T(n) = k+1.

So instead of O(log n) you get the much stronger $T(1) + \lceil \log\_2 n \rceil$ for all n \>= 1.

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


# Question
Title: largest gcd of an array after a few operations
consider we have `n` bags of random amounts of coins. given `k` extra coins, the question is to find the largest gcd that can be obtained by adding these coins to any bag( all the `k` coins may not go in one bag and not all the coins are necessarily added)

input consists of the number of bags followed by `k`( number of extra coins ) and the number of coins in each bag in the next line. the output the the largest gcd.

example:

```
input:
3 3
3 4 2

output:
4

```

which can be obtained by adding one coin to the first and two coins to the third bag.

(all inputs are between 0 and 1000 and the time limit is 1 secs)

# Answer
If you have n numbers then find the largest c such that n * (c-1) \<= k. You can achieve gcd=c easily. For example n = 1000, k= 1,000,000 you increase every number by 1,000 so no matter what the numbers are you can make them all multiples of 1,001.

Find the largest d so that k is enough to increase every number at least to d. That’s an upper bound for the gcd, because the gcd cannot be larger than every number.

Then try whether each g from d downwards to c could be the gcd by checking how much each number needs increasing to make it a multiple of g, and stop if the total increase exceeds k.
> 0 votes

---
Tags: data-structures, python
---


# Question
Title: Inductive sequence of words in a biprefix code
Let $X = X\_1 \cup X\_2$ a code on an alphabet $A$, with $X\_1$ a biprefix code and $X\_2$ a uniform code, with $m(X\_1) \< m(X\_2)$, i.e. the maximal length of the first is strictly lower than the second. Now, if $v \in X\_2$ we define a sequence such that $v\_0 = v$ and $v\_{i+1} = 1$ if $v\_i \notin X\_1A^\*$ and $v\_{i+1} = y\_ix\_i$ if instead $v\_i \in X\_1A^\*$, with $v\_i = x\_iy\_i$ with $x\_i \in X\_1, y\_i \in A^\*$.

Now, let $u,v \in X\_2$ and suppose there exist two integers $i \leq j$ such that $u\_{i} = v\_j$. Since $X\_1$ is biprefix, this implies that $u\_{i-1} = v\_{j-1}$. Why does this imply that $u\_0 = v\_{j-1}$? The paper I am reading motivates this last deduction by induction, but I can’t see how $j-1$ could stay fixed in the process. Any hints?

# Answer
> 0 votes
Your paper has a typo. It should be $u\_0 = v\_{j-i}$ rather than $u\_0 = v\_{j-1}$.

Indeed, consider the following example: the alphabet is $A = \\{0,1\\}$, and the two codes are $X\_1 = A^1$ and $X\_2 = A^2$. Take $u = 01$ and $v = 10$. Then $u\_0 = 01$, $v\_0 = 10$, and $v\_1 = 01$. If $i = 0$ and $j = 1$ then $u\_i = v\_j$, yet $u\_0 \neq v\_{j-1}$; but $u\_0 = v\_{j-i}$.

You already know that $u\_i = v\_j$ implies $u\_{i-1} = v\_{j-1}$. Applying this step $i$ times, you immediately conclude that $u\_0 = v\_{j-i}$.

---
Tags: proof-techniques, induction, word-combinatorics
---


title: What is combinational circuit?

text:
# Question
Title: What is combinational circuit?
I'm reading the Digital Design and Computer Architecture by David Harris, Sarah Harris. The authors give the following definition of combinational logic:

> A combinational circuit’s outputs depend only on the current values of the inputs; in other words, it combines the current input values to compute the output... A combinational circuit is memoryless, but a sequential circuit has memory. The functional specification of a combinational circuit expresses the output values in terms of the current input values.

However, they claim this circuit is not combinational:

because "node n6 connects to the output terminals of both I3 and I4". Indeed, it's one of the designated signs when a scheme can not be combinational but, according to the authors:

> Certain circuits that disobey these rules are still combinational, so long as the outputs depend only on the current values of the inputs.

As I'm able to catch on, the aforementioned circuit is the case: its output is 1 if and only if its inputs are both 1, otherwise the output is 0. So the output is defined as a function of the inputs (the AND function).

In fact, there was already a question about this circuit and it has an accepted answer. Here's an excerpt from it:

> Circuit (d) cannot be written in this form *\[of formula\]*, since the outputs of I3 and I4 are wired together. What is the relation between the input to the rightmost gate and the outputs of I3 and I4? Not something that can be described combinatorially.

Unfortunately, I'm still confused due to

* The circuit, **regarded as a black box**, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;
* The relation between the input to the rightmost gate and the outputs of I3 and I4 can be described through the function NAND of the circuit inputs and this function is quite "memoryless". It's not obvious for me why we can't afford to depict a gate input using multiple outputs of other gates.

I need some elaboration. Maybe things would fall into place if someone provide a circuit example when two gates outputs is connected to one input and it actually causes "memory" (in contrast to the considered sample).

# Answer
For me a short-circuit isn't combinatorial nor sequential. It's an error, it may fry the circuits.

> The circuit, regarded as a black box, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;

You can make a logic inverter with high power relays. You set opposite tensions, the relays or the wires connecting them turn into melted metal. You have a memorised effect (blown circuit) : It is sequential!
> 1 votes

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: How will Big O be with quantum computers?
I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change our understanding of current algorithms? For example, will this mean that the difference between an algorithm running at Big O(2^n) and another running at Big O(n^2) in traditional computers be insignificant in a quantum computer? Would time complexity even be an issue with quantum computers? This might have a very obvious answer but I don't know the answer (and I'm really am curious).

# Answer
> 1 votes
Big-O has nothing to do with quantum computers. This should be obvious by the fact that Big-O notation was introduced in 1894, long before we had any knowledge of quantum theory … or computers for that matter.

Big-O is simply a convenient notation for classifying growth rates of functions. Big-O doesn't care how you interpret those functions.

So, the definition of Big-O will not change for quantum computers for the simple reason that its definition has nothing to do with computers.

---
Tags: algorithms, time-complexity, quantum-computing, big-o-notation
---


# Question
Title: Transitive closure of a directed graph (reachability) algorithm intuition/explanation
Consider $n\times n$ matrix $T$ which represents transitive closure of a directed graph. That means $T\_{uv}=1$ if and only if there exist a directed path between vertices $u$ and $v$. Initially, $T$ is a identity matrix (every vertex has a self-loop). Now consider following function:

```
function insertEdge(u, v):
  for x from 1 to n:
    if T[x][u] == 1 and T[x][v] == 0:
      for y from 1 to n:
        T[x][y] = max(T[x][y], T[v][y])

```

This function adds a directed edge from $u$ to $v$, while maintaining the transitive closure of the matrix $T$. However, I have no idea how and why this algorithm works. So I'll be glad for any intuition or explanation of this algorithm.

# Answer
What the algorithm is doing is updating all $T\[x\]\[y\]$.

Assume that $T$ is transitive and that a new edge $(u,v)$ is added. Which pairs $(x,y)$ would need updating? Well, those pairs for which adding $(u,v)$ creates a new path from $x$ to $y$.

Assume that we are in a case that doesn't enter the IF. If it is because $T\[x\]\[u\]\neq 1$ then there was no path to go from $x$ to $u$. So adding $(u,v)$ will not help getting from $x$ to $y$.

If $T\[x\]\[u\]=1$ and $T\[x\]\[v\]=1$, then the new edge $(u,v)$ doesn't really change anything in terms of being able to get from $x$ to $y$.

So, the cases excluded by the IF are cases that don't need updating anyway.

Assume now that you are in a case that does enter the IF. So, $T\[x\]\[u\]=1$ and $T\[x\]\[v\]=0$.

If $T\[x\]\[y\]=1$ we already were able to get from $x$ to $y$ before adding $(u,v)$. The maximum returns $1$. So, the value of $T\[x\]\[y\]$ is not changed and still is $1$ after the loop exits.

Assume that $T\[x\]\[y\]=0$. If we consider a $y$ such that $T\[v\]\[y\]=1$, then that means that we can go from $x$ to $y$ by going from $x$ to $u$, from $u$ to $v$ using the newly added edge, and from $v$ to $y$. Precisely in this case the maximum will also result in $1$. To $T\[x\]\[y\]$ gets updated to $1$.

Now, if the inned loop lands in a $y$ such that $T\[x\]\[y\]=0$ and $T\[v\]\[y\]=0$, that means that we originally were not able to get from $x$ to $y$ by paths not using the edge $(u,v)$. Any path that uses the newly added edge $(u,v)$ would have to go from $x$ to $u$, then $u$ to $v$ and finally some path from $v$ to $y$. This last part of the path can be assumed consisting entirely of edges different from $(u,v)$ by taking the portion starting from the last time that the supposed path leaves $v$. But the assumption $T\[v\]\[y\]=0$ means that this path doesn't exist. So, there is no way to go from $x$ to $y$, and in fact the maximum in the code results in $0$ in this case.

So, that covers all the cases.
> 0 votes

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


# Question
Title: Why can't we mimic a dog's ability to smell COVID?
As far as I can tell, we have invented tools and algorithm to:

* Detect a wider range of colors at a larger range than humans or any other animals on the planet
* Detect sound with wavelengths inaccessible to humans or most animals on the planet

But why is it that dogs can smell COVID or Cancer and we can't produce a similar tool to "smell diseases"? Why can't we mimic the dog's sense of smell: is it a hardware limitation or a software one? Am I mistaken in thinking that this sense is the hardest to mimic?

# Answer
> 38 votes
We can actually detect some diseases via smell, and the term to search for is *olfaction*. The general problem is known as *breath analysis*.

However, the research into olfaction and machine learning is rather new (perhaps even surprisingly new). As Lötsch et al. point out, little research (prior to the very recent research) on olfaction and machine learning has been performed, with a few exceptions:

1. *Quantifying olfactory perception: mapping olfactory perception space by using multidimensional scaling and self-organizing maps*, Mamlouk et al., *Neurocomputing*, 2003.
2. *Relationships between molecular structure and perceived odor quality of ligands for a human olfactory receptor*, Sanz et al., *Chem Senses*, 2008.
3. *Diagnosis and Classification of 17 Diseases from 1404 Subjects via Pattern Analysis of Exhaled Molecules*, Nakhleh et al., *ACS Nano*, 2017.
4. And the one mentioned above, *Machine Learning in Human Olfactory Research*, Lötsch et al, *Chemical senses*, 2019.

I don't know whether the problem in general is harder, but as you are touching on in your question, the problem is much harder from a hardware perspective. Where imaging only needs a simple camera, and hearing only need a simple microphone, to detect smell you need a so-called as chromatography–mass spectrometry instrument. As the Wikipedia article mentions:

> Breath gas analysis consists of the analysis of volatile organic compounds, for example in blood alcohol testing, and various analytical methods can be applied.

Here are some pointers from popular science that should assist you in getting into the literature:

# Answer
> 39 votes
Addressing the hardware side of your question:

A dog's sense of smell was developed through millions of years of evolution. The dog's nose is powered by hundreds of millions of organic nanomachines (olfactory receptors) working in concert to detect the faintest traces of odors, in the form of individual molecules floating among an endless sea of nitrogen, oxygen, and molecules from other nearby sources producing orders. I don't think we have hard numbers, but some estimates say that a dog's nose can distinguish molecules in the parts-per-billion or even parts-per-trillion (or higher) range.

When these millions of finely crafted organic nanomachines detect molecules of something besides oxygen and nitrogen floating in the air, the signal is sent to the brain, which then cross-references this data against an exhaustive library of known molecules (some instinctive and some learned), and interprets it as a "smell". Different concentrations of different molecules will be interpreted as different smells, and we know from numerous practical use cases that dogs can be trained to seek out specific smells.

It takes extremely sophisticated sensors to even begin to approach a dog's ability to detect and classify those stray molecules floating through the air that make up an odor.

In contrast, measuring sound is child's play (since it's just vibrations through air or another medium) and even imaging is comparatively simple (measure the wavelength and intensity of light striking the image sensor).

An astronomically greater amount of R&D has gone into light and sound because these have the greatest number of commercial applications. We can use light sensors to record and share photos and videos. We can use audio sensors to record and share music, speech, and more. We can combine these two technologies to produce movies, television, and more.

On the other hand, the best you could do with an odor sensor is produce a chart or graph of relative molecular concentrations. We don't have any kind of consumer-level technology that can reproduce arbitrary odors from digital recordings for other audiences to smell. Hollywood isn't likely to be investing millions of dollars per year into odor sensors. There aren't enough practical applications.

When we do have a practical need for odor detection outside of scientific research (e.g. for security or police purposes), do we typically issue some multi-million dollar precision gadget that can detect all of the relevant molecules in the air? No, we do what humans have probably done for thousands of years before the first electronics: use a trained dog.

# Answer
> 0 votes
One of the major players in this question is adaptation. The brain is a marvel of adaptation which software developers are still desperately trying to unlock. So from that perspective, it's a software issue. However, unlike many engineering efforts, it isn't "hardware leads to software." In the brain, hardware and software intermingle to the point where it is sometimes hard to distinguish them.

In the case of smell, the brain adapts to the particular sensors it has. This permits a different kind of sensor which is less a-priori specialized and more "we'll work with what we get." This can be a difficult kind of sensor to work with in engineering, requiring complex calibration and training. At some point, it simply becomes more cost and time effective to train a dog, leveraging a few million years of evolution.

From an engineering perspective, it's not worth spending \\$50,000 to build a smelling machine and half a man year of training and calibration when you can put a female dog and a male dog together, wait for a free smelling machine to be produced, spend a few weeks training them (the smell training phase for drug sniffing dogs is around 3-4 weeks), and be ready to roll. Glendale Police claim the whole price of a K-9 unit dog is \\$22,500. The typical engineering process is to turn up the precision in the process, so that you can roll out units with very little calibration/training. And while calibration/training is a software thing, it also has a major effect on the choices that the hardware team makes!

We simply haven't found a cheap, high precision, reproducible way of handling smells the way dogs do.

---

You mention the amazing things we have done with detecting light, spanning many wavelengths. But evolution is amazing too. Consider this Single Photon Detector. It can detect single photons in a range of wavelengths just a little larger than "visible wavelengths." It costs $4,600 at the time I wrote this answer.

Our Mark-I eyeballs have detectors too. In particular the rods are *very* effective at sensing light. If given 30-45 minutes of pure darkness, the rods will adapt to the low light, becoming more and more sensitive. Once fully adapted, a rod is capable of detecting *single* photons striking it. This is done through a remarkable active feedback system involving several inhibition loops.

We have over 100 million rods in the human eye. That many Single Photon Counter Modules would cost over $4 billion, and take up roughly the volume of an Olympic swimming pool! Of course the data shows the human eye can detect a single photon roughly 1.6% of the time while the spec for that detector is closer to 20% on average and 35% at its peak, but since 90% of the light that reaches the eye never actually hits a photodetector, the photodetectors themselves have to be at least 16% effective at detecting this single peaks. Not bad for a detector no larger than the diameter of a human hair!

*Full disclosure: I have no relationship with Thor Labs nor this product. It was the first product recommendation for a google search for "Single Photon Detector."*

# Answer
> -1 votes
Well, given this is a computing forum, I would say that all computing requires input. You have to have a way to "input" the smell. So far, as one of the answers described, we have very few ways of translating a smell which is a physical world thing, into data, and even so far, those methods mentioned have arguable limits on how they translate to a "smell".

Once that happens in a cost effective and available manner, everything else will just translate over, just like it did with imaging. As the old saying goes, Garbage in, Garbage Out. I'll add, Nothing in, Nothing out.

---
Tags: machine-learning, applied-theory, applications
---


# Question
Title: Best operating system for a computing degree?
Not sure which OS is best to invest in for my computer science degree. Have had varying opinions - from your experience in education or working in the sector, what is the operating system that will treat me the best for the next three years of my degree?

# Answer
> 2 votes
Some Operating Systems that I feel are important to understand are (in no particular order):

* Microsoft Research Singularity for its interesting approach of compile-time memory and process isolation, thus obviating the need for any sort of MMU, CPU privilege separation, and hardware memory protection. Also, the safety and modularity of message-passing semantics with the performance of mutable shared memory by compile-time verification of messaging protocol state machines.
* Microsoft Research Midori for an interesting view into how a research operating system (Singularity) changes when you apply its ideas to a pragmatic production OS (Midori was never released, but it was run in production in Microsoft Bing).
* Microsoft Research Verve, another take on Language-based Operating Systems.
* Smalltalk – You might ask yourself, what business does a *Programming Language* have to be listed in a list of *Operating Systems*? Especially a programming language whose fundamental design principles famously include

> An operating system is a collection of things that don't fit into a language. There shouldn't be one.

Well, it is precisely for that reason that I find Smalltalk to be a fascinating and important "Operating System". It shows you what a system without an operating system could look like.

Some slightly more modern incarnations include SqueakNOS (original implementation), SqueakNOS (revived), and CogNOS / nopsys.
* ETH Zürich Barrelfish for an interesting take on an OS for heterogeneous manycore systems. For example, the laptop I am typing this on right now has eight cores, which are actually composed of two different kinds of cores in two blocks of four cores. It also has several co-processors for graphics, video, machine learning, and security. Heterogeneous multicores are already commonplace, manycores are already commonplace, it shouldn't be long until we see heterogeneous manycores. Also, even though this OS is older than the cloud hype, it would actually be a perfect cloud OS.
* ETH Zürich Oberon for an interesting approach to GUIs. All modern desktop OSs are essentially descendants of Smalltalk. (While fanatic trolls on both sides of the side accuse either Bill Gates of stealing from Steve Jobs or Steve Jobs of stealing from Bill Gates, reality is that both teams visited the Smalltalk team around the same time, and that's where both got their ideas from.) Oberon is very different.
* Plan 9 from Bell Labs (the successor to Unix) and its successor Inferno give great insight into Unix. If you understand Plan 9 and Inferno, you understand the ideas behind Unix, and you see all the places where those ideas were betrayed. For example, a fundamental design idea in Unix, Plan 9, and Inferno is "Everything Is A File", except in Unix, there are lots of things that *aren't* files, whereas in Plan 9 and Inferno, they are. Network sockets are "file-like" in Unix, but are simply files in Plan 9 and Inferno. Windows don't even exist in Unix itself, and are in-memory structures hidden behind specialized APIs in X and Wayland, but they are just files in Plan 9 and Inferno.
* The Burroughs Master Control Program because "everybody knows" you cannot write an OS in a high-level language … except these guys did it. In 1961.

# Answer
> 1 votes
I'm in the final year of a 4-year engineering degree program in Electronics and Communication Engineering. I have installed and use Kubuntu for the past 3 years and I love it!

* It is **lightweight and crashes very rarely** (with 8 GB RAM, but 4 GB RAM is also useable with fewer applications runnning concurrently).
* **Most updates can be done without restarting your computer** and **you are not forced to update**.
* **Beautiful and intuitive GUI** (KDE)
* Free KDE development tools like KDevelop and Kate are awesome!
* Easily install and update software using Discover application.
* **Different modes and a fully customisable desktop**
* Tons of **free** software that can be installed.
* The **PDF reader, Okular** is really good!
* Learning Unix and Linux administration is a very valuable skill in the computing industry.

---
Tags: operating-systems, education
---


# Question
Title: Floating point bitwise comparator. If f1 and f2 are floating point numbers with the following properties can we always say f1 > f2?
Recall floating-point representation:

Suppose $f$ is a floating-point number then we can express f as, If $f$ is normal: $$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k})$$ If $f$ is denormal/subnormal: $(e = 0)$ $$(-1)^{s}\cdot2^{-126}(0 + \sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k})$$

where

* $s$ is the sign of $f$.
* $e$ is the stored exponent of $f$. This means $e-127$ is the effective exponent of $f$.
* $b\_k$ is the $k$-th bit of $f$ where $b\_0$ is the LSB and $b\_{22}$ is the MSB.

Let $f\_1$ be a floating-point number with constants $s\_1, e\_1,$ and $b\_{1k}$.

Let $f\_2$ be a floating-point number with constants $s\_2, e\_2,$ and $b\_{2k}$.

I'm trying to find out if the following statement is true: $e\_1 \> e\_2 \> 0$ and $s\_1 = s\_1$ then $f\_1 \> f\_2$.

My initial strategy was to subtract $f\_2$ from $f\_1$ and show that it must be strictly greater than $0$.

What I have so far.

$ \begin{align\*} f\_1-f\_2 &= 2^{e\_1-127}(1 + \sum\limits\_{k=1}^{23} b\_{1,23-k}\cdot 2^{-k}) - 2^{e\_2-127}(1 + \sum\limits\_{k=1}^{23} b\_{2,23-k}\cdot 2^{-k})\\ &= 2^{-127}(2^{e\_1}(1 + \sum\limits\_{k=1}^{23} b\_{1,23-k}\cdot 2^{-k}) - 2^{e\_2}(1 + \sum\limits\_{k=1}^{23} b\_{2,23-k}\cdot 2^{-k})) \\ &= 2^{-127}(2^{e\_1} + \sum\limits\_{k=1}^{23} b\_{1,23-k}\cdot 2^{e\_1-k} - 2^{e\_2} - \sum\limits\_{k=1}^{23} b\_{2,23-k}\cdot 2^{e\_2-k})\\ &=2^{-127}(2^{e\_1} - 2^{e\_2} + \sum\limits\_{k=1}^{23} b\_{1,23-k}\cdot 2^{e\_1-k} - \sum\limits\_{k=1}^{23} b\_{2,23-k}\cdot 2^{e\_2-k})\\ &=2^{-127}(2^{e\_1} - 2^{e\_2} + \sum\limits\_{k=1}^{23}(b\_{1,23-k}\cdot 2^{e\_1-k}-b\_{2,23-k}\cdot 2^{e\_2-k})) \end{align\*} $

Now since $e\_1 \> e\_2 \iff e\_1-e\_2 \> 0 \iff 2^{e\_1}-2^{e\_2} \> 1$ we have that:

$ \begin{align\*} f\_1-f\_2 & \> 2^{-127}(1 + \sum\limits\_{k=1}^{23}(b\_{1,23-k}\cdot 2^{e\_1-k}-b\_{2,23-k}\cdot 2^{e\_2-k})) \end{align\*} $

In order for the above to always be greater than zero I require that $\sum\limits\_{k=1}^{23}(b\_{1,23-k}\cdot 2^{e\_1-k}-b\_{2,23-k}\cdot 2^{e\_2-k}) \> -1$.

However, I don't know how to formally show this. Any help/hints are much appreciated as inequalities are not my strong suit.

# Answer
> 0 votes
If we study the expression for a floating point number, $$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k}),$$

and pay attention to the sum $\sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k}$, we note that

$$0 \leq \sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k} \leq \sum\limits\_{k=1}^{23} 2^{-k} \< \sum\limits\_{k=1}^\infty 2^{-k} = 1,$$

where the last equality is formed by evaluating the geometric series. Thus we find that

$$2^{e-127} \leq2^{e-127}(1 + \sum\limits\_{k=1}^{23} b\_{23-k}\cdot 2^{-k}) \< 2^{e-127}\cdot 2$$

Thus if $s = 0$ and $e\_1 \> e\_2$ we find that $f\_2 \< 2^{e\_2 - 127} \cdot 2 \leq 2^{e\_1 - 127} \leq f\_1$.

Note that if $s = 1$ and $e\_1 \> e\_2$, the signs are reversed and we actually have $f\_2 \> f\_1$. But always $|f\_1| \> |f\_2|$.

---

The extended result of the above is that if we ignore the effects of denormal numbers, NaNs, infinities and say that $-0 \< 0$, we have

$$f\_1 \< f\_2 \iff n\_1 \< n\_2,$$

where $n\_1, n\_2$ are the bit patterns of $f\_1, f\_2$ interpreted as $w$-bit two's complement integers.

# Answer
> 0 votes
The relevant bit:

> I'm trying to find out if the following statement is true: $e\_1 \> e\_2 \> 0$ and $s\_1 = s\_1$ then $f\_1 \> f\_2$.

If course it is not true. If both numbers are negative then $e\_1 \> e\_2 \> 0$ implies that $f\_1 \< f\_2 ≤ 0$.

Apart from that:

1. If the signs are different then the positive number is greater than the negative one, with the exception that +0 and -0 are equal, and if one is +NaN and the other is -NaN then they are unordered.
2. If the signs are both positive, then the number with the greater exponent is greater, and if the exponents are the same then the number with the greater mantissa is greater, with the exception that +NaN compares unordered to anything.
3. If the signs are both positive, and the exponent and mantissa are the same, then the numbers are equal except +NaN compares unordered to anything.
4. If the signs are both negative, then use the same tests as for positive signs, except that you replace "greater" with "less".

---
Tags: floating-point
---


# Question
Title: Prove that the language Cats-Vs-Dogs is undecidable
Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not both.}.

# Answer
> 1 votes
Rice's theorem will give a direct and simple proof for this question.

# Answer
> 1 votes
If you have not yet learned Rice's Theorem you can use a Turing reduction here, which is essentially a proof by contradiction. We want to show that some undecidable problem can be reduced to Cats-Vs-Dogs, which would mean that if we could decide Cats-VS-Dogs, we could decide that undecidable problem, a contradiction! Let's use the halting problem. We know that the language {\<M,w\> | M halts on w} is undecidable.

Suppose Cats-VS-Dogs is decidable and let T be a decider for it. Construct the TM S as follows:

On input: \<S',w\>
$\quad$ Construct Machine M as follows:
$\quad\quad$ On input x:
$\quad\quad\quad$ if x is 'dogs' ACCEPT
$\quad\quad\quad$ run S' on w
$\quad\quad\quad$ if x is 'cats' ACCEPT
$\quad$ Run T on \<M\>
$\quad$ If T accepts REJECT otherwise ACCEPT

Notice that if S' halts on w then L(M) contains both 'dogs' and 'cats,' so when we run T on \<M\> T will reject since it decides the Cats-VS-Dogs problem, in this case S accepts. On the other hand if S' does not halt on w then L(S') contains 'dogs' but not 'cats' since running S' on w will never halt. In this case when running T on \<M\> T will accept, so S rejects. Then L(S) = {\<M,w\> | M halts on w}.

Also notice that the machine called M is never run by S, just constructed and its description passed to T. Since T decides Cats-VS-Dogs T always halts, so S always halts too. Then S decides {\<M,w\> | M halts on w} and we have obtained our contradiction!

---
Tags: formal-languages, turing-machines, automata, undecidability
---


# Question
Title: Is well-founded recursion enough for practical total functional programming?
Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt.

Well-founded recursion is a recursive definition of a function such that the definition of $f(x)$ only ever makes a recursive call $f(y)$ when $y\<x$ for some well-founded relation $\<$.

But the wikipedia page of Total functional programming refers also to other types of provably-terminating recursion:

> \[Termination is guaranteed by\] a restricted form of recursion, which operates only upon 'reduced' forms of its arguments, such as Walther recursion, substructural recursion, or "strongly normalizing" as proven by abstract interpretation of code.

Are there any ways that one can do *better* than well-founded recursion, for practical total functional programming? I've always thought of well-founded recursion as "the most general provably terminating recursion"

# Answer
> 2 votes
Let's restrict ourselves to the model of Turing machines (or, in general, of state machines). Consider complete states $s\_1, s\_2$ of the Turing machine (a complete state is a state specifying the full configuration of the Turing machine). We say that $s\_1 \gets s\_2$ if and only if we transition from $s\_2$ directly to $s\_1$.

It is easy to see that the Turing machine will terminate from any state if, and only if, $\gets$ is a well-founded relation.

A similar result holds for a strict language based on the $\lambda$-calculus. It's possible to determine whether a given term $T$ will reduce to a normal form by considering the $\beta$-reduction relation $\gets\_\beta$ on all terms which $T$ can be reduced to. $T$ will reduce to a normal form under any reduction order if and only if $\gets\_\beta$ is well-founded.

Thus, it's really not possible to get any more general than well-founded relations for proving termination.

---
Tags: recursion, functional-programming
---


# Question
Title: Reinforcement learining basics - is it possible to deal with environment with random events
As part of data science course I would like to solve particular problem with reinforcement learning algorithm.

I believe I understand general concept, however the problems I had read about up till now had no random factor included. I would like to ask if it's valid to assume that reinforcement learning algorithm will be able to find **"good" (somewhat close to optimal) solution when, at each step, one or more random events can occur**, provided that we know the probability of those events?

**For practical example that I can think of:** let's say we have to find exit from labyrinth as quick as possible, on each turn we can decide to rest or move. If we move, we become more tired, which increases probability that we will fall and twist our ankle (if this happens our speed is reduced for several turns). We know what's the probability of falling on each turn, but we do not know if this will really happen or not. During rest we reduce probability of falling.

In my project I would like to include several (around 5) of such random events.

**Is it correct to assume that reinforcement learning algorithm should be able to find a valid solution, despite such random factors?** We can define "valid" as, for example, in 90% of cases taking less than X turns. If yes, I would highly appreciate if you could point me in right direction, or to any materials describing practical solutions to such problems.

Thank you in advance for your input and sorry in case this question is really basic (hopefully not)!

# Answer
> 2 votes
Yes, in general reinforcement learning algorithms can handle random events in the environment. Think about the q-learning update rule $$ Q(s\_t,a\_t)= Q\_{s\_t, a\_t} + \alpha \left(r\_{t+1} + \gamma max\_aQ(s\_{t+1},a)\right) $$ But remember $$Q(s\_{t+1},a) = \mathbb{E}\_\pi\left( \sum\_{i=t+2}^T\gamma^{i-1}r\_{i} \right)$$ that is the *expected value* of the discounted sum of future rewards. This handles randomness in the environment quite well and eventually the value will adjust to factor in these random events. In a tabular environment this will always converge to the optimal value function and corresponding policy.

If you know the environment dynamics (which it seems like you do here) $$ p\left(s', r\mid s,a\right)$$ you can use a dynamic programming method like policy iteration or value iteration to efficiently compute an optimal policy and value function. I recommend looking at the first 4 chapters of *Reinforcement Learning: An Introduction* by Sutton and Barto (at least chapters 3 and 4). The text is available freely online on their website at their website.

---
Tags: randomness, reinforcement-learning
---


# Question
Title: Closest Pair of Points Algorithm - Fortune and Hopcroft
I am interested in implemented the deterministic ${O(n\log(\log(n)))}$ algorithm for the closest pair of points problem described here by Fortune and Hopcroft: https://ecommons.cornell.edu/bitstream/handle/1813/7460/78-340.pdf

In particular I would like to have a solution to the two-dimensional case.

They say: "The algorithm is based on the following observation: suppose we can find an interval size such that at most one point falls within each interval, and there are two nonempty adjacent intervals. Then to determine the closest pair we need only examine, for each point, the intervals surrounding the point". And for the one dimensional case which they describe in detail, the initial interval size is selected by taking `(max(S) - min(S))/n` where ${S}$ is the collection of points and ${n}$ is the number of points.

They claim the extension to higher dimensions is "obvious", but it's not at all clear to me how this above line might be generalised.

Does anyone have any suggestions? Many thanks.

# Answer
> 1 votes
One thing that you might not be aware of is that there's a 'hidden' exponential factor (it's explained on page 3). In $k$ dimensions the runtime is $O(kn \log(\log(n)) + 3^kn)$, as when you partition $k$-dimensional space into hypercubes each cube has $3^k - 1$ neighbors.

The rest of the algorithm really is 'obvious' then: you split your space up in hypercubes (which is just a fancy word for splitting up each dimension separately into intervals). Each point will then map to exactly one cube, and the rest of the algorithm follows.

E.g. suppose our interval size is $1$ and our domain is $\[0, 10)$. Then in 1D we have that the point $3.4$ maps to bucket $3$ and $8.8$ maps to bucket $8$. In three dimensions if our interval size and (per-dimension) domain is the same, we have that $(2.3, 8.4, 4.4)$ maps to bucket $(2, 8, 4)$ and $(4.1, 5.2, 9.5)$ maps to $(4, 5, 9)$. So you end up with three-dimensional buckets but the algorithm hashes the buckets afterwards so that doesn't matter.

---

If you have anything more than two or three dimensions my suggestion would be to look for another algorithm.

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


# Question
Title: Give the Regular-Expression (NFA) with specific Separation Patterns
Question: Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.

Attempt: Followed the way we construct the set of strings such that $a$ occurs the odd number of times, I got the following solution: $$b^\*a(bb(bb)^\* abb(bb)^\*a)^\*$$ But then I found the pattern $abbaa$ is not acceptable, as $a$ can appear multiple times consecutively. Is there any systematic way to solve the above problem?

# Answer
> 0 votes
I'll assume that no $a$s can appear together without interruption by a group of $(bb)^+$s, even if they form a group of odd $a$s. In that case

$$ a(bb)^+ (a(bb)^+ a(bb)^+)^\* $$

should suffice, where $x^+$ is defined simply as $x^+ = x x^\*$.

---
Tags: complexity-theory, regular-languages, finite-automata, regular-expressions
---


# Question
Title: Doubt regarding the implications of a 2-SAT constraint
Consider an example 2-SAT instance with the constraint (x1 ∨ x2). This CNF has these two implications:

¬x1→x2 and ¬x2→x1.

"They actually mean, if x1 is false then x2 must be true, and if x2 is false then x1 must be true, respectively. Any other case would make the 2-sat problem unsatisfiable."

My doubt is regarding this statement. I can understand the above written two implications, but I don't understand how only those two values of x1 and x2 make this 2-SAT instance satisfiable. Clearly setting both x1 and x2 to true can also satisfy this constraint. I don't see that case being captured in the two implications written above.

Can someone explain this to me? Apologies if this is a stupid question, I haven't formally studied logic.

# Answer
$A\rightarrow B$ doesn't necessarily mean that $B\rightarrow A$. In your example, "$x\_1$ is false then $x\_2$ must be true" doesn't imply that if $x\_2$ is true, $x\_1$ must be false. Therefore, setting both $x\_1$ and $x\_2$ to true would not contradict the statement.

Also, as a side note, $\lnot x\_1\rightarrow x\_2$ is logically equivalent to $\lnot x\_2 \rightarrow x\_1$, so the two implications you described are identical.
> 2 votes

---
Tags: logic, propositional-logic, 2-sat
---


# Question
Title: calculating the string similarity of an optimal alignment
## description of the algorithms behavior

I have two strings `s1` and `s2`, with $len\\\_s1 \<= len\\\_s2$. I would like to find the substring of `s2`, that has the biggest similarity to `s1`. The following alignments are possible:

```
[s2[:i] for i in range(len_s1)] + [s2[i:i+len_s1] for i in range(len_s2))]

```

e.g. for `s1="ab"` and `s2="abcde"` the following alignments should be considered:

```
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

```

The similarity between `s1` and the substring `s2_substr` of `s2` is defined in terms of a normalized version of the InDel Distance. The InDel-Distance is a variation of the Levenshtein distance, that only allows the use of insertions and deletions (this can be e.g. achieved using a weight of 2 for substitutions). The distance is normalized in the following way: $1 - dist / (len\\\_s1 + len\\\_s2\\\_substr)$. I am using a bitparallel algorithm to calculate the InDel-Distance in $O(\[len\_s1/w\]len\_s2)$ with the computer wordsize `w` (64 bit or higher when using SIMD). The algorithm is described in the paper New Bit-Parallel Indel-Distance Algorithm by Heikki Hyyrö.

### Example

Here is a small example that shows how this algorithm works: For this example I am using the same example string shown above (`s1="ab"` and `s2="abcde"`). As shown above this generates the possible substrings of `s2`:

```
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

```

These substrings have the following similarities to `s1`

| s1 | len\_s1 | s2\_substr | len\_s2\_substr | distance | similarity |
| --- | --- | --- | --- | --- | --- |
| 'ab' | 2 | '' | 0 | 2 DEL -\> 2 | 1 - 2 / (2+0) = 0 |
| 'ab' | 2 | 'a' | 1 | 1 DEL -\> 1 | 1 - 1 / (2+1) = 0.66 |
| 'ab' | 2 | 'ab' | 2 | 0 | 1 - 0 / (2+2) = 1 |
| 'ab' | 2 | 'bc' | 2 | 1 INS, 1 DEL -\> 2 | 1 - 2 / (2+2) = 0.5 |
| 'ab' | 2 | 'cd' | 2 | 2 INS, 2 DEL -\> 4 | 1 - 4 / (2+2) = 0 |
| 'ab' | 2 | 'de' | 2 | 2 INS, 2 DEL -\> 4 | 1 - 4 / (2+2) = 0 |
| 'ab' | 2 | 'e' | 1 | 1 INS, 2 DEL -\> 3 | 1 - 3 / (2+1) = 0 |

In this case the alignment 'ab' \<-\> 'ab' has the biggest similarity, so the function should return a similarity of 1.

## Naive solution

A naive sliding window approach could calculate the distance in the following way:

```
max_similarity = 0
for s2_substr in variations:
    substr_similarity = similarity(s1, s2_substr)
    max_similarity = max(max_similarity, substr_similarity)

```

However this would have to test `len_s1 + len_s2` possible alignments, so it has a complexity of `O([len_s1+len_s2]*[len_s1/w]*len_s2`. This becomes very slow for longer strings.

## Different implementations of this algorithm

A relatively similar implementation is included e.g. in the Python library `FuzzyWuzzy`, which searches for the longest common substrings of `s1` in `s2`. The starting points of those substrings are then used to calculate the best alignment. However it is not guaranteed, that the optimal alignment starts with one of the longest common substrings and therefore calculates a wrong similarity in many cases.

## Question

Is there a faster algorithm to calculate this kind of similarity? The algorithm has the following requirements:

1. defines similarity in Terms of the normalized InDel-Distance
2. allows Gaps at start and end of `s2`
3. when `s2_substr` is not placed at the start or end of `s2` it requires the length `len_s1`

As suggested by D.W. the smallest distance with gaps at start and end can be found by making insertions to the smaller string free in the start (init first row of the distance matrix with 0 instead of insertion costs). The smallest value in the result row is the distance for the smallest alignment. However this approach has a couple of problems:

1. it does not guarantee, that the length of the substring `s2_substr` is `len_s1` for substrings that do not start at the start or end of `s2`. (Maybe this could be guaranteed with a modification, that I am just not aware of)
2. it searches for the alignment with the smallest InDel Distance. However I am trying to optimize the normalized InDel Distance as described above. Since the normalization depends on the length of the substring `s2_substr`, which is not constant (at start/end of the string it can be smaller than `len_s1`), this does not always give the correct results.

# Answer
I think you should be able to adapt the standard dynamic programming algorithm to this, with a minor modification: you simply treat deletions at the beginning and end of `s2` as costing 0.
> 0 votes

---
Tags: algorithms, strings, matching, edit-distance, string-matching
---


# Question
Title: Subset of nodes such that all nodes of a graph are adjacent
We have been given a graph $G$, we need to find a subset of nodes $S$ such that each node of the graph is in $S$ or is adjacent to a node from $S$. Additionally, the elements of the subset $S$ should not be adjacent to each other neither should they share a common neighbour node.

This is an example of the given problem: In the given graph, the subset $S = $ {2, 4} is a valid solution as $3$ and $5$ are adjacent to 2 while $1$ and $6$ are adjacent to $4$. Further, $2$ and $4$ are not adjacent neither do they share a common neighbour.

The subset $S = $ {4, 5} is NOT valid as $4$ and $5$ have a common neighbour $1$.

I have been looking for an efficient way to do this; my attempt at an algorithm gives an exponential time complexity.

Any hints are appreciated, thanks in advance.

# Answer
This is an exact cover problem, so you could use standard algorithms for exact cover; or you could use a SAT solver.
> 0 votes

# Answer
In the literature, such a subset is called a *perfect code*.

As it is NP-complete to determine if a given graph has a perfect code, even on some very restricted inputs, your exponential-time algorithm is probably about as good as it gets.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Do a pair of parallel edges form a cycle in a graph
Whenever there is a back edge, a cycle is detected. Then, do a pair of parallel edges form a cycle in a graph? If no, why it is not a back edge?

# Answer
Graph theory is notorious for having nonequivalent definitions of the same term being used by different authors in different places, so it is important to check the definition of the terms in your case. If you use the definition I'm familiar with \begin{align\*} &\text{A }\textit{cycle }\mathcal{C}\text{ is an alternating sequence of vertices and edges, beginning with a vertex }v\_0\\ &\text{ such that no vertices or edges repeat except that }v\_0\text{is both the first and last element}\\ &\text{of the sequence} \end{align\*} In that case if $G=(V,E,f)$, $v\_1,v\_2\in V$, $e\_1,e\_2\in E$ and $f(e\_1) = f(e\_2) = \\{v\_1,v\_2\\}$ then $v\_1e\_1v\_2e\_2v\_1$ is a cycle in $G$.
> 1 votes

---
Tags: graphs
---