Gilles 'SO- stop being evil''s user avatar
Gilles 'SO- stop being evil''s user avatar
Gilles 'SO- stop being evil''s user avatar
Gilles 'SO- stop being evil'
  • Member for 11 years, 11 months
  • Last seen this week
74 votes
4 answers
33k views

(When) is hash table lookup O(1)?

40 votes
6 answers
10k views

Clock synchronization in a network with asymmetric delays

38 votes
2 answers
2k views

Are generational garbage collectors inherently cache-friendly?

30 votes
2 answers
837 views

Characterization of lambda-terms that have union types

23 votes
2 answers
3k views

Recursive definitions over an inductive type with nested components

21 votes
1 answer
562 views

Ratio of decidable problems

20 votes
3 answers
1k views

Parsing arbitrary context-free grammars, mostly short snippets

19 votes
5 answers
3k views

For what kind of data are hash table operations O(1)?

19 votes
3 answers
2k views

ML function of type 'a -> 'b

19 votes
2 answers
470 views

How many edges can a unipathic graph have?

19 votes
4 answers
5k views

Simulate a fair die with a biased die

17 votes
3 answers
3k views

What are the possible sets of word lengths in a regular language?

15 votes
2 answers
2k views

Number of words of a given length in a regular language

13 votes
1 answer
407 views

Break an authentication protocol based on a pre-shared symmetric key

12 votes
4 answers
381 views

Why store self and parent links (. and ..) in a directory entry?

11 votes
1 answer
407 views

Is a function looking for subsequences of digits of $\pi$ computable?

11 votes
2 answers
249 views

CCS process for a drink dispenser with two different prices

10 votes
5 answers
1k views

Language of the values of an affine function

10 votes
1 answer
1k views

Are two-level schedulers only useful to manage swapping?

9 votes
2 answers
2k views

Round-robin scheduling: allow listing a process multiple times?

9 votes
3 answers
623 views

Find out whose turn it is to buy the croissants

8 votes
2 answers
827 views

Detecting overflow in summation

8 votes
3 answers
471 views

ML functions from polymorphic lists to polymorphic lists

5 votes
1 answer
317 views

termination of two concurrent threads with shared variables

5 votes
1 answer
1k views

Mutex implementation on top of a minimalistic preemptive scheduler

4 votes
0 answers
308 views

Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

4 votes
0 answers
142 views

Bignum divisibility algorithm

4 votes
1 answer
351 views

Range of CRC-32

4 votes
3 answers
200 views

Language of the graph of an affine function

4 votes
1 answer
127 views

Break an authentication protocol based on a pre-shared symmetric key, with message numbers