Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 12 years, 2 months
  • Last seen this week
74 votes
4 answers
34k views

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

41 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
3 answers
869 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
565 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
471 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
408 views

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

12 votes
4 answers
402 views

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

11 votes
1 answer
414 views

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

11 votes
5 answers
1k views

Language of the values of an affine function

11 votes
2 answers
256 views

CCS process for a drink dispenser with two different prices

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
625 views

Find out whose turn it is to buy the croissants

8 votes
2 answers
848 views

Detecting overflow in summation

8 votes
3 answers
476 views

ML functions from polymorphic lists to polymorphic lists

5 votes
1 answer
321 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
311 views

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

4 votes
0 answers
153 views

Bignum divisibility algorithm

4 votes
1 answer
365 views

Range of CRC-32

4 votes
3 answers
200 views

Language of the graph of an affine function

4 votes
1 answer
128 views

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