# Question
Title: Information-theoretic limits for a weighing puzzle
Consider the following problem:

> You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can be in a different order). Using balance scales (the outcomes are $\>$, $=$ or $\<$) at most $k$ times, determine whether the labels are correct.

I'm not exactly interested in how to solve the problem: the original problem was for $n=6$ and $k=2$, and I know solutions. What I'm interested in is the following: when I heard the problem, I first tried to determine whether a solution even exists from the information-theoretic standpoint. I.e. is the amount of information revealed by $k$ weighings even potentially enough? I don't know how to approach it.

For example, for $n=6$ and $k=2$ there exist $2$ solutions:

> compare $1,2,3$ with $6$ and then compare $3,5$ with $1,6$
> compare $1,3$ with $5$ and then compare $1,2,5$ with $3,6$

But if we estimate the amount of information naively, then we conclude that with $2$ weighings we can only distinguish $3^k=9$ permutations, which is much less than required $6!$.

# Answer
You don't need to distinguish n! permutations. You only need to decide whether you have one particular permutation or not.

You start with a set of n! possible permutation. Then you make a measurement, and some permutations in that set are compatible with your measurement, and some are not. So you replace the set of permutations with one that is compatible with your measurement.

For sorting, your measurement is a comparison of two elements. What you need to achieve is that no matter what the outcome is, you are finally left with a set containing one permutation only. To achieve this, you will try to find a comparison that splits your set into two halves that are as close together in size as possible, in case the outcome of the comparison leaves you with the bigger set.

For your problem, you just need to decide whether the permutation (1, 2, 3, ..., n) is in the set of permutations compatible with your measurements or not. You will therefore make a measurement where one of the two possible outcomes means that (1, 2, 3, ..., n) is in your set, and as few other permutations as possible. So you want to split the set as unevenly as possible.

That's what you did. Comparing (1, 2, 3) against 6 means that only twelve permutations including the perfectly ordered one will be compatible with the result: (1, 2, 3) can be ordered in six ways, and (4, 5) can be ordered in two ways. If the comparison is not equal, then there are 708 permutations compatible with that, but that is fine since you have your answer.

Obviously each coin except one must be part of some weighing (if you leave out two coins you can't know if they are in the right order). If you had a limit like "at most four coins can be weighed" that would give you a lower bound. Since you are allowed to weigh all coins in one measurement you'd have to come up with something more clever to find a useful lower bound.
> 0 votes

# Answer
I don't think information theory is going to be useful here. From $k$ weighings, you obtain up to $k \lg 3$ bits of information. The output of the algorithm is binary: either "yes, the labels are correct" or "no they are not", which requires only a single bit to encode. Thus, a naive information-theoretic bound will say that as long as $k \lg 3 \ge 1$, you might have enough information to decide.

There is no requirement to distinguish all $n!$ permutations. There are many cases where I can tell that the labels are incorrect without knowing what are the correct labels.
> 1 votes

---
Tags: information-theory, lower-bounds
---


# Question
Title: What are the closure properties of LL(k) languages?
Suppose I have two LL languages $L\_1, L\_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by LL($k$) grammars?

* $L\_1 \cup L\_2$ (union)
* $L\_1 \circ L\_2$ (concatenation)
* $L\_1^\*$ (Kleene star)
* $L\_1 \cap R$ (intersection with a regular language)

# Answer
> 9 votes
All of these (except possibly Kleene closure) are answered (in the negative) in Rosenkrantz & Stearns, Properties of Deterministic Top-Down Grammars, 1970.

For an example of a language whose Kleene closure is non-deterministic, see this answer by Hendrik Jan.

---
Tags: formal-languages, automata, formal-grammars
---


# Question
Title: Machine Learning method maps from $\mathbb{R}$ to $\mathbb{R}^2$
I have worked with image classification and image segmentation etc.

While working with images we are either mapping from $\mathbb{R}^2\to\mathbb{R}$ or $\mathbb{R}^2\to\mathbb{R}^2$. Are there any machine leaning methods that can map from $\mathbb{R}\to\mathbb{R}^2$. For example, I have a feature vector of $3$-$5$ elements and I want to map it to $32\times32$ (approximately).

Is is possible? If it is, by which methods?

# Answer
> 0 votes
Sure. You can use a neural network with fully connected layers; or a neural network with deconvolutional layers. The latter is common in image segmentation tasks, so you may already be familiar with it.

---
Tags: machine-learning
---


title: Is Prediction the same as Compression?

text:
# Question
Title: Is Prediction the same as Compression?
Just came across this transcript that states:

> The principle is that prediction is the same thing as compression. And what that means is that whenever you have a prediction algorithm, you can also get a correspondingly good compression algorithm for data you already have, and vice versa.

Even though the article gives some examples, I would like to know some answers from this community on the question: Is Prediction the same as Compression?

# Answer
Fundamentally, yes. Prediction can be used to compress, and compression is a form of prediction. More generally, any learned pattern can be used to compress and vice versa.

This rabbit hole goes a lot deeper, for example I'd suggest A Tutorial Introduction to the Minimum Description Length Principle as a thorough introduction into trying to *learn and choose models* using compression.
> 5 votes

# Answer
Prediction is a very useful part of compression.

Given a sequence of unrelated integers, you can check how they are distributed and compress them say using Hufmann or arithmetic coding.

If the integers are related, you *predict* their values as good as you can, calculate the prediction errors, and compress the prediction errors; the errors should be smaller numbers than the original ones and therefore compress to a smaller size.
> 2 votes

---
Tags: information-theory, data-compression
---


title: Is arithmetic a context free grammar?

text:
# Question
Title: Is arithmetic a context free grammar?
Like including parenthesis (`(` and `)`), addition, subtraction, multiplication, and division, and the Order of Operations in mind.

I tried (in Lark EBNF):

```
%import common.WS
%ignore WS
%import common.SIGNED_NUMBER -> NUMBER

start: exp
?exp : add
     | mul
     | sub
     | div
     | NUMBER
     | frac
     | parenthesis
?parenthesis: "(" exp ")"
add  : exp "+" exp
sub  : exp "-" exp
mul  : (exp "*" exp) | NUMBER parenthesis
div  : exp "/" exp

```

I wonder if the Order of Operations would make arithmetic a context-free grammar.

*Originally this post*

# Answer
> 1 votes
You are confusing two or three different concepts here:

* Languages: these are collections of strings.
* Context-free grammars: this is a specific way to describe languages.
* Parsing: this is the process in which a computer "understands" input.

You haven't explained what you mean by "arithmetic"; some people think of arithmetic as the set of first-order statements about the natural numbers which are true, for example. However, it seems that by arithmetic you mean the set of well-formed arithmetic expressions (you leave out some important details, for example, what atoms are allowed, whether whitespace is allowed, and so on). Assuming this, arithmetic is most certainly *not* a context-free grammar, simply because arithmetic is a *language*, not a *grammar*. However, it can be described as a context-free grammar, as you demonstrate.

The next thing you are worried about is parsing ("order of operations"). Grammars describe languages, that is, sets of strings; parsing is a separate issue. It is true that context-free grammars are intimately related to parsing, via parse trees. It is possible to construct a context-free grammar for the language of arithmetic expressions that reflects "order of operations", in the sense that we can use the parse tree directly to evaluate the expressions in a recursive way (in the fashion of attribute grammars.

For example, suppose that the only atom is $n$, and that we are only interested in addition and multiplication, and allow parentheses; and furthermore, multiplication has higher priority than addition, and both associate to the left. This is reflected in the following grammar:

\begin{align} &\mathit{EXPR} \to \mathit{EXPR} + \mathit{TERM} \mid \mathit{TERM} \\ &\mathit{TERM} \to \mathit{TERM} * \mathit{FACTOR} \mid \mathit{FACTOR} \\ &\mathit{FACTOR} \to (\mathit{EXPR}) \mid n \end{align}

You can check that $n+n+n$ is "understood" as $\[n+n\]+n$, and $a+b\*c$ is understood as $a+\[b\*c\]$, for example. Moreover, this grammar is unambiguous (unless I made a mistake), that is, any word in the language has a unique parse tree.

In practice, starting with an ambiguous context-free grammar and precedence rules (including associativity), parser generators can create equivalent unambiguous context-free grammars (or more accurately, parsing algorithms).

---
Tags: context-free, arithmetic
---


# Question
Title: Why are $L$-reductions defined the way they are?
I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the definition.

Recall that a problem $A$ is $L$-reducible to another problem $B$ if there exist polynomial-time computable functions $f$ and $g$, and positive constants $\alpha$ and $\beta$ such that:

1. If $x$ is an instance of problem $A$, then $f(x)$ is an instance of problem $B$.
2. If $y'$ is a solution to the instance $f(x)$ of problem $B$, then $g(y')$ is a solution to the instance $x$ of problem $A$.
3. $OPT\_B(f(x)) \leq \alpha OPT\_A(x)$.
4. $|c\_A(g(y'))-OPT\_A(x)| \leq \beta |c\_B(y')-OPT\_B(f(x))|$.

where $c\_A$ and $c\_B$ are the cost functions for the problems $A$ and $B$, and $OPT\_A$ and $OPT\_B$ have their usual meanings.

Points 1, 2, and 4 seem completely natural to me. We want some way to map instances of $A$ to instances of $B$ in polynomial time. $f$ takes care of that. Additionally, we want some way (again in polynomial time) to map solutions to instances of $B$ to solutions to instances of $A$. $g$ takes care of that. Finally, we want the mapped solutions to preserve some notion of "quality" so that we can make statements like "if $y'$ is a "good" solution, then $g(y')$ is not "too bad" of a solution". Point 4 takes care of that. But what do we need point 3 for? It seems to me that points 1, 2 and 4 suffice for the definition of a "natural" approximation-preserving reduction.

I know that for $L$-reducibility to imply $PTAS$-reducibility, we need point 3. But is that the only reason for adding point 3 to the definition?

# Answer
L-reductions were defined by Papadimitriou and Yannakakis in their paper Optimization, approximation, and complexity classes. From the abstract:

> Furthermore, we show that a number of common optimization problems are complete for MAXSNP under a kind of careful transformation (called L-reduction) that preserves approximability.

A survey of various related notions of reducibility is Ausiello and Paschos, Approximability preserving reduction. Each of the notions of reductions appearing there was invented to serve some purpose. Definitions are typically not arbitrary. They are supposed to model some intuitive notion. Some definitions are more successful than others. When unsure about a definition, it's always a good idea to check out the original paper(s) introducing the definition.
> 2 votes

---
Tags: reductions, approximation, definitions
---


title: Proving of regular language

text:
# Question
Title: Proving of regular language
# Is this regular or not

L = {w1w^R | w ∈ {0,1}\* (where for any word w ∈ {0,1})\*, w^R denotes the reverse of w)

# Answer
> 0 votes
L is not a regular language.

We can contradict by pumping lemma for regular languages.

Let assume L is regular, so there exists an integer $ k $ of pummping lemma.

$ w = a^kb $

$ w^R = ba^k $

$ ww^R = a^kbba^k \in L $

$ w' = a^{k-r}bba^k \notin L , r\>0 $

Contradiction to $ w' \in L $.

---
Tags: automata, regular-languages, regular-expressions
---


# Question
Title: Minimum-average-cost subtree that is not necessarily spanning
I'm looking for an efficient algorithm for the following problem:

Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root).

Output: a subtree from the root that has the minimum average cost per edge.

There are some results for minimum average-cost spanning trees, but in this case the output is not necessarily spanning.

In the tree below, where A is the root of the tree:

1. The subgraph containing nodes A and B has average cost `mean(6) = 6`
2. We can improve on the average cost by including node C to get `mean(6, 5) = 5.5`.
3. The optimal subgraph includes nodes A, B, D and E, but not C, to get `mean(6, 7, 1) = 4.67`

A greedy algorithm would be a depth-first search that appends edges that lower the mean. But such an algorithm would miss the optimal subgraph, because it wouldn't append the edge to node D with cost 7.

# Answer
It turns out that there's a linear time algorithm, published in Carlson J., Eppstein D. (2006) The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems. In: Arge L., Freivalds R. (eds) Algorithm Theory – SWAT 2006. SWAT 2006. Lecture Notes in Computer Science, vol 4059. Springer, Berlin, Heidelberg.

The paper is paywalled, so I have implemented it in R package called wmms.

Here is a summary of the steps:

1. Guess what the maximum average profit is by using the median.
2. Depth-first (start at some leaves and work in) add the profit and cost of each leaf to its parent, unless profit/cost is lower than the guessed maximum, in which case skip it.

* For non-leaf nodes, use the (sum profit)/(sum cost) of leaves added (aka merged) to it.

The insight behind (1) and (2) is that, if the guess (the median) is correct, then the (sum profit) / (sum cost) will be the maximum.

* Because leaf nodes with lower-than-maximum profit should always be cut.
* And because parent nodes with lower-than-maximum profit should only be kept when their average over the subtree beneath them brings them to/above the maximum.

After this first pass, whatever (sum profit) / (sum cost) is at the root node is now a lower bound on the maximum. And if (sum profit) / (sum cost) is less than the guessed maximum, then the guessed maximum is an upper bound, otherwise the upper bound is Inf, because, as above, if the guessed maximum were correct, then (sum profit) / (sum cost) would have met it.

Before repeating (2) we can prune the tree in a few safe ways.

3. Prune any leaf nodes (or nodes that become leaves by the time they are traversed) whose profit/cost is less than the lower bound that we just defined.
4. Any node (not only leaves) with personal profit/cost (not including remaining child nodes) above the upper bound can be merged with its parent. When merging a non-leaf node with its parent, the non-leaf node's children become direct children of the non-leaf node's parent.

These work because we now know that these nodes are either definitely not in the optimum tree, or definitely are.

The other thing we can do is:

5. Any non-leaf node with profit/cost below the lower bound, and that only has one child, merge the child into it. Because the child has a profit/cost between the bounds, so we don't know yet know if we can drop it, but if we do eventually drop it, we'll definitely drop its parent too. So they might as well be combined. If they aren't eventually dropped, it's because their (sum profit)/(sum cost) meets/exceeds the maximum. We can only do this with only-children, because for siblings, we would need to know the effect of pruning each one without the other.

Now we are ready to repeat (2) to (4).

Eventually, only the root node will remain. Its (sum profit) / (sum cost) will be the maximum.
> 1 votes

# Answer
Tried to add this to the comments thread but stack overflow won't let me (new account)

@j\_random\_hacker I was thinking along similar lines to DP (a recursive algorithm that ran through the subtrees out to the leaves) but I hit a problem - I don't think the problem has an optimal substructure.

If you consider the graph in the image below, if x=1 then the 30-weight-edge is not part of the optimal solution (100,1,1,1) whereas if x=40 then it is (100,1,1,30). Inclusion of a specific edge in the optimal solution depends upon the weight of edges in completely separate parts of the graph.

I'd actually started writing some code before I realised. My recursive function assumed that given a subtree & the path from root to subtree you could make a decision but this counterexample broke it :(
> 1 votes

# Answer
## An exact but somewhat complicated $O(n\log n)$ algorithm

This problem intrigued me, and the solution I've come up with uses a strategy that's totally new to me (I doubt it's new to the world -- if anyone knows of other problems that can be solved "this way", let me know!). This algorithm allows negative and/or fractional edge costs, and operates directly on trees that may be non-binary. To get the time complexity down to $O(n\log n)$ requires making use of a property of averages, as well as a way to efficiently add "blocks" of edges at a time.

Let the input tree be $T$, and the parent of a vertex $v$ be $p(v)$. I will call a subtree of $T$ rooted at some node $v$ and including the edge $p(v)v$ a *branch*, and say that it is *headed by $p(v)v$*. (Note that a branch headed by $uv$ need not include all descendants of $v$.) Denote by $A(G)$ the average of all edges in the graph $G$.

## Combining averages

**Lemma 1:** The average of the union of two multisets is between the original two averages.

**Proof:** Suppose multiset 1 has $b$ items, which sum to $a$, and multiset 2 has $d$ items, which sum to $c$. Then the average of multiset 1 is $a/b$, the average of multiset 2 is $c/d$, and the average of their union is $(a+c)/(b+d)$. We want to show that the last expression is between the first two.

Suppose w.l.o.g. that $a/b \le c/d$. Then:

$$ a/b \le c/d\\ ad \le bc\\ ad+ab \le bc+ab\\ a(b+d) \le b(a+c)\\ a/b \le (a+c)/(b+d) $$

Similar reasoning shows that $(a+c)/(b+d) \le c/d$.

---

The utility of this is that it allows us to be certain that adding a multiset to another multiset with a higher average "pulls down" the latter multiset's average, *without having to know anything about the items in either multiset or even their sizes*.

## Stragegy: Greedy, but not using the raw edge costs

The key to enabling a correct greedy algorithm is the following lemma. The statement is rather convoluted, but in essence it means, "Whenever an optimal solution includes some branch, it must also include every branch with a lower average that could have been added to it at some point".

**Lemma 2:** Suppose there is an optimal solution $OPT$ that contains an edge $uv$. Call the branch in $OPT$ headed by $uv$ $b\_{uv}$. Then this optimal solution must also include every edge $xy$ such that $x$ is in $OPT$, is not within the subtree of $T$ rooted at $v$, and there exists a branch $b\_{xy}$ in $T$ headed by $xy$ with lower average, i.e., such that $A(b\_{xy}) \< A(b\_{uv})$.

**Proof:** Suppose (towards contradiction) that an optimal solution $OPT$ does exist that contains some edge $uv$ heading a branch $b\_{uv}$, but does not contain some edge $xy$ for which there exists a branch $b\_{xy}$ in $T$ such that $A(b\_{xy}) \< A(b\_{uv})$.

Let $r$ be what is left of $OPT$ if we remove $b\_{uv}$. It must be that $A(r) \ge A(b\_{uv})$, since otherwise we could remove $b\_{uv}$, and by Lemma 1 obtain a new solution with strictly lower average, contradicting the optimality of $OPT$. Thus, again by Lemma 1, $A(OPT) = A(r \cup b\_{uv}) \ge A(b\_{uv})$.

$A(b\_{xy}) \< A(b\_{uv})$ by assumption, and the preceding sentence establishes $A(b\_{uv}) \le A(OPT)$, so combining these we have $A(b\_{xy}) \< A(OPT)$. So by Lemma 1 again, we get that $A(OPT \cup b\_{xy}) \< A(OPT)$, contradicting the optimality of $OPT$. Thus $xy$ must also be part of this solution.

---

What this means is that we never need to consider adding an edge to the solution until we have already added every edge that leads to a lower-average branch. IOW, at each step as we are building the solution tree, from among the "frontier" of edges that are adjacent to vertices already in the solution, the only edge we need to consider adding is the one that leads to the subtree having the *minimum* average. This also makes the stopping criterion clear: Stop as soon as the minimum-attainable-average rises above the average of the solution we have built so far. (Once the minimum is too high to be useful, every other edge surely is too.)

## Computing the minimum averages efficiently with "blocks"

So what we need is a way to efficiently compute, for each edge $uv$ in $T$, the minimum average of any branch in $T$ that is headed by $uv$. Once we have these, we can repeatedly pick the lowest-minimum-average edge from a heap, add it to the current solution, and then add all of its child-edges to the heap, continuing until the lowest minimum-average edge exceeds the current solution average.

This is starting to look like a nicer problem: These minimum-average values depend only on the tree *below* the edge under consideration, suggesting a bottom-up computation might work. It does, but we need to be careful to avoid the time complexity blowing back up to $O(n^2)$.

The straightforward approach would be: For each edge $uv$ in a postorder traversal, create a new solution containing just that edge, add all of the (already-computed) minimum averages of its child edges to a heap, choose the lowest, add it to the solution and add its own child edges to the heap, and repeat until the stopping criterion is met. This is a correct algorithm, but the problem is that it may be necessary to add $O(n)$ edges separately for each starting edge $uv$, leading to $O(n^2)$ time overall. For example this is true of any tree in which every edge costs less than its parent, since in this case the optimal solution for each starting edge $uv$ winds up including *every* edge in the subtree below it, each of which are added separately.

Instead, once we have discovered all the edges of an optimal branch headed by $uv$, we can **collapse all of $v$'s descendants in this branch into $v$**, which acquires as children all children of those original vertices. $v$ now represents a solid subtree "block" that is never split apart by later algorithm steps, and which can be added in a single step. (The original subtree structure can be stowed away inside $v$ to enable the top-level solution subtree to be recursively "exploded" back out once the algorithm is finished.)

## Exotic heaps to the rescue

An edge is only ever collapsed at most once throughout the course of the whole algorithm, and collapsing an edge can be done in $O(1)$ time, so there are no efficiency concerns there. But there remains the issue of uncollapsed child edges: These may need to be considered for addition into the solution multiple times, potentially once per ancestor. Or do they? The only way we "consider" these edges is by selecting the one having minimum average value among all frontier edges, and a heap can do this in $O(\log n)$ time. So the only remaining issue is ensuring that, when we select an edge to add to the solution and want to add all of its child edges to the heap, this can be done efficiently. This is a *heap meld* operation, and while it can't be done efficiently by the "standard" binary heap, other heap data structures can accomplish this in as little as $O(1)$ amortised time!
> 1 votes

---
Tags: algorithms, trees, minimum-spanning-tree
---


# Question
Title: How to convert regular expression to CFG?
How can I convert the regular expression (ab\*)\*b to a context-free grammar?

When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of writing it?

# Answer
There is a simple algorithm to convert regular expressions to context-free grammars. It goes as follows.

Base cases:

* $\emptyset$ corresponds to the empty grammar.
* $\epsilon$ corresponds to the grammar $S \to \epsilon$.
* $\sigma$ (where $\sigma \in \Sigma$) corresponds to the grammar $S \to \sigma$.

Inductive cases:

* $r = r\_1 + r\_2$. Given CFGs for $r\_1,r\_2$ with disjoint nonterminals and starting symbols $S\_1,S\_2$, add rules $S \to S\_1 \mid S\_2$ and make $S$ the new starting symbols.
* $r = r\_1r\_2$. Same, adding the rule $S \to S\_1 S\_2$ instead.
* $r = r\_1{}^\*$. Same, adding the rules $S \to S S\_1 \mid \epsilon$ instead.
> 3 votes

---
Tags: computability, context-free
---


# Question
Title: Criteria for selecting language for first programming course
As a university-level CS educator, the issue of which programming language to teach in the first programming course often comes up for discussion. There are thousands of languages to choose between, and lots of religious fever (or fevour) supporting one language camp over another. All of this subjective bias surrounding each programming language makes it very difficult for an educator to choose one.

My question is:

> What **objective** criteria can an educator use to select a programming language to use as the basis for a first year university programming course? What is the basis for these criteria?

**Note**: I do not want to see a list of programming languages and why they are the best one to use. The question isn't about the best language, it is about *the criteria for selecting a language*. Answers may however be use programming languages to illustrate particular points.

---

This question was inspired by another question which was deemed off-topic: https://cs.stackexchange.com/questions/1946/criteria-for-choosing-a-first-programming-language.

# Answer
I'll throw in my own two cents although I believe this subject is a bottomless pit. Don't get me wrong, I think it's a fascinating question, but probably not one we will solve here to everybody's satisfaction.

In a nutshell, I'd say that the language should do *what you want it to do*, in a *simple* and *unambiguous* a way as possible, and *not more*.

My own experience comes from tutoring several generations of first and second year students with the Oberon programming language. People who know this language will recognize its influence in my opinions. Note that this language was used to teach "Algorithms and Data Structures". At the time (back then), functional programming and object-oriented design were taught in separate courses as of second year.

**Important**: Before going into the specifics of any language, however, I would like to emphasize that the most important thing is to be absolutely clear, to yourself and to your students, about what the goals of your course are. Are you teaching programming *per se*? Or algorithms and data structures? Or software engineering? Before choosing a language, it's worth it to think a moment about where you're going with it. Differences at this level (goals) is what probably, in my opinion, leads to most disagreements on this topic.

The points I consider important may overlap with several things that have already been said, but I believe most end up being subsets of one of the following four:

* **Simplicity**: The students are usually there to be taught programming, algorithms and data structures, and not the features and intricacies of any specific programming language. Wirth used the Einstein quote "Make it as simple as possible, but not simpler" as a guiding principle in the design of Oberon, and there are several other languages out there that do it just as well. Your programming language of choice should be able to implement all the concepts required in your lecture, but should do this with the smallest possible set of features/details. The programming language is usually just the tool, not the goal.
* **Unambiguity**: A close sibling of simplicity, there should be one construct for each concept, with as little overlap as possible. Think of it as there being only one "right" way of implementing every concept. Three different types of loops that semantically all do the same thing? Or fifteen different ways to increment a variable? Not good. This also makes correcting homework or generally just understanding your students' code a *lot* easier. Your teaching assistants will appreciate it.
* **Portability**: Students will go to class with Linux, Windows and OSX machines, and the programming environment should be as similar (identical) as possible under all three. The results of any program should also be identical. This is another point that the teaching assistants, responsible for marking homework and dealing with questions/problems, will greatly appreciate.
* **Industry preference**: Seriously, we should start worrying about this only if "Industry" itself ever decides what programming language it likes best. Since the invention of computers this has been a constantly-moving target. For the moment, if your students *really* learn how to program, then it won't be language-dependent. There are, however, some areas where industry manages to agree on a standard, e.g. VHDL for circuit design or SQL for database queries, so this is still a valid point.

Again, how a language fits this list is strongly dependent on what it is you're trying to teach!
> 15 votes

# Answer
* **Developing algorithmic thinking to solve problems as the main goal:** One bad thing about using an object-oriented paradigm in the first course is, that getting new learners into things like inheritance, polymorphism, etc, distracts them from the above-mentioned main goal. In fact, introduction of any secondary considerations beside this core goal, like software engineering, portability, industry usefulness etc, are counter-productive, for the reason stated.
* **Not an Object-Oriented Language:** Nowadays, most universities start teaching programming right with an object-oriented language. I think this is a mistake. There are things in the world that can be truly understood only in contrast to its opposite. Without being exposed to a procedural paradigm of programming (data and functions as two separate aspects of program), the basic idea of object-orientation (data and behavior viewed as ***intrinsically*** tied together) can be missed by many. And because, object-oriented programming is so important, missing its basic idea is not a small thing. Besides, since most probably in more senior courses CS students will program mainly in OO, they need to be exposed to the procedural side of things as well.

So, at the end, I would go for a procedural language, avoiding advanced features, focusing on developing algorithmic thinking. But, by avoiding advanced features I don't mean avoiding challenging problems. I mean, that even challenging problems, students should be required to solve it using first principles, simple tools.
> 13 votes

# Answer
Since we are talking about the first programming course in a Computer Science programme, I'd say the most important aspect would be what fundamental concepts of CS it will teach your students. Since there is no language that can teach all concepts at once, you need to consider what concepts will be needed further on.

I don't agree with @Kaveh's notion that industry relevance is important; it may be a bonus, but it is of minor importance here. With a solid foundation in CS principles, learning an "industrial" language in later courses will be relatively easy.

As a side note, regardless of the language chosen to be the first, it is important to subject your students to another, radically different, language as soon as possible.
> 11 votes

# Answer
As an introductory remark, consider the possibility of presenting more than one language (in one course). In my first term we where shown both SML and Java. The contrast had its very own and important message: choose the right tool for the job.

But now for criteria, in arbitrary order.

**Difficulty** to learn is a subjective issue, but important: you don't want your student to waste time on learning the language, but on *doing* things with it. Arguably, dynamic languages like Ruby may win on this front: you can feed them anything, and there are excellent "dummy" tutorials on the web. If I remember correctly, there are also studies that show that students who have not programmed before achieve better results with functional languages than with others.

**Richness**: the language(s) must be rich enough for all the concepts you want to teach. For example, if you want to discuss higher-order functions, you need a language where functions are values, such as functional languages or Scala.

**Scalability**: Chances are your students won't learn more languages on their own than those you show them. So you want your chosen language(s) to scale over the course of their studies: they need to write your pet exercises now, but may also attack a middle-sized project later. Java and languages with similar ecosphere are good choices here.

**Tool support**: This is related to scalability. If you expect/want your students to be productive with the language, then good IDEs, build managers and libraries have to exist. Interactive shells (Ruby, Scala) are also nice thing, especially for starters. Tools have to work on all major platforms, too.

**Documentation**: You probably don't want to actually *teach* the language but have students teach themselves with your (abstract) guidance. Therefore, good documentation is important. Arguable, the more popular and established a language is, the better the documentation. For example, Scala's documentation is quite poor (but improving). Tools like Hoogle are a plus.

**Availability**: There are actually people who teach using Matlab or Visual C++. Consider that not everybody might have a license or a machine that can run the necessary programs. You should probably favor free languages that run on a variety of platforms.

**Cleanness**: You probably want to shape the way your students think. The messier the language, the messier they will think; I would never propose PHP in a course. Dynamic languages in general have disadvantages here: they allow, sometimes even promote, bad habits.

Which criteria are more important for you than others also depends on *what* you want to teach. Is this literally a programming course? Is it an algorithms and data structures course? Is it a course that introduces concepts of programming languages in different paradigms? Is it a course about software development in the big?
> 10 votes

# Answer
When choosing a first programming language, there are many issues that need to be considered. Many of these have been considered in the answers above. I include 3 more as these were a part of my answer to the closed question ( https://cs.stackexchange.com/questions/1946/criteria-for-choosing-a-first-programming-language ) that originally inspired this question. I've copied my answer here (and modified it) based on the current policy of deleting closed questions.

Here are 3 points to consider, using a few programming languages as examples.

## Programming in the large vs programming in the small

When first learning to program, one needs to learn how to *program in the small*, before moving on to learn mechanisms to help *programming in the large*.

By programming in the small, I mean writing programs with fewer than 100 lines. These programs will involve algorithms that manipulate simple data structures, have simple control flow, and will solve simple problems. They will in general not be considered as *applications*.

By programming in the large, I mean writing large programs built from many components/classes, building on top of an API, with a GUI, a database, possibly in a client-server configuration.

The things a programmer needs to think about when programming in the small are very different from when programming in the large. Programming in the large requires the programmer to think about modularity, good interfaces, good design, reusability, and many other issues. Modern programming languages provide many constructs to help program in the large. These constructs include classes, modules, interfaces, information hiding, etc. When programming in the small, these issues are much less important.

A programming language such as C++ has many features to help programming in the large, but it is more difficult to sit down and start writing a very simple program. Java is similar.

On the other hand, a language like Python, Ruby, Scheme or Haskell makes it much easier to directly write a program.

## High-level vs low-level

Languages like C++ and C are rather lower-level language. They enable the programmer to manipulate references into memory directly. Although, this allows one to write very efficient code, the low level details can be difficult for a first programmer to learn the language. Some would argue that these low level details get in the way of writing the logic to solve the problem.

A higher-level language like Python makes it easier to express concepts more directly in terms of the problem domain.

## Staticallly Typed vs Dynamically Typed

C++, Haskell, Java and many more languages are statically typed. This means that the compiler automatically finds places where potential errors occur based on the expected types of values at each location in the code. There is a bit of a religious war about whether static typing is a good thing or not, but I will steer clear of that one. One problem with static typing for new programmers is that the error messages reported by the compiler are often difficult to understand. This is especially the case with C++ templates and Haskell programs in general.

Python, Ruby and Scheme are dynamically typed. This means that errors are detected while the program is running. One can argue that this is too late to detect the errors (but one can also use testing to avoid such errors). Again, avoiding the religious argument, the advantage of the kind of errors that one encounters when writing simple programs in a dynamically typed programming language are of the sort *this object does not know how to do this operation*. In the context of a small program, these errors are easy to understand and track down.

Languages like C have weak typing, meaning that although the compiler helps out with some errors, the run-time fails to trap others that occur, such as invalid memory accesses. As a result, the error message returned to the programmer is akin to "Program crashed". A dynamically typed language would trap these errors and convert them into a more comprehensible error message.

## Others

For other languages different considerations may come into play, such as the support provided by the programming environment, the available APIs, quality of books and online tutorials, etc.
> 9 votes

# Answer
My main concern is *universality*, in the sense that learning *this* programming language should make the student able to handle most programming languages.

As much as I regret it, this criterion excludes pure functional languages. It also applies to the course that should not use exotic features of the language.

... but this is only common sense.
> 8 votes

# Answer
Fascinating question; I like your emphasis on objective criteria. We want freshmen to learn:

**programming concepts**: The first programming language must support: function calls, iteration, recursion

**fundamental ideas**: The first programming language must support arrays (for the first steps in a gentle introduction to how how memory really works and how pointers work)

**practical programming skills**: how to use the debugger, how to use the profiler, how to solve large problems (a high level language), how to put together large systems, how to break down problems (decomposition of problems), how to avoid writing complicated code, how to communicate *to humans* the intent behind an (often cryptic) series of executable statements.

the fact that pre-written libraries exist for things like sort(), and how to use them -- i.e., the fact that it's not necessary to write everything from scratch.

**Other criteria for a first language**:

interpreted (quick feedback helps the learning process).

an interactive environment which speeds learning, testing, and debugging.

high-quality source code is available for students to read in that language

"easy to read", "syntax that approaches natural language" (to make it easier to read and grade the SourceCode)

portable (runs on Mac OS, Windows, Unix). At least one free software implementation of the language.

fast to teach, "few gotchas" -- for example, "\[I\]t may be faster to first teach beginners Python and then Java, rather than Java as a first OOPL." -- "Comparison of Object-Oriented Progamming Languages" and TelescopeRule

Matthias Felleisen developed a programming language with error messages tailored to a beginner audience. He emphasizes that the particular language choice is not as important as teaching a good design methodology. In fact, he sees the first CS course as a Liberal Arts class, teaching critical thinking, problem solving, and attention to detail.

**criteria for a second programming language**

Stuff we want students to learn, but perhaps this can wait for the second programming language:

a "relevant" language that is "not too esoteric"; something "popular in the industry"

Complexity theory: how to recognize tasks that are impossible with current technology.

higher-level stuff: how to pick the right tool for the job, how to use a compiler, structures, object-oriented programming, functional programming, logic programming, compiler design, composing and manipulating functions (in the Lisp/ML sense), concurrent and distributed programming,

low-level stuff: pointer arithmetic, computer architecture. memory management, stack frames, assembly programming, machine architecture, device drivers and operating system design (so the machine won't "seem like some frightening black box they can't penetrate")

EDIT: I find it disappointing that posting a summary of something that I wrote, in collaboration with many others, "may not be a legal post".

So I'm adding a more formal citation to my previous informal link, attempting to comply with fair use and other wiki copyright issues.

This answer is a summary of Freshman's First Language (Anon 2011) at the Portland Pattern Repository.

(Anon 2011) Many anonymous and various other authors. "Freshmans First Language". Portland Pattern Repository. September 27, 2011. http://c2.com/cgi/wiki?FreshmansFirstLanguage.
> 6 votes

# Answer
I think simplicity and ease of learning is one of the main criteria. In an introductory course on programming we would like to avoid unnecessary programming hurdles and focus as much as possible on the principles of programming and algorithmic problem solving. The first year students often lack the ability to think algorithmicly about problems so the course is also about teaching algorithmic thinking.

Another criteria is usefulness of the language in the industry. We would not want to teach a language that is of no use in the industry. A clear majority of the students are going to work in the industry so one should have an eye towards what is being used (and will be used when students graduate) in the industry.

The third criteria would be the courses the students are going to take in later years. The courses, particularly the required courses, are not designed on themselves but in coordination with other courses.

The last one I can think of right now is the same as jmad's answer, the language should provide ease in learning other important languages. It should be rich enough and picking up the later important languages would be easy (here, important means important from the perspective of the students).

I think many universities have shifted their main introduction to programming course from Java/C++/C to Python although they might provide introduction to programming in other languages from time to time (often for non-computer science majors, e.g. C for electrical engineering majors) though they may show flexibility if the instructor wants to experiment with teaching another language once in a while.
> 5 votes

# Answer
So, I'll dispense with my knee-jerk reaction immediately, which is that everyone should learn programming via SICP because Lisp is the Right Thing.

There have been many good criteria offered already for selecting a language... **simplicity** and **portability** being among the most important. However, I also think it's vital for students new to programming not to get the wrong idea (or have no idea) about what's happening behind the scenes with modern languages.

Although some of these other posts have offered excellent criteria, I'd like to use a particular language to illustrate what 'meeting the criteria' looks like.

Some of these concerns have been addressed (far better than I could attempt to) in Joel Spolsky's blog post, The Perils of JavaSchools. Choosing languages like Java or Python closes over two of the harder (and most vital) concepts in CS; namely, pointers and recursion.

Of course, teaching an intro course in C is going to be incredibly dense, while also likely missing many important concepts related to recursion. Likewise, a course taught in Lisp will have to address pointers under the covers, as `car` and `cdr` imply important concepts related to linked-lists, while letting the language handle the details.

Basically, what I'm getting at, is that students need to understand the fundamentals of data structures and algorithms, as well as practical implementation.

I also disagree with the suggestion **not** to use an object-oriented language. I think the utility of object-oriented languages to modeling the real world is a positive asset to new programmers, as long as the impedance mismatch is made clear, and that object-oriented languages are one paradigm among many.

I would propose that Ruby (suggested as a possibility by another post as well) exemplifies many qualities to look for in a language to use for an intro to programming course.

I'll justify this assertion momentarily, but first I want to comment on one trend that disturbs me in intro CS courses. I work at a university which, like many schools, has recently switched to using Python for its intro courses. I firmly believe that Python is the new BASIC, and the tendency of the language is to choose newb-friendliness over power and expressiveness, as I recently argued elsewhere. This is a disservice, and we need to think about the programmers they will become, not the newbs they are at the moment.

Anyhow, justifying Ruby as an introductory language...

* Ruby, although not tail-call optimized, does recursion rather well. So there's that.
* Ruby is multi-paradigm. Although it is a pure object-oriented language, it also embraces functional programming, as well as having some imperative, C-derived training wheels tacked on. Compare this to Python, which is a procedural language with some tacked-on OO (although the bolts are showing), and some functional elements (which Python's BDFL has repeatedly tried to excise).
* CRuby (aka MRI or 'Ruby Classic') is written, and extended, in C. You can teach students about pointers, memory management, and the dread god `malloc()` by teaching them to extend the language in C.
* Even thought it's a high-level, dynamic language, you can teach a lot about data structures, types, etc.; there are libraries (gems) for anything you could imagine, from red-black trees to doing odd things with duck-typing.

Anyhow, there's no substitute for learning many languages, from many paradigms, whether you use them professionally or not. Basically, I think everyone should *understand*, if not *use*, C and Lisp. Ruby is the best compromise I can think of for an introductory semester.

Anyhow... that's my US$.02. I'm not trying to convince you to use Ruby, mind you... just using it as an exemplar of qualities to look for in a language for teaching an intro course.
> 5 votes

# Answer
My first programming language was a toy assembly language. The second was Fortran. In between, I was taught an "algorithms" notation, which was roughly Algol 60. I turned out quite ok. In fact, I think what I was taught was pretty much perfect.

When I first looked at functional programming, in research papers though not in an implemented language, I went "wow, this is completely different. It is quite mathematical!" Most people that get taught functional programming still have the same kind of "wow" experience. I think that is great.

I think imperative programming and functional programming are two completely different ways of looking at the world. We would disservice to our students if we rob them of that diverse experience.

The best first programming language should be something that is as simple as possible and as clear as possible, so that the students are able to focus on how to think clearly. Unfortunately, the simplicity and clarity of assembly, Fortran and Algol 60 are unmatched by most modern day programming languages. Haskell is a good exception. But, Haskell would make my ideal second programming language, not the first. Eiffel or Oberon could perhaps fit the bill.
> 5 votes

# Answer
At The North Carolina School of Science and Mathematics, we have introduced students to Python since 2004. We use it to teach procedural programming, because we think that the ability to write short, correct procedures is vital to progressing later with heavier tools, including OO programming.

We like it for these reasons.

1. Python is not a free-format language. It forces the students to write their code in blocks using indentation. (As a technical note, we use the vim text editor and put \[`set tabstop=4 set et`\] in the .vimrc to eliminate annoying problems and for code indentation to be noticeable but not to cause ugly excessive horizontal drift). Our students get used to seeing the hierarchical structure of programs delimited by whitespace. As a result, their formatting habits tend to be very good as they program in other languages.
2. Python's syntactical simplcity makes it beginner-friendly. Simple programs can be written with a minimum of arcane keywords and magical incantations. We want student who wouldn't ordinarily think of programming to try it. Note the lovely simplicity of Python's `hello.py`; it is crystal-clear what is happening.
3. Python is dynamically typed and duck typed. This makes introducing variables easy. I tell my students that variables are just labels. They point at objects. You send a message to an object using the variable name, much as someone sends a message to you by calling you on the phone.
4. Python is a tool that ambitious students won't outgrow. It has sophisticated libraries that do hosts of useful stuff. It is a powerful creative tool that is accessible to beginners.
5. Python is free and runs on all major platforms. Our school is a heterogeneous OS environment with all sorts of machines. We do not have to worry about headaches such as compatibility issues. It will run on just about any computer.
6. Python has excellent documentation. We encourage our students to explore, tinker, and color outside of the lines. They learn about using Python documentation early and often wind up exploring cool stuff outside of class.

We have been very pleased with Python.
> 5 votes

# Answer
I would say, that the language (under some limitations) does not matter as much, as what you do with the language. You can learn about the same about software development, algorithms, object oriented programming, computer hardware and so forth in most languages. The key is, to develop something interesting, which utilizes all of these concepts.

(migrated answer from https://cs.stackexchange.com/questions/1946/criteria-for-choosing-a-first-programming-language/)
> 3 votes

# Answer
***TL;DR:*** There's no way to *objectively* answer this because there's no *objective* basis for the criteria behind it. It's as arbitrary as trying to debate if blue is, *objectively*, a "better" color than red, or if vanilla ice cream is *objectively* "tastier" than chocolate.

---

I think there're some wonderful posts already present, but I'll add my own 2 cents.

> What **objective** criteria can an educator use to select a programming language to use as the basis for a first year university programming course?

This question is akin to asking if there's a way to *objectively* choose the first ice cream flavor someone else should try when visiting an ice cream place for the first time. No, there is no *objective* way to choose something that's inherently *subjective*.

Why? Because even when we look at the reasonable criteria mentioned in Pedro's answer, everyone will still have a *subjective* view of how each factor "holds up" against the views of someone else.

For example, is Ruby *objectively* "simpler" than Python? Simpler in what sense? With respect to what? What does "simpler" mean for *you*? Does it mean "fewer lines of code"? Does it mean "easier to read and understand"? What about others? Why should anyone agree with any particular selection here? I don't think we can answer that question *objectively*.

This leads to the next question.

> What is the basis for these criteria?

As reasonable as some criteria might be, I think this is more grounded on *subjective* preference than anything else. For example, there's no reason why I should just accept Pedro's criteria of *simplicity*, *unambiguity*, *portability* and *industry preference* -regardless of how reasonable some might think it to be. In fact, industry *preference* is subjective by definition and would simply lead to a vicious circle. (Everyone gets trained in it, so everyone uses it in industry, which is why everyone gets trained in it, ...)

For example, why not

* **Efficiency:** Execution times and memory footprint can actually be measured.
* **Size:** The fewest number of reserved words possible would make the language easier to learn.
* **Feature Set:** A wider set of supported features (e.g. lambdas, generics, object-orientation, operator overloading, etc.) would allow you to teach more concepts without having to switch languages and go back to square one.
* **Interoperability:** A language that makes it easy to work with other languages and native systems (e.g. Win32 API from C# or Python, etc) could be raised as a better long-term time investment, etc.

The point is that, while I could come up with a different set of evaluation criteria and still be considered reasonable, we can't claim it's *objectively* superior/inferior to someone else's.

In conclusion, there's no *objective* basis for the criteria. It's as arbitrary as trying to debate if blue is, *objectively*, a "better" color than red, or if vanilla ice cream is *objectively* tastier than chocolate.

That is not to say that you can't have *good reasons* to justify your preferences, but at the end of the day, they're just *your* preferences.
> 1 votes

# Answer
Criteria for selecting a programming language for teaching a first course.

```
Simplicity
    One should be able to express the solutions to problems,
    by slowly introducing new concepts.
Necessity
    without over specifying and without extraneous boilerplate,
    nothing required that isn’t part of the solution.
Portability
    The result of evaluating must be bit for bit identical, everywhere.
Accessibility
    The number of unique implementations should be a nonnegative integer
    less than one.

```

Criteria for selecting a programming language for assignments

```
Any.
The solution must be correct, and verifiable, somehow.
The TA/grader may have a lot to learn--no harm in that.

```

Criteria for selecting a programming language for teaching later courses

```
Exactly the same as above.
Pseudo code is always preferable, unless compilation is required.
If compilation is required, pick a language for the concepts taught.
Change languages as needed—to suit the material.

```

Criteria to avoid

```
Whatever students claim to want.
Whatever industry claims to want.
.Whatever makes it easier to grade assignments.

```

Criteria for selecting a programming language to teach as a class

```
Whatever you like.
Whatever you think is useful to know.
Whatever a sufficient number of people want to learn.

```
> 0 votes

---
Tags: programming-languages, education
---


title: What is loop invariant for this loop?

text:
# Question
Title: What is loop invariant for this loop?
As far as i understand all loops have a loop invariants. My understanding is that loop invariant is an argument that is ***true*** at the beginning of the loop block as well as at the end of the loop. For example:

```
while(P) {
  //predicate is true here
  body of the loop
  //predicate still true here
}

```

But let\`s say i have the following loop (the code is in Java):

```
while(stack.size() > 0 && stack.peek() < 0) {
   stack.pop();
}

```

What i am trying to do here is to pop all negative numbers from the top of the stack - so at the end of the loop at the beginning of the stack will be a positive number or we have an empty stack. It is not clear from this loop what its invariant? What technic we can use to get loop invariant. In general, i would like to use loop invariants for validation of program correctness.

# Answer
> 1 votes
```
"
    Pre: stack is empty or contains only integers
    Post: Stack top is non-negative Integer
    P:  Stack top is an Integer   ( P is the invariant )
    BB: Stack top is negative
    T:  Stack size
"

" Establish P "
stack size > 0 or: [stack push: 0].
[ stack top negative
] whileTrue:
    [ " reduce T "
      stack pop.
      " restore P "
      stack size > 0 or: [stack push: 0]
    ]
" P && non BB => Post "

```

---
Tags: loops, java, loop-invariants
---


title: Difficult reccurence with two variables

text:
# Question
Title: Difficult reccurence with two variables
My question is a follow-up for the following thread: Solving unusual recurrence with two variables

I baisically have the same reccurence relation but with a small change---

$$T(n,k) = T(n-1,k)+T(n-m,k+1)$$

**The change is the addition of $m$ in the second element in the recursion (instead of 1 in the original question)**

The boundary cases remain the same (for some given constant $C$):

For all $x \leq C$ and for any $k$: $T(x,k)=1$

For all $y \geq C$ and for any $n$: $T(n,y)=1$

I'm trying to approximate the value of $T(n,0)$ (with a tight upper bound as possible). In the original question we were able to give a close formula for the reccurence after $i$ steps, which helped bounding its value. But due to the addition of $m$, this formula doesn't hold anymore.

A direction for how to address such reccursions or any idea for the solution would be very helpful.

# Answer
It will be less confusing to reparametrize $T$ by switching the order in which the second parameter increases: $$ T(n,k) = \begin{cases} 1 & \text{if } n \leq C \text{ or } k = 0, \\ T(n-1,k) + T(n-m,k-1) & \text{otherwise}. \end{cases} $$

Having done this switch, let us get rid of $C$ completely. Including $C$ as the third parameter, notice that $T(n+C,k,C) = T(n+D,k,D)$, and so it suffices to solve the recurrence for some value of $C$. We choose $C = 1$.

Let us now unroll the recurrence. Suppose that $n \> m$ and $k \> 0$. Then \begin{align} T(n,k) &= T(n-m,k-1) + T(n-1,k) \\ &= T(n-m,k-1) + T(n-m-1,k-1) + T(n-2,k) \\ &= T(n-m,k-1) + \cdots + T(2-m,k-1) + T(1,k) \\ &= T(n-m,k-1) + \cdots + T(2-m,k-1) + 1 \\ &= T(n-m,k-1) + \cdots + T(2,k-1) + m + 1. \end{align} This gives us $T(n,1) = n-m-1+m+1 = n$ if $n \> m$; you can check that the same formula works for all $n \geq 1$. Continuing, $$ T(n,2) = T(n-m,1) + \cdots + T(2,1) + m + 1. $$ If $n \> m$ then we can compute exactly $$ T(n,2) = (n-m) + \cdots + (2) + m + 1 = \frac{(n-m)(n-m+1)}{2} + m. $$ When $1 \leq n \leq m$, you can check that $T(n,2) = n$.

At this point we can in principle continue and obtain exact formulas. However, they will be quite messy. Fortunately, when $m$ is constant, it is easy to prove by induction that $T(n,k) = \Theta(n^k)$; indeed, $T(n,k) = n^k/k! + O(n^{k-1})$. Obtaining an explicit dependence on $m$ is certainly possible, but unless it's expressly needed, I wouldn't bother.
> 1 votes

---
Tags: asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n)
I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division)

The number `n` can be as large as 10^12, so a formula or a solution having the time complexity of O(logn) will work.

This is how far I can get:

1. The sum can be described as n * (1 + 1/2 + 1/3 + 1/4 + ... + 1/n). The series inside the parenthese is the Harmonic Progression which has no formula to calculate. So I don't think this can lead to a solution.
2. Playing with some numbers, this is what I get:

```
11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1
9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1
8 + 4 + 2 + 2 + 1 + 1 + 1 + 1
7 + 3 + 2 + 1 + 1 + 1 + 1
6 + 3 + 2 + 1 + 1 + 1
5 + 2 + 1 + 1 + 1
4 + 2 + 1 + 1
3 + 1 + 1
2 + 1
1

```

So by skipping the number 1s, we can reduce the time by a half. If using a loop to calculate the sum, we only need to loop until n/2. Since the rest contains only number 1s.

I've been trying to come up with a formula to calculate the series that is not 1 + 1 + ... + 1. Please help if you know the acceptable answer (a formula or a O(logn) solution).

# Answer
> 7 votes
Based on the following observation, you can derive a $O(\sqrt{n})$ time algorithm ( by computing the sum on the right-hand side naively in a $O(\sqrt{n})$-sized loop): (For $n=10^{12}$ this yields $n=10^{6}$ which is enough for say competitive programming sites which usually allow ~10^8 operations)

> For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$: $$ \sum\_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = 2\sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor - k^2 $$

---

This post on Math StackExchange provides a clear visual proof of the equality above.

The following is a proof for the equality above that does not depend on a graph.

All variables below stand for positive integers. Let us fix $n$ and $k=\lfloor\sqrt{n}\rfloor$. For all $i, j\le n$, let $\delta(i,j)=1$ if $i\cdot j\le n$. $\delta(i,j)=0$ otherwise. In particular,

* $\delta(i,j) = 1$ if $i,j\le k$.
* $\delta(i,j) = 0$ if $i,j\ge k+1$.

**Proposition**. $\left\lfloor\dfrac{n}{i}\right\rfloor = \displaystyle\sum\_{j=1}^n \delta(i,j) $ for all $i$.
Proof. Both sides count the number of positive multiples of $i$ that are smaller than or equal to $n$. $\ \checkmark$

$$\begin{aligned} \sum\_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor &= \sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \+ \sum\_{i=k+1}^n \left\lfloor\frac{n}{i}\right\rfloor \\ &= \sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \+ \sum\_{i=k+1}^n \sum\_{j=1}^n \delta(i,j)\\ &= \sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \+ \sum\_{i=k+1}^n \sum\_{j=1}^k \delta(i,j)\\ &= \sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \+ \sum\_{j=1}^k \sum\_{i=k+1}^n \delta(i,j)\\ &= \sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \+ \sum\_{j=1}^k\left(\sum\_{i=1}^n \delta(i,j)-\sum\_{i=1}^k \delta(i,j)\right)\\ &= 2\sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \- \sum\_{j=1}^k\sum\_{i=1}^k \delta(i,j))\\ &= 2\sum\_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor \- k^2 \quad \checkmark \\ \end{aligned}$$

The proof above is, basically, a direct translation of the visual proof.

# Answer
> 0 votes
Following what eru-cs wrote you get a nice and fast formula, but it is mathematically quite difficult. If you are not that good at maths (and it is hard) and can afford a bit more execution time:

If k \< $n^{1/2}$ then you can calculate easily the smallest and largest i such that n/i = k using integer division, and from that you can count how many such i there are; multiply by k and you get the sum of n/i for all these i.

You add up these sums, then you find for which i you didn’t add n/i and you add those. Done.

You can optimise this a bit, because the largest i such that n/i = k is one less than the smallest i such that n/i = k+1. And since calculating these sums is more complex, you might do the sums for $k \< (n/2)^{1/2}$ for example.

---
Tags: algorithms, summation
---


# Question
Title: Unifiers modulo commutativity in terms of syntactic unifiers and $\approx_{C}$-class
I am studying Term Rewriting by reading Baader's book "Term Rewriting and All That". I am in the chapter of Equational Unification, in the section of Commutative Functions. I am trying to do the following exercise:

> Let $s, t \in T(\Sigma, V)$. By exercise 10.10 we know that the $\approx\_{C}$-classes of these terms are finite. Let $\\{s\_1, \ldots, s\_m \\}$ be the $\approx\_{C}$-class of $s$, and let $\\{t\_1, \ldots, t\_n \\}$ the $\approx\_{C}$-class of $t$. Show that: $$ \mathcal{U}\_{C}(\\{ s \approx\_{C}^{?} t \\}) = \bigcup\limits\_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}\_{\emptyset}(\\{s\_i =^{?} t\_j \\}) $$ and that $\\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s\_i =^{?} t\_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \\}$ is a complete set of C-unifiers of $s \approx\_{C}^{?} t$.

It seems obvious, but how can I prove that: $$\mathcal{U}\_{C}(\\{ s \approx\_{C}^{?} t \\}) = \bigcup\limits\_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}\_{\emptyset}(\\{s\_i =^{?} t\_j \\}) ? \tag{1}$$

After I prove that, I know how to proceed: let $\delta$ be an arbitrary C-unifier of $s \approx\_{C}^{?} t$. By the equation (1) above, this means that $\exists\_{i, j}: \ s\_i \delta = t\_i \delta$. Take $\sigma$ the mgu of $s\_i =^{?} t\_j$ and we have that $\sigma$ is more general than $\delta$. Therefore, $\\{ \sigma \ | \ \sigma \ \text{ is an mgu of } s\_i =^{?} t\_j \text{ for some } i, j, 1 \leq i \leq m, 1 \leq j \leq n \\}$ is a complete set of C-unifiers of $s \approx\_{C}^{?} t$.

How can I prove (1)? Any hint/suggestion is very much appreciated. Thanks in advance.

# Answer
> 1 votes
Note that for all $s, t \in T(\Sigma, V)$ we have:
$$s \approx\_{C} t \iff \exists\_{i, j}: s\_i = t\_j \tag{\*}$$

Using (\*) for the terms $s \sigma$ and $t \sigma$ we obtain: $$s \sigma \approx\_{C} t \sigma \iff \exists\_{i, j}: s\_i \sigma = t\_j \sigma, $$i.e, $$\mathcal{U}\_{C}(\\{ s \approx\_{C}^{?} t \\}) = \bigcup\limits\_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}\_{\emptyset}(\\{s\_i =^{?} t\_j \\})$$

---
Tags: term-rewriting, unification
---


# Question
Title: How to find the language of a CFG from Production rules
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are

\begin{align} &S \to AS \mid \epsilon \\ &A \to aa \mid ab \mid ba \mid bb \end{align}

How can I find the language it describes?

# Answer
> 2 votes
The idiom "$X \to YX \mid \epsilon$" (or "$X \to XY \mid \epsilon$") means that $X$ generates $Y^\*$ (assuming there are no other productions for $X$). This means that your grammar generates $A^\*$. You know what $A$ generates. Putting everything together, you should be able to find a very concise description of the language generated by your grammar.

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


# Question
Title: Unary function is partially n-computable
Please help me prove the following problem:

A unary function $f(x)$ is said to be *partially $n$-computable* if it is computed by some $\mathcal{S}$ program $\mathcal{P}$ such that $\mathcal{P}$ has no more than $n$ instructions, every variable in $\mathcal{P}$ is among $X, Y, Z\_1, . . . , Z\_n$ and every label in $\mathcal{P}$ is among $A\_1,...,A\_n,E$. Prove that if a unary function $f : N \rightarrow N$ is computed by a program with no more than $n$ instructions, then $f$ is partially $n$-computable.

This problem is in Chapter 2, Section 4 of Computability, Complexity, and Languages by M.Davis.

I am quite confused by this problem because the statement at the beginning and the question that needs to be proved are just two ways of saying the same thing. The statement is "q if p" and the question is "if p then q" which both mean "p implies q". So I totally don't understand what is asked to be proved here.

# Answer
> 0 votes
Well there are trivial two conditions you have to prove.

If $f:N\rightarrow N$ is computable in $n$ instructions, then there exists a corresponding program $P$ that computes it in $n$ instructions. $P$ could assign one new variable in every instruction, thus the program uses $\leq n$ new variables. Furthermore the program only contains $n$ instructions meaning there is one label for every instruction at max, hence the number of labels is $\leq n$. This completes the proof (that $f$ is *partially n-computable*)

---
Tags: computability
---


# Question
Title: is any faster algorithm to calculate this series? ∑∑ai/aj
I am wondering if it is possible to calculate the following double sum, where $a\_1,\ldots,a\_n$ are positive integers, in time faster than the trivial $O(n^2)$: $$ \sum\_{i=1}^n \sum\_{j=1}^n \left\lfloor \frac{a\_i}{a\_j} \right\rfloor. $$

For example, if $a\_1 = 1, a\_2 = 2, a\_3 = 3$ then the sum is $9$.

# Answer
> 2 votes
Assuming that your numbers $a\_i$ are small enough and $n$ is large enough, the following algorithm may work better in practice.

For each $a\_i$, for all possible division results $d\_j$, find minimum $v\_j$ such that $\lfloor \frac {a\_i} {v\_j} \rfloor = d\_j$. The idea is the following:

* There can't be too many different $d\_j$. E.g. for $a=10^9$ there are about $6 \cdot 10^4$ possible $d\_j$. It's possible to show that there are $O(\sqrt{a})$ possible values of $d\_j$ (about $2 \sqrt a$). Note that it's possible to iterate all possible $d\_j$'s in time linear of their amount.
* All numbers between neighboring $v\_j$'s give the same result after division.

Therefore, the algorithm is the following:

* Sort $a\_1, \ldots, a\_n$
* For each $a\_i$, find all possible $\\{(d\_j, v\_j)\\}$ as described above. Using binary search on array of $a\_i$, for all $j$ find the number of $a\_i$ lying between $v\_j$ and $v\_{j+1}$. Division by any of them results in $d\_j$.

P.S.: This algorithm can take exponential time (since it's polynomial on the numbers themselves), but it can have a guaranteed $O(n^2 \log n)$ time when we ignore $d\_j$ which can't be achieved: when we've found the last number $a\_k$ which lies between $v\_j$ and $v\_{j+1}$, we select the next $d$ to consider based on $a\_{k+1}$. Additional $\log n$ comes from the binary search.

# Answer
> 0 votes
Dmitry’s idea will work very well for many sequences of integers. If I had to evaluate many different sums for values of n around a few million then I would use this approach to have a fighting chance to find the sum without doing trillions and trillions of operations.

But a hard case would be: About n/2 numbers randomly between n and 4n, and the remaining numbers randomly between 4n^2 and 16n^2. In this case it seems very hard to avoid doing about n^2/4 divisions. Still, note that a difficult worst case may never happen.

---
Tags: algorithms
---


# Question
Title: Is there a way to map a multi-variable structure onto a single range?
I want to categorise variants of a structure made up of some number of variable components by mapping it to a unique range. Assume that the individual components all fall within the same base range.

I'm using color as an example for this question as its intuitive to think about but I don't want the question to be specific to that, its just a framework for understanding the problem.

## Simple case:

Imagine I have a structure, called `C` made up of two values `(r, b)` (red and blue) and I want to categorise variants of `C` into distinct bands, things like "very red", "quite blue", "slightly blue", "quite red" etc.

In this case I could just map the values by starting at `0` and then adding anything in the `r` channel and subtracting anything in the `b` channel, then I would get a final value in a 1 dimensional range somewhere between `-1` and `1` (assuming the values for `r` and `b` are clamped. Then I could use this output value to categorise it into a band: maybe anything below `-0.8` is "very blue" and a value between `0.4` and `0.5` is "somewhat red".

Examples:

`(0.1, 0.3)` `->` `-0.2`

`(1.0, 0.0)` `->` `1.0`

`(0.2, 0.9)` `->` `-0.7`

## Not so simple:

However, if I introduce a third value, so `C` is made up of `(r, b, g)`, I can't see how I can easily map this to a range which I can make assertions about, like "bluey green" or "reddish blue". Trying to create a solution in code for this (naively) just ends with a complicated set of conditional statements.

One solution I thought might work would be to convert the 3D version of `C` into a point on a triangle expressed as a weighting of its vertices (where each vertex corresponds to one of `C`'s components), and then convert that point in 2D coordinate space into a categorisation based on where it falls in a sub-shape - which is just a delimited area - on the triangle. So I could say, if the point falls inside this sub-shape on the triangle its "bluey green", if the point falls inside this other sub-shape, then its "reddish blue" etc. However, this does seems like a fairly intricate solution and I'm not sure if I am heading down the wrong path.

Also, I can't see how this would then generalise to putting more and more variables into `C`.

I don't a have strong intuition for what field of mathematics or computer science I should be looking into to solve a problem like this or how exactly mapping like this work.

**If anyone knows how to solve this** or **what sort of things I should be looking at to solve it**, I would really appreciate some advice! Thanks.

# Answer
If you want to solve this for colors, there are many techniques that are appropriate in that domain. But you say you aren't really asking about colors, so I'll treat it as an analogy and try to give an answer that is more general (but wouldn't be what I would recommend for colors):

It sounds like you want to cluster the possible values into multiple clusters. I would suggest you read about clustering algorithms. You'll need to pick a "similarity measure" that measures how similar two structures are. That is domain-specific and not something we can tell you; you'll have to pick it based on your knowledge of the specific application domain.
> 0 votes

---
Tags: mathematical-programming
---


# Question
Title: How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges *valid* if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.

Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem?

I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

# Answer
You can color a pair of arcs $(a\_1,a\_2)$ by the same color, if and only if *all the paths* from the source to the sink, passing through the arc $a\_1$, also pass through the arc $a\_2$.

Let's consider the set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. Then we can define an equivalence relation on the set $A$:

$$(a\_1 \sim a\_2) \equiv (P(a\_1) = P(a\_2))$$

A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.

The algorithm to split all the arcs into such equivalence classes is exact, but may be slow for large graphs. It consists of two steps:

**Step 1**. For each arc $a \in A$ compute the subset $P(a) \subset P$. This can be done by scanning all the paths in the set $P$, and updating all the subsets $P(a)$ along each such path.

**Step 2.** Let's assume that we store all the subsets $P(a)$ as binary numbers. Sort the set $A$ by these numbers - this will allow us to group together all the arcs with the same subset of paths. Scan this sorted set of arcs, assigning the same color to arcs in each group.
> 4 votes

# Answer
I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^\*(\min(n^3,m^2))$ time.

## Theory

Let $P(a)$ denote the set of paths that start at $s$, go through the arc $a$, and end at $e$.

*Lemma 1.* $a\_1,a\_2$ can be given the same color iff $P(a\_1)=P(a\_2)$.

Let $G^\*$ be the dual graph of $G$, i.e., each arc of $G$ is a vertex of $G^\*$, and for each pair of arcs $u \to v$, $v \to w$ in $G$ we connect the corresponding vertices with a directed arc in $G^\*$. The start vertex of $G^\*$ is a new vertex $s\_0$, and it has an arc in $G^\*$ to each arc $s \to v$ in $G$; and similarly for its end vertex.

*Lemma 2.* An arc $a\_2$ is in every path of $P(a\_1)$ iff $a\_2$ is a dominator or post-dominator of $a\_1$ in $G^\*$.

Say that $a\_1 \prec a\_2$ if $a\_1$ is the immediate dominator of $a\_2$ and $a\_2$ is the immediate post-dominator of $a\_1$ in $G^\*$.

*Lemma 3.* $P(a)=P(a')$ iff there exists a sequence of arcs $a\_1,\dots,a\_n$ such that $a=a\_1 \prec a\_2 \prec \cdots \prec a\_n=a'$.

## Algorithm

This theory immediately leads to an efficient algorithm for your problem:

1. Compute the dominator tree $D$ and post-dominator tree $D'$ of $G^\*$.
2. Initialize a Union-Find data structure with each arc of $G$ in its own set.
3. For arc $a\_1$ of $G$, let $a\_2$ be its immediate dominator in $D$; if $a\_1$ is the immediate dominator of $a\_2$ in $D'$, call Union($a\_1,a\_2$).
4. Assign a different color to each set of the Union-Find data structure.

## Running time analysis

If $G$ has $n$ vertices and $m$ arcs, then $G^\*$ has $m$ vertices and $\min(n^3,m^2)$ arcs. Computing the dominator tree can be done in nearly linear time (see e.g., https://en.wikipedia.org/wiki/Dominator\_(graph\_theory)#Algorithms or Dominator Tree for DAG). The Union-Find algorithm can be done in nearly linear time. Thus, the running time is essentially $O(\min(n^3,m^2))$, ignoring logarithmic factors.

I wouldn't be surprised if there is a more efficient way to compute the dominator tree of $G^\*$ without constructing $G^\*$ explicitly, which would lead to improvements in the running time of this algorithm.

## Proofs

*Proof of Lemma 1.* If $P(a\_1) \ne P(a\_2)$, there is some path that goes through $a\_1$ but not $a\_2$ (or vice versa), and then by the requirements, $a\_1,a\_2$ cannot be given the same color.

For the converse, suppose we form equivalence classes on the arcs where $a\_1,a\_2$ are equivalent if $P(a\_1)=P(a\_2)$, give each equivalence class a unique color, and color each edge according to the color of the equivalence class it is contained in. Then this satisfies all of the constraints: for any color $c$ and any two arcs $a\_1,a\_2$ colored $c$, we have $P(a\_1)=P(a\_2)$, so any path $p \in P(a\_1)$ also satisfies $p \in P(a\_2)$ and thus visits $a\_2$; and any path $p \notin P(a\_1)$ also satisfies $p \notin P(a\_2)$ and thus does not visit $a\_2$.

I haven't written out the proofs of Lemmas 2-3, so I recommend you do that and check my reasoning before using this algorithm.
> 4 votes

# Answer
It sounds to me like the greedy algorithm should work, I'm not able to come up with any counter-examples, however, I haven't had time to try to prove the claim either.

**Terminology**

Definition. Let $s$ be the start and $t$ be the end vertices (source and sink, respectively). Let $a$ and $b$ be vertices where there is a path from $a$ to $b$ (from now on $a \< b$), i.e. $s \leq a \< b \leq t$. We say that an $st$-path $P = \left(s=v\_1, \dots, v\_\ell=t\right)$ is *$(a,b)$-non-laminar* if $a \in P$ and $b \notin P$, or $a \notin P$ and $b \in P$. Intuitively, this means that $P$ "branches" out *between* $a$ and $b$, and branches in *after* $b$, or branches out *before* $a$ and branches in between $a$ and $b$.

Let us define $\text{lca}(v)$ to be the vertex that is the lowest common ancestor of the vertices $\\{u \in V \mid (u,v) \in E\\}$, i.e. the lowest common ancestor of the in-neighbors of $v$.

We say that a path is $v$-non-laminar if it is $(\text{lca}(v), v)$-non-laminar.

**Greedy algorithm.**

(1) If a vertex has in-degree = 1 and out-degree = 1, then you use the in-arc's color for the out-arc.

(2) Every time you *fan out*, that is, whenever you have a vertex with out-degree at least two, each out-arc needs a *new color*.

(3a) Every time you *fan in*, i.e., there is a vertex $v$ with in-degree at least two, and there is no $v$-non-laminar path, you take the color of an in-arc of $\text{lca}(v)$.

(3b) Every time you *fan in* and there is a $v$-non-laminar path, you need a *new color*.

That should cover all possible cases, and I think it shouldn't be too difficult to show that you can do it in $O(n^2)$ time. It might be possible to lower the time to $O(n + m)$, but I can't think of it now.
> 3 votes

# Answer
There is a simple randomized linear-time algorithm (one-sided error). It is based on HEKTO's idea, using the equivalent relation.

The algorithm chooses weight $w\_a$ for each arc $a$. Then, the algorithm computes the weighted sum of paths $W(a) = \sum\_{p \in P(a)} \prod\_{a' \in p} w\_{a'}$ for each each arc $a$. All $W$ values can be computed by using two dynamic programming (combining "forward" DP and "backward" DP) and in $\Theta(n + m)$ arithmetic operations. The algorithm then assign one color for each $W$ value, using a hash map.

Pseudo code:

```
forward = [ 1 if it is the source, 0 otherwise | vertices ]
for each arc a in topological order:
    forward[a.to] += forward[a.from] * w[a]

backward = [ 1 if it is the destination, 0 otherwise | vertices ]
for each arc a in reverse topological order:
    backward[a.from] += w[a] * backward[a.to]

for each arc a:
    W[a] = forward[a.from] * w[a] * backward[a.to]

```

It is easy to see $W(a) = W(b)$ if and only if $P(a) = P(b)$ if weights $w$ are treated as formal variables. According to Schwartz–Zippel lemma, if we choose weight randomly from a finite field $F$, then one particular equality fails in at most probability $m/|F|$. The overall success probability of the algorithm can be bounded by $1 - m^3 / 2|F|$ because we have at most $m \choose 2$ equations we want to distinguish, but it should be more like $\approx 1 - m^2/|F|$ for "typical input" (though I'm not very sure). We can choose a large prime of size $p \approx 2^{64}$ and do a modular arithmetic $F = GF(p)$ to implement the algorithm.
> 3 votes

# Answer
This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I don't employ any randomization here, so this algorithm also produces the exact coloring.

For each arc $a \in A$ let's consider a set of arcs $R(a) \subset A$, *reachable* from the arc $a$ in *both* forward and backward directions. Any arc $a \in A$ is reachable from itself, so $a \in R(a)$. We can color a pair of arcs $(a\_1,a\_2)$ by the same color, if and only if $R(a\_1) = R(a\_2)$. So, as in my original answer, we can define an equivalence relation on the set $A$:

$$(a\_1 \sim a\_2) \equiv (R(a\_1) = R(a\_2))$$

A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.

We can compute sets $R(a)$ for each arc $a \in A$, using the iterative process, similar to one, described in the @pcpthm answer. For each vertex $u \in V$ we define two sets of arcs - a set $F(u) \subset A$ of arcs, forward-reachable from the vertex $u$, and a set $B(u) \subset A$ of arcs, backward-reachable from the vertex $u$. For any arc $a=(u,v)$ we can represent its $R(a)$ as a union of three non-intersecting sets:

$$R(a) = B(u) \cup \\{(u,v)\\} \cup F(v)$$

Sets $F(u)$ and $B(u)$ for each vertex $u \in V$ can be computed using topological ordering on the set $V$. For example, the backward (according to this ordering) scan of the set $V$ will give us all the sets $F(u)$ using the formula:

$$F(u) = \bigcup\_{v \in N\_{out}(u)}(\\{(u,v)\\} \cup F(v))$$

where $N\_{out}(u)$ \- open "out"-neighborhood of the vertex $u$. Each such set can be represented by a binary number of the length $m=|A|$. The union operation here for large $m$ can be performed in $O(m)$ time, so the total time to compute all the $R(a)$ will be $O((n+m)m)$.

This algorithm is slower than the randomized algorithm in the @pcpthm answer, however it looks like it's the price we need to pay for the exact solution. The culprit is a necessity to work with large sets of arcs, which can't be represented by a single machine word.
> 2 votes

---
Tags: algorithms, graphs, colorings, topological-ordering
---


# Question
Title: Curry-Howard, void, and type checking in Haskell
I am trying to understand an example of theorem proving via type checking in Haskell given here. The example is as follows.

Using the Curry-Howard isomorphism, construct an inhabitant of the type and prove that $N= (A\vee (B\rightarrow A))\\& (C\\&(C\rightarrow B))\rightarrow ((\neg B\\& A)\vee ((A\rightarrow B)\\&(B\rightarrow A)))$ holds.

The author provides a following code.

```
data Void
nnot :: Void -> a
nnot = undefined
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (Void -> b, a) (b -> a)
proposition (Left x, (y, f)) = Left (nnot, x)
proposition (Right g, (y,f)) = Left (nnot, (g (f y)))

```

The implication $(A\vee (B\rightarrow A))\\& (C\\&(C\rightarrow B))\rightarrow (\neg B \\& A)$ does not hold. But the constructed term is claimed to prove it, and the type checker is satisfied by it. Why?

I feel that the transcription of the initial formulae to the type of `proposition` is incorrect, since the negation of `b` is represented with `Void -> b` which is the absurdity (and it is defined as `nnot`). I.e. from the logical point of view, the pair `(Void -> b, a)` corresponds to the term $\bot \\& A$. But that does not give an answer why the type checker verifies the code above. Thus, I will greatly appreciate any hints on the following two questions.

1. Why does the Haskell compiler approve the type of `proposition`?
2. If that is the case when Curry-Howard is not in place then how I can actually use the type checker to prove formulas with negation via Curry-Howard?

I do not know either this question is more appropriate on cs or stackoverflow, so please sorry if it is off-topic.

EDIT: Given the following corrected proposition:

```
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (b -> Void, a) (b -> a)

```

I have written the following "proof" for it, and the type checker was satisfied. I do not know whether I can believe that the proposition can be counted as being proved after the type check.

```
proposition (Left x, (y, f)) = Right ((\z1 z2 -> z1) x)
proposition (Right g, (y,f)) = Right ((\z1 z2 -> z1) (g (f y)))

```

And still I have no idea whether it is possible to prove any negation by the type checking procedure.

Edit2: I thought I had got some understanding of the topic, but then I tried the following:

```
prop1 :: ((Either a b), c) -> b
prop1 (Right x, y) = x

```

This code is Ok for Haskell (for example, there). But it seems to be ill-typed from the point of view of logic: the corresponding type is $(A\vee B)\\& C\rightarrow B$. It is obvious that the case given in `prop1(Right x, y) = x` has the right (heh) type, but I did not define the case for `prop1(Left x, y)`, thus the proposition is not proved for this case. Hence, I can have problems with the disjunction as well.

# Answer
> 7 votes
I would find a different tutorial because the author of that one is fundamentally confused. They wrongly claim that $\neg a$ and $\bot\to a$ are equivalent ($a\to\bot$ would be correct), and also wrongly claim that you can't write a function of type $\texttt{Void}\to a$.

$\texttt{Void}\to a$ is vacuously true. In principle a function of that type should require no definition at all because the number of cases for which you need to define it is zero. GHC doesn't accept that, but (with `-XEmptyCase`) it does accept

```
f :: Void -> a
f x = case x of {}

```

which is a perfectly valid, logically sound definition.

> Why does the Haskell compiler approve the type of proposition?

The proposition as written in the Haskell code is actually true. The proof is invalid though since it uses $\texttt{undefined}$.

If you replaced the right hand side with $(b\to\texttt{Void},a)$ then it would be false, but you could still "prove" it using $\texttt{undefined}$; in fact you could just write $\texttt{proposition} = \texttt{undefined}$ and the type checker would accept that. It would also accept $\texttt{proposition} = \texttt{proposition}$. If you want to use Haskell as a Curry-Howard sandbox you have to take care that your code doesn't throw an exception or fail to terminate, because the compiler won't catch those errors.

---

Response to edit: your proof is correct but it can be simplified. In the first case, there's no need to create a function and immediately apply it to one of its arguments. Instead of `(\z1 z2 -> z1) x` you can write `\z2 -> x`, or `\_ -> x` since the argument/premise isn't used. In the second case, you don't need to prove `b -> a` since you already have `g :: b -> a`. The simplified proof is

```
proposition (Left x, _) = Right (\_ -> x)
proposition (Right g, _) = Right g

```

In addition to the pitfalls that Dan Doel mentioned in a comment, missing cases are another thing to watch out for. GHC by default doesn't even warn about them. With `-Werror=incomplete-patterns` it will refuse to accept programs with missing cases.

You can prove negations. You need to return a value of type $\texttt{Void}$, which you can't create yourself but you can get from elsewhere. For example here's a proof of $((P\Rightarrow Q) \mathbin{\\&} \neg Q)\Rightarrow \neg P$:

```
f :: (a -> b, b -> Void) -> (a -> Void)
f (x, y) = \z -> y (x z)

```

You may reasonably wonder where your caller got the value of type $\texttt{Void}$, but that's the caller's problem, not yours. Deriving a contradiction in a subproof doesn't mean the logic is inconsistent, it just means you've shown that you'll never actually reach this point in the real world.

---
Tags: type-inference, haskell, curry-howard
---


# Question
Title: Using Limits to Determine Asymptotic Relationship
Let's say we have $3^{4n}$ and $4^{3n}$. With the note of The Asymptotic Cheat Sheet from MIT.

We should first calculate the lim n-\>infinity $3^{4n}$/$4^{3n}$. and it result is $\infty$.

In the we have

```
lim n→∞ f(n)/g(n) != 0,∞  ⇒  f=Θ(g)   Note 1

```

and

```
lim n→∞  f(n)/g(n)=∞     ⇒ f=ω(g)   Note 2

```

My questions is: Given that f(n) is $3^{4n}$ and g(n) is $4^{3n}$ in this case, which "case" should we apply ? How should one read Note 1 correctly ? Does it mean "lim n→∞ f(n)/g(n) not equal to 0, but equal to infinity? then f=Θ(g) " Or
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?

Also if f(n) = $\theta $ g(n)? doesn't that already mean f(n) = $O$ g(n)? if so, then note 1 should read as "lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?

# Answer
Knowing $3^4=81$ and $4^3=64$, we have $f(n)=81^n$ and $g(n)=64^n$. Using this we obtain: $$\lim\limits\_{n \to \infty}\frac{f(n)}{g(n)}=\lim\limits\_{n \to \infty}\left(\frac{81}{64}\right)^n=+\infty$$ so you have your "Note 2". By definition last limit mean $\forall C\>0$ we have $\exists N \in \mathbb{N}$, such that $\forall n\>N$ holds $\frac{f(n)}{g(n)} \geqslant C$ so we have $f\in \Omega(g)$.

For further let's assume, that we have positive functions and $g$ have not $0$s subsequence.

Following question. Your "note 1" means that $\lim\limits\_{n \to \infty}\frac{f(n)}{g(n)}$ is not $0$ and is not $\infty$, but equals to some number between them.

And last. Suppose $\lim\limits\_{n \to \infty}\frac{f(n)}{g(n)}=A\>0$. This means, that $A-\varepsilon\<\frac{f(n)}{g(n)} \< A+\varepsilon$, for appropriate $n$, and so we can conclude $f \in \Theta(g)$.
> 0 votes

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


# Question
Title: Better way to decide if a set is a pure simplicial complex
# Setup

I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex.

A pure simplicial complex is a set where all facets have the same degree, a facet is a simplex that is not contained in a simplex of higher degree. So for example, a single vertex is a facet. A set of vertices is a pure simplicial complex because all the facets are of degree one and so on.

In this case a simplicial complex is up to order 2 (triangles) so it is expressed as 2 matrices.

An $|edges|\times|vertices|$ adjacency matrix and a $|face|\times|edges|$ adjacency matrix. If you are curious about the details here's a cool resource on simplicial complexes in the context of CS: https://www.cs.cmu.edu/~kmcrane/Projects/DDG/

I represent a subset of the complex as 3 vectors, a vertex vector, an edge vector and a face vector, where every entry is 0 or 1. 1 means the element is in the subset, 0 means it isn't.

# Attempted solution

So to determine if a subset is a pure simplicial complex I thought of the following approach. let's say we want to find all the vertex facets first.

0 out all the edge rows in the edge adjacency matrix that are not in the subset. This is achieved by the product $\text{sub\_edge\_adjacency} = D(edges) \times \text{edge\_adjacency}$ where $D$ is an operator that generates a diagonal matrix from a vector. Then multiply the above by a vector filled with 1's of the same dimension as the number of edges and multiply from the right $ones * \text{subedge\_adjacency}$. Which is equivalent to just adding all the rows into a single vector...

From then on...

I am not going to keep explaining the algorithm as it should be obvious this is convoluted. I suspect there is a much nicer way to check if a subset is a pure simplicial complex. Essentially I am trying to code the 8th programming problem of chapter 2 in the resource I linked.

I tested my monstrosity and it works, but I am wondering if someone can come up with a cleaner algorithm.

# Constraints

To clarify, the algorithm should be constraint to using mostly, or even exclusively, linear algebra operations. This means that most information should be obtained through the use of matrix products, additions, and queries of the properties of the matrices, like the number of zeroes, the trace of the diagonal etc...

# Refined implementation

I managed to simplify the logic quite a bit, but I want to see if it is possible to get a more straighforward implementation:

```
using SBM = Eigen::SparseVector<bool>;
std::array<SBM, 3> Closure(
    const Eigen::SparseMatrix<bool>& edge_matrix,
    const Eigen::SparseMatrix<bool>& face_matrix,
    const std::array<Eigen::SparseVector<bool>, 3>& simplices)
{
    const auto face_vertex_adjacency = face_matrix * edge_matrix;
    const auto& vertices = simplices[0];
    const auto& edges = simplices[1];
    const auto& faces = simplice
    s[2];

    SBM closure1_edges = edges + face_matrix.transpose() * faces;
    SBM closure1_vertices = vertices + edge_matrix.transpose() * edges;

    return {closure1_vertices, closure1_edges, faces};
}
bool IsComplex(
    const Eigen::SparseMatrix<bool>& edge_matrix,
    const Eigen::SparseMatrix<bool>& face_matrix,
    const std::array<Eigen::SparseVector<bool>, 3>& simplices)
{
    const auto& vertices = simplices[0];
    const auto& edges = simplices[1];
    const auto& faces = simplices[2];

    auto[closure_vertices, closure_edges, closure_faces] =
        Closure(edge_matrix, face_matrix, {vertices, edges, faces});

    return
        closure_vertices.isApprox(vertices) &&
        closure_edges.isApprox(edges) &&
        closure_faces.isApprox(faces);
}

int IsPureComplex(
    const Eigen::SparseMatrix<bool>& edge_matrix,
    const Eigen::SparseMatrix<bool>& face_matrix,
    const std::array<SBM, 3>& simplices)
{
    const SBM& verts = simplices[0];
    const SBM& edges = simplices[1];
    const SBM& faces = simplices[2];

    if(!IsComplex(edge_matrix, face_matrix, simplices)) return -1;

    SBM point_faces = edges.transpose() * edge_matrix;
    const bool has_point_facets = SBM((verts - point_faces).pruned()).nonZeros();

    SBM line_faces = faces.transpose() * face_matrix;
    const bool has_line_facets = SBM((edges - line_faces).pruned()).nonZeros();
    const bool has_triangle_facets = faces.nonZeros();

    if(int(has_point_facets) + int(has_line_facets) + int(has_triangle_facets) != 1)
        return -1;

    return 3 * has_triangle_facets + 2 * has_line_facets + has_point_facets;
}

```

I added all the code so that this is copy pasteable, but the only important function is the last one `IsPureComplex`. The above works and is better than what I originally had, but I wonder if it is possible to make it even simpler. That is to say, shorter and with less cyclomatic complexity.

# Answer
First, suppose there is at least one triangle in the set. Now the complex is pure if and only if all vertices are contained in some triangle, because any edge that is a facet contains at least one vertex. This is simple to check: iterate over all triangles and mark all vertices contained in them. If there are no unmarked vertices, the complex is pure. Otherwise, each unmarked vertex lies inside a facet that is not a triangle.

If your set does not contain a triangle, you can use the same approach to determine whether there is facet that is not an edge.
> 1 votes

---
Tags: algorithms, computational-geometry, linear-algebra, simplex
---