## Top new questions this week:

### What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal ...

probability-theory weighted-graphs mathematical-foundations markov-chains

### Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...

algorithms algorithm-analysis data-structures runtime-analysis discrete-mathematics

### Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...

computability integers randomness real-numbers

### Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...

algorithms graph-theory optimization combinatorics

### Compression functions are only practical because "The bit strings which occur in practice are far from random"?

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question. Andrej explains that given the set of all bit strings of length 3 or ...

information-theory data-compression

### Primitive Recursion and course-of-values recursion - examples?

I ran into examples that I not trivially understand on course-of-values recursion, In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the ...

computability computation-models recursion-theory primitive-recursion

### Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as possible and no backtracking is allowed, ...

formal-languages regular-languages regular-expressions

## Greatest hits from previous weeks:

### Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...

algorithms sorting

### Is 0* decidable?

I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite ...

formal-languages computability

### Can someone help me make this branch and bound algorithm more efficient for a large input?

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the coursera discrete optimisation course) I tried implementing dynamic programming first, and that worked ...

algorithms efficiency knapsack-problems branch-and-bound

### Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...

formal-languages regular-languages mathematical-foundations
 asked by Simon Weinzierl 1 vote

### Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...

algorithms graph-theory graphs data-structures shortest-path