title: Complexity of Nelder-Mead Algorithms

text:
# Question
Title: Complexity of Nelder-Mead Algorithms
If the objective function contains $n$ variables (e.g. $f(x\_1, ..., x\_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the algorithm needs to evaluate $f$ to achieve the desired value by precision $\epsilon$?

For instance, suppose $f(x\_1,x\_2) = \text{Tr}(x\_1x\_2)$ is defined on $2$-dimensional parameters $(x\_1,x\_2) \in R^2$, where $-1 \leq x\_1, x\_2 \leq 1$. Starting from random sets of parameters of $v = (v\_1, v\_2), w = (w\_1, w\_2), y = (y\_1, y\_2)$, the Nelder-Mead algorithm starts from a triangle in 2D and evaluate $f(v), f(w), f(y)$ and either reflect/expand/contract/shrink, and repeat the procedure until it converges to desired values of $|f\_{target} - f| \leqslant \epsilon$. Is there theoretical bounds on how many times the algorithm evaluate $f$ until the convergence is taken?

# Answer
> 1 votes
There are no guarantees. In the worst case, if the function $f$ is particularly unfriendly, any optimization algorithm might need to evaluate $f$ on every possible combination of values, to find the optimum. (Consider a function $f$ that is zero on all points except for a single point, where it is very large or very small.) So, in effect, there are no bounds on the number of evaluations of $f$ needed.

With some optimization algorithms, one can obtain some bounds if we have additional conditions on $f$ (e.g., that it is Lipschitz), but my sense is that these bounds are typically not terribly useful in practice.

---
Tags: complexity-theory, optimization, search-algorithms
---


# Question
Title: Does a path exist going through each color only once?
I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once.

I think this problem can be formulated using network flow. Somehow a penalty can be placed on nodes of the same color that makes the flow 0 or infinity if a node is repeated.

Thanks!

# Answer
> 3 votes
I understand from your question that you are asking for a polynomial-time algorithm for solving the problem. It is unlikely there is one for the problem.

Taking the hint of @jjohn, this is exactly the same problem as in the Kleinberg-Tardos book, Exercise 8.12. They call the problem *evasive path*. Here, color classes represent different zones, and you must get from $s$ to $t$ visiting each zone at most once.

There are at least two straightforward reductions. The other one is from directed Hamiltonian path, and the other one from set partitioning, i.e. exact cover. If you still care about solving the problem, you can do it in $O^\*(2^k)$-time, where $k$ is the number of colors.

# Answer
> 0 votes
This is NPC and we can reduce a $k$-SAT problem (usually $3$-SAT) to this.

Firstly given a $3$-SAT problem, we can construct a full-connected directed graph: a source node $s$, a sink node $t$ and some layers. Each layer comes from a clause in the SAT problem and have $3$ (or $k$) nodes.

Then we let each pair of nodes form a zone/color if they are oppositie, i.e., $x$ and $\bar{x}$. So it's easy to see that we can find such a path from $s$ to $t$, if and only if there is a solution for the SAT problem.

---
Tags: algorithms, graphs, decision-problem, network-flow
---


title: the load factor in hash table

text:
# Question
Title: the load factor in hash table
What is numerically the best value or range of values used as a reference for the load factor used in the hash table? What is the pseudo-code of the “rehashing” method, which is applied when many elements are added to a hash table and the load factor increases and the best value used as a reference is exceeded.

# Answer
> 0 votes
I’ll suggest to do some work yourself.

When you look up, or add, or remove a value from the hash table, what operations would be performed with different load factors, with which probability, what the cost of these operations is, and what the memory usage would be on average.

That should give you some idea, which you then confirm with actual measurements.

You will also have a hysteresis: You have one load factor that is considered "too high" and another that is considered "too low". You resize the hash table if your load factor is too high or too low. Having only one load factor has the risk that you resize the hash table if the load factor becomes too high, then you remove one item and resize again because it is too low, add one item and resize and so on. You'd pick the new table size so that the load factor is somewhere in the middle, so you'd have to add or remove many many items before you want to resize again.

Last thing: Some hash tables have an interface where you can set the size beforehand. Say you have 10,000 items, then you create the hash table, big enough to have a good load factor if filled with 10,000 items, and add the items, so you avoid multiple resizing operations. Typically implementations assume that you will add a few more items than planned and are careful with resizing.

Important note: You don't write code for hash tables just for fun. For example, if you write code for MacOS or iOS using hash tables, there is ONE implementation that you will use, provided by the OS, and written by someone who knows a lot more about optimal implementations of hash tables than I ever will. Sure, you can write an implementation for educational reasons, but you won't come near a good implementation.

# Answer
> -1 votes
According to this, Python doubles the hash table when the load factor reaches $2/3$. This mentions the probe sequence used by Python for implementing dictionaries using hash tables.

---
Tags: algorithms, hash
---


# Question
Title: What is the principle of multiplication of D-normalized polynomials for a CRC calculation?
I'm studying the principle of CRCs from *everything we know about CRC but afraid to forget* by Andrew Kadatch1 and Bob Jenkins, 2010.

I do not understand:

```
bPowX[k+1] = (bPowX[k] >> 1) ^ P    // in Listing 1: Multiplication of normalized polynomials

//XpowN returns (x**N mod P(x))
result ^= Multiply(temp, Multiply(m, XpowN(d)));      // in Listing 2: Multiplication of unnormalized polynomial

```

Why do we need `^ P`?

Why do we need to calculate `mod P(x)`?

# Answer
> 3 votes
For the first question, the `>> 1` is multiplying the polynomial `bPowX[k]` by *x*. (The polynomials in this implementation are reflected, so the high powers of *x* are in the least significant bits.) The `^ P` is then taking that polynomial and computing the remainder upon dividing by the polynomial *P(x)*. That is the modulo operation, *mod P(x)*. The `^ P` is done only if multiplying by *x* results in a power of *x* that is the degree of *P(x)*, `D`. That happens when the low bit is initially a one, which represents *xD-1*. The `^` operation is how you subtract (or add for that matter) polynomials over GF(2).

For an analogy in integers, let's say I am doing my calculations modulo 13. I have 5 and double it, getting 10. Still less than 13, so it is already mod 13. That's like the branch in the polynomial code where the `& 1` is zero. I double it again and get 20. Now that's more than 13, so I need to subtract 13 to get 20 mod 13. That gives me 7. That's like the branch in the polynomial code where the `& 1` is one.

The second question is effectively: Why are we treating the *D* bits of a CRC as a polynomial over GF(2), and doing our operations modulo some polynomial over GF(2)? That is at the very core of the mathematics of cyclic redundancy checks, so the response would be too long for an answer here. There are many textbooks covering the use of finite fields for error detection and correction.

---
Tags: crc
---


title: Understanding a CRC32 Implementation

text:
# Question
Title: Understanding a CRC32 Implementation
I'm currently trying to understand an implementation of CRC32 about which I have a question.

On this page at section 6, there is the following code:

```
public uint Compute_CRC32_Simple(byte[] bytes)
{
    const uint polynomial = 0x04C11DB7; /* divisor is 32bit */
    uint crc = 0; /* CRC value is 32bit */

    foreach (byte b in bytes)
    {
        crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80000000) != 0) /* test for MSB = bit 31 */
            {
                crc = (uint)((crc << 1) ^ polynomial);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

```

I'm particularly interested in understanding this line: `crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */`

What are the mathematics that make this line possible, both the shifting of the current byte (turned into an int) by 24 and the following XOR with the current crc? Unfortunately, the author doesn't go into detail regarding this. What I want to know is why dividing the current byte and then xoring the remainder with the next byte is the same as a manual division bit by bit

EDIT: made question clearer

# Answer
> 1 votes
Perhaps what you are imagining is something like this at the top of the inner loop, where the bits of `b` are fed one-by-one into the high bit of the CRC:

```
        if (b & 0x80)
            crc ^= 0x80000000;
        b <<= 1;

```

That is equivalent to this:

```
        crc ^= (uint)(b & 0x80) << 24;
        b <<= 1;

```

Now you can see where the 24 comes from. Note that each time, both `crc` and `b` are shifted up by one. It only makes decisions based on the high bit of `crc`, and the order that you do exclusive-or's in doesn't matter, so you can simply exclusive-or all eight of the bits of `b` into the high byte of `crc` outside of the inner loop, to get the same effect:

```
    crc ^= (uint)b << 24;

```

---
Tags: coding-theory, error-correcting-codes, crc
---


# Question
Title: (Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory
The Weight Distribution / Subspace Weights Problem in coding theory is defined as this:
Instance: A binary $m$ by$n$ matrix $H$ and an integer $k \> 0$
Question: Is there a set of $k$ columns of $H$ that sum to the all-zero vector?

You might also say:
Given a binary $m$ by$n$ matrix $H$ and an integer $k \> 0$, is there a vector $\vec{x}$, s.t. $$ A\vec{x} = \vec{0} $$ where $\vec{x}$ has Hamming Weight k?

This Problem is proven to be NP-complete (On the Inherent Intractability of Certain Codiig Problems). But is there any fast (polynomial) exact (for small inputs) or approximation algorithm to solve the problem?
So far I wasn't able to find one.

# Answer
> 0 votes
I believe this is called the low-weight codeword problem. Searching on this will turn up a number of research papers with algorithms for this problem.

---
Tags: complexity-theory, linear-algebra, hamming-code
---


# Question
Title: Complexity of string comparison vs whitespace-trimmed string comparison
I recently worked on an algorithm which, among other things, checks strings for equality using the classic builtin equality operator:

```
str1 == str2

```

(I think it should be irrelevant to the question, but I faced this issue in C++, and `str1` and `str2` are obviously `std::string`s.)

At a later point I decided to relax the equality condition between strings such that it actually does

```
trimspace(str1) == trimspace(str2)

```

where `trimspace` removes leading and trailing whitespace.

I innocently thought that the complexity (at least in the worst case scenario of equal strings) would stay the same, because just like the original code has to check each and every corresponding character of the two strings for equality, also the new one would do the same, just after skipping any leading or trailing whitespace, which is also done by visiting each space character only once.

In reality I observed an enormous slowdown.

Stepping through the code with a debugger, I eventually realized that the `str1 == str2` call was translated to a single call to `memcmp`, which is a builtin that checks two `char` arrays for equality, whereas the `trimspace(str1) == trimspace(str2)` resulted in as many calls to `memchr` as the total number of leading and trailing whitespaces of the two strings plus 4, plus one call to `memcmp` for comparing the trimmed strings.¹

This clearly resulted in the slowdown I mentioned, I guess because of the cost of the function calls.

I see that the fundamental problem is that, despite the two expressions require both O(N),

* the first one, `str1 == str2`, which requires all characters to be compared, doesn't require them to be compared in order, because they can all be compared at the same time, in parallel, so the CPU can take advantage of that;
* on the other hand the expression `trimspace(str1) == trimspace(str2)` requires to traverse the string in an ordered way (from left to right and from right to left) to trim the (leading and trailing) spaces one by one.

How is this difference between the two computations above formalized in the computational complexity theory?

---

¹ For example, to compare  `hello`  (3 spaces before and 2 spaces after the word *hello*) with itself, the 3 leading and 2 trailing characeters are successfully compared for equality with the space character, and the `h` and `o` are checked unsuccessfully, thus terminating the trimming; and this happens for the two copies of the string, resulting in 14 characters being compared for equality with the speace character, each comparison happening via a call to `memchr`; then `hello` is compared with its identical counterpart via one single call to `memcmp`.

---

I initially posted this question on stackoverflow; you can see it (deleted) here.

# Answer
> 2 votes
From the viewpoint of complexity theory, comparing two strings, with or without surrounding whitespace, takes time linear in the lengths of the strings, because there is no computational model, practical or afaik theoretical, in which parallel computation is unlimited. A real-world machine could do parallel comparison of a certain length of strings, which would reduce the constant factor of the total comparison by the degree of parallelisation, but the constant will not reach 0, and the computation will be asymptotically linear.

In practice, there are a lot of possible optimisations which could make a huge difference, at least if it's unlikely that the strings being compared are equal. That's not very relevant to complexity theory, but to illustrate a few:

* If the representation of strings includes their length, then you could start `str1 == str2` by comparing the lengths, in O(1) time. Depending on the frequency distribution of string lengths, this might result in sublinear average time. But it won't work for trimmed strings, since you have to trim the strings before comparing the lengths.
* Similarly, you can stop the scan as soon as you find a pair of differing characters. But in the case of trimmed strings, your algorithm starts by trimming, which takes time linear in the amount of surrounding whitespace. Again, depending on the frequency distribution of the arguments to the function, this can have a large effect. If, for example, strings are uniformly distributed over a large alphabet, then the first difference will be found in linear time, on average. (However, comparing two equal strings will result in worst-case (linear) performance.) But for the trimmed strings, the work involved in trimming will depend on the frequency distribution of surrounding whitespace, which could have much more impact than the cost of comparing the first few characters.

In practical terms, writing `trimspace(str1) == trimspace(str2)` is certainly the clearest and probably advisable in many cases, but in performance critical code you would be well-advised to find an algorithm with better average-time performance. For example, many languages would force the creation of two new string objects in order to store the results of the `trimspace` calls; copying objects is not free (indeed, it takes linear time), and the copy is completely unnecessary.

Similarly, it's not necessary to trim the ends of the strings unless the strings have matched equal up to that point. So a better algorithm might be:

* Find $i\_1$ and $i\_2$, the indices of the first non-whitespace characters in $s\_1$ and $s\_2$.
* While $s\_1\[i\_1\] = s\_2\[i\_2\]$, increment both $i\_1$ and $i\_2$.
* If, while performing the above test, one of the indices reaches the length of its corresponding string, check whether all the remaining characters (if any) in the other string are whitespace. If a non-whitespace character is encountered, return False; otherwise, return True.

That will still take $O(n+m)$ in the worst case (which is when the strings are equal), but if equality is not a common case, it's likely to be sublinear on average.

# Answer
> 0 votes
If the m-th of n characters is different, comparison takes O(m) time to find the strings are different. If strings where preceded by k and k' white space characters, you could do the comparison of unequal strings in O(k+k'+m).

If you call a function first that trims the strings, then it depends on the implementation. Some implementations may return the same string in O(1) if there is neither leading nor trailing whitespace. Some implementations may be able to return objects representing a substring of another string, in O(l + t) if there are l leading and t trailing whitespace characters. Other implementations will return a copy of the relevant characters, typically in O(n).

# Answer
> 0 votes
Analysing the complexity, answering whether two strings are equal can be done in linear sequential time by comparing them character by character, so the runtime is in $O(n)$ if the strings have length $n$. Comparison can be done with memcmp, but from the complexity point of view, that is just a detail.

If you ask whether two strings are equal when you ignore leading or trailing whitespaces is a completely different problem. One way to solve it is to trim both strings, but the complexity of trimming itself depends on the number of characters considered "whitespace". In the worst case, if you have a string of length $n$ and $k$ possible whitespace characters, trimming can take $\Theta(kn)$ because you have to check every all characters before and including the first non-whitespace with (in worst-case) all whitespace characters, and do the same from the end.

That's your "number of whitespaces+4" calls to memchr for trimming two strings. They're not constant time, but linear in the number of whitespaces.

So your solution to check whether two strings are equal ignoring leading and trailing whitespaces has complexity $O(kn)$.

Theoretically speaking, this makes no difference, since $k$ is a small constant, but practically, trimming a string is more work than comparing it to another string.

---
Tags: complexity-theory, substrings, string-matching, equality, exact-string-matching
---


# Question
Title: How to find wiggle sortable arrays? Did I misunderstand John L.s' answer?
I have read following answer and question How to wiggle sort an array in linear time complexity?.

But while reading I came up with a question. I can't comment on answers yet, so I decided to make an extra question out of it.

John L. states that

> Call A wiggle-sorted if A0 \< A1 \> A2 \< A3 \> A4\<...
> Call A wiggle-sortable if we can rearrange its entries so that it becomes wiggle-sorted. An array is always wiggle-sortable if all numbers in it are distinct. If all numbers are not distinct, the array may or may not be wiggle-sortable. For example, \[1,2,2\] is not wiggle-sortable while \[1,1,2\] is wiggle-sortable."

I understand that there is no possibility to wiggle sort \[1, 2, 2\] because for wiggle sorting values next to each other are not allowed to be even and the values at the even indexes have to be smaller than those at the odd indexes. So, \[2, 1, 2\] would not be allowed.

I am confused because further in John L.s' answer it is stated:

> Characterization of wiggle-sortable arrays. The following propositions are equivalent for a number array of size n.

> 1. A is wiggle-sortable of size n.
> 2. (Not too many medians) The number of medians of A is no more than ⌈n/2⌉.
> 3. If we have just sorted A(in the usual sense), then wn(A) is wiggle-sorted.

If 1 and 2 are equivalent then 2 being true means 1 is true.
The median for \[1, 2, 2\] is 2, the number of medians is also 2.
⌈n/2⌉ is ⌈3/2⌉ = 2. So 2. seems fulfilled to me but \[1, 2, 2\] is not wiggle-sortable.

John L.s' seems to be way better at math than me though, so maybe I did misunderstand something?

# Answer
You have identified an off-by-one error in that answer.

The correct statement for proposition $2$ should be the following.

> (Not too many medians)$\def \A{\mathcal A}$ The number of medians of $\A$ is no more than $⌈n/2⌉$. Furthermore, if $n$ is odd and the number of medians is $\[n/2\]$, the median must be the smallest number of $\A$.

Or, what is equivalent,

> Any number occurs at most $⌈n/2⌉$ times in $\A$. Furthermore, if $n$ is odd and a number occurs $⌈n/2⌉$ times, it must be the smallest number of $\A$.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is there an algorithm for finding a minimal subgraph that connects certain nodes?
This problem comes up in the context of game skilltrees, for example in Path of Exile. In this case, one wants to have a subgraph of the entire graph that connects all desired nodes to the origin, but contains as few nodes as possible. Is there an efficient algorithm for this, or a good heuristic? Or is it, as I suspect, NP-hard?

Simply using Dijkstra to determine the distances and then Kruskal to find a minimum spanning tree does not work. This is because the cost of connecting a subsequent node can depend on what nodes are already connected (and by which paths).

# Answer
You are talking about the Steiner tree problem. The decision problem is as follows:

Given a graph $G = (V, E)$ and a set of *terminal* vertices $T \subseteq V$ and a integer $k$, does there exist a set of at most $k$ edges $F \subseteq E$ such that $G' = (T, F)$ is connected.

The problem is indeed NP-complete, but on the positive side, it is solvable in *fixed parameter tractable* time $O(3^k (n+m))$.

There is an approximation algorithm too.
> 1 votes

# Answer
As already said, that is the (NP-hard) Steiner tree problem in graphs. If you just care about the number of included vertices, you can simply set all edge weights to 1. Please note that NP-hard does not mean at all that it is not efficiently solvable in practice. Under "External links" on https://en.wikipedia.org/wiki/Steiner\_tree\_problem you find some efficient exact solvers for this problem, which provide optimal solutions to Steiner tree problems with tens of thousands of edges within seconds.
> 0 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?
In the Optimal Substructure Wikipedia,

> As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.
>
> (Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D.) However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure: the cheapest flight from A to B involving a single connection is either the direct flight; or a flight from A to some destination C, plus the optimum direct flight from C to B.

It is very unclear that why optimal substructure can be observed when we specify the at most intermediate stops? From my understanding (which can be wrong), even if we provide the at most intermediate stops such as K = 4, we can not conclude that the cheapest price will be the sum of the prices of the individual flights in the trip as the multi flight trip is usually not the sum of the prices of the individual intermediate flights.

Can anyone please explain me with examples?

# Answer
It is better to ignore the confusing text below, which was added to that page of Wikipedia by an anonymous user on "20 August 2020", as shown on this comparison page.

> However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure: the cheapest flight from A to B involving a single connection is either the direct flight; or a flight from A to some destination C, plus the optimum direct flight from C to B.

Here is a better explanation that could replace that confusing text.

> However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure. The cheapest flight from A to B that involves at most $k$ layovers is either the direct flight; or the cheapest flight from A to some location C that involves at most $t$ layover for some $t$ such that $0\le t\le k-1$, plus the cheapest flight from C to B that involves at most $k-1-t$ layovers.
> 1 votes

---
Tags: graphs, dynamic-programming, optimal-strategy
---


title: Condensed Nearest Neighbor Explanation

text:
# Question
Title: Condensed Nearest Neighbor Explanation
I have a question regarding the Condensed Nearest Neighbor algorithm from chapter "Nonparametric Methods" in the book *Introduction to Machine Learning (OIP)*, by Ethem Alpaydin, Mit Press, 2004. pp. 174–174.

Ultimately, I am supposed to return the subset `Z` to be a local minimal subset to use for training set in KNN. Why am I returning `Z`, which, if I understand correctly, is the array of all of the misclassified points? Wouldn't I want to return the points that *were* classified correctly? What benefit does this give me in returning all the points I got wrong?

# Answer
`Z` is not the array of misclassified points. Try working through an example, and be careful and precise when making statements like that; while you can talk about which points are classified by a particular classifier, that will depend on the classifier. So, when there are multiple classifiers floating around (or multiple training sets floating around), you need to specify *which classifier* you are referring to. I suspect this is what is tripping you up: something that is misclassified with one training set might be correctly classified with another training set.

The key guarantee of this procedure is: if you use Z as your training set for a nearest-neighbor classifier, then this NN classifier will have 100% accuracy. Try working through an example to see why. (It iteratively grows the training set as needed to ensure that every point will be classified correctly by that NN classifier.)

As always, when you are confused, start by working through a small example with a few points (two, three, four), simulating the algorithm by hand, with pencil and paper. That will often be very effective at building intuition -- and in this case it should be sufficient to understand what is going on.
> 1 votes

# Answer
The idea is to form a subset ($Z$) of the training set such that it classifies the same way as the whole set, using the nearest-neighbor rule.

If a classification error occurs, adding to $Z$ the element that causes the error will obviously fix the error. You continue until there are no more errors.
> 0 votes

---
Tags: algorithms, machine-learning, reductions, nearest-neighbour
---


title: Logical consequence problem, doubt

text:
# Question
Title: Logical consequence problem, doubt
It is possible to have this logical consequence? $$ \forall x (p(x) \vee q(x)) \models \forall x p(x) \vee \forall x q(x) $$

# Answer
The statement $\forall x (p(x) \vee q(x))$ does not imply $\forall x p(x) \vee \forall x q(x)$ because there exist a domain, a propositional function p(x) and a propositional function q(x) for which $\forall x (p(x) \vee q(x))$ is true and $\forall x p(x) \vee \forall x q(x)$ is false.

For an example, let the domain be the set of all integers, let $p(x)$ be the propositional function "$x$ is even'' and let $q(x)$ be the propositional function "$x$ is odd''. Then, $\forall x (p(x) \vee q(x))$ is true because every integer is either even or odd, but $\forall x p(x) \vee \forall x q(x)$ is false because it's not the case that ever integer is even and it's not the case that every integer is odd.

Of course, you can find other domains and propositional functions $p(x)$ and $q(x)$ such that both expressions have the same truth value, but the implication does not hold because it does not hold in general.
> 2 votes

# Answer
Take the structure $\mathfrak{A} = (\\{a, b\\}, =)$ and $p(x) \equiv x = a$, $q(x) \equiv x = b$. Then $\mathfrak{A} \models \forall x (p(x) \vee q(x))$ but $\mathfrak{A} \not\models \forall x p(x) \vee \forall x q(x)$.
> 1 votes

---
Tags: logic, first-order-logic
---


# Question
Title: What loop invariant can be used for this loop? (Algorithm to check if a sequence is stack permutable)
I've written a function that gets a permutation and checks if that permutation can be reached using a stack from an input sequence which is \<1,2,3,...,n\>. (we take elements from left)
For example: if we have an input sequence, then if the function gets these permutations:
\<4,3,2,1\> - Returns true since we can push (1) push (2) push (3) push (4) and then pop (4) pop pop pop to get this permutation.
\<4,3,1,2\> - Returns false since this permutation cannot be reached (2 will always be above 1 in the stack after reaching 4,3).
The algorithm looks something like this in pseudocode:
I've referred to the permutation we're checking by P, and the \<1,2,3,...,n\> sequence by In(input).
The empty stack I'm using will be S.

```
While (In is not empty)
   i = 0
   Take In leftmost element store it in x (1 then 2 then 3,...)
   if (x == P[i])
      i = i + 1 // i can be printed by push pop so we  keep going
      while(S is not empty)
         x = pop(S)
         if (x == P[i])
            i = i + 1 // x is the next number in the permutation
         else
            push(x) // x isn't the next number so we keep it in stack for later
            break
   else
      push(x)

if (S is not empty AND i = n+1)
   return TRUE
else
   return false

```

The idea is to keep taking numbers from our input sequence (In) until we reach the next permutation number (P\[i\]), once we reach it we check if the next one can be found in the stack before checking the next input numbers (they will be sorted such that the biggest will be on top of the stack, so if it's lower value than the top we can't really reach it, and if it's higher value then we will reach it in the input sequence).
Now what I'm trying to do is to prove the correctness of this algorithm, for that I know I need to write some loop invariants for my loops, I've tried to think of my goal, which is to check if a permutation can be reached using a stack, if the stack is not empty at the end, then we got stuck and the permutation can't be reached, just like \<4,3,1,2\>.
My attempt for loop-variant for the outer loop (`while(In not empty)`):
At the start if each iteration, the elements P\[0...i-1\] (As of all the elements of the permutation until the one P\[i\] we're looking at now), are either reached in the permutation (Pushed and popped - just like 4 in \<4,3,1,2\> when we're looking at 3, it would have been reached by push push push push pop), OR they're inside the stack.

Now if this worked, I would've been done since at the end if the stack isn't empty, then the permutation cannot be created, but when I looked in the inner loop, I still go into the stack to check, so the elements P\[1...i-1\] are really reached again sometimes and that ruined my plans, and I've been stuck trying to come up with another loop invariant or fixing this one.
I would appreciate any help and feedback, Thanks in advance.

# Answer
This question is interesting in the sense that although people might convince themselves that the "obvious" algorithm is correct, it may not be obvious to find a good loop invariant.

#### The Basic Idea

Your algorithm is, in fact, simulating the possible sequence of actions that produces a given stack-permutable sequence. **Given a stack-permutable sequence, there is only one sequence of actions to produce it essentially**. If your algorithm takes the only possibly-successful actions upon each input number, it must be correct.

#### A Clearer Algorithm

Let us augment your pseudocode with a write-only queue Q to make it clear that the algorithm tries to reproduce the given permutation P. Since the queue is never read, it does not change the semantic of the algorithm in the question.

```
Initialize an empty queue Q and an empty stack S
Let In be input that produces 1, 2, ..., n.
Treat sequence P as a queue
While In is not empty:
    Move the next number from In (1 then 2 then 3,...) onto S
    While S is not empty and the top of S is the front of P:
        Move the top of S to Q
        Pop P

if S is empty
   return True    # Q is the same as the original P
else
   return False

```

#### The Loop Invariant.

Given P, the algorithm runs a sequence of moving actions of one of two types:

* move a number from In to S
* move a number from S to Q and pop P as well (only when the top of the S is the same as the front of P)

Here is the invariant of the whole algorithm: **the algorithm always take the only possible moving action so that in the end Q might be the same as the original (input) P.**

**Proof**: Before any moving action, the algorithm may find S and P in one of the following two states.

* S is not empty and the top of S is the same as the front of P. Let the number at the top of S (and the front of P) be s.

Suppose the algorithm moves another number i from In to S.

+ Since S is a stack, i will be moved into Q before s if both of them will ever be moved to Q. Once i and s are in Q, no later actions can change the order of them in Q, since Q is a queue. So in the end, i will sit earlier than s in Q.
    + On the other hand, i will only be moved into Q at the point of time t later when both the top of the stack is i and the front of P also *becomes* i. Since P is a queue and the front of P is s now, i must sit later than s now. In other words, i sits later than s in the original P.

The inconsistent order of i and s in Q and in the original P means this moving action from In to S cannot be successful. Hence, the only action for the algorithm to take so that in the end Q might be the same as the original P possibly is moving the number at S to Q and popping P.
* Either S is empty or the top of S is not the same as the front of P.
In this case, the only possible action for the algorithm to take is moving a number from In to S.
> 1 votes

---
Tags: permutations, loops, stacks, loop-invariants
---


# Question
Title: Implementing Flajolet–Martin algorithm in Python
**I am stuck on what to do.**

I am trying to create a simple implementation of the **Flajolet–Martin algorithm** using Python. The stream will be the contents of a text file and you will produce an approximation of the number of unique words in the file as given by the algorithm. You will need to process the file one line at a time and may not store any part of the file. You can obtain words by splitting the lines on whitespace. Your code will be run from a terminal according to the following command

The **text file** is:

```
this is a fun file
this is the second line of the file
this is the third line of the file
this is the fourth and final line of the file

```

**Code**

```
import sys

for line in sys.stdin:
    words = line.split()
    for word in words:
        bin_string = bin(hash(word))
        print(bin_string)

```

# Answer
The objective is to estimate the cardinality of a multiset M, where M is the set of words in the file, using a small amount of storage. The probabilistic counting algorithm in the Flajolet-Martin 1985 paper requires a hash function whose output is sufficiently uniformly distributed over the set of all $L$-bit strings, and works as follows. A big string BITMAP\[0..L-1\] is initialized to all zeros. For each word w in the multiset, hash(w) is computed, and an index i is determined, where i is the position of the least significant 1 in the binary representation of hash(w). (The pseudocode below assumes the function rho computes this index $i$.) Then, BITMAP\[i\] is set to 1. After a pass through all elements of the multiset $M$, the quantity $R$ is computed and is the position of the leftmost zero in BITMAP. An estimate of the number n of distinct elements in the multiset is $n \approx \frac{2^R}{\psi}$, where $\psi = 0.77351$.

Here's the pseudcode (I'll leave you to implement the code below, including the functions rho and hash, in Python):

```
for i = 0 to L-1:
    BITMAP[i] = 0
for word in M:
    i = rho(hash(word))
    BITMAP[i] = 1
R = smallest i such that BITMAP[i] = 0
n = 2^R / 0.77351  #estimate of number of distinct elements in M

```

The intuition is that if $n$ is the number of distinct elements in the multiset $M$, then BITMAP\[0\] is accessed about $n/2$ times, BITMAP\[1\] is accessed about $n/4$ times, and so on, and so if $i \>\> log\_2 n$, then BITMAP\[i\] will be 0 with high probability, and if $i \<\< log\_2 n$, then BITMAP\[i\] will be 1 with high probability, and there will be a fringe of 0's and 1's for $i \approx \log\_2 n$. The authors suggest using the position of the left-most zero or right-most 1 in BITMAP to obtain the estimate $R$ (they propose using the former, and some of the other literature suggests using the latter).
> 0 votes

---
Tags: algorithms, hash, python, hashing, streaming-algorithm
---


# Question
Title: Use induction to prove the correctness of shortest path algorithm
Suppose given a directed graph $G=(V,E)$ with positive weights and we try to find shortest path $d(s,t,\ell)$ from $s$ to $t$ such that we traverse at most $\ell$ edges ($\ell$ is even). Let $w(u,v)$ be weight of edge (u,v), so we use this recurrence, $$d(s,t,\ell)=\begin{cases} \min\_{x \in V}\\{d(s,x,\frac{\ell}{2})+d(x,t,\frac{\ell}{2})\\},& \text{if } \ell\geq 2\\ w(s,t), & \ell=1\\ \infty, & \ell=0 \end{cases} $$

How we can prove by induction that the above recurrence find optimal solution?

I try to induction on $\ell$ so when we let $\ell=0$ the answer is $\infty$ so it's correct. Also for $\ell=1$ the correct answer is $w(s,t)$ so the recurrence is correct, but how we can extend this idea to show that whole recurrence is correct?

# Answer
> 1 votes
Here is how a proof by induction would look like here. We prove by induction on $r$ the following claim:

> For every pair of vertices $s,t$, the value of $d(s,t,2^r)$ is the length of the shortest path from $s$ to $t$ which uses at most $2^r$ edges (or $\infty$ when there is no such path).

Denote this claim by $P(r)$. You need to prove two things:

1. Basis: $P(0)$ holds.
2. Step: If $P(r)$ holds then $P(r+1)$ holds.

If the proof doesn't work, perhaps you need to modify your recurrence. In case this modification involves allowing lengths which are not powers of $2$, you might need to prove the following similar claim by induction on $\ell$:

> For every pair of vertices $s,t$, the value of $d(s,t,\ell)$ is the length of the shortest path from $s$ to $t$ which uses at most $\ell$ edges (or $\infty$ when there is no such path).

Denoting this claim by $Q(\ell)$, the proof by induction would go as follows:

1. Basis: $Q(0)$ and $Q(1)$ holds.
2. Step: If $Q(r)$ holds for all $r \< \ell$, then $Q(\ell)$ also holds.

Good luck!

---
Tags: algorithms
---


# Question
Title: Proving the NP hardness of two variants of SAT
$k$-$\text{RSAT}$ is a variant of $k$-$\text{SAT}$ where we restrict our attention to formulae in which each variable occurs at most $3$ times, and each literal occurs at most twice. The language $k$-$\text{RSAT}$ is $$\\{\phi \in k{-}\text{SAT} \mid \text{ no variable (literal) occurs more than 3 (2) times in }\phi \\}.$$

$k$-$\text{NAESAT}$ is a variant of $k$-$\text{SAT}$ where we allow only assignments in which at least one literal in each clause evaluates to $0$.

I'm trying to prove that $k$-$\text{RSAT}$ and $3$-$\text{NAESAT}$ are $\text{NP}$ hard. If it helps, the previous subpart to this problem involved proving that $k$-$\text{NSAT}$ (defined below) is $NP$ hard (which I've proven).

$k$-$\text{NSAT}$ is a variant of $k$-$\text{SAT}$ where, given a $k{-}\text{CNF}$ formula $\phi$ and a natural number $n$, the problem is to determine if there exists an assignment for which at least $n$ clauses of $\phi$ evaluate to 1

How do I prove this?

# Answer
> 1 votes
The idea is to use a gadget that lets you copy variables. Given a variable $x$, there is a gadget that allows you to create a copy of $x$, that is, a new variable $x'$ such that any satisfying assignment of the gadget satisfies $x = x'$. Using your gadget, you create enough copies of each variable, and then replace each occurrence of a variable by a single copy of the variable.

---
Tags: complexity-theory, np-hard, satisfiability
---


title: Can we show that #3CNF is in FPTAS

text:
# Question
Title: Can we show that #3CNF is in FPTAS
If we have a deterministic algorithm $A$ such that $\\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\\#3CNF$? How can we show that $\\#3CNF \in FPTAS$?

# Answer
Given a CNF $\varphi$, you can create a CNF $\varphi^{(2)}$ such that $N(\varphi^{(2)}) = N(\varphi)^2$, where $N(\varphi)$ is the number of assignments satisfying $\varphi$. If you apply a #SAT approximation algorithm to $\varphi^{(2)}$, then you get an approximation of $N(\varphi)$ which is better than what you would get if you applied the algorithm directly on $\varphi$. To get an even better approximation, create a CNF $\varphi^{(k)}$ such that $N(\varphi^{(k)}) = N(\varphi)^k$.

In your case you have the additional complicated that everything is a 3CNF, but I suggest starting without this restriction.
> 1 votes

---
Tags: algorithms, complexity-theory, approximation, counting
---


# Question
Title: Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method
The book I took this example from (*Introduction to Algorithms, CLRS*) wants to prove that the recurrence relation

$$T(n) = 2T(\lfloor n/2 \rfloor)+n$$

is $O(n\lg n)$ using the so-called substitution method. When proving the inductive step, they use the strong mathematical induction, so they assume that

$$\forall m : m \< n, T(m) = O(m \lg m)$$

In particular, when $m=\lfloor n/2 \rfloor$ we have that

$$T(\lfloor n/2 \rfloor) \leq c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) $$

Substituting into the recurrence yields

$$T(n) \leq 2 (c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor)) + n $$

So they multiplied by 2 both sides, but I do not understand why there's "$+n$" at the end. Of course it comes from the recurrence relation, but I don't understand why they do that. Shouldn't they just prove that $T(n) \leq c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) $?

# Answer
> 1 votes
They didn't "multiply by 2 both sides". Rather, they substituted the bound they have on $T(\lfloor n/2 \rfloor)$ in the recurrence relation: \begin{align} T(n) &\stackrel{(\dagger)}= 2T(\lfloor n/2 \rfloor) + n \\ &\stackrel{(\ddagger)}\leq 2c\lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \end{align} Here $(\dagger)$ is the recurrence relation, and $(\ddagger)$ is the result of substituting the induction hypothesis. In order to complete the proof of the inductive step, we need to show the following inequality $(\ast)$: $$ 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \stackrel{(\ast)}\leq cn\lg n $$ In order to prove $(\ast)$, we argue as follows: $$ 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor \leq 2c(n/2) \lg(n/2) + n = cn(\lg n - 1) + n = cn\lg n + (c-1)n, $$ which is at most $cn\lg n$ as long as $c \geq 1$.

(For the proof to work, we also need the induction basis, which might require larger $c$. Note that the basis here is $n=2,3$, since $c1\lg 1 = 0$ is probably not a bound on $T(1)$.)

# Answer
> 3 votes
If we multiply the left-hand side $T(\lfloor n/2 \rfloor)$ by $2$, we get $2T(\lfloor n/2 \rfloor)$, not $T(n)$.

Let $P(n)$ be a propositional function. To prove that $P(n)$ is true for all $n \ge 1$, you can (sometimes) use the principle of strong induction, which states that it suffices to prove that $P(1)$ is true, and that for all $n \ge 2$, $P(n)$ is true whenever $P(1),P(2),...,P(n-1)$ is true. This assumption that each of $P(1),P(2),\ldots,P(n-1)$ is true is called the inductive hypothesis. In particular, by the inductive hypothesis, we have that $P(\lfloor n/2 \rfloor)$ is true.

In your example, $P(n)$ is the propositional function $T(n) \le c n \log n$, which you want to prove is true for all sufficiently large $n$. Of course, you can also assume that $T(n) = 2 T(\lfloor n/2 \rfloor) + n$, since you are given in the problem statement that this equation holds for all $n$. In the right hand side of this equation, there is a term $T(\lfloor n/2 \rfloor)$, for which you can substitute an upper bound of $c \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor)$ because $P(\lfloor n/2 \rfloor)$ is true by the inductive hypothesis.

In other words, you can assume $T(n)=2T(\lfloor n/2 \rfloor)+n$ and $T(\lfloor n/2 \rfloor) \le c \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor)$, and you try to show that $T(n) \le c n \log n$.

---
Tags: recurrence-relation
---


# Question
Title: How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?
I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords. As far as I know, to calculate the number of errors to be corrected and/or detected someone must know the Hamming distance between 2 codewords. However, I do not have any relevant information to find out a solution to this question. I tried to calculate the efficiency of this code using the formula: (E = Number of original message bits / length of the codeword). The efficiency in my case is 1/5. But, I do not know how can I use this information to calculate the number of errors that can be corrected and detected.

# Answer
> 1 votes
There are $2^{10}$ binary strings of length $10$. We can partition them into pairs $x\_1\ldots x\_90,x\_1\ldots x\_91$. Since your code contains more than $2^9$ codewords, it will contain at least one such pair. Hence the minimum distance of your code is only $1$.

# Answer
> 0 votes
While the Hamming distance is used in general to determine the number of bit errors that can be detected or corrected, this particular problem is a degenerate case where the code is so large that the Hamming distance of the code is 1.

More specifically, the set $\\{0,1\\}^{10}$ of all 1024 10-bit strings can be partitioned into 512 subsets of the form $\\{a,b\\}$, where $a,b \in \\{0,1\\}^n$, $a$ contains a 0 in the first position and $b$ contains a 1 in the first position, and $a$ and $b$ have the same values in the other positions. Thus, the Hamming distance between two codewords in the same subset is exactly $1$.

If the codebook has 550 codewords, then by the pigeonhole principle some two codewords must belong to the same subset, i.e. must have a Hamming distance between them of only 1. This means, if even one bit is flipped, the receiver will not be able to decode the transmitted signal correctly. Hence, this code does not have any error detection (or correction) capability.

---
Tags: information-theory, error-correcting-codes, hamming-code, hamming-distance
---


# Question
Title: What kind of algorithm do i need when the place of numbers changing according to n number?
I have a project in Golang. But i don't have any idea about how to solve it.

n will be an odd number (Feedback will be given if an odd number is not written)

* As output, a structure with n\*n matrix appearance will be created according to the following rules and printed on the screen.

## Rules

The rules will be transferred assuming the entered number is 3. (Any number can be entered)

* The first number will be in the middle column of the first row.
* The next number is placed in the diagonal square, to the top right.
* In such a case, the overflowing number is placed at the bottom of the column in the section it is in.
* The next number is placed in the diagonal square, to the top right.
* If the number overflows from the right, it is placed on the leftmost row.
* The next number is placed in the diagonal square, to the top right.
* If the cell is full, it is placed under the previously placed number. The number 4 is placed under the number 3.
* The next number, the number 5, is placed in the diagonal square to the top right.
* The next number, the number 6, is placed in the diagonal square to the top right.
* The next number, 7, is placed in the diagonal square to the top right.
* In case of cross overflow, it is placed below the previous number.
* For other numbers, the above rules are applied.
* Since the number 8 overflows from the right, it is placed on the far left in the line it is in.
* The number 9 overflows.
* In case of overflow, it is placed at the bottom of the column.
* All numbers are placed by operating the rules.

here's the output for `n = 3`

```
Enter the number : 3
8 1 6
3 5 7
4 9 2

```

I can make the zigzag matrix but I can't build an algorithm for this question. Can anyone help me about building the algorithm?

Progress:

I noticed that the sums of each row and column are equal. For example:

* `n=3` ==\> the sum of each row and column of the resulting matrix is equal to each other and to 15.
* `n=5` ==\> the sum of each row and column of the resulting matrix is equal to each other and 65.
* `n=7` ==\> the sum of each row and column of the resulting matrix is equal to each other and 175.
* `n=9` ==\> the sum of each row and column of the resulting matrix is equal to each other and 369.

# Answer
> 0 votes
Your observations to the sum of rows and columns hold the hint. Its a magic square !

There are numerous articles that go in depth into the construction of these squares and how they hold the properties they have. One of them here.

Now, the algorithm is just understanding these properties and then scaling them out to bigger N. The article I linked above shows a way to create a 9x9 square by treating it as a set of 9 3x3 squares.

# Answer
> 0 votes
```
package main

import (
    "fmt"
)

func array(n int) (int, []int) {

    m := make([]int, n*n)
    A := func(x int) int { return (x + n - 1) % n }
    i, j := n/2, 0
    for k := 1; k <= n*n; k++ {
        m[i*n+j] = k
        if m[A(i)*n+A(j)] != 0 {
            j = (j + 1) % n
        } else {
            i, j = A(i), A(j)
        }
    }
    return n, m
}

func main() {
    var n int
    fmt.Print("Enter the n number: ")
    fmt.Scanf("%d", &n)

    if n%2 == 0 {
        fmt.Println("Please enter a valid number")
    } else {
        fmt.Println("n number: ", n)
        n, m := array(n)
        j := 2
        for i := 1; i <= n*n; i *= 10 {
            j++
        }
        f := fmt.Sprintf("%%%dd", j)
        for j := 0; j < n; j++ {
            for i := 0; i < n; i++ {
                fmt.Printf(f, m[i*n+j])
            }
            fmt.Println()
        }
    }

}

```

here's the golang code for building n\*n matrix (n is a number from user)which is a magic square

---
Tags: matrices
---


# Question
Title: What is the BigO of a C# function when runtime is 3n - logn + 1
I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which runtime is 3n - logn + 1 milliseconds, where n is the length of the string S.

Please help!

# Answer
> 0 votes
A general rule of thumb when expressing a function in big O notation is to discard the lower order terms, and to discard the coefficient in the dominant term. For large n, 3n dominates 3n-log n +1, and discarding the coefficient 3 as well, we get that 3n-log n +1=O(n).

There is a formal mathematical definition for big O notation and it can be proved mathematically that 3n-log n+1=O(n).

---
Tags: algorithms, big-o-notation, notation
---


title: Time complexity of Euclidean algorithm

text:
# Question
Title: Time complexity of Euclidean algorithm
Consider Euclidean algorithm to find $GCD(a,b)$ as follow:

$$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}.$$

I read this link, suppose $a\geq b$, I think the running time of this algorithm is $O(\log\_ba)$. My argument is as follow that consider two cases:

1. $b\leq \frac{a}{b}$, then $a\mod b\leq \frac{a}{b}$, because
let $a\mod b=x$ so $0\leq x\<b$.
2. $b\>\frac{a}{b}$, then $a\mod b\leq \frac{a}{b}$, because
let $a\mod b=x$ so $x$ is at most $\frac{a}{b}$ because at each step when we compute $a\mod b$, we decrease at least $a$ by a factor of $\frac{a}{b}$ so $a\mod b\leq \frac{a}{b}$.

Consequently, computing $GCD(a,b)$ has running time $O(\log\_ba)$. Above argument is true or not?

# Answer
I'm not convinced your proof of the first case above is correct. Also, initially, the upper bound for $a \mod b$ is $a/b$, but $b$ will be replaced by a smaller value before the next iteration. So, the upper bound doesn't seem to reduce by the same constant factor $b$ in each iteration.

Your final answer that the complexity of Euclid's algorithm is $O(\log a)$ is correct. Here's a proof:

Suppose the Euclidean algorithm Euclid(a,b) is used to compute gcd(a,b), where $a \> b$. We show that $a \mod b \< a/2$. Consider two cases: (i) Suppose $b \le a/2$. Then, the remainder $a \mod b \< b \le a/2$, and we're done. (ii) Suppose $b \> a/2$. Then, $a-b \< a/2$, whence $a \mod b \< a/2$.

After one iteration, the pair $(a,b)$ is replaced by $(b, a \mod b)$, and after another iteration by $(a \mod b, c)$ for some $c$. Thus, after two iterations, $a$ is replaced by a number $\< a/2$. In general, after every two iterations, the first number in the pair is reduced by a factor of at least $2$. Hence, the total number of iteration is $O(\log a)$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to converts Pseudo boolean constraints to cnf format?
How to convert Pseudo boolean constraints to CNF format

for example L1 + … + Ln ≥ 1 is converted to L1 ∨ … ∨ Ln

but how about:

L1 + … + Ln ≥ k

L1 + … + Ln \< k

or

L1 + L2 = k

or

2 L1 + 2 L2L3 + L4 ≥ 3

is it there a book that I could read to understand more?

# Answer
> 1 votes
Apply the Tseitin transform to a circuit with adders and comparators.

For the special case of $L\_1 + \dots + L\_n \ge k$ (or $\le k$), see Encoding 1-out-of-n constraint for SAT solvers and Reduce the following problem to SAT.

---
Tags: logic
---


# Question
Title: Count the number of intersections of n chords of a circle in O(n log n) time
Suppose you are given two sets $\\{p\_1, p\_2,\dots , p\_n\\}$ and $\\{q\_1, q\_2,\dots , q\_n\\}$ of $n$ points on the unit circle. Each point $p\_i$ is connected to $q\_i$ by a line segment. How could we count the number of intersections of all $n$ line segments in $O(n\log n)$? You could also see the problem in Jeff Erickson's book, *Algorithms*.

I have read the posts finding the number of intersections of n line segments with endpoints on two parallel lines and find the number of intersections of $n$ chords in $O(n \log^2 n$) time. So I think by use their idea we can solve the problem above, but I get stuck.

# Answer
Fix an arbitrary point on the circle. For example, $p\_0$. Each line segment from $p\_i$ to $q\_i$ can be represented by a pair of numbers $(a\_i, b\_i)$, where

* $a\_i$ is the clockwise circular distance from $p\_0$ to one end of the line segment and
* $b\_i$ is the clockwise circular distance from $p\_0$ to the other end of the line segment

such that $a\_i\<b\_i$.

Draw line $y=0$ and $y=1$ on the coordinate plane.

* For each number $a\_i$, let $A\_i=(a\_i,0)$, a point on $y=0$.
* For each number $b\_i$, let $B\_i=(b\_i,1)$, a point on $y=1$.

Convince yourself that the line segment from $p\_i$ to $q\_i$ intersects with the line segment from $p\_j$ to $q\_j$ iff the line segment from $A\_i$ to $B\_i$ does NOT intersects with the line segment from $A\_j$ to $B\_j$.

The number of all unordered pairs of line segments from $A\_i$ to $B\_i$ is $\binom n2$.

Now the problem is to count the number of unordered pairs of intersecting line segments from $A\_i$ to $B\_i$. This is the exercise 14 (a) of chapter 1 in the book *Algorithms* by Jeffe Erickson or the post on StackOverflow as mentioned in the question. I would assume that you can solve that exercise.
> 4 votes

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


# Question
Title: Bayes theorem probability doesn't make sense
I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following:

my calculations were:

$$P(B/A) = 0.8\times A$$ $$P(B) = (Bx\*0,55)+((1-Bx)\*(0,55))$$ $$P(A/B) = (Ax\*Bx)/Cx$$

The probability gets above 1. What am I doing wrong?

# Answer
Well, then your data is clearly wrong!!

Bayes Theorem or not, you simply **cannot** have $$P\left(B\\,|\\,A \right) \times P\left(A\right) \> P\left(B\right) $$ but this "impossibility" is *exactly* what happens in your last two rows!!
> 3 votes

# Answer
The problem is your data! For example, the last row shows that $\mathbb{P}(A) = 1$ and $\mathbb{P}(B|A) = 0.8$. If $\mathbb{P}(A) = 1$ means $A$ is equivalent to all possiblities of event world. Hence, $\mathbb{P}(B|A)$ couldn't be anything except 1.
> 2 votes

# Answer
I agree with @OmG that the table is wrong. However, $\mathbb{P}(B\mid A)$ must be equal to $\mathbb{P}(B)$ and not $1$.

**Intuitively:** as @OmG said, $\mathbb{P}(A)=1$ means that under $\mathbb{P}$ the event $A$ is not informative therefore you will not update the probability of $B$ after conditioning on $A$ and thus $\mathbb{P}(B\mid A)$ must be equal to $\mathbb{P}(B)$.

**Formally:** by definition of the conditional probability of an event, $$\mathbb{P}(B\mid A)=\frac{\mathbb{P}(B \cap A)}{\mathbb{P}(A)}=\mathbb{P}(B),$$ since $\mathbb{P}(A)=1$. Thus, $\mathbb{P}(B \cap A)=\mathbb{P}(B)$. It contradicts your table.
> 1 votes

---
Tags: probability-theory, bayesian-statistics
---


title: Implications of Savitch's theorem

text:
# Question
Title: Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:

• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.

• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.

• Savitch’s theorem implies that $NExpSpace = ExpSpace$.

• Knowing that QBF validity is $PSpace$-hard, Savitch’s theorem implies that QBF validity is also $NPSpace$-hard.

I'm not entirely sure about how to go about solving the first 2. I know that the last two are true for sure, because Savitch's theorem implies that $PSPACE = NPSPACE$ and $EXPSPACE = NEXPSPACE$ as the square of a polynomial is a polynomial and the square of an exponential function is an exponential function. But I'm not sure about the first two.

# Answer
For the first two, we do not know whether it is true or false.

* It is not known whether $\text{NSpace}(\log n)$ = $\text{DSpace}(\log n)$, although Savitch’s theorem implies that $\text{NSpace}(\log n)\subseteq \text{DSpace}(\log^2 n)$.
* It it not known whether $\text{NSpace}(n^2)$ = $\text{DSpace}(n^4)$, although Savitch’s theorem implies that $\text{NSpace}(n^2)\subseteq\text{DSpace}(n^4)$.

Or we could say that Savitch's theorem is not strong enough to determine whether $\text{NSpace}(\log n)$ = $\text{DSpace}(\log n)$ and whether $\text{NSpace}(n^2)$ = $\text{DSpace}(n^4)$ without further significant development in the complexity theory of compute science.

There are claims that $\text{NSpace}(\log n) \neq\text{DSpace}(\log n)$, such as corollary $1$ in this paper by Tianrong Lin. However, "$\text{L} = \text{NL}$ problem" is listed one of open problems in this Wikipedia page still. Here $\text{L}$ is $\text{DSpace}(\log n)$ and $\text{NL}$ is $\text{NSpace}(\log n)$.
> 1 votes

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


# Question
Title: Dynamic Programming - Difficult Jumping Frog Problem
Given a set of $n$ stones, arranged in a row at equal distances from each other. The stones are numbered from $0$ to $n-1$. A frog that is on stone number $0$ has to get to stone number $n-1$.

A jump is a move from stone $i$ to stone $j$ ($i\<j$). Such a jump has length equal to $j-i$. The maximum jump length of the frog depends on its energy level (which cannot drop below $0$). A jump of length $j-i$ costs the frog $j-i$ energy. For example, with an initial energy of $3$, a frog on stone $0$ can jump to stone $3$ at most.

On some stones, there may be worms, which add energy to the frog. If the frog jumps on a stone with a worm on it, it MUST eat the worm. The list $T\[0...n-1\]$ contains the energy values of the worms on the corresponding stones. If there is no worm on the stone, this is equivalent to a value of $0$.

The frog starts with $0$ Energy, but it is guaranteed that there is a worm on stone number $0$.

Given a list $T$, the task is to return a list of the indexes of the stones on which the frog has been, before getting to stone $n-1$. However, this must be the shortest possible list. In some cases there may be more than one solution, whichever is accepted. It is guaranteed that always the frog will be able to get to stone $n-1$.

Example no. 1: For $T = \[3, 0, 2, 1, 0, 2, 5, 0\]$ the answer is $\[0, 2, 5\]$.

Example no. 2: For $T = \[7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0\]$ the answer is $\[0, 5, 7\]$.

I have no idea how to approach this problem, all I know is that I probably need to use dynamic programming here, but how? Anyone have any ideas?

# Answer
Dynamic programming is about how to implement a problem, but I think you need to solve the problem first.

A good way to solve problems in this nature is with recursion, which to solve the problem, we should try to define it recursively first.

You can think of defining this recurrence as

f(stoneIndex, energy) -\> which stones can we jump to, given the food on stoneIndex, and our energy level?

In terms of implementation, this should follow pretty quickly from the recurrence. To do DP, just cache calls to f()
> 0 votes

# Answer
We shall use bottom-up dynamic programming, where subproblems of smallest size are solved first, and their solutions are used to update the solutions to larger subproblems. Let $A$ be a two-dimensional array, where $A\[e,i\]$ denotes the minimum number of jumps needed to reach the $i$-th stone with an energy of $e$ (after consuming the worm at stone $i$). Thus, if $T= \[7,0,0,1,0,3,0,6,0,0,0,0,0,0,0\]$, then $A\[7,0\]=0$ because you reached stone $0$ after $0$ jumps, and the energy level after reaching stone $0$ and consuming the worm at that stone is $7$. (When you work this out in paper, you can draw a 2D grid of $A\[e,i\]$ values in (say) the first-quadrant of the x-y plane).

The algorithm can iterate over the indices $i$, as they go from $0$ to $n-2$. For each value of $i$, find all the energy levels $e$ that are attained by various paths that reach that stone, and for each such pair of indices $(e,i)$ where a value has been set, use the current value of $A\[e,i\]$ to update the values of $A\[e',i'\]$ for all feasible $(e',i')$. The feasible values of $(e',i')$ are those where the jump size $i'-i$ is in $\\{1,2,\ldots,e\\}$ and $e' = e - (i'-i) + T\[i'\]$ because you start with energy level $e$, consume energy $i'-i$ to make the jump, and consume energy $T\[i'\]$ at stone $i'$. If $A\[e',i'\]$ is already at most $A\[e,i\]+1$, then don't do anything, otherwise reduce its value to $A\[e,i\]+1$ because a shorter path has been found. (When reducing the value, also update the parent pointer, like we usually do with dynamic programming algorithms, so that an optimal solution can be recovered later.)

For example, when $i=0$, the only pair $(e,i)$ for which a value has been set is $(7,0)$, for which $A\[7,0\]=0$. With this current energy level of 7 at stone 0, a 1-jump gives $A\[6,1\]=1$, a 2-jump gives $A\[5,2\]=1$, a 3-jump gives $A\[5,3\]=1$ (note that it is $A\[5,3\]$, not $A\[4,3\]$ that is set to 1, because the worm of energy 1 is consumed at position 3, increasing the energy level by 1), a 4-jump gives $A\[3,4\]=1$, a 5-jump gives $A\[5,5\]=1$, a 6-jump gives $A\[1,6\]=1$, and a 7-jump $A\[6,7\]=1$. Then, one proceeds to $i=1$ and updates values of $A\[e,j\]$ for $j \> 1$. You'll notice that when you get to $i=5$ (say), the values of $A\[5,5\]$ and $A\[6,5\]$ have been set to 1 and 2, respectively, because it's possible to reach stone 5 using a single jump and energy level 5, or using two jumps and energy level 6.

At the end of iteration $i=n-2$, the algorithm would have the shortest path to stone $n-1$.
> 0 votes

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


# Question
Title: How does Sipser's proof that $0^n1^n$ is not regular work?
In Sipser's Introduction to the Theory of Computation this is how $0^n1^n$ is proved to be not regular

Example 1.73:

> Let $B$ be the language $\\{0^n1^n|n \ge 0\\}$
>
> We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. Let $p$ be the pumping length given by the pumping lemma. Choose $s$ to be the string $0^p1^p$. Because $s$ is a member of $B$ and $s$ has length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s = xyz$, where for any $i \ge 0$ the string $xy^iz$ is in $B$. We consider three cases to show that this result is impossible.
>
> * The string $y$ consists only of $0$'s. In this case, the string $xyyz$ has more $0$'s than $1$'s and so is not a member of $B$, violating condition 1 of the pumping lemma. This case is a contradiction.
> * The string $y$ consists only of $1$'s. This case also gives a contradiction.
> * The string $y$ consists of both $0$'s and $1$'s. In this case, the string $xyyz$ may have the same number of $0$'s and $1$'s, but they will be out of order with some $1$'s before $0$'s. Hence it is not a member of $B$, which is a contradiction.

In the first condition ($y$ consists only of $0$'s), why would the string $xyyz$ have more $0$'s than $1$'s?

Let's say that $|x|=p-2$ and consists only of $0$'s. $|y| = 1$ and $y=0$, $|z| = p$ and consists only of $1$'s. At this point $|y| \> 0$ and $|xy| \le p$.

In this case we would have the same number of $0$'s and $1$'s without violating any of the constraints of the pumping lemma. Of course $xyyyz$ would violate it then, but that's not his proof.

My question is, why does he state that the number of $0$'s is larger than the number of $1$'s for $xyyz$?

# Answer
If $x$ consists of $p-2$ zeros, $y$ is 0 and $z$ consists of $p$ ones, then $xyz$ is $0^{p-1}1^p$, not $0^p 1^p$. Hence, the particular partition you give is impossible. If $|xy| \< p$, then $z$ must take the remaining zeros.

Recall that we started with the assumption that the string $0^p 1^p$ was partitioned into three section $x,y,z$. This implies the number of zeros in $x,y,z$ must be $p$, and since $y$ is 0, $xyyz$ will have more $0$'s than $1$'s.
> 2 votes

# Answer
With the way you split your string, $|z|$ is $p +1$ and not $p$. Then, $z$ will be $01^p$ and not $1^p$. And with this, the proof stated by Sipser still holds.
> 1 votes

---
Tags: pumping-lemma
---


# Question
Title: Question about what exponentially small probability of success means in randomized algorithms
I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and contracts them instead of an edge. You then have to show that the probability of this modified algorithm suceeding is exponentially decreasing. I have solved the exercise and my result says that the probability of the modified algorithm succeeding is less than $(\frac{7}{8})^{\frac{n}{4}}$. The original algorithm says that there is a probability larger than $\frac{2}{n^{2}}$ for success. So we have:

* Original probability of success: At least $\frac{2}{n^{2}}$
* Modified probability of success: Less than $(\frac{7}{8})^{\frac{n}{4}}$

So what I am trying to decipher is what exponentially decreasing probability means exactly, for the modified algorithms probability we have a base of $\frac{7}{8}$ which is a proper fraction, and a exponent that increases when $n$ increases. So each time $n$ increases it clearly gets smaller and smaller. For our original probability we have $\frac{2}{n^{2}}$, this probability of success also gets smaller and smaller when $n$ increases, but this is not considered exponentially small? is it called polynomial small then?

# Answer
> 3 votes
A quantity is *exponentially small* (with respect to parameter $n$) if it is $\Omega(\alpha^n)$ and $O(\beta^n)$ for some $\alpha,\beta \in (0,1)$.

A quantity is *polynomially small* if it is $\Omega(n^{-a})$ and $O(n^{-b})$ for some $a,b \> 0$.

Let me stress that these definitions are not standard. There are otherwise to define these notions. For example, you could be more strict, and require an exponentially small quantity to be $\Theta(\alpha^n)$; or you could be more lax, and require a polynomially small quantity to be $\Omega(n^{-a})$ (without a matching upper bound). In many (but not all) cases, these are informal, qualitative concepts, which can be made precise in several different ways.

---
Tags: probability-theory, randomized-algorithms, monte-carlo
---


# Question
Title: Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode
> Let $L=\\{b^ma^n \mid \text{$m$ and $n$ are coprime} \\}$. Using Nerode's theorem, prove that $L$ is irregular.

From Nerode's theorem I know that $L$ is regular if and only if the number of equivalence classes of $R\_L$ (the relation defined in Nerode's theorem) is finite, so I need to prove that there are infinitely many equivalence classes.

The first thing that came to mind from $L$'s definition is using Dirichlet's theorem, hence I tried:

Let $w\_{m, i}=b^ma^i$, ($m,i$ are coprime), and I prove that for $j\ne i$, ($m, j$ coprime), $$w\_{m, i} \not R\_L w\_{m, j}$$ Let $z=a^{m+ni}$, ($n$ an integer promised by Dirichlet's theorem such that $m+ni$ and $m$ are coprimes), so $$w\_{m, i}z = b^ma^{m+ni+i}= b^ma^{m+(n+1)i}\in L$$ and $$w\_{m, j}z = b^ma^{m+ni+j}\not\in L$$ But this isn't necessarily true as $m$ and $m+(n+1)i$ might not be coprime and $m$ and $m+ni+j$ might be.

I know from previous exercises that I need to find $w\_i$ and show that for a word $z$ $$w\_iz\in L\text{ and }w\_jz\not\in L \space\space (i\ne j)$$ and therefore there are infinitely many equivalence classed, but I find coprimality difficult to handle.

# Answer
Let $P$ be the set of all primes. Show that the words $\\{b^p : p \in P\\}$ belong to different equivalence classes.
> 1 votes

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


title: Proving Undecidability of this Language

text:
# Question
Title: Proving Undecidability of this Language
Consider the language $$L = \\{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|\<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \\}$$ where $i$ and $j$ are fixed non-zero natural number for L

I am trying to prove that $L$ is **undecidable**.

My thought is that reduce the **Universal Language** to $L$. That is, I should describe an algorithm that transforms an input $\langle M,w \rangle$ into an output $\langle M' \rangle$ the code for another TM, then assume that there is a TM $M\_1$ that can decide $L$, which means $M\_1$ accepts $\langle M' \rangle$ iff $L(M') = L$. Then I design a TM $M\_2$ such that it first reads $\langle M,w \rangle$ and transforms it into $\langle M' \rangle$ according to the algorithm, and then it operates on $M\_1$. I am stuck on how to design the algorithm or the $M'$ so that I can create a contradiction such as universal language is recursive.

Am I on the correct track?

# Answer
> 3 votes
Fix $i$ and $j$ as two positive integers, as per your comment.

Consider the language $H$ containing all pairs $\langle T, y\rangle$ where $T$ is (encoding of) a Turing machine, $y \in \Sigma^\*$, and $T$ halts when its input is $y$.

Notice that, given $\langle T, y\rangle$, you can compute (the description of) a Turing machine $M^{(j)}\_{T, y}$ that, "waits" for $j$ steps, clears its tape, writes $y$, resets its head on the first position of $y$ (if any), and finally simulates $T$. I claim that $\langle T, y\rangle \in H \iff M^{(j)}\_{T,y} \in L$.

Indeed, if $\langle T, y\rangle \in H$ then $M^{(j)}\_{T,y}$ halts on input $x = \varepsilon$. Moreover, the number of steps executed is at least $j$, and $|x| = 0 \< i$. This shows that $M^{(j)}\_{T,y} \in T$. On the other hand, $\langle T, y\rangle \not\in H$ implies that the simulation perfomred by $M^{(j)}\_{T,y}$ does not halt, and hence $M^{(j)}\_{T,y} \not\in L$.

Since $H$ is a well-known undecidable language, so is $L$.

---
Tags: turing-machines, computability, undecidability, halting-problem
---


# Question
Title: why use bellman-ford instead of Dijstra in RIP routing?
The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra algorithm was published in 1959. Why RIP use Bellman-Ford instead of Djikstra? More generally, why routing protocols prescribe specific shortest path algorithm, could they be parametrics how the short path is calculated?

# Answer
Bellmon Ford is used by distance vector routing protocol (DVR). In DVR technique router keep knowledge of only next router which is adjacent that's why exchange of routing database only with neighbors. So in DVR no need of shortest path. But in DVR every router implicitly will able to find shortest path very slowly after stabilize. The main drawback of DVR technique is *slow convergence* and *count-to-infinity* problem.

But to keep the knowledge of entire topology router needs every other router's (neighbors as well as non-neighbors) routing database, because of *first convergence* and remove the *count-to-infinity* problem. So from one router to reach another we need shortest path algorithm. In this scenario link state (OSPF) routing protocol is example which does multicasting as well unicasting.
> 3 votes

---
Tags: graphs, shortest-path, computer-networks, communication-protocols, routing
---


title: Data Science vs Operations Research

text:
# Question
Title: Data Science vs Operations Research
The general question, as the title suggests, is:

* What is the difference between DS and OR/optimization.

On a conceptual level I understand that DS tries to *extract* knowledge from the available data and uses mostly Statistical, Machine Learning techniques. On the other hand, OR *uses* the data in order to make *decisions* based on the data, for example by optimizing some objective function (criterion) over the data (input).

I wonder, how these two paradigms compare.

* Is one subset of the other?
* Are they consider complementary fields?
* Are there examples that one field complements the other or they are used in conjuction?

In particular, I am interested in the following:

> Is there any example where OR techniques are used to solve a Data Science question/problem?

# Answer
While both Operations Research and Data Science both cover a large amount of topics and areas, I'll try to give my perspective on what I see as the most representative and mainstream parts of each.

As others have pointed out, the bulk of Operations Research is primarily concerned with making *decisions*. While there are many different ways to determine how to make decisions, the most mainstream parts of OR (in my opinion) are focused on modelling decision problems in a mathematical programming framework. In these kinds of frameworks, you typically have a set of decision variables, constraints over these variables, and an objective function dependent on your decision variables that you are trying to minimize or maximize. When the decision variables can take values in $\mathbb{R}$, the constraints are linear inequalities over your decisions variables, and the objective function is a linear function of the decision variables, then you have a linear program -- the main workhorse of OR for the past sixty years. If you have other kinds of objective functions or constraints, you find yourself in the realm of integer programming, quadratic programming, semi-definite programming, etc...

Data Science, on the other hand, is mostly concerned with making *inferences*. Here, you're typically starting with a big pile of data and you'd like to infer something about data you haven't seen yet in your big pile. The typical sorts of things you see here are: 1) the big pile of data represents the past results of two different options and you'd like to know which option will yield the best results, 2) the big pile of data represents a time series and you'd like to know how that time series will extend into the future, 3) the big pile of data represents a labelled set of observations and you'd like infer labels for new, unlabelled observations. The first two examples fall squarely into classical statistical areas (hypothesis testing and time-series forecasting, respectively) while the third example I think is more closely associated with modern machine learning topics (classification). Fun trivia: I believe that for a long time, the job title at Google for people doing what we now call Data Science was (is?) "Statistician".

So, in my opinion, Operations Research and Data Science are mostly orthogonal disciplines, although there is some overlap. In particular, I think that time-series forecasting appears in a non-trivial amount in OR; it's one of the more significant, non-math programming-based parts of OR. Operations Research is where you turn if you have a known relationship between inputs and outputs; Data Science is where you turn if you're trying to determine that relationship (for some definition of input and output).
> 10 votes

# Answer
This isn't a full answer, since mhum's is quite good in contrasting the differing *aims* of OR vs DS.

Rather, I want to address this comment of yours:

> I was wondering if, for example, one could use any OR techniques to solve DS problems.

The answer is yes. The clearest example that comes to mind is Support Vector Machines (SVMs).

To "fit" an SVM model to some data (which must be done before you can use it to infer predictions), the following optimisation problem must be solved:

> Maximize the dual,
>
> $$ g(a) = \sum\_{i=1}^{m} \alpha\_i - \frac{1}{2} \sum\_{i=1}^{m} \sum\_{j=1}^{m} \alpha\_i \alpha\_j y\_i y\_j x\_i^T x\_j,$$
>
> subject to the constraints
>
> $$ 0 \leq \alpha\_i \leq C, \qquad \sum\_{i=1}^n y\_i \alpha\_i = 0$$

This is a constrained optimisation problem, just like many in the field of OR, and it is solved using quadratic programming methods or interior point methods. These are generally associated with the field of OR rather than DS but this is an example of their wider applicability.

More generally, optimisation is key to many of the statistical and machine learning models employed in the field of DS, since the process of training these models can typically be formulated as a minimisation problem involving a loss/regret function - from the humble centuries-old linear regression model to the very latest deep learning neural network.

A good reference on SVMs is Bishop.
> 6 votes

# Answer
As a strategist, I've had the opportunity to work with both sides of the discipline. In trying to explain what OR and DS are to a qualitative MBA executive, my (overly) simplistic one line introduction for each

OR: economists that know how to code
DS: statisticians that know how to code.

In practical terms, how the two groups typically come together: the OR side develops the decision model, and the DS side figures out the appropriate data implementation to feed the model.

Each on their own, will rely on the theoretical traditions of their disciplines - together, they conduct experimentation to structure the data and refine the model in order to get to the true insights needed for optimal decisions. As each gets to know the other, their thinking and their language will typically converge.
> 3 votes

# Answer
I obtained my Operations Research degree from a military institution and have been using it for military applications for about 15 years. In that timeframe, Data Science has grown into a main-stream term referring to people with varying degrees of expertise in the data and information space. In the Department-of-Defense (DoD), Data-science is not very well defined, but yet, there is an understanding of wanting more of it, and there is an expectation that DS is crucial for data-architecting, data-normalization, ML, AI and facilitating analytics. Unfortunately, some decision makers perceive visualizations as being the end-state goal of analytics, but that is better left as a tangential discussion in the future.

Before DS became a main-stream term, Ops Researchers were used by the DoD to perform the data tasks that I mentioned above, but also to do Mathematical Programming, Optimization, Network optimizations (as in SCM, not computer networks), Network Interdiction and vulnerability analysis, and simulations for prediction and prescription, plus process testing and wargaming.

The Advances in Computer Science, Computer Hardware and Computing Power, plus the reduction of cost in those areas have now provided the necessary demand for a dedicated discipline to exploit data in the way that all our theories have only dreamed of since the era of vacuum tubes. I think for the most part ORs have been filling a void out of necessity, but not necessarily with the right standard discipline and expertise that it really merits. I don't mean to say that ORs can't do data science, or that we can't be experts on it. However, in my experience we (ORs) have been performing data-science tasks in order to support analytics (modeling, simulation, decision aides, etc...)

In general, and surprising, due to the age of the two disciplines, there is a better understanding in the Department-of-Defense of what Data Scientists do, than what ORs do. Probably because of the main-stream aspect of DS, and the current data-age we live in. To the sad and frustrating point where now OR has to defend its utility, since the wrong assumption is that DS can do all that ORs do.

The confusion is also due to the fact that Ops Research does not always produce a tool or data-product, but instead delivers analysis that may have used techniques that are not always advertised or highlighted as they are not the focus, but the results of the analysis itself. Also Ops Researchers tend to grow from a functional group and culture first, and then become ORs. This has a huge positive impact for the studies and analysis, but also does not give the ORs an obvious distinction within the team. Data Scientists, however, due to their "newness," average age and specific niche that they operate in, plus the fact that they can come in from outside the functional area and culture, they are automatically identified as an enabler and SME.

I hope that my experiences help answer the original questions or at least give a different perspective to better inform the group. I did not want to go technical as I think that there is a lot of overlap between the two disciplines, and we are all still trying to get better definitions as we settle in this space.

Cheers to the group,

p.s. I find this graphic useful in illustrating OR:
> 2 votes

# Answer
If you count ML and AI driven by ML as a part of Data Science(which some people do and some dont according to my experience, for instance Microsoft professional program in AI contains key aspects of Data Science+Machine learning(with both DL and RL) while Higher School of Economics presents practically same advanced parts of Microsoft cuuriculum as Advanced Machine Learning) then there are many similarities in mathematics that is used in both fields. For instance: Nonlinear Programming(Lagrange multipliers, KKT conditions...)--\>used for derivation of Support Vector Machines...Econometrics which is mostly based on Regressions---\> Regressions are key part of both Data Scinece in general and more specifically Supervised Learning...Statistics(normally found in OR Curriculum)---\>key for Data Science and Machine Learning as well...Stochastic Processes---\>very important in Reinforcement Learning...Dynamic Programming---\>again found in Reinforcement Learning...So,I would say there are some similarities with Data Science in general and pretty much similarities with ML. Of course, goals of these disciplines are different but there is a lot of similarities in mathematics that is being used in these disciplines.
> -2 votes

---
Tags: optimization, data-mining
---


# Question
Title: Find largest number of disjoint paths with lenght $k$ in a tree
Consider this problem from Jeff book

> Given a rooted tree $T$ and an integer $k$ as input, and it should compute the largest possible number of disjoint paths in $T$ , where each path has length $k$. Do not assume that T is a binary tree.

How we can use greedy approach to solve above problem?

# Answer
> 2 votes
You should add, as stated in the book, that, in a path, "all moves must move away from the ground" (meaning that a path cannot contains two children of the same node). That is an important information.

Now, you should consider a path from a leaf of maximal depth, delete it and rince and repeat.

For the correctness, consider a solution (a set of path of length $k$), and prove that there exists a solution of the same size with a path from a leaf of maximal depth.

For a detailled proof of correctness:

Let us prove by induction on the size of the tree that the algorithm is correct and optimal.

* base case: if the tree is empty, the algorithm stops as there is no path. Hence, it is optimal.
* inductive step: suppose the algorithm is correct for every tree of size $\leqslant n$, $n$ being a natural number. Let $T$ be a tree of size $n+1$ and $x$ be the leaf of maximum depth among all nodes of $T$ (if there are several such leaves, choose arbitrarily).

Since "all moves must move away from the ground", there exists an unique path starting from $x$, let's say $p=(x = x\_0, x\_1, x\_2, …, x\_k)$, where for $i = 0, …, k-1$, $x\_{i+1}$ is the parent of $x\_i$.

Let us show that there is an optimal solution containing the path $p$. Consider a solution $S =\\{p\_1, …, p\_m\\}$, where $p\_j$'s are paths of length $k$, and $m$ is maximal (meaning that $S$ is an optimal solution). One of the following is true:

+ one of the $p\_j$ is equal to $p$; then there is nothing to do.
    + the subtree rooted in $x\_k$ does not contain a node in a path $p\_j$. Then adding the path $p$ to $S$ would yield into a better solution, which means that $S$ wasn't optimal.
    + the subtree rooted in $x\_k$ contains a node in a path $p\_j$. Then no other path in $S$ contains a node in the subtree rooted in $x\_k$, because any path containing a node in this subtree contains $x\_k$ (because $x$ is supposed to be a leaf of maximum depth). That means that $(S\cup \\{p\\}) \setminus \\{p\_j\\}$ is a valid solution and of same size as $S$, hence optimal.

Now consider the tree $T$ where the subtree rooted in $x\_k$ is deleted. Such a tree $T'$ is of size $\leqslant n$, therefore we can use the induction hypothesis and the algorithm will return an optimal solution for $T'$, and adding the path $p$, we get an optimal solution for $T$.

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


# Question
Title: Consistent Hashing Algorithm Without Distribution / Load Balancing
I need some help finding or creating a consistent hashing algorithm with the following properties:

1. Given N buckets, only distributes keys to bucket N.
2. When number of buckets are increased from N to N+1, only keys in N have to be migrated to N+1.
3. When number of buckets are reduced from N to N-1, only keys in N are migrated to N-1

More context, I'm building a distributed hash table on an environment, where reliability is not an issue, it's guaranteed that each node would be up, and not added or removed unpredictably (I control the nodes being added or removed)

I don't want replication (replication of data is handled at a lower level), Also when nodes are removed, they can only be removed in a LIFO manner (node 2, cannot be removed before node 3)

I would appreciate any insight into this, and literature suggestions.

# Answer
The below is with 0-based indexing for the buckets.

* We assume we have some hash function $h(k) \rightarrow \[0,1)$.
* When looking up $k$ check the last node (index $N-1$) and the node $\lfloor Nh(k) \rfloor$.
* When inserting $k$ we always insert in the last node (index $N-1$).
* When $N$ changes to $N'$ (which can be either $N+1$ or $N-1$) redistribute all keys (in all buckets) as follows: $\lfloor N'h(k) \rfloor$.

Conceptually this uses a number-line $\[0,1)$ for the keys, where each bucket has the same size. Thus, e.g. when $N=4$, the buckets correspond to $\left\[0, \frac{1}{4}\right), \left\[\frac{1}{4}, \frac{2}{4}\right), \left\[\frac{2}{4}, \frac{3}{4}\right), \left\[\frac{3}{4}, 1\right)$. The last bucket can also contain keys which were directly inserted there, regardless of $h(k)$.

Looking at $N'=N+1$, then the range for $N'$, $\left\[1-\frac{1}{N+1}, 1\right)$, is completely contained in the previous range for $N$, $\left\[1-\frac{1}{N},1\right)$, so only keys in bucket $N$ can migrate to $N'$.

Similarly, when $N'=N-1$, then the previous range for $N$ is completely contained in the range for $N-1$ so it will be migrated to $N$. The new range for $N'$ is $\left\[1 - \frac{1}{N-1}, 1\right)$. The previous range for $N-i$ was $\left\[1 - \frac{i}{N}, 1 - \frac{i-1}{N}\right)$ so for $i \> 1$ we see that this doesn't overlap the new range for $N'$ (specifically that $1 - \frac{1}{N-1} \> 1 - \frac{i-1}{N}$). So we see that no other bucket migrates keys to $N'$.
> 2 votes

---
Tags: algorithms, distributed-systems, hash, hash-tables
---


# Question
Title: Integer linear programming formulation of boolean selection
Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases} 0 & \text{if} \ x = 0 \\ s & \text{if} \ x = 1 \end{cases}$. Currently in the problem, $s$ is the sum of $n$ boolean variables $x\_1 + x\_2 + \cdots + x\_n$ so I want to compute $x \land x\_1 + x \land x\_2 + \cdots + x \land x\_n$. However, computing each individual $x \land x\_i$ requires its own variable and constraints and I'm wondering if its possible to use a constant number of variables and constraints.

# Answer
> 3 votes
Use the three inequalities

$$0 \le y \le s$$

$$y \le Mx$$

$$y \ge s - M(1-x)$$

where $M$ is a large constant, chosen to be larger than the largest possible value of $s$ (e.g., $M=n+1$ in your example).

---
Tags: linear-programming, integer-programming
---


# Question
Title: Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$?

A relation between $\chi(G)$ and $\chi(\overline{G})$ is present here. But it is not providing the exact value of $\chi(\overline{G})$ in the general case. So my belief is that the answer to the question above is No or Unknown. I am looking for either of the following:

1. An algorithm that computes $\chi(\overline{G})$
2. A proof that $\chi(\overline{G})$ cannot be found in polynomial time from $\chi(G)$.
3. If 2 is true then is there any existing approximation and randomized solutions.

# Answer
> 5 votes
Morandini, NP-complete problem: partition into triangles shows that the following problem is NP-complete: Given a tripartite graph $G$ on $3n$ vertices (given together with a tripartition), determine whether $G$ contains $n$ vertex-disjoint triangles.

Since the graph $G$ is tripartite, we can construct an optimal coloring of $G$. First, we check whether $G$ is bipartite, and if so, we construct an optimal 2-coloring of $G$ (or a 1-coloring, if $G$ is empty). Otherwise, we use the given tripartition to construct an optimal 3-coloring of $G$.

We claim that $\chi(\overline{G}) = n$ iff $G$ contains $n$ vertex-disjoint triangles. Since each triangle in $G$ corresponds to an independent set in $\overline{G}$, if $G$ contains $n$ vertex-disjoint triangles (which necessarily cover all vertices of $G$), then we can color $\overline{G}$ using $n$ colors by coloring the $i$'th triangle with color $i$. Conversely, suppose that $\chi(\overline{G}) = n$. Since $G$ is tripartite, each color class of $\overline{G}$ contains at most 3 vertices (otherwise it would contain at least two vertices in the same part, which are connected by an edge in $\overline{G}$). Since $\overline{G}$ has exactly $3n$ vertices, each color class must consist of precisely 3 vertices, which form a triangle in $G$.

---
Tags: algorithms, complexity-theory, graphs, colorings, polynomial-time-reductions
---


# Question
Title: Would it make sense to use an array of linked lists for a Priority Queue, given a fixed number of priorities?
From what I can gather priority queues are typically implemented with heaps. If I have a small fixed number of priorities (such as 4), wouldn't a small array where each index represents the priority, and indexes into the associated linked list at that priority, be a more efficient implementation than using a heap, allowing O(1) time for all operations? Searching for the next element would be O(1) as only 4 indexes need scanning (beginning at index 0) to find a linked list that isn't empty.

I haven't seen this mentioned anywhere or in my course so am just curious if there's a reason this isn't done.

# Answer
Not only does it make sense, it's a common data structure in operating systems to implement the ready queue for tasks. Operating systems typically have a fixed number of priority levels, so it makes sense.

One optimisation if you have a lot of priority levels (say, 64 to 256 of them) is to also maintain a bit vector to represent which priorities have items in them. You can then use word operations (e.g. find first set) to find the highest-priority element.
> 16 votes

---
Tags: priority-queues
---


# Question
Title: Prove $REJECT\leq_mACCEPT$ and vice versa
a friend of mine sent me a question which he can't solve and I didn't succeed to solve it as well.

***Question:*** We define two languages:

$$ACCEPT=\\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\ accepts\ w \\}$$ $$REJECT=\\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\ \ halts\ on\ w\ and\ rejects\ it \\}$$

***Note:*** $\overline{ACCEPT} \neq REJECT$

The question is to prove that $REJECT\leq\_mACCEPT$ and vice versa.

***What I think:***

I had an idea to run $M$ on $w$ and return the opposite of what it returns but I think there's a problem because of the ***halts on w*** statement.

# Answer
> 1 votes
There might have been confusion on the meaning of "return the opposite of what it returns" when you run $M$ on $w$.

When $M$ runs forever, nothing can be returned by $M$. Then that rule does not make sense! Not only there is no way to specify "the opposite of" nothing, but also it is simply impossible to *return*, i.e., to halt.

By the way, note that there is huge difference between "halt and return nothing" and running forever. In the case of running forever, a running machine does not return anything, either. Note that "it returns nothing" might be *ambiguous*.

The right specification is to stipulate "return the opposite of what is returns when it halts". The condition "when it halts" should be present, although it might be skipped in sloppy writing or in well-understood context.

The better choice could be sticking to "accept", "reject", "halt" and "loop" and abandoning the word "return" when we are talking about decision problems.

---

Since the question involves Turing machines that can reject, let us define a Turing machine as an 8-tuple $\langle Q,\Gamma ,b,\Sigma ,\delta ,q\_{0},A, R\rangle$, where $Q,\Gamma ,b,\Sigma ,\delta ,q\_{0}$ are as usual and $A$ and $R$ are the set of accepting and rejecting states respectively. A Turing machines halts means it either accepts or rejects and vice versa.

Here is a clearer description of the wanted reduction.

Given $\langle M,w\rangle$, switch the set of accepting states and the set of rejecting states in $M$ to obtain a new Turing machine $M'$. More specifically, $M$ is the same as $M'$ except that each accepting state in $M$ will be defined as a rejecting state in $M'$ and each rejecting state in $M$ will be defined as an accepting state in $M'$. More formally, if $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q\_{0},A, R\rangle$, then $M'=\langle Q,\Gamma ,b,\Sigma ,\delta ,q\_{0},R, A\rangle$.

Let $f:\Sigma^\*\to\Sigma^\*$ be defined by $f(u)=\langle M', w\rangle$ if $u=\langle M,w\rangle$ and $f(u)=u$ otherwise.

We can check routinely that the map $f$ is a one-to-one Turing reduction from $REJECT$ to $ACCEPT$ as well as a one-to-one Turing reduction from $ACCEPT$ to $REJECT$.

---
Tags: formal-languages, turing-machines, reductions
---