## Top new questions this week:

### Huffman encoding: why is there no need for a separator?

Char Code ==== ==== E 0000 i 0001 y 0010 l 0011 k 0100 . 0101 space 011 e 10 r 1100 s 1101 ...

coding-theory encoding-scheme huffman-coding

### If P=NP, are there cryptosystems that would require n^2 time to break?

If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption ...

cryptography encryption

### Can any finite problem be in NP-Complete?

My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ...

np-complete np

### Will \$L = \{a^* b^*\}\$ be classified as a regular language?

Will \$L = \{a^* b^*\}\$ be classified as a regular language? I am confused because I know that \$L = \{a^n b^n\}\$ is not regular. What difference does the kleene star make?

formal-languages regular-languages kleene-star

### What is the relation between First Order Logic and First Order Theory?

I thought that any FOT is a subset of FOL, but that does not seem to be the case, because FOL is complete (every formula is either valid or invalid), while some FOT (like linear integer arithmetic) is ...

logic first-order-logic

### If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup, how would one refer the speedup gained by using an O(1) algorithm vs an O(n)?

complexity-theory terminology

### Origin of the concept of types

About the state of art that I'm running ahead of Type Theory I have the these question all related between them. Where did the idea of type come from? (It seems that all start when Russell and ...

type-theory history

## Greatest hits from previous weeks:

### If the speed of electrical charge hasn't changed, how have computers become faster?

Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, ...

computer-architecture

### Are there any problems that get easier as they increase in size?

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...

algorithms asymptotics

### How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...

algorithms search-algorithms trees binary-trees search-trees

### Branch and Bound running time and golden ratio

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...

algorithms complexity-theory optimization branch-and-bound