## Top new questions this week:

### Can this special case of bin packing be solved in polynomial time?

Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$. Is there a polynomial-...

combinatorics packing

### Is there a $\Sigma^0_3$ variant of the halting problem?

In terms of the arithmetical hierarchy, the halting problem is known to be $\Sigma^0_1$-complete, and the so-called universal halting problem, is the problem of determining whether a given computer ...

computability halting-problem

### NP-complete problem

Is the following line true? Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$ and $B$ is NP-complete problem, then $C$ is also NP-complete. If B is NP-complete, then C would ...

np-complete np

### What is a guarenteed amount of colors, depending on the graph's arboricity

Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist? For ...

graphs colorings

### Is ANN a data structure or an algorithm?

When I read about Artificial Neural Networks (ANN), no one says what ANN is. For instance, Wikipedia says: Artificial neural networks (ANNs), usually simply called neural networks (NNs), are ...

neural-networks

### How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?

Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get? So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...

complexity-theory reductions np-hard np co-np

### Approximation of rational sequences via linear recurrences of small order

I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact ...

recurrence-relation approximation

## Greatest hits from previous weeks:

### Residual Graph in Maximum Flow

I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow? Can anyone help me ...

algorithms graphs network-flow

### Floyd's Cycle detection algorithm | Determining the starting point of cycle

I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare) I can see how the ...

### Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...

information-theory coding-theory

I am looking to calculate the physical address corresponding to a logical address in a paging memory management scheme. I just want to make sure I am getting the calculation right, as I fear I could ...

operating-systems memory-management paging

### Difference between Turing machine and Universal Turing machine

I've read what a Turing machine and a UTM are, but I don't get the difference. What can a UTM do which a normal Turing machine can not?

turing-machines

### Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...

algorithms graphs search-algorithms graph-traversal

### BIT: What is the intuition behind a binary indexed tree and how was it thought about?

A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...

algorithms binary-trees trees

## Can you answer these questions?

### How good a center of a BFS tree is?

Consider a graph $G=(V,E)$, and a BFS tree $T$ starting from an arbitrary node $v\in V$. Now consider finding the center node $u_T$ of $T$, i.e., the vertex with the lowest eccentricity in $T$, which ...

algorithms graphs shortest-path

### What's a good way to sort a set of several correlated vectors?

Let's say I have a bunch of lists of real numbers which we'll call a, b, c, etc. Moreover, ...

sorting
 asked by Closed Limelike Curves 1 vote