# Question
Title: How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
I have following language $L:= \\{a^n b^n c^m \mid n \neq m; n,m \ge 0 \\}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.

In any case, i need to choose $w = uv^iwx^iy$ so that $w \in L$.

I tried $a^p b^p c^{p+1}$ , $a^p b^p c^{p+p!}$ ($p$ \- Pumping Length) and couple of others. All of my proofs converged to 5 cases:

1. Only A (both $v$ and $x$ pump $a$'s),
2. A & B ($v$ pumps $a$'s, $x$ pumps $b$'s),
3. Only B (both - $b$'s),
4. B & C ($v$ \- $b$'s, $x$ \- $c$'s),
5. Only C (both - $c$'s).

Cases #1-#4 are not a problem, but in #5 $w \in L$ regardless $i$ chosen (cause condition is not broken). Thus, how do i choose the word here?

This page hints to take p!-Trick, but it doesn't work here..?

# Answer
Your analysis is correct. In order to keep the $a^n b^n c^m$ structure of the string, the only ways to pump are case (2) pump both $a$'s and $b$'s, or case (5) pump only $c$'s. All other case will distroy the structure of the string.

You applied the $p!+p$-trick, and consider the string $a^p b^p c^{p!+p}$. In case (2) this will indeed pump to a string of the form $a^{p!+p} b^{p!+p} c^{p!+p}$ outside of the language because all segments are of equal length. No luck in case (5), you are right.

The solution is to apply Ogden's Lemma. The Lemma is like the common Pumping Lemma for CF languages where we count so called "marked" positions in a word. By marking the $a$'s in the string one is forced to pump $a$'s, so only case (2) applies.

Apart from a mirror-like symmetry this is explained in the application for inherent ambiguity of Ogden in wikipedia.
> 1 votes

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


# Question
Title: The math behind the time complexity of Heap Insertion
Insertion into a heap is an O(logn) operation. Insertion of n elements into a heap one by one is summarised as O(n * logn). I wonder about the math behind this, because I could not reach to the same outcome.

Let's say we have an empty heap h = \[\].

* The first insertion will be a constant time operation, say O(1)
* The second insertion will also be O(1), because there was only one element in the heap
* The third will be O(log2) and so on

So if we write it down, the overall time complexity will be:

O(1 + 1 + log2 + log3 + ... + log(n-1)) = O(2 + log(n - 1)!) = O(logn!) approximately, which is nowhere close to O(n * logn).

# Answer
$$\ln(n!)=\ln\left(\prod\_{k=1}^nk\right)=\sum\_{k=1}^n\ln(k)\approx\int\_{k=0}^n\ln(t)\\,dt=(t\ln(t)-t)\Big|\_{t=0}^n=n\ln(n)-n.$$

One can show that the approximation error does not impact the asymptotic behavior.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit
You are given the number $m$ and $m$ intervals of the form $a\_i, b\_i, v\_i$, where $a\_i\<=b\_i$ and $v\_i\>0$ and also a number $n$ and an array $s$ of length $n$, where $s\_i\>0$. In one operation you can choose an interval say $j$ and decrease the values of $s\_i$ by 1, where $a\_j\<=i\<=b\_j$, and you can choose interval $j$ at most $v\_j$ times. The task is to find the minimum number of operations required to make all elements of $s$ non-positive.

My approach is some greedy where I sort the intervals by the starting point, and then iterate over the values of $s$ and if $s\_i$ is positive I repeatedly find the first starting interval that contains index i and apply the minimum necesary ammount of operations. The way I do the update it is with segment trees. Overall, I am not convinced this greedy approach is right.

# Answer
Your greedy approach does not work. Consider the $m=2$ intervals $\[1,2\]$ and $\[2,3\]$ each of which can only be used once. Let the array $s$ of $n = 3$ elements be $\langle 0, 1, 1 \rangle$.

Your approach uses $2$ operations, namely it chooses first the interval $\[1,2\]$ and then the interval $\[2,3\]$. However, the minimum number of operations needed to solve the problem is $1$ (i.e., simply choose $\[2,3\]$).
> 0 votes

# Answer
There is actually a quite simple greedy algorithm that lets us pick one interval after the other in an optimal way. At any point we do the following:

1. Find the smallest i with $s\_i \> 0$. If there is no such i then we are done. If there is a smallest i, then we need to pick an interval containing i at some point, so we pick it right now.
2. Among all the intervals $\[a\_j .. b\_j\]$ with $v\_j \> 0$ containing i, that is with $a\_j ≤ i ≤ b\_j$, we pick the one with the largest $b\_j$ and remove it, then we go back to Step 1. Removing an interval with a larger $b\_j$ is never less good than removing one with a smaller $b\_j$, so this will lead to an optimal solution if one exists.

What happens with Steven's counter example against the original algorithm? We have $s\_2 \> 0$ and $s\_3 \> 0$. In Step 1 $i = 2$ is the smallest i. Both intervals contain $i = 2$, but for the interval \[2 .. 3\], $b\_j = 3$ has the largest value, so we pick the interval \[2 .. 3\], decrease $s\_2$ and $s\_3$, and now we have no i with $s\_i \> 0$ anymore.
> 0 votes

---
Tags: greedy-algorithms, intervals, segment-trees
---


title: Order in a subset

text:
# Question
Title: Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (\<="n" consecutive 0s) AND (\<="n" consecutive 1s).

Then, we want to find the order of values in the resulting subset incrementally.

Also, we want to do the "un-ordering" of the values. i.e. find the value of the subset from the given order.

Note: The order must be found only by checking the subset value, and not by trying to iterate all values upto that value. This will be efficient for a large "K" range of digits.

Example:

> K = 6

> n \<= 2 consecutive 0s AND 1s

```
000000 -> (>2 consecutive 0s OR 1s) -> remove from subset
000001 -> (>2 consecutive 0s OR 1s) -> remove from subset
000010 -> (>2 consecutive 0s OR 1s) -> remove from subset
000011 -> (>2 consecutive 0s OR 1s) -> remove from subset
000100 -> (>2 consecutive 0s OR 1s) -> remove from subset
000101 -> (>2 consecutive 0s OR 1s) -> remove from subset
000110 -> (>2 consecutive 0s OR 1s) -> remove from subset
000111 -> (>2 consecutive 0s OR 1s) -> remove from subset
001000 -> (>2 consecutive 0s OR 1s) -> remove from subset
001001 -> (<= 2 consecutive 0s AND 1s) -> order [1]
001010 -> (<= 2 consecutive 0s AND 1s) -> order [2]
001011 -> (<= 2 consecutive 0s AND 1s) -> order [3]
001100 -> (<= 2 consecutive 0s AND 1s) -> order [4]
001101 -> (<= 2 consecutive 0s AND 1s) -> order [5]
001110 -> (>2 consecutive 0s OR 1s) -> remove from subset
001111 -> (>2 consecutive 0s OR 1s) -> remove from subset

010000 -> (>2 consecutive 0s OR 1s) -> remove from subset
010001 -> (>2 consecutive 0s OR 1s) -> remove from subset
010010 -> (<= 2 consecutive 0s AND 1s) -> order [6]
010011 -> (<= 2 consecutive 0s AND 1s) -> order [7]
010100 -> (<= 2 consecutive 0s AND 1s) -> order [8]
010101 -> (<= 2 consecutive 0s AND 1s) -> order [9]
010110 -> (<= 2 consecutive 0s AND 1s) -> order [10]
010111 -> (>2 consecutive 0s OR 1s) -> remove from subset
011000 -> (>2 consecutive 0s OR 1s) -> remove from subset
011001 -> (<= 2 consecutive 0s AND 1s) -> order [11]
011010 -> (<= 2 consecutive 0s AND 1s) -> order [12]
011011 -> (<= 2 consecutive 0s AND 1s) -> order [13]
011100 -> (>2 consecutive 0s OR 1s) -> remove from subset
011101 -> (>2 consecutive 0s OR 1s) -> remove from subset
011110 -> (>2 consecutive 0s OR 1s) -> remove from subset
011111 -> (>2 consecutive 0s OR 1s) -> remove from subset

100000 -> (>2 consecutive 0s OR 1s) -> remove from subset
100001 -> (>2 consecutive 0s OR 1s) -> remove from subset
100010 -> (>2 consecutive 0s OR 1s) -> remove from subset
100011 -> (>2 consecutive 0s OR 1s) -> remove from subset
100100 -> (<= 2 consecutive 0s AND 1s) -> order [14]
100101 -> (<= 2 consecutive 0s AND 1s) -> order [15]
100110 -> (<= 2 consecutive 0s AND 1s) -> order [16]
100111 -> (>2 consecutive 0s OR 1s) -> remove from subset
101000 -> (>2 consecutive 0s OR 1s) -> remove from subset
101001 -> (<= 2 consecutive 0s AND 1s) -> order [17]
101010 -> (<= 2 consecutive 0s AND 1s) -> order [18]
101011 -> (<= 2 consecutive 0s AND 1s) -> order [19]
101100 -> (<= 2 consecutive 0s AND 1s) -> order [20]
101101 -> (<= 2 consecutive 0s AND 1s) -> order [21]
101110 -> (>2 consecutive 0s OR 1s) -> remove from subset
101111 -> (>2 consecutive 0s OR 1s) -> remove from subset

110000 -> (>2 consecutive 0s OR 1s) -> remove from subset
110001 -> (>2 consecutive 0s OR 1s) -> remove from subset
110010 -> (<= 2 consecutive 0s AND 1s) -> order [22]
110011 -> (<= 2 consecutive 0s AND 1s) -> order [23]
110100 -> (<= 2 consecutive 0s AND 1s) -> order [24]
110101 -> (<= 2 consecutive 0s AND 1s) -> order [25]
110110 -> (<= 2 consecutive 0s AND 1s) -> order [26]
110111 -> (>2 consecutive 0s OR 1s) -> remove from subset
111000 -> (>2 consecutive 0s OR 1s) -> remove from subset
111001 -> (>2 consecutive 0s OR 1s) -> remove from subset
111010 -> (>2 consecutive 0s OR 1s) -> remove from subset
111011 -> (>2 consecutive 0s OR 1s) -> remove from subset
111100 -> (>2 consecutive 0s OR 1s) -> remove from subset
111101 -> (>2 consecutive 0s OR 1s) -> remove from subset
111110 -> (>2 consecutive 0s OR 1s) -> remove from subset
111111 -> (>2 consecutive 0s OR 1s) -> remove from subset

```

# Answer
These are known as ranking and unranking algorithms. See, e.g., https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/

Let $\text{rank}(x)$ denote the rank of $x \in \\{0,1\\}^K$, i.e., the number of $K$-bit strings that lexicographically precede $x$ and satisfy your requirements (no more than $n$ consecutive 0's or 1's).

Define $f\_{K,n}(w)$ as the number of $K$-bit strings that start with $w$ and that satisfy your requirements (no more than $n$ consecutive 0's or 1's). $f\_{K,n}(w)$ can be computed in polynomial time by forming a DFA for the regular language of $K$-bit strings that start with $w$ and satisfy your requirements, and then counting the number of strings accepted by this DFA. (See https://cstheory.stackexchange.com/q/8200/5038 and https://cs.stackexchange.com/a/71379/755.)

$\text{rank}(x)$ can be expressed as a sum of at most $K$ terms of the form $f\_{K,n}(w)$. Specifically,

$$\text{rank}(x) = \sum\_{i=1}^K x\_i f\_{K,n}(x\_{1 \cdots i-1} 0).$$

By the above remarks, this gives a polynomial-time algorithm for computing $\text{rank}(x)$.

Let $\text{unrank}(n)$ denote the unranking of $n \in \mathbb{N}$, i.e., the string $x$ such that $\text{rank}(x)=n$. You can obtain an algorithm for computing $\text{unrank}(n)$ in polynomial time, using filling in one bit of $x$ at a time and calling $\text{rank}(\cdot)$ at each step. For instance, if $\text{rank}(100\cdots 0) \> n$, then $x$ starts with 0, otherwise $x$ starts with $1$; and so on.
> 2 votes

---
Tags: combinatorics, sets, arithmetic, binary
---


title: Recursive array

text:
# Question
Title: Recursive array
The following is a function to write a recursive function that accepts an array and a callback. Function returns true if a single value in array returns true when passed to the callback otherwise it returns false.

I have trouble understanding the "if not" line written here(line 4), how does the cb interact with arr? Please help.

```
def isOdd(num):
    if num%2==0:
        return False
    else:
        return True

def someRecursive(arr, cb):
    if len arr == 0:
        return False
    if not(cb(arr[0])):     #Maybe till it is an empty array. DOUBT HERE
        return someRecursive(arr[1:],cb)
    return True

```

# Answer
> 1 votes
The if not branches says that the program continues to recurse if the first element of the array does not satisfy `cb` (`cb(arr[0])` returns false).

The function checks the condition `cb` on one (the first) element at every call, and give the rest to the next recursion. Since the first element is removed at every iteration, `arr[0]` is different in each function call.

Once `not(cb(arr[0]))` gives false, the function returns True, and the return value propagates back to previous iterations.

# Answer
> 1 votes
The function starts by checking for an empty array and returns *false* in that case.

Otherwise, it tests the first element of the array and returns *true* if the condition *cb* is met. Otherwise, it recurses with the array less the first element.

Said differently, the function recursively scans the array until some element fulfills the condition, and reports if there is one.

---
Tags: arrays, python
---


# Question
Title: Connection between NAND gates and Turing completeness
I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing completeness? It seems to me that NAND gate circuits are closer to finite automata than Turing machines. My intuition is that I can build flip-flops, and therefore registers and memory, out of NAND gates, and unbounded memory is a crucial property of Turing complete systems. I'm looking for a more theoretical or mathematical explanation, or pointers on what to read.

# Answer
There is indeed little connection. For a thorough understanding, let me explain the connection between *programs* and *circuits*.

A *program* (or *algorithm*, or *machine*) is a mechanism for computing a function. For definiteness, let us assume that the *input* is a binary string $x$, and the *output* is a Boolean output $b$. The size of the input is potentially unbounded. One example is a program that determines whether the input is the binary encoding of a prime number.

A (Boolean) *circuit* is a collection of instructions for computing some *finite* function. We can picture the circuit as an electrical circuit, or think of it as a sequence of instructions (this view is called confusingly a *straight-line program*). Concretely, we can assume that the *input* is a binary string $x$ **of length $n$**, and the *output* is Boolean. One example is a circuit that determines whether the input encodes a prime number (just as before, only now the input has to be of length $n$).

We can convert a program $P$ into a circuit $P\_n$ that simulates $P$ on inputs of length $n$. The corresponding sequence of circuits $P\_0,P\_1,P\_2,\ldots$ is not arbitrary – they can all be *constructed* by a program that given $n$ outputs $P\_n$. We call such a sequence of circuits a *uniform* circuit (confusingly, we often think of the sequence as a "single" circuit $P\_n$ for an indefinite $n$).

Not every sequence of circuits is uniform. Indeed, a sequence of circuits can compute *every* function from strings to Boolean, computable or uncomputable! Nevertheless, in complexity theory we are interested in such *non-uniform* models in which the circuits are restricted. For example, the question P=NP states that NP-complete problems cannot be solved by polynomial time algorithms. This implies that NP-complete problems cannot be solved by polynomial size uniform circuits. It is moreover conjectured that NP-complete problems cannot be solved by polynomial size circuits *without the requirement of uniformity*.

Turing-complete computation models are models which realize all computable functions (and no more). In contrast, complete systems of gates (such as AND,OR,NOT or NAND) allow computing arbitrary *finite* functions using circuits made of these gates. Such complete systems can compute completely arbitrary functions using (unrestricted) sequences of circuits.
> 13 votes

# Answer
You are in fact correct. A combinational logic circuit is equivalent to a finite automaton. NAND gates do not make them more powerful; they are used because it is simply cheaper to build a digital logic circuit with only one kind of gate than it is to build it with all different gates. In fact, a NAND gate can be constructed from just an AND gate and a NOT gate. Flip-flops make the circuit Turing-complete. Here is a handy key:

Combinational circuits ~ Finite automata ~ Regular languages ~ Regular expressions ~ Propositional calculus ~ Straight line programs

Sequential circuits ~ Turing machines ~ Recursively enumerable languages ~ Predicate calculus ~ $\mu$-recursive functions

If you want to learn more, there is a very good book you can download in PDF form for free that explains all this:

https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf
> 6 votes

# Answer
Logical gates alone can do little, they can just build combinatorial logical systems.

But as soon as you add a clock, *states* become possible and you can build sequential systems and devices such as Turing machines or any kinds of processors.
> 0 votes

# Answer
Its because nand is another statement for distinction/contradiction --- contradictions are bad in logic because they make 'every possible statement true and its possible to build a contradiction out of a NAND more or less directly (just negate one input and tie them together). This is the deeper theoretical reason for a NAND gate's universality.
> -3 votes

---
Tags: turing-machines, turing-completeness, digital-circuits
---


title: optimization problem in CV

text:
# Question
Title: optimization problem in CV
hopefully I'm writing this post in the adequate place if not please move my post

I'm reading this paper about L-shaping fitting for vehicles. and ran into this optimization in the photo attached.

in the paper it is written that due to the combinatorial complexity of the partition problem it is not easy to solve the optimization, but what does partition has to do with it ?

I have a simple solution for each theta given: the given theta creates 2 perpendicular lines(l1,l2) that correspond to P,Q from the paper. for every point: measure the distance from the point to each line and add the point to the corresponding group of the closest line.

why wouldn't it work? or why is it not computationally possible ? the algorithm I'm proposing here seems to be O(N\*k) - N number of points and k - number of degrees we test

thanks everyone :)

# Answer
What the author means - and is right in thinking so - is that from an analytical point of view, the optimization is arduous. This is because the objective function depending on the three parameters $\theta,c\_1,c\_2$, also depends on the assignments of the points to $P$ and $Q$, which can be made in $2^m$ ways.
> 1 votes

---
Tags: optimization, computer-vision
---


# Question
Title: How to simplify this regular expression?
How do i prove that the regular expression $$a^\*(ba^\*)^\*$$ is the same as $$(a+b)^\*$$. Is there a way to prove this using regular expression identities?

# Answer
> 0 votes
Clearly, the second expression generates all strings made of $a$ and $b$.

Now, by induction, with the first expression:

* you can generate the empty string $\epsilon$, as $a^0(ba^\*)^0$;
* any string generated with this expression can be appended with a $b$, which is $(ba^0)^1$;
* any string generated with this expression can be appended with a $a$:

+ either the string is $a^\*$, and $a^\*a=a^\*$,
    + or the string is $a^\*(ba^\*)^+$, and $a^\*(ba^\*)^+a=a^\*(ba^\*)^\*(ba^\*)a=a^\*(ba^\*)^\*(ba^\*)=a^\*(ba^\*)^+$.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Division of Large Numbers with Known Factors
Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a\_1 \cdot \dots \cdot a\_n$ and $b = b\_1 \cdot \cdots \cdot b\_m$. Required is their quotient $$ \frac a b = \frac {a\_1 \cdots a\_n} {b\_1 \cdots b\_m} $$ of which is also known that it is a (positive) integer.

More formally: $A$ is supposed to be an algorithm with the following properties:

**Input:** $a = a\_1 \cdot \dots \cdot a\_n$ and $b = b\_1 \cdot \cdots \cdot b\_m$, $a\_1, \dots, a\_n, b\_1, \dots, b\_m \in \mathbb N$.

**Output:** $\frac a b$ of which we know $\frac a b \in \mathbb N$.

Desired is an algorithm with good asymptotic run time.

---

**Answers to the comment section:**

* We know that $b \> 1$ and that the quotient $\frac a b$ is a natural number, therefore there are common factors *somewhere*. Unfortunately I have no precise answer.
* Regarding the (previously existing) algorithm idea: Even if none of the pairs are divisible, then one can still multiply up all numbers in the numerator and divide by the product of all numbers in the denominator. In other words, looking for pairs is supposed to simplify the computations. In particular if the product of the numbers $a\_1 \cdots a\_n$ is very large, one might not be able to store these numbers in a, say, 32-bit integer.

# Answer
Here is a suggestion for an algorithm that might satisfy your constraints.

First, we'll come up with an upper bound $M$ for the quotient $a\_1a\_2\dots a\_n/b\_1b\_2\dots b\_m$. There are many acceptable ways to do this: the first way that comes to mind is round each $a\_i$ up to the next largest power of two and round each $b\_i$ down to the next smallest power of $2$. This will give you an upper bound $M$ which is at most $2^{n+m}$ times larger than the product. Of course, you can get a tighter approximation by taking logarithms (and you may wish to, if your goal to work entirely with machine-word arithmetic).

The next step is to choose a set of primes $\\{p\_k\\}$ with the property that $\prod\_k p\_k \geq M$. It should be sufficient to take the first $\log M$ primes here (if you really want to optimize things, you can take the first $O(\log M / \log \log M)$ primes -- see https://en.wikipedia.org/wiki/Primorial).

The strategy is now as follows. We will compute the value $v\_k$ of this quotient modulo each prime $p\_k$. We will then use the Chinese Remainder Theorem to find the unique integer $v$ in the range $\[1, M\]$ congruent to $v\_k$ modulo $p\_k$ (if the quotient $a/b$ is indeed an integer, it must equal $v$).

How do we compute the value $v\_k = (a/b) \bmod p\_k$? This is fairly standard modular arithmetic -- the trick is to first factor out all factors of $p\_k$ in the $a\_i$ and $b\_j$. If there are more factors in the numerator than denominator then $v\_k = 0$. Otherwise, you can just reduce each of the $a\_i$ and $b\_j$ modulo $p\_k$, take the modular inverses of the $b\_j$, and multiply them all together.

There are a couple of ways to implement the Chinese remainder theorem part. One very explicit way to do this is to just compute

$$v = \sum\_{k} v\_k \left(\prod\_{k' \neq k} p\_{k'}\right) w\_k \bmod P$$

where $P = \prod p\_k$, and $w\_{k} = \left(\prod\_{k' \neq k} p\_{k'}\right)^{-1} \bmod p\_k$. Note that the total number of primes you have will be small (logarithmic in your total answer) so this is a small computation.

So, this gives an algorithm to recover $v$ only using arithmetic between small numbers (if $P$ fits in a machine word, all these operations can be done with machine-word arithmetic). Is it more efficient than the naive approach? If you end up using $\ell$ primes here, your total complexity is on the order of $O(\ell(n + m))$ (assuming all primes stay machine-word-size). And as stated, we can take $\ell$ to be $\log M$, for a complexity of $O((n+m)\log M)$, where $M$ is any upper bound on the quotient.

Now, if you naively multiply the numbers in e.g. the numerator together it might take $O(n^2)$ time to complete the computation of the numerator (if each multiplicand fits in a word, the $i$th multiplication is between an $i$-word number and a $1$-word number, which takes time $O(i)$; summing from $i = 1$ to $n$ gives $O(n^2)$). But you can also reduce this to something closer to $O(n \mathrm{poly}\log n)$ by i. using the FFT-based multiplication algorithms mentioned in the comments and ii. repeatedly multiplying the two smallest numbers you have in the numerator. So you can also get this idea to work in quasi-linear time with some effort.

**Edit**:

Actually, I just realized that this is probably overkill for what you want to do. You can also just repeatedly take GCDs of each term $b\_j$ in the denominator with each $a\_i$ in the numerator, cancelling out common factors. This is probably the fastest way to solve your type of problem, and will have equally good time complexity. I'll leave the CRT-based write-up here for now though, since it is often a useful tool for these sorts of questions.
> 1 votes

---
Tags: algorithms, reference-request, arithmetic
---


# Question
Title: Is a predecessor subgraph always connected?
Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G\_{p}$ of $G$ is always connected?

Here's how the predecessor subgraph is defined: for a graph $G = (V, E)$ with source $s$, the **predecessor subgraph** of $G$ is $G\_{p} = (V\_{p}, E\_{p})$, where $V\_{p} = \\{ v \in V : v.p \neq NIL\\} \cup \\{s\\}$ and $E\_{p} = \\{ (v.p, v) : v \in V\_{p} - \\{s\\}\\}$

I've read that the predecessor subgraph forms a tree, but in the context of that claim, it was assumed the predecessor subgraph is connected and $|E\_{p}| = |V\_{p}| - 1$.

Can anyone offer a proof that the predecessor subgraph $G\_{p}$ of a graph $G$ is always connected (or disprove the claim)?

# Answer
> 1 votes
Let $s$ be your source vertex and let $d(v)$ denote the distance from $s$ to $v$. Let $v\_1, \dots, v\_n$ be the vertices of your graph in non-decreasing order of distances from $s$.

You can show by induction on $i$ that the subgraph $G\_i$ of $G\_p$ induced by $\\{v\_1, \dots v\_i\\}$ is connected.

The base case is trivial as $G\_1$ contains only $v\_1=s$.

Consider now $i\>1$. It suffices to argue that $G\_i$ contains an edge $(v\_j, v\_i)$ for some $j\<i$. By definition, the predecessor $p(v\_i)$ of a vertex $v\_i$ (w.r.t. the source $s$) ensures that there is a shortest path from $s$ to $v\_i$ that first goes from $s$ to $p(v\_i)$ and then traverses the edge $(p(v\_i),v)$. Since edge-weights are non-negative, $d(p(v\_i)) \< d(v\_i)$ which shows that $p(v)=v\_j$ for some $j\<i$.

Since your graph has exactly $n-1$ edges and it is connected, it is actually a tree.

---
Tags: graphs, algorithm-analysis, subgraphs
---


# Question
Title: Computing an initial ellipsoid for solving a convex program
Suppose we want to find a vector $x\in R^n$ that satisfies the constraints $g\_i(x)\leq 0$, for $i\in 1,\ldots, m$, where all $g\_i$ are convex functions. The functions can be given by an oracle access: there is an oracle that, given x, returns $g\_i(x)$. If this helps, we can also have an oracle for their derivative $g\_i′(x)$.

This is a special case of convex programming, and it is known that it can be solved (at least approximately) by the ellipsoid method.

But to use the ellipsoid method, we need an initial ellipsoid, that contains the feasible region. In all papers I read, this step is either skipped, or it is assumed that the initial ellipsoid is given. I did not find an explanation of how such an initial ellipsoid can be computed, given just the functions $g\_i$.

QUESTIONS:

* Is there a general procedure for finding an ellipsoid for a given convex program, that can be used to initialize the ellipsoid method?
* If there is no general procedure, then what are some special cases in which such an ellipsoid can be computed efficiently? What conditions are needed so that the initial ellipsoid can be computed efficiently?

# Answer
So considering this answer for unconstrained minimization:

> For any $n$, let $f$ be a $\sigma$ strongly convex function, write $$\epsilon = \left\\|\nabla f(0) \right\\|\_2$$ then the ball of radius $\epsilon / \sigma$ around 0 includes the minimum.

I suppose one could use the penalty method or barrier method in terms of converting the constrained optimization problem to an unconstrained one and finding an initial ellipsoid. It looks like you don't really have an optimization term here, so we could just have the value "0" for the constrained version. Since that answer specifies needing a $\sigma$ strongly convex function to be optimized you could most likely achieve this using the penalty method - the value of the penalty constants shouldn't matter I believe since these would then come out naturally into the calculation of $\sigma$ and $\epsilon$ and I believe would cancel out.
> 1 votes

---
Tags: optimization, numerical-analysis, convex-hull
---


# Question
Title: Regular expression for binary string containing no instances of 01
In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\\{00,01,10,11\\}$ and it is clear that we need to enumerate some expression that avoids the following combination of strings: 01, 00+10,00+11, 10+11. I'm just having finding trouble enumerating the regular expression to fulfill these following invariants.

# Answer
> 2 votes
If there is a $0$, it may not be followed by a $1$, so the string is made of "not $0$s" followed by $0$s.

$$1^\*0^\*$$

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


# Question
Title: Why is `3[arr]` notation of accessing elements in array is not used?
Today, I came across the notation `3[arr]` in C++, and I was surprised to find out that it's a valid way to access array elements. For example:

```
int arr[] = {10, 20, 30};
int element = 1[arr]; // This compiles and works!

```

Online IDE: https://onlinegdb.com/4o8qnsx8O

The assembly of this looks exactly same

```
arr:
        .long   10
        .long   20
        .long   30
main:
        push    ebp
        mov     ebp, esp
        sub     esp, 16
        mov     eax, DWORD PTR arr+4    ; getting 20 from arr variable, store in eax
        mov     DWORD PTR [ebp-4], eax  ; store eax to variable "a"
        mov     eax, DWORD PTR arr+4    ; getting 20 from arr variable, store in eax
        mov     DWORD PTR [ebp-8], eax  ; store eax to variable "b"
        mov     eax, 0
        leave
        ret

```

Disassembly from Godbolt: https://godbolt.org/z/dEaYjashs

While this notation seems to work, it's somewhat unconventional, and I'm curious if it's considered a good practice in C++ programming. In natural language, we say "Accessing 3rd element of array arr", then isn't `3[arr]` notation fits better here?

My questions are:

1. Is using `3[arr]` a valid and safe practice in C++?
2. Are there any specific situations or use cases where this notation might be advantageous?
3. Is there any guideline or convention against using `3[arr]` that I should be aware of?

I haven't encountered this notation in any code I've seen so far, so any insights or advice on its usage would be greatly appreciated.

# Answer
Since addition is commutative, we can use any accessor method. But in programming, the more code is **human-understandable**, the better it is ranked. And that is why guidelines exist.

In this case, using `arr[3]` is more readable than `3[arr]`. Instead of array, let's think in term of hashmaps: Suppose you are asked to get *third key* key in the *my\_map* (and you can use same notion of in hashmap key access), which is more readable `"third key"[my_map]` or my\_map\["third key"\]. To me, its second one.
> 0 votes

# Answer
The C++ standard says "The built-in subscript expression `E1[E2]` is exactly identical to the expression `*(E1 + E2)`...". So `3[arr]` is `*(3+arr)` is `*(arr+3)` is `arr[3]`.

https://en.cppreference.com/w/cpp/language/operator\_member\_access
> -1 votes

---
Tags: arrays, memory-management, c
---


# Question
Title: What is the difference between quantum computing and parallel computing?
Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the difference or how are they different?

# Answer
> 1 votes
***Disclaimer 1**: I am in no way, shape or form an expert on this topic. I am not even an amateur. All my knowledge on quantum computing comes from reading a single book and implementing a puny quantum circuit simulator. So please take everything I say with a table spoon of salt.*

***Disclaimer 2**: Definitions are a tricky thing. Technically, quantum computing allows for a special form of parallel computing called quantum parallelism. In addition to quantum parallelism, the traditional concepts of parallel computing should still be applicable: You should be able to apply two or more arithmetic / logic / quantum operations to subgroups of Your quantum bits (qbits) in parallel.*

*With that out of the way, in the following I will try to point out two key differences between **quantum parallelism** and **classical parallelism**.*

## Short Answer

Out of my head, I can think of two key differences between *classical parallelism* and *quantum parallelism*:

* *Classical parallelism* requires multiple physical logical/arithmetic/processing units to operate in parallel. *Quantum parallelism*, on the other hand can be achieved by a single arithmetic/logic/processing unit, and the level of quantum parallelism increases with the number of qbits.
* During quantum computer operation, the qbits can be in an intricate, entangled state, which enables quantum parallelism. But as soon as You query a result (by measuring), the quantum state collapses to a classical bit state with each measured qbit becoming either 0 or 1. This limits the amount of information You can retrieve from a quantum parallel computation.

## Example

Let's say you have a classical computer with four bits of memory. At one point in time, this memory can be in one of 16 states: $ 0000\_2, 0001\_2, 0010\_2, \dots, 1111\_2$. We could, somewhat inefficiently, describe the memory state using a 16-dimensional state vector $s$ as follows:

* $0000\_2$: $s = \[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\]$
* $0001\_2$: $s = \[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0\]$
* $0010\_2$: $s = \[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0\]$
* $0011\_2$: $s = \[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0\]$
* $\dots$
* $1111\_2$: $s = \[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1\]$

For our classical computer, this state vector always contains exactly one $1$ and fifteen $0$ entries. If we, however, turn this classical computer it into a quantum computer, the quantum state $s$ can suddenly be any real-valued\[1\] vector as long as it has norm 1, i.e. $s \in \mathbb{R}^{16}, \lVert s\rVert\_2=1$. This means our quantum computer can be in multiple classical bit states at the same time, e.g.

$$ \hat{s} = \[0,\sqrt{1/2},\sqrt{1/2},0,0,0,0,0,0,0,0,0,0,0,0,0\]$$

Would be a valid quantum state which equally combines the classical states $0001\_2$ and $0010\_2$. Lets now say we want to apply a classical arithmetic operation to our quantum computer: A two-bit integer addition:

$$ (\operatorname{bit}\_4\operatorname{bit}\_3)\_2 \leftarrow (\operatorname{bit}\_4\operatorname{bit}\_3)\_2 + (\operatorname{bit}\_2\operatorname{bit}\_1)\_2 \mod 4 $$

Where $\operatorname{bit}\_1$ is the least significant qbit. In our state vector space, we can conveniently describe this operation as matrix multiplication $A s$, where $A$ is the following permutation matrix:

$$ A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

If we apply this operation to $\hat{s}$, we get:

$$t = A \hat{s} = \[0, 0, 0, 0, 0, \sqrt{1/2}, 0, 0, 0, 0, \sqrt{1/2}, 0, 0, 0, 0, 0\]$$

This means by applying our operation a single time to our quantum state, we have performed two classical operations. *That* is quantum parallelism. But there is a problem: We cannot query the result. If we try to measure the qbits of our new quantum state $t$, it will collapse into one of two classical states:

* $t\_1 = \[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\]$
* $t\_2 = \[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0\]$

For all we know, this collapse happens randomly. In our simple example both $t\_1$ and $t\_2$ happen with equal probability of $50\\%$.

Even though we have computed two additions in (quantum) parallel, we can only randomly retrieve one of the two results. *That* is the measuring problem. So in order make use of quantum parallelism the final output state should be either a classical state or close to a classical state so that it can be measured by running the computation a constant number of times.

*\[1\] Technically $s$ could also be a vector of complex or quaternion values, maybe even octonions, depending on quantum computer.*

# Answer
> 0 votes
For a parallel computer, we need to have one billion different processors. In a quantum computer, a single register can perform a billion computations. This is known as quantum parallelism. Also a quantum computer returns a single randomly-selected correct result, while a parallel computer can directly return all valid results. That's the reason why reading results out of quantum computers generally is slow and getting all results requires running the quantum computation enough times to be relatively certain that the random sampling has seen all possible results.

Hope this helps!

See this also: differences-between-quantum-computing-and-parallelism

# Answer
> -3 votes
One big difference is that in parallel computation separate processors need not be executing copies the same instruction at the same time in lockstep; they may be more loosely synchronized or in some cases completely desynchronized. In fact, separate processors need not be executing the same sequence of instructions. This is the distinction between SIMD \[Single Instruction, Multiple Data\] and MIMD \[Multiple Instruction, Multiple Data\] parallelism. Quantum computers are by nature SIMD (interpreting quantum superposition as equivalent to processor replication).

Phrased another way: With multi-core you can run all the different processes on a laptop simultaneously; you cannot do that with a quantum processor.

---
Tags: computation-models, parallel-computing, quantum-computing
---


# Question
Title: How to maintain completely dynamic convex hull quickly?
If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)

A completely dynamic convex hull means that I can insert and delete a point without rebuilding the whole convex hull, which costs $O(n)$'s time.

My problem is, is there any solutions to deleting points quickly? Maybe it could be solved with persistent data structures, but up to now, I haven't come up with any concrete method yet.

# Answer
> 3 votes
This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".

# Answer
> 2 votes
You can use my code. I implemented the ideas from the paper by Overmars and van Leeuwen. https://github.com/sumeetshirgure/DynamicPlanarHull/tree/master

---
Tags: data-structures, time-complexity, computational-geometry
---


# Question
Title: Understanding the Recursive Algorithm for Integer Division
In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\text{Input: Two n-bit integers x and y, where }y ≥ 1\\\\ &\text{Output: The quotient and remainder of x divided by y}\\\\ \\\\ &\text{if $x = 0$: return $(q, r) = (0, 0)$}\\\\ &\text{$(q, r)$ = divide$(\lfloor x/2\rfloor, y)$}\\\\ &\text{$q = 2 · q, r = 2 · r$}\\\\ &\text{if $x$ is odd: $r = r + 1$}\\\\ &\text{if $r ≥ y: r = r − y, q = q + 1$}\\\\ &\text{return $(q, r)$}\\\\ \end{align}

I am trying to understand the internal mathematical working of this recursive algorithm for division.

There is a similar recursive algorithm for multiplication given in my reference,

\begin{align} &\text{function multiply $(x, y)$}\\\\ &\text{Input: Two n-bit integers $x$ and $y$, where $y≥0$}\\\\ &\text{Output: Their product}\\\\ \\\\ &\text{if $y = 0$: return $0$}\\\\ &\text{$z$ $=$ multiply$(x, by/2c)$}\\\\ &\text{if $y$ is even:}\\\\ &\quad\text{return $2z$}\\\\ &\text{else:}\\\\ &\quad\text{return $x + 2z$}\\\\ \end{align} The operation of the multiplication algorithm can be understood as follows: $$ x.y=\begin{cases} 2(x.\lfloor y/2\rfloor)\text{ if }y\text{ is even}\\\\x+2(x.\lfloor y/2\rfloor)\text{ if }y\text{ is even} \end{cases} $$ which can be verified as, \begin{align} y&=2n\implies 2(x.\lfloor y/2\rfloor)=2(x.\lfloor n\rfloor)=2xn=x.2n=xy\\\\ y&=2n+1\implies x+2(x.\lfloor y/2\rfloor)=x+2(x.\lfloor n+1/2\rfloor)=x+2xn=x(1+2n)=xy \end{align}

But is it possible to understand the given division algorithm in a similar way ?

# Answer
> 2 votes
Suppose $x$ is divided by $y$, and the quotient is $q$ and remainder is $r$. Then, it means the following:

$$x = q \cdot y + r \quad \quad \textrm{where} \quad r \< y. \quad \quad (1)$$

Consider the case when $x = even$. Then, $x = 2x'$. Suppose that $x'$ when divided by $y$ gives quotient $q'$ and remainder $r'$. Then, we have:

$$x = 2x' = 2 \cdot (q'\cdot y + r') \quad \quad \textrm{where} \quad r' \< y. \quad \quad (2)$$

By equation $(1)$, we have

1. for $2r' \< y$, we get $q = 2q'$ and $r=2r'$.
2. for $2r' \> y$, we get $q = 2q'+1$ and $r=2r'-y\<y$. This step follows from the fact that $2r'\<2y$.

You can show a similar proof for $x = odd$.

# Answer
> 0 votes
The division algorithm You are trying to understand is basically a recursive description of good old long division, albeit in binary form. You can think of the following line:

$$ (q,r) = divide(\lfloor x/2\rfloor,y) $$

As moving the divisor $y$ one binary digit to the left. This is done recursively until the least significant digit of $y$ is left of the most significant digit of $x$. From there the actual long division starts by repeatedly shifting in the next bit of $x$, determining the next bit of the quotient $q$, all the while keeping track of the remainder $r$.

# Answer
> 0 votes
Instead of directly dividing $x$ by $y$, you divide $x\div 2$ by $y$ and multiply the quotient by $2$. This gives an approximate quotient, and the rest of the computation is a correction to get the true quotient, which may be off by one unit ($x\div y=2( (x\div2)\div y)$ or $2( (x\div2)\div y)+1$). Notice that $x\div2$ amounts to dropping the least significant bit of $x$.

This principle is applied recursively, up to the moment that $x\<y$, so that the quotient is zero.

# Answer
> 0 votes
One can prove by induction on $x\ge 0$ that $$(q,r) =\text{divide}(x,y)\Longrightarrow x=q y + r\text{ and }0\le r\le y-1$$ Indeed this is true when $0=x$ because $0=0.y + 0$. When $1\le x$, first note that $2\le x+\[x\text{ odd}\]$, where $\[\text{ }\]$ is Iverson's bracket, hence $$0\le\left\lfloor\frac{x}{2}\right\rfloor= \frac{x-\[x\text{ odd}\]}{2}\le\frac{x + (x-2)}{2}= \frac{2x-2}{2}=x-1\<x$$ So after $(q, r) = \text{divide}(\left\lfloor\frac{x}{2}\right\rfloor,y)$, the induction hypothesis implies that $$\frac{x-\[x\text{ odd}\]}{2}=q y+r\quad\text{and}\quad 0\le r\le y-1$$ Hence $$x= (2q)y + (2 r +\[x\text{ odd}\])$$ If $2 r +\[x\text{ odd}\]\< y$, this is an euclidean division of $x$ by $y$ and the algorithm correctly returns $(2q, 2 r +\[x\text{ odd}\])$ to satisfy the induction hypothesis. When $y \le 2 r +\[x\text{ odd}\]$, one can write $$x= (2q+1)y + (2 r +\[x\text{ odd}\]-y)$$ and it holds $$0\le 2 r +\[x\text{ odd}\]-y\le 2(y-1)+\[x\text{ odd}\]-y\le y-1$$ so this is again an euclidean division an the algorithm correctly returns $(2q+1, 2 r +\[x\text{ odd}\]-y)$.

---
Tags: algorithms, recursion
---


# Question
Title: Efficient algorithm for finding a point P with the highest winding number
Given an ordered list of two-dimensional points $P$ that represent the vertices of an $N$-sided (very) self-intersecting polygon, find a point $p\_{best}$ with the highest winding number of all points within that polygon represented by $P$.

Sunday's algorithm sounds great for efficient calculation given one point, but selection of what points to query seems difficult. Originally, I thought one arbitrarily selected point infinitesimally to the right/left of each segment would be sufficient, or that a point at the, but both do not account for e.g. the center of star polygons.

One approach that would work would be to break down each segment at each crossing point, and then selecting a point to the right / left of each sub-segment. Is that necessary, though? In the worst case, a star polygon with N segments could have $O(N^2)$ sub-segments once broken down.

The context for this is finding what area I've "run the most circles around" given my Google Maps point-by-point tracking data, so N is on the order of 10,000 to 100,000. I am curious because I have a guess it'd be something on my commute, but I'm not sure.

# Answer
Yes, you can "break down each segment at each crossing point", and then you'll get a *Planar Subdivision* or Planar straight-line graph. All the edges of this graph will be **oriented** according to the natural orientation of the original self-intersecting polygon. It's easy to see that all the points, belonging to the same **face** of this graph, will have the same winding number - so actually you need to find a face with maximal winding number.

Now observe that winding numbers of two faces, having a common edge, **differ by one**. If you move from a face with winding number $N$ to its neighboring face, crossing their common edge, oriented from **left to right** \- this neighboring face will have winding number $N+1$. And vice versa, if you cross the edge, oriented from right to left, the face winding number will be decremented.

The winding number of the external face is **zero**. So, you can start from the external face and calculate winding numbers of all faces, jumping from face to face across their common edges. Now, take the face with maximal winding number and choose any point inside it - this will be your $p\_{best}$.
> 1 votes

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


# Question
Title: Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
Is the language $L=\\{1^n2^n3^m : n\neq m\\}$ context free?

I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?

# Answer
> 1 votes
The language is not context free, and indeed Ogden's Lemma can be used to show so. See the answer in the following duplicate.

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


# Question
Title: Z Notation: sequence of sequences - find sum
Let me just say that this is for a university project. I do not expect an answer but more of a "hint".

I have a schema of a Supermarket that holds a sequence of queues:

```
+-- Supermarket-------
|queues: seq Queue
----------------------

```

And here is how I've defined a queue:

```
+-- Queue ----------
|length: ℕ
--------------------

```

I wish to define a schema that returns the total number of customers, waiting in line. Thus far I have:

```
+--TotalQueueCustomers----
|Ξsupermarket: Supermarket
|totalCustomers!: ℕ
|-------------------------
|totalCustomers = total θ supermarket
--------------------------

```

I'm struggling with defining the `total` function. It needs to "loop" every customer in every queue and sum their `length`s. Here is what I have so far: `total = q: Queue ⦁ q.length ↦ q.length`

Any idea?

# Answer
> 1 votes
I am not aware of the Z notation but here's what you have to do:
step 1: initialize a variable total to 0
step 2: loop through all queues
step 3: add the length of every queue to total

# Answer
> 1 votes
To specify the $\mathit{TotalQueueCustomers}$ operation it helps to know that, in Z (and VDM and B), a sequence is a function from a finite prefix of the positive integers to the element type. Here your element type is $\mathit{Queue}$. To express the sum of the $\mathit{length}$ components of all the $\mathit{Queue}$s in your $\mathit{queues}$ you would want to write the Z-equivalent of this big sum in mathematics: $$\sum\_{i=1}^{\\#\mathit{queues}}\mathit{queues}(i).length$$ where $\\# s$ is the length of sequence $s$ and $z.a$ is component $a$ of schema $z$. Your operation becomes the following.

```
+-TotalQueueCustomers------------------------------------------------
| ΞSupermarket
| totalCustomers!: ℕ
|--------------------------------------------------------------------
| totalCustomers! = Σi ∙ (1 ≤ i ≤ #queues | queues(i).length)
---------------------------------------------------------------------

```

Note that it includes just two copies of `Supermarket`, the plain one and a primed one. No need to give them new names (as you did with `supermarket`).

---
Tags: formal-methods, z-notation
---


# Question
Title: T(n) = T(n-1) + T(n-1) vs T(n) = 2*T(n-1)
If I have 2 version of code

1.)

```
def T(n):
    if n == 0:
        return 1
    return T(n-1)+T(n-1)

```

2.)

```
 def T(n):
    if n == 0:
        return 1
    return 2 * T(n-1)

```

Is my understanding correct that the time complexity of the first function is O(2^n) and the second function is O(n)

# Answer
> 2 votes
Yes, the running time of the first is $\Theta(2^n)$ unless you have tail-call optimization or you do memoization.

The running time of the second is $\Theta(n)$.

Beware that the *input size* is actually $\log\_2 n$ which would make the latter function actually run in time $O(2^{\left| x \right|})$ where $x$ is the size of the input.

---
Tags: time-complexity
---


title: What is most efficient for GCD?

text:
# Question
Title: What is most efficient for GCD?
I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case, I decided to use Java, but C/C++ may be another option).

I need to use the most efficient code possible in my program.

In recursive mode, you can write:

```
static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

```

And in iterative mode, it looks like this:

```
static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

```

---

There is also the Binary algorithm for the GCD, which may be coded simply like this:

```
int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

```

# Answer
Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for `%` which I don't know by heart). In the recursive version, let $a\_i$ and $b\_i$ be the argument of the $i$th recursive call: $$\begin{gather\*} a\_{i+1} = b\_i \\ b\_{i+1} = a\_i \mathbin{\mathrm{mod}} b\_i \\ \end{gather\*}$$

In the imperative version, let $a'\_i$ and $b'\_i$ be the values of the variables `a` and `b` at the beginning of the $i$th iteration of the loop. $$\begin{gather\*} a'\_{i+1} = b'\_i \\ b'\_{i+1} = a'\_i \mathbin{\mathrm{mod}} b'\_i \\ \end{gather\*}$$

Notice a resemblance? Your imperative version and your recursive version are calculating exactly the same values. Furthermore, they both end at the same time, when $a\_i=0$ (resp. $a'\_i=0$), so they perform the same number of iterations. So algorithmically speaking, there is no difference between the two. Any difference will be a matter of implementation, highly dependent on the compiler, the hardware it runs on, and quite possibly the operating system and what other programs are running concurrently.

The recursive version makes only tail recursive calls. Most compilers for imperative languages do not optimize these, and so it is likely that the code they generate will waste a little time and memory constructing a stack frame at each iteration. With a compiler that optimizes tail calls (compilers for functional languages almost always do), the generated machine code may well be the same for both (assuming you harmonize those calls to `abs`).
> 26 votes

# Answer
For numbers that are small, the binary GCD algorithm is sufficient.

GMP, a well maintained and real-world tested library, will switch to a special half GCD algorithm after passing a special threshold, a generalization of Lehmer's Algorithm. Lehmer's uses matrix multiplication to improve upon the standard Euclidian algorithms. According to the docs, the asymptotic running time of both HGCD and GCD is `O(M(N)*log(N))`, where `M(N)` is the time for multiplying two N-limb numbers.

Full details on their algorithm can be found here.
> 9 votes

# Answer
As I know Java doesn’t support tail recursion optimization in general, but you can test your Java implementation for it; if it doesn’t support it, a simple `for`-loop should be faster, otherwise recursion should be just as fast. On the other hand, these are bit optimizations, choose the code you think is easier and more readable.

I should also note that the fastest GCD algorithm is not Euclid’s algorithm, Lehmer’s algorithm is a bit faster.
> 3 votes

# Answer
First, don't use recursivity to replace a tight loop. It is slow. Don't rely on the compiler to optimize it out. Second, in your code, you call Math.abs() within every recursive calls, which is useless.

In your loop, you can easily avoid temporary variables and swapping a and b all the time.

```
int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

```

Swapping using the a ^= b ^= a ^= b makes the source shorter but takes many instructions to execute. It will be slower than the boring swap with a temporary variable.
> 2 votes

# Answer
For **small numbers**, % is quite an expensive operation, perhaps the simpler recursive

```
GCD[a,b] := Which[
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

```

is quicker? (Sorry, Mathematica code and not C++)
> 0 votes

# Answer
*Disclaimer: Practical performance questions are highly application-specific and can only be satisfyingly answered by application-specific benchmarks that sufficiently represent field conditions. This answer uses a synthetic benchmark instead, which may not at all be representative of Your specific application.*

A while ago, I ran a little synthetic benchmark (long version here) to answer, once and for all, which one of the following GCD algorithms is the fastest:

* a) Subtraction-based Euclid's Algorithm
* b) Division/Modulo-based Euclidean Algorithm
* c) Binary GCD

The answer was a clear and resounding: d) A combination of all of the above. So without further ado, I proudly present to You: The tribrid GCD algorithm!

```
public static long tribridGCD( long x, long y )
{
  x = abs(x);
  y = abs(y);
  int l = Long.numberOfTrailingZeros(x); x >>>= l;
  int r = Long.numberOfTrailingZeros(y); y >>>= r;
  int shift = min(l,r);
  if( x > y ) {
    long z = x; x = y; y = z;
  }
  while( x != 0 ) {
    long z = x > (y>>>1) ? y-x : y%x;
    y = x;
    x = z;
    // Invariant: x <= y && (y is odd)
    x >>>= Long.numberOfTrailingZeros(x);
  }
  return y << shift;
}

```
> 0 votes

# Answer
What you present as the Binary GCD algorithm is *not* the Binary GCD algorithm, because it still uses the modulo (remainder) operator $\\%$ (in fact it is the standard algorithm with the swap-via-xor trick, which probably makes it slower). This is unfair in the comparison as modulo is a costly operation. The real Binary algorithm only uses shifts and subtractions, notoriously fast.

Anyway, telling the most efficient algorithm is not possible for several reasons:

* the answer can be machine-dependent,
* the answer can even be dependent on the input value, and
* the GCD is pretty fast to compute, and in practice it is impossible to measure short execution times accurately.
> 0 votes

# Answer
**Euclid Algorithm is most efficient for calculating GCD:**

```
Static long gcd(long a,long b)
{
if(b==0)
return a;
else
return gcd(,a%b);
}

```

***example:-***

```
Let A = 16, B = 10.
GCD(16, 10) = GCD(10, 16 % 10) = GCD(10, 6)
GCD(10, 6) = GCD(6, 10 % 6) = GCD(6, 4)
GCD(6, 4) = GCD(4, 6 % 4) = GCD(4, 2)
GCD(4, 2) = GCD(2, 4 % 2) = GCD(2, 0)

Since B = 0 so GCD(2, 0) will return 2.

```
> -2 votes

---
Tags: algorithms, recursion, arithmetic
---


# Question
Title: Finding growth rate of T(n) of a code segment
I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented:

```
sum = 0
for i = 1 to 2 * n
 for j = 1 to i * i
   for k = 1 to j
     sum++

```

I tried making this into a function called `run(n)` in Python that returns sum and got `run(1) = 11`, `run(2) = 192`, `run(3) = 1183`, and `run(4) = 4488`. However, my book only presents 3 possible answers, those being $\Theta(n^4)$, $\Theta(n^5)$, and $\Theta(n^6)$.

I don't think my results match any of these choices. I might be confused as to what the question is asking as it says

> present answers in terms of summations

or my code might be incorrect, but I am confused on what to do next. I am very new to algorithms, so any help would be appreciated.

# Answer
> 1 votes
The innermost loop increments `sum` exactly $j$ times. The middle loop runs $i^2$ times with increasing values of $j$ so it increments `sum` $\dfrac{i^2(i^2+1)}2$ times. And finally, the outer loop runs $2n$ times, for a total of $$\sum\_{i=1}^{2n}\frac{i^2(i^2+1)}2=\frac{n (1 + 2 n) (1 + 4 n) (2 + 3 n + 6 n^2)}{15}$$ incrementations. \[Thanks to Wolfram Alpha.\]

# Answer
> 0 votes
Let $I$ be the number of times the `for i` is executed, $J$ the number of times `for j`, and $K$ the number of times `for k` is executed.

1. $I$ is $\Theta(n)$ times
2. $J$ is $\Theta(I \cdot I) = \Theta(n^2)$ times
3. $K$ is $\Theta(J) = \Theta(n^2)$

The correct answer is the product of $I$, $J$ and $K$, i.e., $\Theta(n \cdot n^2 \cdot n^2) = \Theta(n^5)$.

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


title: Missing 770201 seconds in Y2K2038

text:
# Question
Title: Missing 770201 seconds in Y2K2038
From what I understand about the Y2K38 problem, unpatched 32 bit systems with signed UTC times will jump back from 19 January 2038 at 03:14:07 UTC to 13 December 1901, at 20:45:52. Calculating the difference between these date-times gives me 4294197095 seconds. That's not the same as 4294967296 seconds, off by 770201 seconds. That's 8 days, 21 hours, 56 minutes and 41 seconds.

I could imagine 2 hours, 3 minutes and 19 seconds of smear seconds. But then that leaves 9 days. Where did the time go?

(If this fits better on a different stackexchange site, please let me know which.)

# Answer
> 2 votes
I think you have an error in your math. 19 January 2038 at 03:14:07 UTC is $t\_1 = 2147483647$ seconds after the epoch. 13 December 1901 at 20:45:52 is $t\_2 = 2147483648$ seconds before the epoch.

Notice that $t\_1 = 2^{31}-1$ and that $ - t\_2 = -2^{31}$. That's exactly the minimum and maximum values representable by a signed 32-bit integer in two's complement. Unsurprisingly: $t\_1 - (-t\_2) = 2^{32}-1$, as expected.

```
$ t1=$(date -d "2038-1-19 03:14:07+00:00" +%s)
$ t2=$(date -d "1901-12-13 20:45:52+00:00" +%s)
$ echo "t1: $t1; t2: $t2; Difference: $(( $t1 - $t2 ))"
t1: 2147483647; t2: -2147483648; Difference: 4294967295

```

---
Tags: real-time
---


# Question
Title: An efficient way of finding the closest point of a sampled function to another point
I have a function $f(x)$, has been sampled into a sequence $$ y\_0, y\_1, ..., y\_{n - 1} $$ at points $x\_k = k \Delta x$. $f(x)$ is neither smooth or monotone.

Under this assumption, what is the fastest way of finding $$ \min\_{k=0}^{n - 1}|P - (x\_k, y\_k)| $$ where $P$ is an arbitrary point?

I could do a linear search, but I need to compute the minimum distance for $n^2$ different points which makes the overall algorithm $n^3$.

# Answer
> 3 votes
You can construct a Voronoi diagram for your points, and then use a point location algorithm. Because you need quadratic work regardless you don't even need an efficient algorithm for the Voronoi diagram.

# Answer
> 2 votes
If You sample the function once beforehand, the problem breaks down to a simple Nearest Neighbor Search. There are many different data structures and algorithms for solving the nearest neighbor problem.

As long as $x\_k$ and $y\_k$ are fairly low-dimensional, one popular solution is the kd-tree which can be build in $\mathcal{O}(n \log{n})$ for your $n$ sample points. Querying the closest sample points to the $n²$ search points usually takes $\mathcal{O}(n^2\log{n})$.

Kd-tree libraries are available in most programming languages, e.g. for NumPy, there is scipy.spatial.KDTree. Kd-trees are a fast general purpose solution but likely not the fastest specific solution.

---
Tags: computational-geometry
---


# Question
Title: RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a
i am reviewing older exams from my computational theories lesson in university and i am struggling to figure this one out: Construct a regular expression for the following language: Strings of even length in alphabet {a,b,c} that contain exactly one a.

Roughly translated from greek, hope it makes sense. Thanks

# Answer
The idea is that if a string contains one $a$, then it can be written as $xay$, where $x,y \in (b+c)^\*$. Furthermore, $xay$ has even length if either $x$ has even length and $y$ has odd length, or vice versa. Using this, it is straightforward to come up with a regular expression.
> 3 votes

# Answer
The answer you are looking for is: (b|c)((b|c)(b|c))\*a((b|c)(b|c))\* | a(b|c((b|c)(b|c))\*)

Logic behind this is: If you start with a, you need at least one more b|c and then as many b|c PAIRS as you want. Otherwise you can start with b|c combinations making sure they are an odd number, add the 'a' later to make it even in total and continue with b|c pairs.

Υ.Γ: Πες μου οτι διαβαζες θεωρια υπολογισμου απο Κατσαρο
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: How do I improve my problem-solving and creative thinking skills in Computer Science?
I am a CS undergrad trying to improve my problem-solving skills. I have noticed that I have a problem with theoretical computer science which I've been trying to fix largely unsuccessfully till now. I have noticed these in Undergrad courses such as *Theory of Computation*, *Algorithm Design*, *Discrete Mathematics*, *Game Theory* etc. I am able to understand most of the underlying theory pretty well and even visualize a lot of stuff but when it comes to solving problems during examinations, the correct approaches never seem to come to me. I have tried practising a lot of sample problems for such courses but it never seems to help with questions which involve some sort of **creative thinking**. I spend way too much time in a limited-time setting and end up not being able to come up with a seemingly 'obvious' solution. I have also noticed this with puzzles. In trying to isolate the problem, I've noticed that exam temperament is not the problem, since I'm able to do fairly well in Systems courses or courses which are not so puzzle-oriented. Here are some examples of questions I'm talking about:

* Write a Context Free Grammar $G$ such that $L(G)$ is \<given\>
* Find an algorithm for a multi-armed bandit problem which satisfies \<some given conditions\>
* Write an algorithm to solve a \<given task\> in \<given time complexity\>
* Prove that \<given language\> is not a regular language
* Find the Nash Equilibrium for a \<given game design\> etc

The common aspect of all such problems is that they can't be solved methodically, but rather there's that one creative manipulation/idea which splits the problem apart. How do I get my creative juices flowing and get better at solving such puzzling problems in a limited time frame?

*P.S. I really want to get better at this since I'm genuinely putting in a lot of time and effort but my scores don't seem to reflect that. I couldn't find the most appropriate tags for this question, but I've tried to enter what I felt was appropriate. Open to suggestions for better ways to frame the question!*

# Answer
> 5 votes
Without knowing You and Your personal situation, this question is almost impossible to answer. So all I can try to give is some general-purpose advice which hopefully gets You on the right track.

## Get Enough Sleep

Thanks to modern Hustle Culture, bright white LED-lighting and bright-screened smartphones that make noise every 2 minutes, it becomes harder and harder to get enough regular sleep. According to studies, sleep is very important for both learning and creative thinking. Pulling all-nighters for studying is a terrible idea.

Do not ever write a PHD or a Thesis for/with an idiot Professor that seems to celebrate and/or demand sleep deprivation of his employees! Burnout is a real risk with such superiors!

## Know Your Learning Type

Everybody learns differently. There are different psychological models of Learning Styles. These are just models, so don't get too lost in them, but it is good to roughly know which type of learner You are. This will give You a good idea how to study more efficiently.

## Find the Right Resources

Once You know Your learning type, it should be easier for you to pick the right resources. Sadly, You can usually not choose Your teacher. But You can pick and choose almost everything else. Do You get frequently stuck reading one book on some topic? Try another book that better suits Your learning style! If You are more of an audio-visual learner, You could try some open source online lectures like MIT OpenCourseWare.

## Bounce Your Ideas Off Somebody Else

The ability to explain a topic is a really good measure of how well You understand that topic. If You get stuck during explanation, You will quickly realize the gaps in Your knowledge.

It might be a good idea to join a study group. If study groups are not Your thing, talk to Your friends, Your goldfish or Yourself. If even if they do not understand a word of what You are saying it will still help You. If You are able to explain a topic to a layman or a child, You have achieved true understanding!

## Learn Programming

I cannot speak for other countries, but in Germany, I have met my fair share of graduated computer scientist who did not know a single programming language. Based on that experience, my advice is: Learn a programming language! A good starting language may be Python. Even if it doesn't improve your grades, it will make you a better computer scientist. But the ability to program can also be a great study help.

Need to understand context-free grammar? Why not implement you own Earley parser? Or use an existing parser, to write Your own silly little programming language?

Need to study algorithmic complexity? Why not implement some sorting algorithms and learn what makes them tick?

## Don't Beat Yourself Up!

It saddens me to hear that You seem to feel like You have to emphasize that You really want to learn. People try their best all the time and still fail sometimes. That's normal! That's human! Keep trying! That does not mean You didn't try hard enough!

In this modern Hustle Culture world, people are laser-focused on the success stories, the toxic, narcissistic tech billionaires and (wannabe) dictators. In truth, we could learn much more from our mistakes than our successes. But this modern Hustle Culture society seems to think, that people who fail, have done everything wrong, and people who succeed have done everything right. Nothing could be further from the truth. There is an interesting GDC talk that points out, just how clueless successful game designer are, for example.

People that focus on Your mistakes and tell You that "You just didn't try hard enough!" are absolutely toxic. Steer clear of those people and ignore them! Instead, look for the people that give advice on how to improve things in the future!

---
Tags: education, theory
---


title: 3sat to clique reduction program

text:
# Question
Title: 3sat to clique reduction program
I am searching for a program to convert 3sat to clique problem.

I tried following links

https://www.geeksforgeeks.org/maximal-clique-problem-recursive-solution/

https://www.geeksforgeeks.org/find-all-cliques-of-size-k-in-an-undirected-graph/

But it is not converting 3sat problem.

Is there any algorithm to convert 3sat to clique ?

# Answer
> 1 votes
Let 3-SAT formula $\phi$ be $C\_1 \wedge C\_2 \wedge \dots \wedge C\_m$, where $C\_i$ is a clause consisting of the disjunction of three literals: $(\ell\_i^1 \vee \ell\_i^2 \vee \ell\_i^3)$.

We can create an auxiliary graph $G$ as follows:

* For each clause $C\_i$ create three vertices $\ell\_i^1, \ell\_i^2, \ell\_i^3$, i.e., one for each literal. And add all edges between them.
* Add an edge between each pair of complementary literals. I.e., if $\ell\_i^h$ and $\ell\_j^k$ refer to the same variable but one literal is positive and the other is negated, then add the edge $(\ell\_i^h, \ell\_j^k)$.

Let $\overline{G}$ be the complement of $G$ (i.e., $\overline{G}$ has the same vertex set as $G$ and it contains an edge $e$ if and only if $e$ is not in $G$).

**Claim: The 3-SAT formula $\phi$ is satisfiable if and only if $\overline{G}$ contains a clique of size $m$.**

Proof ($\Longrightarrow$): Consider a truth assignment that satisfies $\phi$ and, for each clause $C\_i$ choose a literal $\ell^\*\_i$ that is true according to such an assignment. Notice that the set $L = \\{\ell^\*\_i \mid i=1,\dots,m\\}$ contains exactly one literal per clause (by definition) and does not contain any pair of complementary literals (since they cannot both be true). Then $L$ is an independent set of size $m$ of $G$, which means that the subgraph induced by $L$ must be a clique of size $m$ in to complement $\overline{G}$ of $G$.

Proof ($\Longleftarrow$): Let $L$ be the vertices of a of size $m$ in $\overline{G}$ and notice that $L$ must be an independent set in $G$. Since no independent set of $G$ can contain two literals from the same clause (all literals from the same clause have an edge between them), and since there are exactly $m$ clauses, $L$ contains exactly one literal $\ell\_i^\*$ from each clause $C\_i$. Moreover, this set of literals cannot contain any pair of complementary literals. Then you can find a satisfying assignment for $\phi$ by setting the variables according to the values of the literals in $L$. The "leftover" variables (if any) that do not correspond to any literal in $L$ can be set arbitrarily.

Here is the pseudocode of a possible implementation:

```
Inputs:
- the number m of triplets
- a list L of m triples. The generic j-th element of the i-th triple, denoted by L[i][j], contains either the index k>=1 of a variable to encode the positive literal on the k-th variable, or -k to encode the negated literal

Output: the list of edges of the graph resulting from the above reduction. The vertices of the graph are integers from 1 to 3m. The j-th literal of the i-th clause is vertex (i-1)*3+j.

For i = 1,2,...,m-1:
   For i' = i+1, i+2,....,m:
      For j = 1,2,3:
         For j' = 1,2,3:
            If L[i][j] != -L[i'][j']:
                Output the edge ((i-1)*3 + j, (i'-1)*3 + j')

```

---
Tags: p-vs-np, 3-sat, clique, java
---


# Question
Title: Alternatives to SVD for rank factorization
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \times m}$.

A popular approach is to compute the singular value decomposition (SVD) $M = UDV^\*$ and keep the columns of $U$ and rows of $V$ corresponding to the non-zero singular values. This is a great approach, especially since it behaves nicely under noise. However, SVD seems to compute more than I need for just rank factorization (and the noise tolerance is cool, but not necessary).

**What are the other approaches I can use?** In particular, I am interested in algorithms that have *one* (or more) of the following properties:

1. Outperform SVD asymptotically.
2. Outperform SVD in practice, or on special inputs (for a reasonably interesting class of special inputs).
3. Performance under small perturbation of $M$ is well understood.

I am fine with giving $k$ to the algorithm ahead of time. Note that SVD does not require this (unless we are doing a perturbation analysis, but even then we usually give a bound on perturbation size and determine $k$ at run-time based on that).

# Answer
The proper search term in scientific journals is *"Rank-Revealing Decomposition"*. If You want some theoretic guarantees on numeric accuracy/stability, the search term would be *"Strong Rank-Revealing Decomposition"*. There seems to exist a (strong) rank-revealing version of almost every type of decomposition:

## Practically Outperforming SVD

Most SVD implementations, e.g. in LAPACK, are incredibly highly optimized. The opposite is true for strong rank-revealing decompositions: There seem to be no optimized implementations at all. A while ago, I came up with an improved SRRQR variant. One of my very rough benchmarks seem to indicate that the aforementioned SRRQR version *could* potentially outperform LAPACK's SVD after putting a lot of elbow grease into it. A lot of research and development would be required. The same is likely true for all the other strong rank-revealing decompositions.

The only rank-revealing decomposition used in practice seems to be the RRQR. It outperforms the SVD by a considerable margin but not by an order of magnitude. In fact, the RRQR is used as part of the Jacobi SVD in LAPACK.

## Theoretically Outperforming the SVD

It is my strong belief that we do not yet know enough about decomposition algorithms to answer this question. In 1969, Strassen already found an $\mathcal{O}(n^{\log\_2{7}+\mathcal{o}(1)})$ algorithm for matrix inversion. Even faster algorithms like Coppersmith-Winograd have been found since. Do such algorithms exist for SVD? For (strong) rank-revealing decompositions? Can we make such algorithms numerically stable? As far as I know, we do not have the answers to these questions yet.

Most decompositions (including the SRRQR) use an $\mathcal{O}\left(\max{(m,n)}\cdot\min^2{(m,n)}\right)$ implementation, making their complexity identical in practice.

Current R&D seems to be heavily focused on sparse and tensor decompositions, so we will likely not get an answer to these questions any time soon.

## Numeric Accuracy/Stability

While RRQR works really accurately in practice, it is easy to construct synthetic examples where it fails completely (see Matrix Computations, 4th ed., Chapter 5.4.3).

The strong rank-revealing factorizations all make some theoretic guarantees of one kind of another which should make them more resilient to pathologically bad inputs.
> 3 votes

---
Tags: algorithms, machine-learning, numerical-analysis, linear-algebra
---


# Question
Title: Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing
I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition):

Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = xi.key. For keys ki and kj , we define the indicator random variable Xij = I {h(ki) = h(kj)}. Under the assumption of simple uniform hashing, we have Pr {h(ki) = h(kj)} = 1/m.

I know that the probability of a specific key being assigned to a slot is 1/m as a result of simple uniform hashing, hence Pr(h(ki)) = a = 1/m, Pr(h(kj)= a = 1/m. But I haven't been able to take the mental leap to infer from this that the probability of two keys being assigned to the same slot is 1/m. Is there any place on the internet where I can find proof of this?

# Answer
What is the probability of both being in slot 1, both being in slot 2, …., both being in slot m? And since these events are separate, you can add up those m probabilities and get the probability that two are the same.
> 1 votes

---
Tags: probability-theory, hashing
---


# Question
Title: Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?
Which function grows faster:

$$f(n) = 4^{n^2 \log\_2 n} \text{ or } g(n) = (n!)^n$$

Which is true?

* $f(n) = O(g(n))$
* $g(n) = O(f(n))$
* i.e., $f(n) = \Theta(g(n))$
* none of the above?

For lower values of $n$, it looks like $f(n)$ is bigger, but I'm not sure for very big values of $n$.

# Answer
With some manipulations: $$ f(n) = 4^{n^2 \log n} = (2^2)^{n^2 \log n} = (2^{\log n})^{2n^2} = n^{2 n^2}. $$ and: $$ g(n)= (n!)^n \le (n^n)^n = n^{n^2}. $$

Taking the limit: $$ \lim\_{n \to \infty} \frac{f(n)}{g(n)} \ge \lim\_{n \to \infty} \frac{n^{2 n^2}}{n^{n^2}} = \lim\_{n \to \infty} n^{n^2} = +\infty. $$
> 3 votes

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


# Question
Title: Constructing an SAT formula from a Clique graph
We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand. From my knowledge when we are reducing SAT to clique we don't focus on its compliment, so why are we trying to derive the formula from the compliment graph? It also seems strange that they randomly chose 4 vertices to label (P, R, S ¬Q) then derive the rest of the labels from there? Is this the general process we use when reducing Clique to SAT, even for 3SAT?

If anyone can help explain the solution because I have watched multiple videos on reducing clique to SAT, asked ChatGPT, looked at many stack resources but I am still very confused. There's isn't much on the reverse either (Clique to SAT)

This is the question:

This is the solution:

# Answer
> 0 votes
I wouldn't get too trapped in this question as it is only an example. Let's think about the general case. How can we build a formula $\varphi(G, k)$ out of a graph $G$ and an integer $k$ such that $G$ has a $k$-clique if, and only if, $\varphi(G, k)$ is satisfiable? Here's a general construction:

We start by constructing variables $x\_{v, i}$ for $i \in \\{1, \ldots, k\\}$ and $v \in V(G)$. They will represent that vertex $v$ is the $i$-th vertex in the desired clique. We first need to force that each position $i$ in the clique is used by some vertex, so we add clauses: $$ \bigvee\_{v \in V(G)} x\_{v, i}, \quad \forall i \in \\{1, \ldots, k\\}.$$

We also need to forbid a vertex $v$ from using more than one position, by adding clauses of the form:

$$ \overline{x\_{v, i}} \lor \overline{x\_{v, j}}, \quad \forall i \neq j \in \\{1, \ldots, k\\}. $$

Now let us construct variables $y\_v$ that state that vertex $v$ is part of the clique, so we have $$y\_v \iff (x\_{v, 1} \lor \ldots \lor x\_{v, k}),$$ which can be written with the following clauses: $$ \overline{y\_v} \lor x\_{v\_1} \ldots \lor x\_{v, k} $$ and $$ \overline{x\_{v, i}} \lor y\_v, \quad \forall i \in \\{1, \ldots, k\\}. $$

Now we need to enforce that if $y\_v$ and $y\_u$ then indeed $(u,v) \in E(G)$. This can be done by creating clauses of the form $$\overline{y\_v} \lor \overline{y\_u}, \quad \forall u \neq v \text{ s.t. } (u,v) \not\in E(G).$$

What the solution is suggesting, is that instead of thinking of a clique in $G$ you can think of an "independent set" in $\overline{G}$. Then, we can encode things in a similar fashion, with variables $z\_{v, i}$ representing that vertex $v$ is the $i$-th of the desired independent set. Now, if $(u, v) \in E(\overline{G})$, then we add clauses of the form $$ \overline{z\_{v, i}} \lor \overline{z\_{u, j}}, \quad \forall i \neq j \in \\{1, \ldots, k\\}, $$ for every edge $(u, v) \in E(\overline{G})$. Which encoding will be smaller depends on whether $|E(G)|$ is smaller than $|E(\overline{G})|$ or not.

---
Tags: np-complete, np, 3-sat, clique
---


title: EXP reduction to show NEXP-completeness

text:
# Question
Title: EXP reduction to show NEXP-completeness
I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$.

The computational complexity class $\text{NEXPTIME}$ or $\text{NEXP}$ has been defined here. In the same page, there is a section on $\text{NEXP-complete}$. This section states that the reduction must *polynomial* time. For the case of the deterministic version of this class, we can not have exponential time reductions as having exponential time reduction leads to all problems in $\textbf{EXP}$ be $\textbf{EXP-complete}$.

This reasoning is also held for the class $\textbf{P}$, which is why we have log-space reductions defined here. But when we are talking about $\textbf{NP}$ we deal with polynomial-time reductions. By same logic, I should be allowed exponential-time reductions for $\textbf{NEXP}$.

# Answer
The complete statement about completeness for complexity classes is "Problem A is complete for complexity class B under C-reductions."

In many cases it is clear from the context what notion of reducibility we are using, and so we can get away with not mentioning it explicitly. For P-completeness, it is clear that we mean logspace reductions if not stated otherwise, for NP-completeness we mean polytime reductions unless stated otherwise. The wiki page you link is clarifying that they are using polytime reductions for NEXP-completeness, too.

Of course you can go and study completeness for NEXP under EXP-reductions. But since "Problem A is complete for NEXP under EXP-reductions." is a much weaker statement than "Problem is complete for NEXP under polytime reductions.", it would be preferable to make the latter statement whenever you can prove it.
> 2 votes

---
Tags: complexity-theory, reductions, polynomial-time-reductions
---


# Question
Title: WAV file header: Why 2 bytes for channel?
It is mentioned in 22 - 23 Number of Channels which will be 1 if mono, 2 if stereo. So why 22 and 23 (that is 2 bytes) allocated here? With 1 byte, we can put either 1 or 2.

# Answer
> 2 votes
The dry and somewhat unhelpful answer is: The creators of the WAV file specification deemed 65535 to be a reasonable maximum number of channels.

Any reasonable surround sound system (3.1, 5.1, 7.1) has less than 255 speakers. So the creators must have had other applications of channels in mind, like perhaps Multitrack Recording. Let's say You want to record an orchestra and a choir. Each musician and singer is recorded by a separate microphone. The number of recorded channels/tracks could easily exceed 255.

---
Tags: filesystems
---


# Question
Title: Question about remainder in automata construction that checks divisibility
I'm trying to understand de construction of a DFA from the book "Introduction to Automata Theory, Languages, and Computation by John Hopcroft and Jeffrey Ullman 1st ed" It says:

Where it says "If the remainder of i/3 is p, then the remainder of 2i/3 is 2p mod 3." its dividing it twice to get the remainder. Shouldn't it be done only once? And why when describing the case for `(2i+1)/3` don't they use `p`?

I've seen other questions about this same automata in SO but they use a less mathematical explanation to how to build it.

# Answer
> 1 votes
Is your question: "Why $i/3 \equiv\_3 p $ implies $2i/3 \equiv\_3 2p$?

If so, the premise means that $i/3 = 3k + p$ for some integer $k$. Now, $2i/3 = 2 \cdot 3k + 2p = 3 \cdot (2k) + 2p$, so if you take $k' = 2k$ you have that $2i/3 = 3k' + 2p$, which is exactly the definition of $2i/3 \equiv\_3 2p$.

---
Tags: finite-automata
---


# Question
Title: Why can't I prove that the regular language is closed under concatenation by this way?
I'm reading Michael Sipser's "Introduction to the Theory of Computation", and it says:

> THEOREM 1.26 The class of regular languages is closed under the concatenation operation

In the video, if we scroll to the last section, he said that we cannot prove this by "concatenating" `m1` and `m2` together and pointing all accepted states of `m1` to the starting state of `m2`.

I don't get why this doesn't work (he did explain a bit but I didn't get the point). From what I understand, if we pass `w1w2` (concatenated strings) through a "concatenated" m1 and m2, it first goes through `m1`, ends at one of the original accepted state (but not accepted anymore after the concatenation), and at this point the `w1` part of `w1w2` has been read so essentially it is equivalent to move `w2` through `m2`, which will definitely end at an accepted state.

Where did I go wrong with the above thought? Thanks in advance!

# Answer
Actually, that works if you add $\varepsilon$-transitions between final states of $M\_1$ and the initial state of $M\_2$.

His argument of "maybe the cut of $w$ was wrong and you should have waited longer" is flawed if you consider nondeterministic automata, which are made to explore all possibilities at once.

What doesn't work, though, is if those transitions are labelled by an alphabet symbol, and not $\varepsilon$.
> 4 votes

# Answer
I would assume you are familiar with regular expressions since that was discussed in the video you linked. However, it seems like nondeterminism hasn't been introduced.

Consider two regular expressions $a^\*$ and $ab$. The first one represents the language that contains string made up of 0 or more "a", while the other represents the language that simply contains "ab". Lets assume we have machines $M\_1$ and $M\_2$ for the languages, respectively. If you simply attach the final states of $M\_1$ to the start state of $M\_2$, when will be the right time for the machine to jump from $M\_1$ to $M\_2$ if it is continually reading "a" from the input? Remember the machine cannot read ahead nor unread the input.
> 1 votes

---
Tags: regular-languages
---


# Question
Title: Algorithm for finding a consequtive sequence of clips with the least amount of cuts
The title isn't the most explanatory or accurate since I had issues putting it into just a few words so here we go. I have a real-world problem and managed to find an inefficient solution that my computer is barely able to find before running out of RAM. I'm interested to find out if my problem is unique or if there is already a name for it and possibly much better algorithms.

**Real-world problem description** There's a TV show where they have a certain number of clips(~30) that they repeatedly show in an arbitrary, changing order with a good amount of repetitions before having shown all of them. I made a recording and want to cut them into one video that contains all of the clips without any repetition. *I want to make as few (imperfect) cuts as possible.*

**My attempt at formalizing this issue**

* There's a set of items C(for clips). It doesn't have any duplicates and the order of elements does not matter.
* There's an ordered set of indices into C. I call that R(for Recording). This is basically a chapter list of the recording which tells us where we can find which clip. Repetition is allowed.
* There's something I call a group G, which is a list of consecutive indices into R. Or in programming terms, a range.
* There's something I call a Sequence S, which is a list of Groups that forms the final solution that I'm looking for. The groups must not overlap each other. The sequence must contain every clip exactly once. Note that there's some indirection here since the groups contain indices into R which then gives us an index into C. There may me multiple solutions so an algorithm would produce multiple S.

**My algorithm for finding the solution**

* We'll create state for every attempt to find groups. That state contains a sequence S, a list of indices into C (clips) that are part of one of the groups, and a list of indices into R(recording) that are part of one of the groups.
* Create initial state-array: For every index into R, we'll create a group that's as big as possible. We only consider later indices, not earlier ones. We'll stop increasing the group size as soon as we hit an index into R, that describes a clip that we've considered already. When we found a group, we'll add it to the state, and mark the clip and recording position as used in their respective arrays. To prevent duplicates, we check if a newly found group is fully contained by the previous group and we'll skip adding state for it.

Now we'll enter the main loop. With every iteration we'll add one more group to every state and we'll stop as soon as there's any state(containing a sequence S) that covers all possible clips in C. We will also add a bunch of new states with every iteration, but all of them will have the same number of groups inside their S.

* create a new, empty list of states States2
* For every state in our list of states:
    + For every index into R:
        - Create a group that's as big as possible. We only consider later indices, not earlier ones. We'll also make sure to not create any groups containing clips that were already considered. Once found we'll clone the current state, fill in the new group, and insert it into States2. Effectively, we'll find every possible way to add another group to the current list. This is why the number of states in our list will increase a lot with every iteration.
* make States2 replace the original list of states

At the end of that loop we'll have a list of states with both unfinished and finished sequences. You can remove the unfinished ones and remove duplicates(which exist, I guess that's a hint that the algorithm could be more memory effecient). Now you have unique Sequences S.

# Answer
This is a kind of exact cover problem, one where you want to minimize the size of the cover (i.e., minimize the number of sets selected to be in the cover). Here, each potential range forms a set, containing the clips that are found in that range.

A plausible approach would be to use a SAT solver or ILP solver. In particular, you can use the standard ILP formulation of the set cover problem to express this as an instance of integer linear programming, then apply an off-the-shelf ILP solver. There are no guarantees, as the worst-case complexity of the problem is exponential, but for the problem size you mention, I suspect this would be successful at finding the optimal solution in a reasonable amount of time.
> 0 votes

# Answer
A possibly more efficient algorithm would use dynamic programming. For any subset of the clips $S\subseteq C$ and starting time $t$, calculate and memoize the minimum number of cuts needed to extract the clips in $S$ from the recording starting at time $t$. This gives an algorithm with $O(|R| \cdot 2^{|C|})$ worst-case complexity, but if you filter out unnecessary subproblems (for instance those where $S$ contains a clip that is not present in the recording from time $t$ onwards) you might get an algorithm that works for instances with moderately small sets $C$. In any case, I expect that this algorithm will be much more efficient than the one you have described in your post.
> 0 votes

---
Tags: algorithms
---


# Question
Title: What is the optimal resource to follow to learn Operating System?
I wanted to learn Operating System on my own. Although I have learned few basic things from here and there, but wanted to know the suggestions (books, any video lecture, etc.) from this community.

# Answer
> 0 votes
I'm also learning about Operating Systems. One thing that I observed is that there is lack of quality lectures around this topic due to this topic being extremely tough. So, I tried a new experiment.

I'll now read multiple books and form an opinion. That's the most optimal way in this case.

The books that I've bought are:

* Galvin et al Operating System Concepts
* Stallings Operating Systems Internals
* Deitel et al Operating System

Other good books in this domain are:

* Operating System by william stallings (I'm not a big fan of his abstract way of presenting concepts)
* Operating Systems: Three Easy Pieces

Some video lectures in this domain are:

There are udemy courses by Vignesh Sekar but they're too boring and bland and maybe basic. I'd rather read books.

https://www.youtube.com/watch?v=jciGIvn7UfM&list=PLyqSpQzTE6M9SYI5RqwFYtFYab94gJpWk

https://www.youtube.com/watch?v=0Q1oFPC1ElI&list=PLLDC70psjvq5hIT0kfr1sirNuees0NIbG&index=28

https://www.youtube.com/watch?v=z3Nw5o9dS7Q&list=PLsylUObW5M3CAGT6OdubyH6FztKfJCcFB

Course by german university.

https://www.tele-task.de/series/1231/

https://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/resources/Course-Material.html

https://none.cs.umass.edu/~shenoy/courses/spring23/lectures/

https://www.cs.columbia.edu/~smb/classes/s06-4118/lectures.html

http://users.cms.caltech.edu/~donnie/cs124/lectures/

http://www.cse.iitd.ernet.in/os-lectures

https://oscourse.org/

https://courses.cs.washington.edu/courses/csep551/14au/video/

https://pages.cs.wisc.edu/~remzi/Classes/537/Spring2018/

http://gauss.ececs.uc.edu/Courses/c4029/

https://webcms3.cse.unsw.edu.au/COMP1521/18s2/resources/20598

https://merlot.usc.edu/cs402-m23/summer-preview.html

https://elearn.daffodilvarsity.edu.bd/course/view.php?id=7706

https://cs.slu.edu/~dferry/courses/old/csci3500\_fl20/

https://ics.uci.edu/~aburtsev/238P/

https://warwick.ac.uk/fac/sci/physics/research/condensedmatt/imr\_cdt/students/david\_goodwin/teaching/operating\_systems/l1\_concepts.pdf

https://www.cs.utexas.edu/users/dahlin/Classes/UGOS/index.html

https://mycourses.aalto.fi/course/view.php?id=32526

---
Tags: operating-systems
---


# Question
Title: What is the time complexity of this algorithm of finding all prime numbers?
I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called.

```
primes = []

n = int(input("Enter number : "))

for j in range(2,n+1):
    flag = True
    for i in primes:
        if i*i>j:
            break
        if j%i == 0:
            flag = False
            break
    if flag:
        primes.append(j)
print(primes)

```

# Answer
> 4 votes
The following complexity is not tight; however closeby:

The complexity of the algorithm is at least $\Omega(n \sqrt{n}/\log^2 n)$ and at most $O(n \sqrt{n}/\log n)$.

For any natural number $x$, the number of primes smaller than $x$ is given by prime-counting function $\pi(x)$. It is known that $\pi(x) = \Theta(x/\log x)$ (wiki and wolfram) for any natural number $x$. Therefore, for any number $j$, the algorithm is doing at most $ \pi(\sqrt{j})$ computations to check if $j$ is prime or not.

Thus, an upper bound complexity of your algorithm is $\\, n \cdot \pi(\sqrt{n}) = O(n \sqrt{n}/\log n)$.

Now, we compute the lower bound complexity. Suppose that $j$ is a prime number. Then, the algorithm is doing at least $\pi(\sqrt{j})$ computations to check if $j$ is prime or not. Therefore the algorithm has the running time at least $\sum\_{j: prime} \pi(\sqrt{j})$.

Note that $\pi(n) = \Theta(n/\log n)$. In other words, there exists constants $c\_1$ and $c\_2$ such that $c\_2 (n/\log n) \leq \pi(n) \leq c\_1 (n/\log n)$ for every $n \geq n\_o$ for some sufficiently large $n\_o$. Now, it is not very difficult to see that there exits a constant $c$ such that there are $\Omega(n/\log n)$ prime numbers larger than $n/c$ for every $n \geq n\_o$ for some sufficiently large $n\_o$.

Thus, the complexity of the algorithm over all the prime numbers is $\sum\_{j: \text{ prime}} \pi(\sqrt{j}) \geq \sum\_{j: \text{prime and } j \> n/c} \pi(\sqrt{j}) \geq \Omega(n/\log n) \cdot \pi(\sqrt{n/c}) = \Omega(n \sqrt{n}/\log^2 n)$.

---
Tags: complexity-theory, time-complexity, algorithm-analysis, primes
---