Category Archives: Uncategorized

Solution to STOC 2022 cryptic crossword

Original crossword


Across clues

  • Spoke first at STOC, with handouts. (4)
    SAID = S(TOC) + AID (handouts are a visual aid)
  • Laugh at Romanian jail without pa[r]king for Ford, say. (8)
    HARRISON (Ford, an actor) = HA + R + PRISON – P (= parking)
  • Danes maybe cycling for cake. (7)
    ECLAIR = CLAIRE (Danes, an actress) rotated = “cycling”. Difficult clue.
  • Squared dodecahedron contains root. (4)
    EDDO (a plant). Contained in … ED DO…
  • With competence, like Niels Henrik? (4)
    ABLY, wordplay on “like [mathematician Niels Henrik] Abel”.
  • Trouble sounds like beer. (3)
    AIL (vb.), homophone of ALE.
  • L[a]nsky impales most of suricate with tip of yari. (5)
    MEYER (Lansky, a mobster) = ME(Y)ER[CAT]
  • Taster confused desserts. (6)
    TREATS = TASTER*
  • Programmer is a father. (3)
    ADA (Lovelace) = A + DA (= father)
  • Some alternating state. (3)
    ANY = A (as in complexity class AC) + N.Y.
  • Limaye without an almond, say. (3)
    NUT = NUTAN – AN
  • Bullet point keeps her in France. (6)
    PELLET = PT (= point, abbrev.) around ELLE (her, Fr.)
  • Assholes insert Landau symbol into abstracts after second review. (7)
    EGOISTS = E (2nd letter in REVIEW) + G[O]ISTS
  • Logic from the Horn of Africa. (2)
    SO = second order logic, also abbreviation of Somalia
  • Like, with probability 1. (2)
    AS = like = almost surely
  • Complex zero first encountered by lady friend. (7)
    OEDIPAL (a type of complex) = O + E + DI + PAL
  • Partly hesitant at ternary bit. (6)
    TATTER, hidden word.
  • Supporting structure turns semi-liquid. (3)
    GEL = LEG backward (= turned)
  • Everything Arthur left to end of protocol. (3)
    ALL = A[rthur] + L[eft] + [protoco]L
  • Unbounded fan-in polylogarithmic depth circuit model is fake. (3)
    ACT = AC (complexity class) + T (a Ford model)
  • Maybe Tracey’s luxury car runs out of [p]olynomial time. (6)
    ULLMAN (an actress) = PULLMAN – P
  • Pin[k] dress you ordered last Friday initially returned. (5)
    FLOYD (a band), backwards acrostic (“initially”, “returned”)
  • Relationship uncovered travel document. (2-1)
    IS-A (a UML relation) = [v]ISA
  • Be certain about last Pfaffian orientation. (4)
    BENT = BE[N]T
  • Detect conference cost size. (4)
    FEEL = FEE + L
  • Matching for horses? (6)
    STABLE (a type of matching, and where horses stay)
  • Collect information about first woman embracing the state. (8)
    RETRIEVE = RE (= about) + T(he) + RI (= Rhode Island, a US state) + EVE
  • Central to better AI data storage technology. (4)
    RAID, hidden in “…r AI d…”

Down clues

  • Safer testable codes? (4, 4)
    SEAT BELT = TESTABLE* (code is an iffy anagram indicator). Better clue in hindsight would have been “Locally testable codes are a buzzword. (3)” for ECO (hidden).
  • Maybe Arthur without Merlin is even worse … (5)
    ILLER = (Arthur) MILLER – M
  • definition of time than deterministic Arthur–Yaroslav. (3)
    DAY = D + A +Y (a complexity class abbreviations)
  • Cover us about first sign of integrality gap. (6)
    HIATUS = HAT + US around I(ntegrality)
  • Publish, but not ultimately sure about polynomial-time recurrence. (7)
    RELAPSE = RELEASE – (sur)E holding P
  • 49 subsets the setter handles. (6)
    IDEALS = stable subsets = I + DEALS
  • Food at indiscrete algorithms conference held around Yale’s entrance. (4)
    SOYA = SODA – D (SODA without discrete) + Y
  • Revealed no deep confusion. (6)
    OPENED = NODEEP*
  • Not having an arbitrary number of children. (4)
    NARY = N-ARY, double definition
  • In Related Work section, over-inflate scientific contribution of Rabin in data structure. (4)
    BRAG = R (Rabin abbreviated as in RSA) inside BAG
  • Iceland exists. (2)
    IS, double definition
  • Cuckoo hashing incurs five seconds. (3)
    ANI = second letters of “hAshing iNcurs fIve”
  • Function of what is owed, I hear. (3)
    DET = homophone of “debt”.
  • Cut off measure of computer performance, not taking sides. (3)
    LOP = [F]LOP[S]
  • Two sigmas above the mean, or about ten delta. (8)
    TALENTED = TENDELTA* (“about” is the anagram indicator)
  • Coattail at breakfast? (3)
    OAT, tail of COAT, a breakfast cereal.
  • Twisted polygon in tessellation supporting functors. (7)
    TORTILE = TOR (functor) above TILE (a polygon in a tessellation).
  • Tree parent has two left edges. (6)
    MALLEE = MA + L + L (left, twice) + E + E (edge set, twice)
  • Temporary visitor betrays topless arrangement. (6)
    STAYER = [B]ETRAYS*
  • Trigonometric function is pretty dry. (3)
    SEC, double definition
  • Denounce operator in vector analysis and put it away. (6)
    DELETE = DEL + ATE (vb., past tense)
  • 49 litres of sick. (3)
    ILL = IL (roman numerals for 49) + L
  • Turing machine’s second network. (4)
    ALAN = A (second letter in MACHINE) + LAN
  • Academic degree supports unlimited games for simple minds in the US. (5)
    AMEBA (US spelling of AMOEBA) = [G]AME[S] + BA
  • Open access journal rejected final proof in distance estimate. (4)
    AFAR = AJAR – J + F (last letter of PROOF).
  • Conceal often sample space. (4)
    LOFT, sample of “…L OFT…”
  • Objectively, we are American. (2)
    US = objective form of “we”
  • It negates where you drink. (3)
    BAR, double definition, the bar us used to negate a variable

Special instructions

The letters missing from 4 of the clues, indicated by […] above, are K A R P, a homophone of CARP (“sounds like nitpicking”). The answers to those clues are HARRISON, MEYER, ULLMAN, and FLOYD. The six members of the first STOC programme committee were Harrison, Meyer, Ullman, Floyd, Karp, and Hartmanis. The answer to the entire puzzle is therefore HARTMANIS, additionally indicated as “confused with H(ungarian) MARTIANS” = HMARTIANS*.

Assholes insert Landau symbol into abstracts after second review (7)

Themed cryptic crossword I compiled (over two fun evenings) for the STOC 2022 conference. Lots of short words, to make it super-friendly.

Special instructions. Four of six people that form a group related to our meeting appear in the grid, clued for their namesakes. Alas, each of these clues is missing a letter. This sound like nit-picking, but the letters form the name of the fifth person. The sixth person of the group, not to be confused with the Hungarian “Martians,” is the puzzle answer.

Across
1. Spoke first at STOC, with handouts. (4)
4. Laugh at Romanian jail without paking for Ford, say. (8)
10. Danes maybe cycling for cake. (7)
11. Squared dodecahedron contains root. (4)
12. With competence, like Niels Henrik? (4)
14. Trouble sounds like beer. (3)
16. Lnsky impales most of suricate with tip of yari. (5)
17. Taster confused desserts. (6)
19. Programmer is a father. (3)
21. Some alternating state. (3)
22. Limaye without an almond, say. (3)
23. Bullet point keeps her in France. (6)
26. Assholes insert Landau symbol into abstracts after second review. (7)
29. Logic from the Horn of Africa. (2)
31. Like, with probability 1. (2)
34. Complex zero first encountered by lady friend. (7)
38. Partly hesitant at ternary bit. (6)
39. Supporting structure turns semi-liquid. (3)
41. Everything Arthur left to end of protocol. (3)
43. Unbounded fan-in polylogarithmic depth circuit model is fake. (3)
44. Maybe Tracey’s luxury car runs out of olynomial time. (6)
45. Pin dress you ordered last Friday initially returned. (5)
46. Relationship uncovered travel document. (2-1)
47. Be certain about last Pfaffian orientation. (4)
48. Detect conference cost size. (3)
49. Matching for horses? (6)
50. Collect information about first woman embracing the state. (8)
51. Central to better AI data storage technology. (4) 

Down
1. Safer testable codes? (4, 4)
2. Maybe Arthur without Merlin is even worse … (5)
3. … definition of time than deterministic Arthur–Yaroslav. (3)
4. Cover us about first sign of integrality gap. (6)
5. Publish, but not ultimately sure about polynomial-time recurrence. (7)
6. 49 subsets the setter handles. (6)
7. Food at indiscrete algorithms conference held around Yale’s entrance. (4)
8. Revealed no deep confusion. (6)
9. Not having an arbitrary number of children. (4)
13. In Related Work section, over-inflate scientific contribution of Rabin in data structure. (4)
15. Iceland exists. (2)
18. Cuckoo hashing incurs five seconds. (3)
20. Function of what is owed, I hear. (3)
24. Cut off measure of computer performance, not taking sides. (3)
25. Two sigmas above the mean, or about ten delta. (8)
27. Coattail at breakfast? (3)
28. Twisted polygon in tessellation supporting functors. (7)
30. Tree parent has two left edges. (6)
32. Temporary visitor betrays topless arrangement. (6)
33. Trigonometric function is pretty dry. (3)
35. Denounce operator in vector analysis and put it away. (6)
36. 49 litres of sick. (3)
37. Turing machine’s second network. (4)
40. Academic degree supports unlimited games for simple minds in the US. (5)
41. Open access journal rejected final proof in distance estimate. (4)
42. Conceal often sample space. (4)
44. Objectively, we are American. (2)
47. It negates where you drink. (3) 

Surveillance paternalism

At a conference in Norway last week I learned new word coined by Tore Burheim, IT Director at Bergen University: overvåkningsomsorg. It’s a variation of Shoshana Zuboff’s brilliant word, overvåkningskapitalism, surveillance capitalism.

There is no perfect translation into English: omsorg is care, so the direct translation would be surveillance care, but that doesn’t quite work. Health care is “taking care of health”. Surveillance care would be “taking care of surveillance”. That’s not what is meant. Overvåkningsomsorg is the use of surveillance for ostensibly benevolent reaons, it is surveillance-for-care: A Huxleyan or Benthamian society where the system puts you under surveillance because it cares for you. Where Zuboff’s dystopia is easy to dislike (who likes surveillance? who actually likes capitalism?), overvåkningsomsorg is a delicious oxymoron.

I propose surveillance paternalism as the English translation, even though it’s not perfect. (“Paternalism” is not as warm as “care”.) Surveillance benevolence? “The age of benevolent surveillance”?) Danish overvågningsomsorg and Swedish övervakningsomsorg, are easy. For German, I propose Überwachungsfürsorge or maybe even Überwachungsbarmherzigkeit or something like Wohlfahrtsüberwachung.

Anyway, great word and great book title. Somebody should write this.

EATCS Council 2021 Election Statement

I am delighted to be nominated for the EATCS Council, on which I have served for a full term now.

ICALP

Looking back at my election statement from 2017, it is dominated by my ambition to increase the quality of ICALP, primarily by giving ICALP a steering committee.

I am happy that I can just write DONE next to this action point, see https://eatcs.org/index.php/committees. The ICALP steering committee turned out to be a complete success. I am extremely proud of what we’ve done with ICALP, including reacting very quickly to the COVID pandemic in 2019–2020. Mostly the success is due to the incredibly competent and pleasant people working inside the committee (ably headed by Anca Muscholl), and the amazing atmosphere that continues to permeate the entire TCS community.

Publication models

I worry about the publication and review model in the sciences, including in TCS, and have spent a lot of time involved in the advisory board of TheoretiCS, tirelessly headed by Thomas Schwentick. TheoretiCS will be an open access journal of very high quality covering all of TCS; having the journal tightly integrated into the community is a core value, and I serve as the representative of ICALP.

This has been very long process that I am extremely excited about, and I’m proud of what we’ve done so far.

TCS and the sciences

My 2017 election statement includes a passage about “ how the mathematical discipline of theoretical computer science can interact with its surroundings”.

This remains a central question for me, but a much harder one than helping to build steering committees or journals. I had the honour of serving as chair of the Swedish Research Council’s panel for (all of) computer science in 2019, 2020, and 2021, which has solidified by understanding of both CS and the role of TCS inside CS.

Core principles

I am a signatory of the open letter to CACM about core principles of scientific inquiry and stand by the values elucidated therein. I am cognisant of the fact that academia, including TCS, are divided on this issue (see the excellent rebuttal of our position by David Karger), and want to make my position clear as part of this election statement.

Hjælp til projektopgave om kunstig intelligens, overvågning, science fiction, algoritmer og det digitale samfund

Kære projektgruppe af elever på skole X.

I har været så søde at spørge mig om hjælp til en projektopgave, og har sendt mig en masse gode og relevante spørgsmål om noget, jeg faktisk ved noget om. Dejligt.

Undskyld

Desværre har jeg ikke tid til at svare jer. Det er der mindst tre grunde til.

  1. Jeres spørgsmål er alt for brede. »Hvad er problemerne med…« eller lignende vil, når I spørger en akademiker af en vis lødighed, afføde en alenlang redegørelse. Det ville tage mig 1 år og 500 sider at svare ordentligt på den slags spørgsmål. Ganske rigtigt er det netop indholdet til den bog, jeg altid gerne ville have skrevet. Men jeg har altså ikke skrevet den.
    Hvis I spurgte en politiker, så ville vedkommende have et færdig, kort og forberedt svar. Men jeg er ikke politiker. Det er deres opgave. Min er en anden.
    Journalister kan forresten heller ikke stille gode spørgsmål til akademikere, så I er i meget godt selskab.
  2. Jeg kender ikke jeres baggrund. Jeg er god til at forklare, men jeg kan ikke forklare noget potentielt teknisk uden at vide, hvad I forstår. Bør jeg begynde med 50 sider om grundlæggende it eller ej? Kan I programmere? Ved I, hvad en algoritme er? Jeg aner det ikke, og hvis jeg skal svare ordentligt, skal jeg først få grundlaget på plads.
    Journalister kan heller ikke finde ud af dette.
  3. Selv hvis I var i stand til at formulere klare og præcise spørgsmål, som jeg kunne svare på ved blot at bruge en time eller to, så ville jeg stadig ikke have tid til det. I er nemlig rigtig mange og skriver tydeligvis projektopgaver på de samme tidspunkter af året.

Information

Hvad kan I så gøre?

Sommetider deltager jeg i offentligheden i samtaler eller holder foredrag om de emner, som I spørger om. Dem er I meget velkomne til at kigge på, og citere mig for det sagte. Kig især på de lange samtaler på Cast IT.

Der er meget mere, inklusive debatartikler i dagblade, på https://thorehusfeldt.com/appearances/ .

ITU at NCPC 2019 (5 October)

This page summarises the preparation for ITU students for the Nordic Collegiate Programming Competition (»Danmarksmesterskaberne i Programmering«) for 2019

The Nordic Collegiate Programming Competition (NCPC) is a programming and problem solving event held every year. Teams of 3 programmers try to solve as many problems as they can (from a list of a dozen or so tasks) in five hours. The NCPC is open to all, but in order to compete in the “official” part (placing in the national championship or proceeding to the European or world finals), you need to be a university student, and you need to register in advance and participate on site. That is also the most fun and satisfying experience.

How difficult is this?

This is for you. If you have programming skills corresponding to a single ITU introductory programming course, you should be able to solve 1–2 problems. You should feel very good about that. If you have even taken an introductory algorithms class (or other problem solving class) then maybe 3–4 questions are within reach, which puts you very high on the list. You can look at last years’ standing for all of Denmark; as you can see this event is highly welcoming of newcomers. (Don’t get distracted by the monstrous performances of the top participants; think of it like running the Berlin marathon — you don’t feel bad about being slower than the world record holder in the same race).

The event (»Danmarksmesterskaberne i programmering«)

The Danish events label themselves Danish Championships, and typically take place in Aarhus, Odense, and Copenhagen. ITU Students are encouraged to participate in the Copenhagen event hosted at KU, and supported by NetCompany and JobIndex.

If you want some inspiration, here is a hyggelig film about the 2016 event:

You can also look at the

  • web site for NCPC 2018 (last year), where you can see the team names and how well they did (under Final standings), read the problems, and look at the slides explaining their solutions. As you can see, there were 0 ITU teams. We want to change this.

Preparation at ITU

You should totally participate. If you’re on your 2nd year of studies and enjoy programming, problem solving, and collaborating, this is a brilliant, engaging, and intellectually and socially satisfying way to improve your skills – it is also great team building. And boy, does it look good on your cv.

  • Create a team. You want to create a team, maximally (and preferably) of 3 people, and find a suitably painful team name. If you don’t yet have a team, we will probably be able to create some during September. If you want to seriously compete, you need to read the rules for participating in the official championships, see the event web site. Or you can be like me and just participate for the fun of it. Align your expectations with your friends.
  • Chat channel: https://talk.itu.dk/channel/dmprog-ncpc-2019 : a chat channel at talk.itu.dk for this event. If you’re an ITU student, you already have an account. We’ll use this to communicate about pizza, problems, teams formation, news, etc.
  • NCPC Coaching Fridays at ITU at 15: Most Fridays at 15–16, starting 30 August, one of the ITU teachers will be available (room to be announced) for some coaching. Among other things, we’ll go through last year’s NCPC problems, point to other good material, discuss strategy and preparation. See the bottom of this page for an overview.
  • Bjarki’s course. Bjarki Ágúst Guðmundsson maintains a very ambitious course about competitive programming at https://algo.is. Includes links to relevant open Kattis exercises. No matter where you are in your skill development, there should be a module or two for you that makes you better.
  • Johan’s book. Johan Sannemo, Principles of algorithmic problem solving. Similar to Bjarki’s course, slightly different format and focus.
  • Grind. Log on to open.kattis.com. Sort the problems by difficulty and solve them from the top. Or search for NCPC to find old contest problems.
  • Teambuild. Do some programming in your team in order to understand your group’s dynamics. (The contest is with a single computer, so only one person at a time is typically typing.) Agree on one or two languages. (Python 2 and Java both are good choices.)
  • Select written material. You can bring any written material. So: Learn not to rely on on-line material (you can’t google stackoverflow during the contests) and find out which written you actually need and can navigate (say, a programming language reference, but not all 4 volumes of the Art of Computer Programming). You can even maintain your own evolving document, with often-forgotten code snippets, standard templates, hints to yourself, your editor configuration, soothing picture of a kitten, etc. Here’s an example from a very experienced partipant (Måns Magnusson), heavily focussing on algorithms: https://github.com/exoji2e/notebook.
  • Three hour warm-up event Friday 20 September 16-19. ITU will host a 3 hour warm-up event two weeks before NCPC at https://open.kattis.com/contests/ne66md. The main goal is to give you a chance to experience a mini-contest as a team (for instance, who does the typing?) Register informally at talk.itu.dk/ncpc , and the Computer Science Department will provide free food (probably sandwiches and soft drinks). Brief intro at 15:45 in 2A03, we’ve reserved the tables on the 2nd floor (2R01, etc.) during event. Last-minute drop-ins welcome.
  • Five hour warm-up event Saturday 28 September 11-16 . Exactly one week before the main event. Hosted by the Kattis people at https://open.kattis.com/contests/ncpc2019warmup.

Coaching/Lectures

I’ll give some extra lectures in various formats. The expected skill set that of 2nd year Software students, but everybody is welcome.

  • 30 Aug, 13-14, repeated at 16-17. 2A08. Repeated at 16-17 same day. (Thore). Welcome. Kattis basics, NCPC basics, tips and tricks, questions and answers. Solution of NCPC 2018 problem B–babybites (where Thore’s team was 1st last year!) and C–codecleanups.
  • 6 Sep, 15-16. 2A08. (Thore) H–houselawn, greedy algorithms, I-intergalactic bidding.
  • 13 Sep, 15-16. 2A08. (Thore) Graph problems. deliverydelays (very hard! we didn’t manage to solve it)
  • (20 Sep): No coaching, since there’s a warm-up event. at 16.
  • 24 Sep, 8–10, Aud5. Dynamic programming I. Part of the MSc Algorithm Design course. Everybody welcome.
  • 1 Oct, 8–10, Aud5. Dynamic programming II. Part of the MSc Algorithm Design course. Everybody welcome.

Worrying about superintelligence is like worrying about overpopulation on the Sun.

Worrying about artificial intelligence is like worrying about overpopulation in Bangladesh.

Will Code for Drinks @ Scrollbar, 2nd edition

On Friday 12 April, we ran another social coding event in the IT University of Copenhagen Friday bar ScrollBar. “We” is two colleagues (Martin Aumüller and Troels Bjerre Lund) and myself. This is the second time we try this, and it was a big success again. More than 50 teams participated, more than 40 solved at least 3 problems(!), and two of the ITU student teams solved 5 problems(!). The atmosphere was just great. Scrollbar was filled with teams of people gathered around laptops, paper, and drinks – typing, laughing, smiling, arguing, drinking, fist-pumping, thinking, and snogging.

The target audience is 1st years students on ITU’s various programmes, and that audience has matured a lot since the Fall. We decided to make the selection of problems a lot harder, with 6 problems (compared to 4 in the Fall), one of them pretty challenging.

We used the Kattis problem to host the event, using publicly available problems. The even site is https://open.kattis.com/contests/fwmxyb, and the problems were Križaljka, Pig Latin,Opening Ceremony, Datum, Entering the Time, and Worst Weather Ever.

In the organising group, we spend a lot of time on problem selection, and I’m again very happy with the resulting set. All the problems were immediately appealing, as well as easy to debug locally. (You can quickly make your own inputs for many of them, and verify your implementation’s answer with your own eyes.) Most of these problems require zero algorithmic insight at all and can be solved in interpreted Python 3 within the time limit. For one problem you need to sort, and another uses binary search. Except for one problem, all were easy-to-medium and don’t involve a lot of code. (My own solutions require 3, 9, 15, 15, 43, and 45 lines of python code.) For most of the problems, it’s clear “what to do,” but there are still some design choices to make, a lot of edge cases to avoid or handle, and a tiny bit of problem solving.

After a lot of soul-searching, we added a single hard problem, F, in order to keep even the experts among the audience busy – the event was graced by the presence of some very, very experienced competitive programmers. There was some good-natured sniping among these groups: the expected presence of an expert team from Sweden led to the creation of a Danish-German team of ITU employees named for Ulrik Gyldenløve, who fought victoriously against the Swedes in 17th century.

Scoreboard Hacking

To maintain the social aspect of the event, we decided to stick with a common scoreboard projected against the wall of the bar. It provides some kind of shared visual presence even for the non-coding guests at the bar. For this, we managed to implement one of the ideas from the Fall: the non-competitive ordering.

Here’s how the final standings of the event look using the standard Kattis scoreboard:

The standard Kattis scoreboard is sorted by number of solved problems; ties are broken on total time; the board also shows failed attempts.

We worry a lot about de-emphasizing the competitive aspect of the event, which lead us to rethink the scoreboard design. “Our” event is about people working in teams and solving problems. Once this is realised, the the information design is clear. We don’t want the board to include the team rank, or various timings, nor the documentation of failure. Instead, the board is about teams and solved problems, as well as the overall timer.

The transformed Will Code for Drinks-scoreboard.

“Our” board is sorted by most recent solve, so that every team gets a brief moment at the top. Team members could proudly walk up to the bar, announce their team name which was shown at the top of the score board, and receive their free drink. This worked spectacularly; people were sooo happy.

Hiding the unwanted table rows and re-ordering the board required nontrivial javascript-hacking using the Tampermonkey userscript manager in the Firefox web browser, mostly done by Tobias Christiani. (We discussed other ways of implementing the idea, but this one turned out to be easiest and least intrusive.) While we were at it, we changed some of the CSS style information to keep the design in sync with ScrollBar’s visual identity. It looks nicer, and it is nicer than the original.

Next event?

The next Will Code for Drinks will certainly happen in the Fall of 2019. I remain frustrated about how hard it is to attract inexperienced programmers – my ambition is to make 1st-year students aware of how much they can already do with their skill set. Martin, Troels, and I do provide help with problem solving and debugging, wearing silly hats. This works well for those inexperienced programmers who actually show up to the event, but I would like there to be more than a few handful of those.

One idea is to arrange a separate event specifically aimed at 1st-semester students, and advertise it directly to that population. “Will Hello World for Drinks?” in October, only 1st year students can register, lots of TA support? Followed by standard “Will Code for Drinks” for everybody in late November? Or is this exactly wrong because of the separation? Talk to me if you have an idea. Buy me a beer first.

Will Code for Drinks @ Scrollbar 2018

Homemade poster for the event

I am foremost a teacher, and I care a lot about introductory programming, computational thinking, algorithms, and the social environment of a university.

As an experiment in “social coding,” we implemented an event called “Will Code for Drinks @ Scrollbar” in the Friday bar at IT University of Copenhagen on 23 November 2018. The basic idea is to get beginning programmers—this includes 1st semester students and professors—together for a few hours, solve some well-defined programming exercises, and get a drink for each solved exercise.

Preparation

The idea was born over a couple of lunches with colleagues, and thanks to the enthusiasm of Martin Aumüller and Troels Lund it quickly developed momentum.

The platform we used for this is Kattis (open.kattis.com), which is a well-working system developed for programming competitions. Kattis comes with thousands of extremely well-done exercises, a reliable server with an accessible web interface, and very simple procedures for registering individuals, forming teams, and hosting contests.

Preparation included:

  1. Establishing rapport with the ITU Friday bar—a student-run organisation that hosts a social event every Friday afternoon during the semester. They loved the idea, and we were able to find a free date where no other ScrollBar event or theme (Halloween) was already planned, and no other ITU event (Board Game night!) was scheduled elsewhere in the house by one of the many other social committees.
  2. Learning Kattis and solving dozens of exercises there in order to find a selection of the event. The idea was that students with very little programming experience were supposed to at least solve one exercise, possibly with help, during the event. The selection we ended up with were Baby Bites, Spavanac, the lovely Trik, and the somewhat harder Bank Queue. We figured that 3 drinks are enough for anybody, and wanted a more challenging problem to keep everybody engaged during the event.
  3. Spreading the word among first-year programming teachers and their students. During the weeks up the event, our enthusiasm infected several students, who registered on Kattis and started grinding in preparation.
  4. Decisions, decisions… should the event be called “Will Code for Beer” instead? Drink or drinks? How competitive should we make it?
  5. Creating a visual identity. My original plan was to use a lot of images of various people holding cardboard “Will Code for Drinks” signs. In the end, it was too much work (after talking to the communications department about GDPR), and I cobbled together a clean visual identity on my computer in a couple of minutes. Another reason to reject the hobo-theme is that it possibly repels students who are concerned about appearances.
  6. Find some way to pay for the resulting bar tab, and that will be acceptable to the Accounting and Finances section.
  7. Design and order caps so that assistants (Martin, Troels, and myself) would be visible during the contest. Alas, the caps were not delivered on time.
An early experiment in developing a visual identity for the event. In the end, I rejected this direction, despite the great resonance among students and colleagues, for purely aesthetic reasons.

During the event

The event was “just” a contest on the open Kattis server  https://open.kattis.com/contests/f4ktq9

The moment the contest started at 15:30, we had most of the students in the same room adjacent to the bar, so we could help with Kattis registration, logging in, reading from standard input, etc. After that, participants slowly moved into ScrollBar and the ITU Atrium. We kept ourselves visible and available, and helped with programming and problem solving.

After

I spent a few hours writing emails to individual groups that I had talked to during the contest, explaining other approaches to specific tasks. Then I sent a brief thank-you note to all participants that I could identify and invited feed-back and suggestions for improvement. This was quite boring, I had to identify partipants  who had registered under their own name on Kattis and had a name I could uniquely find in the ITU student roster.

Evaluation

This was supposed to be a test run, and I had hoped for 5 teams of students. In reality, slightly over 50 teams registered, with 130 participants. Stunning success!

Will Code for Drinks @ ScrollBar 2018 in full activity. Photo by Troels Lund.

Of the participants I was able to identify, 48 are first-semester students. These were the intended target group. More that half of the students are from the educations hosted by the Computer Science department, but all of ITU’s student populations were present. 45 teams solved at least one problem, 35 teams solved three. 10 teams solved all four problems; this includes the teams consisting of faculty members and Ph.D. students. Phew!

In the end, the “damage” was 183 beers, 80 cocktails, and 8 soft drinks. In total, students solved 132 programming exercises in 2.5 hours, and fun was had. As a teacher, I couldn’t be happier.

In just a few weeks, ITU is now the second-largest and second-ranked Danish uni on Kattis. Aarhus is still way ahead.

Future

I would love to make this event even more social and less competitive. An idea that came up during the contest was to have the scoreboard ranked by “most recent solve” rather than “number of solves”. That way, every team gets to be at the top at least once. Removing the scoreboard entirely is another option, but that removes the shared digital forum – in effect, all the teams would exist in their own little bubble.

The best idea we’ve come up with in this vein is to couple the teams with music playlists. Then the current leader (i.e., the team that most recently solved a problem) would decide which music is played in the bar. “Will Code for Drinks and Music” or “Will Code for Drinks and Rick Roll” or something. To make this work, we need a more advanced registration system, and we’d need to scrape the standings off the Kattis server.  All doable.

Another improvement would be to have our own, ITU- or ScrollBar-branded problems instead of relying on (often well-known) problems from the Kattis pool. We could switch to another system than Kattis (or build our own) but that is a lot of work, and there is intrinsic value in incentivising students to register on Kattis.

No matter the form, we will certainly do this again in Spring 2019!

A Glimpse of Algorithmic Fairness

Workshop presentation at Ethical, legal & social consequences of artificial intelligence, Network for Artificial Intelligence and Machine Learning at Lund University (AIML@LU), Lund University, 22 November 2018.

Abstract

Several recent results in algorithms address questions of algorithmic fairness — how can fairness be axiomatised and measured, to which extent can bias in data capture or decision making be identified and remedied, how can different conceptualisations of fairness be aligned, which ones can be simultaneously satisfied. What can be done, and what are the logical and computational limits?

I give a very brief overview of some recent results in the field aimed at an audience assumed to be innocent of algorithmic thinking. The presentation includes a brief description of the location of the field algorithms among other disciplines, and the mindset of algorithmic or computational thinking. The talk includes pretty shapes that move about in order to communicate some intuition about the results, but is otherwise unapologetic about the fact that the arguments are ultimately formal and precise, which is important for addressing fairness in a transparent and accountable fashion.

References

Toon Calders, Sicco Verwer: Three naive Bayes approaches for discrimination-free classification. Data Min. Knowl. Discov. 21(2): 277-292 (2010). [PDF at author web page]

Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. [arXiv 1703.00056]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
Fairness through awareness. Innovations in Theoretical Computer Science 2012: 214-226. [arXiv 1104:3913]

Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, Suresh Venkatasubramanian: Certifying and Removing Disparate Impact. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015. [arXiv 1412.3756]

Sorelle A. Friedler, Carlos Scheidegger, Suresh Venkatasubramanian: On the (im)possibility of fairness. [arXiv:1609.07236]

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum: Multicalibration: Calibration for the (Computationally-Identifiable) Masses. Int. Conf. Machine Learning 2018: 1944-1953. [Proceedings PDF]

Jon M. Kleinberg, Sendhil Mullainathan, Manish Raghavan: Inherent Trade-Offs in the Fair Determination of Risk Scores. Innovations in Theoretical Computer Science 2017: 43:1-43:23. [arXiv 1609:05807]


(The image at the top, the title slide of my presentation, shows a masterpiece of the early Renaissance, Fra Angelico’s The Last Judgement (ca. 1430), illustrating a binary classifier with perfect data access and unlimited computational power.)