# Question
Title: Assignment algorithm for symmetric matrices
I stumbled on the Hungarian algorithm during my personal research when I was assigned interesting problem as homework:

Given a list of objects $L$ and a pairing function $\delta : L \times L \rightarrow \left\[0, 1\right\]$, pair each object $\alpha$ in $L$ with exactly one $\beta$ in $L$ such that:

* $\sum\_{i = 1}^n \delta(\alpha\_n, \beta\_n)$ is maximal
* $(\alpha, \beta) \iff (\beta, \alpha)$
* $(\alpha, \beta) \implies \alpha \neq \beta$

Now, since we just started programming as a class, our TA wants us to use a heuristic approach to solve the problem - e.g. swap assignments until you reach a local maximum etc.

I thought of using the Hungarian algorithm to guarantee an optimal matching in (relatively) feasible time. For this, I constructed a graph with all $\alpha$ having nodes to all $\beta$ and initializing the edge of two same elements to $\infty$.

However, as it turns out, the implementation I wrote disregards the symmetric aspect of this matrix - in other words my algorithm does not guarantee that $\alpha$ is also it's the partner of the partner of $\alpha$.

I suspect that reason for this is that this is not a bipartite graph anymore. Even though there is a difference between an $\alpha$ on the left and a $\beta$ on the right, it's not a "real" bipartite graph. Is this correct?

According to the Math stack exchange I should use the more general blossom algorithm in this case, but somehow I have a feeling that I could make better use of the properties of my matrix. Is there a better algorithm for this case?

# Answer
> 1 votes
Your problem is exactly the same as maximum weight perfect matching, solved by the blossom algorithm. Although $\delta$ is not given as symmetric, you can reduce your problem to the symmetric case by replacing $\delta$ with $$ \delta'(\alpha,\beta) = \max(\delta(\alpha,\beta),\delta(\beta,\alpha)). $$ I'll let you figure out how to translate a solution which is optimal with respect to $\delta'$ to one which is optimal with respect to $\delta$.

---
Tags: graphs, optimization, matching
---


# Question
Title: Can formal languages be used to study mathematical notation?
**Question:** Are there any introductory texts in formal language or programming language theory which discuss how to apply it to the study of optimal notation?

In particular, I am interested to learn what stack-languages, parse trees, and indices are, and how to predict when a certain type of notation will lead to exponential redundancy.

I have basically no background in either formal language/grammar or programming theory, since as a math major the only computer science I learned was algorithms and graph theory, as well as very modest smidgens of complexity theory and Boolean functions. Thus, if the only books which discuss this are not introductory, I would be grateful for answers that both list such books discussing exponential notation blow-up as well as introductory books that will prepare for the books which directly address my question.

**Context:** This question is inspired primarily by an answer on Physics.SE, which says that:

> It is very easy to prove (rigorously) that there is no parentheses notation which reproduces tensor index contractions, because parentheses are parsed by a stack-language (context free grammar in Chomsky's classification) while indices cannot be parsed this way, because they include general graphs. The parentheses generate parse trees, and you always have exponentially many maximal trees inside any graph, so there is exponential redundancy in the notation.

Throughout the rest of the answer, other examples of "exponential notation blow-up" are discussed, for example with Petri Nets in computational biology.

There are also other instances where mathematical notation is difficult to parse, for example as mentioned here when functions and functions applied to the argument are not distinguished clearly. This can become especially confusing when the function becomes the argument and the argument becomes the function, e.g. here.

# Answer
> 6 votes
1. Formal language theory does not concern itself with the semantics of the language. That might seem odd, since we tend to think of language as a mechanism for communicating something, but if you think about it, there are really two levels of understanding language (at least): the surface level, in which the language is a stream of lexemes, and the underlying denotational level which is more or less divorced from the surface representation. (Chomsky posited an intermediate "transformational" level to get around some limitations with CFGs but that's not relevant here.) Consequently, it is possible to say "the same thing" in different languages; Chomsky is not a Whorfian. (See Wikipedia for a brief overview, with some references).
2. Nonetheless, a context-free grammar is not sufficient to distinguish correct and incorrect utterances. Chomsky offered the classic example: *Colourless ideas sleep furiously* (which he spelled incorrectly, being a USian). See Wikipedia, again. (Unfortunately Wikipedia doesn't have a Canadian English version.) The precise division between syntactic and semantic errors is hard, if not impossible, to demarcate and there has been considerable debate over this topic in CS fields, which I'm not going to even attempt to discuss here because I always get into trouble when I do. However, we can identify one classic grammatical rule present in many human languages: noun/verb agreement. *I disagrees* seems to me to be a syntactic error in the sense that I understand the intent of the utterance perfectly but also recognize it as erroneous. But this syntactic issue can only be captured by a context-free grammar if we enumerate all possible agreements. That is, we can write something vaguely like $S \to NP\_{sing} VP\_{sing} | NP\_{plural} VP\_{plural}$, but it is easy to see how the enumeration could get out of hand in language with more complicated agreement rules (gender, for example).
3. The problem with context-free grammars is that they are context-free, although you shouldn't take that description too seriously because it is easy to fall into the trap of misinterpreting technical use of common words (which, I might argue, is the basis of this question in the first place). That means that a nonterminal (like $NP$ above) must derive exactly the same set of phrases regardless of the context in which it appears. So we could not write, for example, $S \to NP\_X VP\_X$ with the understanding that $X$ needs to be filled in the same way in both expansions. (This is one of the issues which which transformational grammar attempted to grapple.)
4. That is exactly the problem with tensor index contractions. A tensor index contraction places a particular requirement on the use of index variables: an index variable must be used exactly twice, in which case it cannot be on the left-hand side, or exactly once, in which it must be on the left-hand side. (Since I'm not a physicist, I'd be tempted to collapse that into saying that an index variable must appear exactly twice in all. But there is a semantic distinction between free and placeholder variables, which is important to the understanding of the expression.) Here, there is no simple finite collection of index variables and no limit to the number of placeholders used. Moreover, renaming placeholders does not affect semantics provided that the new names are not used elsewhere in the expression, and one might expect the formal language description to capture that fact.
5. It is in fact possible to rigorously prove the assertion that context-free grammars cannot capture contextual agreement, as in the previous examples. I think that has something to do with what the quoted claim is asserting. Depending on how omnicurious you are, you might find it interesting to learn more, but I don't think it will end up being particularly relevant to the philosophical or physical insights you seem to be seeking.
6. The other linked articles, about unfortunate surface forms in mathematical notation, are simply anecdotal; none of them, as far as I can see, makes any deep or even superficial point relevant to formal language theory, just as the possibly famous joke that one man's fish is another man's *poisson* is not even vaguely insightful about romance linguistics, but it's still funny (IMO).

---
Tags: formal-languages, reference-request, formal-grammars, programming-languages
---


# Question
Title: Optimization over convex combinations in a circle
Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product

$$f(P) = d(P, A) \\; d(P,B) \\; d(P,C)$$

where $P$ is a point on the circle and $d$ are distances between points.

Now, every point $D$ in the interior of the circle can be written as a convex combination of points $D\_i$ on the circle:

$$D = d\_1 D\_1 + d\_2 D\_2 + d\_3 D\_3$$ where each $d\_i \> 0$ and $d\_1+d\_2+d\_3=1$. Then we define $F$ as

$$F(D) = d\_1 f(D\_1) + d\_2 f(D\_2) + d\_3 f(D\_3).$$

The problem I am interested in is: find the choice of points $\\{D\_1,D\_2,D\_3\\}$ which minimizes $F$ for a given $D$.

However, since the optimization is performed over all possible choices of $\\{D\_1,D\_2,D\_3\\}$, it is in general very difficult. Could this perhaps correspond to a more manageable optimization problem that can be computed?

Note that if one was to remove the restriction that points $D\_i$ lie on the circle and define $f$ in the same way for every point in the interior, the minimization problem would correspond exactly to finding the convex hull (convex envelope) of the function $f$. This would provide a lower bound for the original problem, but I am not sure if the computation of this quantity is in any way easier.

I would appreciate any pointers with regards to computing the minimum.

# Answer
> 3 votes
A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms.

In particular, define parameters $\theta\_1,\theta\_2,\theta\_3$, representing the angle from the horizontal of $D\_1,D\_2,D\_3$, respectively. Here each $\theta\_i$ is in the range $\[0,2\pi)$. The locations of $D\_1,D\_2,D\_3$ are completely determined by the value of $\theta\_1,\theta\_2,\theta\_3$. Therefore, we can express the value of $F$ as a function of $\theta\_1,\theta\_2,\theta\_3$: let's write this as $F^\*(\theta\_1,\theta\_2,\theta\_3)$. It's tedious but not too hard to write down an explicit expression for $F^\*$.

The problem becomes: given an expression for $F^\*$, find $\theta\_1,\theta\_2,\theta\_3$ that maximize $F^\*(\theta\_1,\theta\_2,\theta\_3)$, subject to $0 \le \theta\_1,\theta\_2,\theta\_3 \< 2\pi$. This is a mathematical optimization problem on a three-dimensional objective function $F^\* : \[0,2\pi)^3 \to \mathbb{R}\_{\ge 0}$. There are standard algorithms for maximizing such a function, e.g., using gradient descent or any number of other methods. You can try applying any of them.

In practice, I suggest you run gradient descent, starting from an initial point (an initial assignment to $\theta\_1,\theta\_2,\theta\_3$) chosen at random. Run gradient descent until convergence. This will give you a local maximum. Repeat this 1000 times, with 1000 different randomly chosen starting values, and take the best solution found in any of these iterations. While there are no guarantees, I expect this to work well. Generally speaking, these methods tend to work very well when the number of dimensions is small, and in this case, you have only 3 variables and 3 dimensions, so I expect they'll work well. In particular, I expect the function $F^\*$ to be piecewise smooth, with only a small finite number of pieces, so this procedure will probably ensure that you have at least one starting point in each piece and thus that gradient descent finds the maximum within each piece, ensuring that you find the global maximum with high probability.

If you wanted to do a more careful analysis, you could probably work out analytically the boundaries of each piece (i.e., decompose the three-dimensional space $\[0,2\pi)^3$ into a finite union of regions within which $F^\*$ is continuous and differentiable) and then run one iteration of gradient descent per piece. However, that sounds tedious, and it's probably easier to just slam the thing into an off-the-shelf optimization tool and let the computer do the grunt work for you. Doing the delicate analysis might be important if you want a procedure that is guaranteed correct in all cases (e.g., long and skinny triangles, etc.), but if you just want something that'll probably work without working too hard, I suggest you spare yourself the headache and let the computer do the crunching.

---
Tags: algorithms, optimization, computational-geometry, convex-hull
---


title: MDS minimization with gradient descent

text:
# Question
Title: MDS minimization with gradient descent
I have the following **multiple dimensional scaling** (MDS) minimization problem in vectors $v\_1, v\_2, \dots, v\_n \in \mathbb R^2$

$$\min\_{v\_1, v\_2, \dots, v\_n} \sum\_{i,j} \left( \\|v\_i - v\_j\\| - d\_{i,j} \right)^2$$

which I wish to solve numerically using gradient descent. I know all the values of $d\_{i,j}$.

I am confused because the input to gradient descent is just a vector, but for this problem it is $n$ vectors. I've come across scant information about a gradient-matrix and matrix calculus but I don't understand enough to see how this is analgous with vector calculus and hence gradient descent.

1. Is solving this minimization problem via gradient descent possible and why?
2. How else could I solve this minimization problem numerically for $v\_1, v\_2 \dots, v\_n$?

# Answer
Just concatenate all of the variables into a single, long vector. In your case, you'll have a $2n$-dimensional vector:

$$v = (v\_{1,x},v\_{1,y},v\_{2,x},v\_{2,y},\dots,v\_{n,x},v\_{n,y})$$

where $v\_{i,x}$ is the x-coordinate of $v\_i$ and $v\_{i,y}$ is the y-coordinate of $v\_i$. Now treat this as a function of $v$, i.e.,

$$f(v) = \sum\_{i,j} (||v\_i - v\_j|| - d\_{i,j})^2$$

This gives you an objective function $f: \mathbb{R}^{2n} \to \mathbb{R}$, which you can try to maximize. For instance, you can apply the gradient descent method to $f$ (after computing the partial derivatives of $f$).

---

That said: for your particular problem, gradient descent might not work very well, unless you happen to have a starting point (initial value for $v\_1,\dots,v\_n$) that is close to the optimum value. There might be many local optima that gradient descent could get stuck in. The only way to know for sure is to experiment with a bit and see what happens.
> 2 votes

---
Tags: optimization, machine-learning, numerical-algorithms, gradient-descent
---


# Question
Title: Can properties such as memory usage of a function be expressed in a dependently typed language?
Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this be done through dependent typing and effects systems?

# Answer
Yes, it can. While conceptually it's not that difficult, it hasn't been studied all that much. One aspect of the field is cost semantics such as the research done by Guy Blelloch.

In the vein of the video Anton mentioned is Daniellson's work in Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures. This does indeed use a monad to carry around a cost per operation. A similar monad, at the semantic level, is used in Denotational cost semantics for functional languages with inductive types. Here's a 2016 paper doing something similar in Coq, A Coq Library For Internal Verification of Running-Times.

The NuPRL people have also long been interested in doing things like this. In Expressing Computational Complexity in Contstructive Type Theory, which basically amounts to calculating over a structured operational semantics. Where it gets a bit more interesting is that you can reflect the language semantics into the language. The example in the final section, section 12, of Naive Computational Type Theory illustrates and discusses this sort of thing.
> 8 votes

---
Tags: type-theory, functional-programming, dependent-types, inductive-datatypes
---


# Question
Title: Big O complexity of algorithm with a nested for loop only running once
I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^2) since there is a loop over N elements and another potential other loop over N elements inside the loop. The other one thinks that since the second loop over N will only ever be executed once, the complexity is O(N). Help!

Here is the algorithm in Python:

```
def get_indexes(numbers, sum):
    s = set(numbers)
    for n in numbers:
        if n >= sum:
            continue
        if (sum - n) in s:
            return [numbers.find(n), numbers.find(sum - n)]
    return []

```

# Answer
Both of you are correct. The algorithm runs in time $O(n^2)$ (where $n$ is the size of `numbers`), and it also runs in time $O(n)$.

Big O is only an upper bound on the running time. The algorithm also runs in $O(n^3)$, in $O(n\log n)$, in $O(2^n)$, and in $O(f(n))$ for many other (in fact, infinitely many) functions $f(n)$.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Why there are no approximation algorithms for SAT and other decision problems?
I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the algorithm is not optimal, it will make errors.)

I cannot find any approximation algorithms for such problems. I was looking specifically for SAT and I found in Wikipedia page about Approximation Algorithm the following: *Another limitation of the approach is that it applies only to optimization problems and not to "pure" decision problems like satisfiability, although it is often possible to ...*

Why we do not, for example, define the approximation ratio to be something proportional to the number of mistakes that the algorithm makes? How do we actually solve decision problems in greedy and sub-optimal manner?

# Answer
> 36 votes
Approximation algorithms are only for optimization problems, not for decision problems.

Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to solve some decision problem? Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be confusing to use the same term for two different things.

OK, could we define some other ratio (let's call it something else -- e.g., "the det-ratio") that quantifies the number of mistakes an algorithm makes, for some decision problem? Well, it's not clear how to do that. What would be the denominator for that fraction? Or, to put it another way: there are going to be an infinite number of problem instances, and for some of them the algorithm will give the right answer and others it will give the wrong answer, so you end up with a ratio that is "something divided by infinity", and that ends up being meaningless or not defined.

Alternatively, we could define $r\_n$ to be the fraction of mistakes the algorithm mistakes, on problem instances of size $n$. Then, we could compute the limit of $r\_n$ as $n \to \infty$, if such a limit exists. This *would* be well-defined (if the limit exists). However, in most cases, this might not be terribly useful. In particular, it implicitly assumes a uniform distribution on problem instances. However, in the real world, the actual distribution on problem instances may not be uniform -- it is often very far from uniform. Consequently, the number you get in this way is often not as useful as you might hope: it often gives a misleading impression of how good the algorithm is.

To learn more about how people deal with intractability (NP-hardness), take a look at Dealing with intractability: NP-complete problems.

# Answer
> 15 votes
The reason you don't see things like approximation ratios in decision making problems is that they generally do not make sense in the context of the questions one typically asks about decision making problems. In an optimization setting, it makes sense because it's useful to be "close." In many environments, it doesn't make sense. It doesn't make sense to see how often you are "close" in a discrete logarithm problem. It doesn't make sense to see how often you are "close" to finding a graph isomer. And likewise, in most decision making problems, it doesn't make sense to be "close" to the right decision.

Now, in practical implementations, there are many cases where it's helpful to know what portion of the problems can be decided "quickly" and what portion cannot. However, unlike optimization, there's no one-size-fits-all way to quantify this. You can do it statistically, as you suggest, but *only* if you know the statistical distribution of your inputs. Most of the time, people who are interested in decision problems are not so lucky to have such distributions.

As a case study, consider the halting problem. The halting problem is known to be undecidable. It's a shame, because its a really useful problem to be able to solve if you're making a compiler. In practice, however, we find that most programs are actually very easy to analyze from a halting problem perspective. Compilers take advantage of this to generate optimal code in these circumstances. However, a compiler must recognize that there is a possibility that a particular block of code is *not* decidable. Any program which relies on code being "likely decidable" can get in trouble.

However, the metric used by compilers to determine how well they do at solving these particular cases of the halting problem is very different from a metric used by a cryptography program to test whether a particular pair of primes is acceptably hardened against attacks. There is no one size fits all solution. If you want such a metric, you will want to tailor it to fit your particular problems space and business logic.

# Answer
> 8 votes
In addition to the existing answers, let me point out that there are situations where it makes sense to have an approximate solution for a decision problem, but it works different than you might think.

With these algorithms, only one of the two outcomes is determined with certainty, while the other might be incorrect. Take the Miller-Rabin test for prime numbers, for instance: If the test determines that a number is *not* prime, that result is for certain. But in the other case it only means that the number is *probably* prime. Depending on how much compute time you are willing to invest, you can increase your confidence in the result, but it won't be 100% as it is for the not-prime case.

This is especially powerful when tackling undecidable problems: You could write a tool that tries to solve the halting problem for a specific piece of code. If it can find a proof that the program will not loop endlessly, you can claim so with 100% certainty. If you cannot find such a proof, it might just be that the program control flow is too convoluted for your tool to analyze, but it is not a proof that it will loop forever. By simplifying the control structures, you might be able to create an equivalent program that is simple enough for the tool to proof that it will halt for certain.

---
Tags: algorithms, satisfiability, approximation, decision-problem
---


title: Inequality caused by float inaccuracy

text:
# Question
Title: Inequality caused by float inaccuracy
At least in Java, if I write this code:

```
float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

```

the value of $e$ would be $false$. I believe this is caused by the fact that floats are very limited in the way of accurately representing numbers. But I don't understand why just changing the position of $a$ could cause this inequality.

I reduced the $b$s to one in both line 3 and 4 as below, the value of $e$ however becomes $true$:

```
float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

```

What exactly happened in line 3 and 4? Why addition operations with floats are not associative?

Thanks in advance.

# Answer
In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number.

Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results are rounded in an identical way. In other words, floating-point addition is commutative.

Take $b + b + a$: $b$ is a floating-point number. With ***binary*** floating point numbers, $2b$ is also a floating-point number (the exponent is larger by one), so $b+b$ is added without any rounding error. Then $a$ is added to the ***exact*** value $b+b$. The result is the ***exact*** value $2b + a$, rounded to the nearest floating-point number.

Take $a + b + b$: $a + b$ is added, and there will be a rounding error $r$, so we get the result $a+b+r$. Add $b$, and the result is the ***exact*** value $2b + a + r$, rounded to the nearest floating-point number.

So in one case, $2b + a$, rounded. In the other case, $2b + a + r$, rounded.

PS. Whether for two particular numbers $a$ and $b$ both calculations give the same result or not depends on the numbers, and on the rounding error in the calculation $a + b$, and is usually hard to predict. Using single or double precision makes no difference to the problem in principle, but since the rounding errors are different, there will be values of a and b where in single precision the results are equal and in double precision they are not, or vice versa. The precision will be a lot higher, but the problem that two expressions are mathematically the same but not the same in floating-point arithmetic stays the same.

PPS. In some languages, floating point arithmetic may be performed with higher precision or a higher range of numbers than given by the actual statements. In that case, it would be much much more likely (but still not guaranteed) that both sums give the same result.

PPPS. A comment asked whether we should ask if floating point numbers are equal or not at all. Absolutely if you know what you are doing. For example, if you sort an array, or implement a set, you get yourself into awful trouble if you want to use some notion of "approximately equal". In a graphical user interface, you may need to recalculate object sizes if the size of an object has changed - you compare oldSize == newSize to avoid that recalculation, knowing that in practice you almost never have almost identical sizes, and your program is *correct* even if there is an unnecesary recalculation.
> 20 votes

# Answer
Java uses IEEE 754 binary floating point representation, which dedicates 23 binary digits to the mantissa, that is normalized to begin with the first significant digit (omitted, to save space).

$0.00004\_{10} = 0.00000000000000101001111100010110101100010001110001101101000111...\_{2} = \[1.\]\color{red}{01001111100010110101100}010001110001101101000111...\_{2} \times 2^{-15}$

$1000\_{10}+0.00004\_{10} =1111101000.00000000000000101001111100010110101100010001110001101101000111...\_{2}=\[1.\]\color{red}{11110100000000000000000}\color{blue}{1}01001111100010110101100010001110001101101000111...\_{2}\times 2^{9}$

The parts in red are the mantissas, as they are actually represented (before rounding).

Because of this, $(1000\_{10} +0.00004\_{10})+0.00004\_{10}$ will produce a rounding error that is *repeated*, and thus different from the error in $(0.00004\_{10}+0.00004\_{10})+1000\_{10}$.
> 5 votes

# Answer
The binary floating point format supported by computers is essentially similar to decimal scientific notation used by humans.

A floating-point number consists of a sign, mantissa (fixed width), and exponent (fixed width), like this:

```
+/-  1.0101010101 × 2^12345
sign   ^mantissa^     ^exp^

```

Regular scientific notation has a similar format:

```
+/- 1.23456 × 10^99

```

If we do arithmetic in scientific notation with finite precision, rounding after each operation, then we get all the same bad effects as binary floating point.

---

## Example

To illustrate, suppose we use exactly 3 digits after the decimal point.

```
a = 99990 = 9.999 × 10^4
b =     3 = 3.000 × 10^0

```

### (a + b) + b

Now we compute:

```
c = a + b
  = 99990 + 3      (exact)
  = 99993          (exact)
  = 9.9993 × 10^4  (exact)
  = 9.999 × 10^4.  (rounded to nearest)

```

In the next step, of course:

```
d = c + b
  = 99990 + 3 = ...
  = 9.999 × 10^4.  (rounded to nearest)

```

Hence (a + b) + b = 9.999 × 104.

### (b + b) + a

But if we did the operations in a different order:

```
e = b + b
  = 3 + 3  (exact)
  = 6      (exact)
  = 6.000 × 10^0.  (rounded to nearest)

```

Next we compute:

```
f = e + a
  = 6 + 99990      (exact)
  = 99996          (exact)
  = 9.9996 × 10^4  (exact)
  = 1.000 × 10^5.  (rounded to nearest)

```

Hence (b + b) + a = 1.000 × 105, which is different than our other answer.
> 5 votes

# Answer
We recently ran into a similar rounding issue. The above mentioned answers are correct, however quite technical.

I found the following to be a good explanation as to why rounding errors exist. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: binary floating points can not be accurately mapped to decimal floating points. This causes inaccuracies that can compound during mathematical operations.

An example using decimal floating numbers: 1/3 + 1/3 + 1/3 would normally be equal to 1. However, in decimals: 0.333333 + 0.333333 + 0.333333 is never exactly equal to 1.000000

The same happens when doing mathematical operations on binary decimals.
> 0 votes

---
Tags: arithmetic, floating-point, numerical-algorithms
---


title: Expected distance between tree nodes

text:
# Question
Title: Expected distance between tree nodes
I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k.

A will pick a random node x from this list and B will independently pick a random node y from this list.

I have to find expected distance between these two nodes.

My way of solving it was to find the distance between all the (k\*(k-1)/2)nodes of the list and dividing it by number of nodes in the list.

for ex: n=6,k=6 list=\[1,2,3,4,5,6\]

```
                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

```

My answer was coming out to be 87/6 but the actual answer was 29/6.Please help me find whatever i am doing wrong here.

# Answer
> 4 votes
Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that $$ \sum\_{i\<j} d(i,j) = 87. $$ Hence the average distance is $$ \frac{1}{6^2} \sum\_{i,j=1}^6 d(i,j) = \frac{1}{36} \left(\sum\_{i\<j} d(i,j) + \sum\_{i\>j} d(i,j) + \sum\_{i=j} d(i,j)\right) = \frac{2\cdot 87}{36} = \frac{29}{6}. $$

A simple way to do the calculation is as follows. Suppose that there are $n$ nodes, and that edge $e$ of weight $w\_e$ cuts the tree into parts of size $k\_e,n-k\_e$. Then the average distance is $$ \frac{2}{n^2} \sum\_e w\_e k\_e (n-k\_e). $$ For example, in our case we get $$ \frac{2}{36} (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) = \frac{29}{6}. $$

---
Tags: algorithms, graphs, trees
---


# Question
Title: Finding the language of a context-free grammar?
Given following question:

Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \\{S\\}$, set of terminals $\Sigma = \\{0, 1\\}$, and set of rules $R = \\{S \rightarrow \epsilon , S \rightarrow 0 , S \rightarrow 1 , S → 0S0 , S \rightarrow 1S1\\}$. Describe $L(G)$, the language of the grammar $G$.

I know that $\epsilon, 0, 1, 00, 11, 010, 101, 01010, 10101, 10001, 01110$ all fit the grammar, but I can't find a formal way to express what I want to say. Perhaps I don't know the symbols or something, but I would express it as

$L(G) = \\{(0\ or\ 1)^n(0\ or\ 1)^{(0\ or\ 1)}(0\ or\ 1)^n,\ n \ge 0\\}$

Is this right? Is there a more formal way to express this?

# Answer
Your grammar generates the language of all palindromes. It can be described in the following ways:

1. $L(G)$ is the language of all palindromes over $\\{0,1\\}$.
2. $L(G) = \\{ x \in \\{0,1\\}^\* : x \text{ is a palindrome} \\}$.
3. $L(G) = \\{ x \in \\{0,1\\}^\* : x^R = x \\}$.

The first option is really the best, but unfortunately your TAs are expecting the third option.
> 3 votes

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


title: How many bits for offset/frame/page

text:
# Question
Title: How many bits for offset/frame/page
I'm working on the following exercise and can't get the calculations right:

Assume an OS uses:

* 33 bits for physical address
* 34 bits for logical address
* 2KB frame size

Calculate:

* How many bits are used for the offset
* How many bits are used to identify a frame
* How many bits are used to identify a page

And then: Assuming the page tables include the valid and dirty(edit) bit, calculate the size (in bits) of a process' page table using all pages.

I have a hard time understanding this type of calculation and will greatly appreciate any help.

# Answer
The frame size is 2KB. Assuming memory is byte-addressable, we need an offset into 2000 different bytes. 2000 is approximately (2^10)\*2 = 2^11, so we need 11 bits for the frame offset.

Then, we can easily calculate that 33 - 11 = 22 bits are used to identify a physical page (frame), and 34 - 11 = 23 bits are needed to identify a virtual page.
> 1 votes

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


title: Understanding Amdahl's Law calculation

text:
# Question
Title: Understanding Amdahl's Law calculation
I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput.

Which is a pretty straightforward calculation with Amdahl's Law

$S = \frac{1}{(1-f)+(\frac{f}{k})} $

$f$ = fraction of work performed by component = .40

$k$ = the speedup of new component = 1.00

$S$ = overall system speedup

Plugging in my values I get

$S = \frac{1}{(1-.4)+(\frac{.4}{1})} $

$S = 1 $

Which from my understanding mean's there is no speed up in the system. I am unsure if my calculation is wrong or my understanding of Amdahl's Law because I would think this processor upgrade would've provided at least some system speedup.

My book gives an example where $S = 1.22$ means a $22\\%$ increase in speed so I think I am interpreting the answer correctly, which implies I did my calculation wrong, but that also seems correct.

# Answer
> 1 votes
"100% **greater** throughput" means a (local) speed-up by factor $k=2$.

---
Tags: performance, program-optimization
---


# Question
Title: Is the MinMax/optimization/search variant of a decision problem always easier/equal?
Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant?

From Wikipedia:

> If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. It is not NP-complete, because it is not a decision problem.

Is the max-variant of this problem only NP-hard because the decision-variant is also NP-hard (and NP-complete)? (and not because it is harder)

What about polynomial time problems? If the decision variant of a problem is in P, I would assume that the optimization variant is not NP-hard, because that would imply P = NP. Do we say that it is in P then, or is it in another class/no class?

# Answer
No. A reduction only proves that it is "at least as hard", not that it is easier. Normally, the optimization problem is approximately as hard as the corresponding decision version (to within a polynomial factor).

If the decision problem is in P (can be solved in polynomial time), and there's a polynomial time reduction from the optimization problem to the decision problem, then that implies that the optimization problem can be solved in polynomial time. It's not literally in P, because P is a class of decision problems, but you can think of it as being in some class that is analogous/similar to P.

It's not clear to me what you mean by "the MinMax variant" or "the max-variant", so I can't answer that part.
> 1 votes

---
Tags: complexity-theory, np-complete, np-hard, decision-problem, polynomial-time
---


# Question
Title: Can a purely declarative language really exist?
Wikipedia has several languages listed as declarative languages. One of these languages listed is XSLT, which is a language for applying transformations to XML.

https://en.wikipedia.org/wiki/XSLT

As I understand it though, imperative languages say HOW to do something, while declarative languages only say WHAT to do and leave it up to the eg. compiler to figure out the imperative details.

In this light, since when writing XSLT we still say "Do transform A, then do transform B", it seems like we are still writing imperative code.

Furthermore, taking a language like C++ which is arguably imperative, it actually seems semi declarative because the optimizer can re-order instructions or, change algorithms.

In fact, a switch statement seems to be a declarative associative structure, with containing values known at compile time, letting the optimizer make the imperative details based on the type of data it stores. It can do binary searching, jump tables, if/else if chains and more. http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

This leads to my question...

Is it possible to have a purely declarative language? If so, what would it look like, and could an interpreter/compiler actually be made to convert anything into imperative machine code, beyond a no-op?

It also seems impossible to have a purely imperative language in modern days, as the CPU can do instruction re-ordering, speculative branch predictions, and similar, making your instructions more of hints as to what to do, as opposed to exact instructions of what to do.

Or am I completely off base here?

# Answer
> 3 votes
Declarative programming defined the goal, as in your example transform A to B, where steps made are not present in this layer of abstraction, and simply it is not enforced.

Imperative programming defines steps to achieve the goal. With optimizations it is a bit of mixture of both - steps are defined but this is translated to goal and then changed to make it faster.

To achieve exactly imperative in this pure form all optimisations need to be suppressed, branching does not change the order. Interpreter executing one instruction at the time does that already.

As far as I know we call languages like C, Fortran, Pascal, assembler imperative languages and do not go into details of execution. One example is read from disk 1bit, 1 byte, several bytes and so on - disk reads the whole batch at once so it did not exactly what we asked for, the same with access to memory.

The side effects are not declarative, but imperative. Purely functional language is declarative already. The problem with purely functional language is e.g. I/O, which is mittigated by monads, to set states, but it does not matter to declarative one.

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


# Question
Title: Combinatorics approach to staircase problem
There are $n$ stairs and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs every time. What is the total number of ways they can reach the top?

There are many ways to do this by using code. But when I first read this problem was to use a combinatorics approach. This problems seems very similar to a "stars and bars" problem. The stars would be the number of stairs and the bars would be the number of steps that be taken.

Given this is the case, my solution is simply: ${(n)+(2-1)}\choose{1}$.

Is the concept of stars and bars the simplest approach to solving this problem or is there a simpler combinatorics concept at play here and if so, how do I recognize such things? By simple, I mean can I solve this problem by simpler computation than combinatorics (even if it requires some sort of brute force method)?

# Answer
You can usually check whether a solution is correct by running it on some small examples. For example, say you have a stair with two steps; how many ways are there to reach the top?

Well, you can either take $1 + 1$ steps or just a single step of $2$. Unfortunately, this gives a counter-example for the proposed solution.

However, fear-not, there is still a simple combinatorial interpretation here. Since each step is either $1$ or $2$ steps, then your problem revolves down to finding all sums of the form $1 + 2 + 1 + 1 + \dots + 2 = n$. In other words, you're looking for the compositions of $n$ using just $1$ and $2$.

To solve this problem, try to work through the problem top-down. Say you are at the top ($n$) of the stair, what are the two possible choices you could have made in your final step? Well, you could have either taken a single step from $n-1$ or a double-step from $n-2$; these are necessarily disjoint since they end at different steps. Therefore, the total number of ways to reach $n$ is the same as the total number of ways to reach $n-1$ along with the total number of ways to reach $n-2$. Now, this characterizes a familiar recurrence, so I'll leave the rest to you.
> 2 votes

# Answer
Hint: a good way to sanity-check your answer is to check your formula on small values of $n$ to see if it seems to give the right number for them. This is always a good first step. Then, if it appears to give the right answer for small numbers (say $n \< 10$), the next step is to write out a proof of correctness: say, proof by induction.
> 2 votes

# Answer
Let $W(n)$ be the number of ways you can reach step $n$ by 1- or 2-step moves. Then $W(1)=1, W(2)=2$ (by two 1-step moves or one 2-step move). Then to reach $n$ height, your last move is either a 1-step move from height $n-1$ or a 2-step move from height $n-2$, giving us the recurrence $W(n) = W(n-1) + W(n-2)$. I'll leave the solution of this recurrence to you. (Hint: it should be familiar.)
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Find an upper bound for a Linear Recurrence
Im having a hard time trying to figure out how to find an upper bound to the following recurrence:

$T(N)=T(N-1)+\mathcal{O}(n)$

where i know initially $N=\lfloor\tfrac{n}{logn}\rfloor$

I believe it can be solved as a linear recurrence, but i don't know how to put $n$ in terms of $N$.

# Answer
You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N.

We have $n ≈ N \log n$.

You substitute this for n and get $n ≈ N \log (N \log n) = N \log N + N \log \log n$.

$\log \log n$ is small compared to $\log N$, so we ignore it and get $T(N)=T(N-1)+\mathcal{O}(N \log N)$

We get $T(N)$ by summing $\mathcal{O}(k \log k)$ for k = 1 to N, which will be $\mathcal{O}(N^2 \log N)$.
> 3 votes

# Answer
Finding a good analytic characterization of $n(N)$ is tricky. Let's first consider the relaxation where $N = \frac{n}{\log n}$ without the flooring restriction. Here's a somewhat nonintuitive approximation: let $m(z) = 1 + \frac{1}{z}$, let's see how $\frac{m(z)}{\log m(z)}$ behaves as a function of $z$:

$$ \begin{array}{ccc} z = 1 & 10 & 100 & 1000 & 10000 \\ 2.88\dots & 11.54\dots & 101.50\dots & 1001.50\dots & 10001.50\dots \end{array} $$

Asymptotically, this seems to give a good approximation of $n(N)$.

In fact, the Laurent series for $n(z)$ around $z = \infty$ is $$ n(z) = 1 + \frac{1}{z} + \frac{3}{2z^2} + O(z^{-3}) $$ and a second order truncation seems to be a good approximation for nearly all positive integers (even if we add in the flooring restriction, it is the correct answer for $N \ge 2$). Therefore, we're looking for the telescoping series $$ T(N) = \sum\_{1 \le k \le N} n(k) = N + H(N) + \frac{\pi^2}{4} - \frac{3}{2} \cdot \frac{3 + 2N}{2(N+1)^2} + O(N^{-2}) $$ where $H(N) = \sum\_k^N k^{-1} = O(\log N)$ is the harmonic series. This then shows that a tighter bound for your series is just $\Theta(N)$ asymptotically.
> 3 votes

---
Tags: asymptotics, recurrence-relation, upper-bound
---


# Question
Title: Why aren't existential types implemented in any mainstream language?
I'm talking about first-order existential types, as summarized here, with `pack` as the introduction form that bundles up a type with an expression of that type, and `open` as the elimination form that unpacks the type and its representative expression.

This seems just as fundamental as parametric polymorphism (universal types), so I'm surprised that this construct isn't implemented in e.g. Haskell or OCaml. Does anyone know the reasons for this?

# Answer
> 6 votes
`OCaml`'s idea of modules roughly correspond with existential types ;)

Let's set up some rough semantics in order to frame this correspondence properly. First, I'll give the intro/elimination rules for existential types (I'll only use a variable $\to$ type context $\Gamma$ for the sake of simplicity here): $$ \frac{\Gamma \vdash e\\{\alpha\mapsto \tau\\} : \sigma\\{\alpha\mapsto \tau\\}}{\Gamma \vdash \[\tau, e\] : \exists \alpha. \sigma} ({\rm Pack}) ~~~~~~~ \frac{\Gamma \vdash e : \exists \alpha.\sigma ~~~ \Gamma, x:\sigma \vdash e' : \tau'}{\Gamma \vdash {\rm let} ~ \[\alpha, x\] = e ~ {\rm in} ~ e' : \tau'}({\rm Unpack}) $$ where $e\\{\alpha \mapsto \tau\\}$ substitutes all occurrences of the type variable $\alpha$ with the concrete type $\tau$. In practice, we will also decorate the packed form with its existential type in order to disambiguate the semantics.

Operationally, we have the context reductions: $$ \frac{e \Downarrow v}{\[\tau, e\] \Downarrow \[\tau, v\]} ~~~~~~ \frac{e \Downarrow v}{{\rm let} ~ \[\alpha, x\] = e ~ {\rm in} ~ e' \Downarrow {\rm let} ~ \[\alpha, x\] = v ~ {\rm in} ~ e'} $$ which corresponds to the reduction strategies that reduces the expressions in the existential packages and the expressions to be unpacked.

Finally, we have the extensional $\eta$-reduction rule: $$ \frac{}{{\rm let} ~ \[\alpha, x\] = \[\tau, v\]\_{\exists \alpha. \sigma} ~ {\rm in} ~ e \to e \\{\alpha \mapsto \tau, x \mapsto v\\}} $$

So for example, the program \begin{align\*} {\rm let} ~ \[\alpha, x\] &= \[{\rm int}, (0, {\rm succ})\]\_{\exists \alpha. \alpha \times (\alpha \to \alpha)} ~ {\rm in} ~ ({\rm snd} ~ x : \alpha \to \alpha)({\rm fst} ~ x : \alpha)\\ &\to^{\eta} ({\rm snd} ~ (0, {\rm succ}) : {\rm int} \to {\rm int})({\rm fst} ~ (0, {\rm succ}) : {\rm int}) \\ &\to^\* {\rm succ} ~ 0 \\ &\to^\beta 1 \end{align\*}

This exact idea is present in `OCaml`'s concept of modules, save that the packed type must be a record (but which can be made to be isomorphic to any other OCaml type). For example, the creation of an existential type is done through the `module type` keyword:

```
module type Bundle =
sig
  type α
  val data : α * (α -> α)
end

```

This signature corresponds to the existential type $\exists \alpha. \alpha \times (\alpha \to \alpha)$. We can witness an inhabitant of this type by instantiating it with the `struct` keyword:

```
module BundleInt : Bundle = struct
  type α = int
  val data = (0, (+) 1)
end

```

which corresponds to the pack/intro $\[{\rm int}, (0, (+) 1)\]\_{\exists \alpha. \alpha \times (\alpha \to \alpha)}$. Unfortunately, there is no explicit ${\rm let} \dots$ elimination form, but something like `open BundleInt` is equivalent to `let [α, data] = BundleInt in ...` where α and `data` are specified in the creation of the module type `Bundle`.

So while module types aren't exactly the same as your traditional existential types (the variables to be bound are explicitly pushed into the intro-form rather than in the elimination-form), their expressiveness are the same.

---
Tags: programming-languages, type-theory
---


title: Mealy to Moore Conversion

text:
# Question
Title: Mealy to Moore Conversion
Consider an $m$ output, $n$ state Mealy machine. How many states does the equivalent Moore machine contain?

The answer is $mn$ but my argument is that the total number of output produced while reading a string of length $n$ ($n$ states) Mealy will produce $m$ outputs ($m$ transitions) but a Moore machine produces a output even in the initial state without any transitions. So to accommodate the first transition of the Mealy machine (the first output of the Mealy) we need another state in the Moore machine. So the answer should be $mn + 1$.

Can anyone tell where am I going wrong?

# Answer
It is very simple to understand.

The Mealy machine has 'm' outputs that means total 'm' transitions possible.
Number of states are 'n'.
Hence, there are a maximum of m\*n transitions possible in total.

All these transitions should be depicted in Moore machine as well, as the power of both are same.
> 3 votes

# Answer
You are right, but you confuse the two possible conversions.

It is asked from Mealy to Moore. The Mealy machine does not have a output at the initial state, as the output depends on input and current state. So there is no additional output to "be accommodated" in the Moore machine.
> 0 votes

---
Tags: automata, finite-automata, simulation
---


title: Minimum number of sets of points

text:
# Question
Title: Minimum number of sets of points
During my work I've encountered this problem:

$G = \\{(x\_i,y\_i,z\_i)\\}\_{i=1}^{n}$ is a group of points in space ($\forall i \\;\\; x\_i,y\_i,z\_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant.

Divide $G$ to $m$ groups (as few as possible) that follow this rule: for each pair of points in the same group, the distance between these two points is less than or equal to $d$. ($m$ should be, as said, the minimum)

I thought about solving it by turning it into a graph where each point is a node and 2 nodes are connected if and only if the distance between these 2 points is smaller than $d$. Then the solution is the same as finding a minimal cover of the graph using Cliques. This is an NP problem and thus can't be solved in polynomial time unless P=NP. So that doesn't provide a useful solution.

Does anybody have any idea how to solve this problem?

# Answer
I can't access the paper itself, but judging by its abstract and a mention on p. 5 of this paper, a slight generalisation of your problem was proved NP-hard in 1978: Complete-Link Cluster Analysis by Graph Coloring (Pierre Hansen and Michel Delattre). I say "slight generalisation" because (I assume that) the problem proved hard allows arbitrary distances between points; it's possible that Euclidean version of the problem, which you seem to have, is easier. Maybe even the metric version is easier.

For the case of exactly 2 clusters, Wikipedia gives a poly-time algorithm based on 2SAT.
> 2 votes

---
Tags: algorithms, graphs, set-cover, clique
---


# Question
Title: Express a number as a sum of consecutive primes (How many ways?)
I found this problem on codeforces in an ACM archive.

---

Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :

Given $n = 41$:

$41 = 41 = 2 +5+3 +7 + 11 + 13 = 11 + 13 + 17$

As we can see, there are three ways of writing $41$ as a sum of consecutive primes, keeping in mind that since $41$ is a prime, a sum that consists of only $41$ is a valid sum as well.

Knowing that $n \leq 10000$, list the number of ways you can express the input numbers as sums of consecutive primes.

---

My effort regarding this problem consists of the following :

Given that the max $n $ is $10000 $, I populated a vector of primes using the sieve of eratosthenes (its size is precisely $1229$).

Following, I computed a vector of prefix sums, such that at index $p$ of that particular vector, we have the sum of all consecutive primes up to inclusively $p$ (non prime indexed entries are equal to $0$).

For example: $\text{prime\_sums\[2\] = 2 }, \text{ prime\_sums\[3\] =5 },\text{ prime\_sums\[5\] = 10}$, etc.

Now, using this particular vector we could simply do traversals of the sum array for each of the input numbers and upon finding a way to write it as a sum (by comparing its value with that of each sum we encounter) , we would do multiple subtractions between elements of the sum array in order to find other possible ways to express our number as a sum of consecutive primes.

But this kills the speed of the program and feels really inelegant and awkward. Can you suggest alternative ways?

# Answer
> 2 votes
I assume that n is large, and that we only want the answer for one single n. In that case, we would avoid creating a sieve of all the primes up to n, if possible, because it would take O (n); I think we can do this faster.

Create a list of all primes p ≤ M, using a sieve, with a cleverly chosen M. This takes about O (M) and finds about $M / \ln M$ primes. Then we find all solutions involving primes up to M by adding up primes starting with p = 2 until the sum is ≥ n, recording a solution if the sum equals n, removing the first primes until the sum is \< n, adding primes until the sum is ≥ n etc. This only takes O ($M / \ln M)$ which is less than O (M) for the sieve, so we can ignore it.

This part of the algorithm finishes when we would need to add a prime p \> M to the list (which we don't have). At that point we know that the sum of the K largest primes ≤ M is less than s, for some K, and that we have found every possible way to write n as the sum of more than K primes. Now we have to find ways to write n as the sum of k ≤ K consecutive primes; in addition k is odd if n is odd, and k is even if n is even.

For every k, we do this by creating a sieve of primes around n / k; this sieve should be large enough to contain more than k primes. When we have the sieve, we find the first k/2 primes \> n/k and k - k/2 primes ≤ n/k. If the sum is less than n then we add the next larger prime and remove the smallest one until the sum is ≥ n; if the sum is \> n then we add the next smaller prime and remove the next larger one until the sum is ≤ n. If the sieve turns out to be to small we create a bigger one. If the sum is n, we have a solution.

Creating the sieve takes at least O ($(n/k)^{1/2} / \log n$) steps for trial divisions. Instead of creating the sieve around n/k, we could have made the original sieve larger, choosing M ≈ n / (k - 2) instead of M ≈ n / k, which would have cost about $n / k^2$ steps.

Both costs balance when $n / k^2 = (n/k)^{1/2} / \log n$ or $n^{1/2} = k^{3/2} / \log n$ or $n \log^2 n = k^3$ or $k = (n \log^2 n)^{1/3}$ or $M = n/k = (n \div \log n)^{2/3}$

The estimate for creating the small sieves may have been a bit generous; if we use this method with $M = n^{2/3}$ then it should run in $O (n^{2/3})$.

# Answer
> 1 votes
You say the number of primes less than 10000 is $n=1229 \sim 10^3$. Let the primes be stored in increasing order in the array $primes$. Let $map$ be a C++ map ( inserting in C++ map has complexity $O(\log{n})$ ). Then do the following

```
 for i = 1 to i = n
   sum = 0
   for j = i to j = n
     sum = sum + primes[j]
     map[sum] = map[sum] + 1

```

(After this when given an input number $num$ just report $map\[num\]$ )

Complexity for above code becomes $O(n^2log(n^2))$. $n$ being around $1000$ I guess it is fast enough. ( This is almost similar to your approach and will mostly pass the judge ).

---
Tags: algorithms, primes
---


title: Complement of CFL is Recursive

text:
# Question
Title: Complement of CFL is Recursive
If CFL are not closed under complementation, it means that if a language '$L$' is CFL then its compliment $L^C$ is not CFL. Then how can we discuss about $L^C$ being recursive?

My doubt arose because I think if a language cannot be decided CFL or not then how can it be declared Recursive ?

# Answer
> 15 votes
You can think of it as " every CFL is Recursive".
And Recursive languages are closed under complementation.

Therefore, if a language $L$ is CFL then it is also recursive and hence, $L^C$ is also recursive.

---
Tags: context-free
---


# Question
Title: Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$
In the grammar for *S* production two bodies have same starting symbol

$ S \to Aa \mid b A c \mid Bc \mid bBa $

So i removed the left factoring from those two productions

$ S \to bC$

$ C \to Ac Bc$

Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions

$ A \to d$

$ B \to d$

I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution

# Answer
You're looking at an implicit conflict in your grammar. Given \begin{align\*} S &\to Aa \mid b A c \mid Bc \mid bBa \\ A &\to d \\ B &\to d, \end{align\*} we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.

Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.

This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}\_n (\alpha) \cap {\rm first}\_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.

Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \\{d\\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before: \begin{align} S &\to da \mid bdc \mid dc \mid bda \\ &\Rightarrow ({\rm left ~ factoring}) \\ S &\to d X \mid bd X \\ X &\to a \mid c \end{align}

Computing the 1-lookahead predictive table results in $$ \begin{array}{ccccc} & a & b & c & d \\ S & & \to bdX && \to dX\\ X & \to a & & \to c \end{array} $$

which corresponds to the algorithm

```
function parseS(words):
  if next word is b:
    // -> bdX
    consume b; consume d; parseX(rest)
  else if next word is d:
    // -> dX
    consume d; parseX(rest)
  else: error

function parseX(words):
  if next word is a: consume a
  else if next word is c: consume c
  else: error

```
> 3 votes

---
Tags: automata, compilers
---


# Question
Title: Graph splitting via an algorithm and proof of properties
Given the following function:

```
function split(G)
    if (all vertices of G have even degree) then
        return (V (G), ∅)
    else
        Let a ∈ V be a vertex of odd degree;
        S ← NG(a);
        G ← G − a;
        for ((∀)u, v ∈ S, u != v) do
            if (uv ∈ E(G)) then
                E(G) ← E(G) − uv;
            else
                E(G) ← E(G) ∪ uv;
        (W1, W2) ← split(G);
        if (|W1 ∩ S| % 2 = 0) then
            V1 ← W1 ∪ {a};
            V2 ← W2;
        else
            V2 ← W2 ∪ {a};
            V1 ← W1;
return (V1, V2)

```

I have to show that V1∩V2 = ∅, V1∪V2 = V(G) and the subgraphs of G obtained from V1 and V2 have an even degree on all vertices.

Now, based on the function it is obvious that the properties stated above hold true, but I am stumped as to how exactly should I go about proving them and by what general rule or criteria the split function splits the graph(I have no problem following the algorithm but the "big picture" escapes me).

EDIT: NG(a) Is the set of a's neighbours.

# Answer
> 2 votes
I'll give you the schema of the proof. You'll have to fill in the blanks on your own. The idea is to prove by induction the following property $P(n)$:

> On a graph $G$ having $n$ vertices, the function $\mathrm{split}(G)$ terminates and returns a partition $V\_1,V\_2$ of the vertex set of $V$ such that in the subgraphs of $G$ induced by $V\_1$ and $V\_2$, all vertices have even degree.

First you have to prove the base case $P(1)$. That's quite easy.

Now, for every $n$ you have to prove that $P(n)$ implies $P(n+1)$. To do this, you analyze what happens when $\mathrm{split}$ is run on a graph $G$ having $n+1$ vertices. There are two cases: if all degrees in $G$ are even then it is easy to see that $\mathrm{split}(G)$ terminates with an appropriate partition. Otherwise, $\mathrm{split}$ creates a graph $G'$ on $n$ vertices and runs itself on $G'$. Since $G'$ has $n$ vertices, the induction hypothesis implies that $\mathrm{split}(G')$ with a partition $V'\_1,V'\_2$ of the vertex set of $G'$ such that the subgraphs of $G'$ induced by $V'\_1,V'\_2$ have only even degrees. The procedure $\mathrm{split}$ uses $V'\_1,V'\_2$ to create a partition $V\_1,V\_2$ of the graph $G$. It thus clearly terminates. To finish the proof, you have to show that the subgraphs of $G$ induced by $V\_1,V\_2$ have all even degrees.

This is the structure of the proof. All you have to do now is to fill in the blanks.

---
Tags: algorithms, graphs, algorithm-analysis, correctness-proof
---


title: Binary tree To Red-Black tree

text:
# Question
Title: Binary tree To Red-Black tree
I have a question regarding the solution provided by *Karolis Juodelė*. Given in this question; Colour a binary tree to be a red-black tree

Black = black nodes, white = red nodes

So for this tree when I try to manually work out the code, it seems to fail on the node 17. E.G. I have a black quota of 3 so I color the root black. Afterwards I go to the left child (17) and that has the same min height (namely 17 - 21 - 23) -\> so I color this black. After this black colour I cannot see how I will end up with a valid tree with 1 black node left.

So if you could provide how to solve it for this example that would be great!

# Answer
> 1 votes
Well, apparently my answer was wrong. The algorithm, at least. The theorem seems to be okay, if a little unreadable.

More in line with that proof, the algorithm should be

```
if n is root,   # as before
    n.color = black
    n.black-quota = n.height / 2, rounded up.
    # black-quota could start at any value between n.height/2 and n.min-height

else if n.parent is red,   # as before
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    n.black-quota = n.parent.black-quota - 1

    # check that the subtree isn't totally uncolorable
    if n.min-height < n.black-quota then
        error "shortest path was too short"

    # use red only if the subtree is not colorable (as a tree), with given quota
    if n.height <= n.black-quota*2  then
        n.color = black

    else
        n.color = red

```

What I meant by the last condition is that 17 is red for the sole reason that you can't color it black i.e. $b(17) \notin \[\frac{1}{2}h(17), m(17)\]$.

Hopefully that works. Thanks for pointing out the error!

---
Tags: data-structures, binary-trees, search-trees, balanced-search-trees
---


title: Why are Red-Black trees so popular?

text:
# Question
Title: Why are Red-Black trees so popular?
It seems that everywhere I look, data structures are being implemented using red-black trees (`std::set` in C++, `SortedDictionary` in C#, etc.)

Having just covered (a,b), red-black & AVL trees in my algorithms class, here's what I got out (also from asking around professors, looking through a few books and googling a bit):

* AVL trees have smaller average depth than red-black trees, and thus searching for a value in AVL tree is consistently faster.
* Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete. I'm saying potentially, because this would depend on the cost of the structural change to the tree, as this will depend a lot on the runtime and implemntation (might also be completely different in a functional language when the tree is immutable?)

There are many benchmarks online that compare AVL and Red-black trees, but what struck me is that my professor basically said, that usually you'd do one of two things:

* Either you don't really care that much about performance, in which case the 10-20% difference of AVL vs Red-black in most cases won't matter at all.
* Or you really care about performance, in which you case you'd ditch both AVL and Red-black trees, and go with B-trees, which can be tweaked to work much better (or (a,b)-trees, I'm gonna put all of those in one basket.)

The reason for that is because a B-tree stores data more compactly in memory (one node contains many values) there will be much fewer cache misses. You could also tweak the implementation based on the use case, and make the order of the B-tree depend on the CPU cache size, etc.

The problem is that I can't find almost any source that would analyze real life usage of different implementations of search trees on real modern hardware. I've looked through many books on algorithms and haven't found anything that would compare different tree variants together, other than showing that one has smaller average depth than the other one (which doesn't really say much of how the tree will behave in real programs.)

**That being said, is there a particular reason why Red-black trees are being used everywhere, when based on what is said above, B-trees should be outperforming them?** (as the only benchmark I could find also shows http://lh3lh3.users.sourceforge.net/udb.shtml, but it might just be a matter of the specific implementation). Or is the reason why everyone uses Red-black trees because they're rather easy to implement, or to put it in different words, hard to implement poorly?

**Also, how does this change when one moves to the realm of functional languages?** It seems that both Clojure and Scala use Hash array mapped tries, where Clojure uses a branching factor of 32.

# Answer
To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question

> For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary. Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

So a RedBlack tree insert can be implemented without recursion, on **some** CPUs recursion is **very** expensive if you overrun the function call cache (e.g SPARC due to is use of Register window)

(I have seen software run over 10 times as fast on the Sparc by removing one function call, that resulted in a often called code path being too deep for the register window. As you don't know how deep the register window will be on your customer's system, and you don't know how far down the call stack you are in the "hot code path", not using recursion make like more predictable.)

Also not risking running out of stack is a benefit.
> 16 votes

# Answer
I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures!

There are some cases where you can't use B-trees at all.

One prominent case is `std::map` from C++ STL. The standard requires that `insert` does not invalidate existing iterators

> No iterators or references are invalidated.

http://en.cppreference.com/w/cpp/container/map/insert

This rules out B-tree as an implementation because insertion would move around existing elements.

Another similar use case are intrusive datastructures. That is, instead of storing your data inside the node of the tree, you store pointers to children/parents inside your structure:

```
// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

```

You just can't make a B-tree intrusive, because it is not a pointer-only data structure.

Intrusive red-black trees are used, for example, in jemalloc to manage free blocks of memory. This is also a popular data structure in the Linux kernel.

I also believe that "single pass tail recursive" implementation is **not** the reason for red black tree popularity as a *mutable* data structure.

First of all, stack depth is irrelevant here, because (given $\log{n}$ height) you would run out of the main memory before you run out of stack space. Jemalloc is happy with preallocating worst case depth on the stack.

There are a number of flavors of red-black tree implementation. A famous one are left leaning red black trees by Robert Sedgewick (**CAUTION!** there are other variants which also are named "left leaning", but use a different algorithm). This variant indeed allows to perform rotations on the way down the tree, **but** it lack the important property of $O(1)$ amortized number of fixups, and this makes it slower (as measured by the author of jemalloc). Or, as opendatastrutures puts it

> Andersson's variant of red-black trees, Sedgewick's variant of red-black trees, and AVL trees are all simpler to implement than the RedBlackTree structure defined here. Unfortunately, none of them can guarantee that the amortized time spent rebalancing is $ O(1)$ per update.

The variant described in opendatastructures uses parent pointers, a recursive down pass for insertion and an iterative loop up pass for fixups. The recursive calls are in a tail positions and compilers optimize this to a loop (I've checked this in Rust).

That is, you can get a constant memory loop implementation of a mutable search tree without any red-black magic if you use parent pointers. This works for B-trees as well. You need magic for single pass tail recursive immutable variant, and it will break $O(1)$ fixup anyway.
> 15 votes

# Answer
Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this:

1) Average insertion cost is constant for red-black trees (if you don't have to search), while it's logarithmic for AVL trees. Furthermore, it involves at most one complicated restructuring. It's still O(log N) in the worst case, but that's just simple recolorings.

2) They require only 1 bit of extra information per node, and you can often find a way to get that for free.

3) I don't have to do this very often, so every time I do it I have to figure it out how to do it all over again. The simple rules and the correspondence with 2-4 trees makes it seem easy *every time*, even though the code turns out to be complicated *every time*. I still hope that someday the code will turn out simple.

4) The way the red-black tree splits the corresponding 2-4 tree node and inserts the middle key into the parent 2-4 node *just by recoloring* is super elegant. I just love to do it.
> 6 votes

# Answer
Red-black or AVL trees have an advantage over B-trees and the like when the key is long or for some other reason moving a key is expensive.

I created my own alternative to `std::set` within a major project, for a number of performance reasons. I chose AVL over red-black for performance reasons (but that small performance enhancement was not the justification for rolling my own instead of std::set). The "key" being complicated and hard to move was a significant factor. Do (a,b) trees still make sense if you need another level of indirection in front of the keys? AVL and red-black trees can be restructured without moving keys, so they have that advantage when keys are expensive to move.
> 4 votes

---
Tags: data-structures, search-trees, applied-theory, dictionaries, balanced-search-trees
---


# Question
Title: How to solve this asymptotic complexity problem?
The increasing order of following functions in terms of asymptotic complexity is:

(A) f1(n) \< f4(n) \< f2(n) \< f3(n)

(B) f1(n) \< f2(n) \< f3(n) \< f4(n)

(C) f2(n) \< f1(n) \< f4(n) \< f3(n)

(D) f1(n) \< f2(n) \< f4(n) \< f3(n)

I saw this question on GeeksQuiz but I am unable to understand its answer. The correct answer is D.

I think that f(2) will have the highest complexity among all because for a given number it will give the maximum output.

Please help and explain how is it solved?

# Answer
> 1 votes
$f\_3(n)$ has the highest asymptotic time since it is an exponential function. Although it is $(1+\epsilon)^n$ and might seem very tiny in terms of growth, there exists a real number $m$ where it grows faster than the rest.

Then, we have $f\_4(n)$ as quadratic function.

$f\_2(n)$ is unfortunately linear. Which means, it does not grow as fast as $f\_4(n)$ and $f\_2(n)$. Actually, while considering asymptotic growing, you should ignore the constants in the function. Thus, we can say that $O(1000000n) = O(n)$.

The tricky part is $f\_1(n)$. It would grow faster than $f\_2(n)$ if it was $O(n \log n)$. However, it is $O(n^{1-\epsilon} \log n)$, which makes it grow slower than a linear function.

---
Tags: algorithm-analysis, time-complexity, asymptotics
---


# Question
Title: How can unifying 2 sentences in first-order logic result in a variable becoming 2 different things?
I'm working on a program which must use inference in first-order logic, and everything is working great except for 1 thing which I don't understand.

The book I'm using, "Artificial Intelligence A Modern Approach" by Russell and Norvig, shows a proof on page 349 which has me confused. They combine the two following sentences: **~Loves(x,F(x))** v Loves(G(x),x)
~Animal(x) v **Loves(Jack,x)**
And they combine into:
~Animal(F(Jack)) v Loves(G(Jack),Jack)

This makes absolutely no sense to me because the variable "x" becomes both "F(Jack)" and "Jack", and that seems wrong to me.

Using the Unify function which I created by following the pseudocode provided in the book returns a failed substitution, but if the combination of the previously mentioned sentences is correct then what kind of substitution would need to be returned? (I know it's not just {x/Jack} because that would result in the sentence "~Animal(Jack) v Loves(G(Jack),Jack)", Animal would be missing the function F as shown in the example.)

Any help would be extremely appreciated!

# Answer
> 3 votes
The variables called `x` in the two sentences are not related. We can rename them to make it clear:

```
~Loves(x1,F(x1)) v Loves(G(x1),x1)
~Animal(x2) v Loves(Jack,x2)

```

Now when matching `~Loves(x1,F(x1))` and `Loves(Jack,x2)`, you can see you'll get `Jack/x1, F(Jack)/x2` and the final result as in the book.

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


# Question
Title: What is induced matching, maximum induced matching and mim-width?
I understand the concept of *induced subgraph*, but could not understan what *induced matching* is. As appears in this paper, it is defined as

> A matching in a graph is an induced matching if it occurs as an induced subgraph of the graph.

However, in this paper, there is a slightly different definition:

> A matching in a graph is a set of edges, no two of which meet a common vertex. An induced matching M in a graph G is a matching where no two edges of M are joined by an edge of G.

Thus, I am confused since there are no example figures.

Also, there is a term called *mim-width*, which is maximum induced matching width and few no none examples exist in the literature.

Could you please give some examples for me to clear things out?

# Answer
Both definitions are the same. An *induced matching* $M$ in $G$ consists of a set of edges such that $G|\_{V(M)} = M$, that is, the subgraph of $G$ induced by the vertices of $M$ is exactly $M$. This is the first definition.

Now it is always the case that $G|\_{V(M)} \supseteq M$, so $M$ is an induced matching if $G|\_{V(M)}$ contains no other matching, that is, $G$ contains no edge connecting vertices in two different edges of $M$. This is exactly the second definition.

I have never heard of *mim-width*, so it is safe to assume that it will be defined in any paper which uses it. However, it probably refers to the size (probably number of edges) of the largest induced matching in the graph.
> 4 votes

---
Tags: graphs
---


# Question
Title: Where can I find CS problem set resources?
I am trying to learn to program and I don't just want to learn syntax, but rather learn and practice breaking up and solving problems. Now, I want to know where can I go to get hold of material that ranges in programming problems from beginner to intermediate and hopefully even further so that I can train my problem-solving skills. Any tips or advice on how to train problem-solving skills would be highly appreciated too.

# Answer
What about Project Euler?

It is more focused on mathematics but still a really nice set of problems which range in the difficulty from easy to tough.

I enjoy it every time and it is a nice approach for diggin into a new programming language, like Haskell.
> 0 votes

# Answer
i don't know how far along you are in your learning but I found that actually coding is the best way. try Scratch. it is a graphical interface for code that jigsaws together only in ways that are syntactically correct so, as you have asked, you can learn to structure code and create anything you like without learning an actual language. it makes understanding simple coding very easy. Enjoy
> 0 votes

---
Tags: programming-languages
---


title: Where can I read CS papers?

text:
# Question
Title: Where can I read CS papers?
I am a self taught programmer, with no formal degree in CS. I have read couple of papers which were recommended on some or other blog and found them interesting. Where can I read papers on computer science ? Are these papers available for free? If not papers are there any essays on any popular blog posts?

# Answer
> 5 votes
If you have no formal degree in CS, I think what you need is textbook instead of scientific papers.

Being a self-taught programmer is a great achievement and I think you can build up on that with theory. But, reading papers require some deep knowledge in some area.

I would suggest you to buy one of these books:

Algorithms by Robert Sedgewick and Kevin Wayne

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Data Structures and Algorithm Analysis in C++, 4th Edition Mark A. Weiss

In these books, you can also find some references to suggested readings.

# Answer
> 3 votes
As has already been noted, papers probably are not the best way for you to start.

Perhaps you might like to check out the ArsDigita University website. This has been a project running in 2000 and 2001 (yes, some time has passed since then, but I think this does not really matter for the basics of CS), providing an intensive introduction to the most fundamental areas of CS. Course materials are available at the website, as well as pointers to books used in particular courses. In addition, lecture videos are also available online.

# Answer
> 1 votes
i´m in your same situation. I've never studied computational complexity formally, apart from some programming courses i did.

CS is a very big area of study and the advice people will give you will depend in your particular interests.

An area of study that doesn´t require (in general) to know much about mathematics/complexity theory is the study of the complexity of games. I've beeen reading papers about it and some them are more accesible than others, but generally patience is the most important thing to understand those papers.

A good place to start is the page of wikipedia: List of np complete problems. Look in the section of games and puzzles and you will see references to papers about game complexity

# Answer
> 0 votes
If you insist on reading papers, you should be able to browse the journals in the library of a university with a CS program (the more engineering-oriented the university, the more likely they will have such papers). As long as you are discreet and don't try to take out anything, you shouldn't even need to be a student or faculty to use the library (I've done this myself).

On the other hand, don't be surprised when what you read turns out to be both (a) very challenging to understand and (b) concerned with issues far outside the range of practical significance.

---
Tags: research
---


# Question
Title: Sampling maximal shortest paths in a graph?
Let **S** be the set of all possible shortest paths in a directed graph. A path s in **S** is said to be maximal if it is not a subpath of another path in **S** i.e. it cannot be extended to another shortest path.

Let **M** be the set of all **maximal** paths in **S**.

Does anyone know how to efficiently sample paths from **M**. Ideally, I would like the probability of sampling the longer paths in **M** to be higher.

`Example: In the directed triangle, (1,2,3), we have 3 maximal paths, 1->2->3, 2->3->1, and 3->1->2`

# Answer
## Non-maximal paths are prefixes or suffixes of shortest paths

So a maximal path is just a path that begins at a vertex $u$ with no in-edge and ends at a vertex $v$ with no out-edge.

It's straightforward to see that if a shortest path $P$ from $u$ to $v$ is a subpath of some shortest path $Q$ from $x$ to $y$, then $P$ is also a subpath of a shortest path $R$ from $x$ to $v$, and a subpath of a shortest path $S$ from $u$ to $y$. Thus the following statements are equivalent:

1. $P$ is not maximal;
2. There exists a shortest path $Q \ne P$ that contains $P$ as a subpath;
3. There exists a shortest path $X \ne P$ that contains $P$ as a subpath, is longer than $P$ and either begins at $u$ or ends at $v$.

(1) and (2) are equivalent by definition; (2) follows from (3) trivially; (3) follows from (2) by the reasoning above and the fact that, since $Q \ne P$, at least one of $R$ and $S$ must be longer than $P$ and end at one of $P$'s two endpoints; $X$ can be whichever one this is. We will use (3) to efficiently determine whether a given shortest path is maximal.

## Maximality is determined by endpoints and length

If some shortest path from $u$ to $v$ could be extended to a longer shortest path, then *all* shortest paths from $u$ to $v$ could be so extended -- since the only property we care about is the length, and that doesn't change. So the question of whether a given path $P$ from $u$ to $v$ is maximal is entirely determined by the length of $P$, and its start and end points $u$ and $v$ -- it is not necessary to know what specific internal vertices $P$ uses. Thus, for any pair of vertices $(u, v)$, we can determine in a preprocessing step whether this vertex pair is "maxable"; a path $P = (u, \dots, v)$ is then maximal exactly when the pair $(u, v)$ is maxable and $P$ has length equal to the distance between $u$ and $v$.

The idea is to build a complete list of all maxable pairs $(u, v)$ and the number $n\_{uv}$ of shortest paths between them. Once these are known, paths can be uniformly sampled using a simple recursive procedure.

## Determining maxable pairs

Let $A$ be the set of all vertex pairs $(u, v)$ such that $v$ is reachable from $u$. This can easily be determined in $O(n^2+nm)$ time by starting a DFS from each vertex in turn.

We determine the set of maxable pairs by initially declaring that every vertex pair $(u, v)$ such that $v$ is reachable from $u$ is maxable; we then "cross out" all pairs $(u, v)$ for which some shortest path from $u$ to some $x$ has a shortest path from $u$ to $v$ as an initial subpath; finally, we "cross out" all pairs $(u, v)$ for which some shortest path from some $x$ to $v$ has a shortest path from $u$ to $v$ as a final subpath. By (3) above, all pairs $(u, v)$ that have not been crossed out are maxable.

I'll now describe the first "crossing out" step. The second is identical, except that we first reverse all edge directions, and when we are about to cross out some pair $(u, v)$, we instead cross out $(v, u)$. The following assumes an unweighted graph; if the edges are weighted, you can replace the BFS with Dijkstra's algorithm.

From each vertex $u$ in turn, perform BFS on $G$, using $u$ as the root. For each vertex $v$ visited at level $L$ during a particular BFS, if $v$ is adjacent (in $G$) to any vertex on level $L+1$ of the BFS tree, cross out the pair $(u, v)$. This is because the paths in $G$ whose vertices start at the root $u$ of a BFS tree and thereafter occupy strictly increasing levels in that tree are exactly the shortest paths starting at $u$, and the "downward" (w.r.t. the BFS tree) edge leaving $v$ indicates that there is some $x$ for which a shortest path from $u$ to $x$ uses a shortest path from $u$ to $v$ as a subpath. This can be performed in $O(n+m)$ time per root vertex, for $O(n^2+nm)$ time overall.

Let $Z$ be the set of maxable vertex pairs that remain after the above has run.

## Counting shortest paths

As a further preprocessing step, we would like to count the number of shortest paths between any pair of vertices $(u, v)$.

For any vertex $u$, the number of shortest paths from $u$ to every other vertex $v$ can be calculated in $O(n+m)$ time with BFS. This means that the total time needed to compute the number of paths between every pair $(u, v)$ of vertices is $O(n^2+nm)$. Let $n\_{uv}$ be the number of paths from $u$ to $v$. Discard any pairs $(u, v)$ for which $n\_{uv} = 0$, i.e., for which $v$ is not reachable from $u$.

Let $n\_z = \Sigma\_{(u, v) \in Z} n\_{uv}$.

## Sampling algorithm

The input is a graph $G$. If $G$ has no vertices, return an empty path. (This will arise as a base case later on.) If it has at least one vertex then it has at least one maximal path (even if that consists of a single vertex).

The next step is to choose a start and an end vertex for the path. This works differently depending on whether we are at the top level of the call stack or not:

* If we are at the top level of the call stack, choose an endpoint pair $(u, v)$ from $Z$ at random with probability $n\_{uv}/n\_z$; otherwise
* Let $n = \Sigma\_{(u, v) \in A \cap (V(G)\times V(G))} n\_{uv}$. Choose an endpoint pair $(u, v)$ from $Y$ at random with probability $n\_{uv}/n$.

**These probabilities ensure that paths are chosen uniformly at random**; if you want to weight paths in some other way, you are of course welcome to push these probabilities around. $u$ will be the first vertex in your random path, and $v$ will be the last. If $u = v$ then we are done: return the single-vertex path $u$.

Otherwise, construct a subproblem to recurse on: this is the induced subgraph $G'$ of $G$ whose vertex set is the intersection of $X$ and $Y$, where $X$ is all vertices in $G$ that are reachable from a child of $u$, and $Y$ is all vertices in $G$ that $v$ is reachable from, except for $v$ itself. Recurse on this subproblem; it will produce a (possibly empty) path $P$. Return the path $u, P, v$.

Note that whenever two vertices $u$ and $v$ still remain in $G'$, the number of paths between them $n\_{uv}$ also remains unchanged -- so it's not necessary to recalculate these for each subproblem. $X$ and $Y$ can each be found using DFS in $O(n+m)$ time, intersected in $O(n\log n)$ time (sort each list, if necessary, then use a $O(n)$ list merge) and the edges of $G$ that remain in $G'$ found in $O(m)$ time. Each recursion level shrinks the graph by at least 2 vertices, so there are at most $O(n)$ recursive calls. Thus the overall time complexity for sampling is $O(n(n + m + n\log n)) = O(n^2\log n + mn)$.
> 2 votes

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


# Question
Title: Total functional programming language without an static type checker
All papers with the subject of total functional programming make use of some kind of static type checking to ensure totality. This make sense considering hoy easily is to make a language Turing-complete. The question is: Is there any untyped/dynamically-typed formalism that ensures total functions?

**Edit**

In other words, there exist any formalism that only allows to construct total functions, with the impossibility of construction of partial functions, so there is no need of a filtering stage like a type checker or a termination analysis?

# Answer
The question is, how do you eliminate terms that run forever:

In particular, things like $(\lambda x \ldotp x\ x)(\lambda x \ldotp x\ x)$ and the Y combinator must NOT be in your language, since they can be used to construct computations that do not halt.

Static typing in things like System F eliminates these: they start with a full lambda calculus, and then filter out ill-typed terms.

But, do do this in an untyped setting, you need to eliminate these terms *by construction*. They cannot be expressible in your language.

I can think of some silly ways to do this, like the language of imperative programs with no functions or and only loops over lists. But in general, as soon as you have higher order functions, these problematic constructs are constructible. So while I won't say that it's impossible, it's probably very difficult to do in a way that makes much sense.

It's possible for you to statically filter out these things with something that isn't a type system, with termination checkers, but these will always throw false positives, and while they aren't static typing, they are still very much a static filter on your programs.

Note that, depending on what you consider "dynamically typed," you could eliminate programs like this by keeping track of types using inference, but only throwing errors at runtime. Thus something like the Y combinator is still rejected, just later. This is dynamically typed, but probably not what you are looking for.
> 10 votes

# Answer
Absolutely! There's even an existing implementation! I wrote this `loop.py` program in python:

```
while True:
    print "Hello world!"
    print "20 GOTO 10"

```

And ran it like this: `timeout 10 python loop.py`. Tadaa!

More to the point, what do you consider to be "static analysis"? A programing language that only contains for-loops will always terminate. Is parsing it "static analysis"? How about a compiler that compiles a C program and runs it for 10 seconds, and returns the compiled code only if the program terminates?

In theoretical CS, we always have the option of running a program a few steps at "compile time" to see what happens. At run-time, you always have the option of making an early exit out of a program if it's taking too long. Indeed, that is what the vast majority of programs do, instead of "termination checking". There's even such a feature for javascript scripts in the browser (or the infamous "program not responding" messages).
> 5 votes

---
Tags: functional-programming
---


title: C++ : N line segment Intersection

text:
# Question
Title: C++ : N line segment Intersection
I need to find intersection of *N* line segments (given by coordinates of start and end points) which are either vertical or horizontal.So I read that *Sweep Line Algorithm* is a good way to solve this.

But I can't seem to find it's implementation in C++ anywhere on Internet. Can someone provide me it's code in C++ ?

# Answer
Depending on how long the lines are and what the likelihood of intersections is, you could also use a spatial join. I.e. you treat all all lines as rectangles, put them in a spatial index and search for each line with which other lines it overlaps. You can use a standard R-Tree or Quadtree, but I would actually suggest a PH-Tree here, for example this one, because they are very fast for window queries with small result sets (for example if you expect usually only 1 intersection). For all results, you would have to manually calculate whether the lines actually intersect or not, because overlapping rectangles is an indicator for overlap, but obviously not a guarantee.

Also 'Sweep Line' is more of a general approach of tackling a problem, a bit like 'divide and conquer'. It is not an algorithm in itself, you would have to be more specific how you would use it to solve your intersection problem.
> 0 votes

---
Tags: computational-geometry
---


# Question
Title: A special case for the subset sum problem
If we wanted to see if any disjointed subset of a set $X = \[w\_1, ..., w\_n\]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution or a simple greedy algorithm.

A simple implementation of which could be the following. Sort the set $X$ in non-decreasing order and try taking taking the values of $X\_{sorted}$ one by one only if said number is smaller than the difference of $M$ with the sum of the currently selected numbers. By the end of it we should be able to see if it is possible to form the number $M$ using a combination of that set. This will of course not work all the time.

My question is, how things would change if we knew that the numbers $w\_1, w\_2$ and so on are in fact guaranteed to be multiples of 2. Would then be another way to check if any given integer $M$ can be formed or not with a combination of those numbers?

# Answer
> 3 votes
Obviously, even numbers cannot add up to an odd $M$. Other than that, we could just set $v\_i = w\_i /2$ and $N = M/2$. Then finding a subset of $w\_1, \dots w\_n$ which adds up to $M$ would be the same as finding a subset of $v\_1, \dots, v\_n$ which adds up to $N$, where the latter is the unconstrained knapsack problem.

---
Tags: algorithms, time-complexity, knapsack-problems
---


# Question
Title: The fastest algorithm for intersection of two sorted lists?
Say that there are two sorted lists: A and B.

The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different).

What is the known to be the fastest algorithm for this functionality?

Can any one give me an idea or reference?

# Answer
Hwang and Lin's Algorithm (*A simple algorithm for merging two disjoint linearly-ordered sets* (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal sizes with (possibly) fewer comparisons. It works by calculating a stride from the ratio m/n and doing the comparison against that element in the larger list; for instance if m/n = 4 it will compare the fourth element of the larger list against the first of the other, and either eliminate all 4 elements or do a binary search within them for the correct insertion/intersection point.

It neatly covers the continuum from merging equal-sized lists with the usual algorithm to merging a list of one element into a list of n with a single binary search.
> 10 votes

# Answer
Essentially the same algorithm as you'd use to merge the two lists. In the general case, you can't possibly do better than looking at essentially every element of both lists because, if you don't look at the elements, you don't know what's in the lists, so you don't know what's in the intersection. (OK, you can stop as soon as you've run out of elements in one of the lists but, if the biggest element of both lists is the same, you'll have read everything.)
> 3 votes

---
Tags: algorithms, lists
---