# Question
Title: Formal definition of the Dynamic Array - what is the Dynamic Array
I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points.

**Dynamic Array**, according to the Wikipedia's article, is a Data Structure. Article states, that:

> Dynamic array (also called as growable array, resizable array, dynamic table, or array list) is a random access, variable-size list data structure that allows elements to be added or removed.

This/above definition, surprisingly coincides with the definition of the **Dynamic Array** provided in the Data Structures and Algorithms Made Easy book (Chapter 3.5), by Narasimha Karumanchi.

**However!**,

We know, that the **Data Structure**, by its formal definition, is a specialized implementation of the **Abstract Data Type (ADT)**, but I have never seen, in any programming language ever, any specialized Data Structure called **Dynamic Array**, nor can I find any ADT which is implemented by **Dynamic Array**.

For instance, we have several Data Structures, in Java, which implement **List** interface (and interface constitutes an **ADT**, in this case, as similarly to the concept of ADT, it declares the abstract behavioural characteristic of *What* must be done, and - says nothing about *How*), and Dynamic Array is defined (as shown above) as a Data Structure implementing a concept of the Array with the functionality of adding and removing elements in/from it. Many resources (including books provided) define the model of the Dynamic Array as implementations of List - namely **ArrayList** and **LinkedList** in the case of Java.

So,

1. if the Dynamic Array is a Data Structure, then what is the ADT implemented by that Data Structure?
2. Maybe Dynamic Array suits more the concept of ADT where the implementations of it are provided in a different ways (example in Java is classes implementing List)?
3. What is the formal definition of **Dynamic Array**? is it ADT? is it Data Structure? as I find the definitions in the books/articles, quite contradictory and they oppose each other.

I, personally, think of defining it as a special type of Array Abstract Data Type, in which, structure is not a fixed-sized. I'd call it a special type of Array ADT, which makes it also ADT. Because, it's obvious, that if the Data Structures implementing the **Dynamic Array** (as said in the provided resources) are very concrete classes like **LinkedList** and **ArrayList** then the **Dynamic Array** itself is no longer a Data Structure, but rather it's some special kind of Array ADT.

What is the **Dynamic Array**? how it should be correctly and formally defined? Maybe it's just a concept of non-fixed-sized array, which is a conceptual model and has nothing to do with any ADT or DS?

# Answer
> 2 votes
I'm not sure what you mean by this:

> I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

There are many examples of dynamic arrays in mainstream programming languages:

* Python: `list`
* C++: `std::vector`
* Java: `ArrayList`
* Rust: `Vec`
* OCaml (Batteries included): `BatDynArray`
* Javascript: `array` (when dense)
* and many others...

To answer your question about whether or not dynamic arrays are data structures or ADTs: why not both? Clearly, there is a well-known implementation technique known as a "dynamic array" which is characterized by random-access arrays and exponential resizing. So in this sense, there is an agreed upon notion of a "dynamic array data structure". But also, in many of the examples I gave above, the library interface exposes functionality for explicit resizing (e.g. trimming to size). This suggests that dynamic arrays could be considered as an ADT, because the library interface includes details of performance semantics. And presumably, the "dynamic array data structure" is not the only possible implementation of the "dynamic array ADT".

# Answer
> 0 votes
Never looked at e.g. Perl, or C++, or a *lot* of other languages...

In Perl (and Raku, it's successor), an array is (at least) just as big as needed for it's last element. If I say in Raku:

```
my @a = 1, 2, 3;

```

I've got a 3-element array called `@a`, and `@a[10] = 42;` extends it to 11 elements (zero based). You can also apply `push`, `pop`, `shift`, `unshift` (add/remove at the top or the start of the array).

C++'s `vector` is also an extensible array.

C's standard library offers the realloc(3) routine, that enlarges (or reduces) a heap based memory area, copying data if needed.

# Answer
> 0 votes
As an example, in Objective-C and Swift the fact that an array is dynamic is never mentioned at all. An array is either immutable (you can't change it's elements, so no reasonable person would expect to be able to add or remove elements if you can't even change them), or it is mutable (and if it is mutable, then you can change any aspects of it, including the values of its elements, and the number of elements).

We don't even mention that a mutable array is dynamic because the fact seems so obvious. (And mutable arrays are really nice to build things like stacks, FiFo lists, priority queues and probably many other things, which are all just mutable lists with a few functions added. Other things like dictionaries and sets *use* mutable arrays internally).

As an exercise, design a mutable array where adding and removing items both at the beginning and the end of the array can be done in constant time. As a second exercise design an array where the amortized time to insert and remove items or sequences of items at index $i\_1$, $i\_2$, $i\_3$ etc. is proportional to the sum of the distances $|i\_1 - i\_2|$, $|i\_3 - i\_2|$, etc. plus the number of items added or removed. In other words, applying many sequential changes in the array is fast.

---
Tags: data-structures, arrays, abstract-data-types
---


title: Big O Tires Question?

text:
# Question
Title: Big O Tires Question?
My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.)

What's the runtime of this code?

```
int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n -1) + f(n -1);
}

```

The tree will have depth `N`. Each node (i.e., function call) has two children. Therefore, each level will have twice as many calls as the one above it. The number of nodes on each level is:

Level #Nodes Also expressed as… Or… 0 1 20 1 2 2 * previous level = 2 2^1 2 4 2 * previous level = 2 * 2^1 = 2^2 2^2 3 8 2 * previous level = 2 * 2^2 = 2^3 2^3 4 16 2 * previous level = 2 * 2^3 = 2^4 2^4

Therefore, there are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^N (which is 2^n+1 - 1) nodes. (see "Sum of powers of 2 on page 630.)

Try to remember this pattern. When you have a recursive function that makes multiple calls, the runtime will often (but not always) look like O(branches^depth), where branches is the number of times each recursive call branches. In this case 2, so O(2^n).

**As you may recall, the base of a log doesn't matter for big O since logs of different bases are only different by a constant factor. Howerver, this does not apply to exponents. The base of an exponent does matter. Compare 2^n and 8^n. If you expant 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.**

---

I do not understand the last paragraph. What base of a log? What is that and why do they say this here? What do they mean?

# Answer
This requires some basic logarithm concepts. You may have come across logarithmic equations with general definition as:

> logb(x) = y is valid if by = x | Here b is the base, y is the exponent value that makes by = x

Let's consider x having a value 64. Below are some logarithmic outputs (y) with different bases:

> log2(64) = 6 | As, 64 = 26 (base 2)
>
> log4(64) = 3 | As, 64 = 43 (base 4)
>
> log8(64) = 2 | As, 64 = 82 (base 8)

If you notice above, **the logs of different bases are only different by a constant factor**. (between 6, 3 and 2)

Now let's consider no change in base and this time we will consider exponential base, a general expression would be something like:

> log*e*(x) = y , or ln(x) = y

Let's consider x having value 2n. So y will be:

> y = log*e*(2n), or y = ln(2n)

Now if we change value of x to 8n then y would be:

> y = log*e*(8n) = log*e*(23n)

23n can be represented in terms of 2n as:

> 23n = 22n * 2n (or 23*n or 2n * 2n * 2n)

If you notice, the difference between x being 2n and x being 23n **is not by any constant factor**.

Hence validating the statement:

> **The base of an exponent does matter. Compare 2^n and 8^n. If you expand 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.**
> 0 votes

---
Tags: landau-notation, mathematical-foundations
---


# Question
Title: Does time or space complexity of arithmetic operations get affected by the number of digits?
Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations **A+B** and **C+D** have equal complexity in terms of time and space? or **C+D** is more complex due to the size of digits?

# Answer
The complexity of arithmetic operations is typically measured in *bit operations*, though not everybody agrees this is the correct measure. There is a Wikipedia page listing the complexity of the best algorithms currently known for various operations, including addition and multiplication.
> 3 votes

# Answer
It depends on the model you use. Yuval Filmus's answer assumes you use a multitape Turing machine. This is also mentioned in the Wikipedia page:

> Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.

However, for example, if you use a random access machine, the time and space complexity of an arithmetic operation of any-digit numbers is considered to be $O(1)$.
> 0 votes

---
Tags: complexity-theory, time-complexity, space-complexity, arithmetic
---


# Question
Title: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?
Question is as follows: Given regular languages $L$, $M$. Is $K=\\{uw | u,w \in \Sigma^\*,(\exists v \in M) uvw \in L\\}$ necessarily regular?

Thank you for any input.

# Answer
The most direct method to solve the problem is to show to build, starting with finite state automata $A\_L$ and $A\_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$.

For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct.

The idea can be as follows. If the automaton $A\_L$ follows a path on a word, one should be able to decompose this in the form $uvw$ in such a way that the subword $v$ can be accepted by $A\_M$. The middle part $v$ should be made invisible in the new automaton for $K$. This idea can be made formal using concepts from finite automata like $\varepsilon$-instructions and direct product construction.

If you have knowledge of other closure properties then the one from this exercise can be deduced. Closure properties you then need are intersection, morphism and inverse morphism.

Enjoy.
> 1 votes

# Answer
Yes $K$ is a regular language. Lets try to see this using closure properties of regular languages. Consider the marked duplicate alphabet of $\Sigma$, $\Sigma' = \\{ a' | a \in \Sigma \\} $. Now consider the homomorphisms $\alpha, \beta, \gamma$ defined as follows. $$ \alpha : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \alpha(a) = a $$ $$\alpha(a') = a$$

$$ \beta : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \beta(a) = a $$ $$\beta(a') = \epsilon$$

$$ \gamma : \Sigma \mapsto \Sigma'$$ $$ \gamma(a) = a'$$ Then $$ K = \beta(\Sigma^\*\gamma(M)\Sigma^\* \cap \alpha^{-1}(L)) $$

Since regular languages are closed under morphisms and inverse morphisms $K$ is also regular
> 1 votes

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


# Question
Title: Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question
hope you all are doing well.

I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien.

The question instructs the reader to "Write a function that takes as input a set and returns its power set". The input is the set S = {0,1,2}.

I understand that there are at most ***2^n*** recursive calls of the method `directedSoFar`. However, I don’t understand why we spend `O(n)` time within a call of `directedSoFar`. There are no loops inside the method, only 2 lines at the recursive case to add and remove elements into the current `selectedSoFar` solution, and another 2 lines at the base case. Doesn't this mean that we only spend constant time within a call, and not `O(n)` time?

I’ve struggled with this for a while, and have posted on the official forum as well as Reddit, but got no responses. I would appreciate it if anyone would be generous enough to help me.

Thank you

# Answer
> 1 votes
Note the following line of code:

```
powerSet.add(new ArrayList<>(SelectedSoFar);

```

Whenever we create a subset, we add the subset (list) to a list of list : `power set`. The size of subset will be $n$ (actually it will vary from $1$ to $n$, but we can take it to be $n$).

Even though adding a list requires *one line of code*, but it will involve copying all the elements. This is why it will take `O(n)` time.

---
Tags: algorithms, time-complexity, sets, java
---


# Question
Title: Is there a language that cannot be polynomially reduced to?
Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?

# Answer
> 1 votes
As stated in the comments, every problem is reducible to itself (under *any* notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...).

It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider:

* No nonempty set is many-one reducible to $\emptyset$.
* No set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$.

I'll prove the first, since the second is identical. Suppose $A\not=\emptyset$, and pick $a\in A$. Fixing any function $f$ whatsoever, we have $a\in A$ but $f(a)\not\in \emptyset$, so $f$ is not a many-one reduction of $A$ to $\emptyset$. This doesn't impact your main question, but it does illustrate a subtlety of many-one reductions. *(Note that this doesn't apply to more complex reductions like Turing or truth-table: with respect to such notions, all computable sets are reducible to each other.)*

---

You also ask in the comments whether there is some $X$ such that *every* set is reducible to $X$. The answer is **no**, regardless of what reducibility we use:

* One natural example, applicable to all the usual reducibility notions in complexity theory, is provided by the Turing jump: every language $A$ has a "halting problem analogue," $A'$. The usual proof that the halting problem is not computable relativizes to show that $A'$ is not Turing-reducible to $A$, and a very simple argument shows additionally that $A$ is $1$-reducible to $A'$ \- even logtime-$1$-reducible, under a mild assumption on the enumeration of oracle Turing machines we use. So in a very strong sense every set is strictly less complicated than its jump.

+ Incidentally the "complexity interval" between a set and its jump is always quite rich: the jump is very much *not* a successor operation. So in some sense using the jump here is massive overkill. However, there's no "natural" way so far as we know to build such "intermediate" sets (and this is why the halting problem is the canonical example of a non-computable set!). Indeed it's broadly conjectured that there are no "natural" sets $A,B$ such that $B$ is strictly between $A$ and $A'$ in terms of Turing reducibility, and we know some technical results along these lines. So introducing the Turing jump here is kind of unavoidable if we don't want to do weird stuff.
* More coarsely, basically all of the reductions we consider in the context of computability theory have the property that they're **indexed by natural numbers**: for any $A$, there are only countably many $B$ which are reducible to $A$ according to that notion. Now apply Cantor.

+ This applies even to very strong reducibilities like hyperarithmetic reducibility *(which in particular is so strong that the halting problem and the Turing jump in general is totally irrelevant)*. To break out of this situation we need to either look at "ambiguous" reducibilities like generic or coarse reductions or set-theoretic reducibilities like relative constructibility which are consistently fairly trivial. But the former are still subject to the "no-top-element" issue in a coarse manner by only slightly messier arguments, and the latter are generally only studied under additional assumptions which make them nontrivial (and in particular, lacking a top element).

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


# Question
Title: Turing machine with an oracle for a proper subset of a known undecidable language
Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A\_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $L$. Is it possible to define such an $L$ so that $T$ does not decide $E\_{TM}$ (the language of descriptions of Turing machines whose languages are empty)?

Intuitively, it seems the problem is that when the oracle answers "No", $T$ is unable to distinguish whether the string it fed to the oracle to receive this response belongs to $A\_{TM} - L$ or $\overline{A\_{TM}}$. But this doesn't really prove that $T$ can't decide $E\_{TM}$.

# Answer
It seems you're working towards the notion of **Turing reducibility**. For example, adding a nontriviality assumption you're roughly asking here:

> Is there a set which is not computable but also does not compute the halting problem?

This is an excellent question, and the answer is far from obvious - but ultimately **yes** in a very strong sense (although a subsequent follow-up question is still open and generally believed to have a negative answer). These were some of the first serious results in computability theory:

* Kleene and Post in $1945$ showed that the answer to your question is yes in a strong way: there is in fact some $A$ which is strictly intermediate between the computable sets and the halting problem with respect to Turing reducibility. Their argument also showed that we can find an $A$ which is *incomparable* with the halting problem with respect to Turing reducibility, so we get a strong affirmative answer.
* This wasn't the end of the story, though. One year earlier, Post had posed a separate question: is there a computably enumerable set which is noncomputable but does not compute the halting problem? (Such a set would necessarily be strictly weaker than the halting problem as opposed to incomparable.) This was answered affirmatively about ten years later by Friedberg and by Muchnik independently; this required a new idea, the **priority argument** (although later priority-free proofs were discovered). The priority argument subsequently became one of the most, if not the most, important technique in computability theory, and was rapidly advanced far beyond the point of the Friedberg/Muchnik argument (some relevant results here include Sacks' density theorem and Lachlan's monster theorem).
* However, the Kleene/Post and Friedberg/Muchnik degrees were all fairly artificial. Their arguments showed that the interval between the computable sets and the halting problem is extremely rich, and subsequent results would point towards them being "maximally" rich in some senses, but did not construct examples of such sets which are interesting on their own. Indeed, it is still the case that every natural Turing degree is basically just an iterate of the Turing jump (basically, something of the same "flavor" as the halting problem itself). The question of whether there is a natural intermediate Turing degree is still wildly open; there are some not-too-implausible candidates, but also results pointing towards a negative answer (and I think almost everybody believes that the answer is negative). Certainly the discover of any natural degree which isn't an iterate of the Turing jump would be one of the most important results in computability theory.
> 1 votes

---
Tags: turing-machines, undecidability, oracle-machines
---


title: How to find optimal partition subsets

text:
# Question
Title: How to find optimal partition subsets
Given a partition $\[0,1\]$，there are 5000 partition subsets $P\_i=\[a\_{i1},a\_{i2}\]\in\[0,1\], 0≤a\_{i1}\leq a\_{i2} \leq 1, i \in \\{1,2,...,5000\\}$. I want to analyze these subsets and find 10 subsets to contain sixty or seventy percent of the subsets. These 10 subsets could be disjoint, or even overlapping.

# Answer
> 1 votes
First, let me be sure u r aware of SET PACKING & SET PARTITIONING Problems

https://slideplayer.com/slide/4514539/

Then, I think ur problem is much easier avoiding the overlapping & the complete coverage constraints.

Going simple, here r some heuristics (think as u solving for max/optimal accepting 30%-40%"deviation from optimality)

1-Pick the max. length partition, then in the next 9th steps choose bet the global max of remaining partitions & the max of those starting after what u have reached so far.... I think that's O(10\*5000) let's call it $ O(k n) $

2-Do something similar to $Bucket$ $Sorting$

Divide the partition to 10 smaller partitions(put an overlapping sub partition in its starting point bucket) , then select the max length one in each bucket. Still the same order complexity $ O(k\*n) $

Finally, maybe a little bit complicated, but if u want a Theoretical abstraction of ur problem I've just watched this about the $maximum$ $K$ $coverage$ problem and the $Influence$ $maximization$ problem.

If u looked to the interval \[0,1\] as say M smaller/unit sub intervals being ur target population, and viewed each sub partition as connected to/infleuncing the sub intervals(units) it covers. Then u want to select $K$ (10 in ur case) subpartitions that gives u maximum coverage/influence

https://youtu.be/GqKbx3LCQqE

# Answer
> 0 votes
I would recommend you formulate this as an instance of integer linear programming (straightforward) and then let an off-the-shelf ILP solver solve it, and see if that is able to come up with an efficient solution in a reasonable amount of time.

---
Tags: computation-models
---


# Question
Title: Max sum non adjacent and k size subsequence
You are given a number n, representing the count of elements. 2. You are given n numbers, representing n elements. 3. You are given an integer k. 3. You are required to find the maximum sum of a subsequence having at most k elements. 4. Adjacent elements can't be selected. \*You have to solve it using Dynamic Programming (preferred - tabulation). Input Format

A number n n1 n2 .. n number of elements A number k Constraints

1 \<= n \<= 1000 1 \<= k \<= 500 -1000 \<= n1, n2, .. n elements \<= 1000 Output Format

A number. Sample Input 0

9 4 1 2 5 8 3 1 9 7 3 Sample Output 0

21

# Answer
> 0 votes
-First, it seems u mean ur elements \<=1000 not the reverse (no need for the "1000\<=" in the start of the line before the sample i/p & o/p)

-Then, it is not necessary to use dynamic programming. This is even a simpler version of this Q
How to find optimal partition subsets

-Simply search for the $ n\[max\] $ value, repeat in a loop $K-1$ times

$DO$ Find n\[max2\] $WHILE$ |max2-max1|\>1

This is just a pseudo code, if u must to, u can change it to a recursive dynamic programming form. Something like

SOL(n, k) =..... + SOL(n-1,k-1)

I hope this is clear enough

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


title: Minimize circuit functions

text:
# Question
Title: Minimize circuit functions
$\begin{array}{rrrr | rr } 0& 0 & 0 & 0 & 1 &1 &1 &1 &1 & 1&0 \\ 0& 0 & 0 & 1 & 0 &1 &1 &0 &0 & 0&0 \\ 0& 0 & 1 & 0 & 1 &1 &0 &1 &1 & 0&1 \\ 0& 0 & 1 & 1 & 1 & 1&1 &1 &0 & 0&1 \\ 0& 1 & 0 & 0 & 0 &1 & 1&0 &0 & 1&1 \\ 0& 1 & 0 & 1 & 1 &0 &1 &1 &0 & 1&1 \\ 0& 1 & 1 & 0 & 1 &0 &1 &1 &1 & 1&1 \\ 0& 1 & 1 & 1 & 1 &1 &1 &0 &0 & 0&0 \\ 1& 0 & 0 & 0 & 1 &1 &1 &1 &1 & 1&1 \\ 1& 0 & 0 & 1 & 1 &1 &1 &1 &0 & 1&1 \\ \end{array}$

Can someone explain me how to minimize this function?

right side is my output I know how to build the functions but not how to minimize functions with this type of scale

# Answer
> 0 votes
First you have to build the formula whose behavior is mirrored in the truth table, for large circuits it is impossible to simplify simply by looking at the truth table. Once you have the formula, you can proceed to apply the axioms and rules of Boolean algebra to shrink the formula.

Examples of Rules:

1. $\lnot(\lnot A \lor B) \lor A = A$
2. $\lnot(\lnot A \lor B) \lor \lnot(\lnot A \lor \lnot B)=A$
3. $A+AB=A$ (Algebraic manipulation)

# Answer
> 0 votes
What is exactly ur problem?

I mean do u need help understanding Karnaugh maps, or expressions reductions???

Karnaugh Maps for O/P one:

u draw a table for the i/p values say $AB$ for the rows and $CD$ for the columns, but remember that $11$ precedes $10$ to simplify the reduction. $d$ means $Don't$ $Care$ to use the non existing values to simplify the reduction.

```
C'D'     C'D      CD   CD'

```

A'B' 1 0 1 1

A'B 0 1 1 1

AB d d d d

AB' 1 1 d d

To simplify the F1 we take as large squares as we can (circulation is allowed)

-We take the 2 last columns together making $D$

+The 2 last rows making $A$

Then we have 2 remaining 1s, for the 1st of them we take the middle square:

* $BC$

We have the 1st corner remaining 1, trying to largen any square or rectangle, we use the $circular$ reduction and take the 4corners. i.e.,

* $B'D'$

Thus, F1=A+D+BC+B'D'

---

Now, example of the expression reduction method on the last O/P... say F7

We write down the expression for the each 1 in F7, then add them together (add here represents OR) and try to simplify normally. F7 has 1s at: 2,3,4,5,6,8,9

F7= A'B'CD'+ A'B'CD + A'BC'D' + A'BC'D+ A'BCD' + AB'C'D' + AB'C'D

Now simplify...

F7=(A'B'CD'+ A'B'CD) + (A'BC'D' + A'BC'D) + A'BCD' + (AB'C'D' + AB'C'D)

F7= A'B'C(D'+D) + A'BC'(D'+D) + A'BCD' + AB'C'(D' +D)

```
= A'B'C+ (A'BC'+ A'BCD') + AB'C'
= A'B'C+ A'B(C'+CD') + AB'C'

```

and so on,...

(u see, the karnaugh map is usually easier)

---
Tags: circuits, digital-circuits
---


# Question
Title: Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point
I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past their start and end points) to an arbitrary point.

The best I have done so far is to generate a set of sample points along each line and use a KD-tree to solve the nearest neighbor problem for the points - i.e. find the nearest line sample point to the query point. But this is inaccurate and needs a large number of samples for long lines.

I did see this: Algorithm for nearest edge detection with respect to a point (in all directions)

but it relied on a sweep method and a small number of lines of finite length.

# Answer
All your lines define a *planar subdivision*, where each polygonal *region* is bounded by a finite number of line segments or rays. So, at first you need to find a (probably infinite) region, containing a query point, and then you'll be able to select its boundary line with minimum distance from this point.

There are many ways to preprocess a planar subdivision in order to solve the Point location problem with logarithmic time complexity. Some hierarchical data structure is typically devised, which can be traversed for any query point, and it's proved, that the length of the traverse path is limited by $O(log(N))$, where $N$ is the number of regions. As @Pseudonym mentioned in comments, you can also use Binary space partitioning (BSP) to build a BSP tree - it's also a hierarchical data structure (binary tree), which will allow you to efficiently find a region, containing a query point. It looks like your problem suits well for this BSP approach.

Sorry to say, you can get regions with $O(n)$ boundary segments/rays, where $n$ is the number of lines. To overcome this difficulty you can further subdivide each region into Voronoi diagram, generalized for its boundary segments and rays. It's easy to see that the total number of such refined regions will be limited by $O(n^2)$, which still gives you logarithmic time complexity for the nearest line search. However in average case these regions with many boundary segments/rays will make up a small fraction of all regions - so in average you still will be able to quickly select the closest boundary segment/ray just by looping over the region boundary.

---

If you want to know more about general properties of the geometric structure you're working with - it makes sense to read this Wiki page.
> 1 votes

# Answer
I may have misunderstood your goal - do you assume the edges continue on in both directions even though they are defined by 2 specific points along them? I assume so because you say that the distance is defined by perpendicular distance. In which case how about this -
1. For each line segment, calculate the angle.
2. Draw an imaginary line that goes through your arbitrary point at an angle that is perpendicular to the line segment.
3. Find the point of intersection between the line segment and the new imaginary line, find the distance between that point and your arbitrary point. Keep the lowest distance.
If the lines are not infinitely long then when you check the distance, check min(distance to start point, distance to end point).
> 0 votes

---
Tags: algorithms, nearest-neighbour
---


# Question
Title: Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?
## After removing multi-sets and sets that have elements that don't exist in $S$.

$S$ = $\[9,6,7,4,5,1,8\]$

$C$ =$\[\[9,6,7\],\[4,5\],\[1,8\]\]$

Transform the values in $C$ of the shared index values with $S$. (This must be done before touching $S$)

$C$ = $\[\[1,2,3\],\[4,5\],\[6,7\]\]$

And do the same for $S$

$S$ = $\[1,2,3,4,5,6,7\]$

Square each $x$ integer in both $S$ and $C$

$f(x)$ = $x^2$, $x ∈ S$ then $C$

$S$ = $\[1, 4, 9, 16, 25, 36, 49\]$

$C$ = $\[\[1,4,9\],\[16,25\],\[36,49\]\]$

Then remove all sets with repeating sums to prevent false positives. This means no $\[1\],\[1\]s...$ that could be used, to sum up to the total sum of $S$, This also means $\[1,4,9\]$ or $\[4,9,1\]$. (leave one though!)

1. After the transformation is complete use subset-sum solver and define total-sum as $140$ (total-sum of $s$)
2. Define list of integers as a summed up set of $C$ = $\[\[14\],\[41\],\[85\]\]$
3. Run Algorithm and get the solution

## Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?

# Answer
If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $4^2=2^2+2^2+2^2+2^2$. This is enough to construct a counterexample.

Let $S=\\{1,2,3,4,5,6,7\\}$ and $C=\\{\\{1,2\\},\\{2,3\\},\\{2,5\\},\\{2,6\\}\\,\\{2,7\\},\\{1,3,4,5,6,7\\}\\}$.

There is no exact cover (the only way to get $4$ is to take $\\{1,3,4,5,6,7\\}$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.
> 1 votes

---
Tags: set-cover, polynomial-time-reductions
---


# Question
Title: Why is the commit phase in PBFT necessary?
I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that

* PREPARE phase ensures fault-tolerant consistent ordering of requests **within views**
* COMMIT phase ensures fault-tolerant consistent ordering of requests **across views**

Some tutorial glosses over that

> The PREPARE phase ensures that a majority of correct replicas has agreed on a sequence number for a client’s request. **Yet that order could be modified by a new leader elected in a view change**.

Can someone show me an example of how COMMIT interacts with view changes?

# Answer
> 6 votes
PBFT is a master piece, for its technical breakthrough and exquisitely precise language. Many descriptions on the protocol details worth reading multiple times to grasp all the nuances.

I will:

1. quote the original paper (some math notation expressed in Latex, I will use pseudo code instead)
2. add on my understanding/interpretation.
3. Q&A myself important questions
4. Answer your question directly by giving out an example

**Pre-Prepare and Prepare phases**

> We define the predicate *prepared(m,v,n,i)* ....
>
> The pre-prepare and prepare phases of the algorithm guarantee that non-faulty replicas agree on a total order for the requests within a view. More precisely, they ensure the following invariant: if *prepared(m,v,n,i)* is true then *prepared(m',v,n,j)* is false for any non-faulty replica *j* (including *i = j*) and any *m'* such that *D(m') !=D(m)* .

This means, once reached "prepared" stage (i.e. one replica has received more than 2f+1 PREPARE), this replica, if non-faulty, could be certain that, this message *m* in this view *v* is associated with this sequence number *n*.

**Commit phase**

> The commit phase ensures the following invariant: if *committed-local(m,v,n,i)* is true for some non-faulty *i* then *committed(m,v,n)* is true. This invariant and the view-change protocol described in Section 4.4 ensure that non-faulty replicas agree on the sequence numbers of requests that commit locally **even if they commit in different views at each replica**.

^^^ This is the clue for me to go back and carefully read the definition of "commit-local" over and over:

> and *committed-local(m,v,n,i)* is true if and only if *prepared(m,v,n,i)* is true and has accepted 2f+1 commits (possibly including its own) from different replicas that **match the pre-prepare for *m*;** a commit matches a pre-prepare if they have the same view, sequence number, and digest.

^^^ notice that? **match the pre-prepare**, not *match the prepare*, why? remember "PREPARE" gives certainty on ordering **within** a view, "PRE-PREPARE for m" emphasize on certainty of sequence number regardless of which view, as long as commit matches the pre-prepare.

Maybe you know why by not, but if it is still not clear, please read on.

**Q:Why COMMIT phase necessary?**

1. There are replicas (non-faulty or otherwise) that didn't receive enough (i.e. 2f+1) PREPARE messages, either due to lossy network or being offline for a while. For them, they **can't reach PREPARED stage**. But! But when they heard from 2f+1 replicas broadcasting COMMIT message, they could be certain to commit on *(m,v,n,i)*
2. Apparently, a obvious benefit for COMMIT stage is that it **accelerate the agreement/consensus process**. Intuitively, you could understand it as : I'm on my way to school, Bob told me school is closed today. I couldn't take one man's word as truth. But as I march on, I see many more classmates (who have already checked whether school is closed or not) returning back from school telling me school is closed. Up until majority told me so, I will take their word for it before reaching school myself.

**Example of cross view COMMIT**

There are 4 replicas in total. For a message *m*, I, the replica, received a COMMIT: *(COMMIT, m, v, n, i=2)*, meaning in view *v*, node #2 told me he committed. But since I didn't receive any other commits, I couldn't reach "commit-local" stage.

Now, "NEW-VIEW" message has been passed around. During protocol redo: other replicas multicast PREPARE messages for each message between *min-s* and *max-s*, then later I receive another COMMIT *(COMMIT, m, v+1, n, i=3)*

Now, could I reach "commit-local"? since I have one commit in view v and another in view v+1.

Answer is **yes**. Because new primary issued a new PREPARE for *m*, and I had two **matching commits** -- 2 commits in a 4 replicas system. Good enough.

Hope it helps! Any further comment is welcomed. Cheers!

# Answer
> 2 votes
PBFT do need the commit phase to ensure that message m is assigned with sequence number n even during view change. This is because if a message m with sequence number n is committed at some replica after 2f+1 COMMITS is received, this (n,m) will be included in NEW-VIEW message thus rebroadcasting to all other nodes by new primary.

This question confused me for quite a long time and today I get it. I will try to explain it clearly but I suggest you be very very familiar with the paper, at least you should know what does "prepared" "commit\_local" mean.

## Overview of PBFT

The PBFT have three algorithms:

* Request handling algorithm

+ The client send message to primary with "id == currentView mod |R|"
    + Three messages
        - 1) Pre-prepare(n, m, v, i). The acceptor will accept this if **in view v** they do not accept another pre-prepare whose sequence number n is assigned with another request m'. The condition "in view v" is important because it ensures that a faulty primary cannot stop a replica by sending a faulty Pre-prepare message.
        - 2) Prepare(n, m, v, i). If a replica gathers enough(2f+1) valid Prepare message it is prepared. Two non-faulty prepared replicas will agree on (n,m). This is because 2f+1 ensures that there is at least a non-faulty node k so k cannot send different messages.
        - 3) Commit(n, m, v, i). If a replica reaches "prepared", it will broadcast a Commit message and wait for another 2f Commits. Then it is committed locally and ensures that at least f+1 non-faulty replica are prepared.
* View change

+ To ensure liveness.
    + Messages:
        - 1) View-Change: If a node feels timeout it will create a View-Change. This view-change will bring all prepared messages(with proofs) known to it.For better understanding I ignore CHECKPOINT message.
        - 2) New-View: If the new primary gathers 2f+1 View-Change, it will take all prepared messages in it. The latest prepared message is marked as "max-s". The new primary will broadcast and the acceptor will redo for each sequence number.
* Garbage collection algorithm

+ A way to remove logs after backing up. We don't discuss it in this post.

## Why commit phase cannot be omitted?

## Commit phase is key to safety during view change

From a high level view, the commit phase ensures this invariant:

If commit\_local(n,m,v) is true for some replica i, then commit\_local(n,m',v+1) is false for any non-fault replica i'.

Prove:

Commit\_local(n,m,v) is reached at some replica i means that 2f+1 replica(Q1) declares prepared. This means that there is some non-faulty replica in Q1 votes for View-Change in New-View message. Hence, there is at least one prepared message (n,m) in New-View message. This message broadcasts to all other replicas with New-View message.

For any replica i' receiving New-View, it may have two status:

1) It already commit (n,m)

2) It hasn't commit (n,m) yet. It may be waiting for COMMITS, or PREPARES, or even PRE-PREPARE, whatever.

In the second case, it will reprocess from pre-prepare(n,m) phase for v+1. So (n,m) is kept during view change. In one word, the commit phase will ensure that if (n,m) is committed at some replica, then (n,m) will be included in NEW-VIEW thus it is sent to all other replicas in view-change phase.

## What if we omit commit phase?

What if we omit the commit phase? The safety is destroyed because m can be committed with n at some replicas while another m' with n committed at some other replicas.

Suppose a non-faulty replica commits the request after (m,n) is prepared in view v. This means 2f+1 replicas(Q1) declared they receive pre-prepare for (m,n) in view v.

At the same time, it is possible that no other replica is prepared yet since the network is partially synchronized. After some timeout a view change happens.

Now since no replica is prepared, it is possible that some quorum does not send any view change with sequence number \>= n, so in new primary max-s \< n. Now new primary will assign n with a new message m' from client's new request. Though at least f+1 non-faulty replica in Q1 receives pre-prepare (n,m) in view v, these old pre-prepares cannot prevent new pre-prepare messages (n, m') in view v+1 from being accepted. They are not in same view! **Recall the condition of accepting pre-prepare messages!!**

Now, (n,m) is committed in some replica while (n,m') is committed in other replicas during view change.

Conclusion: the commit phase ensures that if (n,m) is committed at some replica, then (n,m) will be included in NEW-VIEW thus it is sent to all other replicas in view-change phase.

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


title: Computing FIRST and FOLLOW

text:
# Question
Title: Computing FIRST and FOLLOW
Given the following grammar with terminals $VT=\\{\[,\],a,b,c,+,-\\}:$

> $S \rightarrow \[SX\]|a$
>
> $X \rightarrow +SY|Yb|\epsilon$
>
> $Y \rightarrow -SXc|\epsilon$

This should be the FIRST function:

> $first(S) = \\{\[,a\\}$
>
> $first(X) = \\{\epsilon,+,-,b\\}$
>
> $first(Y) = \\{\epsilon,-\\}$

What would the FOLLOW function be?

# Answer
This is the FOLLOW function:

> $follow(S) = \\{\\$,+,-,b,\],c\\}$
>
> $follow(X) = \\{\],c\\}$
>
> $follow(Y) = \\{b,\],c\\}$
> 0 votes

---
Tags: formal-languages, compilers, parsers
---


# Question
Title: Are NP proofs limited to polynomial length?
> In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.

The proofs for an NP decision problem are verified in polynomial time.

**Does this imply the proofs are at most polynomial length?**

"Well you have to read the whole input. If the input is longer than polynomial, then the time is greater than polynomial."

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Therefore, perhaps some NP problem has candidate proofs that are longer than polynomial length but checked in polynomial time.

# Answer
> 1 votes
> The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time.

While you could define proofs to exceed a polynomial length, only a polynomial prefix of the proof could be read in polynomial time, assuming the head starts at cell 0 and can move at max one cell to the right in one time unit.

# Answer
> 0 votes
A proof of "yes" instance means providing a solution. Providing a solution is providing a valid input. By definition, it can be verified in time and space polynomial relatively to the input, or else it is not a problem in NP.

It is unknown whether all proofs of "no" instances are verifiable in polynomial time and space (the difference between NP and Co-NP).

*To answer the question precisely, the proof of a "yes" instance is the input value. You cannot say that the input has polynomial length because polynomial is used when comparing to the input size. Therefore the question is meaningless because of the word 'polynomial'. If you really want a polynomial somewhere, the size of the proof relatively to the input can be defined as a linear function f(x) = ax+b where a=1 and b=0, which can be simplified to f(x)=x because the size of the input is equal to itself.*

---
Tags: complexity-theory, np, decision-problem
---


# Question
Title: How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?
I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^\*(2^{n/2})$? I can understand the algorithm for Subset Sum Problem (SSP) which is a particular instance of 0-1 KP, but for the generalized problem there might be something wrong with the step:

> ```
>   for each subset of A do
>       find the subset of B of greatest value such that the combined weight is less than W
>
> ```

As I understand, this is to search (eg. do binary search) on combined weights of all subsets of B, which takes logarithm time for each search. But after knowing which subsets have combined weight less than W, how to find the one of greatest value? If search on values of the subsets with weight \< W, it takes linear time to find the maximum since the list of value is unsorted this time. As a result, the total time complexity is no longer $O^\*(2^{n/2})$, but something like $O^\*(2^n)$.

Even if it starts from finding the subset of greatest value (easy for a table) first without constriction on combined weight, after that, verification of weight will probably turn false and thus more tests are needed for other subsets, of which the number seems associated to the table size linearly again.

Now I can only assume the total value and combined weight are strongly positive correlated, so that after finding the subset with maximum allowed weight, it takes only constant time to search around this subset for the exact one of greatest value. But I am not satisfied with this explanation. So anyone has better ideas about this issue?

PS: I have read the original paper by Horowitz, Ellis and Sahni, Sartaj, but I found the problem defined there is a decision problem rather than the common optimization problem. Maybe somebody can provide ideas in this direction.

# Answer
> 0 votes
First, precompute the weights of every subset of $B$.

Sort them by weight and put the weights and subsets in parallel arrays so that $W\[i\] = weight$ and $S\[i\] = subset$.

Then make another parallel array so that $BEST\[i\]$ is the index $j$ of the set of greatest value such that $j\<=i$. You can do this with a single scan from $i=0$ upward, remembering the greatest value seen so far at every step.

Now, to search $B$, you do a binary search in $W$ to find the maximum permissible weight, and get the best set from the same index in $BEST$

---
Tags: time-complexity, algorithm-analysis, optimization, knapsack-problems, subset-sum
---


# Question
Title: Turing reducibility of 2 versions of the satisfiability problem
I need help with this problem.

> There are 2 versions of the satisfiability problem:
>
> \[1\] decision version: determine whether an arbitrary formula f is satisfiable or not
>
> \[2\] search version: if an arbitrary formula f is satisfiable, return an assignment of truth values to variables in the formula that makes f satisfiable. if f is unsatisfiable, return NIL.
>
> Show that \[2\] is Turing reducible to \[1\].

I have to prove that the oracle algorithm of \[1\] entails that of \[2\] to say "\[2\] is Turing reducible to \[1\]".

I see that \[2\] is just the oracle algorithm of \[1\] since it discriminates the satisfiability of an arbitrary formula f.

Can this mean the oracle algorithm of \[1\] entails that of \[2\]? If can, what would be the reason?

# Answer
> 1 votes
Any algorithm that decides the satisfiability of a formula can also be used to find an assignment for a satisfiable formula:

While not all variables are assigned:

* Pick a variable and choose value 0.
* If formula is no longer satisfiable, replace value with 1.

---
Tags: reductions, satisfiability, discrete-mathematics
---


# Question
Title: What is the time complexity of finding the FIRST and FOLLOW sets?
Given how important these are for parsing, I'm surprised I wasn't able to find anything about their complexity. I'm interested in all combinations of:

What is the (edit: best known) time complexity of calculating \<FIRST | FOLLOW | FIRST and FOLLOW\> of a \<single | all\> nonterminals of a \<context-free | LR\> grammar?

Links to resources or partial answers are welcome.

# Answer
$\mathbf{first}\_1$ and $\mathbf{follow}\_1$ as relations over the symbols of a grammar $\mathcal{G}$ can be computed for a given non-terminal in $\Theta(|\mathcal{G}|)$, wnere the size of $\mathcal{G}$ is defined in a an intuitive way (basically, the sum of the lengths of the productions).

It's clear that $|\mathcal{G}|$ is a lower limit since no algorithm could work without considering every symbol of every production of the grammar. An algorithm which takes time linear to the size of the grammar (with a proof of time complexity) is provided in section 5.5 of *Parsing Theory, Vol. 1* (S. Sippu & E. Soisalon-Soininen, 1988). (If $k\gt 1$, a polynomial term is introduced because of the size of the $FIRST\_k$ sets.)

Thus, to compute the entire relation requires $O(|\mathcal{G}|\cdot|T|)$, where $T$ is the set of terminal symbols in $\mathcal{G}$. The $|T|$ factor (which could, in the worst case, be $O(|\mathcal{G}|)$) is the result of having to perform set union operations on sets of up to $|T|$ elements. In practice, there is no advantage to attempting to compute the $FIRST$ and $FOLLOW$ sets for an individual non-terminal; there is a lot of overlap in the individual computations.

These results were not new; the bibliography credits Donald B. Johnson & Ravi Sethi (1976) *A characterisation of LL(1) grammars*, but a paywall impedes my verification. The algorithms are also cited in Hunt, Szymanski & Ullman (1977) *Operations on Sparse Relations*, which refers to a 1974 paper by the same authors, with roughly the same name (paywalled, but you might be able to find it).

By way of a side note, the framework of relational expressions developed and used by Sippu & Soisalon-Soininen throughout the two volumes of *Parsing Theory* is a thing of beauty which for me was sufficient to justify my investment in the textbook. But you might be able to find it in a good academic library.
> 0 votes

---
Tags: time-complexity, parsers
---


# Question
Title: Reducibility of 2 boolean satisfiability problems
I beg some help with this problem.

> There are 2 boolean satisfiability problems.
>
> Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$.
> Problem $B$: Determining whether an arbitrary formula of size $n-1$ is $satisfiable$ in which $n$ is a positive integer $\ge 2$
>
> Prove that $A$ can be solvable if $B$ is solvable.

I guess the solution would be showing that $A$ is Turing-reducible to $B$. It means I have to show the oracle algorithm of $B$ derives the oracle algorithm of $A$.

As you see, the arbitrary formula of $B$ is $n-1$, but that of $A$ is $n$. How can I suppose to entail the oracle algorithm about $A$ from the oracle of $B$, which is determining the formula of 1-less size than that of $B$?

# Answer
> 1 votes
Problem A is reducible to Problem B in following manner:

* Pick a variable in problem A and set it to 0
* Now we have a formula of size n-1, if satisfiable with B then return satisfiable
* Else, pick problem A again and set the variable to 1
* Now we have a formula of size n-1 again, if satisfiable with B then return satisfiable else return unsatisfiable

In other words: Split problem A into two problems B using any variable. If B says unsatisfiable for both 0 and 1 then it is unsatisfiable. If it says satisfiable for at least one of the two, then it is satisfiable.

---
Tags: reductions, satisfiability, discrete-mathematics
---


title: Relaxing hypotheses of Master Theorem

text:
# Question
Title: Relaxing hypotheses of Master Theorem
*This question is related to Master Theorem on oscillating function.*

Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master Theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)=\Theta(g(n))$ for a function $g(n)$ that does not violate the regularity condition, so that the Master Theorem is applicable if $g(n)$ is used instead of $f(n)$. Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

Can I then safely conclude that $T(n)=\Theta(g(n))$? Or there are some reasonable conditions on $g(n)$ we can add (I suppose that if $g(n)$ is polinomially bounded then maybe Akra-Bazzi method will apply, even if one have to swich integration and $\Theta$, and I'm not sure this is sound)?

Notice that from $f(n)=\Theta(g(n))$ we cannot deduce that $f(n)$ is **always** less than or equal to $g(n)$ or to a $d\cdot g(n)$ for some fixed $d$ (indeed, $g(n)$ can be equal to 0 for some value of $n$, so I'm not totally convinced by the answer to Regularity condition in the master Theorem in the presence of Landau notation for f as it is not possible to prove the base case of the induction, unless one changes the initial condition). So I cannot prove by induction that $T(n)\<T'(n)$ for all $n$ and, anyway, I only want to prove $T(n)=\Theta(T'(n))$.

To give some context, this is the case I want to apply the result to: consider the recurrence

$T(n)=2\cdot T(n/2)+f(n)$

where I only know that $f(n)=\Theta(n\sqrt{n})$. Then I can unfold the recurrence obtaining \begin{equation\*} \begin{split} T&(n)=2T\left(\frac{n}{2}\right)+\Theta(n\sqrt{n})= 2\left(2T\left(\frac{n}{4}\right)+\Theta\left(\frac{n}{2}\sqrt{\frac{n}{2}}\right)\right)+\Theta(n\sqrt{n}) =\\ &=\ldots=2\left(2\left(2\ldots \left(2T\left(\frac{n}{2^h}\right)+\Theta\left(\frac{n}{2^{h-1}}\sqrt{\frac{n}{2^{h-1}}}\right)\right)\ldots\right)\right)+\Theta(n\sqrt{n}) \end{split} \end{equation\*}

until $2^h=n$, i.e. $h=\log(n)$. Then $T(n)=\sum\_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)$.

Performing the calculations I get \begin{equation\*} \begin{split} T(n)&=\sum\_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\Theta\left(\sum\_{i=0}^{\log(n)-1} 2^i\cdot\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\\ &=\Theta\left(n\sqrt{n}\cdot\sum\_{i=0}^{\log(n)-1} \frac{1}{\sqrt{2^i}}\right) \end{split} \end{equation\*} The series $\sum\_{i=0}^{+\infty} \frac{1}{\sqrt{2^i}}$ is convergent, so I can conclude (I hope correctly) that $T(n)=\Theta(n\sqrt{n})$.

On the other hand, I cannot directly apply Master Theorem, as from $f(n)=\Theta(n\sqrt{n})$ I cannot conclude $2f\left(\frac{n}{2}\right)\<cf(n)$ for some $c\<1$. Indeed, if *definitively* we have $c\_1 n\sqrt{n}\leq f(n)\leq c\_2 n\sqrt{n}$, then

$f(n)\geq c\_1 n\sqrt{n}= 2\sqrt{2}c\_1 \frac{n}{2}\sqrt{\frac{n}{2}}\geq\frac{2\sqrt{2}c\_1}{c\_2} f\left(\frac{n}{2}\right)=\frac{\sqrt{2}c\_1}{c\_2} 2f\left(\frac{n}{2}\right)$

and so

$2f\left(\frac{n}{2}\right)\leq \frac{c\_2}{\sqrt{2}c\_1} f(n)$

but $\frac{c\_2}{\sqrt{2}c\_1}$ is not necessarily less than 1.

# Answer
> 1 votes
Yes. Here is the idea.

If $f(n) = \Theta(g(n))$ then there exist constants $C\_1,C\_2\>0$ such that for large $n$, $$ C\_1g(n) \leq f(n) \leq C\_2g(n). $$ Now consider the two recurrences $$ T\_1(n) = aT\_1(n/b) + C\_1g(n) \\ T\_2(n) = aT\_2(n/b) + C\_2g(n) $$ Choosing suitable initial conditions, you can prove inductively that $$ T\_1(n) \leq T(n) \leq T\_2(n). $$ You consider a regime in which applying the master theorem gives you that $T\_1(n) = \Theta(g(n))$ and $T\_2(n) = \Theta(g(n))$. It follows that $T(n) = \Theta(g(n))$.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Convert propositional logic formulas to mathematical constraints
## Brief introduction

In all boolean (or more generally mixed-integer) linear programs, constraints are represented as a matrix $A$, a support vector $b$ and is computed by $A^T x \leq b$, where $x$ is a boolean vector one wants to optimize in some way. Another way of formulating the problem is to say that one wants to select a set of items such that a bunch of logic formulas are satisfied while optimizing some function. In my setting, I have all the soon-to-be-constraints in a list of propositional logic formulas. So, to be able to compute and solve using some kind of ILP-solver, I need to convert all logic formulas into mathematical constraints.

## Straight-forward conversion from logic formula constraints

The most straight-forward way to convert from a propositional logic formula into mathematical constraints is to first convert the formula into Conjunctive normal form (CNF for short) and then from the CNF create one constraint for each and-clause. For example, let $q$ be formulated as the logical formula $$q = (a \lor b) \rightarrow c$$, then $q$ is converted to CNF $$q\_{cnf} = (c \lor \neg a) \wedge (c \lor \neg b)$$ Now, for each conjunction clause we will have one constraint and for each variable in each disjunction we'll set $(1-x)$ if a variable $x$ is negated and just $x$ otherwise:

$$ (1-a)+c \> 0 \wedge (1-b)+c \> 0 \Rightarrow \\ c-a \> -1 \wedge c-b \> -1 \Rightarrow \\ c-a \geq 0 \wedge c-b \geq 0 \Rightarrow \\ a-c \leq 0 \wedge b-c \leq 0 $$

which we'll represent by a matrix $A$ and a vector $b$

$$ A= \begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & -1 \end{bmatrix} $$ $$ b= \begin{bmatrix} 0 & 0 \end{bmatrix} $$ where each column index in $A$ represents each variable of $a, b, c$, and we can now easily compute and solve for some optimization problem using all kinds of solvers.

## Question

In the general case, a propositional logic formula is converted into many mathematical constraints. For some cases, the formula could be converted into just one constraint. For example, $a \wedge (b \lor c)$ can be represented in one line as $-2a - b - c \leq -3$ whereas $(a \wedge b) \lor c$ cannot be represented by one constraint.

**Is there a method for determine if a formula can be represented as one constraint or not? And in the best case, is there even a method for converting into that one constraint if it exists or many otherwise?**

# Answer
Functions which can be described using a single constraint are known as *halfspaces* or *linear threshold functions*. They are also the functions computable using a single *threshold gate*.

Checking whether a function of this form exists is a linear programming problem: you look for a set of weights $w\_1,\ldots,w\_n,C$ such that if $f(x\_1,\ldots,x\_n) = 1$ then $$ \sum\_i w\_i x\_i \geq C + 1, $$ and if $f(x\_1,\ldots,x\_n) = -1$ then $$ \sum\_i w\_i x\_i \leq C - 1. $$

More efficient algorithms exist. For example, Maass and Turán gave a famous such algorithm in their paper "How fast can a threshold gate learn?".
> 2 votes

---
Tags: optimization, integer-programming, propositional-logic
---


# Question
Title: Unambiguous context-free grammar for strings with at least as many a's as b's
I have designed this Grammar but it is ambiguous:

$$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$

Would anyone help me make it unambiguous? Assume the alphabet is $\\{a,b\\}$.

# Answer
Let us replace $a$ with $\nearrow$ and $b$ with $\searrow$. Given a sequence of arrows, we construct a "walk" in which each arrow's tail starts from the preceding arrow's head. We keep track of the height. You are interested in walks which end up at or above the starting height.

Given such a walk $w = w\_1 \ldots w\_n$, let $i \in \\{0,\ldots,n\\}$ be the last position at which the walk reaches the starting height, and write $w = (w\_1 \ldots w\_i) (w\_{i+1} \ldots w\_n) =: xy$. The first part $x$ is a sequence with an equal number of $\nearrow$ and $\searrow$. The second part $y$ is either empty, or of the form $y = \nearrow z$, where $z$ is a walk that never dips below the starting height.

Let us start with $x$. We can partition $x$ into subwords $x\_1 \ldots x\_\ell$, breaking $x$ at each point in which the walk reaches the starting height. Each $x\_i$ is of one of the following forms: $\nearrow U \searrow$, where $U$ is a walk that never dips below the starting height and returns to the origin, and $\searrow D \nearrow$, where $D$ is a walk that never exceeds the starting height and returns to the origin.

A walk of type $U$ is either empty, or must be of the form $\nearrow U \searrow U$, and similarly for a walk of type $D$. We can therefore express the $x$ part of our overall walk using the rules: \begin{align} &X \to \nearrow U \searrow X \mid \searrow D \nearrow X \mid \epsilon \\ &U \to \nearrow U \searrow U \mid \epsilon \\ &D \to \searrow D \nearrow D \mid \epsilon \end{align}

Now let's tackle the $z$ part, which is a walk that never dips below the starting height. Either $z$ ends up at the starting height, in which case it is of type $U$, or it is of the form $U \nearrow z'$, where $z'$ satisfies the exact same constraints. In other words, the $y$ part is just $(\nearrow U)^\*$. In total, we get the grammar \begin{align} &S \to S \nearrow U \mid X \\ &X \to \nearrow U \searrow X \mid \searrow D \nearrow X \mid \epsilon \\ &U \to \nearrow U \searrow U \mid \epsilon \\ &D \to \searrow D \nearrow D \mid \epsilon \end{align}
> 3 votes

# Answer
Here is an unambiguous grammar for strings with at least as many $a$'s as $b$'s. $\def\L#1{{\mathcal L(#1)}}$

$$\begin{align} S&\to EM\mid E\\ M&\to aDM\mid aD\\ E&\to aBE\mid bAE\mid\epsilon\\ D&\to aBD\mid\epsilon\\ B&\to b\mid aBB\\ A&\to a\mid bAA\\ \end{align}$$

The following table should help us understand the strings generated by each non-terminal.

$$ \text{number of $a$'s minus number of $b$'s} $$

\begin{array}{|c|c|} \hline &\text{in the whole string} & \text{in every proper prefix}\\\hline A&1& \lt 1\\\hline B&-1&\gt -1\\\hline D&0&\ge0\\\hline E&0&\text{no restriction}\\\hline M&\gt0&\gt0\\\hline S&\ge0&\text{no restriciton}\\\hline \end{array}

---

**Some notations**. For all string $w$, let $d(w)=|w|\_a-|w|\_b$, i.e., the number of $a$'s minus the number of $b$'s. Define $d\_w:\\{1,\cdots, |w|-1\\}\to \mathbb N$, $w(i)=d(p\_i(w))$, where $p\_i(w)$ is the proper prefix of $w$ of length $i$. For example, for $w=abb$, $$\begin{align}d\_w(1)&=d(a)=1 - 0=1,\\ d\_w(2)&=d(ab)=1-1=0.\end{align}$$

Given a string $w$ and one of its prefixes $p$, let $w-p$ denote $w$ with $p$ removed, i.e. $w = p(w-p)$.

**Continuity Lemma.** $d(\cdot)$ is continuous in the sense that $d(w)$ changes at most by 1 if $w$ is extended or shrunk by one terminal. $d\_w(\cdot)$ is continuous in the sense that $d\_w(i)$ changes at most by 1 if $i$ becomes one less or bigger. So we have "intermediate value theorem" for $d(\cdot)$ and $d\_w(\cdot)$.

**Linearity Lemma.** Given two strings $p$ and $w$, we have $$\begin{align}|w-p|&=|w|-|p|,\\ d\_{w-p}(i) &= d\_{w}(|p| +i) - d(|p|),\color{#d0d0d0}{\text{ for } i=1,2,\cdots, |w|-1} \end{align}$$ **Proof.** By definition. $\blacksquare$

**Proposition AB.** We have two equivalences, $$\begin{align} w\in \L A &\iff d(w) =1\text{ and } d\_w \lt 1,\\ w\in \L B &\iff d(w) =-1\text{ and } d\_w \gt -1. \end{align}$$ **Proof**: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=1$ are immediate to verify. Suppose $w$ is of greater length.

* $d(w) =1\text{ and } d\_w \lt 1$. Since $d\_w(1)\lt 1$, $w$ starts with $b$, i.e, the first value of $d\_w$ is $d(b)=-1$. Since $d(w)=1$, $d(p)=0$ for some proper prefix $p$ of $w$. Let $b\mu$ be the shortest such prefix. Since $d\_\mu \< 1$, $d(\mu)=d(b\mu)-d(b)=1$, and $\mu$ is shorter than $w$, we have $\mu\in \L A$ by induction hypothesis.

Since $d\_w\lt 1$ and $d(a\mu)=0$, $d\_{w-b\mu} \lt 1$. Also note $d(w-b\mu)=1-0=1$. Since $w-b\mu$ is shorter than $w$, $w-b\mu\in\L A$ by induction hypothesis. So $w=b\mu(w-b\mu)$ can be generated from $A\to bAA$.
* $d(w) = -1\text{ and } d\_w \gt -1$. This case is the same as the case above, but with $-1$ and $1$ switched, $\>$ and $\<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w$ can be generated from $B\to aBB$. $\blacksquare$

**Proposition DE.** We have two equivalences, $$\begin{align} w\in \L D &\iff d(w)=0\text{ and } d\_w \gt 0,\\ w\in \L E &\iff d(w)=0. \end{align}$$

**Proof**: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=0$ are immediate to verify. Suppose $w$ is of greater length.

* $d(w)=0$ and $d\_w\>0$. Since $d\_w(1)\>0$, $w$ starts with $a$. Let $a\mu$ be the shortest non-empty prefix with $d(a\mu)=0$. Then $d(\mu)=-1$ and $d\_{\mu}\gt0$, which means $\mu\in\mathcal L(aB)$. Since $d(a\mu)=0$, have $d\_{w-a\mu}\gt0$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\L D$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in D$.
* $d(w)=0$.
    + $w$ starts with $a$. Let $a\mu$ be the shortest prefix of $w$ such that $d(a\mu)=0$. Then $d(\mu)=-1$ and $d\_\mu \> -1$, which means $\mu\in \L B$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\mathcal L(E)$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in E$.
    + $w$ starts with $b$. This case is the same as the case above, but with $-1$ and $1$ switched, $\>$ and $\<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w\in E$. $\blacksquare$

**Proposition M.** $w\in \L M \iff d\_w \ge 1$.
**Proof.** The "$\Rightarrow$" direction is implied by the proposition above immediately since $M$ becomes multiple $aD$'s.
To prove the "$\Leftarrow$" direction, suppose $d\_w\ge1$. Note that $w$ starts with $a$. Let $p$ be the longest prefix of $w$ such that $d(p)=1$, which implies $d\_{w-p}\ge1$. Since we also have $d\_p\ge1$, $p\in\L U$. If $p=w$, $w$ can be generated from $M\to U$. Otherwise, since $w-p$ has the same restriction as $w$, $w$ can be generated from $M\to UM$. $\blacksquare$.

**Proposition S.** $w\in \L S \iff d(w) \ge 0.$
**Proof.** The "$\Rightarrow$" direction is implied by proposition E and proposition M immediately.
To prove the "$\Leftarrow$" direction, consider a string $w$ with $d(w)\ge0$. If $d(w)=0$, then $\mu\in\L E$. Otherwise, $d(w)\>0$. Let $p$ be the longest prefix of $w$ such that $d(p)=0$. Then $p\in\mathcal L(E)$. Consider $w-p$. We must have $d\_{w-p}\ge 1$; otherwise, we can extend $p$. So $w-p\in \mathcal L(M)$. $w=p(w-p)$ can be generated by $S\to EM$. $\blacksquare$

**Proposition unambiguity**. The grammar is unambiguous.
**Proof.** Given the propositions above that characterize each language involved numerically, it is relative easy to prove as the following.

* Let $s\in\L S$.
    + $d(s)=0$. Then $s$ has to be parsed by $S\to E$.
    + $d(s)\gt 0$. Then $s$ has to be parsed by $S\to EM$. Suppose $s=e\_1m\_1=e\_2m\_2$, where $e\_1,e\_2\in\L E$ and $m\_1, m\_2\in\L M$. Since $d\_{m\_1}\>0$, if $m\_2$ is a proper suffix of $m\_1$, i.e., $m\_1-m\_2$ is a proper prefix of $m\_1$, we would have $d(m\_1-m\_2)\>0$, which contradicts with $d(m\_1-m\_2)=d(m\_1)-d(m\_2)=(d(s)-d(e\_1))-(d(s)-d(e\_2))=0$. This contradiction means $m\_1$ cannot be a proper suffix of $m\_1$. By symmetry, $m\_2$ cannot be a proper suffix of $m\_1$, either. Hence, $m\_1=m\_2$ and $e\_1=e\_2$.
* Let $m\in\L M$.
    + $\min d\_m=1$. Then $m$ has to be parsed by $M\to aD$.
    + $\min d\_m\>1$. Then $m$ has to be parsed by $M\to aDM$. Suppose $m=ad\_1m\_1=ad\_2m\_2$, where $d\_1,d\_2\in\L D$ and $m\_1, m\_2\in\L M$. Since $d\_{m\_1}\>0$, if $m\_2$ is a proper suffix of $m\_1$, i.e., $m\_1-m\_2$ is a proper prefix of $m\_1$, we would have $d(m\_1-m\_2)\>0$, which contradicts with $d(m\_1-m\_2)=d(m\_1)-d(m\_2)=(d(s)-d(ad\_1))-(d(s)-d(ad\_2))=0$. This contradiction means $m\_1$ cannot be a proper suffix of $m\_1$. By symmetry, $m\_2$ cannot be a proper suffix of $m\_1$, either. Hence, $d\_1=d\_2$ and $m\_1=m\_2$.
* Let $e\in\L E$.
    + $|e|=0$. Then $e$ has to be parsed by $E\to \epsilon$.
    + $|e|\>0$.
        - $e$ starts with $a$. Then $e$ has to be parsed by $E\to aBE$. Suppose $e=ab\_1e\_1=ab\_2e\_2$, where $b\_1,b\_2\in\L B$ and $e\_1, e\_2\in\L E$. Since $d\_{b\_1}\>-1$ and $d(b\_2)=-1$, $b\_2$ cannot be a proper prefix of $b\_1$. By symmetry, $b\_1$ cannot be a proper prefix of $b\_2$, either. Hence, $b\_1=b\_2$ and $e\_1=e\_2$.
        - $e$ starts with $b$. This case is symmetric to the case above.
* Let $w\in\L D$.
    + $|w|=0$. Then $w$ has to be parsed by $D\to \epsilon$.
    + $|w|\>0$. Then $w$ has to be parsed by $D\to aBD$. Suppose $w=ab\_1q\_1=ab\_2q\_2$, where $b\_1,b\_2\in\L B$ and $d\_1, d\_2\in\L D$. Since $d\_{b\_1}\>-1$ and $d(b\_2)=-1$, $b\_2$ cannot be a proper prefix of $b\_1$. By symmetry, $b\_1$ cannot be a proper prefix of $b\_2$, either. Hence, $b\_1=b\_2$ and $d\_1=d\_2$.
* Let $w\in\L B$.
    + $|w|=1$. Then $w$ has to be parsed by $B\to b$.
    + $|w|\>1$. Then $w$ has to be parsed by $B\to aBB$. Suppose $w=ab\_1b\_3=ab\_2b\_4$, where $b\_1,b\_2,b\_3,b\_4\in\L B$. Since $d\_{b\_1}\>-1$ and $d(b\_2)=-1$, $b\_2$ cannot be a proper prefix of $b\_1$. By symmetry, $b\_1$ cannot be a proper prefix of $b\_2$, either. Hence, $b\_1=b\_2$ and $b\_3=b\_4$.
* Let $w\in\L A$. This case is symmetric to the case above. $\blacksquare$

---

Here is a simpler unambiguous grammar given by Yuval. $$\begin{align} S&\to SaU \mid X\\ X&\to aUbX\mid bDaX\mid\epsilon\\ D&\to bDaD\mid\epsilon\\ U&\to aUbU\mid\epsilon\\ \end{align}$$

Here is the numerical characterization for the language generated by each terminal. Check his answer for visual explanations. $$ \text{number of $a$'s minus number of $b$'s} $$ \begin{array}{|c|c|} \hline &\text{in the whole string} & \text{in every proper prefix}\\\hline S&\ge0&\text{no restriciton}\\\hline X&0&\text{no restriciton}\\\hline U&0&\ge0\\\hline D&0&\le0\\\hline \end{array}
> 2 votes

---
Tags: context-free, formal-grammars, counting, ambiguity
---


# Question
Title: Convert ((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) to MathJax?
I need help coverting these two question to Math Jax ((50^A)\*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) and (((50^A)(50^B)(50^C))/(4^2)) + (((50^A)(50^B))/(4^2))+((50^A)/(4))+(1/4) I don't know how to do it, for a mathstack exchange question.

# Answer
> 2 votes
Probably you should ask questions about how to ask on MathStack on their meta site! Each site on Stack Exchange has a Meta site to ask questions about asking questions! They even have a tutorial there: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

However, learning how to typeset mathematics is something Computer Science students and researchers have to learn how to do, so perhaps it could be considered just about on-topic!

MathJax is based on LaTeX which is a page description language used for writing documents which happens to be quite good at writing maths. LaTeX (created by Leslie Lamport) was built upon TeX which was created by Donald Knuth. Both Computer Scientists.

The simplest way of using MathJax is to just use the dollar symbol `$` to quote or surround your formula. If we take your first formula:

```
((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)

```

Put it with the dollars, we get:

```
$((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

```

which displays this:

$((50^A)\*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

Now perhaps you want that to be a bit neater. They you can replace the slashes by some better arrangement and make them fractions. In MathJax w can invoke layout function by using the backslash `\` to indicate a layout function name and give its arguments within curly braces `{}`. We want the `\frac` function like this:

```
$\frac{((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

```

$\frac{((50^A)\*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

We can do that again for each fraction:

```
$\frac{((50^A)*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

```

$\frac{((50^A)\*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

Which can be tidied up further, but that gives you the basics!

---
Tags: mathematical-programming
---


# Question
Title: Approximation algorithm question, clustering on n points
So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the encapsulated points from this max ball we found, then iterate through all the points again. Continue until there are no longer any points not encapsulated. Return all the centers we found.

I'm not sure if this algorithm is correct. O(1) approximation algorithm is in terms of O( $\frac{\Delta\_{ours}}{\Delta}$). The requirement is a polynomial algorithm, which I believe mine is in the order of $n^{2}$.

I'm also not sure how to prove the correctness of an approximation algorithm either.

# Answer
> 1 votes
There's an even simpler algorithm, the greedy algorithm. This algorithm iterates through the points in some order. Initially the set of centers is empty. When point $p$ is reached, if $p$ is within distance $2\Delta$ of one of the selected centers, then we do nothing. Otherwise, we add $p$ to the set of centers. Naive implementation of this algorithm runs in time $O(kn)$, which is polynomial.

Why does this work? Suppose that balls at radius $\Delta$ centered at the points $p\_{i\_1},\ldots,p\_{i\_k}$ cover the entire set, and suppose that the algorithm above has selected points $p\_{j\_1},\ldots,p\_{j\_k}$. We have to show that every point in the set is within distance $2\Delta$ of these points.

For a point $p$, let $c(p)$ denote the point among $p\_{i\_1},\ldots,p\_{i\_k}$ which is closest to $p$. I claim that $c(p\_{j\_a}) \neq c(p\_{j\_b})$ for $a \neq b$. Indeed, by construction $\\|p\_{j\_a}-p\_{j\_b}\\| \> 2\Delta$. But if $c(p\_{j\_a}) = c(p\_{j\_b}) = q$, then $\\|p\_{j\_a}-p\_{j\_b}\\| \leq \\|p\_{j\_a}-q\\| + \\|q-p\_{j\_b}\\| \leq 2\Delta$.

Renumber the points so that $c(p\_{j\_a}) = p\_{i\_a}$, and consider an arbitrary point $p$ in the set. Suppose that $c(p) = p\_{i\_a}$. Then $\\|p-p\_{j\_a}\\| \leq \\|p-p\_{i\_a}\\| + \\|p\_{i\_a}-p\_{j\_a}\\| \leq 2\Delta$.

---
Tags: algorithms, approximation, correctness-proof
---


title: Reduction from $HALT$ to $A_{TM}$

text:
# Question
Title: Reduction from $HALT$ to $A_{TM}$
I know the reduction to from $A\_{TM}$ to $HALT$. But is the following reduction **from** $HALT$ to $A\_{TM}$ correct?

We are looking for total computable function $f$ mapping from $HALT$ to $A\_{TM}$. The following TM $F$ calculates the reduction $f$.

```
F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

```

I think the line `if T accepts or rejects, *accept*` is correct, but it would be great if someone could check this.

Edit: I found the following slides, but I don't think the construction in there is correct: http://slideplayer.com/slide/13791105/

# Answer
There are multiple notions of "reduction." You've correctly described a **many-one reduction** of $HALT$ to $A\_{TM}$. The reduction you've linked to (with the proof on slide 24 of the deck you linked) is instead a **truth-table reduction**. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of **Turing reduction**.

While many-one reductions are generally the default notion in complexity theory, Turing reductions and the resulting degree structure are the default in computability theory. Note that if all I want to do is prove the undecidability of some set, a Turing reduction from some known-to-be-undecidable set is sufficient.

---

First, let's explicitly recall the definitions of the languages involved:

* $A\_{TM}=\\{\langle M,w\rangle: M$ halts and accepts on input $w\\}$.
* $HALT=\\{\langle M,w\rangle: M$ halts on input $w\\}$.

Your proposed reduction of $HALT$ to $A\_{TM}$ is **correct**: given $M$, we can computably build a new machine $\hat{M}$ which accepts precisely those strings on which $M$ halts. (Basically, just replace all the "reject" states in $M$ by "accept" states.)

---

Now let's look at the other reduction which you linked to (the aforementioned slide 24, reproduced below).

> ## Example reduction
>
> * Deciding $HALT$ using a procedure that decides $A\_{TM}$ (“reducing $HALT$ to $A\_{TM}$”)
>     + On input $\left\<M, w\right\>$
>     + Check if $\left\<M, w\right\>\in A\_{TM}$
>         - if yes, the\[n\] $M$ halts on w; **ACCEPT**
>         - if no, then $M$ either rejects *w* or it loops \[o\]n $w$
>     + construct $M'$ by swapping $q\_{accept}$/$q\_{reject}$ in $M$
>     + check if $\left\<M', w\right\>\in A\_{TM}$
>         - if yes, then $M'$ accepts $w$, so $M$ rejects $w$; **ACCEPT**
>         - if no, then $M$ neither accepts nor rejects $w$; **REJECT**

Basically, rather than going to "all halting states accept" the linked argument considers separately:

* the original machine, and
* the "contrary" machine which accepts exactly when the original one rejects and vice-versa.

An affirmative answer for either case in $A\_{TM}$ ensures an affirmative answer for the original machine in $HALT$.

Off the top of my head I see no reason to do this rather than follow your argument, especially because it yields a weaker result, but it is correct and is enough to prove the broader claim in the slides, namely that $A\_{TM}$ is undecidable.
> 2 votes

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


# Question
Title: building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas
Here's the question:

> Assume there exists a polynomial time machine $M$ that receives two formulas $\varphi\_1,\varphi\_2$ and satisfies the following:
>
> * If $\varphi\_1 \in \mathrm{SAT}$ and $\varphi\_2 \notin \mathrm{SAT}$, then $M(\varphi\_1,\varphi\_2)=1$
> * If $\varphi\_1 \notin \mathrm{SAT}$ and $\varphi\_2 \in \mathrm{SAT}$, then $M(\varphi\_1,\varphi\_2)=0$
>
> Show that there also exists a polynomial time algorithm for SAT.
>
> Note that we have no guarantee for the output of $M(\varphi\_1,\varphi\_2)$ whenever $\varphi\_1,\varphi\_2$ are both satisfiable (or when both are not).

Can I get any hint on how to start the solution?

# Answer
Here is something your oracle can do: if you are given two formulas $\alpha,\beta$, and are guaranteed that at least one of them is satisfiable, then you can find one of them which is satisfiable by calling $M(\alpha,\beta)$: if $M(\alpha,\beta) = 1$ then $\alpha$ is satisfiable, and if $M(\alpha,\beta) = 0$ then $\beta$ is satisfiable.

Given a satisfiable formula $\varphi$ over $x\_1,\ldots,x\_n$, you can use this to find a satisfying assignment, variable by variable: at each step, you consider assigning the variable the two possible truth values, and use the method described above to find an assignment under which the formula is still satisfiable. Finally, you can check whether the supposed satisfying assignment indeed satisfies $\varphi$. If so, $\varphi$ is satisfiable. Otherwise, it isn't.
> 1 votes

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


# Question
Title: how to construct a formula with an opposite SAT value of another one
given a formula S (that is built of binary variables and "or", "not", "and" gates). IS there a polynomial algorithim that builds S' that satisfies:
S' satisfied if and only if S doesn't satisfied.
which means: S' is in SAT if and only if S not in SAT

# Answer
The existence of such an algorithm would imply co-NP is included in NP which is unlikely

*Checking that a formula is satisfiable: NP, generate proof by providing a solution*

*Checking that a formula is unsafisfiable: co-NP, generating proof can be harder, in classical proof systems the shortest proof of unsatisfiability of an arbitrary formula can be exponentially long*

The algorithm you are looking for would mean all problems in co-NP have a short refutation, by providing a solution to the "opposite" formula. Therefore we are unaware of the existence of such an algorithm.
> 9 votes

# Answer
yet we can't determined such a thing due to the fact that SAT is NP-hard and the "UNSAT" is co-Np-hard.
> 1 votes

# Answer
There can't be such a polynomial-time algorithm that reliably inverts satisfiability unless P = NP.

If S is satisfiable, you can only make it unsatisfiable by adding constraints. If S is unsatisfiable, you can only make it satisfiable by removing constraints. By the law of the excluded middle S must be satisfiable or unsatisfiable, which means your algorithm must either add or remove constraints, which means that you must be able to determine whether S is satisfiable or unsatisfiable in polynomial time before you can decide what changes to make. That is, you must have a polynomial-time algorithm that decides Boolean satisfiability as a necessary first step.
> -1 votes

---
Tags: complexity-theory, logic
---


# Question
Title: Independent Set Problem Variant, Induction
So the question gives us some mysterious algorithm, that given a graph G and an integer k, it outputs true/false to whether there is an independent set of size k in G.

So we have to design an algorithm that can call this mysterious algorithm within a polynomial number of times, to return an independent set of size k from G if it exists, or outputs impossible. The hint is induction.

I'm having trouble figuring an algorithm to solve this. I know however, that the proof for this algorithm involves removing or adding a vertex in the inductive step.

# Answer
> 2 votes
Hint: Suppose you have a graph $G = (V,E)$ which is *yes*, and then there is a vertex $v \in V$ such that $G - v$ (the graph where you have removed $v$ from the graph) is *no*. What can you say about $v$ and $G$?

Let us take an example, namely the following graph:

$G= (\\{a,b,c,d\\}, E=\\{ab, bc, cd, ad, ac\\})$

```
a —— d
| \  |
|  \ |
b —— c

```

and with $k=2$. This is currently a *yes* instance.

First we ask: If we delete $a$ from $G$, will the resulting instance still be a *yes* instance?

```
     d
     |
     |
b —— c

```

The answer is *yes*, this graph is still a *yes* instance.

Then we delete $b$ and ask the same question:

```
     d
     |
     |
     c

```

The answer is now *no*, this instance is no longer a *yes* instance. Hence we cannot delete $b$. Instead we try to delete $c$:

```
     d

b

```

The answer is *still yes*, and $|V(G')| = k$, so we conclude that $\\{b, d\\}$ is an independent set in $G$ of size $k$.

---
Tags: algorithms, graphs
---


title: ODEs and Zeno Machines

text:
# Question
Title: ODEs and Zeno Machines
Disclaimer: I know nothing about differential equations, and I don't know if this belongs here...

Wikipedia states that a Zeno machine is a hypothetical machine able to compute infinite steps in finite time, by making use of supertasks. Building such a machine is physically impossible. My question is this: Is the Zeno machine an example of an differential equation and if so, is my assumption correct that we can utilize a differential equation solver to solve the Zeno machine differential.equation, like in this paper, which shows a different but fundamentally the same concept?

# Answer
> 1 votes
**No**, they are not the same.

There are different equivalent representations for any problem (e.g. Turing machines, neural networks, differential equations, ...). But changing from one representation to another does not change whether the problem is fundamentally solvable - otherwise they would not constitute equivalent representations.

Zeno machines can be considered as Turing machines plus hypercomputation which, if it were possible, would permit solving certain previously undecidable problems.

Differential equations can be seen as extension of algebraic equations (or, conversely: an algebraic equation is a differential equation where no derivatives appear).

However, those two types of extensions are independent of each other:

1. There exist differential equations which are solvable by Turing machines.
2. There exist differential equations which are not solvable by Zeno machines.

If what made Zeno machines different from Turing machines was that only Zeno machines could represent differential equations, then there could be no Turing machines which can solve for differential equations.

But if you search for "differential equation solver" you get a lot of results: there exist programs which can solve certain differential equations. So a Zeno machine is not necessary for solving differential equations. Therefore Zeno machines and differential equations cannot be the same.

You can interpret the computations of a Zeno machine as a differential equation only insofar as you can already interpret the computations of a Turing machine as a differential equation. So neither do differential equations tell you anything about Zeno machines nor do Zeno machines tell you anything about differential equations.

---
Tags: turing-machines, computability
---


# Question
Title: What is the time complexity Big-O of this algorithm?
What is the time complexity Big-O of this algorithm?

, The first assumption it's O(N * lg N) but it is not correct, why?

```
        count = 0
        for i = N : 1 {
            for j = 0 : i {
                count = count + 1
                j =  j + 1
            }
            i = i/2
        }
        print(count)

```

# Answer
> 4 votes
The second for-loop while be executed `N + N/2 + N/4 +....+ N/N`

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of `N + N/2 + N/4 +....+ N/N` will be `O(N)`

# Answer
> 3 votes
The runtime for this algorithm is $\Theta(n)$.

By rewriting the iterative formula as a recurrence relation $T(n)=T\left(\frac{n}{2}\right) + n$ we can use Master Theorem to analyze the runtime. The recursive equation doesn't meet the criteria for the first or second cases but it does meet those for the third, meaning $T(n)=\Theta(f(n))$ where $f(n)$ is the amount of work done at each iterative level of the algorithm; in this case $f(n)=\Theta(n)$ and so $T(n)=\Theta(n)$.

# Answer
> 1 votes
*\*Cough\** Nice homew... Ahem

It's O(N\*log(N)) because the outer loop runs log(N) times (i from N to 1, dividing by 2 each time) and the inner loop runs i times (so N times the first time for example, then less).

# Answer
> 1 votes
there is two loops .. the inner loop over O(N) numbers(0 to i at most i=N) and the outer one starts the loop from N and slice it by two in each iteration (N -\> N/2 -\> N/4 ..) therefore the big-O of the algorithm is **O(Log(N)\*N)**.

# Answer
> 0 votes
A more practical approach:

The most executed statements in this example is the ones inside the innermost loop, for example

```
count = count + 1

```

This statement counts how many times it is executed, which means that the total runtime is approximately proportional to the output.

So, try to run this program with various inputs and see what the output is. I don't know this language, so I don't know the exact semantics, but it seems that the approximate count is $2N$.

Knowing this answer should put you on the right track to finding out why.

# Answer
> 0 votes
When the value of i is N, the inner loop will run N times

Then, the value of i becomes N/2, so the inner loop will run N/2 times

then, the value of i becomes (N/2)/2, so the inner loop will run N/4 times

This continues till the value of i becomes 1, so the total time complexity is : $$N + N/2 + N/4 + N/8 + ....... + 1$$

**Or** $$1 + 2 + 4 + 8 + 16 + ..... N/2 + N$$

Total number of terms in this is t= $$log2(N)$$ **ignore lower terms(constants) in the calculations below(for the sake of Big O Notation):**

summing up we get $$2^t-1 = log(N)$$ Thus, time complexity is O(N)

# Answer
> 0 votes
Forget about the outer loop. Just remember that on it's way from $N$ to 1, $i$ gets divided by $2$ on each iteration.

Now, on the first iteration **of the second loop**, $j$ will go from $0$ to $N$, and so we will have $N-0+1 = N+1$ steps. On the second iteration, $j$ will go from $0$ to $\frac N2$, so we will have $\frac N2 + 1$ iterations. You can see how this evolves: $(N + 1) + (\frac N2 + 1) + (\frac N4 + 1) + \dots + 2.$

For simplicity, let's remove the $1$'s from each term because their effect on $N$ is insignificant as $N \rightarrow \infty$.

Now, all you have to do is sum up $S = N + \frac N2 + \frac N4 + \dots + 1$.

Factorizing $N$ gives $S = N(1 + \frac 12 + \frac 14 + \dots +\frac {1}{2^n}) = N \sum\_{k=0}^{n} (\frac 12)^k$.

The result of the sum (using the formula of a finite geometric series) is $2(1-(\frac 12)^{N+1})$. As $N\rightarrow \infty$, this sum tends to $2(1-0) = 2$.

Finally, we have that $T(N) = \Theta(2N) = \Theta(N)$.

---
Tags: algorithms, time-complexity, algorithm-analysis, big-o-notation
---


title: Compare two atan2

text:
# Question
Title: Compare two atan2
I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple concentric points on some step I get a pencil of radius vectors origins from the center of a circle. I need to sort them by angle (or at least to find minmax elements). I use the next formula to compare raduis vectors $\mathbf{v\_i} = (x\_i, \\;y\_i)$ and $\mathbf{v\_j} = (x\_j, \\;y\_j)$:

$$ atan2(y\_i, \\;x\_i) \< atan2(y\_j, \\;x\_j) $$

I sure result can be achieved avoiding trigonometric functions. Can it be expressed without comparisons?

Currently I can sort them by quadrants, if both points are in the same quadrant, then I just look at cross product sign, otherwise I compare quadrant numbers.

PS: can someone create `point-location` tag?

# Answer
The following answer is based on the following graph, taken from Wikipedia:

If $x\_i,x\_j \> 0$ then you can use the monotonicity of the arctangent to get the equivalent condition $y\_i/x\_i \< y\_j/x\_j$, or $y\_ix\_j \< y\_jx\_i$.

If $x\_i \< 0$ and $x\_j \> 0$ then the answer depends only on the sign of $y\_i$, and if $x\_i \> 0$ and $x\_j \< 0$ then the answer depends only on the sign of $y\_j$.

If $x\_i,x\_j \< 0$ and $y\_i,y\_j$ have different signs, then again the answer depends only on the sign of $y\_i$. If $y\_i,y\_j$ have the same sign, then once again you can use monotonicity.

---

It is a good guess that the answer depends only on the sign of the determinant $$ \begin{vmatrix} x\_i & y\_i \\ x\_j & y\_j \end{vmatrix} = x\_i y\_j - x\_j y\_i.$$
> 2 votes

# Answer
Just to summarize the answer above as a computer programme (the determinant method does not work):

```
def atan2_lt( a, b, c, d ):
    """
    Test atan2(a,b) < atan2(c,d) without computing either.
    """
    if b*d < 0: return a < 0 if b < 0 else c > 0
    elif b > 0 or a*c > 0: return a*d < b*c
    else: return a < 0 and c > 0

```

**Edit:** the above does not handle edge cases where a, b, c, or d is 0. I need to refine this.
> 1 votes

---
Tags: computational-geometry, comparison, voronoi-diagrams
---


title: Big theta notation

text:
# Question
Title: Big theta notation
I'm trying to figure out the following problem:

> If algorithm $A$ has a big theta notation of $n^3$ and algorithm $B$ has a big theta notation of $n^2$, there might be an infinite number of inputs for which $A$ has a lower running time than $B$. Is the statement correct?

My guess is that it's not correct, because big theta notation is bounded from both sides, therefore $n^3$ can't be faster than $n^2$ for any input.

Is my theory correct?

Thanks

# Answer
> 2 votes
The answer depends on what you mean exactly by "an algorithm has a big-theta notation". Asymptotic notations is used to denote set of functions, not algorithms. It is important to know what function you are talking about.

If given an algorithm $Alg$, you denote by $f\_{Alg}(n)$ the maximum running time of $Alg$ among all inputs of size $n$, your statement is false. Let $B$ be an algorithm that just executes an empty loop for $n^3$ iterations. Let $A$ be an algorithm that checks whether the first bit of the input is even or odd. If it is even, it executes an empty loop for $n^2$ iterations. If it is odd, it terminates immediately. According to the above choices, $f\_A(n) = \Theta(n^3)$, and $f\_B(n) = \Theta(n^2)$, yet there are infinite inputs for which $A$ runs faster than $B$ (i.e., essentially all input strings with an odd bit).

In this sense saying that $f\_{Alg}(n) = \Omega(g(n))$ means that there is a constant $c\>0$ such that, for every sufficiently large $n$, there is **at least one input** of size $n$ such that $f\_{Alg}(n) \ge c g(n)$. With this interpretation you cannot say that an algorithm $X$ that takes $2^n$ time on inputs of even even length and $n$ time on inputs of odd length, has a time complexity of $\Omega(2^n)$.

That said, sometimes $f\_{Alg}(n) = \Omega(g(n))$ is used in the following weaker sense: there is a constant $c\>0$ such that, for every sufficiently large $n$, there is **at least one input** of size $n' \ge n$ such that $f\_{Alg}(n') \ge c g(n')$. In this sense you would say that $X$ has time complexity of $\Omega(2^n)$.

Less commonly, $f\_{Alg}(n) = \Omega(g(n))$ is used in the following stronger sense: for every sufficiently large $n$, and **for every input** of size $n$, $f\_{Alg}(n) \ge c g(n)$. In this sense, $f\_A$ as defined above would not even belong to $\Omega(n^3)$. This notion is not really useful, since it is often very easy to design algorithms for which the best lower-bound on their running time according to the above interpretation is $\Omega(n)$ (by checking if the input belongs to some class of inputs for which the solution is trivially known).

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


# Question
Title: More Information about the Question Answering System called LUKE
LUKE is a new state-of-art in question answering system and after googled keywords LUKE Studio Ousia NAIST and RIKEN AIP (I suppose LUKE is a colaboration between several research centers) I couldn't find any information.

LUKE is mentioned in the following pages:

https://paperswithcode.com/sota/question-answering-on-squad11.

https://sheng-z.github.io/ReCoRD-explorer/.

Is there here anyone with insider information able to explain LUKE?

# Answer
Check this out. This might be the paper

https://www.researchgate.net/project/LUKE-Project

https://www.researchgate.net/publication/340461536\_Global\_Entity\_Disambiguation\_with\_Pretrained\_Contextualized\_Embeddings\_of\_Words\_and\_Entities
> 1 votes

---
Tags: natural-language-processing
---