melonmouse

letztes Jahrdiscuss

Great idea! It also works on the side of the board, I couldn't help building it out: https://onemillionchessboards.com/#4363,6

melonmouse

vor 2 Jahrendiscuss

The linked proof for that median of medians is O(n) feels counterintuitive to me. Here's a (simpler?) alternative.

  T(0) = 0
  T(1) = 1
  T(n) = n + T(n/5) + T(7/10*n)

We want to prove that:

  T(n) ≤ C*n

It is intuitive that T(a+b) ≥ T(a) + T(b), or in other words, T is superadditive. That can be shown by induction:

Induction base: it holds for all a+b < 1, the only case being a=0, b=0:

  T(0+0) = 0 + T(0) + T(0) ≥ T(0) + T(0)

Induction step: suppose it holds for all a+b < k. Let a+b = k.

  T(a+b) = T(k)
         = k + T(k/5) + T(7/10*k)
         ≥ k + T(a/5) + T(b/5) + T(7/10*a) + T(7/10*b)
         = [a + T(a/5) + T(7/10*a)] + [b + T(b/5) + T(7/10*b)]
         = T(a) + T(b)

Because T is superadditive:

  T(n) = n + T(n/5) + T(7/10*n)
       ≤ n + T(n/5 + 7/10*n)
       = n + T(9/10*n)

Now we can apply the master theorem. Or to write out the proof (using a geometric series):

  T(n) ≤ n + T(9/10*n)
       ≤ n * ∑ᵢ₌₀ᶦⁿᶠᶦⁿᶦᵗʸ (9/10)^i
       = n * 1/(1-9/10)
       = 10*n

So, we have shown the algorithm is O(n) with C=10 (or less).

melonmouse

vor 4 Jahrendiscuss

As a joke, I made a webpage where you can do attribution to ALL GitHub repositories:

http://thanksforthecode.com

It scrolls past all the repos movie-credits-style. Doing it that way takes several days! It shows how abstract and absurd giving contribution to such a large body of works is.

melonmouse

vor 4 Jahrendiscuss

Who should we thank for the code written by Copilot? In a way, we should thank everyone in the training data. That includes: everyone with a public Github repository.

Context: https://github.com/usewits/ThanksForTheCode

You can customize it like this: thanksforthecode.com?name=PROJECT_NAME

melonmouse

Submissions

A way to do attribution when using GitHub Copilot

comments