# Question
Title: Range sum query - tree representation efficiency
I was reading about possible solutions to the well known problem:

> Given array `A` with length `N` create a structure that enables
>
> * Answering what is the sum $\sum\_{k=i}^{j} A\[k\]$
> * Updating $A\[k\]$

I've seen most solutions use binary index tree but was curios whether it's possible to just use a regular tree that is built using similar qualities.

So given $A = \[5, 4, 7, 9, 1\]$

I try to construct a tree by creating a tree node for each value that has a start and end (which are just the index in the beginning.

To construct the tree I push all the starting node into a queue $Q$

```
while not Q.empty():
  next <- []
  for i in range(Q.size()):
    f <- Q.front()
    Q.pop()
    if Q.empty():
      if marker:
        parent <- make_parent(f, marker)
        next.push(parent)
      else:
        marker <- f
    else:
      f2 <- Q.front()
      Q.pop()
      parent <- make_parent(f, marker)
      next.push(parent)

  for n in next:
     Q.push(n)

```

After the this ends marker will hold the root

(I have working c++ code but I tried to provide something more abstract and simple)

and to get a sum of range I perform the following (assuming I have an array Nodes that holds all the leaves) and that the query starts with the root of the tree that we created above

```
sumRangeNode(int i, int j, Node* n)
  if i == j
    return Nodes[i]
  if n == null
    return 0
  if j < n->start || i > n->end
    return 0;

  if i <= n->start && j >= n->end
    return n->val

  return sumRangeNode(i, j, n->left) + sumRangeNode(i, j, n->right)

```

The question is does it still have the $\log(N)$ complexity, I've tried to reason about it but struggled with:

* The fact that I might be building a tree with "stragglers" like the $1$ in the example
* The fact that I recursively explore right *and* left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.

# Answer
This approach does work. A "Binary-Indexed-Tree" is just an *implicit* balanced binary tree with some extra "compression". See this answer for the details on how and why this is done, but essentially the purpose is just to run in fewer cycles.

Your approach works fine asymptotically and will probably even perform fine in practice.

---

First, is the resulting tree produced by your queue always guaranteed to be "short"? The answer is yes. The easiest way to see this is notice that your queue's use is naturally into "epochs", where each epoch builds *roughly* one level of the tree.

First, as a simplification, don't bother tracking the `marked` separately from the others. Instead, just repeat the loop until `Q` has only one element, and then let that be your root. This simplifies your state and makes it easier to follow.

```
while q.size() > 1:
   next = []
   while q.size() > 0:
       a := q.pop()
       if q.empty():
           next.push(a)
       else:
           b := q.pop()
           next.push(make_parent(a, b))
   for v in next:
       q.push(v)
root := q.pop()

```

If the queue contains all $n$ before an iteration, then afterwards it will contain either $\lfloor n / 2 \rfloor$ or $\lfloor n / 2 \rfloor + 1$ nodes depending on whether $n$ is is even or odd.

In addition, the maximum height of the nodes in the array will increase by at most one, since each node is only paired with one other (a careful analysis will show it always increases by exactly one, but we don't actually care).

The first observation tells us that the loop will run for $O(\log n)$ iterations. The second therefore tells us that the resulting tree will have height at most $O(\log n)$ since the height of the trees in the queue increase by at most 1 every iteration.

So the tree may not be perfectly "balanced", but its height is still bounded by $O(\log n)$ and thus any operation that runs in time bounded by the tree's height will run in $O(\log n)$ time.

---

> The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.

This is actually straightforward. Suppose your tree has nodes in some levels that look the below, where the `[--...--]` indicate the range of values in the original array that the node represents.

Corresponding queries will be drawn with `(...)` instead. There are (generically) only a few kinds to worry about:

```

    [---------------45-----------------]
    [------------30----------][---15---]
  (- - Q1 - -)
           (- - Q2 - -)
                        (- - Q3 - -)
                        (- - - - - Q4 - - - -)
  (- - - - - - - - Q5 - - - - - - - - - - -)

```

Note that Q2 and Q4 have a symmetric forms that I'm omitting.

* Q1 only traverses the left half
* Q2 only traverses the left half
* Q3 traverses both halves
* Q4 traverses both halves
* Q5 covers the entire range, so it won't traverse either

Thus we only really need to analyze Q3 and Q4.

Q4 totally covers the right half, so that "traversal" is guaranteed to be constant. So only the left half is traverses to any non-constant depth.

Thus the only "interesting" case is the Q3-type query, which only partially crosses the left child range and the right child range.

Note that the type-Q3 query extends *to the left edge* of the right child, and *to the right edge* of the left child.

This means that in the subtrees, there will be *no* type-Q3 queries, which can't extend to *either* edge. All queries will either completely miss each node, completely cover them, or extend past an edge.

So there will be at most *one* type-Q3 query in the entire tree (note that type Q5 also check both children, but that they are "fast").

Since there can only be one of them, you can essentially ignore them in the analysis - at most $O(\log n) + O(\log n) = O(\log n)$ nodes will be visited.
> 2 votes

---
Tags: algorithms, time-complexity, data-structures, binary-trees
---


# Question
Title: Is it a sufficient condition to be in NP?
Suppose the following situation.

* You have a decision problem $D$.
* You know that $SAT$ is $NP$-complete.
* You know that $D\leq\_p SAT$.

Can you conclude that $D\in NP$?

I think it's true because it means that $D$ is at least as hard as any other problem in $NP$.

As I know I am not able to post questions to answer with yes/no: If it's true, can you give a better explanation? If it's false, can you argue why is so?

PD: it's not homework.

# Answer
> 1 votes
You can obtain a non-deterministic polynomial-time Turing machine $T$ for $D$ as follows:

* Since $D \le\_p SAT$, there is a polynomial-time Turing machine $T'$ that maps any instance of $D$ into an instance of $SAT$. Simulate the $T'$ on $x$, where $x$ is the input of $T$.
* Use any non-deterministic polynomial-time algorithm to decide SAT (e.g., guess the value of all the variables in the SAT formula and check if the formula is satisfied). By definition of Karp reduction, $T$ will accept if and only if $x \in D$.

This shows that $D \in \mathsf{NP}$.

---
Tags: complexity-theory, np, complexity-classes
---


# Question
Title: A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?
First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).

**I) Vectors**

A vector have a axiomatic meaning, i.e., given a set $\mathcal{A}$ of objects, their objects can be called *vectors* if and only if they satisfy the vector space axioms $\[1\]$. Of course that, 3D vectors (little arrows), function, matrices and so on are different objects, but under a well defined *vector addition $\boxplus$, and scalar multiplication* $\boxdot$ they are the same: Vectors!

Furthermore, I think that is impossible to talk about more complicated objects like Tensors without a vector space structure underlying the mathematical usage of CS objects.

**II) My doubt**

**So, I would like to know: arrays, lists, strings are the same object as vectors? In other words, they satisfy the vector space axioms?**

$$\* * \*$$

$\[1\]$ https://en.wikipedia.org/wiki/Vector\_space#Definition

# Answer
The objects you mention are not the same. In particular, lists and (mutable) strings are dynamic data structures whereas arrays are not; their size is fixed. Now, whether some set of *instances* of data structures forms a vector space depends on the underlying types, some do, others do not. Considering e.g. boolean arrays of fixed size $n$ together with the usual addition/scalar multiplication of $\mathbb F\_2^n$ yields a vector space, integer arrays of fixed size $n$ do not yield one with the usual operations.
> 1 votes

# Answer
Array: maps consecutive integers to array elements. Often maps integers fro 0 to n-1. Arrays may have fixed or variable size, depending on the implementation.

List: A list is either empty, or it has a first element, and each element except the last has a link to the next element. Allows inserting and removing elements. Depending on the implementation, iterating from the first to the last element, and possibly also iterating from the last to the first element can be done quickly. Often an array is used to implement a list.

Vectors are basically the same as arrays under a different name.

Strings... are complicated. They often use an array of bytes for implementation, but have tons of specialised operations because they are meant for human-readable text. Characters can be represented as ASCII, but more likely UTF-8 etc. String libraries may fully support Unicode, and then your knowledge about arrays will be totally misleading. I recommend looking at strings as a basic type like integer, floating point number, etc.
> 0 votes

---
Tags: arrays, strings, mathematical-foundations, mathematical-analysis, lists
---


# Question
Title: Issue triangulating a font glyph for a specific scenario
I am trying to triangulate TTF glyphs for drawing in opengl. The below image shows an example glyph (Taken fron FontForge application). The X represent control points of a bezier spline, circular and square points represent points on the glyph but they can also be the start / end points of the bezier splines.

I have a triangulation process that can take all these points and render them in opengl, I'd like to render the bezier curves in a shader, I have something that does this and it works. They way I split things up is to take the control points, the start points and end points of the bezier spline and pass those to the bezier shader. For the curves that curve out side the shape I need to remove the control points from the triangulation routine (because I don't want to fill in these triangles completely, I leave that to the bezier shader). For the control points that curve in to the shape I keep them for the opposite reason to above.

For the example above I have shown some additional red lines showing what the new outline would look like with the outer control points removed. That can be seen below.

This shows an example of the issue I am having, I can no longer triangulate this because the red lines at the bottom cross outside the shape and then back in again.

Is there a better algorithm I can use to do this to avoid situations like this?

# Answer
> 1 votes
The points and control points define a spline curve. Your graphics hardware is usually not capable of handling splines directly, so you convert the spline into a polygon. You'll add enough points to the polygon so that the difference between spline and polygon is negligible. Control points are NOT part of the spline! So adding them to your straight line segments is a massive mistake. Don't do that, and your problem goes away.

I'd start with the points that are given to be on the curve, then figure out how many points you need to add between these points to keep the error low enough. You might want to add points just in the middle, so the same letter at a bigger size will contain all the points of a smaller size letter plus additional ones, and the curves will look the same.

For best quality, make sure that the area where the polygon is to the left of the spline and the area where it is to the right is about the same. That's because this could affect line thickness, and that is something very, very easy to spot by the naked eye.

---
Tags: algorithms
---


title: Prove $n! = o(n^n)$ without limits

text:
# Question
Title: Prove $n! = o(n^n)$ without limits
I've already proven the statement using the limit definition of $o(g(n))$ and Stirling's approximation, but how do I prove it using the main definition for $o$ notation provided in CLRS instead?

Definition: $f(n) = o(g(n))$ if for all $c \> 0$ there is $n\_0 \> 0$ such that $0 \leq f(n) \< cg(n)$ for all $n \> n\_0$.

I've tried substituting Stirling's approximation again, but I am unaware of any analytic means of determining $n\_0$ as a function of $c$ due to the presence of the $n$ term as both a base and exponent in the resulting inequality.

# Answer
> 5 votes
You do not need anything as fancy as Stirling. It is easy to see that $n!\cdot n \< n^n$ for all $n\>2$ (just compare the first two terms of $n!=1\cdot 2\cdot\ldots$ witht those of $n^n=n\cdot n\cdot\ldots$).

---
Tags: asymptotics
---


# Question
Title: How to find a cut in a graph with additional constraints?
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+\_{\*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.

I would like to find (if it exists) a subset $S \subset V$ such that $\delta(S) \< 2$, $S$ contains at least one vertex of $C$, and $S \ne C$. Here $\delta(S)$ represents the sum of the weights of the edges that cross the cut $(S, V \setminus S)$.

Is there a polynomial-time algorithm for this problem?

I have thought of two possible approaches:

1. Create a new graph $G'$ using as edge weights $c'(v,w) = -c(v,w)$ and adapt (by updating some LP formulation or DP approach) the max-cut optimization version to this case;
2. Reduce this problem in the problem of partitioning $V$ into two vertex sets $X,Y$ so that the sum of the weights of the edges crossing the cut is \< 2, and $X$ and $Y$ each contain at least one vertex of $C$. However, I couldn't think of any approach to solve this problem, yet.

I know the max-cut problem is hard, which makes me wonder whether there is a polynomial-time algorithm for this problem.

Remark: The proposed solution does not need to follow the presented approaches, they are presented just to help the reader.

I am facing this problem in a fractional separation routine of a routing MILP formulation.

# Answer
The problem can be solved in polynomial time. Here is one algorithm:

* For each $s \in C$ and each $t \in V \setminus C$ such that $s \neq t$:

+ Find the minimum-cost $(s,t)$-cut. By the max-flow min-cut theorem, this can be done in polynomial time using any maximum flow algorithm.
    + If the cost of this cut is \< 2, output it and halt.
* For each $s\_0 \in C$ and each $s\_1 \in V \setminus C$ and each $t \in V \setminus \\{s\_0,s\_1\\}$:

+ Find the minimum-cost cut that contains both $s\_0$ and $s\_1$ in the left part and $t$ in the right part. This can be done in polynomial time by modifying the graph to merge the two vertices $s\_0,s\_1$ into a new vertex $s'$, then finding a minimum $(s',t)$-cut in the modified graph.
    + If the cost of this cut is \< 2, output it (replacing $s'$ with $s\_0,s\_1$) and halt.
* If you reach this point without halting, output that no such cut exists.

There may be more efficient algorithms by modifying algorithms for min-cut instead of min $(s,t)$-cut. I don't know. However, this suffices to show that the problem can be solved in polynomial time.

---

*Proof of correctness:* Suppose a cut $(S,V \setminus S)$ of the desired form exists. Then there are only two ways we can have $S \ne C$:

* Case 1: $C \setminus S \ne \emptyset$: In this case, pick any vertex in $C \cap S$ and call it $s^\*$ (this can be done since $C \cap S \ne \emptyset$) and pick any vertex in $C \setminus S$ and call it $t^\*$ (this can be done since $C \setminus S \ne \emptyset$). Consider the minimum-cost $(s^\*,t^\*)$-cut, $(S^\*,T^\*)$. By construction, $S^\*$ has at least one element of $C$ (since $s^\* \in S^\*$) and $S^\* \ne C$ (since $t^\* \notin S^\*$) and $\delta(S^\*) \le \delta(S) \< 2$, so $(S^\*,T^\*)$ is a valid solution to your problem. Moreover, it will be found by one of the iterations of the first for-loop, namely, when $s=s^\*$ and $t=t^\*$, so the algorithm will correctly find a solution.
* Case 2: $S \setminus C \ne \emptyset$: In this case pick any vertex in $S \setminus C$ and call it $s^\*\_1$ (this can be done since $S \setminus C \ne \emptyset$), pick any vertex in $S \cap C$ and call it $s^\*\_0$ (this can be done since $S \cap C \ne \emptyset$), and pick any vertex in $V \setminus S$ and call it $t^\*$ (this can be done since $S \ne V$). Consider the minimum-cost cut $(S^\*,T^\*)$ such that $s^\*\_0 \in S^\*$, $s^\*\_1 \in S^\*$, and $t^\* \in T^\*$. By construction, $S^\*$ has at least one element of $C$ (since $s^\*\_0 \in S^\*$) and $S^\* \ne C$ (since $s^\*\_1 \in S^\*$) and $\delta(S^\*) \le \delta(S) \< 2$, so $(S^\*,T^\*)$ is a valid solution to your problem. Moreover, it will be found by one of the iterations of the second for-loop, namely, when $s\_0=s^\*\_0$ and $s\_1=s^\*\_1$ and $t=t^\*$, so the algorithm will correctly find a solution.

We see that in either case, if a solution exists, the algorithm will successfully output a valid solution; and those are the only two cases that can occur if a solution exists.

Conversely, if no valid solution exists, it is easy to see that the algorithm will correctly output that no cut exists.
> 2 votes

---
Tags: graphs, np-hard, weighted-graphs, max-cut, bipartite-graph
---


# Question
Title: Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?
I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations.

**What I'm trying to calculate:**

I have number of items. Lets call items a1, a2, ..., an. Each item consists of three components (let's call them x, y and z). Components have a ratio which is percentage. Sum of that ratio is always 1 (or 100%).

There is individual amount of each item and each item has unique tolerance/range +- % (min - max).

Then I have target ratio (x, y and z). I need to figure out what amount of each item must be to find combination which forms target ratio. Items amount must be between their minimum and maximum values. Combined items forms overall x, y and z values with should match target x, y and z

**Here is an example how I started to solve the problem:**

**Item 1:**
Amount: 100
Tolerance: +-30%
x = 0.25, y = 0.50 and z = 0.25
Minimum amount: 100% - 30% = 70% -\> 100 x 0.7 = 70
Maximum amount: 100% + 30% = 130% -\> 100 x 1.3 = 130

(Here 70% and 130% are coming from tolerances and after that min and max amounts can be calculated

**Item 2:**
Amount: 250
Tolerance: +-25%
x = 0.15, y = 0.30 and z = 0.55
Minimum amount: 100% - 25% = 75% -\> 250 x 0.75 = 187.5
Maximum amount: 100% + 25% = 125% -\> 250 x 1.25 = 390.6

**Item 3:**
Amount: 180
Tolerance: +-40%
x = 0.40, y = 0.40 and z = 0.20
Minimum amount: 100% - 40% = 60% -\> 180 x 0.6 = 108
Maximum amount: 100% + 40% = 140% -\> 180 x 1.4= 252

I have a target ratio. In this example let the **target ratio** be:

x = 0.25, y = 0.40 and z = 0.35

I need to find what the amount of each items should be in order to form the target ratio and the items must be in their tolerance ranges (between min and max).

Because of each items has 3 components, without min/max amount the combination can be easily calculated (multiplier for each item) with 3 equations below by using linear equation. Item 1 = a1, item 2 = a2 and item 3 = a3:

0.25 a1 + 0.50 a2 + 0.25 a3 = 0.25 \<- target x = 0.25
0.15 a1 + 0.30 a2 + 0.55 a3 = 0.40 \<- target y = 0.40
0.40 a1 + 0.40 a2 + 0.20 a3 = 0.35 \<- target z = 0.35

After calculating linear equation I get ratio of items: a1 = 0.375, a2 = 0.375 and a3 = 0.25 meaning that a1 = 37.5%, a2 = 37.5% and a3 = 25.0% of overall amount of items. Now x, y and z match with target ratio. At this point I haven't used the minimum or maximum values.

Below is the link to online calculator which I now used to calculate factors using linear equation for test purposes: (Also note that I used a, b and c for item/variable names instead of a1, a2 and a3 in online calculator). Link to online calculator

In this example there are 3 variables/items and 3 equations. Two problems: min/max is not included and there can be for example 10 items/variables in equation. Then the linear equation doesn't work anymore because there are much more items/variables than equations. I'm not sure how but these min and max amount's must be added to the same equation (and is it possible to form a matrix):

a1 \>= 70 \<- item 1 minimum amount
a1 \<= 130 \<- item 1 maximum amount
a2 \>= 187.5 \<- item 2 minimum amount
a2 \<= 390.6 \<- item 2 maximum amount
a3 \>= 108 \<- item 3 minimum amount
a3 \<= 252 \<- item 3 maximum amount

And this is my problem. I have no idea how to combine these together (inequalities and linear equations or am I going totally wrong direction?). I need to be able to get values for a1, a2, a3, …, an. And I need at least one suitable solution (combination) if there is any solution also when there are multiple or infinite amount of solutions.

If someone can help I would be very grateful! Thanks for your time!

# Answer
I find it hard to tell from your question, but your problem sounds like it might be an instance of linear programming, in which case there existing solvers you can use.
> 0 votes

---
Tags: algorithms, mathematical-programming, program-optimization
---


title: How to Sort 2D array with out 1D array

text:
# Question
Title: How to Sort 2D array with out 1D array
Hello I am a new Computer Science student
Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place back into the 2D array but here is the problem aren't we using more space and time because we have to copy the array back. What I have tried so far

```
#include<stdio.h>

#include<stdlib.h>
#include<time.h>

#define ROWS 3
#define COL 5

void sort(int array[], int size);
void random(int rows, int col, int array[][col]);
void print(int rows, int col, int array[][col]);

int main(void)
{
    int set = ROWS*COL;
    int array[ROWS][COL];
    random(ROWS, COL, array);
    print(ROWS, COL, array);
    sort(array[0], set);
    printf("\n\n\n");
    print(ROWS, COL, array);
    return 0;

}
void print(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            printf("%d ", array[idx][kdx]);
        }
        printf("\n");
    }
}
void random(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            array[idx][kdx] = rand() % 10;
        }
    }
}
void sort(int array[], int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

```

But it's not any kind of algorithm and it will not work with dynamic memory you can say since it is just taking benefit of the way `c` store arrays. But things are different for dynamic arrays in c Is there any Algorithm to sort 2D array.

# Answer
> 0 votes
By dynamic I presume you mean either:

`int* array = malloc(sizeof(int)*col*rows);`

or

`int* array = new int[rows][col]();`

In which case its fairly simple:

```
void sort(int* array, int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

//in main or wherever
int* array = malloc(sizeof(int)*col*rows);
random(array, col*rows);
sort(array, col*rows);
free(array);

```

Although that is a very sloooooowwwwww sorting operation. How about researching logsort or quicksort?

---
Tags: algorithms, sorting, c, c++
---


# Question
Title: Mathematical expression for the quantity that we are maximising in the stock buying and selling problem
**Problem Statement:**

Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

**Example 1:**

```
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

```

Here's the link to the problem.

---

I know the solution to this problem but what I'd like to know is how do I write the total profit, (i.e. the thing that we are trying to maximize,) as a mathematical expression? I tried the following (where $n$ is the length of the list):

$$\sum\_{ \substack{1 \leq i,j \leq n \\ i\lt j}} (x\_j - x\_i)\[i,j \text{ unique}\] $$

But this would be wrong since it could include both $i = 1, j = 2$ and $i = 2, j = 3$, and we can't both buy and sell a stock on day 2. Also I had to resort to the Iversonian notation for this, and if possible, I'd like to avoid it.

I don't know if I should be needing two variables for the summation, since we only iterate through the list once for calculating the profit, but I couldn't do it in one variable.

**PS:** This is my first time posting here and I couldn't really decide on the tags for this problem. Pardon me if they are wrong, and let me know which ones to use and I'll update the question. :)

# Answer
> 1 votes
To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x\[1\], \ldots, x\[n\]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b \< s \leq n$. The profit from this single transaction is $P = x\[s\] - x\[b\]$.

However, the problem allows many buys and sells, say $(b\_1, s\_1), \ldots, (b\_k, s\_k)$ for some numbers which must satisfy $$1 \leq b\_1 \< s\_1 \< b\_2 \< s\_2 \< \cdots \< b\_k \< s\_k \leq n.$$ The total profit from these $k$ transactions is $$ P = \sum\_{i = 1}^k \left(x\[b\_i\] - x\[s\_i\]\right). $$ Of course the tricky part is that you don't know ahead of time what $k$ should be, so you're not only trying to optimise over the $b\_i$ and $s\_i$ variables, but also $k$.

---
Tags: discrete-mathematics, greedy-algorithms, mathematical-foundations
---


# Question
Title: Proving that grammar generates language with multi variable inequalities
I am struggling with trying to come up with the inductive proofs to prove that the following grammar is equal to $ L = \\{0^m1^n | m \leq 2n, n \leq 2m \\}$

The grammar is

$ S → A \\:|\\: B $

$ A → 00A1 \\:|\\: C $

$ B → 0B11 \\:|\\: C $

$ C → 0C1 \\:|\\: ε $

How exactly do the proofs for proving $ L \subseteq L(G) $ differ from $L(G) \subseteq L$.

In specific, how do the inequalities affect the format of the inductive proof?

# Answer
The grammar produces words that we can separate into two cases:

1. $S$ gets replaced by $A$, then the second rule is used $k\geq0$ times with the branch that keeps the $A$ present. Then it is used with the branch that replaces $A$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{2k+r}1^{k+r}$.
2. $S$ gets replaced by $B$, then the third rule is used $k\geq0$ times with the branch that keeps the $B$ present. Then it is used with the branch that replaces $B$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{k+r}1^{2k+r}$.

In the first case $m=2k+r,n=k+r$ satisfy $m=2k+r\leq 2(k+r)=2n$ and $n=k+r\leq 2(2k+r)=2m$. In the second case $m=k+r,n=2k+r$ satisfy $m=k+r\leq 2(2k+r)=n$ and $n=2k+r\leq 2(k+r)=2m$. Therefore, all words produced by the grammar belong to $L$.

---

Now, suppose that you take a word in $L$. This would be a word of the form $0^m1^n$ with $m\leq 2n$ and $n\leq 2m$. As before, let's separate the analysis in two cases:

1. Assume that $m\geq n$. Define $r=2n-m$. Observe that since $m\leq 2n$ we have $r\geq0$ and that $r\leq n$, since $m\geq n$. Define $k=n-r=m-n$ and note that $m-r=2(m-n)=2k$. Therefore, $0^m1^n=0^{2k+r}1^{k+r}$. Now you can see how to produce this word using the grammar by following the flow in case 1 above.
2. Assume that $n\<m$. Define $r=2m-n$. Observe that $r\geq$, since $n\leq 2m$ and that $n-r=n-m\geq0$. Define $k=n-m$. Then $m=k+r$ and $n=2k+r$. Therefore, $0^m1^n=0^{k+r}1^{2k+r}$. Now you can see that you can produce this word using the grammar as in case $2$ above.
> 0 votes

---
Tags: context-free, induction
---


# Question
Title: Self study materials for computational complexity theory
I will be taking a computational complexity theory course in about a year, and as the reference material will be Computational Complexity A Modern Approach I am more than confident that without a proper preparation that course will eat me alive. The book seems to have excellent practise problems in the sense that it will build up my CS toolbox. But I am going to need extra material to help me to get to a level where I can confidently self study the book in quetion. Therefore I was wondering that does there exist a solution manual for the book or are conference papers my only option to check how the quality of my proofs/work as a hint when I am stuck?

# Answer
> 1 votes
To self-study from *Computational Complexity: A Modern Approach*, the prerequisites are:

* A few courses in algorithms\* (you should be comfortable reading and writing pseudocode, using Big-$\mathcal O$ notation, and using abstract data structures like lists, sets and hashmaps)
* A course in discrete math
* A course which treats Finite State Machines and formal languages\** (To the point where you are comfortable drawing and reading finite state machines)
* Any course which teaches proofs

Most Bachelor (undergraduate) courses teach all the above. I recommend at least $3$ of the above; the book is written well enough that it remains quite accessible. It does not assume any prior knowledge about complexity classes or Turing Machines.

If you wish to prepare well for a particular course a year in advance, then find out which chapters the course discusses, and read those and then some more, including some exercises (a single-semester course can probably cover less than half the book). Ask the professor which chapters are used, as this changes from one year to the next (Be prepared that the professor has not decided this a year in advance, because she will decide based on what works this year. If she does give an answer, don't treat it as binding or unchanging).

When these requirements are met, my experience is that a big obstacle to overcome is that some students from a CS background have a \`\`coding mindset" in which, when presented with a problem, they try to solve it with an algorithm. That is not the objective here. Instead, the objective is to understand how different problems relate to each other, and to understand what is the computational power different computational models (e.g. Turing Machines, polynomial-size circuits, FSMs, Turing Machines which use a polynomial amount of memory. And what if they are allowed to flip random coins?). We wish to understand how these two things - problems and computational models - map onto each other. Inevitably, this means proving statements of the form "This problem is too difficult to be solved by that computational model", and "This computational model is more powerful than that one'', and you can't program your way out of that. This is more similar in flavour to abstract algebra, in which one simply tries to comprehend all the groups and rings that are out there; you compare their properties, without trying to code up the multiplication for a particular group.

If you have more time, then read *Quantum Computing Since Democritus* by Scott Aaronson, because (it is a fun read and) it motivates the questions that are asked in complexity theory.

If you have infinite time, then you can program a SAT Solver; this will help you get familiar with Boolean formulas.

\*For example, *The Design and Analysis of Algorithms*, by Anany Levitin.

\**I learned from and recommend *Introduction to Languages and the Theory of Computation*, by John Martin. It goes all the way from Finite State Machines to Turing Machines. Any book on formal languages should suffice.

---
Tags: complexity-theory, education
---


# Question
Title: How to implement two stacks in one array?
I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve **Excercise 10.1-2** from **Chapter 10 Elementary Data Structures** from CLRS Second Edition. Here is what its states:

> Explain how to implement two stacks in one array *A\[1..n\]* in such a way that neither stack overflows unless the total number of elements in both stacks together is *n*. The PUSH and POP operations should run in *O(1)* time.

The solution that I have come up with so far is:

> Let array *A\[1..n\]* implement two stacks: *S1\[1..i\]* and *S2\[i..n\]*.
>
> For the *PUSH-S1* and *PUSH-S2* operations, if the stack is 'full' then start pushing elements into the *other* stack (eg. if stack *S1* is full when a new element is trying to be pushed in, then push that element into stack *S2* and vice versa).

The problem with this approach is I will not be able to *POP-S1* or *POP-S2* reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are *(key,value)* pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be *O(n)* (feel free to correct me if I am wrong here), which would not be *O(1)*.

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.

# Answer
> 7 votes
Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays *and* fix their direction of growth accordingly. They don't have to grow in the same direction.

# Answer
> 5 votes
Here are some hints:

1. One of the stacks should grow "up" and the other "down".
2. *There is no way of 'remembering' which element belongs to which stack* \- you are allowed to use additional variables to help you with stuff like that. (This makes more sense with the solution proposed by the first hint.)

# Answer
> 1 votes
The first stack starts at 1 and grows up towards n, while the second starts form n and grows down towards 1. Stack overflow happens when an element is pushed when the two stack pointers are adjacent.

# Answer
> 1 votes
This method efficiently utilizes the available space. It doesn’t cause an overflow if there is space available in arr\[\]. The idea is to start two stacks from two extreme corners of arr\[\]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.

# Answer
> -1 votes
I thought of another solution. If we split the array into half (or as close as possible if the array has odd length) and make the first element go into the first stack and the second element go into the second stack. While popping we could retrace these steps. However, by implementing in this way would it violate any stack principle?

# Answer
> -1 votes
I guess there are many solutions to this problem. For the particular case of 2 stacks in one array, I like the solution of starting one stack at the first index and the second one at the last index. As the stacks grow, you know the array is full when the heads of each stack are adjacent.

However, you could implement this the same way as implementing K stacks in 1 array. If you store a queue with the free slots available, you have everything you need. For instance, you would know in which slot you would add your next value (independently from the stack you are pushing to). Everytime you push or pop a value, you pop or push a free slot, respectively. Storing such a queue might be considered overhead, still, the space complexity would remain the same.

The only thing you would have to do is to properly set the pointers (or indexes, after all, we are using an array).

Here is a short description, space complexity `O(N)` where `N` is the size of the array. Pop/push complexities `O(1)`.

```
1) initialize a queue holding the free slots from 0 to N - 1.
2) initialize the heads of all the stacks to -1 (the stacks are empty)
3) POP: given a stack, set the head of that stack to the next element
   pointed to by the current head, and then remove the current head.
   Enqueue the index of the slot which just came free to the queue of free slots.
4) ADD: get the next available index from the queue of free slots.
   Create your new node in the new slot, and make it point to the current
   head of that stack. Then set the current head of that stack to the newly added node.

```

# Answer
> -2 votes
Some hints

Make an array

Array elements with odd index are for stack1

Array elements with even index are for stack2

Now You can grow both stacks from left to right direction

Just keep variables that maintain top position of both stacks. You won't have to search the array.

and if stack1 becomes full while stack2 is empty you can keep track for additional stack1 elements in the stack2 by maintaining some variables

---
Tags: data-structures, arrays, stacks
---


title: Cashier Scanning Algorithm Problem

text:
# Question
Title: Cashier Scanning Algorithm Problem
I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.

> A cashier only has `x` time to scan a person's goods. The goods come 1 item per time step in a conveyor belt. In one time step, the cashier can either scan an item or bag the item (so when bagging, the cashier misses the item on the conveyor belt for that time step). The place to hold scanned, unbagged goods has a max capacity of `c`, where each good takes 1 unit space. However, once the cashier starts to bag scanned items, the cashier must bag all unbagged scanned items. The cashier also wants to ensure he makes the most money possible. How would the cashier go about choosing the goods such that he maximizes the amount of money the buyer spends. What is the maximum amount of money the cashier can make?

This seems to be a modification of the 0-1 knapsack problem, where the max capacity `c` is the max capacity of the knapsack, the price of the item is its value in the knapsack, and all items have a 1 unit space. I am, however, confused about how I would incorporate the "conveyor belt" of missing items and the moving of items out of `c` into the algorithm. I imagine this could still be run in $O(nc)$ time with $O(c)$ space complexity (in fact the original problem statement says it should be possible in these bounds). How would I go about modifying the 0-1 knapsack problem for this?

# Answer
> 1 votes
Let the $i$th item have profit $p\_i$, and assume there are $n$ items passing by.

We can construct a graph where the nodes are pairs $(k, b)$ where $k$ is the number of timesteps, and $b$ is the number of items in our bagging area. We have $0 \leq k \leq x$ and $0 \leq b \leq c$.

Then, avoiding invalid nodes and/or nonsensical self-edges,

1. Add edges from $(i-1, b)$ to $(i, b + 1)$ with weight $-p\_i$. These represent scanning an item.
2. Add edges from $(i, b)$ to $(i + 1, b)$ with weight $0$ for all $i$. These represent skipping an item.
3. Add edges from $(i, b)$ to $(i + b, 0)$. These represent bagging all scanned items.

Now we have a directed weighted acyclic graph, in which we can find the longest path in linear time. And the longest path between $(0, 0)$ and $(x, 0)$ precisely gives us the maximum profit (and following the path also gives us the steps used).

There are $O(cn)$ edges, and thus that is our complexity.

---
Tags: algorithms
---


# Question
Title: How should I understand left/right derivations of grammars and parse trees?
I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.

$S \to NP$ $V$ $NP$
$NP \to$ the $N$
$N \to$ cat | mouse
$V \to$ ate

**LEFT**

$S\to NP$ $V$ $NP$
$S\to$ the $N$ $V$ $NP$
$S\to$ the $N$ $V$ the $N$
$S\to$ the cat $V$ the $N$
$S\to$ the cat ate the $N$
$S\to$ the cat ate the mouse

**RIGHT**

$S\to NP$ $V$ $NP$
$S\to NP$ $V$ the $N$
$S\to$ the $N$ $V$ the $N$
$S\to$ the $N$ $V$ the mouse
$S\to$ the $N$ ate the mouse
$S\to$ the cat ate the mouse

**My Thoughts**

My lecture material says that we operate on the left/rightmost non terminal. I'm not 100% sure how to differentiate terminals and non-terminals but I assumed that if it became an English word it was a terminal hence I skipped it as long as there was a production remaining with another identifier in it.

**Parse Tree**

I know that the parse tree should be the same for the left and right derivation of the above grammar, just don't know how to build one. All examples I find online are too complex for my understanding. I just started learning about this stuff very recently. I genuinely don't know how to create the parse trees.

# Answer
A non-terminal is something with a production rule. You're correct that words aren't non-terminals. They are terminal precisely because there is no production which expands the word.

In a leftmost derivation, every step must expand the leftmost non-terminal. The leftmost non-terminal is the non-terminal which is closest to the left :-). In $\text{the N V NP}$ , the leftmost non-terminal is $\text{N}$. So if you choose a derivation step which expands $\text{NP}$, that's not a leftmost derivation.

In a parse tree, the root is whatever the root of the grammar is ($\text{S}$ in this case) and each node has as its children the symbols on the right-hand side of the production which is used the expand that particular non-terminal. Terminals are leaf nodes; they have no children.
> 1 votes

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


# Question
Title: Need help with this runtime of algorithm with double loops that results in 0
I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it.

> ```
> for (i = 0; i <= n; i++) do
>      j = 2*i
>      while j <= n do
>          j = j + 1
>          print("Hello World")
> end
>
> ```

Then I get the runtime
$Θ(\sum\_{i=1}^n 1 + n -2i)=Θ(n+n^2-n(n+1))=Θ(0)$??

# Answer
> 1 votes
The result you state is clearly wrong, since the second line (for example) runs $n+1$ times. The problem is in your sum, which you don't explain how you got to.

Here is the code again, with line numbers:

```
1: for i in 0,...,n:
2:   j = 2*i
3:   while j ≤ n:
4:     j = j + 1
5:     print "hello world"
6:   end while
7: end for

```

The running time heavily depends on the model. However, assuming that $n \geq 0$, the running time will be proportional to the number of times that lines 2 and 4 are executed. Line 2 is executed $n+1$ times. As for line 4, for a given value of $i$, it is executed $\max(n-2i+1,0)$ times (for example, if $2i = n$ it is executed once). In total, it is executed this many times:

$$ \sum\_{i=0}^n \max(n-2i+1,0). $$ In order to calculate this sum, it will be easier to consider separately the cases $n$ even and $n$ odd. If $n = 2m$ then the maximal $i$ for which $n-2i+1\>0$ is $m$. Furthermore, the summand goes from $n+1$ down to $1$ in jumps of $2$; there are $m+1=n/2+1$ summands in total. Therefore the sum equals $$ 1 + 3 + 5 + \cdots + (n + 1) = \frac{(n/2+1)(1+(n+1))}{2} = \frac{(n+2)^2}{4} = \Theta(n^2). $$ If $n = 2m+1$ then the maximal $i$ for which $n-2i+1\>0$ is also $m$. This time, the summand goes from $n+1$ down to $2$, and there are $m+1 = (n+1)/2$ summands. Therefore the sum equals $$ 2 + 4 + 6 + \cdots + (n+1) = \frac{((n+1)/2)(2+(n+1))}{2} = \frac{(n+1)(n+3)}{4} = \Theta(n^2). $$ In total, we get that the number of times that line 4 is executed is $\Theta(n^2)$ in both cases, and so $\Theta(n^2)$ overall (this is a subtle point, and requires a short argument).

We conclude that the total running time is $\Theta(n^2)$. (This *may* need the assumption $n\>0$, depending on your exact definition; you can take $\Theta(n^2+1)$ if you want to be extra sure.)

# Answer
> 0 votes
Sum $\sum\_{i=1}^n (1 + n -2i)$ is wrong calculation, because while loop produce steps only when $2i \leqslant n$.

---
Tags: algorithms, runtime-analysis
---


# Question
Title: What does it mean that B-tree leaves carry no information?
According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".

What does it mean that they **carry no information**?

Does that mean that there are no more pointers to children nodes? (kinda redundant to say that as they are the leaves no?)

In the more literal meaning I understand from it that there is actually no information there (AKA the nodes values vs. the key which is used to search) but that doesn't make sense as each key in a B-tree appear only at one node and thus must have a value associated to it or at least a pointer to the data.

Please notice that I'm not referring to a B+ tree where indeed there is an extra layer just for the data/values/information and the keys are indeed duplicated between nodes levels.

# Answer
> 1 votes
So according to CLRS (quotations):

* Any "satellite information" associated with a key is stored in the same node as the key
* Leaf nodes have no children, so their c*i* fields \[pointers to child nodes, added for clarification\] are undefined
* A common variant on a B-tree, known as a B+-tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes

There was no mention about leaf nodes carrying no keys/information/etc...

So basically leaf nodes do carry keys in order to actually get the data you search for (just like all the other nodes), they just don't carry pointers to child nodes.

And why Donald Knuth wrote (according to Wikipedia and other sources) that leaf nodes "carry no information" is beyond me, maybe he was referring to a different variant of B-tree... I honestly don't know.

---
Tags: data-structures, trees, b-tree
---


# Question
Title: How to show a function is primitive recursive by induction?
I know, loosely speaking, if we can define a function $f$ in term of \begin{align} &f(0,\vec{x})=g(\vec{x})\\ &f(n+1,\vec{x})=h(f(n),n,\vec{x}) \end{align} where functions $g,h$ are primitive recursive. Then $f$ is primitive recursive.

However, what it means to show a function is primitive recursive by induction?

I had read above explaination on page 93 on book $\textit{Computability}$ by Epstein and Carnielli, but still I'm not sure if I got the idea. Could someone provide some examples about how a inductive definition shows a function is primitive recursive?

# Answer
Wikipedia gives such an example. You haven't stated the definition of *basic functions* or *basic operations*, so I will assume the Wikipedia definition.

The successor function $S(x) = x+1$ is a basic function, and so is assigned 0. Projection functions such as $P\_1^1(x) = x$, $P\_2^3(x,y,z) = y$ and $P\_3^3(x,y,z) = z$ are also assigned 0. The constant function $z(x) = 0$ is also assigned 0.

The function $g(x,y,z) = S(P\_2^3(x,y,z)) = y + 1$ is a composition of two functions assigned 0, and so is assigned 1.

Using these functions, we can define a function $h(x,y)$ by primitive recursion: $h(0,y) = P\_1^1(y) = y$, and $h(S(x),y) = g(x,h(x,y),y) = h(x,y) + 1$. This function is assigned 2, and you can check that $g(x,y) = x + y$.

The function $r(x,y,z) = h(P\_2^3(x,y,z),P\_3^3(x,y,z)) = g(y,z) = y + z$ is assigned 3.

We can define a function $k(x,y)$ by primitive recursion: $k(0,y) = z(y) = 0$, and $k(S(x),y) = r(x,k(x,y),y) = k(x,y)+y$. This function is assigned 4, and you can check that $k(x,y) = x\cdot y$.
> 1 votes

---
Tags: computability, induction, primitive-recursion
---


# Question
Title: Does FOL extended with least-fixed points satisfy the Compactness Theorem?
I am aware that first-order logics (FOL) satisfies the compactness theorem. That is, if a FOL theory is insatisfiable, a finite subset of the axioms of such theory is insatisfiable too.

Is it the case that FOL extended with least-fixed point (LFP) satisfies the compactness theorem too?

# Answer
No, it does not satisfy compactness anymore.

Least fixed point operators can let us define, for example, the standard part of a model of $\mathsf{PA}$. The standard part of a model $\mathfrak{A}=(A;+^\mathfrak{A},\times^\mathfrak{A},0^\mathfrak{A},1^\mathfrak{A})$ of $\mathsf{PA}$ is just the smallest subset of $A$ containing $0^\mathfrak{A}$ and closed under $n\mapsto n+^\mathfrak{A}1^\mathfrak{A}$. But this is exactly a least fixed point definition: the standard part of $\mathfrak{A}$ is the least fixed point of the operator $$\Phi(P): x=0\vee\exists y(P(y)\wedge y+1=x).$$

This in turn lets us pin down the standard model of $\mathsf{PA}$ up to isomorphism by the theory $\mathsf{PA}$ \+ "Every element is standard." But this contradicts compactness: no compact logic can ever pin down an infinite structure up to isomorphism (this is really just the observation that the upwards Lowenheim-Skolem theorem is just a compactness corollary).
> 1 votes

---
Tags: first-order-logic, descriptive-complexity
---


title: 3SAT to 3SAT-WITH-MAJORITY reduction

text:
# Question
Title: 3SAT to 3SAT-WITH-MAJORITY reduction
I've been struggling with reduction while solving this exercise and I would really appreciate some help if not the solution.

Problem: \[3-SAT-WITH-MAJORITY\]

Input: A set of clauses $C = {\\{c\_1, \dots, c\_k}\\}$ over $n$ boolean variables $x\_1, \dots, x\_n$ where every clause contains exactly three literals.

Output: YES if there is a truth assignment to the variable such that both

* every clause is satisfied under the assignment
* there are at least k/2 clauses in which all 3 literals are set to true under the assignment.

NO otherwise.

Show that this problem is NP-complete.

# Answer
> 3 votes
Hint: Take a SAT instance $C$ with $k$ clauses and introduce $3k$ new variables $\top^i\_1, \top^i\_2, \top^i\_3$ for $i \leq k$ and construct $k$ new clauses $c^\top\_i = \\{ \top^i\_1,\top^i\_1,\top^i\_3 \\}$. Let $C' = C \cup \bigcup\_{i=1}^k c^\top\_i$ be the input to 3SAT-WITH-MAJORITY.

---
Tags: complexity-theory
---


# Question
Title: Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions?
The transfer of control is often completed through some type of software interrupt instruction. These special instructions result in the CPU to save the current state of the machine and transfer control to a function in the operating system. They are like a cross between an ordinary subroutine call instruction and a hardware interrupt. My question is that Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions?

# Answer
> 1 votes
System calls could be done, and have been done, with normal (normal enough) call instructions. However, the *operation* wouldn't be a normal call: the privilege level changes, and it is unsafe to allow calling arbitrary offsets (which might not be the entrypoint of a subroutine) with a lot of privileges. So there should be some mechanism that both limits the possible destinations and changes the privilege level. That mechanism is similar in function to how a dedicates system call instruction would work, but it could be triggered by a normal subroutine call instead.

Call gates on x86 are an example of that, a mechanism that allows system calls to some locations that have been set up in advance, by using relatively normal far calls. 32bit code does not normally use far calls though, so it's not really the same thing as a completely standard subroutine call. Far calls were more usual in the 16bit era, and the 80286 which introduced call gates was still a 16bit processor, but it seems that call gates did not see much use on the 80286. Similar mechanisms existed on some other old processors.

# Answer
> 0 votes
Because the system call implicitly changes privilege to kernel level. His can't be ensured when doing regular routine calls. Besides, the place you want to call (inside the kernel) is already off-limits for userland.

---
Tags: operating-systems
---


# Question
Title: Is the heap in "Data Structures Algorithms in Java" by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?
In the book, *Data Structures Algorithms in Java* Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an

> "Example of a heap storing 13 entries with integer keys. The last position is the one storing entry (13,W)."

I've recreated the a similar image using qtree-tikz with my own depth and height calculations in the box on the left.

According to the book,

> A heap *T* storing *n* entries has height $h = \lfloor \log n \rfloor$.
>
> **Justification:** From the fact that *T* is complete, we know that the number of nodes in levels $0$ through $h-1$ of *T* is precisely $1+2+4+...+2^{h-1} = 2^{h}-1$, and that the number of nodes in level $h$ is at least 1 and at most $2^h$. Therefore
>
> $n \geq 2^h -1 +1 = 2^h$ and $n \leq 2^h -1 +2^h = 2^{h+1} -1$.

Here is where I see a problem. I added the depths and heights for nodes at each level according to my understanding of trees in the box to the left of the tree. The example tree Figure 9.1 shown above obviously has 7 inner nodes and although depth level 3 would have 8 nodes, it is unfull at 6 nodes.

If I follow the "Justification", I end up with the following

* > "we know that the number of nodes in levels 0 through $h-1$ of *T* is $2^h-1$"

$2^2 -1 = 3 \neq 7$.
* but my understanding is that the $7$ would match the formula $2^3-1$, which means the $h$ referred to in the text must be $h=4$. But the $h =3$ from my understanding. **Herein lies the problem.**

I am being forced to conclude that there must be a missing level of sentinels, $2^3 -1 = 7$ and the only way to get a power of 3 in those formulas is to have a height of 4. But why on earth would the authors, who otherwise explain everything in detail, not make important piece of information explicit? Or, did I miss something? I would appreciate a thorough explanation to help me understand the proof. It also seems that the authors throw around the term "level" loosely, sometimes meaning depth level and sometimes meaning height level.

I should also mention that earlier in the book, on page 286, they provide a definition for the *height* of a tree without any examples (and it is a bit cryptic).

> We next define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

> * If $p$ is a leaf, then the height of $p$ is $0$.
> * Otherwise, the height of $p$ is one more than the maximum of the heights of $p$'s children.

# Answer
You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric series:

$$ 2^0 + \cdots + 2^{h-1} = \frac{2^h - 1}{2 - 1} = 2^h - 1.$$

I think that a good rule of thumb for distinguishing between height and depth is that *depth* is the more useful one (the number of nodes on a complete level at depth $d$ is $2^d$, and a node's depth does not change as the tree grows), while the height $h$ is only really useful when looking at the tree as a whole (and is just the upper bound for depths).
> 1 votes

# Answer
After accepting Joppy's answer for clearing up my confusion, I'd like to elaborate with a more precise expression. I would have explained it in terms of depth, since we're starting with the root node:

$$ \sum\_{d=0}^{h-1} 2^d = 2^h -1 \left. \right\vert \text{d is the depth (at each level) and h is the total height of a binary tree.} $$

This works because the number of nodes at each level is $2^d \left. \right\vert \text{where d is the depth of the current level}$.

$d = 0 \rightarrow 2^0 = 1$

$d = 1 \rightarrow 2^1 = 2$

$d = 2 \rightarrow 2^2 = 4$

$d = 3 \rightarrow 2^3 = 8$
> 0 votes

---
Tags: trees, binary-trees, heaps
---


# Question
Title: Closest point in embedded simplicial complex
Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k\< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded in $\mathbb R^3$ ($n=3$) and one-dimensional chains of line segments ($k=1$) in $\mathbb R^n$.

**Given many points $\\{x\_i\\}\_{i=1}^M\subset \mathbb R^n$, is there a data structure/algorithm for efficiently answering closest point queries of the form $\min\_{y\in\mathcal S} \\|x\_i-y\\|\_2$?**

I'm looking for a generalization of methods that handle, e.g., closest point on a triangle mesh. Pointers to existing implementations are also much appreciated!

# Answer
If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries. For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-Tree work fine with millions of points.

C++ implementations are available from libSpatialIndex, Boost R-Tree, PH-Tree C++, and many others.

For Java implementations, have a look at my TinSpin Index Library or any other one.

Disclaimer: I am the developer of TinSpin and PH-Tree.

**EDIT**

I assumed by `point` you mean `vertex`, my mistake. I think you can adapt the approach if you are looking for nearest points on any simplex: Instead of storing vertices in the index, you can store the 2D/3D/$k$D bounding boxes of all geometries (vertices/lines/triangles/..) in the tree. Then there are two options:

1. Use a nearest neighbor search to go through all bounding boxes and their elements to calculate the actual distance. You will have to check and compare these distances until the distance of the bounding boxes becomes larger than the current closest simplex you could find.
2. Implement a custom distance function that returns nearest neighbors sorted by their closest point. This may require in depth knowledge of the index you are using.

This should still result in a $O(log(numberOfSimplexes))$ unless there are a lot of elongated geometries with overlapping bounding boxes. For example, a bad case would be a spherical data space with all geometries being lines that represent the diameter. By intuition, I think R-Trees or the PH-tree are best suited for this kind of search.

I have little experience with this, but for larger dimensionality $k$, the bounding box approach may work less well because boxes in $k$-dim space tend to become very large, so they may be a lot of overlap (or maybe not, because the whole dataspace is also growing exponentially?).

In any case, it can make sense to break up 'flat' objects (such as line segments in 3D) in to multiple segments in order to represent them with a chain of smaller bounding boxes instead of one large bounding box. Having several small bounding boxes if more efficient than one large one.
> 1 votes

---
Tags: data-structures, computational-geometry, amortized-analysis, topology, space-partitioning
---


# Question
Title: Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?
There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:

There are n tasks, each task `t_i` has a weight `w_i` and a length `l_i`. Find an order of tasks `t_1`, ... `t_j`, ..., `t_n` that minimizes the total cost of completion, where the cost of completion of each task is `c_j * w_j`, where `c_j` is the time it has passed since you started working on the first task until you finished the jth task.

If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:

`task_1` with `w_1 = 1` and `l_1 = 5` and

`task_2` with `w_2 = 4` and `l_2 = 2`

If we started first `task_1`, its cost would be `5 * 1 = 5` while if we started first `task_2`, its cost would be `2 * 4 = 8`. But, the cost of completing `task_2` after `task_1` is `(5+2) * 4 = 28`. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.

Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio `w_i/l_i`.

Which part of the problem hints that the solution doesn't require to check all the possible orders?

The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.

# Answer
> 4 votes
In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.

It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot improve the solution.

Now you look for a criterion when swapping two tasks would improve the solution. For an optimal solution, that criterion must fail for any two consecutive tasks. And lucky enough there is a simple criterion.

So any problem where tasks must be performed consecutively, and where swapping two tasks doesn't affect all the other tasks, you can solve if you can determine which order of the two tasks is better.

This doesn't work for the travelling salesman problem for example, because swapping two cities affects other cities as well.

# Answer
> 1 votes
Generally speaking, we have a few standard paradigms for designing algorithms: divide-and-conquer, dynamic programming, greedy algorithms, and reduction to an existing known problem. When you have no idea how to solve a problem, one useful strategy is to try each of those paradigms in turn for a little while: spend a little time looking for a divide-and-conquer algorithm, spend a little time looking for a dynamic programming time algorithm, spend a little time looking for a greedy algorithm, and so on. With practice, you may be able to develop a feeling for which paradigms are most likely to be suitable for any particular problem and let you direct your energy, but as a starting point (or if you have no particular hunch), then you can try each one of them.

Now when you spend time looking for a greedy algorithm, usually if a greedy algorithm exists, it will be very simple. Most problems can't be solved with greedy algorithms, but the ones that can, usually have a very simple algorithm. There's a basic approach to finding greedy algorithms: you brainstorm a few plausible candidates (usually there are a few natural ones), then check each one to see if it is correct. See How to prove greedy algorithm is correct for methods to check whether a candidate greedy algorithm is correct. Usually, you can quickly eliminate most candidates that aren't correct (e.g., because they don't pass random testing). So, if you get lucky and one of your candidates is actually a correct algorithm, usually you'll be able to quickly get some confirmation that it looks very promising.

With all of that background, I can answer your question. How would you find this algorithm? You'd find it by spending a little time on each major algorithm design paradigm, including greedy algorithms; and you'd have a good chance of finding the particular order if you brainstorm for candidates, and likely you'll come up with this as one of the candidates. How would you avoid looking for complicated solutions first? There's no silver bullet, but it's often helpful to spend a little time on each paradigm before spending too long on any one paradigm. Also, as you get more practice, you may find that you develop an intuition or sense for which paradigms are most worth trying, for any particular problem, which might guide you in this particular case to make sure to try a few greedy algorithms. In this case, it's pretty easy to see how I might make a "greedy" choice at each step, without regard to its future consequences, so it's natural to try a greedy algorithm whenever you have a sequence of choices to make.

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


title: What does "lookahead" refer to?

text:
# Question
Title: What does "lookahead" refer to?
I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.

What does "lookahead" refer to? How does this relate to LL, LR, LALR? Basic examples would be great, as I'm not well versed in this subject.

# Answer
"A good driver drives in three cars. His own car, the car behind him, and the car in front of him". (Bertold Brecht).

"Lookahead" is what you do when you drive a car. You look ahead and make decisions not just based on things around you, but also based on things ahead of you.

A parser with a lookahead of 1 makes decisions based on the current symbol and the symbol ahead of it. That often keeps it from making the wrong parsing decisions.
> 4 votes

---
Tags: turing-machines, automata, regular-expressions, parsers, syntax
---


# Question
Title: Are functions that are equal to a constant as you take a limit to infinty O(1)?
The below function converges to a constant as you take n to infinity.

$f(n)=(1 + \frac{1}{n})^n$

$\lim \limits\_{n \to \infty}(1 + \frac{1}{n})^n = e$

Would this imply that it is O(1) since you can just upper bound it with a constant?

# Answer
> 0 votes
By definition of $O$ notation, if you can find a constant $c$ and $n\_0$ such that $f(n) \< c g(n)$ for all $n \> n\_0$, we can say $f(n) = O(g(n))$. In this case, suppose $n\_0 = 1000$ and $c = 3$ and $g(n) = 1$. You can show that as $f(n)$ is increasing function and $\lim\_{n\to\infty}f(n) = e$, it is true $f(n) \< 3 g(n)$ for all $n \> 1000$. Therefore, $f(n) = O(1)$.

# Answer
> 0 votes
Bounded functions are O(1). Functions that are bounded from some point on are O(1), and they are exactly the functions that are O(1). Any function with a limit is bounded from some point onward, but many other functions are as well and therefore O(1).

---
Tags: asymptotics
---


title: Two-phase locks: why is it better?

text:
# Question
Title: Two-phase locks: why is it better?
I'm reading Arpaci's Operating Systems: Three Easy Pieces, the chapter on Locks.

At the end of the chapter, they present Two-phase locks (section 28.16). They say

> A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.

I understand this may only be useful in a multiprocessor environment, is that right?

Also, it seems a little arbitrary to me to wait the first time and then go to sleep. I mean, I don't see why this would be such a great improvement over going directly to sleep in the case the lock is being held.

Is there anything I'm missing?

Thanks in advance!

---

Below is the whole paragraph on Two-phase locks:

> One final note: the Linux approach has the flavor of an old approach that has been used on and off for years, going at least as far back to Dahm Locks in the early 1960’s \[M82\], and is now referred to as a two-phase lock. A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.
>
> However, if the lock is not acquired during the first spin phase, a sec- ond phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later. The Linux lock above is a form of such a lock, but it only spins once; a generalization of this could spin in a loop for a fixed amount of time before using futex support to sleep.
>
> Two-phase locks are yet another instance of a hybrid approach, where combining two good ideas may indeed yield a better one. Of course, whether it does depends strongly on many things, including the hard- ware environment, number of threads, and other workload details. As always, making a single general-purpose lock, good for all possible use cases, is quite a challenge.

# Answer
> 1 votes
To answer your first question: Spinlocks are only useful in a multiprocessing environment.

Spinning is waiting. If you're waiting for a lock to be released, and it must occur on the current CPU because there are no other CPUs, then a context switch must occur for the lock to be released. It follows that the current thread should just sleep, because it will need to anyway.

Of course, in a single-CPU environment, you can still spin-wait for other types of resource, such as a hardware device.

As Joppy indicated in the comment, putting a thread to sleep is a much heavier-weight operation than sitting in a loop. Whether or not it's worth spinning depends on a bunch of things, such as how expensive it is to sleep and context switch, and how long the lock is likely to be held.

There is a huge design space here. The default behaviour of Solaris kernel locks, for example, is to spin if the owner is running on another CPU, and sleep otherwise, the theory being that if the owner is making progress, it's more likely that the lock may be released soon. As a nice bonus, this automatically does the "right" thing on a single CPU.

---
Tags: concurrency
---


title: Determing Big Oh Of Given Data

text:
# Question
Title: Determing Big Oh Of Given Data
I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should determine the exponent of the dominant term and provide an estimate for the coefficient on the dominant term.

---

I made the following graph of the data and a log/log graph to try and figure it out. At first I thought it might have been 1/n or something along those lines but as n gets quite large, the execution time increases again instead of asymptotically approaching a value.

The log graph having such a distinct pattern leads me to believe that the answer will lie there but I'm stuck as to where to go from here. Any help would be great.

# Answer
You can't. You can't infer big-O complexity from a finite set of data points, as big-O complexity is about asymptotics. See, e.g., How to fool the plot inspection heuristic?.
> 1 votes

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


# Question
Title: Is the Tomasi-Kanade factorization still commonly used as a modern computer vision technique?
My understanding is that, in very rough terms, the Tomasi-Kanade algorithm published in 1992 describes a way to reconstruct the 3D structure of an object from multiple images of that object, given that you have a reliable method of identifying important structural features from the 2D images.

A lack of general information on the topic has prompted me to ask this question: is this method deployed in any recent computer vision systems? Has it been followed up by other methods? Finally, if anyone would like to suggest any resources containing background information that are helpful in digesting the paper, please do. Despite being familiar with the mathematics, I had a hard time making any sense of it.

# Answer
3D reconstruction method proposed by Tomasi and Kanade is a pioneering work and has delivered fruitful insights, but it does not seem to be commonly used 'as-is' in modern applications, or at least in research.

I guess this is because, at the moment of early 90's, there were not plenty numbers of local feature detector & descriptor as nowadays, ego-motion estimation (and 3D reconstruction) mainly relied on optical flow. However, since the appearance of local feature descriptors like *SIFT*, such ego-motion estimation method gradually shifted to utilize local feature descriptors to find sparse corresponding points among images due to its robustness and real-time performance. (Note that this is highly active topic in computer vision research, there are lots of proposals on how to estimate frame-by-frame motion. For your reference, one of the recent algorithms, named *ORB-SLAM*, integrates *FAST* as a detector and *ORB* as a descriptor.)

Talking about global structure, recent algorithms use bundle adjustment, which minimizes reprojection error to estimate motion in higher accuracy. This sometimes comes with pose graph optimization to handle loop detection in the sequence of images.

Sorry I have no idea which literature would help to read the article, but if you want to get a glimpse of what visual odometry is, I would suggest the tutorial coordinated by Prof. Scaramuzza.

Hope it helps.
> 1 votes

# Answer
The Tomasi-Kanade algorithm is probably not used too much these days, though it is an important algorithm that provides a lot of insights and opens interesting avenues of research. I would say that the main drawback of the algorithm is not that it assumes an orthographic camera, but that it requires a full data-matrix, in which all points are visible in every view. This is usually not realistic in practice.

The most significant step to address the first issue was the Sturm-Triggs extension of the algorithm to true perspective camerad (i.e. the pinhole camera model). There were several follow-ups to this, trying to improve on the original method, including papers by Shyjan Mahmood, John Oliensis and others, to a point where the algorithm works well for the perspective model, as long as points are visible in all views.

The situation where there are gaps in the data is addressed by the research topic of low-rank matrix factorization with missing or noisy data. Unlike the low-rank factorization of a full data matrix, where a least-squares solution is available using SVD (as in the original Tomasi-Kanade algorithm) low-rank factorization of a matrix with holes, or per-entry weights, is NP hard. Nevertheless, various methods of trying to do this have been proposed, and a good place to look at this is the paper "Damped Newton Factorization for matrix factorization ..." by Buchanan and Fitzgibbon. This discusses and compares various methods.

Essentially the same sort of algorithm is used for dynamic structure and motion, or multi-object structure and motion. A good place to start looking into that is the work of Rene Vidal, who has looked at these problems in great depth.
> 3 votes

# Answer
Tomasi-Kanade factorization algorithm relies on the assumption of an orthographic camera model. Most of the current non-rigid SfM algorithms also rely on this assumption. So, although the algorithm in its original form might be outdated for ordinary SfM applications, some of the underlying ideas are still currently used in the non-rigid scenario.
> 0 votes

---
Tags: algorithms, computer-vision, linear-algebra
---


# Question
Title: Minimum spanning tree of multi directed graph
I have problem of inferring a rooted tree out of a connected simple graph.

The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of condition:

* There is a known root, which is `s` in the following example.
* We know directions of some edges **if they are chosen**. These edges are **not** chosen yet, or the problem becomes a Steiner tree problem.

Note that numbers on edges are their weights. So we will get `s -> b -> c -> a` if a normal min spanning tree is applied, but the direction of edge `ac` is wrong. On the other hand, we cannot use Chu–Liu/Edmonds' algorithm for spanning arborescence of directed graphs, because we don't know and cannot infer the direction of edge `bc`.

We can infer some edges' directions according to the position of the root. For example, in the example, we know `s -> b` and `s -> a`.

**It seems that the problem can be solved by two steps**:

1. turn the simple graph into a multi-graph. For edges (in the original simple graph) whose directions are unknown, we represent them in a multi-graph using two directed edges between two vertices with inverse directions.
2. We find the minimum oriented spanning tree of this multi-graph.

---

## Oriented Spanning Tree

In the final section of spanning tree, Wikipedia, oriented spanning tree is mentioned and a paper \[levine2011sandpile\] is referred. The problem fits the setting. It says:

> Given a vertex `v` on a directed multigraph `G`, an oriented spanning tree `T` rooted at `v` is an acyclic subgraph of `G` in which every vertex other than `v` has outdegree 1.

*Note that the term "outdegree" is a bit confusing, which I think should be "indegree". But it doesn't matter, because it just restricts the simple subgraph to be a directed tree with root being source or sink.*

But it is not clear to me how an algorithm can be implemented according to that paper.

---

# Answer
> 0 votes
As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).

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


# Question
Title: Finding closest edge to a point in a planar graph
I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a `O(log n)` complexity.

So far I was not successful in finding any reference that would discuss this specific problem. Is there any treatment you know of?

For this problem, we can assume that the graph is embedded in a Euclidian plane in a known way, where vertices are mapped to points and edges are mapped to straight line segments.

# Answer
## Use a Voronoi diagram of the line segments

As @D.W. noted, a Voronoi diagram of line segments1 is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of *Computational Geometry* by de Berg et al. But I don't think you should do this.

## Don't use a sweepline algorithm

However, while sweep-line algorithms are nice in theory, implementing them in a robust and efficient manner turns out to be quite difficult in practice. I think this goes doubly so for the Bentley-Ottman algorithm. Therefore, in the field of *algorithm engineering*, which concerns itself with implementing algorithmic ideas on a computer, (randomized) incremental construction methods are usually preferred. These methods are much easier to make robust and are dynamic (support modifications efficiently) by default2. The (expected) running time is also often not so bad in theory, and can beat the theoretically superior algorithm in practice. (if someone managed to implement the other algorithm effectively, that is).

## Use random incremental construction

I recommend the algorithm by Karavelas (described in this conference paper ). It computes a line segment Voronoi diagram in $O((n+m)\log^2 n)$ expected time, together with a hierarchical structure that supports nearest neighbor queries in $O(\log^2 n)$ expected time. (Here, $n$ is number of segments, and $m$ the number of points)

This algorithm is implemented in the CGAL library, see this manual page for the details.

---

1: Formally, this is only a proper generalisation of a Voronoi diagram if the line segments are disjoint, because if the nearest point is point shared by two segments, we cannot uniquely determine its cell. If these line segments form the embedding of a planar graph, they only intersect at the end-points. In this case, we can often get away with shrinking the segments a tiny bit s.t. the endpoints are now disjoint. Another option is to consider the open segments and their endpoints as 3 separate objects, and make a Voronoi diagram of those.
2: More precisely, insertion is already implemented, and deletion is usually not too hard to add.
> 3 votes

# Answer
I haven't tried to work out the details, but it seems plausible to me that it might be possible to solve this with a sweepline algorithm, with ideas from the Bentley-Ottman algorithm.

In particular, one approach would be to build the Voronoi diagram of the line segments (rather than a Voronoi diagram of points, as we usually do), then store it in a data structure that allows us to quickly query, given a point, which Voronoi cell it is contained in. A standard architecture for that with a sweepline algorithm is to move a vertical sweepline left to right, with an "event" for each point/vertex in the Voronoi diagram. At any point in time, we store the set of Voronoi edges sorted vertically in a binary search tree; we store all of these, one per event, using a persistent data structure.

I *think* the edges of that Voronoi diagram are composed of line segments and segments of a circle, all obtained by taking segments from (a subset of) the following possibilities:

* Given a pair of line segments AB and CD, there's a line equidistant between the two of them.
* Given a pair of line segments AB and CD, there's a parabolic arc that is equidistant between A and CD. (And symmetrically for B.)

And I *think* all of the vertices of the Voronoi diagram are composed of intersections between the following constructed lines:

* Given a pair of line segments AB and CD, consider the line equidistant between them.
* Given a line segment AB, consider the line that is perpendicular to AB and goes through A. (And symmetrically for B.)

So, I think it might be possible to identify all of the vertices of the Voronoi diagram by using a sweepline algorithm based on Bentley-Ottman to construct all of those intersections; then use a persistent data structure based on a sweepline with one event per vertex, where we use the persistent binary tree to represent the Voronoi cells that intersect with the sweepline.

You would need to check the details. I haven't tried to work through all of this to see if it can actually be made to work or if there are some difficulties I'm overlooking right now.

Possibly also useful: https://gis.stackexchange.com/q/104631, https://mathoverflow.net/q/311592/37212, https://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.2920&rep=rep1&type=pdf
> 2 votes

---
Tags: computational-geometry, planar-graphs
---


# Question
Title: Why does SAT-UNSAT $\in NP \implies NP = coNP$
I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, unless NP = coNP.

I fail to see why.

I searched and I came across multiples posts such at this one and that one that prove that if SAT-UNSAT is in coNP, then NP = coNP. But unless the fact that SAT-UNSAT $\in NP \implies$ SAT-UNSAT $\in coNP$ (which I do not see), then those proofs are not exactly what would help me. The same goes for this question, I would need SAT-UNSAT $\in coNP$.

***Question*** : Considering the first question (and the answer associated), if the problem SAT-UNSAT $\in NP$, why does NP = coNP.

My take : Well, I can see that the problem SAT-UNSAT is NP-hard and coNP-hard. If SAT-UNSAT $\in NP$, then SAT-UNSAT is NP-complete. This implies things such that the problem UNSAT (which is coNP-complete) is NP-hard since we can reduce UNSAT to SAT-UNSAT which is NP-complete. That's all I got and that doesn't really help.

I'd appreciate any clarification on the subject. Thanks to you all

# Answer
Suppose that $X$ is a coNP problem which is NP-hard.

Let $A$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction from $A$ to $X$. Since $X$ is in coNP, this shows that $A$ is in coNP.

We have shown that $\mathsf{NP} \subseteq \mathsf{coNP}$. Now suppose $B$ is in coNP. Then $\overline{B}$ is in NP, and so in coNP. Hence $B$ is in NP. This shows that also $\mathsf{coNP} \subseteq \mathsf{NP}$, and so $\mathsf{NP} = \mathsf{coNP}$.
> 2 votes

---
Tags: np-complete, np, complexity-classes, co-np
---


title: Complexity of Radix Sort

text:
# Question
Title: Complexity of Radix Sort
I am a little confused by the complexity proof of Radix Sort.

For **counting sort**, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range.

But this is not entirely correct, right? To do binary arithmetic on numbers as big as $R$, I need $\log\_2 R$ operations for any deterministic hashing function. So the complexity of counting shot should be $O(\log\_2 R \cdot (n+R))$.

Then the complexity of **radix sort** with base $b$ should be $O(\log\_b R \cdot \log\_2b \cdot (n+b))$, which is equivalent to $O(\log\_2R \cdot n)$. For range $R = \Omega(n)$, this is $\Omega(n \log n)$ and thus not $O(n)$.

Can someone point out where I am going wrong in my proof? As far as I know, radix sort is $O(n)$ for $R = O(n^c)$.

# Answer
We typically analyze algorithms in the so-called "RAM machine" or "transdichotomous model". In this model, operations on machine words take $O(1)$, and a machine word has length $O(\log n)$ bits, where $n$ is the size of the input (in bits), or any other polynomially related quantity.

If $R$ is polynomial in $n$ (in this case, the length of the array), then an integer in the range $\\{1,\ldots,R\\}$ can be stored in a single machine word, and so operations on such integers take constant time in this model.
> 3 votes

---
Tags: time-complexity, sorting, radix-sort
---


# Question
Title: What is the name of this problem (the dual of the asymmetric k-center problem)
I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse.

In this problem, the number of warehouses is fixed to $k$, and the goal is minimizing the maximum distance between any city to it's the nearest warehouse.

But, if we want to find a minimum number of centers to meet the demand of having maximum distance from any cities to it's nearest warehouses be fixed (less than) to $t$, what known problem is defined.

Actually, instead of minimizing the distance, I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?

# Answer
It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.

> instead of minimizing the distance \[$t$\], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?

Observe that we may assume the maximum allowed distance $t=1$, because we can simply scale the input by a factor of $1/t$. This problem is known as the **DISCRETE UNIT DISK COVER** problem (DUDC).

DUDC is NP-hard. To see why, first note that the problem is equivalent to the dominating set problem on unit disk graphs.2 The dominating set problem is NP-hard for general graphs, but this does not imply that it remains hard for unit disk graphs in particular. However, the dominating set problem is known to be NP-hard on "grid graphs": unit disk graphs that have an embedding where all vertices lie on an integer grid with disks of radius $1/2$.3 Since all grid graphs are unit disk graphs, the dominating set problem is NP-hard for unit disk graphs, and hence DUDC is NP-hard.

---

1: Another option is that there is a finite number of fixed sites for warehouses, which are *not necessarily* inside a city. But this has the problem I discuss here as a special case, so my discussion here shows that both problems are in fact NP-hard.
2: Technically, we need to restrict ourselves to unit disk graphs for which we can compute an embedding in polynomial time, as this is not known to be possible for an arbitrary unit disk graph. Fortunately, this is possible for "grid graphs" (what helps is that these graphs are planar, unlike general unit disk graphs), so the construction works out fine.
3: See the paper *Unit disk graphs* by Clark, Colbourn and Johnson. They also note there exists an earlier proof for the hardness of the DUDC problem in the conference paper "S. Masuyama, T. Ibaraki and T. Hasegawa, *The computational complexity of the M-center problems in the plane*" from 1981, but this paper appears to be accessible only for members of the Japanese institute that published the conference proceedings)
> 1 votes

---
Tags: algorithms, complexity-theory, np-complete, computational-geometry, clustering
---


# Question
Title: Comparing the big-$O$ of these four functions
Sometimes you can substitute values for $n\_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.

But for the following functions, for example, taking the limit in infinity for $f\_3$ over $f\_2$ requires using l'Hôpital's rule which doesn't simplify anything. $f\_3$ is technically the product of a polynomial and an exponential function. And I don't know how to go with comparing functions like that with others.

Firstly, I know that $f\_4$ is the most efficient because it is $O(n^2)$. ($f\_4(n) = n + \frac{n(n + 1)}{2}$) and the rest are exponential.

But for the rest, I really don't know what to besides using my intuition which could be really far from the correct answer anyway. Please help me compare these rigorously.

$f\_1(n) = n^{\sqrt{n}}$

$f\_2(n) = 2^n$

$f\_3(n) = n^{100}2^{\frac{n}{2}}$

$f\_4(n) = \Sigma\_{i=1}^{n}i + 1$

# Answer
> 0 votes
One useful technique for comparing functions asymptotically is to take their logs since doing that turns exponentials into polynomials. So, if you are comfortable with comparing polynomials, then taking logs is always something you should be thinking about.

There is one thing that you have to be careful of when you do that, however. After taking logs, *you can not throw away constant factors anymore*.

If you take the logs of your functions, you get $\log(f\_1(n))=\sqrt{n}\log(n)$, $\log(f\_2(n))=n\log(2)$ and $\log(f\_3(n))= 100\log(n)+\frac{n}{2}\log(2)$. So, $f\_2$ is asymptotically larger than $f\_3$ which, in turn is asymptotically larger than $f\_1$. You already know where $f\_4$ goes.

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


# Question
Title: What is the polynomial time reduction between these two Hamiltonian cycle problems?
*Problem 1:* Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.

*Problem 2:* Given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.

What is the polynomial-time reduction of problem 1 to problem 2?

> Let TSP1 denote the following problem: given a TSP instance in which all edge costs are positive integers, compute the value of an optimal TSP tour. Let TSP2 denote: given a TSP instance in which all edge costs are positive integers, and a positive integer T, decide whether or not there is a TSP tour with total length at most T. Let HAM1 denote: given an undirected graph, either return the edges of a Hamiltonian cycle (a cycle that visits every vertex exactly once), or correctly decide that the graph has no such cycle. Let HAM2 denote: given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
>
> From Roughgarden's online algorithms course

*The solution:*

> If TSP2 is polynomial-time solvable, then so is TSP1. If HAM2 is polynomial-time solvable, then so is HAM1.

# Answer
First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky.

Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2).

```
algorithm for P1 with input G = (V,E):
  E' = {} # edges of "Hamilton Cycle"
  run subroutine for P2 on G
  if there is no Ham. Cycle:
    report that there is no Ham. Cycle
  for e in E:
    run P2 on (V,E - {e})
    if (V,E - {e}) contains "Hamilton Cycle":
      E <- E - {e}   # remove e
    else:
      E' <- E' + {e} # add e to cycle
  return E'

```

It uses the procedure for P2 $O(|E|)$ times, thus we obtained a polynomial reduction.
> 1 votes

---
Tags: algorithms, graphs, reductions, hamiltonian-path, polynomial-time-reductions
---


# Question
Title: How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^\*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.

If $A$ is a language, then \begin{align\*} AA^\* & = A(A^0\cup A^1\cup\cdots) \tag{Definition of $A^\*$}\\ & = A^1\cup A^2\cdots \tag{Distributive law} \\ & = (A^0\cup A^1\cup\cdots)A \tag{Distributive law} \\ & = A^\*A. \end{align\*}

Is this enough? I'm thinking that in order for it to be a proper proof, I have to show that $AA^\*$ and $A^\*A$ are subsets of each other. That is, take an element $s = xy$ where $x\in A$ and $y\in A^\*$ and show that $x\in A^\*$ and $y\in A$ (and vice versa). However, I get stuck very early when doing that method.

# Answer
If $x\in AA^∗$ then there are $a\in A$ and $b\in A^∗$ such that $x=ab$. Since $b\in A^∗$ then either there are $b\_1,b\_2,...,b\_n\in A$, with $n\geq1$, such that $b=\prod\_{k\in\[1,n\]}b\_k$ or $b=\epsilon$. It follows that either $x=a\prod\_{k\in\[1,n\]}b\_k$ or $x=a$. In the first case you can write $x=\left(a\prod\_{k\in\[1,n−1\]}b\_k\right)b\_n$, since concatenation is associative. Since $a\prod\_{k\in\[1,n−1\]}b\_k\in A^∗$ and $b\_n\in A$, you get that $x\in A^∗A$. In the second case $x=a=\epsilon a$, since $\epsilon$ is a neutral under concatenation. Since $\epsilon\in A^∗$ and $a\in A$, then we get again that $x\in A^∗A$. So, $AA^∗\subset A^∗A$.

The reverse inclusion is pretty much the same argument, but starting with $x\in A^\*A$.
> 1 votes

# Answer
$AA^\*$ is the set of all strings consisting of a string in A, followed by zero or more strings in A, which means all strings consisting of one or more strings in A. $A^\*A$ is the set of all strings consisting of zero or more strings in A, followed by one string in A, which also means all strings consisting of one or more strings in A. So both are the same.
> 1 votes

---
Tags: automata, regular-languages, finite-automata, regular-expressions, kleene-star
---


# Question
Title: Is the set of all context-free languages contained in the set of all languages that have a w-grammar?
Word grammar (w-grammar) is a context free grammar in which all laws are of the following forms:

$A \rightarrow B, A \rightarrow \epsilon, A \rightarrow w\_1B, A \rightarrow Bw\_2$

$A, B \in N$ (nonterminal), $w\_i \in \Sigma^\ast$

$ L\_{w-grammar} $ \- set of all languages that have a w-grammar

$ L\_{CFG} $ \- set of all languages that have a context free grammar

Is the following statement is true $ L\_{CFG} \subseteq L\_{w-grammar} $ ?

# Answer
The class of languages accepted by this kind of grammar is known as linear languages (the definition on Wikipedia is slightly different, but equivalent). According to Wikipedia, the language of all balanced parentheses (generated by $S \to SS \mid (S) \mid \epsilon$) is context-free but not linear.
> 1 votes

---
Tags: context-free
---


# Question
Title: first order logic to normal form order of operations
```
 ∃y∀x [A(x) ∧ B(y) -> C(x,y)]
 ∃y∀x [¬(A(x) ∧ B(y)) v C(x,y)]
 ∃y∀x [¬A(x) v ¬B(y) v C(x,y)]

```

I need to convert the above to conjunctive normal form. I'm a little confused about the order of operations in the case of both existential and universal quantifier and which part of the expression they apply to. From the last step, would I skolemize y across the entire expression meaning:

```
∀x [¬A(x) v ¬B(S(x)) v C(x,S(x)]

```

or do I take the universal quantifier first?

# Answer
> 1 votes
You always remove quantifiers in the order in which they appear in the prefix, from left to right, that is, you first eliminate $\exists y$ and then $\forall x$.

But the variables to apply the skolem function to are just the variables occurring free in the expression, no bound ones. Since $x$ is bound by $\forall x$, and $y$ is being skolemized away, the skolem function for $\exists y$ becomes a zero-place function symbol, or constant, `S()`:

`∃y∀x [¬A(x) v ¬B(y) v C(x,y)]`
`>>`
`∀x [¬A(x) v ¬B(S()) v C(x,S())]`

In the next step, eliminate the the universal quantifier:

`∀x [¬A(x) v ¬B(S()) v C(x,S())]`
`>>`
`¬A(x) v ¬B(S()) v C(x,S())`.

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