# Question
Title: Lower bound of disjointness by discrepancy?
I need to show that $Disc\_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \\{0,1\\}^n \times \\{0,1\\}^n \to \[0,1\]$. Disjointness is defined as

$Disj(X,Y)=\left\\{ \begin{array}\[ll\]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$

The discrepancy for a function is defined as $Disc\_\mu(f) = \max\_R \\{Disc\_\mu(R,f)\\}$ over all rectangles $R$ and further

$$Disc\_\mu(R,f) = |\Pr\_\mu \[(x,y) \in R \wedge f(x,y)=1\] - \Pr\_\mu\[(x,y) \in R \wedge f(x,y) =0\] |.$$

I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.

The problem is given as an exercise without a solution in the book *Communication Complexity* by E. Kushilevitz and N. Nisan on page 40.

# Answer
> 1 votes
Let me clarify the question first.

* $\mu$ is a probability distribution over the sample space $S=\\{0,1\\}^n \times \\{0,1\\}^n$.
* A combinatorial rectangle (or just rectangle) $R$ is a subset of $S$ of the form $A\times B$, where $A\subseteq \\{0,1\\}^n$ and $B\subseteq \\{0,1\\}^n$.
* For all $x\in \\{0,1\\}^n$, we can think of $x$ as the characteristic vector of a subset of $\\{1, \cdots, n\\}$. That is, $x=(x\_1, x\_2, \cdots, x\_n)$ where $x\_i=1$ if and only if $i$ is in that subset. We may abuse $x$ to mean that subset.
* We define $Disj(x, y) = 1$ for $x,y\in \\{0,1\\}^n$ if and only if the subset $x$ and the subset $y$ are disjoint. ($Disj(x, y) = 0$ if and only if they are not disjoint.)

---

For the sake of contradiction, suppose that $Disc\_\mu(Disj) \< \frac{1}{2n+1}$.

So, $Disc\_\mu(S,Disj) = \left|\Pr\_\mu \[Disj(x,y)=1\] - \Pr\_\mu\[Disj(x,y) =0\] \right| \< \frac{1}{2n+1}\tag{1},$ and $Disc\_\mu(R\_i,Disj) \lt \frac{1}{2n+1}\tag{2},$ where $R\_i=X\_i\times X\_i$, $X\_i$ is the set of all $x\in \\{0,1\\}^n$ that are subsets of $\\{1, \cdots, n\\}$ that contain $i$.

Since $Disj(x,y)=1$ means $x,y\in X\_i$ for some $i$, $$\begin{aligned}\Pr\_\mu \[Disj(x,y)=1\] &\le\sum\_{i=1}^n\Pr\_\mu \[(x,y)\in X\_i\times X\_i\]\\ &=\sum\_{i=1}^n\left|\Pr\_\mu\[(x,y) \in R\_i \wedge Disj(x,y)=1\] - \Pr\_\mu\[(x,y) \in R\_i \wedge Disj(x,y) =0\] \right|\\ &=\sum\_{i=1}^n Disc\_\mu(R\_i,Disj) \lt \frac{n}{2n+1} \end{aligned}$$

Combining the inequality (1), we know that $$\Pr\_\mu \[Disj(x,y)=0\] \lt \frac {n+1}{2n+1}.$$

So $\Pr\_\mu \[Disj(x,y)=1\] + \Pr\_\mu\[Disj(x,y) =0\] \<1$. However, the left hand side should be 1 since $Disj(x,y)$ is either 1 or 0. That is a contradiction. QED.

# Answer
> 1 votes
You asked two questions. I'll answer the second. A rectangle is a set $R$ of the form

$$R = \\{(x\_1,\dots,x\_n) : \ell\_1 \le x\_1 \le u\_1, \dots, \ell\_n \le x\_n \le u\_n\\}$$

for some $\ell\_1,\dots,\ell\_n,u\_1,\dots,u\_n$.

---
Tags: lower-bounds, communication-complexity
---


title: radix-sort with different bases

text:
# Question
Title: radix-sort with different bases
So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16.

Does it follow the same idea? and i read somewhere that i need to pass the base number to the radix function but not sure why would that be needed? because if i have for example:

```
int arr[] = {0xAA, 0x2D , 0x4B, 0x5A, 0x322, 0x24, 0x2, 0x42};

```

it works perfectly. So not sure why i need to pass the base to the function.

# Answer
> 2 votes
Radix sort splits data into own digits of given size, you may choose the base in which data would be treated. If you have 64bit integer you may choose size of radix to be any number, say 2 bits, 4bits, 21bits, 32bits etc., but since computer stores digits as binary numbers it makes more sense to stick with power of two.
Also, you would like to omit modulo operator and use bit masks for efficiency purposes, which is not possible for other numbers.

You haven't described your code, but if it assumes 10 as default base, it is perfectly good, your code is in hexadecimal representation, which gets stored as binary and then treated as decimal based number for sorting. This doesn't change your code, just language feature to provide numbers like that (you can input octal number using 0 in front, say 056, but it will not change running time, but changing radix will).

---
Tags: sorting, radix-sort
---


# Question
Title: What is the time complexity of this method?
On CodingBat.com there's a problem that asks for the length of the longest sequence of repeating characters within a string:

(https://codingbat.com/prob/p179479)

---

Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same.

maxBlock("hoopla") → 2

maxBlock("abbCCCddBBBxx") → 3

maxBlock("") → 0

---

This is the solution I wrote:

```
public int maxBlock(String str) {

  int max = 0;

  for(int i = 0; i < str.length(); i++)
  {
    char c = str.charAt(i);
    int j = i + 1;
    int possibleMax = 1;

    // iterate through a "block"
    while(j < str.length() && str.charAt(j) == c)
    {
      possibleMax++;
      j++;
    }

    // if the block's length is greater than any found, save it
    if(possibleMax > max)
      max = possibleMax;
  }

  return max;
}

```

The time complexity is at least O(N) but I'm not sure if the while loop inside makes it O(N^2).

# Answer
> 0 votes
The worst-case time complexity is $O(n^{2})$.

Consider the example string "aaaaaaaaaa" — that is, 10 'a's. This happens to be the worse case edge scenario, because `j++` has to run for every remaining character in the string, at every position. When i=0, the `while` loop will run 9 times; when i=1, 8 times; so on until when i=N-1, the loop runs 0 times. Therefore, the total number of times the `while` loop has to run (over all `i`) is given by the sum from 0 to N-1, which, with arithmetic series, is $S = \frac{N}{2}(N-1)$. This simplifies to $\frac{N^{2}-N}{2}$; however, when writing time complexity with big-O notation, we ignore constant or slower-growing factors. Therefore, as $N$ grows asymptotically large, the total time complexity reduces to $O(N^{2})$, although in reality it is something closer to $O(\frac{N^{2}}{2})$.

Another way to look at it is that the outer `for` loop runs exactly $N$ times, and the number of times the inner `while` loop runs does depend on $N$ (and linearly at that), so the time complexity must be at least greater than $O(n)$.

---
Tags: time-complexity
---


# Question
Title: How many ways to express N as sum of 2, 3 and 5?
I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:

* N = 5 + 2
* N = 2 + 5
* N = 2 + 2 + 3
* N = 2 + 3 + 2
* N = 3 + 2 + 2

But most of I found on the Internet that the different position is different way to express N (as this link for expressing N as sum of 1, 3, 4). Following that link, I try following DP formula:

```
    f[0] = f[1] = 0 ;
    f[2] = f[3] = f[4] = 1;
    for(int i = 5; i < 100; i++) {
        f[i] = f[i-2] + f[i-3] + f[i-5];
    }

```

But it isn't correct, as N = 7, F\[N\] = 4. So what is the correct DP method for this problem?

**Hard version:** I also concern about **don't care order of way to express N**, such as N = 2 + 2 + 3 and N = 2 + 3 + 2 and N = 3 + 2 + 2 will be only count as 1 time.

*Note that I'm trying to solve above problem in complexity O(N).*

# Answer
> 2 votes
It looks like you're missing some considerations with respect to the base cases. Since you're starting your for loop at `i = 5`, you should have base cases set for `i = 0, 1, 2, 3, 4`. f\[0\] = 1 since there's 1 way to choose a set of numbers that sums to 0 — choose nothing. f\[1\] = 0 since there's no way to make 1 out of 2, 3, and 5. f\[2\] and f\[3\] are both equal to 1 because they are in your set. Finally, f\[4\] = 1, since 2+2 = 4. This gives output f\[7\] = 5, as shown in your example cases.

For the "harder version", I suggest you look up the coin change problem. The problem formulation is essentially the same — how many ways are there to make up a given sum using a set of coins? The basic idea, and the one that prevents doubly counting permutations of the same solution, is that for each coin or value, you consider whether or not you wish to include it in the current solution set. If so, you get closer to the sum, and you can choose to reuse the same coin/value. If not, the value of your solution stays the same, but you never use that coin/value again in that solution. The final number of ways is just the sum of these two possibilities. Note that this method does have a time complexity of $O(mn)$.

**Additional Links**

https://www.geeksforgeeks.org/coin-change-dp-7/

---
Tags: dynamic-programming, counting
---


# Question
Title: graphs - finding a shortest path length not achievable by breadth first search
supposedly for some graphs there exists valid shortest path lengths between two nodes of the graph that cant be constructed by breadth first search. what defines these shortest paths that breadth first search cant reach?

# Answer
BFS doesn't work well on graphs with weighted edges, or in other words, graphs where the cost to travel each edge isn't equal. The reason for this is that BFS implicitly assumes equal path lengths. At each step, all nodes adjacent to the current node get pushed into the queue, regardless of the edge weights. This results in a situation where the *number of edges traveled*, rather than any *actual edge weights*, reflects the "path length".

For example, consider a graph with 3 nodes A, B, and C; the edge from A to B AB's weight is 2, BC's weight is 3, and AC's weight is 100. Since A is 2 edges (AB, BC) away from C by taking the path through B, but only 1 edge away from C by taking edge AC, BFS would choose AC as the "shortest path" even though it's weight is significantly higher than the sum of AB and BC.

Instead, try algorithms such as Dijkstra's and Bellman-Ford that explicitly take into account the edge weights (e.g. with a priority queue in Dijkstra's). They tend to have a greater time complexity, but will return the correct answer.
> 1 votes

---
Tags: graphs
---


# Question
Title: Closed form solution of $T(n) = 5T(n-1) + n^2$
How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation?

$$T(n) = \begin{cases} 1 & n = 1\\ 5T(n-1) + n^2 & \text{otherwise} \end{cases}$$

# Answer
> 3 votes
> How to find the closed form solution of this equation?

This is linear nonhomogeneous recurrence relation of the form $a\_n = a\_n^{h}+a\_n^{p}$ where former expression in the right hand side is homogeneous solution while later one particular. Now, $a\_n^p$ becomes $p\_2n^2+p\_1n+p\_0$ whereas $a\_n^h$ becomes $\alpha5^n$. Now solve them.

Another straightforward approach is to recursively solve the equation as follows $$\begin{align\*} T(n) &= 5\cdot T(n-1)+n^2 \\ &= 5\[5\cdot T(n-2)+(n-1)^2\]+n^2 \\ &= 5^2T(n-2)+5(n-1)^2 + n^2 \\ &= 5^3T(n-3)+5^2(n-2)^2 + 5(n-1)^2 + n^2 \\ & \vdots\\ &= \sum\_{k=0}^{n-1}5^{n-k}\cdot k^2 \end{align\*}$$

> Is there a repeatable pattern for solving this equation?

The very word recurrence implies pattern.

---
Tags: recurrence-relation
---


title: Algorithms for Connect 4?

text:
# Question
Title: Algorithms for Connect 4?
Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following:

1) Minimax with Alpha-Beta Proning

2) A Neural Net

3) Machine Learning

My program has one second to make a move, so I can only branch out 2 moves ahead with Minimax. Which solution would best perform under 1 second?

I looked around the web, but couldn't find anything relevant.

Also, are there any other additional resources you suggest I have a look at?

# Answer
Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four.

I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can actually read the following:

"*In September 1988, James Allen determined the game-theoretic value through a brute-force search (Allen, 1998): a win for the player to move first. A few weeks later, in October 1988, connect-four was solved through a knowledge-based approach, resulting in the tournament program VICTOR (Allis, 1988; Uiterwijk et al., 1989a; Uiterwijk et al., 1989b). Recently John Tromp has calculated the game-theoretic value for all 8-ply connect-four positions (Tromp, 1993).*"

You will find all the bibliographical references in the Bibliography chapter of the PhD in case you need further information. Of these, the most relevant to your case is Allis (1998). A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins. M.Sc. Thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam. Go to Chapter 6 and you'll discover that this game can be optimally solved just by considering a number of rules. And this take almost no time!

So, my first suggestion would be for you to consider none of the approaches you mention but a knowledge-based approach instead. From what I remember when I studied these works, most of these rules should be easy to generalize to connect six though it might be the case that you need additional ones. However, if all you want is a computer-game to give a quick reasonable response, this is definitely the way to go.

Additionally, in case you are interested in trying to extend the results by Tromp that Allis mentions in the exceprt I was showing above or even to strongly solve the game (according to Jonathan Schaeffer's taxonomy this implies that you are able to derive the optimal move to any legal configuration of the game), then you should read some of the latest works by Stefan Edelkamp and Damian Sulewski where they use GPUs for optimally traversing huge state spaces and even optimally solving some problems.

Hope this helps,
> 8 votes

# Answer
If your looking for a suitable solution that you can implement quickly, I would go with the Minimax algorithm because this is the typical kind of problem where you would use Minimax.

If you choose Neural nets or some other form of machine learning, the runtime performance would probably be good but the question is would it find good moves?

To train a neural net you give it a data set of whit inputs and for each set of inputs a correct output, so in this case you might try to have inputs a0, a1, ..., aN where the value of aK is a 0 = empty, 1 = your chip, 2 = opponents chip. Indicating whether there is a chip in slot k on the playing board. The output would then be the best move to make in that situation. So how do you decide which is the best possible move? You could perhaps do a minimax to try to find some optimal move or you could manually create a data set where you choose what you think is a good move.

Still it's hard to say how well a neural net would do even with good training data. Also neural nets can be configured in different way, so you would have to do a whole lot of tweaking to get good results (if at all possible).

A lot of what I've said applies to other types of machine learning also.
> 2 votes

# Answer
### Monte Carlo Method

Aside from the knowledge-based approach and minimax, I'd recommend looking into a Monte Carlo method.

The idea is simple: in a given position, a player has at most 7 possible moves (fewer, as columns fill up). For each possible candidate move, make a copy of the board and play the move. Then, play the game making *completely random moves* until a terminal state (win, loss or draw) is reached. Take note of the outcome. Repeat this procedure as long as time remains for the algorithm to run.

Once the clock expires on the algorithm, compare the win/loss count for each candidate move and determine which option yielded the best win percentage. This is likely the strongest move in the position--make it!

**Advantages of the MC method:**

* Easy to implement. No domain-specific knowledge or heuristics are necessary (you could think of it as the opposite of the knowledge-based approach).
* You can search positions up to your precise time bound in CPU/clock time. There is no problem with cutting the search off at an arbitrary point. The longer time you spend, the stronger the AI.
* It's embarassingly parallel, so you could have a few worker threads running the simulations on their own copies of the board on different cores.

**Disadvantages:**

* There's no absolute guarantee of finding the best or winning move as is the case in an exhaustive search, although the evaluation of positions in MC converges slowly to minimax.
* In games with high branching factor or when supplying insufficient search time to the algorithm, performance can degrade. Monte Carlo Tree Search uses additional techniques beyond the pure MC method described here to help minimize the search space and is the algorithm behind Google's DeepMind victories in Go.

---

Here's a snippet from a MC function for a simple Connect 4 game (source) to give a sense of how straightforward a basic implementation is:

```
/**
 * drop pieces on a board randomly until the game reaches a terminal state
 *
 * @param connect4 *c4 a pointer to the game
 */
void c4rand_game(connect4 *c4) {
    while (!c4just_won(c4) && !c4full(c4)) {
        c4move(c4, rand() % c4->cols);
    }
}

/**
 * runs a simulation from current position to determine the best move
 *
 * @param connect4 *c4 a pointer to the game
 * @param simulations the number of simulations to attempt per move
 * @return the column of the best move or -1 if none found
 */
int c4simulate(connect4 *c4, int simulations) {
    int i, j;
    double ratio;
    double best_ratio = 0;
    int best_move = -1;

    for (i = 0; i < c4->cols; i++) {
        int wins = 0;
        int losses = 0;

        for (j = 0; j < simulations; j++) {
            connect4 cpy = c4cpy(c4);
            c4move(&cpy, i);
            c4rand_game(&cpy);

            if (c4just_won(&cpy)) {
                (c4->ply & 1) == (cpy.ply & 1) ? losses++ : wins++;
            }
        }

        ratio = losses > 0 ? (double)wins / losses : wins;

        if (ratio > best_ratio) {
            best_ratio = ratio;
            best_move = i;
        }
    }

    return best_move;
}

```
> 1 votes

# Answer
You could use a Neural Net, you'd just need to create a genetic algorithm to train it. No need to collect any data, just have it continuously play against existing bots.

The only problem I can see with this approach is that it's more of an approximation rather than the actual solution. You'd also need to give it enough of a degree of freedom so that it can adapt to any arbitrary strategy played.

If your approach is to have it be a normal bot, though I think this would work fine.
> 0 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, board-games
---


title: Why does $O(n \log n)$ seem so linear?

text:
# Question
Title: Why does $O(n \log n)$ seem so linear?
I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$.

However when plotting the computational time against the cardinality of the input set, it seems somewhat linear and computing $R^2$ confirms this somewhat. When then sanity checking myself by plotting $n$ on the $x$-axis and $n \log\_2 n$ on the $y$-axis with python, and plotting this it also seemed linear. Computing $R^2$ (`scipy.stats.linregress`) further confuses me, as I get $R^2=0.9995811978450471$ when my $x$ and $y$ data is created as so:

```
for n in range(2, 10000000):
    x.append(n)
    y.append(n * math.log2(n))

```

Am I missing something fundamental? Am I using too few iterations for it to matter? When looking at the graph at http://bigocheatsheet.com/ it does not seem linear at all.

# Answer
> 1 votes
Just some general observations.

* O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
* A Θ(n log n) running time can have many different components, for instance

$\qquad\displaystyle a \cdot n\log n + b \cdot n \log \log n + c \cdot \sqrt n + d \cdot n + e \cdot \log n + d$

While technically the linearithmic term dominates, if $a$ is small compared to the other coefficients you will have a hard time detecting it.
* Measuring wall-clock running time is noisy without end, inparticular because the coefficients mentioned above get skewed by platform details. Try investigating *counts*, for instance of a dominant operation or block.
* Linear regresssion *always works*. Since the "difference" between $n \log n$ and $n$ *is* rather small (also considering above point), it's not susprising you'd get a high confidence. Run linearithmic regression and compare!

---
Tags: algorithm-analysis, experimental-analysis
---


title: How to count in linear time worst-case?

text:
# Question
Title: How to count in linear time worst-case?
This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the array. There are some suggestions, but I'm looking for a way to do this in worst case linear time. More specifically:

> Given a list $A$ of $n$ elements with $k$ elements distinct, determine a list of tuples $U = \\{(x\_i, c\_i)\\}^k$ of all unique elements $x\_i \in A$ such that $c\_i$ is the count of element $x\_i$ in $A$.

Here are some (failed) ideas I've had and have been suggested:

1. *Balanced Binary Search Tree* \- With this it will take $O(\log k)$ to insert into the tree and increase values. After inserts we could do a tree traversal in $O(k)$. Thus, total time comes out to $O(n \log k)$ which is too slow.
2. *Hash Map* \- With this we can get $O(1)$ *expected* inserts and thus $O(n)$ *expected* time. However, this is still not $O(n)$ worst case.
3. *Empty Space Mapping* \- Find the minimum and maximum element in $A$. Allocate (but do *not* initialize) enough memory to cover this range. Use this memory basically as a hash map and include a random hash so that we don't try to access corrupted memory. This strategy presents issues. (1) It's probabilistic with very very very low probability of failing, but still not guaranteed. Using memory like this limits us to floating-point or integer constraints.
4. *Associative Arrays* \- There are many other associative arrays that can be used, similar to hash maps and BSTs, but I am not finding any that match these constraints.

Maybe there is some obvious method I am missing, but I also think it could be potentially not be possible. What are your thoughts?

# Answer
This is a nice question.

In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without counting the duplicities.

However, it is not clear whether it can be done in another computational model. It seems unlikely in any reasonable deterministic computational model.
> 6 votes

# Answer
There exist randomized algorithms whose expected running time is $O(n)$; or where the probability that the running time takes longer than $cn$ is exponentially small in $c$.

In particular, randomly choose a 2-universal hash function, then use it to hash all of the elements of the array. This achieves the stated running times, if you choose the length of the output of the 2-universal hash appropriately.

As another example, you can build a randomized algorithm whose worst-case running time is $O(n)$ (it always runs in linear time, no matter what) and has a probability of error of at most $1/2^{100}$. (How? Run the above algorithm, and terminate it if it runs longer than $cn$ steps for some appropriately chosen $c$.) In practice, that's good enough, as the probability that your computer outputs the wrong answer due to a cosmic ray is already much higher than $1/2^{100}$.
> 1 votes

# Answer
Your approach 3 can be made safe using a solution to exercise 2.12 of Aho, Hopcroft, and Ullman (1974) *The Design and Analysis of Computer Algorithms* as described, for example, in Using uninitialized memory for fun and profit.

Basically, in addition to your array of N elements with the counts you have two arrays of N elements and one auxiliary count to create a sparse set indicating which of the counts are valid.

In C-like pseudocode:

```
uint* a = malloc(n);
uint* b = malloc(n);
uint* c = malloc(n);
uint len = 0;

get_count(uint x) {
    uint idx = a[x];
    return idx >= 0 && idx < len && b[idx] == x ? c[idx] : 0;
}

increment_count(uint x) {
    uint idx = a[x];
    if (idx < 0 || idx >= len || b[idx] != x) {
        idx = len;
        len++;
        a[x] = idx;
        b[idx] = x;
        c[idx] = 0;
    }
    c[idx]++;
}

```

Practical implementation of the sparse set is discussed in this StackOverflow answer.
> 1 votes

---
Tags: algorithms, search-trees, hash-tables
---


# Question
Title: Hash function orders ships from closest to furthest from the origin
Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle).

We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to furtest away from the origin.

We want to have an **expected** time complexity of this ordering algorithm to be done in $\theta(n)$ time.

Each ship has a coordinate $(x,y)$, and so I want my hash function to be something like $\text{h((x,y)) = small index if close to origin, big index if farther}$.

What would be a hash function and algorithm that can run in expected $\theta(n)$ time?

I think my hash function should be something like the following, taking into account the distance:

$h((x,y)) = \sqrt{(x-0)^2 + (y-0)^2} = \sqrt{x^2+y^2}$

# Answer
You can't. This problem is as hard as sorting, so it'll need $\Omega(n \log n)$ time (in the comparison-based model); it's not reasonable to expect a linear-time algorithm for sorting.

The obvious solution is to sort the points by their distance from the origin. If the hash function computes the distance from the origin, well, then you're just sorting hash values.
> 1 votes

# Answer
Hash functions should be constant. Ships move. As soon as a ship moves, whatever hash based data structure you are using is now invalid.

And you can’t use hash functions for sorting.
> 0 votes

---
Tags: hash, hash-tables
---


# Question
Title: What is the 1's and 2's complement of 0.01101?
What is the 1's and 2's complement of 0.01101? I'm unable to find any details on this from google.

Basically how do we represent the floating points in 1's and 2's complement forms?

Even wikipedia only says that 1's complement is the inverted bits of binary representation. The examples only contain integer values. I couldn't find anything clear about what is the exact significance of this system. Hence, unable to deduce if the inverting bits applies to floating points also.

# Answer
One's and two's complement apply to (fixed-point) encodings of integers. They don't apply to floating-point numbers. Floating point is different.
> 3 votes

# Answer
Other answers have noted that the two's complement and one's complement operations are only defined on integers or bundles of bits.

Having said that, these are common operations applied to the mantissa of a floating-point number (e.g. in Goldschmidt's division algorithm). However what you're really doing here is applying it to a *fixed*-point number, where the binary point is fixed after the first digit.

So, for example, if x=0.01101 is a mantissa, its one's complement is 1.10010 and its two's complement is 1.10011 (i.e. 2-x).
> 1 votes

# Answer
If u want to find 1's complement of binary float numbers Use formula (r^n-r^-m-N) Eg 0.0110 Here r =2 base of binary no.

n is the number of digits in integer part but in this there is no digit in integer part so n=0 m is digit in fractional part N is our original Number

Now (r^n-r^-m-N) (2^0)-(2-4)-0.0110 (1)-(1/16)-0.0110 (1-1/16)-0.0110 (16-1/16)-0.0110 (15/16)-0.0110 (0.9375)-0.0110 Now we have convert. 0.9375 into binary which is =0.111 (0.1111)-(0.0110) 0.1001
> -1 votes

---
Tags: floating-point, number-formats
---


# Question
Title: Difference between auxiliary space v/s space complexity
I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$.

So, if someone asks me what's the Space complexity of merge sort, heapsort or insertion sort then what should I tell them $O(1)$ or $O(n)$?

Also, note in case of selection sort, I've read it's Space Complexity is $O(1)$ which is auxiliary space.

# Answer
> 7 votes
First consider the definitions below:

$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.

$\mathbf{Space \space Complexity}$ is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity $\textit{includes}$ input size.

---

I can see where your confusion comes from; usually, when we say "Space complexity of Mergesort" we mean its Auxiliary Space, because we obviously cannot improve the space we use for the input itself. As such, some of the statements in your question are not correct.

$\bullet$ Mergesort has Auxiliary space of $O(n)$ (in its common use) since you allocate a new array, and Space complexity of $O(n)$

An example between the two would be:

If we compare Quicksort and Mergesort, they both have a space complexity of $O(n)$ and run at $O(n\log n)$ time, but Mergesort requires Auxiliary space of $O(n)$ while Quicksort requires Auxiliary space of $O(1)$

Finally, to answer your question: usually the intention while asking about "space complexity" is indeed Auxiliary space, although there is some ambiguity here in regard to the formal definitions above. To be pedantic, you can separate the two space complexity types in your answer.

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


title: Turing machine - compare two words

text:
# Question
Title: Turing machine - compare two words
I have a simple turing machine with single tape. I need to compare two words `<w1>$<w2>$` and write output. Language is all letters and numbers.

I did comparation with the {a,b} language but there are more characters.

Is only solution do it one by one in different branches? I mean read / mark the letter (enter the letter branch), go to the second word and read /mark the same letter, go to the first word, repeat? My problem with this solution is, when I want to change something I need to remake all branches. The other problems are the error handling, when I do not find the right letter I don't want crash. How handle that?

# Answer
Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and forth, but the programming would be even worse.

And yes, in general you have to rewrite everything when you change something. There are no functions, procedures etc. that you can program in a modular way. In principle, though, you could use different, disjoint sets of states in different parts of your computation. If you change something in one part, you only need to adapt the "interface" where you move from one set of states to another.

If you do not find the right letter, in principle there is no problem with "crashing", because this probably means not accepting. If you want a "controlled" end, you can for example run to the right end of the input and stop there (stopping means entering a configuration where no more move is possible); if this kind of stopping for you is "crashing" you can also enter into an infinite loop.
> 3 votes

---
Tags: turing-machines, comparison
---


# Question
Title: Contradiction proof for inequality of P and NP?
I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

> We start off by assuming that $P=NP$. Then it yields that $\mathit{SAT} \in P$ which itself then follows that $\mathit{SAT} \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $\mathit{SAT}$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

# Answer
> Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$.

Sure.

> As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$.

No. *Polynomial* time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L \in NP$ we have $r(L) \< k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.
> 57 votes

# Answer
Suppose that $\mathrm{3SAT}\in\mathrm{NTIME}\[n^k\]$. By the nondeterministic version of the time hierarchy theorem, for any $r$, there is a problem $X\_r\in\mathrm{NTIME}\[n^r\]$ that is not in $\mathrm{NTIME}\[n^{r-1}\]$. This is an unconditional result that doesn't depend on any kind of assumption such as $\mathrm{P}\neq\mathrm{NP}$

Choose any $r\>k$. Suppose we have a deterministic reduction from $X\_r$ to $\mathrm{3SAT}$ that runs in time $n^t$. It produces a $\mathrm{3SAT}$ instance of size at most $n^t$, which can be solved in time at most $(n^t)^k=n^{tk}$. By our choice of $X\_r$, we must have $tk\>r-1$, so $t\>(r+1)/k$. This function grows without bound with $r$.

This means that there is no bound on how long it can take to reduce an arbitrary $\mathrm{NP}$ problem to $\mathrm{3SAT}$. Even if $\mathrm{3SAT}\in \mathrm{P}$, there's still no bound on how long those reductions can take. So, in particular, even if $\mathrm{3SAT}\in\mathrm{DTIME}\[n^{k'}\]$ for some $k'$, we can't conclude that $\mathrm{NP}\subseteq\mathrm{DTIME}\[n^{k'}\]$, or even $\mathrm{NP}\subseteq\mathrm{DTIME}\[n^{k''}\]$ for some $k''\>k'$.
> 8 votes

---
Tags: complexity-theory, time-complexity, p-vs-np
---


# Question
Title: Why can we (apparently) implement CFG parsers only using (N)DFAs?
I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be *nested*.

For parsing those files I am required to use a handcrafted parser written in C++. More specifically, I need to extend the given parser and lexer base classes in order to specify the language. Unfortunately, I have some serious doubts about the theoretical fundamentals behind these classes, which I would like to discuss/clarify here. So, let me first give a little introduction to the architecture of all this (note that unfortunately I am not allowed to post any code here, but I don't think it's necessary anyway) - see also **TL;DR** below.

*(Disclaimer: I would like to add upfront that after working with regular expression libraries (nowadays simply standard C++) and parser generators like ANTLR I am not at all a fan of this handcrafted solution and therefore my view might be a littled biased. I admit that I am neither a formal language specialist, nor have I dealt with any serious theoretical computer science topics beyond undergraduate level, and that itself has been a while. Still I am quite sure that the "parser" that I have to use is less than suboptimal and I doubt that it's even a parser in a "classical" sense)*

**Lexer:**

As one would expect, the lexer tokenizes some input stream using an underlying (N)DFA, whose transitions are specified by the user in the derived class. This would be something like `AddTransition(srcState, transition, dstState)`, where `transition` could be for example a string `"keyword"` -- a convenience function would then insert the respective transitions for each character `'k'->'e'->...`, you get the point...

I find this solution rather cumbersome as it requires one to explicitely define the automaton for each token recognized by the lexer, sometimes urging me to draw automata on paper instead of simply writing it down as a regular expression that would work similarly (but would be way easier to express). Not to mention EOL, EOF issues that need to be taken care of in each case.

But so far, I think the lexer does what a lexer is supposed to do: It recognizes a *regular language* defined by the user and tokenizes it to be passed to the parser.

**Parser:**

The parser has a far more uncommon structure, at least from my point of view. As a layman, I would expect a parser to be implemented using some sort of $LL(k)$, $LR$, $LALR$, ... structure for reading in the tokens provided by the lexer and that generates a parse tree which can then be further processed. Most importantly, I would expect a typical parser to be able to recognize *context-free* languages by using some sort of pushdown automaton (PDA) implementation or the like (please correct me if I'm wrong).

Instead, the parser is based on the same structure as the lexer, that is, it uses a NDFA whose transitions are defined by the user. The complexity is even worse than with the lexer class, sometimes requiring the user to manually define hundreds of states and transitions, which easily lead to hard-to-spot bugs. For example, very simple differences in the parsed code like `blah {` vs. `blah{` can lead to problems if transitions were not correctly defined. There are unit tests for these cases, but for some "technical" reasons for each grammatical rule with the similar underlying structure (e.g. to recognize `foo {...}` vs. `bar {...}`) the transitions need to be rewritten, therefore it's not enough to simply write and test if some construct `<keyword> { <content> }` works, but rather for each instance of `<keyword>` and `<content>` tests must be written. Of course, same applies to changes in the underlying grammar. Think of all the EOF, EOL etc. issues mentioned above - a nightmare!

But my *main* issue with this parser is the theoretical foundations it is built upon. It is supposed to read in languages which allow nested scopes surrounded by brackets (from my humble perspective, that's at least a context-free language). But the parser is built around a NDFA and as far as I know by the Pumping Lemma this is already an issue. In order to overcome the NDFA limitations, every automaton state may be assigned a callback function. For the states in question, these callbacks implement something like a bracket counter. For example, whenever a state for an opening bracket is reached, the counter is incremented and for a closing bracket, it is decremented accordingly.

This works fine so far, but wouldn't that already be a *PDA* rather than a DFA? I'm asking because the author insists on saying that the parser still has a pure NDFA structure and that it is a common misconception that NDFAs can't read nested structures, because that would only apply if one was going to have infinitely deep nesting. I admit I don't have too many arguments to argue that this is wrong, yet I find this statement very questionable, also because I've never seen any parsers in the wild which are implemented that way.

**TL;DR**

I have strong doubts that a parser which uses a simple (non-deterministic) Finite Automaton is suitable to parse languages with nested structures, assignments, variable definitions etc.. Since it doesn't apply *any* of the concepts commonly known from parsers (syntax trees, $LL$, $LR$ and their ilk) and simply uses callbacks to perform some action when reaching a state, I wonder if the term "parser" is correct at all. To me it seems more like a lexer on a higher level with lots of extensions to cope with corner cases.

***But what puzzles me the most is that so far it seems to work fine, despite all the manual effort required to define states and transitions*** (leave aside the code duplication issues etc.). Therefore I wonder if there is maybe a strong misconception from my side?

Where does one draw the line between DFAs and PDAs (wrt. implementation)? To me, the NDFA combined with the bracket counter (which in theory can be seen as a stack) works more like a PDA.

Can the construct explained above be really called a "parser"? The term "parser" is used so naturally in combination with ASTs, CFGs and $LL$, $LR$ etc. that I wasn't able to find any discussions on that topic in the internet. Feel free to ask in case I need to clarify something (I admit it's hard to explain as a non-native speaker and also without being able to show code).

# Answer
> 2 votes
We can't answer questions about your specific codebase. In general: A NDFA, by definition, has no memory other than the state of the automaton. It sounds like your program has additional memory/variables/state (e.g., the counters updated by the callbacks), which means your program is not implementing a NDFA; it is doing something more. A DFA with multiple counters is Turing-complete if you can do some minimal operations on them; see, e.g., https://en.wikipedia.org/wiki/Counter\_machine.

So why do we usually use parsers based on pushdown automata rather than counter automata? Because it is usually a nicer way to think about the problem. It's a very helpful abstraction to be able to write down the grammar of the language as a context-free grammar; that's natural and expressive and is easy to think about. Pragmatically, this decomposition of concerns (write down a declarative specification of the language as a context-free grammar; leave it up to someone else to construct a tool that turns this into a parsing implementation) has proven useful and powerful. In contrast, counter automata don't have those benefit. For instance, with an implementation based on counter automata, there is no separation of concerns between the spec and the implementation; the implementation is the spec.

# Answer
> 1 votes
Deterministic finite automata (and nondeterministic) can only recognize regular languages. If the parser can recognize context-free grammars then it is not a DFA or NFA.

To recognize context-free grammars the model must be at least as "powerful" as pushdown automata.

It seems the codebase is complicated so this may have been inadvertently implemented (especially if there are counters and other state). If the parser truly is a finite automaton then there will be a way to break it. A pure finite automata will store nothing other than its current state.

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


# Question
Title: How does sum of first $k$ integers equal $k(k+1)/2$
According to this video, he explains $$p = k(k+1) / 2$$ Where $p$ is the sum of the first $k$ natural numbers. I understand $k$ means times of repetition and $k+1$ is how it increments, but why does he divide by $2$? I can't justify it.

---

Here is what the video describes:

```
for (i = 1; i <= n; i++)
  p += i

```

$$\begin{array}{|c|c|} \hline i & p \\ \hline 1 & 1 \\ \hline 2 & 3 \\ \hline 3 & 6 \\ \hline 4 & 10 \\ \hline \vdots & \vdots \\ \hline i & i(i+1)/2 \\ \hline \end{array}$$

# Answer
> 6 votes
Let me tell you the story of young Carl Friedrich Gauss.

He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he asked the kids to add up the numbers 1 to 1000.

30 seconds later young Carl Friedrich had the answer: 500,500.

How did he do it?

He changed the order and added 1+1000, 2+999, 3+998 up to 500+501. Each sum is 1001, and there are 500 sums, so the result is 1001 * 500. Obviously k=1000, so this is (k+1) * k / 2.

You can use this for adding numbers in any arithmetic progression: sum = (first + last) * count / 2.

# Answer
> 0 votes
It is not an algorithm time complexity. The time complexity of the specified loop in the picture is $\Theta(n)$ (as it does $n$ add operation).

What you can see in the sum of $1 + 2 + ... + k$ can be proved easily by mathematical induction. You can verify that for $n = 1$ obviously. Now suppose it is true for $n$ $f(n) = 1 + 2 + ... + n = \frac{n(n+1)}{2}$. And try to prove for $n+1$. By the definition we know that $f(n+1) = 1 + 2 + 3 + ... + n + (n+1) = f(n) + n + 1$. From the induction assumption we will have $f(n+1) = \frac{n(n+1)}{2} + n+1 = (n+1)(\frac{n}{2} + 1) = \frac{(n+1)(n+2)}{2}$. The proof is completed.

# Answer
> 0 votes
And a completely different answer that can handle more cases:

Let’s say you are summing $3x^2 + 7x - 4$. You guess that the solution is something like $ax^3$. When you go from k-1 to k, the sum increases by $3k^2 + 7k - 4$. The formula increases by $a(k^3 - (k-1)^3)$ = $a(3k^2-3k+1)$. So you guess a=1.

So your formula starts with $k^3$. You subtract $a(3k^2-3k+1)$ from $3k^2 + 7k - 4$, leaving 10k - 5, and calculate the sum for this. Works for any polynomial.

Now all this was guessing, so you use complete induction to prove it.

---
Tags: mathematical-analysis
---


# Question
Title: Shifting and adding to get multiplication values?
multiplying by 33 --\> $2^5 + 2^0$ is same as (num \<\< 5) + 1

and by 65599 as (num \<\< 16) + (num \<\< 6) - (num \<\< 0)

How do you get these numbers though i.e. 16,6?? I know log can be used but Is there any other quicker way to do this?

EDITED\___________________

what I need to do is create a hash function such that I have to recursively multiply with numbers like 65599 or 33... hence the shift might be a better option

# Answer
Shifting left is the same as multiply by two.
Take number, say in your example 33, convert to binary, 100001, here 1\<\< 6 is the leftmost bit and 1 is rightmost bit. As you have noticed it is $2^0$.

Second example is handled manually, it is 10000000000111111, so at first you set leftmost bit, then notice that consecutive ones could be converted to 1000000 - 1.

Standard usage is to speed up multiplication by constant, so you precompute it and use in your code. It makes sense until additions, subtractions and bit shifts are cheaper on target machine than one vanilla multiplication.
Some bit twidlings are already present in compilers, other may break compilers ability to optimise more.

Such operation is good in static, compiled languages, like C. It may work on managed ones (with platform independent emulation of arithmetic operations), but makes little sense on interpreted languages like Python (unless you compile it).
> 1 votes

# Answer
I do not understand the piece of your question "--\> 25 + 20". I will ignore that, and explain the rest.

The easiest way is to look at a number in binary.

The binary for 33 is "100001".

Reading this from left to right, the digits represent (1\<\<5), (1\<\<4), (1\<\<3), (1\<\<2), (1\<\<1) and (1\<\<0). (1\<\<0) = 1. The last digit always represents (1\<\<0), which is 1. So, 33 can be expressed as 1\*(1\<\<5) + 0\*(1\<\<4) + 0\*(1\<\<3) + 0\*(1\<\<2) + 0\*(1\<\<1) + 1\*(1\<\<0). Since 1\*x=x, and 0\*x=0, this can be simplified to 33=(1\<\<5) + (1\<\<0).

So these are all the same:

* 33 * N
* ((1\<\<5) + (1\<\<0)) * N
* (1\<\<5)\*N + (1\<\<0)\*N
* (N\<\<5) + (N\<\<0)
* (M\<\<5) + N

You can compare this to base 10 - I'll use 135 as an example here. "\<

If we multiply 135\*3 (base 10), we might say "(3\*1) hundred + (3\*3) tens + (3\*5) ones = 300 + 90 + 15 = 405.

This method can be applied for any number, and will result in additions only. For the general case, any combination of powers-of-two that can be added or subtracted, can be added or subtracted in the same way. For example, 65599 in binary is "10000000000111111". I can see a long string of ones (at the end), so I would identify the lowest 1 in the series (in this case representing 1\<\<0), add it on here to make a simpler number, the subtract it again later:

* 65599 = 10000000000111111
* = 65599 +(1\<\<0) - (1\<\<0)
* = 65600 - (1\<\<0)
* = 10000000001000000 - (1\<\<0)
* = (1\<\<16) + (1\<\<6) - (1\<\<0)

Using addition only, you the shifts are cumulative. Since 1\<\<2 = (1\<\<1)\<\<1, you can follow these steps to multiply A\*B:

1. total=0
2. Convert A to binary - e.g. convert 65599 to "10000000000111111".
3. start at the most significant (left-most) bit (bit=binary digit) of A
4. If the bit you are looking at is a 1, then add B to total.
5. Regardless of what bit it is, multiply the total by 2 - a.k.a total=total\<\<1
6. If the bit of A you are looking is the least significant bit, stop here - total will be your answer.
7. Otherwise, look at the next bit (moving towards the right) of A, and go back to step 4.

This is how computers often multiply. Step 2 is unnecessary for computers, because that's how they store numbers all the time.

This is much quicker than multiplying by counting - you go around the loop one per bit, with 3-4 operations per loop - add B (if appropriate); double the total; move to the next bit, conditional-branch back if not complete. Since computers deal with set sizes (e.g. 64-bit), and the highest bit is shifted out into the "carry" flag, you can treat the carry as the check if you need to add or not. This means the above code reduces to:

* total=0
* do 64 times:
    + A = A\<\<1
    + if there was a carry from the above instruction, total=total+B
    + total=total\<\<1

If you're following these instructions, pad A with zeroes on the left, to 64 bits; then when you shift-left (i.e. add a bit to the right), then the left-most bit becomes the carry.
> 1 votes

# Answer
Fundamentally, you're just doing long multiplication, as you learnt in school except in binary, rather than decimal.

Decimal long multiplication uses the fact that, e.g., $$65599 = 6\times 10^4 + 5\times10^3 + 5\times10^2 + 9\times10^1 + 9\times10^0\\,,$$ and note that everything before "$\times$" is a decimal digit $0$$9$. In decimal, multiplication by $10^k$ is just shifting left $k$ digits and padding with zeros.

The binary version is using $$\begin{align\*} 65599 &= 2^{16} + 2^5 + 2^4 + 2^3 + 2^2 + 2^1\\ &= 1\times 2^{16} + 0\times2^{15} + 0\times 2^{14} + \dots\\,, \end{align\*}$$ where everything before "$\times$" is now a binary digit $0$$1$, which looks simpler but makes no real difference. And, in binary, multiplication by $2^k$ is just a shift.

But what you've actually done is observed that $2^5+2^4+2^3+2^1+2^0 = 2^6-1$, so $65599=2^{16}+(2^6-1)$. It's not actually essential that the things before "$\times$" are digits in the number base. You could equally do long multiplication in decimal by writing $$65599 = 6\times10^4 + 5\times10^3 + 6\times10^4 - 1\times10^0\\,.$$
> 0 votes

---
Tags: multiplication
---


title: Vertex Cover of size at most $\log n$

text:
# Question
Title: Vertex Cover of size at most $\log n$
Consider the following language: $$ L = \\{ G | G \text{ has a VC of size at most } \log n \\} $$

Does $L\in P$ or $L\in NPC$?

# Answer
> 5 votes
If you solve *Vertex Cover* with the simple branching algorithm, you achieve an FPT running time of $2^k \text{poly}(n)$, where $k$ is an upper bound for the solution you are looking for.

Substituting $k$ for $\log n$ gives you the answer you are looking for.

---
Tags: complexity-theory, vertex-cover
---


# Question
Title: How do you compute the Pareto Front of a set?
I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst and chose based on which one finished higher but whats better 3rd and 2nd, or 1st and 4th?

Pareto front is a set of nondominated solutions, being chosen as optimal, if no objective can be improved without sacrificing at least one other objective.

1. **(Energy Used, Weight)**

(30,20)

(50,30)

(10,40)

(20,50)

(40,10)

Diagram Showing the Table

# Answer
> 1 votes
A multi-objective optimization problem can be formulated as

\begin{align} \min\limits\_{\phi \in \Phi} & \quad \[f\_1(\phi), f\_2(\phi), \ldots, f\_m(\phi)\]^T \label{eq:mo-objectives} \\ s.t. & \quad g\_j(\phi) \leqslant 0,~j = 1, \ldots, J \label{eq:mo-constraints} \end{align}

Without loss of generality, assume that all objective functions are minimization functions. In this problem, the first equation represents the set of $m$ objective functions and the second denotes the problem constraints, which generate a polytope $\mathcal{P}$. Furthermore, $\Phi$ denotes the set of feasible solutions contained in $\mathcal{P}$ and $\phi \in \Phi$ represents a feasible solution.

A solution $\phi\_1 \in \Phi$ **dominates** another solution $\phi\_2 \in \Phi$ if and only if $f\_i(\phi\_1) \leqslant f\_i(\phi\_2)$ for all objective functions $\\{f\_1, f\_2, \ldots, f\_m\\}$ and $f\_i(\phi\_1) \< f\_i(\phi\_2)$ for at least one objective function $f\_i$.

A solution $\phi' \in \Phi$ is said to be **non-dominated** if and only if there is no solution $\phi \in \Phi$ such that $\phi$ dominates $\phi'$.

A non-dominated solution $\phi^\* \in \Phi$ is said to be **Pareto-optimal** if and only if, for all solutions $\phi \in \Phi$, $f\_i(\phi^\*) \leqslant f\_i(\phi)$ for all objective functions $\\{f\_1, f\_2, \ldots, f\_m\\}$ and $f\_i(\phi^\*) \< f\_i(\phi)$ for at least one objective function $f\_i$.

The **Pareto-front** is the set of the Pareto-optimal solutions.

---

We can derive a simple algorithm to compute the Pareto-front of a given subset of solutions $\Phi' = \\{\Phi'\_1, \ldots, \Phi'\_n\\} \subseteq \Phi$. This algorithm will be specifically designed for your case (two objectives), but can easily be generalized to any number $m$ of objective functions.

First of all, assume that the solutions in $\Phi'$ are ordered in increasing order of the first objective (energy used). In addition, ensure that, for a given value of *energy used*, the solutions are also ordered in increasing order of their second objective (weight).

1. Let $i \gets 1$.
2. Add $\Phi'\_i$ to the Pareto-front.
3. Find smallest $j\>i$ such that $\operatorname{weight}(\Phi'\_j) \< \operatorname{weight}(\Phi'\_i)$.
4. If no such $j$ exists, stop. Otherwise let $i \gets j$ and go to step 2.

---
Tags: algorithms, optimization, sets, pareto
---


title: Logic of multiple variables in ILP

text:
# Question
Title: Logic of multiple variables in ILP
Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?

# Answer
> 2 votes
There's a straightforward way to represent the logical AND of $n$ variables $x\_1,\dots,x\_n$: add the linear inequalities $y \ge x\_1+ \dots + x\_n-(n-1)$, $y \le x\_i$ for each $i$, and $0 \le y \le 1$.

---
Tags: logic, binary-trees, linear-programming, boolean-algebra, integer-programming
---


# Question
Title: Check whether all elements are different
Assume we have $n$ double elements $a\_1 \dots a\_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer between $1$ and $n$ and which can be calculate in $O(1)$ time. Let $m := \\{(i,j) : a\_j \neq a\_i \text{ and } h(a\_j) = h(a\_i)\\}.$

How can i check if all $n$ elements are different in $O(n+ |m|)$ time and $O(n)$ memory?

1) The naive approach would be to check all $n$ elements if there is another element with the same value, which requires $O(n^2)$ time.

2) A better way would be if i sort the elements, which needs $O(n \cdot \log(n))$ time and then check each adjacent pair of elements. In total it would be $O(n \cdot \log(n))$.

But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how.

# Answer
This sounds like an assignment, so I'll just give you a few things to think about:

* Using a hash table/hash map allows you to access elements in near $O(1)$ time. The only reason it's not exactly $O(1)$ is because of the collisions, $m$.
* Given two elements $a\_i$ and $a\_j$, if $h(a\_i) = h(a\_j)$, the two elements may or may not be equal. The hash table has to handle this collision in some way; you may then have to go back and check for actual duplicates.
* On the other hand, if $h(a\_i) \neq h(a\_j)$, it's necessarily true that the elements are NOT equal. $a\_i$ and $a\_j$ are stored in separate locations in the hash table.
* Think about the worst case test case; what would happen as you build up the hash table?
> 2 votes

# Answer
Quite interestingly, element distinctness problem has been asked recently, see here.

To summarize: A lower bound of $\Omega(n\log(n))$ can be proven via decision tree, therefore you were right to say approach 2) cannot be improved (if your only tool is comparing two elements).

---

In your problem, you need to use the fact $h(a\_i) \rightarrow \\{1 \dots n\\}.$ How?

1. Create $n$ bins $B\_1 ... B\_n$
2. Go through your array and map each $a\_i$ to the $j$-th bin, if $h(a\_i)=j$. Additionally, each bin saves all the indexes of the elements mapped to its respective value.
3. If for every $i$, $B\_i = 1$ you are done and can determine the set is distinct.
4. Else, for every $i$ s.t $B\_i \> 1$, you compare all the indexes of the elements that hash to $i$. If you find two that are equal, you can determine the set is not distinct. Continue until all collisions are checked, then determine the set is distinct.

It should be clear steps 1,2,3 take $O(n)$ in total, assuming $h$ outputs a value in constant time.

What about step 4?

For every "useless" comparison we make - that is a comparison between two distinct elements that hash to the same bin - there is some pair $(i,j)$ that fulfills $a\_i \neq a\_j$ and $h(a\_i) = h(a\_j)$, and we compare it only once.

So in step 4 we make a total of $m$ comparisons. Therefore the runtime would be $O(n+m)$.
> 2 votes

---
Tags: algorithms, hashing
---


title: Why isn't DIV necessarily in P?

text:
# Question
Title: Why isn't DIV necessarily in P?
In my formal languages class, we discussed DIV, defined as following:

$\mathrm{DIV} = \\{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 \< d \leq b$ }\\}$

($\langle\cdot\rangle$ means encoded, let's say as binary)

We were told that it isn't known whether DIV is in P and were tasked to prove it was in NP. I naively and mistakenly assumed that DIV was in P because of the following algorithm:

```
   On input <a,b>
   For all 1<d<=b
       check if d divides a.
       If so, accept.
   reject.

```

I thought that this algorithm would run in polynomial time because we do $b$ many divisions at worst. Division is polynomial time, therefore, $b$ many divisions is also polynomial time. (also note, $b \< a$, or DIV is trivially true, where $d = a$).

However, i was told that this algorithm is not polynomial time with respect to the input. I don't really understand this part. Something along the lines of since $a$ and $b$ are encoded in binary, the input is of order $O(\log n)$. And that means our b many divisions is actually $O(b) \cdot O(\text{divisions})$, and that $O(b)$ is $O(2^{\log b})$. However, isn't $2^{\text{log base $2$ of $b$}}$ the same as $b$? How is that not polynomial time?

# Answer
> 4 votes
When we say that an algorithm runs in polynomial time, we mean polynomial in the length of the input to the algorithm, i.e., the number of bits needed to represent the input. Suppose both $a$ and $b$ are at most $n$; then the pair $\langle a,b\rangle$ takes $\lg n$ bits to represent. So, an algorithm whose running time is $O(n)$ takes *exponential* time (exponential in $\lg n$). In particular, your algorithm is an exponential time algorithm.

The problem DIV is basically equivalent to the integer factoring problem. It is an open question whether there exists any polynomial-time algorithm for it, but many believe that there probably is no polynomial time algorithm for it.

---
Tags: complexity-theory, formal-languages, time-complexity
---


# Question
Title: Why is Graph Isomorphism downward self reducible?
To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing an oracle that solves graph isomorphism for (n-1) vertices.

To be clear, the oracle only tells 'Yes' or 'No'. It does not give us the isomorphism.

This problem appears as an exercise in Arora-Barak's chapter on Interactive Proofs.

---

How do I show that Graph Isomorphism is downward self-reducible?

My attempt is to start with an arbitrary vertex in $G\_1$ and guess its image in $G\_2$, and remove them and make an oracle call on the remaining graph. But now, I do not know how to proceed. These graphs being isomorphic may not necessarily mean that the original graphs are isomorphic.

# Answer
This answer shows how to prove an easier variation, the case of (undirected loopless) multigraph isomorphism.

### The problem of multigraph isomorphism is downward self-reducible

The simple idea is to merge two vertices in a way that distinguish those two vertices and edges involving them.

---

Let $G$ be a multigraph. If the sum of degrees of two vertices reaches the maximum, we will call an ordered pair of those two vertices a degree-maximum pair. For a degree-maximum pair $(u,v)$, construct $G\_{u,v}$ as follows.

* Its vertices are all vertices of $G$ except $u$ and $v$, together with a new vertex $u\_v$ which is understood as $u$ merged by $v$. Note that $G\_{u,v}$ has one less vertice than $G$.
* Its edges consists of two parts.

+ the edges of $G$ whose endpoints are neither $u$ nor $v$ with the same multiplicity. Let $m$ be the maximum multiplicity of these edges.
    + for all vertex $w$ of $G$ that is neither $u$ nor $v$, edge $\\{w, u\_v\\}$ with multiplicity that is the sum of the multiplicity of $\\{w,u\\}$ in $G$ and the product of $m+1$ and the multiplicity of $\\{w,v\\}$ in $G$.

It is easy to see that if we are given a multigraph $G'$ that is isomorphic to $G\_{u,v}$ for some multigraph $G$, we can reconstruct $G$ from $G'$ up to isomorphism.

---

Suppose we are given two graphs of $n$ vertices, $G$ and $H$. Use the oracle to compare $G\_{u,v}$ with $H\_{x,y}$ for all tuples $(u,v,x,y)$, where $(u,v)$ is a degree-maximum pair in $G$ and $(x,y)$ is a degree-maximum pair in $H$. Once the oracle return yes, we conclude $G$ and $H$ are isomorphic; otherwise the oracle always return no, in which case we conclude $G$ and $H$ are not isomorphic. It take polynomial time to construct $G\_{u,v}$ from $G$ or $H\_{x,y}$ from $H$. There are less than $n^2$ tuples. So the whole algorithm takes polynomial time. QED.

---

I am yet to find a proof that shows the problem of (non-multi)graph isomorphism is downward self-reducible.
> 1 votes

---
Tags: complexity-theory, reductions, oracle-machines, graph-isomorphism
---


title: Nim game tree + minimax

text:
# Question
Title: Nim game tree + minimax
**Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player alternatively thereafter does the same to some single stack when it is his turn to play. The game proceeds until each stack has either just one penny or two—at which point continuation becomes impossible. The player who first cannot play is the loser. Show, by drawing a game tree, whether any of the players can always win.**

Why is the state 6-1 not going to 3-3-1?If we have 6-1 pennies we can remove 3 pennies from the 6 stack and we have 3-3-1 pennies.So why isn't 3-3-1 not a child of 6-1?

# Answer
Because - according to the rules above - each player must divide a stack into two stacks that must be unequal.
> 3 votes

# Answer
(b) Assume two players, min and max, play nim (as described above). Min plays first.

If a terminal state in the search tree developed above is a win for min, a utility function of zero is assigned to that state. A utility function of 1 is assigned to a state if max wins the game.

Apply the minimax algorithm to the search tree to assign utility functions to all states in the search tree.
> 0 votes

---
Tags: artificial-intelligence, search-trees, game-theory
---


# Question
Title: How post correspondence problem is undecidable?
An undecidable problem is a problem that cannot have any algorithm to solve it.

Post correspondence problem can be solved using a brute force approach. Then how can it be an undecidable problem?

# Answer
> Post correspondence problem can be solved using a brute force approach.

No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm.

But the PCP allows us to use each domino as many time as we want, which makes the number of possible configurations infinite.

**Proof of undecidability:**
We will prove this by reducing "Acceptance problem of Turing Machine" to an instance of PCP. We already know that, acceptance problem of Turing Machine: $$ L^A = \\{ \<M,w\> | M \\:is \\:a \\:TM \\:and \\:M \\:accepts \\:w \\} $$ is undecidable. Hence, if our instance of PCP is decidable, acceptance problem of Turing Machine will also be decidable, A contradiction.
The reduction involves making dominoes for all possible configurations of a TM when run on the input string. A full reduction can be found here. Let me know in the comments, if you need any clarifications on the reduction.
> 6 votes

---
Tags: undecidability
---


# Question
Title: are they any implications if i reduce a sha256 result into 248 bits?
i am working a prototype using some cryptographic properties. the question is simple but perhaps deep enough for me to decide :

sha256 is a strong hash function, but i have space for 248 bits only. my guess is if i remove any 8 bits the resulting mySHA248 will keep all good properties with slightly less entropy/collision resistance.

# Answer
You will get slightly more collisions, which is not a problem in many use cases, but overall hash properties are preserved.

If some hash loses its properties by omitting last few characters (or any selected ones), then hash is flawwed by having internal correlated structure.

In fact, NIST publication effectively trims hash to desired number of bits.
> 1 votes

---
Tags: hash
---


# Question
Title: Why operating system needs interrupt stack, if it has process control block?
I'm reading about an operating system but some concept confuses me.

**What doesn't confuse me:**

When an interrupt or system call or processor exception occurs, it happens when user mode tries to switch to the kernel mode, the operating system uses PCB(process control block) to save needed stuff, namely - hardware completing previous instructions, saves program counter, stack pointer, registers, changes execution state and so on. For each process has a separate process control block. This seems logical.

**What confuses me:**

But after several subchapters, I've read that interrupt or system call or processor exception occurs, an operating system needs to save some information - program counter, stack pointer, registers, execution state and so on. But this time saves not in PCB, it saves in "interrupt stack". It also said for each process needs the separate location of "kernel stack".

After that appears a few questions:

* Is "interrupt stack" and "kernel stack" the same thing, just different named?
* If the operating system already has PCB, why it needs to use "kernel stack. Yes, for each process operating system has separate PCB. And
the separate location for each process in kernel stack.
* Does the operating system use both kernel stack and PCB? If it does, why not just one of these?
* What difference between PCB and kernel stack, if they are used for the same tasks

P.S Operating System Principles and Practice

# Answer
The operating system cannot continue using user-accessible memory when it is handling an interrupt, that program may be buggy, malicious, or worse. It may overwrite any part of its address space at any time. That includes the stack.

The stack is often a critical part of the execution of a program, so the operating system has no choice other than to switch to another stack, which the user mode program can't corrupt.

The PCB holds information about a task. When that task is not running, the PCB may hold the context.

There may be two different kinds of context saves, one for switching from one task to another, and one just for when it is preempted by an interrupt. The latter is held on the interrupt stack, which as mentioned is separate from the user mode stack for security and correctness reasons.

Unless there is some microarchitectural reason to have a special stack for interrupts, kernel stacks and interrupt stacks are very similar, only differing in when they are used. The specifics about the stack are implementation details.
> 1 votes

# Answer
The interrupt has nothing to do with a process. On a multi- processor system, a process can be killed five nanoseconds after starting to process an interrupt, and the PCB is gone. And with it, all the information about the interrupt that you stored.

You don’t want to mix up interrupts and switching between processes. They are independent.
> 1 votes

---
Tags: operating-systems, stacks, os-kernel
---


# Question
Title: In a DFA, does every state have a transition on every symbol of the alphabet?
If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?

# Answer
> 24 votes
You seem to have stumbled on a contentious issue. Apparently computer scientists like to argue. I certainly like to argue, so here goes!

My answer is an unequivocal: No. A deterministic finite automata does not need a transition from every state for every symbol. The meaning when $\delta(q,a)$ does not exist is simply that the DFA does not accept the input string.

While you can create a definition of DFA that requires that $\delta(q,a)$ does exist, it is simply not the case that a missing transition makes the resulting structure (whatever you call it) in any way *nondeterministic* as many of the commenters are claiming. If you are taking a course on automata theory then the next topic will be context-free languages and push-down automata where the distinction between nondeterministic and deterministic automata is crtical, and you need to use the correct definition of non-determinism.

Non-determinism is associated with having *more than one* legal transition.

I think we all agree with the following Wikipedia definition (which I'll show in just a second is slightly ambiguous):

A deterministic finite automaton $M$ is a 5-tuple, ($Q$, $\Sigma$, $\delta$, $q\_0$, $F$), consisting of

1. a finite set of states ($Q$)
2. a finite set of input symbols called the alphabet ($\Sigma$)
3. a transition *function* ($\delta : Q \times \Sigma \rightarrow Q$)
4. a start state ($q\_0 \in Q)$
5. a set of accept states ($F \subseteq Q$).

Let $w = a\_1 a\_2 \cdots a\_n$ be a string over the alphabet $\Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r\_0, r\_1, \ldots, r\_n$, exists in $Q$ with the following conditions:

1. $r\_0 = q\_0$
2. $r\_{i+1} = \delta(r\_i, a\_{i+1})$, for $i = 0, \ldots, n−1$
3. $r\_n \in F$.

The ambiguity, and the controversy is over the defintion of the transition function, $\delta$ (number "3" in the *first* bulleted list.) We all agree that what differentiates a DFA from an NFA is that $\delta$ is a function rather than a *relation*. But is $\delta$ a *partial function* or a *total function*?

The definition of the DFA works just fine if $\delta$ is a partial function. Given an input string, if you reach a state $q\_i$ with an input symbol $a\_j$ where there is no next state then the automata simply does not accept.

Moreover when you extend this definition to create the definition of push-down automata it will be the case that you *must* make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic.

If the partial function bothers you then here is a trivial transformation that makes $\delta$ a total function. (This transformation is *not* like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs. None of those facts is true of the subset construction algorithm.)

1. add a state $q\_{\mathrm{error}}$
2. for every pair $(q\_i, s\_j)$ where $\delta$ is undefined, define $\delta(q\_i, s\_j) = q\_{\mathrm{error}}$.

This automata has a $\delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.

## Edit, January 2019

Commenter @Alex Smart rightly critiques me for neither giving references, nor for explaining why we should care. So here goes:

The reason we *care* about the exact definition of determinism vs non-determinism, is that some classes of non-deterministic automata are more powerful than their deterministic cousins, and some classes of non-deterministic automata are *not* more powerful than their deterministic cousins. For finite automata and Turing machines the deterministic and non-deterministic variants are of equivalent power. For pushdown automata there are languages where the distinction is important: There are NPDA that accept the language, and no DPDA accepts the language. For the linear bounded automata the question is (or was last time I checked) open. The increase of power of NPDA over DPDA comes from allowing *multiple* transitions, not from turning the transition function from a total function to a partial function.

Books from the compiler community:

Aho and Ullman, *Principles of Compiler Design*, 1977: First defines NFA (page 88) with a transition relation, then (p. 90-91):

> We say a finite automaton is *deterministic* if 1. It has no transitions on input $\epsilon$. 2. For each state $s$ and input symbol $a$, there is at most one edge labeled $a$ leaving $s$.

Aho, Sethi, and Ullman, *Compilers, principles, tecniques, and tools*, 1988 reprint, is similar, it first defines NFA with a transition relation, then (p. 115-116):

> A *deterministic finite automata* (DFA, for short) is a special case of a non-deterministic finitie automaton in which ... there is at most one edge labeled $a$ leaving $s$.

(Note that in the comments @Alex Smart says, "the dragon specifically mentions that the function is total." I assume he is talking about the later edition with co-author Lam, which I don't have access to at the moment.)

Appel, *Modern Compiler Implementation in Java*, 1988 (p. 22):

> In a *deterministic* finite automaton (DFA), no two edges leaving from the same state are labeled with the same symbol.

Appel then goes on to explain that when using DFA to recognize longest matches we explicitly make use of the missing transitions to decide when to stop (p. 23):

> when a *dead* state (a nonfinal state with no output transitions) is reached, the variables \[which record the longest match we've seen so far\] tell what token was matched, and where it ended.

Books from the switching-theory community:

Kohavi, *Switching and Finite Automata Theory, 2/e*, 1978, p. 611 says:

> Because a state diagram describes a *deterministic* machine, the next state transition must be determined *uniquely* by the present state and the presently scanned input symbol.

I would typically interpret *uniquely* to mean "exactly one", not "no more than one". (I.e., Kohavi seems to be saying that determinism requires a total function)

Books from the theory-of-computation community:

Here it seems to be more common to define DFAs before NFAs, and require DFAs to have a total transition function, but then define NPDAs before DPDAs, and define "determinism" as being a restriction of the transition relation to having no-more-than-one entry for each state/symbol pair.

This is true of Hopcroft and Ullman, 1979, Lewis and Papadimitriou, 1981, and, especially of Sipser, 2006, who uses the definition of DFA pedagogically to introduce precise formal definitions, and explain their importance and explicitly says (p.36):

> the transition function, $\delta$, specifies exactly one next state for each possible combination of a state and an input symbol.

This seems to follow the historical development. Deterministic finite automata were introduced in the 40s and 50s. Non-determinisitc finite automata were introduced in the paper by Rabin and Scott, "Finite automata and their decision problems, *IBM J. Rsrch and Dvpt*, 3(2):114-125, 1959. Following earlier authors, Rabin and Scott define deterministic finite automata (which they call *ordinary* automata) as having a transition function "defined on the Cartesian product $s\times\Sigma$ of all pairs of states and symbols." (Which I would interpret as meaning a total function).

Interestingly Rabin and Scott, also define non-deterministic finite automata in terms of a total function! Page 120, Definition 9:

> A *nondeterministic (finite) automaton* ... is a system where ... $M$ is a function\[!\] of $S\times\Sigma$ with values in the set of all subsets of $S$.

That is: the transition function being total does not make the system deterministic!

Sipser 2006 follows Rabin and Scott and uses a total transition function from states/symbols to the power set of states for his definitions of non-deterministic finite automata, non-deterministic PDA, and non-deterministic Turing Machines, but skips the topic of deterministic PDA.

Both Hopcroft and Ullman, 1979, and Lewis and Papadimitriou, 1981 use partial functions in their definitions of deterministic PDAs. They first define NPDAs with a transition relation, and then when they get to PDAs, Lewis and Papadimitriou say (p. 135),

> A pushdown automaton is *deterministic*, intuitively speaking, if there is at most one transition applicable to each configuration.

While Hopcroft and Ullman say (p. 112):

> The PDA ... is deterministic in the sense that at most one move is possible from any ID.

# Answer
> 8 votes
As scaaahu notes in the comments, by a common definition, a deterministic finite automaton (DFA) must have a transition from every state on every alphabet symbol, i.e. the transition function $\delta(q,a)$ is defined for all $q \in Q$ and $a\in \Sigma$ where $Q$ is the set of states and $\Sigma$ is the alphabet.

Once you start leaving out transitions, or adding multiple transitions on the same symbol from the same state you have a *non*-deterministic finite automaton (NFA). NFAs also have an additional possibility, $\varepsilon$-transitions, where they can move from one state to another without reading a symbol from the input.

In terms of computability, NFAs are equivalent to DFAs - there's an algorithm to convert from an NFA to a DFA, and a DFA is just trivially an NFA that doesn't use any nondeterminism, so they both define the set of regular languages.

# Answer
> 7 votes
There are definitions of DFA along the lines of

> If $A$ is NFA and $|\delta(q,a)| \leq 1$ for all $q$ and $a$ (and if $\delta(q,\varepsilon) \neq \emptyset$, then $\delta(q,a) = \emptyset$ for all $a \in \Sigma$) then $A$ is DFA.

In that case, you don't need all transitions. If the automaton does not have a transition fitting the next input symbol, it rejects.

It is a nice exercise to show that both definitions are equivalent in terms of which languages can be accepted.

# Answer
> 0 votes
In the definition of DFA, every states should have all the alphabet that in £. For an example if the £={a,b,c} and Q={q0,q1,q2} , all of this states should have the all a,b,c symbols that transition to other state or same state.

# Answer
> 0 votes
The simplest answer for this is, you add **dead** state for **left symbol**. As in conversion from NFA to DFA, we get Φ transion for some symbols, which signifies we create Dead state for it.

---
Tags: terminology, automata, finite-automata
---


title: 2D peak reasoning to move to a half

text:
# Question
Title: 2D peak reasoning to move to a half
You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A\[i\]\[j\] are A\[i-1\]\[j\], A\[i+1\]\[j\], A\[i\]\[j-1\] and A\[i\]\[j+1\]. For corner elements, missing neighbors are considered of negative infinite value.

If someone has any understanding please share on how it decides which side to pick as that reduces complexity to $O(n \log n)$.

Solution is to consider the middle column, find its 1d maximum, then if it's not the peak, look at left and right side and pick a side which is larger. My doubt is, why is this algorithm correct?

---

Related material:

A) geeks link: https://www.geeksforgeeks.org/find-peak-element-2d-array/

B) mit This was shared in mit slides where it talks about 1d peak and then 2d peak 1) https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

2) its second link gives an working example but not the reasoning http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf shows a working

C) Stackoverflow There is also a StackOverflow discussion https://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time

My doubt is How Can it predict based on seeing left and right element accurately that it has to go to the bigger half. I tried it a lot of times and it always works. So I know it to be true. I then tried to create a counter example but I couldn't .

It's a very old question : I initiated a chat but it didnt helped so asking question here : https://chat.stackoverflow.com/rooms/192196/2d-peak

# Answer
The point is that we are not trying to find the global maximum element of the array, only a peak (that is, a local maximum).

Let's say that you look at the middle column and find its global maximum, and this maximum is not a peak, because the value to its left is larger. Then you know that the left half of the matrix contains a value that is larger than all of the elements of the middle column. Hence there is always a peak in the left half (for example, the global maximum of the left half, but we do not necessarily search for that).

The values in the right half are irrelevant; they could be larger or smaller, but we don't care. We only want to be sure that we do not recurse into a half that contains 0 peaks.
> 2 votes

# Answer
The algorithm from Geeks starts by finding the **maximum** element in the middle column (not the 1D-peak). Let us denote this element by $p\_m$ and the middle column by $c\_m$.

A peak found on the $\min$-side is **not** guaranteed to be a peak in the initial matrix; consider the case where the peak is found in the cell directly adjacent to $p\_m$.

A peak found on the $\max$-side will **always** be a peak in the initial matrix.

If the peak is found in the column directly adjacent to $c\_1$. It must be the maximum element in its column to be declared a peak, and therefore it must be greater than all elements in $c\_1$, and thus a global peak.

If the peak is not found in the column adjacent to $c\_1$, then it must also be a global peak.
> 0 votes

---
Tags: algorithms, arrays
---


# Question
Title: Counting inversions in an array of 1 to N
Is there a straightforward way to characterise the number of inversions in an array of length `N` having distinct elements, each element an integer from 1 to `N`?

It's for a constraint optimization problem, where the number of inversions needs to be minimized.

# Answer
> 2 votes
You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum\_{i=1}^{|A|}\sum\_{j=i+1}^{|A|}\[A\_j\<A\_i\]$$

Where $\[A\_j \< A\_i\] = 1$ when $A\_j \< A\_i$ and $0$ otherwise.

---
Tags: algorithms
---


# Question
Title: for two languages in $NP$ does one of them karp reducible to another?
$\forall A, B \in NP \implies A\<\_m^{poly}B. \lor B\<\_m^{poly} A.$

I want to know is there any work around this theorem? or is it correct?

# Answer
The theorem, as stated, is false: if $A=\emptyset$ and $B=\Sigma$, then we cannot reduce either of them to the other. If take either of $A,B$ to be non-trivial problems in $P$, the claim is true, which is not hard to show (see here). If either of $A,B$ is NP-complete, then the claim also holds by definition of NP-hardness.

So, the only case left is for problems $A,B\in NP-(NPC\cup P)$, the NP-intermediate problems. Note that such problems exist if and only if $P\neq NP$.

It would not be very surprising to me for two NP-intermediate problems to be incomparable, but this would be very hard to prove, as we currently do not have a good idea of what problems even could be NP-intermediate. So, it would seem that the full answer to your question is an open problem, but if I had to guess then I'd guess the answer is no.
> 3 votes

---
Tags: reductions, np
---


# Question
Title: Efficient method for generating the smoothing function
The smoothing function of a boolean function with respect to one of its variables is the disjunction of its cofactors. For example given a Boolean function F(a,b,c) the cofactors with respect to a are F(0,b,c) and F(1,b,c), the smoothing function with respect to a therefore is G(b,c) = F(0,b,c) + F(1,b,c).

Now, given a circuit for F, one simple method for creating the circuit for G is to make two copies of the circuit for F, hardwire the inputs for a as 0 and 1 in the two circuits respectively and then OR the outputs. However this will double the number of gates needed. If one needs to do this for several variables, then the size of the resulting circuit grows exponentially in the number of variables removed. What bothers me the most about this is that we are creating simpler functions (as judged by the number of variables and consequently the size of the truth table) with increasing number of gates. This leads me to think that maybe there is a well known way for creating a circuit for the smoothing function using fewer gates than in the original circuit.

For the purpose of this question, let us assume that the truth tables are too big to enumerate and the functions under consideration are not linear.

# Answer
> 2 votes
Suppose that we are substituting variable $x$.

You will have a lot of zeroes and ones in the circuit, so a simple simplification function should help a lot. Additionally a potentially large part of your circuit unrelated to $x$ might be duplicated, so I would suggest preventing its duplication in the first place.

First I would mark any inputs (including the constants $0$ and $1$) to the circuit that aren't $x$ as *unrelated*. Second, any gate that only has unrelated inputs is marked as unrelated itself. This is done repeatedly until the result is stable. Then, any unrelated subcircuit which has a related gate as parent is removed and replaced with a temporary variable (e.g. $t\_1, t\_2,$ etc) and it is for each temporary variable what circuit it corresponded to.

Then you should apply your smoothing function definition and minimize recursively using $S$, applying matching with priority from top to bottom:

$$\begin{align} S(0) &= 0\\ S(1) &= 1\\ S(\neg 0) &= 1\\ S(\neg 1) &= 0\\ S(a + b) &= \begin{cases} 1 & S(a) = 1 \vee S(b) = 1\\ 0 & S(a) = 0 \wedge S(b) = 0\\ S(a) & S(b) = 0\\ S(b) & S(a) = 0\\ S(a) & S(a) = S(b)\\ S(a) + S(b)&S(a) \< S(b)\\ S(b) + S(a)&\text{otherwise} \end{cases}\\ S(a \cdot b) &=\begin{cases} 1 & S(a) = 1 \wedge S(b) = 1\\ 0 & S(a) = 0 \vee S(b) = 0\\ S(a) & S(b) = 1\\ S(b) & S(a) = 1\\ S(a) & S(a) = S(b)\\ S(a) \cdot S(b)& S(a) \< S(b)\\ S(b) \cdot S(a)& \text{otherwise}\\ \end{cases}\\ S(\neg \neg a) &= S(a)\\ S(\neg a) &= \neg S(a)\\ S(a) &= a\end{align}$$

Note that all comparisons here are done simply on the symbolic formulas, with comparison done in any consistent order (such as an arbitrary lexicographic order). This minimization isn't very advanced, but runs very fast and fully eliminates any constants unless the entire circuit is constant. If your primitive gates aren't conjunction and disjunction you'll need a different minimization function, but I think the concept is clear.

After minimization is done you can add back the $t\_1, t\_2,$etc circuits and connect wherever they occur.

---

Practical algorithms aside, I don't believe that your intuition of the circuit becoming simpler is correct when truth tables are too large to be enumerated.

Let's do a napkin math calculation. Suppose you have 64 inputs and consider a 'reasonable' useful circuit any circuit with $\leq 10000$ binary gates, then there are $4\sum\_{g=0}^{10000}\sum\_{k=0}^{g} (64+k)^2$ possible circuits, assuming $4$ different gate types. That's approximately $2^{52}$ possible reasonably sized circuits.

There are $2^{2^{64}}$ possible truth tables. We haven't even scratched the surface of the surface of all possible circuits. There is plenty of space for combinations of reasonable circuits to blow up exponentially in size and I don't see reason to believe why they wouldn't - there's plenty of domain left to blow up into.

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


# Question
Title: Correctness of the Betweenness centrality formula
> Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is:
>
> $$\sum\_{s \neq v \neq t} \frac{\sigma\_{st}(v)}{\sigma\_{st}}$$
>
> Where $\sigma\_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma \_{st}(v)$ is the number of those paths that pass through $v$.

However it doesn't seem to me that the formula calculates what is defined. Why do we divide by the total number of shortest paths between $s$ and $t$ each time? Shouldn't we just divide by $2$ to compensate the fact that $s$ and $t$ will appear twice in different orders?

# Answer
> 3 votes
Suppose we want to quantify the extent to which $v$ is between $s$ and $t$. There could be a few ways.

One way to describe that extent is the probability of passing through $v$ if we want to reach from $s$ to $t$ by a randomly-selected shortest path. Assuming each shortest path is selected with equal probability, we will get $\frac{\sigma\_{st}(v)}{\sigma\_{st}}$, where $\sigma\_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma \_{st}(v)$ is the number of those paths that pass through $v$. In particular, the extent of $v$ between $s$ and $t$ is 0 if none of the shortest paths from $s$ to $v$ goes through $v$ while it is 1 if all of them must go through $v$.

Assigning the same weight to each pair of starting node and destination node, we can see that $\sum\_{s \neq v \neq t} \frac{\sigma\_{st}(v)}{\sigma\_{st}}$ measure the extent in which $v$ is the center of betweenness.

The graph is created by https://graphonline.ru/

If you use $\frac{\sigma\_{st}(v)}2$ to quantify the extent to which $v$ is between $s$ and $t$, there is no problem if you just care about $v$ considering $s$ and $t$ as fixed. However, take a look at the above graph.

* How much is $v\_3$ between $v\_0$ and $v\_4$? There are 3 shortest paths from $v\_0$ to $v\_4$, 2 of which pass through $v\_3$. We get $\frac{\sigma\_{v\_0v\_4}(V\_3)}2 = 2/2=1$.
* How much is $v\_5$ between $v\_0$ and $v\_6$? There is only 1 shortest path from $v\_0$ to $v\_6$, which passes through $v\_5$. We get $\frac{\sigma\_{v\_0v\_6}(v\_5)}2 = 1/2=0.5$.

Since $1\>0.5$, we would like to conclude that $v\_3$ is more between $v\_0$ and $v\_4$ than $v\_5$ is between $v\_0$ and $v\_6$. However, we can go to $v\_4$ without passing through $v\_3$ while we must pass through $v\_5$ to reach $v\_6$ by a shortest path. So $v\_3$ should be less between $v\_0$ and $v\_4$ than $v\_5$ is between $v\_0$ and $v\_6$. This simple example shows that it does not make much sense to divide by 2 or, in fact, any constant if we want to normalize the measurement.

### Exercises

**Exercise 1.** What are the centers of the graph above in terms of the betweenness centrality? (Note there could be multiple centers.)

**Exercise 2.** Suppose we define the betweenness centrality of $v$ as $\sum\_{s \neq v \neq t} \frac{\tau\_{st}(v)}{\tau\_{st}}$, where $\tau\_{st}$ is the total number of distinct edges in the union of all shortest paths from $s$ to $t$ and $\tau\_{st}(v)$ is the number of those edges that are also incident to $v$. Would you consider the above definition a better definition of betweenness centrality?

**Exercise 3.** Suppose we define the betweenness centrality of $v$ as $\sum\_{s \neq v \neq t} \frac{\rho\_{st}(v)}{\rho\_{st}}$, where $\rho\_{st}$ is the total number of distinct edges in the union of all shortest paths from $s$ to $t$ and $\rho\_{st}(v)$ is the number of distinct edges that are on a shortest path from $s$ to $t$ that passes through $v$. Would you consider the above definition a better definition of betweenness centrality?

# Answer
> 3 votes
> However it doesn't seem to me that the formula calculates what is defined.

The formula is right. The betweenness centrality is a value in an interval $\[0, \ldots, 1\]$. Thus, if the betweenness centrality of node $v$ is equal to $1$, then all shortest paths between two nodes of this graph pass through $v$. I will explain the correctness of this summation below.

---

> Why do we divide by the total number of shortest paths between s and t each time?

You are developing a summation of the percentages. This is needed to ensure that this sum will never exceed $1$. Suppose that you have $m$ different $s$-$t$ pairs of vertices in your graph. Thus, $\sigma\_{st} = m$ and your summation goes through all $m$ $s$-$t$ pairs.
One can note that the term $\sigma\_{st}(v)$ on this equation is binary (the shortest $s$-$t$ path passes through $v$ or not). Thus, if all $s$-$t$ paths go through $v$, you will have $m \cdot \frac{1}{m} = 1$.

---

> Shouldn't we just divide by 2 to compensate the fact that s and t will appear twice in different orders?

Indirectly, you're right. This formula measures the percentage of the shortest $s$-$t$ paths that pass through node $v$. In fact, a simple optimization of this algorithm for undirected graphs is to consider only $s$-$t$ paths where $s \< t$. However, you can't divide it by $2$.

---

Curiosity: The only graph topology who has a node with betweenness centrality equal to $1$ is a star graph, like the examples shown in the figure below.

---
Tags: graphs, social-networks, network-analysis
---


# Question
Title: Why was primality test thought to be NP?
To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $\sqrt{n}$, meaning that the complexity would be $O(\sqrt{n})$. In my opinion, $O(\sqrt{n}) \< O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?

# Answer
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.

$\bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.

$\bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $\log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=\log(p)$ and $\sqrt{p}=\frac{1}{2} \log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $\sqrt{p}$ will be $2^{\frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.

---

The question "Where exactly does the Primality problem lie" has been answered in the link here
> 7 votes

# Answer
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.

And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
> 0 votes

---
Tags: complexity-theory, time-complexity, np
---


title: MILP problem NP-hard proof

text:
# Question
Title: MILP problem NP-hard proof
Since a MILP problem is not necessarily NP hard. How could I demonstrate that a MILP problem is actually NP hard? There exists some smart and easy method to do that? Many thanks!

# Answer
> 2 votes
In general, a general MILP was proved to be NP-Hard. This is a well-known proof and can be easily found in any textbook (or even on Wikipedia).
However, you can see one specific MILP problem as an 'instance' of the general MILP problem. Thus, you still need to show its complexity.

---

In fact, several MILP problems are NP-Hard:

1. Elementary Shortest Path (if the graph has negative cycles)
2. Degree-constrained Minimum Spanning Tree
3. Vehicle Routing Problem

However, many others are shown to be solvable in polynomial-time:

1. Job scheduling
2. Minimum Spanning Tree
3. Aircraft scheduling problem

---

You can demonstrate that a MILP problem is NP-Hard in the same way you do with any other optimization problem.

All you need to do is to reduce an NP-Hard optimization problem $\sigma$ to your MILP, construct a solution for MILP, and shows a polynomial-time transformation of your obtained solution to a solution of $\sigma$.

Sadly, there is no standard technique or proof method that can be applied to show the complexity of any MILP problems and you need to use your creativity (and mathematical skills, in many cases) to proof the complexity of your problem.

---
Tags: optimization, np-hard
---