# Question
Title: Hoare triple: Loop invariant and correctness
The following Hoare triple in which variable *a* is an array of integers, and *len*, *max*, *i*, *n*, *j* and *m* are integer-valued variables. Provide a loop **invariant** (using **predicate logic**) suitable for proving **partial correctness** of the Hoare triple. Explain in words why it is a loop invariant and why it is sufficient to prove partial correctness.

$$\begin{align\*} &\\{0 \< len \\} \\ &i = 0; \\ &n = 1; \\ &j = 0; \\ &m = 1; \\ &\textbf{while}\\;(i+n \< len)\\;\\{ \\ &\quad\textbf{if}\\;(a\[(i+n)\]-a\[(i+n-1)\] ≤max)\\;\\{ \\ &\quad\quad n = n+1; \\ &\quad\quad \textbf{if} (m\<n)\\;\\{ \\ &\quad\quad\quad j = i; \\ &\quad\quad\quad m = n; \\ &\quad\quad \\}\\;\textbf{else}\\;\\{skip\\} \\ &\quad\ \\}\\;\textbf{else}\\;\\{ \\ &\quad\quad\quad i=i+n; \\ &\quad\quad\quad n=1; \\ &\quad\ \\} \\ &\ \\} \\ &\\;\\{0≤j∧1≤m∧(j+m)≤len∧ \\ &\quad\quad (∀ k : Z · ((j \< k ∧ k \< j+m) ⇒ (a\[k\] − a\[(k−1)\] ≤ max )))\\} \end{align\*}$$

I tried to use **loop rule** and get the **invariant** I by the third premise:

$$\\{I \land \lnot b\\} \\; \[\] \\; S \\; \\{Q\\}$$

***b*** is *len ≤ i+n*, but postcondition Q is too complex. Then I try to create two table to find rule, one table predicate a\[(i+n)\]−a\[(i+n−1)\]≤max, and predicate len = 6, then I get the program will terminate at fifth loop, and another table predicate a\[(i+n)\]−a\[(i+n−1)\]\>max also len =6, I get the same answer that terminates at fifth loop. In addition, I tried one time ≤max and one time \>max, then I get the same answer. So here I find a part of invariant which is ***loop times*** = ***len*** \- 1. From above is what I did, but I have no idea about how to go next step.

# Answer
> 1 votes
I believe the loop invariant is the same as the postcondition, except with *j* and *m* swapped with *i* and *n*, respectively. That statement can be proven true at the start and end of each loop. This is true partially by virtue of the fact that the final implication is trivially true when *n = 1* (as in the outer else condition), because no *k* value is in the range.

The fact that *j* and *m* are only ever assigned from *i* and *n* while the invariant is true, and the postcondition is true prior to the loop, implies that the postcondition holds.

Another key observation is that *i+n \< len* implies *i+n+1 ≤ len*, so the proposed invariant holds true, even after the loop condition fails.

I hope that helps.

---
Tags: logic, hoare-logic, predicate-logic
---


title: runtime of 2 dependent nested for loops

text:
# Question
Title: runtime of 2 dependent nested for loops
```
for (i=1; i<=n ;i=i*2){

  for (j=1; j<=i ;j++){

  basic_step;

  }
}

```

Regarding the above nested loops, I can't seem to understand why is the following runtime analysis is correct (specifically the **first equality**), when $k$ is defined as $\log i$, meaning $i=2^k$. What is the process that one should come up with, in order to decide this setting and the sigmas' indices? While I do understand that the outer loop runs for $\Theta(\log n)$ times, I still can't grasp the setting of $k$. A clarification will be very much appreciated!

$$\sum\_{k=0}^{\log n}\sum\_{j=1}^{2^k}1$$

# Answer
> 2 votes
The value of $i$ at the $k$'th iteration (starting from zero) is $i\_k := 2^k$. The inner loop runs $i\_k$ times, for a total of $i\_0 + i\_1 + \cdots + i\_K$, where $K$ is the largest number such that $i\_K \leq n$, that is $\lfloor \log\_2 n \rfloor$. Therefore the running time is $$ \sum\_{k=0}^{\lfloor \log\_2 n \rfloor} 2^k = 2^{\lfloor \log\_2 n \rfloor + 1} - 1 = \Theta(n). $$

---
Tags: algorithms, complexity-theory, asymptotics, runtime-analysis
---


# Question
Title: What easy algorithms are there for calculating products of cycle decompositions?
Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade.

```
  sub infix:<+>(@x, @y) {
   #x, y are lists of digits
   #returns a list of digits
   my @greater = (@y.elems > @x.elems) ?? @y !! @x;
   my @lesser_ = (@y.elems > @x.elems) ?? @x !! @y;
   my @gPopped = @greater;
   my @lPopped = @lesser_;
   my $carry = 0;
   my @sum;
   loop (my $i = 0; $i < @greater.elems; $i++) {
     if (@lPopped.elems >= 1) {
       my $gDigit = @gPopped.tail;
       my $lDigit = @lPopped.tail;
       @sum.append: (($gDigit + $lDigit) % 10) + $carry;
       $carry = (($gDigit + $lDigit) / 10).floor;
       @lPopped = @lPopped.head(@lPopped.elems - 1);
       @gPopped = @gPopped.head(@gPopped.elems - 1);
     } else {
        my $gDigit = @gPopped.tail;
        @sum.append: $gDigit + $carry;
        $carry = 0;
        @gPopped = @gPopped.head(@gPopped.elems - 1);
     }
   }
   return @sum.reverse;
  }

```

The algorithm is very easy and a child can do it by hand. Meanwhile, I am unaware of any algorithm for multiplying two permutations decomposed into cycle form (e.g. $(123)\times(12)(34)$). What is an easy algorithm for multiplying two cycles?

# Answer
> 2 votes
Here is how I would do it manually, taking the example of $(123) \cdot (12)(34)$.

Start with a number appearing on the right permutation, say 1. The right permutation sends it to 2, and the left to 3.

Doing the same with 3, we get 4 and then 4.

Doing the same with 4, we get 3 then 1. We have closed a cycle $(134)$.

Now take another number on the right (or left) permutation not already covered – has to be 2. It gets sent to 1 then 2. We have closed a cycle – 2 is a fixed point.

In total, the result is $(134)$.

Now let's compute $(12)(34) \cdot (123)$.

Let's start with 1. It goes to 2 then 1. So it's a fixed point.

Let's try 2 next. It goes to 3 then 4, which goes to itself then 3, which goes to 1 then 2. We have closed a cycle $(243)$. That's the answer.

---
Tags: algorithms, discrete-mathematics, mathematical-programming
---


# Question
Title: Why can't we replace Dijkstra's priority queue with a regular queue?
I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority queue. However, the runtime will still be O((E + V) log V). However, with a queue, that runtime will be O(E + V). Can anybody find a simple example of where Dijkstra's would fail if we used a queue instead of a Priority Queue?

# Answer
The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order the implementation happens to enqueue them.
> 1 votes

# Answer
Actually never mind I just realized when you are trying to find A -\> F:

A -\> C 3

C - \> D 3

D -\> E 1

E -\> F 1

A -\> E 10

We will first assign an incorrect value to F (11) based on a longer distance value to E (10). When E is corrected, we would rely on backtracking to edit F's distance which would be more inefficient than using the Priority queue.
> 0 votes

---
Tags: priority-queues, queues
---


# Question
Title: Empty intersection of longest path in connected graph
> Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

I found this examples in numerous study, but i couldn't find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?

# Answer
> 6 votes
You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.

Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.

```
     1
     2
    3 4
   5   6
  7 8 9 10
11        12

```

Then for vertices `1,2,7,11,10,12`, for example, `1`, there is a longest path `11-7-8-4-6-5-3-9-10-12` that does not contain `1`.

For vertices `3,4,5,6,8,9`, for example, `3`, there is a longest path `1-2-4-6-5-7-8-9-10-12` that does not contain `3`.

# Answer
> 1 votes
A bit old post yet I guess some one might benefit from this reply. I tried to solve for the simpler graph of 12 vertices. This graph is more symmetrical and hence easier (but the method might be applicable to the 25 vertex one too).

> Steps (look at earlier reply for vertex numbering)

1. Build a path of length 10 (max path length; see previous replies too) without each of the vertices with degree 1 (3 of them). There will be three of them. For instance a path without 12 is 1-2-3-9-8-4-6-5-7-11. By symmetry it is easier to get paths without 1 and 11.
2. Now comes the turn for removing vertices in the interior of the graph (with more than 1 as degree). Remove one such vertex e.g. 4 i.e. G-4 where G is the graph. We can get a path of length 10 (if you are counting the vertices) e.g. 1-2-3-5-6-10-9-8-7-11 without vertex 4. By symmetry other points can be removed and we can get paths of length 10.

Thus for every vertex in the graph we have shown that it is possible to get a longest path without it. Thus with a counter example we show that all longest paths need not have a common vertex.

# Answer
> -1 votes
It is easy if you consider the property exhibited in the graph that says for each vertex there is a longest path now say for the labelled vertex v\_1 there is a longest path P\_1 and continue for all vertices in this fashion you will get collection of longest paths whose intersection will be empty.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: How to search an almost sorted array faster than O(n) time?
Assume a 1-indexed array A\[1...n\], containing integers, where A\[1\] ≤ A\[n\]. The contents of the array have the following property : for 1 ≤ i \< n, |A\[i\] − A\[i + 1\]| ≤ 1.

Develop an efficient recursive algorithm to find j such that A\[j\] = z, where A\[1\] ≤ z ≤ A\[n\]. The algorithm must be more efficient that O(n).

Binary search was my first thought but you would still have to search through both halves because it doesn't have to be from low to high.

# Answer
Let's say you have n = 100, $a\_1 = 50$, $a\_{100} = 100$, and $a\_{50} = 73$. You would then know that the range from $a\_1$ to $a\_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a\_{50}$ to $a\_{100}$ contains all numbers from 73 to 100, and maybe some others.

I think binary search will actually work, if the number you are looking for is within the interval from the first to the last array element. You will always know one half which *must* contain the number you are looking for, and one half which *might* contain the number so obviously you search the half that *must* contain it.

If the number is outside that range, you may have to check every single item: You could have $a\_i = 0$ for every $i$ except $a\_k = 1$. You can examine $n-1$ items $a\_i$ which are all 0, and you still don't know if 1 is in the array or not; the one remaining element could be $-1$, $0$ or $+1$.
> 2 votes

---
Tags: algorithms, time-complexity, search-algorithms, arrays
---


# Question
Title: Table-driven lexers in Engineering a Compiler 2nd Edition
Recently, I am reading Engineering a Compiler 2nd Edition.

But I am struggling to understand the following pseudocode.

Can anyone help me to explain the pseudocode in a simple and plain English?

* Why `NextChar` does take a char input?
* Why `lexeme` is the result 0f `lexeme + char`?
* What is the result of `Delta[state, cat];`?

# Answer
Let me answer your questions very quickly:

* `NextChar(char)` reads a character and assigns it to the variable `char`.
* The new character is appended to the current lexeme being built via the command `lexeme = lexeme + char`.
* The table `Delta` implements the transition function $\delta$ of a DFA (sometimes called an FSM). There is a lot of information on DFAs on the web and even on Computer Science.

I was able to answer these questions via a combination of common sense and a very rudimentary knowledge of how lexers work. More generally, when faced with code or pseudocode which you don't quite understand, you should try to figure out what the code is trying to accomplish, and how. For example, `NextChar` surely reads a character. You might expect it to return it, but from the context it is clear that it is actually stored in its argument. The fact that it is adjoined to `lexeme` significantly strengthens this guess.
> 1 votes

---
Tags: compilers
---


# Question
Title: minimum moves for Knight on a infinite chessboard
You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.

I can only think of a bfs solution. Is there a better solution possible?

**The question is further extended by adding obstacles to the board. How to solve this question what will be the complexity.**(I basically need a answer for this.)

Thank you.

# Answer
> 1 votes
With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.

Define the "optimal distance" between points as the distance given by the algorithm for lowest number of moves without obstacles. At the starting point, find all neighbouring points, and for each calculate a lower bound for the number of moves to the target: One initial move, and the moves for the closest distance to the target. Then the same from the other end. Next you examine those points with the lowest lower bound. All moves are eventually evaluated, bot you tend to check those first that get you closer to the target.

# Answer
> 0 votes
Without obstacles you can solve this in constant time. You'll have to work the details out, but the idea is that in two moves if you want to cover distance you can move 4 steps in one direction and 0 or 2 in the either, or 3 steps in each direction. So let's say the distance is (100, 48): You do 24 double moves (4, 2) plus 1 double move (4, 0). Let's say the distance is (100, 60): You move diagonally until one distance is half the other, say 8 double moves (3, 3) leaving a distance of (76, 36) which can be covered in 19 double moves.

You make a small table of how to best cover small distances: (0, 0) takes 0 moves, (1, 0) takes three moves, (1, 1) takes two moves, (2, 0) takes two moves, (2, 1) takes 1 move, (2, 2) takes 4 moves, etc. And you are left with a small number of possibilities how to go a large distance in the fastest way, followed by a small distance.

---
Tags: algorithms, graphs, searching
---


# Question
Title: Where were the ideas of vote, accept and commit phases originally introduced?
In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5.

Is this a novel introduction or has this been previously been introduced, and if so, where? More specifically, I refer to definitions of these given in section 5.

# Answer
> 1 votes
This dates back to the Byzantine broadcast algorithm of Bracha:

Bracha, Gabriel. "Asynchronous Byzantine agreement protocols." Information and Computation 75.2 (1987): 130-143.

---
Tags: reference-request, distributed-systems, communication-protocols, consensus, blockchain
---


# Question
Title: How to get to the efficient solution of a problem on buying with exchange policy
I was working through some coding challenges at hackerrank.com and got to this one.

I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. So I found this.

After explaining the *naive method*, which is the one that I used, then there is the *efficient solution*. But I can not understand the explanation that goes from the *naive method* to the *efficient solution*.

Can someone help me understand how is the logic to get to the *efficient solution*:

> In above naive implementation, we noticed that after finding initial number of chocolates, we recursively divide the number of chocolates with the number of wrappers required. until we left with 1 chocolate or wrapper. We are recomputing the values i.e. ((choc/wrap + choc%wrap)/wrap until we get 1. **It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1)**

# Answer
> It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1).

First, we can verify by brute force that the number of additional chocolates we can get by returning wrappers repeatedly is indeed (choc-1)/(wrap-1).

Second, here is how we can understand or prove that formula.

Suppose we have wrap-1 wrappers. Imagine we can borrow one wrapper from a benefactor. Then we can return the wrap wrappers for a chocolate, the wrapper for which will be returned to the benefactor. So we do not owe the benefactor anything any more.

Looking back, we had wrap-1 wrappers initially while we had enjoyed one chocolate without wrapper in the end. So, every wrap-1 wrappers will bring one chocolate without wrapper, as long as we had no less than wrap wrappers. If we have choc wrappers, we will have choc/(wrap-1) wrapper-less chocolates. However, there is a catch. There is, in fact, no benefactor. So the number should be (choc-1)/(wrap-1) instead.

In a more friendly world where there are benefactors or a more admissible policy where wrap-1 wrappers can be exchanged for one wrapper-less chocolate, the number of additional wrapper-less chocolates will be choc/(wrap-1).
> 1 votes

---
Tags: algorithms, algorithm-analysis, optimization
---


# Question
Title: Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$
In one of my exams I needed to find a CFG for $L=\\{a^ib^{2i}c^{2i} | i\>1\\}$.

however, it really seemed to me that it is not a CFG. I tried to show it is not using the pumping lemma, and think I managed, but I don't really know if I did something wrong there.

So was I wrong or the question is wrong?

Thank you.

# Answer
Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\\{a^ib^ic^i : i \> 1\\}$, which differs from a well-known non-context-free language by just a finite number of words.
> 2 votes

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


title: Is a complete code always optimal?

text:
# Question
Title: Is a complete code always optimal?
According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?

# Answer
No. If I have three symbols with probabilities A = 0.5, B = 0.25 and C = 0.25 then A=0, B=10, C=11 is complete and optimal. B=0, A=10, C=11 is complete but absolutely *not* optimal.

An optimal code on the other hand *must* be complete, because otherwise you can shorten the encoding of some symbol.
> 2 votes

---
Tags: information-theory, data-compression
---


title: PH=PSPACE implies collapse of PH?

text:
# Question
Title: PH=PSPACE implies collapse of PH?
If PH=PSPACE, does this imply that the PH collapses to one of its levels?

(somehow I get an error message when posting "question doesn't meet quality standard" so I add this sentence in order to workaround it)

# Answer
> 2 votes
yes, it says so on wikipedia https://en.wikipedia.org/wiki/Polynomial\_hierarchy

"If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse"

---
Tags: complexity-theory
---


# Question
Title: What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$?
Is there a standard name for the operator that takes a function $f:X\rightarrow(Y\rightarrow Z)$ and returns the function $f':Y\rightarrow(X\rightarrow Z)$ that satisfies, for every $y \in Y$ and $x \in X$, $f'(y)(x) = f(x)(y)$?

# Answer
The function $$\lambda f.\lambda x.\lambda y.f\\;y\\;x$$ of type $$\forall X. \forall Y. \forall Z.(X \to Y \to Z) \to Y \to X \to Z$$ is often called **flip**. This is the case in Haskell (see here), and in some OCaml libraries as well (see here). According to wikipedia, people call this function (or combinator) $C$ in the context of combinatory logic (that name sounds pretty random though).
> 6 votes

# Answer
Given the tag , the answer in combinatory logic is **C**, i.e. "the **C** combinator". Obviously, this name is not self-documenting or going to be obvious in even a slightly more general context.
> 2 votes

---
Tags: terminology, lambda-calculus, combinatory-logic
---


# Question
Title: Why does NTM need to derive certificate to prove "If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM"?
(Sipser's Chapter 7: Time COmplexity, Pgs 294-295)

If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the certificate"--essentially constructing the verifier-- if we already know one exists.

On the other hand, if you don't have the certificate, you can use a NTM to derive it and check w against c. So you don't need to pass any input into V. So V is useless.

I don't really understand this proof.

# Answer
By definition NP is the class of languages for which you can efficiently verify with a certificate that a string is in the language.

Informally; it is the class of problems that you can verify the solution to given a witness, but you cannot find one easily. If you could, then it would be in P.

A NTM can be seen as a unrealistic Turing machine which always guesses the right answer. Since the NTM is non-deterministic given an input x. We cannot be sure exactly what path he took to derive the solution, therefore a witness is needed.

For example;

Problem: Is 24 prime?

A NTM would guess the answer to be no and the certificate would be the number “4”.

A verifier presented with the certificate can divide 24 by 4 and also come to the conclusion that 24 is not prime.
> 1 votes

---
Tags: time-complexity, nondeterminism
---


# Question
Title: Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode
There exist a vast array of prominent bitcode formats, each suited for their specific task:

* **LLVM IR:**

This format is build around a XML like binary streams model, designed to be used as a common compiler target across a multitude of Architectures and languages.
* **JVM bytecode:**

Java compile target, mainly; increasingly reused as a larger target in that ecosystem.
* **Khronos Spir-V:**

Shader language target, graphics hardware abstraction.
* **Web Assembly:**

Built as a target to better integrate ecosystems and existing code within the browser context.
* **Specialized: (Ex. Lua and Python Bytecodes):**

Interpreters generally execute bytecode during execution whether, explicitly or not.

The hardware/ISA ecosystem is equally split, particularly amoung ARM, i386/x86, x86\_64, Microchip/Atmel and now Risc-V. Fragmentation also exists in the computer graphics industry, which in many ways has outpaced CPU growth in recent times. Hardware Acceleration Layer/API design is primary split between Khronos and Microsoft, but now apple and Google are joining in; Even in the case of the two leading providers, backwards compatibility has proven to be a difficult problem, leading to increased segmentation and overhead.

I only see these problems getting worse in the future with the current state of traditional Moore's Law, increasing use of accelerators and FPGAs, IoT proliferation, diverse memory types and caching mechanisms, hyperscaling, etc...

In the past, segmentation has been forsean and in the case of character set localization, avoided. This is why the Unicode Consortium was Established, independent of any single company/organization. The Unicode Consortium has managed to standardize over 100,000 character encodings to date and this is virtually universal.

Theoretically I see no reason why this cannot be accomplished in the bitcode/turing realm.

https://www.quora.com/unanswered/Why-is-there-no-extensive-standards-organization-for-instruction-set-architectures-ISA-and-bitcodes-as-there-is-in-the-case-of-Unicode-1

In Response to Community:

* @Gilles Unicode acts as a super-set of its predecessor, ASCII; it conforms to UTF-8, UTF-16 and UTF-32 standards. Modern microprocessors are no strangers to expanding type codes in their instruction decoding pipelines. Any machine can emulate larger types than its baseline and architecture level support for this is not uncommon.

Reference:

# Answer
> 2 votes
Unicode is a suitable encoding for most scripts because it includes characters from all the scripts. The analog would be an instruction set architecture that includes instructions from all processors. This would be huge and impractical to implement whether in hardware or in software. It would even be contradictory: how do you reconcile an architecture with 16-bit words with an architecture with 64-bit words? an architecture that allows unaligned word accesses with one that doesn't? an architecture that guarantees the presence of an MMU with one that guarantees that addresses used by software map directly to addresses in physical memory? an architecture that guarantees that all memory accesses take exactly the same amount of time with one that has memory caches?

A realistic ISA can't combine what all the ISA do. You have to make choices, and these choices depend on your objectives. If you're building a processor for real-time processing, a guarantee that memory accesses take the same amount of time is crucial. If you're building a processor for fast numerical or symbolic computation, caching memory accesses is essential for performance. A good instruction set for general-purpose computing is not the same as for graphical rendering, and machine learning calls for yet another approach. There is no one-size-fits-all.

Why isn't there a standard model of vehicle? Why are there so many different models of cars and airplanes and bicycles and motorcycles and helicopters and submarines and so on?

# Answer
> 0 votes
There is a very strong demand to be able to exchange textual information. EVERYBODY wants to be able to exchange textual information. Billions of people.

How many people want to use different code representations? It's only possibly compiler writers, and nobody else. But compiler writers are mostly happen with the one bytecode representation they are using: Java bytecode if you write a Java compiler, LLVM IR if you use Clang and so on.

And with Unicode, the effort is just writing a huge document and maintaining some tables. With a bytecode representation, you can't just standardise on one, you then have to go through the huge effort to turn it into actual code running on some machine.

Summary: No standard because the benefit is much less, and the cost much higher, than with standardising unicode.

---
Tags: computer-architecture, distributed-systems
---


# Question
Title: Is finite subset of a set which contains all non regular languages a regular set?
Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ?

I know that A is not recursive enumerable set (undecidable). So I wonder that if finite subset of undecidable set is a regular language or not.

# Answer
> 1 votes
Your question doesn't make sense because of a category error. "Regular" is a property of sets of strings. A set of languages is a set of sets of strings, so it doesn't make sense to ask if it's regular.

---
Tags: formal-languages, regular-languages, undecidability
---


# Question
Title: Gas Station problem : Fixed path variation
Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I'm not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?

# Answer
> 4 votes
The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).

The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this solution is in fact identical to the greedy one (to understand why this almost always works, you can read up on matroids and see how the standard proof is done in this case).

Informally, in this case :

Call GS your greedy strategy and let OPTS be an optimal strategy which agrees with GS for the longest time, starting from the beginning. Suppose GS and OPTS differ in strategy for the first time in city C:

* If OPTS fuels up more than GS at this point, then that means that GS fueled up just enough to reach the next cheapest city C'. It is clear that OPTS will arrive in C' with more fuel than GS (more than 0). But GS can then fill its tank up to as much as OPTS (for cheaper than OPTS could have at any point between C and C'). We can thus construct an optimal strategy OPTS' which does what GS does up to C' and then copies OPTS. But OPTS' is optimal and "agrees with GS" for longer than OPTS, which is impossible by definition of OPTS. So it is impossible that OPTS fuels up more than GS in C.
* If OPTS fuels up less than GS in C, then let C' be the next city where OPTS is gonna fuel up. C' can not be cheaper than C, otherwise GS would have filled up just enough to get there and OPTS would have had to fuel up at some point between C and C'. So C' is as least as expensive as C, and filling up in C would not have been worse for OPTS. We can once again construct a new strategy OPTS' which contradicts the definition of OPTS. So it is impossible that OPTS fuels up less than GS in C.

Putting both together, we see that there can not be a "first disagreement point" between GS and OPTS. Thus, GS = OPTS, and GS is an optimal strategy.

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


# Question
Title: TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?
So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The latter requires demonstrating an algorithm which computes the L in polynomial space. This is usually achieved by having recursive calls such that is re-used.

In TBQF proof, the equation $\phi\_{i+1}(A,B)$= $\exists Z \[\phi\_{i+1}(A,Z) \land \phi\_{i+1}(Z,B) \]$ ($Z$ is mid-point )is default recursive relation for computing TBQF truth. In any standard proof, it is said that $\phi\_{i+1}(A,B)$ is computed two times and for $m$ nodes, this formula explodes hence, other recursive-relation should be used to bound.

However in Savitch's proof, the recursive relation is $Path(a,b,t)$ = $Path(a,mid,t-1)$ AND $Path(mid,b,t-1)$ accepts then ACCEPT. In proof, it is stated that this relation reuses-spaces.

My Question is **Why in TBQF relation space explodes while in Path, it is reused?** Both of these relations looks more or less same to me because both refers to i-1 instances and will need space to store them?.

# Answer
In the proof of the $\textit{PSPACE-}$completeness of TQBF, we need to construct a formula of some specific type. The recursive midpoint algorithm is easy to implement (and Savitch's Theorem requires finding the $\textit{algorithm}$), while the same idea, if performed in a similar manner, results in an exponential formula (and the completeness proof requires the $\textit{formula}$).

More generally, suppose there's some language $\textit{L}$, an optimal algorithm $A$ deciding $L$, and the smallest formula (maybe quantified) $\varphi$, s.t. $\varphi(x) = 1 \Leftrightarrow x \in L$. For me, it's not very clear why $A\in \textit{PSPACE}$ would imply that $\varphi$ is small (I only see it as a consequence of the $\textit{PSPACE}-$completeness theorem)
> 1 votes

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


title: Subset Sum to SAT reduction

text:
# Question
Title: Subset Sum to SAT reduction
I have seen numerous ways to reduce CNF-SAT to SS, but is there any way to reduce SS to SAT (or one of its variations)? I have tried researching it, but all it brings up is the (apparently) much more common opposite reduction.

# Answer
> 2 votes
You can reduce addition to a circuit with XOR, AND, OR gates.

Each element of the sum must first be ANDed with an extra variable that is true if the element belongs to the subset, and false otherwise.

Then the circuit can be trivially reduced to 3-SAT. The clauses are determined by the gates.

For example each AND gate (A & B = C) requires these 4 clauses:

(A | !B | !C)

(!A | B | !C)

(A | B | !C)

(!A | !B | C)

Why? Because:

false & true != true

true & false != true

false & false != true

true & true != false

Each clause eliminates one impossible situation for the gate.

Then if you want the result of the sum to be zero, you add one unit clause for each bit of the result.

---
Tags: complexity-theory
---


# Question
Title: Number of nodes in Van-Emde-Boas tree of universe size u?
The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level.

The height of the tree is $h = \lg \lg(u)$ and $u$ is an even power of 2, $u = 2^{2^k}$. I tried to calculate the count using the sum:

$$\sum\_{i=1}^{h-1} 2^i\\,2^{i + 1}$$

But it doesn't work. Any idea on how to do the math?

## Edit:

Sorry for the confusion that might be caused by the illustration. The illustration is based on the CLRS book's implementation of VEB trees, but the summary nodes are not shown. Thinking again about it now, I would like to know the count of all the nodes including the summary nodes and their tree nodes, as well as, the count of just the nodes without the summary.

# Answer
The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from *how to read off the set represented by a van-Emde-Boas tree*, which was drawn by Raphael based on a figure in CLRS, where a number in orange is drawn at a min field that marks its presence in the set of integers being represented.

How many nodes are there in the vEB tree implemented like the illustration above?

There are $1 + 5 + 5 \times 3 = 21$ nodes in the illustration above.

For the sake of simplicity, let $w=2^h$ and $u=2^w=2^{2^h}$. A vEB tree over the universe $\\{0,1,\cdots, u-1\\}$ is of depth $h=\log\log u$.

* There is one node of depth 0, which is the root node.
* There are $2^{2^{h-1}} + 1$ nodes of depth 1.
* Each node of depth 1 has $2^{2^{h-2}} + 1$ child nodes of depth 2.
* ...
* Each node of depth i has $2^{2^{h-i-1}} + 1$ child nodes of depth $i+1$.
* ...
* Each node of depth $h-1$ has $2^{2^{h-h}}+1=3$ child nodes of depth $h$.

In total, the number of all nodes is $$1 + \sum\_{i=1}^{h}\prod\_{k=1}^i(2^{2^{h-k}} + 1)=(2^{2^h} - 1)\sum\_{i=0}^{h}\frac1{2^{2^i} - 1}\tag{1}$$ which is 1, 4, 21, 358, 92007, 6029862760, 25898063359598159721, $\cdots$ for $h=0,1,2,3,4,5,6,\cdots$ respectively. When $h\ge4$, the number of nodes is about $1.404u$.

Similarly, the number of all summary nodes is, for $h\ge1$, $$1 + \sum\_{i=2}^{h}\prod\_{k=1}^{i-1}(2^{2^{h-k}} + 1)=(2^{2^{h}} - 1)\sum\_{i=1}^{h}\frac1{2^{2^i} - 1},\tag{2}$$ which is 0, 1, 4, 21, 358, 92007, 6029862760, $\cdots$ for $h = 0,$$1, 2,3,4,5,$$6,\cdots$ respectively.

What is the number of all non-summary nodes? Subtracting (2) from (1), we obtain

$$(2^{2^{h}} - 1)\left.\frac1{2^{2^i} - 1}\right|\_{i=0}=2^{2^h}-1=u-1.$$

The formula also hold for $h=0$. So we have obtained the following surprising formula. $$\text{the number of non-summary nodes in a vEB tree of universe size } u=2^{2^h}\text{ is }u-1.$$

---

Every node at the same depth use the same amount of space. Nodes at a smaller depth may use much more space than those at a larger depth. For example, for $h=5$, the root node contains a bit-array of size 65536 but a leaf node just contains several words. Since the number of nodes that use bigger space decreases very quickly as their depth becomes smaller, the total space used is $O(u)$.

---

**Exercise.** The number of all leaf nodes, which are vEB trees of universe size 2 in a vEB tree of universe size $u=2^{2^h}$ is $u-1$.
> 1 votes

---
Tags: algorithms, data-structures, van-emde-boas-trees
---


# Question
Title: efficiently calculate nearest common ancestor in a family tree (each person has two parents)
I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each person, then walk back from root tossing off anything common.

In a matriarchal society, for example, this could be used to quickly calculate how any two people are related as long as only the mothers are considered.

But if both parents are considered, eg mother AND father, then the algorithm just described breaks down.

So I wondered is there an algorithm to tell two people how they are related in a family tree where both parents are considered? For example, see the Icelandic genealogy app (https://www.islendingabok.is/) which does precisely that. How's it done, algorithmically speaking?

# Answer
> 0 votes
Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately the same number of generations back on each side.

Indeed, this is exactly what you should do on a tree: going all the way back to the root and then discarding all common ancestors after the first takes more time.

---
Tags: graphs
---


# Question
Title: Any array takes at least log(n!) compairs to be sorted
I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using comparison based algorithem) in just 6 steps. Can you guys help me out with this?

# Answer
> 0 votes
The statement is not quite rigorous. Sorting requires at least $\lg(n!)$ comparisons *in the worst case*. Because you can very well design an algorithm that would check that the array is already sorted and stop if true. Such an algorithm would indeed sort a sorted array in $n-1$ comparisons.

This said, you can permute an array of $n$ elements in $n!$ ways, and to "unpermute" you need to somehow identify the permutation. A comparison-based algorithm is a binary decision tree, and the depth of such a tree having $n!$ leaves must be at least $\lceil\lg n!\rceil$ (because a binary tree of depth $d$ has at most $2^d$ leaves).

# Answer
> 0 votes
There are n! ways how n items in an array can be arranged. If you have k comparisons each with two possible outcomes, then you have a total of $2^k$ possible outcomes.

Therefore, if $2^k \< n!$, there are at least two different arrangements of the data where all comparisons produce the same result. Since you cannot know which arrangement of data you have, you cannot sort them both correctly.

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Is this possible to solve 3SAT in O(n^24) time and O(1) space?
Assume that **n** is the number variables of the given 3CNF formula (n≥3) and all clauses in the given 3CNF formula are different.

That means that for each clause, each literal can be either positive or negative and be one of the **n** variables, so the number of options for each literal is **2n**, but each clause has exactly 3 literals, so the maximum number of different clauses is 2n•2n•2n = (2n)3 = 8n3 = O(n3).

I have read here that 3CNF formula must have at least 8 different clauses in the form:

(x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)

to be unsatisfiable.

If this small 3CNF formula is included or subset of a larger 3CNF formula, then the larger 3CNF formula is unsatisfiable for sure, because of that subset.

So the algorithm needs to search for this subset and if the algorithm found it then the algorithm returns "given formula is unsatisfiable" as output.

And this suppose to be correct for sure.

But what happens if the algorithm does**n't** find such subset?

Does this necessarily means that the given 3CNF formula is **not** **un**satisfiable, i.e. satisfiable?

Because that the subset has exactly 8 clauses, the algorithm needs to iterate through all the different subsets of 8 clauses in the given 3CNF formula.

If the given 3CNF formula has **m** clauses, then there should be θ(m8) different subsets of 8 clauses, but if all clauses are different, then m=O(n3), thus O((n3)8) = O(n3•8) = O(n24)

So the running time of the algorithm to iterate through all these subsets and to find the unsatisfiable subset, if exists, takes θ(n24) time.

To do this, the algorithm needs 8 inner for loops, where each for loop is inside the other, with 8 iterative variables.

Because that the algorithm doesn't allocate any memory during the run time, the space complexity of this algorithm suppose to be θ(1).

Let me know if I was wrong and on what, i.e. if I am wrong then why?

Why I was wrong?

Please explain.

I want to learn from mistakes.

I think that

> it's too good to be true

and

> if it's too good to be true, something's wrong.

# Answer
> 3 votes
You are correct in your assumption that your algorithm correctly identifies some unsatisfiable instances, but for the general case it does not work.

For instance, you can always rewrite a clause $\\{A, B, C\\}$ to the equisatisfiable clause set $\\{A, X, Y\\}, \\{\neg X, A, B\\}, \\{\neg Y, B, C\\}$. To see this, observe that you can always recover the original clause through resolution. If applied to say, the first clause in the above example, this will already break your algorithm.

Maybe someone with more knowledge on SAT can give some more insightful information.

# Answer
> 3 votes
The operative phrase is "at ***least*** 8"! The funny thing about 3SAT is that every clause with 3 distinct variables eliminates a full 1/8th of the model space. So how is it that you can have a formula with hundreds of clauses in it and not completely obliterate all of the possible solutions? The answer, of course, is that most of the clauses *overlap* in the portions of the model space that they exclude; and the more variables you have, the more "volume" each clause overlaps in the model space. The scenario where 8 clauses is *sufficient* to make a formula unsatisfiable is obviously where those 8 "blocks" have *no overlap*.

Geometrically speaking, one can view the model space for a formula as an $n$-dimensional hypercube of width $2$, where each dimension corresponds to a variable in the formula, and can have the value $true$ or $false$. Since it's hard to visualize hypercubes with more than 3 dimensions, it's helpful to project them down onto 2 dimensions like so:

Here I've rendered the formula provided by @rus9384 as a table showing how the model space is covered. The "canonical" unsatisfiable core with only 3 variables would replace the last 2 clauses with $(\lnot x, \lnot y, z)$ and $(\lnot x, \lnot y, \lnot z)$. In this case, all the "blocks" would be "aligned". If you could see this properly in 4 dimensions, it would look like we are building a 4-dimensional LEGO cube by stacking a bunch of 1x2 bricks in the same direction. What @rus9384 has done is take 2 of the "bricks" (which logically form a 2x2 block) and "rotated" them 90 degrees. Of course, this still covers the model space exactly.

Now, to see why an unsatisfiable core might contain *more* than 8 clauses, we should first think about what a 2-clause looks like. Suppose our formula contained $(x, y)$. This is actually the resolution of 1 and 2, so in a way, you could say that it *does* contain this 2-clause. And note that 1 and 2 together cover 1/4th of the space. In general, a clause with $k$ distinct variables covers $\frac{1}{2^k}$th of the model space (assuming no tautologies, of course). Thus, to force *more* than 8 clauses in the Minimal Unsatisfiable Core (MUC), we need to cover *less* than 1/8th of the model space with one or more of the clauses! Using the formula above, we can do that by introducing a clause with 4 variables, which only excludes 1/16th of the space (e.g., $(x, y, z, t)$ only takes up 1 cell in the table).

"But wait!" you say: "...we were talking about 3SAT! You can't have 4-clauses!" @Max showed that you can run Resolution forwards and backwards to get the desired clauses. So, for instance, we can introduce a new variable, $w$, and add $(\lnot x, \lnot y, \lnot w)$ and $(w, \lnot z, \lnot t)$, which resolve to the 4-clause $(\lnot x, \lnot y, \lnot z, \lnot t)$. If we replaced clause 8 in our formula with this new 4-clause (or its 3-clause "parents"), then suddenly our formula becomes satisfiable, because we have left a "hole" in the model! We would need at least one more formula to patch it up. As you can imagine, one can force a MUC to be larger than any fixed size ($\geq 8$) simply by building it with "blocks" that are arbitrarily small.

"But wait!" you say: "...you already said that all 3-clauses cover 1/8th of the model space! They are all the same size!!!" And indeed that is true. What's really going on is that we are shifting the overlap into other variables/dimensions so that the intersection with the "MUC core", if you will, is less than 1/8th, if that makes sense.

# Answer
> 2 votes
Following SAT instance is unsatisfiable:

$$(x\lor y\lor z)\land(x\lor y\lor\overline z)\land(x\lor\overline y\lor z)\land(x\lor\overline y\lor\overline z)\land(\overline x\lor y\lor z)\land(\overline x\lor y\lor\overline z)\land(\overline x\lor\overline y\lor t)\land(\overline x\lor\overline y\lor\overline t)$$

And it does not have those 8 clauses that you want to find.

Also, I don't see why it must take $O(n^{24})$ time. Finding a group of 8 clauses (if it exists) can be done in $O(n\log n)$ time.

Edit:

> If the given 3CNF formula has m clauses, then there should be θ(m^8) different subsets of 8 clauses

This is wrong. Number of input clauses always bounded by $n$ (or $m$ in your case). It's initial value.

Number of different subsets would be bounded by $\frac{n}{8} = O(n)$.

Algorithm would be as follows:

1. Sort all clauses.
2. Take two variables: `a` and `b`. While `C[a]` and `C[b]` have all the same variables, increase `b` : `b++`.
3. If `C[a]` and `C[b]` differ by at least one variable, put `a = b; b++`.

This algorithm results in $O(n\log n)$ time.

# Answer
> 0 votes
Your evaluation only works into one direction, you can use it to test for unsatisfiability for the listed cases which are only a subset of all unsatisfiability cases. Imagine for example a formula in which 100 clauses contain x and one clause contains (¬x ∨ ¬x ∨ ¬x).

---
Tags: complexity-theory, satisfiability, 3-sat, sat-solvers
---


# Question
Title: Given n sets of points in the plane find the shortest path which passes from exactly one point from each set
I am trying to find an algorithm for this. You can imagine each set $(S\_1, S\_2, \ldots, S\_n)$ as points with different colour. Also it isn't necessarily $|S\_1|=|S\_2|=\cdots=|S\_n|$.

For $n=1$ we trivially have a single (random) point.

For $n=2$ we have two sets of points $S, Q$ and we seek to find the (distance of the) closest pair of points $p, q$ such that $p\in S$ and $q \in Q$. I have also found an efficient algorithm for this, using voronoi diagrams.

For $n\>2$ things get tricky. I have no clue where should I head to. Let's say we have $x$ red, $y$ green and $z$ blue points laid down in an Euclidian plane. How do we find the minimum distance of a route passing for one red, one green and one blue point?

Is this some special case of the Traveling Purchaser Problem?

# Answer
> 0 votes
This problem is a generalization of TSP known as Set TSP. Not surprisingly, it is both NP-complete and well-studied.

---
Tags: algorithms, time-complexity, computational-geometry, traveling-salesman
---


# Question
Title: Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?
I know this would be an *O(k log n)* operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access...

My question though is, when we have an implicit array representation of a min-heap, e.g.:

```
min_heap = [1, 2, 4, 3, 6, 5, 54, 12, 12, 34]

```

In this case, is it possible to infer the Kth-smallest value's index from the value of K, so you can use the array index to get the value in O(1) time?

# Answer
> 2 votes
This is not possible. If this is the case then we could extract a sorted list in linear time; $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $\Omega(n \log n)$ lower bound worst case, so this is not possible.

---
Tags: algorithms, asymptotics, arrays, heaps
---


title: Recurrence Equation upper limit problem

text:
# Question
Title: Recurrence Equation upper limit problem
I was looking at my teacher's notes and came about the following recurrence equation :

$$ T(n) = \begin{cases} 1 &\quad\text{if } n\leq 1\\ 4T\left(\frac{n}{2}\right) + n^3 &\quad\text{if } n\gt1 \\ \end{cases} $$
In order to solve it I proceeded as follows :
$$ T(n) = n^3 + 4T\left(\frac{n}{2}\right) = n^3 + 4\big( 4T\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)^3 \big) = \\ n^3 + 4\left(\frac{n}{2}\right)^3 + 16T(\frac{n}{4}) = \cdots $$
I'll spare some latex and state that we can see from unwrapping the equation that at the generic level $i$ the incurred price is :
$$ T\_i = 4^i\left(\frac{n}{2^i}\right)^3 $$
In order to compute the overall price we can sum all the prices incurred at all levels, obtaining :
$$ T(n) = \sum\_{i=0}^{log^n -1}{\big(4^i\left(\frac{n}{2^i}\right)^3\big)} + 4^{log^n}T(1) = \\ n^3 \sum\_{i=0}^{log^n-1}{\big(2^{2i}\frac{1}{2^{3i}}\big)} + n^2 = \\ n^3 \sum\_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 $$ My problem begins here. In order to solve it I'd say that the series in questions can be solved as :
$$ {\displaystyle \sum \_{k=m}^{n}x^{k}={\frac {x^{m}-x^{n+1}}{1-x}}\quad {\text{with }}x\neq 1.} $$
which applied to my scenario would yield
$$ n^3 \left(\frac{1 - (\frac{1}{2})^{log^n}}{1 - \frac{1}{2}}\right) + n^2 = \\ 2n^3 - 2n^2 + n^2 = 2n^3 - n^2 = \Theta(n^3) $$
But my professor says :
$$ n^3 \sum\_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 \leq n^3 \sum\_{i=0}^{\infty}{\big(\frac{1}{2^{i}}\big)} + n^2 = \\ n^3 \frac{1}{1 - \frac{1}{2}} + n^2 = 2n^3 + n^2 $$
And thus $T(n) = O(n^3)$ instead of $\Theta(n^3)$ since we proved only an upper limit.

My question is thus, why can't I solve the summation as I did instead of extending it to infinity?

# Answer
Yes, you could solve the summation in exact formula. Yes, you could obtain $T(n)=\Theta(n^3)$, a tighter asymptotic bound. Your professor would and should not forbid you to do that.

The message from your professor could be that an upper bound such as $O(n^3)$ is as good as $\Theta(n^3)$ more often than not. For example, once we know an algorithm runs in $O(n^3)$ time without a huge constant multiplier on a problem of input size $n$ less than 1000, then we can be comfortable starting implementing the algorithm, without worrying much that the code may take hours to run. A tighter asymptotic bound such as $\Theta(n^3)$ will not help us move ahead significantly further. On the other hand, such a tighter asymptotic usually comes with a heavier price, which is not much heavier in this particular problem, though.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Time complexity of Sieve of Eratosthenes
Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?

# Answer
Write a sum for the number of operations of removing multiples of primes. How many operations to remove all multiples of 103 for example from an array of n bits? How many operations to remove all multiples of a prime number p? So you get a sum.

Then you need to know what the sum 1/1 + 1/2 + 1/3 + ... + 1/n is (roughly) and importantly *why*. You see that by adding 1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 ... + 1/15) + ... and there is an obvious upper bound.

Now instead of adding 1/k for $2^m ≤ k \< 2^{m+1}$ you add 1/k for only the *primes* k with $2^m ≤ k \< 2^{m+1}$. How many are there? What sum do you get now? And then you have a sum that looks almost exactly like the one you started with and gives you the result.
> 1 votes

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


# Question
Title: When compiled into binary, what signifies the end of a string? How can this be differentiated from user input which compiles to the same binary?
Apologies for the strange title, this is one of those questions I can't find through a Google search just because I don't even know what I'm supposed to be searching for.

As I understand it, programs are ultimately compiled into binary which is then run by a computer.

So say, for example, you have a simple program which takes a user input and then executes some code -- when compiled into binary, there must be some sort of 'signature' that signifies the end of the user input so the computer knows where it ends. Say just for the sake of this example it's something simple like 0110. So after the user has input his data it might look like ...1100 0101 **0110** 1010 1001..., where the 0110 signifies the end of the string so the computer knows it's ended and that the rest is code from the program.

But what if the user input contained the same signature? Say the user input, after conversion to binary, came out to be ...**0110** 0010 **0110** 1010 1001... What is there to prevent the user from 'tricking' the computer into thinking the user input has ended, and then running malicious code now that the PC believes it's part of the program and not the string?

Hope this question makes any sort of sense, I'd be incredibly grateful if someone could explain this to me. It seems so trivial but it's been bugging me that I can't find an answer for it.

# Answer
Both programs in binary form and binary user data are usually stored in *files*, and normally the filesystem records the length of all its files separately. So, the operating system always knows the end of the binary string, which is supposed to be loaded and executed as a separate process. Please see this question and its answers for more information.

Could an attacker use a binary input with malicious code, added in the end of input string, to modify normal program behavior? Yes, and this method of attacking is called *buffer overflow*. Fortunately, modern programs normally don't use input functions, which can lead to the buffer overflow.
> 0 votes

---
Tags: security
---


title: Complexity guess and induction proof

text:
# Question
Title: Complexity guess and induction proof
I was trying to prove by induction that
$$ T(n) = \begin{cases} 1 &\quad\text{if } n\leq 1\\ T\left(\lfloor\frac{n}{2}\rfloor\right) + n &\quad\text{if } n\gt1 \\ \end{cases} $$ is $\Omega(n)$ implying that $\exists c\>0, \exists m\geq 0\\,\\,|\\,\\,T(n) \geq cn \\,\\,\forall n\geq m$

Base case : $T(1) \geq c1 \implies c \leq 1$

Now we shall assume that $T(k) = \Omega(k) \implies T(k) \geq ck \\,\\,\forall k \< n$ and prove that $T(n) = \Omega(n)$.
$$ T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\ c \leq 2 - \frac{2}{n} $$
So we have proved that $T(n) \geq c n$ in :

1) The base case for $c \leq 1$

2) The inductive step for $c \leq 2 - \frac{2}{n}$

Yet we have to find a value that satisfies them both for all $n\geq 1$, the book suggest such value is $c = 1$ which to me is not true since :

$$ 1 \leq 1\\1\leq2 - \frac{2}{n}\implies 1 \leq 0 \text{ for n = 1} $$
My guess would be $0$ but is not an acceptable value; So we just say its $\Omega(n)$ but for $n \gt 1$?Or how can we deal with it?

# Answer
> 1 votes
It looks like you have used a heavy machinery but only to arrive at a wrong conclusion.

---

Here is a simple proof that $T(n)=\Omega(n)$.

* It is clear that $T(n)\ge0$.
* Hence $T(n)=T(\lfloor{\frac n2}\rfloor)+n\ge n$ for $n\ge2$. Done.

---

> Now we shall assume that $T(k) = \Omega(k) \implies T(k) \geq ck \\,\\,\forall k \< n$ and prove that $T(n) = \Omega(n)$.
>
> $T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\ c \leq 2 - \frac{2}{n}$

What you are doing above is trying to find a sufficient condition for a wanted $c$. In the end, you have found that "$c \leq 2 - \frac{2}{n}$ for all $n$" is a sufficient condition for a wanted $c$. However, that condition is not necessary for a wanted $c$.

Second, you could have succeeded had you noticed that you can assume $n\ge2$ in " $T(k) \geq ck \\,\\,\forall k \< n$ and prove that $T(n) = \Omega(n)$". Then you would have found "$c \leq 2 - \frac{2}{n}$ for all $n\ge2$", which is equivalent to "$c\le1$". So you could have obtained $c=1$ at all.

Third, in order to prove $T(n)=\Omega(n)$, you do not have to show that for some $c\gt0$, $T(n)\ge cn$ for all $n$. It is enough to show that there exists $m$ and $c\gt0$ such that $T(n)\ge cn$ for all $n\ge m$. So you can try $m=2$ or $m=2019$ or $m=10^{80}$.

---

The following exercise is somewhat off the track of big $\Omega$-notation.

**Exercise**. Show that $T(n)=2n-b(n)$, where $b(n)$ is the number of 1s in the binary representation of $n$. Show that $T(n)\sim 2n$ when $n$ goes to infinity.

# Answer
> 1 votes
You're overthinking. $T(\lfloor\frac{n}{2})\rfloor \ge 1 \Rightarrow T(n) = T(\lfloor\frac{n}{2})\rfloor + n \> n \Rightarrow T(n) = \Omega(n)$

---
Tags: recurrence-relation
---


# Question
Title: Minimize same placed elements in a list of permutations (Heap)
I'm trying to optimize the permutations generated from a set of n elements.

Here is the pitch: I have a set of 6 elements $\\{1,2,3,4,5,6\\}$ and I want to create 10 permutations. I could use Heap algorithm to keep 10 among 6! possible combinations.

But I'd like to add specific constraint : I want to select the 10 permutations that **minimize the number of elements at the same index**. (avoid having 10 permutations with the 3 at the same index for example)

For instance, I simply create the first 6 permutations by rotating my initial set from 1 to 6 to the right to obtain the following combinations: $\\{1,2,3,4,5,6\\}$, $\\{2,3,4,5,6,1\\}$, $\\{3,4,5,6,1,2\\}$, $\\{4,5,6,1,2,3\\}$, $\\{5,6,1,2,3,4\\}$, $\\{6,1,2,3,4,5\\}$

Now, I would like to generate additional combinations following my constraint, do you have any clue or advice ?

# Answer
My initial guess, based on some cursory knowledge about Permutohedrons:

Given your set $S = {1,2,3,...}$, generate all permutations $P(S)$ and define a multigraph $G(V,E)$ where $V = P(S)$ (each permutation is a vertex) and the edge-set $E$ consists of pairs of permutations that share an element at a common location (e.g. $123456$ and $123465$ are connected by $4$ edges).

Your problem is then picking a subset of $V' \subset V$ s.t. the subgraph induced by $V'$ has as few edges as possible.

Considerations:

* You can use a weighted graph instead of a multigraph. Replace $n$ edges with 1 edge with weight $n$. The optimization objective would then be total edge weight of the induced subgraph.
* Based on the many symmetries, I would guess that it should be possible to achieve a very good (maybe even optimal) solution with a greedy algorithm.

Possible greedy algorithm:

* Construct graph, initialize $V' = \emptyset$
* Until $|V'| = n$:
    + For each $v \in V \setminus V'$: $v^+ :=$ total weight of edges between $v$ and $w\in V'$
    + If $v^+ = 0$, add $v$ to $V'$. Else, add vertex with lowest $v^+$.
> 0 votes

---
Tags: optimization, permutations
---


# Question
Title: How to create a model which predicts the radius of a circle?
My training set is made up of 2d images with one imperfect but broadly circular shape in them (plus plenty of noise). I wish to train a model to predict the "radius" (obviously it's a somewhat subjective concept here) of the shape.

Let's say that I know the approximate center of the shape.

What approach would you use? Have each input to the model be one of the pixels including that pixel's distance from the center, as well as its colour?

What if I also wanted to predict the volume of the shape, and it was less regular?

# Answer
Finding reasonably-regular shapes in noisy data? I'd try classical techniques first, like RANSAC or a Hough transform.

Why machine learning?
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Are consensus (and atomic broadcast) protocols limited by single node's resources?
The main question is the following:
**When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, dataset size) of the system are limited by the performance of a single node?**

To give an example:
A system based on partitioned-logs, like Apache Kafka, can provide ordering guarantees in a single partition, but it can't provide any ordering guarantees between different partitions. However, this gives Kafka the capability to scale to extremely large datasets. **I was contemplating whether it would be possible to create a system that could provide the ordering guarantee for the whole dataset, while also allowing the dataset's size to increase in the same quasi-linear way**.

My speculative answer to this is **no** for the following reason:
It's been proved that the atomic broadcast problem is equivalent to the consensus problem *\[1\]*. Based on the fact that the consensus problem requires an elected leader, which drives the consensus process, I concluded that the scaling capabilities of such a system is limited by the resources of a single node.

Are there any flaws in my thinking ?

\[1\]: https://en.wikipedia.org/wiki/Atomic\_broadcast#Equivalent\_to\_Consensus

# Answer
> 2 votes
Your argument for "no" is flawed, for two reasons:

* When we say that X reduces to Y, we mean that a solution to Y is one way to solve X. But there might be other ways to solve X that don't rely on solving Y.
* Some protocols for consensus elect a leader, but that doesn't necessarily imply that *all* approaches to solve consensus require electing a leader. (For example: consider Bitcoin. No leader, but it arguably solves a consensus kind of problem.)

# Answer
> 0 votes
I've already accepted D.W.'s answer above, but posting some of my later findings for reference of people that end up reading this question:

* As implied in the question, all consensus algorithms (e.g. Paxos, Raft, Chandra–Toueg) have an elected leader (even a temporary one) which is driving the convergence to the consensus result. This aspect creates a somewhat central bottleneck that would make a quasi-linear scaling extremely challenging. For instance, adding nodes to the system to increase performance would increase coordination, thus preventing big performance increases
* With regards to Bitcoin and other similar (blockchain) approaches, it does not require an elected leader, but it solves a different version of the consensus problem. More specifically, Bitcoin achieves probabilistic (not deterministic) consensus.

---
Tags: algorithms, distributed-systems, consensus
---


# Question
Title: Regular Expression: Writing an expression with at least two characters in length?
A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\\{x, y\\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members of $L$ while $xy$, $yyy$, and $yyxx$ are not in $L$.

(a) Write a regular expression to describe the language $L$.

I thought perhaps $\Sigma x\Sigma^\*$ would be the correct answer, but then $\Sigma$ could be either an empty string or $x$ or $y$, and the empty string would make it no longer valid because $x$ wouldn't be the second symbol. Is there some kind of expression that could mean $(x + y)x\Sigma^\*$?

# Answer
$\Sigma$ does not include the empty string; it only contains the **characters** of the language, and the empty string is not a character. As user ttnick said in a comment, in general, if $\Sigma=\\{x\_1,x\_2,\dots,x\_n\\}$, then "$\Sigma$" in a regex represents $x\_1 + x\_2 + \dots +x\_n$ (equivalently $x\_1 \cup x\_2 \cup \dots \cup x\_n$, depending on what notation you're using). The empty string comes from taking the Kleene star ($\Sigma^\*$) of the alphabet $\Sigma$.

For a tiny bit of theory background, this is because we want the Kleene star to produce a *monoid*, which is a mathematical object that 1) has an associative composition operation—in this case, string concatenation—and 2) has an element $\varepsilon$ such that for any other element (string) $s$, we have $\varepsilon s=s\varepsilon=s$. Intuitively, you can think of the Kleene star $\Sigma^\*$ as "the set of strings $s$ such that all characters in $s$ are in $\Sigma$", and this is clearly (though vacuously) true of the empty string!
> 3 votes

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


# Question
Title: Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?
Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges.

Is the following statement true?
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected.

I've proved it for $|E|=n-1$:

Per induction:
Start:
For $\left|V\right|=1$ the graph is trivially connected.

Induction step:
Let the statement be shown for all graphs $G=\left(V,E\right)$ where $\left|V\right|=n-1$ and $|E| = n-2$.

Let further $G=\left(V,E\right)$ with $\left|V\right|=n$ and $|E| = n-1$ be given.

We're now looking for an induced sub graph $G|\_{V^\prime}$ where $V^\prime\subset V, \left|V^\prime\right|=n-1$, so that $G|\_{V^\prime}$ has at least $n-2$ edges.

(Any such sub graph can have at most $n-2 $ edges, as there'll always be at least one edge that originally lead to the removed node)

Let's now assume that every sub graph $G|\_{V^\prime}$ has less than $n-2$ edges.
Then, the removed node in any sub graph would have at least $2$ edges.

Thus, every node must have at least $2$ edges, and therefore there'd have to exist at least $n$ edges in the graph.

Therefore, there's at least one sub graph $G|\_{V^\prime}$ with $n-2$ edges, for which our induction assumption holds. And because there is one edge from $G|\_{V^\prime}$ to the erased edge, we get that $G$ is connected.

Therefore, the induction is completed.

However, if I try to generalize the above proof, the same style leads to an inequality that only holds if $|E|\>|V|$.

Therefore, if the above proof can be generalized, how would it look? If not, what's an example where it fails?

# Answer
> If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge , then $G$ is connected.

No, it is not true. Here is an counterexample.

Graph made at https://graphonline.ru/en/

**Exercise.** Construct a simpler counterexample where $|V|=n$ and $|E|=n-1$.
> 3 votes

---
Tags: graphs, connected-components
---


# Question
Title: Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}
I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}\*, |w| = k}. In the website it lists the answer and I'm having a little bit of trouble trying to figure out what a specific part of this answer means. It states:

> Assume L is regular. From the pumping lemma there exists a p such that every w ∈ L such that |w| ≥ p can be represented as x y z with |y|≠0 and |xy|≤ p. Let us choose a^2p b^p. Its length is 3p≥p. Since the length of xy cannot exceed p, y must be of the form a^k for some k \> 0. From the pumping lemma a^2p-k b^p must also be in L but it is not of the right form since the number of a’s cannot be twice the number of b’s (Note that you must subtract not add , otherwise some a’s could be shifted into w). Hence the language is not regular.

So my issue lies in the very last line of the proof where it states that " you must subtract not add, otherwise some a's could be shifted into w"

Is there anyone that could help me visualize what this could possibly mean, I feel as though it may be trivial but I seem to be having trouble with it.

Thank you in advance!

# Answer
In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma.

Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$.

In this case, however, you reach a contradiction by looking at the word $xz$ (i.e., $xy^0z$). So you are pumping "down", or subtracting copies of $y$.

The reason for this is that if you look at e.g., $xy^2z$, then you get a word of the form $a^{2p+k}b^p$, but this word might be written as $a^{2r} a^lb^p$ with $l+p=r$, so you would not reach a contradiction.
> 2 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: (M)ILP overlap of two intervals

text:
# Question
Title: (M)ILP overlap of two intervals
I got an ILP Model where $c\_i$ represents the starting time for a visit$\_i$. $c\_i$ is already constraint by a number of constraints, one is $c\_i \> 0$.

I have now outside of my model 0 or multiple desired intervals for the visit$\_i$, lets call them $dStart\_{ik}$ and $dEnd\_{ik}$ where k represents the k-th desired interval. i started by adding two variables per k: $desiredStart\_{ik}$ and $desiredEnd\_{ik}$.

I added the constraints

$desiredStart\_{ik} \>= dStart\_{ik}$

$desiredStart\_{ik} \>= c\_{i}$

$desiredEnd\_{ik} \<= dEnd\_{ik}$

$desiredEnd\_{ik} \<= c\_{i+1}$

$desiredDuration\_{ik} \<= desiredEnd\_{ik} - desiredStart\_{ik}$

with the last constraint, i get the problem if the intervals do not overlap, the $desiredDuration\_{ik}$ gets negative. So I added a "helper" Variable $desiredHelper\_{ik}$ to it so it looks like this:

$desiredDuration\_{ik} \<= desiredEnd\_{ik} - desiredStart\_{ik} + desiredHelper\_{ik}$

The general problem of my model is a minimsationProblem, so I added these two terms to the target function:

$+100000 \sum\_{i=0}^N \sum\_{k=0}^N desiredHelper\_{ik} -\sum\_{i=0}^N \sum\_{k=0}^N desiredDuration\_{ik} $

With this formulation I see a problem, it favours solutions where the desired interval is closer by the actual solution. Is there a better formulation? how could I avoid the $desiredHelper\_{ik}$ variable?

# Answer
In case someone else needs this in the future

I ended up using indicator constraints

$desiredOverlap\_{ik} = 1 \rightarrow desiredEnd\_{ik} - desiredStart\_{ik} \geq 0$ $desiredOverlap\_{ik} = 1 \rightarrow desiredDuration\_{ik} = desiredEnd\_{ik} - desiredStart\_{ik}$ $desiredOverlap\_{ik} = 0 \rightarrow desiredEnd\_{ik} - desiredStart\_{ik} \leq 0$ $desiredOverlap\_{ik} = 0 \rightarrow desiredDuration\_{ik} = 0$
> 0 votes

---
Tags: linear-programming, integer-programming, intervals, constraint-programming
---


# Question
Title: Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)
I am learning about quantum error correction which is for a part based on classical linear error correcting code.

There is a very basic answer on an exercice I do not understand. Here is the problem (From Nielsen & Chuang, page 450, exercice 10.25)

> Let $C$ be a linear code. Show that if $x \in C^{\perp} $, then: $\sum\_{y \in C} (-1)^{x.y} = |C|$ Show that if $x \notin C^{\perp}$, then: $\sum\_{y \in C} (-1)^{x.y}=0$

I can show the first one using the definition, basically if $x \in C^{\perp}$ by definition $\forall y \in C$ I have $x.y=0$

Thus: $\sum\_{y \in C} (-1)^{x.y} = \sum\_{y \in C} (-1)^0 = |C|$ (where I assume that what is called $|C|$ is the number of element in the linear code which is $2^k$ if we want to encode $k$ bits an information right ?

**However** I don't understand the second one. Indeed, if $x \notin C^{\perp}$ then $x.y=1$ (We work with modulo 2 scalar product). And we have:

$$\sum\_{y \in C} (-1)^{x.y}=\sum\_{y \in C} (-1)=-|C|$$

Where is my mistake ?

**In summary my questions are:**

* Do you agree with me that if we want to encode $k$ bits of info, then $|C|=2^k$
* Why for $x \notin C^{\perp}$ $\sum\_{y \in C} (-1)^{x.y}=0$

# Answer
Suppose that $e\_1, \ldots, e\_k$ are (linearly independent) rows of the generator matrix of $C$. We can find vectors $e\_{k+1}, \ldots, e\_{n}$ s.t. $\\{e\_i\\}\_{i=1}^n$ is a basis in $\mathbb{F}\_2^n$ (not necessarily orthogonal).

$\textbf{Claim 1.}$ $\exists i \in \[k\],$ s.t. $\langle x, e\_i \rangle = 1$. Otherwise, for $\forall y \in C$ the inner product $\langle x, y \rangle = \sum\_{i=1}^k \beta\_i \langle x, e\_i \rangle = 0,$ where $y = \sum\_{i=1}^k\beta\_ie\_i$ is the basis decomposition of $y$ (all operations are modulo 2). Hence, the assumption that $x \notin C^{\perp}$ is incorrect.

Without loss of generality, $\langle x, e\_1\rangle = \ldots = \langle x, e\_s\rangle = 1$, $\langle x, e\_{s+1}\rangle = \ldots = \langle x, e\_k\rangle = 0$ for some $s \in \[k\]$.

Then $\langle x, y\rangle = \sum\_{i=1}^s\beta\_i$. The number of sequences $\\{\beta\_i\\}\_{i=1}^s$ of an even weight is the same as the number of odd-weight sequences, and it's equal to $2^{s-1}$, which concludes the proof.
> 1 votes

---
Tags: error-correcting-codes
---


# Question
Title: For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones?
I'm reading up on bitwise operators, complements, and two's complements, and I'm wondering why the lower limit of a range (aka lowest negative number) isn't all zeroes in binary, and the upper limit isn't all ones.

For example, for 8 bit integers, why don't we represent `-128` as `0000 0000`, `-127` as `0000 0001`, `-1` as `0111 1111`, `0` as `1000 0000`, and `+127` as `1111 1111`?

# Answer
> 1 votes
This would make it basically impossible to implement the C language. In the C language, a value that can represented both as a signed and unsigned integer must have the same bit representation.

There are other problems, like you can’t use the same hardware for adding signed and unsigned integers, conversion between signed and unsigned requires an actual hardware operation.

---
Tags: integers, binary
---


# Question
Title: Expressing unsigned comparison through signed comparison of 2's complement
Let `n > 0` be a natural number and for any two reminders `a, b` modulo `2^n` we have that `a < b` ***iff*** `a xor 0x800..00 <(signed) b xor 0x800...00`.

It is also true that `a <(signed) b` iff `(0x800...00 & b <= 0x800...00 & a) && (a & 0x7FF...FFF < b & 0x7FF...FFF)`.

Is there a way to prove the equivalence of these two propositions?

# Answer
It's even a bit simpler, namely both:

* `a <u b == (a ^ m) <s (b ^ m)`, and,
* `a <s b == (a ^ m) <u (b ^ m)`

Where `m` is the mask with the sign bit set.

I don't have a formal proof for that, but the image below shows what is happening. The top row shows the "unsigned order" of the number line, chopped in half, with the first part having a 0 in the top bit and the second half having a 1 in the top bit. The bottom row shows the same sub-ranges but in the "signed order". The bottom block in the signed case is the same block as the top block in the unsigned case. Notice that the signed and unsigned order of the two sub-ranges is swapped, but the order within the sub-ranges is the same.

XORing by `m` is equivalent to adding `m` and to subtracting `m`, so you may think of it as:

* swapping the order of the two sub-ranges (xor)
* pushing the two sub-ranges to the right (by the width of a block), with wrap-around to the left side (addition)
* pushing the two sub-ranges to the left, with wrap-around to the right side (subtraction)

In any case the order of the blocks is swapped, so it swaps between the signed order and the unsigned order.
> 2 votes

---
Tags: boolean-algebra, modular-arithmetic
---


# Question
Title: Why is left recursion and left factoring no problem in bottom up parsing?
i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced. But why is this then a problem in LL(k) parsing?

# Answer
> 4 votes
LL parsing must predict which production will be used before it starts parsing the contents of that production. (It is a *top-down* parse — it constructs the parse node and then fills in the children.)

LR parsing is bottom-up; first it lets the children be recognised, and only then does it apply the production and create the parse node. Consequently, it does not need to know which production will be used until the end of the production, so it can handle a grammar where two or more productions start with the same symbols.

Also, since LR parsing does not immediately expand the predicted production onto the stack (or recursively call itself to parse the predicted production) recursive productions are not problematic.

---
Tags: compilers, parsers
---


title: Algorithm for detecting overlaps

text:
# Question
Title: Algorithm for detecting overlaps
*This is a real-world application, not a student assignment.*

Suppose a list of events of that have `startTime` and `endTime`, and some overlap information. In pseudocode:

```
class Event {
    Time startTime;
    Time endTime;
    bool overlapsStart;
    bool overlapsEnd;
}

```

Events are considered overlaping if and only if their times intersect, but it's not considered overlap if some event just "touches" another (starts exactly when some other finishes).

There are two types of event: `NormalEvent` and `EmptyEvent`.

---

**What I want?**

For each event in the list, I want to:

1) Remove all `EmptyEvent`s that overlap another event of any type. In special, if some `EmptyEvent` overlaps another `EmptyEvent`, only one needs to be removed, so that the overlap ceases.

2) The `NormalEvent`s are first ordered by `startTime`, and then their booleans are set:

* `overlapsStart` is true if the event overlaps some event that comes **before** it.
* `overlapsEnd` is true if the event overlaps some event that comes **after** it.

---

**A trivial example:**

```
event1 = 6:00AM ➜ 8:00AM

```

and

```
event2 = 7:00AM ➜ 9:00AM

```

then:

```
event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

```

**Another example:**

Now, this is what happens if some event "contains" another:

```
event1 = 6:00AM ➜ 9:00AM

```

and

```
event2 = 7:00AM ➜ 8:00AM

```

then, first event1 is put before event2, since it starts before. Then:

```
event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

```

---

Naive implementation: I could analyze each event in turn, one by one, looking at all other events. That's easy, however this is too slow for a large number of events.

**My question:** What's an efficient way of solving this?

# Answer
> 2 votes
I suppose you want to delete as little EmptyEvents as possible.

In that case, you can achieve what you want in `O(nlog(n))` time, where `n` is the number of events.

Proceed as follows:

* First, get rid of the `EmptyEvents` which overlap with a `NormalEvent`. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a `counter = 0` and an empty unordered set `S`. Now go through your vector of times in order.

+ Each time you come across the start-time of an `EmptyEvent`, if `counter > 0`, then flag that event for deletion. If `counter == 0`, put that event (or rather its id) in `S`.
    + Each time you come across the end-time of an `EmptyEvent`, if `counter > 0`, then flag that event for deletion. Delete the corresponding event from `S` (if it is still in there).
    + Each time you come across the start-time of a `NormalEvent`, increase the `counter` by `1`.
    + Each time you come across the end-time of a `NormalEvent`, decrease the `counter` by `1`, flag all `EmptyEvents` in `S` for deletion and clear `S`.

(then delete all the flagged events)
* Then, choose the largest subset of `EmptyEvents`, no two intersecting. To do so, sort all `EmptyEvents` according to end-time. Then just go through these events and greedily select one each time it doesn't intersect with the last selected one.
* Then, set all the `NormalEvent` booleans. Set a `counter = 0` and `prevStart` to track the most recent start-time. Sort all `NormalEvents` start and end-times. Iterate through them in order.

+ Each time you come across start-time of `NormalEvent` `e`, set `e.overlapsStart` to `counter > 0`. Then increase `counter` by `1`. Also set `prevStart = e.startTime`.
    + Each time you come across end-time of a `NormalEvent` `e`, decrease the `counter` by `1` and set `e.overlapsEnd` to `e.startTime < prevStart`.

I'll let you convince yourself of the validity of each step. But here is a good starting point if you are unable to do so : Interval scheduling on Wikipedia

# Answer
> 2 votes
@Tassle algorithm works great but needs more explaining for vectors ordering.

> To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order.

The priority for the first vector ordering is:

```
Time
End-time over start-time
NormalEvent over EmptyEvent

```

> Then, set all the NormalEvent booleans. Set a counter = 0 and an empty unordered set S of Events. Sort all NormalEvents start and end-times. Iterate through them in order.

The priority for the second vector ordering is:

```
Time
Start-time over end-time
NormalEvents over EmptyEvent

```

---
Tags: algorithms, efficiency, intervals, ordering
---


# Question
Title: Detecting spoken words in audio stream or file?
I am a hobbyist interested in single word recognition. What is the state of research? Where I can get papers or/and software tools regarding that?

Thanks in advance for any advice!

# Answer
Its a huge field. Basics are to convert the audio into a spectragraph (a Fourier transform). That highlights what frequencies are present in the signal and at what intensities. From this you break up windows (wavelets in some models) and learn to identify the phonemes from these. Phonemes are the names for the types of sounds you can make with your mouth. There is a lot biology in this, how air leave your mouth, if your tounge is against the roof of your mouth, behind your teeth etc. This all affects what frequencies result and subsequently you see those in the spectrograph. With experience you can read phonemes right off from these graphs.

Phonemes are not letters in a written alphabet, they are an alphabet all their own. But the work of linguist have decoded what phonemes emerge from pronouncing words. It is tricky business because unlike written words, when we speak one words phonemes can blend with the start of another. So detecting single words is actually involved. You instead start to score the likelihood of a sequence of phonemes and work back to the most probable sequence. This can be done with hidden Markov models, but the rise of neural nets might be changing what's the best approach here. But certainly this is the place that becomes language specific.

A final common component is domain and grammar. Producing text from speech works best if there is an expectation that the words come from a limited domain, such as ordering your pizza or sending text messages. Again the linguist have to help by providing language models that map spoken language (often quite different from rules of written language) to likely sequences of words. Pauses and intonation have to provide clues for punctuation. So there is a lot of training and retraining to do within a domain to get it work.

Of the list of things here about the only one that springs to mind as "go do it yourself" would be to read in an audio stream and produce the spectragraph. That much is classical signal processing and calculus. As for phonemes, linguistic, random models, and machine learning... those seem to me to be specialist material.

Well at least this is how it was done in broad strokes years ago when I was peripherally involved. I'm sure it has advanced but hope this gives some help.
> 1 votes

---
Tags: pattern-recognition
---


# Question
Title: smaller size approximation to minimum vertex cover
Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?

Usual algorithms seems to aim to find an approximation such that the output is a cover, but may have more vertices than the minimum cover. Instead, I want a smaller set - I don't mind if some edges are still left and is therefore not a cover. Between two smaller sets, the one that covers more (total number of edges) is preferable.

# Answer
> 0 votes
Do you want a set whose size is a lower bound? Or do you want a lower bound on the size?

If you want a set, does it need to be a subset of a minimum vertex cover, or just a smaller set (in the latter case, any set of the appropriate cardinality would do)?

Since there is a well-known approximation algorithm that is a factor of two over-approximation, you can divide the result by two to get a factor of two under-approximation. In fact, these notes use a lower bound to prove the over-approximation factor.

---
Tags: algorithms, graphs, approximation
---


# Question
Title: Subtyping and subkinding, are they relevant?
I'm thinking about a type system that has some special kind of some certain types that are subtypes of the universe kind `type`.

Imagine the typing relation, where $A$ and $B$ are both types, $\textbf{Type}$ is the universe kind, like `*` in Haskell or `Type` in Idris or `Set` in Agda; while `<:` denotes subtyping:

$$ A:a \\ B:b \\ A \<: B \\ a \<: \textbf{Type} \\ b \<: \textbf{Type} $$

Then what should the relation between $a$ and $b$? Could one of them be the subtype (or subkind?) of the other? Although it is fine to make $a$ and $b$ distinct, but ideally we want more consistent subtyping (subkinding) relations to present.

In other words, if I allow either $a \<: b$ or $b \<: a$, will the type system become inconsistent?

# Answer
There will be no inconsistency. Those arise from shady postulates which state that some subkind is an element of itself, or that "too large" a kind/type is an element of a "too small" one (the most famous example is $\mathrm{Type} : \mathrm{Type}$), but that is not what we are dealing with here.

To give an example of what you're looking for, take $\mathrm{Type}$ to be the class of all sets. For the subtype and subkind relations we simply use subset and subclass inclusion. Take $a$ to be the class of all finite sets, and $b$ the class of all countable sets. Let $A = \\{23, 42\\}$ and $B = \mathbb{N}$. Then we have $A : a$, $B : b$, $A \subseteq B$, $a \subseteq b$, and both $a$ and $b$ are subkinds of $\mathrm{Type}$. And it would not be difficult to arrange $A \subseteq B$ and $b \subseteq a$, if we so wished.

Or you could take $\mathrm{Type} = a = b$ and $A = B$, but that's not a very informative answer, even though it has its virtues.
> 2 votes

---
Tags: type-theory
---


# Question
Title: Efficient algorithm to simulate dealing cards from a large deck of cards?
In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are `N` players, card `i` goes to player `i mod N`). If the number of each type of card is known, is there a way to simulate dealing the cards and get a count of each type of card each player has?

For example, if there are N=3 players, and there are 5 card types and the count of each card is `[3000000000, 3000000000, 3000000000, 3000000000, 2]`, one possible output is `[1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 0]`, which represents the number of cards of each type that each player has.

A naive algorithm is to create a large array of all of the cards, do the Fisher–Yates shuffle on it, and then go through each element and increment the count of the card for the current player and set the current player to the next player. For the example above, this creates an array of size 12000000002 and requires that many iterations, but there are only 5 card types and 3 players (output is size 15).

Is there a more efficient algorithm? It would have to generate the output with the same probability that the naive algorithm would.

# Answer
In the special case of two players and two card types, this is exactly the hypergeometric distribution. More accurately, the number of cards of the first type that the first player gets is distributed hypergeometrically; and the rest of the deal can be deduced from that.

Conversely, you can simulate the entire dealing process by sampling appropriate hypergeometric distributions. Indeed, the number of cards of the first type that the first player gets had hypergeometric distribution. After deciding that amount, remove these cards and reduce the number of cards that remain for the first player and repeat, until you have detail the first player their entire hand. Then repeat with the other players.

The two problems are thus equivalent. Presumably there are online resources, and probably even libraries, for sampling hypergeometric random variables efficiently.
> 2 votes

---
Tags: algorithms, probability-theory
---


# Question
Title: Sum of unique integers to cnf constraint
As a study project I try to solve the kakuro puzzle problem using SAT SOLVER. I can't really find an efficient way to convert the sum of k unique integers (1...9) to a CNF constraint. What I had in mind:

for a group of k cells (1,...k) and a sum of j:

```
    find all subsets with size of k from P({1,2,...9})
    correctSubSets <- filter out all subsets that SUM(subset)!= sum
    AllVars <- EMPTY_SET
    for i in 1...k:
       add to current cnf a union of correctSubSets s.t each prefixed with i
       add to AllVars a union of correctSubSets s.t each prefixed with i
       for each pair in AllVars:
              if pair represents two different cells ix,jy:
                  if there is no sum s.t x,y part of it:
                     add to cnf (-ix, -jy) (not ix or not jy)

example for sum = 5 and k=2:
AllVars={11, 24, 13, 22, 12, 23, 14, 21}
cnf = (11, 13, 12, 14), (21, 22, 23, 24), (-11, -22), (-11, -21), (-11, -23), (-12, -21), (-12,-22), (-12,-24) ....... and more and more

```

I fill like this is very though to implement and not efficient at all. how to solve it correctly?

# Answer
> 4 votes
Here's a strategy for solving Kakuro with a SAT solver.

1. Make a nine variables for each cell, each variable indicating whether that cell contains $1$, $2$, etc.
2. Add a exactly-one-out-nine constraint for the variables of each cell. You can do this naively in 37 clauses by adding a clause that at least one of the nine must be true ($x\_1 \vee x\_2 \vee \dots \vee x\_9$) and 36 clauses that no pair of them may be true at the same time ($(\neg x\_1 \vee \neg x\_2) \wedge (\neg x\_1 \vee \neg x\_3) \wedge \dots \wedge (\neg x\_8 \vee \neg x\_9)$).
3. For each row/column in the puzzle add an at-most-one-out-of-k constraint in the manner above for all the variables encoding ones, twos, threes, etc in that row or column to ensure each row/column uses unique numbers.
4. For each row/column make a new set of variables $q\_1, q\_2, \dots $ that encode "contains $1$, contains $2$, etc". As an example, if a row contains cells $a, b, c, d$ then "contains $2$" would be $(\neg q\_2 \vee a\_2 \vee b\_2 \vee c\_2 \vee d\_2)$ and $(q\_2 \vee \neg a\_2) \wedge \dots \wedge (q\_2 \vee \neg d\_2)$.
5. Now for each row/column, take the target sum and find all partitions using unique parts smaller than or equal to nine of it, excluding order, using exactly the right amount of parts that fit in the row/column. This may sound like a lot, but this is at worst 11 unique partitions for digits 1-9. Then for each partition introduce a new variable $p$. Suppose our target is $14$ and our partition is $14 = 8 + 3 +2 +1$. Then we add clauses $p \vee q\_9 \vee \neg q\_8 \vee q\_7 \vee q\_6 \vee q\_5 \vee q\_4 \vee \neg q\_3 \vee \neg q\_2 \vee \neg q\_1$ and $(\neg p \vee \neg q\_9) \wedge (\neg p \vee q\_8) \wedge (\neg p \vee \neg q\_7) \wedge (\neg p \vee \neg q\_6) \wedge (\neg p \vee \neg q\_5) \wedge\\\(\neg p \vee \neg q\_4) \wedge (\neg p \vee q\_3) \wedge (\neg p \vee q\_2) \wedge (\neg p \vee q\_1)$

You get the idea. The variable $p$ is now an indicator variable for the combination $q\_8, q\_3, q\_2, q\_1$ being true. It may not be necessary to also include the negated terms for $q\_9, q\_7, q\_6, q\_5, q\_4$, but it may speed up (or slow down) the SAT solver. Experiment with it.
6. Finally for all partitions variables $p\_k$ of a row/column add a single clause $p\_1 \vee p\_2 \vee \dots \vee p\_k$ indicating at least one of the partitions must hold.

---
Tags: constraint-satisfaction, sat-solvers, java
---


# Question
Title: Proof: There exists an irregular language L such that LLLL is regular
As title.

I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.

A senior gave me a hint that Lagrange's four square theorem might help, but I don't see how I can utilize it.

Thanks.

# Answer
Let us prove a more general result:

> For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular.

The language we construct will be unary, that is, of the form $L = \\{a^n : n \in S\\}$, where $S \subseteq \mathbb{N}$ is $$ S = \\{ km : k \geq 0 \\} \cup \\{ m^k + 1 : k \geq 1 \\}. $$ Let $1 \leq p \leq m-1$, and consider $p \cdot S$, i.e., the set of all sums of $p$ elements from $S$. Since all elements in $S$ are equivalent to either $0$ or $1$ modulo $m$, if $a \in S$ is equivalent to $p$ modulo $m$ then it must have the form $$a = m^{k\_1} + 1 + \cdots + m^{k\_p} + 1. $$ The base $m$ representation of $a$ thus has at most $p+1$ non-zero digits (it could have fewer if some of the $k\_i$ are equal). It is easy to check that a vanishing fraction of numbers have this property.

Let $L\_{m,p} = \\{ a^{km+p} : k \geq 0\\}$. It follows that $L' = L^p \cap L\_{m,p}$ is an infinite language with vanishing density, and so it cannot be regular (since regular unary languages are eventually periodic, and so if they have vanishing density they must be finite). Since $L\_{m,p}$ is regular, it follows that $L^p$ isn't regular.

In contrast, $m \cdot S$ is cofinite — it contains all integers which are at least $m^2-1$ — and so $L^m$ is regular.

---

The language constructed above has the "regularity profile" $\\{k : k \geq m\\}$. This is the set of powers $k \geq 1$ such that $L^k$ is regular ($L^0$ is always regular). This prompts the following question:

> What regularity profiles are possible?

Any regularity profile is closed under addition, but are there any other constraints?
> 6 votes

# Answer
Unless you must deal with unary regular languages, there is no need for complex math ...

Just pick an irregular language that is able to "capture and mask" the concatenation of itself; e.g. over $\Sigma = \\{a,b \\}$

$L = \\{ (a^ib^j) (a^n b^n) \mid i, j \geq 1, n \geq 1\\} \\; \cup \\; $ $ \\{ (a^ib^j)^k \mid i, j \geq 1, k \neq 2\\}$

$LLLL$ is equal to ....
> 3 votes

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