## Top new questions this week:

### Are "Flow Free" puzzles NP-hard?

A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $\:n\times n\:$ grid graph such that each vertex is in at most one pair. $\:$ A ...

np-hard square-grid

### Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...

algorithm-analysis runtime-analysis recurrence-relation

### What exactly is an algorithm?

I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, ...

algorithms

### Detecting palindromes in binary numbers using a finite state machine

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary ...

regular-languages finite-automata

### Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. ...

turing-machines notation

### What problem cannot be solved by a short program?

BACKGROUND: Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of ...

complexity-theory programming-languages kolmogorov-complexity

### Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?

graph-theory binary-trees spanning-trees

## Greatest hits from previous weeks:

### Understanding Peterson’s and Dekker’s algorithms

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries. I tried to formulate the algorithms in informal language like follows: ...

concurrency synchronization mutual-exclusion

### How to verify number with Bob without Eve knowing?

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob ...

algorithms cryptography

### Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...

algorithms dynamic-programming

### Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...

algorithms complexity-theory graph-theory shortest-path graph-algorithms