title: accessing out of range physical address

text:
# Question
Title: accessing out of range physical address
What happens if a CPU instruction (e.g. on ARM architecture) tries to access a physical address that is out of range. This easily could happen if the CPU is on non-virtual (non-paging) mode. This could also happen if the CPU is in paging mode and the page table maps the virtual address to a physical address that is out of range. A physical address is out of range iff that address is not served by any of the plugged RAM chips.

Would the CPU run into an exception and invoke some interrupt service routine? Would the CPU read/write some garbage value?

# Answer
The exact response is hardware implementation specific. Typically the memory access will timeout and a hardware exception will be generated. DEC called these Machine Checks, other manufacturers may use different terms. The CPU will follow some interrupt path that will handle the timeout. In normal operation the most common result will be a system crash (again different terms are used, but "Bugcheck" was favored by DEC, "ABEND" is used by others.).

There are some system implementations that don't have a timeout mechanism, in these cases the typical response would be a hang waiting for a response from memory or in a less desirable case, random noise would be read from the data lines.

During boot sequences, the exception handling is sometimes changed so that the system configuration can be discovered. The configuration code may "probe" addresses until it gets an exception in order to find the end of physical memory. Again, this is architecture dependent and not always necessary if the hardware provides some other means of determining the installed memory.

Since you mention ARM specifically, you can read a white paper for ARM memory implementation here: Principles of ARM® Memory Maps This paper has the following recommendation regarding memory accesses: "Unpopulated DRAM partitions must not alias any other addresses, accesses should return bus errors."
> 2 votes

---
Tags: computer-architecture, cpu, memory-hardware, memory-access
---


# Question
Title: Logarithmic run time for calculating prime numbers?
Here's the function I'm currently analyzing. I know it's not the most optimal but I'm not understanding the $\theta()$ of this algorithm. I've been told that it's not actually $\theta(n)$ but instead a logarithmic run-time and it had something to do with the bits of the value passed in. I'm not understanding how the bits are causing the logarithmic so if someone can explain that it'd be great.

```
   function isPrime(n):
1  if n = 2 return true
2  for i from 2 to n
3      if n % i = 0 return false
4  return true

```

# Answer
> 4 votes
Let's use a different parameter for your input, $m$. The number of instructions that your algorithm executes in the worst case is $O(m)$.

We often measure the running time of algorithms in terms of the length of their input (measured either in bits or in words), often denoted by $n$. The length of your input is $n \approx \log\_2 m$, since this is how long it takes to encode the integer $m$ in binary. Therefore your algorithm actually performs an *exponential* number of instructions $O(2^n)$.

A different issue is the cost of arithmetic operations, such as the modulo operation on line 3. In most models of computation (and in real life), the cost of such an operation depends on the length of the numbers being operated on. Therefore your algorithm runs in time which is worse than $2^n$ by a polynomial factor $n^{O(1)}$ (the exact polynomial factor depends on the algorithm you use to perform the division). Such a running time is usually denoted $\tilde{O}(2^n)$.

# Answer
> 2 votes
Well, first, the algorithm is incorrect: it claims that every integer less than or equal to $2$ is prime, and every integer greater than $2$ is composite.

* Any $n\leq1$ fails the test at line $1$, does zero iterations of the loope at lines $2$$3$ and returns `true` at line $4$.
* $n=2$ triggers the `return true` on line $1$.
* Any $n\>2$ fails the test at line $1$. If it is composite, it returns `false` at line $3$ for its smallest prime factor; if it is prime, then the loop will get as far as $i=n$, at which point the `n%i=0` is true, so we return `false` at line $3$.

So, suppose we correct line $2$ to be `for i=2 to n-1` and assume the input is greater than $1$. Then, for any prime input $n\>2$, the loop at lines $2$$3$ will run for each value $2, \dots, n-1$, which is $n-2 = \Theta(n)$ iterations. So your suspicion that the running time is $\Theta(n)$ is correct: this algorithm is not logarithmic.

In general, as Yuval explains, we measure the running time of algorithms in terms of the length of the input as written in binary. Since the number $n$ takes $\Theta(\log n)$ bits to write down, and the running time of the algorithm is $\Theta(n) = \Theta(2^{\text{input length}})$, this algorithm would normally be described as having exponential running time.

---
Tags: runtime-analysis, primes
---


# Question
Title: On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem
in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.

Besides, it's easy to see that the KP problem is a special case of the QKP.

How should one proceed to prove the NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem?

CCQKP:

$$max\ \sum\_{i=1}^{n} \sum\_{j=1}^{n} x\_i x\_j c\_{ij}$$ $s.t$ $$\sum\_{j=1}^{n} a\_j x\_j \leq C$$ $$\sum\_{j=1}^{n}x\_j = 1$$ $$0 \leq x\_j \leq 1,\ j = 1,...,n$$ $$\sum\_{j=1}^{n}z\_j = k$$ $$z\_j \in \\{0,1\\},\ j = 1,...,n$$

I'm aware that we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.

# Answer
> 0 votes
The quadratic knapsack problem is NP-hard. Therefore, the cardinality-constrained quadratic knapsack problem is NP-hard, too (as Yuval says, just don't use any cardinality constraints).

If problem X is a special case of problem Y, and problem X is NP-hard, then so is problem Y. Now let X = CCQKP and Y = QKP.

---
Tags: complexity-theory, optimization, np-complete, reductions, np-hard
---


# Question
Title: Are the definitions of recursively enumerate equivalent?
There are a couple of definitions of **recursively enumerable**, for example in Judah: *$A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0\_1$ formula $\varphi(x)$ such that*

$$A:=\\{n \in \mathbb{N}: \mathbb{N} \vDash \varphi(n)\\}$$

In Shoenfield: *A predicate $P$ is r.e. if there is a recursive predicate $Q$ such that*

$$P(\bar{a}) \leftrightarrow \exists x Q(\bar{a}, x)$$ *for all* $\bar{a} \in P$. And in here there is another one A new definition of recursively enumerable set?.

My question is: Are the definitions of recursively enumerate equivalent? Why?

# Answer
Your two definitions are essentially the same: a $\Sigma\_1^0$ formula is one of the form $$\exists x Q(n,x),$$ where $Q$ is computable and $n$ is the parameter.

Another difference between the two definitions is that the first only defines r.e. sets, i.e. unary relations, whereas the second defines r.e. relations of arbitrary arity. The two definitions coincide in the case of unary relations.
> 3 votes

---
Tags: computability, terminology, first-order-logic
---


title: Finding Euclidean Minimum Spanning Tree

text:
# Question
Title: Finding Euclidean Minimum Spanning Tree
Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.

We can solve this problem with Prim's algorithm in $O(n^2)$ which is too slow. I've found an algorithm called Delanuay Triangulation but is there any other ways to solve this problem in $O(n log n)$ or faster?

# Answer
If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck.

You should also specify in what space you're operating. If you're working with $\mathbb N^2$ coordinates, you can possibly do it in $\mathcal O(n \log\log n)$ (with a randomized algorithm to generate the triangulation).

If you have $P\in \mathbb R^2$ your choices (ordered by difficulty of implementation from easiest to not-easiest) are:

* Delaunay triangulation
* WSPD based approaches (first find clusters on Quadtree of $P$, then build MSTs for each cluster and then connect clusters to get complete MST)
* Improved version of Boruvka's algorithm: paper

The last one is also an improvement over the other two in higher dimensions. This answer is more or less a condensed version of the literature review of the linked paper.
> 3 votes

---
Tags: algorithms, minimum-spanning-tree, euclidean-distance
---


title: Measuring infinite loops

text:
# Question
Title: Measuring infinite loops
Theoretically, is there a way to measure how many infinite loops are running at a given point in time? In other words, is there a way to freeze everything and get a number on how many infinite lines of code are running on every machine.

# Answer
> 0 votes
While I don't think your question is fitting for cs.StackExchange, let me try to answer it anyway:

You would approach this problem as follows:

1. To answer how many infinite loops run on all devices, you would need to determine the number of infinite loop on each device
2. To determine the number of infinite loops on each device, you would have to count all loops running on each device and then determine if they will be running forever
3. The last step would require a method that determines for a given loop if it will run forever. Assuming you had such a method, you could do the following:

a.) Take any piece of code, $\Pi$

b.) Put it into a loop of the form: "$\text{do} \\{\ \Pi\ \\}\ \text{while}\ (false);$" As the resulting expression is a loop, you could feed it to your loop-decision method to find out if it terminates.

c.) The loop will terminate, if and only if $\Pi$ terminates. As you can take any $\Pi$ you want, you would thus be able to solve the Halting problem, which is proven to be impossible.

Thus, it is mathematically impossible to answer your question.

PS: I think the correct label would be computability-theory, not complexity-theory. The latter deals with computations that need a finite time and approaches to derive boundaries for that finite time.

---
Tags: time-complexity, loops
---


# Question
Title: Minimum Number of Integers From a List that Add up to N (Dynamic Programming)
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:

> Given a list $L$ of $K$ integers, $\[a\_1, a\_2, ... , a\_k$\], where each $a\_{i+1} \> a\_i$ and each $a\_i \> 0$, design an algorithm that finds the minimum number of such $a\_i$ that their sum adds up to $N$. You can use each $a\_i$ an unlimited number of times. You may assume $N$ is a possible sum for any $L$.
>
> Example: $L = \[1, 3, 5\]$. $N = 10$. The optimal choice is $5 + 5$. A possibility is using $10$ $1$'s, but that is not optimal.

I thought I found the optimal solution using a greedy algorithm, where we start with $0$ add the largest integer from $L$ without going over.

But my greedy algorithm fails in this case:

> Integers: $\[1, 5, 7\]$, $N = 10$; greedy algorithm gives $7+1+1+1$, but optimal solution is $5+5$.

The people I've talked to suggested taking a Dynamic Programming approach, but I am not quite comfortable with DP. What suggestions or hints do you have for thinking of a DP approach? I think I should approach this recursively, but in what way? Should I keep breaking it down to halves until I find individual components (kinda like mergesort), and see what numbers these components add up to in $L$?

# Answer
You start with an array $A$ from 0 to N and initialize every value with $\infty$ (or some very large number). Then you set $A\[0\] = 0$.

Then you loop the following until no more changes occur:

For each number $0 \leq n \leq N$ and for each integer $l\in L$ you update $A\[n+l\] = min(A\[n+l\],A\[n\]+1)$ (don't forget to check for array boundary violations)

When finished, the value of $A\[n\]$ should contain the minimum number of integers from your list that sum up to $n$.

Expected runtime of this is pretty bad (assuming you have a huge $N$ and $L = \\{1,N\\}$, as you will update values for $n\<N$ for quite some time until you've found your solution.

You can optimize it a bit by observing, that in each iteration, the assigned values increase by one and thus, if some value has been assigned it will not be updated anymore. Therefore, as soon as $A\[n\] \neq \infty$ you can stop as the lowest value has been found.

Also you can keep track of a "frontier", i.e those indices $i$, for which $A\[i\]$ has been assigned in the last iteration. You can implement this with a queue, where you add $n+l$ to the queue if the minimum is lower than the previously found value and don't iterate over all $n$ but take the first element from the queue, which has been initialized with $Queue.add(0)$.

The resulting runtime should be $\approx\mathcal O (K\cdot r)$ (or something similar, e.g. $\mathcal O (K^2\cdot r)$) where $K$ is the number of integers in your set and $r$ is the result.

You could improve it a little bit if you replace the queue with a priority queue (e.g. a maxheap).

Alternatively you could precompute some multiples of your numbers (e.g. if $N=10^6-1$ and you have 1 and 1000, you would first determine the values for the largest multiple of each number that is below $N$ (999999\*1 and 999\*1000) and assign those directly).
> 0 votes

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


# Question
Title: Manber's graph-partitioning implementation
I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in *A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File*.

Generally speaking he wants to divide vertices of a weighted, directed graph $G=(V,E)$ into two sets $V\_1$ and $V\_2$ in such a way, that the sum of the weights of the edges that go from $V\_1$ to $V\_2$ is maximized.

He states that since this is a NP-problem he chose to first partition the graph randomly and then examine each vertex to see if switching this vertex to the opposite set would improve the total. This whole process is repeated several times for several random initial partitions to see which one of them yields the best results.

The following pseudocode is provided:

```
Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times *{ k is a constant; we used 100 }*
       randomly assign each vertex to either V1 or V2 with equal probability;
       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if switching v to the opposite set improves the sum of weights then
             switch v;
          **if switching v caused other vertices, not already on the queue, to
          prefer to switch then put them on the queue;**
       store the best solution to date;
```

I'm not sure what I'm supposed to code for the bolded part. How do I check for the "preference" of non queues vertices? Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

# Answer
> How do I check for the "preference" of non queues vertices?

The previous step was

```
          if switching v to the opposite set improves the sum of weights then
             switch v;

```

so clearly you already know how to check for the preference of a vertex. Whether or not it is in the queue is immaterial.

To do it *efficiently* requires some additional data storage and pre-calculation which is not explicitly described in the pseudocode. In more detail,

```
Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times
       randomly assign each vertex to either V1 or V2 with equal probability;

       initialise two arrays of edge weight sums, internalSums and externalSums
       for each edge e = (s, t) in E do
          if s and t are in the same partition
             increment internalSums[s] and internalSums[t] by weight(e)
          else
             increment externalSums[s] and externalSums[t] by weight(e)

       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if internalSums[v] > externalSums[v]
             switch v;
             swap internalSums[v] and externalSums[v]
             for each edge e = (v, u) in E do
                update internalSums[u] and externalSums[u] appropriately
                if u is not in the queue and internalSums[u] > externalSums[u]
                   enqueue u
       store the best solution to date;

```

---

> Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

I must confess that I would be unable to distinguish easily between the algorithm working as intended and the algorithm selecting a purely random partition and skipping the rest of the process.
> 0 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: generating mazes using Eller's algorithm - why do I get loops?
I'm making a maze generator that uses Eller's algorithm. There's not much information about this particlar algorithm on the Internet. So I have some things misunderstood about it. I've made a picture to show you the proccess of generating an incorrect maze.

I didn't found any information about this in article1 and article2.

What should I do to avoid generating loops?

# Answer
> 1 votes
> here I get two blocks of the same set, but they don't go one after the other. So I join the second one go it's own unique set

Don't do that; this is not a step mentioned in your first reference! Two cells are in the same set when there is already a path between them (by going up though the already generated portion). By arbitrarily placing the second block into a new set, you are ignoring the fact that it is connected to other cells.

When you leave the `3` blocks alone, you will get

```
(03 17)03
 03(03 03)

```

You are required to place a wall between two blocks of the same set, because they already have a path between them. Thus you produce

```
 03 03|03

```

And don't had a loop.

---
Tags: algorithms
---


# Question
Title: Condition of square root algorithm (Newton's method)
I am reading the book *Algorithm 4th* and see this square root algorithm using Newton's method (java sample code):

```
public static double sqrt(double c)
{
    if (c < 0) return Double.NaN;
    double err = 1e-15;
    double t = c;
    while (Math.abs(t - c/t) > err * t)
        t = (c/t + t) / 2.0;
    return t;
}

```

**I wanna know what's the rule behind the `while` loop condition,**

`Math.abs(t - c/t) > err * t`

Why is it `(|t-c/t|)/t > err`? For exmaple, can't the condition simply be `|t-c/t| > err`?

I know that, `t-c/t` -\> 0 when loop count -\> ∞.

I remember that I encouter many *"manually choose approximation condition"* when learn *Probability Theory*. But now I totally forget it. So any related,basic background knowledge explanation or introduction would be much appreciated.

---

Newton's method from my original math textbook:

$$ a\>0, x\_0\>0, \\ \\{X\_n\\}: X\_n = \frac{1}{2}(x\_{n-1} + \frac{a}{x\_{n-1}}) \\ \lim{x\_n} = \sqrt{a}\ $$

# Answer
Firstly, there is a typo in the code. `if (c > 0) return Double.NaN;` should be `if (c < 0) return Double.NaN;`. To be fair to the questioner, this typo exists in the original textbook, *Algorithms*, fourth edition by Robert Sedgewick and Kevin Wayne (the e-book version only? I do not have the paper version, yet). To be fair to the book, just one page before where the typo occurs, the same code appears correctly with more explanation on Java syntax.

Secondly, there is a minor magic about the code. Note If you let `c=0` and hence `t=0` initially, the code `c/t` will not throw "java.lang.ArithmeticException: / by zero", which you would encounter if running java code `int oneOverZero = 1/0;`. The call to `sqrt(0)` will return 0 correctly. This is the magic by IEEE-754 (1985) floating-point standard.

---

Now let us get to the real business.

`Math.abs(t - c/t) > err * t`

This code is written according to general best practice for checking if two floating-point numbers is equal across most if not all programming languages that implement IEEE Floating-Point Standard, including c/c++ and Java. For some basic background knowledge explanation or introduction, you can checked Comparing Floating Point Numbers, 2012 Edition, especially the section "Relative epsilon comparisons". You can also check the Floating-point Comparison by C++ boost libray.

In a nutshell, in order to find if two floating-point numbers are equal or near enough, instead of comparing them using the "==" operator, or checking whether their difference is 0 or near 0, we should **check whether their absolute difference is small enough relative to the minimum (or the maximum) of the two especially when those two numbers are near 0 or very large**.

Let us see what might happen otherwise. Suppose we have the following code instead, where we check the absolute difference of `t` and `c/t` is smaller than `err` or not.

```
public static double sqrtDubious(double c)
{
    if (c > 0) return Double.NaN;
    double err = 1e-15;
    double t = c;
    while (Math.abs(t - c/t) > err)  // is the absolute diff almost 0?
        t = (c/t + t) / 2.0;
    return t;
}

```

Then `sqrtDubious(100000)` will run into infinite loop while `sqrtDubious(1e-30)` returns an apparently wrong number `1.235E-15`. However, `sqrt(100000)` and `sqrt(1e-30)` works. In fact, as far as I have tried, `sqrt(double c)` works pretty well for all numbers within the range of Java type double.

Also note the value of `err` is critical, too. If you change it to be smaller than 1e-15 such as 1e-16, then `sqrt(double c)` may behave erratically. Sometimes it goes into infinite loop, sometimes not. An accurate description of these wrong cases is rather too hard.

By the way, my testing code is written in Java, the language in which the code in the question is written. So, if you see a different result with your C/C++ code on your machine in the cases where I claim the result is wrong, I will not be too surprised since all these errors cases are very context-sensitive and seemingly erratic, although there are certain patterns if we digger deeper. (Various C/C++ doubles may not be the same as the Java double, anyway.)
> 1 votes

# Answer
Try calculating the square root if 1e-100 with the changed loop condition and see what result you get. Then try calculating the square root of 1e100. Do you run into any problems?

This is numerical mathematics, limits won’t work well. Print out the value of t -c/t and check whether it actually converges, and check if it converges to 0. For some different values if c.

From a wiser man than me: The problem are not the things we don’t know. The problem are the things we know that ain’t so.
> 1 votes

# Answer
> can't the condition simply be |t-c/t| \> err?

Only if you restrict `c` such that `err` will always be more than 1 ULP. Otherwise the condition is equivalent to `|t-c/t| > 0`, and rounding errors mean that oscillation around the root is possible.

(In actual fact, the chosen value of `err * t` is about 4.5 ULPs).
> 0 votes

---
Tags: algorithms
---


# Question
Title: Prove that A** = A*, where A is a language over Σ*
Let $\mathcal A$ be an arbitrary language over $\Sigma^\*$

**Proof.**

To prove, $\mathcal A^{\**} = \mathcal A^\* $

$\mathcal A^{\**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \right)^\*$ by definition of **Kleene Star**

My idea is that Kleene star operation distributes over the union of languages but then, I dont know what to do next.

I need some directions.

# Answer
> 16 votes
Since $L \subseteq L^\*$ for all $L$, we have $\mathcal{A}^\* \subseteq \mathcal{A}^{\**}$. In the other direction, suppose that $w \in \mathcal{A}^{\**}$. Then there exists an integer $n \geq 0$ and words $x\_1,\ldots,x\_n \in \mathcal{A}^\*$ such that $w = x\_1 x\_2 \ldots x\_n$. Since $x\_i \in \mathcal{A}^\*$, there exists an integer $m\_i$ such that $x\_i \in \mathcal{A}^{m\_i}$. Thus $w \in \mathcal{A}^{m\_1 + \cdots + m\_n} \subseteq \mathcal{A}^\*$, and it follows that $\mathcal{A}^{\**} \subseteq \mathcal{A}^\*$.

# Answer
> 7 votes
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.

The inclusion $L \subseteq L^\*$ always holds, so $\mathcal A^\* \subseteq \mathcal A^{\**}$.

We are left with proving $\mathcal A^{\**} \subseteq \mathcal A^{\*}$. For this, recall that $L^\*$ can be defined as the least language such that $$ \\{\epsilon\\} \cup LL^\* = L^\* $$ Hence, $\mathcal A^{\**}$ is the least language such that $$ \\{\epsilon\\} \cup \mathcal A^\* \mathcal A^{\**} = \mathcal A^{\**} $$ so, if we prove that $\mathcal A^\*$ also satisfies the same property, i.e. if we prove $$ \\{\epsilon\\} \cup \mathcal A^\* \mathcal A^{\*} = \mathcal A^{\*} \qquad (\*) $$ by the minimality of $\mathcal A^{\**}$, we will obtain the wanted $\mathcal A^{\**} \subseteq \mathcal A^{\*}$. Proving $(\*)$ is then trivial.

# Answer
> 5 votes
Depending on what you take as the definition of the Kleene Closure, the proof can be rather trivial. Here is a direct proof from the universal property:

The language $\mathcal{A}^\ast \subseteq \Sigma^\ast$ is the smallest submonoid of $\Sigma^\ast$ that contains $\mathcal{A}$. Likewise, the language $\mathcal{A}^{\ast\ast}$ is the smallest submonoid of $\Sigma^\ast$ that contains $\mathcal{A}^\ast$. Now:

* By definition, $\mathcal{A}^{\ast\ast}$ contains $\mathcal{A}^\ast$, so $\mathcal{A}^\ast \subseteq \mathcal{A}^{\ast\ast}$.
* On the other hand, $\mathcal{A}^\ast$ does contain $\mathcal{A}^\ast$ and is a monoid, therefore the smallest submonoid containing $\mathcal{A}^\ast$ cannot be larger than $\mathcal{A}^\ast$, hence $\mathcal{A}^{\ast\ast} \subseteq \mathcal{A}^\ast$.

Both inclusions together give equality.

---
Tags: regular-languages, automata, proof-techniques
---


title: When packets are not full?

text:
# Question
Title: When packets are not full?
When in computer networks it happens that the packets are not full? I have heard that sometimes in UDP that happens, if that’s the case, why not all the space is not used?

# Answer
The space isn't used if there isn't data to send. If you're writing a letter, you write as much as you need and you don't insist that the last page must be full of writing. And you don't wait until you have something extra to say to fill that page, because that would delay the rest of the letter.
> 2 votes

# Answer
"When in computer networks it happens that the packets are not full."

**The above statement is dubious. It is much better to say a packet is either a complete packet or a wrong packet.**

Let us assume we are not talking about wrong or testing or artificial situations, where every bet is off. Since we are talking about packets, i.e., in terminologies in the network layer, let us ignoring concerns where we do not have enough application data to send. That is a concern in application layer. We will come back to that point later.

Then what does it mean by "the packets are not full"?

A reasonable way to interpret or understand "the packets are not full" is that some bits in a packet are not used. That is, some bits are not part of the control information nor part of the payload. However, in all computer network protocols that I know of, there is no such thing as free-floating bits in a packet. **Every bit of a packet must be used for a particular purpose**. That is, it is either part of control information or it is part of the payload. In fact, the length of control information, which usually consists of version, addresses, priority, length, hop number and so on is usually predefined for a group of packets while the length of payload is usually specified by a field in control information. In particular, the length of a UDP packet is specified in the packet itself. I can imagine there might be some niche protocol where each packet must be of some fixed sizes, for example, to look like and behave the same for security reasons. Even for that protocol, every bit in a packet still fulfils a useful purpose, in the sense that the packet is wrong without any of them. I would refrain from calling those packets not full.

You might argue that "packet are not full" could mean that a packet is not full of user data just like some part of pages of a letter is left blank. OK, that is just a decent try to confuse people. As I have emphasized, besides control information, all other bytes in a network packet is called "user data" or "payload" by the most common and established convention as said in Wikipedia entry on network packet.

Now let us come to the application layer. It could happen that the expected or the actual data sent to and received by the receiving application could have some portion that contains no actual data. I would say just that. **As an application developer, I will not say anything about whether the underlying packet are full or not. Those network packets is not my business. Those packets is out of my sight.**
> 0 votes

---
Tags: computer-networks, communication-protocols, protocols
---


# Question
Title: How to describe the time complexity of a continually running program with a stream of inputs?
Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time.

For instance, I recently had a part of a program that took a continual stream of discrete strings (~256 chars) and checked if each one was in some sort of set or container.

Initially I was using a hash set, though I found despite the O(1) of looking up in the set, computing of the hash of the strings was slower than using a tree instead of a hashset and not computing any hashes.

How would one compare these two operations?

```
k = key length (smallish, 256)
n = items in the collection  (~10)
m = number of keys streamed (-> infinity)

hash set/table lookup:
worst:  O(m * (k + n)) -> O(m)
best:   O(m * k) -> O(m)

tree lookup:
worst:  O(m * k)  ->  O(m)
best:  O(m)

```

Usually, in practice, the tree will destroy the hash set. The last time I had to write something like this, the tree lookup was about 5x faster.

# Answer
> 1 votes
I would say that you should not look at the overall runtime (as it will be dominated by $m =\infty$ anyway) and instead look at the expected complexity of processing a single element (or a group of them if it doesn't scale linearly).

I'm not entirely sure what you mean with "Tree lookup" but I will just guess and provide an answer for that:

Calculating the hash of a key with length $k$ is done in $\mathcal O(k)$. The corresponding field in the hashmap/table/set is then retrieved with a single lookup.

Assuming your tree is a BST where each node is a key (256 chars, alphabet of size 26) and you compare either left or right side and you have 10 nodes in the tree:

* The tree has $log\_2(10) \approx 4$ levels (1,2,4,2 nodes)
* For a lookup, in each level the current key has to be compared to the node's key. The chance that the first characters match is $\frac1{26}$. That the first two match $\frac1{26^2}$, and so on.
* In most cases, you will have a mismatch at the all four nodes where a value is compared
* Your average case thus involves a few (2-4) lookups (following left or right child pointers in the tree) and comparing a few letters. If the key matches, the whole key is compared but I assume that this doesn't happen very often.

Thus, the BST lookup has a better performance without further modifications.

Maybe more fitting for stackoverflow than cs.stackexchange but still, my suggestion for your problem would be the following:

* Determine if the values in the collection have some pattern (if they are SHA hashes of random data or similar, very very likely not the case)
* Look at the percentage of successful matches (I would guess very low)
* Implement a custom "Hashing". If the items in your collections start with different letters (or 2, whatever), you only need the first letter of each element in your stream to know with which item from your collection you have to compare it (for equality).

---
Tags: time-complexity, performance
---


# Question
Title: What does the "0 ≤ K < N-1" expression means?
Given the following statement:

> "A nonempty array A consisting of N integers is given. Any integer K, such that 0 ≤ K \< N-1, splits array A into two non-empty parts"

What does the **0 ≤ K \< N-1** expression mean in this context?

# Answer
You have an array with indices from $0$ to $N-1$. $K$ is an in integer in this range, i.e. larger or equal to zero and smaller than $N-1$.

This integer splits the array into two parts as follows:

Part 1: From $0$ to $K$ (including K)

Part 2: From $K$ (excluding K, i.e. starting with $K+1$) to $N-1$.

$K$ has to be smaller than $N-1$ (and not smaller or equal) because else there would only be one Part (the whole array) for $K= N-1$.
> 4 votes

# Answer
$a\<b\<c$ means $a\<b$ and $b\<c$.
> 4 votes

---
Tags: algorithms, arrays
---


# Question
Title: How can I reduce Subset Sum to Partition?
Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation!

Is it possible to reduce this problem using a Levin Reduction ?

If you don't understand write for clarification!

# Answer
> 25 votes
Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$. Let $L'$ be the list formed by adding $S+B,2S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \\{ 2S-B \\}$ and $L\setminus M \cup \\{ S+B \\}$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$.

(2) If $L'$ can be partitioned into two equal parts $P\_1,P\_2$, then there is a sublist of $L$ summing to $B$. Indeed, since $(S+B)+(2S-B) = 3S$ and each part sums to $2S$, the two elements belong to different parts. Without loss of generality, $2S-B \in P\_1$. The rest of the elements in $P\_1$ belong to $L$ and sum to $B$.

# Answer
> 4 votes
The answer mentioned by @Yuval Filmus is incorrect (it's correct ONLY if there are no negative integers). Consider the following multiset :

$$\\{-5, 2, 2, 2, 2, 2\\} $$

and the target sum is $-2$. We know that there is no subset. Now, we construct the instance for the partition problem. The two new elements added are $2\sigma-t = 12$ and $\sigma+t = 3$. The multiset is now: $$\\{-5, 2, 2, 2, 2, 2, 3, 12\\}$$ and the total sum is $20$.

The partition problem solves the answer giving the subset $$\\{2, 2, 2, 2, 2\\}$$ Here, the 2 new elements are in the same subset (there is no other way to partition into half the sum). Hence, this is a counter example. The correct answer is as follows:

Add an element whose value is $2t-\sigma$. The total sum of the multiset is now $2t$. Solve the partition problem which will give 2 subsets of sum $t$. Only one of the partition will contain the new element. We choose the other partition whose sum is $t$ and we have solved the subset problem by reducing it into a partition problem. This is what the link explains.

# Answer
> 2 votes
Here is a straightforward proof:

It is easy to see that SET-PARTITION can be verified in polynomial time; given a partition $P\_1,P\_2$ just sum the two and verify that their sums equal each other, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most $|X|$ many summations).

The core of the proof is in reducing SUBSETSUM to PARTITION; to that end given set $X$ and a value $t$ (the subset sum query) we form a new set $X'=X \cup \\{s-2t\\}$ where $s=\sum\_{x \in X}x$. To see that this is a reduction:

* ($\implies$ ) assume there exists some $S \subset X$ such that $t=\sum\_{x \in S}x$ then we would have that \begin{equation\*} s-t=\sum\_{x \in S\cup \\{ s-2t \\} }x, \end{equation\*} \begin{equation\*} s-t=\sum\_{x \in X' \setminus( S\cup \\{s-2t\\})}x \end{equation\*} and we would have that $S\cup \\{ s-2t \\} $ and $X' \setminus( S\cup \\{s-2t\\})$ form a partition of $X'$
* ($\impliedby $) Suppose that there is a partition $P\_1',P\_2' $ of $X'$ such that $\sum\_{x \in P\_1'}x= \sum\_{x \in P\_2'}x$. Notice that this induces a natural partition $P\_1$ and $P\_2$ of $X$ such that WLOG we have that \begin{equation\*} s-2t+\sum\_{x \in P\_1}x= \sum\_{x \in P\_2}x \end{equation\*} \begin{equation\*} \implies s-2t+\sum\_{x \in P\_1}x+\sum\_{x \in P\_1}x= \sum\_{x \in P\_2}x+\sum\_{x \in P\_1}x = s \end{equation\*} \begin{equation\*} \implies s-2t+2\sum\_{x \in P\_1}x = s \end{equation\*} \begin{equation\*} \implies \sum\_{x \in P\_1}x = t \end{equation\*}

Hence from a solution $t=\sum\_{x \in S}x$ we can form a parition $P\_1 =S\cup \\{ s-2t \\} $, $P\_2=X' \setminus( S\cup \\{s-2t\\})$ and conversely from a partition $P\_1',P\_2' $ we can form a soltuion $t=\sum\_{x \in P\_1'\setminus \\{s-2t\\}}x$ and therefore the mapping $f:(X,t)\rightarrow X'$ is a reduction (because $(X,t)$ is in the language/set SUBSETSUM $\Leftrightarrow X'=f(X,t)$ is in the language/set PARTITION) and it is clear to see that the transformation was done in polynomial time.

# Answer
> 0 votes
**Subset Sum:**

Input: {a1,a2,...,am} s.t M={1..m} and ai are non negative integer and S⊆{1..k} and Σai(i∈S) = t

**Partition:**

Input: {a1,a2,...,am} and S⊆ {1,· · ·,m} s.t Σai(i∈S) = Σaj(j∉S)

**Partition Np Proof:** if prover provides a partitions(P1,P2) for verifier, verifier can easily calculate the sum of P1 and P2 and check if the result is 0 in linear time.

**NP\_Hard: SubsetSum ≤p PARTITION**

Let x be input of SubsetSum and x=〈a1,a2,...,am,t〉 and Σai(i from 1 to m) = a

*Case1: 2t \>= a:*

Let f(x)=〈a1,a2,...,am,am+1〉 where am+1= 2t−a

We want to show that **x∈SubsetSum ⇔ f(x)∈PARTITION**

so there exist S⊆ {1,...,m} s.t T = {1..m} - S and Σai(i∈T) = a-t

and Let T' = {1...m,m+1} - S so Σaj(j∈T') = a-t+2t-a = t

which is exactly Σai(i∈S)= t and it shows f(x)∈PARTITION

now We also will show that **f(x)∈PARTITION ⇔ x∈SubsetSum**

so there exist S⊆ {1,...,m,m+1} s.t T = {1,...,m,m+1} - S and Σai (i∈T)= \[a+(2t-a)-t\]=t

and it shows Σai(i∈T) = Σaj(j∈S) so m+1∈T and S⊆ {1,· · ·,m} and Σai(i∈S)= t

so x∈SubsetSum

*Case 2: 2t =\< a* :

we can check same but just this time am+1 is a−2t

# Answer
> -4 votes
this link has a good description of both reductions, partition to subset-sum and subset-sum to partition. I think it is more obvious than **YUVAL**'s answer. useful link

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Karp reduction from PARTITION to SUBSET SUM
PARTITION: Given a set of positive integers $A=\\{a\_1,...,a\_n\\}$ does there exist a subset of $A$ with sum equal to the sum of it's complement?

SUBSET SUM: Given a set of positive integers $A=\\{a\_1,...,a\_n\\}$ and another positive integer $B$, does there exist a subset of $A$ such that it's sum is equal to $B$?

I was trying to prove that if PARTITION is NP-complete then SUBSET SUM is also NP-complete, by reducing PART to SSUM.

My solution was: let $A=\\{a\_1,...,a\_n\\}$ be a set of positive integers. Then if A when fed into PART gives the solution $I=\\{k\_1,...,k\_m\\}$ (where $k\_i$ are the indices of the members of the solution subset), then we construct $A'=\\{a\_1,...a\_n,S\\}$ where $S$ is the sum of $\\{a\_{k\_1},a\_{k\_2},...,a\_{k\_m}\\}$. $A'$ is a solution to SSUM.

My problem with this is that this goes only one way, meaning that we can't show that given A' then A is a solution to PART. Is this a problem? and how could i modify the proof to cover it?

# Answer
Let's say we have a canditate set $A=\\{a\_1,...,a\_n\\}$ to feed as input to PARTITION. There is a transformation in polynomial time $f$, with $f(A)=(A,B)$, where $B=$${\sum\_{i=1}^n a\_i }\over 2$.
Then $A$ is a solution to $PART$ if and only if $(A,B)$ is a solution to $SSUM$.
So we have $PART \le\_m^p SSUM$
> 3 votes

# Answer
Here is a straightforward proof:

It is easy to see that SUBSETSUM can be verified in polynomial time; given a set of integers $S$ and an integer $t$ just evaluate the sum $\sum\_{x \in S}x$ and verify that the equality $t=\sum\_{x \in S}x$ holds, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most $|S|$ many summations).

The core of the proof is in reducing PARTITION to SUBSETSUM; to that end given set $X$ we form a new set $X'=X \setminus \\{s-2t\\}$ where $s=\sum\_{x \in X}x$ and the number $s-2t\in X$ is found in the following fashion:

* Is $s$ is odd then there must be an odd number $x \in X$ (otherwise $s$ would not be odd) and any odd number $x \in X$ is of the desired form $s-2t$ (a linear search can find the desired element).
* Is $s$ is even then any even number will be of the form $s-2t$. If no even number exists then if we let $2X=\\{2x\_1,...,2x\_n\\}$ we then notice that the following equivalence $(\exists P\_1',P\_2'\subset2X)(\sum\_{x \in P\_1 }x=\sum\_{x \in P\_2}x) \Longleftrightarrow (\exists P\_1,P\_2\subset X)(\sum\_{x \in P\_1 }x=\sum\_{x \in P\_2}x)$ gives us that we can replace $X$ with $2X$ and then perform the reduction (this is true because $\sum\_{x \in P\_i' }x=2\sum\_{x \in P\_i }x$).

We then let $f:X \mapsto (X',t)$. To see that this is a reduction:

* ($\implies$ ) assume there exists some $S \subset X'$ such that $t=\sum\_{x \in S}x$ then we would have that \begin{equation\*} s-t=\sum\_{x \in S\cup \\{ s-2t \\} }x, \end{equation\*} \begin{equation\*} s-t=\sum\_{x \in X \setminus( S\cup \\{s-2t\\})}x \end{equation\*} and we would have that $S\cup \\{ s-2t \\} $ and $X \setminus( S\cup \\{s-2t\\})$ form a partition of $X$
* ($\impliedby $) Suppose that there is a partition $P\_1,P\_2 $ of $X$ such that $\sum\_{x \in P\_1}x= \sum\_{x \in P\_2}x$. Notice that this induces a natural partition $P\_1'$ and $P\_2'$ of $X$ such that WLOG we have that \begin{equation\*} s-2t+\sum\_{x \in P\_1'}x= \sum\_{x \in P\_2'}x \end{equation\*} \begin{equation\*} \implies s-2t+\sum\_{x \in P\_1'}x+\sum\_{x \in P\_1'}x= \sum\_{x \in P\_2'}x+\sum\_{x \in P\_1'}x = s \end{equation\*} \begin{equation\*} \implies s-2t+2\sum\_{x \in P\_1'}x = s \end{equation\*} \begin{equation\*} \implies \sum\_{x \in P\_1'}x = t \end{equation\*}

Hence from a solution $t=\sum\_{x \in S}x$ we can form a parition $P\_1 =S\cup \\{ s-2t \\} $, $P\_2=X' \setminus( S\cup \\{s-2t\\})$ and conversely from a partition $P\_1',P\_2' $ we can form a soltuion $t=\sum\_{x \in P\_1'\setminus \\{s-2t\\}}x$ and therefore the mapping $f:X \mapsto (X',t)$ is a reduction (because $X$ is in the language/set PARTITION $\Leftrightarrow (X',t)=f(X)$ is in the language/set SUBSETSUM) and it is clear to see that the transformation was done in polynomial time.
> 0 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Matching/finding mathematical plot images
I'm trying to come up with a method to match a given mathematical plot against a database of other plots. To make it more specific: plots are generated in R as PNG and might have different dimensions. The latter means that simple pixel-by-pixel matching won't work, even when resized, because text, plotting symbol, margins etc. between two versions of the same old are non-linear transformations of each other.

There's a number of good image matching algorithms available online but those assume any area in the picture is relevant, whereas with mathematical plots it's predominantly about the artifacts representing data that's being plotted.

I'm looking for pointers: is there an algorithm, paper etc. related to this task? Or maybe someone heard of a specialized DNN (which could help in identifying those most important artifacts)?

Appreciate any suggestions.

# Answer
> 1 votes
A natural approach is to first scrape the data from each plot; then come up with a distance measure to compare the similarity of the data from two plots; then given a template plot, loop over all plots in the database, compute the distance, and find the most similar one.

There are many tools for scraping plots (i.e., given an image that contains a plot, extract the underlying data). See, e.g., https://academia.stackexchange.com/q/7671/705, https://stats.stackexchange.com/q/14437/2921, etc.

You'll have to choose the distance measure yourself. You haven't answered questions about what notion of similarity you want to use, and we can't tell you what to use. You could, for instance, rescale the data so that the x-axis and y-axis both vary across the range \[0,1\] (so all plots share the same scale), then use the $L\_2$ distance (Euclidean norm) between the two time series represented on the plots. That might or might not suit your needs.

I don't expect deep learning to be particularly useful here. I would try more direct methods first.

---
Tags: machine-learning, image-processing, pattern-recognition
---


# Question
Title: Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?
Just what the title says. Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)?

My current thoughts are that this is a consensus problem, and is thus impossible to achieve in an asynchronous messaging system (like the Internet). Another way I look at it is that if we could generate such a sequence in a distributed system, then the problem of total ordering is solved.

Please correct me if I'm wrong.

# Answer
> 4 votes
You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time.

The two best solutions we have are partial ordering (Lamport clocks) and consensus (which can be fault tolerant but is typically driven by an elected leader). The latter provides total order and works well in practice (with randomized timers), but is impossible to guarantee in theory (FLP).

# Answer
> 0 votes
You should take a look to CRDTs (Conflict-free replicated data type)

Those are data structures designed for distributed networks that can be updated concurrently without coordination between the replicas, as the resolution of conflicts is handled mathematically.

I was researching and working on Operational Transformation algorithms (SOCT4) some years ago, to implement a distributed collaboration software, and had some contacts with a Inria team, experts on this area, who provided this information, check their website for papers about latest research on this topic, they are doing an incredible work.

When I looked at them they were somehow limited, but increasing and decreasing sequences was already supported at the time (2013)

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


# Question
Title: Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?
Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^\*1^\*$? Why?

I think it's undecidable but can't find any undecidable problem to reduce it to.

# Answer
> 3 votes
Yes it is decidable.
We can construct a **total** Turing machine M that on input $G$ (where G is a CFG) checks whether it generates at least one string in $0^\*1^\*$.
Let $G\_1$ be a regular language such that $L(G\_1)=0^\*1^\*$.
Note that the intersection of CFL and a regular language is indeed a CFL. And hence a CFG for the intersection of $G$ and $G\_1$ can be constructed. Call the constructed CFG $G'$. Also, the emptiness problem for CFG is decidable and hence just check the emptiness of the constructed CFG $G'$.
If it's empty, G doesn't generate any string in $0^\*1^\*$; and likewise if it's not empty.

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


# Question
Title: Use the pumping lemma to prove that the following language is not context free
Can anyone help with the following problem ?

Let $B = \\{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \\}$, use the pumping lemma to prove B is not context-free

Thanks in advance.

# Answer
> 3 votes
Consider the following Context Free Grammar $G$:

$S \rightarrow aSdd\ |\ X\ |\ \epsilon$
$X \rightarrow bXc\ |\ \epsilon$

The language $L(G)$ generated by $G$ corresponds to the set of all the strings $\\{\epsilon, add, aadddd, ..., bc, bbcc,..., abcdd, abbccdd,...\\}$.
More generally, it corresponds to $ \\{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \\}$.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Is any State Space Tree always Binary Tree?
> A backtracking algorithm generates, explicitly or implicitly, a state-space tree.
>
> Introduction to the design & analysis of algorithms / Anany Levitin

I wonder that whether the saying always holds. If yes, is it always binary tree? For any problem which can be solved by backtracking, skeleton of the solution can be generalized?

# Answer
> 1 votes
Think about the chess problem or more simple 8-Queen problem are Tic Tac Toe game. The states are not binary trees. As seen from Quoara ;

> A state space tree is a tree constructed from all of the possible states of the problem as nodes, connected via state transitions from some initial state as root to some terminal state as a leaf.

---
Tags: graphs, recurrence-relation, recursion, backtracking
---


# Question
Title: Minimize sum of squares of rows in matrix when sum of columns have some constraint
I'm looking for an algorithm that can find any matrix $a\_{j,i}$ such that $$ \sum\_{i \in I} \left(\sum\_{j\in J} a\_{j,i}\right)^2 $$ is minimal, while also for each $j\in J$ satisfying the constraint $$ k\_j = \sum\_{i \in I} a\_{j,i} $$ where $k\_j$ is some non-negative constant. Furthermore every $a\_{j,i}$ must be non-negative, and some arbitrary selection of $a\_{j,i}$s in the matrix are fixed to be zero.

---

This problem models a situation where each $j$ has some fixed amount of resources that need to be divided in some way between a row of buckets. The constraint saying that some values are fixed to zero means that some buckets are missing on some rows.

We then want to find the way to divide the resources between buckets such that the columns of buckets have their contents divided as equally as possible between them.

---

Notice that if no values are fixed to zero, the solution is easy, since we can simply assign the values $$ a\_{j,i} = \frac{k\_j}{\\#I}, $$ where $\\#I$ is the number of columns. This way every line of buckets has an equal amount of resources assigned, and since decreasing the contents in one line would increase the contents of another, this is optimal.

---

The only solution I've currently been able to find is using some sort of linear programming solver that supports quadratic objectives, but I hope that this problem could be solved more efficiently than that.

---

**Nontrivial example** Suppose we are looking for a 3x3 matrix where \begin{align} 1 &= a\_{1,1} + a\_{1,2} \\ 2 &= a\_{2,1} + a\_{2,2} + a\_{2,3} \\ 1 &= \phantom{a\_{3,1} +\\,} a\_{3,2} + a\_{3,3} \end{align} Notice that some terms are missing in these sums. This is equivalent of fixing those terms to zero.

We then want to minimize $$ (a\_{1,1}+a\_{2,1})^2 + (a\_{1,2}+a\_{2,2}+a\_{3,2})^2 + (a\_{2,3}+a\_{3,3})^2. $$ Notice that a lower bound on the minimum is $3\cdot\left(\frac{4}{3}\right)^2=\frac{16}4$, since in this case the $4$ total resources are equally divided.

In this case we can achieve that lower bound with the solution \begin{bmatrix} 1/3 & 2/3 & 0 \\ 1 & 0 & 1 \\ 0 & 2/3 & 1/3 \end{bmatrix} which indeed has the minimum $\frac{16}3$.

A different solution is \begin{bmatrix} 2/3 & 1/3 & 0 \\ 2/3 & 2/3 & 2/3 \\ 0 & 1/3 & 2/3 \end{bmatrix}

---

**Example that doesn't hit lower bound of minimum**. Suppose we have the constraints \begin{align} 1 &= a\_{1,1} + a\_{1,2} \\ 4 &= \phantom{a\_{2,1} +}\\,\\, a\_{2,2} \\ 1 &= \phantom{a\_{3,1} +}\\,\\, a\_{3,2} + a\_{3,3} \end{align} In this case we have $a\_{1,1} \leq 1$, but in order to reach the lower bound where every line is equal to $2$, we must have $a\_{1,1} = 2$, which is not possible.

In this case there is only one optimal solution, which is: \begin{bmatrix} 1 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 1 \end{bmatrix}

# Answer
> 1 votes
### Summary

Solve iteratively by pseudo-inverse, set negative $x\_{ij}$ to 0, and remove negative $x\_{ij}$ from equations.

Warning: seems to always work only if number of rows equal to the number of columns. Don't know if it is because of ill-conditioning of matrix or the initial guess is too far off or bug.

### Lagrange Multipliers

I will write in math's ordering of index.

$x\_{ij}$ is the element of matrix $X$ at row $i$ and column $j$.

The square of column sum of the $j^{th}$ column is:

$$\left(\sum\_{i} x\_{ij} \right)^{2}$$

The row sum constraint for the $i^{th}$ row is:

$$0 = s\_i - \sum\_{j} x\_{ij} $$

Optimize sum of square of column sums by Lagrange multipliers:

$$ L = \left \[ \sum\_{j} \left(\sum\_{i} x\_{ij}\right)^2 \right \] - \sum\_{i} \lambda\_i\left(s\_i - \sum\_{j} x\_{ij}\right) $$

Set derivatives to zero:

$$\forall i, j: 0 = \frac{\partial L}{\partial x\_{ij}} = 2\left (\sum\_{k} x\_{kj}\right) + \lambda\_{i}$$

$$\forall i: 0 = \frac{\partial L}{\partial \lambda\_{i}} = s\_i - \sum\_{j}x\_{ij} $$

### Pseudo-inverse

Matrix equation:

$$A\vec{y} = \vec{b}$$

"Solve" by Moore-Penrose inverse (pseudo-inverse)

$$\vec{y} = A^{+}\vec{b}$$

This gives a solution that is as good as possible, even when some of the equations conflicts with each other.

### Karush–Kuhn–Tucker conditions

What if the solution says some of the $x\_{ij}$ is negative?

We set all negative $x\_{ij}$ to zero, remove these variables from the matrix equation, and solve by Moore-Penrose inverse again. Repeat until no more negative $x\_{ij}$.

(This is a simplified version of KKT because I don't understand everything in KKT yet.)

See: https://math.stackexchange.com/questions/1747435/correct-formulation-of-equality-and-non-negativity-constrained-non-linear-minimi

https://optimization.mccormick.northwestern.edu/index.php/Quadratic\_programming

### Example

I will explain with the 1-4-1 problem as an example.

Let $\vec{y}$ be the coefficients in row-major ordering and the $\lambda\_i$

$$\vec{b} = \begin{bmatrix} x\_{1,1}&x\_{1,2}&x\_{1,3}&x\_{2,1}&x\_{2,2}&x\_{2,3}&x\_{3,1}&x\_{3,2}&x\_{3,3}&\lambda\_{1}/2&\lambda\_{2}/2&\lambda\_{3}/2\\ \end{bmatrix}^{T}$$

where $\[\cdot\]^{T}$ denotes transpose of a matrix/vector.

I define a geometry matrix $G$. If $g\_{ij} = 0$, $x\_{ij}$ should be zero. $$G = \begin{bmatrix} {\color{red}1}&{\color{red}1}&{\color{red}0}\\ {\color{green}0}&{\color{green}1}&{\color{green}0}\\ {\color{blue}0}&{\color{blue}1}&{\color{blue}1}\\ \end{bmatrix}$$

Matrix $A$ is:

$$A = \begin{bmatrix} {\color{red}1}&{\color{red}1}&{\color{red}0}&0&0&0&0&0&0&0&0&0\\ 0&0&0&{\color{green}0}&{\color{green}1}&{\color{green}0}&0&0&0&0&0&0\\ 0&0&0&0&0&0&{\color{blue}0}&{\color{blue}1}&{\color{blue}1}&0&0&0\\ \hdashline {\color{red}1}&0&0&{\color{green}0}&0&0&{\color{blue}0}&0&0&{\color{magenta}1}&0&0\\ 0&{\color{red}1}&0&0&{\color{green}1}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}&0\\ 0&0&{\color{red}0}&0&0&{\color{green}0}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}\\ \end{bmatrix}$$

* Upper half is for constraints.
* Bottom half is for $0 = {\partial L}/{\partial x\_{ij}}$.
* The magenta numbers are for $\lambda\_1$, $\lambda\_2$, and $\lambda\_3$.

The $\vec{b}$ is just the row sum padded by zeros:

$$\vec{b} = \begin{bmatrix}1&4&1&0&0&0\\\end{bmatrix}^{T}$$

### Result

```
--- cycle 0 ---
    Matrix A:
        [[1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.4 -0.4  0.   0.   4.   0.   0.  -0.4  1.4 -1.4 -3.2 -1.4]]
    X:
        [[ 1.4 -0.4  0. ]
         [ 0.   4.   0. ]
         [ 0.  -0.4  1.4]]
    lambda^{T} / 2:
        [[-1.4 -3.2 -1.4]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1.4 3.2 1.4]
--- cycle 1 ---
    Matrix A:
        [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.  0.  0.  0.  4.  0.  0.  0.  1. -1. -4. -1.]]
    X:
        [[1. 0. 0.]
         [0. 4. 0.]
         [0. 0. 1.]]
    lambda^{T} / 2:
        [[-1. -4. -1.]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1. 4. 1.]

```

### Program

```
import numpy as np
from numpy.linalg import pinv, lstsq

def vec_y_split(vec_y, geometry):
    """Reshape vec_y into reshaped vec_y matrix and lambda
    """
    n_rows, n_cols = geometry.shape
    return vec_y[:-n_cols].reshape(geometry.shape), vec_y[-n_cols:]

def array_to_indent_str(x, indent=1):
    s = " " * indent * 4
    return s + str(x).replace("\n", "\n" + s)

def print_vec_y(vec_y, geometry, row_sum, indent=0):
    c, lam = vec_y_split(vec_y, geometry)
    s = " " * indent * 4
    print(s + "X:")
    print(array_to_indent_str(np.around(c, 3), indent + 1))
    print(s + "lambda^{T} / 2:")
    print(array_to_indent_str(np.around(lam.T, 3), indent + 1))
    print(s + "row sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=1), 3), indent + 1))
    print(s + "column sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=0), 3), indent + 1))
    print(s + "Error (Not considering zero requirement):")
    err = np.sum((c.sum(axis=1) - row_sum) ** 2) ** 0.5
    print(s + str(err))

def make_mat_A(geometry):
    n_rows, n_cols = geometry.shape
    mat_A = np.zeros((n_cols + n_rows, geometry.size + n_cols))
    # row equations
    for i in range(n_rows):
        for j in range(n_cols):
            mat_A[i, i * n_cols + j] = geometry[i, j]
    # col equations
    for j in range(n_cols):
        mat_A[n_rows + j, geometry.size + j] = 1
        for i in range(n_rows):
            mat_A[n_rows + j, i * n_cols + j] = geometry[i, j]
    return mat_A

def make_vec_b(geometry, row_sum):
    n_rows, n_cols = geometry.shape
    vec_b = np.empty((n_cols + n_rows, 1))
    vec_b[:n_rows, 0] = row_sum
    return vec_b

def remove_var(geometry, mat_A, coeff, epsilon):
    n_rows, n_cols = geometry.shape
    for i in range(n_rows):
        for j in range(n_cols):
            ix = i * n_cols + j
            if coeff[ix] < -epsilon:
                mat_A[:, ix] = 0

def iterate(geometry, mat_A, vec_b, vec_y, row_sum):
    i = 0
    epsilon = 1e-7
    n_rows, n_cols = geometry.shape

    while i == 0 or np.any(vec_y[:-n_cols] < -epsilon):
        print("--- cycle %d ---" % i)
        print("    Matrix A:")
        print(array_to_indent_str(np.around(mat_A, 3), 2))
        print("    Vector b^{T}:")
        print(array_to_indent_str(np.around(vec_b.T, 3), 2))

        vec_y = lstsq(mat_A, vec_b, rcond="warn")[0]

        if i > 0:
            remove_var(geometry, mat_A, vec_y, epsilon)

        print("    Vector y^{T}:")
        print(array_to_indent_str(np.around(vec_y.T, 3), 2))
        print_vec_y(vec_y, geometry, row_sum, indent=1)

        i += 1

def search(geometry, row_sum):
    print("=== Start ===")
    print("row_sum^{T}:")
    print(row_sum.T)
    print("geometry:")
    print(geometry)
    n_rows, n_cols = geometry.shape
    vec_y = np.empty(geometry.size + n_cols)
    # Set initial guess to solution with no zero
    vec_y[:-n_cols].reshape(n_rows, n_cols)[:] = \
        row_sum[:, np.newaxis] / n_cols
    vec_y[-n_cols:] = 0
    print("Intial Guess:")
    print_vec_y(vec_y, geometry, row_sum, indent=1)

    mat_A = make_mat_A(geometry)
    vec_b = make_vec_b(geometry, row_sum)
    iterate(geometry, mat_A, vec_b, vec_y, row_sum)

def problem_1_4_1():
    # For the 1-4-1 problem, use
    row_sum = np.array([1, 4, 1])
    geometry = np.array(
        [[1, 1, 0],
         [0, 1, 0],
         [0, 1, 1], ]
    )
    search(geometry, row_sum)

def problem_random():
    np.set_printoptions(precision=3)
    N = 100 * 2
    n_rows = N
    n_cols = N
    # row_sum is integers between 1 and 100 inclusive.
    row_sum = np.random.randint(1, 1000, size=n_rows)
    # geometry is a random array of zeros and ones.
    geometry = np.random.choice(2, size=(n_rows, n_cols))

    search(geometry, row_sum)

problem_1_4_1()
problem_random()

```

### Random Implementation Ideas

1. No need to calculate pseudo inverse. Some solvers solves for a linear least square system. That is equivalent to solve by Moore-Penrose inverse, but possibly faster. https://eigen.tuxfamily.org/dox/group\__LeastSquares.html
2. Use sparse solvers if there are many zeros.
3. Maybe rewrite the equations in block triangular form. For each overall iteration, perform one newton iteration on each block. That means no need for sparse matrix and two much smaller dense matrices. Don't know if that is possible though.
4. Use old solution as initial value for finding new solution.

### Alternative and Questions

Use/Derive Simplex/criss-cross algorithm for the derivative of the lagrange multiplier equations. Don't know speed.

Or Use/Derive Simplex algorithm for quadratic programming.

https://www.me.utexas.edu/~jensen/ORMM/supplements/methods/nlpmethod/S2\_quadratic.pdf

https://math.stackexchange.com/questions/246808/analog-of-simplex-method-for-quadratic-programming

What algorithm does the solver use?

How big is the matrix $X$?

How many zeros in matrix $X$?

---
Tags: optimization, linear-algebra
---


title: Sorting functions by asymptotic growth

text:
# Question
Title: Sorting functions by asymptotic growth
Assume I have a list of functions, for example

$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$

How do I sort them asymptotically, i.e. after the relation defined by

$\qquad f \leq\_O g \iff f \in O(g)$,

assuming they are indeed pairwise comparable (see also here)? Using the definition of $O$ seems awkward, and it is often hard to prove the existence of suitable constants $c$ and $n\_0$.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).

# Answer
> 54 votes
If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions.

> If $c = \lim\_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then
>
> * $c=0 \qquad \ \\,\iff f \in o(g)$,
> * $c \in (0,\infty) \iff f \in \Theta(g)$ and
> * $c=\infty \quad \ \ \ \iff f \in \omega(g)$.

With this, you should be able to order most of the functions coming up in algorithm analysis¹. As an exercise, prove it!

Of course you have to be able to calculate the limits accordingly. Some useful tricks to break complicated functions down to basic ones are:

* Express both functions as $e^{\dots}$ and compare the exponents; if their ratio tends to $0$ or $\infty$, so does the original quotient.
* More generally: if you have a convex, continuously differentiable and strictly increasing function $h$ so that you can re-write your quotient as

$\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^\*(n))}{h(g^\*(n))}$,

with $g^\* \in \Omega(1)$ and

$\qquad \displaystyle \lim\_{n \to \infty} \frac{f^\*(n)}{g^\*(n)} = \infty$,

then

$\qquad \displaystyle \lim\_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

See here for a rigorous proof of this rule (in German).
* Consider continuations of your functions over the reals. You can now use L'Hôpital's rule; be mindful of its conditions²!
* Have a look at the discrete equivalent, Stolz–Cesàro.
* When factorials pop up, use Stirling's formula:

$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

It is also useful to keep a pool of basic relations you prove once and use often, such as:

* logarithms grow slower than polynomials, i.e.

$\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$ for all $\alpha, \beta \> 0$.
* order of polynomials:

$\qquad\displaystyle n^\alpha \in o(n^\beta)$ for all $\alpha \< \beta$.
* polynomials grow slower than exponentials:

$\qquad\displaystyle n^\alpha \in o(c^n)$ for all $\alpha$ and $c \> 1$.

---

It can happen that above lemma is not applicable because the limit does not exist (e.g. when functions oscillate). In this case, consider the following characterisation of Landau classes using limes superior/inferior:

> With $c\_s := \limsup\_{n \to \infty} \frac{f(n)}{g(n)}$ we have
>
> * $0 \leq c\_s \< \infty \iff f \in O(g)$ and
> * $c\_s = 0 \iff f \in o(g)$.
>
> With $c\_i := \liminf\_{n \to \infty} \frac{f(n)}{g(n)}$ we have
>
> * $0 \< c\_i \leq \infty \iff f \in \Omega(g)$ and
> * $c\_i = \infty \iff f \in \omega(g)$.
>
> Furthermore,
>
> * $0 \< c\_i,c\_s \< \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$ and
> * $ c\_i = c\_s = 1 \iff f \sim g$.

---

Check here and here if you are confused by my notation.

---

¹ Nota bene: My colleague wrote a Mathematica function that does this successfully for many functions, so the lemma really reduces the task to mechanical computation.

² See also here.

# Answer
> 20 votes
Another tip: sometimes applying a monotone function (like log or exp) to the functions makes things clearer.

# Answer
> 18 votes
Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual:

$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$ \gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$

Here $\alpha(n)$ denotes the inverse Ackermann function.

# Answer
> 12 votes
Tip: draw graphs of these functions using something like Wolfram Alpha to get a feeling for how they grow. Note that this is not very precise, but if you try it for sufficiently large numbers, you should see the comparative patterns of growth. This of course is no substitute for a proof.

E.g., try: plot log(log(n)) from 1 to 10000 to see an individual graph or plot log(log(n)) and plot log(n) from 1 to 10000 to see a comparison.

# Answer
> 10 votes
I suggest proceeding according to the definitions of various notations. Start with some arbitrary pair of expressions, and determine the order of those, as outlined below. Then, for each additional element, find its position in the sorted list using binary search and comparing as below. So, for example, let's sort $n^{\log\log n}$ and $2^n$, the first two functions of n, to get the list started.

We use the property that $n = 2^{\log n}$ to rewrite the first expression as $n^{\log\log n} = (2^{\log n})^{\log\log n} = 2^{\log n\log\log n}$. We could then proceed to use the definition to show that $n^{\log\log n} = 2^{\log n\log\log n} \in o(2^n)$, since for any constant $c \> 0$, there is an $n\_0$ such that for $n \geq n\_0$, $c(n^{\log\log n}) = c(2^{\log n\log\log n}) \< 2^n$.

Next, we try $3^n$. We compare it to $2^n$, the largest element we have placed so far. Since $3^n = (2^{\log 3})^n = 2^{n\log3}$, we similarly show that $2^n \in o(3^n) = o(2^{n \log 3})$.

Etc.

# Answer
> 5 votes
Here a list from Wikipedia, The lower in the table the bigger complexity class; $$ \begin{array}{|l|l|} \hline Name & \text{Running Time} \\ \hline \text{Constant time} & \mathcal{O}(1) \\ \text{Inverse Ackermann time} & \mathcal{O}(a(n)) \\ \text{Iterated logarithmic time} & \mathcal{O}(\log^\*n) \\ \text{Log-logarithmic} & \mathcal{O}(n \log n) \\ \text{Logarithmic time} & \mathcal{O}(\log n) \\ \text{Polylogarithmic time} & poly(\log n) \\ \text{Fractional power} & \mathcal{O}(n^c) ,\text{where } 0\<c\<1 \\ \text{Linear time} & \mathcal{O}(n) \\ \text{"n log star n" time} & \mathcal{O}(n \log^\* n) \\ \text{Quasilinear time} & \mathcal{O}(n \log n) \\ \text{Quadratic time} & \mathcal{O}(n^2) \\ \text{Cubic time} & \mathcal{O}(n^3) \\ \text{Polynomial time} & poly(n) = 2^{\mathcal{O}(\log n)} \\ \text{Quasi-polynomial time} & 2^{\mathcal{O}(poly(\log n))} \\ \text{Sub-exponential time (first definition)} & \mathcal{O}(2^{n^{\epsilon}}), \epsilon \>0 \\ \text{Sub-exponential time (second definition)} & 2^{\mathcal{o}(n)}\\ \text{Exponential time(with linear exponent)} & 2^{\mathcal{O}(n)} \\ \text{Exponential time} & 2^{poly(n)} \\ \text{Factorial time} & \mathcal{O}(n!) \\\hline \end{array} $$

note : $poly(x) = x^{\mathcal{O}(1)}$

---
Tags: asymptotics, landau-notation, reference-question
---


# Question
Title: Why does the explanation of auxiliary carry flag differ from the article to article?
These two images are from Google search.

> AUXILIARY CARRY FLAG: This flag is set to a 1 by the instruction just ending if a carry occurred **from bit 3 to bit 4** of the A Register during the instruction’s execution

Explanation from Quora

> It indicates when a carry or borrow has been generated **out of the** **least significant four bits** of the accumulator register following the execution of an arithmetic instruction. It is primarily used in decimal (BCD) arithmetic instructions.

Explanation from Wikipedia

These two different definitions really confuses me. As I experimented this on Keil using 8051, and it showed that AC is set when the carry occurs out of four low bits. What is the precise definition?

# Answer
> 1 votes
The two definitions are exactly the same. Don't forget that in computer science, we often start counting things at zero rather than at one.

---
Tags: cpu
---


title: Nyquist theorem, sample meaning

text:
# Question
Title: Nyquist theorem, sample meaning
Given that this wave was sampled at a sampling frequency *f*:

Why does the wave sampled at a sampling frequency *3f/2* look like this?

What does *3f/2* mean? Does it mean that we sample every 2 waves 3 times?

# Answer
> 1 votes
The wave is the whole curve: you shouldn't think of your first diagram as showing "four waves" as if you were counting waves from the sea hitting the beach. Although your graphs aren't labelled, the horizontal axis is likely intended to be time, not distance, and the graph shows the oscillation of a single particle over time. So the dashed line shows the movement of the particle over time: think of it as moving up and down.

The sampling frequency is the number of times per second that you measure the particle's position. In the first diagram, the measurements all happen when the particle is in the same place so sampling at that particular frequency causes you to believe that the particle isn't moving at all (the orange line). In the second diagram, we're sampling $3/2=1.5$ times more often so, now we see the particle in different positions and, in particular, we see that it's not stationary.

Note that the two diagrams are drawn at different scales, which isn't very helpful.

# Answer
> 0 votes
Both $f$ and $3f/2$ are frequencies, measured in units of $\mathit{time}^{-1}$. Sampling at frequency $f$ means sampling every $1/f$ time units. If you're sampling with frequency $3f/2$, you're sampling $3/2$ times more than when sampling with frequency $f$ for the same time duration.

---
Tags: sampling
---


# Question
Title: How to efficiently create balanced KD-Trees from a static set of points
From Wikipedia, KD-Trees:

> Alternative algorithms for building a balanced k-d tree **presort** the data prior to building the tree. They then maintain the order of the presort during tree construction and hence **eliminate the costly step** of finding the median at each level of subdivision. \[..\] This algorithm presorts n points in **each of k dimensions**

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

```
0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)

```

I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

```
Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1)
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)

```

We start creating the KD-Tree. Lets split by **X axis**, at the first step. We select the median of the points, `3 = (3, 6)`, so the Left and right trees will like this:

```
Left  (first half)
1 = (2, 9)
4 = (2, 1)

Right  (second half)
0 = (4, 7)
2 = (5, 4)

```

Now we want to sort the Left and the Right trees by **Y axis**. How are we supposed to make use of the points that we sorted previously by **Y axis** ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by **Y axis**. What is Wikipedia talking about ?

# Answer
> 0 votes
At depth = 1, with your pre-sorted Y list, you'll still need to perform a comparison to the parent node (and compare by X value).

This ensures that items on the left branch will have X value less than parent node, and items on right branch will have X value greater than parent node.

Since at depth = 1, your list is already pre-sorted by Y value, you save time from sorting at each level.

In the case that your item is the same as the parent node, you don't insert, because that node is already the parent.

---
Tags: algorithms, search-algorithms, trees, binary-trees, search-trees
---


title: Understanding CLIQUE structure

text:
# Question
Title: Understanding CLIQUE structure
I am working on the following problem:

Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is a complete subset of some graph. The graph coloring problem consists of assigning a color to each of the vertices of a graph such that adjacent vertices have different colors and the total number of colors used is minimized. We define the chromatic number of a graph G to be this minimum number of colors required to color graph G. Prove that the chromatic number of a graph G is no less than the size of a maximal clique of G.

So far, I have been thinking about the problem and came up with the following:

* In a clique, every vertex is adjacent to every other vertex
* Therefore, since the problem states adjacent verteces always have different colors, the number of colors needed would be the number of verteces in the clique
* Thus, the chromatic number of any graph G has to be at least the maximal size of the clique, per the definition of a clique.

Can someone verify if my understanding is correct? Or am I glaringly not understanding a clique?

# Answer
> 2 votes
Your understanding is right. So in particular, for any graph $G$ with a clique of size $k$, you will need at least $k$ colors to properly color it. In case this is not obvious, you can think about it via a contradiction. So assume $G$ contains a clique of size $k$, and you have a proper coloring with less than $k$ colors. It follows that the clique contains at least two vertices with the same color. By definition of a clique, these two vertices are adjacent. But this is a contradiction to the coloring being proper.

Further, one might also wonder if the chromatic number of a graph would always equal the clique number. In this direction, you can have a look at perfect graphs for which the chromatic number of every induced subgraph equals its clique number. On the other hand, the Mycielski graphs show that there are graph that don't even contain a triangle (equivalently, a clique on 3 vertices), while the chromatic number can be arbitrarily large.

---
Tags: algorithms, graphs, clique
---


# Question
Title: When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted?
So, after a collision, a piece of information gets stored in the *next* bucket. When retrieving the value later with a key, how do we know it has not been shifted due to a collision and that we are in fact receiving the wrong value?

# Answer
> 4 votes
With linear probing, the appropriate bucket stores both the value and the literal key. So when retrieving, you start in the bucket determined by the hash code and check if the key is the same. If it's not, you move to the next one and check again, and repeat until you find what you're looking for.

---
Tags: hash-tables
---


title: Is my pumping lemma proof correct?

text:
# Question
Title: Is my pumping lemma proof correct?
> Show that $L = \\{a^nb^l \ | \ n \leq l \\}$ is not regular

I'd like to check if my proof for this is correct.

*Proof:* Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+1 \geq m$ and $1\leq |a^m| \leq m$. Write $w=xyz$ where $x=\varepsilon$, $y=a^m$ and $z=b^{m+1}$. We have $$xy^3z= \varepsilon(a^m)^3b^{m+1} = a^{3m}b^{m+1} \not\in L\\,,$$ since $3m \> m+1$ for any positive integer $m$. Thus by the contrapositive of the Pumping Lemma we can conclude that $L$ is not regular. $\square$

---

Although we normally close "check my work questions", this question illustrates a very common mistake with the pumping lemma, so is intended as a reference question.

# Answer
> 0 votes
No, this proof is not correct.

To prove that a language is non-regular using the pumping lemma, you need to show that:

1. for all $m\>0$, there is a string $w\in L$ of length at least $m$ such that
2. for all ways of writing $w=xyz$ with $|y|\geq 1$,
3. there is some $i\geq 0$ such that $xy^iz\notin L$.

You have shown that *some* way of writing $w=xyz$ makes part 3 true, but that is not enough.

To understand why, it's helpful to consider why the pumping lemma is true. The point is that, if a language is regular, it is accepted by a DFA and that DFA has some number $n$ of states. That means that, if it reads a string $w$ of length more than $n$ then, by the pigeonhole principle, it must enter some state $q$ twice (or more). Then we can set $w=xyz$ where

* $x$ is what is read before entering $q$ for the first time ($x=\varepsilon$ if $q$ is the initial state);
* $y$ is what is read after the character that causes the first entry to $q$ up to, but not including, the character that causes the second entry to $q$ (so $y$ contains at least one character, i.e., $|y|\geq 1$);
* $z$ is the rest of the string.

Now the point is that the string $xy^iz$ causes the DFA to go around the loop from $q$ to $q$ $i$ times, then carry on to an accepting state by reading $z$, so every string $xy^iz$ must also be accepted. However, the specific partition of $w$ into $x$, $y$ and $z$ depends on which automaton you're considering. To show that *no* automaton accepts the language, you need to show that every possible automaton fails, which means you need to show that all possible partitions $w=xyz$ fail.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: Random conditional association

text:
# Question
Title: Random conditional association
I have a really specific problem to solve and i'm looking for an existing algorithm to help me (i hope i'm in the right section of stackExchange).

I would have to make "random" association between items but all association need to have to answer to specific conditions.

Below, an simple exemple in javascript.

1. **INPUT**

`var items = [12, 32, 25, 11, 8, 2, 4, 3, 8, 9];`
2. **CONDITION**

All couples sum need to be between "**20**"(include) and "**27**"(include).

3. **OUTPUT**

`result = [[12,9], [11,9], [25,2], ...];`

This is a really "simple" exemple. I need to implement this with at least 3 or 4 items by couples but the conditions is almost the same.

Is it an algorithm that existing to easly do this kind of stuff ? Or did i need to iterate all couples possibilities to pick up randomly after ? Even a way to iterate less for the generation of all couples would be nice.

Thank you a lot for your help.

# Answer
> 1 votes
There is a similar problem, where you're looking for pairs with a given sum $S$.

For that problem, you initialize an empty set and then iterate once through your numbers. For each number $x$ you do:

1. Check, if the number $S-x$ is in the set. If it is, you can form the pair $(x,S-x)$.
2. Add $x$ to the set.

If its allowed to use a number twice, you would only have to switch step (1) and (2).

To check for ranges instead of exact sums you would have to adapt your data structure. You would exchange the set with a range tree and do the following:

1. Query your range tree for the range $(low-x,high-x)$ (where low and high are 20 and 27 in your example). This query will return a set $P$ of numbers and you can form a pair $(x,p) \forall p \in P$.
2. Add $x$ to the range tree.

Obviously, this approach only works for pairs. If you want to get all tuples with 4 elements you could first generate all distinct pairs and then try to combine them with the approach I've outlined above. This would result in an $\mathcal O (n^2 \log n)^\*$ algorithm (same for tuples with 3 elements, though you would add the pair-sums to the DS and query with the elements from your initial array and not with other pair-sums).

\*: This runtime is only correct if the size of tuples in a range is bounded with $\mathcal O(1)$. The worst case without this assumption is of course $\mathcal (N^4)$, when e.g. you have $N$ positive numbers and your allowed range is from $0$ to $\infty$ (result = all possible 4-tuples, without constraints).

PS: I think it's highly likely, that there cannot be a better algorithm, as this problem is an adaptation of 3SUM.

# Answer
> 0 votes
Assume the input is static (not a stream).

Assume needs to make lots of random pairs satisfying the condition.

Let's say the constraint is 4 $\le$ sum of the pairs $\le$ 10.

Setp 1. Sort the items.

```
data array: [1, 3, 4, 5, 7, 9]

```

Step 2. For each item, precompute the ranges that satisfies the condition.

```
As element 1, and the next element (offset 1) can form a pair.
    offset array: [1, ... ]
As element 1 can form valid pairs with 3, 4, 5, 7, 9, which are
5 elements
    size array:   [5, ... ]
1 and 5 are offset and size of the 0th range.

```

Step 3. Randomly select a range, weighted by the sizes of the ranges. This can be done by selecting a random number x between 1 (inclusive) and the sum of sizes of all range (inclusive). Then search for x in the cumulative sum of the size array by binary search.

```
 If size array is:  [5, 1,  4,  6,  7]
 cumulative sum is: [5, 6, 10, 16, 23]

```

Step 4. If the ith range is selected, one of the element of the pair is `data[i]`.

Step 5. Randomly select an element within the selected range. Let's say the jth element is selected. The other element of the pair is `data[i + j + offset[i]]`.

Step 6. If you want the larger element in a pair can be either the 0th or 1st element of the pair, then you can randomly swap the two elements of the pair.

---
Tags: algorithms, randomness
---


# Question
Title: Is Artificial General Intelligence possible with our current machine learning models?
In other words, is artificial human level intelligence not possible yet just because of limitations in processing power and amount of data required to train the models? Or we don't have the knowledge of how to achieve it even in theory? Suppose that processing power and amount of training data is not a problem, could humanity build AGI with our current machine learning models and knowledge?

# Answer
The short answer is, we don't know! This is an open question in AI research.

We know how neurons transmit signals, and can simulate that in a straightforward way: that's how layered perceptron models work. If we had a way to measure all the connections in a human brain, and enough computing power (which would be a LOT of computing power), we could simulate it. Or we could just make a neural network with as many neurons and connections as a human brain has. There's no theoretical missing link, we're just orders and orders of magnitude away in scale.

But it's an unanswered question whether the human mind exists entirely within neurons or not. It's a philosophical question more than a computer science one, and comes down to monism versus dualism.

Those who believe there's no theoretical barrier to AGI (just a problem of scale) tend to call their belief the Strong Church-Turing Thesis, which claims that a universal Turing machine could simulate a human mind, given unbounded resources and time. Or, equivalently, that a human mind is a Turing machine, or that there's nothing a human mind can do that a computer cannot do given time and resources for it.
> 6 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: The validity of the potential function for splay tree
The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in the splay tree, where the rank of a node $x$ is taken as the logarithm of the size ($s(x)$; i.e., number of nodes in) of the subtree rooted at $x$:

$$\Phi(T\_i) = \sum\_{x \in T} \log (s(x)).$$

To make sure that the amortized cost is an upper bound of the actual cost, it is required that the final potential is no less than the initial potential $\Phi(T\_0)$ (Page 657):

$$\forall 1 \le i \le m: \Phi(T\_i) \ge \Phi(T\_0).$$

***Problem:*** How to verify the condition above? (I did not find the argument in the paper.) Maybe it is not necessary to verify this condition; if so, why?

# Answer
***Answer My Own Question:***

***The short answer:***

We don't have to verify $$\forall 1 \le i \le m: \Phi(T\_i) \ge \Phi(T\_0).$$ This condition is a special case of a more general one, which we need to verify for this example.

***The detailed answer:***

Consider a data structure $D$ and its states $D\_0 \cdots D\_m$ produced by a sequence of $m$ operations $o\_1 \cdots o\_m$: $$ D\_0,\\; o\_1,\\; D\_1,\\; o\_2,\\; \cdots,\\; \underbrace{D\_{i-1},\\; o\_{i},\\; D\_{i}}\_{\text{the $i$-th operation}},\\; \cdots,\\; D\_{m-1},\\; o\_{m},\\; D\_{m}. $$

The amortized cost of the $i$-th operation $o\_i$ is defined as: $$\hat{c\_i} = c\_i + \Big(\Phi(D\_{i}) - \Phi(D\_{i-1})\Big)$$

Therefore, the total actual cost of these $m$ operations equals the total amortized cost plus the net decrease in potential from the initial to the final state.

$$ \sum\_{1 \le i \le m} c\_i = \left( \sum\_{1 \le i \le m} \hat{c\_i} \right) \+ \Big(\underbrace{\Phi(D\_{0}) - \Phi(D\_m)}\_{\text{net decrease in potential}} \Big). $$

For each upper bound $\Box$ for $\Phi(D\_{0}) - \Phi(D\_m)$, we get a corresponding upper bound for the total actual cost of all operations:

$$ \sum\_{1 \le i \le m} c\_i \le \left( \sum\_{1 \le i \le m} \hat{c\_i} \right) + \Box. $$

The condition $$\forall 1 \le i \le m: \Phi(D\_i) \ge \Phi(D\_0)$$ in the post is just a special case of deriving upper bounds for the total actual cost, where the upper bound is the total amortized cost. Moreover, it is common to choose $\Phi$ such that $\Phi(D\_0) = 0$ and $\Phi(D\_i) \ge 0$ for all $i$.

To verify the validity of the potential function for splay trees, we use the following upper bound for $\Phi(T\_{0}) - \Phi(T\_i)$:

$$\Phi(T\_{0}) - \Phi(T\_i) \le n \log n.$$
> 0 votes

---
Tags: algorithms, data-structures, amortized-analysis, binary-search-trees, splay-trees
---


# Question
Title: Calculation of effective average instruction execution time in a 2-level paging system
> * System has a two level paging scheme
> * Average CPU time for a instruction = 100ns
> * Average number of memory accesses per instruction = 2
> * Regular memory access = 150 ns
> * Page fault service time = 8ms
> * TLB hit ratio = 0.9
> * Page fault rate = 0.0001
>
> What is the average instruction time if the time required for address translation is negligible?

I worked out the solution as follows

```
Average instruction execution time = CPU time + Memory access time

Memory access time = No. of memory accesses by the instruction * average memory access time

Average memory access time =
 [probability of a TLB hit * regular memory access time]
 + [probability of a TLB miss * (Time for accessing the 1st level of the paging tables
     + Time for accessing the 2nd level of the paging tables
     + Time for accessing memory which may not be paged in with the translated address)]

Time for accessing the 1st level of the paging tables
= Time for accessing the 2nd level of the paging tables
= Time for accessing memory which may not be paged in with the translated address
    = [probability of a page fault * (page fault service time + regular memory access time) ]
      + [probability of no page fault * regular memory access time]
    = [0.0001 * (8 ms + 150ns)]  + [0.9999 * 150 ns]
    = 950 ns

Thus, average time per memory access = [0.9 * 150ns] + [0.1 * 3 * 950ns] = 420ns

Average instruction execution time = 100ns + (2 * 420ns) = 940ns

```

However the choices for this question are 645ns, 1050ns, 1215ns and 1230 ns.

I can't seem to be able to see where I have reasoned wrong.

**EDIT**

---

Average number of memory accesses per instruction is 2

# Answer
> 3 votes
I think the question wants you to assume that only about 30% of instructions involve a data memory access (which is somewhat low even for a RISC, Hennessey & Patterson give 47% for MIPS for 5 SPECint2000 benchmarks). 100ns + (1.3 * 420ns) = 646.

(Unless the average number of memory accesses per instruction was provided elsewhere, this question is technically unanswerable; but guessing that the number is less than two per instruction \[e.g., a load-store ISA and not a memory-memory ISA\] might be reasonable.)

# Answer
> 2 votes
I see two possible flaws in your reasoning. 1) At least the first level of the page table is typically pinned in memory (so it could never cause a page fault). 2) The page fault rate is presumably independent of the TLB miss rate (i.e., it is page faults per access not page faults per TLB miss).

This still will not provide an answer equal to any of the options. If the page fault rate is per access, then that would add 800ns to each memory access--1600ns in total--, which exceeds the highest value for *total* execution time! If the page fault rate is--bizarrely--per TLB miss (and the whole page table is pinned in memory), page faults would add 80ns to each memory access and TLB misses would add 30ns to each access; this would total 100ns + 2 * (150ns + 80ns + 30ns) = 620.

My guess is that the person providing the solution made an arithmetic error and only included the TLB miss and page fault overhead for one memory access. I.e., instead of 100ns + 2 * 150ns + 2 * (0.1 * \[2 * 150ns\]) + 2 * 0.0001 * 800ms--which would equal 2060ns--, they calculated 100ns + 2 * 150ns + ONE * (0.1 * \[2 * 150ns\]) + ONE * 0.0001 * 800ms--which would equal 1230ns, which is one of the answers provided. (This is assuming the page table is pinned in memory.)

**Students should not have to debug questions!**

# Answer
> 1 votes
Adding the exact question as this was asked in GATE2004

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

Answer:

Average Instruction execution time

= Average CPU execution time + Average time for getting data(instruction operands from memory for each instruction)

= Average CPU execution time \+ Average address translation time for each instruction \+ Average memory fetch time for each instruction \+ Average page fault time for each instruction

= 100 +2(0.9(0)+0.1(2×150)) +2×150 +1/10000×8×10^6

(Page Fault Rate per 10,000 **instruction** is directly given in question and this is not per memory access.Two memory accesses per instruction and hence we need 2 × address translation time for average instruction execution time)

\[ TLB access time assumed as 0, and 2 page tables need to be accessed in case of TLB miss as the system uses two-level paging \]

= 100+60+300+800

= 1260ns

# Answer
> 0 votes
Average Instruction Execution time = Instruction time + 2\*(Average Memory Access time) Average memory access time = 0.9(0) + 0.1(2\*150) + 150 + 1/10000(8)\*10^6 =980ns. Now, Average Instruction Execution time = 100 + 2\*980 =2060ns.

---
Tags: operating-systems, virtual-memory, paging
---


# Question
Title: Prominent applications not suited for distributed computing
In the www I can find a lot of application examples suited for and benefitting a lot from distributed computing.

---

**Question**: Are there applications which are *not* suited for distributed computing? If yes (which I assume) which promiment examples are out there?

---

Thanks a lot for pointing me into some useful direction.

# Answer
> 0 votes
* Most of the old (de)compression algorithms were not suitable for parallel or distributed computing. The variable length nature prevented decompressing later parts of the input stream before decompression of earlier parts was finished. And adaptive dictionaries often prevented compressing later parts of the input stream before compression of earlier parts was finished. Both issues can probably be avoided at reasonable cost, and maybe some modern (de)compression algorithms actually do this.
* Nearly all cryptographic hashes will not be suitable for speedup by distributed computing. Any feature which could be exploited to make distributed speedup possible also risks being exploitable to weaken the cryptographic security of the hash.
* Many popular black box opimization algorithms are not suitable for distributed computing in their basic form. Especially local optimization algorithms like the Nelder–Mead method or the Broyden–Fletcher–Goldfarb–Shanno algorithm are inherently sequential. But even more global algorithms like simulated annealing are local (and sequential) in their basic form, even so it is possible to develop parallel forms for them.

---
Tags: distributed-systems
---


# Question
Title: Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable
Consider the following language $$EQ\_{DFA} = \\{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\\}$$

Given the fact that $EQ\_{DFA}$ is decidable, how can I prove that the language $$SEQ\_{DFA} = \\{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A)\subseteq L(B)\\}$$ is also decidable?

Thank you in advance

# Answer
There are several ways to prove that $SEQ\_{DFA}$ is decidable. One of them is by using the fact that $EQ\_{DFA}$ is decidable.

Assume that $L\_1$ and $L\_2$ are languages such that $L\_1\leq\_m L\_2$ (that is, there is a mapping reduction from $L\_1$ to $L\_2$). It holds that if $L\_2$ is decidable, then so is $L\_1$. Hence, in order to prove that $SEQ\_{DFA}$ is deciadable, we reduce it to $EQ\_{DFA}$. As hinted in the comment, we propose the following reduction.

* The Reduction: Let $C$ be a fixed DFA for the empty language, that is, $L(C) = \emptyset$. The reduction operates as follows. Given instance $\langle A= \langle Q\_{A}, \Sigma, q^{A}\_0, \delta\_{A}, F\_{A}\rangle, B= \langle Q\_{B}, \Sigma, q^{B}\_0, \delta\_{B}, F\_{B}\rangle\rangle$ of $SEQ\_{DFA}$, the reduction computes a product automaton, $D$, for $L(A)\cap L(B)^C$ and outputs $\langle D, C\rangle$.
* Correctness: $L(A)\subseteq L(B)$ iff $L(A)\cap L(B)^C = \emptyset$ iff $L(D) = \emptyset$ iff $L(D) = L(C)$. (the first equivalence mentioned in the comment is simple enough and thus is left for the reader).
* Computability: the only non-trivial part is to compute $D$ given $A$ and $B$. We claim that $D$ is defined by $D = \langle Q\_{A}\times Q\_{B}, \Sigma, (q^{A}\_0, q^{B}\_0), \delta\_{D}, F\_{D}\rangle$. Where:

1) For every $(q, s)\in Q\_{A}\times Q\_{B}$ and $\sigma \in \Sigma$, $\delta\_{D}$ is defined by: $$\delta\_{D}((q, s),\sigma) = (\delta\_{A}(q, \sigma), \delta\_{B}(s, \sigma))$$

2) $F\_{D} = F\_{A}\times (Q\_{B}\setminus F\_{B})$.

Note that $D$ is a standard product automaton and thus for every finite word $w\in \Sigma^\*$, we have that $\delta\_{D}((q, s), w) = (\delta\_{A}(q, w), \delta\_{B}(s, w))$ (this can be proven by induction on $|w|$). Therefore, $w\in L(D)$ iff $\delta\_{D}((q^{A}\_0, q^{B}\_0), w) \in F\_{D}$ iff $(\delta\_{A}(q^{A}\_0, w),\delta\_{B}(q^{B}\_0, w) ) \in F\_{A}\times (Q\_{B}\setminus F\_{B})$ iff $w\in L(A)$ and $w\in L(B)^C$ iff $w\in L(A)\cap L(B)^C$. Therefore $L(D) = L(A)\cap L(B)^C$ and thus we're done.
> 1 votes

---
Tags: computability, finite-automata
---