# Question
Title: Getting all vertices with fixed index in their topological ordering of a DAG
During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve.

There are typically more than one order of a topological ordering for any given DAG. Some vertices will always be in the same index regardless of the ordering. Find a linear algorithm to get all fixed vertices in the topological order for a DAG.

From what I've gathered, this means that that fixed vertex is related to all vertices after it in the ordering AND it depends on all vertices before it in the ordering.

I've been trying to work out a linear algorithm to get all of these vertices but I'm not sure how.

# Answer
> 3 votes
In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

## Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only **source** (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a **sink** (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

## Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with `false` values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F\[v\]$ is `true` if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially `false`, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

1. Fill $I$ with values by scanning the adjacency list of the DAG.
2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
    1. Remove a vertex $v$ from $Q$.
    2. If $s \> 1$ or $sinked$ is `true`, set $F\[v\]$ to `false`.
    3. If $v$ is a sink, set $sinked$ to `true`.
    4. For each neighbor $u$ of $v$ in the DAG, decrement $I\[u\]$ by 1. If after this, $I\[u\]$ becomes 0, insert $u$ to $Q$.
4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to `true`).

## Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.

## Note

This algorithm is a modification of Kahn's Topological sorting algorithm.

---
Tags: algorithms, graphs, graph-traversal, dag, topological-ordering
---


title: Closest pair of points in 3D

text:
# Question
Title: Closest pair of points in 3D
My professor mentioned that if we already know the divide and conquer algorithm for the closest pair of points in 2 dimensions it's easy to think of a similar algorithm for the 3 dimensions. But I am a bit confused as to what changes we have to make.

I think we'll divide the points in two sets based on the x coordinate, find the closest pair of points in each set (let's say that the minimum distance is δ) but instead of a strip (2δ width), since we have three dimensions we'll use a slab to compare the distance between point that exist in different sets. But I don't know what I have to do next.

# Answer
> 6 votes
As you say, you can split the points in two sets $A$ and $B$ of roughly the same size, depending on whether their $x$ coordinate smaller than or at least some threshold $x\_0$. Solve the problem recursively on $A$ and $B$ and let $\delta$ be the minimum distance between any two points in the same set.

Now, instead of a strip of width $2\delta$, consider a slab with width $2\delta$ (centered on $x\_0$) and with unbounded height and depth (towards the $y$ and $z$ axes).

Notice that a necessary condition for pair of points $p\_a \in A$ and $p\_b \in B$ to be at distance less than $\delta$ is that both $p\_a$ and $p\_b$ must belong to the slab.

Imagine subdividing this slab into cubes having side $\delta/2$, so that no cube crosses $x\_0$. Pick any point $p$ in the slab and consider the "supercube" $C\_p$ of side $2\delta$ centered in $p$. All points outside of $C\_p$ are either outside of the slab or are too far away from $p$ even when we just consider the difference of the $y$ or $z$ coordinates. The means that, if there is a point at distance at most $\delta$ from $p$, then it must belong to $C\_p$. However $C\_p$ intersects at most $5^3$ cubes. This means that for each point we only need to check the points in at most $5^3$ cubes.

How many points are there in these cubes? At most $5^3$. To see this notice that a cube cannot contain more than one point. Indeed, each cube is entirely contained in either $A$ or $B$ and the maximum distance between two points in the same cube is $\frac{\delta}{2} \cdot \sqrt{3} \< \delta$.

How do we check these points efficiently? Let's start with an observation: given a collection $S$ of points and some parameter $\delta$ with the guarantee that each points has at most constantly many points within distance $\delta$, the 2D-algorithm that you already know can be used to enumerate all pairs of points at distance at most $\delta$ in time $O(|S| \log |S|)$.

Take all the points in the slab and project them onto the 2d-plane perpendicular to the $x$ axis and passing through $x\_0$ (i.e., "squish the slab" along the $x$ axis). We only need to consider the pairs of points whose projections are at distance at most $\delta$. By the above argument, for each point there are there are at most $5^3$ other points within such distance.

But then we can use the 2D-algorithm to get a list of all pairs of points to check! This takes time $O(|S| \log |S|)$ where $|S|$ is the number of points in the slab. Let's be pessimistic and assume that all current points end up in the slab. We have the following recurrence equation, where $n$ denotes the number of points: $$ T(n) = 2T(n/2) + O(n \log n), $$ which has solution $T(n) = O(n \log^2 n)$ as you can see using the master theorem.

It turns out that you can be more clever in the selection of $x\_0$. You can pick, in time $O(n)$, a threshold that (i) splits the point in $A$ and $B$ such that $\min\\{|A|, |B|\\} \ge c n$ for some constant $c\>0$, and (ii) ensures that $S$ contains $O(n^{1-\epsilon})$ points for some constant $\epsilon\>0$. With this clever selection you get the following recurrence: $$ \begin{align\*} T(n) &\le T(cn) + T((1-c)n) + O(n) + O(n^{1-\epsilon} \log n^{1-\epsilon}) \\ & \le T(cn) + T((1-c)n) + O(n). \end{align\*} $$ This recurrence has solution $T(n) = O(n \log n)$. To see this you can notice that the recursion tree has depth $O(\log n)$ and that the overall time spent on the recursive calls on each level of the tree is $O(n)$.

See this paper for an explanation of how to select $x\_0$.

# Answer
> 2 votes
The 2D approach you know probably uses sorting. Here I describe how to do it without sorting. This approach is straightforward to generalize to higher dimensions.

Below, "$\delta$-close" means "the distance is at most $\delta$"

We divided the points based on the $x$-coordinate, found $\delta$, and now it remains to do the "merge" part. We consider the points that are $\delta$-close to the border. Several observations:

1. If $(x\_1,y\_1)$ and $(x\_2,y\_2)$ are $\delta$-close, then we have $|y\_1 - y\_2| \le \delta$.
2. For an integer $k$, let $S\_k = \\{(x,y) \mid y \in \[k, k+2\] \text{ and $(x,y)$ is $\delta$-close to the border}\\}$. If $(x\_1,y\_1)$ and $(x\_2,y\_2)$ are $\delta$-close, then, by Observation 1, there exists an integer $k$ such that both $(x\_1,y\_1) \in S\_k$ and $(x\_2,y\_2) \in S\_k$.
3. For any $k$, $|S\_k|$ is at most constant.

As a result, we have at most $O(n)$ non-empty $S\_k$. By Observation 2, it suffices for each non-empty $k$ to try all possible pairs of points from $S\_k$, which, by Observation 3, takes constant time.

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: The solution for the all-pair shortest path problem on unweighted and undirected graph
The multi-source shortest path problem for unweighted and undirected graph is as follows: Given an unweighted and undirected graph, find the length of the shortest path between any pair of vertexes.

A straightforward method is to use BFS starting from each vertex, as the time complexity of BFS is *O*(*V*+*E*), the total time consumption is *O*(*V*(*V*+*E*)). My problem is: **Are there other algorithms for the problem with better time complexity?**

# Answer
> 2 votes
This paper shows how to solve the problem in time $O(n^{\omega} \log n)$, where $\omega \< 2.372$ is the matrix multiplication exponent.

This means that you have a better algorithm than repeated BFS when $|E|$ is asymptotically larger than $ \frac{n^{w-1}}{\log n}$, for example when $|E| = \Omega(n^{1.372})$.

---
Tags: graphs, shortest-path
---


# Question
Title: Time complexity of optimal algorithm for solving this problem
Given an $N\times N$ matrix $M$ whose elements are integers, find the largest element that occurs in each row of the matrix.

I tried using hashtable as follow:

Idea is to use hash-table(let's call it $ht\_1$) to keep track of count of occurrence of each element. Now, To handle case where element repeats in same row we use another hash-table(call this $ht\_2$). Now before performing increment in $ht\_1$ we check whether this element is already occurred in this row itself or not. If not then and then we perform increment in $ht\_1$.

Then once you finish processing whole array as just described make one more pass on array and this time keep track of max element which have exactly $N$ occurrence as noted by $ht\_1$.

So overall this runs in $O(N^2)$ expected time.

But Because use of hash-table worst case time complexity is still $O(N^4)$.

Now, I wonder can I do better than this? Means is there any way to solve in $O(N^2)$ in worst case.

Note: There is no other constraint on this.

# Answer
$O(n^2 log n)$ is easy: Create a sorted array of the items in the first row. Lookup the items in the second row in this array using binary search, and remove items that were not present. Same with the third row etc. The last remaining item is the largest one present in evert row. The main effort is $n^2$ lookups in an array of size n.

Using a hash table probably makes it $O (n^2)$, especially if you make the hash table say size 3n (which adds only a constant factor). Not guaranteed but likely faster than a O(n^2 log n) array.
> 4 votes

# Answer
* Hash the first row and associate a flag to every element. $O(n)$.
* For the next rows,

+ Reset all flags $O(n)$,
    + Scan the row and set the flags of the elements already in the hash $O(n)$,
    + Delete the elements with a flag reset $O(n)$.

In the end, you are left with the values that appear in every row. Total $O(n^2)$.

---

For a simpler version, sort the rows in-place and perform merges of the top row and the next with removal of the elements of the top row not matched.

Worst-case $O(n^2\log n)$ guaranteed.

Alternatively, storing the common elements in a balanced tree though still worst-case $O(n^2\log n)$, will become faster and faster as the first row empties.
> 1 votes

---
Tags: algorithms
---


# Question
Title: A question about the graph theory or data structure and algorithms
I would like to ask this question as I am not sure about the answer.

Let $G=(V,E)$ be a connected, undirected graph, and let $x,y\in V$ be two different vertices. Let $A$ be the problem of finding the shortest simple path between $x$ and $y$, and let $B$ be the problem of finding the longest simple path between $x$ and $y$. Which of the following statement about $A$ and $B$ is true?

1. Both $A$ and $B$ can be solved on polynomial time
2. $A$ is not known to be solvable in polynomial time but $B$ can be solved in polynomial time
3. $A$ can be solved in polynomial time but $B$ is not known to be solvable in polynomial time
4. It is known that both $A$ and $B$ can be solved in polynomial time
5. It is not known whether either $A$ and $B$ can be solved in polynomial time

I think option 3 is correct because the time complexity for finding the shortest path between two nodes is $O(n^2)$ but for $B$, I am not sure.

Could you please explain? Thank you so much

# Answer
> 0 votes
Problem $A$ can be solved in polynomial time. Problem $B$ is NP-hard. This means that options 2 and 5 are certainly false.

We don't know whether option 1 is true. If it is true is, then P=NP.

Option 3 is currently true (but might become false in the future if P is proven to be equal to NP).

Option 4 is currently false but might become true in the future (if P is proven to be equal to NP).

If we live in a world where P=NP then both option 1 and option 3 are currently true.

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: The math behind converting from any base to any base without going through base 10?
I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still not sure if I have it right. I have the converting from a larger base to a smaller base down okay because it is simply take first digit multiply by base you want add next digit repeat. My problem comes when converting from a smaller base to a larger base. When doing this they talk about how you need to convert the larger base you want into the smaller base you have. An example would be going from base 4 to base 6 you need to convert the number 6 into base 4 getting 12. You then just do the same thing as you did when you were converting from large to small. The difficulty I have with this is it seems you need to know what one number is in the other base. So I would of needed to know what 6 is in base 4. This creates a big problem in my mind because then I would need a table. Does anyone know a way of doing this in a better fashion.

I thought a base conversion would help but I can't find any that work. And from the site I found it seems to allow you to convert from base to base without going through base 10 but you first need to know how to convert the first number from base to base. That makes it kinda pointless.

Commenters are saying I need to be able to convert a letter into a number. If so I already know that. That isn't my problem however. My problem is in order to convert a big base to a small base I need to first convert the base number I have into the base number I want. In doing this I defeat the purpose because if I have the ability to convert these bases to other bases I've already solved my problem.

Edit: I have figured out how to convert from bases less than or equal to 10 into other bases less than or equal to 10. I can also go from a base greater than 10 to any base that is 10 or less. The problem starts when converting from a base greater than 10 to another base greater than 10. Or going from a base smaller than 10 to a base greater than 10. I don't need code I just need the basic math behind it that can be applied to code.

# Answer
> 68 votes
This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that **a number is not its digit representation**. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a sequence of sounds which you make when you communicate a number). What is confusing you is the fact that you never *see* a number but always its digit representation. So you end up thinking that the number *is* the representation.

Therefore, the question to ask is not "how do I convert from one base to another" but rather "how do I find out which number is represented by a given string of digits" and "how do I find the digit representation of a given number". Once we have the answers, it will be easy to answer the original question, too.

So let us produce two functions in Python, one for converting a digit representation to a number, and another for doing the opposite. Note: when we run the function Python will of course *print on the screen* the number it got in base 10. But this does *not* mean that the computer is keeping numbers in base 10 (it isn't). It is *irrelevant* how the computer represents the numbers.

```
def toDigits(n, b):
    """Convert a positive number n to its digit representation in base b."""
    digits = []
    while n > 0:
        digits.insert(0, n % b)
        n  = n // b
    return digits

def fromDigits(digits, b):
    """Compute the number given by digits in base b."""
    n = 0
    for d in digits:
        n = b * n + d
    return n

```

Let us test these:

```
>>> toDigits(42, 2)
[1, 0, 1, 0, 1, 0]
>>> toDigits(42, 3)
[1, 1, 2, 0]
>>> fromDigits([1,1,2,0],3)
42

```

Armed with conversion functions, your problem is solved easily:

```
def convertBase(digits, b, c):
    """Convert the digits representation of a number from base b to base c."""
    return toDigits(fromDigits(digits, b), c)

```

A test:

```
>>> convertBase([1,1,2,0], 3, 2)
[1, 0, 1, 0, 1, 0]

```

**Note:** we did *not* pass through base 10 representation! We converted the base $b$ representation to the number, and then the number to base $c$. The number was *not* in any representation. (Actually it was, the computer had to represent it somehow, and it did represent it using electrical signals and funky stuff that happens in chips, but certainly those were not 0's and 1's.)

# Answer
> 27 votes
I think the best way to understand this is in discussion with an alien (at least as an analogy).

**Definition** *$x$ is a number in base $b$* means that $x$ is a string of digits $\<b$.

**Examples** The string of digits 10010011011 is a number in base 2, the string 68416841531 is a number in base 10, BADCAFE is a number in base 16.

Now Suppose I grew up on the planet QUUX where everyone is taught to work in $q$ for their whole lives, and I meet you who is used to base $b$. So you show me a number, and what do I do? I need a way to interpret it:

**Definition** I can *interpret* a number in base $b$ (Note: $b$ is a number in base $q$) by the following formula

$$\begin{array}{rcl} \[\\!\[\epsilon\]\\!\] &=& 0 \\ \[\\!\[\bar s d\]\\!\] &=& \[\\!\[\bar s\]\\!\] \times b + d \end{array}$$

where $\epsilon$ denotes the empty string, and $\bar s d$ denotes a string ending in the digit $d$. See my proof that addition adds for an introduction to this notation.

So what's happened here? You've given me a number in base $b$ and I've interpreted it into base $q$ without any weird philosophy about what numbers truly are.

**Key** The key to this is that the $\times$ and $+$ I have are functions that operate on base $q$ numbers. These are simple algorithms defined recursively on base $q$ numbers (strings of digits).

---

This may seem a bit abstract since I've been using variables rather than actual numbers throughout. So let's suppose you are a base 13 creature (using symbols $0123456789XYZ$) and I am used to base 7 (which is much more sensible) using symbols $\alpha \beta \gamma \delta \rho \zeta \xi$.

So I've seen your alphabet and tabulated it thus:

$$\begin{array}{|c|c||c|c||c|c|} \hline 0 & \alpha & 1 & \beta & 2 & \gamma \\ 3 & \delta & 4 & \rho & 5 & \zeta \\ 6 & \xi & 7 & \beta\alpha & 8 & \beta\beta \\ 9 & \beta\gamma & X & \beta\delta & Y & \beta\rho \\ & & Z & \beta\zeta & & \\ \hline \end{array}$$

So I know that you work in base $\beta\xi$, and I know what base 7 number any digit you write corresponds to.

Now if we were discussing physics and you were telling me about fundamental constants (say) $60Z8$ so I need to interpret this:

$$\begin{array}{rcl} \[\\!\[60Z8\]\\!\] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ \end{array}$$

So I start by multiplying out $\beta \zeta \times \beta\xi$ but this is grade school stuff for me, I recall:

**Quux multiplication table**

$$\begin{array}{|c|cccccc|} \hline \\ \times & \beta & \gamma & \delta & \rho & \zeta & \xi \\ \hline \beta & \beta & \gamma & \delta & \rho & \zeta & \xi \\ \gamma & \gamma & \rho & \xi & \beta\beta & \beta\delta & \beta\zeta \\ \delta & \delta & \xi & \beta\gamma & \beta\zeta & \gamma\beta & \gamma\rho \\ \rho & \rho & \beta\beta & \beta\zeta & \gamma\gamma & \gamma\xi & \delta\delta \\ \zeta & \zeta & \beta\delta & \gamma\beta & \gamma\xi & \delta\rho & \rho\gamma \\ \xi & \xi & \beta\zeta & \gamma\rho & \delta\delta & \rho\gamma & \zeta\beta \\ \beta\alpha & \beta\alpha & \gamma\alpha & \delta\alpha & \rho\alpha & \zeta\alpha & \xi\alpha \\ \hline \end{array}$$

so to find $\beta \zeta \times \beta\xi$ I do:

$$\begin{array}{ccc} & \beta & \zeta \\ \times & \beta & \xi \\ \hline & \xi & \gamma \\ & \rho & \\ \beta & \zeta & \\ \hline \delta & \beta & \gamma \\ \gamma & & \\ \end{array}$$

so I've got this far

$$\begin{array}{rcl} \[\\!\[60Z8\]\\!\] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \beta \gamma + \beta\beta \\ \end{array}$$

Now I need to perform the addition using the algorithm which was mentioned before:

$$\begin{array}{ccc} \delta & \beta & \gamma \\ & \beta & \beta \\ \hline \delta & \gamma & \delta \\ \end{array}$$

so

$$\begin{array}{rcl} \[\\!\[60Z8\]\\!\] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \beta \gamma + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \gamma \delta \\ \end{array}$$

and continuing this way I get $$\[\\!\[60Z8\]\\!\] = \zeta\delta\xi\gamma\rho.$$

---

In summary: If I have my own conception of number in terms of base $q$ strings of digits, then I have way to interpret your numbers from base $b$ into my own system, based on the fundamental arithmetic operations - which operate natively in base $q$.

# Answer
> 11 votes
This is a refactoring (Python 3) of Andrej's code. While in Andrej's code numbers are represented through a list of digits (scalars), in the following code numbers are represented through a list of **arbitrary symbols** taken from a custom string:

```
def v2r(n, base): # value to representation
    """Convert a positive number to its digit representation in a custom base."""
    if n == 0: return base[0]
    b = len(base)
    digits = ''
    while n > 0:
        digits = base[n % b] + digits
        n  = n // b
    return digits

def r2v(digits, base): # representation to value
    """Compute the number represented by string 'digits' in a custom base."""
    b = len(base)
    n = 0
    for d in digits:
        n = b * n + base[:b].index(d)
    return n

def b2b(digits, base1, base2):
    """Convert the digits representation of a number from base1 to base2."""
    return v2r(r2v(digits, base1), base2)

```

To perform a conversion from value to representation in a custom base:

```
>>> v2r(64,'01')
'1000000'
>>> v2r(64,'XY')
'YXXXXXX'
>>> v2r(12340,'ZABCDEFGHI') # decimal base with custom symbols
'ABCDZ'

```

To perform a conversion from representation (in a custom base) to value:

```
>>> r2v('100','01')
4
>>> r2v('100','0123456789') # standard decimal base
100
>>> r2v('100','01_whatevr') # decimal base with custom symbols
100
>>> r2v('100','0123456789ABCDEF') # standard hexadecimal base
256
>>> r2v('100','01_whatevr-jklmn') # hexadecimal base with custom symbols
256

```

To perform a base conversion from one custome base to another:

```
>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'

```

# Answer
> 5 votes
Fundamental operation of base convertion is the `toDigits()` operation of @AndrejBauer answer. However, to make it there is no need to create a number in the internal representation of the numbers, which is basically a conversion from and to base 2 representation. You can make the needed operations in the original base representation.

So the first step is to do repetitive modulo division operation

```
def convertBase(n,original_base,destination_base):
    digits = []
    while not is_zero(n):
        digits.insert(0,modulo_div(n,original_base,destination_base))
    return digits

```

As the internal representation is digits, one has to make a specilaised function for testing zero

```
def is_zero(n):
    for d in n:
        if d != 0:
            return False
    return True

```

Eventually one has to make the modulo\_div operation which is actually the standard division by destination base as we learnt at school.

```
def modulo_div(n,original_base,destination_base):
    carry = 0
    for i in range(len(n)):
        d = n[i]
        d+=original_base*carry
        carry = d%destination_base
        d=(d//destination_base)
        n[i] = d
        #print(i,d,carry)
    return carry

```

just a test check to verify the code is correct:

```
print(convertBase([1,1,2,0], 3, 2))
#[1, 0, 1, 0, 1, 0]

print(convertBase([1, 0, 1, 0, 1, 0], 2, 3))
#[1, 1, 2, 0]

```

# Answer
> 1 votes
You can convert from base n to base 10 without any conversion to some intermediate base.

To convert from base n to base 9, for example, you take the algorithm for conversion to base 10, and replace “10” with “9”. Same for any other base.

# Answer
> 0 votes
I know an easy way to do base conversion that doesn't require a computer program. It's by defining a way to convert from any base to base 2 and vice versa and then coverting from one base to another base by first converting from the first base to base 2 then converting from base 2 to the other base. 2 is so easy to multiply or divide by in any base.

To convert from any base to base 2, all you have to do is recognize that for any number, if you take its base 2 notation and start from 0 and then for each digit in order from left to right double if that digit is zero and double than add 1 if that digit is 1, you get to that number itself. Now given that number in any base, you can divide by 2 in that base to get a quotient and remainder. If the remainder is 1, the last binary digit is 1 and if the remainder is 0, the last binary digit is 0. Divide by 2 again. If the remainder is 1, the second last digit is 1 and if the remainder is 0, the second last digit is 0 and so on until you get a quotient of 0.

To convert from base 2 to any base, all you have to do is in that base, start from 0, then for each binary digit going from left to right, double in that base if that digit is 0 and double then add 1 in that base if that digit is 1.

# Answer
> 0 votes
There is one not-so-useful special case:
Pairs of bases where each is a power of their GCD.

You can just consider symbol groups "the size of their LCM" and use a *lookup table* \- recoding more than handling numbers.

# Answer
> 0 votes
```
    // Let's look at the number 11201 in base 3
    // which we will represent as (11201),3
    //
    // (11201),3 = ( ),7
    //
    // 3^4 3^3 3^2 3^1 3^0
    //   1   1   2   0   1
    //
    // The "amount" of number we have in any given base
    // can be computed as per the following algorithm:
    //
    // begin_psuedocode
    // ans = 0;
    // ans = ( 1 * 3^4 ) + ans;
    // ans = ( 1 * 3^3 ) + ans;
    // ans = ( 2 * 3^2 ) + ans;
    // ans = ( 0 * 3^1 ) + ans;
    // ans = ( 1 * 3^0 ) + ans;
    // end_psuedocode
    //
    // or, otherwise stated:
    //
    // begin_pseudocode
    // ans = 1;
    // ans = ( ans * 3 ) + 1;
    // ans = ( ans * 3 ) + 2;
    // ans = ( ans * 3 ) + 0;
    // ans = ( ans * 3) + 1
    // end_pseudocode
    //
    // first step in converting to new base, is to
    // represent input number in input base, for this example, base 3
    // ((((1*10 + 1)10 + 2)10 + 0)10 + 1)
    //
    // since arithmetic works in any base
    // we simply convert each number to the new base
    // and our above equation will still hold true
    // the magic of aritmetic and math
    //
    // so the next step is to
    // map equation to the output base, for this example, base 7
    // ((((1*3 + 1)3 + 2)3 + 0)3 + 1)
    //
    // lastly, to determine the number in the new base,
    // we actually process each computation in the equation, in the new base
    //
    // ans = 1
    // ans = ans * 3 + 1 = (1*3) + 1 = 3 + 1 = 4
    // ans = ans * 3 + 2 = (4*3) + 2 = 15 + 2 = 20
    // ans = ans * 3 + 0 = (20*3) + 0 = 60 + 0 = 60
    // ans = ans * 3 + 1 = (60*3) + 1 = 240 + 1 = 241
    //
    // So finally, we have that
    // (11201),3 = (241),7

```

For full implementation of algorithm, see: https://github.com/primetimenumberline/BaseSwap/blob/master/Program.cs

Live demo over at: https://numbertheory-baseswap.netlify.app

Sample outputs:

https://i.stack.imgur.com/hytsi.png

https://i.stack.imgur.com/uL9Wr.png

https://i.stack.imgur.com/TRdst.png

---
Tags: algorithms, arithmetic, number-formats
---


# Question
Title: Algorithm to find best order for items on pages with a fixed height
I am looking for an algorithm to find the best order of items to fit on pages. Consider the following case, we have a page with the *height = 300* We have images with the following heights - *\[150,200,100,150,300\]*

So I want to find the best order for this images in order to fill the page. For example:

**First page**: 150 - 150 **Second page**: 200 - 100 **Third page**: 300 **Fourth page**: 150

Are there any algorithms to solve this task?

Have tried to find algorithms but only have an idea to just solve it via several iterations over an array.

# Answer
This sounds like it might be the bin packing problem. If so, the problem is NP-complete, but there are many methods for heuristics, approximation algorithms, etc., which you can read about and apply in your setting.
> 1 votes

---
Tags: algorithms, algorithm-analysis, sorting, search-algorithms
---


# Question
Title: Can distance-regular graphs with different intersection arrays have the same number of k-hop neighbors for all k?
I would like to ask a very fundamental question regarding distance-regular graphs. Denote $d(u,v)$ as the distance between node $u$ and $v$. Distance-regular graphs are graphs such that for any pair of vertices $u,v$ with $d(u,v)=i$, there are always $b\_i$ neighbors $w$ of $u$ with $d(w,v)=i+1$ and $c\_i$ neighbors $w$ of $u$ with $d(w,v)=i-1$. Therefore, distance-regular graphs are characterized by the intersection array $(b\_0,\cdots,b\_{D-1};c\_1,\cdots,c\_D)$ where $D$ is the dimension of the graph.

However, I wonder if it can be described using only the valency $k\_i$, which is the number of nodes $v$ with $d(u,v)=i$ given an arbitrary node $u$. Clearly, the intersection array $(b\_0,\cdots,b\_{D-1};c\_1,\cdots,c\_D)$ uniquely determines $(k\_1,\cdots,k\_D)$. I would like to ask whether the converse also holds: $(k\_1,\cdots,k\_D)$ unique determines the intersection array $(b\_0,\cdots,b\_{D-1};c\_1,\cdots,c\_D)$. Thank you!

# Answer
> 1 votes
It seems that I have found such pair of distance-regular graphs, which are illustrated below. They both have 20 vertices.

The first graph is the Desargues Graph and the second is the Dodecahedron.

---
Tags: graphs, combinatorics
---


# Question
Title: Can dot producting the result of vector-matrix multiplication speed up the runtime?
Suppose we have a matrix $A$ of dimension $n \times n$ and two vectors $\vec{u}$ and $\vec{v}$ of dimension $n$.

Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(n)$ with the naive algorithm (since the output is a vector of length $n$).

(Forgive me if there is a better runtime. I don't know the current status of vector matrix multiplication.)

If we were to apply the dot product to our equation, we get $A\vec{v} \cdot \vec{u} = \vec{x} \cdot \vec{u}$. We know the final space complexity goes down to $O(1)$ for the result and $O(1)$ space complexity during the running time of the naive algorithm. But the naive algorithm is still $O(n^2)$ in time complexity.

Is there a way to manipulate the equation so that we get an improved time complexity without hurting the space complexity using the dot product?

A bonus question for pondering: Can we use operations that reduce information like the dot product (or for example other information destroying operations like the derivative) to speed up both the space and time of algorithms?

# Answer
No. It is not possible to reduce the time complexity below $O(n^2)$ time. It takes $\Theta(n^2)$ time just to read every entry in $A$. Moreover, the result depends on every entry of $A$ (if there is any entry that the algorithm doesn't read, then the algorithm will produce the wrong output on some inputs). Consequently, every correct algorithm requires at least $\Omega(n^2)$ time to compute the answer.

So, the naive algorithm is asymptotically optimal.
> 3 votes

# Answer
If you expand your expression, the result is a linear combination of the terms of the outer product of $\vec u$ and $\vec v$, where the coefficients are the elements of $A$. So all these terms are independent and must all be evaluated.

A similar reasoning shows that the matrix/vector also has $\Omega(n^2)$ complexity (knowing the product does not allow you to reconstruct the matrix). The case of matrix/matrix is different, as the elements of the result are not independent (knowing the product and one matrix allows you to retrieve the other).

---

For the second part of the question, ponder this: armies of top-level mathematicians have been working hard on linear algebra problems for decades. All the useful techniques and algorithms are found in textbooks and taught at school. This is stable.
> 1 votes

---
Tags: complexity-theory, time-complexity, runtime-analysis, linear-algebra, matrix-multiplication
---


title: Is “x' = f(x)” a programming paradigm?

text:
# Question
Title: Is “x' = f(x)” a programming paradigm?
I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the inability of C++ (or really, any current procedural programming language) to express atomic state change in a way that is both performant and unambiguous. For example, consider the following trivial function:

```
void swap_and_increment(int& a, int& b) {
  int old_a = a;
  a = b + 1;
  b = old_a + 1;
}

```

Because the first assignment to 'a' destroys the old value of 'a', we have to store it in 'old\_a' in order for the swap to work. In contrast, we could write it like this:

```
void swap_and_increment(int& a, int& b) {
  a' = b + 1;
  b' = a + 1;
}

```

where a' means "the new value of a", but this syntax has no equivalent in real C++. This may seem like an insignificant problem at first, but when you scale up to something the size of a Game Boy simulation which has thousands of variables that need to change simultaneously it becomes a serious design problem.

GateBoy solves this problem by instrumenting every variable in debug builds to catch "old/new" bugs - variables get marked as "old" or "new" during execution and reading a "new" value when you expect an "old" value is a runtime error. Metron takes a different tactic and does some symbolic code analysis at translation time to do essentially the same thing - it can ensure that for every possible path through the code, all reads of "old" values are actually reading old values and vice versa for "new" values.

If we generalize the problem a bit, we can say that the difficulty comes in trying to model a system where the entire state of the system represented as X needs to be transformed in to a new state X' via a pure function F without constantly making copies of old state (kills performance), requiring the author to keep track of which parts of the state are old or new at any given point (causes bugs), or relying on hardware support like transactional memory (not widely available). To put it more concisely, a program in the form "x' = f(x)" has no good representation in the software programming languages we use today.

I recently had the opportunity to discuss this issue with a bunch of grizzled old software and hardware veterans, and the approximate consensus seems to be:

* "x' = f(x)" as a model for global atomic state change makes sense to both software and hardware developers, with some viewing it as "just another name for a state machine" (mostly software devs) and some as "so obvious that it doesn't need to be stated" (mostly hardware devs).
* There really isn't any software-oriented language out there that allows for global atomic state change to be both performant (the compiler understands the distinction between "old" and "new" and can reorder code to avoid excessive copies or temporaries) and unambiguous (the distinction between an "old" value and a "new" value has some explicit representation in the language syntax).

So, what do we call this model? Allowing the compiler to reorder statements to preserve "oldness" and "newness" during execution seems to diverge from the "a program is a sequence of operations" model of procedural programming, and the fact that we *do* want to modify X in place instead of constantly creating new (potentially very large) state objects makes it a poor fit for functional programming.

So, my question to the audience - Does it makes sense to call "x' = f(x)" a programming paradigm? It's certainly not a new one, but it also doesn't fit well with the paradigms we've given names to. What should we do with it?

# Answer
I am no good at giving names to paradigms. Someone else will be. But the answer to what you actually want to do is quite straightforward, in C++ at least.

Basically you accumulate **actions**, and having accumulated them you execute them all at the end. In the example you give, each action is of the form "set `a` to some value". Your problem is that you want all the "some values" to be evaluated before any action is performed - and to make this happen automatically so it can't be broken by a dozy programmer. *This happens naturally* with this model, because all the evaluations (of `a+1` etc) happen when the action objects are constructed, and the execution happens much later.

How exactly you do this is a matter of taste and of practicality. But given an `Action` class that looks like this:

```
    class Action
    {int & destination; int source;
    public:
    Action(int &d,int s) :destination(d),source(s) {};
    void apply() {d=s;};
    ~Action() {apply();}; // This is one way of doing it (see below).
    }

```

you can create each action as an object and calculate what new value you are going to have at the time each object is constructed.

In your particular example, with a fixed number of actions, I would be inclined to make the destructor of the object call `apply()`. Thus your

```
    void swap_and_increment(int& a, int& b) {
    Action first {a,b+1);
    Action second {b,a+1);
    }

```

will:

* Calculate `b+1` and `a+1` based on the old values before calling the constructors.
* At the end of the function, when the destructors are called and (as I have suggested) automatically call `apply()`, this will set new values of `a` and `b`, as you asked.

If you don't like giving names to things then you can just create an array of `Action`s:

```
    Action actions[]={{a,b+1},{b,a+1}};

```

and this will create the objects (doing the calculation from the old values at this time), and then the destructor of the array will call the destructors of the objects and will thus perform the assignments all in one go.

The reason for using arrays is that this makes the compiler do all the work and at runtime the overhead should be tiny (no memory allocation or deallocation, no function calls).

If your real structure is more sophisticated than the example you gave, then you could use a vector instead of an array. You would then make sure that the `Action` cannot be copied or assigned, only moved, and have an extra flag so that a moved-from `Action` will do nothing at all when its destructor is called. As before, destruction of the vector would happen automatically at the end of the function, and destruction of the vector would can the destructors of the objects and thus call `apply()` for each of them.

---

As to what **name** you give to the pattern of "accumulate actions and then execute them all at the end", I leave that to the linguists to decide.
> 0 votes

---
Tags: programming-languages, functional-programming, programming-paradigms
---


# Question
Title: Choosing the ideal problem to prove the hardness
I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from every known hard problem to a possible hard problem. So, while proving the hardness of a problem, it does not matter which hard problem we pick, because there is a reduction from all of them. But, in practice it is always ideal to pick a problem for which the reduction is easy to obtain. For e.g., the reduction from Independent set to Vertex cover is straight away defined, where as the reduction from Hamiltonian cycle to Vertex cover is time consuming. So, i am wondering how do we know which hard problem to pick to prove the hardness for a given problem. Since, i am new to this area, i just want to know how does one go about proving the hardness of a problem.
TIA.

# Answer
> 2 votes
Experience and luck. But also having a list of NP-complete problems that you reduce from, and go through one by one exhaustively. Then, of course, you try to prove that the problem can be solved in polynomial time. Then you repeat.

You will, with experience, learn how to come up with gadgets that "propagate" information. The kind of gadget you need depends on the problem, and then you need to find out if the kind of gadget you need naturally fits into the problem you are reducing from.

Just the other day I was trying to find a polynomial time algorithm for a problem when I realized that it might be difficult. I immediately got a feeling that we could use hitting set or set cover to reduce from, and after a while I ended up with reducing from vertex cover, simply by understanding the problem better.

You should start compiling a list of NP-complete problems that you are familiar with, and these should contain Vertex Cover, Independent Set, Clique, Dominating Set, as well as Multicolored Clique and Multicolored Independent Set, 3-Coloring, SAT, 3-SAT, 1-in-3-SAT, Hamiltonian/Longest Cycle/Path, Feedback Vertex/Arc Set, 3D-Matching, Hitting Set, Set Cover, Max Cut, 3-Partition, etc. Go through every problem and ask *how would I reduce from this problem*.

Ps. these problems are just some of the problems *I* use. You might need a different list, and it might change throughout your career.

---
Tags: complexity-theory, graphs, reductions, np-hard, polynomial-time-reductions
---


title: sort is equal to inversions logic

text:
# Question
Title: sort is equal to inversions logic
In Bubble sort, the number of swaps/comparisons is equal to the number of inversions.

1st pass it will do (n -1) comparison
2nd pass it will do (n-2) comparison....so on
(n-1)n = n^2 - n Worst case of bubble sort is theta(n^2)

How is the number of inversions theta(n^2) too??
please explain the logic behind this

# Answer
> 0 votes
At every "phase" it will do that much comparisons. Since there are $n$ such "phases", the number of comparisons can be worst case $\Theta(n^2)$

# Answer
> 0 votes
The number of swaps and the number of comparisons are two different measures.

The number of swaps in BubbleSort is always equal to the number of inversions in the original array. To see this, it suffices to notice that each swap decreases the number of inversions by exactly $1$ and that a sorted array has $0$ inversions.

The number of comparisons is only weakly related to the number of inversions. To see this, notice that BubbleSort performs $n-1$ comparison on a sorted array (which has no inversions). Moreover, even if the input array is not sorted BubbleSort can perform $\Omega(n \cdot i)$ comparisons when there are just $O(i)$ inversions. To see this assume $i \le \frac{n}{2}$ and consider an input array consisting of two consecutive sorted blocks of elements. The first blocks contains the integers from $i+1$ to $n$, and the second block contains the integers from $1$ to $i$. BubbleSort needs $\Omega(n)$ iterations, and hence $\Omega(n^2)$ comparisons, while the number of inversions is $i \cdot (n-i) = O(n \cdot i)$.

# Answer
> 0 votes
The number of inversions in an array does not depend on any algorithm. It ranges from $0$ (sorted sequence) to $\dfrac{(n-1)n}2$ (reverse sorted sequence), so is $O(n^2)$ and but not $\Theta(n^2)$.

It turns out that bubble sort performs exactly that number of swaps.

The "blind" version that you evaluated performs exactly $\dfrac{(n-1)n}2$ comparisons in all cases, and that is $\Theta(n^2)$.

A variant will stop a pass at the last swap performed at the previous pass, possibly reducing to $n-1=O(n)$ comparisons in total, which is the minimum possible !

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


# Question
Title: Probabilty that quicksort partition creates an imbalanced partition
I have come across this question:

> Let 0\<α\<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is ≥α times the size of the original array?

The answer is 1-2\*α.

Can anyone explain me how has this answer come?

# Answer
If $\alpha=0.5$, then $1-2 * 0.5 = 0$, which says that the smaller subarray cannot have length greater than half the original, since then it would be the larger subarray.

If $\alpha=0$, then $1-2 * 0 = 1$, so the size of any subarray must be greater than or equal to zero.

The pivot is randomly chosen, so uniformly distributed between $0$ and $1$. The probability that a particular subarray has size $\geq a = 1-a$. Probability that that particular subarray is also less than half the size of the original $= 0.5-\alpha$. If you're talking about not a particular subarray but whichever one is the smallest, then double it, meaning it has probability $1.0$ of being between $0$ and $0.5$ the length of the original. That is $p=1-2\alpha$.

That explanation makes intuitive sense to me. Basically the answer just says the size of the smaller subarray is uniformly distributed between $0$ and $0.5$ the size of the original.
> 5 votes

# Answer
The other answers didn't quite click with me so here's another take:

If at least one of the 2 subarrays must be you can deduce that the pivot must also be in position . This is obvious by contradiction. If the pivot is then there is a subarray smaller than . By the same reasoning the pivot must also be . Any larger value for the pivot will yield a smaller subarray than on the "right hand side".

This means that , as shown by the diagram below:

What we want to calculate then is the probability of that event (call it A) i.e .

The way we calculate the probability of an event is to sum of the probability of the constituent outcomes i.e. that the pivot lands at .

That sum is expressed as:

Which easily simplifies to:

With some cancellation we get:
> 3 votes

# Answer
Another way to think about this, which maybe helpful is, to pick a concrete value of $\alpha$ and the size of the original array, $n$. Lets say that $\alpha = 0.2$ and $n = 100$. Then, $\alpha n = 20$. Lets also denote the size of the smaller subarray by $|S|$.

If the pivot chosen is at index $21$, then the size of the smaller subarray, $|S|$ is $20$ (remember that the pivot is excluded in the particular partition algorithm under discussion). This satisfies the condition that $|S| \ge \alpha n$.

Now, lets look at $1 - \alpha = 0.8$. Then $(1-\alpha)n = 80$ for our choice of $n$. Now, the pivot needs to be at index $80$ or less. Say, the pivot is at index 80. The size of $|S| = 100 - 81 + 1 = 20$ and satisfies the condition that $|S| \ge \alpha n$. If the pivot, is say, at index 81, then $|S| = 100 - 82 + 1 = 19$ and this violates the minimum size requirement on $|S|$.

Hence, we see that the pivot must be sandwiched between $\alpha n$ and $(1-\alpha)n$. That is, $$\alpha n \lt p \le (1-\alpha)n$$ Since pivots are chosen uniformly at random, the required probability is the size of the interval into which the pivot must fall divided by the number of elements in the original array. That is $$Pr = \frac{(1-\alpha)n - \alpha n}{n} = 1 - 2\alpha$$
> 0 votes

---
Tags: algorithms, algorithm-analysis, probability-theory, quicksort
---


# Question
Title: Number of ways to make change in o(k), where k is number of coins
Godd afternoon,

We have set C of k coins; For example C = (2, 3)
We have positive integer n.

In how many ways we can represent n using those coins?

**Example:**

> If n = 12; C = (2, 3) we can represent 12 as 3+3+3+3, 3+3+2+2+2 or 2+2+2+2+2+2, so in three ways.

**Introduction:**

For any predefined set of coins, there exists formula for number of ways to make change. We can find it using generating functions.

For example number of ways to represent n using set of coins (2, 5) is equal to n-th coefficient in $\frac{1}{(1 - x^2)(1 - x^3)}$ series expansion. We decompose this function to simple fractions. Then it's easy to find series expansion.

$F(x) = \frac{1}{(1 - x^2)(1 - x^3)} = \frac{1}{4(1 - x)} + \frac{1}{4(1 + x)} + \frac{1}{6(1 - x)^2} + \frac{1}{3(x^2 + x + 1)} = \frac{1}{4}\sum\_{n=0}^{\infty}x^n + \frac{1}{4}\sum\_{n=0}^{\infty}(-1)^nx^n + \frac{1}{6}(\frac{1}{1 - x})' + \frac{1}{3(x^2 + x + 1)} = ... = \frac{1}{4}\sum\_{n=0}^{\infty}(\frac{1}{4} + \frac{(-1)^n}{4} + \frac{n+1}{6} + \frac{c\_{n}}{3})x^n$

Where $c\_{3k} = 1, c\_{3k + 1} = -1, c\_{3k + 2} = 0$.

We could represent $\frac{1}{x^2 + x + 1}$ as a sum of series with complex coefficients, it's easier however, to just find reverse formal series for polynomial $x^2 + x + 1$, and that's what I did.

**Now, the actual question:**

How to do this for C (set of coins) not predefined. Is there an algorithm we can use to replicate my reasoning in the computer? Decompose a fraction into simple fractions, determine the formula (automatically) and in constant time (in practice in linear time from number of coins, because the formula would contain k elements) find the result.

# Answer
Dynamic programming provides an $O(nv)$ solution where $n$ is the number of coins and $v$ is the target value. A slight variation to the classic coin change dynamic programming solution can be used to count number of solutions.

https://www.geeksforgeeks.org/coin-change-dp-7/amp/
> 1 votes

---
Tags: algorithms, discrete-mathematics, generating-functions
---


title: Language of ambiguous words

text:
# Question
Title: Language of ambiguous words
Consider an ambiguous context-free grammar $G$. Define $A(G)$ the set of ambiguous words, meaning: $$A(G) = \\{u\in L(G) \mid u \text{ has at least two derivation trees for }G\\}$$ Can we say something about $A(G)$ in the general case? In particular, is $A(G)$ a context-free language?

# Answer
> 8 votes
The standard example that context-free languages are not closed under intersection can also be used as a counter-example for the language of ambiguous words.

Construct unambiguous grammars for $\\{ a^n b^n c^m \mid m,n\ge 1\\}$ and $\\{ a^m b^n c^n \mid m,n\ge 1\\}$. Take the union of these grammars in the common way. The union language is of course context-free, but the ambiguous strings are in the intersection, which is not context-free.

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


# Question
Title: how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000
how to count all pairs such that w^x=y^z, where 1\<=w,x,y,x\<=n and 1\<=n\<=1000000 for example for n=3, there is 15 solutions

1^1=1^1

1^1=1^2

1^1=1^3

1^2=1^1

1^2=1^2

1^2=1^3

1^3=1^1

1^3=1^2

1^3=1^3

2^1=2^1

2^2=2^2

2^3=2^3

3^1=3^1

3^2=3^2

3^3=3^3

# Answer
> 0 votes
Count how many pairs have a product of 1; there are $n^2$ = $10^{12}$. It’s all the cases $1^x = 1^z$. Then ignore w, y = 1.

Count the cases with identical left and right side $w^x = w^x$. There are $(n-1) \cdot n$ cases.

Divide the numbers from 2 to n into (here) about 999,000 non-powers, about 1000 squares, 100 cubes etc. Each number goes into one category only, so 64 counts as a sixth power. Now you count separately all cases of (i-th power)^x = (j-th power)^z with i ≠ j.

Two such numbers can only be equal if they are equal to say $(t^i)^x = (t^j)^z$ for some non-power t, and x, z are both multiples of gcd(i, j) so the total exponents are the same. Say i is smaller. Then the different values $t^j \<= n$ are one limitation, and there are fewer possible exponents for $t^i$.

For example if i = 3, j = 7, then $t^3$ raised to the power 7, 14, 21 etc matches $t^7$ raised to the power 3, 6, 9, 12 etc. There are 142,857 multiples of 7 up to a million, so we have 142,857 pairs for each of the very small set of possible t (only t = 2, 3, 5, 6, 7 have 7th powers up to n = 1,000,000).

i = 1, j = 2: There are less than 1000 squares $t^2 ≤ n$. There are 500,000 possible exponents, for example 2 or 24 raised to the power 2, 4, 6, 8 etc equals 4 or $24^2$ raised to the power 1, 2, 3, 4 etc.

Easiest to count the cases for i \< j, then double the number for the cases i \> j.

---
Tags: algorithms, dynamic-programming, number-theory, counting
---


# Question
Title: How to simulate a Discrete Event Simulation model with a real-time server?
My Problem is having to work with real-time server in a DES model. I have the following situation:

I want to build a discrete event simulation model (*Using event scheduling world view*). However, this model needs to be connected to another **real-time** program.
Within this model, the event routines create next events based on the answer, that the model gets from a 3rd Party software. In better words, the model needs to make a TCP/IP connection to a server at the beginning and generate next events based on the answers which it receives from the other program.
As an example: The model executes event A and within its event routine code, there will be a TCP/IP call to a server which asks "Should I generate the event B or C?". Assume the answer from the server is B, an event of type B will be generated, and so on. Based on my knowledge, the simulation model has a **virtual time**, which it shifts to the next event time in the event list, upon executing the current event.
Now imagine the following scenario:
Event A (event time: 11:00:00) & B (event time: 11:00:01) are on the event list. Event A gets to be executed first, virtual simulation time is now 11:00:00. It makes a call to the server to find out which event to generate next. The Server takes 2 seconds to answer.

How should the virtual time of model be shifted?

* If I consider that 2s delay and shift the virtual time to 11:00:02, the event B will be overpassed (*See Edit*). But the clock will be the same as it would be in a real-world system.
* If I ignore this 2s response time, the model will shift the clock to 11:00:01 and execute event B, although the time in the real-world scenario is now 11:00:02. This means, the model does not behave similarly to the real-world.

I was wondering if someone can guide me to the right direction? How should I deal with the real-time scheduling issue of the DES model? I tried searching online and in literature, but I found nothing which seems to be the solution to my problem. I would appreciate it if anyone can tell me where I can find some useful material on this matter.
Regards

Edit: By "overpassed" I meant the event will be skipped by the simulation model and not get executed because the simulation time will be set to 11:00:02 which is later than 11:00:01 (execution time of event B). In real world, System does event A and sends a request to server at 11:00:01 and while waiting for the server response for event A, goes on and executes event B on the next second. Later when the response for A is there, it will then decide which event to put on event list. Can't figure out how this "waiting for response from server while executing the next event" could be modelled.

# Answer
In the real world, different objects are concurrently doing stuff. In simulation, you just need to simulate that.

When an event happens that affects object O, your simulate should calculate what will O will do in response, and what is the next action (if any) that object O will take, and at what time O will take it. Let's say O will take action A at some time t' in the future. Then, insert an event into the priority queue, with key t', and value A.

At each step of the simulation, you pop off the earlier item from the priority key, simulate the action specified by that item, and simulate the effect of that action (which might involve some other objects that will transition state in response, so you simulate what their next action will do and the time at which it'll occur and insert those into the priority queue).

How does this apply to your situation?

Initially, the priority queue contains event A at time 11:00:00 and event B at time 11:00:01.

You pop off the earliest item in the priority queue. This is event A at time 11:00:00. So, at virtual time 11:00:00, you simulate event A and discover that it will make a call to the server. Presumably this involves sending a message to the server, which will arrive at the server at time 11:00:02. So, you add an event (let's call it event C) to the priority queue, with time 11:00:02, indicating that at that time, the server will receive a message telling it to determine what event to do next.

Now the priority queue contains event B at time 11:00:01 and event C at time 11:00:02.

You pop off the earliest item in the queue. This is event B at time 11:00:01. So, at virtual time 11:00:01, you simulate the effect of B. It does whatever it does - maybe inserting some more events into the priority queue, or changing the state of some objects, or who knows what.

Now the priority queue contains event C at time 11:00:02 (and possibly other stuff, if B added other events).

You pop off the earliest item in the queue. This is event C at time 11:00:02. So, at virtual time 11:00:02, you simulate the effect of C. This involves a message arriving at the server. The server presumably does some computation and determines what event to issue next. So, you insert that event into the queue, with the appropriate time (based on how long it would take the server to perform the next action/event).

And so on. Everything continues from there. Nothing is overpassed. Everything behaves similarly to the real world.

All that this simulation loop does is let you "skip over" quiet periods where nothing is happening and where you'd be waiting for the next event to happen.
> 0 votes

---
Tags: simulation, real-time
---


# Question
Title: Possible approaches to the Ship City problem?
About few ago in my freshman year of college I stumbled across an an old blog post on r/programming posing a programming challenge. Here is the short version of it:

> Hundreds of ships would like to dock to each other to build a floating city of ships.
>
> Although they are all bound to each other, any ship must be able to leave the collective without needing to ask any other ship to move.
>
> This means they always need to have a route to get to open waters.
>
> However to maintain physical stability against the waters, there should be a route to be able to walk from one ship to any other ship.
>
> Given a n x n size of the city, what is the most compact tiling possible for all of the ships?

He provides some good examples in the blog post which clear up what the target is. I wanted to take another shot at the problem but it still seems insanely hard. I have done a lot of searching but I haven't found anything else about this problem. The author says he failed to solve it mathematically, and I also can't imagine a mathematical solution/model to this outside of combinatorics. A brute force approach would be out of the question due to how fast-growing the number of possible configuration is. What potential approaches do you think would be worth considering?

# Answer
I found a very systemmatic approach to solve the problem but it depends on my instinct and it has no direct proof yet (or I am not sure if it is "correct"). Maybe someone else can prove/disprove my approach.

First, I will not try to put 100 ships into a square as the question asks but I will try to find the maximum number of ships can be put inside a `nxn` square, which will eventually lead to the answer of the original question.

My instinct says to create corridors(1 space between) to get to the maximum efficiency. Like a parking lot for ships. For example:

```
^^^^^^^^^^^^^^^^...
<> <> <> <> <> <...
<> <> <> <> <> <...
<> <> <> <> <> <...
<> <> <> <> <> <...
<> <> <> <> <> <...
<> <> <> <> <> <...
<> <> <> <> <> <...
...................
...................
...................

```

Of course we cover top and left part first and then create corridors. However, this method relies on inside being divisible by 3. Let's consider other sizes (remainder 1 and 2).

If we have remainder 1 inside (`(n-1)/3` gives remainder 1), it is simple, like below:

```
^^^^^^^^^^^
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>
<> <> <> <>

```

If we have remainder 2 inside, it is a bit more complicated. I tried this part manually and I am not sure, but came up with the following in the end:

```
^^^^^^^^^
<> <> <
<> <> <
<> <> <
<> <> <
<> <> <
<> <> <
<> <> <
<> <> <

```

We have `2xn-1` space left. After a couple tries, I realized that I can create corridors here too, but horizontally:

```
^^^^^^^^^
<> <> <vv
<> <> <
<> <> <^^
<> <> <vv
<> <> <
<> <> <^^
<> <> <vv
<> <> <>

```

To formulize my approach to get the number of maximum ships inside `nxn` size square, I came up with the following:

(remainder 2 inside) For n = 3k, $2n + 1 + \frac{n-3}{3} * 2 * (n-1) + \frac{n-3}{3} * 2 * 2 + 1$

(remainder 0 inside) For n = 3k + 1, $2n + 1 + \frac{n-1}{3} * 2 * (n-1)$

(remainder 1 inside) For n = 3k + 2, $2n + 1 + \frac{n-2}{3} * 2 * (n-1) + n - 1$

These formulas might be reduced into one formula with floor and ceil functions but I didn't have time for it. I might look into it later.

Furthermore, these formulas might not work for small n. I am not sure about the base case.

To get the answer for 100 ships, we just need to increase n until it becomes bigger than 100. So it should be $n = 12$, the city can hold 104 ships.
> 1 votes

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Traverse Matrix in Reverse Diagonal strips
I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

```
1 2 3
4 5 6
7 8 9

```

Would have to be traversed in the following order:

\[3\],\[2,6\],\[1,5,9\],\[4,8\],\[7\]

# Answer
> 0 votes
I hope that the following example will inspire you: $$ (2,0) \\ (1,0),(2,1) \\ (0,0),(1,1),(2,2) \\ (0,1),(1,2) \\ (0,2) $$ This is the same as the order you were describing. Notice that line $i$ (counting from zero) consists of $(x,y)$ such that $y-x = i-2$, arranged in order of increasing $y$ (or decreasing $x$). Furthermore, $y$ runs from $\max(i-2,0)$ to $\min(i,2)$.

In the general $n\times n$ case, just replace all occurrences of $2$ with $n-1$, and let $i$ run from $0$ to $2n-1$.

# Answer
> 2 votes
Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\\,1,\\,0,\\,-1,\\,-2$. This gives something like

```
for c := 2 to -2 step -1
    for x := 0 to 2
        y := x-c
        if 0<=y<=2
            print A[x,y]

```

# Answer
> 0 votes
```
public static void main(String args[]) {
    int[][] metrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    /* index pattern

    Top-Right:
    0,2
    0,1 1,2
    0,0 1,1 2,2
    1,0 2,1
    2,0

    Bottom-Left
    2,0
    1,0 2,1
    0,0 1,1 2,2
    0,1 1,2
    0,2

    */

    System.out.println("Output - Top-Right: ");
    for(int c = 2; c >= -2; c--) { // c = 2,1,0,−1,−2
        for (int x = 0; x <= 2; x++) {
            int y = x + c; // x - y = c
            if (0 <= y && y <= 2) {
                System.out.print(metrix[x][y] + " ");
            }
        }
    }
    // Output - Top-Right: 3 2 6 1 5 9 4 8 7

    System.out.println("Output - Bottom-Left: ");
    for(int c = 2; c >= -2; c--) {
        for (int x = 0; x <= 2; x++) {
            int y = x - c;
            if (0 <= y && y <= 2) {
                System.out.print(metrix[x][y] + " ");
            }
        }
    }
    // Output - Bottom-Left: 7 4 8 1 5 9 2 6 3
}

```

# Answer
> 0 votes
**Mathematical derivation of the solution:**

We first observe that a reverse diagonal is such that the difference between the row index and column index is constant, $r-c=d$. So we will fix $d$ and try all $(r,c)=(c+d,c)$. Notice that $d$ can be negative.

From the definition of the domain of the indexes $0\le r,c\<n$, we draw $0\le c+d,c\<n$, or $\max(-d,0)\le c\<\min(n-d,n)$, which is the range of possible $c$.

For this range to be non-empty, we need $\max(-d,0)\<\min(n-d,n)$. For a positive value, this reduces to $0\<n-d$, or $d\<n$. For a negative value, $-d\<n$ or $d\>-n$. Using these results, we can readily write the double loop:

```
for d= 1-n to n-1
    for c= max(-d, 0) to min(n-d, n)-1
        A[c+d, c]

```

It is also possible to split, considering the two signs of $d$:

```
for d= 1-n to -1
    for c= -d to n-1
        A[c+d, c]

for d= 0 to n-1
    for c= 0 to n-d-1
        A[c+d, c]

```

This scans from bottom-left to top-right.

---

By a similar reasoning, you can handle the case of a rectangular matrix, which is a little more tricky.

# Answer
> 0 votes
For those who are struggling to understand the problem in terms of mathematical equations, here's an elaboration!

Example:

```
1 2 3
4 5 6
7 8 9

```

Indices of corresponding diagonals (if we are going from right to left):

```
[0][2]
[0][1], [1][2]
[0][0], [1][1], [2][2]
[1][0], [2][1]
[2][0]

```

If you calculate x-y for every pair in every row, you will realise that all of them have the same sum -\> i.e. `x-y=c`

Example:

```
0-2 = -2
0-1 = 1-2 = -1
0-0 = 1-1 = 2-2 = 0
1-0 = 2-1 = 1
2=0 = 2

```

# Answer
> -2 votes
Here's the Python version:

```
def reverse_diagonal_traversal(matrix):
    side = len(matrix) + 1
    iterations = side - 1
    for i in range(1, side):
        for j in range(i):
            yield matrix[j][iterations + j - i]
    for i in range(side - 2, 0, -1):
        for j in range(i):
            yield matrix[iterations + j - i][j]

def test(side):
    matrix = [range(i * side, side + i * side) for i in range(side)]
    print matrix
    for i in reverse_diagonal_traversal(matrix):
        print i

```

Writing this in C would require too much code dealing with memory (de)allocation / printing, which isn't really part of this problem. I'd imagine that porting the above to C won't be a problem.

The idea behind the code is that you need to produce iterations of `1..N` length until you reach the main diagonal, and then `N-1..1`. In the first half, you'd have to select the row at `N` at the first step of the iteration, and then `N-i` for each value of `i` in the iteration. You'd select the column starting at `nth iteration - length of iteration`, and then for each iteration step you'd increment that by one.

Finally, I'm not sure this is the most "elegant" solution (maybe you can do it in just half the code), but I couldn't find a good way to do that.

---
Tags: algorithms, data-structures, adjacency-matrix
---


# Question
Title: maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$
Let $N$ be a number and consider the sequence of $a\[i\]$, $b\[i\]$ with $i=1,n$ where $a\[i\]$ are positive integers and $b\[i\]$ is the sign '$\<$' or '$\>$'. Find the maximum length of the subsequence(which is not necessarily contiguous) (a\[i\],b\[i\]) such that if $$b\[i\]='\<'$$ then $$a\[i+1\]\<a\[i\]$$ and if $$b\[i\]='\>'$$ then $$a\[i+1\] \>a\[i\]$$.

For instance if the input is:

```
6
3 >
2 <
1 >
3 >
1 <
8 <

```

Then the output is `4` And the only maximum subsequence that we can choose is: `2 < 1 > 3 > 8 <` because `1<2 3>1` and `8>3`.

My idea: I tought about constructing the array dp\[\] such that dp\[i\] represents the maximum length of the longest sequence of (a\[i\],b\[i\]) with the given properties. I constructed it from the end like this:

$$b\[i\]='\>'$$ then $$dp\[i\] = max(1+dp\[j\], i \< j \<= n \\&\\& nr\[j\] \> nr\[i\])$$ and if $$b\[i\]='\<'$$ then $$dp\[i\] = max(1+dp\[j\], i \< j \<= n \\&\\& nr\[j\] \< nr\[i\])$$ The difficulty of the problem lies in finding the number $max(1+dp\[j\], i \< j \<= n \\&\\& nr\[j\] \< nr\[i\])$ and $max(1+dp\[j\], i \< j \<= n \\&\\& nr\[j\] \> nr\[i\])$ I implemented this by using a search tree which with all the elements of dp\[\] from $n$ to $i+1$ and then do the corresponding query depending on the sign. However, this solution turned up not to be very efficient since it takes more than 0.15 seconds for certain tests.

May somebody help solve this with a more efficient algorithm.

This is what I tried:

```
#include <iostream>

using namespace std;
int tree[400001],dp[101001],h[400001];
struct af
{
    int nr;
    char rs;
}v[101001];
int op(int x,int y)
{
    return x<y?y:x;
}
void update(int node, int left, int right, int pos, int val) {
    if (left == right) {
        tree[node] = val;
        h[node]=v[left].nr;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid)
        update(2 * node, left, mid, pos, val);
    else
        update(2 * node + 1, mid + 1, right, pos, val);
    tree[node] = op(tree[2 * node] , tree[2 * node + 1]);
}
int query(int node,int left,int right,int x,int y)
{
    if(x<=left && right<=y)
        return dp[node];
    int mid=(left+right)/2;
    int ans1=0,ans2=0;
    if(x<=mid) ans1=query(2*node,left,mid,x,y);
    if(y>mid) ans2=query(2*node+1,mid+1,right,x,y);
    return op(ans1,ans2);

}
int query1(int node, int left, int right, int x, int y,int z) {
    if(x <= left && right <= y && left==right)
    {

        if(h[node]>z && (h[node]!=0))
        {

            return tree[node];
        }
        else return 0;

    }
    int mid = (left + right) / 2;
    int ans1 = 0, ans2 = 0;

    if(x <= mid)
       {ans1 = query1(2 * node, left, mid, x, y,z);}
    if(y > mid)
       ans2 = query1(2 * node + 1, mid + 1, right, x, y,z);
    return op(ans1 , ans2);
}
int query2(int node, int left, int right, int x, int y,int z) {
    if(x <= left && right <= y && left==right)
    {
        if(h[node]<z && (h[node]!=0))
        return tree[node];
        else return 0;
    }
    int mid = (left + right) / 2;
    int ans1 = 0, ans2 = 0;
    if(x <= mid)
       ans1 = query2(2 * node, left, mid, x, y,z);
    if(y > mid)
       ans2 = query2(2 * node + 1, mid + 1, right, x, y,z);
    return op(ans1 , ans2);
}
void build(int node, int left, int right){
    if(left == right){
       tree[node] = dp[left];
       h[node]=v[left].nr;
       return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = op(tree[2 * node],tree[2 * node + 1]);
}
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>v[i].nr>>v[i].rs;

    dp[n]=1;
    update(1,1,n,n,1);
    for(int i=n-1;i>0;--i)
    {

        if(v[i].rs=='>')
        {

            dp[i]=query1(1,1,n,i+1,n,v[i].nr);
            dp[i]++;
        }
        if(v[i].rs=='<')
        {
            dp[i]=query2(1,1,n,i+1,n,v[i].nr);
            dp[i]++;
        }
        update(1,1,n,i,dp[i]);
    }
    cout<<tree[1];
    return 0;
}

```

# Answer
You just have a sequence of boolean values, either true or false. How you calculate which ones are true or false is both trivial and irrelevant. So you need to find the longest possible subsequence of all true values.

May I suggest that your solution to this is bizarrely complex. There is no need for a search tree whatsoever. There is no need for any storage that is larger than O(1). There is no need for anything that seems to look like dynamic programming.

To find the subsequences:

1. Let i = 0. Let longest\_l, longest\_r = -1, -1
2. Starting at index i, find the first index l ≥ i with a a value "true". If there is no such index then go to Step 6.
3. Starting at index l, find the last consecutive index r with a value of "true".
4. If longest\_l \< 0 or r-l \> longest\_r - longest\_l then replace longest\_l with l, and longest\_r with r.
5. Let i = r + 1 and go to Step 2.
6. If longest\_l \< 0 then all elements of the sequence are false. Otherwise the longest subsequence with "true" values is from longest\_i to longest\_j.

For n = 100101 with 800KB of data I'd expect this to be some milliseconds at most, plus the time of loading the data which may be more or a lot more.
> 1 votes

---
Tags: algorithms, dynamic-programming, balanced-search-trees, search
---


# Question
Title: Selecting the smallest node set in a graph so that all nodes outside the set can connect to this set within certrain distance
Let's say we have a graph $G$ with $|V|$ nodes. We wish to select the smallest set of nodes $S$ that:

$dis(i, j) \le k, \forall i \in S, j\in V-S$,

where $k$ denotes a certain distance threshold.

Smallest means the least number of nodes.

# Answer
Reduce from dominating set, let $k=1$.
> 1 votes

# Answer
This looks quite NP-complete to me (just guessing). Obviously if S is not connected then you split it into connected sub-graphs and solve each one individually. Call two nodes a, b connected if their distance is at most k.

Since this is NP-complete, just a heuristic: Put the nodes in some order. If a comes before b, and a is connected to everyone that b is connected to, then we wouldn't put b into S (because exchanging it with a would be better or the same). This reduces the number of candidates to put into S.

Look for the node with the most connections to nodes not in S and not connected to a node in S, and move it into S. Repeat until everything is connected to S.

A second algorithm: Look for nodes with many connections to nodes not in S and not connected to a node in S, pick one at random, and move it into S. Repeat until everything is connected to S. Count the nodes in S. Then try again until it looks like better solutions are hard to find.

A third algorithm: Same as the second, put prefer nodes with connections that don't have many connections themselves.

That's just some ideas. You can find an optimal S by using backtracking. You *definitely* prefer a node to put into S that is connected to everyone in S, and if there is no such node then you prefer *two* nodes that are together connected to everyone not in S. Just try out different things, and measure the time.
> 0 votes

---
Tags: graphs
---


# Question
Title: Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a\_0 * S\_1 + a\_1) * S\_2 + a\_3 ) * ... + a\_{n-2}) * S\_{n-1} + a\_{n-1}$,
such keys preserve the order of tuples and can be compared in constant time,
but they occupy $log\_2 \prod\_{i=0}^{n-1}{S\_i} $ bits per key (in my program there are already $512-2048$ bit keys).
Total number of keys can be estimated beforehand and the usual array density is $10^{-10} - 10^{-20}$ (fraction of array cells that are populated).
The tuples are not available beforehand but are added to the array from time to time, and they are never deleted.

I want to shrink size of the keys at the expense of comparison time.

I need a data structure (hashtable) that:

1. Maps a tuple into an integer as a perfect hash fuction in $O(n + \log N)$ time, where $N$ is the number of already processed tuples. Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere.
2. allows key comparison in $\lt O(\log N)$ time (ideally constant time)

**EDIT**

This question is not about a multidimensional array enhancement, it's about hashing large integer tuples while preserving their row-major order.

# Answer
> 0 votes
The problem is a case of list-labeling problem.

It seems impossible to fullfill `Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere` requirement, as even unacceptably large $N$-bit mappings (labels of size $m = 2^{\Omega(N)}$ in list-labeling problem terminology) are still expected to be relabeled.

So I dropped `Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere` requirement.
The current draft idea is to use polynomial list-labeling over a BST or a skip list that contains the tuples to get the labels,
a mapping consists of 2 parts - a label itself and a version of the label,
if mappings are compared externally then first their versions are compared, if they are the same then labels are compared, otherwise mappings are updated in $O(log N)$ to the most actual version, that's the worst comparison time.
However overall efficiency depends on when and how often the external comparisons happen and if the economy of reduced mapping size outweights downside of need to store the older versions of labels.

# Answer
> 0 votes
Could you use a different ordering, specifically Morton Ordering (Z-order curve)?

I could offer one of my own projects, the PH-tree index. It is an ordered map that uses multidimensional keys (e.g. a vector of integer). In your case, you would use the "coordinate" of your matrix as "key". This would save you from manually creating a key and inserting it into a (perfect) hashmap. Insertion, deletion and lookup are all in the order of $O(n\*\log{N})$. Space complexity is roughly $O(nN)$.

Note that the Java implementation support up to 1000 dimensions (actually more, but I never tested more). The (more recent) C++ implementation supports up to 63 dimensions, but it hasn\`t been optimized much for $n\>6$ yet.

It all hinges obviously on whether Morton order (instead of row-major) would be an option for you problem.

You can simulate row-major ordering by performing a window query on any given row and it would return all entries in that row in the correct order. That means, to get *all* occupied cells in row-major order, you would need to perform one window query for each row...

**EDIT**

I forgot to mention: The original PH-tree concept uses prefix sharing to reduce memory consumption. In short: all keys in a "node" of the PH-tree are spatially close, meaning that they typically share a lot of their leading bits. The tree exploits this and stores the common prefix only once. The differing bits of the keys in the node are then compressed into a single bit stream.

Unfortunately, this "compression" is only available in Java version and it is not used by default. Please let me know if this is interesting to you, I can provide instructions on how to enable it.

---
Tags: time-complexity, data-structures, space-complexity, hash, hash-tables
---


title: T(n) = 2T(n/4) + sqrt(n)

text:
# Question
Title: T(n) = 2T(n/4) + sqrt(n)
T(n) = 2T(n/4) + sqrt(n) I am trying to solve this question and ended up with the answer O(√n.log√n). But when I checked online the answer was supposed to be O(√n.logn) or √n.logn base 4. I am not sure how to remove the square root from n.

# Answer
> 0 votes
With $T(n)=\sqrt n\log n$, $$T(n)-2T\left(\dfrac n4\right)=\sqrt n\log n-2\sqrt{\frac n4}\log\frac n4 \\\=\sqrt n\log 4.$$

# Answer
> -2 votes
Given: T(n) = 2T(n/4) + sqrt(2)

Complexity should be sqrt(n) =\> n^(1/2).

Please let me know whether the following derivation makes any sense.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Why is proving something is NP-complete useful, and where can I use it?
I trying to understand where, as a programmer in situations where it can be good to do a NP-complete reduction to prove that a problem is NP-complete, why is it good to do that as a programmer? I don't understand.

# Answer
> 18 votes
When dealing with a problem, knowing how to recognize a $\mathsf{NP}$-hard problem can prevent you from hair loss trying to find an efficient solution (as it is thought that $\mathsf{P}\neq \mathsf{NP}$).

Reductions can also be seen in a "If I know how to solve $A$, then I know how to solve $B$" way.

When confronted to a $\mathsf{NP}$-hard problem, you can then think of ways to deal with intractability.

# Answer
> 11 votes
If a problem is NP-complete that means that lots and lots of great mathematicians, computer scientists, and very clever software developers have not been able to find an efficient solution for the problem. And that means nobody can blame you if you can't find one. If you could find one, they'd introduce a Nobel prize for computer science just for you. (Roughly quoted from memory from Garey-Johnson, Computers and Intractability, 1979).

# Answer
> 7 votes
Knowing about NP-complete problems is part of the cultural baggage of every computer scientist, as is the case for other core results (such as the non-computability of the halting problem). NP-complete problems arise in practice. The maximal independent set problem for graphs is aimed at simultaneously exploiting a maximal amount of resources that are not dependent on one another.

Theoretical computer science focuses on extremes: problems that are not computable, problems that are too hard to compute (for larger sized instances), limits of computational speed up, limits of compressibility etc. You can interpret these results (from a practical point of view) as guard rails you need to know about in order to make reasonable decisions about new problems. Some of these problems turn up in practice in different guises. The reduction process helps to show that a new problem is NP-complete by linking it (in the chain of NP-complete problems) to a known NP-complete problem. As pointed out in the first answer: when this happens it is reasonable to stop searching for an efficient solution (unless the aim is to resolve the long standing open problems related to NP-completeness).

Theoretical results may appear at times to stay far from practice. They do impact application areas: the halting problem indicated the need to develop real-time programming languages by restricting higher level constructs. The limits of compressibility and running-time speed-up support decisions on when it is reasonable to give up on trying to optimise code for certain applications.

# Answer
> 6 votes
As a working programmer, you need to recognize when you are being asked by the business to *do the **literally** impossible*.

Assuming ≠ (you don't need to understand what that means, just know that most of us do), then when you are being asked to solve a problem that falls into NP the solution is going to necessarily be slow (although it may be fast enough in practice).

But if you are told that your map direction calculations for the shortest route that visits cities A, B, C, D, E, and F is too slow, you need to understand that there is a hard bound on how fast it can be.

That's why it's important to understand broadly the sorts of problems in the NP space and why people ask about them (sometimes in disguise) in interviews: you need to be able to recognize immediately that the objective is unachievable and start brainstorming workarounds or trade-offs to hopefully still achieve the business goals.

# Answer
> 5 votes
As a programmer, you likely do not need to pay *much* attention to the class of NP-complete problems. The class of NP problems is *much* more useful. Obviously, if your problem is NP, it cannot be solved for all inputs in polynomial time (by a deterministic Turing machine, and assuming $P\ne NP$... which is currently considered a pretty darn reasonable assumption)

The easiest way to prove that your problem is NP is to demonstrate that, were you to be able to solve your problem in polynomial time, you could also solve an existing NP problem in polynomial time as well. This is what they mean by a "reduction".

For mathematicians, the idea of NP-completeness is very useful. Completeness says that you can reduce *any* NP problem to any NP-complete problem. This is very useful for the topic of $P=NP$. If you could find a polynomial time solution to *any* NP-complete problem, it is trivial to show that you found a solution to *every* NP problem, thus demonstrating that $P=NP$ without having to mechanically exhaust every last NP problem, one by one, demonstrating that every one of them was infact P.

As a programmer, the best use for NP-complete I have found is to take advantage of the raw amount of effort people have put into exploring good algorithms for dealing with them. I may be working on a problem that's totally unique to my domain, but if I can transform it into another NP problem that people have indeed worked hard on, I may be able to leverage their work. This is especially true for the SAT problems, for which a *tremendous* amount of work has been done.

As a simple example, in SAT problems, there is often a particularly difficult class of problems that take the form (a|b|c)&(d|e|f)&...&(x|y|z), where a, b, c, ... z are literals (possibly negated), and they aren't all unique (i.e. d may be the same as ~a). In many cases, it is easy to show that the complexity of satisfying that expression explodes as the expression gets longer. But sometimes my problem doesn't call for such expressions. Maybe mine has a limit in how many terms it uses, bounding the exponential growth to something palatable. Maybe each term has no more than one negated term (which makes those Horn clauses -- satisfiability of Horn clauses is in P. In fact, it's linear!).

Sometimes you get lucky and find that, when you do the transformation, you get something really easy (like the Horn clauses mentioned above). In those cases, you might simply figure out what the analog for Horn clauses is in your problem, and just code it up yourself. Other times there's some *amazing* math behind it, and the easiest way to solve your problem is to actually reduce it to SAT, and solve that.

If I have a problem that is NP, it is NP. I can't leverage other mathematicians to magically make it P. However, often I *don't* actually have a NP problem. I really have a hard-to-describe subset of a NP problem that I called NP out of laziness or ignorance. If I transform my problem into another, I can also tranform my real inputs. There's a decent chance that my real problem fell within the range of a previously explored P region of a NP problem. SAT, for instance, has been *mightily* explored. We're actually pretty darn good at finding ways to satisfy many boolean expressions. Maybe an existing SAT solver has a polynomial time solution for all of the reductions of my problem *within the limited inputs I need*. It's easy to prove they can't solve them all (because SAT is NP), but dang if we haven't made great advancements on many cases!

It's also helpful for demonstrating when I'm not so lucky. If I can take a "hard" problem from SAT, and show that solving my problem requires solving my problem too, then I show one of the following:

* My problem is NP-complete
* My problem requires exploring a P sub-problem of a NP-complete problem like SAT which the state of the art from hundreds of mathematicians hasn't solved yet, or.
* I need to come up with a more clever reduction to sidestep the issue

This does a good job of focusing my attention. Should I *really* be trying to solve this problem? Is this problem perhaps NP? (even if I haven't proven it formally). Am I capable of finding the more clever reduction? (which, if I can find, shows how I may be able to use the existing proofs for SAT to solve my problem)

Other than that, NP is far more useful for programmers than NP-complete.

Well, maybe. I have found that, when explaining why we *shouldn't* do something, the term "NP-complete" rings really nicely in people's ears. There's something about the word "complete" that suggest finality, even when your audience doesn't really grasp P vs NP. NP-hard is another useful word, but I find NP-complete does the job really well.

# Answer
> 5 votes
To argue in front of your boss.

Source: https://www.ac.tuwien.ac.at/people/szeider/cartoon/

This cartoon is originally from the famous textbook *Computers and Intractability* by Garey & Johnson, but adapted to the current Zeitgeist.

PS: Concerning the adaption, I would prefer to see real parity here, i.e., having one Alice and one Bob and not Alice two times, but I am not sufficiently talented to modify the cartoon.

# Answer
> 3 votes
I once was working as a consulting company where we were writing software for a warehouse management system. One of the requirements was to generate pick lists that would optimize the loading of trucks. My manager came up with an algorithm that he thought would work. It turns out that what he came up with was really just the Bin-Packing Problem, which is known to be NP. He was not familiar with the concept of P and NP, but I was, and I was able to convince him that his solution would not scale, no matter how powerful the computer was that ran the algorithm. This probably save us several weeks of development time. We ended up implementing a heuristic based algorithm that was not optimal, but which worked well in practice.

# Answer
> 1 votes
In my sens, Proving NP-Completeness of a problem, can let you try general solutions.

There are some general or maybe efficient (easy to implement and customize, more understandable or representative, scalable, a better parallel version) solutions for any problem. By term "general solutions", i mean interpolation, modeling, approximation, meta-heuristic search algorithms and optimization, ... vice versa.

Using these general solutions is reasonable only if you don't know the true solution or algorithm. So performing a research for proving that a problem is not a NP, or its solution could be approximated by easier algorithms with acceptable result, or it is reducible to some P algorithms, is a valuable effort. This value of this research is depended on use-case (problem), i.e. in a small company it is not valuable.

# Answer
> 1 votes
When you decide on a cryptographic scheme you want to know that cracking it is an NP complete problem --- that is, you want the encoding/decoding scheme you want to be as hard as possible to crack. For example, RSA encryption relies on the NP-complete problem of factoring (very large) numbers into their prime factors.

---
Tags: np-complete
---


title: Page/Frame VS Block

text:
# Question
Title: Page/Frame VS Block
I am bit confused on these terminologies.

While studying Paging of Operating System we study about Page and Frame.

> Size of one Frame of Main Memory = Size of one Page of a Process

While studying Cache Memory Mapping in Computer Organization we study about Memory Block.

> Size of one Block of Main Memory = Size of one Block of a Cache Memory

Questions

* 1\] Difference(s) between Page/Frame and Block.
* 2\] How are they related, if at all they are?
* 3\] Do they both exist at the same time? If yes, how?

# Answer
> 1 votes
Paging is a non-contiguous, fixed size partitioning method to allocate memory to a process. The process(virtual address space/virtual memory) is divided into fixed size partitions(pages) and then loaded into main memory. This post explains why page size is the same as frame size. A page is not the same as a frame, as a page refers to a partition of virtual memory whereas a frame is a partition of physical memory, which holds a page.

---

A cache block/cache line is a fixed size partition of the cache, which exploits \[locality of reference\]\[2\]. A cache is an optimization, an effort to reduce the effective memory access time. A system can work perfectly fine without a cache, just slower.

---

Are they related? Yes and No. The idea of partitioning in both concepts is similar, however their purposes and working are entirely different. The main memory is an addressable memory and needs an address translation mechanism to work with paging, whereas the cache is a content addressable memory, it doesn't have addresses of its own and uses Cache mapping techniques to place data in cache. The size of a cache block is generally not equal to page size.

---

Do they both exist at the same time? Yes and No, in modern computer systems, Yes. However, no one can stop you from building your own system without paging and caching, or keeping either of them or both.

---
Tags: computer-architecture, operating-systems, memory-management, cpu-cache, virtual-memory
---


# Question
Title: Modified Quickselect - Proving linear time
As we know, Quickselect chooses a 'random' element in order to partition the array around that element in every iteration.

Assume the random element is at most the $\frac{1}{k}\cdot n$ largest element, and at least the $\frac{k-1}{k}\cdot n$ largest element, for some constant $k\>1$.

I'm asked to prove that under those terms, Quickselect will run in linear time.

Here is how far I've got:

We know that for each iteration, there exists $r\_i \in \mathbb{R}$ such that: $\frac{1}{k}\cdot n\leq r\_i\cdot n \leq \frac{k-1}{k}\cdot n$, this lets us know that: $$ T(n)=T(r\_1\cdot n)+O(n) $$

but also, we know that: $$ T(n)\leq T(\frac{k-1}{k}\cdot n)+O(n)$$ I was not able to continue further than this, I'm aware that I need to reach some sort of summation equation.

# Answer
> 1 votes
You can do it by proving by induction that there exists a constant $A$ such that for all $n\geqslant 0$, $T(n) \leqslant Akn$.

Note that the constant $A$ can be chosen depending on $T(1)$ and such that the $\mathcal{O}(n)$ in your relation is $\leqslant An$.

---
Tags: recurrence-relation
---


# Question
Title: Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By $(d, h)$-tree-decomposition, I mean to divide the vertices $V$ into $k$ trees, such that the height of each tree is $h$, and each non-leaf node has $d$ children.

I know it is definitely $\text{NP}$-Hard, since minimum $(1, |V|-1)$-tree-decomposition is the minimum Hamilton path. But are there any good approximation algorithms?

# Answer
This problem does not admit even a constant-factor polynomial time approximation algorithm, unless P = NP.

Proof: Assume there exists a polynomial time $\alpha$-approximation algorithm $A$ for this problem. Consider the following reduction from Hamiltonian path:

Given an unweighted undirected graph $G$ as input. Give every edge weight $1$. Now complete the graph by adding dummy edges between every pair of vertices with weight $|V| \cdot \alpha$. Call this graph $H$.

Now, if $G$ admits a Hamiltonian path then the minimum $(1, |V| - 1)$ decomposition of $H$ has weight exactly $|V| - 1 \implies A(H) \leq \alpha \cdot (|V| - 1)$.

On the other hand, if $G$ does not admit a Hamiltonian path then the minimum $(1, |V|-1)$ decomposition of $H$ has weight $\geq |V| \cdot \alpha \> \alpha \cdot (|V| - 1)$.

Therefore, $G$ admits a Hamiltonian path if and only if $A(H) \leq \alpha \cdot (|V| - 1)$.

This is the exact proof for why it is NP-Hard to approximate the Travelling Salesman Problem within a constant factor.
> 1 votes

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


# Question
Title: Regular language under intersection and complement confusion
I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L\_1$ and $L\_2$ as regular then $L\_1 \cap L\_2 = L\_3$ makes $L\_3$ regular. Now for the case of when $L$ is not regular, then its complement $L^\complement$ is also not regular. But when $L\_1$ and $L\_2$ are not regular then $L\_1 \cap L\_2 = L\_3$ doesn't make $L\_3$ not regular, why? does being closed mean for non regularity too?

# Answer
> 1 votes
Non-regular languages are not closed under intersection.

Let $L\_1 = \\{aa^nb^n \mid n \ge 0\\}$ and $L\_2 = \\{ba^nb^n \mid n \ge 0\\}$. Then $L\_1 \cap L\_2 = \emptyset$ is regular, but neither $L\_1$ nor $L\_2$ are regular.

# Answer
> 0 votes
Intersection of 2 non regular languages means the languages could be anything other than regular, and each class of languages have their own set of closure properties. The problem of finding which class a language belongs to is undecidable.

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