Anyway, that's all for this week. I hope it was worth the wait, and that I convinced you there was so much more fun to have, even in something as simple and heavily taught and studied as sorting #algorithms...

Please write questions and comments below, and see you next week! #weaeklyquiz

11/end

📊 It's Friday here (and Thursday elsewhere for many: you know who you are!), time for a (bi)weₐᵉkly quiz!

Today, let's do something simple, just to get our affairs in order: sorting! #weaeklyquiz

1/5

Alright, that's all for today! I want to apologize for not mentioning Herman Chernoff in Q1, I ran out of poll options space.

Hope you found this #weaeklyquiz enjoyable! as usual, answers and discussion in a few days. Until then, please write comment and questions below!

9/end

📊It's a bit late, but time for our (bi)weekly quiz! Today, a thing I probably* talked about before, but will almost certainly* come very handy at some point, even if it does look a bit random*.

"Low-space Chebyshev!" 🎲 Or: randomness, but cheap. #weaeklyquiz

* Bad puns, everywhere.

1/9

That's all for the week. I hope you enjoyed this — and see you next week for another 📊 biweₑakly quiz on various aspects of theoretical #ComputerScience! #weaeklyquiz

In the meantime, if you have any questions of comment, please reply below ↴

14/end

Answers and discussion for last week's 📊biweₑakly quiz.

(For the quiz itself: https://mathstodon.xyz/@ccanonne/109842825668135282)

Only two questions — let's dive in, first with computing Fibonacci-type numbers!

How hard is it? I give you two initial values, and ask you to give me the n-th value of the sequence. Naively, implementing the recursion the "natural" way will give an exponential-time (in n) algo.

1/ #weaeklyquiz

This week's 📊biweₑakly quiz will be very short, more of a hook than a quiz. A 2-parter, on two different things! #weaeklyquiz

First one: Fibonacci. Recall that the Fibonacci numbers are defined recursively by F₀=F₁=1, and 𝐹ₙ₊₂=𝐹ₙ₊₁+𝐹ₙ
for n≥0.

Now, you can generalize that a little by changing the initial conditions...

1/

That's all for today! If you have any questions, or comments, or feedback, please reply below.

I hope you found this interesting! Remember: we barely scratched the surface, there are connections to many wonderful topics, and the Multiplicative Weights Algorithm (MWU) algorithm is the GOAT. 🐐

See you next week! #weaeklyquiz

19/end

Alright, that's all for today! Hope you enjoyed this #weaeklyquiz. As usual, answers and discussions in ≈3 days.

In the meantime, feel free to comment or ask questions below!

11/end

📊 It's Thurs-Fri-day [citation needed], time for a (bi)weekly #quiz! It's been a while, so let's take it slowly... lest we make mistakes. Perfect segue: today, Online #Learning Mistake Bounds!

What?

Well, you want to learn a classifier, here a function f: {0,1}ⁿ→{0,1}...

1/ #weaeklyquiz

I have been making online #weaeklyquiz in #TheoreticalComputerScience and #maths for more than 3 years now: first on Twitter weekly, now fortnightly both there and here on Mastodon. If you're interested, they're all listed here:
https://ccanonne.github.io/weeklyquiz.html

Answers and discussion for last week's 📊quiz on proper (PAC) learning. Upshot: sometimes #learning is easy... but not if you want to do it properly. #weaeklyquiz

I'll assume you've read the original 🧵 which recalls the def of the PAC (Probably Approximately Learning) framework. If not: it's above! https://mathstodon.xyz/@ccanonne/109560081784732381

1/13