Author Archives: thorehusfeldt

False Friends in Your Algorithms Course

Your first algorithms course is not easy.

The words are not the hardest part, but from years of teaching this material we have learned that words do sometimes invite enormous misunderstandings. You can be led down a garden path by a fancy word that you learned, only to discover that it means something else this week.

Luckily, the terminological issue is relatively easy to remedy by just writing it down and raising awareness. Here are some of the false friends I am aware of. (Do contact me with more examples, in particular ones that actually confused you.)


A stack is a specific abstract data type, see Stack (abstract data type). When we say “stack” in an algorithms course, we almost always mean the data type.

However, the word “stack” is also a specific data structure in the runtime system of an active computer programme, see Call stack, also called execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to just “the stack”.

When we talk about recursion and its implementation in our course, some people may say “the stack,” rather than “the call stack” or some more unambigous term. For instance, you may overhear “in your graph exploration programme, you wouldn’t have run out of stack space if you had used a stack.” The first stack is the recursion stack, the other isn’t.

The (call) stack is a stack (abstract data type), but not vice versa.


A heap is a specific data structure that implements the abstract data type priority queue, see Heap (data structure). When we say “heap” in an algorithms course, we almost always mean the data type.

Howver, the word “heap” is also used to refer to a specific chunk of dynamically allocated memory, see Dynamic memory allocation.
We almost never use that term in the present course, but you may come across it in relation to data structures in other material, for instance about allocating linked lists and other dynamic data structures.

The (memory) heap is not a heap data structure.


In mathematics, a map is a “function,” a something that connects (“maps”) things from one set to another, see Map (mathematics)). The Danish word is afbildning.

Some programming languages use term to refer to what we call “symbol table” in this course: a something that maps “keys” to “values”, see Map (computer science).
Other words are associative array or dictionary.
An example is Java’s interface java.util.Map that describes an abstract data type for a symbol table, and is famously implemented in the data structures java.util.HashMap.

However, in other programming languages, map is used for the application of a function to a sequence, see Map (higher order function)) This is true for Python. (Python instead used “dictionary”, dict, for its symbol tables.)

So in Python, map is a higher-order function, in Java, Map it is an interface. These things have nothing to do with each other.

One can try to stick to the term symbol table for the abstract data type.

running time / runtime

Running time is the time to execute an algorithm, synonymous with Time complexity.
It is given as a growth rate in terms of a size measure, using some asympototic notation. We can say “the running time of merge sort is O(n log n)”.

We may also use it to refer to the actual execution time (in seconds) of a concrete piece of code.
We can then say “the execution time for ex8.cpp was 2.4 seconds on input”.

In contrast, the runtime system is the environment in which a programme is executed, and runtime) as part of a program’s life cycle. We talk about runtime errors if a programme fails during execution, and may want to distinguish between checking array index-out-of-bounds error at runtime or compile-time.
Neither of these concepts have to do with running time.


Graph means two things in algorithms and discrete mathematics; they have nothing in common.

Most of the time we mean a combinatorial structure that models a pairwise relation, see
Graph (discrete mathematics))
In this context, “graph” is a synonym of “network”.

It may also mean graph of a function, which is what you have learned in school. Such a graph is either a set of points or the drawing of these points. This is what we mean when we say “graph of a function,” or “draw the running time as a graph.”


“Random” means two different things: stochastic (as in throwing dice or drawing lots) or unpredictable (as in arbitrary). These are very different and your instructor will be very cross with you if should mix them up.

When, for instance, we pick the split element in quicksort randomly, we mean “uniformly at random and independently from previous random choices.” It’s very important that you don’t misread this as “arbitrary”: if the split element in quicksort is picked arbitrarily (say, by your worst enemy), the analysis breaks down and quicksort becomes slowsort.

Of course, when we talk about the very important random access model of computation (RAM), the word “random” means arbitrary/unconstrained/unpredictable. Here, it is important that accessing memory location M[i] takes constant time, no matter how i was chosen. Even your worst enemy wouldn’t be able to make the RAM spend more than constant time. So: the word random does not mean that the constant-time bound holds only for random-in-the-stochastic sense access, or (God forbid) that the result of M[i] is random or even arbitrary.

I believe that “random” only means “decidedly nonrandom” when we’re talking about the random access machine, so you’re probably safe in interpreting it as “taken from a probability distribution, probably uniformly and independently unless something else is said” in all other contexts.


A node is a localised swelling in a network, it is a synonym of “knot,” both from the Latin nodus.
Think of a fisherman’s net.

In an algorithms course, node means “basic unit of a data structure”, see Node computer science).
It often appears explicitly in an implementation, typically as an object of class Node, and sometimes only implictly as a useful abstraction.

We will also use node for the fundamental unit of a graph, see
Vertex). We will try to stick to “vertex” for such nodes, but the terms are synonyms and you will meet node-as-vertex in many places.
Another good word for node-as-vertex is point.

Perhaps confusingly, when you construct the data structure to solve a basic graph problem, typically you don’t use a node (data structure) for a node (combinatorial object).


Linear means at least two, completely unrelated things.
In “linear programming”, the word is used as in calculus (linear function), to highlight the fact that the variable has degree 1 (rather than appearing squared.)

In “linear probing,” a collosion strategy employed by hash tables, it just means “one-after-the-other”.


In “introduction to programming,” or “computer programming” or “Java programming,” the word programming means “writing instructions”, typically using a programming language.
In “linear programming,” “quadratic programming,” or “dynamic programming,” the word programming just means planning or scheduling, as in “TV programming” or “theatre programming,” and could be usefully replaced with scheduling or optimisation almost everywhere it occurs.
As a particular confusion, constructing a linear program (or “programme” if you’re fancy), means setting up a bunch of constraints (these constraints are linear functions), but does not involve writing the (computer program) to solve those constraints. You can write a Java program to solve a linear program.


Dynamic means “the entries or instance can change” or “the entries are never recomputed”.
In the former sense, it is used in dynamic array (an array whose length can change – all arrays are mutable, so in that sense they’re all dynamic) or dynamic graph algorithm (an algorithm for a graph that undergoes changes.) In the latter sense it is used in dynamic programming, a specific algorithmic optimisation strategy, where the whole points was that functions without side effects never change, so we might as well store them is a static table and never change them.

The history of the term “dynamic programming” is documented by Bellman and quite entertaining.


Asymptotic means “never falling together”, and the term draws attention to the fact that one function is the asymptote of another by virtue of the two never touching. This is typically a topic of high school maths, see asymptote. In the analysis of algorithms, “asymptotic” almost always just means “for large values of the input size” and has nothing to do with “not touching” or even approaching each other. In particular, a function is asymptotically itself, and 2 is 1 in asymptotic notation; see Big O notation. There is an intermediate concept of asymptotic analysis which somewhat explains how the two terms related.

Lindsay, Pluckrose, Horkheimer, Marcuse unlocked in Secret Sartre

For immediate release. To celebrate the publication of Cynical Theories in the middle of the exciting cultural and academic climate of 2020, Helen Pluckrose, James Lindsay, Herbert Marcuse, and Max Horkheimer are now playable characters in Secret Sartre, the social deduction game of academic intrigue and ideological infighting.

“The intellectual corruption of sense-making institutions, in particular academia, that we have been witnessing in the past few decades is increasingly credited to the post-marxist ideas of Critical Theory in the Frankfurt school, rather than only the traditions of French postmodernism. Players of Secret Sartre have expressed their desire to acknowledge this perceptual shift – to allow different voices to be heard in the game, to open the shared experience to a different narrative – and Max Horkheimer has long been a favourite request among both devoted and casual players,” says game designer Thore Husfeldt.

Print and cut into four cards using the traditional, legitimising norm of rectangle. Use the card backs that come with the basic Secret Sartre game. The secret allegiance of Marcuse and Horkheimer is Postmodernism. The secret allegiance of Pluckrose and Lindsay is Science.

“To complete the Critical Theory faction, we’ve added Herbert Marcuse, father of the New Left, and another central Frankfurt school thinker. Through his advisor Heidegger, he also connects Secret Sartre to that other large totalitarian tradition of the 20th century, Fascism. This also allows us to acknowledge our ludic, ideological, and intellectual debt to the original game.”

To balance the new expansion offering, both Helen Pluckrose and James Lindsay join the quixotic Science faction, championing values such as truth, humanism, evidence, conversation, honesty, and enlightenment. Pluckrose and Lindsay are the authors of Cynical Theories (Pitchstone, 2020) became famous through the Grievance studies affair.

The current expansion to the original 2015 game follows a previous expansion from 2017, which added Jordan B. Peterson and Bret Weinstein to the forces of the Enlightenment.

The game expansion is available as a free download immediately. To unlock Horkheimer for actual play in Secret Sartre requires purchase of Cynical Theories in hardcover or a sizeable donation to New Discourses.

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.


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.


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å .

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: : a chat channel at 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 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 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:
  • Three hour warm-up event Friday 20 September 16-19. ITU will host a 3 hour warm-up event two weeks before NCPC at 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 , 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


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, 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.


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 (, 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

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.


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.


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.


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.


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.


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.)

Excellence in Teaching, ITU 2018

(I’m really proud about having received ITU’s Excellence in Teaching award for 2018. I am first and foremost a teacher, and view education as my most meaningful task. (It’s also the only thing that I am really good at.) Having my work recognised is immensely satisfying.


mads, thore.png

ITU Vice Chancellor Mads Tofte presents the award. 23 September 2018.

Here is the laudation from Vice Chancellor Mads Tofte:

Award for excellence in teaching

Every year, ITU awards a few teachers its Award for Excellence in Teaching. We do so based on what students have said about teachers in their evaluations. It is very difficult to choose, because students say so many positive things about so many different teachers. But we have arrived at the following, one from each of our three departments:

Associate Professor Thore Husfeldt of the Department of Computer Science

During the past year, Thore has been teaching “Algorithm Design”, “Algorithms and Data Structures” and “Foundations of Computing – Algorithms and Data Structures”. Here are some of the things that students write about Thore:

  • Absolute rock star
  • Best lecturer on ITU, hands down
  • Thore makes things, that seemed very complicated when reading the book, seem easy peasy when he explains them at the lectures.
  • Jeg kan godt lide den del af undervisningen, hvor vi ved håndsoprækning skal stemme om, hvilket svar vi tror er rigtigt på et spørgsmål. Typisk gør det, at Thore godt fatter, hvad det er, han skal uddybe.
  • The black board exercises in the lectures are a brilliant break in between the coding and explaining.
  • Very engaged! Obviously very capable and passionate about teaching this subject
  • It is the one class I don’t miss, even if it’s at 8am and that’s because of the quality of the teacher

Superintelligence in SF. Part III: Aftermaths

Part II of a 3-part summary of a 2018 workshop on Superintelligence in SF. See also [Part I: Pathways] and [Part II: Failures].

The third and final part of apocalyptic taxonomy describes the outcome, or aftermath, of the emergence and liberation of artificial superintelligence. The list of scenarios is taken from Tegmark (2018). In my introductory slide I tried to roughly order these scenarios along two axes, depending on the capability of the superintelligence, and the degree of control.



These scenarios are not clearly delineated, nor are they comprehensive. There is a longer description in Chapter 5 of Tegmark (2018). Another summary is at AI Aftermath Scenarios at the Future of Life Institute blog, where you can also find the results of a survey about which scenario to prefer.


Intelligent life on Earth becomes extinct before a superintelligence is ever developed because civilisation brings about its own demise by other means than the AI apocalypse.


Society has chosen deliberate technological regression, so as to forever forestall the development of superintelligence. In particular, people have abandoned and outlawed research and development in relevant technologies, including many discoveries from the industrial and digital age, possibly even the scientific method. This decision be in reaction to a previous near-catastrophic experience with such technology.

Turing Police

Superintelligence has not been developed, and societies have strict control mechanisms that prevent research and development into relevant technologies. This may be enforced by a totalitarian state using the police or universal surveillance.

Tegmark’s own label for this scenario is “1984,” which was universally rejected by the workshop.

Egalitarian Utopia

Society includes humans, some of which are technologically modified, and uploads.
The potential conflict arising from productivity differentials between these groups are avoided by abolishing property rights.

Libertarian Utopia

Society includes humans, some of which may be technologically modified, and uploads. Biological life and machine life have segregated into different zones. The economy is almost entirely driven by the fantastically more efficient uploads. Biological humans peacefully coexist with these zones, benefit from trading with machine zones; the economic, technological, and scientific output of humans is irrelevant.

Gatekeeper AI

A single superintelligence has been designed. The value alignment problem has been resolved in the direction that the superintelligence has one single goal: to prevent the second superingelligence, and to interfere as little as possible with human affairs. This scenario differs from the Turing police scenario in the number of superintellinces actually constructed (0 versus 1) and need not be a police state.


The superintelligence has come about by a gradual modification of modern humans. Thus, there is no conflict between the factions of “existing biological humans” and “the superintelligence” – the latter is simply the descendant life form of the former. “They” are “we” or rather, “our children.” 21st century homo sapiens is long extinct, voluntarily, just as each generation of parents faces extinction.

Enslaved God

The remaining scenarios all assume a superingelligence of vastly superhuman intellect. They differ in how much humans are “in control.”

In the Enslaved God scenario, the safety problems for developing superintelligence (control, value alignment) have been solved. The superingelligence is a willing, benevolent, and competent servant to its human masters.

Protector God

The superintelligence weilds significant power, but remains friendly and discreet, nudging humanity unnoticably into the right direction without being too obvious about it. Humans retain an illusion of control, their lives remaing challenging and feel meaningful.

Benevolent Dictator

The superintelligence is in control, and openly so. The value alignment problem is solved in humanity’s favour, and the superintelligence ensures human flourishing. People are content and entertained. Their lives are free of hardship or even challenge.


The omnipotent superintelligence ensures that humans are fed and safe, maybe even healthy. Human lives are comparable to those of zoo animals, they feel unfree, may be enslaved, and are significantly less happy that modern humans.


The superintelligence has not kept humans around. Humanity is extinct and has left no trace.


Workshop participants quickly observed the large empty space in the lower left corner! In that corner, no superintelligence has been developed, yet the (imagined) superintelligence would be in control.

Other fictional AI tropes are out of scope. In particular the development of indentured mundane artificial intelligences, which may outperform humans in specific cognitive tasks (such as C3P0s language facility or many space ship computers), without otherwise exhibiting superior reasoning skills.